2 * Copyright (C) 2008 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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 Computer, 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.
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.
29 #ifndef SegmentedVector_h
30 #define SegmentedVector_h
32 #include <wtf/Noncopyable.h>
33 #include <wtf/Vector.h>
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 {
41 friend class SegmentedVector<T, SegmentSize, InlineCapacity>;
43 typedef SegmentedVectorIterator<T, SegmentSize, InlineCapacity> Iterator;
45 ~SegmentedVectorIterator() { }
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); }
50 // Only prefix ++ operator supported
51 Iterator& operator++()
53 ASSERT(m_index != SegmentSize);
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);
61 // Points to the "end" symbol
63 m_index = SegmentSize;
69 bool operator==(const Iterator& other) const
71 return m_index == other.m_index && m_segment == other.m_segment && &m_vector == &other.m_vector;
74 bool operator!=(const Iterator& other) const
76 return m_index != other.m_index || m_segment != other.m_segment || &m_vector != &other.m_vector;
79 SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize, InlineCapacity>& other)
81 m_vector = other.m_vector;
82 m_segment = other.m_segment;
83 m_index = other.m_index;
88 SegmentedVectorIterator(SegmentedVector<T, SegmentSize, InlineCapacity>& vector, size_t segment, size_t index)
95 SegmentedVector<T, SegmentSize, InlineCapacity>& m_vector;
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);
111 typedef SegmentedVectorIterator<T, SegmentSize, InlineCapacity> Iterator;
116 m_segments.append(&m_inlineSegment);
124 size_t size() const { return m_size; }
125 bool isEmpty() const { return !size(); }
129 if (index < SegmentSize)
130 return m_inlineSegment[index];
131 return segmentFor(index)->at(subscriptFor(index));
134 T& operator[](size_t index)
141 return at(size() - 1);
144 template <typename U> void append(const U& value)
148 if (m_size <= SegmentSize) {
149 m_inlineSegment.uncheckedAppend(value);
153 if (!segmentExistsFor(m_size - 1))
154 m_segments.append(new Segment);
155 segmentFor(m_size - 1)->uncheckedAppend(value);
166 if (m_size <= SegmentSize)
167 m_inlineSegment.removeLast();
169 segmentFor(m_size - 1)->removeLast();
173 void grow(size_t size)
175 ASSERT(size > m_size);
176 ensureSegmentsFor(size);
183 m_segments.resize(1);
184 m_inlineSegment.clear();
190 return Iterator(*this, 0, m_size ? 0 : SegmentSize);
195 return Iterator(*this, 0, SegmentSize);
200 m_segments.shrinkToFit();
204 typedef Vector<T, SegmentSize> Segment;
206 void deleteAllSegments()
208 // Skip the first segment, because it's our inline segment, which was
209 // not created by new.
210 for (size_t i = 1; i < m_segments.size(); i++)
211 delete m_segments[i];
214 bool segmentExistsFor(size_t index)
216 return index / SegmentSize < m_segments.size();
219 Segment* segmentFor(size_t index)
221 return m_segments[index / SegmentSize];
224 size_t subscriptFor(size_t index)
226 return index % SegmentSize;
229 void ensureSegmentsFor(size_t size)
231 size_t segmentCount = m_size / SegmentSize;
232 if (m_size % SegmentSize)
234 segmentCount = std::max<size_t>(segmentCount, 1); // We always have at least our inline segment.
236 size_t neededSegmentCount = size / SegmentSize;
237 if (size % SegmentSize)
238 ++neededSegmentCount;
240 // Fill up to N - 1 segments.
241 size_t end = neededSegmentCount - 1;
242 for (size_t i = segmentCount - 1; i < end; ++i)
243 ensureSegment(i, SegmentSize);
245 // Grow segment N to accomodate the remainder.
246 ensureSegment(end, subscriptFor(size - 1) + 1);
249 void ensureSegment(size_t segmentIndex, size_t size)
251 ASSERT(segmentIndex <= m_segments.size());
252 if (segmentIndex == m_segments.size())
253 m_segments.append(new Segment);
254 m_segments[segmentIndex]->grow(size);
258 Segment m_inlineSegment;
259 Vector<Segment*, InlineCapacity> m_segments;
264 using WTF::SegmentedVector;
266 #endif // SegmentedVector_h