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 final {
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 {
145 WTF_MAKE_FAST_ALLOCATED;
146protected:
147 DequeIteratorBase();
148 DequeIteratorBase(const Deque<T, inlineCapacity>*, size_t);
149 DequeIteratorBase(const DequeIteratorBase&);
150 DequeIteratorBase& operator=(const DequeIteratorBase&);
151 ~DequeIteratorBase();
152
153 void assign(const DequeIteratorBase& other) { *this = other; }
154
155 void increment();
156 void decrement();
157
158 T* before() const;
159 T* after() const;
160
161 bool isEqual(const DequeIteratorBase&) const;
162
163private:
164 void addToIteratorsList();
165 void removeFromIteratorsList();
166 void checkValidity() const;
167 void checkValidity(const DequeIteratorBase&) const;
168
169 Deque<T, inlineCapacity>* m_deque;
170 size_t m_index;
171
172 friend class Deque<T, inlineCapacity>;
173
174#ifndef NDEBUG
175 mutable DequeIteratorBase* m_next;
176 mutable DequeIteratorBase* m_previous;
177#endif
178};
179
180template<typename T, size_t inlineCapacity = 0>
181class DequeIterator : public DequeIteratorBase<T, inlineCapacity> {
182 WTF_MAKE_FAST_ALLOCATED;
183private:
184 typedef DequeIteratorBase<T, inlineCapacity> Base;
185 typedef DequeIterator<T, inlineCapacity> Iterator;
186
187public:
188 typedef ptrdiff_t difference_type;
189 typedef T value_type;
190 typedef T* pointer;
191 typedef T& reference;
192 typedef std::bidirectional_iterator_tag iterator_category;
193
194 DequeIterator(Deque<T, inlineCapacity>* deque, size_t index)
195 : Base(deque, index) { }
196
197 DequeIterator(const Iterator& other) : Base(other) { }
198 DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
199
200 T& operator*() const { return *Base::after(); }
201 T* operator->() const { return Base::after(); }
202
203 bool operator==(const Iterator& other) const { return Base::isEqual(other); }
204 bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
205
206 Iterator& operator++() { Base::increment(); return *this; }
207 // postfix ++ intentionally omitted
208 Iterator& operator--() { Base::decrement(); return *this; }
209 // postfix -- intentionally omitted
210};
211
212template<typename T, size_t inlineCapacity = 0>
213class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity> {
214 WTF_MAKE_FAST_ALLOCATED;
215private:
216 typedef DequeIteratorBase<T, inlineCapacity> Base;
217 typedef DequeConstIterator<T, inlineCapacity> Iterator;
218 typedef DequeIterator<T, inlineCapacity> NonConstIterator;
219
220public:
221 typedef ptrdiff_t difference_type;
222 typedef T value_type;
223 typedef const T* pointer;
224 typedef const T& reference;
225 typedef std::bidirectional_iterator_tag iterator_category;
226
227 DequeConstIterator(const Deque<T, inlineCapacity>* deque, size_t index)
228 : Base(deque, index) { }
229
230 DequeConstIterator(const Iterator& other) : Base(other) { }
231 DequeConstIterator(const NonConstIterator& other) : Base(other) { }
232 DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
233 DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
234
235 const T& operator*() const { return *Base::after(); }
236 const T* operator->() const { return Base::after(); }
237
238 bool operator==(const Iterator& other) const { return Base::isEqual(other); }
239 bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
240
241 Iterator& operator++() { Base::increment(); return *this; }
242 // postfix ++ intentionally omitted
243 Iterator& operator--() { Base::decrement(); return *this; }
244 // postfix -- intentionally omitted
245};
246
247#ifdef NDEBUG
248template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkValidity() const { }
249template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkIndexValidity(size_t) const { }
250template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::invalidateIterators() { }
251#else
252template<typename T, size_t inlineCapacity>
253void Deque<T, inlineCapacity>::checkValidity() const
254{
255 // In this implementation a capacity of 1 would confuse append() and
256 // other places that assume the index after capacity - 1 is 0.
257 ASSERT(m_buffer.capacity() != 1);
258
259 if (!m_buffer.capacity()) {
260 ASSERT(!m_start);
261 ASSERT(!m_end);
262 } else {
263 ASSERT(m_start < m_buffer.capacity());
264 ASSERT(m_end < m_buffer.capacity());
265 }
266}
267
268template<typename T, size_t inlineCapacity>
269void Deque<T, inlineCapacity>::checkIndexValidity(size_t index) const
270{
271 ASSERT_UNUSED(index, index <= m_buffer.capacity());
272 if (m_start <= m_end) {
273 ASSERT(index >= m_start);
274 ASSERT(index <= m_end);
275 } else {
276 ASSERT(index >= m_start || index <= m_end);
277 }
278}
279
280template<typename T, size_t inlineCapacity>
281void Deque<T, inlineCapacity>::invalidateIterators()
282{
283 IteratorBase* next;
284 for (IteratorBase* p = m_iterators; p; p = next) {
285 next = p->m_next;
286 p->m_deque = 0;
287 p->m_next = 0;
288 p->m_previous = 0;
289 }
290 m_iterators = 0;
291}
292#endif
293
294template<typename T, size_t inlineCapacity>
295inline Deque<T, inlineCapacity>::Deque()
296 : m_start(0)
297 , m_end(0)
298#ifndef NDEBUG
299 , m_iterators(0)
300#endif
301{
302 checkValidity();
303}
304
305template<typename T, size_t inlineCapacity>
306inline Deque<T, inlineCapacity>::Deque(std::initializer_list<T> initializerList)
307 : Deque()
308{
309 for (auto& element : initializerList)
310 append(element);
311}
312
313template<typename T, size_t inlineCapacity>
314inline Deque<T, inlineCapacity>::Deque(const Deque& other)
315 : m_start(other.m_start)
316 , m_end(other.m_end)
317 , m_buffer(other.m_buffer.capacity())
318#ifndef NDEBUG
319 , m_iterators(0)
320#endif
321{
322 const T* otherBuffer = other.m_buffer.buffer();
323 if (m_start <= m_end)
324 TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
325 else {
326 TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
327 TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
328 }
329}
330
331template<typename T, size_t inlineCapacity>
332inline Deque<T, inlineCapacity>::Deque(Deque&& other)
333 : Deque()
334{
335 swap(other);
336}
337
338template<typename T, size_t inlineCapacity>
339inline auto Deque<T, inlineCapacity>::operator=(const Deque& other) -> Deque&
340{
341 // FIXME: This is inefficient if we're using an inline buffer and T is
342 // expensive to copy since it will copy the buffer twice instead of once.
343 Deque<T, inlineCapacity> copy(other);
344 swap(copy);
345 return *this;
346}
347
348template<typename T, size_t inlineCapacity>
349inline auto Deque<T, inlineCapacity>::operator=(Deque&& other) -> Deque&
350{
351 swap(other);
352 return *this;
353}
354
355template<typename T, size_t inlineCapacity>
356inline void Deque<T, inlineCapacity>::destroyAll()
357{
358 if (m_start <= m_end)
359 TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
360 else {
361 TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
362 TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
363 }
364}
365
366template<typename T, size_t inlineCapacity>
367inline Deque<T, inlineCapacity>::~Deque()
368{
369 checkValidity();
370 invalidateIterators();
371 destroyAll();
372}
373
374template<typename T, size_t inlineCapacity>
375inline void Deque<T, inlineCapacity>::swap(Deque<T, inlineCapacity>& other)
376{
377 checkValidity();
378 other.checkValidity();
379 invalidateIterators();
380 std::swap(m_start, other.m_start);
381 std::swap(m_end, other.m_end);
382 m_buffer.swap(other.m_buffer, 0, 0);
383 checkValidity();
384 other.checkValidity();
385}
386
387template<typename T, size_t inlineCapacity>
388inline void Deque<T, inlineCapacity>::clear()
389{
390 checkValidity();
391 invalidateIterators();
392 destroyAll();
393 m_start = 0;
394 m_end = 0;
395 m_buffer.deallocateBuffer(m_buffer.buffer());
396 checkValidity();
397}
398
399template<typename T, size_t inlineCapacity>
400template<typename Predicate>
401inline auto Deque<T, inlineCapacity>::findIf(const Predicate& predicate) -> iterator
402{
403 return std::find_if(begin(), end(), predicate);
404}
405
406template<typename T, size_t inlineCapacity>
407template<typename Predicate>
408inline auto Deque<T, inlineCapacity>::findIf(const Predicate& predicate) const -> const_iterator
409{
410 return std::find_if(begin(), end(), predicate);
411}
412
413template<typename T, size_t inlineCapacity>
414inline void Deque<T, inlineCapacity>::expandCapacityIfNeeded()
415{
416 if (m_start) {
417 if (m_end + 1 != m_start)
418 return;
419 } else if (m_end) {
420 if (m_end != m_buffer.capacity() - 1)
421 return;
422 } else if (m_buffer.capacity())
423 return;
424
425 expandCapacity();
426}
427
428template<typename T, size_t inlineCapacity>
429void Deque<T, inlineCapacity>::expandCapacity()
430{
431 checkValidity();
432 size_t oldCapacity = m_buffer.capacity();
433 T* oldBuffer = m_buffer.buffer();
434 m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
435 if (m_start <= m_end)
436 TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
437 else {
438 TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
439 size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
440 TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
441 m_start = newStart;
442 }
443 m_buffer.deallocateBuffer(oldBuffer);
444 checkValidity();
445}
446
447template<typename T, size_t inlineCapacity>
448template<typename U>
449bool Deque<T, inlineCapacity>::contains(const U& searchValue) const
450{
451 auto endIterator = end();
452 return std::find(begin(), endIterator, searchValue) != endIterator;
453}
454
455template<typename T, size_t inlineCapacity>
456inline auto Deque<T, inlineCapacity>::takeFirst() -> T
457{
458 T oldFirst = WTFMove(first());
459 removeFirst();
460 return oldFirst;
461}
462
463template<typename T, size_t inlineCapacity>
464inline auto Deque<T, inlineCapacity>::takeLast() -> T
465{
466 T oldLast = WTFMove(last());
467 removeLast();
468 return oldLast;
469}
470
471template<typename T, size_t inlineCapacity> template<typename U>
472inline void Deque<T, inlineCapacity>::append(U&& value)
473{
474 checkValidity();
475 expandCapacityIfNeeded();
476 new (NotNull, std::addressof(m_buffer.buffer()[m_end])) T(std::forward<U>(value));
477 if (m_end == m_buffer.capacity() - 1)
478 m_end = 0;
479 else
480 ++m_end;
481 checkValidity();
482}
483
484template<typename T, size_t inlineCapacity> template<typename U>
485inline void Deque<T, inlineCapacity>::prepend(U&& value)
486{
487 checkValidity();
488 expandCapacityIfNeeded();
489 if (!m_start)
490 m_start = m_buffer.capacity() - 1;
491 else
492 --m_start;
493 new (NotNull, std::addressof(m_buffer.buffer()[m_start])) T(std::forward<U>(value));
494 checkValidity();
495}
496
497template<typename T, size_t inlineCapacity>
498inline void Deque<T, inlineCapacity>::removeFirst()
499{
500 checkValidity();
501 invalidateIterators();
502 ASSERT(!isEmpty());
503 TypeOperations::destruct(std::addressof(m_buffer.buffer()[m_start]), std::addressof(m_buffer.buffer()[m_start + 1]));
504 if (m_start == m_buffer.capacity() - 1)
505 m_start = 0;
506 else
507 ++m_start;
508 checkValidity();
509}
510
511template<typename T, size_t inlineCapacity>
512inline void Deque<T, inlineCapacity>::removeLast()
513{
514 checkValidity();
515 invalidateIterators();
516 ASSERT(!isEmpty());
517 if (!m_end)
518 m_end = m_buffer.capacity() - 1;
519 else
520 --m_end;
521 TypeOperations::destruct(std::addressof(m_buffer.buffer()[m_end]), std::addressof(m_buffer.buffer()[m_end + 1]));
522 checkValidity();
523}
524
525template<typename T, size_t inlineCapacity>
526inline void Deque<T, inlineCapacity>::remove(iterator& it)
527{
528 it.checkValidity();
529 remove(it.m_index);
530}
531
532template<typename T, size_t inlineCapacity>
533inline void Deque<T, inlineCapacity>::remove(const_iterator& it)
534{
535 it.checkValidity();
536 remove(it.m_index);
537}
538
539template<typename T, size_t inlineCapacity>
540inline void Deque<T, inlineCapacity>::remove(size_t position)
541{
542 if (position == m_end)
543 return;
544
545 checkValidity();
546 invalidateIterators();
547
548 T* buffer = m_buffer.buffer();
549 TypeOperations::destruct(std::addressof(buffer[position]), std::addressof(buffer[position + 1]));
550
551 // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
552 if (position >= m_start) {
553 TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
554 m_start = (m_start + 1) % m_buffer.capacity();
555 } else {
556 TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
557 m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
558 }
559 checkValidity();
560}
561
562template<typename T, size_t inlineCapacity>
563template<typename Func>
564inline void Deque<T, inlineCapacity>::removeAllMatching(const Func& func)
565{
566 size_t count = size();
567 while (count--) {
568 T value = takeFirst();
569 if (!func(value))
570 append(WTFMove(value));
571 }
572}
573
574template<typename T, size_t inlineCapacity>
575template<typename U, typename Func>
576inline void Deque<T, inlineCapacity>::appendAndBubble(U&& value, const Func& func)
577{
578 append(WTFMove(value));
579 iterator begin = this->begin();
580 iterator iter = end();
581 --iter;
582 while (iter != begin) {
583 iterator prev = iter;
584 --prev;
585 if (!func(*prev))
586 return;
587 std::swap(*prev, *iter);
588 iter = prev;
589 }
590}
591
592template<typename T, size_t inlineCapacity>
593template<typename Func>
594inline T Deque<T, inlineCapacity>::takeFirst(const Func& func)
595{
596 unsigned count = 0;
597 unsigned size = this->size();
598 while (count < size) {
599 T candidate = takeFirst();
600 if (func(candidate)) {
601 while (count--)
602 prepend(takeLast());
603 return candidate;
604 }
605 count++;
606 append(WTFMove(candidate));
607 }
608 return T();
609}
610
611template<typename T, size_t inlineCapacity>
612template<typename Func>
613inline T Deque<T, inlineCapacity>::takeLast(const Func& func)
614{
615 unsigned count = 0;
616 unsigned size = this->size();
617 while (count < size) {
618 T candidate = takeLast();
619 if (func(candidate)) {
620 while (count--)
621 append(takeFirst());
622 return candidate;
623 }
624 count++;
625 prepend(WTFMove(candidate));
626 }
627 return T();
628}
629
630#ifdef NDEBUG
631template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity() const { }
632template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase<T, inlineCapacity>&) const { }
633template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList() { }
634template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList() { }
635#else
636template<typename T, size_t inlineCapacity>
637void DequeIteratorBase<T, inlineCapacity>::checkValidity() const
638{
639 ASSERT(m_deque);
640 m_deque->checkIndexValidity(m_index);
641}
642
643template<typename T, size_t inlineCapacity>
644void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase& other) const
645{
646 checkValidity();
647 other.checkValidity();
648 ASSERT(m_deque == other.m_deque);
649}
650
651template<typename T, size_t inlineCapacity>
652void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList()
653{
654 if (!m_deque)
655 m_next = 0;
656 else {
657 m_next = m_deque->m_iterators;
658 m_deque->m_iterators = this;
659 if (m_next)
660 m_next->m_previous = this;
661 }
662 m_previous = 0;
663}
664
665template<typename T, size_t inlineCapacity>
666void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList()
667{
668 if (!m_deque) {
669 ASSERT(!m_next);
670 ASSERT(!m_previous);
671 } else {
672 if (m_next) {
673 ASSERT(m_next->m_previous == this);
674 m_next->m_previous = m_previous;
675 }
676 if (m_previous) {
677 ASSERT(m_deque->m_iterators != this);
678 ASSERT(m_previous->m_next == this);
679 m_previous->m_next = m_next;
680 } else {
681 ASSERT(m_deque->m_iterators == this);
682 m_deque->m_iterators = m_next;
683 }
684 }
685 m_next = 0;
686 m_previous = 0;
687}
688#endif
689
690template<typename T, size_t inlineCapacity>
691inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase()
692 : m_deque(0)
693{
694}
695
696template<typename T, size_t inlineCapacity>
697inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const Deque<T, inlineCapacity>* deque, size_t index)
698 : m_deque(const_cast<Deque<T, inlineCapacity>*>(deque))
699 , m_index(index)
700{
701 addToIteratorsList();
702 checkValidity();
703}
704
705template<typename T, size_t inlineCapacity>
706inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const DequeIteratorBase& other)
707 : m_deque(other.m_deque)
708 , m_index(other.m_index)
709{
710 addToIteratorsList();
711 checkValidity();
712}
713
714template<typename T, size_t inlineCapacity>
715inline DequeIteratorBase<T, inlineCapacity>& DequeIteratorBase<T, inlineCapacity>::operator=(const DequeIteratorBase& other)
716{
717 other.checkValidity();
718 removeFromIteratorsList();
719
720 m_deque = other.m_deque;
721 m_index = other.m_index;
722 addToIteratorsList();
723 checkValidity();
724 return *this;
725}
726
727template<typename T, size_t inlineCapacity>
728inline DequeIteratorBase<T, inlineCapacity>::~DequeIteratorBase()
729{
730#ifndef NDEBUG
731 removeFromIteratorsList();
732 m_deque = 0;
733#endif
734}
735
736template<typename T, size_t inlineCapacity>
737inline bool DequeIteratorBase<T, inlineCapacity>::isEqual(const DequeIteratorBase& other) const
738{
739 checkValidity(other);
740 return m_index == other.m_index;
741}
742
743template<typename T, size_t inlineCapacity>
744inline void DequeIteratorBase<T, inlineCapacity>::increment()
745{
746 checkValidity();
747 ASSERT(m_index != m_deque->m_end);
748 ASSERT(m_deque->m_buffer.capacity());
749 if (m_index == m_deque->m_buffer.capacity() - 1)
750 m_index = 0;
751 else
752 ++m_index;
753 checkValidity();
754}
755
756template<typename T, size_t inlineCapacity>
757inline void DequeIteratorBase<T, inlineCapacity>::decrement()
758{
759 checkValidity();
760 ASSERT(m_index != m_deque->m_start);
761 ASSERT(m_deque->m_buffer.capacity());
762 if (!m_index)
763 m_index = m_deque->m_buffer.capacity() - 1;
764 else
765 --m_index;
766 checkValidity();
767}
768
769template<typename T, size_t inlineCapacity>
770inline T* DequeIteratorBase<T, inlineCapacity>::after() const
771{
772 checkValidity();
773 ASSERT(m_index != m_deque->m_end);
774 return std::addressof(m_deque->m_buffer.buffer()[m_index]);
775}
776
777template<typename T, size_t inlineCapacity>
778inline T* DequeIteratorBase<T, inlineCapacity>::before() const
779{
780 checkValidity();
781 ASSERT(m_index != m_deque->m_start);
782 if (!m_index)
783 return std::addressof(m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1]);
784 return std::addressof(m_deque->m_buffer.buffer()[m_index - 1]);
785}
786
787} // namespace WTF
788
789using WTF::Deque;
790