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