common/quiche_circular_deque.h

// Copyright (c) 2019 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef QUICHE_COMMON_QUICHE_CIRCULAR_DEQUE_H_
#define QUICHE_COMMON_QUICHE_CIRCULAR_DEQUE_H_

#include <algorithm>
#include <cstddef>
#include <cstring>
#include <iterator>
#include <memory>
#include <ostream>
#include <type_traits>

#include "common/platform/api/quiche_export.h"
#include "common/platform/api/quiche_logging.h"

namespace quiche {

// QuicheCircularDeque is a STL-style container that is similar to std::deque in
// API and std::vector in capacity management. The goal is to optimize a common
// QUIC use case where we keep adding new elements to the end and removing old
// elements from the beginning, under such scenarios, if the container's size()
// remain relatively stable, QuicheCircularDeque requires little to no memory
// allocations or deallocations.
//
// The implementation, as the name suggests, uses a flat circular buffer to hold
// all elements. At any point in time, either
// a) All elements are placed in a contiguous portion of this buffer, like a
//    c-array, or
// b) Elements are phycially divided into two parts: the first part occupies the
//    end of the buffer and the second part occupies the beginning of the
//    buffer.
//
// Currently, elements can only be pushed or poped from either ends, it can't be
// inserted or erased in the middle.
//
// TODO(wub): Make memory grow/shrink strategies customizable.
template <typename T,
          size_t MinCapacityIncrement = 3,
          typename Allocator = std::allocator<T>>
class QUICHE_NO_EXPORT QuicheCircularDeque {
  using AllocatorTraits = std::allocator_traits<Allocator>;

  // Pointee is either T or const T.
  template <typename Pointee>
  class QUICHE_NO_EXPORT basic_iterator {
    using size_type = typename AllocatorTraits::size_type;

   public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = typename AllocatorTraits::value_type;
    using difference_type = typename AllocatorTraits::difference_type;
    using pointer = Pointee*;
    using reference = Pointee&;

    basic_iterator() = default;

    // A copy constructor if Pointee is T.
    // A conversion from iterator to const_iterator if Pointee is const T.
    basic_iterator(
        const basic_iterator<value_type>& it)  // NOLINT(runtime/explicit)
        : deque_(it.deque_), index_(it.index_) {}

    // A copy assignment if Pointee is T.
    // A assignment from iterator to const_iterator if Pointee is const T.
    basic_iterator& operator=(const basic_iterator<value_type>& it) {
      if (this != &it) {
        deque_ = it.deque_;
        index_ = it.index_;
      }
      return *this;
    }

    reference operator*() const { return *deque_->index_to_address(index_); }
    pointer operator->() const { return deque_->index_to_address(index_); }
    reference operator[](difference_type i) { return *(*this + i); }

    basic_iterator& operator++() {
      Increment();
      return *this;
    }

    basic_iterator operator++(int) {
      basic_iterator result = *this;
      Increment();
      return result;
    }

    basic_iterator operator--() {
      Decrement();
      return *this;
    }

    basic_iterator operator--(int) {
      basic_iterator result = *this;
      Decrement();
      return result;
    }

    friend basic_iterator operator+(const basic_iterator& it,
                                    difference_type delta) {
      basic_iterator result = it;
      result.IncrementBy(delta);
      return result;
    }

    basic_iterator& operator+=(difference_type delta) {
      IncrementBy(delta);
      return *this;
    }

    friend basic_iterator operator-(const basic_iterator& it,
                                    difference_type delta) {
      basic_iterator result = it;
      result.IncrementBy(-delta);
      return result;
    }

    basic_iterator& operator-=(difference_type delta) {
      IncrementBy(-delta);
      return *this;
    }

    friend difference_type operator-(const basic_iterator& lhs,
                                     const basic_iterator& rhs) {
      return lhs.ExternalPosition() - rhs.ExternalPosition();
    }

    friend bool operator==(const basic_iterator& lhs,
                           const basic_iterator& rhs) {
      return lhs.index_ == rhs.index_;
    }

