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)
+        {
+            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)
+        {
+            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, due to crbug.com/360572
+    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