18e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 28e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Copyright (C) 2008 Apple Inc. All rights reserved. 38e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 48e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Redistribution and use in source and binary forms, with or without 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * modification, are permitted provided that the following conditions 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * are met: 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 1. Redistributions of source code must retain the above copyright 98e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * notice, this list of conditions and the following disclaimer. 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * notice, this list of conditions and the following disclaimer in the 128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * documentation and/or other materials provided with the distribution. 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * its contributors may be used to endorse or promote products derived 158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * from this software without specific prior written permission. 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project */ 288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef SegmentedVector_h 308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define SegmentedVector_h 318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include <wtf/Vector.h> 338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 340bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdochnamespace WTF { 350bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 360bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch // An iterator for SegmentedVector. It supports only the pre ++ operator 370bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch template <typename T, size_t SegmentSize> class SegmentedVector; 380bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch template <typename T, size_t SegmentSize> class SegmentedVectorIterator { 390bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch private: 400bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch friend class SegmentedVector<T, SegmentSize>; 410bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch public: 420bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch typedef SegmentedVectorIterator<T, SegmentSize> Iterator; 430bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 440bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch ~SegmentedVectorIterator() { } 450bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 460bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch T& operator*() const { return m_vector.m_segments.at(m_segment)->at(m_index); } 470bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch T* operator->() const { return &m_vector.m_segments.at(m_segment)->at(m_index); } 480bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 490bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch // Only prefix ++ operator supported 500bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch Iterator& operator++() 510bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch { 520bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch ASSERT(m_index != SegmentSize); 530bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch ++m_index; 540bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch if (m_index >= m_vector.m_segments.at(m_segment)->size()) { 550bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch if (m_segment + 1 < m_vector.m_segments.size()) { 560bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch ASSERT(m_vector.m_segments.at(m_segment)->size() > 0); 570bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch ++m_segment; 580bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch m_index = 0; 590bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } else { 600bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch // Points to the "end" symbol 610bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch m_segment = 0; 620bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch m_index = SegmentSize; 630bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } 640bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } 650bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch return *this; 660bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } 670bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 680bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch bool operator==(const Iterator& other) const 690bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch { 700bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch return (m_index == other.m_index && m_segment = other.m_segment && &m_vector == &other.m_vector); 710bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } 720bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 730bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch bool operator!=(const Iterator& other) const 740bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch { 750bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch return (m_index != other.m_index || m_segment != other.m_segment || &m_vector != &other.m_vector); 760bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } 770bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 780bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize>& other) 790bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch { 800bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch m_vector = other.m_vector; 810bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch m_segment = other.m_segment; 820bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch m_index = other.m_index; 830bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch return *this; 840bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } 850bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 860bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch private: 870bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch SegmentedVectorIterator(SegmentedVector<T, SegmentSize>& vector, size_t segment, size_t index) 880bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch : m_vector(vector) 890bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch , m_segment(segment) 900bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch , m_index(index) 910bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch { 920bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } 930bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 940bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch SegmentedVector<T, SegmentSize>& m_vector; 950bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch size_t m_segment; 960bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch size_t m_index; 970bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch }; 988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // SegmentedVector is just like Vector, but it doesn't move the values 1008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // stored in its buffer when it grows. Therefore, it is safe to keep 1018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // pointers into a SegmentedVector. 1028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template <typename T, size_t SegmentSize> class SegmentedVector { 1030bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch friend class SegmentedVectorIterator<T, SegmentSize>; 1048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 1050bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch typedef SegmentedVectorIterator<T, SegmentSize> Iterator; 1060bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 1078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project SegmentedVector() 1088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_size(0) 1098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_segments.append(&m_inlineSegment); 1118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ~SegmentedVector() 1148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deleteAllSegments(); 1168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t size() const { return m_size; } 119231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block bool isEmpty() const { return !size(); } 1208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project T& at(size_t index) 1228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (index < SegmentSize) 1248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_inlineSegment[index]; 1258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return segmentFor(index)->at(subscriptFor(index)); 1268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project T& operator[](size_t index) 1298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return at(index); 1318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project T& last() 1348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return at(size() - 1); 1368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template <typename U> void append(const U& value) 1398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++m_size; 1418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_size <= SegmentSize) { 1438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_inlineSegment.uncheckedAppend(value); 1448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 1458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!segmentExistsFor(m_size - 1)) 1488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_segments.append(new Segment); 1498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project segmentFor(m_size - 1)->uncheckedAppend(value); 1508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1520bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch T& alloc() 1530bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch { 1540bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch append<T>(T()); 1550bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch return last(); 1560bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } 1570bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 1588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void removeLast() 1598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_size <= SegmentSize) 1618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_inlineSegment.removeLast(); 1628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 1638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project segmentFor(m_size - 1)->removeLast(); 1648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project --m_size; 1658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void grow(size_t size) 1688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(size > m_size); 1708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ensureSegmentsFor(size); 1718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_size = size; 1728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void clear() 1758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deleteAllSegments(); 1778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_segments.resize(1); 1788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_inlineSegment.clear(); 1798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_size = 0; 1808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1820bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch Iterator begin() 1830bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch { 1840bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch return Iterator(*this, 0, m_size ? 0 : SegmentSize); 1850bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } 1860bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 1870bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch Iterator end() 1880bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch { 1890bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch return Iterator(*this, 0, SegmentSize); 1900bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } 1910bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 1928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 1938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef Vector<T, SegmentSize> Segment; 1940bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 1958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void deleteAllSegments() 1968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Skip the first segment, because it's our inline segment, which was 1988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // not created by new. 1998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (size_t i = 1; i < m_segments.size(); i++) 2008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project delete m_segments[i]; 2018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2020bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 2038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool segmentExistsFor(size_t index) 2048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return index / SegmentSize < m_segments.size(); 2068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2070bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 2088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Segment* segmentFor(size_t index) 2098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_segments[index / SegmentSize]; 2118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2120bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 2138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t subscriptFor(size_t index) 2148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return index % SegmentSize; 2168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2170bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 2188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void ensureSegmentsFor(size_t size) 2198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t segmentCount = m_size / SegmentSize; 2218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_size % SegmentSize) 2228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++segmentCount; 2238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project segmentCount = std::max<size_t>(segmentCount, 1); // We always have at least our inline segment. 2248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t neededSegmentCount = size / SegmentSize; 2268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (size % SegmentSize) 2278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++neededSegmentCount; 2288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Fill up to N - 1 segments. 2308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t end = neededSegmentCount - 1; 2318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (size_t i = segmentCount - 1; i < end; ++i) 2328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ensureSegment(i, SegmentSize); 2330bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch 2348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Grow segment N to accomodate the remainder. 2358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ensureSegment(end, subscriptFor(size - 1) + 1); 2368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void ensureSegment(size_t segmentIndex, size_t size) 2398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(segmentIndex <= m_segments.size()); 2418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (segmentIndex == m_segments.size()) 2428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_segments.append(new Segment); 2438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_segments[segmentIndex]->grow(size); 2448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size_t m_size; 2478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Segment m_inlineSegment; 2488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Vector<Segment*, 32> m_segments; 2498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2510bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch} // namespace WTF 2528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 253231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Blockusing WTF::SegmentedVector; 254231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block 2558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif // SegmentedVector_h 256