18e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 28e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Copyright (C) 2007, 2008 Apple Inc. All rights reserved. 38f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian * Copyright (C) 2009 Google Inc. All rights reserved. 48e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Redistribution and use in source and binary forms, with or without 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * modification, are permitted provided that the following conditions 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * are met: 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 98e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 1. Redistributions of source code must retain the above copyright 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * notice, this list of conditions and the following disclaimer. 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * notice, this list of conditions and the following disclaimer in the 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * documentation and/or other materials provided with the distribution. 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of 158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * its contributors may be used to endorse or promote products derived 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * from this software without specific prior written permission. 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project */ 298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef WTF_Deque_h 318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define WTF_Deque_h 328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// FIXME: Could move what Vector and Deque share into a separate file. 348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// Deque doesn't actually use Vector. 358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "Vector.h" 378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectnamespace WTF { 398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> class DequeIteratorBase; 4181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> class DequeIterator; 4281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> class DequeConstIterator; 4381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> class DequeReverseIterator; 4481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> class DequeConstReverseIterator; 458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity = 0> 47ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch class Deque { 48ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch WTF_MAKE_FAST_ALLOCATED; 498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 5081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeIterator<T, inlineCapacity> iterator; 5181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeConstIterator<T, inlineCapacity> const_iterator; 5281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeReverseIterator<T, inlineCapacity> reverse_iterator; 5381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeConstReverseIterator<T, inlineCapacity> const_reverse_iterator; 548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Deque(); 5681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch Deque(const Deque<T, inlineCapacity>&); 5781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch Deque& operator=(const Deque<T, inlineCapacity>&); 588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ~Deque(); 598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void swap(Deque<T, inlineCapacity>&); 618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; } 638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool isEmpty() const { return m_start == m_end; } 648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator begin() { return iterator(this, m_start); } 668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator end() { return iterator(this, m_end); } 678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator begin() const { return const_iterator(this, m_start); } 688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator end() const { return const_iterator(this, m_end); } 698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project reverse_iterator rbegin() { return reverse_iterator(this, m_end); } 708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project reverse_iterator rend() { return reverse_iterator(this, m_start); } 718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_reverse_iterator rbegin() const { return const_reverse_iterator(this, m_end); } 728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_reverse_iterator rend() const { return const_reverse_iterator(this, m_start); } 738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; } 758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; } 76545e470e52f0ac6a3a072bf559c796b42c6066b6Ben Murdoch T takeFirst(); 778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename U> void append(const U&); 798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename U> void prepend(const U&); 808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void removeFirst(); 818f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian void remove(iterator&); 828f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian void remove(const_iterator&); 838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void clear(); 858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 868f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian template<typename Predicate> 878f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian iterator findIf(Predicate&); 888f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 9081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch friend class DequeIteratorBase<T, inlineCapacity>; 918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef VectorBuffer<T, inlineCapacity> Buffer; 938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef VectorTypeOperations<T> TypeOperations; 9481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeIteratorBase<T, inlineCapacity> IteratorBase; 958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 968f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian void remove(size_t position); 978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void invalidateIterators(); 988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void destroyAll(); 998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void checkValidity() const; 1008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void checkIndexValidity(size_t) const; 1018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void expandCapacityIfNeeded(); 1028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void expandCapacity(); 1038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t m_start; 1058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t m_end; 1068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Buffer m_buffer; 1078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef NDEBUG 1088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project mutable IteratorBase* m_iterators; 1098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 1108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 1118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity = 0> 1138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project class DequeIteratorBase { 1148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 11581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeIteratorBase<T, inlineCapacity> Base; 1168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project protected: 1188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeIteratorBase(); 11981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch DequeIteratorBase(const Deque<T, inlineCapacity>*, size_t); 1208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeIteratorBase(const Base&); 1218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Base& operator=(const Base&); 1228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ~DequeIteratorBase(); 1238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void assign(const Base& other) { *this = other; } 1258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void increment(); 1278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void decrement(); 1288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project T* before() const; 1308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project T* after() const; 1318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool isEqual(const Base&) const; 1338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 1358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void addToIteratorsList(); 1368f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian void removeFromIteratorsList(); 1378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void checkValidity() const; 1388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void checkValidity(const Base&) const; 1398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 14081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch Deque<T, inlineCapacity>* m_deque; 1418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t m_index; 1428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 14381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch friend class Deque<T, inlineCapacity>; 1448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef NDEBUG 1468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project mutable DequeIteratorBase* m_next; 1478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project mutable DequeIteratorBase* m_previous; 1488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 1498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 1508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 15181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity = 0> 15281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch class DequeIterator : public DequeIteratorBase<T, inlineCapacity> { 1538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 15481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeIteratorBase<T, inlineCapacity> Base; 15581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeIterator<T, inlineCapacity> Iterator; 1568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 15881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch DequeIterator(Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { } 1598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeIterator(const Iterator& other) : Base(other) { } 1618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; } 1628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project T& operator*() const { return *Base::after(); } 1648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project T* operator->() const { return Base::after(); } 1658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator==(const Iterator& other) const { return Base::isEqual(other); } 1678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator!=(const Iterator& other) const { return !Base::isEqual(other); } 1688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Iterator& operator++() { Base::increment(); return *this; } 1708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix ++ intentionally omitted 1718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Iterator& operator--() { Base::decrement(); return *this; } 1728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix -- intentionally omitted 1738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 1748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 17581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity = 0> 17681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity> { 1778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 17881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeIteratorBase<T, inlineCapacity> Base; 17981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeConstIterator<T, inlineCapacity> Iterator; 18081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeIterator<T, inlineCapacity> NonConstIterator; 1818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 18381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch DequeConstIterator(const Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { } 1848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeConstIterator(const Iterator& other) : Base(other) { } 1868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeConstIterator(const NonConstIterator& other) : Base(other) { } 1878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; } 1888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; } 1898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const T& operator*() const { return *Base::after(); } 1918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const T* operator->() const { return Base::after(); } 1928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator==(const Iterator& other) const { return Base::isEqual(other); } 1948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator!=(const Iterator& other) const { return !Base::isEqual(other); } 1958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Iterator& operator++() { Base::increment(); return *this; } 1978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix ++ intentionally omitted 1988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Iterator& operator--() { Base::decrement(); return *this; } 1998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix -- intentionally omitted 2008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 20281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity = 0> 20381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch class DequeReverseIterator : public DequeIteratorBase<T, inlineCapacity> { 2048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 20581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeIteratorBase<T, inlineCapacity> Base; 20681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeReverseIterator<T, inlineCapacity> Iterator; 2078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 20981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch DequeReverseIterator(const Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { } 2108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeReverseIterator(const Iterator& other) : Base(other) { } 2128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; } 2138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project T& operator*() const { return *Base::before(); } 2158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project T* operator->() const { return Base::before(); } 2168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator==(const Iterator& other) const { return Base::isEqual(other); } 2188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator!=(const Iterator& other) const { return !Base::isEqual(other); } 2198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Iterator& operator++() { Base::decrement(); return *this; } 2218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix ++ intentionally omitted 2228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Iterator& operator--() { Base::increment(); return *this; } 2238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix -- intentionally omitted 2248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 22681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity = 0> 22781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch class DequeConstReverseIterator : public DequeIteratorBase<T, inlineCapacity> { 2288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 22981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeIteratorBase<T, inlineCapacity> Base; 23081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeConstReverseIterator<T, inlineCapacity> Iterator; 23181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef DequeReverseIterator<T, inlineCapacity> NonConstIterator; 2328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 23481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch DequeConstReverseIterator(const Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { } 2358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeConstReverseIterator(const Iterator& other) : Base(other) { } 2378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeConstReverseIterator(const NonConstIterator& other) : Base(other) { } 2388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeConstReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; } 2398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project DequeConstReverseIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; } 2408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const T& operator*() const { return *Base::before(); } 2428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const T* operator->() const { return Base::before(); } 2438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator==(const Iterator& other) const { return Base::isEqual(other); } 2458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator!=(const Iterator& other) const { return !Base::isEqual(other); } 2468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Iterator& operator++() { Base::decrement(); return *this; } 2488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix ++ intentionally omitted 2498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Iterator& operator--() { Base::increment(); return *this; } 2508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix -- intentionally omitted 2518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifdef NDEBUG 25481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkValidity() const { } 25581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkIndexValidity(size_t) const { } 25681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::invalidateIterators() { } 2578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else 25881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 25981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void Deque<T, inlineCapacity>::checkValidity() const 2608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 26181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch // In this implementation a capacity of 1 would confuse append() and 26281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch // other places that assume the index after capacity - 1 is 0. 26381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ASSERT(m_buffer.capacity() != 1); 26481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 2658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_buffer.capacity()) { 2668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!m_start); 2678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!m_end); 2688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 2698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_start < m_buffer.capacity()); 2708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_end < m_buffer.capacity()); 2718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 27481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 27581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void Deque<T, inlineCapacity>::checkIndexValidity(size_t index) const 2768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(index <= m_buffer.capacity()); 2788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_start <= m_end) { 2798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(index >= m_start); 2808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(index <= m_end); 2818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 2828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(index >= m_start || index <= m_end); 2838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 28681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 28781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void Deque<T, inlineCapacity>::invalidateIterators() 2888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project IteratorBase* next; 2908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (IteratorBase* p = m_iterators; p; p = next) { 2918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project next = p->m_next; 2928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p->m_deque = 0; 2938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p->m_next = 0; 2948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p->m_previous = 0; 2958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_iterators = 0; 2978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 2998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 30081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 30181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline Deque<T, inlineCapacity>::Deque() 3028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_start(0) 3038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_end(0) 3048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef NDEBUG 3058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_iterators(0) 3068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 3078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 3098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 31181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 31281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline Deque<T, inlineCapacity>::Deque(const Deque<T, inlineCapacity>& other) 3138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_start(other.m_start) 3148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_end(other.m_end) 3158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_buffer(other.m_buffer.capacity()) 3168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef NDEBUG 3178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_iterators(0) 3188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 3198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const T* otherBuffer = other.m_buffer.buffer(); 3218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_start <= m_end) 3228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start); 3238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else { 3248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer()); 3258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start); 3268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 32981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 33081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void deleteAllValues(const Deque<T, inlineCapacity>& collection) 3318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 33281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef typename Deque<T, inlineCapacity>::const_iterator iterator; 3338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator end = collection.end(); 3348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (iterator it = collection.begin(); it != end; ++it) 3358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project delete *it; 3368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 33881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 33981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline Deque<T, inlineCapacity>& Deque<T, inlineCapacity>::operator=(const Deque<T, inlineCapacity>& other) 3408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 34181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch // FIXME: This is inefficient if we're using an inline buffer and T is 34281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch // expensive to copy since it will copy the buffer twice instead of once. 3438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Deque<T> copy(other); 3448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project swap(copy); 3458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return *this; 3468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 34881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 34981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void Deque<T, inlineCapacity>::destroyAll() 3508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_start <= m_end) 3528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end); 3538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else { 3548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end); 3558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity()); 3568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 35981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 36081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline Deque<T, inlineCapacity>::~Deque() 3618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 3638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invalidateIterators(); 3648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project destroyAll(); 3658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 36781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 36881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void Deque<T, inlineCapacity>::swap(Deque<T, inlineCapacity>& other) 3698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 3718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project other.checkValidity(); 3728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invalidateIterators(); 3738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project std::swap(m_start, other.m_start); 3748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project std::swap(m_end, other.m_end); 3758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_buffer.swap(other.m_buffer); 3768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 3778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project other.checkValidity(); 3788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 38081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 38181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void Deque<T, inlineCapacity>::clear() 3828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 3848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invalidateIterators(); 3858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project destroyAll(); 3868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_start = 0; 3878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_end = 0; 3888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 3898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 39181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 3928f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian template<typename Predicate> 39381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline DequeIterator<T, inlineCapacity> Deque<T, inlineCapacity>::findIf(Predicate& predicate) 3948f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian { 3958f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian iterator end_iterator = end(); 3968f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian for (iterator it = begin(); it != end_iterator; ++it) { 3978f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian if (predicate(*it)) 3988f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian return it; 3998f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 4008f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian return end_iterator; 4018f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 4028f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 40381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 40481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void Deque<T, inlineCapacity>::expandCapacityIfNeeded() 4058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_start) { 4078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_end + 1 != m_start) 4088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 4098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else if (m_end) { 4108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_end != m_buffer.capacity() - 1) 4118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 4128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else if (m_buffer.capacity()) 4138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 4148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project expandCapacity(); 4168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 41881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 41981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void Deque<T, inlineCapacity>::expandCapacity() 4208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 4228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t oldCapacity = m_buffer.capacity(); 4238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t newCapacity = max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1); 4248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project T* oldBuffer = m_buffer.buffer(); 4258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_buffer.allocateBuffer(newCapacity); 4268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_start <= m_end) 4278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start); 4288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else { 4298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer()); 4308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t newStart = newCapacity - (oldCapacity - m_start); 4318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart); 4328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_start = newStart; 4338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_buffer.deallocateBuffer(oldBuffer); 4358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 4368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 43881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 43981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline T Deque<T, inlineCapacity>::takeFirst() 440545e470e52f0ac6a3a072bf559c796b42c6066b6Ben Murdoch { 441545e470e52f0ac6a3a072bf559c796b42c6066b6Ben Murdoch T oldFirst = first(); 442545e470e52f0ac6a3a072bf559c796b42c6066b6Ben Murdoch removeFirst(); 443545e470e52f0ac6a3a072bf559c796b42c6066b6Ben Murdoch return oldFirst; 444545e470e52f0ac6a3a072bf559c796b42c6066b6Ben Murdoch } 445545e470e52f0ac6a3a072bf559c796b42c6066b6Ben Murdoch 44681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> template<typename U> 44781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void Deque<T, inlineCapacity>::append(const U& value) 4488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 4508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project expandCapacityIfNeeded(); 4518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project new (&m_buffer.buffer()[m_end]) T(value); 4528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_end == m_buffer.capacity() - 1) 4538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_end = 0; 4548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 4558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++m_end; 4568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 4578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 45981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> template<typename U> 46081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void Deque<T, inlineCapacity>::prepend(const U& value) 4618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 4638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project expandCapacityIfNeeded(); 4648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_start) 4658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_start = m_buffer.capacity() - 1; 4668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 4678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project --m_start; 4688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project new (&m_buffer.buffer()[m_start]) T(value); 4698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 4708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 47281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 47381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void Deque<T, inlineCapacity>::removeFirst() 4748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 4768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invalidateIterators(); 4778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!isEmpty()); 4788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]); 4798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_start == m_buffer.capacity() - 1) 4808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_start = 0; 4818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 4828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++m_start; 4838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 4848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 48681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 48781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void Deque<T, inlineCapacity>::remove(iterator& it) 4888f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian { 4898f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian it.checkValidity(); 4908f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian remove(it.m_index); 4918f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 4928f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 49381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 49481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void Deque<T, inlineCapacity>::remove(const_iterator& it) 4958f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian { 4968f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian it.checkValidity(); 4978f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian remove(it.m_index); 4988f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 4998f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 50081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 50181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void Deque<T, inlineCapacity>::remove(size_t position) 5028f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian { 5038f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian if (position == m_end) 5048f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian return; 5058f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 5068f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian checkValidity(); 5078f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian invalidateIterators(); 5088f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 5098f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian T* buffer = m_buffer.buffer(); 5108f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian TypeOperations::destruct(&buffer[position], &buffer[position + 1]); 5118f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 5128f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian // Find which segment of the circular buffer contained the remove element, and only move elements in that part. 5138f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian if (position >= m_start) { 5148f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1); 5158f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian m_start = (m_start + 1) % m_buffer.capacity(); 5168f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } else { 5178f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position); 5188f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity(); 5198f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 5208f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian checkValidity(); 5218f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 5228f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 5238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifdef NDEBUG 52481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity() const { } 52581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase<T, inlineCapacity>&) const { } 52681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList() { } 52781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList() { } 5288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else 52981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 53081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void DequeIteratorBase<T, inlineCapacity>::checkValidity() const 5318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 5328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_deque); 5338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_deque->checkIndexValidity(m_index); 5348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 53681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 53781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void DequeIteratorBase<T, inlineCapacity>::checkValidity(const Base& other) const 5388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 5398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 5408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project other.checkValidity(); 5418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_deque == other.m_deque); 5428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 54481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 54581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList() 5468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 5478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_deque) 5488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_next = 0; 5498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else { 5508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_next = m_deque->m_iterators; 5518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_deque->m_iterators = this; 5528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_next) 5538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_next->m_previous = this; 5548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_previous = 0; 5568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5578f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 55881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 55981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList() 5608f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian { 5618f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian if (!m_deque) { 5628f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian ASSERT(!m_next); 5638f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian ASSERT(!m_previous); 5648f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } else { 5658f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian if (m_next) { 5668f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian ASSERT(m_next->m_previous == this); 5678f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian m_next->m_previous = m_previous; 5688f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 5698f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian if (m_previous) { 5708f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian ASSERT(m_deque->m_iterators != this); 5718f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian ASSERT(m_previous->m_next == this); 5728f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian m_previous->m_next = m_next; 5738f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } else { 5748f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian ASSERT(m_deque->m_iterators == this); 5758f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian m_deque->m_iterators = m_next; 5768f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 5778f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 5788f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian m_next = 0; 5798f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian m_previous = 0; 5808f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 5818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 5828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 58381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 58481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase() 5858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_deque(0) 5868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 5878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 58981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 59081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const Deque<T, inlineCapacity>* deque, size_t index) 59181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch : m_deque(const_cast<Deque<T, inlineCapacity>*>(deque)) 5928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_index(index) 5938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 5948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project addToIteratorsList(); 5958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 5968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 59881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 59981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const Base& other) 6008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_deque(other.m_deque) 6018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_index(other.m_index) 6028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project addToIteratorsList(); 6048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 6058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 60781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 60881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline DequeIteratorBase<T, inlineCapacity>& DequeIteratorBase<T, inlineCapacity>::operator=(const Base& other) 6098f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian { 6108f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian checkValidity(); 6118f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian other.checkValidity(); 6128f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian removeFromIteratorsList(); 6138f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 6148f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian m_deque = other.m_deque; 6158f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian m_index = other.m_index; 6168f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian addToIteratorsList(); 6178f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian checkValidity(); 6188f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian return *this; 6198f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 6208f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 62181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 62281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline DequeIteratorBase<T, inlineCapacity>::~DequeIteratorBase() 6238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef NDEBUG 6258f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian removeFromIteratorsList(); 6268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_deque = 0; 6278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 6288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 63081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 63181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline bool DequeIteratorBase<T, inlineCapacity>::isEqual(const Base& other) const 6328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(other); 6348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_index == other.m_index; 6358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 63781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 63881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void DequeIteratorBase<T, inlineCapacity>::increment() 6398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 6418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_index != m_deque->m_end); 6428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_deque->m_buffer.capacity()); 6438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_index == m_deque->m_buffer.capacity() - 1) 6448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_index = 0; 6458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 6468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++m_index; 6478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 6488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 65081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 65181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void DequeIteratorBase<T, inlineCapacity>::decrement() 6528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 6548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_index != m_deque->m_start); 6558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_deque->m_buffer.capacity()); 6568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_index) 6578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_index = m_deque->m_buffer.capacity() - 1; 6588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 6598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project --m_index; 6608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 6618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 66381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 66481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline T* DequeIteratorBase<T, inlineCapacity>::after() const 6658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 6678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_index != m_deque->m_end); 6688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return &m_deque->m_buffer.buffer()[m_index]; 6698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 67181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity> 67281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline T* DequeIteratorBase<T, inlineCapacity>::before() const 6738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 6758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_index != m_deque->m_start); 6768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_index) 6778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1]; 6788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return &m_deque->m_buffer.buffer()[m_index - 1]; 6798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} // namespace WTF 6828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectusing WTF::Deque; 6848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif // WTF_Deque_h 686