wtf/Deque.h

   1 /*
   2  * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1.  Redistributions of source code must retain the above copyright
   9  *     notice, this list of conditions and the following disclaimer.
  10  * 2.  Redistributions in binary form must reproduce the above copyright
  11  *     notice, this list of conditions and the following disclaimer in the
  12  *     documentation and/or other materials provided with the distribution.
  13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
  14  *     its contributors may be used to endorse or promote products derived
  15  *     from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #ifndef WTF_Deque_h
  30 #define WTF_Deque_h
  31
  32 // FIXME: Could move what Vector and Deque share into a separate file.
  33 // Deque doesn't actually use Vector.
  34
  35 #include "Vector.h"
  36
  37 namespace WTF {
  38
  39     template<typename T> class DequeIteratorBase;
  40     template<typename T> class DequeIterator;
  41     template<typename T> class DequeConstIterator;
  42     template<typename T> class DequeReverseIterator;
  43     template<typename T> class DequeConstReverseIterator;
  44
  45     template<typename T>
  46     class Deque {
  47     public:
  48         typedef DequeIterator<T> iterator;
  49         typedef DequeConstIterator<T> const_iterator;
  50         typedef DequeReverseIterator<T> reverse_iterator;
  51         typedef DequeConstReverseIterator<T> const_reverse_iterator;
  52
  53         Deque();
  54         Deque(const Deque<T>&);
  55         Deque& operator=(const Deque<T>&);
  56         ~Deque();
  57
  58         void swap(Deque<T>&);
  59
  60         size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
  61         bool isEmpty() const { return m_start == m_end; }
  62
  63         iterator begin() { return iterator(this, m_start); }
  64         iterator end() { return iterator(this, m_end); }
  65         const_iterator begin() const { return const_iterator(this, m_start); }
  66         const_iterator end() const { return const_iterator(this, m_end); }
  67         reverse_iterator rbegin() { return reverse_iterator(this, m_end); }
  68         reverse_iterator rend() { return reverse_iterator(this, m_start); }
  69         const_reverse_iterator rbegin() const { return const_reverse_iterator(this, m_end); }
  70         const_reverse_iterator rend() const { return const_reverse_iterator(this, m_start); }
  71
  72         T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
  73         const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
  74
  75         template<typename U> void append(const U&);
  76         template<typename U> void prepend(const U&);
  77         void removeFirst();
  78
  79         void clear();
  80
  81     private:
  82         friend class DequeIteratorBase<T>;
  83
  84         typedef VectorBuffer<T, 0> Buffer;
  85         typedef VectorTypeOperations<T> TypeOperations;
  86         typedef DequeIteratorBase<T> IteratorBase;
  87
  88         void invalidateIterators();
  89         void destroyAll();
  90         void checkValidity() const;
  91         void checkIndexValidity(size_t) const;
  92         void expandCapacityIfNeeded();
  93         void expandCapacity();
  94
  95         size_t m_start;
  96         size_t m_end;
  97         Buffer m_buffer;
  98 #ifndef NDEBUG
  99         mutable IteratorBase* m_iterators;
 100 #endif
 101     };
 102
 103     template<typename T>
 104     class DequeIteratorBase {
 105     private:
 106         typedef DequeIteratorBase<T> Base;
 107
 108     protected:
 109         DequeIteratorBase();
 110         DequeIteratorBase(const Deque<T>*, size_t);
 111         DequeIteratorBase(const Base&);
 112         Base& operator=(const Base&);
 113         ~DequeIteratorBase();
 114
 115         void assign(const Base& other) { *this = other; }
 116
 117         void increment();
 118         void decrement();
 119
 120         T* before() const;
 121         T* after() const;
 122
 123         bool isEqual(const Base&) const;
 124
 125     private:
 126         void addToIteratorsList();
 127         void checkValidity() const;
 128         void checkValidity(const Base&) const;
 129
 130         Deque<T>* m_deque;
 131         size_t m_index;
 132
 133         friend class Deque<T>;
 134
 135 #ifndef NDEBUG
 136         mutable DequeIteratorBase* m_next;
 137         mutable DequeIteratorBase* m_previous;
 138 #endif
 139     };
 140
 141     template<typename T>
 142     class DequeIterator : public DequeIteratorBase<T> {
 143     private:
 144         typedef DequeIteratorBase<T> Base;
 145         typedef DequeIterator<T> Iterator;
 146
 147     public:
 148         DequeIterator(Deque<T>* deque, size_t index) : Base(deque, index) { }
 149
 150         DequeIterator(const Iterator& other) : Base(other) { }
 151         DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
 152
 153         T& operator*() const { return *Base::after(); }
 154         T* operator->() const { return Base::after(); }
 155
 156         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
 157         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 158
 159         Iterator& operator++() { Base::increment(); return *this; }
 160         // postfix ++ intentionally omitted
 161         Iterator& operator--() { Base::decrement(); return *this; }
 162         // postfix -- intentionally omitted
 163     };
 164
 165     template<typename T>
 166     class DequeConstIterator : public DequeIteratorBase<T> {
 167     private:
 168         typedef DequeIteratorBase<T> Base;
 169         typedef DequeConstIterator<T> Iterator;
 170         typedef DequeIterator<T> NonConstIterator;
 171
 172     public:
 173         DequeConstIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
 174
 175         DequeConstIterator(const Iterator& other) : Base(other) { }
 176         DequeConstIterator(const NonConstIterator& other) : Base(other) { }
 177         DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
 178         DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
 179
 180         const T& operator*() const { return *Base::after(); }
 181         const T* operator->() const { return Base::after(); }
 182
 183         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
 184         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 185
 186         Iterator& operator++() { Base::increment(); return *this; }
 187         // postfix ++ intentionally omitted
 188         Iterator& operator--() { Base::decrement(); return *this; }
 189         // postfix -- intentionally omitted
 190     };
 191
 192     template<typename T>
 193     class DequeReverseIterator : public DequeIteratorBase<T> {
 194     private:
 195         typedef DequeIteratorBase<T> Base;
 196         typedef DequeReverseIterator<T> Iterator;
 197
 198     public:
 199         DequeReverseIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
 200
 201         DequeReverseIterator(const Iterator& other) : Base(other) { }
 202         DequeReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
 203
 204         T& operator*() const { return *Base::before(); }
 205         T* operator->() const { return Base::before(); }
 206
 207         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
 208         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 209
 210         Iterator& operator++() { Base::decrement(); return *this; }
 211         // postfix ++ intentionally omitted
 212         Iterator& operator--() { Base::increment(); return *this; }
 213         // postfix -- intentionally omitted
 214     };
 215
 216     template<typename T>
 217     class DequeConstReverseIterator : public DequeIteratorBase<T> {
 218     private:
 219         typedef DequeIteratorBase<T> Base;
 220         typedef DequeConstReverseIterator<T> Iterator;
 221         typedef DequeReverseIterator<T> NonConstIterator;
 222
 223     public:
 224         DequeConstReverseIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
 225
 226         DequeConstReverseIterator(const Iterator& other) : Base(other) { }
 227         DequeConstReverseIterator(const NonConstIterator& other) : Base(other) { }
 228         DequeConstReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
 229         DequeConstReverseIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
 230
 231         const T& operator*() const { return *Base::before(); }
 232         const T* operator->() const { return Base::before(); }
 233
 234         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
 235         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 236
 237         Iterator& operator++() { Base::decrement(); return *this; }
 238         // postfix ++ intentionally omitted
 239         Iterator& operator--() { Base::increment(); return *this; }
 240         // postfix -- intentionally omitted
 241     };
 242
 243 #ifdef NDEBUG
 244     template<typename T> inline void Deque<T>::checkValidity() const { }
 245     template<typename T> inline void Deque<T>::checkIndexValidity(size_t) const { }
 246     template<typename T> inline void Deque<T>::invalidateIterators() { }
 247 #else
 248     template<typename T>
 249     void Deque<T>::checkValidity() const
 250     {
 251         if (!m_buffer.capacity()) {
 252             ASSERT(!m_start);
 253             ASSERT(!m_end);
 254         } else {
 255             ASSERT(m_start < m_buffer.capacity());
 256             ASSERT(m_end < m_buffer.capacity());
 257         }
 258     }
 259
 260     template<typename T>
 261     void Deque<T>::checkIndexValidity(size_t index) const
 262     {
 263         ASSERT(index <= m_buffer.capacity());
 264         if (m_start <= m_end) {
 265             ASSERT(index >= m_start);
 266             ASSERT(index <= m_end);
 267         } else {
 268             ASSERT(index >= m_start || index <= m_end);
 269         }
 270     }
 271
 272     template<typename T>
 273     void Deque<T>::invalidateIterators()
 274     {
 275         IteratorBase* next;
 276         for (IteratorBase* p = m_iterators; p; p = next) {
 277             next = p->m_next;
 278             p->m_deque = 0;
 279             p->m_next = 0;
 280             p->m_previous = 0;
 281         }
 282         m_iterators = 0;
 283     }
 284 #endif
 285
 286     template<typename T>
 287     inline Deque<T>::Deque()
 288         : m_start(0)
 289         , m_end(0)
 290 #ifndef NDEBUG
 291         , m_iterators(0)
 292 #endif
 293     {
 294         checkValidity();
 295     }
 296
 297     template<typename T>
 298     inline Deque<T>::Deque(const Deque<T>& other)
 299         : m_start(other.m_start)
 300         , m_end(other.m_end)
 301         , m_buffer(other.m_buffer.capacity())
 302 #ifndef NDEBUG
 303         , m_iterators(0)
 304 #endif
 305     {
 306         const T* otherBuffer = other.m_buffer.buffer();
 307         if (m_start <= m_end)
 308             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
 309         else {
 310             TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
 311             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
 312         }
 313     }
 314
 315     template<typename T>
 316     void deleteAllValues(const Deque<T>& collection)
 317     {
 318         typedef typename Deque<T>::const_iterator iterator;
 319         iterator end = collection.end();
 320         for (iterator it = collection.begin(); it != end; ++it)
 321             delete *it;
 322     }
 323
 324     template<typename T>
 325     inline Deque<T>& Deque<T>::operator=(const Deque<T>& other)
 326     {
 327         Deque<T> copy(other);
 328         swap(copy);
 329         return *this;
 330     }
 331
 332     template<typename T>
 333     inline void Deque<T>::destroyAll()
 334     {
 335         if (m_start <= m_end)
 336             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
 337         else {
 338             TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
 339             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
 340         }
 341     }
 342
 343     template<typename T>
 344     inline Deque<T>::~Deque()
 345     {
 346         checkValidity();
 347         invalidateIterators();
 348         destroyAll();
 349     }
 350
 351     template <typename T>
 352     inline void Deque<T>::swap(Deque<T>& other)
 353     {
 354         checkValidity();
 355         other.checkValidity();
 356         invalidateIterators();
 357         std::swap(m_start, other.m_start);
 358         std::swap(m_end, other.m_end);
 359         m_buffer.swap(other.m_buffer);
 360         checkValidity();
 361         other.checkValidity();
 362     }
 363
 364     template <typename T>
 365     inline void Deque<T>::clear()
 366     {
 367         checkValidity();
 368         invalidateIterators();
 369         destroyAll();
 370         m_start = 0;
 371         m_end = 0;
 372         checkValidity();
 373     }
 374
 375     template<typename T>
 376     inline void Deque<T>::expandCapacityIfNeeded()
 377     {
 378         if (m_start) {
 379             if (m_end + 1 != m_start)
 380                 return;
 381         } else if (m_end) {
 382             if (m_end != m_buffer.capacity() - 1)
 383                 return;
 384         } else if (m_buffer.capacity())
 385             return;
 386
 387         expandCapacity();
 388     }
 389
 390     template<typename T>
 391     void Deque<T>::expandCapacity()
 392     {
 393         checkValidity();
 394         size_t oldCapacity = m_buffer.capacity();
 395         size_t newCapacity = max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1);
 396         T* oldBuffer = m_buffer.buffer();
 397         m_buffer.allocateBuffer(newCapacity);
 398         if (m_start <= m_end)
 399             TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
 400         else {
 401             TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
 402             size_t newStart = newCapacity - (oldCapacity - m_start);
 403             TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
 404             m_start = newStart;
 405         }
 406         m_buffer.deallocateBuffer(oldBuffer);
 407         checkValidity();
 408     }
 409
 410     template<typename T> template<typename U>
 411     inline void Deque<T>::append(const U& value)
 412     {
 413         checkValidity();
 414         expandCapacityIfNeeded();
 415         new (&m_buffer.buffer()[m_end]) T(value);
 416         if (m_end == m_buffer.capacity() - 1)
 417             m_end = 0;
 418         else
 419             ++m_end;
 420         checkValidity();
 421     }
 422
 423     template<typename T> template<typename U>
 424     inline void Deque<T>::prepend(const U& value)
 425     {
 426         checkValidity();
 427         expandCapacityIfNeeded();
 428         if (!m_start)
 429             m_start = m_buffer.capacity() - 1;
 430         else
 431             --m_start;
 432         new (&m_buffer.buffer()[m_start]) T(value);
 433         checkValidity();
 434     }
 435
 436     template<typename T>
 437     inline void Deque<T>::removeFirst()
 438     {
 439         checkValidity();
 440         invalidateIterators();
 441         ASSERT(!isEmpty());
 442         TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
 443         if (m_start == m_buffer.capacity() - 1)
 444             m_start = 0;
 445         else
 446             ++m_start;
 447         checkValidity();
 448     }
 449
 450 #ifdef NDEBUG
 451     template<typename T> inline void DequeIteratorBase<T>::checkValidity() const { }
 452     template<typename T> inline void DequeIteratorBase<T>::checkValidity(const DequeIteratorBase<T>&) const { }
 453     template<typename T> inline void DequeIteratorBase<T>::addToIteratorsList() { }
 454 #else
 455     template<typename T>
 456     void DequeIteratorBase<T>::checkValidity() const
 457     {
 458         ASSERT(m_deque);
 459         m_deque->checkIndexValidity(m_index);
 460     }
 461
 462     template<typename T>
 463     void DequeIteratorBase<T>::checkValidity(const Base& other) const
 464     {
 465         checkValidity();
 466         other.checkValidity();
 467         ASSERT(m_deque == other.m_deque);
 468     }
 469
 470     template<typename T>
 471     void DequeIteratorBase<T>::addToIteratorsList()
 472     {
 473         if (!m_deque)
 474             m_next = 0;
 475         else {
 476             m_next = m_deque->m_iterators;
 477             m_deque->m_iterators = this;
 478             if (m_next)
 479                 m_next->m_previous = this;
 480         }
 481         m_previous = 0;
 482     }
 483 #endif
 484
 485     template<typename T>
 486     inline DequeIteratorBase<T>::DequeIteratorBase()
 487         : m_deque(0)
 488     {
 489     }
 490
 491     template<typename T>
 492     inline DequeIteratorBase<T>::DequeIteratorBase(const Deque<T>* deque, size_t index)
 493         : m_deque(const_cast<Deque<T>*>(deque))
 494         , m_index(index)
 495     {
 496         addToIteratorsList();
 497         checkValidity();
 498     }
 499
 500     template<typename T>
 501     inline DequeIteratorBase<T>::DequeIteratorBase(const Base& other)
 502         : m_deque(other.m_deque)
 503         , m_index(other.m_index)
 504     {
 505         addToIteratorsList();
 506         checkValidity();
 507     }
 508
 509     template<typename T>
 510     inline DequeIteratorBase<T>::~DequeIteratorBase()
 511     {
 512 #ifndef NDEBUG
 513         // Delete iterator from doubly-linked list of iterators.
 514         if (!m_deque) {
 515             ASSERT(!m_next);
 516             ASSERT(!m_previous);
 517         } else {
 518             if (m_next) {
 519                 ASSERT(m_next->m_previous == this);
 520                 m_next->m_previous = m_previous;
 521             }
 522             if (m_previous) {
 523                 ASSERT(m_deque->m_iterators != this);
 524                 ASSERT(m_previous->m_next == this);
 525                 m_previous->m_next = m_next;
 526             } else {
 527                 ASSERT(m_deque->m_iterators == this);
 528                 m_deque->m_iterators = m_next;
 529             }
 530         }
 531         m_deque = 0;
 532         m_next = 0;
 533         m_previous = 0;
 534 #endif
 535     }
 536
 537     template<typename T>
 538     inline bool DequeIteratorBase<T>::isEqual(const Base& other) const
 539     {
 540         checkValidity(other);
 541         return m_index == other.m_index;
 542     }
 543
 544     template<typename T>
 545     inline void DequeIteratorBase<T>::increment()
 546     {
 547         checkValidity();
 548         ASSERT(m_index != m_deque->m_end);
 549         ASSERT(m_deque->m_buffer.capacity());
 550         if (m_index == m_deque->m_buffer.capacity() - 1)
 551             m_index = 0;
 552         else
 553             ++m_index;
 554         checkValidity();
 555     }
 556
 557     template<typename T>
 558     inline void DequeIteratorBase<T>::decrement()
 559     {
 560         checkValidity();
 561         ASSERT(m_index != m_deque->m_start);
 562         ASSERT(m_deque->m_buffer.capacity());
 563         if (!m_index)
 564             m_index = m_deque->m_buffer.capacity() - 1;
 565         else
 566             --m_index;
 567         checkValidity();
 568     }
 569
 570     template<typename T>
 571     inline T* DequeIteratorBase<T>::after() const
 572     {
 573         checkValidity();
 574         ASSERT(m_index != m_deque->m_end);
 575         return &m_deque->m_buffer.buffer()[m_index];
 576     }
 577
 578     template<typename T>
 579     inline T* DequeIteratorBase<T>::before() const
 580     {
 581         checkValidity();
 582         ASSERT(m_index != m_deque->m_start);
 583         if (!m_index)
 584             return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
 585         return &m_deque->m_buffer.buffer()[m_index - 1];
 586     }
 587
 588 } // namespace WTF
 589
 590 using WTF::Deque;
 591
 592 #endif // WTF_Deque_h