1/*
2 * Copyright (C) 2007-2017 Apple Inc. All rights reserved.
3 * Copyright (C) 2009 Google Inc. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of Apple Inc. ("Apple") nor the names of
15 * its contributors may be used to endorse or promote products derived
16 * from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30#pragma once
31
32// FIXME: Could move what Vector and Deque share into a separate file.
33// Deque doesn't actually use Vector.
34
35#include <algorithm>
36#include <iterator>
37#include <wtf/Vector.h>
38
39namespace WTF {
40
41template<typename T, size_t inlineCapacity> class DequeIteratorBase;
42template<typename T, size_t inlineCapacity> class DequeIterator;
43template<typename T, size_t inlineCapacity> class DequeConstIterator;
44
45template<typename T, size_t inlineCapacity = 0>
46class Deque {
47 WTF_MAKE_FAST_ALLOCATED;
48public:
49 typedef T ValueType;
50
51 typedef DequeIterator<T, inlineCapacity> iterator;
52 typedef DequeConstIterator<T, inlineCapacity> const_iterator;
53 typedef std::reverse_iterator<iterator> reverse_iterator;
54 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
55
56 Deque();
57 Deque(std::initializer_list<T>);
58 Deque(const Deque&);
59 Deque(Deque&&);
60 ~Deque();
61
62 Deque& operator=(const Deque&);
63 Deque& operator=(Deque&&);
64
65 void swap(Deque&);
66
67 size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
68 bool isEmpty() const { return m_start == m_end; }
69
70 iterator begin() { return iterator(this, m_start); }
71 iterator end() { return iterator(this, m_end); }
72 const_iterator begin() const { return const_iterator(this, m_start); }
73 const_iterator end() const { return const_iterator(this, m_end); }
74 reverse_iterator rbegin() { return reverse_iterator(end()); }
75 reverse_iterator rend() { return reverse_iterator(begin()); }
76 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
77 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
78
79 template<typename U> bool contains(const U&) const;
80
81 T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
82 const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
83 T takeFirst();
84
85 T& last() { ASSERT(m_start != m_end); return *(--end()); }
86 const T& last() const { ASSERT(m_start != m_end); return *(--end()); }
87 T takeLast();
88
89 void append(T&& value) { append<T>(std::forward<T>(value)); }
90 template<typename U> void append(U&&);
91 template<typename U> void prepend(U&&);
92 void removeFirst();
93 void removeLast();
94 void remove(iterator&);
95 void remove(const_iterator&);
96
97 template<typename Func> void removeAllMatching(const Func&);
98
99 // This is a priority enqueue. The callback is given a value, and if it returns true, then this
100 // will put the appended value before that value. It will keep bubbling until the callback returns
101 // false or the value ends up at the head of the queue.
102 template<typename U, typename Func>
103 void appendAndBubble(U&&, const Func&);
104
105 // Remove and return the first element for which the callback returns true. Returns a null version of
106 // T if it the callback always returns false.
107 template<typename Func>
108 T takeFirst(const Func&);
109
110 // Remove and return the last element for which the callback returns true. Returns a null version of
111 // T if it the callback always returns false.
112 template<typename Func>
113 T takeLast(const Func&);
114
115 void clear();
116
117 template<typename Predicate> iterator findIf(const Predicate&);
118 template<typename Predicate> const_iterator findIf(const Predicate&) const;
119
120private:
121 friend class DequeIteratorBase<T, inlineCapacity>;
122
123 typedef VectorBuffer<T, inlineCapacity> Buffer;
124 typedef VectorTypeOperations<T> TypeOperations;
125 typedef DequeIteratorBase<T, inlineCapacity> IteratorBase;
126
127 void remove(size_t position);
128 void invalidateIterators();
129 void destroyAll();
130 void checkValidity() const;
131 void checkIndexValidity(size_t) const;
132 void expandCapacityIfNeeded();
133 void expandCapacity();
134
135 size_t m_start;
136 size_t m_end;
137 Buffer m_buffer;
138#ifndef NDEBUG
139 mutable IteratorBase* m_iterators;
140#endif
141};
142
143template<typename T, size_t inlineCapacity = 0>
144class DequeIteratorBase {
145protected:
146 DequeIteratorBase();
147 DequeIteratorBase(const Deque<T, inlineCapacity>*, size_t);
148 DequeIteratorBase(const DequeIteratorBase&);
149 DequeIteratorBase& operator=(const DequeIteratorBase&);
150 ~DequeIteratorBase();
151
152 void assign(const DequeIteratorBase& other) { *this = other; }
153
154 void increment();
155 void decrement();
156
157 T* before() const;
158 T* after() const;
159
160 bool isEqual(const DequeIteratorBase&) const;
161
162private:
163 void addToIteratorsList();
164 void removeFromIteratorsList();
165 void checkValidity() const;
166 void checkValidity(const DequeIteratorBase&) const;
167
168 Deque<T, inlineCapacity>* m_deque;
169 size_t m_index;
170
171 friend class Deque<T, inlineCapacity>;
172
173#ifndef NDEBUG
174 mutable DequeIteratorBase* m_next;
175 mutable DequeIteratorBase* m_previous;
176#endif
177};
178
179template<typename T, size_t inlineCapacity = 0>
180class DequeIterator : public DequeIteratorBase<T, inlineCapacity> {
181private:
182 typedef DequeIteratorBase<T, inlineCapacity> Base;
183 typedef DequeIterator<T, inlineCapacity> Iterator;
184
185public:
186 typedef ptrdiff_t difference_type;
187 typedef T value_type;
188 typedef T* pointer;
189 typedef T& reference;
190 typedef std::bidirectional_iterator_tag iterator_category;
191
192 DequeIterator(Deque<T, inlineCapacity>* deque, size_t index)
193 : Base(deque, index) { }
194
195 DequeIterator(const Iterator& other) : Base(other) { }
196 DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
197
198 T& operator*() const { return *Base::after(); }
199 T* operator->() const { return Base::after(); }
200
201 bool operator==(const Iterator& other) const { return Base::isEqual(other); }
202 bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
203
204 Iterator& operator++() { Base::increment(); return *this; }
205 // postfix ++ intentionally omitted
206 Iterator& operator--() { Base::decrement(); return *this; }
207 // postfix -- intentionally omitted
208};
209
210template<typename T, size_t inlineCapacity = 0>
211class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity> {
212private:
213 typedef DequeIteratorBase<T, inlineCapacity> Base;
214 typedef DequeConstIterator<T, inlineCapacity> Iterator;
215 typedef DequeIterator<T, inlineCapacity> NonConstIterator;
216
217public:
218 typedef ptrdiff_t difference_type;
219 typedef T value_type;
220 typedef const T* pointer;
221 typedef const T& reference;
222 typedef std::bidirectional_iterator_tag iterator_category;
223
224 DequeConstIterator(const Deque<T, inlineCapacity>* deque, size_t index)
225 : Base(deque, index) { }
226
227 DequeConstIterator(const Iterator& other) : Base(other) { }
228 DequeConstIterator(const NonConstIterator& other) : Base(other) { }
229 DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
230 DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
231
232 const T& operator*() const { return *Base::after(); }
233 const T* operator->() const { return Base::after(); }
234
235 bool operator==(const Iterator& other) const { return Base::isEqual(other); }
236 bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
237
238 Iterator& operator++() { Base::increment(); return *this; }
239 // postfix ++ intentionally omitted
240 Iterator& operator--() { Base::decrement(); return *this; }
241 // postfix -- intentionally omitted
242};
243
244#ifdef NDEBUG
245template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkValidity() const { }
246template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkIndexValidity(size_t) const { }
247template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::invalidateIterators() { }
248#else
249template<typename T, size_t inlineCapacity>
250void Deque<T, inlineCapacity>::checkValidity() const
251{
252 // In this implementation a capacity of 1 would confuse append() and
253 // other places that assume the index after capacity - 1 is 0.
254 ASSERT(m_buffer.capacity() != 1);
255
256 if (!m_buffer.capacity()) {
257 ASSERT(!m_start);
258 ASSERT(!m_end);
259 } else {
260 ASSERT(m_start < m_buffer.capacity());
261 ASSERT(m_end < m_buffer.capacity());
262 }
263}
264
265template<typename T, size_t inlineCapacity>
266void Deque<T, inlineCapacity>::checkIndexValidity(size_t index) const
267{
268 ASSERT_UNUSED(index, index <= m_buffer.capacity());
269 if (m_start <= m_end) {
270 ASSERT(index >= m_start);
271 ASSERT(index <= m_end);
272 } else {
273 ASSERT(index >= m_start || index <= m_end);
274 }
275}
276
277template<typename T, size_t inlineCapacity>
278void Deque<T, inlineCapacity>::invalidateIterators()
279{
280 IteratorBase* next;
281 for (IteratorBase* p = m_iterators; p; p = next) {
282 next = p->m_next;
283 p->m_deque = 0;
284 p->m_next = 0;
285 p->m_previous = 0;
286 }
287 m_iterators = 0;
288}
289#endif
290
291template<typename T, size_t inlineCapacity>
292inline Deque<T, inlineCapacity>::Deque()
293 : m_start(0)
294 , m_end(0)
295#ifndef NDEBUG
296 , m_iterators(0)
297#endif
298{
299 checkValidity();
300}
301
302template<typename T, size_t inlineCapacity>
303inline Deque<T, inlineCapacity>::Deque(std::initializer_list<T> initializerList)
304 : Deque()
305{
306 for (auto& element : initializerList)
307 append(element);
308}
309
310template<typename T, size_t inlineCapacity>
311inline Deque<T, inlineCapacity>::Deque(const Deque& other)
312 : m_start(other.m_start)
313 , m_end(other.m_end)
314 , m_buffer(other.m_buffer.capacity())
315#ifndef NDEBUG
316 , m_iterators(0)
317#endif
318{
319 const T* otherBuffer = other.m_buffer.buffer();
320 if (m_start <= m_end)
321 TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
322 else {
323 TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
324 TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
325 }
326}
327
328template<typename T, size_t inlineCapacity>
329inline Deque<T, inlineCapacity>::Deque(Deque&& other)
330 : Deque()
331{
332 swap(other);
333}
334
335template<typename T, size_t inlineCapacity>
336inline auto Deque<T, inlineCapacity>::operator=(const Deque& other) -> Deque&
337{
338 // FIXME: This is inefficient if we're using an inline buffer and T is
339 // expensive to copy since it will copy the buffer twice instead of once.
340 Deque<T, inlineCapacity> copy(other);
341 swap(copy);
342 return *this;
343}
344
345template<typename T, size_t inlineCapacity>
346inline auto Deque<T, inlineCapacity>::operator=(Deque&& other) -> Deque&
347{
348 swap(other);
349 return *this;
350}
351
352template<typename T, size_t inlineCapacity>
353inline void Deque<T, inlineCapacity>::destroyAll()
354{
355 if (m_start <= m_end)
356 TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
357 else {
358 TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
359 TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
360 }
361}
362
363template<typename T, size_t inlineCapacity>
364inline Deque<T, inlineCapacity>::~Deque()
365{
366 checkValidity();
367 invalidateIterators();
368 destroyAll();
369}
370
371template<typename T, size_t inlineCapacity>
372inline void Deque<T, inlineCapacity>::swap(Deque<T, inlineCapacity>& other)
373{
374 checkValidity();
375 other.checkValidity();
376 invalidateIterators();
377 std::swap(m_start, other.m_start);
378 std::swap(m_end, other.m_end);
379 m_buffer.swap(other.m_buffer, 0, 0);
380 checkValidity();
381 other.checkValidity();
382}
383
384template<typename T, size_t inlineCapacity>
385inline void Deque<T, inlineCapacity>::clear()
386{
387 checkValidity();
388 invalidateIterators();
389 destroyAll();
390 m_start = 0;
391 m_end = 0;
392 m_buffer.deallocateBuffer(m_buffer.buffer());
393 checkValidity();
394}
395
396template<typename T, size_t inlineCapacity>
397template<typename Predicate>
398inline auto Deque<T, inlineCapacity>::findIf(const Predicate& predicate) -> iterator
399{
400 return std::find_if(begin(), end(), predicate);
401}
402
403template<typename T, size_t inlineCapacity>
404template<typename Predicate>
405inline auto Deque<T, inlineCapacity>::findIf(const Predicate& predicate) const -> const_iterator
406{
407 return std::find_if(begin(), end(), predicate);
408}
409
410template<typename T, size_t inlineCapacity>
411inline void Deque<T, inlineCapacity>::expandCapacityIfNeeded()
412{
413 if (m_start) {
414 if (m_end + 1 != m_start)
415 return;
416 } else if (m_end) {
417 if (m_end != m_buffer.capacity() - 1)
418 return;
419 } else if (m_buffer.capacity())
420 return;
421
422 expandCapacity();
423}
424
425template<typename T, size_t inlineCapacity>
426void Deque<T, inlineCapacity>::expandCapacity()
427{
428 checkValidity();
429 size_t oldCapacity = m_buffer.capacity();
430 T* oldBuffer = m_buffer.buffer();
431 m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
432 if (m_start <= m_end)
433 TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
434 else {
435 TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
436 size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
437 TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
438 m_start = newStart;
439 }
440 m_buffer.deallocateBuffer(oldBuffer);
441 checkValidity();
442}
443
444template<typename T, size_t inlineCapacity>
445template<typename U>
446bool Deque<T, inlineCapacity>::contains(const U& searchValue) const
447{
448 auto endIterator = end();
449 return std::find(begin(), endIterator, searchValue) != endIterator;
450}
451
452template<typename T, size_t inlineCapacity>
453inline auto Deque<T, inlineCapacity>::takeFirst() -> T
454{
455 T oldFirst = WTFMove(first());
456 removeFirst();
457 return oldFirst;
458}
459
460template<typename T, size_t inlineCapacity>
461inline auto Deque<T, inlineCapacity>::takeLast() -> T
462{
463 T oldLast = WTFMove(last());
464 removeLast();
465 return oldLast;
466}
467
468template<typename T, size_t inlineCapacity> template<typename U>
469inline void Deque<T, inlineCapacity>::append(U&& value)
470{
471 checkValidity();
472 expandCapacityIfNeeded();
473 new (NotNull, std::addressof(m_buffer.buffer()[m_end])) T(std::forward<U>(value));
474 if (m_end == m_buffer.capacity() - 1)
475 m_end = 0;
476 else
477 ++m_end;
478 checkValidity();
479}
480
481template<typename T, size_t inlineCapacity> template<typename U>
482inline void Deque<T, inlineCapacity>::prepend(U&& value)
483{
484 checkValidity();
485 expandCapacityIfNeeded();
486 if (!m_start)
487 m_start = m_buffer.capacity() - 1;
488 else
489 --m_start;
490 new (NotNull, std::addressof(m_buffer.buffer()[m_start])) T(std::forward<U>(value));
491 checkValidity();
492}
493
494template<typename T, size_t inlineCapacity>
495inline void Deque<T, inlineCapacity>::removeFirst()
496{
497 checkValidity();
498 invalidateIterators();
499 ASSERT(!isEmpty());
500 TypeOperations::destruct(std::addressof(m_buffer.buffer()[m_start]), std::addressof(m_buffer.buffer()[m_start + 1]));
501 if (m_start == m_buffer.capacity() - 1)
502 m_start = 0;
503 else
504 ++m_start;
505 checkValidity();
506}
507
508template<typename T, size_t inlineCapacity>
509inline void Deque<T, inlineCapacity>::removeLast()
510{
511 checkValidity();
512 invalidateIterators();
513 ASSERT(!isEmpty());
514 if (!m_end)
515 m_end = m_buffer.capacity() - 1;
516 else
517 --m_end;
518 TypeOperations::destruct(std::addressof(m_buffer.buffer()[m_end]), std::addressof(m_buffer.buffer()[m_end + 1]));
519 checkValidity();
520}
521
522template<typename T, size_t inlineCapacity>
523inline void Deque<T, inlineCapacity>::remove(iterator& it)
524{
525 it.checkValidity();
526 remove(it.m_index);
527}
528
529template<typename T, size_t inlineCapacity>
530inline void Deque<T, inlineCapacity>::remove(const_iterator& it)
531{
532 it.checkValidity();
533 remove(it.m_index);
534}
535
536template<typename T, size_t inlineCapacity>
537inline void Deque<T, inlineCapacity>::remove(size_t position)
538{
539 if (position == m_end)
540 return;
541
542 checkValidity();
543 invalidateIterators();
544
545 T* buffer = m_buffer.buffer();
546 TypeOperations::destruct(std::addressof(buffer[position]), std::addressof(buffer[position + 1]));
547
548 // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
549 if (position >= m_start) {
550 TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
551 m_start = (m_start + 1) % m_buffer.capacity();
552 } else {
553 TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
554 m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
555 }
556 checkValidity();
557}
558
559template<typename T, size_t inlineCapacity>
560template<typename Func>
561inline void Deque<T, inlineCapacity>::removeAllMatching(const Func& func)
562{
563 size_t count = size();
564 while (count--) {
565 T value = takeFirst();
566 if (!func(value))
567 append(WTFMove(value));
568 }
569}
570
571template<typename T, size_t inlineCapacity>
572template<typename U, typename Func>
573inline void Deque<T, inlineCapacity>::appendAndBubble(U&& value, const Func& func)
574{
575 append(WTFMove(value));
576 iterator begin = this->begin();
577 iterator iter = end();
578 --iter;
579 while (iter != begin) {
580 iterator prev = iter;
581 --prev;
582 if (!func(*prev))
583 return;
584 std::swap(*prev, *iter);
585 iter = prev;
586 }
587}
588
589template<typename T, size_t inlineCapacity>
590template<typename Func>
591inline T Deque<T, inlineCapacity>::takeFirst(const Func& func)
592{
593 unsigned count = 0;
594 unsigned size = this->size();
595 while (count < size) {
596 T candidate = takeFirst();
597 if (func(candidate)) {
598 while (count--)
599 prepend(takeLast());
600 return candidate;
601 }
602 count++;
603 append(WTFMove(candidate));
604 }
605 return T();
606}
607
608template<typename T, size_t inlineCapacity>
609template<typename Func>
610inline T Deque<T, inlineCapacity>::takeLast(const Func& func)
611{
612 unsigned count = 0;
613 unsigned size = this->size();
614 while (count < size) {
615 T candidate = takeLast();
616 if (func(candidate)) {
617 while (count--)
618 append(takeFirst());
619 return candidate;
620 }
621 count++;
622 prepend(WTFMove(candidate));
623 }
624 return T();
625}
626
627#ifdef NDEBUG
628template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity() const { }
629template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase<T, inlineCapacity>&) const { }
630template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList() { }
631template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList() { }
632#else
633template<typename T, size_t inlineCapacity>
634void DequeIteratorBase<T, inlineCapacity>::checkValidity() const
635{
636 ASSERT(m_deque);
637 m_deque->checkIndexValidity(m_index);
638}
639
640template<typename T, size_t inlineCapacity>
641void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase& other) const
642{
643 checkValidity();
644 other.checkValidity();
645 ASSERT(m_deque == other.m_deque);
646}
647
648template<typename T, size_t inlineCapacity>
649void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList()
650{
651 if (!m_deque)
652 m_next = 0;
653 else {
654 m_next = m_deque->m_iterators;
655 m_deque->m_iterators = this;
656 if (m_next)
657 m_next->m_previous = this;
658 }
659 m_previous = 0;
660}
661
662template<typename T, size_t inlineCapacity>
663void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList()
664{
665 if (!m_deque) {
666 ASSERT(!m_next);
667 ASSERT(!m_previous);
668 } else {
669 if (m_next) {
670 ASSERT(m_next->m_previous == this);
671 m_next->m_previous = m_previous;
672 }
673 if (m_previous) {
674 ASSERT(m_deque->m_iterators != this);
675 ASSERT(m_previous->m_next == this);
676 m_previous->m_next = m_next;
677 } else {
678 ASSERT(m_deque->m_iterators == this);
679 m_deque->m_iterators = m_next;
680 }
681 }
682 m_next = 0;
683 m_previous = 0;
684}
685#endif
686
687template<typename T, size_t inlineCapacity>
688inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase()
689 : m_deque(0)
690{
691}
692
693template<typename T, size_t inlineCapacity>
694inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const Deque<T, inlineCapacity>* deque, size_t index)
695 : m_deque(const_cast<Deque<T, inlineCapacity>*>(deque))
696 , m_index(index)
697{
698 addToIteratorsList();
699 checkValidity();
700}
701
702template<typename T, size_t inlineCapacity>
703inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const DequeIteratorBase& other)
704 : m_deque(other.m_deque)
705 , m_index(other.m_index)
706{
707 addToIteratorsList();
708 checkValidity();
709}
710
711template<typename T, size_t inlineCapacity>
712inline DequeIteratorBase<T, inlineCapacity>& DequeIteratorBase<T, inlineCapacity>::operator=(const DequeIteratorBase& other)
713{
714 other.checkValidity();
715 removeFromIteratorsList();
716
717 m_deque = other.m_deque;
718 m_index = other.m_index;
719 addToIteratorsList();
720 checkValidity();
721 return *this;
722}
723
724template<typename T, size_t inlineCapacity>
725inline DequeIteratorBase<T, inlineCapacity>::~DequeIteratorBase()
726{
727#ifndef NDEBUG
728 removeFromIteratorsList();
729 m_deque = 0;
730#endif
731}
732
733template<typename T, size_t inlineCapacity>
734inline bool DequeIteratorBase<T, inlineCapacity>::isEqual(const DequeIteratorBase& other) const
735{
736 checkValidity(other);
737 return m_index == other.m_index;
738}
739
740template<typename T, size_t inlineCapacity>
741inline void DequeIteratorBase<T, inlineCapacity>::increment()
742{
743 checkValidity();
744 ASSERT(m_index != m_deque->m_end);
745 ASSERT(m_deque->m_buffer.capacity());
746 if (m_index == m_deque->m_buffer.capacity() - 1)
747 m_index = 0;
748 else
749 ++m_index;
750 checkValidity();
751}
752
753template<typename T, size_t inlineCapacity>
754inline void DequeIteratorBase<T, inlineCapacity>::decrement()
755{
756 checkValidity();
757 ASSERT(m_index != m_deque->m_start);
758 ASSERT(m_deque->m_buffer.capacity());
759 if (!m_index)
760 m_index = m_deque->m_buffer.capacity() - 1;
761 else
762 --m_index;
763 checkValidity();
764}
765
766template<typename T, size_t inlineCapacity>
767inline T* DequeIteratorBase<T, inlineCapacity>::after() const
768{
769 checkValidity();
770 ASSERT(m_index != m_deque->m_end);
771 return std::addressof(m_deque->m_buffer.buffer()[m_index]);
772}
773
774template<typename T, size_t inlineCapacity>
775inline T* DequeIteratorBase<T, inlineCapacity>::before() const
776{
777 checkValidity();
778 ASSERT(m_index != m_deque->m_start);
779 if (!m_index)
780 return std::addressof(m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1]);
781 return std::addressof(m_deque->m_buffer.buffer()[m_index - 1]);
782}
783
784} // namespace WTF
785
786using WTF::Deque;
787