Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(567)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: Source/WTF/wtf/Deque.h

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

Powered by Google App Engine
This is Rietveld 408576698