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