| /* |
| * Copyright (C) 2007, 2008 Apple Inc. All rights reserved. |
| * Copyright (C) 2009 Google Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of |
| * its contributors may be used to endorse or promote products derived |
| * from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
| * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
| * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY |
| * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
| * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
| * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (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 |
| |
| // FIXME: Could move what Vector and Deque share into a separate file. |
| // Deque doesn't actually use Vector. |
| |
| #include "wtf/Vector.h" |
| #include <iterator> |
| |
| namespace WTF { |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| class DequeIteratorBase; |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| class DequeIterator; |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| class DequeConstIterator; |
| |
| template <typename T, |
| size_t inlineCapacity = 0, |
| typename Allocator = PartitionAllocator> |
| class Deque : public ConditionalDestructor<Deque<T, INLINE_CAPACITY, Allocator>, |
| (INLINE_CAPACITY == 0) && |
| Allocator::isGarbageCollected> { |
| WTF_USE_ALLOCATOR(Deque, Allocator); |
| |
| public: |
| typedef DequeIterator<T, inlineCapacity, Allocator> iterator; |
| typedef DequeConstIterator<T, inlineCapacity, Allocator> const_iterator; |
| typedef std::reverse_iterator<iterator> reverse_iterator; |
| typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
| |
| Deque(); |
| Deque(const Deque&); |
| Deque& operator=(const Deque&); |
| Deque(Deque&&); |
| Deque& operator=(Deque&&); |
| |
| void finalize(); |
| void finalizeGarbageCollectedObject() { finalize(); } |
| |
| void swap(Deque&); |
| |
| 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(end()); } |
| reverse_iterator rend() { return reverse_iterator(begin()); } |
| const_reverse_iterator rbegin() const { |
| return const_reverse_iterator(end()); |
| } |
| const_reverse_iterator rend() const { |
| return const_reverse_iterator(begin()); |
| } |
| |
| 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]; |
| } |
| T takeFirst(); |
| |
| T& last() { |
| ASSERT(m_start != m_end); |
| return *(--end()); |
| } |
| const T& last() const { |
| ASSERT(m_start != m_end); |
| return *(--end()); |
| } |
| T takeLast(); |
| |
| T& at(size_t i) { |
| RELEASE_ASSERT(i < size()); |
| size_t right = m_buffer.capacity() - m_start; |
| return i < right ? m_buffer.buffer()[m_start + i] |
| : m_buffer.buffer()[i - right]; |
| } |
| const T& at(size_t i) const { |
| RELEASE_ASSERT(i < size()); |
| size_t right = m_buffer.capacity() - m_start; |
| return i < right ? m_buffer.buffer()[m_start + i] |
| : m_buffer.buffer()[i - right]; |
| } |
| |
| T& operator[](size_t i) { return at(i); } |
| const T& operator[](size_t i) const { return at(i); } |
| |
| template <typename U> |
| void append(U&&); |
| template <typename U> |
| void prepend(U&&); |
| void removeFirst(); |
| void removeLast(); |
| void remove(iterator&); |
| void remove(const_iterator&); |
| |
| void clear(); |
| |
| template <typename VisitorDispatcher> |
| void trace(VisitorDispatcher); |
| |
| static_assert(!std::is_polymorphic<T>::value || |
| !VectorTraits<T>::canInitializeWithMemset, |
| "Cannot initialize with memset if there is a vtable"); |
| static_assert(Allocator::isGarbageCollected || |
| !AllowsOnlyPlacementNew<T>::value || |
| !IsTraceable<T>::value, |
| "Cannot put DISALLOW_NEW_EXCEPT_PLACEMENT_NEW objects that " |
| "have trace methods into an off-heap Deque"); |
| static_assert(Allocator::isGarbageCollected || |
| !IsPointerToGarbageCollectedType<T>::value, |
| "Cannot put raw pointers to garbage-collected classes into a " |
| "Deque. Use HeapDeque<Member<T>> instead."); |
| |
| private: |
| friend class DequeIteratorBase<T, inlineCapacity, Allocator>; |
| |
| class BackingBuffer : public VectorBuffer<T, INLINE_CAPACITY, Allocator> { |
| WTF_MAKE_NONCOPYABLE(BackingBuffer); |
| |
| private: |
| using Base = VectorBuffer<T, INLINE_CAPACITY, Allocator>; |
| using Base::m_size; |
| |
| public: |
| BackingBuffer() : Base() {} |
| explicit BackingBuffer(size_t capacity) : Base(capacity) {} |
| |
| void setSize(size_t size) { m_size = size; } |
| }; |
| |
| typedef VectorTypeOperations<T> TypeOperations; |
| typedef DequeIteratorBase<T, inlineCapacity, Allocator> IteratorBase; |
| |
| void remove(size_t position); |
| void destroyAll(); |
| void expandCapacityIfNeeded(); |
| void expandCapacity(); |
| |
| BackingBuffer m_buffer; |
| unsigned m_start; |
| unsigned m_end; |
| }; |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| class DequeIteratorBase { |
| DISALLOW_NEW(); |
| |
| protected: |
| DequeIteratorBase(); |
| DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>*, size_t); |
| DequeIteratorBase(const DequeIteratorBase&); |
| DequeIteratorBase& operator=(const DequeIteratorBase<T, 0, Allocator>&); |
| ~DequeIteratorBase(); |
| |
| void assign(const DequeIteratorBase& other) { *this = other; } |
| |
| void increment(); |
| void decrement(); |
| |
| T* before() const; |
| T* after() const; |
| |
| bool isEqual(const DequeIteratorBase&) const; |
| |
| private: |
| Deque<T, inlineCapacity, Allocator>* m_deque; |
| unsigned m_index; |
| |
| friend class Deque<T, inlineCapacity, Allocator>; |
| }; |
| |
| template <typename T, |
| size_t inlineCapacity = 0, |
| typename Allocator = PartitionAllocator> |
| class DequeIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> { |
| private: |
| typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base; |
| typedef DequeIterator<T, inlineCapacity, Allocator> Iterator; |
| |
| public: |
| typedef ptrdiff_t difference_type; |
| typedef T value_type; |
| typedef T* pointer; |
| typedef T& reference; |
| typedef std::bidirectional_iterator_tag iterator_category; |
| |
| DequeIterator(Deque<T, inlineCapacity, Allocator>* 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, |
| size_t inlineCapacity = 0, |
| typename Allocator = PartitionAllocator> |
| class DequeConstIterator |
| : public DequeIteratorBase<T, inlineCapacity, Allocator> { |
| private: |
| typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base; |
| typedef DequeConstIterator<T, inlineCapacity, Allocator> Iterator; |
| typedef DequeIterator<T, inlineCapacity, Allocator> NonConstIterator; |
| |
| public: |
| typedef ptrdiff_t difference_type; |
| typedef T value_type; |
| typedef const T* pointer; |
| typedef const T& reference; |
| typedef std::bidirectional_iterator_tag iterator_category; |
| |
| DequeConstIterator(const Deque<T, inlineCapacity, Allocator>* 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, size_t inlineCapacity, typename Allocator> |
| inline Deque<T, inlineCapacity, Allocator>::Deque() : m_start(0), m_end(0) {} |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline Deque<T, inlineCapacity, Allocator>::Deque(const Deque& other) |
| : m_buffer(other.m_buffer.capacity()), |
| m_start(other.m_start), |
| m_end(other.m_end) { |
| 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); |
| } |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline Deque<T, inlineCapacity, Allocator>& |
| Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other) { |
| Deque<T> copy(other); |
| swap(copy); |
| return *this; |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline Deque<T, inlineCapacity, Allocator>::Deque(Deque&& other) |
| : m_start(0), m_end(0) { |
| swap(other); |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline Deque<T, inlineCapacity, Allocator>& |
| Deque<T, inlineCapacity, Allocator>::operator=(Deque&& other) { |
| swap(other); |
| return *this; |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void Deque<T, inlineCapacity, Allocator>::destroyAll() { |
| if (m_start <= m_end) { |
| TypeOperations::destruct(m_buffer.buffer() + m_start, |
| m_buffer.buffer() + m_end); |
| m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, |
| m_buffer.buffer() + m_end); |
| } else { |
| TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end); |
| m_buffer.clearUnusedSlots(m_buffer.buffer(), m_buffer.buffer() + m_end); |
| TypeOperations::destruct(m_buffer.buffer() + m_start, |
| m_buffer.buffer() + m_buffer.capacity()); |
| m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, |
| m_buffer.buffer() + m_buffer.capacity()); |
| } |
| } |
| |
| // Off-GC-heap deques: Destructor should be called. |
| // On-GC-heap deques: Destructor should be called for inline buffers (if any) |
| // but destructor shouldn't be called for vector backing since it is managed by |
| // the traced GC heap. |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void Deque<T, inlineCapacity, Allocator>::finalize() { |
| if (!INLINE_CAPACITY && !m_buffer.buffer()) |
| return; |
| if (!isEmpty() && |
| !(Allocator::isGarbageCollected && m_buffer.hasOutOfLineBuffer())) |
| destroyAll(); |
| |
| m_buffer.destruct(); |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void Deque<T, inlineCapacity, Allocator>::swap(Deque& other) { |
| typename BackingBuffer::OffsetRange thisHole; |
| if (m_start <= m_end) { |
| m_buffer.setSize(m_end); |
| thisHole.begin = 0; |
| thisHole.end = m_start; |
| } else { |
| m_buffer.setSize(m_buffer.capacity()); |
| thisHole.begin = m_end; |
| thisHole.end = m_start; |
| } |
| typename BackingBuffer::OffsetRange otherHole; |
| if (other.m_start <= other.m_end) { |
| other.m_buffer.setSize(other.m_end); |
| otherHole.begin = 0; |
| otherHole.end = other.m_start; |
| } else { |
| other.m_buffer.setSize(other.m_buffer.capacity()); |
| otherHole.begin = other.m_end; |
| otherHole.end = other.m_start; |
| } |
| |
| m_buffer.swapVectorBuffer(other.m_buffer, thisHole, otherHole); |
| |
| std::swap(m_start, other.m_start); |
| std::swap(m_end, other.m_end); |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void Deque<T, inlineCapacity, Allocator>::clear() { |
| destroyAll(); |
| m_start = 0; |
| m_end = 0; |
| m_buffer.deallocateBuffer(m_buffer.buffer()); |
| m_buffer.resetBufferPointer(); |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void Deque<T, inlineCapacity, Allocator>::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, size_t inlineCapacity, typename Allocator> |
| void Deque<T, inlineCapacity, Allocator>::expandCapacity() { |
| size_t oldCapacity = m_buffer.capacity(); |
| T* oldBuffer = m_buffer.buffer(); |
| size_t newCapacity = |
| std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1); |
| if (m_buffer.expandBuffer(newCapacity)) { |
| if (m_start <= m_end) { |
| // No adjustments to be done. |
| } else { |
| size_t newStart = m_buffer.capacity() - (oldCapacity - m_start); |
| TypeOperations::moveOverlapping(oldBuffer + m_start, |
| oldBuffer + oldCapacity, |
| m_buffer.buffer() + newStart); |
| m_buffer.clearUnusedSlots(oldBuffer + m_start, |
| oldBuffer + std::min(oldCapacity, newStart)); |
| m_start = newStart; |
| } |
| return; |
| } |
| m_buffer.allocateBuffer(newCapacity); |
| if (m_start <= m_end) { |
| TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, |
| m_buffer.buffer() + m_start); |
| m_buffer.clearUnusedSlots(oldBuffer + m_start, oldBuffer + m_end); |
| } else { |
| TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer()); |
| m_buffer.clearUnusedSlots(oldBuffer, oldBuffer + m_end); |
| size_t newStart = m_buffer.capacity() - (oldCapacity - m_start); |
| TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, |
| m_buffer.buffer() + newStart); |
| m_buffer.clearUnusedSlots(oldBuffer + m_start, oldBuffer + oldCapacity); |
| m_start = newStart; |
| } |
| m_buffer.deallocateBuffer(oldBuffer); |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline T Deque<T, inlineCapacity, Allocator>::takeFirst() { |
| T oldFirst = std::move(first()); |
| removeFirst(); |
| return oldFirst; |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline T Deque<T, inlineCapacity, Allocator>::takeLast() { |
| T oldLast = std::move(last()); |
| removeLast(); |
| return oldLast; |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| template <typename U> |
| inline void Deque<T, inlineCapacity, Allocator>::append(U&& value) { |
| expandCapacityIfNeeded(); |
| new (NotNull, &m_buffer.buffer()[m_end]) T(std::forward<U>(value)); |
| if (m_end == m_buffer.capacity() - 1) |
| m_end = 0; |
| else |
| ++m_end; |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| template <typename U> |
| inline void Deque<T, inlineCapacity, Allocator>::prepend(U&& value) { |
| expandCapacityIfNeeded(); |
| if (!m_start) |
| m_start = m_buffer.capacity() - 1; |
| else |
| --m_start; |
| new (NotNull, &m_buffer.buffer()[m_start]) T(std::forward<U>(value)); |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void Deque<T, inlineCapacity, Allocator>::removeFirst() { |
| ASSERT(!isEmpty()); |
| TypeOperations::destruct(&m_buffer.buffer()[m_start], |
| &m_buffer.buffer()[m_start + 1]); |
| m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_start], |
| &m_buffer.buffer()[m_start + 1]); |
| if (m_start == m_buffer.capacity() - 1) |
| m_start = 0; |
| else |
| ++m_start; |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void Deque<T, inlineCapacity, Allocator>::removeLast() { |
| ASSERT(!isEmpty()); |
| if (!m_end) |
| m_end = m_buffer.capacity() - 1; |
| else |
| --m_end; |
| TypeOperations::destruct(&m_buffer.buffer()[m_end], |
| &m_buffer.buffer()[m_end + 1]); |
| m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_end], |
| &m_buffer.buffer()[m_end + 1]); |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void Deque<T, inlineCapacity, Allocator>::remove(iterator& it) { |
| remove(it.m_index); |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void Deque<T, inlineCapacity, Allocator>::remove(const_iterator& it) { |
| remove(it.m_index); |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void Deque<T, inlineCapacity, Allocator>::remove(size_t position) { |
| if (position == m_end) |
| return; |
| |
| T* buffer = m_buffer.buffer(); |
| TypeOperations::destruct(&buffer[position], &buffer[position + 1]); |
| |
| // Find which segment of the circular buffer contained the remove element, |
| // and only move elements in that part. |
| if (position >= m_start) { |
| TypeOperations::moveOverlapping(buffer + m_start, buffer + position, |
| buffer + m_start + 1); |
| m_buffer.clearUnusedSlots(buffer + m_start, buffer + m_start + 1); |
| m_start = (m_start + 1) % m_buffer.capacity(); |
| } else { |
| TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, |
| buffer + position); |
| m_buffer.clearUnusedSlots(buffer + m_end - 1, buffer + m_end); |
| m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity(); |
| } |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase() |
| : m_deque(0) {} |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase( |
| const Deque<T, inlineCapacity, Allocator>* deque, |
| size_t index) |
| : m_deque(const_cast<Deque<T, inlineCapacity, Allocator>*>(deque)), |
| m_index(index) {} |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase( |
| const DequeIteratorBase& other) |
| : m_deque(other.m_deque), m_index(other.m_index) {} |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline DequeIteratorBase<T, inlineCapacity, Allocator>& |
| DequeIteratorBase<T, inlineCapacity, Allocator>::operator=( |
| const DequeIteratorBase<T, 0, Allocator>& other) { |
| m_deque = other.m_deque; |
| m_index = other.m_index; |
| return *this; |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline DequeIteratorBase<T, inlineCapacity, Allocator>::~DequeIteratorBase() {} |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline bool DequeIteratorBase<T, inlineCapacity, Allocator>::isEqual( |
| const DequeIteratorBase& other) const { |
| return m_index == other.m_index; |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void DequeIteratorBase<T, inlineCapacity, Allocator>::increment() { |
| 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; |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void DequeIteratorBase<T, inlineCapacity, Allocator>::decrement() { |
| 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; |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::after() const { |
| RELEASE_ASSERT(m_index != m_deque->m_end); |
| return &m_deque->m_buffer.buffer()[m_index]; |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::before() const { |
| RELEASE_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]; |
| } |
| |
| // This is only called if the allocator is a HeapAllocator. It is used when |
| // visiting during a tracing GC. |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| template <typename VisitorDispatcher> |
| void Deque<T, inlineCapacity, Allocator>::trace(VisitorDispatcher visitor) { |
| ASSERT(Allocator::isGarbageCollected); // Garbage collector must be enabled. |
| const T* bufferBegin = m_buffer.buffer(); |
| const T* end = bufferBegin + m_end; |
| if (IsTraceableInCollectionTrait<VectorTraits<T>>::value) { |
| if (m_start <= m_end) { |
| for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != end; |
| bufferEntry++) |
| Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>( |
| visitor, *const_cast<T*>(bufferEntry)); |
| } else { |
| for (const T* bufferEntry = bufferBegin; bufferEntry != end; |
| bufferEntry++) |
| Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>( |
| visitor, *const_cast<T*>(bufferEntry)); |
| const T* bufferEnd = m_buffer.buffer() + m_buffer.capacity(); |
| for (const T* bufferEntry = bufferBegin + m_start; |
| bufferEntry != bufferEnd; bufferEntry++) |
| Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>( |
| visitor, *const_cast<T*>(bufferEntry)); |
| } |
| } |
| if (m_buffer.hasOutOfLineBuffer()) |
| Allocator::markNoTracing(visitor, m_buffer.buffer()); |
| } |
| |
| template <typename T, size_t inlineCapacity, typename Allocator> |
| inline void swap(Deque<T, inlineCapacity, Allocator>& a, |
| Deque<T, inlineCapacity, Allocator>& b) { |
| a.swap(b); |
| } |
| |
| } // namespace WTF |
| |
| using WTF::Deque; |
| |
| #endif // WTF_Deque_h |