Home | History | Annotate | Download | only in wtf 
      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 
     38 namespace 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 
    683 using WTF::Deque;
    684 
    685 #endif // WTF_Deque_h
    686