Bug 1189490 - Part 0: Add a FIFO queue container type to js/public; r=terrence
☠☠ backed out by 91cb27a1be1e ☠ ☠
authorNick Fitzgerald <fitzgen@gmail.com>
Fri, 31 Jul 2015 13:27:44 -0700
changeset 287406 cebec1f7c9dba4fe6d17270ae905108695396ba4
parent 287405 829ee40cf65526c7b1b96b289be9f11d3a9d05f5
child 287407 78f80496c70ac7005fd0ab0de91944f3df672106
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',