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

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/wtf/Deque.h