1 //
2 // Copyright 2018 The ANGLE Project Authors. All rights reserved.
3 // Use of this source code is governed by a BSD-style license that can be
4 // found in the LICENSE file.
5 //
6 // FastVector.h:
7 // A vector class with a initial fixed size and variable growth.
8 // Based on FixedVector.
9 //
10
11 #ifndef COMMON_FASTVECTOR_H_
12 #define COMMON_FASTVECTOR_H_
13
14 #include "common/debug.h"
15
16 #include <algorithm>
17 #include <array>
18 #include <initializer_list>
19
20 namespace angle
21 {
22 template <class T, size_t N, class Storage = std::array<T, N>>
23 class FastVector final
24 {
25 public:
26 using value_type = typename Storage::value_type;
27 using size_type = typename Storage::size_type;
28 using reference = typename Storage::reference;
29 using const_reference = typename Storage::const_reference;
30 using pointer = typename Storage::pointer;
31 using const_pointer = typename Storage::const_pointer;
32 using iterator = T *;
33 using const_iterator = const T *;
34
35 FastVector();
36 FastVector(size_type count, const value_type &value);
37 FastVector(size_type count);
38
39 FastVector(const FastVector<T, N, Storage> &other);
40 FastVector(FastVector<T, N, Storage> &&other);
41 FastVector(std::initializer_list<value_type> init);
42
43 FastVector<T, N, Storage> &operator=(const FastVector<T, N, Storage> &other);
44 FastVector<T, N, Storage> &operator=(FastVector<T, N, Storage> &&other);
45 FastVector<T, N, Storage> &operator=(std::initializer_list<value_type> init);
46
47 ~FastVector();
48
49 reference at(size_type pos);
50 const_reference at(size_type pos) const;
51
52 reference operator[](size_type pos);
53 const_reference operator[](size_type pos) const;
54
55 pointer data();
56 const_pointer data() const;
57
58 iterator begin();
59 const_iterator begin() const;
60
61 iterator end();
62 const_iterator end() const;
63
64 bool empty() const;
65 size_type size() const;
66
67 void clear();
68
69 void push_back(const value_type &value);
70 void push_back(value_type &&value);
71
72 void pop_back();
73
74 reference front();
75 const_reference front() const;
76
77 reference back();
78 const_reference back() const;
79
80 void swap(FastVector<T, N, Storage> &other);
81
82 void resize(size_type count);
83 void resize(size_type count, const value_type &value);
84
85 // Specialty function that removes a known element and might shuffle the list.
86 void remove_and_permute(const value_type &element);
87
88 private:
89 void assign_from_initializer_list(std::initializer_list<value_type> init);
90 void ensure_capacity(size_t capacity);
91 bool uses_fixed_storage() const;
92
93 Storage mFixedStorage;
94 pointer mData = mFixedStorage.data();
95 size_type mSize = 0;
96 size_type mReservedSize = N;
97 };
98
99 template <class T, size_t N, class StorageN, size_t M, class StorageM>
100 bool operator==(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
101 {
102 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
103 }
104
105 template <class T, size_t N, class StorageN, size_t M, class StorageM>
106 bool operator!=(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
107 {
108 return !(a == b);
109 }
110
111 template <class T, size_t N, class Storage>
uses_fixed_storage()112 ANGLE_INLINE bool FastVector<T, N, Storage>::uses_fixed_storage() const
113 {
114 return mData == mFixedStorage.data();
115 }
116
117 template <class T, size_t N, class Storage>
FastVector()118 FastVector<T, N, Storage>::FastVector()
119 {}
120
121 template <class T, size_t N, class Storage>
FastVector(size_type count,const value_type & value)122 FastVector<T, N, Storage>::FastVector(size_type count, const value_type &value)
123 {
124 ensure_capacity(count);
125 mSize = count;
126 std::fill(begin(), end(), value);
127 }
128
129 template <class T, size_t N, class Storage>
FastVector(size_type count)130 FastVector<T, N, Storage>::FastVector(size_type count)
131 {
132 ensure_capacity(count);
133 mSize = count;
134 }
135
136 template <class T, size_t N, class Storage>
FastVector(const FastVector<T,N,Storage> & other)137 FastVector<T, N, Storage>::FastVector(const FastVector<T, N, Storage> &other)
138 {
139 ensure_capacity(other.mSize);
140 mSize = other.mSize;
141 std::copy(other.begin(), other.end(), begin());
142 }
143
144 template <class T, size_t N, class Storage>
FastVector(FastVector<T,N,Storage> && other)145 FastVector<T, N, Storage>::FastVector(FastVector<T, N, Storage> &&other) : FastVector()
146 {
147 swap(other);
148 }
149
150 template <class T, size_t N, class Storage>
FastVector(std::initializer_list<value_type> init)151 FastVector<T, N, Storage>::FastVector(std::initializer_list<value_type> init)
152 {
153 assign_from_initializer_list(init);
154 }
155
156 template <class T, size_t N, class Storage>
157 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
158 const FastVector<T, N, Storage> &other)
159 {
160 ensure_capacity(other.mSize);
161 mSize = other.mSize;
162 std::copy(other.begin(), other.end(), begin());
163 return *this;
164 }
165
166 template <class T, size_t N, class Storage>
167 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(FastVector<T, N, Storage> &&other)
168 {
169 swap(*this, other);
170 return *this;
171 }
172
173 template <class T, size_t N, class Storage>
174 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
175 std::initializer_list<value_type> init)
176 {
177 assign_from_initializer_list(init);
178 return *this;
179 }
180
181 template <class T, size_t N, class Storage>
~FastVector()182 FastVector<T, N, Storage>::~FastVector()
183 {
184 clear();
185 if (!uses_fixed_storage())
186 {
187 delete[] mData;
188 }
189 }
190
191 template <class T, size_t N, class Storage>
at(size_type pos)192 typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::at(size_type pos)
193 {
194 ASSERT(pos < mSize);
195 return mData[pos];
196 }
197
198 template <class T, size_t N, class Storage>
at(size_type pos)199 typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::at(
200 size_type pos) const
201 {
202 ASSERT(pos < mSize);
203 return mData[pos];
204 }
205
206 template <class T, size_t N, class Storage>
207 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::operator[](
208 size_type pos)
209 {
210 ASSERT(pos < mSize);
211 return mData[pos];
212 }
213
214 template <class T, size_t N, class Storage>
215 ANGLE_INLINE
216 typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::operator[](
217 size_type pos) const
218 {
219 ASSERT(pos < mSize);
220 return mData[pos];
221 }
222
223 template <class T, size_t N, class Storage>
224 ANGLE_INLINE typename FastVector<T, N, Storage>::const_pointer
data()225 angle::FastVector<T, N, Storage>::data() const
226 {
227 ASSERT(!empty());
228 return mData;
229 }
230
231 template <class T, size_t N, class Storage>
data()232 ANGLE_INLINE typename FastVector<T, N, Storage>::pointer angle::FastVector<T, N, Storage>::data()
233 {
234 ASSERT(!empty());
235 return mData;
236 }
237
238 template <class T, size_t N, class Storage>
begin()239 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::begin()
240 {
241 return mData;
242 }
243
244 template <class T, size_t N, class Storage>
begin()245 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::begin()
246 const
247 {
248 return mData;
249 }
250
251 template <class T, size_t N, class Storage>
end()252 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::end()
253 {
254 return mData + mSize;
255 }
256
257 template <class T, size_t N, class Storage>
end()258 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::end()
259 const
260 {
261 return mData + mSize;
262 }
263
264 template <class T, size_t N, class Storage>
empty()265 ANGLE_INLINE bool FastVector<T, N, Storage>::empty() const
266 {
267 return mSize == 0;
268 }
269
270 template <class T, size_t N, class Storage>
size()271 ANGLE_INLINE typename FastVector<T, N, Storage>::size_type FastVector<T, N, Storage>::size() const
272 {
273 return mSize;
274 }
275
276 template <class T, size_t N, class Storage>
clear()277 void FastVector<T, N, Storage>::clear()
278 {
279 resize(0);
280 }
281
282 template <class T, size_t N, class Storage>
push_back(const value_type & value)283 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(const value_type &value)
284 {
285 if (mSize == mReservedSize)
286 ensure_capacity(mSize + 1);
287 mData[mSize++] = value;
288 }
289
290 template <class T, size_t N, class Storage>
push_back(value_type && value)291 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(value_type &&value)
292 {
293 if (mSize == mReservedSize)
294 ensure_capacity(mSize + 1);
295 mData[mSize++] = std::move(value);
296 }
297
298 template <class T, size_t N, class Storage>
pop_back()299 ANGLE_INLINE void FastVector<T, N, Storage>::pop_back()
300 {
301 ASSERT(mSize > 0);
302 mSize--;
303 }
304
305 template <class T, size_t N, class Storage>
front()306 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::front()
307 {
308 ASSERT(mSize > 0);
309 return mData[0];
310 }
311
312 template <class T, size_t N, class Storage>
front()313 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::front()
314 const
315 {
316 ASSERT(mSize > 0);
317 return mData[0];
318 }
319
320 template <class T, size_t N, class Storage>
back()321 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::back()
322 {
323 ASSERT(mSize > 0);
324 return mData[mSize - 1];
325 }
326
327 template <class T, size_t N, class Storage>
back()328 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::back()
329 const
330 {
331 ASSERT(mSize > 0);
332 return mData[mSize - 1];
333 }
334
335 template <class T, size_t N, class Storage>
swap(FastVector<T,N,Storage> & other)336 void FastVector<T, N, Storage>::swap(FastVector<T, N, Storage> &other)
337 {
338 std::swap(mSize, other.mSize);
339
340 pointer tempData = other.mData;
341 if (uses_fixed_storage())
342 other.mData = other.mFixedStorage.data();
343 else
344 other.mData = mData;
345 if (tempData == other.mFixedStorage.data())
346 mData = mFixedStorage.data();
347 else
348 mData = tempData;
349 std::swap(mReservedSize, other.mReservedSize);
350
351 if (uses_fixed_storage() || other.uses_fixed_storage())
352 std::swap(mFixedStorage, other.mFixedStorage);
353 }
354
355 template <class T, size_t N, class Storage>
resize(size_type count)356 void FastVector<T, N, Storage>::resize(size_type count)
357 {
358 if (count > mSize)
359 {
360 ensure_capacity(count);
361 }
362 mSize = count;
363 }
364
365 template <class T, size_t N, class Storage>
resize(size_type count,const value_type & value)366 void FastVector<T, N, Storage>::resize(size_type count, const value_type &value)
367 {
368 if (count > mSize)
369 {
370 ensure_capacity(count);
371 std::fill(mData + mSize, mData + count, value);
372 }
373 mSize = count;
374 }
375
376 template <class T, size_t N, class Storage>
assign_from_initializer_list(std::initializer_list<value_type> init)377 void FastVector<T, N, Storage>::assign_from_initializer_list(std::initializer_list<value_type> init)
378 {
379 ensure_capacity(init.size());
380 mSize = init.size();
381 size_t index = 0;
382 for (auto &value : init)
383 {
384 mData[index++] = value;
385 }
386 }
387
388 template <class T, size_t N, class Storage>
remove_and_permute(const value_type & element)389 ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(const value_type &element)
390 {
391 size_t len = mSize - 1;
392 for (size_t index = 0; index < len; ++index)
393 {
394 if (mData[index] == element)
395 {
396 mData[index] = std::move(mData[len]);
397 break;
398 }
399 }
400 pop_back();
401 }
402
403 template <class T, size_t N, class Storage>
ensure_capacity(size_t capacity)404 void FastVector<T, N, Storage>::ensure_capacity(size_t capacity)
405 {
406 // We have a minimum capacity of N.
407 if (mReservedSize < capacity)
408 {
409 ASSERT(capacity > N);
410 size_type newSize = std::max(mReservedSize, N);
411 while (newSize < capacity)
412 {
413 newSize *= 2;
414 }
415
416 pointer newData = new value_type[newSize];
417
418 if (mSize > 0)
419 {
420 std::move(begin(), end(), newData);
421 }
422
423 if (!uses_fixed_storage())
424 {
425 delete[] mData;
426 }
427
428 mData = newData;
429 mReservedSize = newSize;
430 }
431 }
432 } // namespace angle
433
434 #endif // COMMON_FASTVECTOR_H_
435