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