src/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 VectorDestructorBase<Deque<T, inlineCapacity, Allocator>, T, (inlineCapacity > 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         void trace(typename Allocator::Visitor*);
 116
 117     private:
 118         friend class DequeIteratorBase<T, inlineCapacity, Allocator>;
 119
 120         typedef VectorBuffer<T, inlineCapacity, 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     }
 229
 230     template<typename T, size_t inlineCapacity, typename Allocator>
 231     inline Deque<T, inlineCapacity, Allocator>::Deque(const Deque<T, inlineCapacity, Allocator>& other)
 232         : m_buffer(other.m_buffer.capacity())
 233         , m_start(other.m_start)
 234         , m_end(other.m_end)
 235     {
 236         const T* otherBuffer = other.m_buffer.buffer();
 237         if (m_start <= m_end)
 238             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
 239         else {
 240             TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
 241             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
 242         }
 243     }
 244
 245     template<typename T, size_t inlineCapacity, typename Allocator>
 246     inline Deque<T, 0, Allocator>& Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other)
 247     {
 248         Deque<T> copy(other);
 249         swap(copy);
 250         return *this;
 251     }
 252
 253     template<typename T, size_t inlineCapacity, typename Allocator>
 254     inline void Deque<T, inlineCapacity, Allocator>::destroyAll()
 255     {
 256         if (m_start <= m_end) {
 257             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
 258             m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
 259         } else {
 260             TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
 261             m_buffer.clearUnusedSlots(m_buffer.buffer(), m_buffer.buffer() + m_end);
 262             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
 263             m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
 264         }
 265     }
 266
 267     // Off-GC-heap deques: Destructor should be called.
 268     // On-GC-heap deques: Destructor should be called for inline buffers
 269     // (if any) but destructor shouldn't be called for vector backing since
 270     // it is managed by the traced GC heap.
 271     template<typename T, size_t inlineCapacity, typename Allocator>
 272     inline void Deque<T, inlineCapacity, Allocator>::finalize()
 273     {
 274         if (!inlineCapacity && !m_buffer.buffer())
 275             return;
 276         if (!isEmpty() && !(Allocator::isGarbageCollected && m_buffer.hasOutOfLineBuffer()))
 277             destroyAll();
 278
 279         m_buffer.destruct();
 280     }
 281
 282     // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
 283     template<typename T, size_t inlineCapacity, typename Allocator>
 284     inline void Deque<T, inlineCapacity, Allocator>::swap(Deque<T, 0, Allocator>& other)
 285     {
 286         std::swap(m_start, other.m_start);
 287         std::swap(m_end, other.m_end);
 288         m_buffer.swapVectorBuffer(other.m_buffer);
 289     }
 290
 291     template<typename T, size_t inlineCapacity, typename Allocator>
 292     inline void Deque<T, inlineCapacity, Allocator>::clear()
 293     {
 294         destroyAll();
 295         m_start = 0;
 296         m_end = 0;
 297         m_buffer.deallocateBuffer(m_buffer.buffer());
 298         m_buffer.resetBufferPointer();
 299     }
 300
 301     template<typename T, size_t inlineCapacity, typename Allocator>
 302     template<typename Predicate>
 303     inline DequeIterator<T, inlineCapacity, Allocator> Deque<T, inlineCapacity, Allocator>::findIf(Predicate& predicate)
 304     {
 305         iterator end_iterator = end();
 306         for (iterator it = begin(); it != end_iterator; ++it) {
 307             if (predicate(*it))
 308                 return it;
 309         }
 310         return end_iterator;
 311     }
 312
 313     template<typename T, size_t inlineCapacity, typename Allocator>
 314     inline void Deque<T, inlineCapacity, Allocator>::expandCapacityIfNeeded()
 315     {
 316         if (m_start) {
 317             if (m_end + 1 != m_start)
 318                 return;
 319         } else if (m_end) {
 320             if (m_end != m_buffer.capacity() - 1)
 321                 return;
 322         } else if (m_buffer.capacity())
 323             return;
 324
 325         expandCapacity();
 326     }
 327
 328     template<typename T, size_t inlineCapacity, typename Allocator>
 329     void Deque<T, inlineCapacity, Allocator>::expandCapacity()
 330     {
 331         size_t oldCapacity = m_buffer.capacity();
 332         T* oldBuffer = m_buffer.buffer();
 333         m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
 334         if (m_start <= m_end)
 335             TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
 336         else {
 337             TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
 338             size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
 339             TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
 340             m_start = newStart;
 341         }
 342         m_buffer.deallocateBuffer(oldBuffer);
 343     }
 344
 345     template<typename T, size_t inlineCapacity, typename Allocator>
 346     inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeFirst()
 347     {
 348         T oldFirst = Pass::transfer(first());
 349         removeFirst();
 350         return Pass::transfer(oldFirst);
 351     }
 352
 353     template<typename T, size_t inlineCapacity, typename Allocator>
 354     inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeLast()
 355     {
 356         T oldLast = Pass::transfer(last());
 357         removeLast();
 358         return Pass::transfer(oldLast);
 359     }
 360
 361     template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
 362     inline void Deque<T, inlineCapacity, Allocator>::append(const U& value)
 363     {
 364         expandCapacityIfNeeded();
 365         new (NotNull, &m_buffer.buffer()[m_end]) T(value);
 366         if (m_end == m_buffer.capacity() - 1)
 367             m_end = 0;
 368         else
 369             ++m_end;
 370     }
 371
 372     template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
 373     inline void Deque<T, inlineCapacity, Allocator>::prepend(const U& value)
 374     {
 375         expandCapacityIfNeeded();
 376         if (!m_start)
 377             m_start = m_buffer.capacity() - 1;
 378         else
 379             --m_start;
 380         new (NotNull, &m_buffer.buffer()[m_start]) T(value);
 381     }
 382
 383     template<typename T, size_t inlineCapacity, typename Allocator>
 384     inline void Deque<T, inlineCapacity, Allocator>::removeFirst()
 385     {
 386         ASSERT(!isEmpty());
 387         TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
 388         m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
 389         if (m_start == m_buffer.capacity() - 1)
 390             m_start = 0;
 391         else
 392             ++m_start;
 393     }
 394
 395     template<typename T, size_t inlineCapacity, typename Allocator>
 396     inline void Deque<T, inlineCapacity, Allocator>::removeLast()
 397     {
 398         ASSERT(!isEmpty());
 399         if (!m_end)
 400             m_end = m_buffer.capacity() - 1;
 401         else
 402             --m_end;
 403         TypeOperations::destruct(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
 404         m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
 405     }
 406
 407     template<typename T, size_t inlineCapacity, typename Allocator>
 408     inline void Deque<T, inlineCapacity, Allocator>::remove(iterator& it)
 409     {
 410         remove(it.m_index);
 411     }
 412
 413     template<typename T, size_t inlineCapacity, typename Allocator>
 414     inline void Deque<T, inlineCapacity, Allocator>::remove(const_iterator& it)
 415     {
 416         remove(it.m_index);
 417     }
 418
 419     template<typename T, size_t inlineCapacity, typename Allocator>
 420     inline void Deque<T, inlineCapacity, Allocator>::remove(size_t position)
 421     {
 422         if (position == m_end)
 423             return;
 424
 425         T* buffer = m_buffer.buffer();
 426         TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
 427
 428         // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
 429         if (position >= m_start) {
 430             TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
 431             m_buffer.clearUnusedSlots(buffer + m_start, buffer + m_start + 1);
 432             m_start = (m_start + 1) % m_buffer.capacity();
 433         } else {
 434             TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
 435             m_buffer.clearUnusedSlots(buffer + m_end - 1, buffer + m_end);
 436             m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
 437         }
 438     }
 439
 440     template<typename T, size_t inlineCapacity, typename Allocator>
 441     inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase()
 442         : m_deque(0)
 443     {
 444     }
 445
 446     template<typename T, size_t inlineCapacity, typename Allocator>
 447     inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>* deque, size_t index)
 448         : m_deque(const_cast<Deque<T, inlineCapacity, Allocator>*>(deque))
 449         , m_index(index)
 450     {
 451     }
 452
 453     template<typename T, size_t inlineCapacity, typename Allocator>
 454     inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const DequeIteratorBase& other)
 455         : m_deque(other.m_deque)
 456         , m_index(other.m_index)
 457     {
 458     }
 459
 460     template<typename T, size_t inlineCapacity, typename Allocator>
 461     inline DequeIteratorBase<T, 0, Allocator>& DequeIteratorBase<T, inlineCapacity, Allocator>::operator=(const DequeIteratorBase<T, 0, Allocator>& other)
 462     {
 463         m_deque = other.m_deque;
 464         m_index = other.m_index;
 465         return *this;
 466     }
 467
 468     template<typename T, size_t inlineCapacity, typename Allocator>
 469     inline DequeIteratorBase<T, inlineCapacity, Allocator>::~DequeIteratorBase()
 470     {
 471     }
 472
 473     template<typename T, size_t inlineCapacity, typename Allocator>
 474     inline bool DequeIteratorBase<T, inlineCapacity, Allocator>::isEqual(const DequeIteratorBase& other) const
 475     {
 476         return m_index == other.m_index;
 477     }
 478
 479     template<typename T, size_t inlineCapacity, typename Allocator>
 480     inline void DequeIteratorBase<T, inlineCapacity, Allocator>::increment()
 481     {
 482         ASSERT(m_index != m_deque->m_end);
 483         ASSERT(m_deque->m_buffer.capacity());
 484         if (m_index == m_deque->m_buffer.capacity() - 1)
 485             m_index = 0;
 486         else
 487             ++m_index;
 488     }
 489
 490     template<typename T, size_t inlineCapacity, typename Allocator>
 491     inline void DequeIteratorBase<T, inlineCapacity, Allocator>::decrement()
 492     {
 493         ASSERT(m_index != m_deque->m_start);
 494         ASSERT(m_deque->m_buffer.capacity());
 495         if (!m_index)
 496             m_index = m_deque->m_buffer.capacity() - 1;
 497         else
 498             --m_index;
 499     }
 500
 501     template<typename T, size_t inlineCapacity, typename Allocator>
 502     inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::after() const
 503     {
 504         ASSERT(m_index != m_deque->m_end);
 505         return &m_deque->m_buffer.buffer()[m_index];
 506     }
 507
 508     template<typename T, size_t inlineCapacity, typename Allocator>
 509     inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::before() const
 510     {
 511         ASSERT(m_index != m_deque->m_start);
 512         if (!m_index)
 513             return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
 514         return &m_deque->m_buffer.buffer()[m_index - 1];
 515     }
 516
 517     // This is only called if the allocator is a HeapAllocator. It is used when
 518     // visiting during a tracing GC.
 519     template<typename T, size_t inlineCapacity, typename Allocator>
 520     void Deque<T, inlineCapacity, Allocator>::trace(typename Allocator::Visitor* visitor)
 521     {
 522         ASSERT(Allocator::isGarbageCollected); // Garbage collector must be enabled.
 523         const T* bufferBegin = m_buffer.buffer();
 524         const T* end = bufferBegin + m_end;
 525         if (ShouldBeTraced<VectorTraits<T> >::value) {
 526             if (m_start <= m_end) {
 527                 for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != end; bufferEntry++)
 528                     Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
 529             } else {
 530                 for (const T* bufferEntry = bufferBegin; bufferEntry != end; bufferEntry++)
 531                     Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
 532                 const T* bufferEnd = m_buffer.buffer() + m_buffer.capacity();
 533                 for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != bufferEnd; bufferEntry++)
 534                     Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
 535             }
 536         }
 537         if (m_buffer.hasOutOfLineBuffer())
 538             Allocator::markNoTracing(visitor, m_buffer.buffer());
 539     }
 540
 541     template<typename T, size_t inlineCapacity, typename Allocator>
 542     inline void swap(Deque<T, inlineCapacity, Allocator>& a, Deque<T, inlineCapacity, Allocator>& b)
 543     {
 544         a.swap(b);
 545     }
 546
 547 #if !ENABLE(OILPAN)
 548     template<typename T, size_t N>
 549     struct NeedsTracing<Deque<T, N> > {
 550         static const bool value = false;
 551     };
 552 #endif
 553
 554 } // namespace WTF
 555
 556 using WTF::Deque;
 557
 558 #endif // WTF_Deque_h