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 return mData;
228 }
229
230 template <class T, size_t N, class Storage>
data()231 ANGLE_INLINE typename FastVector<T, N, Storage>::pointer angle::FastVector<T, N, Storage>::data()
232 {
233 return mData;
234 }
235
236 template <class T, size_t N, class Storage>
begin()237 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::begin()
238 {
239 return mData;
240 }
241
242 template <class T, size_t N, class Storage>
begin()243 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::begin()
244 const
245 {
246 return mData;
247 }
248
249 template <class T, size_t N, class Storage>
end()250 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::end()
251 {
252 return mData + mSize;
253 }
254
255 template <class T, size_t N, class Storage>
end()256 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::end()
257 const
258 {
259 return mData + mSize;
260 }
261
262 template <class T, size_t N, class Storage>
empty()263 ANGLE_INLINE bool FastVector<T, N, Storage>::empty() const
264 {
265 return mSize == 0;
266 }
267
268 template <class T, size_t N, class Storage>
size()269 ANGLE_INLINE typename FastVector<T, N, Storage>::size_type FastVector<T, N, Storage>::size() const
270 {
271 return mSize;
272 }
273
274 template <class T, size_t N, class Storage>
clear()275 void FastVector<T, N, Storage>::clear()
276 {
277 resize(0);
278 }
279
280 template <class T, size_t N, class Storage>
push_back(const value_type & value)281 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(const value_type &value)
282 {
283 if (mSize == mReservedSize)
284 ensure_capacity(mSize + 1);
285 mData[mSize++] = value;
286 }
287
288 template <class T, size_t N, class Storage>
push_back(value_type && value)289 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(value_type &&value)
290 {
291 if (mSize == mReservedSize)
292 ensure_capacity(mSize + 1);
293 mData[mSize++] = std::move(value);
294 }
295
296 template <class T, size_t N, class Storage>
pop_back()297 ANGLE_INLINE void FastVector<T, N, Storage>::pop_back()
298 {
299 ASSERT(mSize > 0);
300 mSize--;
301 }
302
303 template <class T, size_t N, class Storage>
front()304 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::front()
305 {
306 ASSERT(mSize > 0);
307 return mData[0];
308 }
309
310 template <class T, size_t N, class Storage>
front()311 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::front()
312 const
313 {
314 ASSERT(mSize > 0);
315 return mData[0];
316 }
317
318 template <class T, size_t N, class Storage>
back()319 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::back()
320 {
321 ASSERT(mSize > 0);
322 return mData[mSize - 1];
323 }
324
325 template <class T, size_t N, class Storage>
back()326 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::back()
327 const
328 {
329 ASSERT(mSize > 0);
330 return mData[mSize - 1];
331 }
332
333 template <class T, size_t N, class Storage>
swap(FastVector<T,N,Storage> & other)334 void FastVector<T, N, Storage>::swap(FastVector<T, N, Storage> &other)
335 {
336 std::swap(mSize, other.mSize);
337
338 pointer tempData = other.mData;
339 if (uses_fixed_storage())
340 other.mData = other.mFixedStorage.data();
341 else
342 other.mData = mData;
343 if (tempData == other.mFixedStorage.data())
344 mData = mFixedStorage.data();
345 else
346 mData = tempData;
347 std::swap(mReservedSize, other.mReservedSize);
348
349 if (uses_fixed_storage() || other.uses_fixed_storage())
350 std::swap(mFixedStorage, other.mFixedStorage);
351 }
352
353 template <class T, size_t N, class Storage>
resize(size_type count)354 void FastVector<T, N, Storage>::resize(size_type count)
355 {
356 if (count > mSize)
357 {
358 ensure_capacity(count);
359 }
360 mSize = count;
361 }
362
363 template <class T, size_t N, class Storage>
resize(size_type count,const value_type & value)364 void FastVector<T, N, Storage>::resize(size_type count, const value_type &value)
365 {
366 if (count > mSize)
367 {
368 ensure_capacity(count);
369 std::fill(mData + mSize, mData + count, value);
370 }
371 mSize = count;
372 }
373
374 template <class T, size_t N, class Storage>
assign_from_initializer_list(std::initializer_list<value_type> init)375 void FastVector<T, N, Storage>::assign_from_initializer_list(std::initializer_list<value_type> init)
376 {
377 ensure_capacity(init.size());
378 mSize = init.size();
379 size_t index = 0;
380 for (auto &value : init)
381 {
382 mData[index++] = value;
383 }
384 }
385
386 template <class T, size_t N, class Storage>
remove_and_permute(const value_type & element)387 ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(const value_type &element)
388 {
389 size_t len = mSize - 1;
390 for (size_t index = 0; index < len; ++index)
391 {
392 if (mData[index] == element)
393 {
394 mData[index] = std::move(mData[len]);
395 break;
396 }
397 }
398 pop_back();
399 }
400
401 template <class T, size_t N, class Storage>
ensure_capacity(size_t capacity)402 void FastVector<T, N, Storage>::ensure_capacity(size_t capacity)
403 {
404 // We have a minimum capacity of N.
405 if (mReservedSize < capacity)
406 {
407 ASSERT(capacity > N);
408 size_type newSize = std::max(mReservedSize, N);
409 while (newSize < capacity)
410 {
411 newSize *= 2;
412 }
413
414 pointer newData = new value_type[newSize];
415
416 if (mSize > 0)
417 {
418 std::move(begin(), end(), newData);
419 }
420
421 if (!uses_fixed_storage())
422 {
423 delete[] mData;
424 }
425
426 mData = newData;
427 mReservedSize = newSize;
428 }
429 }
430 } // namespace angle
431
432 #endif // COMMON_FASTVECTOR_H_
433