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
40namespace 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        m_buffer.deallocateBuffer(m_buffer.buffer());
352        checkValidity();
353    }
354
355    template<typename T, size_t inlineCapacity>
356    template<typename Predicate>
357    inline DequeIterator<T, inlineCapacity> Deque<T, inlineCapacity>::findIf(Predicate& predicate)
358    {
359        iterator end_iterator = end();
360        for (iterator it = begin(); it != end_iterator; ++it) {
361            if (predicate(*it))
362                return it;
363        }
364        return end_iterator;
365    }
366
367    template<typename T, size_t inlineCapacity>
368    inline void Deque<T, inlineCapacity>::expandCapacityIfNeeded()
369    {
370        if (m_start) {
371            if (m_end + 1 != m_start)
372                return;
373        } else if (m_end) {
374            if (m_end != m_buffer.capacity() - 1)
375                return;
376        } else if (m_buffer.capacity())
377            return;
378
379        expandCapacity();
380    }
381
382    template<typename T, size_t inlineCapacity>
383    void Deque<T, inlineCapacity>::expandCapacity()
384    {
385        checkValidity();
386        size_t oldCapacity = m_buffer.capacity();
387        T* oldBuffer = m_buffer.buffer();
388        m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
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 = m_buffer.capacity() - (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
645using WTF::Deque;
646
647#endif // WTF_Deque_h
648