Deque: Add HeapDeque and prevent buggy use of swap and operator=

Source/wtf/Deque.h

 /*
  * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
  * Copyright (C) 2009 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  *
  * 1.  Redistributions of source code must retain the above copyright
  *     notice, this list of conditions and the following disclaimer.
@@ skipping 20 matching lines @@
 #define WTF_Deque_h
 
 // FIXME: Could move what Vector and Deque share into a separate file.
 // Deque doesn't actually use Vector.
 
 #include "wtf/PassTraits.h"
 #include "wtf/Vector.h"
 #include <iterator>
 
 namespace WTF {
+    template<typename T, size_t inlineCapacity, typename Allocator> class DequeIteratorBase;
+    template<typename T, size_t inlineCapacity, typename Allocator> class DequeIterator;
+    template<typename T, size_t inlineCapacity, typename Allocator> class DequeConstIterator;
 
-    template<typename T, size_t inlineCapacity> class DequeIteratorBase;
-    template<typename T, size_t inlineCapacity> class DequeIterator;
-    template<typename T, size_t inlineCapacity> class DequeConstIterator;
-
-    template<typename T, size_t inlineCapacity = 0>
-    class Deque {
-        WTF_MAKE_FAST_ALLOCATED;
+    template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
+    class Deque : public VectorDestructorBase<Deque<T, inlineCapacity, Allocator>, T, (inlineCapacity > 0), Allocator::isGarbageCollected> {
     public:
-        typedef DequeIterator<T, inlineCapacity> iterator;
-        typedef DequeConstIterator<T, inlineCapacity> const_iterator;
+        typedef DequeIterator<T, inlineCapacity, Allocator> iterator;
+        typedef DequeConstIterator<T, inlineCapacity, Allocator> const_iterator;
         typedef std::reverse_iterator<iterator> reverse_iterator;
         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
         typedef PassTraits<T> Pass;
         typedef typename PassTraits<T>::PassType PassType;
 
+        void* operator new(size_t size)
+        {

[Mikhail, 2014/04/08 12:11:30]

Off topic: the same allocation operators are copy-pasted in several container
classes already. Looks like it deserves having a macro, similar to
'WTF_MAKE_FAST_ALLOCATED'

+            return Allocator::template malloc<void*, Deque>(size);
+        }
+        void operator delete(void* p) { Allocator::free(p); }
+        void* operator new[](size_t size) { return Allocator::template newArray<Vector>(size); }
+        void operator delete[](void* p) { Allocator::deleteArray(p); }
+        void* operator new(size_t, NotNullTag, void* location)
+        {

[Mikhail, 2014/04/08 12:11:30]

is this compatible with GC? shouldn't
COMPILE_ASSERT(!Allocator::isGarbageCollected) be added?

[Erik Corry, 2014/04/08 12:14:36]

We do allow heap collections to be off heap, but the backing is always on heap. 
So heap collections can be on the stack or inside other objects, either other
heap collections or other objects.  Therefore it is possible to placement new
them. If you do that and then put a pointer to them in a Member you are busted.

+            ASSERT(location);
+            return location;
+        }
+
         Deque();
-        Deque(const Deque<T, inlineCapacity>&);
-        Deque& operator=(const Deque<T, inlineCapacity>&);
-        ~Deque();
+        Deque(const Deque<T, inlineCapacity, Allocator>&);
+        // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
+        Deque<T, 0, Allocator>& operator=(const Deque&);
 
-        void swap(Deque<T, inlineCapacity>&);
+        void finalize();
+        void finalizeGarbageCollectedObject() { finalize(); }
+
+        // We hard wire the inlineCapacity to zero here, due to crbug.com/360572
+        void swap(Deque<T, 0, Allocator>&);
 
         size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
         bool isEmpty() const { return m_start == m_end; }
 
         iterator begin() { return iterator(this, m_start); }
         iterator end() { return iterator(this, m_end); }
         const_iterator begin() const { return const_iterator(this, m_start); }
         const_iterator end() const { return const_iterator(this, m_end); }
         reverse_iterator rbegin() { return reverse_iterator(end()); }
         reverse_iterator rend() { return reverse_iterator(begin()); }
@@ skipping 13 matching lines @@
         void removeFirst();
         void removeLast();
         void remove(iterator&);
         void remove(const_iterator&);
 
         void clear();
 
         template<typename Predicate>
         iterator findIf(Predicate&);
 
+        void trace(typename Allocator::Visitor*);
+
     private:
-        friend class DequeIteratorBase<T, inlineCapacity>;
+        friend class DequeIteratorBase<T, inlineCapacity, Allocator>;
 
-        typedef VectorBuffer<T, inlineCapacity> Buffer;
+        typedef VectorBuffer<T, inlineCapacity, Allocator> Buffer;
         typedef VectorTypeOperations<T> TypeOperations;
-        typedef DequeIteratorBase<T, inlineCapacity> IteratorBase;
+        typedef DequeIteratorBase<T, inlineCapacity, Allocator> IteratorBase;
 
         void remove(size_t position);
         void destroyAll();
         void expandCapacityIfNeeded();
         void expandCapacity();
 
         Buffer m_buffer;
         unsigned m_start;
         unsigned m_end;
     };
 
-    template<typename T, size_t inlineCapacity = 0>
+    template<typename T, size_t inlineCapacity, typename Allocator>
     class DequeIteratorBase {
     protected:
         DequeIteratorBase();
-        DequeIteratorBase(const Deque<T, inlineCapacity>*, size_t);
+        DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>*, size_t);
         DequeIteratorBase(const DequeIteratorBase&);
-        DequeIteratorBase& operator=(const DequeIteratorBase&);
+        DequeIteratorBase<T, 0, Allocator>& operator=(const DequeIteratorBase<T, 0, Allocator>&);
         ~DequeIteratorBase();
 
         void assign(const DequeIteratorBase& other) { *this = other; }
 
         void increment();
         void decrement();
 
         T* before() const;
         T* after() const;
 
         bool isEqual(const DequeIteratorBase&) const;
 
     private:
-        Deque<T, inlineCapacity>* m_deque;
+        Deque<T, inlineCapacity, Allocator>* m_deque;
         unsigned m_index;
 
-        friend class Deque<T, inlineCapacity>;
+        friend class Deque<T, inlineCapacity, Allocator>;
     };
 
-    template<typename T, size_t inlineCapacity = 0>
-    class DequeIterator : public DequeIteratorBase<T, inlineCapacity> {
+    template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
+    class DequeIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
     private:
-        typedef DequeIteratorBase<T, inlineCapacity> Base;
-        typedef DequeIterator<T, inlineCapacity> Iterator;
+        typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
+        typedef DequeIterator<T, inlineCapacity, Allocator> Iterator;
 
     public:
         typedef ptrdiff_t difference_type;
         typedef T value_type;
         typedef T* pointer;
         typedef T& reference;
         typedef std::bidirectional_iterator_tag iterator_category;
 
-        DequeIterator(Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { }
+        DequeIterator(Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
 
         DequeIterator(const Iterator& other) : Base(other) { }
         DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
 
         T& operator*() const { return *Base::after(); }
         T* operator->() const { return Base::after(); }
 
         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 
         Iterator& operator++() { Base::increment(); return *this; }
         // postfix ++ intentionally omitted
         Iterator& operator--() { Base::decrement(); return *this; }
         // postfix -- intentionally omitted
     };
 
-    template<typename T, size_t inlineCapacity = 0>
-    class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity> {
+    template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
+    class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
     private:
-        typedef DequeIteratorBase<T, inlineCapacity> Base;
-        typedef DequeConstIterator<T, inlineCapacity> Iterator;
-        typedef DequeIterator<T, inlineCapacity> NonConstIterator;
+        typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
+        typedef DequeConstIterator<T, inlineCapacity, Allocator> Iterator;
+        typedef DequeIterator<T, inlineCapacity, Allocator> NonConstIterator;
 
     public:
         typedef ptrdiff_t difference_type;
         typedef T value_type;
         typedef const T* pointer;
         typedef const T& reference;
         typedef std::bidirectional_iterator_tag iterator_category;
 
-        DequeConstIterator(const Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { }
+        DequeConstIterator(const Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
 
         DequeConstIterator(const Iterator& other) : Base(other) { }
         DequeConstIterator(const NonConstIterator& other) : Base(other) { }
         DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
         DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
 
         const T& operator*() const { return *Base::after(); }
         const T* operator->() const { return Base::after(); }
 
         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 
         Iterator& operator++() { Base::increment(); return *this; }
         // postfix ++ intentionally omitted
         Iterator& operator--() { Base::decrement(); return *this; }
         // postfix -- intentionally omitted
     };
 
-    template<typename T, size_t inlineCapacity>
-    inline Deque<T, inlineCapacity>::Deque()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline Deque<T, inlineCapacity, Allocator>::Deque()
         : m_start(0)
         , m_end(0)
     {
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline Deque<T, inlineCapacity>::Deque(const Deque<T, inlineCapacity>& other)
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline Deque<T, inlineCapacity, Allocator>::Deque(const Deque<T, inlineCapacity, Allocator>& other)
         : m_buffer(other.m_buffer.capacity())
         , m_start(other.m_start)
         , m_end(other.m_end)
     {
         const T* otherBuffer = other.m_buffer.buffer();
         if (m_start <= m_end)
             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
         else {
             TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
         }
     }
 
-    template<typename T, size_t inlineCapacity>
-    void deleteAllValues(const Deque<T, inlineCapacity>& collection)
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    void deleteAllValues(const Deque<T, inlineCapacity, Allocator>& collection)
     {
-        typedef typename Deque<T, inlineCapacity>::const_iterator iterator;
+        typedef typename Deque<T, inlineCapacity, Allocator>::const_iterator iterator;
         iterator end = collection.end();
         for (iterator it = collection.begin(); it != end; ++it)
             delete *it;
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline Deque<T, inlineCapacity>& Deque<T, inlineCapacity>::operator=(const Deque<T, inlineCapacity>& other)
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline Deque<T, 0, Allocator>& Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other)
     {
-        // FIXME: This is inefficient if we're using an inline buffer and T is
-        // expensive to copy since it will copy the buffer twice instead of once.
         Deque<T> copy(other);
         swap(copy);
         return *this;
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline void Deque<T, inlineCapacity>::destroyAll()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void Deque<T, inlineCapacity, Allocator>::destroyAll()
     {
         if (m_start <= m_end)
             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
         else {
             TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
         }
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline Deque<T, inlineCapacity>::~Deque()
+    // Off-GC-heap deques: Destructor should be called.
+    // On-GC-heap deques: Destructor should be called for inline buffers
+    // (if any) but destructor shouldn't be called for vector backing since
+    // it is managed by the traced GC heap.
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void Deque<T, inlineCapacity, Allocator>::finalize()
     {
-        destroyAll();
+        if (!inlineCapacity && !m_buffer.buffer())
+            return;
+        if (!isEmpty() && !(Allocator::isGarbageCollected && m_buffer.hasOutOfLineBuffer()))
+            destroyAll();
+
         m_buffer.destruct();
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline void Deque<T, inlineCapacity>::swap(Deque<T, inlineCapacity>& other)
+    // FIXME: Doesn't work if there is an inline buffer, so for now we only
+    // define the version without.
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void Deque<T, inlineCapacity, Allocator>::swap(Deque<T, 0, Allocator>& other)
     {
         std::swap(m_start, other.m_start);
         std::swap(m_end, other.m_end);
         m_buffer.swapVectorBuffer(other.m_buffer);
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline void Deque<T, inlineCapacity>::clear()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void Deque<T, inlineCapacity, Allocator>::clear()
     {
         destroyAll();
         m_start = 0;
         m_end = 0;
         m_buffer.deallocateBuffer(m_buffer.buffer());
         m_buffer.resetBufferPointer();
     }
 
-    template<typename T, size_t inlineCapacity>
+    template<typename T, size_t inlineCapacity, typename Allocator>
     template<typename Predicate>
-    inline DequeIterator<T, inlineCapacity> Deque<T, inlineCapacity>::findIf(Predicate& predicate)
+    inline DequeIterator<T, inlineCapacity, Allocator> Deque<T, inlineCapacity, Allocator>::findIf(Predicate& predicate)
     {
         iterator end_iterator = end();
         for (iterator it = begin(); it != end_iterator; ++it) {
             if (predicate(*it))
                 return it;
         }
         return end_iterator;
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline void Deque<T, inlineCapacity>::expandCapacityIfNeeded()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void Deque<T, inlineCapacity, Allocator>::expandCapacityIfNeeded()
     {
         if (m_start) {
             if (m_end + 1 != m_start)
                 return;
         } else if (m_end) {
             if (m_end != m_buffer.capacity() - 1)
                 return;
         } else if (m_buffer.capacity())
             return;
 
         expandCapacity();
     }
 
-    template<typename T, size_t inlineCapacity>
-    void Deque<T, inlineCapacity>::expandCapacity()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    void Deque<T, inlineCapacity, Allocator>::expandCapacity()
     {
         size_t oldCapacity = m_buffer.capacity();
         T* oldBuffer = m_buffer.buffer();
         m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
         if (m_start <= m_end)
             TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
         else {
             TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
             size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
             TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
             m_start = newStart;
         }
         m_buffer.deallocateBuffer(oldBuffer);
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline typename Deque<T, inlineCapacity>::PassType Deque<T, inlineCapacity>::takeFirst()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeFirst()
     {
         T oldFirst = Pass::transfer(first());
         removeFirst();
         return Pass::transfer(oldFirst);
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline typename Deque<T, inlineCapacity>::PassType Deque<T, inlineCapacity>::takeLast()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeLast()
     {
         T oldLast = Pass::transfer(last());
         removeLast();
         return Pass::transfer(oldLast);
     }
 
-    template<typename T, size_t inlineCapacity> template<typename U>
-    inline void Deque<T, inlineCapacity>::append(const U& value)
+    template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
+    inline void Deque<T, inlineCapacity, Allocator>::append(const U& value)
     {
         expandCapacityIfNeeded();
         new (NotNull, &m_buffer.buffer()[m_end]) T(value);
         if (m_end == m_buffer.capacity() - 1)
             m_end = 0;
         else
             ++m_end;
     }
 
-    template<typename T, size_t inlineCapacity> template<typename U>
-    inline void Deque<T, inlineCapacity>::prepend(const U& value)
+    template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
+    inline void Deque<T, inlineCapacity, Allocator>::prepend(const U& value)
     {
         expandCapacityIfNeeded();
         if (!m_start)
             m_start = m_buffer.capacity() - 1;
         else
             --m_start;
         new (NotNull, &m_buffer.buffer()[m_start]) T(value);
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline void Deque<T, inlineCapacity>::removeFirst()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void Deque<T, inlineCapacity, Allocator>::removeFirst()
     {
         ASSERT(!isEmpty());
         TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
         if (m_start == m_buffer.capacity() - 1)
             m_start = 0;
         else
             ++m_start;
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline void Deque<T, inlineCapacity>::removeLast()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void Deque<T, inlineCapacity, Allocator>::removeLast()
     {
         ASSERT(!isEmpty());
         if (!m_end)
             m_end = m_buffer.capacity() - 1;
         else
             --m_end;
         TypeOperations::destruct(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline void Deque<T, inlineCapacity>::remove(iterator& it)
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void Deque<T, inlineCapacity, Allocator>::remove(iterator& it)
     {
         remove(it.m_index);
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline void Deque<T, inlineCapacity>::remove(const_iterator& it)
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void Deque<T, inlineCapacity, Allocator>::remove(const_iterator& it)
     {
         remove(it.m_index);
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline void Deque<T, inlineCapacity>::remove(size_t position)
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void Deque<T, inlineCapacity, Allocator>::remove(size_t position)
     {
         if (position == m_end)
             return;
 
         T* buffer = m_buffer.buffer();
         TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
 
         // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
         if (position >= m_start) {
             TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
             m_start = (m_start + 1) % m_buffer.capacity();
         } else {
             TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
             m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
         }
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase()
         : m_deque(0)
     {
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const Deque<T, inlineCapacity>* deque, size_t index)
-        : m_deque(const_cast<Deque<T, inlineCapacity>*>(deque))
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>* deque, size_t index)
+        : m_deque(const_cast<Deque<T, inlineCapacity, Allocator>*>(deque))
         , m_index(index)
     {
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const DequeIteratorBase& other)
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const DequeIteratorBase& other)
         : m_deque(other.m_deque)
         , m_index(other.m_index)
     {
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline DequeIteratorBase<T, inlineCapacity>& DequeIteratorBase<T, inlineCapacity>::operator=(const DequeIteratorBase& other)
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline DequeIteratorBase<T, 0, Allocator>& DequeIteratorBase<T, inlineCapacity, Allocator>::operator=(const DequeIteratorBase<T, 0, Allocator>& other)
     {
         m_deque = other.m_deque;
         m_index = other.m_index;
         return *this;
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline DequeIteratorBase<T, inlineCapacity>::~DequeIteratorBase()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline DequeIteratorBase<T, inlineCapacity, Allocator>::~DequeIteratorBase()
     {
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline bool DequeIteratorBase<T, inlineCapacity>::isEqual(const DequeIteratorBase& other) const
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline bool DequeIteratorBase<T, inlineCapacity, Allocator>::isEqual(const DequeIteratorBase& other) const
     {
         return m_index == other.m_index;
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline void DequeIteratorBase<T, inlineCapacity>::increment()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void DequeIteratorBase<T, inlineCapacity, Allocator>::increment()
     {
         ASSERT(m_index != m_deque->m_end);
         ASSERT(m_deque->m_buffer.capacity());
         if (m_index == m_deque->m_buffer.capacity() - 1)
             m_index = 0;
         else
             ++m_index;
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline void DequeIteratorBase<T, inlineCapacity>::decrement()
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline void DequeIteratorBase<T, inlineCapacity, Allocator>::decrement()
     {
         ASSERT(m_index != m_deque->m_start);
         ASSERT(m_deque->m_buffer.capacity());
         if (!m_index)
             m_index = m_deque->m_buffer.capacity() - 1;
         else
             --m_index;
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline T* DequeIteratorBase<T, inlineCapacity>::after() const
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::after() const
     {
         ASSERT(m_index != m_deque->m_end);
         return &m_deque->m_buffer.buffer()[m_index];
     }
 
-    template<typename T, size_t inlineCapacity>
-    inline T* DequeIteratorBase<T, inlineCapacity>::before() const
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::before() const
     {
         ASSERT(m_index != m_deque->m_start);
         if (!m_index)
             return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
         return &m_deque->m_buffer.buffer()[m_index - 1];
     }
 
+    // This is only called if the allocator is a HeapAllocator. It is used when
+    // visiting during a tracing GC.
+    template<typename T, size_t inlineCapacity, typename Allocator>
+    void Deque<T, inlineCapacity, Allocator>::trace(typename Allocator::Visitor* visitor)
+    {
+        COMPILE_ASSERT(Allocator::isGarbageCollected, Garbage_collector_must_be_enabled);
+        const T* bufferBegin = m_buffer.buffer();
+        const T* end = bufferBegin + m_end;
+        if (ShouldBeTraced<VectorTraits<T> >::value) {
+            if (m_start <= m_end) {
+                for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != end; bufferEntry++)
+                    Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
+            } else {
+                for (const T* bufferEntry = bufferBegin; bufferEntry != end; bufferEntry++)
+                    Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
+                const T* bufferEnd = m_buffer.buffer() + m_buffer.capacity();
+                for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != bufferEnd; bufferEntry++)
+                    Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
+            }
+        }
+        if (m_buffer.hasOutOfLineBuffer())
+            Allocator::markNoTracing(visitor, m_buffer.buffer());
+    }
+
 } // namespace WTF
 
 using WTF::Deque;
 
 #endif // WTF_Deque_h