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