tor-browser

Fifo.h (5688B)

---

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* 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 <algorithm>
#include <utility>

#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
//
// The vector template description is variadic to handle the differences
// between GCVector and Vector in template parameters.
template <typename T, size_t MinInlineCapacity = 0,
         class AllocPolicy = TempAllocPolicy,
         template <typename, size_t, class, typename...> class VectorType =
             Vector>
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 older 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.
 VectorType<T, MinInlineCapacity / 2, AllocPolicy> front_;
 VectorType<T, MinInlineCapacity / 2, AllocPolicy> rear_;

private:
 // Maintain invariants after adding or removing entries.
 void fixup() {
   if (front_.empty() && !rear_.empty()) {
     front_.swap(rear_);
     std::reverse(front_.begin(), front_.end());
   }
 }

public:
 explicit Fifo(AllocPolicy alloc = AllocPolicy())
     : front_(alloc), rear_(alloc) {}

 Fifo(Fifo&& rhs)
     : front_(std::move(rhs.front_)), rear_(std::move(rhs.rear_)) {}

 Fifo& operator=(Fifo&& rhs) {
   MOZ_ASSERT(&rhs != this, "self-move disallowed");
   this->~Fifo();
   new (this) Fifo(std::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();
 }

 // Iterator from oldest to yongest element.
 struct ConstIterator {
   const Fifo& self_;
   size_t idx_;

   ConstIterator(const Fifo& self, size_t idx) : self_(self), idx_(idx) {}

   ConstIterator& operator++() {
     ++idx_;
     return *this;
   }

   const T& operator*() const {
     // Iterate front in reverse, then rear.
     size_t split = self_.front_.length();
     return (idx_ < split) ? self_.front_[(split - 1) - idx_]
                           : self_.rear_[idx_ - split];
   }

   bool operator!=(const ConstIterator& other) const {
     return (&self_ != &other.self_) || (idx_ != other.idx_);
   }
 };

 ConstIterator begin() const { return ConstIterator(*this, 0); }

 ConstIterator end() const { return ConstIterator(*this, length()); }

 // Push an element to the back of the queue. This method can take either a
 // |const T&| or a |T&&|.
 template <typename U>
 [[nodiscard]] bool pushBack(U&& u) {
   if (!rear_.append(std::forward<U>(u))) {
     return false;
   }
   fixup();
   return true;
 }

 // Construct a T in-place at the back of the queue.
 template <typename... Args>
 [[nodiscard]] bool emplaceBack(Args&&... args) {
   if (!rear_.emplaceBack(std::forward<Args>(args)...)) {
     return false;
   }
   fixup();
   return true;
 }

 // Construct a T in-place at the front of the queue,
 // making it the next to be popped off.
 template <typename... Args>
 [[nodiscard]] bool emplaceFront(Args&&... args) {
   return front_.emplaceBack(std::forward<Args>(args)...);
 }

 // 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.
 void popFront() {
   MOZ_ASSERT(!empty());
   front_.popBack();
   fixup();
 }

 // Convenience utility.
 T popCopyFront() {
   T ret = front();
   popFront();
   return ret;
 }

 // Clear all elements from the queue.
 void clear() {
   front_.clear();
   rear_.clear();
 }

 // Clear all elements for which the given predicate returns 'true'. Return
 // the number of elements removed.
 template <class Pred>
 size_t eraseIf(Pred pred) {
   size_t frontLength = front_.length();
   front_.eraseIf(pred);
   size_t erased = frontLength - front_.length();

   size_t rearLength = rear_.length();
   rear_.eraseIf(pred);
   erased += rearLength - rear_.length();

   fixup();
   return erased;
 }

 size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
   return front_.sizeOfExcludingThis(mallocSizeOf) +
          rear_.sizeOfExcludingThis(mallocSizeOf);
 }
 size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
   return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
 }
};

}  // namespace js

#endif /* js_Fifo_h */