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 */