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