Source code

Revision control

Other Tools

1
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2
* vim: set ts=8 sts=2 et sw=2 tw=80:
3
* This Source Code Form is subject to the terms of the Mozilla Public
4
* License, v. 2.0. If a copy of the MPL was not distributed with this
5
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7
#ifndef js_Fifo_h
8
#define js_Fifo_h
9
10
#include "mozilla/Move.h"
11
12
#include <algorithm>
13
14
#include "js/Vector.h"
15
16
namespace js {
17
18
// A first-in-first-out queue container type. Fifo calls constructors and
19
// destructors of all elements added so non-PODs may be used safely. |Fifo|
20
// stores the first |MinInlineCapacity| elements in-place before resorting to
21
// dynamic allocation.
22
//
23
// T requirements:
24
// - Either movable or copyable.
25
// MinInlineCapacity requirements:
26
// - Must be even.
27
// AllocPolicy:
28
// - see "Allocation policies" in AllocPolicy.h
29
template <typename T, size_t MinInlineCapacity = 0,
30
class AllocPolicy = TempAllocPolicy>
31
class Fifo {
32
static_assert(MinInlineCapacity % 2 == 0, "MinInlineCapacity must be even!");
33
34
protected:
35
// An element A is "younger" than an element B if B was inserted into the
36
// |Fifo| before A was.
37
//
38
// Invariant 1: Every element within |front_| is older than every element
39
// within |rear_|.
40
// Invariant 2: Entries within |front_| are sorted from younger to older.
41
// Invariant 3: Entries within |rear_| are sorted from older to younger.
42
// Invariant 4: If the |Fifo| is not empty, then |front_| is not empty.
43
Vector<T, MinInlineCapacity / 2, AllocPolicy> front_;
44
Vector<T, MinInlineCapacity / 2, AllocPolicy> rear_;
45
46
private:
47
// Maintain invariants after adding or removing entries.
48
void fixup() {
49
if (front_.empty() && !rear_.empty()) {
50
front_.swap(rear_);
51
std::reverse(front_.begin(), front_.end());
52
}
53
}
54
55
public:
56
explicit Fifo(AllocPolicy alloc = AllocPolicy())
57
: front_(alloc), rear_(alloc) {}
58
59
Fifo(Fifo&& rhs)
60
: front_(std::move(rhs.front_)), rear_(std::move(rhs.rear_)) {}
61
62
Fifo& operator=(Fifo&& rhs) {
63
MOZ_ASSERT(&rhs != this, "self-move disallowed");
64
this->~Fifo();
65
new (this) Fifo(std::move(rhs));
66
return *this;
67
}
68
69
Fifo(const Fifo&) = delete;
70
Fifo& operator=(const Fifo&) = delete;
71
72
size_t length() const {
73
MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0); // Invariant 4.
74
return front_.length() + rear_.length();
75
}
76
77
bool empty() const {
78
MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0); // Invariant 4.
79
return front_.empty();
80
}
81
82
// Iterator from oldest to yongest element.
83
struct ConstIterator {
84
const Fifo& self_;
85
size_t idx_;
86
87
ConstIterator(const Fifo& self, size_t idx) : self_(self), idx_(idx) {}
88
89
ConstIterator& operator++() {
90
++idx_;
91
return *this;
92
}
93
94
const T& operator*() const {
95
// Iterate front in reverse, then rear.
96
size_t split = self_.front_.length();
97
return (idx_ < split) ? self_.front_[(split - 1) - idx_]
98
: self_.rear_[idx_ - split];
99
}
100
101
bool operator!=(const ConstIterator& other) const {
102
return (&self_ != &other.self_) || (idx_ != other.idx_);
103
}
104
};
105
106
ConstIterator begin() const { return ConstIterator(*this, 0); }
107
108
ConstIterator end() const { return ConstIterator(*this, length()); }
109
110
// Push an element to the back of the queue. This method can take either a
111
// |const T&| or a |T&&|.
112
template <typename U>
113
MOZ_MUST_USE bool pushBack(U&& u) {
114
if (!rear_.append(std::forward<U>(u))) {
115
return false;
116
}
117
fixup();
118
return true;
119
}
120
121
// Construct a T in-place at the back of the queue.
122
template <typename... Args>
123
MOZ_MUST_USE bool emplaceBack(Args&&... args) {
124
if (!rear_.emplaceBack(std::forward<Args>(args)...)) {
125
return false;
126
}
127
fixup();
128
return true;
129
}
130
131
// Access the element at the front of the queue.
132
T& front() {
133
MOZ_ASSERT(!empty());
134
return front_.back();
135
}
136
const T& front() const {
137
MOZ_ASSERT(!empty());
138
return front_.back();
139
}
140
141
// Remove the front element from the queue.
142
void popFront() {
143
MOZ_ASSERT(!empty());
144
front_.popBack();
145
fixup();
146
}
147
148
// Convenience utility.
149
T popCopyFront() {
150
T ret = front();
151
popFront();
152
return ret;
153
}
154
155
// Clear all elements from the queue.
156
void clear() {
157
front_.clear();
158
rear_.clear();
159
}
160
161
// Clear all elements for which the given predicate returns 'true'. Return
162
// the number of elements removed.
163
template <class Pred>
164
size_t eraseIf(Pred pred) {
165
size_t frontLength = front_.length();
166
front_.eraseIf(pred);
167
size_t erased = frontLength - front_.length();
168
169
size_t rearLength = rear_.length();
170
rear_.eraseIf(pred);
171
erased += rearLength - rear_.length();
172
173
return erased;
174
}
175
176
size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
177
return front_.sizeOfExcludingThis(mallocSizeOf) +
178
rear_.sizeOfExcludingThis(mallocSizeOf);
179
}
180
size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
181
return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
182
}
183
};
184
185
} // namespace js
186
187
#endif /* js_Fifo_h */