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