Move quic::QuicCircularDeque to quiche::QuicheCircularDeque.
See last comment at cl/366295336 for motivation.
PiperOrigin-RevId: 370769667
Change-Id: I41907c4e7ef592fb8b7f6a298daf4e1ed15f4d2f
diff --git a/common/platform/api/quiche_test.h b/common/platform/api/quiche_test.h
index b584752..1af25df 100644
--- a/common/platform/api/quiche_test.h
+++ b/common/platform/api/quiche_test.h
@@ -12,4 +12,7 @@
template <class T>
using QuicheTestWithParam = quiche::test::QuicheTestWithParamImpl<T>;
+#define EXPECT_QUICHE_DEBUG_DEATH(condition, message) \
+ EXPECT_QUICHE_DEBUG_DEATH_IMPL(condition, message)
+
#endif // QUICHE_COMMON_PLATFORM_API_QUICHE_TEST_H_
diff --git a/common/quiche_circular_deque.h b/common/quiche_circular_deque.h
new file mode 100644
index 0000000..42b2232
--- /dev/null
+++ b/common/quiche_circular_deque.h
@@ -0,0 +1,759 @@
+// 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_
diff --git a/common/quiche_circular_deque_test.cc b/common/quiche_circular_deque_test.cc
new file mode 100644
index 0000000..0b38ab7
--- /dev/null
+++ b/common/quiche_circular_deque_test.cc
@@ -0,0 +1,800 @@
+// 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.
+
+#include "common/quiche_circular_deque.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <type_traits>
+
+#include "common/platform/api/quiche_logging.h"
+#include "common/platform/api/quiche_test.h"
+
+using testing::ElementsAre;
+
+namespace quiche {
+namespace test {
+namespace {
+
+template <typename T, template <typename> class BaseAllocator = std::allocator>
+class CountingAllocator : public BaseAllocator<T> {
+ using BaseType = BaseAllocator<T>;
+
+ public:
+ using propagate_on_container_copy_assignment = std::true_type;
+ using propagate_on_container_move_assignment = std::true_type;
+ using propagate_on_container_swap = std::true_type;
+
+ T* allocate(std::size_t n) {
+ ++shared_counts_->allocate_count;
+ return BaseType::allocate(n);
+ }
+
+ void deallocate(T* ptr, std::size_t n) {
+ ++shared_counts_->deallocate_count;
+ return BaseType::deallocate(ptr, n);
+ }
+
+ size_t allocate_count() const { return shared_counts_->allocate_count; }
+
+ size_t deallocate_count() const { return shared_counts_->deallocate_count; }
+
+ friend bool operator==(const CountingAllocator& lhs,
+ const CountingAllocator& rhs) {
+ return lhs.shared_counts_ == rhs.shared_counts_;
+ }
+
+ friend bool operator!=(const CountingAllocator& lhs,
+ const CountingAllocator& rhs) {
+ return !(lhs == rhs);
+ }
+
+ private:
+ struct Counts {
+ size_t allocate_count = 0;
+ size_t deallocate_count = 0;
+ };
+
+ std::shared_ptr<Counts> shared_counts_ = std::make_shared<Counts>();
+};
+
+template <typename T,
+ typename propagate_on_copy_assignment,
+ typename propagate_on_move_assignment,
+ typename propagate_on_swap,
+ bool equality_result,
+ template <typename> class BaseAllocator = std::allocator>
+struct ConfigurableAllocator : public BaseAllocator<T> {
+ using propagate_on_container_copy_assignment = propagate_on_copy_assignment;
+ using propagate_on_container_move_assignment = propagate_on_move_assignment;
+ using propagate_on_container_swap = propagate_on_swap;
+
+ friend bool operator==(const ConfigurableAllocator& /*lhs*/,
+ const ConfigurableAllocator& /*rhs*/) {
+ return equality_result;
+ }
+
+ friend bool operator!=(const ConfigurableAllocator& lhs,
+ const ConfigurableAllocator& rhs) {
+ return !(lhs == rhs);
+ }
+};
+
+// [1, 2, 3, 4] ==> [4, 1, 2, 3]
+template <typename Deque>
+void ShiftRight(Deque* dq, bool emplace) {
+ auto back = *(&dq->back());
+ dq->pop_back();
+ if (emplace) {
+ dq->emplace_front(back);
+ } else {
+ dq->push_front(back);
+ }
+}
+
+// [1, 2, 3, 4] ==> [2, 3, 4, 1]
+template <typename Deque>
+void ShiftLeft(Deque* dq, bool emplace) {
+ auto front = *(&dq->front());
+ dq->pop_front();
+ if (emplace) {
+ dq->emplace_back(front);
+ } else {
+ dq->push_back(front);
+ }
+}
+
+class QuicheCircularDequeTest : public QuicheTest {};
+
+TEST_F(QuicheCircularDequeTest, Empty) {
+ QuicheCircularDeque<int> dq;
+ EXPECT_TRUE(dq.empty());
+ EXPECT_EQ(0u, dq.size());
+ dq.clear();
+ dq.push_back(10);
+ EXPECT_FALSE(dq.empty());
+ EXPECT_EQ(1u, dq.size());
+ EXPECT_EQ(10, dq.front());
+ EXPECT_EQ(10, dq.back());
+ dq.pop_front();
+ EXPECT_TRUE(dq.empty());
+ EXPECT_EQ(0u, dq.size());
+
+ EXPECT_QUICHE_DEBUG_DEATH(dq.front(), "");
+ EXPECT_QUICHE_DEBUG_DEATH(dq.back(), "");
+ EXPECT_QUICHE_DEBUG_DEATH(dq.at(0), "");
+ EXPECT_QUICHE_DEBUG_DEATH(dq[0], "");
+}
+
+TEST_F(QuicheCircularDequeTest, Constructor) {
+ QuicheCircularDeque<int> dq;
+ EXPECT_TRUE(dq.empty());
+
+ std::allocator<int> alloc;
+ QuicheCircularDeque<int> dq1(alloc);
+ EXPECT_TRUE(dq1.empty());
+
+ QuicheCircularDeque<int> dq2(8, 100, alloc);
+ EXPECT_THAT(dq2, ElementsAre(100, 100, 100, 100, 100, 100, 100, 100));
+
+ QuicheCircularDeque<int> dq3(5, alloc);
+ EXPECT_THAT(dq3, ElementsAre(0, 0, 0, 0, 0));
+
+ QuicheCircularDeque<int> dq4_rand_iter(dq3.begin(), dq3.end(), alloc);
+ EXPECT_THAT(dq4_rand_iter, ElementsAre(0, 0, 0, 0, 0));
+ EXPECT_EQ(dq4_rand_iter, dq3);
+
+ std::list<int> dq4_src = {4, 4, 4, 4};
+ QuicheCircularDeque<int> dq4_bidi_iter(dq4_src.begin(), dq4_src.end());
+ EXPECT_THAT(dq4_bidi_iter, ElementsAre(4, 4, 4, 4));
+
+ QuicheCircularDeque<int> dq5(dq4_bidi_iter);
+ EXPECT_THAT(dq5, ElementsAre(4, 4, 4, 4));
+ EXPECT_EQ(dq5, dq4_bidi_iter);
+
+ QuicheCircularDeque<int> dq6(dq5, alloc);
+ EXPECT_THAT(dq6, ElementsAre(4, 4, 4, 4));
+ EXPECT_EQ(dq6, dq5);
+
+ QuicheCircularDeque<int> dq7(std::move(*&dq6));
+ EXPECT_THAT(dq7, ElementsAre(4, 4, 4, 4));
+ EXPECT_TRUE(dq6.empty());
+
+ QuicheCircularDeque<int> dq8_equal_allocator(std::move(*&dq7), alloc);
+ EXPECT_THAT(dq8_equal_allocator, ElementsAre(4, 4, 4, 4));
+ EXPECT_TRUE(dq7.empty());
+
+ QuicheCircularDeque<int, 3, CountingAllocator<int>> dq8_temp = {5, 6, 7, 8,
+ 9};
+ QuicheCircularDeque<int, 3, CountingAllocator<int>> dq8_unequal_allocator(
+ std::move(*&dq8_temp), CountingAllocator<int>());
+ EXPECT_THAT(dq8_unequal_allocator, ElementsAre(5, 6, 7, 8, 9));
+ EXPECT_TRUE(dq8_temp.empty());
+
+ QuicheCircularDeque<int> dq9({3, 4, 5, 6, 7}, alloc);
+ EXPECT_THAT(dq9, ElementsAre(3, 4, 5, 6, 7));
+}
+
+TEST_F(QuicheCircularDequeTest, Assign) {
+ // assign()
+ QuicheCircularDeque<int, 3, CountingAllocator<int>> dq;
+ dq.assign(7, 1);
+ EXPECT_THAT(dq, ElementsAre(1, 1, 1, 1, 1, 1, 1));
+ EXPECT_EQ(1u, dq.get_allocator().allocate_count());
+
+ QuicheCircularDeque<int, 3, CountingAllocator<int>> dq2;
+ dq2.assign(dq.begin(), dq.end());
+ EXPECT_THAT(dq2, ElementsAre(1, 1, 1, 1, 1, 1, 1));
+ EXPECT_EQ(1u, dq2.get_allocator().allocate_count());
+ EXPECT_TRUE(std::equal(dq.begin(), dq.end(), dq2.begin(), dq2.end()));
+
+ dq2.assign({2, 2, 2, 2, 2, 2});
+ EXPECT_THAT(dq2, ElementsAre(2, 2, 2, 2, 2, 2));
+
+ // Assign from a non random access iterator.
+ std::list<int> dq3_src = {3, 3, 3, 3, 3};
+ QuicheCircularDeque<int, 3, CountingAllocator<int>> dq3;
+ dq3.assign(dq3_src.begin(), dq3_src.end());
+ EXPECT_THAT(dq3, ElementsAre(3, 3, 3, 3, 3));
+ EXPECT_LT(1u, dq3.get_allocator().allocate_count());
+
+ // Copy assignment
+ dq3 = *&dq3;
+ EXPECT_THAT(dq3, ElementsAre(3, 3, 3, 3, 3));
+
+ QuicheCircularDeque<
+ int, 3,
+ ConfigurableAllocator<int,
+ /*propagate_on_copy_assignment=*/std::true_type,
+ /*propagate_on_move_assignment=*/std::true_type,
+ /*propagate_on_swap=*/std::true_type,
+ /*equality_result=*/false>>
+ dq4, dq5;
+ dq4.assign(dq3.begin(), dq3.end());
+ dq5 = dq4;
+ EXPECT_THAT(dq5, ElementsAre(3, 3, 3, 3, 3));
+
+ QuicheCircularDeque<
+ int, 3,
+ ConfigurableAllocator<int,
+ /*propagate_on_copy_assignment=*/std::false_type,
+ /*propagate_on_move_assignment=*/std::true_type,
+ /*propagate_on_swap=*/std::true_type,
+ /*equality_result=*/true>>
+ dq6, dq7;
+ dq6.assign(dq3.begin(), dq3.end());
+ dq7 = dq6;
+ EXPECT_THAT(dq7, ElementsAre(3, 3, 3, 3, 3));
+
+ // Move assignment
+ dq3 = std::move(*&dq3);
+ EXPECT_THAT(dq3, ElementsAre(3, 3, 3, 3, 3));
+
+ ASSERT_TRUE(decltype(
+ dq3.get_allocator())::propagate_on_container_move_assignment::value);
+ decltype(dq3) dq8;
+ dq8 = std::move(*&dq3);
+ EXPECT_THAT(dq8, ElementsAre(3, 3, 3, 3, 3));
+ EXPECT_TRUE(dq3.empty());
+
+ QuicheCircularDeque<
+ int, 3,
+ ConfigurableAllocator<int,
+ /*propagate_on_copy_assignment=*/std::true_type,
+ /*propagate_on_move_assignment=*/std::false_type,
+ /*propagate_on_swap=*/std::true_type,
+ /*equality_result=*/true>>
+ dq9, dq10;
+ dq9.assign(dq8.begin(), dq8.end());
+ dq10.assign(dq2.begin(), dq2.end());
+ dq9 = std::move(*&dq10);
+ EXPECT_THAT(dq9, ElementsAre(2, 2, 2, 2, 2, 2));
+ EXPECT_TRUE(dq10.empty());
+
+ QuicheCircularDeque<
+ int, 3,
+ ConfigurableAllocator<int,
+ /*propagate_on_copy_assignment=*/std::true_type,
+ /*propagate_on_move_assignment=*/std::false_type,
+ /*propagate_on_swap=*/std::true_type,
+ /*equality_result=*/false>>
+ dq11, dq12;
+ dq11.assign(dq8.begin(), dq8.end());
+ dq12.assign(dq2.begin(), dq2.end());
+ dq11 = std::move(*&dq12);
+ EXPECT_THAT(dq11, ElementsAre(2, 2, 2, 2, 2, 2));
+ EXPECT_TRUE(dq12.empty());
+}
+
+TEST_F(QuicheCircularDequeTest, Access) {
+ // at()
+ // operator[]
+ // front()
+ // back()
+
+ QuicheCircularDeque<int, 3, CountingAllocator<int>> dq;
+ dq.push_back(10);
+ EXPECT_EQ(dq.front(), 10);
+ EXPECT_EQ(dq.back(), 10);
+ EXPECT_EQ(dq.at(0), 10);
+ EXPECT_EQ(dq[0], 10);
+ dq.front() = 12;
+ EXPECT_EQ(dq.front(), 12);
+ EXPECT_EQ(dq.back(), 12);
+ EXPECT_EQ(dq.at(0), 12);
+ EXPECT_EQ(dq[0], 12);
+
+ const auto& dqref = dq;
+ EXPECT_EQ(dqref.front(), 12);
+ EXPECT_EQ(dqref.back(), 12);
+ EXPECT_EQ(dqref.at(0), 12);
+ EXPECT_EQ(dqref[0], 12);
+
+ dq.pop_front();
+ EXPECT_TRUE(dqref.empty());
+
+ // Push to capacity.
+ dq.push_back(15);
+ dq.push_front(5);
+ dq.push_back(25);
+ EXPECT_EQ(dq.size(), dq.capacity());
+ EXPECT_THAT(dq, ElementsAre(5, 15, 25));
+ EXPECT_LT(&dq.front(), &dq.back());
+ EXPECT_EQ(dq.front(), 5);
+ EXPECT_EQ(dq.back(), 25);
+ EXPECT_EQ(dq.at(0), 5);
+ EXPECT_EQ(dq.at(1), 15);
+ EXPECT_EQ(dq.at(2), 25);
+ EXPECT_EQ(dq[0], 5);
+ EXPECT_EQ(dq[1], 15);
+ EXPECT_EQ(dq[2], 25);
+
+ // Shift right such that begin=1 and end=0. Data is still not wrapped.
+ dq.pop_front();
+ dq.push_back(35);
+ EXPECT_THAT(dq, ElementsAre(15, 25, 35));
+ EXPECT_LT(&dq.front(), &dq.back());
+ EXPECT_EQ(dq.front(), 15);
+ EXPECT_EQ(dq.back(), 35);
+ EXPECT_EQ(dq.at(0), 15);
+ EXPECT_EQ(dq.at(1), 25);
+ EXPECT_EQ(dq.at(2), 35);
+ EXPECT_EQ(dq[0], 15);
+ EXPECT_EQ(dq[1], 25);
+ EXPECT_EQ(dq[2], 35);
+
+ // Shift right such that data is wrapped.
+ dq.pop_front();
+ dq.push_back(45);
+ EXPECT_THAT(dq, ElementsAre(25, 35, 45));
+ EXPECT_GT(&dq.front(), &dq.back());
+ EXPECT_EQ(dq.front(), 25);
+ EXPECT_EQ(dq.back(), 45);
+ EXPECT_EQ(dq.at(0), 25);
+ EXPECT_EQ(dq.at(1), 35);
+ EXPECT_EQ(dq.at(2), 45);
+ EXPECT_EQ(dq[0], 25);
+ EXPECT_EQ(dq[1], 35);
+ EXPECT_EQ(dq[2], 45);
+
+ // Shift right again, data is still wrapped.
+ dq.pop_front();
+ dq.push_back(55);
+ EXPECT_THAT(dq, ElementsAre(35, 45, 55));
+ EXPECT_GT(&dq.front(), &dq.back());
+ EXPECT_EQ(dq.front(), 35);
+ EXPECT_EQ(dq.back(), 55);
+ EXPECT_EQ(dq.at(0), 35);
+ EXPECT_EQ(dq.at(1), 45);
+ EXPECT_EQ(dq.at(2), 55);
+ EXPECT_EQ(dq[0], 35);
+ EXPECT_EQ(dq[1], 45);
+ EXPECT_EQ(dq[2], 55);
+
+ // Shift right one last time. begin returns to 0. Data is no longer wrapped.
+ dq.pop_front();
+ dq.push_back(65);
+ EXPECT_THAT(dq, ElementsAre(45, 55, 65));
+ EXPECT_LT(&dq.front(), &dq.back());
+ EXPECT_EQ(dq.front(), 45);
+ EXPECT_EQ(dq.back(), 65);
+ EXPECT_EQ(dq.at(0), 45);
+ EXPECT_EQ(dq.at(1), 55);
+ EXPECT_EQ(dq.at(2), 65);
+ EXPECT_EQ(dq[0], 45);
+ EXPECT_EQ(dq[1], 55);
+ EXPECT_EQ(dq[2], 65);
+
+ EXPECT_EQ(1u, dq.get_allocator().allocate_count());
+}
+
+TEST_F(QuicheCircularDequeTest, Iterate) {
+ QuicheCircularDeque<int> dq;
+ EXPECT_EQ(dq.begin(), dq.end());
+ EXPECT_EQ(dq.cbegin(), dq.cend());
+ EXPECT_EQ(dq.rbegin(), dq.rend());
+ EXPECT_EQ(dq.crbegin(), dq.crend());
+
+ dq.emplace_back(2);
+ QuicheCircularDeque<int>::const_iterator citer = dq.begin();
+ EXPECT_NE(citer, dq.end());
+ EXPECT_EQ(*citer, 2);
+ ++citer;
+ EXPECT_EQ(citer, dq.end());
+
+ EXPECT_EQ(*dq.begin(), 2);
+ EXPECT_EQ(*dq.cbegin(), 2);
+ EXPECT_EQ(*dq.rbegin(), 2);
+ EXPECT_EQ(*dq.crbegin(), 2);
+
+ dq.emplace_front(1);
+ QuicheCircularDeque<int>::const_reverse_iterator criter = dq.rbegin();
+ EXPECT_NE(criter, dq.rend());
+ EXPECT_EQ(*criter, 2);
+ ++criter;
+ EXPECT_NE(criter, dq.rend());
+ EXPECT_EQ(*criter, 1);
+ ++criter;
+ EXPECT_EQ(criter, dq.rend());
+
+ EXPECT_EQ(*dq.begin(), 1);
+ EXPECT_EQ(*dq.cbegin(), 1);
+ EXPECT_EQ(*dq.rbegin(), 2);
+ EXPECT_EQ(*dq.crbegin(), 2);
+
+ dq.push_back(3);
+
+ // Forward iterate.
+ int expected_value = 1;
+ for (QuicheCircularDeque<int>::iterator it = dq.begin(); it != dq.end();
+ ++it) {
+ EXPECT_EQ(expected_value++, *it);
+ }
+
+ expected_value = 1;
+ for (QuicheCircularDeque<int>::const_iterator it = dq.cbegin();
+ it != dq.cend(); ++it) {
+ EXPECT_EQ(expected_value++, *it);
+ }
+
+ // Reverse iterate.
+ expected_value = 3;
+ for (QuicheCircularDeque<int>::reverse_iterator it = dq.rbegin();
+ it != dq.rend(); ++it) {
+ EXPECT_EQ(expected_value--, *it);
+ }
+
+ expected_value = 3;
+ for (QuicheCircularDeque<int>::const_reverse_iterator it = dq.crbegin();
+ it != dq.crend(); ++it) {
+ EXPECT_EQ(expected_value--, *it);
+ }
+}
+
+TEST_F(QuicheCircularDequeTest, Iterator) {
+ // Default constructed iterators of the same type compare equal.
+ EXPECT_EQ(QuicheCircularDeque<int>::iterator(),
+ QuicheCircularDeque<int>::iterator());
+ EXPECT_EQ(QuicheCircularDeque<int>::const_iterator(),
+ QuicheCircularDeque<int>::const_iterator());
+ EXPECT_EQ(QuicheCircularDeque<int>::reverse_iterator(),
+ QuicheCircularDeque<int>::reverse_iterator());
+ EXPECT_EQ(QuicheCircularDeque<int>::const_reverse_iterator(),
+ QuicheCircularDeque<int>::const_reverse_iterator());
+
+ QuicheCircularDeque<QuicheCircularDeque<int>, 3> dqdq = {
+ {1, 2}, {10, 20, 30}, {100, 200, 300, 400}};
+
+ // iter points to {1, 2}
+ decltype(dqdq)::iterator iter = dqdq.begin();
+ EXPECT_EQ(iter->size(), 2u);
+ EXPECT_THAT(*iter, ElementsAre(1, 2));
+
+ // citer points to {10, 20, 30}
+ decltype(dqdq)::const_iterator citer = dqdq.cbegin() + 1;
+ EXPECT_NE(*iter, *citer);
+ EXPECT_EQ(citer->size(), 3u);
+ int x = 10;
+ for (auto it = citer->begin(); it != citer->end(); ++it) {
+ EXPECT_EQ(*it, x);
+ x += 10;
+ }
+
+ EXPECT_LT(iter, citer);
+ EXPECT_LE(iter, iter);
+ EXPECT_GT(citer, iter);
+ EXPECT_GE(citer, citer);
+
+ // iter points to {100, 200, 300, 400}
+ iter += 2;
+ EXPECT_NE(*iter, *citer);
+ EXPECT_EQ(iter->size(), 4u);
+ for (int i = 1; i <= 4; ++i) {
+ EXPECT_EQ(iter->begin()[i - 1], i * 100);
+ }
+
+ EXPECT_LT(citer, iter);
+ EXPECT_LE(iter, iter);
+ EXPECT_GT(iter, citer);
+ EXPECT_GE(citer, citer);
+
+ // iter points to {10, 20, 30}. (same as citer)
+ iter -= 1;
+ EXPECT_EQ(*iter, *citer);
+ EXPECT_EQ(iter->size(), 3u);
+ x = 10;
+ for (auto it = iter->begin(); it != iter->end();) {
+ EXPECT_EQ(*(it++), x);
+ x += 10;
+ }
+ x = 30;
+ for (auto it = iter->begin() + 2; it != iter->begin();) {
+ EXPECT_EQ(*(it--), x);
+ x -= 10;
+ }
+}
+
+TEST_F(QuicheCircularDequeTest, Resize) {
+ QuicheCircularDeque<int, 3, CountingAllocator<int>> dq;
+ dq.resize(8);
+ EXPECT_THAT(dq, ElementsAre(0, 0, 0, 0, 0, 0, 0, 0));
+ EXPECT_EQ(1u, dq.get_allocator().allocate_count());
+
+ dq.resize(10, 5);
+ EXPECT_THAT(dq, ElementsAre(0, 0, 0, 0, 0, 0, 0, 0, 5, 5));
+
+ QuicheCircularDeque<int, 3, CountingAllocator<int>> dq2 = dq;
+
+ for (size_t new_size = dq.size(); new_size != 0; --new_size) {
+ dq.resize(new_size);
+ EXPECT_TRUE(
+ std::equal(dq.begin(), dq.end(), dq2.begin(), dq2.begin() + new_size));
+ }
+
+ dq.resize(0);
+ EXPECT_TRUE(dq.empty());
+
+ // Resize when data is wrapped.
+ ASSERT_EQ(dq2.size(), dq2.capacity());
+ while (dq2.size() < dq2.capacity()) {
+ dq2.push_back(5);
+ }
+
+ // Shift left once such that data is wrapped.
+ ASSERT_LT(&dq2.front(), &dq2.back());
+ dq2.pop_back();
+ dq2.push_front(-5);
+ ASSERT_GT(&dq2.front(), &dq2.back());
+
+ EXPECT_EQ(-5, dq2.front());
+ EXPECT_EQ(5, dq2.back());
+ dq2.resize(dq2.size() + 1, 10);
+
+ // Data should be unwrapped after the resize.
+ ASSERT_LT(&dq2.front(), &dq2.back());
+ EXPECT_EQ(-5, dq2.front());
+ EXPECT_EQ(10, dq2.back());
+ EXPECT_EQ(5, *(dq2.rbegin() + 1));
+}
+
+namespace {
+class Foo {
+ public:
+ Foo() : Foo(0xF00) {}
+
+ explicit Foo(int i) : i_(new int(i)) {}
+
+ ~Foo() {
+ if (i_ != nullptr) {
+ delete i_;
+ // Do not set i_ to nullptr such that if the container calls destructor
+ // multiple times, asan can detect it.
+ }
+ }
+
+ Foo(const Foo& other) : i_(new int(*other.i_)) {}
+
+ Foo(Foo&& other) = delete;
+
+ void Set(int i) { *i_ = i; }
+
+ int i() const { return *i_; }
+
+ friend bool operator==(const Foo& lhs, const Foo& rhs) {
+ return lhs.i() == rhs.i();
+ }
+
+ friend std::ostream& operator<<(std::ostream& os, const Foo& foo) {
+ return os << "Foo(" << foo.i() << ")";
+ }
+
+ private:
+ // By pointing i_ to a dynamically allocated integer, a memory leak will be
+ // reported if the container forget to properly destruct this object.
+ int* i_ = nullptr;
+};
+} // namespace
+
+TEST_F(QuicheCircularDequeTest, RelocateNonTriviallyCopyable) {
+ // When relocating non-trivially-copyable objects:
+ // - Move constructor is preferred, if available.
+ // - Copy constructor is used otherwise.
+
+ {
+ // Move construct in Relocate.
+ using MoveConstructible = std::unique_ptr<Foo>;
+ ASSERT_FALSE(std::is_trivially_copyable<MoveConstructible>::value);
+ ASSERT_TRUE(std::is_move_constructible<MoveConstructible>::value);
+ QuicheCircularDeque<MoveConstructible, 3,
+ CountingAllocator<MoveConstructible>>
+ dq1;
+ dq1.resize(3);
+ EXPECT_EQ(dq1.size(), dq1.capacity());
+ EXPECT_EQ(1u, dq1.get_allocator().allocate_count());
+
+ dq1.emplace_back(new Foo(0xF1)); // Cause existing elements to relocate.
+ EXPECT_EQ(4u, dq1.size());
+ EXPECT_EQ(2u, dq1.get_allocator().allocate_count());
+ EXPECT_EQ(dq1[0], nullptr);
+ EXPECT_EQ(dq1[1], nullptr);
+ EXPECT_EQ(dq1[2], nullptr);
+ EXPECT_EQ(dq1[3]->i(), 0xF1);
+ }
+
+ {
+ // Copy construct in Relocate.
+ using NonMoveConstructible = Foo;
+ ASSERT_FALSE(std::is_trivially_copyable<NonMoveConstructible>::value);
+ ASSERT_FALSE(std::is_move_constructible<NonMoveConstructible>::value);
+ QuicheCircularDeque<NonMoveConstructible, 3,
+ CountingAllocator<NonMoveConstructible>>
+ dq2;
+ dq2.resize(3);
+ EXPECT_EQ(dq2.size(), dq2.capacity());
+ EXPECT_EQ(1u, dq2.get_allocator().allocate_count());
+
+ dq2.emplace_back(0xF1); // Cause existing elements to relocate.
+ EXPECT_EQ(4u, dq2.size());
+ EXPECT_EQ(2u, dq2.get_allocator().allocate_count());
+ EXPECT_EQ(dq2[0].i(), 0xF00);
+ EXPECT_EQ(dq2[1].i(), 0xF00);
+ EXPECT_EQ(dq2[2].i(), 0xF00);
+ EXPECT_EQ(dq2[3].i(), 0xF1);
+ }
+}
+
+TEST_F(QuicheCircularDequeTest, PushPop) {
+ // (push|pop|emplace)_(back|front)
+
+ {
+ QuicheCircularDeque<Foo, 4, CountingAllocator<Foo>> dq(4);
+ for (size_t i = 0; i < dq.size(); ++i) {
+ dq[i].Set(i + 1);
+ }
+ QUICHE_LOG(INFO) << "dq initialized to " << dq;
+ EXPECT_THAT(dq, ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4)));
+
+ ShiftLeft(&dq, false);
+ QUICHE_LOG(INFO) << "shift left once : " << dq;
+ EXPECT_THAT(dq, ElementsAre(Foo(2), Foo(3), Foo(4), Foo(1)));
+
+ ShiftLeft(&dq, true);
+ QUICHE_LOG(INFO) << "shift left twice: " << dq;
+ EXPECT_THAT(dq, ElementsAre(Foo(3), Foo(4), Foo(1), Foo(2)));
+ ASSERT_GT(&dq.front(), &dq.back());
+ // dq destructs with wrapped data.
+ }
+
+ {
+ QuicheCircularDeque<Foo, 4, CountingAllocator<Foo>> dq1(4);
+ for (size_t i = 0; i < dq1.size(); ++i) {
+ dq1[i].Set(i + 1);
+ }
+ QUICHE_LOG(INFO) << "dq1 initialized to " << dq1;
+ EXPECT_THAT(dq1, ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4)));
+
+ ShiftRight(&dq1, false);
+ QUICHE_LOG(INFO) << "shift right once : " << dq1;
+ EXPECT_THAT(dq1, ElementsAre(Foo(4), Foo(1), Foo(2), Foo(3)));
+
+ ShiftRight(&dq1, true);
+ QUICHE_LOG(INFO) << "shift right twice: " << dq1;
+ EXPECT_THAT(dq1, ElementsAre(Foo(3), Foo(4), Foo(1), Foo(2)));
+ ASSERT_GT(&dq1.front(), &dq1.back());
+ // dq1 destructs with wrapped data.
+ }
+
+ { // Pop n elements from front.
+ QuicheCircularDeque<Foo, 4, CountingAllocator<Foo>> dq2(5);
+ for (size_t i = 0; i < dq2.size(); ++i) {
+ dq2[i].Set(i + 1);
+ }
+ EXPECT_THAT(dq2, ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)));
+
+ EXPECT_EQ(2u, dq2.pop_front_n(2));
+ EXPECT_THAT(dq2, ElementsAre(Foo(3), Foo(4), Foo(5)));
+
+ EXPECT_EQ(3u, dq2.pop_front_n(100));
+ EXPECT_TRUE(dq2.empty());
+ }
+
+ { // Pop n elements from back.
+ QuicheCircularDeque<Foo, 4, CountingAllocator<Foo>> dq3(6);
+ for (size_t i = 0; i < dq3.size(); ++i) {
+ dq3[i].Set(i + 1);
+ }
+ EXPECT_THAT(dq3,
+ ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4), Foo(5), Foo(6)));
+
+ ShiftRight(&dq3, true);
+ ShiftRight(&dq3, true);
+ ShiftRight(&dq3, true);
+ EXPECT_THAT(dq3,
+ ElementsAre(Foo(4), Foo(5), Foo(6), Foo(1), Foo(2), Foo(3)));
+
+ EXPECT_EQ(2u, dq3.pop_back_n(2));
+ EXPECT_THAT(dq3, ElementsAre(Foo(4), Foo(5), Foo(6), Foo(1)));
+
+ EXPECT_EQ(2u, dq3.pop_back_n(2));
+ EXPECT_THAT(dq3, ElementsAre(Foo(4), Foo(5)));
+ }
+}
+
+TEST_F(QuicheCircularDequeTest, Allocation) {
+ CountingAllocator<int> alloc;
+
+ {
+ QuicheCircularDeque<int, 3, CountingAllocator<int>> dq(alloc);
+ EXPECT_EQ(alloc, dq.get_allocator());
+ EXPECT_EQ(0u, dq.size());
+ EXPECT_EQ(0u, dq.capacity());
+ EXPECT_EQ(0u, alloc.allocate_count());
+ EXPECT_EQ(0u, alloc.deallocate_count());
+
+ for (int i = 1; i <= 18; ++i) {
+ SCOPED_TRACE(testing::Message()
+ << "i=" << i << ", capacity_b4_push=" << dq.capacity());
+ dq.push_back(i);
+ EXPECT_EQ(i, static_cast<int>(dq.size()));
+
+ const size_t capacity = 3 + (i - 1) / 3 * 3;
+ EXPECT_EQ(capacity, dq.capacity());
+ EXPECT_EQ(capacity / 3, alloc.allocate_count());
+ EXPECT_EQ(capacity / 3 - 1, alloc.deallocate_count());
+ }
+
+ dq.push_back(19);
+ EXPECT_EQ(22u, dq.capacity()); // 18 + 18 / 4
+ EXPECT_EQ(7u, alloc.allocate_count());
+ EXPECT_EQ(6u, alloc.deallocate_count());
+ }
+
+ EXPECT_EQ(7u, alloc.deallocate_count());
+}
+
+} // namespace
+} // namespace test
+} // namespace quiche
+
+// Use a non-quiche namespace to make sure swap can be used via ADL.
+namespace {
+
+template <typename T>
+using SwappableAllocator = quiche::test::ConfigurableAllocator<
+ T,
+ /*propagate_on_copy_assignment=*/std::true_type,
+ /*propagate_on_move_assignment=*/std::true_type,
+ /*propagate_on_swap=*/std::true_type,
+ /*equality_result=*/true>;
+
+template <typename T>
+using UnswappableEqualAllocator = quiche::test::ConfigurableAllocator<
+ T,
+ /*propagate_on_copy_assignment=*/std::true_type,
+ /*propagate_on_move_assignment=*/std::true_type,
+ /*propagate_on_swap=*/std::false_type,
+ /*equality_result=*/true>;
+
+template <typename T>
+using UnswappableUnequalAllocator = quiche::test::ConfigurableAllocator<
+ T,
+ /*propagate_on_copy_assignment=*/std::true_type,
+ /*propagate_on_move_assignment=*/std::true_type,
+ /*propagate_on_swap=*/std::false_type,
+ /*equality_result=*/false>;
+
+using quiche::test::QuicheCircularDequeTest;
+
+TEST_F(QuicheCircularDequeTest, Swap) {
+ using std::swap;
+
+ quiche::QuicheCircularDeque<int64_t, 3, SwappableAllocator<int64_t>> dq1, dq2;
+ dq1.push_back(10);
+ dq1.push_back(11);
+ dq2.push_back(20);
+ swap(dq1, dq2);
+ EXPECT_THAT(dq1, ElementsAre(20));
+ EXPECT_THAT(dq2, ElementsAre(10, 11));
+
+ quiche::QuicheCircularDeque<char, 3, UnswappableEqualAllocator<char>> dq3,
+ dq4;
+ dq3 = {1, 2, 3, 4, 5};
+ dq4 = {6, 7, 8, 9, 0};
+ swap(dq3, dq4);
+ EXPECT_THAT(dq3, ElementsAre(6, 7, 8, 9, 0));
+ EXPECT_THAT(dq4, ElementsAre(1, 2, 3, 4, 5));
+
+ quiche::QuicheCircularDeque<int, 3, UnswappableUnequalAllocator<int>> dq5,
+ dq6;
+ dq6.push_front(4);
+
+ // Using UnswappableUnequalAllocator is ok as long as swap is not called.
+ dq5.assign(dq6.begin(), dq6.end());
+ EXPECT_THAT(dq5, ElementsAre(4));
+
+ // Undefined behavior to swap between two containers with unequal allocators.
+ EXPECT_QUICHE_DEBUG_DEATH(swap(dq5, dq6), "Undefined swap behavior");
+}
+} // namespace
