chromium/net/third_party/quiche/src/quiche/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 "quiche/common/platform/api/quiche_export.h"
#include "quiche/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() : … { … }
  explicit QuicheCircularDeque(const allocator_type& alloc)
      : … { … }

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

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

  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) { … }

  QuicheCircularDeque(const QuicheCircularDeque& other)
      : … { … }

  QuicheCircularDeque(const QuicheCircularDeque& other,
                      const allocator_type& alloc)
      : … { … }

  QuicheCircularDeque(QuicheCircularDeque&& other)
      : … { … }

  QuicheCircularDeque(QuicheCircularDeque&& other, const allocator_type& alloc)
      : … { … }

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

  QuicheCircularDeque& operator=(const QuicheCircularDeque& other) { … }

  QuicheCircularDeque& operator=(QuicheCircularDeque&& other) { … }

  ~QuicheCircularDeque() { … }

  void assign(size_type count, const T& 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) { … }

  void assign(std::initializer_list<T> ilist) { … }

  reference at(size_type pos) { … }

  const_reference at(size_type pos) const { … }

  reference operator[](size_type pos) { … }

  const_reference operator[](size_type pos) const { … }

  reference front() { … }

  const_reference front() const { … }

  reference back() { … }

  const_reference back() const { … }

  iterator begin() { … }
  const_iterator begin() const { … }
  const_iterator cbegin() const { … }

  iterator end() { … }
  const_iterator end() const { … }
  const_iterator cend() const { … }

  reverse_iterator rbegin() { … }
  const_reverse_iterator rbegin() const { … }
  const_reverse_iterator crbegin() const { … }

  reverse_iterator rend() { … }
  const_reverse_iterator rend() const { … }
  const_reverse_iterator crend() const { … }

  size_type capacity() const { … }

  void reserve(size_type new_cap) { … }

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

  bool empty() const { … }

  size_type size() const { … }

  void resize(size_type count) { … }

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

  void push_front(const T& value) { … }
  void push_front(T&& value) { … }

  template <class... Args>
  reference emplace_front(Args&&... args) { … }

  void push_back(const T& value) { … }
  void push_back(T&& value) { … }

  template <class... Args>
  reference emplace_back(Args&&... args) { … }

  void pop_front() { … }

  size_type pop_front_n(size_type count) { … }

  void pop_back() { … }

  size_type pop_back_n(size_type count) { … }

  void swap(QuicheCircularDeque& other) { … }

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

  allocator_type get_allocator() const { … }

  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) { … }

  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) { … }

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

  void ClearRetainCapacity() { … }

  void MaybeShrinkCapacity() { … }

  void MaybeExpandCapacity(size_t num_additional_elements) { … }

  void Relocate(size_t new_capacity) { … }

  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 { … }

  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 { … }

  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 { … }

  template <class... U>
  void ResizeInternal(size_type count, U&&... u) { … }

  void DestroyRange(size_type begin, size_type end) const { … }

  // Should only be called from DestroyRange.
  void DestroyUnwrappedRange(size_type begin, size_type end) const { … }

  void DestroyByIndex(size_type index) const { … }

  void DestroyByAddress(pointer address) const { … }

  size_type data_capacity() const { … }

  pointer index_to_address(size_type index) const { … }

  size_type index_prev(size_type index) const { … }

  size_type index_next(size_type index) const { … }

  size_type index_increment_by(size_type index, difference_type delta) const { … }

  // 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 QUICHE_NO_EXPORT 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_