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
39namespace WTF {
40
41template<typename T, size_t inlineCapacity> class DequeIteratorBase;
42template<typename T, size_t inlineCapacity> class DequeIterator;
43template<typename T, size_t inlineCapacity> class DequeConstIterator;
44
45template<typename T, size_t inlineCapacity = 0>
46class Deque {
47 WTF_MAKE_FAST_ALLOCATED;
48public:
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
98private:
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
121template<typename T, size_t inlineCapacity = 0>
122class DequeIteratorBase {
123protected:
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
140private:
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
157template<typename T, size_t inlineCapacity = 0>
158class DequeIterator : public DequeIteratorBase<T, inlineCapacity> {
159private:
160 typedef DequeIteratorBase<T, inlineCapacity> Base;
161 typedef DequeIterator<T, inlineCapacity> Iterator;
162
163public:
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
188template<typename T, size_t inlineCapacity = 0>
189class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity> {
190private:
191 typedef DequeIteratorBase<T, inlineCapacity> Base;
192 typedef DequeConstIterator<T, inlineCapacity> Iterator;
193 typedef DequeIterator<T, inlineCapacity> NonConstIterator;
194
195public:
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
223template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkValidity() const { }
224template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkIndexValidity(size_t) const { }
225template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::invalidateIterators() { }
226#else
227template<typename T, size_t inlineCapacity>
228void 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
243template<typename T, size_t inlineCapacity>
244void 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
255template<typename T, size_t inlineCapacity>
256void 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
269template<typename T, size_t inlineCapacity>
270inline 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
280template<typename T, size_t inlineCapacity>
281inline Deque<T, inlineCapacity>::Deque(std::initializer_list<T> initializerList)
282 : Deque()
283{
284 for (auto& element : initializerList)
285 append(element);
286}
287
288template<typename T, size_t inlineCapacity>
289inline 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
306template<typename T, size_t inlineCapacity>
307inline Deque<T, inlineCapacity>::Deque(Deque&& other)
308 : Deque()
309{
310 swap(other);
311}
312
313template<typename T, size_t inlineCapacity>
314inline 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
323template<typename T, size_t inlineCapacity>
324inline auto Deque<T, inlineCapacity>::operator=(Deque&& other) -> Deque&
325{
326 swap(other);
327 return *this;
328}
329
330template<typename T, size_t inlineCapacity>
331inline 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
341template<typename T, size_t inlineCapacity>
342inline Deque<T, inlineCapacity>::~Deque()
343{
344 checkValidity();
345 invalidateIterators();
346 destroyAll();
347}
348
349template<typename T, size_t inlineCapacity>
350inline 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
362template<typename T, size_t inlineCapacity>
363inline 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
374template<typename T, size_t inlineCapacity>
375template<typename Predicate>
376inline 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
386template<typename T, size_t inlineCapacity>
387inline 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
401template<typename T, size_t inlineCapacity>
402void 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
420template<typename T, size_t inlineCapacity>
421inline auto Deque<T, inlineCapacity>::takeFirst() -> T
422{
423 T oldFirst = WTFMove(first());
424 removeFirst();
425 return oldFirst;
426}
427
428template<typename T, size_t inlineCapacity>
429inline auto Deque<T, inlineCapacity>::takeLast() -> T
430{
431 T oldLast = WTFMove(last());
432 removeLast();
433 return oldLast;
434}
435
436template<typename T, size_t inlineCapacity> template<typename U>
437inline 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
449template<typename T, size_t inlineCapacity> template<typename U>
450inline 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
462template<typename T, size_t inlineCapacity>
463inline 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
476template<typename T, size_t inlineCapacity>
477inline 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
490template<typename T, size_t inlineCapacity>
491inline void Deque<T, inlineCapacity>::remove(iterator& it)
492{
493 it.checkValidity();
494 remove(it.m_index);
495}
496
497template<typename T, size_t inlineCapacity>
498inline void Deque<T, inlineCapacity>::remove(const_iterator& it)
499{
500 it.checkValidity();
501 remove(it.m_index);
502}
503
504template<typename T, size_t inlineCapacity>
505inline 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
528template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity() const { }
529template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase<T, inlineCapacity>&) const { }
530template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList() { }
531template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList() { }
532#else
533template<typename T, size_t inlineCapacity>
534void DequeIteratorBase<T, inlineCapacity>::checkValidity() const
535{
536 ASSERT(m_deque);
537 m_deque->checkIndexValidity(m_index);
538}
539
540template<typename T, size_t inlineCapacity>
541void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase& other) const
542{
543 checkValidity();
544 other.checkValidity();
545 ASSERT(m_deque == other.m_deque);
546}
547
548template<typename T, size_t inlineCapacity>
549void 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
562template<typename T, size_t inlineCapacity>
563void 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
587template<typename T, size_t inlineCapacity>
588inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase()
589 : m_deque(0)
590{
591}
592
593template<typename T, size_t inlineCapacity>
594inline 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
602template<typename T, size_t inlineCapacity>
603inline 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
611template<typename T, size_t inlineCapacity>
612inline 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
624template<typename T, size_t inlineCapacity>
625inline DequeIteratorBase<T, inlineCapacity>::~DequeIteratorBase()
626{
627#ifndef NDEBUG
628 removeFromIteratorsList();
629 m_deque = 0;
630#endif
631}
632
633template<typename T, size_t inlineCapacity>
634inline bool DequeIteratorBase<T, inlineCapacity>::isEqual(const DequeIteratorBase& other) const
635{
636 checkValidity(other);
637 return m_index == other.m_index;
638}
639
640template<typename T, size_t inlineCapacity>
641inline 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
653template<typename T, size_t inlineCapacity>
654inline 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
666template<typename T, size_t inlineCapacity>
667inline 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
674template<typename T, size_t inlineCapacity>
675inline 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
686using WTF::Deque;
687
688#endif // WTF_Deque_h
689