js/src/ds/Fifo.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   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 <algorithm>
  11 #include <utility>
  12
  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, size_t MinInlineCapacity = 0,
  29           class AllocPolicy = TempAllocPolicy>
  30 class Fifo {
  31   static_assert(MinInlineCapacity % 2 == 0, "MinInlineCapacity must be even!");
  32
  33  protected:
  34   // An element A is "younger" than an element B if B was inserted into the
  35   // |Fifo| before A was.
  36   //
  37   // Invariant 1: Every element within |front_| is older than every element
  38   // within |rear_|.
  39   // Invariant 2: Entries within |front_| are sorted from younger to older.
  40   // Invariant 3: Entries within |rear_| are sorted from older to younger.
  41   // Invariant 4: If the |Fifo| is not empty, then |front_| is not empty.
  42   Vector<T, MinInlineCapacity / 2, AllocPolicy> front_;
  43   Vector<T, MinInlineCapacity / 2, AllocPolicy> rear_;
  44
  45  private:
  46   // Maintain invariants after adding or removing entries.
  47   void fixup() {
  48     if (front_.empty() && !rear_.empty()) {
  49       front_.swap(rear_);
  50       std::reverse(front_.begin(), front_.end());
  51     }
  52   }
  53
  54  public:
  55   explicit Fifo(AllocPolicy alloc = AllocPolicy())
  56       : front_(alloc), rear_(alloc) {}
  57
  58   Fifo(Fifo&& rhs)
  59       : front_(std::move(rhs.front_)), rear_(std::move(rhs.rear_)) {}
  60
  61   Fifo& operator=(Fifo&& rhs) {
  62     MOZ_ASSERT(&rhs != this, "self-move disallowed");
  63     this->~Fifo();
  64     new (this) Fifo(std::move(rhs));
  65     return *this;
  66   }
  67
  68   Fifo(const Fifo&) = delete;
  69   Fifo& operator=(const Fifo&) = delete;
  70
  71   size_t length() const {
  72     MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0);  // Invariant 4.
  73     return front_.length() + rear_.length();
  74   }
  75
  76   bool empty() const {
  77     MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0);  // Invariant 4.
  78     return front_.empty();
  79   }
  80
  81   // Iterator from oldest to yongest element.
  82   struct ConstIterator {
  83     const Fifo& self_;
  84     size_t idx_;
  85
  86     ConstIterator(const Fifo& self, size_t idx) : self_(self), idx_(idx) {}
  87
  88     ConstIterator& operator++() {
  89       ++idx_;
  90       return *this;
  91     }
  92
  93     const T& operator*() const {
  94       // Iterate front in reverse, then rear.
  95       size_t split = self_.front_.length();
  96       return (idx_ < split) ? self_.front_[(split - 1) - idx_]
  97                             : self_.rear_[idx_ - split];
  98     }
  99
 100     bool operator!=(const ConstIterator& other) const {
 101       return (&self_ != &other.self_) || (idx_ != other.idx_);
 102     }
 103   };
 104
 105   ConstIterator begin() const { return ConstIterator(*this, 0); }
 106
 107   ConstIterator end() const { return ConstIterator(*this, length()); }
 108
 109   // Push an element to the back of the queue. This method can take either a
 110   // |const T&| or a |T&&|.
 111   template <typename U>
 112   [[nodiscard]] bool pushBack(U&& u) {
 113     if (!rear_.append(std::forward<U>(u))) {
 114       return false;
 115     }
 116     fixup();
 117     return true;
 118   }
 119
 120   // Construct a T in-place at the back of the queue.
 121   template <typename... Args>
 122   [[nodiscard]] bool emplaceBack(Args&&... args) {
 123     if (!rear_.emplaceBack(std::forward<Args>(args)...)) {
 124       return false;
 125     }
 126     fixup();
 127     return true;
 128   }
 129
 130   // Access the element at the front of the queue.
 131   T& front() {
 132     MOZ_ASSERT(!empty());
 133     return front_.back();
 134   }
 135   const T& front() const {
 136     MOZ_ASSERT(!empty());
 137     return front_.back();
 138   }
 139
 140   // Remove the front element from the queue.
 141   void popFront() {
 142     MOZ_ASSERT(!empty());
 143     front_.popBack();
 144     fixup();
 145   }
 146
 147   // Convenience utility.
 148   T popCopyFront() {
 149     T ret = front();
 150     popFront();
 151     return ret;
 152   }
 153
 154   // Clear all elements from the queue.
 155   void clear() {
 156     front_.clear();
 157     rear_.clear();
 158   }
 159
 160   // Clear all elements for which the given predicate returns 'true'. Return
 161   // the number of elements removed.
 162   template <class Pred>
 163   size_t eraseIf(Pred pred) {
 164     size_t frontLength = front_.length();
 165     front_.eraseIf(pred);
 166     size_t erased = frontLength - front_.length();
 167
 168     size_t rearLength = rear_.length();
 169     rear_.eraseIf(pred);
 170     erased += rearLength - rear_.length();
 171
 172     fixup();
 173     return erased;
 174   }
 175
 176   size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 177     return front_.sizeOfExcludingThis(mallocSizeOf) +
 178            rear_.sizeOfExcludingThis(mallocSizeOf);
 179   }
 180   size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 181     return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
 182   }
 183 };
 184
 185 }  // namespace js
 186
 187 #endif /* js_Fifo_h */