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