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 "bitset_utils.h"
15 #include "common/debug.h"
16
17 #include <algorithm>
18 #include <array>
19 #include <initializer_list>
20
21 namespace angle
22 {
23 template <class T, size_t N, class Storage = std::array<T, N>>
24 class FastVector final
25 {
26 public:
27 using value_type = typename Storage::value_type;
28 using size_type = typename Storage::size_type;
29 using reference = typename Storage::reference;
30 using const_reference = typename Storage::const_reference;
31 using pointer = typename Storage::pointer;
32 using const_pointer = typename Storage::const_pointer;
33 using iterator = T *;
34 using const_iterator = const T *;
35
36 FastVector();
37 FastVector(size_type count, const value_type &value);
38 FastVector(size_type count);
39
40 FastVector(const FastVector<T, N, Storage> &other);
41 FastVector(FastVector<T, N, Storage> &&other);
42 FastVector(std::initializer_list<value_type> init);
43
44 FastVector<T, N, Storage> &operator=(const FastVector<T, N, Storage> &other);
45 FastVector<T, N, Storage> &operator=(FastVector<T, N, Storage> &&other);
46 FastVector<T, N, Storage> &operator=(std::initializer_list<value_type> init);
47
48 ~FastVector();
49
50 reference at(size_type pos);
51 const_reference at(size_type pos) const;
52
53 reference operator[](size_type pos);
54 const_reference operator[](size_type pos) const;
55
56 pointer data();
57 const_pointer data() const;
58
59 iterator begin();
60 const_iterator begin() const;
61
62 iterator end();
63 const_iterator end() const;
64
65 bool empty() const;
66 size_type size() const;
67
68 void clear();
69
70 void push_back(const value_type &value);
71 void push_back(value_type &&value);
72
73 void pop_back();
74
75 reference front();
76 const_reference front() const;
77
78 reference back();
79 const_reference back() const;
80
81 void swap(FastVector<T, N, Storage> &other);
82
83 void resize(size_type count);
84 void resize(size_type count, const value_type &value);
85
86 // Specialty function that removes a known element and might shuffle the list.
87 void remove_and_permute(const value_type &element);
88
89 private:
90 void assign_from_initializer_list(std::initializer_list<value_type> init);
91 void ensure_capacity(size_t capacity);
92 bool uses_fixed_storage() const;
93
94 Storage mFixedStorage;
95 pointer mData = mFixedStorage.data();
96 size_type mSize = 0;
97 size_type mReservedSize = N;
98 };
99
100 template <class T, size_t N, class StorageN, size_t M, class StorageM>
101 bool operator==(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
102 {
103 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
104 }
105
106 template <class T, size_t N, class StorageN, size_t M, class StorageM>
107 bool operator!=(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
108 {
109 return !(a == b);
110 }
111
112 template <class T, size_t N, class Storage>
uses_fixed_storage()113 ANGLE_INLINE bool FastVector<T, N, Storage>::uses_fixed_storage() const
114 {
115 return mData == mFixedStorage.data();
116 }
117
118 template <class T, size_t N, class Storage>
FastVector()119 FastVector<T, N, Storage>::FastVector()
120 {}
121
122 template <class T, size_t N, class Storage>
FastVector(size_type count,const value_type & value)123 FastVector<T, N, Storage>::FastVector(size_type count, const value_type &value)
124 {
125 ensure_capacity(count);
126 mSize = count;
127 std::fill(begin(), end(), value);
128 }
129
130 template <class T, size_t N, class Storage>
FastVector(size_type count)131 FastVector<T, N, Storage>::FastVector(size_type count)
132 {
133 ensure_capacity(count);
134 mSize = count;
135 }
136
137 template <class T, size_t N, class Storage>
FastVector(const FastVector<T,N,Storage> & other)138 FastVector<T, N, Storage>::FastVector(const FastVector<T, N, Storage> &other)
139 {
140 ensure_capacity(other.mSize);
141 mSize = other.mSize;
142 std::copy(other.begin(), other.end(), begin());
143 }
144
145 template <class T, size_t N, class Storage>
FastVector(FastVector<T,N,Storage> && other)146 FastVector<T, N, Storage>::FastVector(FastVector<T, N, Storage> &&other) : FastVector()
147 {
148 swap(other);
149 }
150
151 template <class T, size_t N, class Storage>
FastVector(std::initializer_list<value_type> init)152 FastVector<T, N, Storage>::FastVector(std::initializer_list<value_type> init)
153 {
154 assign_from_initializer_list(init);
155 }
156
157 template <class T, size_t N, class Storage>
158 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
159 const FastVector<T, N, Storage> &other)
160 {
161 ensure_capacity(other.mSize);
162 mSize = other.mSize;
163 std::copy(other.begin(), other.end(), begin());
164 return *this;
165 }
166
167 template <class T, size_t N, class Storage>
168 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(FastVector<T, N, Storage> &&other)
169 {
170 swap(*this, other);
171 return *this;
172 }
173
174 template <class T, size_t N, class Storage>
175 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
176 std::initializer_list<value_type> init)
177 {
178 assign_from_initializer_list(init);
179 return *this;
180 }
181
182 template <class T, size_t N, class Storage>
~FastVector()183 FastVector<T, N, Storage>::~FastVector()
184 {
185 clear();
186 if (!uses_fixed_storage())
187 {
188 delete[] mData;
189 }
190 }
191
192 template <class T, size_t N, class Storage>
at(size_type pos)193 typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::at(size_type pos)
194 {
195 ASSERT(pos < mSize);
196 return mData[pos];
197 }
198
199 template <class T, size_t N, class Storage>
at(size_type pos)200 typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::at(
201 size_type pos) const
202 {
203 ASSERT(pos < mSize);
204 return mData[pos];
205 }
206
207 template <class T, size_t N, class Storage>
208 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::operator[](
209 size_type pos)
210 {
211 ASSERT(pos < mSize);
212 return mData[pos];
213 }
214
215 template <class T, size_t N, class Storage>
216 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference
217 FastVector<T, N, Storage>::operator[](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
431 template <class Key, class Value, size_t N>
432 class FastUnorderedMap final
433 {
434 public:
435 using Pair = std::pair<Key, Value>;
436
FastUnorderedMap()437 FastUnorderedMap() {}
~FastUnorderedMap()438 ~FastUnorderedMap() {}
439
insert(Key key,Value value)440 void insert(Key key, Value value)
441 {
442 ASSERT(!contains(key));
443 mData.push_back(Pair(key, value));
444 }
445
contains(Key key)446 bool contains(Key key) const
447 {
448 for (size_t index = 0; index < mData.size(); ++index)
449 {
450 if (mData[index].first == key)
451 return true;
452 }
453 return false;
454 }
455
clear()456 void clear() { mData.clear(); }
457
get(Key key,Value * value)458 bool get(Key key, Value *value) const
459 {
460 for (size_t index = 0; index < mData.size(); ++index)
461 {
462 const Pair &item = mData[index];
463 if (item.first == key)
464 {
465 *value = item.second;
466 return true;
467 }
468 }
469 return false;
470 }
471
empty()472 bool empty() const { return mData.empty(); }
size()473 size_t size() const { return mData.size(); }
474
475 private:
476 FastVector<Pair, N> mData;
477 };
478
479 template <class T, size_t N>
480 class FastUnorderedSet final
481 {
482 public:
FastUnorderedSet()483 FastUnorderedSet() {}
~FastUnorderedSet()484 ~FastUnorderedSet() {}
485
empty()486 bool empty() const { return mData.empty(); }
487
insert(T value)488 void insert(T value)
489 {
490 ASSERT(!contains(value));
491 mData.push_back(value);
492 }
493
contains(T needle)494 bool contains(T needle) const
495 {
496 for (T value : mData)
497 {
498 if (value == needle)
499 return true;
500 }
501 return false;
502 }
503
clear()504 void clear() { mData.clear(); }
505
506 private:
507 FastVector<T, N> mData;
508 };
509
510 class FastIntegerSet final
511 {
512 public:
513 static constexpr size_t kWindowSize = 64;
514 static constexpr size_t kOneLessThanKWindowSize = kWindowSize - 1;
515 static constexpr size_t kShiftForDivision =
516 static_cast<size_t>(rx::Log2(static_cast<unsigned int>(kWindowSize)));
517 using KeyBitSet = angle::BitSet64<kWindowSize>;
518
519 ANGLE_INLINE FastIntegerSet();
520 ANGLE_INLINE ~FastIntegerSet();
521
ensureCapacity(size_t size)522 ANGLE_INLINE void ensureCapacity(size_t size)
523 {
524 if (capacity() <= size)
525 {
526 reserve(size * 2);
527 }
528 }
529
insert(uint64_t key)530 ANGLE_INLINE void insert(uint64_t key)
531 {
532 size_t sizedKey = static_cast<size_t>(key);
533
534 ASSERT(!contains(sizedKey));
535 ensureCapacity(sizedKey);
536 ASSERT(capacity() > sizedKey);
537
538 size_t index = sizedKey >> kShiftForDivision;
539 size_t offset = sizedKey & kOneLessThanKWindowSize;
540
541 mKeyData[index].set(offset, true);
542 }
543
contains(uint64_t key)544 ANGLE_INLINE bool contains(uint64_t key) const
545 {
546 size_t sizedKey = static_cast<size_t>(key);
547
548 size_t index = sizedKey >> kShiftForDivision;
549 size_t offset = sizedKey & kOneLessThanKWindowSize;
550
551 return (sizedKey < capacity()) && (mKeyData[index].test(offset));
552 }
553
clear()554 ANGLE_INLINE void clear() { mKeyData.assign(mKeyData.capacity(), KeyBitSet::Zero()); }
555
empty()556 ANGLE_INLINE bool empty() const
557 {
558 for (KeyBitSet it : mKeyData)
559 {
560 if (it.any())
561 {
562 return false;
563 }
564 }
565 return true;
566 }
567
size()568 ANGLE_INLINE size_t size() const
569 {
570 size_t valid_entries = 0;
571 for (KeyBitSet it : mKeyData)
572 {
573 valid_entries += it.count();
574 }
575 return valid_entries;
576 }
577
578 private:
capacity()579 ANGLE_INLINE size_t capacity() const { return kWindowSize * mKeyData.size(); }
580
reserve(size_t newSize)581 ANGLE_INLINE void reserve(size_t newSize)
582 {
583 size_t alignedSize = rx::roundUpPow2(newSize, kWindowSize);
584 size_t count = alignedSize >> kShiftForDivision;
585
586 mKeyData.resize(count, KeyBitSet::Zero());
587 }
588
589 std::vector<KeyBitSet> mKeyData;
590 };
591
592 // This is needed to accommodate the chromium style guide error -
593 // [chromium-style] Complex constructor has an inlined body.
FastIntegerSet()594 ANGLE_INLINE FastIntegerSet::FastIntegerSet() {}
~FastIntegerSet()595 ANGLE_INLINE FastIntegerSet::~FastIntegerSet() {}
596
597 template <typename Value>
598 class FastIntegerMap final
599 {
600 public:
FastIntegerMap()601 FastIntegerMap() {}
~FastIntegerMap()602 ~FastIntegerMap() {}
603
ensureCapacity(size_t size)604 ANGLE_INLINE void ensureCapacity(size_t size)
605 {
606 // Ensure key set has capacity
607 mKeySet.ensureCapacity(size);
608
609 // Ensure value vector has capacity
610 ensureCapacityImpl(size);
611 }
612
insert(uint64_t key,Value value)613 ANGLE_INLINE void insert(uint64_t key, Value value)
614 {
615 // Insert key
616 ASSERT(!mKeySet.contains(key));
617 mKeySet.insert(key);
618
619 // Insert value
620 size_t sizedKey = static_cast<size_t>(key);
621 ensureCapacityImpl(sizedKey);
622 ASSERT(capacity() > sizedKey);
623 mValueData[sizedKey] = value;
624 }
625
contains(uint64_t key)626 ANGLE_INLINE bool contains(uint64_t key) const { return mKeySet.contains(key); }
627
get(uint64_t key,Value * out)628 ANGLE_INLINE bool get(uint64_t key, Value *out) const
629 {
630 if (!mKeySet.contains(key))
631 {
632 return false;
633 }
634
635 size_t sizedKey = static_cast<size_t>(key);
636 *out = mValueData[sizedKey];
637 return true;
638 }
639
clear()640 ANGLE_INLINE void clear() { mKeySet.clear(); }
641
empty()642 ANGLE_INLINE bool empty() const { return mKeySet.empty(); }
643
size()644 ANGLE_INLINE size_t size() const { return mKeySet.size(); }
645
646 private:
capacity()647 ANGLE_INLINE size_t capacity() const { return mValueData.size(); }
648
ensureCapacityImpl(size_t size)649 ANGLE_INLINE void ensureCapacityImpl(size_t size)
650 {
651 if (capacity() <= size)
652 {
653 reserve(size * 2);
654 }
655 }
656
reserve(size_t newSize)657 ANGLE_INLINE void reserve(size_t newSize)
658 {
659 size_t alignedSize = rx::roundUpPow2(newSize, FastIntegerSet::kWindowSize);
660 mValueData.resize(alignedSize);
661 }
662
663 FastIntegerSet mKeySet;
664 std::vector<Value> mValueData;
665 };
666 } // namespace angle
667
668 #endif // COMMON_FASTVECTOR_H_
669