    friend bool operator!=(const basic_iterator& lhs,
                           const basic_iterator& rhs) {
      return !(lhs == rhs);
    }

    friend bool operator<(const basic_iterator& lhs,
                          const basic_iterator& rhs) {
      return lhs.ExternalPosition() < rhs.ExternalPosition();
    }

    friend bool operator<=(const basic_iterator& lhs,
                           const basic_iterator& rhs) {
      return !(lhs > rhs);
    }

    friend bool operator>(const basic_iterator& lhs,
                          const basic_iterator& rhs) {
      return lhs.ExternalPosition() > rhs.ExternalPosition();
    }

    friend bool operator>=(const basic_iterator& lhs,
                           const basic_iterator& rhs) {
      return !(lhs < rhs);
    }

   private:
    basic_iterator(const QuicheCircularDeque* deque, size_type index)
        : deque_(deque), index_(index) {}

    void Increment() {
      QUICHE_DCHECK_LE(ExternalPosition() + 1, deque_->size());
      index_ = deque_->index_next(index_);
    }

    void Decrement() {
      QUICHE_DCHECK_GE(ExternalPosition(), 1u);
      index_ = deque_->index_prev(index_);
    }

    void IncrementBy(difference_type delta) {
      if (delta >= 0) {
        // After increment we are before or at end().
        QUICHE_DCHECK_LE(static_cast<size_type>(ExternalPosition() + delta),
                         deque_->size());
      } else {
        // After decrement we are after or at begin().
        QUICHE_DCHECK_GE(ExternalPosition(), static_cast<size_type>(-delta));
      }
      index_ = deque_->index_increment_by(index_, delta);
    }

    size_type ExternalPosition() const {
      if (index_ >= deque_->begin_) {
        return index_ - deque_->begin_;
      }
      return index_ + deque_->data_capacity() - deque_->begin_;
    }

    friend class QuicheCircularDeque;
    const QuicheCircularDeque* deque_ = nullptr;
    size_type index_ = 0;
  };

 public:
  using allocator_type = typename AllocatorTraits::allocator_type;
  using value_type = typename AllocatorTraits::value_type;
  using size_type = typename AllocatorTraits::size_type;
  using difference_type = typename AllocatorTraits::difference_type;
  using reference = value_type&;
  using const_reference = const value_type&;
  using pointer = typename AllocatorTraits::pointer;
  using const_pointer = typename AllocatorTraits::const_pointer;
  using iterator = basic_iterator<T>;
  using const_iterator = basic_iterator<const T>;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  QuicheCircularDeque() : QuicheCircularDeque(allocator_type()) {}
  explicit QuicheCircularDeque(const allocator_type& alloc)
      : allocator_and_data_(alloc) {}

  QuicheCircularDeque(size_type count,
                      const T& value,
                      const Allocator& alloc = allocator_type())
      : allocator_and_data_(alloc) {
    resize(count, value);
  }

  explicit QuicheCircularDeque(size_type count,
                               const Allocator& alloc = allocator_type())
      : allocator_and_data_(alloc) {
    resize(count);
  }

  template <
      class InputIt,
      typename = std::enable_if_t<std::is_base_of<
          std::input_iterator_tag,
          typename std::iterator_traits<InputIt>::iterator_category>::value>>
  QuicheCircularDeque(InputIt first,
                      InputIt last,
                      const Allocator& alloc = allocator_type())
      : allocator_and_data_(alloc) {
    AssignRange(first, last);
  }

  QuicheCircularDeque(const QuicheCircularDeque& other)
      : QuicheCircularDeque(
            other,
            AllocatorTraits::select_on_container_copy_construction(
                other.allocator_and_data_.allocator())) {}

  QuicheCircularDeque(const QuicheCircularDeque& other,
                      const allocator_type& alloc)
      : allocator_and_data_(alloc) {
    assign(other.begin(), other.end());
  }

  QuicheCircularDeque(QuicheCircularDeque&& other)
      : begin_(other.begin_),
        end_(other.end_),
        allocator_and_data_(std::move(other.allocator_and_data_)) {
    other.begin_ = other.end_ = 0;
    other.allocator_and_data_.data = nullptr;
    other.allocator_and_data_.data_capacity = 0;
  }

