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/. */
13 #include "js/Vector.h"
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.
23 // - Either movable or copyable.
24 // MinInlineCapacity requirements:
27 // - see "Allocation policies" in AllocPolicy.h
28 template <typename T
, size_t MinInlineCapacity
= 0,
29 class AllocPolicy
= TempAllocPolicy
>
31 static_assert(MinInlineCapacity
% 2 == 0, "MinInlineCapacity must be even!");
34 // An element A is "younger" than an element B if B was inserted into the
35 // |Fifo| before A was.
37 // Invariant 1: Every element within |front_| is older than every element
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_
;
46 // Maintain invariants after adding or removing entries.
48 if (front_
.empty() && !rear_
.empty()) {
50 std::reverse(front_
.begin(), front_
.end());
55 explicit Fifo(AllocPolicy alloc
= AllocPolicy())
56 : front_(alloc
), rear_(alloc
) {}
59 : front_(std::move(rhs
.front_
)), rear_(std::move(rhs
.rear_
)) {}
61 Fifo
& operator=(Fifo
&& rhs
) {
62 MOZ_ASSERT(&rhs
!= this, "self-move disallowed");
64 new (this) Fifo(std::move(rhs
));
68 Fifo(const Fifo
&) = delete;
69 Fifo
& operator=(const Fifo
&) = delete;
71 size_t length() const {
72 MOZ_ASSERT_IF(rear_
.length() > 0, front_
.length() > 0); // Invariant 4.
73 return front_
.length() + rear_
.length();
77 MOZ_ASSERT_IF(rear_
.length() > 0, front_
.length() > 0); // Invariant 4.
78 return front_
.empty();
81 // Iterator from oldest to yongest element.
82 struct ConstIterator
{
86 ConstIterator(const Fifo
& self
, size_t idx
) : self_(self
), idx_(idx
) {}
88 ConstIterator
& operator++() {
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
];
100 bool operator!=(const ConstIterator
& other
) const {
101 return (&self_
!= &other
.self_
) || (idx_
!= other
.idx_
);
105 ConstIterator
begin() const { return ConstIterator(*this, 0); }
107 ConstIterator
end() const { return ConstIterator(*this, length()); }
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 [[nodiscard
]] bool pushBack(U
&& u
) {
113 if (!rear_
.append(std::forward
<U
>(u
))) {
120 // Construct a T in-place at the back of the queue.
121 template <typename
... Args
>
122 [[nodiscard
]] bool emplaceBack(Args
&&... args
) {
123 if (!rear_
.emplaceBack(std::forward
<Args
>(args
)...)) {
130 // Access the element at the front of the queue.
132 MOZ_ASSERT(!empty());
133 return front_
.back();
135 const T
& front() const {
136 MOZ_ASSERT(!empty());
137 return front_
.back();
140 // Remove the front element from the queue.
142 MOZ_ASSERT(!empty());
147 // Convenience utility.
154 // Clear all elements from the queue.
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();
168 size_t rearLength
= rear_
.length();
170 erased
+= rearLength
- rear_
.length();
176 size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf
) const {
177 return front_
.sizeOfExcludingThis(mallocSizeOf
) +
178 rear_
.sizeOfExcludingThis(mallocSizeOf
);
180 size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf
) const {
181 return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf
);
187 #endif /* js_Fifo_h */