summaryrefslogtreecommitdiffstats
path: root/js/src/ds/Fifo.h
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/ds/Fifo.h')
-rw-r--r--js/src/ds/Fifo.h156
1 files changed, 156 insertions, 0 deletions
diff --git a/js/src/ds/Fifo.h b/js/src/ds/Fifo.h
new file mode 100644
index 000000000..84851ac94
--- /dev/null
+++ b/js/src/ds/Fifo.h
@@ -0,0 +1,156 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef js_Fifo_h
+#define js_Fifo_h
+
+#include "mozilla/Move.h"
+
+#include "js/Utility.h"
+#include "js/Vector.h"
+
+namespace js {
+
+// A first-in-first-out queue container type. Fifo calls constructors and
+// destructors of all elements added so non-PODs may be used safely. |Fifo|
+// stores the first |MinInlineCapacity| elements in-place before resorting to
+// dynamic allocation.
+//
+// T requirements:
+// - Either movable or copyable.
+// MinInlineCapacity requirements:
+// - Must be even.
+// AllocPolicy:
+// - see "Allocation policies" in AllocPolicy.h
+template <typename T,
+ size_t MinInlineCapacity = 0,
+ class AllocPolicy = TempAllocPolicy>
+class Fifo
+{
+ static_assert(MinInlineCapacity % 2 == 0, "MinInlineCapacity must be even!");
+
+ protected:
+ // An element A is "younger" than an element B if B was inserted into the
+ // |Fifo| before A was.
+ //
+ // Invariant 1: Every element within |front_| is older than every element
+ // within |rear_|.
+ // Invariant 2: Entries within |front_| are sorted from younger to older.
+ // Invariant 3: Entries within |rear_| are sorted from older to younger.
+ // Invariant 4: If the |Fifo| is not empty, then |front_| is not empty.
+ Vector<T, MinInlineCapacity / 2, AllocPolicy> front_;
+ Vector<T, MinInlineCapacity / 2, AllocPolicy> rear_;
+
+ private:
+ // Maintain invariants after adding or removing entries.
+ bool fixup() {
+ if (!front_.empty())
+ return true;
+
+ if (!front_.reserve(rear_.length()))
+ return false;
+
+ while (!rear_.empty()) {
+ front_.infallibleAppend(mozilla::Move(rear_.back()));
+ rear_.popBack();
+ }
+
+ return true;
+ }
+
+ public:
+ explicit Fifo(AllocPolicy alloc = AllocPolicy())
+ : front_(alloc)
+ , rear_(alloc)
+ { }
+
+ Fifo(Fifo&& rhs)
+ : front_(mozilla::Move(rhs.front_))
+ , rear_(mozilla::Move(rhs.rear_))
+ { }
+
+ Fifo& operator=(Fifo&& rhs) {
+ MOZ_ASSERT(&rhs != this, "self-move disallowed");
+ this->~Fifo();
+ new (this) Fifo(mozilla::Move(rhs));
+ return *this;
+ }
+
+ Fifo(const Fifo&) = delete;
+ Fifo& operator=(const Fifo&) = delete;
+
+ size_t length() const {
+ MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0); // Invariant 4.
+ return front_.length() + rear_.length();
+ }
+
+ bool empty() const {
+ MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0); // Invariant 4.
+ return front_.empty();
+ }
+
+ // Push an element to the back of the queue. This method can take either a
+ // |const T&| or a |T&&|.
+ template <typename U>
+ MOZ_MUST_USE bool pushBack(U&& u) {
+ if (!rear_.append(mozilla::Forward<U>(u)))
+ return false;
+ if (!fixup()) {
+ rear_.popBack();
+ return false;
+ }
+ return true;
+ }
+
+ // Construct a T in-place at the back of the queue.
+ template <typename... Args>
+ MOZ_MUST_USE bool emplaceBack(Args&&... args) {
+ if (!rear_.emplaceBack(mozilla::Forward<Args>(args)...))
+ return false;
+ if (!fixup()) {
+ rear_.popBack();
+ return false;
+ }
+ return true;
+ }
+
+ // Access the element at the front of the queue.
+ T& front() {
+ MOZ_ASSERT(!empty());
+ return front_.back();
+ }
+ const T& front() const {
+ MOZ_ASSERT(!empty());
+ return front_.back();
+ }
+
+ // Remove the front element from the queue.
+ MOZ_MUST_USE bool popFront() {
+ MOZ_ASSERT(!empty());
+ T t(mozilla::Move(front()));
+ front_.popBack();
+ if (!fixup()) {
+ // Attempt to remain in a valid state by reinserting the element
+ // back at the front. If we can't remain in a valid state in the
+ // face of OOMs, crash.
+ AutoEnterOOMUnsafeRegion oomUnsafe;
+ if (!front_.append(mozilla::Move(t)))
+ oomUnsafe.crash("js::Fifo::popFront");
+ return false;
+ }
+ return true;
+ }
+
+ // Clear all elements from the queue.
+ void clear() {
+ front_.clear();
+ rear_.clear();
+ }
+};
+
+} // namespace js
+
+#endif /* js_Fifo_h */