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