  QuicheCircularDeque(QuicheCircularDeque&& other, const allocator_type& alloc)
      : allocator_and_data_(alloc) {
    MoveRetainAllocator(std::move(other));
  }

  QuicheCircularDeque(std::initializer_list<T> init,
                      const allocator_type& alloc = allocator_type())
      : QuicheCircularDeque(init.begin(), init.end(), alloc) {}

  QuicheCircularDeque& operator=(const QuicheCircularDeque& other) {
    if (this == &other) {
      return *this;
    }
    if (AllocatorTraits::propagate_on_container_copy_assignment::value &&
        (allocator_and_data_.allocator() !=
         other.allocator_and_data_.allocator())) {
      // Destroy all current elements and blocks with the current allocator,
      // before switching this to use the allocator propagated from "other".
      DestroyAndDeallocateAll();
      begin_ = end_ = 0;
      allocator_and_data_ =
          AllocatorAndData(other.allocator_and_data_.allocator());
    }
    assign(other.begin(), other.end());
    return *this;
  }

  QuicheCircularDeque& operator=(QuicheCircularDeque&& other) {
    if (this == &other) {
      return *this;
    }
    if (AllocatorTraits::propagate_on_container_move_assignment::value) {
      // Take over the storage of "other", along with its allocator.
      this->~QuicheCircularDeque();
      new (this) QuicheCircularDeque(std::move(other));
    } else {
      MoveRetainAllocator(std::move(other));
    }
    return *this;
  }

  ~QuicheCircularDeque() { DestroyAndDeallocateAll(); }

  void assign(size_type count, const T& value) {
    ClearRetainCapacity();
    reserve(count);
    for (size_t i = 0; i < count; ++i) {
      emplace_back(value);
    }
  }

  template <
      class InputIt,
      typename = std::enable_if_t<std::is_base_of<
          std::input_iterator_tag,
          typename std::iterator_traits<InputIt>::iterator_category>::value>>
  void assign(InputIt first, InputIt last) {
    AssignRange(first, last);
  }

  void assign(std::initializer_list<T> ilist) {
    assign(ilist.begin(), ilist.end());
  }

  reference at(size_type pos) {
    QUICHE_DCHECK(pos < size()) << "pos:" << pos << ", size():" << size();
    size_type index = begin_ + pos;
    if (index < data_capacity()) {
      return *index_to_address(index);
    }
    return *index_to_address(index - data_capacity());
  }

  const_reference at(size_type pos) const {
    return const_cast<QuicheCircularDeque*>(this)->at(pos);
  }

  reference operator[](size_type pos) { return at(pos); }

  const_reference operator[](size_type pos) const { return at(pos); }

  reference front() {
    QUICHE_DCHECK(!empty());
    return *index_to_address(begin_);
  }

  const_reference front() const {
    return const_cast<QuicheCircularDeque*>(this)->front();
  }

  reference back() {
    QUICHE_DCHECK(!empty());
    return *(index_to_address(end_ == 0 ? data_capacity() - 1 : end_ - 1));
  }

  const_reference back() const {
    return const_cast<QuicheCircularDeque*>(this)->back();
  }

  iterator begin() { return iterator(this, begin_); }
  const_iterator begin() const { return const_iterator(this, begin_); }
  const_iterator cbegin() const { return const_iterator(this, begin_); }

  iterator end() { return iterator(this, end_); }
  const_iterator end() const { return const_iterator(this, end_); }
  const_iterator cend() const { return const_iterator(this, end_); }

  reverse_iterator rbegin() { return reverse_iterator(end()); }
  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(end());
  }
  const_reverse_iterator crbegin() const { return rbegin(); }

  reverse_iterator rend() { return reverse_iterator(begin()); }
  const_reverse_iterator rend() const {
    return const_reverse_iterator(begin());
  }
  const_reverse_iterator crend() const { return rend(); }

  size_type capacity() const {
    return data_capacity() == 0 ? 0 : data_capacity() - 1;
  }

