Bug 1189490 - Part 0: Add a FIFO queue container type to js/public; r=terrence
☠☠ backed out by af32792fe260 ☠ ☠
authorNick Fitzgerald <fitzgen@gmail.com>
Sat, 08 Aug 2015 15:19:52 -0700
changeset 288627 858b4f682c5a5367ee10d001c27badb1de887373
parent 288626 7a7febd0dcbe437086acdeee2225f3fe9209e4d1
child 288628 1a1ad27321de3383031cc3fdf38d042ada6c34ee
push id5067
push userraliiev@mozilla.com
push dateMon, 21 Sep 2015 14:04:52 +0000
treeherdermozilla-beta@14221ffe5b2f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersterrence
bugs1189490
milestone42.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1189490 - Part 0: Add a FIFO queue container type to js/public; r=terrence
js/public/Fifo.h
js/src/moz.build
new file mode 100644
--- /dev/null
+++ b/js/public/Fifo.h
@@ -0,0 +1,154 @@
+/* -*- 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/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 younger 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>
+    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>
+    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.
+    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.
+            if (!front_.append(mozilla::Move(t)))
+                CrashAtUnhandlableOOM("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 */
--- a/js/src/moz.build
+++ b/js/src/moz.build
@@ -103,16 +103,17 @@ EXPORTS += [
 EXPORTS.js += [
     '../public/CallArgs.h',
     '../public/CallNonGenericMethod.h',
     '../public/CharacterEncoding.h',
     '../public/Class.h',
     '../public/Conversions.h',
     '../public/Date.h',
     '../public/Debug.h',
+    '../public/Fifo.h',
     '../public/GCAPI.h',
     '../public/HashTable.h',
     '../public/HeapAPI.h',
     '../public/Id.h',
     '../public/LegacyIntTypes.h',
     '../public/MemoryMetrics.h',
     '../public/Principals.h',
     '../public/ProfilingFrameIterator.h',