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