  void reserve(size_type new_cap) {
    if (new_cap > capacity()) {
      Relocate(new_cap);
    }
  }

  // Remove all elements. Leave capacity unchanged.
  void clear() { ClearRetainCapacity(); }

  bool empty() const { return begin_ == end_; }

  size_type size() const {
    if (begin_ <= end_) {
      return end_ - begin_;
    }
    return data_capacity() + end_ - begin_;
  }

  void resize(size_type count) { ResizeInternal(count); }

  void resize(size_type count, const value_type& value) {
    ResizeInternal(count, value);
  }

  void push_front(const T& value) { emplace_front(value); }
  void push_front(T&& value) { emplace_front(std::move(value)); }

  template <class... Args>
  reference emplace_front(Args&&... args) {
    MaybeExpandCapacity(1);
    begin_ = index_prev(begin_);
    new (index_to_address(begin_)) T(std::forward<Args>(args)...);
    return front();
  }

  void push_back(const T& value) { emplace_back(value); }
  void push_back(T&& value) { emplace_back(std::move(value)); }

  template <class... Args>
  reference emplace_back(Args&&... args) {
    MaybeExpandCapacity(1);
    new (index_to_address(end_)) T(std::forward<Args>(args)...);
    end_ = index_next(end_);
    return back();
  }

  void pop_front() {
    QUICHE_DCHECK(!empty());
    DestroyByIndex(begin_);
    begin_ = index_next(begin_);
    MaybeShrinkCapacity();
  }

  size_type pop_front_n(size_type count) {
    size_type num_elements_to_pop = std::min(count, size());
    size_type new_begin = index_increment_by(begin_, num_elements_to_pop);
    DestroyRange(begin_, new_begin);
    begin_ = new_begin;
    MaybeShrinkCapacity();
    return num_elements_to_pop;
  }

  void pop_back() {
    QUICHE_DCHECK(!empty());
    end_ = index_prev(end_);
    DestroyByIndex(end_);
    MaybeShrinkCapacity();
  }

  size_type pop_back_n(size_type count) {
    size_type num_elements_to_pop = std::min(count, size());
    size_type new_end = index_increment_by(end_, -num_elements_to_pop);
    DestroyRange(new_end, end_);
    end_ = new_end;
    MaybeShrinkCapacity();
    return num_elements_to_pop;
  }

  void swap(QuicheCircularDeque& other) {
    using std::swap;
    swap(begin_, other.begin_);
    swap(end_, other.end_);

    if (AllocatorTraits::propagate_on_container_swap::value) {
      swap(allocator_and_data_, other.allocator_and_data_);
    } else {
      // When propagate_on_container_swap is false, it is undefined behavior, by
      // c++ standard, to swap between two AllocatorAwareContainer(s) with
      // unequal allocators.
      QUICHE_DCHECK(get_allocator() == other.get_allocator())
          << "Undefined swap behavior";
      swap(allocator_and_data_.data, other.allocator_and_data_.data);
      swap(allocator_and_data_.data_capacity,
           other.allocator_and_data_.data_capacity);
    }
  }

  friend void swap(QuicheCircularDeque& lhs, QuicheCircularDeque& rhs) {
    lhs.swap(rhs);
  }

  allocator_type get_allocator() const {
    return allocator_and_data_.allocator();
  }

  friend bool operator==(const QuicheCircularDeque& lhs,
                         const QuicheCircularDeque& rhs) {
    return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
  }

  friend bool operator!=(const QuicheCircularDeque& lhs,
                         const QuicheCircularDeque& rhs) {
    return !(lhs == rhs);
  }

  friend QUICHE_NO_EXPORT std::ostream& operator<<(
      std::ostream& os,
      const QuicheCircularDeque& dq) {
    os << "{";
    for (size_type pos = 0; pos != dq.size(); ++pos) {
      if (pos != 0) {
        os << ",";
      }
      os << " " << dq[pos];
    }
    os << " }";
    return os;
  }

