15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/*
25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2009 Google Inc. All rights reserved.
45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *
55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without
65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions
75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * are met:
85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *
95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1.  Redistributions of source code must retain the above copyright
105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *     notice, this list of conditions and the following disclaimer.
115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2.  Redistributions in binary form must reproduce the above copyright
125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *     notice, this list of conditions and the following disclaimer in the
135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *     documentation and/or other materials provided with the distribution.
145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *     its contributors may be used to endorse or promote products derived
165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *     from this software without specific prior written permission.
175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *
185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */
295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef WTF_Deque_h
315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define WTF_Deque_h
325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// FIXME: Could move what Vector and Deque share into a separate file.
345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Deque doesn't actually use Vector.
355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
36591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/PassTraits.h"
37591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/Vector.h"
388abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)#include <iterator>
395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF {
41a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator> class DequeIteratorBase;
42a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator> class DequeIterator;
43a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator> class DequeConstIterator;
445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
45a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
46a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    class Deque : public VectorDestructorBase<Deque<T, inlineCapacity, Allocator>, T, (inlineCapacity > 0), Allocator::isGarbageCollected> {
47f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        WTF_USE_ALLOCATOR(Deque, Allocator);
485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    public:
49a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        typedef DequeIterator<T, inlineCapacity, Allocator> iterator;
50a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        typedef DequeConstIterator<T, inlineCapacity, Allocator> const_iterator;
515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef std::reverse_iterator<iterator> reverse_iterator;
525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef PassTraits<T> Pass;
545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef typename PassTraits<T>::PassType PassType;
555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        Deque();
57a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        Deque(const Deque<T, inlineCapacity, Allocator>&);
58a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
59a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        Deque<T, 0, Allocator>& operator=(const Deque&);
60a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch
61a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        void finalize();
62a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        void finalizeGarbageCollectedObject() { finalize(); }
635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
64a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        // We hard wire the inlineCapacity to zero here, due to crbug.com/360572
65a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        void swap(Deque<T, 0, Allocator>&);
665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        bool isEmpty() const { return m_start == m_end; }
695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        iterator begin() { return iterator(this, m_start); }
715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        iterator end() { return iterator(this, m_end); }
725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        const_iterator begin() const { return const_iterator(this, m_start); }
735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        const_iterator end() const { return const_iterator(this, m_end); }
745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        reverse_iterator rbegin() { return reverse_iterator(end()); }
755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        reverse_iterator rend() { return reverse_iterator(begin()); }
765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        PassType takeFirst();
825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        T& last() { ASSERT(m_start != m_end); return *(--end()); }
845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        const T& last() const { ASSERT(m_start != m_end); return *(--end()); }
851e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        PassType takeLast();
865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
877242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        T& at(size_t i)
887242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        {
897242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            RELEASE_ASSERT(i < size());
907242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            size_t right = m_buffer.capacity() - m_start;
917242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            return i < right ? m_buffer.buffer()[m_start + i] : m_buffer.buffer()[i - right];
927242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        }
937242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        const T& at(size_t i) const
947242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        {
957242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            RELEASE_ASSERT(i < size());
967242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            size_t right = m_buffer.capacity() - m_start;
977242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            return i < right ? m_buffer.buffer()[m_start + i] : m_buffer.buffer()[i - right];
987242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        }
997242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
1007242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        T& operator[](size_t i) { return at(i); }
1017242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        const T& operator[](size_t i) const { return at(i); }
1027242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        template<typename U> void append(const U&);
1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        template<typename U> void prepend(const U&);
1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        void removeFirst();
1061e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        void removeLast();
1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        void remove(iterator&);
1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        void remove(const_iterator&);
1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        void clear();
1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        template<typename Predicate>
1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        iterator findIf(Predicate&);
1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
115a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        void trace(typename Allocator::Visitor*);
116a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch
1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    private:
118a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        friend class DequeIteratorBase<T, inlineCapacity, Allocator>;
1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
120a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        typedef VectorBuffer<T, inlineCapacity, Allocator> Buffer;
1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef VectorTypeOperations<T> TypeOperations;
122a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        typedef DequeIteratorBase<T, inlineCapacity, Allocator> IteratorBase;
1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        void remove(size_t position);
1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        void destroyAll();
1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        void expandCapacityIfNeeded();
1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        void expandCapacity();
1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        Buffer m_buffer;
1309bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)        unsigned m_start;
1319bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)        unsigned m_end;
1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    };
1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
134a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    class DequeIteratorBase {
1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    protected:
1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        DequeIteratorBase();
138a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>*, size_t);
1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        DequeIteratorBase(const DequeIteratorBase&);
140a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        DequeIteratorBase<T, 0, Allocator>& operator=(const DequeIteratorBase<T, 0, Allocator>&);
1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        ~DequeIteratorBase();
1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        void assign(const DequeIteratorBase& other) { *this = other; }
1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        void increment();
1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        void decrement();
1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        T* before() const;
1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        T* after() const;
1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        bool isEqual(const DequeIteratorBase&) const;
1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    private:
154a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        Deque<T, inlineCapacity, Allocator>* m_deque;
1559bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)        unsigned m_index;
1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
157a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        friend class Deque<T, inlineCapacity, Allocator>;
1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    };
1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
160a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
161a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    class DequeIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    private:
163a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
164a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        typedef DequeIterator<T, inlineCapacity, Allocator> Iterator;
1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    public:
1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef ptrdiff_t difference_type;
1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef T value_type;
1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef T* pointer;
1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef T& reference;
1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef std::bidirectional_iterator_tag iterator_category;
1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
173a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        DequeIterator(Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        DequeIterator(const Iterator& other) : Base(other) { }
1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        T& operator*() const { return *Base::after(); }
1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        T* operator->() const { return Base::after(); }
1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        bool operator==(const Iterator& other) const { return Base::isEqual(other); }
1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        Iterator& operator++() { Base::increment(); return *this; }
1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        // postfix ++ intentionally omitted
1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        Iterator& operator--() { Base::decrement(); return *this; }
1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        // postfix -- intentionally omitted
1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    };
1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
190a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
191a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    private:
193a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
194a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        typedef DequeConstIterator<T, inlineCapacity, Allocator> Iterator;
195a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        typedef DequeIterator<T, inlineCapacity, Allocator> NonConstIterator;
1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    public:
1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef ptrdiff_t difference_type;
1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef T value_type;
2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef const T* pointer;
2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef const T& reference;
2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        typedef std::bidirectional_iterator_tag iterator_category;
2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
204a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        DequeConstIterator(const Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        DequeConstIterator(const Iterator& other) : Base(other) { }
2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        DequeConstIterator(const NonConstIterator& other) : Base(other) { }
2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        const T& operator*() const { return *Base::after(); }
2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        const T* operator->() const { return Base::after(); }
2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        bool operator==(const Iterator& other) const { return Base::isEqual(other); }
2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        Iterator& operator++() { Base::increment(); return *this; }
2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        // postfix ++ intentionally omitted
2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        Iterator& operator--() { Base::decrement(); return *this; }
2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        // postfix -- intentionally omitted
2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    };
2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
223a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
224a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline Deque<T, inlineCapacity, Allocator>::Deque()
2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        : m_start(0)
2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        , m_end(0)
2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
230a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
231a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline Deque<T, inlineCapacity, Allocator>::Deque(const Deque<T, inlineCapacity, Allocator>& other)
232f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)        : m_buffer(other.m_buffer.capacity())
233f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)        , m_start(other.m_start)
2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        , m_end(other.m_end)
2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        const T* otherBuffer = other.m_buffer.buffer();
2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        if (m_start <= m_end)
2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        else {
2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        }
2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
245a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
246a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline Deque<T, 0, Allocator>& Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other)
2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        Deque<T> copy(other);
2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        swap(copy);
2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return *this;
2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
253a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
254a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::destroyAll()
2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
256f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        if (m_start <= m_end) {
2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
258f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
259f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        } else {
2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
261f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            m_buffer.clearUnusedSlots(m_buffer.buffer(), m_buffer.buffer() + m_end);
2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
263f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        }
2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
267a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    // Off-GC-heap deques: Destructor should be called.
268a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    // On-GC-heap deques: Destructor should be called for inline buffers
269a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    // (if any) but destructor shouldn't be called for vector backing since
270a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    // it is managed by the traced GC heap.
271a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
272a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::finalize()
2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
274a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        if (!inlineCapacity && !m_buffer.buffer())
275a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch            return;
276a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        if (!isEmpty() && !(Allocator::isGarbageCollected && m_buffer.hasOutOfLineBuffer()))
277a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch            destroyAll();
278a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch
2799bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)        m_buffer.destruct();
2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
282a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
283a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
284a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::swap(Deque<T, 0, Allocator>& other)
2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        std::swap(m_start, other.m_start);
2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        std::swap(m_end, other.m_end);
28809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        m_buffer.swapVectorBuffer(other.m_buffer);
2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
291a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
292a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::clear()
2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        destroyAll();
2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        m_start = 0;
2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        m_end = 0;
297926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        m_buffer.deallocateBuffer(m_buffer.buffer());
2989bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)        m_buffer.resetBufferPointer();
2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
301a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    template<typename Predicate>
303a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline DequeIterator<T, inlineCapacity, Allocator> Deque<T, inlineCapacity, Allocator>::findIf(Predicate& predicate)
3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        iterator end_iterator = end();
3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        for (iterator it = begin(); it != end_iterator; ++it) {
3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            if (predicate(*it))
3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)                return it;
3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        }
3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return end_iterator;
3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
3125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
313a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
314a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::expandCapacityIfNeeded()
3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        if (m_start) {
3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            if (m_end + 1 != m_start)
3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)                return;
3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        } else if (m_end) {
3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            if (m_end != m_buffer.capacity() - 1)
3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)                return;
3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        } else if (m_buffer.capacity())
3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            return;
3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        expandCapacity();
3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
328a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
329a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    void Deque<T, inlineCapacity, Allocator>::expandCapacity()
3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        size_t oldCapacity = m_buffer.capacity();
3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        T* oldBuffer = m_buffer.buffer();
333926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        if (m_start <= m_end)
3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        else {
3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
338926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            m_start = newStart;
3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        }
3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        m_buffer.deallocateBuffer(oldBuffer);
3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
345a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
346a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeFirst()
3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        T oldFirst = Pass::transfer(first());
3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        removeFirst();
3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return Pass::transfer(oldFirst);
3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
353a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
354a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeLast()
3551e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)    {
3561e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        T oldLast = Pass::transfer(last());
3571e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        removeLast();
3581e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        return Pass::transfer(oldLast);
3591e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)    }
3601e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)
361a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
362a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::append(const U& value)
3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        expandCapacityIfNeeded();
3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        new (NotNull, &m_buffer.buffer()[m_end]) T(value);
3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        if (m_end == m_buffer.capacity() - 1)
3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            m_end = 0;
3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        else
3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            ++m_end;
3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
372a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
373a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::prepend(const U& value)
3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        expandCapacityIfNeeded();
3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        if (!m_start)
3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            m_start = m_buffer.capacity() - 1;
3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        else
3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            --m_start;
3805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        new (NotNull, &m_buffer.buffer()[m_start]) T(value);
3815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
3825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
383a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
384a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::removeFirst()
3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        ASSERT(!isEmpty());
3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
388f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        if (m_start == m_buffer.capacity() - 1)
3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            m_start = 0;
3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        else
3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            ++m_start;
3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
395a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
396a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::removeLast()
3971e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)    {
3981e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        ASSERT(!isEmpty());
3991e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        if (!m_end)
4001e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)            m_end = m_buffer.capacity() - 1;
4011e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        else
4021e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)            --m_end;
4031e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        TypeOperations::destruct(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
404f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
4051e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)    }
4061e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)
407a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
408a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::remove(iterator& it)
4095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
4105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        remove(it.m_index);
4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
413a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
414a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::remove(const_iterator& it)
4155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
4165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        remove(it.m_index);
4175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
4185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
419a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
420a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void Deque<T, inlineCapacity, Allocator>::remove(size_t position)
4215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
4225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        if (position == m_end)
4235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            return;
4245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        T* buffer = m_buffer.buffer();
4265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
4275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
4285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
4295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        if (position >= m_start) {
4305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
431f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            m_buffer.clearUnusedSlots(buffer + m_start, buffer + m_start + 1);
4325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            m_start = (m_start + 1) % m_buffer.capacity();
4335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        } else {
4345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
435f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            m_buffer.clearUnusedSlots(buffer + m_end - 1, buffer + m_end);
4365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
4375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        }
4385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
4395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
440a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
441a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase()
4425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        : m_deque(0)
4435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
4445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
4455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
446a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
447a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>* deque, size_t index)
448a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        : m_deque(const_cast<Deque<T, inlineCapacity, Allocator>*>(deque))
4495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        , m_index(index)
4505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
4515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
4525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
453a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
454a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const DequeIteratorBase& other)
4555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        : m_deque(other.m_deque)
4565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        , m_index(other.m_index)
4575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
4585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
4595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
460a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
461a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline DequeIteratorBase<T, 0, Allocator>& DequeIteratorBase<T, inlineCapacity, Allocator>::operator=(const DequeIteratorBase<T, 0, Allocator>& other)
4625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
4635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        m_deque = other.m_deque;
4645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        m_index = other.m_index;
4655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return *this;
4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
4675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
468a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
469a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline DequeIteratorBase<T, inlineCapacity, Allocator>::~DequeIteratorBase()
4705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
4725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
473a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
474a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline bool DequeIteratorBase<T, inlineCapacity, Allocator>::isEqual(const DequeIteratorBase& other) const
4755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return m_index == other.m_index;
4775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
4785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
479a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
480a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void DequeIteratorBase<T, inlineCapacity, Allocator>::increment()
4815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
4825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        ASSERT(m_index != m_deque->m_end);
4835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        ASSERT(m_deque->m_buffer.capacity());
4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        if (m_index == m_deque->m_buffer.capacity() - 1)
4855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            m_index = 0;
4865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        else
4875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            ++m_index;
4885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
4895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
490a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
491a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline void DequeIteratorBase<T, inlineCapacity, Allocator>::decrement()
4925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
4935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        ASSERT(m_index != m_deque->m_start);
4945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        ASSERT(m_deque->m_buffer.capacity());
4955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        if (!m_index)
4965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            m_index = m_deque->m_buffer.capacity() - 1;
4975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        else
4985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            --m_index;
4995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
5005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
501a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
502a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::after() const
5035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
5045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        ASSERT(m_index != m_deque->m_end);
5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return &m_deque->m_buffer.buffer()[m_index];
5065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
5075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
508a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
509a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::before() const
5105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
5115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        ASSERT(m_index != m_deque->m_start);
5125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        if (!m_index)
5135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
5145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return &m_deque->m_buffer.buffer()[m_index - 1];
5155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
5165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
517a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    // This is only called if the allocator is a HeapAllocator. It is used when
518a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    // visiting during a tracing GC.
519a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    template<typename T, size_t inlineCapacity, typename Allocator>
520a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    void Deque<T, inlineCapacity, Allocator>::trace(typename Allocator::Visitor* visitor)
521a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    {
522197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        ASSERT(Allocator::isGarbageCollected); // Garbage collector must be enabled.
523a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        const T* bufferBegin = m_buffer.buffer();
524a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        const T* end = bufferBegin + m_end;
525a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        if (ShouldBeTraced<VectorTraits<T> >::value) {
526a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch            if (m_start <= m_end) {
527a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch                for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != end; bufferEntry++)
528a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch                    Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
529a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch            } else {
530a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch                for (const T* bufferEntry = bufferBegin; bufferEntry != end; bufferEntry++)
531a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch                    Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
532a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch                const T* bufferEnd = m_buffer.buffer() + m_buffer.capacity();
533a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch                for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != bufferEnd; bufferEntry++)
534a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch                    Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
535a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch            }
536a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        }
537a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        if (m_buffer.hasOutOfLineBuffer())
538a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch            Allocator::markNoTracing(visitor, m_buffer.buffer());
539a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    }
540a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch
5417242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    template<typename T, size_t inlineCapacity, typename Allocator>
5427242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    inline void swap(Deque<T, inlineCapacity, Allocator>& a, Deque<T, inlineCapacity, Allocator>& b)
5437242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    {
5447242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        a.swap(b);
5457242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
5467242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
547197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if !ENABLE(OILPAN)
548197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    template<typename T, size_t N>
549197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    struct NeedsTracing<Deque<T, N> > {
550197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        static const bool value = false;
551197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    };
552197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif
553197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
5545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WTF
5555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
5565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using WTF::Deque;
5575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
5585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif // WTF_Deque_h
559