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 256996 858b4f682c5a5367ee10d001c27badb1de887373
parent 256995 7a7febd0dcbe437086acdeee2225f3fe9209e4d1
child 256997 1a1ad27321de3383031cc3fdf38d042ada6c34ee
push id14559
push userphilringnalda@gmail.com
push dateSun, 09 Aug 2015 23:41:14 +0000
treeherderfx-team@0e269a1f1beb [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersterrence
bugs1189490
milestone42.0a1
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',