1 //===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector --*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the SparseBitVector class. See the doxygen comment for 10 // SparseBitVector for more details on the algorithm used. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_SPARSEBITVECTOR_H 15 #define LLVM_ADT_SPARSEBITVECTOR_H 16 17 #include "llvm/Support/ErrorHandling.h" 18 #include "llvm/Support/MathExtras.h" 19 #include "llvm/Support/raw_ostream.h" 20 #include <cassert> 21 #include <climits> 22 #include <cstring> 23 #include <iterator> 24 #include <list> 25 26 namespace llvm { 27 28 /// SparseBitVector is an implementation of a bitvector that is sparse by only 29 /// storing the elements that have non-zero bits set. In order to make this 30 /// fast for the most common cases, SparseBitVector is implemented as a linked 31 /// list of SparseBitVectorElements. We maintain a pointer to the last 32 /// SparseBitVectorElement accessed (in the form of a list iterator), in order 33 /// to make multiple in-order test/set constant time after the first one is 34 /// executed. Note that using vectors to store SparseBitVectorElement's does 35 /// not work out very well because it causes insertion in the middle to take 36 /// enormous amounts of time with a large amount of bits. Other structures that 37 /// have better worst cases for insertion in the middle (various balanced trees, 38 /// etc) do not perform as well in practice as a linked list with this iterator 39 /// kept up to date. They are also significantly more memory intensive. 40 41 template <unsigned ElementSize = 128> struct SparseBitVectorElement { 42 public: 43 using BitWord = unsigned long; 44 using size_type = unsigned; 45 enum { 46 BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT, 47 BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE, 48 BITS_PER_ELEMENT = ElementSize 49 }; 50 51 private: 52 // Index of Element in terms of where first bit starts. 53 unsigned ElementIndex; 54 BitWord Bits[BITWORDS_PER_ELEMENT]; 55 56 SparseBitVectorElement() { 57 ElementIndex = ~0U; 58 memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); 59 } 60 61 public: 62 explicit SparseBitVectorElement(unsigned Idx) { 63 ElementIndex = Idx; 64 memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); 65 } 66 67 // Comparison. 68 bool operator==(const SparseBitVectorElement &RHS) const { 69 if (ElementIndex != RHS.ElementIndex) 70 return false; 71 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 72 if (Bits[i] != RHS.Bits[i]) 73 return false; 74 return true; 75 } 76 77 bool operator!=(const SparseBitVectorElement &RHS) const { 78 return !(*this == RHS); 79 } 80 81 // Return the bits that make up word Idx in our element. 82 BitWord word(unsigned Idx) const { 83 assert(Idx < BITWORDS_PER_ELEMENT); 84 return Bits[Idx]; 85 } 86 87 unsigned index() const { 88 return ElementIndex; 89 } 90 91 bool empty() const { 92 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 93 if (Bits[i]) 94 return false; 95 return true; 96 } 97 98 void set(unsigned Idx) { 99 Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); 100 } 101 102 bool test_and_set(unsigned Idx) { 103 bool old = test(Idx); 104 if (!old) { 105 set(Idx); 106 return true; 107 } 108 return false; 109 } 110 111 void reset(unsigned Idx) { 112 Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); 113 } 114 115 bool test(unsigned Idx) const { 116 return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE)); 117 } 118 119 size_type count() const { 120 unsigned NumBits = 0; 121 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 122 NumBits += countPopulation(Bits[i]); 123 return NumBits; 124 } 125 126 /// find_first - Returns the index of the first set bit. 127 int find_first() const { 128 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 129 if (Bits[i] != 0) 130 return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); 131 llvm_unreachable("Illegal empty element"); 132 } 133 134 /// find_last - Returns the index of the last set bit. 135 int find_last() const { 136 for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; ++I) { 137 unsigned Idx = BITWORDS_PER_ELEMENT - I - 1; 138 if (Bits[Idx] != 0) 139 return Idx * BITWORD_SIZE + BITWORD_SIZE - 140 countLeadingZeros(Bits[Idx]) - 1; 141 } 142 llvm_unreachable("Illegal empty element"); 143 } 144 145 /// find_next - Returns the index of the next set bit starting from the 146 /// "Curr" bit. Returns -1 if the next set bit is not found. 147 int find_next(unsigned Curr) const { 148 if (Curr >= BITS_PER_ELEMENT) 149 return -1; 150 151 unsigned WordPos = Curr / BITWORD_SIZE; 152 unsigned BitPos = Curr % BITWORD_SIZE; 153 BitWord Copy = Bits[WordPos]; 154 assert(WordPos <= BITWORDS_PER_ELEMENT 155 && "Word Position outside of element"); 156 157 // Mask off previous bits. 158 Copy &= ~0UL << BitPos; 159 160 if (Copy != 0) 161 return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); 162 163 // Check subsequent words. 164 for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i) 165 if (Bits[i] != 0) 166 return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); 167 return -1; 168 } 169 170 // Union this element with RHS and return true if this one changed. 171 bool unionWith(const SparseBitVectorElement &RHS) { 172 bool changed = false; 173 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 174 BitWord old = changed ? 0 : Bits[i]; 175 176 Bits[i] |= RHS.Bits[i]; 177 if (!changed && old != Bits[i]) 178 changed = true; 179 } 180 return changed; 181 } 182 183 // Return true if we have any bits in common with RHS 184 bool intersects(const SparseBitVectorElement &RHS) const { 185 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 186 if (RHS.Bits[i] & Bits[i]) 187 return true; 188 } 189 return false; 190 } 191 192 // Intersect this Element with RHS and return true if this one changed. 193 // BecameZero is set to true if this element became all-zero bits. 194 bool intersectWith(const SparseBitVectorElement &RHS, 195 bool &BecameZero) { 196 bool changed = false; 197 bool allzero = true; 198 199 BecameZero = false; 200 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 201 BitWord old = changed ? 0 : Bits[i]; 202 203 Bits[i] &= RHS.Bits[i]; 204 if (Bits[i] != 0) 205 allzero = false; 206 207 if (!changed && old != Bits[i]) 208 changed = true; 209 } 210 BecameZero = allzero; 211 return changed; 212 } 213 214 // Intersect this Element with the complement of RHS and return true if this 215 // one changed. BecameZero is set to true if this element became all-zero 216 // bits. 217 bool intersectWithComplement(const SparseBitVectorElement &RHS, 218 bool &BecameZero) { 219 bool changed = false; 220 bool allzero = true; 221 222 BecameZero = false; 223 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 224 BitWord old = changed ? 0 : Bits[i]; 225 226 Bits[i] &= ~RHS.Bits[i]; 227 if (Bits[i] != 0) 228 allzero = false; 229 230 if (!changed && old != Bits[i]) 231 changed = true; 232 } 233 BecameZero = allzero; 234 return changed; 235 } 236 237 // Three argument version of intersectWithComplement that intersects 238 // RHS1 & ~RHS2 into this element 239 void intersectWithComplement(const SparseBitVectorElement &RHS1, 240 const SparseBitVectorElement &RHS2, 241 bool &BecameZero) { 242 bool allzero = true; 243 244 BecameZero = false; 245 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 246 Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i]; 247 if (Bits[i] != 0) 248 allzero = false; 249 } 250 BecameZero = allzero; 251 } 252 }; 253 254 template <unsigned ElementSize = 128> 255 class SparseBitVector { 256 using ElementList = std::list<SparseBitVectorElement<ElementSize>>; 257 using ElementListIter = typename ElementList::iterator; 258 using ElementListConstIter = typename ElementList::const_iterator; 259 enum { 260 BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE 261 }; 262 263 ElementList Elements; 264 // Pointer to our current Element. This has no visible effect on the external 265 // state of a SparseBitVector, it's just used to improve performance in the 266 // common case of testing/modifying bits with similar indices. 267 mutable ElementListIter CurrElementIter; 268 269 // This is like std::lower_bound, except we do linear searching from the 270 // current position. 271 ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const { 272 273 // We cache a non-const iterator so we're forced to resort to const_cast to 274 // get the begin/end in the case where 'this' is const. To avoid duplication 275 // of code with the only difference being whether the const cast is present 276 // 'this' is always const in this particular function and we sort out the 277 // difference in FindLowerBound and FindLowerBoundConst. 278 ElementListIter Begin = 279 const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin(); 280 ElementListIter End = 281 const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end(); 282 283 if (Elements.empty()) { 284 CurrElementIter = Begin; 285 return CurrElementIter; 286 } 287 288 // Make sure our current iterator is valid. 289 if (CurrElementIter == End) 290 --CurrElementIter; 291 292 // Search from our current iterator, either backwards or forwards, 293 // depending on what element we are looking for. 294 ElementListIter ElementIter = CurrElementIter; 295 if (CurrElementIter->index() == ElementIndex) { 296 return ElementIter; 297 } else if (CurrElementIter->index() > ElementIndex) { 298 while (ElementIter != Begin 299 && ElementIter->index() > ElementIndex) 300 --ElementIter; 301 } else { 302 while (ElementIter != End && 303 ElementIter->index() < ElementIndex) 304 ++ElementIter; 305 } 306 CurrElementIter = ElementIter; 307 return ElementIter; 308 } 309 ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const { 310 return FindLowerBoundImpl(ElementIndex); 311 } 312 ElementListIter FindLowerBound(unsigned ElementIndex) { 313 return FindLowerBoundImpl(ElementIndex); 314 } 315 316 // Iterator to walk set bits in the bitmap. This iterator is a lot uglier 317 // than it would be, in order to be efficient. 318 class SparseBitVectorIterator { 319 private: 320 bool AtEnd; 321 322 const SparseBitVector<ElementSize> *BitVector = nullptr; 323 324 // Current element inside of bitmap. 325 ElementListConstIter Iter; 326 327 // Current bit number inside of our bitmap. 328 unsigned BitNumber; 329 330 // Current word number inside of our element. 331 unsigned WordNumber; 332 333 // Current bits from the element. 334 typename SparseBitVectorElement<ElementSize>::BitWord Bits; 335 336 // Move our iterator to the first non-zero bit in the bitmap. 337 void AdvanceToFirstNonZero() { 338 if (AtEnd) 339 return; 340 if (BitVector->Elements.empty()) { 341 AtEnd = true; 342 return; 343 } 344 Iter = BitVector->Elements.begin(); 345 BitNumber = Iter->index() * ElementSize; 346 unsigned BitPos = Iter->find_first(); 347 BitNumber += BitPos; 348 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 349 Bits = Iter->word(WordNumber); 350 Bits >>= BitPos % BITWORD_SIZE; 351 } 352 353 // Move our iterator to the next non-zero bit. 354 void AdvanceToNextNonZero() { 355 if (AtEnd) 356 return; 357 358 while (Bits && !(Bits & 1)) { 359 Bits >>= 1; 360 BitNumber += 1; 361 } 362 363 // See if we ran out of Bits in this word. 364 if (!Bits) { 365 int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ; 366 // If we ran out of set bits in this element, move to next element. 367 if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) { 368 ++Iter; 369 WordNumber = 0; 370 371 // We may run out of elements in the bitmap. 372 if (Iter == BitVector->Elements.end()) { 373 AtEnd = true; 374 return; 375 } 376 // Set up for next non-zero word in bitmap. 377 BitNumber = Iter->index() * ElementSize; 378 NextSetBitNumber = Iter->find_first(); 379 BitNumber += NextSetBitNumber; 380 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 381 Bits = Iter->word(WordNumber); 382 Bits >>= NextSetBitNumber % BITWORD_SIZE; 383 } else { 384 WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE; 385 Bits = Iter->word(WordNumber); 386 Bits >>= NextSetBitNumber % BITWORD_SIZE; 387 BitNumber = Iter->index() * ElementSize; 388 BitNumber += NextSetBitNumber; 389 } 390 } 391 } 392 393 public: 394 SparseBitVectorIterator() = default; 395 396 SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS, 397 bool end = false):BitVector(RHS) { 398 Iter = BitVector->Elements.begin(); 399 BitNumber = 0; 400 Bits = 0; 401 WordNumber = ~0; 402 AtEnd = end; 403 AdvanceToFirstNonZero(); 404 } 405 406 // Preincrement. 407 inline SparseBitVectorIterator& operator++() { 408 ++BitNumber; 409 Bits >>= 1; 410 AdvanceToNextNonZero(); 411 return *this; 412 } 413 414 // Postincrement. 415 inline SparseBitVectorIterator operator++(int) { 416 SparseBitVectorIterator tmp = *this; 417 ++*this; 418 return tmp; 419 } 420 421 // Return the current set bit number. 422 unsigned operator*() const { 423 return BitNumber; 424 } 425 426 bool operator==(const SparseBitVectorIterator &RHS) const { 427 // If they are both at the end, ignore the rest of the fields. 428 if (AtEnd && RHS.AtEnd) 429 return true; 430 // Otherwise they are the same if they have the same bit number and 431 // bitmap. 432 return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber; 433 } 434 435 bool operator!=(const SparseBitVectorIterator &RHS) const { 436 return !(*this == RHS); 437 } 438 }; 439 440 public: 441 using iterator = SparseBitVectorIterator; 442 443 SparseBitVector() : Elements(), CurrElementIter(Elements.begin()) {} 444 445 SparseBitVector(const SparseBitVector &RHS) 446 : Elements(RHS.Elements), CurrElementIter(Elements.begin()) {} 447 SparseBitVector(SparseBitVector &&RHS) 448 : Elements(std::move(RHS.Elements)), CurrElementIter(Elements.begin()) {} 449 450 // Clear. 451 void clear() { 452 Elements.clear(); 453 } 454 455 // Assignment 456 SparseBitVector& operator=(const SparseBitVector& RHS) { 457 if (this == &RHS) 458 return *this; 459 460 Elements = RHS.Elements; 461 CurrElementIter = Elements.begin(); 462 return *this; 463 } 464 SparseBitVector &operator=(SparseBitVector &&RHS) { 465 Elements = std::move(RHS.Elements); 466 CurrElementIter = Elements.begin(); 467 return *this; 468 } 469 470 // Test, Reset, and Set a bit in the bitmap. 471 bool test(unsigned Idx) const { 472 if (Elements.empty()) 473 return false; 474 475 unsigned ElementIndex = Idx / ElementSize; 476 ElementListConstIter ElementIter = FindLowerBoundConst(ElementIndex); 477 478 // If we can't find an element that is supposed to contain this bit, there 479 // is nothing more to do. 480 if (ElementIter == Elements.end() || 481 ElementIter->index() != ElementIndex) 482 return false; 483 return ElementIter->test(Idx % ElementSize); 484 } 485 486 void reset(unsigned Idx) { 487 if (Elements.empty()) 488 return; 489 490 unsigned ElementIndex = Idx / ElementSize; 491 ElementListIter ElementIter = FindLowerBound(ElementIndex); 492 493 // If we can't find an element that is supposed to contain this bit, there 494 // is nothing more to do. 495 if (ElementIter == Elements.end() || 496 ElementIter->index() != ElementIndex) 497 return; 498 ElementIter->reset(Idx % ElementSize); 499 500 // When the element is zeroed out, delete it. 501 if (ElementIter->empty()) { 502 ++CurrElementIter; 503 Elements.erase(ElementIter); 504 } 505 } 506 507 void set(unsigned Idx) { 508 unsigned ElementIndex = Idx / ElementSize; 509 ElementListIter ElementIter; 510 if (Elements.empty()) { 511 ElementIter = Elements.emplace(Elements.end(), ElementIndex); 512 } else { 513 ElementIter = FindLowerBound(ElementIndex); 514 515 if (ElementIter == Elements.end() || 516 ElementIter->index() != ElementIndex) { 517 // We may have hit the beginning of our SparseBitVector, in which case, 518 // we may need to insert right after this element, which requires moving 519 // the current iterator forward one, because insert does insert before. 520 if (ElementIter != Elements.end() && 521 ElementIter->index() < ElementIndex) 522 ++ElementIter; 523 ElementIter = Elements.emplace(ElementIter, ElementIndex); 524 } 525 } 526 CurrElementIter = ElementIter; 527 528 ElementIter->set(Idx % ElementSize); 529 } 530 531 bool test_and_set(unsigned Idx) { 532 bool old = test(Idx); 533 if (!old) { 534 set(Idx); 535 return true; 536 } 537 return false; 538 } 539 540 bool operator!=(const SparseBitVector &RHS) const { 541 return !(*this == RHS); 542 } 543 544 bool operator==(const SparseBitVector &RHS) const { 545 ElementListConstIter Iter1 = Elements.begin(); 546 ElementListConstIter Iter2 = RHS.Elements.begin(); 547 548 for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end(); 549 ++Iter1, ++Iter2) { 550 if (*Iter1 != *Iter2) 551 return false; 552 } 553 return Iter1 == Elements.end() && Iter2 == RHS.Elements.end(); 554 } 555 556 // Union our bitmap with the RHS and return true if we changed. 557 bool operator|=(const SparseBitVector &RHS) { 558 if (this == &RHS) 559 return false; 560 561 bool changed = false; 562 ElementListIter Iter1 = Elements.begin(); 563 ElementListConstIter Iter2 = RHS.Elements.begin(); 564 565 // If RHS is empty, we are done 566 if (RHS.Elements.empty()) 567 return false; 568 569 while (Iter2 != RHS.Elements.end()) { 570 if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) { 571 Elements.insert(Iter1, *Iter2); 572 ++Iter2; 573 changed = true; 574 } else if (Iter1->index() == Iter2->index()) { 575 changed |= Iter1->unionWith(*Iter2); 576 ++Iter1; 577 ++Iter2; 578 } else { 579 ++Iter1; 580 } 581 } 582 CurrElementIter = Elements.begin(); 583 return changed; 584 } 585 586 // Intersect our bitmap with the RHS and return true if ours changed. 587 bool operator&=(const SparseBitVector &RHS) { 588 if (this == &RHS) 589 return false; 590 591 bool changed = false; 592 ElementListIter Iter1 = Elements.begin(); 593 ElementListConstIter Iter2 = RHS.Elements.begin(); 594 595 // Check if both bitmaps are empty. 596 if (Elements.empty() && RHS.Elements.empty()) 597 return false; 598 599 // Loop through, intersecting as we go, erasing elements when necessary. 600 while (Iter2 != RHS.Elements.end()) { 601 if (Iter1 == Elements.end()) { 602 CurrElementIter = Elements.begin(); 603 return changed; 604 } 605 606 if (Iter1->index() > Iter2->index()) { 607 ++Iter2; 608 } else if (Iter1->index() == Iter2->index()) { 609 bool BecameZero; 610 changed |= Iter1->intersectWith(*Iter2, BecameZero); 611 if (BecameZero) { 612 ElementListIter IterTmp = Iter1; 613 ++Iter1; 614 Elements.erase(IterTmp); 615 } else { 616 ++Iter1; 617 } 618 ++Iter2; 619 } else { 620 ElementListIter IterTmp = Iter1; 621 ++Iter1; 622 Elements.erase(IterTmp); 623 changed = true; 624 } 625 } 626 if (Iter1 != Elements.end()) { 627 Elements.erase(Iter1, Elements.end()); 628 changed = true; 629 } 630 CurrElementIter = Elements.begin(); 631 return changed; 632 } 633 634 // Intersect our bitmap with the complement of the RHS and return true 635 // if ours changed. 636 bool intersectWithComplement(const SparseBitVector &RHS) { 637 if (this == &RHS) { 638 if (!empty()) { 639 clear(); 640 return true; 641 } 642 return false; 643 } 644 645 bool changed = false; 646 ElementListIter Iter1 = Elements.begin(); 647 ElementListConstIter Iter2 = RHS.Elements.begin(); 648 649 // If either our bitmap or RHS is empty, we are done 650 if (Elements.empty() || RHS.Elements.empty()) 651 return false; 652 653 // Loop through, intersecting as we go, erasing elements when necessary. 654 while (Iter2 != RHS.Elements.end()) { 655 if (Iter1 == Elements.end()) { 656 CurrElementIter = Elements.begin(); 657 return changed; 658 } 659 660 if (Iter1->index() > Iter2->index()) { 661 ++Iter2; 662 } else if (Iter1->index() == Iter2->index()) { 663 bool BecameZero; 664 changed |= Iter1->intersectWithComplement(*Iter2, BecameZero); 665 if (BecameZero) { 666 ElementListIter IterTmp = Iter1; 667 ++Iter1; 668 Elements.erase(IterTmp); 669 } else { 670 ++Iter1; 671 } 672 ++Iter2; 673 } else { 674 ++Iter1; 675 } 676 } 677 CurrElementIter = Elements.begin(); 678 return changed; 679 } 680 681 bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const { 682 return intersectWithComplement(*RHS); 683 } 684 685 // Three argument version of intersectWithComplement. 686 // Result of RHS1 & ~RHS2 is stored into this bitmap. 687 void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1, 688 const SparseBitVector<ElementSize> &RHS2) 689 { 690 if (this == &RHS1) { 691 intersectWithComplement(RHS2); 692 return; 693 } else if (this == &RHS2) { 694 SparseBitVector RHS2Copy(RHS2); 695 intersectWithComplement(RHS1, RHS2Copy); 696 return; 697 } 698 699 Elements.clear(); 700 CurrElementIter = Elements.begin(); 701 ElementListConstIter Iter1 = RHS1.Elements.begin(); 702 ElementListConstIter Iter2 = RHS2.Elements.begin(); 703 704 // If RHS1 is empty, we are done 705 // If RHS2 is empty, we still have to copy RHS1 706 if (RHS1.Elements.empty()) 707 return; 708 709 // Loop through, intersecting as we go, erasing elements when necessary. 710 while (Iter2 != RHS2.Elements.end()) { 711 if (Iter1 == RHS1.Elements.end()) 712 return; 713 714 if (Iter1->index() > Iter2->index()) { 715 ++Iter2; 716 } else if (Iter1->index() == Iter2->index()) { 717 bool BecameZero = false; 718 Elements.emplace_back(Iter1->index()); 719 Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero); 720 if (BecameZero) 721 Elements.pop_back(); 722 ++Iter1; 723 ++Iter2; 724 } else { 725 Elements.push_back(*Iter1++); 726 } 727 } 728 729 // copy the remaining elements 730 std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements)); 731 } 732 733 void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1, 734 const SparseBitVector<ElementSize> *RHS2) { 735 intersectWithComplement(*RHS1, *RHS2); 736 } 737 738 bool intersects(const SparseBitVector<ElementSize> *RHS) const { 739 return intersects(*RHS); 740 } 741 742 // Return true if we share any bits in common with RHS 743 bool intersects(const SparseBitVector<ElementSize> &RHS) const { 744 ElementListConstIter Iter1 = Elements.begin(); 745 ElementListConstIter Iter2 = RHS.Elements.begin(); 746 747 // Check if both bitmaps are empty. 748 if (Elements.empty() && RHS.Elements.empty()) 749 return false; 750 751 // Loop through, intersecting stopping when we hit bits in common. 752 while (Iter2 != RHS.Elements.end()) { 753 if (Iter1 == Elements.end()) 754 return false; 755 756 if (Iter1->index() > Iter2->index()) { 757 ++Iter2; 758 } else if (Iter1->index() == Iter2->index()) { 759 if (Iter1->intersects(*Iter2)) 760 return true; 761 ++Iter1; 762 ++Iter2; 763 } else { 764 ++Iter1; 765 } 766 } 767 return false; 768 } 769 770 // Return true iff all bits set in this SparseBitVector are 771 // also set in RHS. 772 bool contains(const SparseBitVector<ElementSize> &RHS) const { 773 SparseBitVector<ElementSize> Result(*this); 774 Result &= RHS; 775 return (Result == RHS); 776 } 777 778 // Return the first set bit in the bitmap. Return -1 if no bits are set. 779 int find_first() const { 780 if (Elements.empty()) 781 return -1; 782 const SparseBitVectorElement<ElementSize> &First = *(Elements.begin()); 783 return (First.index() * ElementSize) + First.find_first(); 784 } 785 786 // Return the last set bit in the bitmap. Return -1 if no bits are set. 787 int find_last() const { 788 if (Elements.empty()) 789 return -1; 790 const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin()); 791 return (Last.index() * ElementSize) + Last.find_last(); 792 } 793 794 // Return true if the SparseBitVector is empty 795 bool empty() const { 796 return Elements.empty(); 797 } 798 799 unsigned count() const { 800 unsigned BitCount = 0; 801 for (ElementListConstIter Iter = Elements.begin(); 802 Iter != Elements.end(); 803 ++Iter) 804 BitCount += Iter->count(); 805 806 return BitCount; 807 } 808 809 iterator begin() const { 810 return iterator(this); 811 } 812 813 iterator end() const { 814 return iterator(this, true); 815 } 816 }; 817 818 // Convenience functions to allow Or and And without dereferencing in the user 819 // code. 820 821 template <unsigned ElementSize> 822 inline bool operator |=(SparseBitVector<ElementSize> &LHS, 823 const SparseBitVector<ElementSize> *RHS) { 824 return LHS |= *RHS; 825 } 826 827 template <unsigned ElementSize> 828 inline bool operator |=(SparseBitVector<ElementSize> *LHS, 829 const SparseBitVector<ElementSize> &RHS) { 830 return LHS->operator|=(RHS); 831 } 832 833 template <unsigned ElementSize> 834 inline bool operator &=(SparseBitVector<ElementSize> *LHS, 835 const SparseBitVector<ElementSize> &RHS) { 836 return LHS->operator&=(RHS); 837 } 838 839 template <unsigned ElementSize> 840 inline bool operator &=(SparseBitVector<ElementSize> &LHS, 841 const SparseBitVector<ElementSize> *RHS) { 842 return LHS &= *RHS; 843 } 844 845 // Convenience functions for infix union, intersection, difference operators. 846 847 template <unsigned ElementSize> 848 inline SparseBitVector<ElementSize> 849 operator|(const SparseBitVector<ElementSize> &LHS, 850 const SparseBitVector<ElementSize> &RHS) { 851 SparseBitVector<ElementSize> Result(LHS); 852 Result |= RHS; 853 return Result; 854 } 855 856 template <unsigned ElementSize> 857 inline SparseBitVector<ElementSize> 858 operator&(const SparseBitVector<ElementSize> &LHS, 859 const SparseBitVector<ElementSize> &RHS) { 860 SparseBitVector<ElementSize> Result(LHS); 861 Result &= RHS; 862 return Result; 863 } 864 865 template <unsigned ElementSize> 866 inline SparseBitVector<ElementSize> 867 operator-(const SparseBitVector<ElementSize> &LHS, 868 const SparseBitVector<ElementSize> &RHS) { 869 SparseBitVector<ElementSize> Result; 870 Result.intersectWithComplement(LHS, RHS); 871 return Result; 872 } 873 874 // Dump a SparseBitVector to a stream 875 template <unsigned ElementSize> 876 void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) { 877 out << "["; 878 879 typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(), 880 be = LHS.end(); 881 if (bi != be) { 882 out << *bi; 883 for (++bi; bi != be; ++bi) { 884 out << " " << *bi; 885 } 886 } 887 out << "]\n"; 888 } 889 890 } // end namespace llvm 891 892 #endif // LLVM_ADT_SPARSEBITVECTOR_H 893