1/* 2 * Copyright (C) 2008 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. Neither the name of Apple Inc. ("Apple") nor the names of 14 * its contributors may be used to endorse or promote products derived 15 * from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29#ifndef SegmentedVector_h 30#define SegmentedVector_h 31 32#include <wtf/Noncopyable.h> 33#include <wtf/Vector.h> 34 35namespace WTF { 36 37 // An iterator for SegmentedVector. It supports only the pre ++ operator 38 template <typename T, size_t SegmentSize = 8, size_t InlineCapacity = 32> class SegmentedVector; 39 template <typename T, size_t SegmentSize = 8, size_t InlineCapacity = 32> class SegmentedVectorIterator { 40 private: 41 friend class SegmentedVector<T, SegmentSize, InlineCapacity>; 42 public: 43 typedef SegmentedVectorIterator<T, SegmentSize, InlineCapacity> Iterator; 44 45 ~SegmentedVectorIterator() { } 46 47 T& operator*() const { return m_vector.m_segments.at(m_segment)->at(m_index); } 48 T* operator->() const { return &m_vector.m_segments.at(m_segment)->at(m_index); } 49 50 // Only prefix ++ operator supported 51 Iterator& operator++() 52 { 53 ASSERT(m_index != SegmentSize); 54 ++m_index; 55 if (m_index >= m_vector.m_segments.at(m_segment)->size()) { 56 if (m_segment + 1 < m_vector.m_segments.size()) { 57 ASSERT(m_vector.m_segments.at(m_segment)->size() > 0); 58 ++m_segment; 59 m_index = 0; 60 } else { 61 // Points to the "end" symbol 62 m_segment = 0; 63 m_index = SegmentSize; 64 } 65 } 66 return *this; 67 } 68 69 bool operator==(const Iterator& other) const 70 { 71 return m_index == other.m_index && m_segment == other.m_segment && &m_vector == &other.m_vector; 72 } 73 74 bool operator!=(const Iterator& other) const 75 { 76 return m_index != other.m_index || m_segment != other.m_segment || &m_vector != &other.m_vector; 77 } 78 79 SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize, InlineCapacity>& other) 80 { 81 m_vector = other.m_vector; 82 m_segment = other.m_segment; 83 m_index = other.m_index; 84 return *this; 85 } 86 87 private: 88 SegmentedVectorIterator(SegmentedVector<T, SegmentSize, InlineCapacity>& vector, size_t segment, size_t index) 89 : m_vector(vector) 90 , m_segment(segment) 91 , m_index(index) 92 { 93 } 94 95 SegmentedVector<T, SegmentSize, InlineCapacity>& m_vector; 96 size_t m_segment; 97 size_t m_index; 98 }; 99 100 // SegmentedVector is just like Vector, but it doesn't move the values 101 // stored in its buffer when it grows. Therefore, it is safe to keep 102 // pointers into a SegmentedVector. The default tuning values are 103 // optimized for segmented vectors that get large; you may want to use 104 // SegmentedVector<thingy, 1, 0> if you don't expect a lot of entries. 105 template <typename T, size_t SegmentSize, size_t InlineCapacity> 106 class SegmentedVector { 107 friend class SegmentedVectorIterator<T, SegmentSize, InlineCapacity>; 108 WTF_MAKE_NONCOPYABLE(SegmentedVector); 109 110 public: 111 typedef SegmentedVectorIterator<T, SegmentSize, InlineCapacity> Iterator; 112 113 SegmentedVector() 114 : m_size(0) 115 { 116 } 117 118 ~SegmentedVector() 119 { 120 deleteAllSegments(); 121 } 122 123 size_t size() const { return m_size; } 124 bool isEmpty() const { return !size(); } 125 126 T& at(size_t index) 127 { 128 return segmentFor(index)->at(subscriptFor(index)); 129 } 130 131 const T& at(size_t index) const 132 { 133 return const_cast<SegmentedVector<T, SegmentSize, InlineCapacity>*>(this)->at(index); 134 } 135 136 T& operator[](size_t index) 137 { 138 return at(index); 139 } 140 141 const T& operator[](size_t index) const 142 { 143 return at(index); 144 } 145 146 T& last() 147 { 148 return at(size() - 1); 149 } 150 151 template <typename U> void append(U&& value) 152 { 153 ++m_size; 154 155 if (!segmentExistsFor(m_size - 1)) 156 m_segments.append(new Segment); 157 segmentFor(m_size - 1)->uncheckedAppend(std::forward<U>(value)); 158 } 159 160 T& alloc() 161 { 162 append<T>(T()); 163 return last(); 164 } 165 166 void removeLast() 167 { 168 segmentFor(m_size - 1)->removeLast(); 169 --m_size; 170 } 171 172 void grow(size_t size) 173 { 174 ASSERT(size > m_size); 175 ensureSegmentsFor(size); 176 m_size = size; 177 } 178 179 void clear() 180 { 181 deleteAllSegments(); 182 m_segments.clear(); 183 m_size = 0; 184 } 185 186 Iterator begin() 187 { 188 return Iterator(*this, 0, m_size ? 0 : SegmentSize); 189 } 190 191 Iterator end() 192 { 193 return Iterator(*this, 0, SegmentSize); 194 } 195 196 void shrinkToFit() 197 { 198 m_segments.shrinkToFit(); 199 } 200 201 private: 202 typedef Vector<T, SegmentSize> Segment; 203 204 void deleteAllSegments() 205 { 206 for (size_t i = 0; i < m_segments.size(); i++) 207 delete m_segments[i]; 208 } 209 210 bool segmentExistsFor(size_t index) 211 { 212 return index / SegmentSize < m_segments.size(); 213 } 214 215 Segment* segmentFor(size_t index) 216 { 217 return m_segments[index / SegmentSize]; 218 } 219 220 size_t subscriptFor(size_t index) 221 { 222 return index % SegmentSize; 223 } 224 225 void ensureSegmentsFor(size_t size) 226 { 227 size_t segmentCount = (m_size + SegmentSize - 1) / SegmentSize; 228 size_t neededSegmentCount = (size + SegmentSize - 1) / SegmentSize; 229 230 // Fill up to N - 1 segments. 231 size_t end = neededSegmentCount - 1; 232 for (size_t i = segmentCount ? segmentCount - 1 : 0; i < end; ++i) 233 ensureSegment(i, SegmentSize); 234 235 // Grow segment N to accomodate the remainder. 236 ensureSegment(end, subscriptFor(size - 1) + 1); 237 } 238 239 void ensureSegment(size_t segmentIndex, size_t size) 240 { 241 ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size()); 242 if (segmentIndex == m_segments.size()) 243 m_segments.append(new Segment); 244 m_segments[segmentIndex]->grow(size); 245 } 246 247 size_t m_size; 248 Vector<Segment*> m_segments; 249 }; 250 251} // namespace WTF 252 253using WTF::SegmentedVector; 254 255#endif // SegmentedVector_h 256