• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
3  * Copyright (C) 2009 Google Inc. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1.  Redistributions of source code must retain the above copyright
10  *     notice, this list of conditions and the following disclaimer.
11  * 2.  Redistributions in binary form must reproduce the above copyright
12  *     notice, this list of conditions and the following disclaimer in the
13  *     documentation and/or other materials provided with the distribution.
14  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
15  *     its contributors may be used to endorse or promote products derived
16  *     from this software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
22  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29 
30 #ifndef WTF_Deque_h
31 #define WTF_Deque_h
32 
33 // FIXME: Could move what Vector and Deque share into a separate file.
34 // Deque doesn't actually use Vector.
35 
36 #include "wtf/PassTraits.h"
37 #include "wtf/Vector.h"
38 #include <iterator>
39 
40 namespace WTF {
41     template<typename T, size_t inlineCapacity, typename Allocator> class DequeIteratorBase;
42     template<typename T, size_t inlineCapacity, typename Allocator> class DequeIterator;
43     template<typename T, size_t inlineCapacity, typename Allocator> class DequeConstIterator;
44 
45     template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
46     class Deque : public VectorDestructorBase<Deque<T, inlineCapacity, Allocator>, T, (inlineCapacity > 0), Allocator::isGarbageCollected> {
47         WTF_USE_ALLOCATOR(Deque, Allocator);
48     public:
49         typedef DequeIterator<T, inlineCapacity, Allocator> iterator;
50         typedef DequeConstIterator<T, inlineCapacity, Allocator> const_iterator;
51         typedef std::reverse_iterator<iterator> reverse_iterator;
52         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
53         typedef PassTraits<T> Pass;
54         typedef typename PassTraits<T>::PassType PassType;
55 
56         Deque();
57         Deque(const Deque<T, inlineCapacity, Allocator>&);
58         // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
59         Deque<T, 0, Allocator>& operator=(const Deque&);
60 
61         void finalize();
finalizeGarbageCollectedObject()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 
size()67         size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
isEmpty()68         bool isEmpty() const { return m_start == m_end; }
69 
begin()70         iterator begin() { return iterator(this, m_start); }
end()71         iterator end() { return iterator(this, m_end); }
begin()72         const_iterator begin() const { return const_iterator(this, m_start); }
end()73         const_iterator end() const { return const_iterator(this, m_end); }
rbegin()74         reverse_iterator rbegin() { return reverse_iterator(end()); }
rend()75         reverse_iterator rend() { return reverse_iterator(begin()); }
rbegin()76         const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
rend()77         const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
78 
first()79         T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
first()80         const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
81         PassType takeFirst();
82 
last()83         T& last() { ASSERT(m_start != m_end); return *(--end()); }
last()84         const T& last() const { ASSERT(m_start != m_end); return *(--end()); }
85         PassType takeLast();
86 
at(size_t i)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         }
at(size_t i)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 
assign(const DequeIteratorBase & other)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 
DequeIterator(Deque<T,inlineCapacity,Allocator> * deque,size_t index)173         DequeIterator(Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
174 
DequeIterator(const Iterator & other)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 
DequeConstIterator(const Deque<T,inlineCapacity,Allocator> * deque,size_t index)204         DequeConstIterator(const Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
205 
DequeConstIterator(const Iterator & other)206         DequeConstIterator(const Iterator& other) : Base(other) { }
DequeConstIterator(const NonConstIterator & 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>
Deque()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>
Deque(const Deque<T,inlineCapacity,Allocator> & other)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>
destroyAll()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>
finalize()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>
swap(Deque<T,0,Allocator> & other)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>
clear()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>
findIf(Predicate & 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>
expandCapacityIfNeeded()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>
expandCapacity()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>
takeFirst()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>
takeLast()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>
append(const U & value)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>
prepend(const U & value)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>
removeFirst()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>
removeLast()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>
remove(iterator & it)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>
remove(const_iterator & it)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>
remove(size_t position)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>
DequeIteratorBase()441     inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase()
442         : m_deque(0)
443     {
444     }
445 
446     template<typename T, size_t inlineCapacity, typename Allocator>
DequeIteratorBase(const Deque<T,inlineCapacity,Allocator> * deque,size_t index)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>
DequeIteratorBase(const DequeIteratorBase & other)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>
~DequeIteratorBase()469     inline DequeIteratorBase<T, inlineCapacity, Allocator>::~DequeIteratorBase()
470     {
471     }
472 
473     template<typename T, size_t inlineCapacity, typename Allocator>
isEqual(const DequeIteratorBase & other)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>
increment()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>
decrement()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>
after()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>
before()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>
trace(typename Allocator::Visitor * visitor)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>
swap(Deque<T,inlineCapacity,Allocator> & a,Deque<T,inlineCapacity,Allocator> & b)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 
556 using WTF::Deque;
557 
558 #endif // WTF_Deque_h
559