1/*
2 * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
3 * Copyright (C) 2009 Google Inc. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1.  Redistributions of source code must retain the above copyright
10 *     notice, this list of conditions and the following disclaimer.
11 * 2.  Redistributions in binary form must reproduce the above copyright
12 *     notice, this list of conditions and the following disclaimer in the
13 *     documentation and/or other materials provided with the distribution.
14 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
15 *     its contributors may be used to endorse or promote products derived
16 *     from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30#ifndef WTF_Deque_h
31#define WTF_Deque_h
32
33// FIXME: Could move what Vector and Deque share into a separate file.
34// Deque doesn't actually use Vector.
35
36#include "wtf/PassTraits.h"
37#include "wtf/Vector.h"
38#include <iterator>
39
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        PassType takeLast();
83
84        template<typename U> void append(const U&);
85        template<typename U> void prepend(const U&);
86        void removeFirst();
87        void removeLast();
88        void remove(iterator&);
89        void remove(const_iterator&);
90
91        void clear();
92
93        template<typename Predicate>
94        iterator findIf(Predicate&);
95
96    private:
97        friend class DequeIteratorBase<T, inlineCapacity>;
98
99        typedef VectorBuffer<T, inlineCapacity> Buffer;
100        typedef VectorTypeOperations<T> TypeOperations;
101        typedef DequeIteratorBase<T, inlineCapacity> IteratorBase;
102
103        void remove(size_t position);
104        void destroyAll();
105        void expandCapacityIfNeeded();
106        void expandCapacity();
107
108        Buffer m_buffer;
109        unsigned m_start;
110        unsigned m_end;
111    };
112
113    template<typename T, size_t inlineCapacity = 0>
114    class DequeIteratorBase {
115    protected:
116        DequeIteratorBase();
117        DequeIteratorBase(const Deque<T, inlineCapacity>*, size_t);
118        DequeIteratorBase(const DequeIteratorBase&);
119        DequeIteratorBase& operator=(const DequeIteratorBase&);
120        ~DequeIteratorBase();
121
122        void assign(const DequeIteratorBase& other) { *this = other; }
123
124        void increment();
125        void decrement();
126
127        T* before() const;
128        T* after() const;
129
130        bool isEqual(const DequeIteratorBase&) const;
131
132    private:
133        Deque<T, inlineCapacity>* m_deque;
134        unsigned m_index;
135
136        friend class Deque<T, inlineCapacity>;
137    };
138
139    template<typename T, size_t inlineCapacity = 0>
140    class DequeIterator : public DequeIteratorBase<T, inlineCapacity> {
141    private:
142        typedef DequeIteratorBase<T, inlineCapacity> Base;
143        typedef DequeIterator<T, inlineCapacity> Iterator;
144
145    public:
146        typedef ptrdiff_t difference_type;
147        typedef T value_type;
148        typedef T* pointer;
149        typedef T& reference;
150        typedef std::bidirectional_iterator_tag iterator_category;
151
152        DequeIterator(Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { }
153
154        DequeIterator(const Iterator& other) : Base(other) { }
155        DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
156
157        T& operator*() const { return *Base::after(); }
158        T* operator->() const { return Base::after(); }
159
160        bool operator==(const Iterator& other) const { return Base::isEqual(other); }
161        bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
162
163        Iterator& operator++() { Base::increment(); return *this; }
164        // postfix ++ intentionally omitted
165        Iterator& operator--() { Base::decrement(); return *this; }
166        // postfix -- intentionally omitted
167    };
168
169    template<typename T, size_t inlineCapacity = 0>
170    class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity> {
171    private:
172        typedef DequeIteratorBase<T, inlineCapacity> Base;
173        typedef DequeConstIterator<T, inlineCapacity> Iterator;
174        typedef DequeIterator<T, inlineCapacity> NonConstIterator;
175
176    public:
177        typedef ptrdiff_t difference_type;
178        typedef T value_type;
179        typedef const T* pointer;
180        typedef const T& reference;
181        typedef std::bidirectional_iterator_tag iterator_category;
182
183        DequeConstIterator(const Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { }
184
185        DequeConstIterator(const Iterator& other) : Base(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>
203    inline Deque<T, inlineCapacity>::Deque()
204        : m_start(0)
205        , m_end(0)
206    {
207    }
208
209    template<typename T, size_t inlineCapacity>
210    inline Deque<T, inlineCapacity>::Deque(const Deque<T, inlineCapacity>& other)
211        : m_buffer(other.m_buffer.capacity())
212        , m_start(other.m_start)
213        , m_end(other.m_end)
214    {
215        const T* otherBuffer = other.m_buffer.buffer();
216        if (m_start <= m_end)
217            TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
218        else {
219            TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
220            TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
221        }
222    }
223
224    template<typename T, size_t inlineCapacity>
225    void deleteAllValues(const Deque<T, inlineCapacity>& collection)
226    {
227        typedef typename Deque<T, inlineCapacity>::const_iterator iterator;
228        iterator end = collection.end();
229        for (iterator it = collection.begin(); it != end; ++it)
230            delete *it;
231    }
232
233    template<typename T, size_t inlineCapacity>
234    inline Deque<T, inlineCapacity>& Deque<T, inlineCapacity>::operator=(const Deque<T, inlineCapacity>& other)
235    {
236        // FIXME: This is inefficient if we're using an inline buffer and T is
237        // expensive to copy since it will copy the buffer twice instead of once.
238        Deque<T> copy(other);
239        swap(copy);
240        return *this;
241    }
242
243    template<typename T, size_t inlineCapacity>
244    inline void Deque<T, inlineCapacity>::destroyAll()
245    {
246        if (m_start <= m_end)
247            TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
248        else {
249            TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
250            TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
251        }
252    }
253
254    template<typename T, size_t inlineCapacity>
255    inline Deque<T, inlineCapacity>::~Deque()
256    {
257        destroyAll();
258        m_buffer.destruct();
259    }
260
261    template<typename T, size_t inlineCapacity>
262    inline void Deque<T, inlineCapacity>::swap(Deque<T, inlineCapacity>& other)
263    {
264        std::swap(m_start, other.m_start);
265        std::swap(m_end, other.m_end);
266        m_buffer.swap(other.m_buffer);
267    }
268
269    template<typename T, size_t inlineCapacity>
270    inline void Deque<T, inlineCapacity>::clear()
271    {
272        destroyAll();
273        m_start = 0;
274        m_end = 0;
275        m_buffer.deallocateBuffer(m_buffer.buffer());
276        m_buffer.resetBufferPointer();
277    }
278
279    template<typename T, size_t inlineCapacity>
280    template<typename Predicate>
281    inline DequeIterator<T, inlineCapacity> Deque<T, inlineCapacity>::findIf(Predicate& predicate)
282    {
283        iterator end_iterator = end();
284        for (iterator it = begin(); it != end_iterator; ++it) {
285            if (predicate(*it))
286                return it;
287        }
288        return end_iterator;
289    }
290
291    template<typename T, size_t inlineCapacity>
292    inline void Deque<T, inlineCapacity>::expandCapacityIfNeeded()
293    {
294        if (m_start) {
295            if (m_end + 1 != m_start)
296                return;
297        } else if (m_end) {
298            if (m_end != m_buffer.capacity() - 1)
299                return;
300        } else if (m_buffer.capacity())
301            return;
302
303        expandCapacity();
304    }
305
306    template<typename T, size_t inlineCapacity>
307    void Deque<T, inlineCapacity>::expandCapacity()
308    {
309        size_t oldCapacity = m_buffer.capacity();
310        T* oldBuffer = m_buffer.buffer();
311        m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
312        if (m_start <= m_end)
313            TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
314        else {
315            TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
316            size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
317            TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
318            m_start = newStart;
319        }
320        m_buffer.deallocateBuffer(oldBuffer);
321    }
322
323    template<typename T, size_t inlineCapacity>
324    inline typename Deque<T, inlineCapacity>::PassType Deque<T, inlineCapacity>::takeFirst()
325    {
326        T oldFirst = Pass::transfer(first());
327        removeFirst();
328        return Pass::transfer(oldFirst);
329    }
330
331    template<typename T, size_t inlineCapacity>
332    inline typename Deque<T, inlineCapacity>::PassType Deque<T, inlineCapacity>::takeLast()
333    {
334        T oldLast = Pass::transfer(last());
335        removeLast();
336        return Pass::transfer(oldLast);
337    }
338
339    template<typename T, size_t inlineCapacity> template<typename U>
340    inline void Deque<T, inlineCapacity>::append(const U& value)
341    {
342        expandCapacityIfNeeded();
343        new (NotNull, &m_buffer.buffer()[m_end]) T(value);
344        if (m_end == m_buffer.capacity() - 1)
345            m_end = 0;
346        else
347            ++m_end;
348    }
349
350    template<typename T, size_t inlineCapacity> template<typename U>
351    inline void Deque<T, inlineCapacity>::prepend(const U& value)
352    {
353        expandCapacityIfNeeded();
354        if (!m_start)
355            m_start = m_buffer.capacity() - 1;
356        else
357            --m_start;
358        new (NotNull, &m_buffer.buffer()[m_start]) T(value);
359    }
360
361    template<typename T, size_t inlineCapacity>
362    inline void Deque<T, inlineCapacity>::removeFirst()
363    {
364        ASSERT(!isEmpty());
365        TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
366        if (m_start == m_buffer.capacity() - 1)
367            m_start = 0;
368        else
369            ++m_start;
370    }
371
372    template<typename T, size_t inlineCapacity>
373    inline void Deque<T, inlineCapacity>::removeLast()
374    {
375        ASSERT(!isEmpty());
376        if (!m_end)
377            m_end = m_buffer.capacity() - 1;
378        else
379            --m_end;
380        TypeOperations::destruct(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
381    }
382
383    template<typename T, size_t inlineCapacity>
384    inline void Deque<T, inlineCapacity>::remove(iterator& it)
385    {
386        remove(it.m_index);
387    }
388
389    template<typename T, size_t inlineCapacity>
390    inline void Deque<T, inlineCapacity>::remove(const_iterator& it)
391    {
392        remove(it.m_index);
393    }
394
395    template<typename T, size_t inlineCapacity>
396    inline void Deque<T, inlineCapacity>::remove(size_t position)
397    {
398        if (position == m_end)
399            return;
400
401        T* buffer = m_buffer.buffer();
402        TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
403
404        // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
405        if (position >= m_start) {
406            TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
407            m_start = (m_start + 1) % m_buffer.capacity();
408        } else {
409            TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
410            m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
411        }
412    }
413
414    template<typename T, size_t inlineCapacity>
415    inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase()
416        : m_deque(0)
417    {
418    }
419
420    template<typename T, size_t inlineCapacity>
421    inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const Deque<T, inlineCapacity>* deque, size_t index)
422        : m_deque(const_cast<Deque<T, inlineCapacity>*>(deque))
423        , m_index(index)
424    {
425    }
426
427    template<typename T, size_t inlineCapacity>
428    inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const DequeIteratorBase& other)
429        : m_deque(other.m_deque)
430        , m_index(other.m_index)
431    {
432    }
433
434    template<typename T, size_t inlineCapacity>
435    inline DequeIteratorBase<T, inlineCapacity>& DequeIteratorBase<T, inlineCapacity>::operator=(const DequeIteratorBase& other)
436    {
437        m_deque = other.m_deque;
438        m_index = other.m_index;
439        return *this;
440    }
441
442    template<typename T, size_t inlineCapacity>
443    inline DequeIteratorBase<T, inlineCapacity>::~DequeIteratorBase()
444    {
445    }
446
447    template<typename T, size_t inlineCapacity>
448    inline bool DequeIteratorBase<T, inlineCapacity>::isEqual(const DequeIteratorBase& other) const
449    {
450        return m_index == other.m_index;
451    }
452
453    template<typename T, size_t inlineCapacity>
454    inline void DequeIteratorBase<T, inlineCapacity>::increment()
455    {
456        ASSERT(m_index != m_deque->m_end);
457        ASSERT(m_deque->m_buffer.capacity());
458        if (m_index == m_deque->m_buffer.capacity() - 1)
459            m_index = 0;
460        else
461            ++m_index;
462    }
463
464    template<typename T, size_t inlineCapacity>
465    inline void DequeIteratorBase<T, inlineCapacity>::decrement()
466    {
467        ASSERT(m_index != m_deque->m_start);
468        ASSERT(m_deque->m_buffer.capacity());
469        if (!m_index)
470            m_index = m_deque->m_buffer.capacity() - 1;
471        else
472            --m_index;
473    }
474
475    template<typename T, size_t inlineCapacity>
476    inline T* DequeIteratorBase<T, inlineCapacity>::after() const
477    {
478        ASSERT(m_index != m_deque->m_end);
479        return &m_deque->m_buffer.buffer()[m_index];
480    }
481
482    template<typename T, size_t inlineCapacity>
483    inline T* DequeIteratorBase<T, inlineCapacity>::before() const
484    {
485        ASSERT(m_index != m_deque->m_start);
486        if (!m_index)
487            return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
488        return &m_deque->m_buffer.buffer()[m_index - 1];
489    }
490
491} // namespace WTF
492
493using WTF::Deque;
494
495#endif // WTF_Deque_h
496