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