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