1 //
2 // Copyright 2015 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 // bitset_utils:
7 //   Bitset-related helper classes, such as a fast iterator to scan for set bits.
8 //
9 
10 #ifndef COMMON_BITSETITERATOR_H_
11 #define COMMON_BITSETITERATOR_H_
12 
13 #include <stdint.h>
14 
15 #include <array>
16 
17 #include "common/angleutils.h"
18 #include "common/debug.h"
19 #include "common/mathutil.h"
20 #include "common/platform.h"
21 
22 namespace angle
23 {
24 // Given x, create 1 << x.
25 template <typename BitsT, typename ParamT>
Bit(ParamT x)26 constexpr static BitsT Bit(ParamT x)
27 {
28     // It's undefined behavior if the shift size is equal to or larger than the width of the type.
29     ASSERT(static_cast<size_t>(x) < sizeof(BitsT) * 8);
30 
31     return (static_cast<BitsT>(1) << static_cast<size_t>(x));
32 }
33 
34 // Given x, create (1 << x) - 1, i.e. a mask with x bits set.
35 template <typename BitsT, typename ParamT>
BitMask(ParamT x)36 constexpr static BitsT BitMask(ParamT x)
37 {
38     if (static_cast<size_t>(x) == 0)
39     {
40         return 0;
41     }
42     return ((Bit<BitsT>(static_cast<ParamT>(static_cast<size_t>(x) - 1)) - 1) << 1) | 1;
43 }
44 
45 template <size_t N, typename BitsT, typename ParamT = std::size_t>
46 class BitSetT final
47 {
48   public:
49     class Reference final
50     {
51       public:
~Reference()52         ~Reference() {}
53         Reference &operator=(bool x)
54         {
55             mParent->set(mBit, x);
56             return *this;
57         }
58         explicit operator bool() const { return mParent->test(mBit); }
59 
60       private:
61         friend class BitSetT;
62 
Reference(BitSetT * parent,ParamT bit)63         Reference(BitSetT *parent, ParamT bit) : mParent(parent), mBit(bit) {}
64 
65         BitSetT *mParent;
66         ParamT mBit;
67     };
68 
69     class Iterator final
70     {
71       public:
72         Iterator(const BitSetT &bits);
73         Iterator &operator++();
74 
75         bool operator==(const Iterator &other) const;
76         bool operator!=(const Iterator &other) const;
77         ParamT operator*() const;
78 
79         // These helper functions allow mutating an iterator in-flight.
80         // They only operate on later bits to ensure we don't iterate the same bit twice.
resetLaterBit(std::size_t index)81         void resetLaterBit(std::size_t index)
82         {
83             ASSERT(index > mCurrentBit);
84             mBitsCopy.reset(index);
85         }
86 
setLaterBit(std::size_t index)87         void setLaterBit(std::size_t index)
88         {
89             ASSERT(index > mCurrentBit);
90             mBitsCopy.set(index);
91         }
92 
setLaterBits(const BitSetT & bits)93         void setLaterBits(const BitSetT &bits)
94         {
95             ASSERT((BitSetT(bits) &= Mask(mCurrentBit + 1)).none());
96             mBitsCopy |= bits;
97         }
98 
99       private:
100         std::size_t getNextBit();
101 
102         BitSetT mBitsCopy;
103         std::size_t mCurrentBit;
104     };
105 
106     using value_type = BitsT;
107     using param_type = ParamT;
108 
109     constexpr BitSetT();
110     constexpr explicit BitSetT(BitsT value);
111     constexpr explicit BitSetT(std::initializer_list<ParamT> init);
112 
113     constexpr BitSetT(const BitSetT &other);
114     constexpr BitSetT &operator=(const BitSetT &other);
115 
116     constexpr bool operator==(const BitSetT &other) const;
117     constexpr bool operator!=(const BitSetT &other) const;
118 
119     constexpr bool operator[](ParamT pos) const;
120     Reference operator[](ParamT pos) { return Reference(this, pos); }
121 
122     constexpr bool test(ParamT pos) const;
123 
124     constexpr bool all() const;
125     constexpr bool any() const;
126     constexpr bool none() const;
127     constexpr std::size_t count() const;
128 
size()129     constexpr std::size_t size() const { return N; }
130 
131     constexpr BitSetT &operator&=(const BitSetT &other);
132     constexpr BitSetT &operator|=(const BitSetT &other);
133     constexpr BitSetT &operator^=(const BitSetT &other);
134     constexpr BitSetT operator~() const;
135 
136     constexpr BitSetT &operator&=(BitsT value);
137     constexpr BitSetT &operator|=(BitsT value);
138     constexpr BitSetT &operator^=(BitsT value);
139 
140     constexpr BitSetT operator<<(std::size_t pos) const;
141     constexpr BitSetT &operator<<=(std::size_t pos);
142     constexpr BitSetT operator>>(std::size_t pos) const;
143     constexpr BitSetT &operator>>=(std::size_t pos);
144 
145     constexpr BitSetT &set();
146     constexpr BitSetT &set(ParamT pos, bool value = true);
147 
148     constexpr BitSetT &reset();
149     constexpr BitSetT &reset(ParamT pos);
150 
151     constexpr BitSetT &flip();
152     constexpr BitSetT &flip(ParamT pos);
153 
to_ulong()154     constexpr unsigned long to_ulong() const { return static_cast<unsigned long>(mBits); }
bits()155     constexpr BitsT bits() const { return mBits; }
156 
begin()157     Iterator begin() const { return Iterator(*this); }
end()158     Iterator end() const { return Iterator(BitSetT()); }
159 
Zero()160     constexpr static BitSetT Zero() { return BitSetT(); }
161 
162     constexpr ParamT first() const;
163     constexpr ParamT last() const;
164 
165     // Produces a mask of ones up to the "x"th bit.
Mask(std::size_t x)166     constexpr static BitsT Mask(std::size_t x) { return BitMask<BitsT>(static_cast<ParamT>(x)); }
167 
168   private:
169     BitsT mBits;
170 };
171 
172 template <size_t N, typename BitsT, typename ParamT>
BitSetT()173 constexpr BitSetT<N, BitsT, ParamT>::BitSetT() : mBits(0)
174 {
175     static_assert(N > 0, "Bitset type cannot support zero bits.");
176     static_assert(N <= sizeof(BitsT) * 8, "Bitset type cannot support a size this large.");
177 }
178 
179 template <size_t N, typename BitsT, typename ParamT>
BitSetT(BitsT value)180 constexpr BitSetT<N, BitsT, ParamT>::BitSetT(BitsT value) : mBits(value & Mask(N))
181 {}
182 
183 template <size_t N, typename BitsT, typename ParamT>
BitSetT(std::initializer_list<ParamT> init)184 constexpr BitSetT<N, BitsT, ParamT>::BitSetT(std::initializer_list<ParamT> init) : mBits(0)
185 {
186     for (ParamT element : init)
187     {
188         mBits |= Bit<BitsT>(element) & Mask(N);
189     }
190 }
191 
192 template <size_t N, typename BitsT, typename ParamT>
BitSetT(const BitSetT & other)193 constexpr BitSetT<N, BitsT, ParamT>::BitSetT(const BitSetT &other) : mBits(other.mBits)
194 {}
195 
196 template <size_t N, typename BitsT, typename ParamT>
197 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator=(const BitSetT &other)
198 {
199     mBits = other.mBits;
200     return *this;
201 }
202 
203 template <size_t N, typename BitsT, typename ParamT>
204 constexpr bool BitSetT<N, BitsT, ParamT>::operator==(const BitSetT &other) const
205 {
206     return mBits == other.mBits;
207 }
208 
209 template <size_t N, typename BitsT, typename ParamT>
210 constexpr bool BitSetT<N, BitsT, ParamT>::operator!=(const BitSetT &other) const
211 {
212     return mBits != other.mBits;
213 }
214 
215 template <size_t N, typename BitsT, typename ParamT>
216 constexpr bool BitSetT<N, BitsT, ParamT>::operator[](ParamT pos) const
217 {
218     return test(pos);
219 }
220 
221 template <size_t N, typename BitsT, typename ParamT>
test(ParamT pos)222 constexpr bool BitSetT<N, BitsT, ParamT>::test(ParamT pos) const
223 {
224     return (mBits & Bit<BitsT>(pos)) != 0;
225 }
226 
227 template <size_t N, typename BitsT, typename ParamT>
all()228 constexpr bool BitSetT<N, BitsT, ParamT>::all() const
229 {
230     ASSERT(mBits == (mBits & Mask(N)));
231     return mBits == Mask(N);
232 }
233 
234 template <size_t N, typename BitsT, typename ParamT>
any()235 constexpr bool BitSetT<N, BitsT, ParamT>::any() const
236 {
237     ASSERT(mBits == (mBits & Mask(N)));
238     return (mBits != 0);
239 }
240 
241 template <size_t N, typename BitsT, typename ParamT>
none()242 constexpr bool BitSetT<N, BitsT, ParamT>::none() const
243 {
244     ASSERT(mBits == (mBits & Mask(N)));
245     return (mBits == 0);
246 }
247 
248 template <size_t N, typename BitsT, typename ParamT>
count()249 constexpr std::size_t BitSetT<N, BitsT, ParamT>::count() const
250 {
251     return gl::BitCount(mBits);
252 }
253 
254 template <size_t N, typename BitsT, typename ParamT>
255 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator&=(const BitSetT &other)
256 {
257     mBits &= other.mBits;
258     return *this;
259 }
260 
261 template <size_t N, typename BitsT, typename ParamT>
262 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator|=(const BitSetT &other)
263 {
264     mBits |= other.mBits;
265     return *this;
266 }
267 
268 template <size_t N, typename BitsT, typename ParamT>
269 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator^=(const BitSetT &other)
270 {
271     mBits = mBits ^ other.mBits;
272     return *this;
273 }
274 
275 template <size_t N, typename BitsT, typename ParamT>
276 constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator~() const
277 {
278     return BitSetT<N, BitsT, ParamT>(~mBits & Mask(N));
279 }
280 
281 template <size_t N, typename BitsT, typename ParamT>
282 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator&=(BitsT value)
283 {
284     mBits &= value;
285     return *this;
286 }
287 
288 template <size_t N, typename BitsT, typename ParamT>
289 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator|=(BitsT value)
290 {
291     mBits |= value & Mask(N);
292     return *this;
293 }
294 
295 template <size_t N, typename BitsT, typename ParamT>
296 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator^=(BitsT value)
297 {
298     mBits ^= value & Mask(N);
299     return *this;
300 }
301 
302 template <size_t N, typename BitsT, typename ParamT>
303 constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator<<(std::size_t pos) const
304 {
305     return BitSetT<N, BitsT, ParamT>((mBits << pos) & Mask(N));
306 }
307 
308 template <size_t N, typename BitsT, typename ParamT>
309 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator<<=(std::size_t pos)
310 {
311     mBits = (mBits << pos & Mask(N));
312     return *this;
313 }
314 
315 template <size_t N, typename BitsT, typename ParamT>
316 constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator>>(std::size_t pos) const
317 {
318     return BitSetT<N, BitsT, ParamT>(mBits >> pos);
319 }
320 
321 template <size_t N, typename BitsT, typename ParamT>
322 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator>>=(std::size_t pos)
323 {
324     mBits = ((mBits >> pos) & Mask(N));
325     return *this;
326 }
327 
328 template <size_t N, typename BitsT, typename ParamT>
set()329 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::set()
330 {
331     ASSERT(mBits == (mBits & Mask(N)));
332     mBits = Mask(N);
333     return *this;
334 }
335 
336 template <size_t N, typename BitsT, typename ParamT>
set(ParamT pos,bool value)337 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::set(ParamT pos, bool value)
338 {
339     ASSERT(mBits == (mBits & Mask(N)));
340     if (value)
341     {
342         mBits |= Bit<BitsT>(pos) & Mask(N);
343     }
344     else
345     {
346         reset(pos);
347     }
348     return *this;
349 }
350 
351 template <size_t N, typename BitsT, typename ParamT>
reset()352 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::reset()
353 {
354     ASSERT(mBits == (mBits & Mask(N)));
355     mBits = 0;
356     return *this;
357 }
358 
359 template <size_t N, typename BitsT, typename ParamT>
reset(ParamT pos)360 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::reset(ParamT pos)
361 {
362     ASSERT(mBits == (mBits & Mask(N)));
363     mBits &= ~Bit<BitsT>(pos);
364     return *this;
365 }
366 
367 template <size_t N, typename BitsT, typename ParamT>
flip()368 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::flip()
369 {
370     ASSERT(mBits == (mBits & Mask(N)));
371     mBits ^= Mask(N);
372     return *this;
373 }
374 
375 template <size_t N, typename BitsT, typename ParamT>
flip(ParamT pos)376 constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::flip(ParamT pos)
377 {
378     ASSERT(mBits == (mBits & Mask(N)));
379     mBits ^= Bit<BitsT>(pos) & Mask(N);
380     return *this;
381 }
382 
383 template <size_t N, typename BitsT, typename ParamT>
first()384 constexpr ParamT BitSetT<N, BitsT, ParamT>::first() const
385 {
386     ASSERT(!none());
387     return static_cast<ParamT>(gl::ScanForward(mBits));
388 }
389 
390 template <size_t N, typename BitsT, typename ParamT>
last()391 constexpr ParamT BitSetT<N, BitsT, ParamT>::last() const
392 {
393     ASSERT(!none());
394     return static_cast<ParamT>(gl::ScanReverse(mBits));
395 }
396 
397 template <size_t N, typename BitsT, typename ParamT>
Iterator(const BitSetT & bits)398 BitSetT<N, BitsT, ParamT>::Iterator::Iterator(const BitSetT &bits) : mBitsCopy(bits), mCurrentBit(0)
399 {
400     if (bits.any())
401     {
402         mCurrentBit = getNextBit();
403     }
404 }
405 
406 template <size_t N, typename BitsT, typename ParamT>
407 ANGLE_INLINE typename BitSetT<N, BitsT, ParamT>::Iterator &
408 BitSetT<N, BitsT, ParamT>::Iterator::operator++()
409 {
410     ASSERT(mBitsCopy.any());
411     mBitsCopy.reset(static_cast<ParamT>(mCurrentBit));
412     mCurrentBit = getNextBit();
413     return *this;
414 }
415 
416 template <size_t N, typename BitsT, typename ParamT>
417 bool BitSetT<N, BitsT, ParamT>::Iterator::operator==(const Iterator &other) const
418 {
419     return mBitsCopy == other.mBitsCopy;
420 }
421 
422 template <size_t N, typename BitsT, typename ParamT>
423 bool BitSetT<N, BitsT, ParamT>::Iterator::operator!=(const Iterator &other) const
424 {
425     return !(*this == other);
426 }
427 
428 template <size_t N, typename BitsT, typename ParamT>
429 ParamT BitSetT<N, BitsT, ParamT>::Iterator::operator*() const
430 {
431     return static_cast<ParamT>(mCurrentBit);
432 }
433 
434 template <size_t N, typename BitsT, typename ParamT>
getNextBit()435 std::size_t BitSetT<N, BitsT, ParamT>::Iterator::getNextBit()
436 {
437     if (mBitsCopy.none())
438     {
439         return 0;
440     }
441 
442     return gl::ScanForward(mBitsCopy.mBits);
443 }
444 
445 template <size_t N>
446 using BitSet8 = BitSetT<N, uint8_t>;
447 
448 template <size_t N>
449 using BitSet16 = BitSetT<N, uint16_t>;
450 
451 template <size_t N>
452 using BitSet32 = BitSetT<N, uint32_t>;
453 
454 template <size_t N>
455 using BitSet64 = BitSetT<N, uint64_t>;
456 
457 template <std::size_t N>
458 class BitSetArray;
459 
460 namespace priv
461 {
462 
463 template <size_t N, typename T>
464 using EnableIfBitsFit = typename std::enable_if<N <= sizeof(T) * 8>::type;
465 
466 template <size_t N, typename Enable = void>
467 struct GetBitSet
468 {
469     using Type = BitSetArray<N>;
470 };
471 
472 // Prefer 64-bit bitsets on 64-bit CPUs. They seem faster than 32-bit.
473 #if defined(ANGLE_IS_64_BIT_CPU)
474 template <size_t N>
475 struct GetBitSet<N, EnableIfBitsFit<N, uint64_t>>
476 {
477     using Type = BitSet64<N>;
478 };
479 constexpr std::size_t kDefaultBitSetSize = 64;
480 using BaseBitSetType                     = BitSet64<kDefaultBitSetSize>;
481 #else
482 template <size_t N>
483 struct GetBitSet<N, EnableIfBitsFit<N, uint32_t>>
484 {
485     using Type = BitSet32<N>;
486 };
487 constexpr std::size_t kDefaultBitSetSize = 32;
488 using BaseBitSetType                     = BitSet32<kDefaultBitSetSize>;
489 #endif  // defined(ANGLE_IS_64_BIT_CPU)
490 
491 }  // namespace priv
492 
493 template <size_t N>
494 using BitSet = typename priv::GetBitSet<N>::Type;
495 
496 template <std::size_t N>
497 class BitSetArray final
498 {
499   public:
500     using BaseBitSet = priv::BaseBitSetType;
501 
502     BitSetArray();
503     BitSetArray(const BitSetArray<N> &other);
504 
505     using value_type = BaseBitSet::value_type;
506     using param_type = BaseBitSet::param_type;
507 
508     class Reference final
509     {
510       public:
511         ~Reference() {}
512         Reference &operator=(bool x)
513         {
514             mParent.set(mPosition, x);
515             return *this;
516         }
517         explicit operator bool() const { return mParent.test(mPosition); }
518 
519       private:
520         friend class BitSetArray;
521 
522         Reference(BitSetArray &parent, std::size_t pos) : mParent(parent), mPosition(pos) {}
523 
524         BitSetArray &mParent;
525         std::size_t mPosition;
526     };
527     class Iterator final
528     {
529       public:
530         Iterator(const BitSetArray<N> &bitSetArray, std::size_t index);
531         Iterator &operator++();
532         bool operator==(const Iterator &other) const;
533         bool operator!=(const Iterator &other) const;
534         size_t operator*() const;
535 
536         // These helper functions allow mutating an iterator in-flight.
537         // They only operate on later bits to ensure we don't iterate the same bit twice.
538         void resetLaterBit(std::size_t pos)
539         {
540             ASSERT(pos > (mIndex * priv::kDefaultBitSetSize) + *mCurrentIterator);
541             prepareCopy();
542             mParentCopy.reset(pos);
543             updateIteratorBit(pos, false);
544         }
545 
546         void setLaterBit(std::size_t pos)
547         {
548             ASSERT(pos > (mIndex * priv::kDefaultBitSetSize) + *mCurrentIterator);
549             prepareCopy();
550             mParentCopy.set(pos);
551             updateIteratorBit(pos, true);
552         }
553 
554         void setLaterBits(const BitSetArray &bits)
555         {
556             prepareCopy();
557             mParentCopy |= bits;
558             updateIteratorBits(bits);
559         }
560 
561       private:
562         ANGLE_INLINE void prepareCopy()
563         {
564             ASSERT(mParent.mBaseBitSetArray[mIndex].end() ==
565                    mParentCopy.mBaseBitSetArray[mIndex].end());
566             if (mParentCopy.none())
567             {
568                 mParentCopy    = mParent;
569                 mCurrentParent = &mParentCopy;
570             }
571         }
572 
573         ANGLE_INLINE void updateIteratorBit(std::size_t pos, bool setBit)
574         {
575             // Get the index and offset, update current interator if within range
576             size_t index  = pos >> kShiftForDivision;
577             size_t offset = pos & kDefaultBitSetSizeMinusOne;
578             if (index == mIndex)
579             {
580                 if (setBit)
581                 {
582                     mCurrentIterator.setLaterBit(offset);
583                 }
584                 else
585                 {
586                     mCurrentIterator.resetLaterBit(offset);
587                 }
588             }
589         }
590 
591         ANGLE_INLINE void updateIteratorBits(const BitSetArray &bits)
592         {
593             mCurrentIterator.setLaterBits(bits.mBaseBitSetArray[mIndex]);
594         }
595 
596         // Problem -
597         // We want to provide the fastest path possible for usecases that iterate though the bitset.
598         //
599         // Options -
600         // 1) For non-mutating iterations the const ref <mParent> is set as mCurrentParent and only
601         //    for usecases that need to mutate the bitset while iterating we perform a copy of
602         //    <mParent> into <mParentCopy> and modify its bits accordingly.
603         // 2) The alternate approach was to perform a copy all the time in the constructor
604         //    irrespective of whether it was a mutating usecase or not.
605         //
606         // Experiment -
607         // BitSetIteratorPerfTest was run on a Windows machine with Intel CPU and these were the
608         // results -
609         // 1) Copy only when necessary -
610         //      RESULT BitSetIteratorPerf.wall_time:    run = 116.1067374961 ns
611         //      RESULT BitSetIteratorPerf.trial_steps : run = 8416124 count
612         //      RESULT BitSetIteratorPerf.total_steps : run = 16832251 count
613         // 2) Copy always -
614         //      RESULT BitSetIteratorPerf.wall_time:    run = 242.7446459439 ns
615         //      RESULT BitSetIteratorPerf.trial_steps : run = 4171416 count
616         //      RESULT BitSetIteratorPerf.total_steps : run = 8342834 count
617         //
618         // Resolution -
619         // We settled on the copy only when necessary path.
620         size_t mIndex;
621         const BitSetArray &mParent;
622         BitSetArray mParentCopy;
623         const BitSetArray *mCurrentParent;
624         typename BaseBitSet::Iterator mCurrentIterator;
625     };
626 
627     constexpr std::size_t size() const { return N; }
628     Iterator begin() const { return Iterator(*this, 0); }
629     Iterator end() const { return Iterator(*this, kArraySize); }
630     unsigned long to_ulong() const
631     {
632         // TODO(anglebug.com/5628): Handle serializing more than kDefaultBitSetSize
633         for (std::size_t index = 1; index < kArraySize; index++)
634         {
635             ASSERT(mBaseBitSetArray[index].none());
636         }
637         return static_cast<unsigned long>(mBaseBitSetArray[0].to_ulong());
638     }
639 
640     // Assignment operators
641     BitSetArray &operator=(const BitSetArray &other);
642     BitSetArray &operator&=(const BitSetArray &other);
643     BitSetArray &operator|=(const BitSetArray &other);
644     BitSetArray &operator^=(const BitSetArray &other);
645 
646     // Bitwise operators
647     BitSetArray<N> operator&(const angle::BitSetArray<N> &other) const;
648     BitSetArray<N> operator|(const angle::BitSetArray<N> &other) const;
649     BitSetArray<N> operator^(const angle::BitSetArray<N> &other) const;
650 
651     // Relational Operators
652     bool operator==(const angle::BitSetArray<N> &other) const;
653     bool operator!=(const angle::BitSetArray<N> &other) const;
654 
655     // Unary operators
656     BitSetArray operator~() const;
657     bool operator[](std::size_t pos) const;
658     Reference operator[](std::size_t pos)
659     {
660         ASSERT(pos < size());
661         return Reference(*this, pos);
662     }
663 
664     // Setter, getters and other helper methods
665     BitSetArray &set();
666     BitSetArray &set(std::size_t pos, bool value = true);
667     BitSetArray &reset();
668     BitSetArray &reset(std::size_t pos);
669     bool test(std::size_t pos) const;
670     bool all() const;
671     bool any() const;
672     bool none() const;
673     std::size_t count() const;
674     bool intersects(const BitSetArray &other) const;
675     BitSetArray<N> &flip();
676     param_type first() const;
677     param_type last() const;
678 
679     value_type bits(size_t index) const;
680 
681   private:
682     static constexpr std::size_t kDefaultBitSetSizeMinusOne = priv::kDefaultBitSetSize - 1;
683     static constexpr std::size_t kShiftForDivision =
684         static_cast<std::size_t>(rx::Log2(static_cast<unsigned int>(priv::kDefaultBitSetSize)));
685     static constexpr std::size_t kArraySize =
686         ((N + kDefaultBitSetSizeMinusOne) >> kShiftForDivision);
687     constexpr static std::size_t kLastElementCount = (N & kDefaultBitSetSizeMinusOne);
688     constexpr static std::size_t kLastElementMask  = priv::BaseBitSetType::Mask(
689         kLastElementCount == 0 ? priv::kDefaultBitSetSize : kLastElementCount);
690 
691     std::array<BaseBitSet, kArraySize> mBaseBitSetArray;
692 };
693 
694 template <std::size_t N>
695 BitSetArray<N>::BitSetArray()
696 {
697     static_assert(N > priv::kDefaultBitSetSize, "BitSetArray type can't support requested size.");
698     reset();
699 }
700 
701 template <size_t N>
702 BitSetArray<N>::BitSetArray(const BitSetArray<N> &other)
703 {
704     for (std::size_t index = 0; index < kArraySize; index++)
705     {
706         mBaseBitSetArray[index] = other.mBaseBitSetArray[index];
707     }
708 }
709 
710 template <size_t N>
711 BitSetArray<N>::Iterator::Iterator(const BitSetArray<N> &bitSetArray, std::size_t index)
712     : mIndex(index),
713       mParent(bitSetArray),
714       mCurrentParent(&mParent),
715       mCurrentIterator(mParent.mBaseBitSetArray[0].begin())
716 {
717     while (mIndex < mCurrentParent->kArraySize)
718     {
719         if (mCurrentParent->mBaseBitSetArray[mIndex].any())
720         {
721             break;
722         }
723         mIndex++;
724     }
725 
726     if (mIndex < mCurrentParent->kArraySize)
727     {
728         mCurrentIterator = mCurrentParent->mBaseBitSetArray[mIndex].begin();
729     }
730     else
731     {
732         mCurrentIterator = mCurrentParent->mBaseBitSetArray[mCurrentParent->kArraySize - 1].end();
733     }
734 }
735 
736 template <std::size_t N>
737 typename BitSetArray<N>::Iterator &BitSetArray<N>::Iterator::operator++()
738 {
739     ++mCurrentIterator;
740     if (mCurrentIterator == mCurrentParent->mBaseBitSetArray[mIndex].end())
741     {
742         mIndex++;
743         if (mIndex < mCurrentParent->kArraySize)
744         {
745             mCurrentIterator = mCurrentParent->mBaseBitSetArray[mIndex].begin();
746         }
747     }
748     return *this;
749 }
750 
751 template <std::size_t N>
752 bool BitSetArray<N>::Iterator::operator==(const BitSetArray<N>::Iterator &other) const
753 {
754     return mCurrentIterator == other.mCurrentIterator;
755 }
756 
757 template <std::size_t N>
758 bool BitSetArray<N>::Iterator::operator!=(const BitSetArray<N>::Iterator &other) const
759 {
760     return mCurrentIterator != other.mCurrentIterator;
761 }
762 
763 template <std::size_t N>
764 std::size_t BitSetArray<N>::Iterator::operator*() const
765 {
766     return (mIndex * priv::kDefaultBitSetSize) + *mCurrentIterator;
767 }
768 
769 template <std::size_t N>
770 BitSetArray<N> &BitSetArray<N>::operator=(const BitSetArray<N> &other)
771 {
772     for (std::size_t index = 0; index < kArraySize; index++)
773     {
774         mBaseBitSetArray[index] = other.mBaseBitSetArray[index];
775     }
776     return *this;
777 }
778 
779 template <std::size_t N>
780 BitSetArray<N> &BitSetArray<N>::operator&=(const BitSetArray<N> &other)
781 {
782     for (std::size_t index = 0; index < kArraySize; index++)
783     {
784         mBaseBitSetArray[index] &= other.mBaseBitSetArray[index];
785     }
786     return *this;
787 }
788 
789 template <std::size_t N>
790 BitSetArray<N> &BitSetArray<N>::operator|=(const BitSetArray<N> &other)
791 {
792     for (std::size_t index = 0; index < kArraySize; index++)
793     {
794         mBaseBitSetArray[index] |= other.mBaseBitSetArray[index];
795     }
796     return *this;
797 }
798 
799 template <std::size_t N>
800 BitSetArray<N> &BitSetArray<N>::operator^=(const BitSetArray<N> &other)
801 {
802     for (std::size_t index = 0; index < kArraySize; index++)
803     {
804         mBaseBitSetArray[index] ^= other.mBaseBitSetArray[index];
805     }
806     return *this;
807 }
808 
809 template <std::size_t N>
810 BitSetArray<N> BitSetArray<N>::operator&(const angle::BitSetArray<N> &other) const
811 {
812     angle::BitSetArray<N> result(other);
813     result &= *this;
814     return result;
815 }
816 
817 template <std::size_t N>
818 BitSetArray<N> BitSetArray<N>::operator|(const angle::BitSetArray<N> &other) const
819 {
820     angle::BitSetArray<N> result(other);
821     result |= *this;
822     return result;
823 }
824 
825 template <std::size_t N>
826 BitSetArray<N> BitSetArray<N>::operator^(const angle::BitSetArray<N> &other) const
827 {
828     angle::BitSetArray<N> result(other);
829     result ^= *this;
830     return result;
831 }
832 
833 template <std::size_t N>
834 bool BitSetArray<N>::operator==(const angle::BitSetArray<N> &other) const
835 {
836     for (std::size_t index = 0; index < kArraySize; index++)
837     {
838         if (mBaseBitSetArray[index] != other.mBaseBitSetArray[index])
839         {
840             return false;
841         }
842     }
843     return true;
844 }
845 
846 template <std::size_t N>
847 bool BitSetArray<N>::operator!=(const angle::BitSetArray<N> &other) const
848 {
849     return !(*this == other);
850 }
851 
852 template <std::size_t N>
853 BitSetArray<N> BitSetArray<N>::operator~() const
854 {
855     angle::BitSetArray<N> result;
856     for (std::size_t index = 0; index < kArraySize; index++)
857     {
858         result.mBaseBitSetArray[index] |= ~mBaseBitSetArray[index];
859     }
860     // The last element in result may need special handling
861     result.mBaseBitSetArray[kArraySize - 1] &= kLastElementMask;
862 
863     return result;
864 }
865 
866 template <std::size_t N>
867 bool BitSetArray<N>::operator[](std::size_t pos) const
868 {
869     ASSERT(pos < size());
870     return test(pos);
871 }
872 
873 template <std::size_t N>
874 BitSetArray<N> &BitSetArray<N>::set()
875 {
876     for (BaseBitSet &baseBitSet : mBaseBitSetArray)
877     {
878         baseBitSet.set();
879     }
880     // The last element in mBaseBitSetArray may need special handling
881     mBaseBitSetArray[kArraySize - 1] &= kLastElementMask;
882 
883     return *this;
884 }
885 
886 template <std::size_t N>
887 BitSetArray<N> &BitSetArray<N>::set(std::size_t pos, bool value)
888 {
889     ASSERT(pos < size());
890     // Get the index and offset, then set the bit
891     size_t index  = pos >> kShiftForDivision;
892     size_t offset = pos & kDefaultBitSetSizeMinusOne;
893     mBaseBitSetArray[index].set(offset, value);
894     return *this;
895 }
896 
897 template <std::size_t N>
898 BitSetArray<N> &BitSetArray<N>::reset()
899 {
900     for (BaseBitSet &baseBitSet : mBaseBitSetArray)
901     {
902         baseBitSet.reset();
903     }
904     return *this;
905 }
906 
907 template <std::size_t N>
908 BitSetArray<N> &BitSetArray<N>::reset(std::size_t pos)
909 {
910     ASSERT(pos < size());
911     return set(pos, false);
912 }
913 
914 template <std::size_t N>
915 bool BitSetArray<N>::test(std::size_t pos) const
916 {
917     ASSERT(pos < size());
918     // Get the index and offset, then test the bit
919     size_t index  = pos >> kShiftForDivision;
920     size_t offset = pos & kDefaultBitSetSizeMinusOne;
921     return mBaseBitSetArray[index].test(offset);
922 }
923 
924 template <std::size_t N>
925 bool BitSetArray<N>::all() const
926 {
927     static priv::BaseBitSetType kLastElementBitSet = priv::BaseBitSetType(kLastElementMask);
928 
929     for (std::size_t index = 0; index < kArraySize - 1; index++)
930     {
931         if (!mBaseBitSetArray[index].all())
932         {
933             return false;
934         }
935     }
936 
937     // The last element in mBaseBitSetArray may need special handling
938     return mBaseBitSetArray[kArraySize - 1] == kLastElementBitSet;
939 }
940 
941 template <std::size_t N>
942 bool BitSetArray<N>::any() const
943 {
944     for (const BaseBitSet &baseBitSet : mBaseBitSetArray)
945     {
946         if (baseBitSet.any())
947         {
948             return true;
949         }
950     }
951     return false;
952 }
953 
954 template <std::size_t N>
955 bool BitSetArray<N>::none() const
956 {
957     for (const BaseBitSet &baseBitSet : mBaseBitSetArray)
958     {
959         if (!baseBitSet.none())
960         {
961             return false;
962         }
963     }
964     return true;
965 }
966 
967 template <std::size_t N>
968 std::size_t BitSetArray<N>::count() const
969 {
970     size_t count = 0;
971     for (const BaseBitSet &baseBitSet : mBaseBitSetArray)
972     {
973         count += baseBitSet.count();
974     }
975     return count;
976 }
977 
978 template <std::size_t N>
979 bool BitSetArray<N>::intersects(const BitSetArray<N> &other) const
980 {
981     for (std::size_t index = 0; index < kArraySize; index++)
982     {
983         if ((mBaseBitSetArray[index].bits() & other.mBaseBitSetArray[index].bits()) != 0)
984         {
985             return true;
986         }
987     }
988     return false;
989 }
990 
991 template <std::size_t N>
992 BitSetArray<N> &BitSetArray<N>::flip()
993 {
994     for (BaseBitSet &baseBitSet : mBaseBitSetArray)
995     {
996         baseBitSet.flip();
997     }
998 
999     // The last element in mBaseBitSetArray may need special handling
1000     mBaseBitSetArray[kArraySize - 1] &= kLastElementMask;
1001     return *this;
1002 }
1003 
1004 template <std::size_t N>
1005 typename BitSetArray<N>::param_type BitSetArray<N>::first() const
1006 {
1007     ASSERT(any());
1008     for (size_t arrayIndex = 0; arrayIndex < kArraySize; ++arrayIndex)
1009     {
1010         const BaseBitSet &baseBitSet = mBaseBitSetArray[arrayIndex];
1011         if (baseBitSet.any())
1012         {
1013             return baseBitSet.first() + arrayIndex * priv::kDefaultBitSetSize;
1014         }
1015     }
1016     UNREACHABLE();
1017     return 0;
1018 }
1019 
1020 template <std::size_t N>
1021 typename BitSetArray<N>::param_type BitSetArray<N>::last() const
1022 {
1023     ASSERT(any());
1024     for (size_t arrayIndex = kArraySize; arrayIndex > 0; --arrayIndex)
1025     {
1026         const BaseBitSet &baseBitSet = mBaseBitSetArray[arrayIndex - 1];
1027         if (baseBitSet.any())
1028         {
1029             return baseBitSet.last() + (arrayIndex - 1) * priv::kDefaultBitSetSize;
1030         }
1031     }
1032     UNREACHABLE();
1033     return 0;
1034 }
1035 
1036 template <std::size_t N>
1037 typename BitSetArray<N>::value_type BitSetArray<N>::bits(size_t index) const
1038 {
1039     return mBaseBitSetArray[index].bits();
1040 }
1041 }  // namespace angle
1042 
1043 template <size_t N, typename BitsT, typename ParamT>
1044 inline constexpr angle::BitSetT<N, BitsT, ParamT> operator&(
1045     const angle::BitSetT<N, BitsT, ParamT> &lhs,
1046     const angle::BitSetT<N, BitsT, ParamT> &rhs)
1047 {
1048     angle::BitSetT<N, BitsT, ParamT> result(lhs);
1049     result &= rhs.bits();
1050     return result;
1051 }
1052 
1053 template <size_t N, typename BitsT, typename ParamT>
1054 inline constexpr angle::BitSetT<N, BitsT, ParamT> operator|(
1055     const angle::BitSetT<N, BitsT, ParamT> &lhs,
1056     const angle::BitSetT<N, BitsT, ParamT> &rhs)
1057 {
1058     angle::BitSetT<N, BitsT, ParamT> result(lhs);
1059     result |= rhs.bits();
1060     return result;
1061 }
1062 
1063 template <size_t N, typename BitsT, typename ParamT>
1064 inline constexpr angle::BitSetT<N, BitsT, ParamT> operator^(
1065     const angle::BitSetT<N, BitsT, ParamT> &lhs,
1066     const angle::BitSetT<N, BitsT, ParamT> &rhs)
1067 {
1068     angle::BitSetT<N, BitsT, ParamT> result(lhs);
1069     result ^= rhs.bits();
1070     return result;
1071 }
1072 
1073 template <size_t N, typename BitsT, typename ParamT>
1074 inline bool operator==(angle::BitSetT<N, BitsT, ParamT> &lhs, angle::BitSetT<N, BitsT, ParamT> &rhs)
1075 {
1076     return lhs.bits() == rhs.bits();
1077 }
1078 
1079 template <size_t N, typename BitsT, typename ParamT>
1080 inline bool operator!=(angle::BitSetT<N, BitsT, ParamT> &lhs, angle::BitSetT<N, BitsT, ParamT> &rhs)
1081 {
1082     return !(lhs == rhs);
1083 }
1084 
1085 #endif  // COMMON_BITSETITERATOR_H_
1086