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