 private:
  void MoveRetainAllocator(QuicheCircularDeque&& other) {
    if (get_allocator() == other.get_allocator()) {
      // Take over the storage of "other", with which we share an allocator.
      DestroyAndDeallocateAll();

      begin_ = other.begin_;
      end_ = other.end_;
      allocator_and_data_.data = other.allocator_and_data_.data;
      allocator_and_data_.data_capacity =
          other.allocator_and_data_.data_capacity;

      other.begin_ = other.end_ = 0;
      other.allocator_and_data_.data = nullptr;
      other.allocator_and_data_.data_capacity = 0;
    } else {
      // We cannot take over of the storage from "other", since it has a
      // different allocator; we're stuck move-assigning elements individually.
      ClearRetainCapacity();
      for (auto& elem : other) {
        push_back(std::move(elem));
      }
      other.clear();
    }
  }

  template <
      typename InputIt,
      typename = std::enable_if_t<std::is_base_of<
          std::input_iterator_tag,
          typename std::iterator_traits<InputIt>::iterator_category>::value>>
  void AssignRange(InputIt first, InputIt last) {
    ClearRetainCapacity();
    if (std::is_base_of<
            std::random_access_iterator_tag,
            typename std::iterator_traits<InputIt>::iterator_category>::value) {
      reserve(std::distance(first, last));
    }
    for (; first != last; ++first) {
      emplace_back(*first);
    }
  }

  // WARNING: begin_, end_ and allocator_and_data_ are not modified.
  void DestroyAndDeallocateAll() {
    DestroyRange(begin_, end_);

    if (data_capacity() > 0) {
      QUICHE_DCHECK_NE(nullptr, allocator_and_data_.data);
      AllocatorTraits::deallocate(allocator_and_data_.allocator(),
                                  allocator_and_data_.data, data_capacity());
    }
  }

  void ClearRetainCapacity() {
    DestroyRange(begin_, end_);
    begin_ = end_ = 0;
  }

  void MaybeShrinkCapacity() {
    // TODO(wub): Implement a storage policy that actually shrinks.
  }

  void MaybeExpandCapacity(size_t num_additional_elements) {
    size_t new_size = size() + num_additional_elements;
    if (capacity() >= new_size) {
      return;
    }

    // The minimum amount of additional capacity to grow.
    size_t min_additional_capacity =
        std::max(MinCapacityIncrement, capacity() / 4);
    size_t new_capacity =
        std::max(new_size, capacity() + min_additional_capacity);

    Relocate(new_capacity);
  }

  void Relocate(size_t new_capacity) {
    const size_t num_elements = size();
    QUICHE_DCHECK_GT(new_capacity, num_elements)
        << "new_capacity:" << new_capacity << ", num_elements:" << num_elements;

    size_t new_data_capacity = new_capacity + 1;
    pointer new_data = AllocatorTraits::allocate(
        allocator_and_data_.allocator(), new_data_capacity);

    if (begin_ < end_) {
      // Not wrapped.
      RelocateUnwrappedRange(begin_, end_, new_data);
    } else if (begin_ > end_) {
      // Wrapped.
      const size_t num_elements_before_wrap = data_capacity() - begin_;
      RelocateUnwrappedRange(begin_, data_capacity(), new_data);
      RelocateUnwrappedRange(0, end_, new_data + num_elements_before_wrap);
    }

    if (data_capacity()) {
      AllocatorTraits::deallocate(allocator_and_data_.allocator(),
                                  allocator_and_data_.data, data_capacity());
    }

    allocator_and_data_.data = new_data;
    allocator_and_data_.data_capacity = new_data_capacity;
    begin_ = 0;
    end_ = num_elements;
  }

  template <typename T_ = T>
  typename std::enable_if<std::is_trivially_copyable<T_>::value, void>::type
  RelocateUnwrappedRange(size_type begin, size_type end, pointer dest) const {
    QUICHE_DCHECK_LE(begin, end) << "begin:" << begin << ", end:" << end;
    pointer src = index_to_address(begin);
    QUICHE_DCHECK_NE(src, nullptr);
    memcpy(dest, src, sizeof(T) * (end - begin));
    DestroyRange(begin, end);
  }

