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