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