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