2 * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
32 // FIXME: Could move what Vector and Deque share into a separate file.
33 // Deque doesn't actually use Vector.
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;
48 typedef DequeIterator<T> iterator;
49 typedef DequeConstIterator<T> const_iterator;
50 typedef DequeReverseIterator<T> reverse_iterator;
51 typedef DequeConstReverseIterator<T> const_reverse_iterator;
54 Deque(const Deque<T>&);
55 Deque& operator=(const Deque<T>&);
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; }
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); }
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]; }
75 template<typename U> void append(const U&);
76 template<typename U> void prepend(const U&);
82 friend class DequeIteratorBase<T>;
84 typedef VectorBuffer<T, 0> Buffer;
85 typedef VectorTypeOperations<T> TypeOperations;
86 typedef DequeIteratorBase<T> IteratorBase;
88 void invalidateIterators();
90 void checkValidity() const;
91 void checkIndexValidity(size_t) const;
92 void expandCapacityIfNeeded();
93 void expandCapacity();
99 mutable IteratorBase* m_iterators;
104 class DequeIteratorBase {
106 typedef DequeIteratorBase<T> Base;
110 DequeIteratorBase(const Deque<T>*, size_t);
111 DequeIteratorBase(const Base&);
112 Base& operator=(const Base&);
113 ~DequeIteratorBase();
115 void assign(const Base& other) { *this = other; }
123 bool isEqual(const Base&) const;
126 void addToIteratorsList();
127 void checkValidity() const;
128 void checkValidity(const Base&) const;
133 friend class Deque<T>;
136 mutable DequeIteratorBase* m_next;
137 mutable DequeIteratorBase* m_previous;
142 class DequeIterator : public DequeIteratorBase<T> {
144 typedef DequeIteratorBase<T> Base;
145 typedef DequeIterator<T> Iterator;
148 DequeIterator(Deque<T>* deque, size_t index) : Base(deque, index) { }
150 DequeIterator(const Iterator& other) : Base(other) { }
151 DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
153 T& operator*() const { return *Base::after(); }
154 T* operator->() const { return Base::after(); }
156 bool operator==(const Iterator& other) const { return Base::isEqual(other); }
157 bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
159 Iterator& operator++() { Base::increment(); return *this; }
160 // postfix ++ intentionally omitted
161 Iterator& operator--() { Base::decrement(); return *this; }
162 // postfix -- intentionally omitted
166 class DequeConstIterator : public DequeIteratorBase<T> {
168 typedef DequeIteratorBase<T> Base;
169 typedef DequeConstIterator<T> Iterator;
170 typedef DequeIterator<T> NonConstIterator;
173 DequeConstIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
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; }
180 const T& operator*() const { return *Base::after(); }
181 const T* operator->() const { return Base::after(); }
183 bool operator==(const Iterator& other) const { return Base::isEqual(other); }
184 bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
186 Iterator& operator++() { Base::increment(); return *this; }
187 // postfix ++ intentionally omitted
188 Iterator& operator--() { Base::decrement(); return *this; }
189 // postfix -- intentionally omitted
193 class DequeReverseIterator : public DequeIteratorBase<T> {
195 typedef DequeIteratorBase<T> Base;
196 typedef DequeReverseIterator<T> Iterator;
199 DequeReverseIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
201 DequeReverseIterator(const Iterator& other) : Base(other) { }
202 DequeReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
204 T& operator*() const { return *Base::before(); }
205 T* operator->() const { return Base::before(); }
207 bool operator==(const Iterator& other) const { return Base::isEqual(other); }
208 bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
210 Iterator& operator++() { Base::decrement(); return *this; }
211 // postfix ++ intentionally omitted
212 Iterator& operator--() { Base::increment(); return *this; }
213 // postfix -- intentionally omitted
217 class DequeConstReverseIterator : public DequeIteratorBase<T> {
219 typedef DequeIteratorBase<T> Base;
220 typedef DequeConstReverseIterator<T> Iterator;
221 typedef DequeReverseIterator<T> NonConstIterator;
224 DequeConstReverseIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
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; }
231 const T& operator*() const { return *Base::before(); }
232 const T* operator->() const { return Base::before(); }
234 bool operator==(const Iterator& other) const { return Base::isEqual(other); }
235 bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
237 Iterator& operator++() { Base::decrement(); return *this; }
238 // postfix ++ intentionally omitted
239 Iterator& operator--() { Base::increment(); return *this; }
240 // postfix -- intentionally omitted
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() { }
249 void Deque<T>::checkValidity() const
251 if (!m_buffer.capacity()) {
255 ASSERT(m_start < m_buffer.capacity());
256 ASSERT(m_end < m_buffer.capacity());
261 void Deque<T>::checkIndexValidity(size_t index) const
263 ASSERT(index <= m_buffer.capacity());
264 if (m_start <= m_end) {
265 ASSERT(index >= m_start);
266 ASSERT(index <= m_end);
268 ASSERT(index >= m_start || index <= m_end);
273 void Deque<T>::invalidateIterators()
276 for (IteratorBase* p = m_iterators; p; p = next) {
287 inline Deque<T>::Deque()
298 inline Deque<T>::Deque(const Deque<T>& other)
299 : m_start(other.m_start)
301 , m_buffer(other.m_buffer.capacity())
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);
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);
316 inline Deque<T>& Deque<T>::operator=(const Deque<T>& other)
318 Deque<T> copy(other);
324 inline void Deque<T>::destroyAll()
326 if (m_start <= m_end)
327 TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
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());
335 inline Deque<T>::~Deque()
338 invalidateIterators();
342 template <typename T>
343 inline void Deque<T>::swap(Deque<T>& other)
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);
352 other.checkValidity();
355 template <typename T>
356 inline void Deque<T>::clear()
359 invalidateIterators();
367 inline void Deque<T>::expandCapacityIfNeeded()
370 if (m_end + 1 != m_start)
373 if (m_end && m_end != m_buffer.capacity() - 1)
380 void Deque<T>::expandCapacity()
383 size_t oldCapacity = m_buffer.capacity();
384 size_t newCapacity = max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1);
385 T* oldBuffer = m_buffer.buffer();
386 m_buffer.allocateBuffer(newCapacity);
387 if (m_start <= m_end)
388 TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
390 TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
391 size_t newStart = newCapacity - (oldCapacity - m_start);
392 TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
395 m_buffer.deallocateBuffer(oldBuffer);
399 template<typename T> template<typename U>
400 inline void Deque<T>::append(const U& value)
403 expandCapacityIfNeeded();
404 new (&m_buffer.buffer()[m_end]) T(value);
405 if (m_end == m_buffer.capacity() - 1)
412 template<typename T> template<typename U>
413 inline void Deque<T>::prepend(const U& value)
415 expandCapacityIfNeeded();
417 m_start = m_buffer.capacity() - 1;
420 new (&m_buffer.buffer()[m_start]) T(value);
424 inline void Deque<T>::removeFirst()
427 invalidateIterators();
429 TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
430 if (m_start == m_buffer.capacity() - 1)
438 template<typename T> inline void DequeIteratorBase<T>::checkValidity() const { }
439 template<typename T> inline void DequeIteratorBase<T>::checkValidity(const DequeIteratorBase<T>&) const { }
440 template<typename T> inline void DequeIteratorBase<T>::addToIteratorsList() { }
443 void DequeIteratorBase<T>::checkValidity() const
446 m_deque->checkIndexValidity(m_index);
450 void DequeIteratorBase<T>::checkValidity(const Base& other) const
453 other.checkValidity();
454 ASSERT(m_deque == other.m_deque);
458 void DequeIteratorBase<T>::addToIteratorsList()
463 m_next = m_deque->m_iterators;
464 m_deque->m_iterators = this;
466 m_next->m_previous = this;
473 inline DequeIteratorBase<T>::DequeIteratorBase()
479 inline DequeIteratorBase<T>::DequeIteratorBase(const Deque<T>* deque, size_t index)
480 : m_deque(const_cast<Deque<T>*>(deque))
483 addToIteratorsList();
488 inline DequeIteratorBase<T>::DequeIteratorBase(const Base& other)
489 : m_deque(other.m_deque)
490 , m_index(other.m_index)
492 addToIteratorsList();
497 inline DequeIteratorBase<T>::~DequeIteratorBase()
500 // Delete iterator from doubly-linked list of iterators.
506 ASSERT(m_next->m_previous == this);
507 m_next->m_previous = m_previous;
510 ASSERT(m_deque->m_iterators != this);
511 ASSERT(m_previous->m_next == this);
512 m_previous->m_next = m_next;
514 ASSERT(m_deque->m_iterators == this);
515 m_deque->m_iterators = m_next;
525 inline bool DequeIteratorBase<T>::isEqual(const Base& other) const
527 checkValidity(other);
528 return m_index == other.m_index;
532 inline void DequeIteratorBase<T>::increment()
535 ASSERT(m_index != m_deque->m_end);
536 ASSERT(m_deque->m_buffer.capacity());
537 if (m_index == m_deque->m_buffer.capacity() - 1)
545 inline void DequeIteratorBase<T>::decrement()
548 ASSERT(m_index != m_deque->m_start);
549 ASSERT(m_deque->m_buffer.capacity());
551 m_index = m_deque->m_buffer.capacity() - 1;
558 inline T* DequeIteratorBase<T>::after() const
561 ASSERT(m_index != m_deque->m_end);
562 return &m_deque->m_buffer.buffer()[m_index];
566 inline T* DequeIteratorBase<T>::before() const
569 ASSERT(m_index != m_deque->m_start);
571 return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
572 return &m_deque->m_buffer.buffer()[m_index - 1];
579 #endif // WTF_Deque_h