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 | |
38 | namespace 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 | |
667 | using WTF::Deque; |
668 | |
669 | #endif // WTF_Deque_h |
670 | |