Reviewed by Darin Adler.
[WebKit-https.git] / JavaScriptCore / wtf / Deque.h
1 /*
2  * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #ifndef WTF_Deque_h
30 #define WTF_Deque_h
31
32 // FIXME: Could move what Vector and Deque share into a separate file.
33 // Deque doesn't actually use Vector.
34
35 #include "Vector.h"
36
37 namespace WTF {
38
39     template<typename T> class DequeIteratorBase;
40     template<typename T> class DequeIterator;
41     template<typename T> class DequeConstIterator;
42     template<typename T> class DequeReverseIterator;
43     template<typename T> class DequeConstReverseIterator;
44
45     template<typename T>
46     class Deque {
47     public:
48         typedef DequeIterator<T> iterator;
49         typedef DequeConstIterator<T> const_iterator;
50         typedef DequeReverseIterator<T> reverse_iterator;
51         typedef DequeConstReverseIterator<T> const_reverse_iterator;
52
53         Deque();
54         Deque(const Deque<T>&);
55         Deque& operator=(const Deque<T>&);
56         ~Deque();
57
58         void swap(Deque<T>&);
59
60         size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
61         bool isEmpty() const { return m_start == m_end; }
62
63         iterator begin() { return iterator(this, m_start); }
64         iterator end() { return iterator(this, m_end); }
65         const_iterator begin() const { return const_iterator(this, m_start); }
66         const_iterator end() const { return const_iterator(this, m_end); }
67         reverse_iterator rbegin() { return reverse_iterator(this, m_end); }
68         reverse_iterator rend() { return reverse_iterator(this, m_start); }
69         const_reverse_iterator rbegin() const { return const_reverse_iterator(this, m_end); }
70         const_reverse_iterator rend() const { return const_reverse_iterator(this, m_start); }
71
72         T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
73         const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
74
75         template<typename U> void append(const U&);
76         template<typename U> void prepend(const U&);
77         void removeFirst();
78
79         void clear();
80
81     private:
82         friend class DequeIteratorBase<T>;
83
84         typedef VectorBuffer<T, 0> Buffer;
85         typedef VectorTypeOperations<T> TypeOperations;
86         typedef DequeIteratorBase<T> IteratorBase;
87
88         void invalidateIterators();
89         void destroyAll();
90         void checkValidity() const;
91         void checkIndexValidity(size_t) const;
92         void expandCapacityIfNeeded();
93         void expandCapacity();
94
95         size_t m_start;
96         size_t m_end;
97         Buffer m_buffer;
98 #ifndef NDEBUG
99         mutable IteratorBase* m_iterators;
100 #endif
101     };
102
103     template<typename T>
104     class DequeIteratorBase {
105     private:
106         typedef DequeIteratorBase<T> Base;
107
108     protected:
109         DequeIteratorBase();
110         DequeIteratorBase(const Deque<T>*, size_t);
111         DequeIteratorBase(const Base&);
112         Base& operator=(const Base&);
113         ~DequeIteratorBase();
114
115         void assign(const Base& other) { *this = other; }
116
117         void increment();
118         void decrement();
119
120         T* before() const;
121         T* after() const;
122
123         bool isEqual(const Base&) const;
124
125     private:
126         void addToIteratorsList();
127         void checkValidity() const;
128         void checkValidity(const Base&) const;
129
130         Deque<T>* m_deque;
131         size_t m_index;
132
133         friend class Deque<T>;
134
135 #ifndef NDEBUG
136         mutable DequeIteratorBase* m_next;
137         mutable DequeIteratorBase* m_previous;
138 #endif
139     };
140
141     template<typename T>
142     class DequeIterator : public DequeIteratorBase<T> {
143     private:
144         typedef DequeIteratorBase<T> Base;
145         typedef DequeIterator<T> Iterator;
146
147     public:
148         DequeIterator(Deque<T>* deque, size_t index) : Base(deque, index) { }
149
150         DequeIterator(const Iterator& other) : Base(other) { }
151         DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
152
153         T& operator*() const { return *Base::after(); }
154         T* operator->() const { return Base::after(); }
155
156         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
157         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
158
159         Iterator& operator++() { Base::increment(); return *this; }
160         // postfix ++ intentionally omitted
161         Iterator& operator--() { Base::decrement(); return *this; }
162         // postfix -- intentionally omitted
163     };
164
165     template<typename T>
166     class DequeConstIterator : public DequeIteratorBase<T> {
167     private:
168         typedef DequeIteratorBase<T> Base;
169         typedef DequeConstIterator<T> Iterator;
170         typedef DequeIterator<T> NonConstIterator;
171
172     public:
173         DequeConstIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
174
175         DequeConstIterator(const Iterator& other) : Base(other) { }
176         DequeConstIterator(const NonConstIterator& other) : Base(other) { }
177         DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
178         DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
179
180         const T& operator*() const { return *Base::after(); }
181         const T* operator->() const { return Base::after(); }
182
183         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
184         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
185
186         Iterator& operator++() { Base::increment(); return *this; }
187         // postfix ++ intentionally omitted
188         Iterator& operator--() { Base::decrement(); return *this; }
189         // postfix -- intentionally omitted
190     };
191
192     template<typename T>
193     class DequeReverseIterator : public DequeIteratorBase<T> {
194     private:
195         typedef DequeIteratorBase<T> Base;
196         typedef DequeReverseIterator<T> Iterator;
197
198     public:
199         DequeReverseIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
200
201         DequeReverseIterator(const Iterator& other) : Base(other) { }
202         DequeReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
203
204         T& operator*() const { return *Base::before(); }
205         T* operator->() const { return Base::before(); }
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::decrement(); return *this; }
211         // postfix ++ intentionally omitted
212         Iterator& operator--() { Base::increment(); return *this; }
213         // postfix -- intentionally omitted
214     };
215
216     template<typename T>
217     class DequeConstReverseIterator : public DequeIteratorBase<T> {
218     private:
219         typedef DequeIteratorBase<T> Base;
220         typedef DequeConstReverseIterator<T> Iterator;
221         typedef DequeReverseIterator<T> NonConstIterator;
222
223     public:
224         DequeConstReverseIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
225
226         DequeConstReverseIterator(const Iterator& other) : Base(other) { }
227         DequeConstReverseIterator(const NonConstIterator& other) : Base(other) { }
228         DequeConstReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
229         DequeConstReverseIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
230
231         const T& operator*() const { return *Base::before(); }
232         const T* operator->() const { return Base::before(); }
233
234         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
235         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
236
237         Iterator& operator++() { Base::decrement(); return *this; }
238         // postfix ++ intentionally omitted
239         Iterator& operator--() { Base::increment(); return *this; }
240         // postfix -- intentionally omitted
241     };
242
243 #ifdef NDEBUG
244     template<typename T> inline void Deque<T>::checkValidity() const { }
245     template<typename T> inline void Deque<T>::checkIndexValidity(size_t) const { }
246     template<typename T> inline void Deque<T>::invalidateIterators() { }
247 #else
248     template<typename T>
249     void Deque<T>::checkValidity() const
250     {
251         if (!m_buffer.capacity()) {
252             ASSERT(!m_start);
253             ASSERT(!m_end);
254         } else {
255             ASSERT(m_start < m_buffer.capacity());
256             ASSERT(m_end < m_buffer.capacity());
257         }
258     }
259
260     template<typename T>
261     void Deque<T>::checkIndexValidity(size_t index) const
262     {
263         ASSERT(index <= m_buffer.capacity());
264         if (m_start <= m_end) {
265             ASSERT(index >= m_start);
266             ASSERT(index <= m_end);
267         } else {
268             ASSERT(index >= m_start || index <= m_end);
269         }
270     }
271
272     template<typename T>
273     void Deque<T>::invalidateIterators()
274     {
275         IteratorBase* next;
276         for (IteratorBase* p = m_iterators; p; p = next) {
277             next = p->m_next;
278             p->m_deque = 0;
279             p->m_next = 0;
280             p->m_previous = 0;
281         }
282         m_iterators = 0;
283     }
284 #endif
285
286     template<typename T>
287     inline Deque<T>::Deque()
288         : m_start(0)
289         , m_end(0)
290 #ifndef NDEBUG
291         , m_iterators(0)
292 #endif
293     {
294         checkValidity();
295     }
296
297     template<typename T>
298     inline Deque<T>::Deque(const Deque<T>& other)
299         : m_start(other.m_start)
300         , m_end(other.m_end)
301         , m_buffer(other.m_buffer.capacity())
302 #ifndef NDEBUG
303         , m_iterators(0)
304 #endif
305     {
306         const T* otherBuffer = other.m_buffer.buffer();
307         if (m_start <= m_end)
308             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
309         else {
310             TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
311             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
312         }
313     }
314
315     template<typename T>
316     inline Deque<T>& Deque<T>::operator=(const Deque<T>& other)
317     {
318         Deque<T> copy(other);
319         swap(copy);
320         return *this;
321     }
322
323     template<typename T>
324     inline void Deque<T>::destroyAll()
325     {
326         if (m_start <= m_end)
327             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
328         else {
329             TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
330             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
331         }
332     }
333
334     template<typename T>
335     inline Deque<T>::~Deque()
336     {
337         checkValidity();
338         invalidateIterators();
339         destroyAll();
340     }
341
342     template <typename T>
343     inline void Deque<T>::swap(Deque<T>& other)
344     {
345         checkValidity();
346         other.checkValidity();
347         invalidateIterators();
348         std::swap(m_start, other.m_start);
349         std::swap(m_end, other.m_end);
350         m_buffer.swap(other.m_buffer);
351         checkValidity();
352         other.checkValidity();
353     }
354
355     template <typename T>
356     inline void Deque<T>::clear()
357     {
358         checkValidity();
359         invalidateIterators();
360         destroyAll();
361         m_start = 0;
362         m_end = 0;
363         checkValidity();
364     }
365
366     template<typename T>
367     inline void Deque<T>::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>
382     void Deque<T>::expandCapacity()
383     {
384         checkValidity();
385         size_t oldCapacity = m_buffer.capacity();
386         size_t newCapacity = 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> template<typename U>
402     inline void Deque<T>::append(const U& value)
403     {
404         checkValidity();
405         expandCapacityIfNeeded();
406         new (&m_buffer.buffer()[m_end]) T(value);
407         if (m_end == m_buffer.capacity() - 1)
408             m_end = 0;
409         else
410             ++m_end;
411         checkValidity();
412     }
413
414     template<typename T> template<typename U>
415     inline void Deque<T>::prepend(const U& value)
416     {
417         checkValidity();
418         expandCapacityIfNeeded();
419         if (!m_start)
420             m_start = m_buffer.capacity() - 1;
421         else
422             --m_start;
423         new (&m_buffer.buffer()[m_start]) T(value);
424         checkValidity();
425     }
426
427     template<typename T>
428     inline void Deque<T>::removeFirst()
429     {
430         checkValidity();
431         invalidateIterators();
432         ASSERT(!isEmpty());
433         TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
434         if (m_start == m_buffer.capacity() - 1)
435             m_start = 0;
436         else
437             ++m_start;
438         checkValidity();
439     }
440
441 #ifdef NDEBUG
442     template<typename T> inline void DequeIteratorBase<T>::checkValidity() const { }
443     template<typename T> inline void DequeIteratorBase<T>::checkValidity(const DequeIteratorBase<T>&) const { }
444     template<typename T> inline void DequeIteratorBase<T>::addToIteratorsList() { }
445 #else
446     template<typename T>
447     void DequeIteratorBase<T>::checkValidity() const
448     {
449         ASSERT(m_deque);
450         m_deque->checkIndexValidity(m_index);
451     }
452
453     template<typename T>
454     void DequeIteratorBase<T>::checkValidity(const Base& other) const
455     {
456         checkValidity();
457         other.checkValidity();
458         ASSERT(m_deque == other.m_deque);
459     }
460
461     template<typename T>
462     void DequeIteratorBase<T>::addToIteratorsList()
463     {
464         if (!m_deque)
465             m_next = 0;
466         else {
467             m_next = m_deque->m_iterators;
468             m_deque->m_iterators = this;
469             if (m_next)
470                 m_next->m_previous = this;
471         }
472         m_previous = 0;
473     }
474 #endif
475
476     template<typename T>
477     inline DequeIteratorBase<T>::DequeIteratorBase()
478         : m_deque(0)
479     {
480     }
481
482     template<typename T>
483     inline DequeIteratorBase<T>::DequeIteratorBase(const Deque<T>* deque, size_t index)
484         : m_deque(const_cast<Deque<T>*>(deque))
485         , m_index(index)
486     {
487         addToIteratorsList();
488         checkValidity();
489     }
490
491     template<typename T>
492     inline DequeIteratorBase<T>::DequeIteratorBase(const Base& other)
493         : m_deque(other.m_deque)
494         , m_index(other.m_index)
495     {
496         addToIteratorsList();
497         checkValidity();
498     }
499
500     template<typename T>
501     inline DequeIteratorBase<T>::~DequeIteratorBase()
502     {
503 #ifndef NDEBUG
504         // Delete iterator from doubly-linked list of iterators.
505         if (!m_deque) {
506             ASSERT(!m_next);
507             ASSERT(!m_previous);
508         } else {
509             if (m_next) {
510                 ASSERT(m_next->m_previous == this);
511                 m_next->m_previous = m_previous;
512             }
513             if (m_previous) {
514                 ASSERT(m_deque->m_iterators != this);
515                 ASSERT(m_previous->m_next == this);
516                 m_previous->m_next = m_next;
517             } else {
518                 ASSERT(m_deque->m_iterators == this);
519                 m_deque->m_iterators = m_next;
520             }
521         }
522         m_deque = 0;
523         m_next = 0;
524         m_previous = 0;
525 #endif
526     }
527
528     template<typename T>
529     inline bool DequeIteratorBase<T>::isEqual(const Base& other) const
530     {
531         checkValidity(other);
532         return m_index == other.m_index;
533     }
534
535     template<typename T>
536     inline void DequeIteratorBase<T>::increment()
537     {
538         checkValidity();
539         ASSERT(m_index != m_deque->m_end);
540         ASSERT(m_deque->m_buffer.capacity());
541         if (m_index == m_deque->m_buffer.capacity() - 1)
542             m_index = 0;
543         else
544             ++m_index;
545         checkValidity();
546     }
547
548     template<typename T>
549     inline void DequeIteratorBase<T>::decrement()
550     {
551         checkValidity();
552         ASSERT(m_index != m_deque->m_start);
553         ASSERT(m_deque->m_buffer.capacity());
554         if (!m_index)
555             m_index = m_deque->m_buffer.capacity() - 1;
556         else
557             --m_index;
558         checkValidity();
559     }
560
561     template<typename T>
562     inline T* DequeIteratorBase<T>::after() const
563     {
564         checkValidity();
565         ASSERT(m_index != m_deque->m_end);
566         return &m_deque->m_buffer.buffer()[m_index];
567     }
568
569     template<typename T>
570     inline T* DequeIteratorBase<T>::before() const
571     {
572         checkValidity();
573         ASSERT(m_index != m_deque->m_start);
574         if (!m_index)
575             return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
576         return &m_deque->m_buffer.buffer()[m_index - 1];
577     }
578
579 } // namespace WTF
580
581 using WTF::Deque;
582
583 #endif // WTF_Deque_h