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