CodeBlocks should be in IsoSubspaces
[WebKit-https.git] / Source / WTF / wtf / Deque.h
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 #ifndef WTF_Deque_h
31 #define WTF_Deque_h
32
33 // FIXME: Could move what Vector and Deque share into a separate file.
34 // Deque doesn't actually use Vector.
35
36 #include <iterator>
37 #include <wtf/Vector.h>
38
39 namespace WTF {
40
41 template<typename T, size_t inlineCapacity> class DequeIteratorBase;
42 template<typename T, size_t inlineCapacity> class DequeIterator;
43 template<typename T, size_t inlineCapacity> class DequeConstIterator;
44
45 template<typename T, size_t inlineCapacity = 0>
46 class Deque {
47     WTF_MAKE_FAST_ALLOCATED;
48 public:
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&);
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>
118     iterator findIf(Predicate&&);
119
120 private:
121     friend class DequeIteratorBase<T, inlineCapacity>;
122
123     typedef VectorBuffer<T, inlineCapacity, FastMalloc> 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
143 template<typename T, size_t inlineCapacity = 0>
144 class DequeIteratorBase {
145 protected:
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
162 private:
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
179 template<typename T, size_t inlineCapacity = 0>
180 class DequeIterator : public DequeIteratorBase<T, inlineCapacity> {
181 private:
182     typedef DequeIteratorBase<T, inlineCapacity> Base;
183     typedef DequeIterator<T, inlineCapacity> Iterator;
184
185 public:
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
210 template<typename T, size_t inlineCapacity = 0>
211 class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity> {
212 private:
213     typedef DequeIteratorBase<T, inlineCapacity> Base;
214     typedef DequeConstIterator<T, inlineCapacity> Iterator;
215     typedef DequeIterator<T, inlineCapacity> NonConstIterator;
216
217 public:
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
245 template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkValidity() const { }
246 template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkIndexValidity(size_t) const { }
247 template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::invalidateIterators() { }
248 #else
249 template<typename T, size_t inlineCapacity>
250 void 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
265 template<typename T, size_t inlineCapacity>
266 void 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
277 template<typename T, size_t inlineCapacity>
278 void 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
291 template<typename T, size_t inlineCapacity>
292 inline 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
302 template<typename T, size_t inlineCapacity>
303 inline Deque<T, inlineCapacity>::Deque(std::initializer_list<T> initializerList)
304     : Deque()
305 {
306     for (auto& element : initializerList)
307         append(element);
308 }
309
310 template<typename T, size_t inlineCapacity>
311 inline 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
328 template<typename T, size_t inlineCapacity>
329 inline Deque<T, inlineCapacity>::Deque(Deque&& other)
330     : Deque()
331 {
332     swap(other);
333 }
334
335 template<typename T, size_t inlineCapacity>
336 inline 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
345 template<typename T, size_t inlineCapacity>
346 inline auto Deque<T, inlineCapacity>::operator=(Deque&& other) -> Deque&
347 {
348     swap(other);
349     return *this;
350 }
351
352 template<typename T, size_t inlineCapacity>
353 inline 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
363 template<typename T, size_t inlineCapacity>
364 inline Deque<T, inlineCapacity>::~Deque()
365 {
366     checkValidity();
367     invalidateIterators();
368     destroyAll();
369 }
370
371 template<typename T, size_t inlineCapacity>
372 inline 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
384 template<typename T, size_t inlineCapacity>
385 inline 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
396 template<typename T, size_t inlineCapacity>
397 template<typename Predicate>
398 inline auto Deque<T, inlineCapacity>::findIf(Predicate&& predicate) -> iterator
399 {
400     iterator end_iterator = end();
401     for (iterator it = begin(); it != end_iterator; ++it) {
402         if (predicate(*it))
403             return it;
404     }
405     return end_iterator;
406 }
407
408 template<typename T, size_t inlineCapacity>
409 inline void Deque<T, inlineCapacity>::expandCapacityIfNeeded()
410 {
411     if (m_start) {
412         if (m_end + 1 != m_start)
413             return;
414     } else if (m_end) {
415         if (m_end != m_buffer.capacity() - 1)
416             return;
417     } else if (m_buffer.capacity())
418         return;
419
420     expandCapacity();
421 }
422
423 template<typename T, size_t inlineCapacity>
424 void Deque<T, inlineCapacity>::expandCapacity()
425 {
426     checkValidity();
427     size_t oldCapacity = m_buffer.capacity();
428     T* oldBuffer = m_buffer.buffer();
429     m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
430     if (m_start <= m_end)
431         TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
432     else {
433         TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
434         size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
435         TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
436         m_start = newStart;
437     }
438     m_buffer.deallocateBuffer(oldBuffer);
439     checkValidity();
440 }
441
442 template<typename T, size_t inlineCapacity>
443 template<typename U>
444 bool Deque<T, inlineCapacity>::contains(const U& searchValue)
445 {
446     for (auto& value : *this) {
447         if (value == searchValue)
448             return true;
449     }
450     return false;
451 }
452
453 template<typename T, size_t inlineCapacity>
454 inline auto Deque<T, inlineCapacity>::takeFirst() -> T
455 {
456     T oldFirst = WTFMove(first());
457     removeFirst();
458     return oldFirst;
459 }
460
461 template<typename T, size_t inlineCapacity>
462 inline auto Deque<T, inlineCapacity>::takeLast() -> T
463 {
464     T oldLast = WTFMove(last());
465     removeLast();
466     return oldLast;
467 }
468
469 template<typename T, size_t inlineCapacity> template<typename U>
470 inline void Deque<T, inlineCapacity>::append(U&& value)
471 {
472     checkValidity();
473     expandCapacityIfNeeded();
474     new (NotNull, std::addressof(m_buffer.buffer()[m_end])) T(std::forward<U>(value));
475     if (m_end == m_buffer.capacity() - 1)
476         m_end = 0;
477     else
478         ++m_end;
479     checkValidity();
480 }
481
482 template<typename T, size_t inlineCapacity> template<typename U>
483 inline void Deque<T, inlineCapacity>::prepend(U&& value)
484 {
485     checkValidity();
486     expandCapacityIfNeeded();
487     if (!m_start)
488         m_start = m_buffer.capacity() - 1;
489     else
490         --m_start;
491     new (NotNull, std::addressof(m_buffer.buffer()[m_start])) T(std::forward<U>(value));
492     checkValidity();
493 }
494
495 template<typename T, size_t inlineCapacity>
496 inline void Deque<T, inlineCapacity>::removeFirst()
497 {
498     checkValidity();
499     invalidateIterators();
500     ASSERT(!isEmpty());
501     TypeOperations::destruct(std::addressof(m_buffer.buffer()[m_start]), std::addressof(m_buffer.buffer()[m_start + 1]));
502     if (m_start == m_buffer.capacity() - 1)
503         m_start = 0;
504     else
505         ++m_start;
506     checkValidity();
507 }
508
509 template<typename T, size_t inlineCapacity>
510 inline void Deque<T, inlineCapacity>::removeLast()
511 {
512     checkValidity();
513     invalidateIterators();
514     ASSERT(!isEmpty());
515     if (!m_end)
516         m_end = m_buffer.capacity() - 1;
517     else
518         --m_end;
519     TypeOperations::destruct(std::addressof(m_buffer.buffer()[m_end]), std::addressof(m_buffer.buffer()[m_end + 1]));
520     checkValidity();
521 }
522
523 template<typename T, size_t inlineCapacity>
524 inline void Deque<T, inlineCapacity>::remove(iterator& it)
525 {
526     it.checkValidity();
527     remove(it.m_index);
528 }
529
530 template<typename T, size_t inlineCapacity>
531 inline void Deque<T, inlineCapacity>::remove(const_iterator& it)
532 {
533     it.checkValidity();
534     remove(it.m_index);
535 }
536
537 template<typename T, size_t inlineCapacity>
538 inline void Deque<T, inlineCapacity>::remove(size_t position)
539 {
540     if (position == m_end)
541         return;
542
543     checkValidity();
544     invalidateIterators();
545
546     T* buffer = m_buffer.buffer();
547     TypeOperations::destruct(std::addressof(buffer[position]), std::addressof(buffer[position + 1]));
548
549     // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
550     if (position >= m_start) {
551         TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
552         m_start = (m_start + 1) % m_buffer.capacity();
553     } else {
554         TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
555         m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
556     }
557     checkValidity();
558 }
559
560 template<typename T, size_t inlineCapacity>
561 template<typename Func>
562 inline void Deque<T, inlineCapacity>::removeAllMatching(const Func& func)
563 {
564     size_t count = size();
565     while (count--) {
566         T value = takeFirst();
567         if (!func(value))
568             append(WTFMove(value));
569     }
570 }
571
572 template<typename T, size_t inlineCapacity>
573 template<typename U, typename Func>
574 inline void Deque<T, inlineCapacity>::appendAndBubble(U&& value, const Func& func)
575 {
576     append(WTFMove(value));
577     iterator begin = this->begin();
578     iterator iter = end();
579     --iter;
580     while (iter != begin) {
581         iterator prev = iter;
582         --prev;
583         if (!func(*prev))
584             return;
585         std::swap(*prev, *iter);
586         iter = prev;
587     }
588 }
589
590 template<typename T, size_t inlineCapacity>
591 template<typename Func>
592 inline T Deque<T, inlineCapacity>::takeFirst(const Func& func)
593 {
594     unsigned count = 0;
595     unsigned size = this->size();
596     while (count < size) {
597         T candidate = takeFirst();
598         if (func(candidate)) {
599             while (count--)
600                 prepend(takeLast());
601             return candidate;
602         }
603         count++;
604         append(WTFMove(candidate));
605     }
606     return T();
607 }
608
609 template<typename T, size_t inlineCapacity>
610 template<typename Func>
611 inline T Deque<T, inlineCapacity>::takeLast(const Func& func)
612 {
613     unsigned count = 0;
614     unsigned size = this->size();
615     while (count < size) {
616         T candidate = takeLast();
617         if (func(candidate)) {
618             while (count--)
619                 append(takeFirst());
620             return candidate;
621         }
622         count++;
623         prepend(WTFMove(candidate));
624     }
625     return T();
626 }
627
628 #ifdef NDEBUG
629 template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity() const { }
630 template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase<T, inlineCapacity>&) const { }
631 template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList() { }
632 template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList() { }
633 #else
634 template<typename T, size_t inlineCapacity>
635 void DequeIteratorBase<T, inlineCapacity>::checkValidity() const
636 {
637     ASSERT(m_deque);
638     m_deque->checkIndexValidity(m_index);
639 }
640
641 template<typename T, size_t inlineCapacity>
642 void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase& other) const
643 {
644     checkValidity();
645     other.checkValidity();
646     ASSERT(m_deque == other.m_deque);
647 }
648
649 template<typename T, size_t inlineCapacity>
650 void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList()
651 {
652     if (!m_deque)
653         m_next = 0;
654     else {
655         m_next = m_deque->m_iterators;
656         m_deque->m_iterators = this;
657         if (m_next)
658             m_next->m_previous = this;
659     }
660     m_previous = 0;
661 }
662
663 template<typename T, size_t inlineCapacity>
664 void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList()
665 {
666     if (!m_deque) {
667         ASSERT(!m_next);
668         ASSERT(!m_previous);
669     } else {
670         if (m_next) {
671             ASSERT(m_next->m_previous == this);
672             m_next->m_previous = m_previous;
673         }
674         if (m_previous) {
675             ASSERT(m_deque->m_iterators != this);
676             ASSERT(m_previous->m_next == this);
677             m_previous->m_next = m_next;
678         } else {
679             ASSERT(m_deque->m_iterators == this);
680             m_deque->m_iterators = m_next;
681         }
682     }
683     m_next = 0;
684     m_previous = 0;
685 }
686 #endif
687
688 template<typename T, size_t inlineCapacity>
689 inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase()
690     : m_deque(0)
691 {
692 }
693
694 template<typename T, size_t inlineCapacity>
695 inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const Deque<T, inlineCapacity>* deque, size_t index)
696     : m_deque(const_cast<Deque<T, inlineCapacity>*>(deque))
697     , m_index(index)
698 {
699     addToIteratorsList();
700     checkValidity();
701 }
702
703 template<typename T, size_t inlineCapacity>
704 inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const DequeIteratorBase& other)
705     : m_deque(other.m_deque)
706     , m_index(other.m_index)
707 {
708     addToIteratorsList();
709     checkValidity();
710 }
711
712 template<typename T, size_t inlineCapacity>
713 inline DequeIteratorBase<T, inlineCapacity>& DequeIteratorBase<T, inlineCapacity>::operator=(const DequeIteratorBase& other)
714 {
715     other.checkValidity();
716     removeFromIteratorsList();
717
718     m_deque = other.m_deque;
719     m_index = other.m_index;
720     addToIteratorsList();
721     checkValidity();
722     return *this;
723 }
724
725 template<typename T, size_t inlineCapacity>
726 inline DequeIteratorBase<T, inlineCapacity>::~DequeIteratorBase()
727 {
728 #ifndef NDEBUG
729     removeFromIteratorsList();
730     m_deque = 0;
731 #endif
732 }
733
734 template<typename T, size_t inlineCapacity>
735 inline bool DequeIteratorBase<T, inlineCapacity>::isEqual(const DequeIteratorBase& other) const
736 {
737     checkValidity(other);
738     return m_index == other.m_index;
739 }
740
741 template<typename T, size_t inlineCapacity>
742 inline void DequeIteratorBase<T, inlineCapacity>::increment()
743 {
744     checkValidity();
745     ASSERT(m_index != m_deque->m_end);
746     ASSERT(m_deque->m_buffer.capacity());
747     if (m_index == m_deque->m_buffer.capacity() - 1)
748         m_index = 0;
749     else
750         ++m_index;
751     checkValidity();
752 }
753
754 template<typename T, size_t inlineCapacity>
755 inline void DequeIteratorBase<T, inlineCapacity>::decrement()
756 {
757     checkValidity();
758     ASSERT(m_index != m_deque->m_start);
759     ASSERT(m_deque->m_buffer.capacity());
760     if (!m_index)
761         m_index = m_deque->m_buffer.capacity() - 1;
762     else
763         --m_index;
764     checkValidity();
765 }
766
767 template<typename T, size_t inlineCapacity>
768 inline T* DequeIteratorBase<T, inlineCapacity>::after() const
769 {
770     checkValidity();
771     ASSERT(m_index != m_deque->m_end);
772     return std::addressof(m_deque->m_buffer.buffer()[m_index]);
773 }
774
775 template<typename T, size_t inlineCapacity>
776 inline T* DequeIteratorBase<T, inlineCapacity>::before() const
777 {
778     checkValidity();
779     ASSERT(m_index != m_deque->m_start);
780     if (!m_index)
781         return std::addressof(m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1]);
782     return std::addressof(m_deque->m_buffer.buffer()[m_index - 1]);
783 }
784
785 } // namespace WTF
786
787 using WTF::Deque;
788
789 #endif // WTF_Deque_h