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