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