Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
       2             :  * vim: set ts=8 sts=4 et sw=4 tw=99:
       3             :  * This Source Code Form is subject to the terms of the Mozilla Public
       4             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       5             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
       6             : 
       7             : #ifndef js_Fifo_h
       8             : #define js_Fifo_h
       9             : 
      10             : #include "mozilla/Move.h"
      11             : 
      12             : #include "js/Utility.h"
      13             : #include "js/Vector.h"
      14             : 
      15             : namespace js {
      16             : 
      17             : // A first-in-first-out queue container type. Fifo calls constructors and
      18             : // destructors of all elements added so non-PODs may be used safely. |Fifo|
      19             : // stores the first |MinInlineCapacity| elements in-place before resorting to
      20             : // dynamic allocation.
      21             : //
      22             : // T requirements:
      23             : //  - Either movable or copyable.
      24             : // MinInlineCapacity requirements:
      25             : //  - Must be even.
      26             : // AllocPolicy:
      27             : //  - see "Allocation policies" in AllocPolicy.h
      28             : template <typename T,
      29             :           size_t MinInlineCapacity = 0,
      30             :           class AllocPolicy = TempAllocPolicy>
      31           0 : class Fifo
      32             : {
      33             :     static_assert(MinInlineCapacity % 2 == 0, "MinInlineCapacity must be even!");
      34             : 
      35             :   protected:
      36             :     // An element A is "younger" than an element B if B was inserted into the
      37             :     // |Fifo| before A was.
      38             :     //
      39             :     // Invariant 1: Every element within |front_| is older than every element
      40             :     // within |rear_|.
      41             :     // Invariant 2: Entries within |front_| are sorted from younger to older.
      42             :     // Invariant 3: Entries within |rear_| are sorted from older to younger.
      43             :     // Invariant 4: If the |Fifo| is not empty, then |front_| is not empty.
      44             :     Vector<T, MinInlineCapacity / 2, AllocPolicy> front_;
      45             :     Vector<T, MinInlineCapacity / 2, AllocPolicy> rear_;
      46             : 
      47             :   private:
      48             :     // Maintain invariants after adding or removing entries.
      49           0 :     bool fixup() {
      50           0 :         if (!front_.empty())
      51           0 :             return true;
      52             : 
      53           0 :         if (!front_.reserve(rear_.length()))
      54           0 :             return false;
      55             : 
      56           0 :         while (!rear_.empty()) {
      57           0 :             front_.infallibleAppend(mozilla::Move(rear_.back()));
      58           0 :             rear_.popBack();
      59             :         }
      60             : 
      61           0 :         return true;
      62             :     }
      63             : 
      64             :   public:
      65           0 :     explicit Fifo(AllocPolicy alloc = AllocPolicy())
      66             :         : front_(alloc)
      67           0 :         , rear_(alloc)
      68           0 :     { }
      69             : 
      70             :     Fifo(Fifo&& rhs)
      71             :         : front_(mozilla::Move(rhs.front_))
      72             :         , rear_(mozilla::Move(rhs.rear_))
      73             :     { }
      74             : 
      75             :     Fifo& operator=(Fifo&& rhs) {
      76             :         MOZ_ASSERT(&rhs != this, "self-move disallowed");
      77             :         this->~Fifo();
      78             :         new (this) Fifo(mozilla::Move(rhs));
      79             :         return *this;
      80             :     }
      81             : 
      82             :     Fifo(const Fifo&) = delete;
      83             :     Fifo& operator=(const Fifo&) = delete;
      84             : 
      85           0 :     size_t length() const {
      86           0 :         MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0); // Invariant 4.
      87           0 :         return front_.length() + rear_.length();
      88             :     }
      89             : 
      90           0 :     bool empty() const {
      91           0 :         MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0); // Invariant 4.
      92           0 :         return front_.empty();
      93             :     }
      94             : 
      95             :     // Push an element to the back of the queue. This method can take either a
      96             :     // |const T&| or a |T&&|.
      97             :     template <typename U>
      98             :     MOZ_MUST_USE bool pushBack(U&& u) {
      99             :         if (!rear_.append(mozilla::Forward<U>(u)))
     100             :             return false;
     101             :         if (!fixup()) {
     102             :             rear_.popBack();
     103             :             return false;
     104             :         }
     105             :         return true;
     106             :     }
     107             : 
     108             :     // Construct a T in-place at the back of the queue.
     109             :     template <typename... Args>
     110           0 :     MOZ_MUST_USE bool emplaceBack(Args&&... args) {
     111           0 :         if (!rear_.emplaceBack(mozilla::Forward<Args>(args)...))
     112           0 :             return false;
     113           0 :         if (!fixup()) {
     114           0 :             rear_.popBack();
     115           0 :             return false;
     116             :         }
     117           0 :         return true;
     118             :     }
     119             : 
     120             :     // Access the element at the front of the queue.
     121           0 :     T& front() {
     122           0 :         MOZ_ASSERT(!empty());
     123           0 :         return front_.back();
     124             :     }
     125             :     const T& front() const {
     126             :         MOZ_ASSERT(!empty());
     127             :         return front_.back();
     128             :     }
     129             : 
     130             :     // Remove the front element from the queue.
     131           0 :     MOZ_MUST_USE bool popFront() {
     132           0 :         MOZ_ASSERT(!empty());
     133           0 :         T t(mozilla::Move(front()));
     134           0 :         front_.popBack();
     135           0 :         if (!fixup()) {
     136             :             // Attempt to remain in a valid state by reinserting the element
     137             :             // back at the front. If we can't remain in a valid state in the
     138             :             // face of OOMs, crash.
     139           0 :             AutoEnterOOMUnsafeRegion oomUnsafe;
     140           0 :             if (!front_.append(mozilla::Move(t)))
     141           0 :                 oomUnsafe.crash("js::Fifo::popFront");
     142           0 :             return false;
     143             :         }
     144           0 :         return true;
     145             :     }
     146             : 
     147             :     // Clear all elements from the queue.
     148           0 :     void clear() {
     149           0 :         front_.clear();
     150           0 :         rear_.clear();
     151           0 :     }
     152             : };
     153             : 
     154             : } // namespace js
     155             : 
     156             : #endif /* js_Fifo_h */