1/*
2 * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
3 * Copyright (C) 2009 Google Inc. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1.  Redistributions of source code must retain the above copyright
10 *     notice, this list of conditions and the following disclaimer.
11 * 2.  Redistributions in binary form must reproduce the above copyright
12 *     notice, this list of conditions and the following disclaimer in the
13 *     documentation and/or other materials provided with the distribution.
14 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
15 *     its contributors may be used to endorse or promote products derived
16 *     from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30#ifndef WTF_Deque_h
31#define WTF_Deque_h
32
33// FIXME: Could move what Vector and Deque share into a separate file.
34// Deque doesn't actually use Vector.
35
36#include "wtf/PassTraits.h"
37#include "wtf/Vector.h"
38#include <iterator>
39
40namespace WTF {
41    template<typename T, size_t inlineCapacity, typename Allocator> class DequeIteratorBase;
42    template<typename T, size_t inlineCapacity, typename Allocator> class DequeIterator;
43    template<typename T, size_t inlineCapacity, typename Allocator> class DequeConstIterator;
44
45    template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
46    class Deque : public VectorDestructorBase<Deque<T, inlineCapacity, Allocator>, T, (inlineCapacity > 0), Allocator::isGarbageCollected> {
47        WTF_USE_ALLOCATOR(Deque, Allocator);
48    public:
49        typedef DequeIterator<T, inlineCapacity, Allocator> iterator;
50        typedef DequeConstIterator<T, inlineCapacity, Allocator> const_iterator;
51        typedef std::reverse_iterator<iterator> reverse_iterator;
52        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
53        typedef PassTraits<T> Pass;
54        typedef typename PassTraits<T>::PassType PassType;
55
56        Deque();
57        Deque(const Deque<T, inlineCapacity, Allocator>&);
58        // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
59        Deque<T, 0, Allocator>& operator=(const Deque&);
60
61        void finalize();
62        void finalizeGarbageCollectedObject() { finalize(); }
63
64        // We hard wire the inlineCapacity to zero here, due to crbug.com/360572
65        void swap(Deque<T, 0, Allocator>&);
66
67        size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
68        bool isEmpty() const { return m_start == m_end; }
69
70        iterator begin() { return iterator(this, m_start); }
71        iterator end() { return iterator(this, m_end); }
72        const_iterator begin() const { return const_iterator(this, m_start); }
73        const_iterator end() const { return const_iterator(this, m_end); }
74        reverse_iterator rbegin() { return reverse_iterator(end()); }
75        reverse_iterator rend() { return reverse_iterator(begin()); }
76        const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
77        const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
78
79        T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
80        const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
81        PassType takeFirst();
82
83        T& last() { ASSERT(m_start != m_end); return *(--end()); }
84        const T& last() const { ASSERT(m_start != m_end); return *(--end()); }
85        PassType takeLast();
86
87        T& at(size_t i)
88        {
89            RELEASE_ASSERT(i < size());
90            size_t right = m_buffer.capacity() - m_start;
91            return i < right ? m_buffer.buffer()[m_start + i] : m_buffer.buffer()[i - right];
92        }
93        const T& at(size_t i) const
94        {
95            RELEASE_ASSERT(i < size());
96            size_t right = m_buffer.capacity() - m_start;
97            return i < right ? m_buffer.buffer()[m_start + i] : m_buffer.buffer()[i - right];
98        }
99
100        T& operator[](size_t i) { return at(i); }
101        const T& operator[](size_t i) const { return at(i); }
102
103        template<typename U> void append(const U&);
104        template<typename U> void prepend(const U&);
105        void removeFirst();
106        void removeLast();
107        void remove(iterator&);
108        void remove(const_iterator&);
109
110        void clear();
111
112        template<typename Predicate>
113        iterator findIf(Predicate&);
114
115        void trace(typename Allocator::Visitor*);
116
117    private:
118        friend class DequeIteratorBase<T, inlineCapacity, Allocator>;
119
120        typedef VectorBuffer<T, inlineCapacity, Allocator> Buffer;
121        typedef VectorTypeOperations<T> TypeOperations;
122        typedef DequeIteratorBase<T, inlineCapacity, Allocator> IteratorBase;
123
124        void remove(size_t position);
125        void destroyAll();
126        void expandCapacityIfNeeded();
127        void expandCapacity();
128
129        Buffer m_buffer;
130        unsigned m_start;
131        unsigned m_end;
132    };
133
134    template<typename T, size_t inlineCapacity, typename Allocator>
135    class DequeIteratorBase {
136    protected:
137        DequeIteratorBase();
138        DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>*, size_t);
139        DequeIteratorBase(const DequeIteratorBase&);
140        DequeIteratorBase<T, 0, Allocator>& operator=(const DequeIteratorBase<T, 0, Allocator>&);
141        ~DequeIteratorBase();
142
143        void assign(const DequeIteratorBase& other) { *this = other; }
144
145        void increment();
146        void decrement();
147
148        T* before() const;
149        T* after() const;
150
151        bool isEqual(const DequeIteratorBase&) const;
152
153    private:
154        Deque<T, inlineCapacity, Allocator>* m_deque;
155        unsigned m_index;
156
157        friend class Deque<T, inlineCapacity, Allocator>;
158    };
159
160    template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
161    class DequeIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
162    private:
163        typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
164        typedef DequeIterator<T, inlineCapacity, Allocator> Iterator;
165
166    public:
167        typedef ptrdiff_t difference_type;
168        typedef T value_type;
169        typedef T* pointer;
170        typedef T& reference;
171        typedef std::bidirectional_iterator_tag iterator_category;
172
173        DequeIterator(Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
174
175        DequeIterator(const Iterator& other) : Base(other) { }
176        DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
177
178        T& operator*() const { return *Base::after(); }
179        T* operator->() const { return Base::after(); }
180
181        bool operator==(const Iterator& other) const { return Base::isEqual(other); }
182        bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
183
184        Iterator& operator++() { Base::increment(); return *this; }
185        // postfix ++ intentionally omitted
186        Iterator& operator--() { Base::decrement(); return *this; }
187        // postfix -- intentionally omitted
188    };
189
190    template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
191    class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
192    private:
193        typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
194        typedef DequeConstIterator<T, inlineCapacity, Allocator> Iterator;
195        typedef DequeIterator<T, inlineCapacity, Allocator> NonConstIterator;
196
197    public:
198        typedef ptrdiff_t difference_type;
199        typedef T value_type;
200        typedef const T* pointer;
201        typedef const T& reference;
202        typedef std::bidirectional_iterator_tag iterator_category;
203
204        DequeConstIterator(const Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
205
206        DequeConstIterator(const Iterator& other) : Base(other) { }
207        DequeConstIterator(const NonConstIterator& other) : Base(other) { }
208        DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
209        DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
210
211        const T& operator*() const { return *Base::after(); }
212        const T* operator->() const { return Base::after(); }
213
214        bool operator==(const Iterator& other) const { return Base::isEqual(other); }
215        bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
216
217        Iterator& operator++() { Base::increment(); return *this; }
218        // postfix ++ intentionally omitted
219        Iterator& operator--() { Base::decrement(); return *this; }
220        // postfix -- intentionally omitted
221    };
222
223    template<typename T, size_t inlineCapacity, typename Allocator>
224    inline Deque<T, inlineCapacity, Allocator>::Deque()
225        : m_start(0)
226        , m_end(0)
227    {
228    }
229
230    template<typename T, size_t inlineCapacity, typename Allocator>
231    inline Deque<T, inlineCapacity, Allocator>::Deque(const Deque<T, inlineCapacity, Allocator>& other)
232        : m_buffer(other.m_buffer.capacity())
233        , m_start(other.m_start)
234        , m_end(other.m_end)
235    {
236        const T* otherBuffer = other.m_buffer.buffer();
237        if (m_start <= m_end)
238            TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
239        else {
240            TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
241            TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
242        }
243    }
244
245    template<typename T, size_t inlineCapacity, typename Allocator>
246    inline Deque<T, 0, Allocator>& Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other)
247    {
248        Deque<T> copy(other);
249        swap(copy);
250        return *this;
251    }
252
253    template<typename T, size_t inlineCapacity, typename Allocator>
254    inline void Deque<T, inlineCapacity, Allocator>::destroyAll()
255    {
256        if (m_start <= m_end) {
257            TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
258            m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
259        } else {
260            TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
261            m_buffer.clearUnusedSlots(m_buffer.buffer(), m_buffer.buffer() + m_end);
262            TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
263            m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
264        }
265    }
266
267    // Off-GC-heap deques: Destructor should be called.
268    // On-GC-heap deques: Destructor should be called for inline buffers
269    // (if any) but destructor shouldn't be called for vector backing since
270    // it is managed by the traced GC heap.
271    template<typename T, size_t inlineCapacity, typename Allocator>
272    inline void Deque<T, inlineCapacity, Allocator>::finalize()
273    {
274        if (!inlineCapacity && !m_buffer.buffer())
275            return;
276        if (!isEmpty() && !(Allocator::isGarbageCollected && m_buffer.hasOutOfLineBuffer()))
277            destroyAll();
278
279        m_buffer.destruct();
280    }
281
282    // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
283    template<typename T, size_t inlineCapacity, typename Allocator>
284    inline void Deque<T, inlineCapacity, Allocator>::swap(Deque<T, 0, Allocator>& other)
285    {
286        std::swap(m_start, other.m_start);
287        std::swap(m_end, other.m_end);
288        m_buffer.swapVectorBuffer(other.m_buffer);
289    }
290
291    template<typename T, size_t inlineCapacity, typename Allocator>
292    inline void Deque<T, inlineCapacity, Allocator>::clear()
293    {
294        destroyAll();
295        m_start = 0;
296        m_end = 0;
297        m_buffer.deallocateBuffer(m_buffer.buffer());
298        m_buffer.resetBufferPointer();
299    }
300
301    template<typename T, size_t inlineCapacity, typename Allocator>
302    template<typename Predicate>
303    inline DequeIterator<T, inlineCapacity, Allocator> Deque<T, inlineCapacity, Allocator>::findIf(Predicate& predicate)
304    {
305        iterator end_iterator = end();
306        for (iterator it = begin(); it != end_iterator; ++it) {
307            if (predicate(*it))
308                return it;
309        }
310        return end_iterator;
311    }
312
313    template<typename T, size_t inlineCapacity, typename Allocator>
314    inline void Deque<T, inlineCapacity, Allocator>::expandCapacityIfNeeded()
315    {
316        if (m_start) {
317            if (m_end + 1 != m_start)
318                return;
319        } else if (m_end) {
320            if (m_end != m_buffer.capacity() - 1)
321                return;
322        } else if (m_buffer.capacity())
323            return;
324
325        expandCapacity();
326    }
327
328    template<typename T, size_t inlineCapacity, typename Allocator>
329    void Deque<T, inlineCapacity, Allocator>::expandCapacity()
330    {
331        size_t oldCapacity = m_buffer.capacity();
332        T* oldBuffer = m_buffer.buffer();
333        m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
334        if (m_start <= m_end)
335            TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
336        else {
337            TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
338            size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
339            TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
340            m_start = newStart;
341        }
342        m_buffer.deallocateBuffer(oldBuffer);
343    }
344
345    template<typename T, size_t inlineCapacity, typename Allocator>
346    inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeFirst()
347    {
348        T oldFirst = Pass::transfer(first());
349        removeFirst();
350        return Pass::transfer(oldFirst);
351    }
352
353    template<typename T, size_t inlineCapacity, typename Allocator>
354    inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeLast()
355    {
356        T oldLast = Pass::transfer(last());
357        removeLast();
358        return Pass::transfer(oldLast);
359    }
360
361    template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
362    inline void Deque<T, inlineCapacity, Allocator>::append(const U& value)
363    {
364        expandCapacityIfNeeded();
365        new (NotNull, &m_buffer.buffer()[m_end]) T(value);
366        if (m_end == m_buffer.capacity() - 1)
367            m_end = 0;
368        else
369            ++m_end;
370    }
371
372    template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
373    inline void Deque<T, inlineCapacity, Allocator>::prepend(const U& value)
374    {
375        expandCapacityIfNeeded();
376        if (!m_start)
377            m_start = m_buffer.capacity() - 1;
378        else
379            --m_start;
380        new (NotNull, &m_buffer.buffer()[m_start]) T(value);
381    }
382
383    template<typename T, size_t inlineCapacity, typename Allocator>
384    inline void Deque<T, inlineCapacity, Allocator>::removeFirst()
385    {
386        ASSERT(!isEmpty());
387        TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
388        m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
389        if (m_start == m_buffer.capacity() - 1)
390            m_start = 0;
391        else
392            ++m_start;
393    }
394
395    template<typename T, size_t inlineCapacity, typename Allocator>
396    inline void Deque<T, inlineCapacity, Allocator>::removeLast()
397    {
398        ASSERT(!isEmpty());
399        if (!m_end)
400            m_end = m_buffer.capacity() - 1;
401        else
402            --m_end;
403        TypeOperations::destruct(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
404        m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
405    }
406
407    template<typename T, size_t inlineCapacity, typename Allocator>
408    inline void Deque<T, inlineCapacity, Allocator>::remove(iterator& it)
409    {
410        remove(it.m_index);
411    }
412
413    template<typename T, size_t inlineCapacity, typename Allocator>
414    inline void Deque<T, inlineCapacity, Allocator>::remove(const_iterator& it)
415    {
416        remove(it.m_index);
417    }
418
419    template<typename T, size_t inlineCapacity, typename Allocator>
420    inline void Deque<T, inlineCapacity, Allocator>::remove(size_t position)
421    {
422        if (position == m_end)
423            return;
424
425        T* buffer = m_buffer.buffer();
426        TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
427
428        // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
429        if (position >= m_start) {
430            TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
431            m_buffer.clearUnusedSlots(buffer + m_start, buffer + m_start + 1);
432            m_start = (m_start + 1) % m_buffer.capacity();
433        } else {
434            TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
435            m_buffer.clearUnusedSlots(buffer + m_end - 1, buffer + m_end);
436            m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
437        }
438    }
439
440    template<typename T, size_t inlineCapacity, typename Allocator>
441    inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase()
442        : m_deque(0)
443    {
444    }
445
446    template<typename T, size_t inlineCapacity, typename Allocator>
447    inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>* deque, size_t index)
448        : m_deque(const_cast<Deque<T, inlineCapacity, Allocator>*>(deque))
449        , m_index(index)
450    {
451    }
452
453    template<typename T, size_t inlineCapacity, typename Allocator>
454    inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const DequeIteratorBase& other)
455        : m_deque(other.m_deque)
456        , m_index(other.m_index)
457    {
458    }
459
460    template<typename T, size_t inlineCapacity, typename Allocator>
461    inline DequeIteratorBase<T, 0, Allocator>& DequeIteratorBase<T, inlineCapacity, Allocator>::operator=(const DequeIteratorBase<T, 0, Allocator>& other)
462    {
463        m_deque = other.m_deque;
464        m_index = other.m_index;
465        return *this;
466    }
467
468    template<typename T, size_t inlineCapacity, typename Allocator>
469    inline DequeIteratorBase<T, inlineCapacity, Allocator>::~DequeIteratorBase()
470    {
471    }
472
473    template<typename T, size_t inlineCapacity, typename Allocator>
474    inline bool DequeIteratorBase<T, inlineCapacity, Allocator>::isEqual(const DequeIteratorBase& other) const
475    {
476        return m_index == other.m_index;
477    }
478
479    template<typename T, size_t inlineCapacity, typename Allocator>
480    inline void DequeIteratorBase<T, inlineCapacity, Allocator>::increment()
481    {
482        ASSERT(m_index != m_deque->m_end);
483        ASSERT(m_deque->m_buffer.capacity());
484        if (m_index == m_deque->m_buffer.capacity() - 1)
485            m_index = 0;
486        else
487            ++m_index;
488    }
489
490    template<typename T, size_t inlineCapacity, typename Allocator>
491    inline void DequeIteratorBase<T, inlineCapacity, Allocator>::decrement()
492    {
493        ASSERT(m_index != m_deque->m_start);
494        ASSERT(m_deque->m_buffer.capacity());
495        if (!m_index)
496            m_index = m_deque->m_buffer.capacity() - 1;
497        else
498            --m_index;
499    }
500
501    template<typename T, size_t inlineCapacity, typename Allocator>
502    inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::after() const
503    {
504        ASSERT(m_index != m_deque->m_end);
505        return &m_deque->m_buffer.buffer()[m_index];
506    }
507
508    template<typename T, size_t inlineCapacity, typename Allocator>
509    inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::before() const
510    {
511        ASSERT(m_index != m_deque->m_start);
512        if (!m_index)
513            return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
514        return &m_deque->m_buffer.buffer()[m_index - 1];
515    }
516
517    // This is only called if the allocator is a HeapAllocator. It is used when
518    // visiting during a tracing GC.
519    template<typename T, size_t inlineCapacity, typename Allocator>
520    void Deque<T, inlineCapacity, Allocator>::trace(typename Allocator::Visitor* visitor)
521    {
522        ASSERT(Allocator::isGarbageCollected); // Garbage collector must be enabled.
523        const T* bufferBegin = m_buffer.buffer();
524        const T* end = bufferBegin + m_end;
525        if (ShouldBeTraced<VectorTraits<T> >::value) {
526            if (m_start <= m_end) {
527                for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != end; bufferEntry++)
528                    Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
529            } else {
530                for (const T* bufferEntry = bufferBegin; bufferEntry != end; bufferEntry++)
531                    Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
532                const T* bufferEnd = m_buffer.buffer() + m_buffer.capacity();
533                for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != bufferEnd; bufferEntry++)
534                    Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
535            }
536        }
537        if (m_buffer.hasOutOfLineBuffer())
538            Allocator::markNoTracing(visitor, m_buffer.buffer());
539    }
540
541    template<typename T, size_t inlineCapacity, typename Allocator>
542    inline void swap(Deque<T, inlineCapacity, Allocator>& a, Deque<T, inlineCapacity, Allocator>& b)
543    {
544        a.swap(b);
545    }
546
547#if !ENABLE(OILPAN)
548    template<typename T, size_t N>
549    struct NeedsTracing<Deque<T, N> > {
550        static const bool value = false;
551    };
552#endif
553
554} // namespace WTF
555
556using WTF::Deque;
557
558#endif // WTF_Deque_h
559