| // Copyright 2023 The Pigweed Authors |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); you may not |
| // use this file except in compliance with the License. You may obtain a copy of |
| // the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| // License for the specific language governing permissions and limitations under |
| // the License. |
| #pragma once |
| |
| #include <algorithm> |
| #include <cstddef> |
| #include <cstdint> |
| #include <initializer_list> |
| #include <iterator> |
| #include <limits> |
| #include <new> |
| #include <type_traits> |
| #include <utility> |
| |
| #include "pw_assert/assert.h" |
| #include "pw_containers/internal/raw_storage.h" |
| #include "pw_preprocessor/compiler.h" |
| #include "pw_span/span.h" |
| |
| namespace pw { |
| namespace inline_circular_buffer_impl { |
| |
| enum Constness : bool { kMutable = false, kConst = true }; |
| |
| template <typename ValueType, typename SizeType, Constness kIsConst> |
| class InlineDequeIterator; |
| |
| } // namespace inline_circular_buffer_impl |
| |
| template <typename T, typename SizeType, size_t kCapacity> |
| class BasicInlineDeque; |
| |
| // Storage for a queue's data and that ensures entries are `clear`'d before |
| // the storage is removed. |
| template <typename ValueType, |
| typename SizeType, |
| size_t kCapacity, |
| bool kIsTriviallyDestructible> |
| class BasicInlineDequeStorage; |
| |
| /// The `InlineDeque` class is similar to the STL's double ended queue |
| /// (`std::deque`), except it is backed by a fixed-size buffer. |
| /// `InlineDeque`'s must be declared with an explicit maximum size (e.g. |
| /// `InlineDeque<int, 10>>`) but deques can be used and referred to without |
| /// the max size template parameter (e.g. `InlineDeque<int>`). |
| /// |
| /// To allow referring to a `pw::InlineDeque` without an explicit maximum |
| /// size, all `InlineDeque` classes inherit from the |
| /// ``BasicInlineDequeStorage`` class, which in turn inherits from |
| /// `InlineDeque<T>`, which stores the maximum size in a variable. This allows |
| /// InlineDeques to be used without having to know their maximum size at compile |
| /// time. It also keeps code size small since function implementations are |
| /// shared for all maximum sizes. |
| template <typename T, size_t kCapacity = containers::internal::kGenericSized> |
| using InlineDeque = BasicInlineDeque<T, uint16_t, kCapacity>; |
| |
| template <typename ValueType, |
| typename SizeType, |
| size_t kCapacity = containers::internal::kGenericSized> |
| class BasicInlineDeque : public BasicInlineDequeStorage< |
| ValueType, |
| SizeType, |
| kCapacity, |
| std::is_trivially_destructible_v<ValueType>> { |
| private: |
| using Base = BasicInlineDeque<ValueType, |
| SizeType, |
| containers::internal::kGenericSized>; |
| |
| public: |
| using typename Base::const_iterator; |
| using typename Base::const_pointer; |
| using typename Base::const_reference; |
| using typename Base::difference_type; |
| using typename Base::iterator; |
| using typename Base::pointer; |
| using typename Base::reference; |
| using typename Base::size_type; |
| using typename Base::value_type; |
| |
| /// Constructs with zero elements. |
| constexpr BasicInlineDeque() noexcept {} |
| |
| /// Constructs with ``count`` copies of ``value``. |
| BasicInlineDeque(size_type count, const_reference value) { |
| Base::assign(count, value); |
| } |
| |
| /// Constructs with ``count`` default-initialized elements. |
| explicit BasicInlineDeque(size_type count) |
| : BasicInlineDeque(count, value_type()) {} |
| |
| /// Copy constructs from an iterator. |
| template < |
| typename InputIterator, |
| typename = containers::internal::EnableIfInputIterator<InputIterator>> |
| BasicInlineDeque(InputIterator start, InputIterator finish) { |
| Base::assign(start, finish); |
| } |
| |
| /// Copy constructs for matching capacity. |
| BasicInlineDeque(const BasicInlineDeque& other) { *this = other; } |
| |
| /// Copy constructs for mismatched capacity. |
| /// |
| /// Note that this will result in a crash if `kOtherCapacity < size()`. |
| template <size_t kOtherCapacity> |
| BasicInlineDeque( |
| const BasicInlineDeque<ValueType, SizeType, kOtherCapacity>& other) { |
| *this = other; |
| } |
| |
| /// Move constructs for matching capacity. |
| BasicInlineDeque(BasicInlineDeque&& other) noexcept { |
| *this = std::move(other); |
| } |
| |
| /// Move constructs for mismatched capacity. |
| template <size_t kOtherCapacity> |
| BasicInlineDeque( |
| BasicInlineDeque<ValueType, SizeType, kOtherCapacity>&& other) noexcept { |
| *this = std::move(other); |
| } |
| |
| /// Copy constructs from an initializer list. |
| BasicInlineDeque(const std::initializer_list<value_type>& list) { |
| *this = list; |
| } |
| |
| /// Copy constructor for arbitrary iterables. |
| template <typename T, typename = containers::internal::EnableIfIterable<T>> |
| BasicInlineDeque(const T& other) { |
| *this = other; |
| } |
| |
| // Assignment operators |
| // |
| // These operators delegate to the base class implementations in order to |
| // maximize code reuse. The wrappers are required so that `operator=` |
| // returns the correct type of reference. |
| // |
| // The `static_cast`s below are unfortunately necessary: without them, |
| // overload resolution prefers to use the "iterable" operators rather than |
| // upcast the RHS. |
| |
| /// Copy assigns from ``list``. |
| BasicInlineDeque& operator=(const std::initializer_list<value_type>& list) { |
| Base::operator=(list); |
| return *this; |
| } |
| |
| /// Copy assigns for matching capacity. |
| BasicInlineDeque& operator=(const BasicInlineDeque& other) { |
| Base::operator=(static_cast<const Base&>(other)); |
| return *this; |
| } |
| |
| /// Copy assigns for mismatched capacity. |
| /// |
| /// Note that this will result in a crash if `kOtherCapacity < size()`. |
| template <size_t kOtherCapacity> |
| BasicInlineDeque& operator=( |
| const BasicInlineDeque<ValueType, SizeType, kOtherCapacity>& other) { |
| Base::operator=(static_cast<const Base&>(other)); |
| return *this; |
| } |
| |
| /// Move assigns for matching capacity. |
| BasicInlineDeque& operator=(BasicInlineDeque&& other) noexcept { |
| Base::operator=(static_cast<Base&&>(std::move(other))); |
| return *this; |
| } |
| |
| /// Move assigns for mismatched capacity. |
| template <size_t kOtherCapacity> |
| BasicInlineDeque& operator=( |
| BasicInlineDeque<ValueType, SizeType, kOtherCapacity>&& other) noexcept { |
| Base::operator=(static_cast<Base&&>(std::move(other))); |
| return *this; |
| } |
| |
| template <typename T, typename = containers::internal::EnableIfIterable<T>> |
| BasicInlineDeque& operator=(const T& other) { |
| Base::operator=(other); |
| return *this; |
| } |
| |
| // Size |
| |
| static constexpr size_type max_size() { return capacity(); } |
| static constexpr size_type capacity() { return kCapacity; } |
| |
| // All other methods are implemented on the generic-sized base class. |
| |
| private: |
| friend class BasicInlineDeque<value_type, |
| size_type, |
| containers::internal::kGenericSized>; |
| |
| static_assert(kCapacity <= std::numeric_limits<size_type>::max()); |
| }; |
| |
| // Specialization of ``BasicInlineDequeue`` for trivially-destructible |
| // ``ValueType``. This specialization ensures that no destructor is generated. |
| template <typename ValueType, typename SizeType, size_t kCapacity> |
| class BasicInlineDequeStorage<ValueType, SizeType, kCapacity, true> |
| : public BasicInlineDeque<ValueType, |
| SizeType, |
| containers::internal::kGenericSized> { |
| // NOTE: no destructor is added, as `ValueType` is trivially-destructible. |
| private: |
| friend class BasicInlineDeque<ValueType, SizeType, kCapacity>; |
| friend class BasicInlineDeque<ValueType, |
| SizeType, |
| containers::internal::kGenericSized>; |
| |
| using Base = BasicInlineDeque<ValueType, |
| SizeType, |
| containers::internal::kGenericSized>; |
| |
| BasicInlineDequeStorage() : Base(kCapacity) {} |
| |
| // The data() function is defined differently for the generic-sized and |
| // known-sized specializations. This data() implementation simply returns the |
| // RawStorage's data(). The generic-sized data() function casts *this to a |
| // known zero-sized specialization to access this exact function. |
| typename Base::pointer data() { return raw_storage_.data(); } |
| typename Base::const_pointer data() const { return raw_storage_.data(); } |
| |
| // Note that this is offset and aligned the same for all possible |
| // kCapacity values for the same value_type. |
| containers::internal::RawStorage<ValueType, kCapacity> raw_storage_; |
| }; |
| |
| // Specialization of ``BasicInlineDequeue`` for non-trivially-destructible |
| // ``ValueType``. This specialization ensures that the queue is cleared |
| // during destruction prior to the invalidation of the `raw_storage_`. |
| template <typename ValueType, typename SizeType, size_t kCapacity> |
| class BasicInlineDequeStorage<ValueType, SizeType, kCapacity, false> |
| : public BasicInlineDeque<ValueType, |
| SizeType, |
| containers::internal::kGenericSized> { |
| public: |
| ~BasicInlineDequeStorage() { Base::clear(); } |
| |
| private: |
| friend class BasicInlineDeque<ValueType, SizeType, kCapacity>; |
| friend class BasicInlineDeque<ValueType, |
| SizeType, |
| containers::internal::kGenericSized>; |
| |
| using Base = BasicInlineDeque<ValueType, |
| SizeType, |
| containers::internal::kGenericSized>; |
| |
| BasicInlineDequeStorage() : Base(kCapacity) {} |
| |
| // The data() function is defined differently for the generic-sized and |
| // known-sized specializations. This data() implementation simply returns the |
| // RawStorage's data(). The generic-sized data() function casts *this to a |
| // known zero-sized specialization to access this exact function. |
| typename Base::pointer data() { return raw_storage_.data(); } |
| typename Base::const_pointer data() const { return raw_storage_.data(); } |
| |
| // Note that this is offset and aligned the same for all possible |
| // kCapacity values for the same value_type. |
| containers::internal::RawStorage<ValueType, kCapacity> raw_storage_; |
| }; |
| |
| // Defines the generic-sized BasicInlineDeque<T> specialization, which |
| // serves as the base class for BasicInlineDeque<T> of any capacity. |
| // |
| // Except for constructors and destructors, all other methods should be |
| // implemented on this generic-sized specialization. Destructors must |
| // only be written for the `BasicInlineDequeStorage` type in order to ensure |
| // that `raw_storage_` is still valid at the time of destruction. |
| // |
| // NOTE: this size-polymorphic base class must not be used inside of |
| // ``std::unique_ptr`` or ``delete``. |
| template <typename ValueType, typename SizeType> |
| class BasicInlineDeque<ValueType, |
| SizeType, |
| containers::internal::kGenericSized> { |
| public: |
| using value_type = ValueType; |
| using size_type = SizeType; |
| using difference_type = ptrdiff_t; |
| using reference = value_type&; |
| using const_reference = const value_type&; |
| using pointer = value_type*; |
| using const_pointer = const value_type*; |
| using iterator = inline_circular_buffer_impl::InlineDequeIterator< |
| value_type, |
| size_type, |
| inline_circular_buffer_impl::Constness::kMutable>; |
| using const_iterator = inline_circular_buffer_impl::InlineDequeIterator< |
| value_type, |
| size_type, |
| inline_circular_buffer_impl::Constness::kConst>; |
| |
| // Polymorphic-sized `pw::InlineDeque<T>` may not be constructed directly. |
| BasicInlineDeque() = delete; |
| |
| // Assignment |
| BasicInlineDeque& operator=(const std::initializer_list<value_type>& list) { |
| assign(list); |
| return *this; |
| } |
| |
| BasicInlineDeque& operator=(const BasicInlineDeque& other) { |
| assign(other.begin(), other.end()); |
| return *this; |
| } |
| |
| BasicInlineDeque& operator=(BasicInlineDeque&& other) noexcept { |
| clear(); |
| for (auto&& item : other) { |
| emplace_back(std::move(item)); |
| } |
| other.clear(); |
| return *this; |
| } |
| |
| template <typename T, typename = containers::internal::EnableIfIterable<T>> |
| BasicInlineDeque& operator=(const T& other) { |
| assign(other.begin(), other.end()); |
| return *this; |
| } |
| |
| void assign(size_type count, const value_type& value) { |
| clear(); |
| Append(count, value); |
| } |
| |
| template < |
| typename InputIterator, |
| typename = containers::internal::EnableIfInputIterator<InputIterator>> |
| void assign(InputIterator start, InputIterator finish) { |
| clear(); |
| CopyFrom(start, finish); |
| } |
| |
| void assign(const std::initializer_list<value_type>& list) { |
| assign(list.begin(), list.end()); |
| } |
| |
| // Access |
| |
| reference at(size_type index) { |
| PW_ASSERT(index < size()); |
| return data()[AbsoluteIndex(index)]; |
| } |
| const_reference at(size_type index) const { |
| PW_ASSERT(index < size()); |
| return data()[AbsoluteIndex(index)]; |
| } |
| |
| reference operator[](size_type index) { |
| PW_DASSERT(index < size()); |
| return data()[AbsoluteIndex(index)]; |
| } |
| const_reference operator[](size_type index) const { |
| PW_DASSERT(index < size()); |
| return data()[AbsoluteIndex(index)]; |
| } |
| |
| reference front() { |
| PW_DASSERT(!empty()); |
| return data()[head_]; |
| } |
| const_reference front() const { |
| PW_DASSERT(!empty()); |
| return data()[head_]; |
| } |
| |
| reference back() { |
| PW_DASSERT(!empty()); |
| return data()[AbsoluteIndex(size() - 1)]; |
| } |
| const_reference back() const { |
| PW_DASSERT(!empty()); |
| return data()[AbsoluteIndex(size() - 1)]; |
| } |
| |
| // Provides access to the valid data in a contiguous form. |
| std::pair<span<const value_type>, span<const value_type>> contiguous_data() |
| const; |
| std::pair<span<value_type>, span<value_type>> contiguous_data() { |
| auto [first, second] = |
| static_cast<const BasicInlineDeque&>(*this).contiguous_data(); |
| return std::make_pair( |
| span<value_type>(const_cast<pointer>(first.data()), first.size()), |
| span<value_type>(const_cast<pointer>(second.data()), second.size())); |
| } |
| |
| // Iterate |
| |
| iterator begin() noexcept { |
| if (empty()) { |
| return end(); |
| } |
| |
| return iterator(this, 0); |
| } |
| const_iterator begin() const noexcept { return cbegin(); } |
| const_iterator cbegin() const noexcept { |
| if (empty()) { |
| return cend(); |
| } |
| return const_iterator(this, 0); |
| } |
| |
| iterator end() noexcept { |
| return iterator(this, std::numeric_limits<size_type>::max()); |
| } |
| const_iterator end() const noexcept { return cend(); } |
| const_iterator cend() const noexcept { |
| return const_iterator(this, std::numeric_limits<size_type>::max()); |
| } |
| |
| // Size |
| |
| [[nodiscard]] bool empty() const noexcept { return size() == 0; } |
| |
| [[nodiscard]] bool full() const noexcept { return size() == max_size(); } |
| |
| // Returns the number of elements in the `InlineDeque`. Disable MSAN since it |
| // thinks `count_` is uninitialized in the destructor. |
| size_type size() const noexcept PW_NO_SANITIZE("memory") { return count_; } |
| |
| size_type max_size() const noexcept { return capacity(); } |
| |
| // Returns the maximum number of elements in the `InlineDeque`. Disable MSAN |
| // since it thinks `capacity_` is uninitialized in the destructor. |
| size_type capacity() const noexcept PW_NO_SANITIZE("memory") { |
| return capacity_; |
| } |
| |
| // Modify |
| |
| void clear() noexcept; |
| |
| void push_back(const value_type& value) { emplace_back(value); } |
| |
| void push_back(value_type&& value) { emplace_back(std::move(value)); } |
| |
| template <typename... Args> |
| void emplace_back(Args&&... args); |
| |
| void pop_back(); |
| |
| void push_front(const value_type& value) { emplace_front(value); } |
| |
| void push_front(value_type&& value) { emplace_front(std::move(value)); } |
| |
| template <typename... Args> |
| void emplace_front(Args&&... args); |
| |
| void pop_front(); |
| |
| void resize(size_type new_size) { resize(new_size, value_type()); } |
| |
| void resize(size_type new_size, const value_type& value); |
| |
| protected: |
| constexpr BasicInlineDeque(size_type capacity) noexcept |
| : capacity_(capacity), head_(0), tail_(0), count_(0) {} |
| |
| // Polymorphic-sized `pw::InlineDeque<T>` may not be used with `unique_ptr` |
| // or `delete`. `delete` could be supported using C++20's destroying delete. |
| ~BasicInlineDeque() = default; |
| |
| private: |
| friend class inline_circular_buffer_impl::InlineDequeIterator< |
| ValueType, |
| SizeType, |
| inline_circular_buffer_impl::Constness::kMutable>; |
| friend class inline_circular_buffer_impl::InlineDequeIterator< |
| ValueType, |
| SizeType, |
| inline_circular_buffer_impl::Constness::kConst>; |
| |
| // The underlying RawStorage is not part of the generic-sized class. It is |
| // provided in the derived class from which this instance was constructed. To |
| // access the data, down-cast this to a known max size specialization, and |
| // return the RawStorage's data, which is the same for all sizes. |
| pointer data() { |
| return static_cast<BasicInlineDeque<value_type, size_type, 0>*>(this) |
| ->data(); |
| } |
| const_pointer data() const { |
| return static_cast<const BasicInlineDeque<value_type, size_type, 0>*>(this) |
| ->data(); |
| } |
| |
| void IncrementWithWrap(size_type& index) const { |
| index++; |
| // Note: branch is faster than mod (%) on common embedded |
| // architectures. |
| if (index == max_size()) { |
| index = 0; |
| } |
| } |
| |
| void DecrementWithWrap(size_type& index) const { |
| if (index == 0) { |
| index = max_size(); |
| } |
| index--; |
| } |
| |
| // Returns the absolute index based on the relative index beyond the |
| // head offset. |
| // |
| // Precondition: The relative index must be valid, i.e. < size(). |
| // |
| // Disable MSAN since it thinks `head_` is uninitialized in the destructor. |
| size_type AbsoluteIndex(const size_type relative_index) const |
| PW_NO_SANITIZE("memory") { |
| const size_type absolute_index = head_ + relative_index; |
| if (absolute_index < max_size()) { |
| return absolute_index; |
| } |
| // Offset wrapped across the end of the circular buffer. |
| return absolute_index - max_size(); |
| } |
| |
| template <typename Iterator> |
| void CopyFrom(Iterator start, Iterator finish); |
| |
| void Append(size_type count, const value_type& value); |
| |
| const size_type capacity_; |
| size_type head_; // Non-inclusive offset for the front. |
| size_type tail_; // Non-inclusive offset for the back. |
| size_type count_; |
| }; |
| |
| // Function implementations |
| |
| template <typename ValueType, typename SizeType> |
| std::pair<span<const ValueType>, span<const ValueType>> |
| BasicInlineDeque<ValueType, SizeType>::contiguous_data() const { |
| if (empty()) { |
| return std::make_pair(span<const value_type>(), span<const value_type>()); |
| } |
| if (tail_ > head_) { |
| // If the newest entry is after the oldest entry, we have not wrapped: |
| // [ |head_|...more_entries...|tail_| ] |
| return std::make_pair(span<const value_type>(&data()[head_], size()), |
| span<const value_type>()); |
| } else { |
| // If the newest entry is before or at the oldest entry and we know we are |
| // not empty, ergo we have wrapped: |
| // [..more_entries...|tail_| |head_|...more_entries...] |
| return std::make_pair( |
| span<const value_type>(&data()[head_], max_size() - head_), |
| span<const value_type>(&data()[0], tail_)); |
| } |
| } |
| |
| template <typename ValueType, typename SizeType> |
| void BasicInlineDeque<ValueType, SizeType>::clear() noexcept { |
| if constexpr (!std::is_trivially_destructible_v<value_type>) { |
| for (auto& item : *this) { |
| item.~value_type(); |
| } |
| } |
| head_ = 0; |
| tail_ = 0; |
| count_ = 0; |
| } |
| |
| template <typename ValueType, typename SizeType> |
| template <typename... Args> |
| void BasicInlineDeque<ValueType, SizeType>::emplace_back(Args&&... args) { |
| PW_ASSERT(!full()); |
| PW_DASSERT(tail_ < capacity()); |
| new (&data()[tail_]) value_type(std::forward<Args>(args)...); |
| IncrementWithWrap(tail_); |
| ++count_; |
| } |
| |
| template <typename ValueType, typename SizeType> |
| void BasicInlineDeque<ValueType, SizeType>::pop_back() { |
| PW_ASSERT(!empty()); |
| PW_DASSERT(tail_ < capacity()); |
| if constexpr (!std::is_trivially_destructible_v<value_type>) { |
| back().~value_type(); |
| } |
| DecrementWithWrap(tail_); |
| --count_; |
| } |
| |
| template <typename ValueType, typename SizeType> |
| template <typename... Args> |
| void BasicInlineDeque<ValueType, SizeType>::emplace_front(Args&&... args) { |
| PW_ASSERT(!full()); |
| DecrementWithWrap(head_); |
| PW_DASSERT(head_ < capacity()); |
| new (&data()[head_]) value_type(std::forward<Args>(args)...); |
| ++count_; |
| } |
| |
| template <typename ValueType, typename SizeType> |
| void BasicInlineDeque<ValueType, SizeType>::pop_front() { |
| PW_ASSERT(!empty()); |
| PW_DASSERT(head_ < capacity()); |
| if constexpr (!std::is_trivially_destructible_v<value_type>) { |
| front().~value_type(); |
| } |
| IncrementWithWrap(head_); |
| --count_; |
| } |
| |
| template <typename ValueType, typename SizeType> |
| void BasicInlineDeque<ValueType, SizeType>::resize(size_type new_size, |
| const value_type& value) { |
| if (size() < new_size) { |
| Append(std::min(max_size(), new_size) - size(), value); |
| } else { |
| while (size() > new_size) { |
| pop_back(); |
| } |
| } |
| } |
| |
| template <typename ValueType, typename SizeType> |
| template <typename Iterator> |
| void BasicInlineDeque<ValueType, SizeType>::CopyFrom(Iterator start, |
| Iterator finish) { |
| while (start != finish) { |
| push_back(*start++); |
| } |
| } |
| |
| template <typename ValueType, typename SizeType> |
| void BasicInlineDeque<ValueType, SizeType>::Append(size_type count, |
| const value_type& value) { |
| for (size_type i = 0; i < count; ++i) { |
| push_back(value); |
| } |
| } |
| |
| namespace inline_circular_buffer_impl { |
| |
| // InlineDequeIterator meets the named requirements for |
| // LegacyRandomAccessIterator |
| template <typename ValueType, typename SizeType, Constness kIsConst> |
| class InlineDequeIterator { |
| public: |
| using container_type = |
| typename std::conditional<kIsConst, |
| const BasicInlineDeque<ValueType, SizeType>, |
| BasicInlineDeque<ValueType, SizeType>>::type; |
| using value_type = ValueType; |
| using size_type = SizeType; |
| typedef typename std::conditional<kIsConst, |
| typename container_type::const_reference, |
| typename container_type::reference>::type |
| reference; |
| typedef |
| typename std::conditional<kIsConst, |
| typename container_type::const_pointer, |
| typename container_type::pointer>::type pointer; |
| using difference_type = std::ptrdiff_t; |
| using iterator_category = std::forward_iterator_tag; |
| |
| constexpr InlineDequeIterator() = default; |
| constexpr InlineDequeIterator(container_type* container, size_type pos) |
| : container_(container), pos_(pos) {} |
| |
| constexpr InlineDequeIterator(const InlineDequeIterator& other) = default; |
| constexpr InlineDequeIterator& operator=(const InlineDequeIterator& other) = |
| default; |
| |
| operator InlineDequeIterator<ValueType, SizeType, Constness::kConst>() const { |
| return {container_, pos_}; |
| } |
| |
| constexpr InlineDequeIterator& Incr(difference_type n) { |
| const difference_type new_pos = |
| n + (pos_ == kEnd ? container_->size() : pos_); |
| |
| PW_DASSERT(new_pos >= 0); |
| PW_DASSERT(new_pos <= container_->size()); |
| |
| pos_ = |
| new_pos == container_->size() ? kEnd : static_cast<size_type>(new_pos); |
| |
| return *this; |
| } |
| |
| constexpr InlineDequeIterator& operator+=(difference_type n) { |
| return Incr(n); |
| } |
| constexpr InlineDequeIterator& operator-=(difference_type n) { |
| return Incr(-n); |
| } |
| constexpr InlineDequeIterator& operator++() { return Incr(1); } |
| constexpr InlineDequeIterator operator++(int) { |
| InlineDequeIterator it(*this); |
| operator++(); |
| return it; |
| } |
| |
| constexpr InlineDequeIterator& operator--() { return Incr(-1); } |
| constexpr InlineDequeIterator operator--(int) { |
| InlineDequeIterator it = *this; |
| operator--(); |
| return it; |
| } |
| |
| constexpr friend InlineDequeIterator operator+(InlineDequeIterator it, |
| difference_type n) { |
| return it += n; |
| } |
| constexpr friend InlineDequeIterator operator+(difference_type n, |
| InlineDequeIterator it) { |
| return it += n; |
| } |
| |
| constexpr friend InlineDequeIterator operator-(InlineDequeIterator it, |
| difference_type n) { |
| return it -= n; |
| } |
| |
| constexpr friend difference_type operator-(const InlineDequeIterator& a, |
| const InlineDequeIterator& b) { |
| return static_cast<difference_type>(a.pos_ == kEnd ? a.container_->size() |
| : a.pos_) - |
| static_cast<difference_type>(b.pos_ == kEnd ? b.container_->size() |
| : b.pos_); |
| } |
| |
| constexpr reference operator*() const { |
| PW_DASSERT(pos_ != kEnd); |
| PW_DASSERT(pos_ < container_->size()); |
| |
| return container_->at(pos_); |
| } |
| |
| constexpr pointer operator->() const { |
| PW_DASSERT(pos_ != kEnd); |
| PW_DASSERT(pos_ < container_->size()); |
| |
| return &**this; |
| } |
| |
| constexpr reference operator[](size_type n) { return *(*this + n); } |
| |
| constexpr bool operator==(const InlineDequeIterator& other) const { |
| return container_ == other.container_ && pos_ == other.pos_; |
| } |
| |
| constexpr bool operator!=(const InlineDequeIterator& other) const { |
| return !(*this == other); |
| } |
| |
| constexpr friend bool operator<(InlineDequeIterator a, |
| InlineDequeIterator b) { |
| return b - a > 0; |
| } |
| |
| constexpr friend bool operator>(InlineDequeIterator a, |
| InlineDequeIterator b) { |
| return b < a; |
| } |
| |
| constexpr friend bool operator<=(InlineDequeIterator a, |
| InlineDequeIterator b) { |
| return !(a > b); |
| } |
| |
| constexpr friend bool operator>=(InlineDequeIterator a, |
| InlineDequeIterator b) { |
| return !(a < b); |
| } |
| |
| private: |
| static constexpr size_type kEnd = std::numeric_limits<size_type>::max(); |
| container_type* container_; // pointer to container this iterator is from |
| size_type pos_; // logical index of iterator |
| }; |
| |
| } // namespace inline_circular_buffer_impl |
| } // namespace pw |