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