gfe-relnote: (n/a) Add QuicCircularDeque to third_party/quic/core. Code not used yet. The implementation is based on Chromium's circular_deque(http://shortn/_RLFU0Zrxza), the backing type of Chromium's QuicDeque. The new class can be used by all existing uses of QuicDeque except the one in PacketNumberQueue. PiperOrigin-RevId: 278627694 Change-Id: If52cd23cd38c173b14ccefad57b86c4bcf405392
diff --git a/quic/core/quic_circular_deque.h b/quic/core/quic_circular_deque.h new file mode 100644 index 0000000..398448f --- /dev/null +++ b/quic/core/quic_circular_deque.h
@@ -0,0 +1,687 @@ +// 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_QUIC_CORE_QUIC_CIRCULAR_DEQUE_H_ +#define QUICHE_QUIC_CORE_QUIC_CIRCULAR_DEQUE_H_ + +#include <algorithm> +#include <cstddef> +#include <iterator> +#include <memory> +#include <ostream> + +#include "net/third_party/quiche/src/quic/platform/api/quic_export.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_logging.h" + +namespace quic { + +// QuicCircularDeque 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, QuicCircularDeque 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 QUIC_NO_EXPORT QuicCircularDeque { + using AllocatorTraits = std::allocator_traits<Allocator>; + + // Pointee is either T or const T. + template <typename Pointee> + class QUIC_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_) {} + + 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 QuicCircularDeque* deque, size_type index) + : deque_(deque), index_(index) {} + + void Increment() { index_ = deque_->index_next(index_); } + + void Decrement() { index_ = deque_->index_prev(index_); } + + void IncrementBy(difference_type delta) { + if (delta == 0) { + return; + } + + index_ = (deque_->begin_ + ExternalPosition() + delta) % + deque_->data_capacity(); + } + + size_type ExternalPosition() const { + if (index_ >= deque_->begin_) { + return index_ - deque_->begin_; + } + return index_ + deque_->data_capacity() - deque_->begin_; + } + + friend class QuicCircularDeque; + const QuicCircularDeque* 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>; + + QuicCircularDeque() : QuicCircularDeque(allocator_type()) {} + explicit QuicCircularDeque(const allocator_type& alloc) + : allocator_and_data_(alloc) {} + + QuicCircularDeque(size_type count, + const T& value, + const Allocator& alloc = allocator_type()) + : allocator_and_data_(alloc) { + resize(count, value); + } + + explicit QuicCircularDeque(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_v< + std::input_iterator_tag, + typename std::iterator_traits<InputIt>::iterator_category>>> + QuicCircularDeque(InputIt first, + InputIt last, + const Allocator& alloc = allocator_type()) + : allocator_and_data_(alloc) { + AssignRange(first, last); + } + + QuicCircularDeque(const QuicCircularDeque& other) + : QuicCircularDeque( + other, + AllocatorTraits::select_on_container_copy_construction( + other.allocator_and_data_.allocator())) {} + + QuicCircularDeque(const QuicCircularDeque& other, const allocator_type& alloc) + : allocator_and_data_(alloc) { + assign(other.begin(), other.end()); + } + + QuicCircularDeque(QuicCircularDeque&& 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; + } + + QuicCircularDeque(QuicCircularDeque&& other, const allocator_type& alloc) + : allocator_and_data_(alloc) { + MoveRetainAllocator(std::move(other)); + } + + QuicCircularDeque(std::initializer_list<T> init, + const allocator_type& alloc = allocator_type()) + : QuicCircularDeque(init.begin(), init.end(), alloc) {} + + QuicCircularDeque& operator=(const QuicCircularDeque& 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; + } + + QuicCircularDeque& operator=(QuicCircularDeque&& 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->~QuicCircularDeque(); + new (this) QuicCircularDeque(std::move(other)); + } else { + MoveRetainAllocator(std::move(other)); + } + return *this; + } + + ~QuicCircularDeque() { 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_v< + std::input_iterator_tag, + typename std::iterator_traits<InputIt>::iterator_category>>> + 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) { + 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<QuicCircularDeque*>(this)->at(pos); + } + + reference operator[](size_type pos) { return at(pos); } + + const_reference operator[](size_type pos) const { return at(pos); } + + reference front() { + DCHECK(!empty()); + return *index_to_address(begin_); + } + + const_reference front() const { + return const_cast<QuicCircularDeque*>(this)->front(); + } + + reference back() { + DCHECK(!empty()); + return *(index_to_address(end_ == 0 ? data_capacity() - 1 : end_ - 1)); + } + + const_reference back() const { + return const_cast<QuicCircularDeque*>(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() { + DCHECK(!empty()); + DestroyByIndex(begin_); + begin_ = index_next(begin_); + MaybeShrinkCapacity(); + } + + void pop_back() { + DCHECK(!empty()); + end_ = index_prev(end_); + DestroyByIndex(end_); + MaybeShrinkCapacity(); + } + + void swap(QuicCircularDeque& 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. + 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(QuicCircularDeque& lhs, QuicCircularDeque& rhs) { + lhs.swap(rhs); + } + + allocator_type get_allocator() const { + return allocator_and_data_.allocator(); + } + + friend bool operator==(const QuicCircularDeque& lhs, + const QuicCircularDeque& rhs) { + return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); + } + + friend bool operator!=(const QuicCircularDeque& lhs, + const QuicCircularDeque& rhs) { + return !(lhs == rhs); + } + + friend QUIC_NO_EXPORT std::ostream& operator<<(std::ostream& os, + const QuicCircularDeque& dq) { + os << "{"; + for (size_type pos = 0; pos != dq.size(); ++pos) { + if (pos != 0) { + os << ","; + } + os << " " << dq[pos]; + } + os << " }"; + return os; + } + + private: + void MoveRetainAllocator(QuicCircularDeque&& 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_v< + std::input_iterator_tag, + typename std::iterator_traits<InputIt>::iterator_category>>> + void AssignRange(InputIt first, InputIt last) { + ClearRetainCapacity(); + if constexpr (std::is_base_of_v<std::random_access_iterator_tag, + typename std::iterator_traits< + InputIt>::iterator_category>) { + 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) { + 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(); + 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 { + // 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; + } + + void RelocateUnwrappedRange(size_type begin, + size_type end, + pointer dest) const { + DCHECK_LE(begin, end) << "begin:" << begin << ", end:" << end; + if constexpr (std::is_trivially_copyable_v<T>) { + memcpy(dest, index_to_address(begin), sizeof(T) * (end - begin)); + DestroyRange(begin, end); + } else { + pointer src = index_to_address(begin); + pointer src_end = index_to_address(end); + while (src != src_end) { + if constexpr (std::is_move_constructible_v<T>) { + new (dest) T(std::move(*src)); + } else { + 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 constexpr (std::is_trivially_destructible_v<T>) { + 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 { + 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 constexpr (std::is_trivially_destructible_v<T>) { + 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; + } + + // 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 quic + +#endif // QUICHE_QUIC_CORE_QUIC_CIRCULAR_DEQUE_H_
diff --git a/quic/core/quic_circular_deque_test.cc b/quic/core/quic_circular_deque_test.cc new file mode 100644 index 0000000..19f8ca2 --- /dev/null +++ b/quic/core/quic_circular_deque_test.cc
@@ -0,0 +1,757 @@ +// 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 "net/third_party/quiche/src/quic/core/quic_circular_deque.h" + +#include <cstddef> +#include <cstdint> +#include <memory> +#include <type_traits> + +#include "net/third_party/quiche/src/quic/platform/api/quic_logging.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_test.h" + +using testing::ElementsAre; + +namespace quic { +namespace test { + +template <typename T, template <typename> class BaseAllocator = std::allocator> +class CountingAllocator : public BaseAllocator<T> { + typedef BaseAllocator<T> BaseType; + + 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); + } +} + +TEST(QuicCircularDeque, Empty) { + QuicCircularDeque<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_DEBUG_DEATH(dq.front(), ""); + EXPECT_DEBUG_DEATH(dq.back(), ""); + EXPECT_DEBUG_DEATH(dq.at(0), ""); + EXPECT_DEBUG_DEATH(dq[0], ""); +} + +TEST(QuicCircularDeque, Constructor) { + QuicCircularDeque<int> dq; + EXPECT_TRUE(dq.empty()); + + std::allocator<int> alloc; + QuicCircularDeque<int> dq1(alloc); + EXPECT_TRUE(dq1.empty()); + + QuicCircularDeque<int> dq2(8, 100, alloc); + EXPECT_THAT(dq2, ElementsAre(100, 100, 100, 100, 100, 100, 100, 100)); + + QuicCircularDeque<int> dq3(5, alloc); + EXPECT_THAT(dq3, ElementsAre(0, 0, 0, 0, 0)); + + QuicCircularDeque<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}; + QuicCircularDeque<int> dq4_bidi_iter(dq4_src.begin(), dq4_src.end()); + EXPECT_THAT(dq4_bidi_iter, ElementsAre(4, 4, 4, 4)); + + QuicCircularDeque<int> dq5(dq4_bidi_iter); + EXPECT_THAT(dq5, ElementsAre(4, 4, 4, 4)); + EXPECT_EQ(dq5, dq4_bidi_iter); + + QuicCircularDeque<int> dq6(dq5, alloc); + EXPECT_THAT(dq6, ElementsAre(4, 4, 4, 4)); + EXPECT_EQ(dq6, dq5); + + QuicCircularDeque<int> dq7(std::move(*&dq6)); + EXPECT_THAT(dq7, ElementsAre(4, 4, 4, 4)); + EXPECT_TRUE(dq6.empty()); + + QuicCircularDeque<int> dq8_equal_allocator(std::move(*&dq7), alloc); + EXPECT_THAT(dq8_equal_allocator, ElementsAre(4, 4, 4, 4)); + EXPECT_TRUE(dq7.empty()); + + QuicCircularDeque<int, 3, CountingAllocator<int>> dq8_temp = {5, 6, 7, 8, 9}; + QuicCircularDeque<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()); + + QuicCircularDeque<int> dq9({3, 4, 5, 6, 7}, alloc); + EXPECT_THAT(dq9, ElementsAre(3, 4, 5, 6, 7)); +} + +TEST(QuicCircularDeque, Assign) { + // assign() + QuicCircularDeque<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()); + + QuicCircularDeque<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}; + QuicCircularDeque<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)); + + QuicCircularDeque< + 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)); + + QuicCircularDeque< + 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()); + + QuicCircularDeque< + 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()); + + QuicCircularDeque< + 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(QuicCircularDeque, Access) { + // at() + // operator[] + // front() + // back() + + QuicCircularDeque<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(QuicCircularDeque, Iterate) { + QuicCircularDeque<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); + QuicCircularDeque<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); + QuicCircularDeque<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 (QuicCircularDeque<int>::iterator it = dq.begin(); it != dq.end(); ++it) { + EXPECT_EQ(expected_value++, *it); + } + + expected_value = 1; + for (QuicCircularDeque<int>::const_iterator it = dq.cbegin(); it != dq.cend(); + ++it) { + EXPECT_EQ(expected_value++, *it); + } + + // Reverse iterate. + expected_value = 3; + for (QuicCircularDeque<int>::reverse_iterator it = dq.rbegin(); + it != dq.rend(); ++it) { + EXPECT_EQ(expected_value--, *it); + } + + expected_value = 3; + for (QuicCircularDeque<int>::const_reverse_iterator it = dq.crbegin(); + it != dq.crend(); ++it) { + EXPECT_EQ(expected_value--, *it); + } +} + +TEST(QuicCircularDeque, Iterator) { + // Default constructed iterators of the same type compare equal. + EXPECT_EQ(QuicCircularDeque<int>::iterator(), + QuicCircularDeque<int>::iterator()); + EXPECT_EQ(QuicCircularDeque<int>::const_iterator(), + QuicCircularDeque<int>::const_iterator()); + EXPECT_EQ(QuicCircularDeque<int>::reverse_iterator(), + QuicCircularDeque<int>::reverse_iterator()); + EXPECT_EQ(QuicCircularDeque<int>::const_reverse_iterator(), + QuicCircularDeque<int>::const_reverse_iterator()); + + QuicCircularDeque<QuicCircularDeque<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(QuicCircularDeque, Resize) { + QuicCircularDeque<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)); + + QuicCircularDeque<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(QuicCircularDeque, RelocateNonTriviallyCopyable) { + // When relocating non-trivially-copyable objects: + // - Move constructor is preferred, if available. + // - Copy constructor is used otherwise. + + { + // Move construct in Relocate. + typedef std::unique_ptr<Foo> MoveConstructible; + ASSERT_FALSE(std::is_trivially_copyable_v<MoveConstructible>); + ASSERT_TRUE(std::is_move_constructible_v<MoveConstructible>); + QuicCircularDeque<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. + typedef Foo NonMoveConstructible; + ASSERT_FALSE(std::is_trivially_copyable_v<NonMoveConstructible>); + ASSERT_FALSE(std::is_move_constructible_v<NonMoveConstructible>); + QuicCircularDeque<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(QuicCircularDeque, PushPop) { + // (push|pop|emplace)_(back|front) + + { + QuicCircularDeque<Foo, 4, CountingAllocator<Foo>> dq(4); + for (size_t i = 0; i < dq.size(); ++i) { + dq[i].Set(i + 1); + } + QUIC_LOG(INFO) << "dq initialized to " << dq; + EXPECT_THAT(dq, ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4))); + + ShiftLeft(&dq, false); + QUIC_LOG(INFO) << "shift left once : " << dq; + EXPECT_THAT(dq, ElementsAre(Foo(2), Foo(3), Foo(4), Foo(1))); + + ShiftLeft(&dq, true); + QUIC_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. + } + + { + QuicCircularDeque<Foo, 4, CountingAllocator<Foo>> dq1(4); + for (size_t i = 0; i < dq1.size(); ++i) { + dq1[i].Set(i + 1); + } + QUIC_LOG(INFO) << "dq1 initialized to " << dq1; + EXPECT_THAT(dq1, ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4))); + + ShiftRight(&dq1, false); + QUIC_LOG(INFO) << "shift right once : " << dq1; + EXPECT_THAT(dq1, ElementsAre(Foo(4), Foo(1), Foo(2), Foo(3))); + + ShiftRight(&dq1, true); + QUIC_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. + } +} + +TEST(QuicCircularDeque, Allocation) { + CountingAllocator<int> alloc; + + { + QuicCircularDeque<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 test +} // namespace quic + +// Use a non-quic namespace to make sure swap can be used via ADL. +namespace { + +template <typename T> +using SwappableAllocator = quic::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 = quic::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 = quic::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>; + +TEST(QuicCircularDeque, Swap) { + using std::swap; + + quic::QuicCircularDeque<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)); + + quic::QuicCircularDeque<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)); + + quic::QuicCircularDeque<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)); + +#if GTEST_HAS_DEATH_TEST && !defined(NDEBUG) + // Undefined behavior to swap between two containers with unequal allocators. + EXPECT_DEBUG_DEATH(swap(dq5, dq6), "Undefined swap behavior"); +#endif +} +} // namespace