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 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 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 while (mCurrentIterator == mCurrentParent->mBaseBitSetArray[mIndex].end())
741 {
742 mIndex++;
743 if (mIndex >= mCurrentParent->kArraySize)
744 {
745 break;
746 }
747 mCurrentIterator = mCurrentParent->mBaseBitSetArray[mIndex].begin();
748 }
749 return *this;
750 }
751
752 template <std::size_t N>
753 bool BitSetArray<N>::Iterator::operator==(const BitSetArray<N>::Iterator &other) const
754 {
755 return mCurrentIterator == other.mCurrentIterator;
756 }
757
758 template <std::size_t N>
759 bool BitSetArray<N>::Iterator::operator!=(const BitSetArray<N>::Iterator &other) const
760 {
761 return mCurrentIterator != other.mCurrentIterator;
762 }
763
764 template <std::size_t N>
765 std::size_t BitSetArray<N>::Iterator::operator*() const
766 {
767 return (mIndex * priv::kDefaultBitSetSize) + *mCurrentIterator;
768 }
769
770 template <std::size_t N>
771 BitSetArray<N> &BitSetArray<N>::operator=(const BitSetArray<N> &other)
772 {
773 for (std::size_t index = 0; index < kArraySize; index++)
774 {
775 mBaseBitSetArray[index] = other.mBaseBitSetArray[index];
776 }
777 return *this;
778 }
779
780 template <std::size_t N>
781 BitSetArray<N> &BitSetArray<N>::operator&=(const BitSetArray<N> &other)
782 {
783 for (std::size_t index = 0; index < kArraySize; index++)
784 {
785 mBaseBitSetArray[index] &= other.mBaseBitSetArray[index];
786 }
787 return *this;
788 }
789
790 template <std::size_t N>
791 BitSetArray<N> &BitSetArray<N>::operator|=(const BitSetArray<N> &other)
792 {
793 for (std::size_t index = 0; index < kArraySize; index++)
794 {
795 mBaseBitSetArray[index] |= other.mBaseBitSetArray[index];
796 }
797 return *this;
798 }
799
800 template <std::size_t N>
801 BitSetArray<N> &BitSetArray<N>::operator^=(const BitSetArray<N> &other)
802 {
803 for (std::size_t index = 0; index < kArraySize; index++)
804 {
805 mBaseBitSetArray[index] ^= other.mBaseBitSetArray[index];
806 }
807 return *this;
808 }
809
810 template <std::size_t N>
811 BitSetArray<N> BitSetArray<N>::operator&(const angle::BitSetArray<N> &other) const
812 {
813 angle::BitSetArray<N> result(other);
814 result &= *this;
815 return result;
816 }
817
818 template <std::size_t N>
819 BitSetArray<N> BitSetArray<N>::operator|(const angle::BitSetArray<N> &other) const
820 {
821 angle::BitSetArray<N> result(other);
822 result |= *this;
823 return result;
824 }
825
826 template <std::size_t N>
827 BitSetArray<N> BitSetArray<N>::operator^(const angle::BitSetArray<N> &other) const
828 {
829 angle::BitSetArray<N> result(other);
830 result ^= *this;
831 return result;
832 }
833
834 template <std::size_t N>
835 bool BitSetArray<N>::operator==(const angle::BitSetArray<N> &other) const
836 {
837 for (std::size_t index = 0; index < kArraySize; index++)
838 {
839 if (mBaseBitSetArray[index] != other.mBaseBitSetArray[index])
840 {
841 return false;
842 }
843 }
844 return true;
845 }
846
847 template <std::size_t N>
848 bool BitSetArray<N>::operator!=(const angle::BitSetArray<N> &other) const
849 {
850 return !(*this == other);
851 }
852
853 template <std::size_t N>
854 BitSetArray<N> BitSetArray<N>::operator~() const
855 {
856 angle::BitSetArray<N> result;
857 for (std::size_t index = 0; index < kArraySize; index++)
858 {
859 result.mBaseBitSetArray[index] |= ~mBaseBitSetArray[index];
860 }
861 // The last element in result may need special handling
862 result.mBaseBitSetArray[kArraySize - 1] &= kLastElementMask;
863
864 return result;
865 }
866
867 template <std::size_t N>
868 bool BitSetArray<N>::operator[](std::size_t pos) const
869 {
870 ASSERT(pos < size());
871 return test(pos);
872 }
873
874 template <std::size_t N>
875 BitSetArray<N> &BitSetArray<N>::set()
876 {
877 for (BaseBitSet &baseBitSet : mBaseBitSetArray)
878 {
879 baseBitSet.set();
880 }
881 // The last element in mBaseBitSetArray may need special handling
882 mBaseBitSetArray[kArraySize - 1] &= kLastElementMask;
883
884 return *this;
885 }
886
887 template <std::size_t N>
888 BitSetArray<N> &BitSetArray<N>::set(std::size_t pos, bool value)
889 {
890 ASSERT(pos < size());
891 // Get the index and offset, then set the bit
892 size_t index = pos >> kShiftForDivision;
893 size_t offset = pos & kDefaultBitSetSizeMinusOne;
894 mBaseBitSetArray[index].set(offset, value);
895 return *this;
896 }
897
898 template <std::size_t N>
899 BitSetArray<N> &BitSetArray<N>::reset()
900 {
901 for (BaseBitSet &baseBitSet : mBaseBitSetArray)
902 {
903 baseBitSet.reset();
904 }
905 return *this;
906 }
907
908 template <std::size_t N>
909 BitSetArray<N> &BitSetArray<N>::reset(std::size_t pos)
910 {
911 ASSERT(pos < size());
912 return set(pos, false);
913 }
914
915 template <std::size_t N>
916 bool BitSetArray<N>::test(std::size_t pos) const
917 {
918 ASSERT(pos < size());
919 // Get the index and offset, then test the bit
920 size_t index = pos >> kShiftForDivision;
921 size_t offset = pos & kDefaultBitSetSizeMinusOne;
922 return mBaseBitSetArray[index].test(offset);
923 }
924
925 template <std::size_t N>
926 bool BitSetArray<N>::all() const
927 {
928 static priv::BaseBitSetType kLastElementBitSet = priv::BaseBitSetType(kLastElementMask);
929
930 for (std::size_t index = 0; index < kArraySize - 1; index++)
931 {
932 if (!mBaseBitSetArray[index].all())
933 {
934 return false;
935 }
936 }
937
938 // The last element in mBaseBitSetArray may need special handling
939 return mBaseBitSetArray[kArraySize - 1] == kLastElementBitSet;
940 }
941
942 template <std::size_t N>
943 bool BitSetArray<N>::any() const
944 {
945 for (const BaseBitSet &baseBitSet : mBaseBitSetArray)
946 {
947 if (baseBitSet.any())
948 {
949 return true;
950 }
951 }
952 return false;
953 }
954
955 template <std::size_t N>
956 bool BitSetArray<N>::none() const
957 {
958 for (const BaseBitSet &baseBitSet : mBaseBitSetArray)
959 {
960 if (!baseBitSet.none())
961 {
962 return false;
963 }
964 }
965 return true;
966 }
967
968 template <std::size_t N>
969 std::size_t BitSetArray<N>::count() const
970 {
971 size_t count = 0;
972 for (const BaseBitSet &baseBitSet : mBaseBitSetArray)
973 {
974 count += baseBitSet.count();
975 }
976 return count;
977 }
978
979 template <std::size_t N>
980 bool BitSetArray<N>::intersects(const BitSetArray<N> &other) const
981 {
982 for (std::size_t index = 0; index < kArraySize; index++)
983 {
984 if ((mBaseBitSetArray[index].bits() & other.mBaseBitSetArray[index].bits()) != 0)
985 {
986 return true;
987 }
988 }
989 return false;
990 }
991
992 template <std::size_t N>
993 BitSetArray<N> &BitSetArray<N>::flip()
994 {
995 for (BaseBitSet &baseBitSet : mBaseBitSetArray)
996 {
997 baseBitSet.flip();
998 }
999
1000 // The last element in mBaseBitSetArray may need special handling
1001 mBaseBitSetArray[kArraySize - 1] &= kLastElementMask;
1002 return *this;
1003 }
1004
1005 template <std::size_t N>
1006 typename BitSetArray<N>::param_type BitSetArray<N>::first() const
1007 {
1008 ASSERT(any());
1009 for (size_t arrayIndex = 0; arrayIndex < kArraySize; ++arrayIndex)
1010 {
1011 const BaseBitSet &baseBitSet = mBaseBitSetArray[arrayIndex];
1012 if (baseBitSet.any())
1013 {
1014 return baseBitSet.first() + arrayIndex * priv::kDefaultBitSetSize;
1015 }
1016 }
1017 UNREACHABLE();
1018 return 0;
1019 }
1020
1021 template <std::size_t N>
1022 typename BitSetArray<N>::param_type BitSetArray<N>::last() const
1023 {
1024 ASSERT(any());
1025 for (size_t arrayIndex = kArraySize; arrayIndex > 0; --arrayIndex)
1026 {
1027 const BaseBitSet &baseBitSet = mBaseBitSetArray[arrayIndex - 1];
1028 if (baseBitSet.any())
1029 {
1030 return baseBitSet.last() + (arrayIndex - 1) * priv::kDefaultBitSetSize;
1031 }
1032 }
1033 UNREACHABLE();
1034 return 0;
1035 }
1036
1037 template <std::size_t N>
1038 typename BitSetArray<N>::value_type BitSetArray<N>::bits(size_t index) const
1039 {
1040 return mBaseBitSetArray[index].bits();
1041 }
1042 } // namespace angle
1043
1044 template <size_t N, typename BitsT, typename ParamT>
1045 inline constexpr angle::BitSetT<N, BitsT, ParamT> operator&(
1046 const angle::BitSetT<N, BitsT, ParamT> &lhs,
1047 const angle::BitSetT<N, BitsT, ParamT> &rhs)
1048 {
1049 angle::BitSetT<N, BitsT, ParamT> result(lhs);
1050 result &= rhs.bits();
1051 return result;
1052 }
1053
1054 template <size_t N, typename BitsT, typename ParamT>
1055 inline constexpr angle::BitSetT<N, BitsT, ParamT> operator|(
1056 const angle::BitSetT<N, BitsT, ParamT> &lhs,
1057 const angle::BitSetT<N, BitsT, ParamT> &rhs)
1058 {
1059 angle::BitSetT<N, BitsT, ParamT> result(lhs);
1060 result |= rhs.bits();
1061 return result;
1062 }
1063
1064 template <size_t N, typename BitsT, typename ParamT>
1065 inline constexpr angle::BitSetT<N, BitsT, ParamT> operator^(
1066 const angle::BitSetT<N, BitsT, ParamT> &lhs,
1067 const angle::BitSetT<N, BitsT, ParamT> &rhs)
1068 {
1069 angle::BitSetT<N, BitsT, ParamT> result(lhs);
1070 result ^= rhs.bits();
1071 return result;
1072 }
1073
1074 template <size_t N, typename BitsT, typename ParamT>
1075 inline bool operator==(angle::BitSetT<N, BitsT, ParamT> &lhs, angle::BitSetT<N, BitsT, ParamT> &rhs)
1076 {
1077 return lhs.bits() == rhs.bits();
1078 }
1079
1080 template <size_t N, typename BitsT, typename ParamT>
1081 inline bool operator!=(angle::BitSetT<N, BitsT, ParamT> &lhs, angle::BitSetT<N, BitsT, ParamT> &rhs)
1082 {
1083 return !(lhs == rhs);
1084 }
1085
1086 #endif // COMMON_BITSETITERATOR_H_
1087