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 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. |
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/Vector.h> |
33 | |
34 | namespace WTF { |
35 | |
36 | // An iterator for SegmentedVector. It supports only the pre ++ operator |
37 | template <typename T, size_t SegmentSize> class SegmentedVector; |
38 | template <typename T, size_t SegmentSize> class SegmentedVectorIterator { |
39 | private: |
40 | friend class SegmentedVector<T, SegmentSize>; |
41 | public: |
42 | typedef SegmentedVectorIterator<T, SegmentSize> Iterator; |
43 | |
44 | ~SegmentedVectorIterator() { } |
45 | |
46 | T& operator*() const { return m_vector.m_segments.at(m_segment)->at(m_index); } |
47 | T* operator->() const { return &m_vector.m_segments.at(m_segment)->at(m_index); } |
48 | |
49 | // Only prefix ++ operator supported |
50 | Iterator& operator++() |
51 | { |
52 | ASSERT(m_index != SegmentSize); |
53 | ++m_index; |
54 | if (m_index >= m_vector.m_segments.at(m_segment)->size()) { |
55 | if (m_segment + 1 < m_vector.m_segments.size()) { |
56 | ASSERT(m_vector.m_segments.at(m_segment)->size() > 0); |
57 | ++m_segment; |
58 | m_index = 0; |
59 | } else { |
60 | // Points to the "end" symbol |
61 | m_segment = 0; |
62 | m_index = SegmentSize; |
63 | } |
64 | } |
65 | return *this; |
66 | } |
67 | |
68 | bool operator==(const Iterator& other) const |
69 | { |
70 | return (m_index == other.m_index && m_segment = other.m_segment && &m_vector == &other.m_vector); |
71 | } |
72 | |
73 | bool operator!=(const Iterator& other) const |
74 | { |
75 | return (m_index != other.m_index || m_segment != other.m_segment || &m_vector != &other.m_vector); |
76 | } |
77 | |
78 | SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize>& other) |
79 | { |
80 | m_vector = other.m_vector; |
81 | m_segment = other.m_segment; |
82 | m_index = other.m_index; |
83 | return *this; |
84 | } |
85 | |
86 | private: |
87 | SegmentedVectorIterator(SegmentedVector<T, SegmentSize>& vector, size_t segment, size_t index) |
88 | : m_vector(vector) |
89 | , m_segment(segment) |
90 | , m_index(index) |
91 | { |
92 | } |
93 | |
94 | SegmentedVector<T, SegmentSize>& m_vector; |
95 | size_t m_segment; |
96 | size_t m_index; |
97 | }; |
98 | |
99 | // SegmentedVector is just like Vector, but it doesn't move the values |
100 | // stored in its buffer when it grows. Therefore, it is safe to keep |
101 | // pointers into a SegmentedVector. |
102 | template <typename T, size_t SegmentSize> class SegmentedVector { |
103 | friend class SegmentedVectorIterator<T, SegmentSize>; |
104 | public: |
105 | typedef SegmentedVectorIterator<T, SegmentSize> Iterator; |
106 | |
107 | SegmentedVector() |
108 | : m_size(0) |
109 | { |
110 | m_segments.append(&m_inlineSegment); |
111 | } |
112 | |
113 | ~SegmentedVector() |
114 | { |
115 | deleteAllSegments(); |
116 | } |
117 | |
118 | size_t size() const { return m_size; } |
119 | bool isEmpty() const { return !size(); } |
120 | |
121 | T& at(size_t index) |
122 | { |
123 | if (index < SegmentSize) |
124 | return m_inlineSegment[index]; |
125 | return segmentFor(index)->at(subscriptFor(index)); |
126 | } |
127 | |
128 | T& operator[](size_t index) |
129 | { |
130 | return at(index); |
131 | } |
132 | |
133 | T& last() |
134 | { |
135 | return at(index: size() - 1); |
136 | } |
137 | |
138 | template <typename U> void append(const U& value) |
139 | { |
140 | ++m_size; |
141 | |
142 | if (m_size <= SegmentSize) { |
143 | m_inlineSegment.uncheckedAppend(value); |
144 | return; |
145 | } |
146 | |
147 | if (!segmentExistsFor(index: m_size - 1)) |
148 | m_segments.append(new Segment); |
149 | segmentFor(index: m_size - 1)->uncheckedAppend(value); |
150 | } |
151 | |
152 | T& alloc() |
153 | { |
154 | append<T>(T()); |
155 | return last(); |
156 | } |
157 | |
158 | void removeLast() |
159 | { |
160 | if (m_size <= SegmentSize) |
161 | m_inlineSegment.removeLast(); |
162 | else |
163 | segmentFor(index: m_size - 1)->removeLast(); |
164 | --m_size; |
165 | } |
166 | |
167 | void grow(size_t size) |
168 | { |
169 | ASSERT(size > m_size); |
170 | ensureSegmentsFor(size); |
171 | m_size = size; |
172 | } |
173 | |
174 | void clear() |
175 | { |
176 | deleteAllSegments(); |
177 | m_segments.resize(1); |
178 | m_inlineSegment.clear(); |
179 | m_size = 0; |
180 | } |
181 | |
182 | Iterator begin() |
183 | { |
184 | return Iterator(*this, 0, m_size ? 0 : SegmentSize); |
185 | } |
186 | |
187 | Iterator end() |
188 | { |
189 | return Iterator(*this, 0, SegmentSize); |
190 | } |
191 | |
192 | private: |
193 | typedef Vector<T, SegmentSize> Segment; |
194 | |
195 | void deleteAllSegments() |
196 | { |
197 | // Skip the first segment, because it's our inline segment, which was |
198 | // not created by new. |
199 | for (size_t i = 1; i < m_segments.size(); i++) |
200 | delete m_segments[i]; |
201 | } |
202 | |
203 | bool segmentExistsFor(size_t index) |
204 | { |
205 | return index / SegmentSize < m_segments.size(); |
206 | } |
207 | |
208 | Segment* segmentFor(size_t index) |
209 | { |
210 | return m_segments[index / SegmentSize]; |
211 | } |
212 | |
213 | size_t subscriptFor(size_t index) |
214 | { |
215 | return index % SegmentSize; |
216 | } |
217 | |
218 | void ensureSegmentsFor(size_t size) |
219 | { |
220 | size_t segmentCount = m_size / SegmentSize; |
221 | if (m_size % SegmentSize) |
222 | ++segmentCount; |
223 | segmentCount = std::max<size_t>(a: segmentCount, b: 1); // We always have at least our inline segment. |
224 | |
225 | size_t neededSegmentCount = size / SegmentSize; |
226 | if (size % SegmentSize) |
227 | ++neededSegmentCount; |
228 | |
229 | // Fill up to N - 1 segments. |
230 | size_t end = neededSegmentCount - 1; |
231 | for (size_t i = segmentCount - 1; i < end; ++i) |
232 | ensureSegment(segmentIndex: i, size: SegmentSize); |
233 | |
234 | // Grow segment N to accomodate the remainder. |
235 | ensureSegment(segmentIndex: end, size: subscriptFor(index: size - 1) + 1); |
236 | } |
237 | |
238 | void ensureSegment(size_t segmentIndex, size_t size) |
239 | { |
240 | ASSERT(segmentIndex <= m_segments.size()); |
241 | if (segmentIndex == m_segments.size()) |
242 | m_segments.append(new Segment); |
243 | m_segments[segmentIndex]->grow(size); |
244 | } |
245 | |
246 | size_t m_size; |
247 | Segment m_inlineSegment; |
248 | Vector<Segment*, 32> m_segments; |
249 | }; |
250 | |
251 | } // namespace WTF |
252 | |
253 | using WTF::SegmentedVector; |
254 | |
255 | #endif // SegmentedVector_h |
256 | |