include/llvm/ADT/SparseBitVector.h

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