  template <typename T_ = T>
  typename std::enable_if<!std::is_trivially_copyable<T_>::value &&
                              std::is_move_constructible<T_>::value,
                          void>::type
  RelocateUnwrappedRange(size_type begin, size_type end, pointer dest) const {
    QUICHE_DCHECK_LE(begin, end) << "begin:" << begin << ", end:" << end;
    pointer src = index_to_address(begin);
    pointer src_end = index_to_address(end);
    while (src != src_end) {
      new (dest) T(std::move(*src));
      DestroyByAddress(src);
      ++dest;
      ++src;
    }
  }

  template <typename T_ = T>
  typename std::enable_if<!std::is_trivially_copyable<T_>::value &&
                              !std::is_move_constructible<T_>::value,
                          void>::type
  RelocateUnwrappedRange(size_type begin, size_type end, pointer dest) const {
    QUICHE_DCHECK_LE(begin, end) << "begin:" << begin << ", end:" << end;
    pointer src = index_to_address(begin);
    pointer src_end = index_to_address(end);
    while (src != src_end) {
      new (dest) T(*src);
      DestroyByAddress(src);
      ++dest;
      ++src;
    }
  }

  template <class... U>
  void ResizeInternal(size_type count, U&&... u) {
    if (count > size()) {
      // Expanding.
      MaybeExpandCapacity(count - size());
      while (size() < count) {
        emplace_back(std::forward<U>(u)...);
      }
    } else {
      // Most likely shrinking. No-op if count == size().
      size_type new_end = (begin_ + count) % data_capacity();
      DestroyRange(new_end, end_);
      end_ = new_end;

      MaybeShrinkCapacity();
    }
  }

  void DestroyRange(size_type begin, size_type end) const {
    if (std::is_trivially_destructible<T>::value) {
      return;
    }
    if (end >= begin) {
      DestroyUnwrappedRange(begin, end);
    } else {
      DestroyUnwrappedRange(begin, data_capacity());
      DestroyUnwrappedRange(0, end);
    }
  }

  // Should only be called from DestroyRange.
  void DestroyUnwrappedRange(size_type begin, size_type end) const {
    QUICHE_DCHECK_LE(begin, end) << "begin:" << begin << ", end:" << end;
    for (; begin != end; ++begin) {
      DestroyByIndex(begin);
    }
  }

  void DestroyByIndex(size_type index) const {
    DestroyByAddress(index_to_address(index));
  }

  void DestroyByAddress(pointer address) const {
    if (std::is_trivially_destructible<T>::value) {
      return;
    }
    address->~T();
  }

  size_type data_capacity() const { return allocator_and_data_.data_capacity; }

  pointer index_to_address(size_type index) const {
    return allocator_and_data_.data + index;
  }

  size_type index_prev(size_type index) const {
    return index == 0 ? data_capacity() - 1 : index - 1;
  }

  size_type index_next(size_type index) const {
    return index == data_capacity() - 1 ? 0 : index + 1;
  }

  size_type index_increment_by(size_type index, difference_type delta) const {
    if (delta == 0) {
      return index;
    }

    QUICHE_DCHECK_LT(static_cast<size_type>(std::abs(delta)), data_capacity());
    return (index + data_capacity() + delta) % data_capacity();
  }

  // Empty base-class optimization: bundle storage for our allocator together
  // with the fields we had to store anyway, via inheriting from the allocator,
  // so this allocator instance doesn't consume any storage when its type has no
  // data members.
  struct AllocatorAndData : private allocator_type {
    explicit AllocatorAndData(const allocator_type& alloc)
        : allocator_type(alloc) {}

    const allocator_type& allocator() const { return *this; }
    allocator_type& allocator() { return *this; }

    pointer data = nullptr;
    size_type data_capacity = 0;
  };

  size_type begin_ = 0;
  size_type end_ = 0;
  AllocatorAndData allocator_and_data_;
};

}  // namespace quiche

#endif  // QUICHE_COMMON_QUICHE_CIRCULAR_DEQUE_H_