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