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