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 <cstring>
20 #include <initializer_list>
21 #include <iterator>
22
23 namespace angle
24 {
25
26 template <class Iter>
27 class WrapIter
28 {
29 public:
30 typedef Iter iterator_type;
31 typedef typename std::iterator_traits<iterator_type>::value_type value_type;
32 typedef typename std::iterator_traits<iterator_type>::difference_type difference_type;
33 typedef typename std::iterator_traits<iterator_type>::pointer pointer;
34 typedef typename std::iterator_traits<iterator_type>::reference reference;
35 typedef typename std::iterator_traits<iterator_type>::iterator_category iterator_category;
36
WrapIter()37 WrapIter() : mIter() {}
38 WrapIter(const WrapIter &x) = default;
39 WrapIter &operator=(const WrapIter &x) = default;
WrapIter(const Iter & iter)40 WrapIter(const Iter &iter) : mIter(iter) {}
41 ~WrapIter() = default;
42
43 bool operator==(const WrapIter &x) const { return mIter == x.mIter; }
44 bool operator!=(const WrapIter &x) const { return mIter != x.mIter; }
45 bool operator<(const WrapIter &x) const { return mIter < x.mIter; }
46 bool operator<=(const WrapIter &x) const { return mIter <= x.mIter; }
47 bool operator>(const WrapIter &x) const { return mIter > x.mIter; }
48 bool operator>=(const WrapIter &x) const { return mIter >= x.mIter; }
49
50 WrapIter &operator++()
51 {
52 mIter++;
53 return *this;
54 }
55
56 WrapIter operator++(int)
57 {
58 WrapIter tmp(mIter);
59 mIter++;
60 return tmp;
61 }
62
63 WrapIter operator+(difference_type n)
64 {
65 WrapIter tmp(mIter);
66 tmp.mIter += n;
67 return tmp;
68 }
69
70 WrapIter operator-(difference_type n)
71 {
72 WrapIter tmp(mIter);
73 tmp.mIter -= n;
74 return tmp;
75 }
76
77 difference_type operator-(const WrapIter &x) const { return mIter - x.mIter; }
78
79 iterator_type operator->() const { return mIter; }
80
81 reference operator*() const { return *mIter; }
82
83 private:
84 iterator_type mIter;
85 };
86
87 template <class T, size_t N, class Storage = std::array<T, N>>
88 class FastVector final
89 {
90 public:
91 using value_type = typename Storage::value_type;
92 using size_type = typename Storage::size_type;
93 using reference = typename Storage::reference;
94 using const_reference = typename Storage::const_reference;
95 using pointer = typename Storage::pointer;
96 using const_pointer = typename Storage::const_pointer;
97 using iterator = WrapIter<T *>;
98 using const_iterator = WrapIter<const T *>;
99
100 // This class does not call destructors when resizing down (for performance reasons).
101 static_assert(std::is_trivially_destructible_v<value_type>);
102
103 FastVector();
104 FastVector(size_type count, const value_type &value);
105 FastVector(size_type count);
106
107 FastVector(const FastVector<T, N, Storage> &other);
108 FastVector(FastVector<T, N, Storage> &&other);
109 FastVector(std::initializer_list<value_type> init);
110
111 template <class InputIt, std::enable_if_t<!std::is_integral<InputIt>::value, bool> = true>
112 FastVector(InputIt first, InputIt last);
113
114 FastVector<T, N, Storage> &operator=(const FastVector<T, N, Storage> &other);
115 FastVector<T, N, Storage> &operator=(FastVector<T, N, Storage> &&other);
116 FastVector<T, N, Storage> &operator=(std::initializer_list<value_type> init);
117
118 ~FastVector();
119
120 reference at(size_type pos);
121 const_reference at(size_type pos) const;
122
123 reference operator[](size_type pos);
124 const_reference operator[](size_type pos) const;
125
126 pointer data();
127 const_pointer data() const;
128
129 iterator begin();
130 const_iterator begin() const;
131
132 iterator end();
133 const_iterator end() const;
134
135 bool empty() const;
136 size_type size() const;
137
138 void clear();
139
140 void push_back(const value_type &value);
141 void push_back(value_type &&value);
142
143 template <typename... Args>
144 void emplace_back(Args &&...args);
145
146 void pop_back();
147
148 reference front();
149 const_reference front() const;
150
151 reference back();
152 const_reference back() const;
153
154 void swap(FastVector<T, N, Storage> &other);
155 void resetWithRawData(size_type count, const uint8_t *data);
156
157 void resize(size_type count);
158 void resize(size_type count, const value_type &value);
159
160 // Only for use with non trivially constructible types.
161 // When increasing size, new elements may have previous values. Use with caution in cases when
162 // initialization of new elements is not required (will be explicitly initialized later), or
163 // is never resizing down (not possible to reuse previous values).
164 void resize_maybe_value_reuse(size_type count);
165 // Only for use with non trivially constructible types.
166 // No new elements added, so this function is safe to use. Generates ASSERT() if try resize up.
167 void resize_down(size_type count);
168
169 void reserve(size_type count);
170
171 // Specialty function that removes a known element and might shuffle the list.
172 void remove_and_permute(const value_type &element);
173 void remove_and_permute(iterator pos);
174
175 private:
176 void assign_from_initializer_list(std::initializer_list<value_type> init);
177 void ensure_capacity(size_t capacity);
178 bool uses_fixed_storage() const;
179 void resize_impl(size_type count);
180
181 Storage mFixedStorage;
182 pointer mData = mFixedStorage.data();
183 size_type mSize = 0;
184 size_type mReservedSize = N;
185 };
186
187 template <class T, size_t N, class StorageN, size_t M, class StorageM>
188 bool operator==(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
189 {
190 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
191 }
192
193 template <class T, size_t N, class StorageN, size_t M, class StorageM>
194 bool operator!=(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
195 {
196 return !(a == b);
197 }
198
199 template <class T, size_t N, class Storage>
uses_fixed_storage()200 ANGLE_INLINE bool FastVector<T, N, Storage>::uses_fixed_storage() const
201 {
202 return mData == mFixedStorage.data();
203 }
204
205 template <class T, size_t N, class Storage>
FastVector()206 FastVector<T, N, Storage>::FastVector()
207 {}
208
209 template <class T, size_t N, class Storage>
FastVector(size_type count,const value_type & value)210 FastVector<T, N, Storage>::FastVector(size_type count, const value_type &value)
211 {
212 ensure_capacity(count);
213 mSize = count;
214 std::fill(begin(), end(), value);
215 }
216
217 template <class T, size_t N, class Storage>
FastVector(size_type count)218 FastVector<T, N, Storage>::FastVector(size_type count)
219 {
220 ensure_capacity(count);
221 mSize = count;
222 }
223
224 template <class T, size_t N, class Storage>
FastVector(const FastVector<T,N,Storage> & other)225 FastVector<T, N, Storage>::FastVector(const FastVector<T, N, Storage> &other)
226 : FastVector(other.begin(), other.end())
227 {}
228
229 template <class T, size_t N, class Storage>
FastVector(FastVector<T,N,Storage> && other)230 FastVector<T, N, Storage>::FastVector(FastVector<T, N, Storage> &&other) : FastVector()
231 {
232 swap(other);
233 }
234
235 template <class T, size_t N, class Storage>
FastVector(std::initializer_list<value_type> init)236 FastVector<T, N, Storage>::FastVector(std::initializer_list<value_type> init)
237 {
238 assign_from_initializer_list(init);
239 }
240
241 template <class T, size_t N, class Storage>
242 template <class InputIt, std::enable_if_t<!std::is_integral<InputIt>::value, bool>>
FastVector(InputIt first,InputIt last)243 FastVector<T, N, Storage>::FastVector(InputIt first, InputIt last)
244 {
245 size_t newSize = last - first;
246 ensure_capacity(newSize);
247 mSize = newSize;
248 std::copy(first, last, begin());
249 }
250
251 template <class T, size_t N, class Storage>
252 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
253 const FastVector<T, N, Storage> &other)
254 {
255 ensure_capacity(other.mSize);
256 mSize = other.mSize;
257 std::copy(other.begin(), other.end(), begin());
258 return *this;
259 }
260
261 template <class T, size_t N, class Storage>
262 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(FastVector<T, N, Storage> &&other)
263 {
264 swap(other);
265 return *this;
266 }
267
268 template <class T, size_t N, class Storage>
269 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
270 std::initializer_list<value_type> init)
271 {
272 assign_from_initializer_list(init);
273 return *this;
274 }
275
276 template <class T, size_t N, class Storage>
~FastVector()277 FastVector<T, N, Storage>::~FastVector()
278 {
279 clear();
280 if (!uses_fixed_storage())
281 {
282 delete[] mData;
283 }
284 }
285
286 template <class T, size_t N, class Storage>
at(size_type pos)287 typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::at(size_type pos)
288 {
289 ASSERT(pos < mSize);
290 return mData[pos];
291 }
292
293 template <class T, size_t N, class Storage>
at(size_type pos)294 typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::at(
295 size_type pos) const
296 {
297 ASSERT(pos < mSize);
298 return mData[pos];
299 }
300
301 template <class T, size_t N, class Storage>
302 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::operator[](
303 size_type pos)
304 {
305 ASSERT(pos < mSize);
306 return mData[pos];
307 }
308
309 template <class T, size_t N, class Storage>
310 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference
311 FastVector<T, N, Storage>::operator[](size_type pos) const
312 {
313 ASSERT(pos < mSize);
314 return mData[pos];
315 }
316
317 template <class T, size_t N, class Storage>
318 ANGLE_INLINE typename FastVector<T, N, Storage>::const_pointer
data()319 angle::FastVector<T, N, Storage>::data() const
320 {
321 return mData;
322 }
323
324 template <class T, size_t N, class Storage>
data()325 ANGLE_INLINE typename FastVector<T, N, Storage>::pointer angle::FastVector<T, N, Storage>::data()
326 {
327 return mData;
328 }
329
330 template <class T, size_t N, class Storage>
begin()331 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::begin()
332 {
333 return mData;
334 }
335
336 template <class T, size_t N, class Storage>
begin()337 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::begin()
338 const
339 {
340 return mData;
341 }
342
343 template <class T, size_t N, class Storage>
end()344 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::end()
345 {
346 return mData + mSize;
347 }
348
349 template <class T, size_t N, class Storage>
end()350 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::end()
351 const
352 {
353 return mData + mSize;
354 }
355
356 template <class T, size_t N, class Storage>
empty()357 ANGLE_INLINE bool FastVector<T, N, Storage>::empty() const
358 {
359 return mSize == 0;
360 }
361
362 template <class T, size_t N, class Storage>
size()363 ANGLE_INLINE typename FastVector<T, N, Storage>::size_type FastVector<T, N, Storage>::size() const
364 {
365 return mSize;
366 }
367
368 template <class T, size_t N, class Storage>
clear()369 void FastVector<T, N, Storage>::clear()
370 {
371 resize_impl(0);
372 }
373
374 template <class T, size_t N, class Storage>
push_back(const value_type & value)375 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(const value_type &value)
376 {
377 if (mSize == mReservedSize)
378 ensure_capacity(mSize + 1);
379 mData[mSize++] = value;
380 }
381
382 template <class T, size_t N, class Storage>
push_back(value_type && value)383 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(value_type &&value)
384 {
385 emplace_back(std::move(value));
386 }
387
388 template <class T, size_t N, class Storage>
389 template <typename... Args>
emplace_back(Args &&...args)390 ANGLE_INLINE void FastVector<T, N, Storage>::emplace_back(Args &&...args)
391 {
392 if (mSize == mReservedSize)
393 ensure_capacity(mSize + 1);
394 mData[mSize++] = std::move(T(std::forward<Args>(args)...));
395 }
396
397 template <class T, size_t N, class Storage>
pop_back()398 ANGLE_INLINE void FastVector<T, N, Storage>::pop_back()
399 {
400 ASSERT(mSize > 0);
401 mSize--;
402 }
403
404 template <class T, size_t N, class Storage>
front()405 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::front()
406 {
407 ASSERT(mSize > 0);
408 return mData[0];
409 }
410
411 template <class T, size_t N, class Storage>
front()412 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::front()
413 const
414 {
415 ASSERT(mSize > 0);
416 return mData[0];
417 }
418
419 template <class T, size_t N, class Storage>
back()420 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::back()
421 {
422 ASSERT(mSize > 0);
423 return mData[mSize - 1];
424 }
425
426 template <class T, size_t N, class Storage>
back()427 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::back()
428 const
429 {
430 ASSERT(mSize > 0);
431 return mData[mSize - 1];
432 }
433
434 template <class T, size_t N, class Storage>
swap(FastVector<T,N,Storage> & other)435 void FastVector<T, N, Storage>::swap(FastVector<T, N, Storage> &other)
436 {
437 std::swap(mSize, other.mSize);
438
439 pointer tempData = other.mData;
440 if (uses_fixed_storage())
441 other.mData = other.mFixedStorage.data();
442 else
443 other.mData = mData;
444 if (tempData == other.mFixedStorage.data())
445 mData = mFixedStorage.data();
446 else
447 mData = tempData;
448 std::swap(mReservedSize, other.mReservedSize);
449
450 if (uses_fixed_storage() || other.uses_fixed_storage())
451 std::swap(mFixedStorage, other.mFixedStorage);
452 }
453
454 template <class T, size_t N, class Storage>
resetWithRawData(size_type count,const uint8_t * data)455 void FastVector<T, N, Storage>::resetWithRawData(size_type count, const uint8_t *data)
456 {
457 static_assert(std::is_trivially_copyable<value_type>(),
458 "This is a special method for trivially copyable types.");
459 ASSERT(count > 0 && data != nullptr);
460 resize_impl(count);
461 std::memcpy(mData, data, count * sizeof(value_type));
462 }
463
464 template <class T, size_t N, class Storage>
resize(size_type count)465 ANGLE_INLINE void FastVector<T, N, Storage>::resize(size_type count)
466 {
467 // Trivially constructible types will have undefined values when created therefore reusing
468 // previous values after resize should not be a problem..
469 static_assert(std::is_trivially_constructible_v<value_type>,
470 "For non trivially constructible types please use: resize(count, value), "
471 "resize_maybe_value_reuse(count), or resize_down(count) methods.");
472 resize_impl(count);
473 }
474
475 template <class T, size_t N, class Storage>
resize_maybe_value_reuse(size_type count)476 ANGLE_INLINE void FastVector<T, N, Storage>::resize_maybe_value_reuse(size_type count)
477 {
478 static_assert(!std::is_trivially_constructible_v<value_type>,
479 "This is a special method for non trivially constructible types. "
480 "Please use regular resize(count) method.");
481 resize_impl(count);
482 }
483
484 template <class T, size_t N, class Storage>
resize_down(size_type count)485 ANGLE_INLINE void FastVector<T, N, Storage>::resize_down(size_type count)
486 {
487 static_assert(!std::is_trivially_constructible_v<value_type>,
488 "This is a special method for non trivially constructible types. "
489 "Please use regular resize(count) method.");
490 ASSERT(count <= mSize);
491 resize_impl(count);
492 }
493
494 template <class T, size_t N, class Storage>
resize_impl(size_type count)495 void FastVector<T, N, Storage>::resize_impl(size_type count)
496 {
497 if (count > mSize)
498 {
499 ensure_capacity(count);
500 }
501 mSize = count;
502 }
503
504 template <class T, size_t N, class Storage>
resize(size_type count,const value_type & value)505 void FastVector<T, N, Storage>::resize(size_type count, const value_type &value)
506 {
507 if (count > mSize)
508 {
509 ensure_capacity(count);
510 std::fill(mData + mSize, mData + count, value);
511 }
512 mSize = count;
513 }
514
515 template <class T, size_t N, class Storage>
reserve(size_type count)516 void FastVector<T, N, Storage>::reserve(size_type count)
517 {
518 ensure_capacity(count);
519 }
520
521 template <class T, size_t N, class Storage>
assign_from_initializer_list(std::initializer_list<value_type> init)522 void FastVector<T, N, Storage>::assign_from_initializer_list(std::initializer_list<value_type> init)
523 {
524 ensure_capacity(init.size());
525 mSize = init.size();
526 size_t index = 0;
527 for (auto &value : init)
528 {
529 mData[index++] = value;
530 }
531 }
532
533 template <class T, size_t N, class Storage>
remove_and_permute(const value_type & element)534 ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(const value_type &element)
535 {
536 size_t len = mSize - 1;
537 for (size_t index = 0; index < len; ++index)
538 {
539 if (mData[index] == element)
540 {
541 mData[index] = std::move(mData[len]);
542 break;
543 }
544 }
545 pop_back();
546 }
547
548 template <class T, size_t N, class Storage>
remove_and_permute(iterator pos)549 ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(iterator pos)
550 {
551 ASSERT(pos >= begin());
552 ASSERT(pos < end());
553 size_t len = mSize - 1;
554 *pos = std::move(mData[len]);
555 pop_back();
556 }
557
558 template <class T, size_t N, class Storage>
ensure_capacity(size_t capacity)559 void FastVector<T, N, Storage>::ensure_capacity(size_t capacity)
560 {
561 // We have a minimum capacity of N.
562 if (mReservedSize < capacity)
563 {
564 ASSERT(capacity > N);
565 size_type newSize = std::max(mReservedSize, N);
566 while (newSize < capacity)
567 {
568 newSize *= 2;
569 }
570
571 pointer newData = new value_type[newSize];
572
573 if (mSize > 0)
574 {
575 std::move(begin(), end(), newData);
576 }
577
578 if (!uses_fixed_storage())
579 {
580 delete[] mData;
581 }
582
583 mData = newData;
584 mReservedSize = newSize;
585 }
586 }
587
588 template <class Value, size_t N, class Storage = FastVector<Value, N>>
589 class FastMap final
590 {
591 public:
592 using value_type = typename Storage::value_type;
593 using size_type = typename Storage::size_type;
594 using reference = typename Storage::reference;
595 using const_reference = typename Storage::const_reference;
596 using pointer = typename Storage::pointer;
597 using const_pointer = typename Storage::const_pointer;
598 using iterator = typename Storage::iterator;
599 using const_iterator = typename Storage::const_iterator;
600
FastMap()601 FastMap() {}
~FastMap()602 ~FastMap() {}
603
604 Value &operator[](uint32_t key)
605 {
606 if (mData.size() <= key)
607 {
608 mData.resize(key + 1, {});
609 }
610 return at(key);
611 }
612
613 const Value &operator[](uint32_t key) const { return at(key); }
614
at(uint32_t key)615 Value &at(uint32_t key)
616 {
617 ASSERT(key < mData.size());
618 return mData[key];
619 }
620
at(uint32_t key)621 const Value &at(uint32_t key) const
622 {
623 ASSERT(key < mData.size());
624 return mData[key];
625 }
626
clear()627 void clear() { mData.clear(); }
628
resetWithRawData(size_type count,const uint8_t * data)629 void resetWithRawData(size_type count, const uint8_t *data)
630 {
631 mData.resetWithRawData(count, data);
632 }
633
empty()634 bool empty() const { return mData.empty(); }
size()635 size_t size() const { return mData.size(); }
636
data()637 const Value *data() const { return mData.data(); }
638
639 bool operator==(const FastMap<Value, N> &other) const
640 {
641 return (size() == other.size()) &&
642 (memcmp(data(), other.data(), size() * sizeof(Value)) == 0);
643 }
644
begin()645 iterator begin() { return mData.begin(); }
begin()646 const_iterator begin() const { return mData.begin(); }
647
end()648 iterator end() { return mData.end(); }
end()649 const_iterator end() const { return mData.end(); }
650
651 private:
652 FastVector<Value, N> mData;
653 };
654
655 template <class Key, class Value, size_t N>
656 class FlatUnorderedMap final
657 {
658 public:
659 using Pair = std::pair<Key, Value>;
660 using Storage = FastVector<Pair, N>;
661 using iterator = typename Storage::iterator;
662 using const_iterator = typename Storage::const_iterator;
663
664 FlatUnorderedMap() = default;
665 ~FlatUnorderedMap() = default;
666
begin()667 iterator begin() { return mData.begin(); }
begin()668 const_iterator begin() const { return mData.begin(); }
end()669 iterator end() { return mData.end(); }
end()670 const_iterator end() const { return mData.end(); }
671
find(const Key & key)672 iterator find(const Key &key)
673 {
674 for (auto it = mData.begin(); it != mData.end(); ++it)
675 {
676 if (it->first == key)
677 {
678 return it;
679 }
680 }
681 return mData.end();
682 }
683
find(const Key & key)684 const_iterator find(const Key &key) const
685 {
686 for (auto it = mData.begin(); it != mData.end(); ++it)
687 {
688 if (it->first == key)
689 {
690 return it;
691 }
692 }
693 return mData.end();
694 }
695
696 Value &operator[](const Key &key)
697 {
698 iterator it = find(key);
699 if (it != end())
700 {
701 return it->second;
702 }
703
704 mData.push_back(Pair(key, {}));
705 return mData.back().second;
706 }
707
insert(Pair pair)708 void insert(Pair pair)
709 {
710 ASSERT(!contains(pair.first));
711 mData.push_back(std::move(pair));
712 }
713
insert(const Key & key,Value value)714 void insert(const Key &key, Value value) { insert(Pair(key, value)); }
715
erase(iterator pos)716 void erase(iterator pos) { mData.remove_and_permute(pos); }
717
contains(const Key & key)718 bool contains(const Key &key) const { return find(key) != end(); }
719
clear()720 void clear() { mData.clear(); }
721
get(const Key & key,Value * value)722 bool get(const Key &key, Value *value) const
723 {
724 auto it = find(key);
725 if (it != end())
726 {
727 *value = it->second;
728 return true;
729 }
730 return false;
731 }
732
empty()733 bool empty() const { return mData.empty(); }
size()734 size_t size() const { return mData.size(); }
735
736 private:
737 FastVector<Pair, N> mData;
738 };
739
740 template <class T, size_t N>
741 class FlatUnorderedSet final
742 {
743 public:
744 using Storage = FastVector<T, N>;
745 using iterator = typename Storage::iterator;
746 using const_iterator = typename Storage::const_iterator;
747
748 FlatUnorderedSet() = default;
749 ~FlatUnorderedSet() = default;
750
begin()751 iterator begin() { return mData.begin(); }
begin()752 const_iterator begin() const { return mData.begin(); }
end()753 iterator end() { return mData.end(); }
end()754 const_iterator end() const { return mData.end(); }
755
find(const T & value)756 iterator find(const T &value)
757 {
758 for (auto it = mData.begin(); it != mData.end(); ++it)
759 {
760 if (*it == value)
761 {
762 return it;
763 }
764 }
765 return mData.end();
766 }
767
find(const T & value)768 const_iterator find(const T &value) const
769 {
770 for (auto it = mData.begin(); it != mData.end(); ++it)
771 {
772 if (*it == value)
773 {
774 return it;
775 }
776 }
777 return mData.end();
778 }
779
empty()780 bool empty() const { return mData.empty(); }
781
insert(const T & value)782 void insert(const T &value)
783 {
784 ASSERT(!contains(value));
785 mData.push_back(value);
786 }
787
erase(const T & value)788 void erase(const T &value)
789 {
790 ASSERT(contains(value));
791 mData.remove_and_permute(value);
792 }
793
remove(const T & value)794 void remove(const T &value) { erase(value); }
795
contains(const T & value)796 bool contains(const T &value) const { return find(value) != end(); }
797
clear()798 void clear() { mData.clear(); }
799
800 bool operator==(const FlatUnorderedSet<T, N> &other) const { return mData == other.mData; }
801
802 private:
803 Storage mData;
804 };
805 } // namespace angle
806
807 #endif // COMMON_FASTVECTOR_H_
808