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