FastLED 3.10.10
Loading...
Searching...
No Matches
deque.h
Go to the documentation of this file.
1#pragma once
2
3#include "fl/stl/stdint.h"
4
5#include "fl/stl/deque_basic.h" // detail::deque_grow_map_capacity (#3270)
6#include "fl/stl/move.h"
7#include "fl/stl/iterator.h"
9#include "fl/stl/new.h" // IWYU pragma: keep
10#include "fl/stl/noexcept.h"
11#include "fl/system/sketch_macros.h" // FL_PLATFORM_HAS_LARGE_MEMORY
12
13namespace fl {
14
15// Per-type chunk-size trait. Specialize to override the default chunk size
16// for a particular T (e.g. when the typical deque<T> sliding window has a
17// known fixed extent that should match the chunk size). See FastLED #3270.
18template <typename T>
20 static constexpr fl::size chunk_size =
21#if FL_PLATFORM_HAS_LARGE_MEMORY
22 64u;
23#else
24 16u;
25#endif
26};
27
28template <typename T>
29class deque {
30private:
31 // Map-of-fixed-size-chunks layout. Existing elements are NEVER moved on
32 // grow; only the chunk-pointer map is reallocated when one side runs out
33 // of room. push_back / push_front allocate a new chunk at the active
34 // end as needed; intermediate chunks (between front and back) are
35 // always allocated. See FastLED #3270.
36 static constexpr fl::size kChunkSize = deque_traits<T>::chunk_size;
37
38 T** mMap = nullptr; // array of T* chunk pointers, length mMapCapacity
39 fl::size mMapCapacity = 0; // number of chunk slots in mMap
40 fl::size mFrontMapIdx = 0; // index in mMap of the chunk holding the front element
41 fl::size mFrontOffset = 0; // offset within front chunk of the front element [0, kChunkSize)
42 fl::size mSize = 0; // total elements
44
46 return static_cast<T*>(mResource->allocate(kChunkSize * sizeof(T)));
47 }
48
50 if (chunk) {
51 mResource->deallocate(chunk, kChunkSize * sizeof(T));
52 }
53 }
54
56 T** m = static_cast<T**>(mResource->allocate(capacity * sizeof(T*)));
57 if (m) {
58 for (fl::size i = 0; i < capacity; ++i) {
59 m[i] = nullptr;
60 }
61 }
62 return m;
63 }
64
66 if (map) {
67 mResource->deallocate(map, capacity * sizeof(T*));
68 }
69 }
70
71 // Translate logical index -> (chunk_idx in mMap, offset within chunk).
72 // Caller validates `logical_idx < mSize` (or == mSize for end-position).
73 void locate(fl::size logical_idx, fl::size& chunk_idx, fl::size& offset) const FL_NO_EXCEPT {
74 fl::size global = mFrontOffset + logical_idx;
75 chunk_idx = mFrontMapIdx + global / kChunkSize;
76 offset = global % kChunkSize;
77 }
78
79 // Number of currently-used chunk slots [mFrontMapIdx .. back_chunk_idx].
80 fl::size used_chunks() const FL_NO_EXCEPT {
81 if (mSize == 0) return 0;
82 fl::size last_global = mFrontOffset + mSize - 1;
83 fl::size last_chunk = mFrontMapIdx + last_global / kChunkSize;
84 return last_chunk - mFrontMapIdx + 1;
85 }
86
87 // Grow the chunk-pointer map. After return:
88 // - mMap has at least `extra_front` empty slots before mFrontMapIdx
89 // - mMap has at least `extra_back` empty slots after the back chunk
90 // Live chunk pointers in [mFrontMapIdx, mFrontMapIdx+used) are preserved
91 // (chunks themselves are never moved). Orphaned chunks outside that range
92 // (left behind by prior pop_front / pop_back when a chunk emptied without
93 // being released) are FREED here -- otherwise the old `mMap` is
94 // deallocated below and those chunk pointers are lost forever, leaking
95 // their backing storage. See FastLED #3286.
96 // mFrontMapIdx may shift to a new position within the new map.
97 void grow_map(fl::size extra_front, fl::size extra_back) FL_NO_EXCEPT {
98 fl::size used = used_chunks();
99 fl::size needed = used + extra_front + extra_back;
100 fl::size new_cap = detail::deque_grow_map_capacity(mMapCapacity, needed);
101 // Center the existing chunks within the new map, biased to leave the
102 // requested extra room on each side.
103 fl::size new_front = extra_front + (new_cap - needed) / 2;
104 T** new_map = allocate_map(new_cap);
105 if (!new_map) {
106 // Allocation failure: match the silent-fail behavior of the prior
107 // vector-style ensure_capacity. Callers must defensively check
108 // capacity / size after push_*.
109 return;
110 }
111 // Free any chunk pointers in the OLD map that live outside the
112 // [mFrontMapIdx, mFrontMapIdx+used) live range; those are orphans
113 // and would otherwise leak when the old map is deallocated.
114 fl::size live_end = mFrontMapIdx + used;
115 for (fl::size i = 0; i < mMapCapacity; ++i) {
116 if (i < mFrontMapIdx || i >= live_end) {
118 mMap[i] = nullptr;
119 }
120 }
121 for (fl::size i = 0; i < used; ++i) {
122 new_map[new_front + i] = mMap[mFrontMapIdx + i];
123 }
125 mMap = new_map;
126 mMapCapacity = new_cap;
127 mFrontMapIdx = new_front;
128 }
129
130 // Ensure the chunk that will hold the next push_back exists. May grow
131 // the map if the back chunk lies past mMapCapacity. Returns false when
132 // allocation failed; the caller must drop the element (FastLED #4899).
134 fl::size global = mFrontOffset + mSize;
135 fl::size need_chunk_idx = mFrontMapIdx + global / kChunkSize;
136 if (need_chunk_idx >= mMapCapacity) {
137 grow_map(0, 1);
138 global = mFrontOffset + mSize;
139 need_chunk_idx = mFrontMapIdx + global / kChunkSize;
140 if (need_chunk_idx >= mMapCapacity) return false; // grow failed
141 }
142 if (mMap[need_chunk_idx] == nullptr) {
143 mMap[need_chunk_idx] = allocate_chunk();
144 }
145 return mMap[need_chunk_idx] != nullptr;
146 }
147
148 // Ensure the chunk that will hold the next push_front exists. May grow
149 // the map if push_front would step before mMap[0]. Returns false when
150 // allocation failed; the caller must drop the element (FastLED #4899).
152 if (mFrontOffset > 0) {
153 // Stays within current front chunk; that chunk is guaranteed
154 // allocated when mSize > 0, and allocated below for empty deque.
155 if (mMapCapacity == 0) {
156 grow_map(1, 0);
157 if (mMapCapacity == 0) return false;
158 }
159 if (mMap[mFrontMapIdx] == nullptr) {
161 }
162 return mMap[mFrontMapIdx] != nullptr;
163 }
164 // mFrontOffset == 0: need the previous chunk.
165 if (mFrontMapIdx == 0) {
166 grow_map(1, 0);
167 if (mFrontMapIdx == 0) return false; // grow failed
168 }
169 if (mMap[mFrontMapIdx - 1] == nullptr) {
171 }
172 return mMap[mFrontMapIdx - 1] != nullptr;
173 }
174
175 // Bulk fills stop at the first failed allocation instead of retrying
176 // every remaining element (FastLED #4899).
178 fl::size before = mSize;
180 return mSize != before;
181 }
182
183public:
184 // Iterator implementation (RandomAccessIterator). The iterator carries
185 // only `(deque*, logical_index)` and resolves to a chunk pointer at
186 // dereference time. Pointer stability for T* taken at insertion time is
187 // provided by chunks themselves never being moved; iterator stability
188 // is preserved across push at either end (logical_index of pre-existing
189 // elements doesn't change for push_back, and is adjusted internally by
190 // mFrontOffset / mFrontMapIdx for push_front).
191 class iterator {
192 public:
193 typedef T value_type;
194 typedef T& reference;
195 typedef T* pointer;
196 typedef fl::size difference_type;
198
199 private:
201 fl::size mIndex;
202
203 friend class deque;
204
205 public:
206 iterator(deque* dq, fl::size index) FL_NO_EXCEPT : mDeque(dq), mIndex(index) {}
207
209 return (*mDeque)[mIndex];
210 }
211
213 return &(*mDeque)[mIndex];
214 }
215
217 ++mIndex;
218 return *this;
219 }
220
222 iterator temp = *this;
223 ++mIndex;
224 return temp;
225 }
226
228 --mIndex;
229 return *this;
230 }
231
233 iterator temp = *this;
234 --mIndex;
235 return temp;
236 }
237
239 mIndex += n;
240 return *this;
241 }
242
243 iterator operator+(fl::size n) const FL_NO_EXCEPT {
244 iterator temp = *this;
245 return temp += n;
246 }
247
249 mIndex -= n;
250 return *this;
251 }
252
253 iterator operator-(fl::size n) const FL_NO_EXCEPT {
254 iterator temp = *this;
255 return temp -= n;
256 }
257
258 fl::size operator-(const iterator& other) const FL_NO_EXCEPT {
259 return mIndex - other.mIndex;
260 }
261
262 T& operator[](fl::size n) const FL_NO_EXCEPT {
263 return (*mDeque)[mIndex + n];
264 }
265
266 bool operator==(const iterator& other) const FL_NO_EXCEPT {
267 return mDeque == other.mDeque && mIndex == other.mIndex;
268 }
269
270 bool operator!=(const iterator& other) const FL_NO_EXCEPT {
271 return !(*this == other);
272 }
273
274 bool operator<(const iterator& other) const FL_NO_EXCEPT {
275 return mIndex < other.mIndex;
276 }
277
278 bool operator<=(const iterator& other) const FL_NO_EXCEPT {
279 return mIndex <= other.mIndex;
280 }
281
282 bool operator>(const iterator& other) const FL_NO_EXCEPT {
283 return mIndex > other.mIndex;
284 }
285
286 bool operator>=(const iterator& other) const FL_NO_EXCEPT {
287 return mIndex >= other.mIndex;
288 }
289 };
290
292 public:
293 typedef T value_type;
294 typedef const T& reference;
295 typedef const T* pointer;
296 typedef fl::size difference_type;
298
299 private:
300 const deque* mDeque;
301 fl::size mIndex;
302
303 friend class deque;
304
305 public:
306 const_iterator(const deque* dq, fl::size index) FL_NO_EXCEPT : mDeque(dq), mIndex(index) {}
307
308 // Implicit conversion from iterator to const_iterator
309 const_iterator(const iterator& it) FL_NO_EXCEPT : mDeque(it.mDeque), mIndex(it.mIndex) {}
310
311 const T& operator*() const FL_NO_EXCEPT {
312 return (*mDeque)[mIndex];
313 }
314
315 const T* operator->() const FL_NO_EXCEPT {
316 return &(*mDeque)[mIndex];
317 }
318
320 ++mIndex;
321 return *this;
322 }
323
325 const_iterator temp = *this;
326 ++mIndex;
327 return temp;
328 }
329
331 --mIndex;
332 return *this;
333 }
334
336 const_iterator temp = *this;
337 --mIndex;
338 return temp;
339 }
340
342 mIndex += n;
343 return *this;
344 }
345
347 const_iterator temp = *this;
348 return temp += n;
349 }
350
352 mIndex -= n;
353 return *this;
354 }
355
357 const_iterator temp = *this;
358 return temp -= n;
359 }
360
361 fl::size operator-(const const_iterator& other) const FL_NO_EXCEPT {
362 return mIndex - other.mIndex;
363 }
364
365 const T& operator[](fl::size n) const FL_NO_EXCEPT {
366 return (*mDeque)[mIndex + n];
367 }
368
369 bool operator==(const const_iterator& other) const FL_NO_EXCEPT {
370 return mDeque == other.mDeque && mIndex == other.mIndex;
371 }
372
373 bool operator!=(const const_iterator& other) const FL_NO_EXCEPT {
374 return !(*this == other);
375 }
376
377 bool operator<(const const_iterator& other) const FL_NO_EXCEPT {
378 return mIndex < other.mIndex;
379 }
380
381 bool operator<=(const const_iterator& other) const FL_NO_EXCEPT {
382 return mIndex <= other.mIndex;
383 }
384
385 bool operator>(const const_iterator& other) const FL_NO_EXCEPT {
386 return mIndex > other.mIndex;
387 }
388
389 bool operator>=(const const_iterator& other) const FL_NO_EXCEPT {
390 return mIndex >= other.mIndex;
391 }
392 };
393
396
397 // Constructors
399
400 explicit deque(memory_resource* resource) FL_NO_EXCEPT : mResource(resource) {}
401
402 explicit deque(fl::size count, const T& value = T()) FL_NO_EXCEPT : deque() {
403 resize(count, value);
404 }
405
406 deque(const deque& other) FL_NO_EXCEPT : deque() {
407 *this = other;
408 }
409
411 *this = fl::move(other);
412 }
413
414 deque(fl::initializer_list<T> init) FL_NO_EXCEPT : deque() {
415 for (const auto& value : init) {
416 if (!try_push_back(value)) break;
417 }
418 }
419
421 clear();
422 // Deallocate any remaining chunk pointers (clear() releases element
423 // storage but may leave the map intact for reuse on a still-live deque;
424 // here we tear it down for good).
425 for (fl::size i = 0; i < mMapCapacity; ++i) {
427 }
429 }
430
432 if (this != &other) {
433 clear();
434 for (fl::size i = 0; i < other.size(); ++i) {
435 if (!try_push_back(other[i])) break;
436 }
437 }
438 return *this;
439 }
440
442 if (this != &other) {
443 // Tear down current state.
444 clear();
445 for (fl::size i = 0; i < mMapCapacity; ++i) {
447 }
449
450 mMap = other.mMap;
451 mMapCapacity = other.mMapCapacity;
452 mFrontMapIdx = other.mFrontMapIdx;
453 mFrontOffset = other.mFrontOffset;
454 mSize = other.mSize;
455 mResource = other.mResource;
456
457 other.mMap = nullptr;
458 other.mMapCapacity = 0;
459 other.mFrontMapIdx = 0;
460 other.mFrontOffset = 0;
461 other.mSize = 0;
462 }
463 return *this;
464 }
465
466 // Element access
467 T& operator[](fl::size index) FL_NO_EXCEPT {
468 fl::size c, o; locate(index, c, o);
469 return mMap[c][o];
470 }
471
472 const T& operator[](fl::size index) const FL_NO_EXCEPT {
473 fl::size c, o; locate(index, c, o);
474 return mMap[c][o];
475 }
476
477 T& at(fl::size index) FL_NO_EXCEPT {
478 if (index >= mSize) {
479 // Bounds error: return front in embedded context (matching the
480 // pre-#3270 deque's documented fallback).
481 return front();
482 }
483 fl::size c, o; locate(index, c, o);
484 return mMap[c][o];
485 }
486
487 const T& at(fl::size index) const FL_NO_EXCEPT {
488 if (index >= mSize) {
489 return front();
490 }
491 fl::size c, o; locate(index, c, o);
492 return mMap[c][o];
493 }
494
497 }
498
499 const T& front() const FL_NO_EXCEPT {
501 }
502
504 fl::size c, o; locate(mSize - 1, c, o);
505 return mMap[c][o];
506 }
507
508 const T& back() const FL_NO_EXCEPT {
509 fl::size c, o; locate(mSize - 1, c, o);
510 return mMap[c][o];
511 }
512
513 iterator begin() FL_NO_EXCEPT { return iterator(this, 0); }
514 const_iterator begin() const FL_NO_EXCEPT { return const_iterator(this, 0); }
515 iterator end() FL_NO_EXCEPT { return iterator(this, mSize); }
516 const_iterator end() const FL_NO_EXCEPT { return const_iterator(this, mSize); }
517
522
523 const_iterator cbegin() const FL_NO_EXCEPT { return const_iterator(this, 0); }
524 const_iterator cend() const FL_NO_EXCEPT { return const_iterator(this, mSize); }
527
528 bool empty() const FL_NO_EXCEPT { return mSize == 0; }
529 fl::size size() const FL_NO_EXCEPT { return mSize; }
530
531 // Total addressable storage in the currently-allocated chunks. Returns
532 // a chunk-size-quantized value (multiple of kChunkSize). The old
533 // vector-style deque reported exact element capacity; chunked deques
534 // report whole-chunk capacity. See FastLED #3270 migration plan.
535 fl::size capacity() const FL_NO_EXCEPT {
536 fl::size allocated = 0;
537 for (fl::size i = 0; i < mMapCapacity; ++i) {
538 if (mMap[i] != nullptr) ++allocated;
539 }
540 return allocated * kChunkSize;
541 }
542
543 fl::size max_size() const FL_NO_EXCEPT {
544 return static_cast<fl::size>(-1) / sizeof(T);
545 }
546
547 // Ensure capacity for at least `n` elements from the current front.
548 // Chunked: pre-allocates ceil(n / kChunkSize) chunks at the back.
549 void reserve(fl::size n) FL_NO_EXCEPT {
550 if (n <= capacity()) return;
551 // Allocate enough chunks behind the current front-offset to hold n total.
552 fl::size needed_chunks = (mFrontOffset + n + kChunkSize - 1) / kChunkSize;
553 fl::size cur_chunks = used_chunks();
554 if (cur_chunks < needed_chunks) {
555 fl::size extra = needed_chunks - cur_chunks;
556 // Ensure mMap has room for `extra` more chunks past current back.
557 fl::size last_used_idx = (mSize == 0) ? mFrontMapIdx : (mFrontMapIdx + used_chunks() - 1);
558 if (last_used_idx + extra >= mMapCapacity) {
559 grow_map(0, extra);
560 }
561 // Allocate chunks at the back to cover [front .. front+n).
562 fl::size first_new = (mSize == 0) ? mFrontMapIdx : (mFrontMapIdx + cur_chunks);
563 for (fl::size i = 0; i < extra; ++i) {
564 if (first_new + i >= mMapCapacity) break;
565 if (mMap[first_new + i] == nullptr) {
566 mMap[first_new + i] = allocate_chunk();
567 }
568 }
569 }
570 }
571
572 // Release chunks that hold no live elements. After return, only the
573 // chunks spanning [front .. back] remain allocated. Capacity is
574 // quantized to kChunkSize and equals ceil(size / kChunkSize) * kChunkSize.
576 if (mSize == 0) {
577 // Release every chunk and the map itself.
578 for (fl::size i = 0; i < mMapCapacity; ++i) {
580 mMap[i] = nullptr;
581 }
583 mMap = nullptr;
584 mMapCapacity = 0;
585 mFrontMapIdx = 0;
586 mFrontOffset = 0;
587 return;
588 }
589 // Release chunks outside [front .. back].
590 fl::size last_used = mFrontMapIdx + used_chunks() - 1;
591 for (fl::size i = 0; i < mMapCapacity; ++i) {
592 if (i < mFrontMapIdx || i > last_used) {
594 mMap[i] = nullptr;
595 }
596 }
597 }
598
600
602 for (fl::size i = 0; i < mSize; ++i) {
603 fl::size c, o; locate(i, c, o);
604 mMap[c][o].~T();
605 }
606 mSize = 0;
607 // Reset front to the start of its current chunk so subsequent
608 // pushes don't waste leading-chunk space. Chunks themselves stay
609 // allocated for reuse; callers wanting deallocation should call
610 // shrink_to_fit() afterward.
611 mFrontOffset = 0;
612 }
613
614 void push_back(const T& value) FL_NO_EXCEPT {
615 if (!ensure_back_room()) return;
616 fl::size global = mFrontOffset + mSize;
617 fl::size c = mFrontMapIdx + global / kChunkSize;
618 fl::size o = global % kChunkSize;
619 new (&mMap[c][o]) T(value);
620 ++mSize;
621 }
622
624 if (!ensure_back_room()) return;
625 fl::size global = mFrontOffset + mSize;
626 fl::size c = mFrontMapIdx + global / kChunkSize;
627 fl::size o = global % kChunkSize;
628 new (&mMap[c][o]) T(fl::move(value));
629 ++mSize;
630 }
631
633 if (!ensure_front_room()) return;
634 if (mFrontOffset == 0) {
635 --mFrontMapIdx;
637 } else {
638 --mFrontOffset;
639 }
641 ++mSize;
642 }
643
645 if (!ensure_front_room()) return;
646 if (mFrontOffset == 0) {
647 --mFrontMapIdx;
649 } else {
650 --mFrontOffset;
651 }
653 ++mSize;
654 }
655
657 if (mSize == 0) return;
658 fl::size c, o; locate(mSize - 1, c, o);
659 mMap[c][o].~T();
660 --mSize;
661 }
662
664 if (mSize == 0) return;
666 ++mFrontOffset;
667 if (mFrontOffset == kChunkSize) {
668 mFrontOffset = 0;
669 ++mFrontMapIdx;
670 }
671 --mSize;
672 }
673
674 void resize(fl::size new_size) FL_NO_EXCEPT {
675 resize(new_size, T());
676 }
677
678 void resize(fl::size new_size, const T& value) FL_NO_EXCEPT {
679 while (mSize < new_size) {
680 if (!try_push_back(value)) return;
681 }
682 while (mSize > new_size) pop_back();
683 }
684
685 void swap(deque& other) FL_NO_EXCEPT {
686 if (this != &other) {
687 T** t_map = mMap;
688 fl::size t_cap = mMapCapacity;
689 fl::size t_idx = mFrontMapIdx;
690 fl::size t_off = mFrontOffset;
691 fl::size t_size = mSize;
692 memory_resource* t_res = mResource;
693
694 mMap = other.mMap;
695 mMapCapacity = other.mMapCapacity;
696 mFrontMapIdx = other.mFrontMapIdx;
697 mFrontOffset = other.mFrontOffset;
698 mSize = other.mSize;
699 mResource = other.mResource;
700
701 other.mMap = t_map;
702 other.mMapCapacity = t_cap;
703 other.mFrontMapIdx = t_idx;
704 other.mFrontOffset = t_off;
705 other.mSize = t_size;
706 other.mResource = t_res;
707 }
708 }
709
710 // Insert / emplace / erase use a higher-level strategy than the
711 // vector-style deque: instead of manual ~T() + placement-new bookkeeping
712 // across un-allocated chunk slots, they (1) extend the deque by pushing
713 // a copy of the current back (or the new value when the deque is
714 // empty), which routes through push_back's chunk-allocation path, then
715 // (2) shift via operator[] assignment. Erase is symmetric: shift via
716 // assignment then pop_back. Requires CopyConstructible + CopyAssignable
717 // T, the same contract as std::deque::insert.
718
719 iterator insert(const_iterator pos, const T& value) FL_NO_EXCEPT {
720 fl::size idx = pos.mIndex;
721 if (idx == mSize) {
723 return iterator(this, idx);
724 }
725 // Push a copy of the current back to extend by one; chunk alloc
726 // is handled inside push_back. On allocation failure leave the
727 // contents unchanged and return end() (FastLED #4899).
728 fl::size old_size = mSize;
729 push_back((*this)[mSize - 1]);
730 if (mSize == old_size) return end();
731 for (fl::size i = mSize - 1; i > idx + 1; --i) {
732 (*this)[i - 1] = fl::move((*this)[i - 2]);
733 }
734 (*this)[idx] = value;
735 return iterator(this, idx);
736 }
737
738 iterator insert(const_iterator pos, T&& value) FL_NO_EXCEPT {
739 fl::size idx = pos.mIndex;
740 if (idx == mSize) {
742 return iterator(this, idx);
743 }
744 // Move-extend at the back so move-only T works. The moved-from
745 // slot at old logical mSize-1 is overwritten by the shift loop.
746 // A failed push does not move from the back (FastLED #4899).
747 fl::size old_size = mSize;
748 push_back(fl::move((*this)[mSize - 1]));
749 if (mSize == old_size) return end();
750 for (fl::size i = mSize - 1; i > idx + 1; --i) {
751 (*this)[i - 1] = fl::move((*this)[i - 2]);
752 }
753 (*this)[idx] = fl::move(value);
754 return iterator(this, idx);
755 }
756
757 iterator insert(const_iterator pos, fl::size count, const T& value) FL_NO_EXCEPT {
758 fl::size idx = pos.mIndex;
759 if (count == 0) return iterator(this, idx);
760 fl::size old_size = mSize;
761 // Extend by `count` slots. First push uses `value` if the deque
762 // is empty, else copies the current back; subsequent pushes copy
763 // whatever's at the back now. All these copies will be overwritten
764 // by the shift + fill below.
765 for (fl::size k = 0; k < count; ++k) {
766 fl::size before = mSize;
767 if (mSize == 0) push_back(value);
768 else push_back((*this)[mSize - 1]);
769 if (mSize == before) {
770 // Allocation failed: drop the partial extension (FastLED #4899).
771 while (mSize > old_size) pop_back();
772 return end();
773 }
774 }
775 // Shift elements [idx .. old_size) right by `count` slots.
776 for (fl::size i = old_size; i > idx; --i) {
777 (*this)[i - 1 + count] = fl::move((*this)[i - 1]);
778 }
779 for (fl::size i = 0; i < count; ++i) {
780 (*this)[idx + i] = value;
781 }
782 return iterator(this, idx);
783 }
784
785 iterator erase(const_iterator pos) FL_NO_EXCEPT {
786 if (pos == end()) return end();
787 fl::size idx = pos.mIndex;
788 for (fl::size i = idx; i + 1 < mSize; ++i) {
789 (*this)[i] = fl::move((*this)[i + 1]);
790 }
791 pop_back();
792 return iterator(this, idx);
793 }
794
795 iterator erase(const_iterator first, const_iterator last) FL_NO_EXCEPT {
796 fl::size start_idx = first.mIndex;
797 if (first == last) return iterator(this, start_idx);
798 fl::size count = last.mIndex - first.mIndex;
799 for (fl::size i = start_idx; i + count < mSize; ++i) {
800 (*this)[i] = fl::move((*this)[i + count]);
801 }
802 for (fl::size k = 0; k < count; ++k) {
803 pop_back();
804 }
805 return iterator(this, start_idx);
806 }
807
808 template<typename... Args>
809 iterator emplace(const_iterator pos, Args&&... args) FL_NO_EXCEPT {
810 fl::size idx = pos.mIndex;
811 if (idx == mSize) {
813 return iterator(this, idx); // end() if the append failed
814 }
815 // Move-extend at the back so move-only T works. The moved-from
816 // slot at old logical mSize-1 is overwritten by the shift loop.
817 // A failed push does not move from the back (FastLED #4899).
818 fl::size old_size = mSize;
819 push_back(fl::move((*this)[mSize - 1]));
820 if (mSize == old_size) return end();
821 for (fl::size i = mSize - 1; i > idx + 1; --i) {
822 (*this)[i - 1] = fl::move((*this)[i - 2]);
823 }
824 (*this)[idx] = T(fl::forward<Args>(args)...);
825 return iterator(this, idx);
826 }
827
828 // Returns void like fl::vector::emplace_back: on allocation failure the
829 // element is not constructed and size() is unchanged (FastLED #4899).
830 template<typename... Args>
832 if (!ensure_back_room()) return;
833 fl::size global = mFrontOffset + mSize;
834 fl::size c = mFrontMapIdx + global / kChunkSize;
835 fl::size o = global % kChunkSize;
836 new (&mMap[c][o]) T(fl::forward<Args>(args)...);
837 ++mSize;
838 }
839
840 template<typename... Args>
842 if (!ensure_front_room()) return;
843 if (mFrontOffset == 0) {
844 --mFrontMapIdx;
846 } else {
847 --mFrontOffset;
848 }
850 ++mSize;
851 }
852
853 void assign(fl::size count, const T& value) FL_NO_EXCEPT {
854 clear();
855 for (fl::size i = 0; i < count; ++i) {
856 if (!try_push_back(value)) break;
857 }
858 }
859
860 bool operator==(const deque& other) const FL_NO_EXCEPT {
861 if (mSize != other.mSize) return false;
862 for (fl::size i = 0; i < mSize; ++i) {
863 if ((*this)[i] != other[i]) return false;
864 }
865 return true;
866 }
867
868 bool operator!=(const deque& other) const FL_NO_EXCEPT { return !(*this == other); }
869
870 bool operator<(const deque& other) const FL_NO_EXCEPT {
871 fl::size min_size = mSize < other.mSize ? mSize : other.mSize;
872 for (fl::size i = 0; i < min_size; ++i) {
873 if ((*this)[i] < other[i]) return true;
874 if ((*this)[i] > other[i]) return false;
875 }
876 return mSize < other.mSize;
877 }
878
879 bool operator<=(const deque& other) const FL_NO_EXCEPT { return *this < other || *this == other; }
880 bool operator>(const deque& other) const FL_NO_EXCEPT { return other < *this; }
881 bool operator>=(const deque& other) const FL_NO_EXCEPT { return *this > other || *this == other; }
882};
883
887
888} // namespace fl
uint8_t pos
Definition Blur.ino:11
const_iterator & operator-=(fl::size n) FL_NO_EXCEPT
Definition deque.h:351
const_iterator & operator++() FL_NO_EXCEPT
Definition deque.h:319
bool operator!=(const const_iterator &other) const FL_NO_EXCEPT
Definition deque.h:373
const_iterator & operator--() FL_NO_EXCEPT
Definition deque.h:330
const_iterator operator+(fl::size n) const FL_NO_EXCEPT
Definition deque.h:346
const T & operator[](fl::size n) const FL_NO_EXCEPT
Definition deque.h:365
const_iterator & operator+=(fl::size n) FL_NO_EXCEPT
Definition deque.h:341
bool operator>(const const_iterator &other) const FL_NO_EXCEPT
Definition deque.h:385
bool operator==(const const_iterator &other) const FL_NO_EXCEPT
Definition deque.h:369
bool operator>=(const const_iterator &other) const FL_NO_EXCEPT
Definition deque.h:389
fl::size operator-(const const_iterator &other) const FL_NO_EXCEPT
Definition deque.h:361
const_iterator operator--(int) FL_NO_EXCEPT
Definition deque.h:335
const T * operator->() const FL_NO_EXCEPT
Definition deque.h:315
bool operator<=(const const_iterator &other) const FL_NO_EXCEPT
Definition deque.h:381
friend class deque
Definition deque.h:303
const T & operator*() const FL_NO_EXCEPT
Definition deque.h:311
const_iterator(const iterator &it) FL_NO_EXCEPT
Definition deque.h:309
const_iterator(const deque *dq, fl::size index) FL_NO_EXCEPT
Definition deque.h:306
const_iterator operator++(int) FL_NO_EXCEPT
Definition deque.h:324
const_iterator operator-(fl::size n) const FL_NO_EXCEPT
Definition deque.h:356
bool operator<(const const_iterator &other) const FL_NO_EXCEPT
Definition deque.h:377
const deque * mDeque
Definition deque.h:300
fl::random_access_iterator_tag iterator_category
Definition deque.h:297
bool operator<=(const iterator &other) const FL_NO_EXCEPT
Definition deque.h:278
iterator operator-(fl::size n) const FL_NO_EXCEPT
Definition deque.h:253
fl::size mIndex
Definition deque.h:201
bool operator>(const iterator &other) const FL_NO_EXCEPT
Definition deque.h:282
iterator & operator+=(fl::size n) FL_NO_EXCEPT
Definition deque.h:238
fl::random_access_iterator_tag iterator_category
Definition deque.h:197
T & operator*() const FL_NO_EXCEPT
Definition deque.h:208
iterator operator--(int) FL_NO_EXCEPT
Definition deque.h:232
bool operator==(const iterator &other) const FL_NO_EXCEPT
Definition deque.h:266
fl::size operator-(const iterator &other) const FL_NO_EXCEPT
Definition deque.h:258
iterator(deque *dq, fl::size index) FL_NO_EXCEPT
Definition deque.h:206
bool operator!=(const iterator &other) const FL_NO_EXCEPT
Definition deque.h:270
iterator operator++(int) FL_NO_EXCEPT
Definition deque.h:221
iterator & operator++() FL_NO_EXCEPT
Definition deque.h:216
iterator operator+(fl::size n) const FL_NO_EXCEPT
Definition deque.h:243
fl::size difference_type
Definition deque.h:196
friend class deque
Definition deque.h:203
bool operator>=(const iterator &other) const FL_NO_EXCEPT
Definition deque.h:286
bool operator<(const iterator &other) const FL_NO_EXCEPT
Definition deque.h:274
T * operator->() const FL_NO_EXCEPT
Definition deque.h:212
T & operator[](fl::size n) const FL_NO_EXCEPT
Definition deque.h:262
iterator & operator--() FL_NO_EXCEPT
Definition deque.h:227
iterator & operator-=(fl::size n) FL_NO_EXCEPT
Definition deque.h:248
bool operator>=(const deque &other) const FL_NO_EXCEPT
Definition deque.h:881
bool try_push_back(const T &value) FL_NO_EXCEPT
Definition deque.h:177
iterator erase(const_iterator pos) FL_NO_EXCEPT
Definition deque.h:785
memory_resource * mResource
Definition deque.h:43
iterator begin() FL_NO_EXCEPT
Definition deque.h:513
const T & back() const FL_NO_EXCEPT
Definition deque.h:508
iterator erase(const_iterator first, const_iterator last) FL_NO_EXCEPT
Definition deque.h:795
void clear() FL_NO_EXCEPT
Definition deque.h:601
fl::size capacity() const FL_NO_EXCEPT
Definition deque.h:535
const_reverse_iterator crend() const FL_NO_EXCEPT
Definition deque.h:526
void push_front(T &&value) FL_NO_EXCEPT
Definition deque.h:644
void swap(deque &other) FL_NO_EXCEPT
Definition deque.h:685
const_reverse_iterator rbegin() const FL_NO_EXCEPT
Definition deque.h:519
void deallocate_chunk(T *chunk) FL_NO_EXCEPT
Definition deque.h:49
void push_back(const T &value) FL_NO_EXCEPT
Definition deque.h:614
void locate(fl::size logical_idx, fl::size &chunk_idx, fl::size &offset) const FL_NO_EXCEPT
Definition deque.h:73
void resize(fl::size new_size, const T &value) FL_NO_EXCEPT
Definition deque.h:678
fl::reverse_iterator< const_iterator > const_reverse_iterator
Definition deque.h:395
fl::reverse_iterator< iterator > reverse_iterator
Definition deque.h:394
fl::size mMapCapacity
Definition deque.h:39
void pop_back() FL_NO_EXCEPT
Definition deque.h:656
iterator insert(const_iterator pos, fl::size count, const T &value) FL_NO_EXCEPT
Definition deque.h:757
void shrink_to_fit() FL_NO_EXCEPT
Definition deque.h:575
deque & operator=(deque &&other) FL_NO_EXCEPT
Definition deque.h:441
deque(fl::size count, const T &value=T()) FL_NO_EXCEPT
Definition deque.h:402
bool ensure_front_room() FL_NO_EXCEPT
Definition deque.h:151
iterator emplace(const_iterator pos, Args &&... args) FL_NO_EXCEPT
Definition deque.h:809
fl::size max_size() const FL_NO_EXCEPT
Definition deque.h:543
bool operator>(const deque &other) const FL_NO_EXCEPT
Definition deque.h:880
const_iterator end() const FL_NO_EXCEPT
Definition deque.h:516
void push_front(const T &value) FL_NO_EXCEPT
Definition deque.h:632
reverse_iterator rbegin() FL_NO_EXCEPT
Definition deque.h:518
static constexpr fl::size kChunkSize
Definition deque.h:36
fl::size size() const FL_NO_EXCEPT
Definition deque.h:529
void deallocate_map(T **map, fl::size capacity) FL_NO_EXCEPT
Definition deque.h:65
T & front() FL_NO_EXCEPT
Definition deque.h:495
void push_back(T &&value) FL_NO_EXCEPT
Definition deque.h:623
bool operator<=(const deque &other) const FL_NO_EXCEPT
Definition deque.h:879
reverse_iterator rend() FL_NO_EXCEPT
Definition deque.h:520
deque() FL_NO_EXCEPT
Definition deque.h:398
bool ensure_back_room() FL_NO_EXCEPT
Definition deque.h:133
void emplace_front(Args &&... args) FL_NO_EXCEPT
Definition deque.h:841
T & at(fl::size index) FL_NO_EXCEPT
Definition deque.h:477
iterator end() FL_NO_EXCEPT
Definition deque.h:515
fl::size mSize
Definition deque.h:42
void reserve(fl::size n) FL_NO_EXCEPT
Definition deque.h:549
deque(memory_resource *resource) FL_NO_EXCEPT
Definition deque.h:400
T * allocate_chunk() FL_NO_EXCEPT
Definition deque.h:45
deque(deque &&other) FL_NO_EXCEPT
Definition deque.h:410
void pop_front() FL_NO_EXCEPT
Definition deque.h:663
const_iterator begin() const FL_NO_EXCEPT
Definition deque.h:514
T ** allocate_map(fl::size capacity) FL_NO_EXCEPT
Definition deque.h:55
const_iterator cend() const FL_NO_EXCEPT
Definition deque.h:524
T & operator[](fl::size index) FL_NO_EXCEPT
Definition deque.h:467
const_reverse_iterator crbegin() const FL_NO_EXCEPT
Definition deque.h:525
bool operator<(const deque &other) const FL_NO_EXCEPT
Definition deque.h:870
memory_resource * get_memory_resource() const FL_NO_EXCEPT
Definition deque.h:599
iterator insert(const_iterator pos, T &&value) FL_NO_EXCEPT
Definition deque.h:738
fl::size used_chunks() const FL_NO_EXCEPT
Definition deque.h:80
void emplace_back(Args &&... args) FL_NO_EXCEPT
Definition deque.h:831
const_iterator cbegin() const FL_NO_EXCEPT
Definition deque.h:523
const T & at(fl::size index) const FL_NO_EXCEPT
Definition deque.h:487
fl::size mFrontOffset
Definition deque.h:41
bool empty() const FL_NO_EXCEPT
Definition deque.h:528
void grow_map(fl::size extra_front, fl::size extra_back) FL_NO_EXCEPT
Definition deque.h:97
deque(const deque &other) FL_NO_EXCEPT
Definition deque.h:406
~deque() FL_NO_EXCEPT
Definition deque.h:420
const T & operator[](fl::size index) const FL_NO_EXCEPT
Definition deque.h:472
bool operator!=(const deque &other) const FL_NO_EXCEPT
Definition deque.h:868
iterator insert(const_iterator pos, const T &value) FL_NO_EXCEPT
Definition deque.h:719
int ** mMap
Definition deque.h:38
void assign(fl::size count, const T &value) FL_NO_EXCEPT
Definition deque.h:853
T & back() FL_NO_EXCEPT
Definition deque.h:503
bool operator==(const deque &other) const FL_NO_EXCEPT
Definition deque.h:860
fl::size mFrontMapIdx
Definition deque.h:40
deque & operator=(const deque &other) FL_NO_EXCEPT
Definition deque.h:431
deque(fl::initializer_list< T > init) FL_NO_EXCEPT
Definition deque.h:414
const_reverse_iterator rend() const FL_NO_EXCEPT
Definition deque.h:521
void resize(fl::size new_size) FL_NO_EXCEPT
Definition deque.h:674
const T & front() const FL_NO_EXCEPT
Definition deque.h:499
Polymorphic memory resource base class (PMR-style).
Reverse iterator adapter - reverses the direction of a bidirectional iterator.
Definition iterator.h:160
fl::UISlider offset("Offset", 0.0f, 0.0f, 1.0f, 0.01f)
PMR-style polymorphic memory resource for type-erased allocation.
FL_NO_INLINE fl::size deque_grow_map_capacity(fl::size current_map_capacity, fl::size min_required_chunks) FL_NO_EXCEPT
constexpr remove_reference< T >::type && move(T &&t) FL_NO_EXCEPT
Definition s16x16x4.h:30
constexpr T && forward(typename remove_reference< T >::type &t) FL_NO_EXCEPT
Definition s16x16x4.h:236
u8 u8 fract8 blur_amount FL_NO_EXCEPT
Definition blur.h:186
constexpr int type_rank< T >::value
MapRedBlackTree< Key, T, Compare, fl::allocator_slab< char > > map
Definition map.h:283
void init(Context &ctx, int w, int h) FL_NO_EXCEPT
Definition engine.h:133
deque< float > deque_float
Definition deque.h:885
memory_resource * default_memory_resource() FL_NO_EXCEPT
Get the default memory resource (wraps fl::Malloc / fl::Free / fl::realloc).
deque< double > deque_double
Definition deque.h:886
deque< int > deque_int
Definition deque.h:884
Base definition for an LED controller.
corkscrew_args args
Definition old.h:149
static constexpr fl::size chunk_size
Definition deque.h:20