1 // Copyright 2023 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14 #pragma once
15
16 #include <algorithm>
17 #include <cstddef>
18 #include <cstdint>
19 #include <initializer_list>
20 #include <iterator>
21 #include <limits>
22 #include <new>
23 #include <type_traits>
24 #include <utility>
25
26 #include "pw_assert/assert.h"
27 #include "pw_containers/internal/raw_storage.h"
28 #include "pw_preprocessor/compiler.h"
29 #include "pw_span/span.h"
30
31 namespace pw {
32 namespace inline_circular_buffer_impl {
33
34 enum Constness : bool { kMutable = false, kConst = true };
35
36 template <typename ValueType, typename SizeType, Constness kIsConst>
37 class InlineDequeIterator;
38
39 } // namespace inline_circular_buffer_impl
40
41 template <typename T, typename SizeType, size_t kCapacity>
42 class BasicInlineDeque;
43
44 // Storage for a queue's data and that ensures entries are `clear`'d before
45 // the storage is removed.
46 template <typename ValueType,
47 typename SizeType,
48 size_t kCapacity,
49 bool kIsTriviallyDestructible>
50 class BasicInlineDequeStorage;
51
52 /// The `InlineDeque` class is similar to the STL's double ended queue
53 /// (`std::deque`), except it is backed by a fixed-size buffer.
54 /// `InlineDeque`'s must be declared with an explicit maximum size (e.g.
55 /// `InlineDeque<int, 10>>`) but deques can be used and referred to without
56 /// the max size template parameter (e.g. `InlineDeque<int>`).
57 ///
58 /// To allow referring to a `pw::InlineDeque` without an explicit maximum
59 /// size, all `InlineDeque` classes inherit from the
60 /// ``BasicInlineDequeStorage`` class, which in turn inherits from
61 /// `InlineDeque<T>`, which stores the maximum size in a variable. This allows
62 /// InlineDeques to be used without having to know their maximum size at compile
63 /// time. It also keeps code size small since function implementations are
64 /// shared for all maximum sizes.
65 template <typename T, size_t kCapacity = containers::internal::kGenericSized>
66 using InlineDeque = BasicInlineDeque<T, uint16_t, kCapacity>;
67
68 template <typename ValueType,
69 typename SizeType,
70 size_t kCapacity = containers::internal::kGenericSized>
71 class BasicInlineDeque : public BasicInlineDequeStorage<
72 ValueType,
73 SizeType,
74 kCapacity,
75 std::is_trivially_destructible_v<ValueType>> {
76 private:
77 using Base = BasicInlineDeque<ValueType,
78 SizeType,
79 containers::internal::kGenericSized>;
80
81 public:
82 using typename Base::const_iterator;
83 using typename Base::const_pointer;
84 using typename Base::const_reference;
85 using typename Base::difference_type;
86 using typename Base::iterator;
87 using typename Base::pointer;
88 using typename Base::reference;
89 using typename Base::size_type;
90 using typename Base::value_type;
91
92 /// Constructs with zero elements.
BasicInlineDeque()93 constexpr BasicInlineDeque() noexcept {}
94
95 /// Constructs with ``count`` copies of ``value``.
BasicInlineDeque(size_type count,const_reference value)96 BasicInlineDeque(size_type count, const_reference value) {
97 Base::assign(count, value);
98 }
99
100 /// Constructs with ``count`` default-initialized elements.
BasicInlineDeque(size_type count)101 explicit BasicInlineDeque(size_type count)
102 : BasicInlineDeque(count, value_type()) {}
103
104 /// Copy constructs from an iterator.
105 template <
106 typename InputIterator,
107 typename = containers::internal::EnableIfInputIterator<InputIterator>>
BasicInlineDeque(InputIterator start,InputIterator finish)108 BasicInlineDeque(InputIterator start, InputIterator finish) {
109 Base::assign(start, finish);
110 }
111
112 /// Copy constructs for matching capacity.
BasicInlineDeque(const BasicInlineDeque & other)113 BasicInlineDeque(const BasicInlineDeque& other) { *this = other; }
114
115 /// Copy constructs for mismatched capacity.
116 ///
117 /// Note that this will result in a crash if `kOtherCapacity < size()`.
118 template <size_t kOtherCapacity>
BasicInlineDeque(const BasicInlineDeque<ValueType,SizeType,kOtherCapacity> & other)119 BasicInlineDeque(
120 const BasicInlineDeque<ValueType, SizeType, kOtherCapacity>& other) {
121 *this = other;
122 }
123
124 /// Move constructs for matching capacity.
BasicInlineDeque(BasicInlineDeque && other)125 BasicInlineDeque(BasicInlineDeque&& other) noexcept {
126 *this = std::move(other);
127 }
128
129 /// Move constructs for mismatched capacity.
130 template <size_t kOtherCapacity>
BasicInlineDeque(BasicInlineDeque<ValueType,SizeType,kOtherCapacity> && other)131 BasicInlineDeque(
132 BasicInlineDeque<ValueType, SizeType, kOtherCapacity>&& other) noexcept {
133 *this = std::move(other);
134 }
135
136 /// Copy constructs from an initializer list.
BasicInlineDeque(const std::initializer_list<value_type> & list)137 BasicInlineDeque(const std::initializer_list<value_type>& list) {
138 *this = list;
139 }
140
141 /// Copy constructor for arbitrary iterables.
142 template <typename T, typename = containers::internal::EnableIfIterable<T>>
BasicInlineDeque(const T & other)143 BasicInlineDeque(const T& other) {
144 *this = other;
145 }
146
147 // Assignment operators
148 //
149 // These operators delegate to the base class implementations in order to
150 // maximize code reuse. The wrappers are required so that `operator=`
151 // returns the correct type of reference.
152 //
153 // The `static_cast`s below are unfortunately necessary: without them,
154 // overload resolution prefers to use the "iterable" operators rather than
155 // upcast the RHS.
156
157 /// Copy assigns from ``list``.
158 BasicInlineDeque& operator=(const std::initializer_list<value_type>& list) {
159 Base::operator=(list);
160 return *this;
161 }
162
163 /// Copy assigns for matching capacity.
164 BasicInlineDeque& operator=(const BasicInlineDeque& other) {
165 Base::operator=(static_cast<const Base&>(other));
166 return *this;
167 }
168
169 /// Copy assigns for mismatched capacity.
170 ///
171 /// Note that this will result in a crash if `kOtherCapacity < size()`.
172 template <size_t kOtherCapacity>
173 BasicInlineDeque& operator=(
174 const BasicInlineDeque<ValueType, SizeType, kOtherCapacity>& other) {
175 Base::operator=(static_cast<const Base&>(other));
176 return *this;
177 }
178
179 /// Move assigns for matching capacity.
180 BasicInlineDeque& operator=(BasicInlineDeque&& other) noexcept {
181 Base::operator=(static_cast<Base&&>(std::move(other)));
182 return *this;
183 }
184
185 /// Move assigns for mismatched capacity.
186 template <size_t kOtherCapacity>
187 BasicInlineDeque& operator=(
188 BasicInlineDeque<ValueType, SizeType, kOtherCapacity>&& other) noexcept {
189 Base::operator=(static_cast<Base&&>(std::move(other)));
190 return *this;
191 }
192
193 template <typename T, typename = containers::internal::EnableIfIterable<T>>
194 BasicInlineDeque& operator=(const T& other) {
195 Base::operator=(other);
196 return *this;
197 }
198
199 // Size
200
max_size()201 static constexpr size_type max_size() { return capacity(); }
capacity()202 static constexpr size_type capacity() { return kCapacity; }
203
204 // All other methods are implemented on the generic-sized base class.
205
206 private:
207 friend class BasicInlineDeque<value_type,
208 size_type,
209 containers::internal::kGenericSized>;
210
211 static_assert(kCapacity <= std::numeric_limits<size_type>::max());
212 };
213
214 // Specialization of ``BasicInlineDequeue`` for trivially-destructible
215 // ``ValueType``. This specialization ensures that no destructor is generated.
216 template <typename ValueType, typename SizeType, size_t kCapacity>
217 class BasicInlineDequeStorage<ValueType, SizeType, kCapacity, true>
218 : public BasicInlineDeque<ValueType,
219 SizeType,
220 containers::internal::kGenericSized> {
221 // NOTE: no destructor is added, as `ValueType` is trivially-destructible.
222 private:
223 friend class BasicInlineDeque<ValueType, SizeType, kCapacity>;
224 friend class BasicInlineDeque<ValueType,
225 SizeType,
226 containers::internal::kGenericSized>;
227
228 using Base = BasicInlineDeque<ValueType,
229 SizeType,
230 containers::internal::kGenericSized>;
231
BasicInlineDequeStorage()232 BasicInlineDequeStorage() : Base(kCapacity) {}
233
234 // The data() function is defined differently for the generic-sized and
235 // known-sized specializations. This data() implementation simply returns the
236 // RawStorage's data(). The generic-sized data() function casts *this to a
237 // known zero-sized specialization to access this exact function.
data()238 typename Base::pointer data() { return raw_storage_.data(); }
data()239 typename Base::const_pointer data() const { return raw_storage_.data(); }
240
241 // Note that this is offset and aligned the same for all possible
242 // kCapacity values for the same value_type.
243 containers::internal::RawStorage<ValueType, kCapacity> raw_storage_;
244 };
245
246 // Specialization of ``BasicInlineDequeue`` for non-trivially-destructible
247 // ``ValueType``. This specialization ensures that the queue is cleared
248 // during destruction prior to the invalidation of the `raw_storage_`.
249 template <typename ValueType, typename SizeType, size_t kCapacity>
250 class BasicInlineDequeStorage<ValueType, SizeType, kCapacity, false>
251 : public BasicInlineDeque<ValueType,
252 SizeType,
253 containers::internal::kGenericSized> {
254 public:
~BasicInlineDequeStorage()255 ~BasicInlineDequeStorage() { Base::clear(); }
256
257 private:
258 friend class BasicInlineDeque<ValueType, SizeType, kCapacity>;
259 friend class BasicInlineDeque<ValueType,
260 SizeType,
261 containers::internal::kGenericSized>;
262
263 using Base = BasicInlineDeque<ValueType,
264 SizeType,
265 containers::internal::kGenericSized>;
266
BasicInlineDequeStorage()267 BasicInlineDequeStorage() : Base(kCapacity) {}
268
269 // The data() function is defined differently for the generic-sized and
270 // known-sized specializations. This data() implementation simply returns the
271 // RawStorage's data(). The generic-sized data() function casts *this to a
272 // known zero-sized specialization to access this exact function.
data()273 typename Base::pointer data() { return raw_storage_.data(); }
data()274 typename Base::const_pointer data() const { return raw_storage_.data(); }
275
276 // Note that this is offset and aligned the same for all possible
277 // kCapacity values for the same value_type.
278 containers::internal::RawStorage<ValueType, kCapacity> raw_storage_;
279 };
280
281 // Defines the generic-sized BasicInlineDeque<T> specialization, which
282 // serves as the base class for BasicInlineDeque<T> of any capacity.
283 //
284 // Except for constructors and destructors, all other methods should be
285 // implemented on this generic-sized specialization. Destructors must
286 // only be written for the `BasicInlineDequeStorage` type in order to ensure
287 // that `raw_storage_` is still valid at the time of destruction.
288 //
289 // NOTE: this size-polymorphic base class must not be used inside of
290 // ``std::unique_ptr`` or ``delete``.
291 template <typename ValueType, typename SizeType>
292 class BasicInlineDeque<ValueType,
293 SizeType,
294 containers::internal::kGenericSized> {
295 public:
296 using value_type = ValueType;
297 using size_type = SizeType;
298 using difference_type = ptrdiff_t;
299 using reference = value_type&;
300 using const_reference = const value_type&;
301 using pointer = value_type*;
302 using const_pointer = const value_type*;
303 using iterator = inline_circular_buffer_impl::InlineDequeIterator<
304 value_type,
305 size_type,
306 inline_circular_buffer_impl::Constness::kMutable>;
307 using const_iterator = inline_circular_buffer_impl::InlineDequeIterator<
308 value_type,
309 size_type,
310 inline_circular_buffer_impl::Constness::kConst>;
311
312 // Polymorphic-sized `pw::InlineDeque<T>` may not be constructed directly.
313 BasicInlineDeque() = delete;
314
315 // Assignment
316 BasicInlineDeque& operator=(const std::initializer_list<value_type>& list) {
317 assign(list);
318 return *this;
319 }
320
321 BasicInlineDeque& operator=(const BasicInlineDeque& other) {
322 assign(other.begin(), other.end());
323 return *this;
324 }
325
326 BasicInlineDeque& operator=(BasicInlineDeque&& other) noexcept {
327 clear();
328 for (auto&& item : other) {
329 emplace_back(std::move(item));
330 }
331 other.clear();
332 return *this;
333 }
334
335 template <typename T, typename = containers::internal::EnableIfIterable<T>>
336 BasicInlineDeque& operator=(const T& other) {
337 assign(other.begin(), other.end());
338 return *this;
339 }
340
assign(size_type count,const value_type & value)341 void assign(size_type count, const value_type& value) {
342 clear();
343 Append(count, value);
344 }
345
346 template <
347 typename InputIterator,
348 typename = containers::internal::EnableIfInputIterator<InputIterator>>
assign(InputIterator start,InputIterator finish)349 void assign(InputIterator start, InputIterator finish) {
350 clear();
351 CopyFrom(start, finish);
352 }
353
assign(const std::initializer_list<value_type> & list)354 void assign(const std::initializer_list<value_type>& list) {
355 assign(list.begin(), list.end());
356 }
357
358 // Access
359
at(size_type index)360 reference at(size_type index) {
361 PW_ASSERT(index < size());
362 return data()[AbsoluteIndex(index)];
363 }
at(size_type index)364 const_reference at(size_type index) const {
365 PW_ASSERT(index < size());
366 return data()[AbsoluteIndex(index)];
367 }
368
369 reference operator[](size_type index) {
370 PW_DASSERT(index < size());
371 return data()[AbsoluteIndex(index)];
372 }
373 const_reference operator[](size_type index) const {
374 PW_DASSERT(index < size());
375 return data()[AbsoluteIndex(index)];
376 }
377
front()378 reference front() {
379 PW_DASSERT(!empty());
380 return data()[head_];
381 }
front()382 const_reference front() const {
383 PW_DASSERT(!empty());
384 return data()[head_];
385 }
386
back()387 reference back() {
388 PW_DASSERT(!empty());
389 return data()[AbsoluteIndex(size() - 1)];
390 }
back()391 const_reference back() const {
392 PW_DASSERT(!empty());
393 return data()[AbsoluteIndex(size() - 1)];
394 }
395
396 // Provides access to the valid data in a contiguous form.
397 std::pair<span<const value_type>, span<const value_type>> contiguous_data()
398 const;
contiguous_data()399 std::pair<span<value_type>, span<value_type>> contiguous_data() {
400 auto [first, second] =
401 static_cast<const BasicInlineDeque&>(*this).contiguous_data();
402 return std::make_pair(
403 span<value_type>(const_cast<pointer>(first.data()), first.size()),
404 span<value_type>(const_cast<pointer>(second.data()), second.size()));
405 }
406
407 // Iterate
408
begin()409 iterator begin() noexcept {
410 if (empty()) {
411 return end();
412 }
413
414 return iterator(this, 0);
415 }
begin()416 const_iterator begin() const noexcept { return cbegin(); }
cbegin()417 const_iterator cbegin() const noexcept {
418 if (empty()) {
419 return cend();
420 }
421 return const_iterator(this, 0);
422 }
423
end()424 iterator end() noexcept {
425 return iterator(this, std::numeric_limits<size_type>::max());
426 }
end()427 const_iterator end() const noexcept { return cend(); }
cend()428 const_iterator cend() const noexcept {
429 return const_iterator(this, std::numeric_limits<size_type>::max());
430 }
431
432 // Size
433
empty()434 [[nodiscard]] bool empty() const noexcept { return size() == 0; }
435
full()436 [[nodiscard]] bool full() const noexcept { return size() == max_size(); }
437
438 // Returns the number of elements in the `InlineDeque`. Disable MSAN since it
439 // thinks `count_` is uninitialized in the destructor.
size()440 size_type size() const noexcept PW_NO_SANITIZE("memory") { return count_; }
441
max_size()442 size_type max_size() const noexcept { return capacity(); }
443
444 // Returns the maximum number of elements in the `InlineDeque`. Disable MSAN
445 // since it thinks `capacity_` is uninitialized in the destructor.
capacity()446 size_type capacity() const noexcept PW_NO_SANITIZE("memory") {
447 return capacity_;
448 }
449
450 // Modify
451
452 void clear() noexcept;
453
push_back(const value_type & value)454 void push_back(const value_type& value) { emplace_back(value); }
455
push_back(value_type && value)456 void push_back(value_type&& value) { emplace_back(std::move(value)); }
457
458 template <typename... Args>
459 void emplace_back(Args&&... args);
460
461 void pop_back();
462
push_front(const value_type & value)463 void push_front(const value_type& value) { emplace_front(value); }
464
push_front(value_type && value)465 void push_front(value_type&& value) { emplace_front(std::move(value)); }
466
467 template <typename... Args>
468 void emplace_front(Args&&... args);
469
470 void pop_front();
471
resize(size_type new_size)472 void resize(size_type new_size) { resize(new_size, value_type()); }
473
474 void resize(size_type new_size, const value_type& value);
475
476 protected:
BasicInlineDeque(size_type capacity)477 constexpr BasicInlineDeque(size_type capacity) noexcept
478 : capacity_(capacity), head_(0), tail_(0), count_(0) {}
479
480 // Polymorphic-sized `pw::InlineDeque<T>` may not be used with `unique_ptr`
481 // or `delete`. `delete` could be supported using C++20's destroying delete.
482 ~BasicInlineDeque() = default;
483
484 private:
485 friend class inline_circular_buffer_impl::InlineDequeIterator<
486 ValueType,
487 SizeType,
488 inline_circular_buffer_impl::Constness::kMutable>;
489 friend class inline_circular_buffer_impl::InlineDequeIterator<
490 ValueType,
491 SizeType,
492 inline_circular_buffer_impl::Constness::kConst>;
493
494 // The underlying RawStorage is not part of the generic-sized class. It is
495 // provided in the derived class from which this instance was constructed. To
496 // access the data, down-cast this to a known max size specialization, and
497 // return the RawStorage's data, which is the same for all sizes.
data()498 pointer data() {
499 return static_cast<BasicInlineDeque<value_type, size_type, 0>*>(this)
500 ->data();
501 }
data()502 const_pointer data() const {
503 return static_cast<const BasicInlineDeque<value_type, size_type, 0>*>(this)
504 ->data();
505 }
506
IncrementWithWrap(size_type & index)507 void IncrementWithWrap(size_type& index) const {
508 index++;
509 // Note: branch is faster than mod (%) on common embedded
510 // architectures.
511 if (index == max_size()) {
512 index = 0;
513 }
514 }
515
DecrementWithWrap(size_type & index)516 void DecrementWithWrap(size_type& index) const {
517 if (index == 0) {
518 index = max_size();
519 }
520 index--;
521 }
522
523 // Returns the absolute index based on the relative index beyond the
524 // head offset.
525 //
526 // Precondition: The relative index must be valid, i.e. < size().
527 //
528 // Disable MSAN since it thinks `head_` is uninitialized in the destructor.
AbsoluteIndex(const size_type relative_index)529 size_type AbsoluteIndex(const size_type relative_index) const
530 PW_NO_SANITIZE("memory") {
531 const size_type absolute_index = head_ + relative_index;
532 if (absolute_index < max_size()) {
533 return absolute_index;
534 }
535 // Offset wrapped across the end of the circular buffer.
536 return absolute_index - max_size();
537 }
538
539 template <typename Iterator>
540 void CopyFrom(Iterator start, Iterator finish);
541
542 void Append(size_type count, const value_type& value);
543
544 const size_type capacity_;
545 size_type head_; // Non-inclusive offset for the front.
546 size_type tail_; // Non-inclusive offset for the back.
547 size_type count_;
548 };
549
550 // Function implementations
551
552 template <typename ValueType, typename SizeType>
553 std::pair<span<const ValueType>, span<const ValueType>>
contiguous_data()554 BasicInlineDeque<ValueType, SizeType>::contiguous_data() const {
555 if (empty()) {
556 return std::make_pair(span<const value_type>(), span<const value_type>());
557 }
558 if (tail_ > head_) {
559 // If the newest entry is after the oldest entry, we have not wrapped:
560 // [ |head_|...more_entries...|tail_| ]
561 return std::make_pair(span<const value_type>(&data()[head_], size()),
562 span<const value_type>());
563 } else {
564 // If the newest entry is before or at the oldest entry and we know we are
565 // not empty, ergo we have wrapped:
566 // [..more_entries...|tail_| |head_|...more_entries...]
567 return std::make_pair(
568 span<const value_type>(&data()[head_], max_size() - head_),
569 span<const value_type>(&data()[0], tail_));
570 }
571 }
572
573 template <typename ValueType, typename SizeType>
clear()574 void BasicInlineDeque<ValueType, SizeType>::clear() noexcept {
575 if constexpr (!std::is_trivially_destructible_v<value_type>) {
576 for (auto& item : *this) {
577 item.~value_type();
578 }
579 }
580 head_ = 0;
581 tail_ = 0;
582 count_ = 0;
583 }
584
585 template <typename ValueType, typename SizeType>
586 template <typename... Args>
emplace_back(Args &&...args)587 void BasicInlineDeque<ValueType, SizeType>::emplace_back(Args&&... args) {
588 PW_ASSERT(!full());
589 PW_DASSERT(tail_ < capacity());
590 new (&data()[tail_]) value_type(std::forward<Args>(args)...);
591 IncrementWithWrap(tail_);
592 ++count_;
593 }
594
595 template <typename ValueType, typename SizeType>
pop_back()596 void BasicInlineDeque<ValueType, SizeType>::pop_back() {
597 PW_ASSERT(!empty());
598 PW_DASSERT(tail_ < capacity());
599 if constexpr (!std::is_trivially_destructible_v<value_type>) {
600 back().~value_type();
601 }
602 DecrementWithWrap(tail_);
603 --count_;
604 }
605
606 template <typename ValueType, typename SizeType>
607 template <typename... Args>
emplace_front(Args &&...args)608 void BasicInlineDeque<ValueType, SizeType>::emplace_front(Args&&... args) {
609 PW_ASSERT(!full());
610 DecrementWithWrap(head_);
611 PW_DASSERT(head_ < capacity());
612 new (&data()[head_]) value_type(std::forward<Args>(args)...);
613 ++count_;
614 }
615
616 template <typename ValueType, typename SizeType>
pop_front()617 void BasicInlineDeque<ValueType, SizeType>::pop_front() {
618 PW_ASSERT(!empty());
619 PW_DASSERT(head_ < capacity());
620 if constexpr (!std::is_trivially_destructible_v<value_type>) {
621 front().~value_type();
622 }
623 IncrementWithWrap(head_);
624 --count_;
625 }
626
627 template <typename ValueType, typename SizeType>
resize(size_type new_size,const value_type & value)628 void BasicInlineDeque<ValueType, SizeType>::resize(size_type new_size,
629 const value_type& value) {
630 if (size() < new_size) {
631 Append(std::min(max_size(), new_size) - size(), value);
632 } else {
633 while (size() > new_size) {
634 pop_back();
635 }
636 }
637 }
638
639 template <typename ValueType, typename SizeType>
640 template <typename Iterator>
CopyFrom(Iterator start,Iterator finish)641 void BasicInlineDeque<ValueType, SizeType>::CopyFrom(Iterator start,
642 Iterator finish) {
643 while (start != finish) {
644 push_back(*start++);
645 }
646 }
647
648 template <typename ValueType, typename SizeType>
Append(size_type count,const value_type & value)649 void BasicInlineDeque<ValueType, SizeType>::Append(size_type count,
650 const value_type& value) {
651 for (size_type i = 0; i < count; ++i) {
652 push_back(value);
653 }
654 }
655
656 namespace inline_circular_buffer_impl {
657
658 // InlineDequeIterator meets the named requirements for
659 // LegacyRandomAccessIterator
660 template <typename ValueType, typename SizeType, Constness kIsConst>
661 class InlineDequeIterator {
662 public:
663 using container_type =
664 typename std::conditional<kIsConst,
665 const BasicInlineDeque<ValueType, SizeType>,
666 BasicInlineDeque<ValueType, SizeType>>::type;
667 using value_type = ValueType;
668 using size_type = SizeType;
669 typedef typename std::conditional<kIsConst,
670 typename container_type::const_reference,
671 typename container_type::reference>::type
672 reference;
673 typedef
674 typename std::conditional<kIsConst,
675 typename container_type::const_pointer,
676 typename container_type::pointer>::type pointer;
677 using difference_type = std::ptrdiff_t;
678 using iterator_category = std::forward_iterator_tag;
679
680 constexpr InlineDequeIterator() = default;
InlineDequeIterator(container_type * container,size_type pos)681 constexpr InlineDequeIterator(container_type* container, size_type pos)
682 : container_(container), pos_(pos) {}
683
684 constexpr InlineDequeIterator(const InlineDequeIterator& other) = default;
685 constexpr InlineDequeIterator& operator=(const InlineDequeIterator& other) =
686 default;
687
688 operator InlineDequeIterator<ValueType, SizeType, Constness::kConst>() const {
689 return {container_, pos_};
690 }
691
Incr(difference_type n)692 constexpr InlineDequeIterator& Incr(difference_type n) {
693 const difference_type new_pos =
694 n + (pos_ == kEnd ? container_->size() : pos_);
695
696 PW_DASSERT(new_pos >= 0);
697 PW_DASSERT(new_pos <= container_->size());
698
699 pos_ =
700 new_pos == container_->size() ? kEnd : static_cast<size_type>(new_pos);
701
702 return *this;
703 }
704
705 constexpr InlineDequeIterator& operator+=(difference_type n) {
706 return Incr(n);
707 }
708 constexpr InlineDequeIterator& operator-=(difference_type n) {
709 return Incr(-n);
710 }
711 constexpr InlineDequeIterator& operator++() { return Incr(1); }
712 constexpr InlineDequeIterator operator++(int) {
713 InlineDequeIterator it(*this);
714 operator++();
715 return it;
716 }
717
718 constexpr InlineDequeIterator& operator--() { return Incr(-1); }
719 constexpr InlineDequeIterator operator--(int) {
720 InlineDequeIterator it = *this;
721 operator--();
722 return it;
723 }
724
725 constexpr friend InlineDequeIterator operator+(InlineDequeIterator it,
726 difference_type n) {
727 return it += n;
728 }
729 constexpr friend InlineDequeIterator operator+(difference_type n,
730 InlineDequeIterator it) {
731 return it += n;
732 }
733
734 constexpr friend InlineDequeIterator operator-(InlineDequeIterator it,
735 difference_type n) {
736 return it -= n;
737 }
738
739 constexpr friend difference_type operator-(const InlineDequeIterator& a,
740 const InlineDequeIterator& b) {
741 return static_cast<difference_type>(a.pos_ == kEnd ? a.container_->size()
742 : a.pos_) -
743 static_cast<difference_type>(b.pos_ == kEnd ? b.container_->size()
744 : b.pos_);
745 }
746
747 constexpr reference operator*() const {
748 PW_DASSERT(pos_ != kEnd);
749 PW_DASSERT(pos_ < container_->size());
750
751 return container_->at(pos_);
752 }
753
754 constexpr pointer operator->() const {
755 PW_DASSERT(pos_ != kEnd);
756 PW_DASSERT(pos_ < container_->size());
757
758 return &**this;
759 }
760
761 constexpr reference operator[](size_type n) { return *(*this + n); }
762
763 constexpr bool operator==(const InlineDequeIterator& other) const {
764 return container_ == other.container_ && pos_ == other.pos_;
765 }
766
767 constexpr bool operator!=(const InlineDequeIterator& other) const {
768 return !(*this == other);
769 }
770
771 constexpr friend bool operator<(InlineDequeIterator a,
772 InlineDequeIterator b) {
773 return b - a > 0;
774 }
775
776 constexpr friend bool operator>(InlineDequeIterator a,
777 InlineDequeIterator b) {
778 return b < a;
779 }
780
781 constexpr friend bool operator<=(InlineDequeIterator a,
782 InlineDequeIterator b) {
783 return !(a > b);
784 }
785
786 constexpr friend bool operator>=(InlineDequeIterator a,
787 InlineDequeIterator b) {
788 return !(a < b);
789 }
790
791 private:
792 static constexpr size_type kEnd = std::numeric_limits<size_type>::max();
793 container_type* container_; // pointer to container this iterator is from
794 size_type pos_; // logical index of iterator
795 };
796
797 } // namespace inline_circular_buffer_impl
798 } // namespace pw
799