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     inline Deque<T>& Deque<T>::operator=(const Deque<T>& other)
 317     {
 318         Deque<T> copy(other);
 319         swap(copy);
 320         return *this;
 321     }
 322
 323     template<typename T>
 324     inline void Deque<T>::destroyAll()
 325     {
 326         if (m_start <= m_end)
 327             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
 328         else {
 329             TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
 330             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
 331         }
 332     }
 333
 334     template<typename T>
 335     inline Deque<T>::~Deque()
 336     {
 337         checkValidity();
 338         invalidateIterators();
 339         destroyAll();
 340     }
 341
 342     template <typename T>
 343     inline void Deque<T>::swap(Deque<T>& other)
 344     {
 345         checkValidity();
 346         other.checkValidity();
 347         invalidateIterators();
 348         std::swap(m_start, other.m_start);
 349         std::swap(m_end, other.m_end);
 350         m_buffer.swap(other.m_buffer);
 351         checkValidity();
 352         other.checkValidity();
 353     }
 354
 355     template <typename T>
 356     inline void Deque<T>::clear()
 357     {
 358         checkValidity();
 359         invalidateIterators();
 360         destroyAll();
 361         m_start = 0;
 362         m_end = 0;
 363         checkValidity();
 364     }
 365
 366     template<typename T>
 367     inline void Deque<T>::expandCapacityIfNeeded()
 368     {
 369         if (m_start) {
 370             if (m_end + 1 != m_start)
 371                 return;
 372         } else if (m_end) {
 373             if (m_end != m_buffer.capacity() - 1)
 374                 return;
 375         } else if (m_buffer.capacity())
 376             return;
 377
 378         expandCapacity();
 379     }
 380
 381     template<typename T>
 382     void Deque<T>::expandCapacity()
 383     {
 384         checkValidity();
 385         size_t oldCapacity = m_buffer.capacity();
 386         size_t newCapacity = max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1);
 387         T* oldBuffer = m_buffer.buffer();
 388         m_buffer.allocateBuffer(newCapacity);
 389         if (m_start <= m_end)
 390             TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
 391         else {
 392             TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
 393             size_t newStart = newCapacity - (oldCapacity - m_start);
 394             TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
 395             m_start = newStart;
 396         }
 397         m_buffer.deallocateBuffer(oldBuffer);
 398         checkValidity();
 399     }
 400
 401     template<typename T> template<typename U>
 402     inline void Deque<T>::append(const U& value)
 403     {
 404         checkValidity();
 405         expandCapacityIfNeeded();
 406         new (&m_buffer.buffer()[m_end]) T(value);
 407         if (m_end == m_buffer.capacity() - 1)
 408             m_end = 0;
 409         else
 410             ++m_end;
 411         checkValidity();
 412     }
 413
 414     template<typename T> template<typename U>
 415     inline void Deque<T>::prepend(const U& value)
 416     {
 417         checkValidity();
 418         expandCapacityIfNeeded();
 419         if (!m_start)
 420             m_start = m_buffer.capacity() - 1;
 421         else
 422             --m_start;
 423         new (&m_buffer.buffer()[m_start]) T(value);
 424         checkValidity();
 425     }
 426
 427     template<typename T>
 428     inline void Deque<T>::removeFirst()
 429     {
 430         checkValidity();
 431         invalidateIterators();
 432         ASSERT(!isEmpty());
 433         TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
 434         if (m_start == m_buffer.capacity() - 1)
 435             m_start = 0;
 436         else
 437             ++m_start;
 438         checkValidity();
 439     }
 440
 441 #ifdef NDEBUG
 442     template<typename T> inline void DequeIteratorBase<T>::checkValidity() const { }
 443     template<typename T> inline void DequeIteratorBase<T>::checkValidity(const DequeIteratorBase<T>&) const { }
 444     template<typename T> inline void DequeIteratorBase<T>::addToIteratorsList() { }
 445 #else
 446     template<typename T>
 447     void DequeIteratorBase<T>::checkValidity() const
 448     {
 449         ASSERT(m_deque);
 450         m_deque->checkIndexValidity(m_index);
 451     }
 452
 453     template<typename T>
 454     void DequeIteratorBase<T>::checkValidity(const Base& other) const
 455     {
 456         checkValidity();
 457         other.checkValidity();
 458         ASSERT(m_deque == other.m_deque);
 459     }
 460
 461     template<typename T>
 462     void DequeIteratorBase<T>::addToIteratorsList()
 463     {
 464         if (!m_deque)
 465             m_next = 0;
 466         else {
 467             m_next = m_deque->m_iterators;
 468             m_deque->m_iterators = this;
 469             if (m_next)
 470                 m_next->m_previous = this;
 471         }
 472         m_previous = 0;
 473     }
 474 #endif
 475
 476     template<typename T>
 477     inline DequeIteratorBase<T>::DequeIteratorBase()
 478         : m_deque(0)
 479     {
 480     }
 481
 482     template<typename T>
 483     inline DequeIteratorBase<T>::DequeIteratorBase(const Deque<T>* deque, size_t index)
 484         : m_deque(const_cast<Deque<T>*>(deque))
 485         , m_index(index)
 486     {
 487         addToIteratorsList();
 488         checkValidity();
 489     }
 490
 491     template<typename T>
 492     inline DequeIteratorBase<T>::DequeIteratorBase(const Base& other)
 493         : m_deque(other.m_deque)
 494         , m_index(other.m_index)
 495     {
 496         addToIteratorsList();
 497         checkValidity();
 498     }
 499
 500     template<typename T>
 501     inline DequeIteratorBase<T>::~DequeIteratorBase()
 502     {
 503 #ifndef NDEBUG
 504         // Delete iterator from doubly-linked list of iterators.
 505         if (!m_deque) {
 506             ASSERT(!m_next);
 507             ASSERT(!m_previous);
 508         } else {
 509             if (m_next) {
 510                 ASSERT(m_next->m_previous == this);
 511                 m_next->m_previous = m_previous;
 512             }
 513             if (m_previous) {
 514                 ASSERT(m_deque->m_iterators != this);
 515                 ASSERT(m_previous->m_next == this);
 516                 m_previous->m_next = m_next;
 517             } else {
 518                 ASSERT(m_deque->m_iterators == this);
 519                 m_deque->m_iterators = m_next;
 520             }
 521         }
 522         m_deque = 0;
 523         m_next = 0;
 524         m_previous = 0;
 525 #endif
 526     }
 527
 528     template<typename T>
 529     inline bool DequeIteratorBase<T>::isEqual(const Base& other) const
 530     {
 531         checkValidity(other);
 532         return m_index == other.m_index;
 533     }
 534
 535     template<typename T>
 536     inline void DequeIteratorBase<T>::increment()
 537     {
 538         checkValidity();
 539         ASSERT(m_index != m_deque->m_end);
 540         ASSERT(m_deque->m_buffer.capacity());
 541         if (m_index == m_deque->m_buffer.capacity() - 1)
 542             m_index = 0;
 543         else
 544             ++m_index;
 545         checkValidity();
 546     }
 547
 548     template<typename T>
 549     inline void DequeIteratorBase<T>::decrement()
 550     {
 551         checkValidity();
 552         ASSERT(m_index != m_deque->m_start);
 553         ASSERT(m_deque->m_buffer.capacity());
 554         if (!m_index)
 555             m_index = m_deque->m_buffer.capacity() - 1;
 556         else
 557             --m_index;
 558         checkValidity();
 559     }
 560
 561     template<typename T>
 562     inline T* DequeIteratorBase<T>::after() const
 563     {
 564         checkValidity();
 565         ASSERT(m_index != m_deque->m_end);
 566         return &m_deque->m_buffer.buffer()[m_index];
 567     }
 568
 569     template<typename T>
 570     inline T* DequeIteratorBase<T>::before() const
 571     {
 572         checkValidity();
 573         ASSERT(m_index != m_deque->m_start);
 574         if (!m_index)
 575             return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
 576         return &m_deque->m_buffer.buffer()[m_index - 1];
 577     }
 578
 579 } // namespace WTF
 580
 581 using WTF::Deque;
 582
 583 #endif // WTF_Deque_h