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#pragma once
30
31#include <wtf/Noncopyable.h>
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 = 8> class SegmentedVector;
38 template <typename T, size_t SegmentSize = 8> 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.at(m_index); }
47 T* operator->() const { return &m_vector.at(m_index); }
48
49 // Only prefix ++ operator supported
50 Iterator& operator++()
51 {
52 m_index++;
53 return *this;
54 }
55
56 bool operator==(const Iterator& other) const
57 {
58 return m_index == other.m_index && &m_vector == &other.m_vector;
59 }
60
61 bool operator!=(const Iterator& other) const
62 {
63 return m_index != other.m_index || &m_vector != &other.m_vector;
64 }
65
66 SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize>& other)
67 {
68 m_vector = other.m_vector;
69 m_index = other.m_index;
70 return *this;
71 }
72
73 private:
74 SegmentedVectorIterator(SegmentedVector<T, SegmentSize>& vector, size_t index)
75 : m_vector(vector)
76 , m_index(index)
77 {
78 }
79
80 SegmentedVector<T, SegmentSize>& m_vector;
81 size_t m_index;
82 };
83
84 // SegmentedVector is just like Vector, but it doesn't move the values
85 // stored in its buffer when it grows. Therefore, it is safe to keep
86 // pointers into a SegmentedVector. The default tuning values are
87 // optimized for segmented vectors that get large; you may want to use
88 // SegmentedVector<thingy, 1> if you don't expect a lot of entries.
89 template <typename T, size_t SegmentSize>
90 class SegmentedVector {
91 friend class SegmentedVectorIterator<T, SegmentSize>;
92 WTF_MAKE_NONCOPYABLE(SegmentedVector);
93 WTF_MAKE_FAST_ALLOCATED;
94
95 public:
96 typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
97
98 SegmentedVector() = default;
99
100 ~SegmentedVector()
101 {
102 deleteAllSegments();
103 }
104
105 size_t size() const { return m_size; }
106 bool isEmpty() const { return !size(); }
107
108 T& at(size_t index)
109 {
110 ASSERT_WITH_SECURITY_IMPLICATION(index < m_size);
111 return segmentFor(index)->entries[subscriptFor(index)];
112 }
113
114 const T& at(size_t index) const
115 {
116 return const_cast<SegmentedVector<T, SegmentSize>*>(this)->at(index);
117 }
118
119 T& operator[](size_t index)
120 {
121 return at(index);
122 }
123
124 const T& operator[](size_t index) const
125 {
126 return at(index);
127 }
128
129 T& first()
130 {
131 ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
132 return at(0);
133 }
134 const T& first() const
135 {
136 ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
137 return at(0);
138 }
139 T& last()
140 {
141 ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
142 return at(size() - 1);
143 }
144 const T& last() const
145 {
146 ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
147 return at(size() - 1);
148 }
149
150 T takeLast()
151 {
152 ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
153 T result = WTFMove(last());
154 --m_size;
155 return result;
156 }
157
158 template<typename... Args>
159 void append(Args&&... args)
160 {
161 ++m_size;
162 if (!segmentExistsFor(m_size - 1))
163 allocateSegment();
164 new (NotNull, &last()) T(std::forward<Args>(args)...);
165 }
166
167 template<typename... Args>
168 T& alloc(Args&&... args)
169 {
170 append(std::forward<Args>(args)...);
171 return last();
172 }
173
174 void removeLast()
175 {
176 last().~T();
177 --m_size;
178 }
179
180 void grow(size_t size)
181 {
182 ASSERT(size > m_size);
183 ensureSegmentsFor(size);
184 size_t oldSize = m_size;
185 m_size = size;
186 for (size_t i = oldSize; i < m_size; ++i)
187 new (NotNull, &at(i)) T();
188 }
189
190 void clear()
191 {
192 deleteAllSegments();
193 m_segments.clear();
194 m_size = 0;
195 }
196
197 Iterator begin()
198 {
199 return Iterator(*this, 0);
200 }
201
202 Iterator end()
203 {
204 return Iterator(*this, m_size);
205 }
206
207 void shrinkToFit()
208 {
209 m_segments.shrinkToFit();
210 }
211
212 private:
213 struct Segment {
214#if COMPILER(MSVC)
215#pragma warning(push)
216#pragma warning(disable: 4200)
217#endif
218 T entries[0];
219#if COMPILER(MSVC)
220#pragma warning(pop)
221#endif
222 };
223
224 void deleteAllSegments()
225 {
226 for (size_t i = 0; i < m_size; ++i)
227 at(i).~T();
228 for (size_t i = 0; i < m_segments.size(); ++i)
229 fastFree(m_segments[i]);
230 }
231
232 bool segmentExistsFor(size_t index)
233 {
234 return index / SegmentSize < m_segments.size();
235 }
236
237 Segment* segmentFor(size_t index)
238 {
239 return m_segments[index / SegmentSize];
240 }
241
242 size_t subscriptFor(size_t index)
243 {
244 return index % SegmentSize;
245 }
246
247 void ensureSegmentsFor(size_t size)
248 {
249 size_t segmentCount = (m_size + SegmentSize - 1) / SegmentSize;
250 size_t neededSegmentCount = (size + SegmentSize - 1) / SegmentSize;
251
252 for (size_t i = segmentCount ? segmentCount - 1 : 0; i < neededSegmentCount; ++i)
253 ensureSegment(i);
254 }
255
256 void ensureSegment(size_t segmentIndex)
257 {
258 ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size());
259 if (segmentIndex == m_segments.size())
260 allocateSegment();
261 }
262
263 void allocateSegment()
264 {
265 m_segments.append(static_cast<Segment*>(fastMalloc(sizeof(T) * SegmentSize)));
266 }
267
268 size_t m_size { 0 };
269 Vector<Segment*> m_segments;
270 };
271
272} // namespace WTF
273
274using WTF::SegmentedVector;
275