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