• 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 
87         template<typename U> void append(const U&);
88         template<typename U> void prepend(const U&);
89         void removeFirst();
90         void removeLast();
91         void remove(iterator&);
92         void remove(const_iterator&);
93 
94         void clear();
95 
96         template<typename Predicate>
97         iterator findIf(Predicate&);
98 
99         void trace(typename Allocator::Visitor*);
100 
101     private:
102         friend class DequeIteratorBase<T, inlineCapacity, Allocator>;
103 
104         typedef VectorBuffer<T, inlineCapacity, Allocator> Buffer;
105         typedef VectorTypeOperations<T> TypeOperations;
106         typedef DequeIteratorBase<T, inlineCapacity, Allocator> IteratorBase;
107 
108         void remove(size_t position);
109         void destroyAll();
110         void expandCapacityIfNeeded();
111         void expandCapacity();
112 
113         Buffer m_buffer;
114         unsigned m_start;
115         unsigned m_end;
116     };
117 
118     template<typename T, size_t inlineCapacity, typename Allocator>
119     class DequeIteratorBase {
120     protected:
121         DequeIteratorBase();
122         DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>*, size_t);
123         DequeIteratorBase(const DequeIteratorBase&);
124         DequeIteratorBase<T, 0, Allocator>& operator=(const DequeIteratorBase<T, 0, Allocator>&);
125         ~DequeIteratorBase();
126 
assign(const DequeIteratorBase & other)127         void assign(const DequeIteratorBase& other) { *this = other; }
128 
129         void increment();
130         void decrement();
131 
132         T* before() const;
133         T* after() const;
134 
135         bool isEqual(const DequeIteratorBase&) const;
136 
137     private:
138         Deque<T, inlineCapacity, Allocator>* m_deque;
139         unsigned m_index;
140 
141         friend class Deque<T, inlineCapacity, Allocator>;
142     };
143 
144     template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
145     class DequeIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
146     private:
147         typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
148         typedef DequeIterator<T, inlineCapacity, Allocator> Iterator;
149 
150     public:
151         typedef ptrdiff_t difference_type;
152         typedef T value_type;
153         typedef T* pointer;
154         typedef T& reference;
155         typedef std::bidirectional_iterator_tag iterator_category;
156 
DequeIterator(Deque<T,inlineCapacity,Allocator> * deque,size_t index)157         DequeIterator(Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
158 
DequeIterator(const Iterator & other)159         DequeIterator(const Iterator& other) : Base(other) { }
160         DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
161 
162         T& operator*() const { return *Base::after(); }
163         T* operator->() const { return Base::after(); }
164 
165         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
166         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
167 
168         Iterator& operator++() { Base::increment(); return *this; }
169         // postfix ++ intentionally omitted
170         Iterator& operator--() { Base::decrement(); return *this; }
171         // postfix -- intentionally omitted
172     };
173 
174     template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
175     class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
176     private:
177         typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
178         typedef DequeConstIterator<T, inlineCapacity, Allocator> Iterator;
179         typedef DequeIterator<T, inlineCapacity, Allocator> NonConstIterator;
180 
181     public:
182         typedef ptrdiff_t difference_type;
183         typedef T value_type;
184         typedef const T* pointer;
185         typedef const T& reference;
186         typedef std::bidirectional_iterator_tag iterator_category;
187 
DequeConstIterator(const Deque<T,inlineCapacity,Allocator> * deque,size_t index)188         DequeConstIterator(const Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) { }
189 
DequeConstIterator(const Iterator & other)190         DequeConstIterator(const Iterator& other) : Base(other) { }
DequeConstIterator(const NonConstIterator & other)191         DequeConstIterator(const NonConstIterator& other) : Base(other) { }
192         DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
193         DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
194 
195         const T& operator*() const { return *Base::after(); }
196         const T* operator->() const { return Base::after(); }
197 
198         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
199         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
200 
201         Iterator& operator++() { Base::increment(); return *this; }
202         // postfix ++ intentionally omitted
203         Iterator& operator--() { Base::decrement(); return *this; }
204         // postfix -- intentionally omitted
205     };
206 
207     template<typename T, size_t inlineCapacity, typename Allocator>
Deque()208     inline Deque<T, inlineCapacity, Allocator>::Deque()
209         : m_start(0)
210         , m_end(0)
211     {
212     }
213 
214     template<typename T, size_t inlineCapacity, typename Allocator>
Deque(const Deque<T,inlineCapacity,Allocator> & other)215     inline Deque<T, inlineCapacity, Allocator>::Deque(const Deque<T, inlineCapacity, Allocator>& other)
216         : m_buffer(other.m_buffer.capacity())
217         , m_start(other.m_start)
218         , m_end(other.m_end)
219     {
220         const T* otherBuffer = other.m_buffer.buffer();
221         if (m_start <= m_end)
222             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
223         else {
224             TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
225             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
226         }
227     }
228 
229     template<typename T, size_t inlineCapacity, typename Allocator>
deleteAllValues(const Deque<T,inlineCapacity,Allocator> & collection)230     void deleteAllValues(const Deque<T, inlineCapacity, Allocator>& collection)
231     {
232         typedef typename Deque<T, inlineCapacity, Allocator>::const_iterator iterator;
233         iterator end = collection.end();
234         for (iterator it = collection.begin(); it != end; ++it)
235             delete *it;
236     }
237 
238     template<typename T, size_t inlineCapacity, typename Allocator>
239     inline Deque<T, 0, Allocator>& Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other)
240     {
241         Deque<T> copy(other);
242         swap(copy);
243         return *this;
244     }
245 
246     template<typename T, size_t inlineCapacity, typename Allocator>
destroyAll()247     inline void Deque<T, inlineCapacity, Allocator>::destroyAll()
248     {
249         if (m_start <= m_end) {
250             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
251             m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
252         } else {
253             TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
254             m_buffer.clearUnusedSlots(m_buffer.buffer(), m_buffer.buffer() + m_end);
255             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
256             m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
257         }
258     }
259 
260     // Off-GC-heap deques: Destructor should be called.
261     // On-GC-heap deques: Destructor should be called for inline buffers
262     // (if any) but destructor shouldn't be called for vector backing since
263     // it is managed by the traced GC heap.
264     template<typename T, size_t inlineCapacity, typename Allocator>
finalize()265     inline void Deque<T, inlineCapacity, Allocator>::finalize()
266     {
267         if (!inlineCapacity && !m_buffer.buffer())
268             return;
269         if (!isEmpty() && !(Allocator::isGarbageCollected && m_buffer.hasOutOfLineBuffer()))
270             destroyAll();
271 
272         m_buffer.destruct();
273     }
274 
275     // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
276     template<typename T, size_t inlineCapacity, typename Allocator>
swap(Deque<T,0,Allocator> & other)277     inline void Deque<T, inlineCapacity, Allocator>::swap(Deque<T, 0, Allocator>& other)
278     {
279         std::swap(m_start, other.m_start);
280         std::swap(m_end, other.m_end);
281         m_buffer.swapVectorBuffer(other.m_buffer);
282     }
283 
284     template<typename T, size_t inlineCapacity, typename Allocator>
clear()285     inline void Deque<T, inlineCapacity, Allocator>::clear()
286     {
287         destroyAll();
288         m_start = 0;
289         m_end = 0;
290         m_buffer.deallocateBuffer(m_buffer.buffer());
291         m_buffer.resetBufferPointer();
292     }
293 
294     template<typename T, size_t inlineCapacity, typename Allocator>
295     template<typename Predicate>
findIf(Predicate & predicate)296     inline DequeIterator<T, inlineCapacity, Allocator> Deque<T, inlineCapacity, Allocator>::findIf(Predicate& predicate)
297     {
298         iterator end_iterator = end();
299         for (iterator it = begin(); it != end_iterator; ++it) {
300             if (predicate(*it))
301                 return it;
302         }
303         return end_iterator;
304     }
305 
306     template<typename T, size_t inlineCapacity, typename Allocator>
expandCapacityIfNeeded()307     inline void Deque<T, inlineCapacity, Allocator>::expandCapacityIfNeeded()
308     {
309         if (m_start) {
310             if (m_end + 1 != m_start)
311                 return;
312         } else if (m_end) {
313             if (m_end != m_buffer.capacity() - 1)
314                 return;
315         } else if (m_buffer.capacity())
316             return;
317 
318         expandCapacity();
319     }
320 
321     template<typename T, size_t inlineCapacity, typename Allocator>
expandCapacity()322     void Deque<T, inlineCapacity, Allocator>::expandCapacity()
323     {
324         size_t oldCapacity = m_buffer.capacity();
325         T* oldBuffer = m_buffer.buffer();
326         m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
327         if (m_start <= m_end)
328             TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
329         else {
330             TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
331             size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
332             TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
333             m_start = newStart;
334         }
335         m_buffer.deallocateBuffer(oldBuffer);
336     }
337 
338     template<typename T, size_t inlineCapacity, typename Allocator>
takeFirst()339     inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeFirst()
340     {
341         T oldFirst = Pass::transfer(first());
342         removeFirst();
343         return Pass::transfer(oldFirst);
344     }
345 
346     template<typename T, size_t inlineCapacity, typename Allocator>
takeLast()347     inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeLast()
348     {
349         T oldLast = Pass::transfer(last());
350         removeLast();
351         return Pass::transfer(oldLast);
352     }
353 
354     template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
append(const U & value)355     inline void Deque<T, inlineCapacity, Allocator>::append(const U& value)
356     {
357         expandCapacityIfNeeded();
358         new (NotNull, &m_buffer.buffer()[m_end]) T(value);
359         if (m_end == m_buffer.capacity() - 1)
360             m_end = 0;
361         else
362             ++m_end;
363     }
364 
365     template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
prepend(const U & value)366     inline void Deque<T, inlineCapacity, Allocator>::prepend(const U& value)
367     {
368         expandCapacityIfNeeded();
369         if (!m_start)
370             m_start = m_buffer.capacity() - 1;
371         else
372             --m_start;
373         new (NotNull, &m_buffer.buffer()[m_start]) T(value);
374     }
375 
376     template<typename T, size_t inlineCapacity, typename Allocator>
removeFirst()377     inline void Deque<T, inlineCapacity, Allocator>::removeFirst()
378     {
379         ASSERT(!isEmpty());
380         TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
381         m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
382         if (m_start == m_buffer.capacity() - 1)
383             m_start = 0;
384         else
385             ++m_start;
386     }
387 
388     template<typename T, size_t inlineCapacity, typename Allocator>
removeLast()389     inline void Deque<T, inlineCapacity, Allocator>::removeLast()
390     {
391         ASSERT(!isEmpty());
392         if (!m_end)
393             m_end = m_buffer.capacity() - 1;
394         else
395             --m_end;
396         TypeOperations::destruct(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
397         m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
398     }
399 
400     template<typename T, size_t inlineCapacity, typename Allocator>
remove(iterator & it)401     inline void Deque<T, inlineCapacity, Allocator>::remove(iterator& it)
402     {
403         remove(it.m_index);
404     }
405 
406     template<typename T, size_t inlineCapacity, typename Allocator>
remove(const_iterator & it)407     inline void Deque<T, inlineCapacity, Allocator>::remove(const_iterator& it)
408     {
409         remove(it.m_index);
410     }
411 
412     template<typename T, size_t inlineCapacity, typename Allocator>
remove(size_t position)413     inline void Deque<T, inlineCapacity, Allocator>::remove(size_t position)
414     {
415         if (position == m_end)
416             return;
417 
418         T* buffer = m_buffer.buffer();
419         TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
420 
421         // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
422         if (position >= m_start) {
423             TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
424             m_buffer.clearUnusedSlots(buffer + m_start, buffer + m_start + 1);
425             m_start = (m_start + 1) % m_buffer.capacity();
426         } else {
427             TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
428             m_buffer.clearUnusedSlots(buffer + m_end - 1, buffer + m_end);
429             m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
430         }
431     }
432 
433     template<typename T, size_t inlineCapacity, typename Allocator>
DequeIteratorBase()434     inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase()
435         : m_deque(0)
436     {
437     }
438 
439     template<typename T, size_t inlineCapacity, typename Allocator>
DequeIteratorBase(const Deque<T,inlineCapacity,Allocator> * deque,size_t index)440     inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>* deque, size_t index)
441         : m_deque(const_cast<Deque<T, inlineCapacity, Allocator>*>(deque))
442         , m_index(index)
443     {
444     }
445 
446     template<typename T, size_t inlineCapacity, typename Allocator>
DequeIteratorBase(const DequeIteratorBase & other)447     inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const DequeIteratorBase& other)
448         : m_deque(other.m_deque)
449         , m_index(other.m_index)
450     {
451     }
452 
453     template<typename T, size_t inlineCapacity, typename Allocator>
454     inline DequeIteratorBase<T, 0, Allocator>& DequeIteratorBase<T, inlineCapacity, Allocator>::operator=(const DequeIteratorBase<T, 0, Allocator>& other)
455     {
456         m_deque = other.m_deque;
457         m_index = other.m_index;
458         return *this;
459     }
460 
461     template<typename T, size_t inlineCapacity, typename Allocator>
~DequeIteratorBase()462     inline DequeIteratorBase<T, inlineCapacity, Allocator>::~DequeIteratorBase()
463     {
464     }
465 
466     template<typename T, size_t inlineCapacity, typename Allocator>
isEqual(const DequeIteratorBase & other)467     inline bool DequeIteratorBase<T, inlineCapacity, Allocator>::isEqual(const DequeIteratorBase& other) const
468     {
469         return m_index == other.m_index;
470     }
471 
472     template<typename T, size_t inlineCapacity, typename Allocator>
increment()473     inline void DequeIteratorBase<T, inlineCapacity, Allocator>::increment()
474     {
475         ASSERT(m_index != m_deque->m_end);
476         ASSERT(m_deque->m_buffer.capacity());
477         if (m_index == m_deque->m_buffer.capacity() - 1)
478             m_index = 0;
479         else
480             ++m_index;
481     }
482 
483     template<typename T, size_t inlineCapacity, typename Allocator>
decrement()484     inline void DequeIteratorBase<T, inlineCapacity, Allocator>::decrement()
485     {
486         ASSERT(m_index != m_deque->m_start);
487         ASSERT(m_deque->m_buffer.capacity());
488         if (!m_index)
489             m_index = m_deque->m_buffer.capacity() - 1;
490         else
491             --m_index;
492     }
493 
494     template<typename T, size_t inlineCapacity, typename Allocator>
after()495     inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::after() const
496     {
497         ASSERT(m_index != m_deque->m_end);
498         return &m_deque->m_buffer.buffer()[m_index];
499     }
500 
501     template<typename T, size_t inlineCapacity, typename Allocator>
before()502     inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::before() const
503     {
504         ASSERT(m_index != m_deque->m_start);
505         if (!m_index)
506             return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
507         return &m_deque->m_buffer.buffer()[m_index - 1];
508     }
509 
510     // This is only called if the allocator is a HeapAllocator. It is used when
511     // visiting during a tracing GC.
512     template<typename T, size_t inlineCapacity, typename Allocator>
trace(typename Allocator::Visitor * visitor)513     void Deque<T, inlineCapacity, Allocator>::trace(typename Allocator::Visitor* visitor)
514     {
515         COMPILE_ASSERT(Allocator::isGarbageCollected, Garbage_collector_must_be_enabled);
516         const T* bufferBegin = m_buffer.buffer();
517         const T* end = bufferBegin + m_end;
518         if (ShouldBeTraced<VectorTraits<T> >::value) {
519             if (m_start <= m_end) {
520                 for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != end; bufferEntry++)
521                     Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
522             } else {
523                 for (const T* bufferEntry = bufferBegin; bufferEntry != end; bufferEntry++)
524                     Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
525                 const T* bufferEnd = m_buffer.buffer() + m_buffer.capacity();
526                 for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != bufferEnd; bufferEntry++)
527                     Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
528             }
529         }
530         if (m_buffer.hasOutOfLineBuffer())
531             Allocator::markNoTracing(visitor, m_buffer.buffer());
532     }
533 
534 } // namespace WTF
535 
536 using WTF::Deque;
537 
538 #endif // WTF_Deque_h
539