diff options
Diffstat (limited to 'JavaScriptCore/wtf/Deque.h')
| -rw-r--r-- | JavaScriptCore/wtf/Deque.h | 600 |
1 files changed, 533 insertions, 67 deletions
diff --git a/JavaScriptCore/wtf/Deque.h b/JavaScriptCore/wtf/Deque.h index c09ef42..70c546b 100644 --- a/JavaScriptCore/wtf/Deque.h +++ b/JavaScriptCore/wtf/Deque.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2007 Apple Inc. All rights reserved. + * Copyright (C) 2007, 2008 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -25,99 +25,565 @@ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ + #ifndef WTF_Deque_h #define WTF_Deque_h -#include <wtf/Assertions.h> -#include <wtf/Noncopyable.h> +// FIXME: Could move what Vector and Deque share into a separate file. +// Deque doesn't actually use Vector. + +#include "Vector.h" namespace WTF { + template<typename T> class DequeIteratorBase; + template<typename T> class DequeIterator; + template<typename T> class DequeConstIterator; + template<typename T> class DequeReverseIterator; + template<typename T> class DequeConstReverseIterator; + template<typename T> - class DequeNode { + class Deque { public: - DequeNode(const T& item) : m_value(item), m_next(0) { } + typedef DequeIterator<T> iterator; + typedef DequeConstIterator<T> const_iterator; + typedef DequeReverseIterator<T> reverse_iterator; + typedef DequeConstReverseIterator<T> const_reverse_iterator; + + Deque(); + Deque(const Deque<T>&); + Deque& operator=(const Deque<T>&); + ~Deque(); + + void swap(Deque<T>&); + + size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; } + bool isEmpty() const { return m_start == m_end; } + + iterator begin() { return iterator(this, m_start); } + iterator end() { return iterator(this, m_end); } + const_iterator begin() const { return const_iterator(this, m_start); } + const_iterator end() const { return const_iterator(this, m_end); } + reverse_iterator rbegin() { return reverse_iterator(this, m_end); } + reverse_iterator rend() { return reverse_iterator(this, m_start); } + const_reverse_iterator rbegin() const { return const_reverse_iterator(this, m_end); } + const_reverse_iterator rend() const { return const_reverse_iterator(this, m_start); } + + T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; } + const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; } + + template<typename U> void append(const U&); + template<typename U> void prepend(const U&); + void removeFirst(); + + void clear(); + + private: + friend class DequeIteratorBase<T>; + + typedef VectorBuffer<T, 0> Buffer; + typedef VectorTypeOperations<T> TypeOperations; + typedef DequeIteratorBase<T> IteratorBase; + + void invalidateIterators(); + void destroyAll(); + void checkValidity() const; + void checkIndexValidity(size_t) const; + void expandCapacityIfNeeded(); + void expandCapacity(); + + size_t m_start; + size_t m_end; + Buffer m_buffer; +#ifndef NDEBUG + mutable IteratorBase* m_iterators; +#endif + }; + + template<typename T> + class DequeIteratorBase { + private: + typedef DequeIteratorBase<T> Base; + + protected: + DequeIteratorBase(); + DequeIteratorBase(const Deque<T>*, size_t); + DequeIteratorBase(const Base&); + Base& operator=(const Base&); + ~DequeIteratorBase(); + + void assign(const Base& other) { *this = other; } + + void increment(); + void decrement(); + + T* before() const; + T* after() const; - T m_value; - DequeNode* m_next; + bool isEqual(const Base&) const; + + private: + void addToIteratorsList(); + void checkValidity() const; + void checkValidity(const Base&) const; + + Deque<T>* m_deque; + size_t m_index; + + friend class Deque<T>; + +#ifndef NDEBUG + mutable DequeIteratorBase* m_next; + mutable DequeIteratorBase* m_previous; +#endif }; template<typename T> - class Deque : Noncopyable { + class DequeIterator : public DequeIteratorBase<T> { + private: + typedef DequeIteratorBase<T> Base; + typedef DequeIterator<T> Iterator; + public: - Deque() - : m_size(0) - , m_first(0) - , m_last(0) - { + DequeIterator(Deque<T>* deque, size_t index) : Base(deque, index) { } + + DequeIterator(const Iterator& other) : Base(other) { } + DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; } + + T& operator*() const { return *Base::after(); } + T* operator->() const { return Base::after(); } + + bool operator==(const Iterator& other) const { return Base::isEqual(other); } + bool operator!=(const Iterator& other) const { return !Base::isEqual(other); } + + Iterator& operator++() { Base::increment(); return *this; } + // postfix ++ intentionally omitted + Iterator& operator--() { Base::decrement(); return *this; } + // postfix -- intentionally omitted + }; + + template<typename T> + class DequeConstIterator : public DequeIteratorBase<T> { + private: + typedef DequeIteratorBase<T> Base; + typedef DequeConstIterator<T> Iterator; + typedef DequeIterator<T> NonConstIterator; + + public: + DequeConstIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { } + + DequeConstIterator(const Iterator& other) : Base(other) { } + DequeConstIterator(const NonConstIterator& other) : Base(other) { } + DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; } + DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; } + + const T& operator*() const { return *Base::after(); } + const T* operator->() const { return Base::after(); } + + bool operator==(const Iterator& other) const { return Base::isEqual(other); } + bool operator!=(const Iterator& other) const { return !Base::isEqual(other); } + + Iterator& operator++() { Base::increment(); return *this; } + // postfix ++ intentionally omitted + Iterator& operator--() { Base::decrement(); return *this; } + // postfix -- intentionally omitted + }; + + template<typename T> + class DequeReverseIterator : public DequeIteratorBase<T> { + private: + typedef DequeIteratorBase<T> Base; + typedef DequeReverseIterator<T> Iterator; + + public: + DequeReverseIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { } + + DequeReverseIterator(const Iterator& other) : Base(other) { } + DequeReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; } + + T& operator*() const { return *Base::before(); } + T* operator->() const { return Base::before(); } + + bool operator==(const Iterator& other) const { return Base::isEqual(other); } + bool operator!=(const Iterator& other) const { return !Base::isEqual(other); } + + Iterator& operator++() { Base::decrement(); return *this; } + // postfix ++ intentionally omitted + Iterator& operator--() { Base::increment(); return *this; } + // postfix -- intentionally omitted + }; + + template<typename T> + class DequeConstReverseIterator : public DequeIteratorBase<T> { + private: + typedef DequeIteratorBase<T> Base; + typedef DequeConstReverseIterator<T> Iterator; + typedef DequeReverseIterator<T> NonConstIterator; + + public: + DequeConstReverseIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { } + + DequeConstReverseIterator(const Iterator& other) : Base(other) { } + DequeConstReverseIterator(const NonConstIterator& other) : Base(other) { } + DequeConstReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; } + DequeConstReverseIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; } + + const T& operator*() const { return *Base::before(); } + const T* operator->() const { return Base::before(); } + + bool operator==(const Iterator& other) const { return Base::isEqual(other); } + bool operator!=(const Iterator& other) const { return !Base::isEqual(other); } + + Iterator& operator++() { Base::decrement(); return *this; } + // postfix ++ intentionally omitted + Iterator& operator--() { Base::increment(); return *this; } + // postfix -- intentionally omitted + }; + +#ifdef NDEBUG + template<typename T> inline void Deque<T>::checkValidity() const { } + template<typename T> inline void Deque<T>::checkIndexValidity(size_t) const { } + template<typename T> inline void Deque<T>::invalidateIterators() { } +#else + template<typename T> + void Deque<T>::checkValidity() const + { + if (!m_buffer.capacity()) { + ASSERT(!m_start); + ASSERT(!m_end); + } else { + ASSERT(m_start < m_buffer.capacity()); + ASSERT(m_end < m_buffer.capacity()); } + } - ~Deque() - { - clear(); + template<typename T> + void Deque<T>::checkIndexValidity(size_t index) const + { + ASSERT(index <= m_buffer.capacity()); + if (m_start <= m_end) { + ASSERT(index >= m_start); + ASSERT(index <= m_end); + } else { + ASSERT(index >= m_start || index <= m_end); } + } - size_t size() const { return m_size; } - bool isEmpty() const { return !size(); } - - void append(const T& item) - { - DequeNode<T>* newNode = new DequeNode<T>(item); - if (m_last) - m_last->m_next = newNode; - m_last = newNode; - if (!m_first) - m_first = newNode; - ++m_size; + template<typename T> + void Deque<T>::invalidateIterators() + { + IteratorBase* next; + for (IteratorBase* p = m_iterators; p; p = next) { + next = p->m_next; + p->m_deque = 0; + p->m_next = 0; + p->m_previous = 0; } + m_iterators = 0; + } +#endif + + template<typename T> + inline Deque<T>::Deque() + : m_start(0) + , m_end(0) +#ifndef NDEBUG + , m_iterators(0) +#endif + { + checkValidity(); + } - void prepend(const T& item) - { - DequeNode<T>* newNode = new DequeNode<T>(item); - newNode->m_next = m_first; - m_first = newNode; - if (!m_last) - m_last = newNode; - ++m_size; + template<typename T> + inline Deque<T>::Deque(const Deque<T>& other) + : m_start(other.m_start) + , m_end(other.m_end) + , m_buffer(other.m_buffer.capacity()) +#ifndef NDEBUG + , m_iterators(0) +#endif + { + const T* otherBuffer = other.m_buffer.buffer(); + if (m_start <= m_end) + TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start); + else { + TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer()); + TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start); } + } - T& first() { ASSERT(m_first); return m_first->m_value; } - const T& first() const { ASSERT(m_first); return m_first->m_value; } - T& last() { ASSERT(m_last); return m_last->m_value; } - const T& last() const { ASSERT(m_last); return m_last->m_value; } - - void removeFirst() - { - ASSERT(m_first); - if (DequeNode<T>* n = m_first) { - m_first = m_first->m_next; - if (n == m_last) - m_last = 0; - - m_size--; - delete n; - } + template<typename T> + void deleteAllValues(const Deque<T>& collection) + { + typedef typename Deque<T>::const_iterator iterator; + iterator end = collection.end(); + for (iterator it = collection.begin(); it != end; ++it) + delete *it; + } + + template<typename T> + inline Deque<T>& Deque<T>::operator=(const Deque<T>& other) + { + Deque<T> copy(other); + swap(copy); + return *this; + } + + template<typename T> + inline void Deque<T>::destroyAll() + { + if (m_start <= m_end) + TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end); + else { + TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end); + TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity()); + } + } + + template<typename T> + inline Deque<T>::~Deque() + { + checkValidity(); + invalidateIterators(); + destroyAll(); + } + + template <typename T> + inline void Deque<T>::swap(Deque<T>& other) + { + checkValidity(); + other.checkValidity(); + invalidateIterators(); + std::swap(m_start, other.m_start); + std::swap(m_end, other.m_end); + m_buffer.swap(other.m_buffer); + checkValidity(); + other.checkValidity(); + } + + template <typename T> + inline void Deque<T>::clear() + { + checkValidity(); + invalidateIterators(); + destroyAll(); + m_start = 0; + m_end = 0; + checkValidity(); + } + + template<typename T> + inline void Deque<T>::expandCapacityIfNeeded() + { + if (m_start) { + if (m_end + 1 != m_start) + return; + } else if (m_end) { + if (m_end != m_buffer.capacity() - 1) + return; + } else if (m_buffer.capacity()) + return; + + expandCapacity(); + } + + template<typename T> + void Deque<T>::expandCapacity() + { + checkValidity(); + size_t oldCapacity = m_buffer.capacity(); + size_t newCapacity = max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1); + T* oldBuffer = m_buffer.buffer(); + m_buffer.allocateBuffer(newCapacity); + if (m_start <= m_end) + TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start); + else { + TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer()); + size_t newStart = newCapacity - (oldCapacity - m_start); + TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart); + m_start = newStart; } + m_buffer.deallocateBuffer(oldBuffer); + checkValidity(); + } - void clear() - { - DequeNode<T>* n = m_first; - m_first = 0; - m_last = 0; - m_size = 0; - while (n) { - DequeNode<T>* next = n->m_next; - delete n; - n = next; + template<typename T> template<typename U> + inline void Deque<T>::append(const U& value) + { + checkValidity(); + expandCapacityIfNeeded(); + new (&m_buffer.buffer()[m_end]) T(value); + if (m_end == m_buffer.capacity() - 1) + m_end = 0; + else + ++m_end; + checkValidity(); + } + + template<typename T> template<typename U> + inline void Deque<T>::prepend(const U& value) + { + checkValidity(); + expandCapacityIfNeeded(); + if (!m_start) + m_start = m_buffer.capacity() - 1; + else + --m_start; + new (&m_buffer.buffer()[m_start]) T(value); + checkValidity(); + } + + template<typename T> + inline void Deque<T>::removeFirst() + { + checkValidity(); + invalidateIterators(); + ASSERT(!isEmpty()); + TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]); + if (m_start == m_buffer.capacity() - 1) + m_start = 0; + else + ++m_start; + checkValidity(); + } + +#ifdef NDEBUG + template<typename T> inline void DequeIteratorBase<T>::checkValidity() const { } + template<typename T> inline void DequeIteratorBase<T>::checkValidity(const DequeIteratorBase<T>&) const { } + template<typename T> inline void DequeIteratorBase<T>::addToIteratorsList() { } +#else + template<typename T> + void DequeIteratorBase<T>::checkValidity() const + { + ASSERT(m_deque); + m_deque->checkIndexValidity(m_index); + } + + template<typename T> + void DequeIteratorBase<T>::checkValidity(const Base& other) const + { + checkValidity(); + other.checkValidity(); + ASSERT(m_deque == other.m_deque); + } + + template<typename T> + void DequeIteratorBase<T>::addToIteratorsList() + { + if (!m_deque) + m_next = 0; + else { + m_next = m_deque->m_iterators; + m_deque->m_iterators = this; + if (m_next) + m_next->m_previous = this; + } + m_previous = 0; + } +#endif + + template<typename T> + inline DequeIteratorBase<T>::DequeIteratorBase() + : m_deque(0) + { + } + + template<typename T> + inline DequeIteratorBase<T>::DequeIteratorBase(const Deque<T>* deque, size_t index) + : m_deque(const_cast<Deque<T>*>(deque)) + , m_index(index) + { + addToIteratorsList(); + checkValidity(); + } + + template<typename T> + inline DequeIteratorBase<T>::DequeIteratorBase(const Base& other) + : m_deque(other.m_deque) + , m_index(other.m_index) + { + addToIteratorsList(); + checkValidity(); + } + + template<typename T> + inline DequeIteratorBase<T>::~DequeIteratorBase() + { +#ifndef NDEBUG + // Delete iterator from doubly-linked list of iterators. + if (!m_deque) { + ASSERT(!m_next); + ASSERT(!m_previous); + } else { + if (m_next) { + ASSERT(m_next->m_previous == this); + m_next->m_previous = m_previous; + } + if (m_previous) { + ASSERT(m_deque->m_iterators != this); + ASSERT(m_previous->m_next == this); + m_previous->m_next = m_next; + } else { + ASSERT(m_deque->m_iterators == this); + m_deque->m_iterators = m_next; } } + m_deque = 0; + m_next = 0; + m_previous = 0; +#endif + } - private: - size_t m_size; - DequeNode<T>* m_first; - DequeNode<T>* m_last; + template<typename T> + inline bool DequeIteratorBase<T>::isEqual(const Base& other) const + { + checkValidity(other); + return m_index == other.m_index; + } - }; + template<typename T> + inline void DequeIteratorBase<T>::increment() + { + checkValidity(); + ASSERT(m_index != m_deque->m_end); + ASSERT(m_deque->m_buffer.capacity()); + if (m_index == m_deque->m_buffer.capacity() - 1) + m_index = 0; + else + ++m_index; + checkValidity(); + } + + template<typename T> + inline void DequeIteratorBase<T>::decrement() + { + checkValidity(); + ASSERT(m_index != m_deque->m_start); + ASSERT(m_deque->m_buffer.capacity()); + if (!m_index) + m_index = m_deque->m_buffer.capacity() - 1; + else + --m_index; + checkValidity(); + } + + template<typename T> + inline T* DequeIteratorBase<T>::after() const + { + checkValidity(); + ASSERT(m_index != m_deque->m_end); + return &m_deque->m_buffer.buffer()[m_index]; + } + + template<typename T> + inline T* DequeIteratorBase<T>::before() const + { + checkValidity(); + ASSERT(m_index != m_deque->m_start); + if (!m_index) + return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1]; + return &m_deque->m_buffer.buffer()[m_index - 1]; + } } // namespace WTF |