source: webkit/trunk/JavaScriptCore/wtf/Deque.h@ 38146

Last change on this file since 38146 was 32234, checked in by [email protected], 17 years ago

2008-04-18 Kevin McCullough <​[email protected]>

Reviewed by Sam.

-<rdar://problem/5770054> JavaScript profiler (10928)

  • Use Deque instead of Vector since the profiler uses prepend a lot and deque is faster at that.
  • profiler/FunctionCallProfile.h: (KJS::FunctionCallProfile::milliSecs): Corrected the name to match its output.
  • wtf/Deque.h: (WTF::deleteAllValues):
  • Property svn:eol-style set to native
File size: 18.9 KB
Line 
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
37namespace 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 void deleteAllValues(const Deque<T>& collection)
317 {
318 typedef typename Deque<T>::const_iterator iterator;
319 iterator end = collection.end();
320 for (iterator it = collection.begin(); it != end; ++it)
321 delete *it;
322 }
323
324 template<typename T>
325 inline Deque<T>& Deque<T>::operator=(const Deque<T>& other)
326 {
327 Deque<T> copy(other);
328 swap(copy);
329 return *this;
330 }
331
332 template<typename T>
333 inline void Deque<T>::destroyAll()
334 {
335 if (m_start <= m_end)
336 TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
337 else {
338 TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
339 TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
340 }
341 }
342
343 template<typename T>
344 inline Deque<T>::~Deque()
345 {
346 checkValidity();
347 invalidateIterators();
348 destroyAll();
349 }
350
351 template <typename T>
352 inline void Deque<T>::swap(Deque<T>& other)
353 {
354 checkValidity();
355 other.checkValidity();
356 invalidateIterators();
357 std::swap(m_start, other.m_start);
358 std::swap(m_end, other.m_end);
359 m_buffer.swap(other.m_buffer);
360 checkValidity();
361 other.checkValidity();
362 }
363
364 template <typename T>
365 inline void Deque<T>::clear()
366 {
367 checkValidity();
368 invalidateIterators();
369 destroyAll();
370 m_start = 0;
371 m_end = 0;
372 checkValidity();
373 }
374
375 template<typename T>
376 inline void Deque<T>::expandCapacityIfNeeded()
377 {
378 if (m_start) {
379 if (m_end + 1 != m_start)
380 return;
381 } else if (m_end) {
382 if (m_end != m_buffer.capacity() - 1)
383 return;
384 } else if (m_buffer.capacity())
385 return;
386
387 expandCapacity();
388 }
389
390 template<typename T>
391 void Deque<T>::expandCapacity()
392 {
393 checkValidity();
394 size_t oldCapacity = m_buffer.capacity();
395 size_t newCapacity = max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1);
396 T* oldBuffer = m_buffer.buffer();
397 m_buffer.allocateBuffer(newCapacity);
398 if (m_start <= m_end)
399 TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
400 else {
401 TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
402 size_t newStart = newCapacity - (oldCapacity - m_start);
403 TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
404 m_start = newStart;
405 }
406 m_buffer.deallocateBuffer(oldBuffer);
407 checkValidity();
408 }
409
410 template<typename T> template<typename U>
411 inline void Deque<T>::append(const U& value)
412 {
413 checkValidity();
414 expandCapacityIfNeeded();
415 new (&m_buffer.buffer()[m_end]) T(value);
416 if (m_end == m_buffer.capacity() - 1)
417 m_end = 0;
418 else
419 ++m_end;
420 checkValidity();
421 }
422
423 template<typename T> template<typename U>
424 inline void Deque<T>::prepend(const U& value)
425 {
426 checkValidity();
427 expandCapacityIfNeeded();
428 if (!m_start)
429 m_start = m_buffer.capacity() - 1;
430 else
431 --m_start;
432 new (&m_buffer.buffer()[m_start]) T(value);
433 checkValidity();
434 }
435
436 template<typename T>
437 inline void Deque<T>::removeFirst()
438 {
439 checkValidity();
440 invalidateIterators();
441 ASSERT(!isEmpty());
442 TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
443 if (m_start == m_buffer.capacity() - 1)
444 m_start = 0;
445 else
446 ++m_start;
447 checkValidity();
448 }
449
450#ifdef NDEBUG
451 template<typename T> inline void DequeIteratorBase<T>::checkValidity() const { }
452 template<typename T> inline void DequeIteratorBase<T>::checkValidity(const DequeIteratorBase<T>&) const { }
453 template<typename T> inline void DequeIteratorBase<T>::addToIteratorsList() { }
454#else
455 template<typename T>
456 void DequeIteratorBase<T>::checkValidity() const
457 {
458 ASSERT(m_deque);
459 m_deque->checkIndexValidity(m_index);
460 }
461
462 template<typename T>
463 void DequeIteratorBase<T>::checkValidity(const Base& other) const
464 {
465 checkValidity();
466 other.checkValidity();
467 ASSERT(m_deque == other.m_deque);
468 }
469
470 template<typename T>
471 void DequeIteratorBase<T>::addToIteratorsList()
472 {
473 if (!m_deque)
474 m_next = 0;
475 else {
476 m_next = m_deque->m_iterators;
477 m_deque->m_iterators = this;
478 if (m_next)
479 m_next->m_previous = this;
480 }
481 m_previous = 0;
482 }
483#endif
484
485 template<typename T>
486 inline DequeIteratorBase<T>::DequeIteratorBase()
487 : m_deque(0)
488 {
489 }
490
491 template<typename T>
492 inline DequeIteratorBase<T>::DequeIteratorBase(const Deque<T>* deque, size_t index)
493 : m_deque(const_cast<Deque<T>*>(deque))
494 , m_index(index)
495 {
496 addToIteratorsList();
497 checkValidity();
498 }
499
500 template<typename T>
501 inline DequeIteratorBase<T>::DequeIteratorBase(const Base& other)
502 : m_deque(other.m_deque)
503 , m_index(other.m_index)
504 {
505 addToIteratorsList();
506 checkValidity();
507 }
508
509 template<typename T>
510 inline DequeIteratorBase<T>::~DequeIteratorBase()
511 {
512#ifndef NDEBUG
513 // Delete iterator from doubly-linked list of iterators.
514 if (!m_deque) {
515 ASSERT(!m_next);
516 ASSERT(!m_previous);
517 } else {
518 if (m_next) {
519 ASSERT(m_next->m_previous == this);
520 m_next->m_previous = m_previous;
521 }
522 if (m_previous) {
523 ASSERT(m_deque->m_iterators != this);
524 ASSERT(m_previous->m_next == this);
525 m_previous->m_next = m_next;
526 } else {
527 ASSERT(m_deque->m_iterators == this);
528 m_deque->m_iterators = m_next;
529 }
530 }
531 m_deque = 0;
532 m_next = 0;
533 m_previous = 0;
534#endif
535 }
536
537 template<typename T>
538 inline bool DequeIteratorBase<T>::isEqual(const Base& other) const
539 {
540 checkValidity(other);
541 return m_index == other.m_index;
542 }
543
544 template<typename T>
545 inline void DequeIteratorBase<T>::increment()
546 {
547 checkValidity();
548 ASSERT(m_index != m_deque->m_end);
549 ASSERT(m_deque->m_buffer.capacity());
550 if (m_index == m_deque->m_buffer.capacity() - 1)
551 m_index = 0;
552 else
553 ++m_index;
554 checkValidity();
555 }
556
557 template<typename T>
558 inline void DequeIteratorBase<T>::decrement()
559 {
560 checkValidity();
561 ASSERT(m_index != m_deque->m_start);
562 ASSERT(m_deque->m_buffer.capacity());
563 if (!m_index)
564 m_index = m_deque->m_buffer.capacity() - 1;
565 else
566 --m_index;
567 checkValidity();
568 }
569
570 template<typename T>
571 inline T* DequeIteratorBase<T>::after() const
572 {
573 checkValidity();
574 ASSERT(m_index != m_deque->m_end);
575 return &m_deque->m_buffer.buffer()[m_index];
576 }
577
578 template<typename T>
579 inline T* DequeIteratorBase<T>::before() const
580 {
581 checkValidity();
582 ASSERT(m_index != m_deque->m_start);
583 if (!m_index)
584 return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
585 return &m_deque->m_buffer.buffer()[m_index - 1];
586 }
587
588} // namespace WTF
589
590using WTF::Deque;
591
592#endif // WTF_Deque_h
Note: See TracBrowser for help on using the repository browser.