Index: base/containers/circular_deque.h |
diff --git a/base/containers/circular_deque.h b/base/containers/circular_deque.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..ff2986c27696f7c6061e9b03e6f75c5ba73438e9 |
--- /dev/null |
+++ b/base/containers/circular_deque.h |
@@ -0,0 +1,779 @@ |
+// Copyright 2017 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 BASE_CONTAINERS_CIRCULAR_DEQUE_H_ |
+#define BASE_CONTAINERS_CIRCULAR_DEQUE_H_ |
+ |
+#include <cstddef> |
+#include <iterator> |
+#include <type_traits> |
+#include <utility> |
+ |
+#include "base/containers/vector_buffer.h" |
+#include "base/logging.h" |
+#include "base/macros.h" |
+#include "base/template_util.h" |
+ |
+// base::circular_deque is similar to std::deque. Unlike std::deque, the |
+// storage is provided in a flat circular buffer conceptually similar to a |
+// vector. The beginning and end will wrap around as necessary so that |
+// pushes and pops will be constant time as long as a capacity expansion is |
+// not required. |
+// |
+// The API should be identical to std::deque with the following differences: |
+// |
+// - ITERATORS IN ARE NOT STABLE. Mutating the container will invalidate all |
+// iterators. |
+// |
+// - Insertions may resize the vector and so are not linear time (std::deque |
+// guarantees amortized constant time for insertions at the ends). |
+// |
+// - Container-wide comparisons are not implemented. If you want to compare |
+// two containers, use an algorithm so the expensive iteration is explicit. |
+// |
+// - Insert and erase in the middle is not supported. This complicates the |
+// implementation and is not necessary for our current goals. We can |
+// consider adding this in the future if necessary. But consider that |
+// the implementation will be quite slow and that callers needing this |
+// beahvior may be better served with a std::list. |
+// |
+// If you want a similar container with only a queue API, use base::queue in |
+// base/containers/queue.h. |
+// |
+// Constructors: |
+// circular_deque(); |
+// circular_deque(size_t count); |
+// circular_deque(size_t count, const T& value); |
+// circular_deque(InputIterator first, InputIterator last); |
+// circular_deque(const circular_deque&); |
+// circular_deque(circular_deque&&); |
+// circular_deque(std::initializer_list<value_type>); |
+// |
+// Assignment functions: |
+// circular_deque& operator=(const circular_deque&); |
+// circular_deque& operator=(circular_deque&&); |
+// circular_deque& operator=(std::initializer_list<T>); |
+// void assign(size_t count, const T& value); |
+// void assign(InputIterator first, InputIterator last); |
+// void assign(std::initializer_list<T> value); |
+// |
+// Random accessors: |
+// T& at(size_t); |
+// const T& at(size_t) const; |
+// T& operator[](size_t); |
+// const T& operator[](size_t) const; |
+// |
+// End accessors: |
+// T& front(); |
+// const T& front() const; |
+// T& back(); |
+// const T& back() const; |
+// |
+// Iterator functions: |
+// 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; |
+// |
+// Memory management: |
+// void reserve(size_t); |
+// size_t capacity() const; |
+// void shrink_to_fit(); |
+// |
+// Size management: |
+// void clear(); |
+// bool empty() const; |
+// size_t size() const; |
+// void resize(size_t); |
+// void resize(size_t count, const T& value); |
+// |
+// End insert and erase: |
+// void push_front(const T&); |
+// void push_front(T&&); |
+// void push_back(const T&); |
+// void push_back(T&&); |
+// void emplace_front(Args&&...); |
+// void emplace_back(Args&&...); |
+// void pop_front; |
+// void pop_back(); |
+// |
+// General: |
+// void swap(circular_deque&); |
+ |
+namespace base { |
+ |
+template <class T> |
+class circular_deque; |
+ |
+namespace internal { |
+ |
+template <typename T> |
+class circular_deque_const_iterator { |
+ public: |
+ using difference_type = std::ptrdiff_t; |
+ using value_type = T; |
+ using pointer = const T*; |
+ using reference = const T&; |
+ using iterator_category = std::random_access_iterator_tag; |
+ |
+ circular_deque_const_iterator(const circular_deque<T>* parent, size_t index) |
+ : parent_deque_(parent), index_(index) { |
+#if DCHECK_IS_ON() |
+ created_generation_ = parent->generation_; |
+#endif // DCHECK_IS_ON() |
+ } |
+ |
+ // Dereferencing. |
+ const T& operator*() const { |
+ CheckUnstableUsage(); |
+ parent_deque_->CheckValidIndex(index_); |
+ return parent_deque_->buffer_[index_]; |
+ } |
+ const T* operator->() const { |
+ CheckUnstableUsage(); |
+ parent_deque_->CheckValidIndex(index_); |
+ return &parent_deque_->buffer_[index_]; |
+ } |
+ |
+ // Increment and decrement. |
+ circular_deque_const_iterator& operator++() { |
+ Increment(); |
+ return *this; |
+ } |
+ circular_deque_const_iterator operator++(int) { |
+ circular_deque_const_iterator ret = *this; |
+ Increment(); |
+ return ret; |
+ } |
+ circular_deque_const_iterator& operator--() { |
+ Decrement(); |
+ return *this; |
+ } |
+ circular_deque_const_iterator operator--(int) { |
+ circular_deque_const_iterator ret = *this; |
+ return ret; |
+ } |
+ |
+ // Random access mutation. |
+ friend circular_deque_const_iterator operator+( |
+ const circular_deque_const_iterator& iter, |
+ difference_type offset) { |
+ circular_deque_const_iterator ret = iter; |
+ ret.Add(offset); |
+ return ret; |
+ } |
+ circular_deque_const_iterator& operator+=(difference_type offset) { |
+ Add(offset); |
+ return *this; |
+ } |
+ friend circular_deque_const_iterator operator-( |
+ const circular_deque_const_iterator& iter, |
+ difference_type offset) { |
+ circular_deque_const_iterator ret = iter; |
+ ret.Add(-offset); |
+ return ret; |
+ } |
+ circular_deque_const_iterator& operator-=(difference_type offset) { |
+ Add(-offset); |
+ return *this; |
+ } |
+ |
+ friend std::ptrdiff_t operator-(const circular_deque_const_iterator& lhs, |
+ const circular_deque_const_iterator& rhs) { |
+ lhs.CheckComparable(rhs); |
+ return lhs.OffsetFromBegin() - rhs.OffsetFromBegin(); |
+ } |
+ |
+ // Comparisons. |
+ friend bool operator==(const circular_deque_const_iterator& lhs, |
+ const circular_deque_const_iterator& rhs) { |
+ lhs.CheckComparable(rhs); |
+ return lhs.index_ == rhs.index_; |
+ } |
+ friend bool operator!=(const circular_deque_const_iterator& lhs, |
+ const circular_deque_const_iterator& rhs) { |
+ return !(lhs == rhs); |
+ } |
+ friend bool operator<(const circular_deque_const_iterator& lhs, |
+ const circular_deque_const_iterator& rhs) { |
+ lhs.CheckComparable(rhs); |
+ return lhs.OffsetFromBegin() < rhs.OffsetFromBegin(); |
+ } |
+ friend bool operator<=(const circular_deque_const_iterator& lhs, |
+ const circular_deque_const_iterator& rhs) { |
+ return !(lhs > rhs); |
+ } |
+ friend bool operator>(const circular_deque_const_iterator& lhs, |
+ const circular_deque_const_iterator& rhs) { |
+ lhs.CheckComparable(rhs); |
+ return lhs.OffsetFromBegin() > rhs.OffsetFromBegin(); |
+ } |
+ friend bool operator>=(const circular_deque_const_iterator& lhs, |
+ const circular_deque_const_iterator& rhs) { |
+ return !(lhs < rhs); |
+ } |
+ |
+ protected: |
+ // Returns the offset from the beginning index of the buffer to the current |
+ // iten. |
+ size_t OffsetFromBegin() const { |
+ if (index_ >= parent_deque_->begin_) |
+ return index_ - parent_deque_->begin_; // On the same side as begin. |
+ return parent_deque_->buffer_.capacity() - parent_deque_->begin_ + index_; |
+ } |
+ |
+ void Increment() { |
+ CheckUnstableUsage(); |
+ parent_deque_->CheckValidIndex(index_); |
+ index_++; |
+ if (index_ == parent_deque_->buffer_.capacity()) |
+ index_ = 0; |
+ } |
+ void Decrement() { |
+ CheckUnstableUsage(); |
+ parent_deque_->CheckValidIndexOrEnd(index_); |
+ if (index_ == 0) |
+ index_ = parent_deque_->buffer_.capacity() - 1; |
+ else |
+ index_--; |
+ } |
+ void Add(difference_type delta) { |
+ CheckUnstableUsage(); |
+ parent_deque_->CheckValidIndex(index_); |
+ difference_type new_offset = OffsetFromBegin() + delta; |
+ DCHECK(new_offset >= 0 && |
+ new_offset <= static_cast<difference_type>(parent_deque_->size())); |
+ index_ = (new_offset + parent_deque_->begin_) % |
+ parent_deque_->buffer_.capacity(); |
+ } |
+ |
+#if DCHECK_IS_ON() |
+ void CheckUnstableUsage() const { |
+ // Since circular_deque doesn't guarantee stability, any attempt to |
+ // dereference this iterator after a mutation (i.e. the generation doesn't |
+ // match the original) in the container is illegal. |
+ DCHECK(parent_deque_); |
+ DCHECK_EQ(created_generation_, parent_deque_->generation_) |
+ << "circular_deque iterator dereferenced after mutation."; |
+ } |
+ void CheckComparable(const circular_deque_const_iterator& other) const { |
+ DCHECK_EQ(parent_deque_, other.parent_deque_); |
+ CheckUnstableUsage(); |
+ other.CheckUnstableUsage(); |
+ } |
+#else |
+ inline void CheckUnstableUsage() const {} |
+ inline void CheckInitialized() const {} |
+ inline void CheckComparable() const {} |
+#endif // DCHECK_IS_ON() |
+ |
+ const circular_deque<T>* parent_deque_; |
+ size_t index_; |
+ |
+#if DCHECK_IS_ON() |
+ // The generation of the parent deque when this iterator was created. The |
+ // container will update the generation for every modification so we can |
+ // test if the container was modified by comparing them. |
+ uint64_t created_generation_; |
+#endif // DCHECK_IS_ON() |
+}; |
+ |
+template <typename T> |
+class circular_deque_iterator : public circular_deque_const_iterator<T> { |
+ using base = circular_deque_const_iterator<T>; |
+ |
+ public: |
+ using difference_type = std::ptrdiff_t; |
+ using value_type = T; |
+ using pointer = T*; |
+ using reference = T&; |
+ using iterator_category = std::random_access_iterator_tag; |
+ |
+ circular_deque_iterator(circular_deque<T>* parent, size_t index) |
+ : circular_deque_const_iterator<T>(parent, index) {} |
+ |
+ // Dereferencing. |
+ T& operator*() { return const_cast<T&>(base::operator*()); } |
+ T* operator->() { return const_cast<T*>(base::operator->()); } |
+ |
+ // Random access mutation. |
+ friend circular_deque_iterator operator+(const circular_deque_iterator& iter, |
+ difference_type offset) { |
+ circular_deque_iterator ret = iter; |
+ ret.Add(offset); |
+ return ret; |
+ } |
+ circular_deque_iterator& operator+=(difference_type offset) { |
+ base::Add(offset); |
+ return *this; |
+ } |
+ friend circular_deque_iterator operator-(const circular_deque_iterator& iter, |
+ difference_type offset) { |
+ circular_deque_iterator ret = iter; |
+ ret.Add(-offset); |
+ return ret; |
+ } |
+ circular_deque_iterator& operator-=(difference_type offset) { |
+ base::Add(-offset); |
+ return *this; |
+ } |
+ |
+ // Increment and decrement. |
+ circular_deque_iterator& operator++() { |
+ base::Increment(); |
+ return *this; |
+ } |
+ circular_deque_iterator operator++(int) { |
+ circular_deque_iterator<T> ret = *this; |
+ base::Increment(); |
+ return ret; |
+ } |
+ circular_deque_iterator& operator--() { |
+ base::Decrement(); |
+ return *this; |
+ } |
+ circular_deque_iterator operator--(int) { |
+ circular_deque_iterator<T> ret = *this; |
+ base::Decrement(); |
+ return ret; |
+ } |
+}; |
+ |
+} // namespace internal |
+ |
+template <typename T> |
+class circular_deque { |
+ private: |
+ using VectorBuffer = internal::VectorBuffer<T>; |
+ |
+ public: |
+ using value_type = T; |
+ using size_type = std::size_t; |
+ using difference_type = std::ptrdiff_t; |
+ using reference = value_type&; |
+ using const_reference = const value_type&; |
+ using pointer = value_type*; |
+ using const_pointer = const value_type*; |
+ |
+ using iterator = internal::circular_deque_iterator<T>; |
+ using const_iterator = internal::circular_deque_const_iterator<T>; |
+ using reverse_iterator = std::reverse_iterator<iterator>; |
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
+ |
+ // --------------------------------------------------------------------------- |
+ // Constructor |
+ |
+ circular_deque() : begin_(0), end_(0) {} |
+ |
+ // Constructs with |count| copies of |value| or default constructed version. |
+ circular_deque(size_type count) : circular_deque() { resize(count); } |
+ circular_deque(size_type count, const T& value) : circular_deque() { |
+ resize(count, value); |
+ } |
+ |
+ // Range constructor. |
+ template <class InputIterator> |
+ circular_deque(InputIterator first, InputIterator last) : begin_(0), end_(0) { |
+ assign(first, last); |
+ } |
+ |
+ // Copy/move. |
+ circular_deque(const circular_deque& other) |
+ : buffer_(other.buffer_.capacity()), begin_(0), end_(0) { |
+ assign(other.begin(), other.end()); |
+ } |
+ circular_deque(circular_deque&& other) noexcept |
+ : buffer_(std::move(other.buffer_)), |
+ begin_(other.begin_), |
+ end_(other.end_) { |
+ other.begin_ = 0; |
+ other.end_ = 0; |
+ } |
+ |
+ circular_deque(std::initializer_list<value_type> init) |
+ : buffer_(), begin_(0), end_(0) { |
+ assign(init); |
+ } |
+ |
+ ~circular_deque() {} |
+ |
+ // --------------------------------------------------------------------------- |
+ // Assignments. |
+ // |
+ // All of these may invalidate iterators and references. |
+ |
+ circular_deque& operator=(const circular_deque& other) { |
+ clear(); |
+ reserve(other.size()); |
+ for (size_t i = 0; i < other.size(); i++) |
+ emplace_back(other[i]); |
+ |
+ IncrementGeneration(); |
+ return *this; |
+ } |
+ circular_deque& operator=(circular_deque&& other) noexcept { |
+ clear(); |
+ buffer_ = std::move(other.buffer_); |
+ begin_ = other.begin_; |
+ end_ = other.end_; |
+ |
+ other.begin_ = 0; |
+ other.end_ = 0; |
+ |
+ IncrementGeneration(); |
+ return *this; |
+ } |
+ circular_deque& operator=(std::initializer_list<value_type> ilist) { |
+ assign(std::begin(ilist), std::end(ilist)); |
+ IncrementGeneration(); |
+ return *this; |
+ } |
+ |
+ void assign(size_type count, const value_type& value) { |
+ clear(); |
+ reserve(count); |
+ for (size_t i = 0; i < count; i++) |
+ emplace_back(value); |
+ IncrementGeneration(); |
+ } |
+ |
+ // This variant should be enabled only when InputIterator is an iterator. |
+ template <typename InputIterator> |
+ typename std::enable_if<::base::internal::is_iterator<InputIterator>::value, |
+ void>::type |
+ assign(InputIterator first, InputIterator last) { |
+ // Possible future enhancement, dispatch on iterator tag type. For forward |
+ // iterators we can use std::difference to preallocate the space requried |
+ // and only do one copy. |
+ clear(); |
+ for (; first != last; ++first) |
+ emplace_back(*first); |
+ IncrementGeneration(); |
+ } |
+ |
+ void assign(std::initializer_list<value_type> value) { |
+ assign(value.begin(), value.end()); |
+ } |
+ |
+ // --------------------------------------------------------------------------- |
+ // Accessors. |
+ // |
+ // Since this class assumes no exceptions, at() and operator[] are equivalent. |
+ |
+ value_type& at(size_type i) { |
+ DCHECK(i < size()); |
+ size_t right_size = buffer_.capacity() - begin_; |
+ if (begin_ <= end_ || i < right_size) |
+ return buffer_[begin_ + i]; |
+ return buffer_[i - right_size]; |
+ } |
+ const value_type& at(size_type i) const { |
+ return const_cast<circular_deque*>(this)->at(i); |
+ } |
+ |
+ value_type& operator[](size_type i) { return at(i); } |
+ const value_type& operator[](size_type i) const { |
+ return const_cast<circular_deque*>(this)->at(i); |
+ } |
+ |
+ value_type& front() { |
+ DCHECK(!empty()); |
+ return buffer_[begin_]; |
+ } |
+ const value_type& front() const { |
+ DCHECK(!empty()); |
+ return buffer_[begin_]; |
+ } |
+ |
+ value_type& back() { |
+ DCHECK(!empty()); |
+ return *(--end()); |
+ } |
+ const value_type& back() const { |
+ DCHECK(!empty()); |
+ return *(--end()); |
+ } |
+ |
+ // --------------------------------------------------------------------------- |
+ // Iterators. |
+ |
+ 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(begin()); } |
+ const_reverse_iterator rbegin() const { |
+ return const_reverse_iterator(begin()); |
+ } |
+ const_reverse_iterator crbegin() const { return rbegin(); } |
+ |
+ reverse_iterator rend() { return reverse_iterator(end()); } |
+ const_reverse_iterator rend() const { return const_reverse_iterator(end()); } |
+ const_reverse_iterator crend() const { return rend(); } |
+ |
+ // --------------------------------------------------------------------------- |
+ // Memory management. |
+ |
+ void reserve(size_type new_capacity) { |
+ if (new_capacity > capacity()) |
+ ExpandCapacityTo(new_capacity + 1); |
+ } |
+ size_type capacity() const { |
+ // One item is wasted to indicate end(). |
+ return buffer_.capacity() == 0 ? 0 : buffer_.capacity() - 1; |
+ } |
+ void shrink_to_fit() { |
+ if (empty()) { |
+ // Optimize empty case to really delete everything if there was |
+ // something. |
+ if (buffer_.capacity()) |
+ buffer_ = VectorBuffer(); |
+ } else { |
+ // One item is wasted to indicate end(). |
+ ExpandCapacityTo(size() + 1); |
+ } |
+ } |
+ |
+ // --------------------------------------------------------------------------- |
+ // Size management. |
+ |
+ void clear() { resize(0); } |
+ |
+ bool empty() const { return begin_ == end_; } |
+ size_type size() const { |
+ if (begin_ <= end_) |
+ return end_ - begin_; |
+ return buffer_.capacity() - begin_ + end_; |
+ } |
+ |
+ // When reducing size, the elements are deleted from the end. When expanding |
+ // size, elements are added to the end with |value| or the default |
+ // constructed version. |
+ // |
+ // Resize on a queue should be very unusual so this is a simple |
+ // implementation. It could be optimized if needed. |
+ void resize(size_type count) { |
+ if (count > size()) { |
+ ExpandCapacityTo(count + 1); |
+ while (size() < count) |
+ emplace_back(); |
+ } else if (count < size()) { |
+ while (size() > count) |
+ pop_back(); |
+ } |
+ IncrementGeneration(); |
+ } |
+ void resize(size_type count, const value_type& value) { |
+ if (count > size()) { |
+ ExpandCapacityTo(count + 1); |
+ while (size() < count) |
+ emplace_back(value); |
+ } else if (count < size()) { |
+ while (size() > count) |
+ pop_back(); |
+ } |
+ IncrementGeneration(); |
+ } |
+ |
+ // --------------------------------------------------------------------------- |
+ // Insert and erase. |
+ // |
+ // These bulk insert operations are not provided as described in the file |
+ // level comment above: |
+ // |
+ // void insert(const_iterator pos, size_type count, const T& value); |
+ // void insert(const_iterator pos, InputIterator first, InputIterator last); |
+ // iterator insert(const_iterator pos, const T& value); |
+ // iterator insert(const_iterator pos, T&& value); |
+ // iterator emplace(const_iterator pos, Args&&... args); |
+ // |
+ // iterator erase(const_iterator pos); |
+ // iterator erase(const_iterator first, const_iterator last); |
+ |
+ // --------------------------------------------------------------------------- |
+ // Begin/end operations. |
+ |
+ void push_front(const T& value) { emplace_front(value); } |
+ void push_front(T&& value) { emplace_front(std::move(value)); } |
+ |
+ void push_back(const T& value) { emplace_back(value); } |
+ void push_back(T&& value) { emplace_back(std::move(value)); } |
+ |
+ template <class... Args> |
+ void emplace_front(Args&&... args) { |
+ ExpandCapacityIfNecessary(1); |
+ if (begin_ == 0) |
+ begin_ = buffer_.capacity() - 1; |
+ else |
+ begin_--; |
+ IncrementGeneration(); |
+ new (&buffer_[begin_]) T(std::forward<Args>(args)...); |
+ } |
+ |
+ template <class... Args> |
+ void emplace_back(Args&&... args) { |
+ ExpandCapacityIfNecessary(1); |
+ new (&buffer_[end_]) T(std::forward<Args>(args)...); |
+ if (end_ == buffer_.capacity() - 1) |
+ end_ = 0; |
+ else |
+ end_++; |
+ IncrementGeneration(); |
+ } |
+ |
+ void pop_front() { |
+ DCHECK(size()); |
+ buffer_.DestructRange(&buffer_[begin_], &buffer_[begin_ + 1]); |
+ begin_++; |
+ if (begin_ == buffer_.capacity()) |
+ begin_ = 0; |
+ |
+ // Technically popping will not invalidate any iterators since the |
+ // underlying buffer will be stable. But in the future we may want to add a |
+ // feature that resizes the buffer smaller if there is too much wasted |
+ // space. This ensures we can make such a change safely. |
+ IncrementGeneration(); |
+ } |
+ void pop_back() { |
+ DCHECK(size()); |
+ if (end_ == 0) |
+ end_ = buffer_.capacity() - 1; |
+ else |
+ end_--; |
+ buffer_.DestructRange(&buffer_[end_], &buffer_[end_ + 1]); |
+ |
+ // See pop_front comment about why this is here. |
+ IncrementGeneration(); |
+ } |
+ |
+ // --------------------------------------------------------------------------- |
+ // General operations. |
+ |
+ void swap(circular_deque& other) { |
+ std::swap(buffer_, other.buffer_); |
+ std::swap(begin_, other.begin_); |
+ std::swap(end_, other.end_); |
+ IncrementGeneration(); |
+ } |
+ |
+ friend void swap(circular_deque& lhs, circular_deque& rhs) { lhs.swap(rhs); } |
+ |
+ private: |
+ friend internal::circular_deque_iterator<T>; |
+ friend internal::circular_deque_const_iterator<T>; |
+ |
+ // Moves the items in the given circular buffer to the current one. The |
+ // source is moved from so will become invalid. The destination buffer must |
+ // have already been allocated with enough size. |
+ static void MoveBuffer(VectorBuffer& from_buf, |
+ size_t from_begin, |
+ size_t from_end, |
+ VectorBuffer* to_buf, |
+ size_t* to_begin, |
+ size_t* to_end) { |
+ size_t from_capacity = from_buf.capacity(); |
+ |
+ *to_begin = 0; |
+ if (from_begin < from_end) { |
+ // Contiguous. |
+ from_buf.MoveRange(&from_buf[from_begin], &from_buf[from_end], |
+ to_buf->begin()); |
+ *to_end = from_end - from_begin; |
+ } else if (from_begin > from_end) { |
+ // Discontiguous, copy the right side to the beginning of the new buffer. |
+ from_buf.MoveRange(&from_buf[from_begin], &from_buf[from_capacity], |
+ to_buf->begin()); |
+ size_t right_size = from_capacity - from_begin; |
+ // Append the left side. |
+ from_buf.MoveRange(&from_buf[0], &from_buf[from_end], |
+ &(*to_buf)[right_size]); |
+ *to_end = right_size + from_end; |
+ } else { |
+ // No items. |
+ *to_end = 0; |
+ } |
+ } |
+ |
+ // Expands the buffer size. This assumes the size is larger than the |
+ // number of elements in the vector (it won't call delete on anything). |
+ // Note the capacity passed here will be one larger than the "publicly |
+ // exposed capacity" to account for the unused end element. |
+ void ExpandCapacityTo(size_t new_capacity) { |
+ VectorBuffer new_buffer(new_capacity); |
+ MoveBuffer(buffer_, begin_, end_, &new_buffer, &begin_, &end_); |
+ buffer_ = std::move(new_buffer); |
+ } |
+ void ExpandCapacityIfNecessary(size_t additional_elts) { |
+ // Capacity is internal capacity, which is one extra. |
+ size_t min_new_capacity = size() + additional_elts + 1; |
+ if (buffer_.capacity() >= min_new_capacity) |
+ return; // Already enough room. |
+ |
+ // Start allocating nonempty buffers with this many entries. |
+ constexpr size_t min_slots = 4; |
+ min_new_capacity = std::max(min_new_capacity, min_slots); |
+ |
+ // std::vector always grows by at least 50%. WTF::Deque grows by at least |
+ // 25%. We expect queue workloads to generally stay at a similar size and |
+ // grow less than a vector might, so use 25%. |
+ size_t new_capacity = std::max( |
+ min_new_capacity, buffer_.capacity() + buffer_.capacity() / 4 + 1); |
+ ExpandCapacityTo(new_capacity); |
+ } |
+ |
+#if DCHECK_IS_ON() |
+ // Asserts the given index is dereferencable. The index is an index into the |
+ // buffer, not an index used by operator[] or at() which will be offsets from |
+ // begin. |
+ void CheckValidIndex(size_t i) const { |
+ if (begin_ <= end_) |
+ DCHECK(i >= begin_ && i < end_); |
+ else |
+ DCHECK((i >= begin_ && i < buffer_.capacity()) || i < end_); |
+ } |
+ |
+ // Asserts the given index is either dereferencable or points to end(). |
+ void CheckValidIndexOrEnd(size_t i) const { |
+ if (i != end_) |
+ CheckValidIndex(i); |
+ } |
+ |
+ // See generation_ below. |
+ void IncrementGeneration() { generation_++; } |
+#else |
+ // No-op versions of these functions for release builds. |
+ void CheckValidIndex(size_t) const {} |
+ void CheckValidIndexOrEnd(size_t) const {} |
+ void IncrementGeneration() {} |
+#endif |
+ |
+ // Danger, the buffer_.capacity() is capacity() + 1 since there is an |
+ // extra item to indicate the end. Container internal code will want to use |
+ // buffer_.capacity() for offset computations. |
+ VectorBuffer buffer_; |
+ size_type begin_; |
+ size_type end_; |
+ |
+#if DCHECK_IS_ON() |
+ // Incremented every time a modification that could affect iterator |
+ // invalidations. |
+ uint64_t generation_ = 0; |
+#endif |
+}; |
+ |
+} // namespace base |
+ |
+#endif // BASE_CONTAINERS_CIRCULAR_DEQUE_H_ |