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