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