• 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 "Vector.h"
37 
38 namespace WTF {
39 
40     template<typename T, size_t inlineCapacity> class DequeIteratorBase;
41     template<typename T, size_t inlineCapacity> class DequeIterator;
42     template<typename T, size_t inlineCapacity> class DequeConstIterator;
43     template<typename T, size_t inlineCapacity> class DequeReverseIterator;
44     template<typename T, size_t inlineCapacity> class DequeConstReverseIterator;
45 
46     template<typename T, size_t inlineCapacity = 0>
47     class Deque {
48         WTF_MAKE_FAST_ALLOCATED;
49     public:
50         typedef DequeIterator<T, inlineCapacity> iterator;
51         typedef DequeConstIterator<T, inlineCapacity> const_iterator;
52         typedef DequeReverseIterator<T, inlineCapacity> reverse_iterator;
53         typedef DequeConstReverseIterator<T, inlineCapacity> const_reverse_iterator;
54 
55         Deque();
56         Deque(const Deque<T, inlineCapacity>&);
57         Deque& operator=(const Deque<T, inlineCapacity>&);
58         ~Deque();
59 
60         void swap(Deque<T, inlineCapacity>&);
61 
size()62         size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
isEmpty()63         bool isEmpty() const { return m_start == m_end; }
64 
begin()65         iterator begin() { return iterator(this, m_start); }
end()66         iterator end() { return iterator(this, m_end); }
begin()67         const_iterator begin() const { return const_iterator(this, m_start); }
end()68         const_iterator end() const { return const_iterator(this, m_end); }
rbegin()69         reverse_iterator rbegin() { return reverse_iterator(this, m_end); }
rend()70         reverse_iterator rend() { return reverse_iterator(this, m_start); }
rbegin()71         const_reverse_iterator rbegin() const { return const_reverse_iterator(this, m_end); }
rend()72         const_reverse_iterator rend() const { return const_reverse_iterator(this, m_start); }
73 
first()74         T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
first()75         const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
76         T takeFirst();
77 
78         template<typename U> void append(const U&);
79         template<typename U> void prepend(const U&);
80         void removeFirst();
81         void remove(iterator&);
82         void remove(const_iterator&);
83 
84         void clear();
85 
86         template<typename Predicate>
87         iterator findIf(Predicate&);
88 
89     private:
90         friend class DequeIteratorBase<T, inlineCapacity>;
91 
92         typedef VectorBuffer<T, inlineCapacity> Buffer;
93         typedef VectorTypeOperations<T> TypeOperations;
94         typedef DequeIteratorBase<T, inlineCapacity> IteratorBase;
95 
96         void remove(size_t position);
97         void invalidateIterators();
98         void destroyAll();
99         void checkValidity() const;
100         void checkIndexValidity(size_t) const;
101         void expandCapacityIfNeeded();
102         void expandCapacity();
103 
104         size_t m_start;
105         size_t m_end;
106         Buffer m_buffer;
107 #ifndef NDEBUG
108         mutable IteratorBase* m_iterators;
109 #endif
110     };
111 
112     template<typename T, size_t inlineCapacity = 0>
113     class DequeIteratorBase {
114     private:
115         typedef DequeIteratorBase<T, inlineCapacity> Base;
116 
117     protected:
118         DequeIteratorBase();
119         DequeIteratorBase(const Deque<T, inlineCapacity>*, size_t);
120         DequeIteratorBase(const Base&);
121         Base& operator=(const Base&);
122         ~DequeIteratorBase();
123 
assign(const Base & other)124         void assign(const Base& other) { *this = other; }
125 
126         void increment();
127         void decrement();
128 
129         T* before() const;
130         T* after() const;
131 
132         bool isEqual(const Base&) const;
133 
134     private:
135         void addToIteratorsList();
136         void removeFromIteratorsList();
137         void checkValidity() const;
138         void checkValidity(const Base&) const;
139 
140         Deque<T, inlineCapacity>* m_deque;
141         size_t m_index;
142 
143         friend class Deque<T, inlineCapacity>;
144 
145 #ifndef NDEBUG
146         mutable DequeIteratorBase* m_next;
147         mutable DequeIteratorBase* m_previous;
148 #endif
149     };
150 
151     template<typename T, size_t inlineCapacity = 0>
152     class DequeIterator : public DequeIteratorBase<T, inlineCapacity> {
153     private:
154         typedef DequeIteratorBase<T, inlineCapacity> Base;
155         typedef DequeIterator<T, inlineCapacity> Iterator;
156 
157     public:
DequeIterator(Deque<T,inlineCapacity> * deque,size_t index)158         DequeIterator(Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { }
159 
DequeIterator(const Iterator & other)160         DequeIterator(const Iterator& other) : Base(other) { }
161         DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
162 
163         T& operator*() const { return *Base::after(); }
164         T* operator->() const { return Base::after(); }
165 
166         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
167         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
168 
169         Iterator& operator++() { Base::increment(); return *this; }
170         // postfix ++ intentionally omitted
171         Iterator& operator--() { Base::decrement(); return *this; }
172         // postfix -- intentionally omitted
173     };
174 
175     template<typename T, size_t inlineCapacity = 0>
176     class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity> {
177     private:
178         typedef DequeIteratorBase<T, inlineCapacity> Base;
179         typedef DequeConstIterator<T, inlineCapacity> Iterator;
180         typedef DequeIterator<T, inlineCapacity> NonConstIterator;
181 
182     public:
DequeConstIterator(const Deque<T,inlineCapacity> * deque,size_t index)183         DequeConstIterator(const Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { }
184 
DequeConstIterator(const Iterator & other)185         DequeConstIterator(const Iterator& other) : Base(other) { }
DequeConstIterator(const NonConstIterator & other)186         DequeConstIterator(const NonConstIterator& other) : Base(other) { }
187         DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
188         DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
189 
190         const T& operator*() const { return *Base::after(); }
191         const T* operator->() const { return Base::after(); }
192 
193         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
194         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
195 
196         Iterator& operator++() { Base::increment(); return *this; }
197         // postfix ++ intentionally omitted
198         Iterator& operator--() { Base::decrement(); return *this; }
199         // postfix -- intentionally omitted
200     };
201 
202     template<typename T, size_t inlineCapacity = 0>
203     class DequeReverseIterator : public DequeIteratorBase<T, inlineCapacity> {
204     private:
205         typedef DequeIteratorBase<T, inlineCapacity> Base;
206         typedef DequeReverseIterator<T, inlineCapacity> Iterator;
207 
208     public:
DequeReverseIterator(const Deque<T,inlineCapacity> * deque,size_t index)209         DequeReverseIterator(const Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { }
210 
DequeReverseIterator(const Iterator & other)211         DequeReverseIterator(const Iterator& other) : Base(other) { }
212         DequeReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
213 
214         T& operator*() const { return *Base::before(); }
215         T* operator->() const { return Base::before(); }
216 
217         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
218         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
219 
220         Iterator& operator++() { Base::decrement(); return *this; }
221         // postfix ++ intentionally omitted
222         Iterator& operator--() { Base::increment(); return *this; }
223         // postfix -- intentionally omitted
224     };
225 
226     template<typename T, size_t inlineCapacity = 0>
227     class DequeConstReverseIterator : public DequeIteratorBase<T, inlineCapacity> {
228     private:
229         typedef DequeIteratorBase<T, inlineCapacity> Base;
230         typedef DequeConstReverseIterator<T, inlineCapacity> Iterator;
231         typedef DequeReverseIterator<T, inlineCapacity> NonConstIterator;
232 
233     public:
DequeConstReverseIterator(const Deque<T,inlineCapacity> * deque,size_t index)234         DequeConstReverseIterator(const Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { }
235 
DequeConstReverseIterator(const Iterator & other)236         DequeConstReverseIterator(const Iterator& other) : Base(other) { }
DequeConstReverseIterator(const NonConstIterator & other)237         DequeConstReverseIterator(const NonConstIterator& other) : Base(other) { }
238         DequeConstReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
239         DequeConstReverseIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
240 
241         const T& operator*() const { return *Base::before(); }
242         const T* operator->() const { return Base::before(); }
243 
244         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
245         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
246 
247         Iterator& operator++() { Base::decrement(); return *this; }
248         // postfix ++ intentionally omitted
249         Iterator& operator--() { Base::increment(); return *this; }
250         // postfix -- intentionally omitted
251     };
252 
253 #ifdef NDEBUG
checkValidity()254     template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkValidity() const { }
checkIndexValidity(size_t)255     template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkIndexValidity(size_t) const { }
invalidateIterators()256     template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::invalidateIterators() { }
257 #else
258     template<typename T, size_t inlineCapacity>
checkValidity()259     void Deque<T, inlineCapacity>::checkValidity() const
260     {
261         // In this implementation a capacity of 1 would confuse append() and
262         // other places that assume the index after capacity - 1 is 0.
263         ASSERT(m_buffer.capacity() != 1);
264 
265         if (!m_buffer.capacity()) {
266             ASSERT(!m_start);
267             ASSERT(!m_end);
268         } else {
269             ASSERT(m_start < m_buffer.capacity());
270             ASSERT(m_end < m_buffer.capacity());
271         }
272     }
273 
274     template<typename T, size_t inlineCapacity>
checkIndexValidity(size_t index)275     void Deque<T, inlineCapacity>::checkIndexValidity(size_t index) const
276     {
277         ASSERT(index <= m_buffer.capacity());
278         if (m_start <= m_end) {
279             ASSERT(index >= m_start);
280             ASSERT(index <= m_end);
281         } else {
282             ASSERT(index >= m_start || index <= m_end);
283         }
284     }
285 
286     template<typename T, size_t inlineCapacity>
invalidateIterators()287     void Deque<T, inlineCapacity>::invalidateIterators()
288     {
289         IteratorBase* next;
290         for (IteratorBase* p = m_iterators; p; p = next) {
291             next = p->m_next;
292             p->m_deque = 0;
293             p->m_next = 0;
294             p->m_previous = 0;
295         }
296         m_iterators = 0;
297     }
298 #endif
299 
300     template<typename T, size_t inlineCapacity>
Deque()301     inline Deque<T, inlineCapacity>::Deque()
302         : m_start(0)
303         , m_end(0)
304 #ifndef NDEBUG
305         , m_iterators(0)
306 #endif
307     {
308         checkValidity();
309     }
310 
311     template<typename T, size_t inlineCapacity>
Deque(const Deque<T,inlineCapacity> & other)312     inline Deque<T, inlineCapacity>::Deque(const Deque<T, inlineCapacity>& other)
313         : m_start(other.m_start)
314         , m_end(other.m_end)
315         , m_buffer(other.m_buffer.capacity())
316 #ifndef NDEBUG
317         , m_iterators(0)
318 #endif
319     {
320         const T* otherBuffer = other.m_buffer.buffer();
321         if (m_start <= m_end)
322             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
323         else {
324             TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
325             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
326         }
327     }
328 
329     template<typename T, size_t inlineCapacity>
deleteAllValues(const Deque<T,inlineCapacity> & collection)330     void deleteAllValues(const Deque<T, inlineCapacity>& collection)
331     {
332         typedef typename Deque<T, inlineCapacity>::const_iterator iterator;
333         iterator end = collection.end();
334         for (iterator it = collection.begin(); it != end; ++it)
335             delete *it;
336     }
337 
338     template<typename T, size_t inlineCapacity>
339     inline Deque<T, inlineCapacity>& Deque<T, inlineCapacity>::operator=(const Deque<T, inlineCapacity>& other)
340     {
341         // FIXME: This is inefficient if we're using an inline buffer and T is
342         // expensive to copy since it will copy the buffer twice instead of once.
343         Deque<T> copy(other);
344         swap(copy);
345         return *this;
346     }
347 
348     template<typename T, size_t inlineCapacity>
destroyAll()349     inline void Deque<T, inlineCapacity>::destroyAll()
350     {
351         if (m_start <= m_end)
352             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
353         else {
354             TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
355             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
356         }
357     }
358 
359     template<typename T, size_t inlineCapacity>
~Deque()360     inline Deque<T, inlineCapacity>::~Deque()
361     {
362         checkValidity();
363         invalidateIterators();
364         destroyAll();
365     }
366 
367     template<typename T, size_t inlineCapacity>
swap(Deque<T,inlineCapacity> & other)368     inline void Deque<T, inlineCapacity>::swap(Deque<T, inlineCapacity>& other)
369     {
370         checkValidity();
371         other.checkValidity();
372         invalidateIterators();
373         std::swap(m_start, other.m_start);
374         std::swap(m_end, other.m_end);
375         m_buffer.swap(other.m_buffer);
376         checkValidity();
377         other.checkValidity();
378     }
379 
380     template<typename T, size_t inlineCapacity>
clear()381     inline void Deque<T, inlineCapacity>::clear()
382     {
383         checkValidity();
384         invalidateIterators();
385         destroyAll();
386         m_start = 0;
387         m_end = 0;
388         checkValidity();
389     }
390 
391     template<typename T, size_t inlineCapacity>
392     template<typename Predicate>
findIf(Predicate & predicate)393     inline DequeIterator<T, inlineCapacity> Deque<T, inlineCapacity>::findIf(Predicate& predicate)
394     {
395         iterator end_iterator = end();
396         for (iterator it = begin(); it != end_iterator; ++it) {
397             if (predicate(*it))
398                 return it;
399         }
400         return end_iterator;
401     }
402 
403     template<typename T, size_t inlineCapacity>
expandCapacityIfNeeded()404     inline void Deque<T, inlineCapacity>::expandCapacityIfNeeded()
405     {
406         if (m_start) {
407             if (m_end + 1 != m_start)
408                 return;
409         } else if (m_end) {
410             if (m_end != m_buffer.capacity() - 1)
411                 return;
412         } else if (m_buffer.capacity())
413             return;
414 
415         expandCapacity();
416     }
417 
418     template<typename T, size_t inlineCapacity>
expandCapacity()419     void Deque<T, inlineCapacity>::expandCapacity()
420     {
421         checkValidity();
422         size_t oldCapacity = m_buffer.capacity();
423         size_t newCapacity = max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1);
424         T* oldBuffer = m_buffer.buffer();
425         m_buffer.allocateBuffer(newCapacity);
426         if (m_start <= m_end)
427             TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
428         else {
429             TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
430             size_t newStart = newCapacity - (oldCapacity - m_start);
431             TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
432             m_start = newStart;
433         }
434         m_buffer.deallocateBuffer(oldBuffer);
435         checkValidity();
436     }
437 
438     template<typename T, size_t inlineCapacity>
takeFirst()439     inline T Deque<T, inlineCapacity>::takeFirst()
440     {
441         T oldFirst = first();
442         removeFirst();
443         return oldFirst;
444     }
445 
446     template<typename T, size_t inlineCapacity> template<typename U>
append(const U & value)447     inline void Deque<T, inlineCapacity>::append(const U& value)
448     {
449         checkValidity();
450         expandCapacityIfNeeded();
451         new (&m_buffer.buffer()[m_end]) T(value);
452         if (m_end == m_buffer.capacity() - 1)
453             m_end = 0;
454         else
455             ++m_end;
456         checkValidity();
457     }
458 
459     template<typename T, size_t inlineCapacity> template<typename U>
prepend(const U & value)460     inline void Deque<T, inlineCapacity>::prepend(const U& value)
461     {
462         checkValidity();
463         expandCapacityIfNeeded();
464         if (!m_start)
465             m_start = m_buffer.capacity() - 1;
466         else
467             --m_start;
468         new (&m_buffer.buffer()[m_start]) T(value);
469         checkValidity();
470     }
471 
472     template<typename T, size_t inlineCapacity>
removeFirst()473     inline void Deque<T, inlineCapacity>::removeFirst()
474     {
475         checkValidity();
476         invalidateIterators();
477         ASSERT(!isEmpty());
478         TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
479         if (m_start == m_buffer.capacity() - 1)
480             m_start = 0;
481         else
482             ++m_start;
483         checkValidity();
484     }
485 
486     template<typename T, size_t inlineCapacity>
remove(iterator & it)487     inline void Deque<T, inlineCapacity>::remove(iterator& it)
488     {
489         it.checkValidity();
490         remove(it.m_index);
491     }
492 
493     template<typename T, size_t inlineCapacity>
remove(const_iterator & it)494     inline void Deque<T, inlineCapacity>::remove(const_iterator& it)
495     {
496         it.checkValidity();
497         remove(it.m_index);
498     }
499 
500     template<typename T, size_t inlineCapacity>
remove(size_t position)501     inline void Deque<T, inlineCapacity>::remove(size_t position)
502     {
503         if (position == m_end)
504             return;
505 
506         checkValidity();
507         invalidateIterators();
508 
509         T* buffer = m_buffer.buffer();
510         TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
511 
512         // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
513         if (position >= m_start) {
514             TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
515             m_start = (m_start + 1) % m_buffer.capacity();
516         } else {
517             TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
518             m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
519         }
520         checkValidity();
521     }
522 
523 #ifdef NDEBUG
checkValidity()524     template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity() const { }
checkValidity(const DequeIteratorBase<T,inlineCapacity> &)525     template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase<T, inlineCapacity>&) const { }
addToIteratorsList()526     template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList() { }
removeFromIteratorsList()527     template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList() { }
528 #else
529     template<typename T, size_t inlineCapacity>
checkValidity()530     void DequeIteratorBase<T, inlineCapacity>::checkValidity() const
531     {
532         ASSERT(m_deque);
533         m_deque->checkIndexValidity(m_index);
534     }
535 
536     template<typename T, size_t inlineCapacity>
checkValidity(const Base & other)537     void DequeIteratorBase<T, inlineCapacity>::checkValidity(const Base& other) const
538     {
539         checkValidity();
540         other.checkValidity();
541         ASSERT(m_deque == other.m_deque);
542     }
543 
544     template<typename T, size_t inlineCapacity>
addToIteratorsList()545     void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList()
546     {
547         if (!m_deque)
548             m_next = 0;
549         else {
550             m_next = m_deque->m_iterators;
551             m_deque->m_iterators = this;
552             if (m_next)
553                 m_next->m_previous = this;
554         }
555         m_previous = 0;
556     }
557 
558     template<typename T, size_t inlineCapacity>
removeFromIteratorsList()559     void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList()
560     {
561         if (!m_deque) {
562             ASSERT(!m_next);
563             ASSERT(!m_previous);
564         } else {
565             if (m_next) {
566                 ASSERT(m_next->m_previous == this);
567                 m_next->m_previous = m_previous;
568             }
569             if (m_previous) {
570                 ASSERT(m_deque->m_iterators != this);
571                 ASSERT(m_previous->m_next == this);
572                 m_previous->m_next = m_next;
573             } else {
574                 ASSERT(m_deque->m_iterators == this);
575                 m_deque->m_iterators = m_next;
576             }
577         }
578         m_next = 0;
579         m_previous = 0;
580     }
581 #endif
582 
583     template<typename T, size_t inlineCapacity>
DequeIteratorBase()584     inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase()
585         : m_deque(0)
586     {
587     }
588 
589     template<typename T, size_t inlineCapacity>
DequeIteratorBase(const Deque<T,inlineCapacity> * deque,size_t index)590     inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const Deque<T, inlineCapacity>* deque, size_t index)
591         : m_deque(const_cast<Deque<T, inlineCapacity>*>(deque))
592         , m_index(index)
593     {
594         addToIteratorsList();
595         checkValidity();
596     }
597 
598     template<typename T, size_t inlineCapacity>
DequeIteratorBase(const Base & other)599     inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const Base& other)
600         : m_deque(other.m_deque)
601         , m_index(other.m_index)
602     {
603         addToIteratorsList();
604         checkValidity();
605     }
606 
607     template<typename T, size_t inlineCapacity>
608     inline DequeIteratorBase<T, inlineCapacity>& DequeIteratorBase<T, inlineCapacity>::operator=(const Base& other)
609     {
610         checkValidity();
611         other.checkValidity();
612         removeFromIteratorsList();
613 
614         m_deque = other.m_deque;
615         m_index = other.m_index;
616         addToIteratorsList();
617         checkValidity();
618         return *this;
619     }
620 
621     template<typename T, size_t inlineCapacity>
~DequeIteratorBase()622     inline DequeIteratorBase<T, inlineCapacity>::~DequeIteratorBase()
623     {
624 #ifndef NDEBUG
625         removeFromIteratorsList();
626         m_deque = 0;
627 #endif
628     }
629 
630     template<typename T, size_t inlineCapacity>
isEqual(const Base & other)631     inline bool DequeIteratorBase<T, inlineCapacity>::isEqual(const Base& other) const
632     {
633         checkValidity(other);
634         return m_index == other.m_index;
635     }
636 
637     template<typename T, size_t inlineCapacity>
increment()638     inline void DequeIteratorBase<T, inlineCapacity>::increment()
639     {
640         checkValidity();
641         ASSERT(m_index != m_deque->m_end);
642         ASSERT(m_deque->m_buffer.capacity());
643         if (m_index == m_deque->m_buffer.capacity() - 1)
644             m_index = 0;
645         else
646             ++m_index;
647         checkValidity();
648     }
649 
650     template<typename T, size_t inlineCapacity>
decrement()651     inline void DequeIteratorBase<T, inlineCapacity>::decrement()
652     {
653         checkValidity();
654         ASSERT(m_index != m_deque->m_start);
655         ASSERT(m_deque->m_buffer.capacity());
656         if (!m_index)
657             m_index = m_deque->m_buffer.capacity() - 1;
658         else
659             --m_index;
660         checkValidity();
661     }
662 
663     template<typename T, size_t inlineCapacity>
after()664     inline T* DequeIteratorBase<T, inlineCapacity>::after() const
665     {
666         checkValidity();
667         ASSERT(m_index != m_deque->m_end);
668         return &m_deque->m_buffer.buffer()[m_index];
669     }
670 
671     template<typename T, size_t inlineCapacity>
before()672     inline T* DequeIteratorBase<T, inlineCapacity>::before() const
673     {
674         checkValidity();
675         ASSERT(m_index != m_deque->m_start);
676         if (!m_index)
677             return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
678         return &m_deque->m_buffer.buffer()[m_index - 1];
679     }
680 
681 } // namespace WTF
682 
683 using WTF::Deque;
684 
685 #endif // WTF_Deque_h
686