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