SparseBitVector.h revision acddf9d019316ac1735667dc92d96092e9f5bf2e
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 <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 = ~0U; 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 // If RHS is empty, we are done 584 if (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 CurrElementIter = Elements.begin(); 619 return changed; 620 } 621 622 if (Iter1->index() > Iter2->index()) { 623 ++Iter2; 624 } else if (Iter1->index() == Iter2->index()) { 625 bool BecameZero; 626 changed |= Iter1->intersectWith(*Iter2, BecameZero); 627 if (BecameZero) { 628 ElementListIter IterTmp = Iter1; 629 ++Iter1; 630 Elements.erase(IterTmp); 631 } else { 632 ++Iter1; 633 } 634 ++Iter2; 635 } else { 636 ElementListIter IterTmp = Iter1; 637 ++Iter1; 638 Elements.erase(IterTmp); 639 } 640 } 641 Elements.erase(Iter1, Elements.end()); 642 CurrElementIter = Elements.begin(); 643 return changed; 644 } 645 646 // Intersect our bitmap with the complement of the RHS and return true if ours 647 // changed. 648 bool intersectWithComplement(const SparseBitVector &RHS) { 649 bool changed = false; 650 ElementListIter Iter1 = Elements.begin(); 651 ElementListConstIter Iter2 = RHS.Elements.begin(); 652 653 // If either our bitmap or RHS is empty, we are done 654 if (Elements.empty() || RHS.Elements.empty()) 655 return false; 656 657 // Loop through, intersecting as we go, erasing elements when necessary. 658 while (Iter2 != RHS.Elements.end()) { 659 if (Iter1 == Elements.end()) { 660 CurrElementIter = Elements.begin(); 661 return changed; 662 } 663 664 if (Iter1->index() > Iter2->index()) { 665 ++Iter2; 666 } else if (Iter1->index() == Iter2->index()) { 667 bool BecameZero; 668 changed |= Iter1->intersectWithComplement(*Iter2, BecameZero); 669 if (BecameZero) { 670 ElementListIter IterTmp = Iter1; 671 ++Iter1; 672 Elements.erase(IterTmp); 673 } else { 674 ++Iter1; 675 } 676 ++Iter2; 677 } else { 678 ++Iter1; 679 } 680 } 681 CurrElementIter = Elements.begin(); 682 return changed; 683 } 684 685 bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const { 686 return intersectWithComplement(*RHS); 687 } 688 689 690 // Three argument version of intersectWithComplement. Result of RHS1 & ~RHS2 691 // is stored into this bitmap. 692 void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1, 693 const SparseBitVector<ElementSize> &RHS2) 694 { 695 Elements.clear(); 696 CurrElementIter = Elements.begin(); 697 ElementListConstIter Iter1 = RHS1.Elements.begin(); 698 ElementListConstIter Iter2 = RHS2.Elements.begin(); 699 700 // If RHS1 is empty, we are done 701 // If RHS2 is empty, we still have to copy RHS1 702 if (RHS1.Elements.empty()) 703 return; 704 705 // Loop through, intersecting as we go, erasing elements when necessary. 706 while (Iter2 != RHS2.Elements.end()) { 707 if (Iter1 == RHS1.Elements.end()) 708 return; 709 710 if (Iter1->index() > Iter2->index()) { 711 ++Iter2; 712 } else if (Iter1->index() == Iter2->index()) { 713 bool BecameZero = false; 714 SparseBitVectorElement<ElementSize> *NewElement = 715 new SparseBitVectorElement<ElementSize>(Iter1->index()); 716 NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero); 717 if (!BecameZero) { 718 Elements.push_back(NewElement); 719 } 720 else 721 delete NewElement; 722 ++Iter1; 723 ++Iter2; 724 } else { 725 SparseBitVectorElement<ElementSize> *NewElement = 726 new SparseBitVectorElement<ElementSize>(*Iter1); 727 Elements.push_back(NewElement); 728 ++Iter1; 729 } 730 } 731 732 // copy the remaining elements 733 while (Iter1 != RHS1.Elements.end()) { 734 SparseBitVectorElement<ElementSize> *NewElement = 735 new SparseBitVectorElement<ElementSize>(*Iter1); 736 Elements.push_back(NewElement); 737 ++Iter1; 738 } 739 740 return; 741 } 742 743 void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1, 744 const SparseBitVector<ElementSize> *RHS2) { 745 intersectWithComplement(*RHS1, *RHS2); 746 } 747 748 bool intersects(const SparseBitVector<ElementSize> *RHS) const { 749 return intersects(*RHS); 750 } 751 752 // Return true if we share any bits in common with RHS 753 bool intersects(const SparseBitVector<ElementSize> &RHS) const { 754 ElementListConstIter Iter1 = Elements.begin(); 755 ElementListConstIter Iter2 = RHS.Elements.begin(); 756 757 // Check if both bitmaps are empty. 758 if (Elements.empty() && RHS.Elements.empty()) 759 return false; 760 761 // Loop through, intersecting stopping when we hit bits in common. 762 while (Iter2 != RHS.Elements.end()) { 763 if (Iter1 == Elements.end()) 764 return false; 765 766 if (Iter1->index() > Iter2->index()) { 767 ++Iter2; 768 } else if (Iter1->index() == Iter2->index()) { 769 if (Iter1->intersects(*Iter2)) 770 return true; 771 ++Iter1; 772 ++Iter2; 773 } else { 774 ++Iter1; 775 } 776 } 777 return false; 778 } 779 780 // Return the first set bit in the bitmap. Return -1 if no bits are set. 781 int find_first() const { 782 if (Elements.empty()) 783 return -1; 784 const SparseBitVectorElement<ElementSize> &First = *(Elements.begin()); 785 return (First.index() * ElementSize) + First.find_first(); 786 } 787 788 // Return true if the SparseBitVector is empty 789 bool empty() const { 790 return Elements.empty(); 791 } 792 793 unsigned count() const { 794 unsigned BitCount = 0; 795 for (ElementListConstIter Iter = Elements.begin(); 796 Iter != Elements.end(); 797 ++Iter) 798 BitCount += Iter->count(); 799 800 return BitCount; 801 } 802 iterator begin() const { 803 return iterator(this); 804 } 805 806 iterator end() const { 807 return iterator(this, true); 808 } 809 810 // Get a hash value for this bitmap. 811 uint64_t getHashValue() const { 812 uint64_t HashVal = 0; 813 for (ElementListConstIter Iter = Elements.begin(); 814 Iter != Elements.end(); 815 ++Iter) { 816 HashVal ^= Iter->index(); 817 HashVal ^= Iter->getHashValue(); 818 } 819 return HashVal; 820 } 821}; 822 823// Convenience functions to allow Or and And without dereferencing in the user 824// code. 825 826template <unsigned ElementSize> 827inline bool operator |=(SparseBitVector<ElementSize> &LHS, 828 const SparseBitVector<ElementSize> *RHS) { 829 return LHS |= *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->operator&=(RHS); 842} 843 844template <unsigned ElementSize> 845inline bool operator &=(SparseBitVector<ElementSize> &LHS, 846 const SparseBitVector<ElementSize> *RHS) { 847 return LHS &= (*RHS); 848} 849 850 851// Dump a SparseBitVector to a stream 852template <unsigned ElementSize> 853void dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) { 854 out << "[ "; 855 856 typename SparseBitVector<ElementSize>::iterator bi; 857 for (bi = LHS.begin(); bi != LHS.end(); ++bi) { 858 out << *bi << " "; 859 } 860 out << " ]\n"; 861} 862} 863 864 865 866#endif 867