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