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
34namespace 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
253using WTF::SegmentedVector;
254
255#endif // SegmentedVector_h
256

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/wtf/SegmentedVector.h