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