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