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