third_party/WebKit/Source/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 #include <iterator>
  39
  40 namespace WTF {
  41     template<typename T, size_t inlineCapacity, typename Allocator> class DequeIteratorBase;
  42     template<typename T, size_t inlineCapacity, typename Allocator> class DequeIterator;
  43     template<typename T, size_t inlineCapacity, typename Allocator> class DequeConstIterator;
  44
  45     template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
  46     class Deque : public ConditionalDestructor<Deque<T, INLINE_CAPACITY, Allocator>, (INLINE_CAPACITY == 0) && Allocator::isGarbageCollected> {
  47         WTF_USE_ALLOCATOR(Deque, Allocator);
  48     public:
  49         typedef DequeIterator<T, inlineCapacity, Allocator> iterator;
  50         typedef DequeConstIterator<T, inlineCapacity, Allocator> const_iterator;
  51         typedef std::reverse_iterator<iterator> reverse_iterator;
  52         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  53         typedef PassTraits<T> Pass;
  54         typedef typename PassTraits<T>::PassType PassType;
  55
  56         Deque();
  57         Deque(const Deque<T, inlineCapacity, Allocator>&);
  58         // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
  59         Deque<T, 0, Allocator>& operator=(const Deque&);
  60
  61         void finalize();
  62         void finalizeGarbageCollectedObject() { finalize(); }
  63
  64         // We hard wire the inlineCapacity to zero here, due to crbug.com/360572
  65         void swap(Deque<T, 0, Allocator>&);
  66
  67         size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
  68         bool isEmpty() const { return m_start == m_end; }
  69
  70         iterator begin() { return iterator(this, m_start); }
  71         iterator end() { return iterator(this, m_end); }
  72         const_iterator begin() const { return const_iterator(this, m_start); }
  73         const_iterator end() const { return const_iterator(this, m_end); }
  74         reverse_iterator rbegin() { return reverse_iterator(end()); }
  75         reverse_iterator rend() { return reverse_iterator(begin()); }
  76         const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
  77         const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
  78
  79         T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
  80         const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
  81         PassType takeFirst();
  82
  83         T& last() { ASSERT(m_start != m_end); return *(--end()); }
  84         const T& last() const { ASSERT(m_start != m_end); return *(--end()); }
  85         PassType takeLast();
  86
  87         T& at(size_t i)
  88         {
  89             RELEASE_ASSERT(i < size());
  90             size_t right = m_buffer.capacity() - m_start;
  91             return i < right ? m_buffer.buffer()[m_start + i] : m_buffer.buffer()[i - right];
  92         }
  93         const T& at(size_t i) const
  94         {
  95             RELEASE_ASSERT(i < size());
  96             size_t right = m_buffer.capacity() - m_start;
  97             return i < right ? m_buffer.buffer()[m_start + i] : m_buffer.buffer()[i - right];
  98         }
  99
 100         T& operator[](size_t i) { return at(i); }
 101         const T& operator[](size_t i) const { return at(i); }
 102
 103         template<typename U> void append(const U&);
 104         template<typename U> void prepend(const U&);
 105         void removeFirst();
 106         void removeLast();
 107         void remove(iterator&);
 108         void remove(const_iterator&);
 109
 110         void clear();
 111
 112         template<typename Predicate>
 113         iterator findIf(Predicate&);
 114
 115         template<typename VisitorDispatcher> void trace(VisitorDispatcher);
 116
 117     private:
 118         friend class DequeIteratorBase<T, inlineCapacity, Allocator>;
 119
 120         typedef VectorBuffer<T, INLINE_CAPACITY, Allocator> Buffer;
 121         typedef VectorTypeOperations<T> TypeOperations;
 122         typedef DequeIteratorBase<T, inlineCapacity, Allocator> IteratorBase;
 123
 124         void remove(size_t position);
 125         void destroyAll();
 126         void expandCapacityIfNeeded();
 127         void expandCapacity();
 128
 129         Buffer m_buffer;
 130         unsigned m_start;
 131         unsigned m_end;
 132     };
 133
 134     template<typename T, size_t inlineCapacity, typename Allocator>
 135     class DequeIteratorBase {
 136     protected:
 137         DequeIteratorBase();
 138         DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>*, size_t);
 139         DequeIteratorBase(const DequeIteratorBase&);
 140         DequeIteratorBase<T, 0, Allocator>& operator=(const DequeIteratorBase<T, 0, Allocator>&);
 141         ~DequeIteratorBase();
 142
 143         void assign(const DequeIteratorBase& other) { *this = other; }
 144
 145         void increment();
 146         void decrement();
 147
 148         T* before() const;
 149         T* after() const;
 150
 151         bool isEqual(const DequeIteratorBase&) const;
 152
 153     private:
 154         Deque<T, inlineCapacity, Allocator>* m_deque;
 155         unsigned m_index;
 156
 157         friend class Deque<T, inlineCapacity, Allocator>;
 158     };
 159
 160     template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
 161     class DequeIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
 162     private:
 163         typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
 164         typedef DequeIterator<T, inlineCapacity, Allocator> Iterator;
 165
 166     public:
 167         typedef ptrdiff_t difference_type;
 168         typedef T value_type;
 169         typedef T* pointer;
 170         typedef T& reference;
 171         typedef std::bidirectional_iterator_tag iterator_category;
 172
 173         DequeIterator(Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
 174
 175         DequeIterator(const Iterator& other) : Base(other) { }
 176         DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
 177
 178         T& operator*() const { return *Base::after(); }
 179         T* operator->() const { return Base::after(); }
 180
 181         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
 182         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 183
 184         Iterator& operator++() { Base::increment(); return *this; }
 185         // postfix ++ intentionally omitted
 186         Iterator& operator--() { Base::decrement(); return *this; }
 187         // postfix -- intentionally omitted
 188     };
 189
 190     template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
 191     class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
 192     private:
 193         typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
 194         typedef DequeConstIterator<T, inlineCapacity, Allocator> Iterator;
 195         typedef DequeIterator<T, inlineCapacity, Allocator> NonConstIterator;
 196
 197     public:
 198         typedef ptrdiff_t difference_type;
 199         typedef T value_type;
 200         typedef const T* pointer;
 201         typedef const T& reference;
 202         typedef std::bidirectional_iterator_tag iterator_category;
 203
 204         DequeConstIterator(const Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
 205
 206         DequeConstIterator(const Iterator& other) : Base(other) { }
 207         DequeConstIterator(const NonConstIterator& other) : Base(other) { }
 208         DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
 209         DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
 210
 211         const T& operator*() const { return *Base::after(); }
 212         const T* operator->() const { return Base::after(); }
 213
 214         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
 215         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 216
 217         Iterator& operator++() { Base::increment(); return *this; }
 218         // postfix ++ intentionally omitted
 219         Iterator& operator--() { Base::decrement(); return *this; }
 220         // postfix -- intentionally omitted
 221     };
 222
 223     template<typename T, size_t inlineCapacity, typename Allocator>
 224     inline Deque<T, inlineCapacity, Allocator>::Deque()
 225         : m_start(0)
 226         , m_end(0)
 227     {
 228         static_assert(!IsPolymorphic<T>::value || !VectorTraits<T>::canInitializeWithMemset, "Cannot initialize with memset if there is a vtable");
 229 #if ENABLE(OILPAN)
 230         static_assert(Allocator::isGarbageCollected || !IsAllowOnlyInlineAllocation<T>::value || !NeedsTracing<T>::value, "Cannot put ALLOW_ONLY_INLINE_ALLOCATION objects that have trace methods into an off-heap Deque");
 231 #endif
 232     }
 233
 234     template<typename T, size_t inlineCapacity, typename Allocator>
 235     inline Deque<T, inlineCapacity, Allocator>::Deque(const Deque<T, inlineCapacity, Allocator>& other)
 236         : m_buffer(other.m_buffer.capacity())
 237         , m_start(other.m_start)
 238         , m_end(other.m_end)
 239     {
 240         const T* otherBuffer = other.m_buffer.buffer();
 241         if (m_start <= m_end)
 242             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
 243         else {
 244             TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
 245             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
 246         }
 247     }
 248
 249     template<typename T, size_t inlineCapacity, typename Allocator>
 250     inline Deque<T, 0, Allocator>& Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other)
 251     {
 252         Deque<T> copy(other);
 253         swap(copy);
 254         return *this;
 255     }
 256
 257     template<typename T, size_t inlineCapacity, typename Allocator>
 258     inline void Deque<T, inlineCapacity, Allocator>::destroyAll()
 259     {
 260         if (m_start <= m_end) {
 261             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
 262             m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
 263         } else {
 264             TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
 265             m_buffer.clearUnusedSlots(m_buffer.buffer(), m_buffer.buffer() + m_end);
 266             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
 267             m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
 268         }
 269     }
 270
 271     // Off-GC-heap deques: Destructor should be called.
 272     // On-GC-heap deques: Destructor should be called for inline buffers
 273     // (if any) but destructor shouldn't be called for vector backing since
 274     // it is managed by the traced GC heap.
 275     template<typename T, size_t inlineCapacity, typename Allocator>
 276     inline void Deque<T, inlineCapacity, Allocator>::finalize()
 277     {
 278         if (!INLINE_CAPACITY && !m_buffer.buffer())
 279             return;
 280         if (!isEmpty() && !(Allocator::isGarbageCollected && m_buffer.hasOutOfLineBuffer()))
 281             destroyAll();
 282
 283         m_buffer.destruct();
 284     }
 285
 286     // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
 287     template<typename T, size_t inlineCapacity, typename Allocator>
 288     inline void Deque<T, inlineCapacity, Allocator>::swap(Deque<T, 0, Allocator>& other)
 289     {
 290         std::swap(m_start, other.m_start);
 291         std::swap(m_end, other.m_end);
 292         m_buffer.swapVectorBuffer(other.m_buffer);
 293     }
 294
 295     template<typename T, size_t inlineCapacity, typename Allocator>
 296     inline void Deque<T, inlineCapacity, Allocator>::clear()
 297     {
 298         destroyAll();
 299         m_start = 0;
 300         m_end = 0;
 301         m_buffer.deallocateBuffer(m_buffer.buffer());
 302         m_buffer.resetBufferPointer();
 303     }
 304
 305     template<typename T, size_t inlineCapacity, typename Allocator>
 306     template<typename Predicate>
 307     inline DequeIterator<T, inlineCapacity, Allocator> Deque<T, inlineCapacity, Allocator>::findIf(Predicate& predicate)
 308     {
 309         iterator end_iterator = end();
 310         for (iterator it = begin(); it != end_iterator; ++it) {
 311             if (predicate(*it))
 312                 return it;
 313         }
 314         return end_iterator;
 315     }
 316
 317     template<typename T, size_t inlineCapacity, typename Allocator>
 318     inline void Deque<T, inlineCapacity, Allocator>::expandCapacityIfNeeded()
 319     {
 320         if (m_start) {
 321             if (m_end + 1 != m_start)
 322                 return;
 323         } else if (m_end) {
 324             if (m_end != m_buffer.capacity() - 1)
 325                 return;
 326         } else if (m_buffer.capacity())
 327             return;
 328
 329         expandCapacity();
 330     }
 331
 332     template<typename T, size_t inlineCapacity, typename Allocator>
 333     void Deque<T, inlineCapacity, Allocator>::expandCapacity()
 334     {
 335         size_t oldCapacity = m_buffer.capacity();
 336         T* oldBuffer = m_buffer.buffer();
 337         size_t newCapacity = std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1);
 338         if (m_buffer.expandBuffer(newCapacity)) {
 339             if (m_start <= m_end) {
 340                 // No adjustments to be done.
 341             } else {
 342                 size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
 343                 TypeOperations::moveOverlapping(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
 344                 m_buffer.clearUnusedSlots(oldBuffer + m_start, oldBuffer + std::min(oldCapacity, newStart));
 345                 m_start = newStart;
 346             }
 347             return;
 348         }
 349         m_buffer.allocateBuffer(newCapacity);
 350         if (m_start <= m_end) {
 351             TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
 352             m_buffer.clearUnusedSlots(oldBuffer + m_start, oldBuffer + m_end);
 353         } else {
 354             TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
 355             m_buffer.clearUnusedSlots(oldBuffer, oldBuffer + m_end);
 356             size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
 357             TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
 358             m_buffer.clearUnusedSlots(oldBuffer + m_start, oldBuffer + oldCapacity);
 359             m_start = newStart;
 360         }
 361         m_buffer.deallocateBuffer(oldBuffer);
 362     }
 363
 364     template<typename T, size_t inlineCapacity, typename Allocator>
 365     inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeFirst()
 366     {
 367         T oldFirst = Pass::transfer(first());
 368         removeFirst();
 369         return Pass::transfer(oldFirst);
 370     }
 371
 372     template<typename T, size_t inlineCapacity, typename Allocator>
 373     inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeLast()
 374     {
 375         T oldLast = Pass::transfer(last());
 376         removeLast();
 377         return Pass::transfer(oldLast);
 378     }
 379
 380     template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
 381     inline void Deque<T, inlineCapacity, Allocator>::append(const U& value)
 382     {
 383         expandCapacityIfNeeded();
 384         new (NotNull, &m_buffer.buffer()[m_end]) T(value);
 385         if (m_end == m_buffer.capacity() - 1)
 386             m_end = 0;
 387         else
 388             ++m_end;
 389     }
 390
 391     template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
 392     inline void Deque<T, inlineCapacity, Allocator>::prepend(const U& value)
 393     {
 394         expandCapacityIfNeeded();
 395         if (!m_start)
 396             m_start = m_buffer.capacity() - 1;
 397         else
 398             --m_start;
 399         new (NotNull, &m_buffer.buffer()[m_start]) T(value);
 400     }
 401
 402     template<typename T, size_t inlineCapacity, typename Allocator>
 403     inline void Deque<T, inlineCapacity, Allocator>::removeFirst()
 404     {
 405         ASSERT(!isEmpty());
 406         TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
 407         m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
 408         if (m_start == m_buffer.capacity() - 1)
 409             m_start = 0;
 410         else
 411             ++m_start;
 412     }
 413
 414     template<typename T, size_t inlineCapacity, typename Allocator>
 415     inline void Deque<T, inlineCapacity, Allocator>::removeLast()
 416     {
 417         ASSERT(!isEmpty());
 418         if (!m_end)
 419             m_end = m_buffer.capacity() - 1;
 420         else
 421             --m_end;
 422         TypeOperations::destruct(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
 423         m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
 424     }
 425
 426     template<typename T, size_t inlineCapacity, typename Allocator>
 427     inline void Deque<T, inlineCapacity, Allocator>::remove(iterator& it)
 428     {
 429         remove(it.m_index);
 430     }
 431
 432     template<typename T, size_t inlineCapacity, typename Allocator>
 433     inline void Deque<T, inlineCapacity, Allocator>::remove(const_iterator& it)
 434     {
 435         remove(it.m_index);
 436     }
 437
 438     template<typename T, size_t inlineCapacity, typename Allocator>
 439     inline void Deque<T, inlineCapacity, Allocator>::remove(size_t position)
 440     {
 441         if (position == m_end)
 442             return;
 443
 444         T* buffer = m_buffer.buffer();
 445         TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
 446
 447         // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
 448         if (position >= m_start) {
 449             TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
 450             m_buffer.clearUnusedSlots(buffer + m_start, buffer + m_start + 1);
 451             m_start = (m_start + 1) % m_buffer.capacity();
 452         } else {
 453             TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
 454             m_buffer.clearUnusedSlots(buffer + m_end - 1, buffer + m_end);
 455             m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
 456         }
 457     }
 458
 459     template<typename T, size_t inlineCapacity, typename Allocator>
 460     inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase()
 461         : m_deque(0)
 462     {
 463     }
 464
 465     template<typename T, size_t inlineCapacity, typename Allocator>
 466     inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>* deque, size_t index)
 467         : m_deque(const_cast<Deque<T, inlineCapacity, Allocator>*>(deque))
 468         , m_index(index)
 469     {
 470     }
 471
 472     template<typename T, size_t inlineCapacity, typename Allocator>
 473     inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const DequeIteratorBase& other)
 474         : m_deque(other.m_deque)
 475         , m_index(other.m_index)
 476     {
 477     }
 478
 479     template<typename T, size_t inlineCapacity, typename Allocator>
 480     inline DequeIteratorBase<T, 0, Allocator>& DequeIteratorBase<T, inlineCapacity, Allocator>::operator=(const DequeIteratorBase<T, 0, Allocator>& other)
 481     {
 482         m_deque = other.m_deque;
 483         m_index = other.m_index;
 484         return *this;
 485     }
 486
 487     template<typename T, size_t inlineCapacity, typename Allocator>
 488     inline DequeIteratorBase<T, inlineCapacity, Allocator>::~DequeIteratorBase()
 489     {
 490     }
 491
 492     template<typename T, size_t inlineCapacity, typename Allocator>
 493     inline bool DequeIteratorBase<T, inlineCapacity, Allocator>::isEqual(const DequeIteratorBase& other) const
 494     {
 495         return m_index == other.m_index;
 496     }
 497
 498     template<typename T, size_t inlineCapacity, typename Allocator>
 499     inline void DequeIteratorBase<T, inlineCapacity, Allocator>::increment()
 500     {
 501         ASSERT(m_index != m_deque->m_end);
 502         ASSERT(m_deque->m_buffer.capacity());
 503         if (m_index == m_deque->m_buffer.capacity() - 1)
 504             m_index = 0;
 505         else
 506             ++m_index;
 507     }
 508
 509     template<typename T, size_t inlineCapacity, typename Allocator>
 510     inline void DequeIteratorBase<T, inlineCapacity, Allocator>::decrement()
 511     {
 512         ASSERT(m_index != m_deque->m_start);
 513         ASSERT(m_deque->m_buffer.capacity());
 514         if (!m_index)
 515             m_index = m_deque->m_buffer.capacity() - 1;
 516         else
 517             --m_index;
 518     }
 519
 520     template<typename T, size_t inlineCapacity, typename Allocator>
 521     inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::after() const
 522     {
 523         ASSERT(m_index != m_deque->m_end);
 524         return &m_deque->m_buffer.buffer()[m_index];
 525     }
 526
 527     template<typename T, size_t inlineCapacity, typename Allocator>
 528     inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::before() const
 529     {
 530         ASSERT(m_index != m_deque->m_start);
 531         if (!m_index)
 532             return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
 533         return &m_deque->m_buffer.buffer()[m_index - 1];
 534     }
 535
 536     // This is only called if the allocator is a HeapAllocator. It is used when
 537     // visiting during a tracing GC.
 538     template<typename T, size_t inlineCapacity, typename Allocator>
 539     template<typename VisitorDispatcher>
 540     void Deque<T, inlineCapacity, Allocator>::trace(VisitorDispatcher visitor)
 541     {
 542         ASSERT(Allocator::isGarbageCollected); // Garbage collector must be enabled.
 543         const T* bufferBegin = m_buffer.buffer();
 544         const T* end = bufferBegin + m_end;
 545         if (ShouldBeTraced<VectorTraits<T>>::value) {
 546             if (m_start <= m_end) {
 547                 for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != end; bufferEntry++)
 548                     Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>(visitor, *const_cast<T*>(bufferEntry));
 549             } else {
 550                 for (const T* bufferEntry = bufferBegin; bufferEntry != end; bufferEntry++)
 551                     Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>(visitor, *const_cast<T*>(bufferEntry));
 552                 const T* bufferEnd = m_buffer.buffer() + m_buffer.capacity();
 553                 for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != bufferEnd; bufferEntry++)
 554                     Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>(visitor, *const_cast<T*>(bufferEntry));
 555             }
 556         }
 557         if (m_buffer.hasOutOfLineBuffer())
 558             Allocator::markNoTracing(visitor, m_buffer.buffer());
 559     }
 560
 561     template<typename T, size_t inlineCapacity, typename Allocator>
 562     inline void swap(Deque<T, inlineCapacity, Allocator>& a, Deque<T, inlineCapacity, Allocator>& b)
 563     {
 564         a.swap(b);
 565     }
 566
 567 #if !ENABLE(OILPAN)
 568     template<typename T, size_t N>
 569     struct NeedsTracing<Deque<T, N>> {
 570         static const bool value = false;
 571     };
 572 #endif
 573
 574 } // namespace WTF
 575
 576 using WTF::Deque;
 577
 578 #endif // WTF_Deque_h