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 template <typename... Args>
74 void emplace_back(Args &&... args);
75
76 void pop_back();
77
78 reference front();
79 const_reference front() const;
80
81 reference back();
82 const_reference back() const;
83
84 void swap(FastVector<T, N, Storage> &other);
85
86 void resize(size_type count);
87 void resize(size_type count, const value_type &value);
88
89 // Specialty function that removes a known element and might shuffle the list.
90 void remove_and_permute(const value_type &element);
91
92 private:
93 void assign_from_initializer_list(std::initializer_list<value_type> init);
94 void ensure_capacity(size_t capacity);
95 bool uses_fixed_storage() const;
96
97 Storage mFixedStorage;
98 pointer mData = mFixedStorage.data();
99 size_type mSize = 0;
100 size_type mReservedSize = N;
101 };
102
103 template <class T, size_t N, class StorageN, size_t M, class StorageM>
104 bool operator==(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
105 {
106 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
107 }
108
109 template <class T, size_t N, class StorageN, size_t M, class StorageM>
110 bool operator!=(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
111 {
112 return !(a == b);
113 }
114
115 template <class T, size_t N, class Storage>
uses_fixed_storage()116 ANGLE_INLINE bool FastVector<T, N, Storage>::uses_fixed_storage() const
117 {
118 return mData == mFixedStorage.data();
119 }
120
121 template <class T, size_t N, class Storage>
FastVector()122 FastVector<T, N, Storage>::FastVector()
123 {}
124
125 template <class T, size_t N, class Storage>
FastVector(size_type count,const value_type & value)126 FastVector<T, N, Storage>::FastVector(size_type count, const value_type &value)
127 {
128 ensure_capacity(count);
129 mSize = count;
130 std::fill(begin(), end(), value);
131 }
132
133 template <class T, size_t N, class Storage>
FastVector(size_type count)134 FastVector<T, N, Storage>::FastVector(size_type count)
135 {
136 ensure_capacity(count);
137 mSize = count;
138 }
139
140 template <class T, size_t N, class Storage>
FastVector(const FastVector<T,N,Storage> & other)141 FastVector<T, N, Storage>::FastVector(const FastVector<T, N, Storage> &other)
142 {
143 ensure_capacity(other.mSize);
144 mSize = other.mSize;
145 std::copy(other.begin(), other.end(), begin());
146 }
147
148 template <class T, size_t N, class Storage>
FastVector(FastVector<T,N,Storage> && other)149 FastVector<T, N, Storage>::FastVector(FastVector<T, N, Storage> &&other) : FastVector()
150 {
151 swap(other);
152 }
153
154 template <class T, size_t N, class Storage>
FastVector(std::initializer_list<value_type> init)155 FastVector<T, N, Storage>::FastVector(std::initializer_list<value_type> init)
156 {
157 assign_from_initializer_list(init);
158 }
159
160 template <class T, size_t N, class Storage>
161 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
162 const FastVector<T, N, Storage> &other)
163 {
164 ensure_capacity(other.mSize);
165 mSize = other.mSize;
166 std::copy(other.begin(), other.end(), begin());
167 return *this;
168 }
169
170 template <class T, size_t N, class Storage>
171 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(FastVector<T, N, Storage> &&other)
172 {
173 swap(*this, other);
174 return *this;
175 }
176
177 template <class T, size_t N, class Storage>
178 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
179 std::initializer_list<value_type> init)
180 {
181 assign_from_initializer_list(init);
182 return *this;
183 }
184
185 template <class T, size_t N, class Storage>
~FastVector()186 FastVector<T, N, Storage>::~FastVector()
187 {
188 clear();
189 if (!uses_fixed_storage())
190 {
191 delete[] mData;
192 }
193 }
194
195 template <class T, size_t N, class Storage>
at(size_type pos)196 typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::at(size_type pos)
197 {
198 ASSERT(pos < mSize);
199 return mData[pos];
200 }
201
202 template <class T, size_t N, class Storage>
at(size_type pos)203 typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::at(
204 size_type pos) const
205 {
206 ASSERT(pos < mSize);
207 return mData[pos];
208 }
209
210 template <class T, size_t N, class Storage>
211 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::operator[](
212 size_type pos)
213 {
214 ASSERT(pos < mSize);
215 return mData[pos];
216 }
217
218 template <class T, size_t N, class Storage>
219 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference
220 FastVector<T, N, Storage>::operator[](size_type pos) const
221 {
222 ASSERT(pos < mSize);
223 return mData[pos];
224 }
225
226 template <class T, size_t N, class Storage>
227 ANGLE_INLINE typename FastVector<T, N, Storage>::const_pointer
data()228 angle::FastVector<T, N, Storage>::data() const
229 {
230 return mData;
231 }
232
233 template <class T, size_t N, class Storage>
data()234 ANGLE_INLINE typename FastVector<T, N, Storage>::pointer angle::FastVector<T, N, Storage>::data()
235 {
236 return mData;
237 }
238
239 template <class T, size_t N, class Storage>
begin()240 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::begin()
241 {
242 return mData;
243 }
244
245 template <class T, size_t N, class Storage>
begin()246 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::begin()
247 const
248 {
249 return mData;
250 }
251
252 template <class T, size_t N, class Storage>
end()253 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::end()
254 {
255 return mData + mSize;
256 }
257
258 template <class T, size_t N, class Storage>
end()259 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::end()
260 const
261 {
262 return mData + mSize;
263 }
264
265 template <class T, size_t N, class Storage>
empty()266 ANGLE_INLINE bool FastVector<T, N, Storage>::empty() const
267 {
268 return mSize == 0;
269 }
270
271 template <class T, size_t N, class Storage>
size()272 ANGLE_INLINE typename FastVector<T, N, Storage>::size_type FastVector<T, N, Storage>::size() const
273 {
274 return mSize;
275 }
276
277 template <class T, size_t N, class Storage>
clear()278 void FastVector<T, N, Storage>::clear()
279 {
280 resize(0);
281 }
282
283 template <class T, size_t N, class Storage>
push_back(const value_type & value)284 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(const value_type &value)
285 {
286 if (mSize == mReservedSize)
287 ensure_capacity(mSize + 1);
288 mData[mSize++] = value;
289 }
290
291 template <class T, size_t N, class Storage>
push_back(value_type && value)292 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(value_type &&value)
293 {
294 emplace_back(std::move(value));
295 }
296
297 template <class T, size_t N, class Storage>
298 template <typename... Args>
emplace_back(Args &&...args)299 ANGLE_INLINE void FastVector<T, N, Storage>::emplace_back(Args &&... args)
300 {
301 if (mSize == mReservedSize)
302 ensure_capacity(mSize + 1);
303 mData[mSize++] = std::move(T(std::forward<Args>(args)...));
304 }
305
306 template <class T, size_t N, class Storage>
pop_back()307 ANGLE_INLINE void FastVector<T, N, Storage>::pop_back()
308 {
309 ASSERT(mSize > 0);
310 mSize--;
311 }
312
313 template <class T, size_t N, class Storage>
front()314 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::front()
315 {
316 ASSERT(mSize > 0);
317 return mData[0];
318 }
319
320 template <class T, size_t N, class Storage>
front()321 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::front()
322 const
323 {
324 ASSERT(mSize > 0);
325 return mData[0];
326 }
327
328 template <class T, size_t N, class Storage>
back()329 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::back()
330 {
331 ASSERT(mSize > 0);
332 return mData[mSize - 1];
333 }
334
335 template <class T, size_t N, class Storage>
back()336 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::back()
337 const
338 {
339 ASSERT(mSize > 0);
340 return mData[mSize - 1];
341 }
342
343 template <class T, size_t N, class Storage>
swap(FastVector<T,N,Storage> & other)344 void FastVector<T, N, Storage>::swap(FastVector<T, N, Storage> &other)
345 {
346 std::swap(mSize, other.mSize);
347
348 pointer tempData = other.mData;
349 if (uses_fixed_storage())
350 other.mData = other.mFixedStorage.data();
351 else
352 other.mData = mData;
353 if (tempData == other.mFixedStorage.data())
354 mData = mFixedStorage.data();
355 else
356 mData = tempData;
357 std::swap(mReservedSize, other.mReservedSize);
358
359 if (uses_fixed_storage() || other.uses_fixed_storage())
360 std::swap(mFixedStorage, other.mFixedStorage);
361 }
362
363 template <class T, size_t N, class Storage>
resize(size_type count)364 void FastVector<T, N, Storage>::resize(size_type count)
365 {
366 if (count > mSize)
367 {
368 ensure_capacity(count);
369 }
370 mSize = count;
371 }
372
373 template <class T, size_t N, class Storage>
resize(size_type count,const value_type & value)374 void FastVector<T, N, Storage>::resize(size_type count, const value_type &value)
375 {
376 if (count > mSize)
377 {
378 ensure_capacity(count);
379 std::fill(mData + mSize, mData + count, value);
380 }
381 mSize = count;
382 }
383
384 template <class T, size_t N, class Storage>
assign_from_initializer_list(std::initializer_list<value_type> init)385 void FastVector<T, N, Storage>::assign_from_initializer_list(std::initializer_list<value_type> init)
386 {
387 ensure_capacity(init.size());
388 mSize = init.size();
389 size_t index = 0;
390 for (auto &value : init)
391 {
392 mData[index++] = value;
393 }
394 }
395
396 template <class T, size_t N, class Storage>
remove_and_permute(const value_type & element)397 ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(const value_type &element)
398 {
399 size_t len = mSize - 1;
400 for (size_t index = 0; index < len; ++index)
401 {
402 if (mData[index] == element)
403 {
404 mData[index] = std::move(mData[len]);
405 break;
406 }
407 }
408 pop_back();
409 }
410
411 template <class T, size_t N, class Storage>
ensure_capacity(size_t capacity)412 void FastVector<T, N, Storage>::ensure_capacity(size_t capacity)
413 {
414 // We have a minimum capacity of N.
415 if (mReservedSize < capacity)
416 {
417 ASSERT(capacity > N);
418 size_type newSize = std::max(mReservedSize, N);
419 while (newSize < capacity)
420 {
421 newSize *= 2;
422 }
423
424 pointer newData = new value_type[newSize];
425
426 if (mSize > 0)
427 {
428 std::move(begin(), end(), newData);
429 }
430
431 if (!uses_fixed_storage())
432 {
433 delete[] mData;
434 }
435
436 mData = newData;
437 mReservedSize = newSize;
438 }
439 }
440
441 template <class Key, class Value, size_t N>
442 class FastUnorderedMap final
443 {
444 public:
445 using Pair = std::pair<Key, Value>;
446
FastUnorderedMap()447 FastUnorderedMap() {}
~FastUnorderedMap()448 ~FastUnorderedMap() {}
449
insert(Key key,Value value)450 void insert(Key key, Value value)
451 {
452 ASSERT(!contains(key));
453 mData.push_back(Pair(key, value));
454 }
455
contains(Key key)456 bool contains(Key key) const
457 {
458 for (size_t index = 0; index < mData.size(); ++index)
459 {
460 if (mData[index].first == key)
461 return true;
462 }
463 return false;
464 }
465
clear()466 void clear() { mData.clear(); }
467
get(Key key,Value * value)468 bool get(Key key, Value *value) const
469 {
470 for (size_t index = 0; index < mData.size(); ++index)
471 {
472 const Pair &item = mData[index];
473 if (item.first == key)
474 {
475 *value = item.second;
476 return true;
477 }
478 }
479 return false;
480 }
481
empty()482 bool empty() const { return mData.empty(); }
size()483 size_t size() const { return mData.size(); }
484
485 private:
486 FastVector<Pair, N> mData;
487 };
488
489 template <class T, size_t N>
490 class FastUnorderedSet final
491 {
492 public:
FastUnorderedSet()493 FastUnorderedSet() {}
~FastUnorderedSet()494 ~FastUnorderedSet() {}
495
empty()496 bool empty() const { return mData.empty(); }
497
insert(T value)498 void insert(T value)
499 {
500 ASSERT(!contains(value));
501 mData.push_back(value);
502 }
503
contains(T needle)504 bool contains(T needle) const
505 {
506 for (T value : mData)
507 {
508 if (value == needle)
509 return true;
510 }
511 return false;
512 }
513
clear()514 void clear() { mData.clear(); }
515
516 private:
517 FastVector<T, N> mData;
518 };
519
520 class FastIntegerSet final
521 {
522 public:
523 static constexpr size_t kWindowSize = 64;
524 static constexpr size_t kOneLessThanKWindowSize = kWindowSize - 1;
525 static constexpr size_t kShiftForDivision =
526 static_cast<size_t>(rx::Log2(static_cast<unsigned int>(kWindowSize)));
527 using KeyBitSet = angle::BitSet64<kWindowSize>;
528
529 ANGLE_INLINE FastIntegerSet();
530 ANGLE_INLINE ~FastIntegerSet();
531
ensureCapacity(size_t size)532 ANGLE_INLINE void ensureCapacity(size_t size)
533 {
534 if (capacity() <= size)
535 {
536 reserve(size * 2);
537 }
538 }
539
insert(uint64_t key)540 ANGLE_INLINE void insert(uint64_t key)
541 {
542 size_t sizedKey = static_cast<size_t>(key);
543
544 ASSERT(!contains(sizedKey));
545 ensureCapacity(sizedKey);
546 ASSERT(capacity() > sizedKey);
547
548 size_t index = sizedKey >> kShiftForDivision;
549 size_t offset = sizedKey & kOneLessThanKWindowSize;
550
551 mKeyData[index].set(offset, true);
552 }
553
contains(uint64_t key)554 ANGLE_INLINE bool contains(uint64_t key) const
555 {
556 size_t sizedKey = static_cast<size_t>(key);
557
558 size_t index = sizedKey >> kShiftForDivision;
559 size_t offset = sizedKey & kOneLessThanKWindowSize;
560
561 return (sizedKey < capacity()) && (mKeyData[index].test(offset));
562 }
563
clear()564 ANGLE_INLINE void clear()
565 {
566 for (KeyBitSet &it : mKeyData)
567 {
568 it.reset();
569 }
570 }
571
empty()572 ANGLE_INLINE bool empty() const
573 {
574 for (const KeyBitSet &it : mKeyData)
575 {
576 if (it.any())
577 {
578 return false;
579 }
580 }
581 return true;
582 }
583
size()584 ANGLE_INLINE size_t size() const
585 {
586 size_t valid_entries = 0;
587 for (const KeyBitSet &it : mKeyData)
588 {
589 valid_entries += it.count();
590 }
591 return valid_entries;
592 }
593
594 private:
capacity()595 ANGLE_INLINE size_t capacity() const { return kWindowSize * mKeyData.size(); }
596
reserve(size_t newSize)597 ANGLE_INLINE void reserve(size_t newSize)
598 {
599 size_t alignedSize = rx::roundUpPow2(newSize, kWindowSize);
600 size_t count = alignedSize >> kShiftForDivision;
601
602 mKeyData.resize(count, KeyBitSet::Zero());
603 }
604
605 std::vector<KeyBitSet> mKeyData;
606 };
607
608 // This is needed to accommodate the chromium style guide error -
609 // [chromium-style] Complex constructor has an inlined body.
FastIntegerSet()610 ANGLE_INLINE FastIntegerSet::FastIntegerSet() {}
~FastIntegerSet()611 ANGLE_INLINE FastIntegerSet::~FastIntegerSet() {}
612
613 template <typename Value>
614 class FastIntegerMap final
615 {
616 public:
FastIntegerMap()617 FastIntegerMap() {}
~FastIntegerMap()618 ~FastIntegerMap() {}
619
ensureCapacity(size_t size)620 ANGLE_INLINE void ensureCapacity(size_t size)
621 {
622 // Ensure key set has capacity
623 mKeySet.ensureCapacity(size);
624
625 // Ensure value vector has capacity
626 ensureCapacityImpl(size);
627 }
628
insert(uint64_t key,Value value)629 ANGLE_INLINE void insert(uint64_t key, Value value)
630 {
631 // Insert key
632 ASSERT(!mKeySet.contains(key));
633 mKeySet.insert(key);
634
635 // Insert value
636 size_t sizedKey = static_cast<size_t>(key);
637 ensureCapacityImpl(sizedKey);
638 ASSERT(capacity() > sizedKey);
639 mValueData[sizedKey] = value;
640 }
641
contains(uint64_t key)642 ANGLE_INLINE bool contains(uint64_t key) const { return mKeySet.contains(key); }
643
get(uint64_t key,Value * out)644 ANGLE_INLINE bool get(uint64_t key, Value *out) const
645 {
646 if (!mKeySet.contains(key))
647 {
648 return false;
649 }
650
651 size_t sizedKey = static_cast<size_t>(key);
652 *out = mValueData[sizedKey];
653 return true;
654 }
655
clear()656 ANGLE_INLINE void clear() { mKeySet.clear(); }
657
empty()658 ANGLE_INLINE bool empty() const { return mKeySet.empty(); }
659
size()660 ANGLE_INLINE size_t size() const { return mKeySet.size(); }
661
662 private:
capacity()663 ANGLE_INLINE size_t capacity() const { return mValueData.size(); }
664
ensureCapacityImpl(size_t size)665 ANGLE_INLINE void ensureCapacityImpl(size_t size)
666 {
667 if (capacity() <= size)
668 {
669 reserve(size * 2);
670 }
671 }
672
reserve(size_t newSize)673 ANGLE_INLINE void reserve(size_t newSize)
674 {
675 size_t alignedSize = rx::roundUpPow2(newSize, FastIntegerSet::kWindowSize);
676 mValueData.resize(alignedSize);
677 }
678
679 FastIntegerSet mKeySet;
680 std::vector<Value> mValueData;
681 };
682 } // namespace angle
683
684 #endif // COMMON_FASTVECTOR_H_
685