src/ds/Fifo.h

/* -*- 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
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 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.
  Vector<T, MinInlineCapacity / 2, AllocPolicy> front_;
  Vector<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>
  MOZ_MUST_USE 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>
  MOZ_MUST_USE bool emplaceBack(Args&&... args) {
    if (!rear_.emplaceBack(std::forward<Args>(args)...)) {
      return false;
    }
    fixup();
    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.
  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 */