1 //===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector -*- C++ -*- ===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Daniel Berlin and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the SparseBitVector class. See the doxygen comment for
11 // SparseBitVector for more details on the algorithm used.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_ADT_SPARSEBITVECTOR_H
16 #define LLVM_ADT_SPARSEBITVECTOR_H
22 #include "llvm/Support/DataTypes.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include "llvm/Support/MathExtras.h"
28 /// SparseBitVector is an implementation of a bitvector that is sparse by only
29 /// storing the elements that have non-zero bits set. In order to make this
30 /// fast for the most common cases, SparseBitVector is implemented as a linked
31 /// list of SparseBitVectorElements. We maintain a pointer to the last
32 /// SparseBitVectorElement accessed (in the form of a list iterator), in order
33 /// to make multiple in-order test/set constant time after the first one is
34 /// executed. Note that using vectors to store SparseBitVectorElement's does
35 /// not work out very well because it causes insertion in the middle to take
36 /// enormous amounts of time with a large amount of bits. Other structures that
37 /// have better worst cases for insertion in the middle (various balanced trees,
38 /// etc) do not perform as well in practice as a linked list with this iterator
39 /// kept up to date. They are also significantly more memory intensive.
42 template <unsigned ElementSize = 128>
43 struct SparseBitVectorElement {
45 typedef unsigned long BitWord;
47 BITWORD_SIZE = sizeof(BitWord) * 8,
48 BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
49 BITS_PER_ELEMENT = ElementSize
52 // Index of Element in terms of where first bit starts.
53 unsigned ElementIndex;
54 BitWord Bits[BITWORDS_PER_ELEMENT];
55 SparseBitVectorElement();
57 explicit SparseBitVectorElement(unsigned Idx) {
59 memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
62 ~SparseBitVectorElement() {
66 SparseBitVectorElement(const SparseBitVectorElement &RHS) {
67 ElementIndex = RHS.ElementIndex;
68 std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
72 bool operator==(const SparseBitVectorElement &RHS) const {
73 if (ElementIndex != RHS.ElementIndex)
75 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
76 if (Bits[i] != RHS.Bits[i])
81 bool operator!=(const SparseBitVectorElement &RHS) const {
82 return !(*this == RHS);
85 // Return the bits that make up word Idx in our element.
86 BitWord word(unsigned Idx) const {
87 assert (Idx < BITWORDS_PER_ELEMENT);
91 unsigned index() const {
96 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
102 void set(unsigned Idx) {
103 Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
106 bool test_and_set (unsigned Idx) {
107 bool old = test(Idx);
113 void reset(unsigned Idx) {
114 Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
117 bool test(unsigned Idx) const {
118 return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
121 unsigned count() const {
122 unsigned NumBits = 0;
123 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
124 if (sizeof(BitWord) == 4)
125 NumBits += CountPopulation_32(Bits[i]);
126 else if (sizeof(BitWord) == 8)
127 NumBits += CountPopulation_64(Bits[i]);
129 assert(0 && "Unsupported!");
133 /// find_first - Returns the index of the first set bit.
134 int find_first() const {
135 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
137 if (sizeof(BitWord) == 4)
138 return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
139 else if (sizeof(BitWord) == 8)
140 return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
142 assert(0 && "Unsupported!");
144 assert(0 && "Illegal empty element");
147 /// find_next - Returns the index of the next set bit following the
148 /// "Prev" bit. Returns -1 if the next set bit is not found.
149 int find_next(unsigned Prev) const {
151 if (Prev >= BITS_PER_ELEMENT)
154 unsigned WordPos = Prev / BITWORD_SIZE;
155 unsigned BitPos = Prev % BITWORD_SIZE;
156 BitWord Copy = Bits[WordPos];
157 assert (WordPos <= BITWORDS_PER_ELEMENT
158 && "Word Position outside of element");
160 // Mask off previous bits.
161 Copy &= ~0L << BitPos;
164 if (sizeof(BitWord) == 4)
165 return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy);
166 else if (sizeof(BitWord) == 8)
167 return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
169 assert(0 && "Unsupported!");
172 // Check subsequent words.
173 for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
175 if (sizeof(BitWord) == 4)
176 return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
177 else if (sizeof(BitWord) == 8)
178 return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
180 assert(0 && "Unsupported!");
185 // Union this element with RHS and return true if this one changed.
186 bool unionWith(const SparseBitVectorElement &RHS) {
187 bool changed = false;
188 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
189 BitWord old = changed ? 0 : Bits[i];
191 Bits[i] |= RHS.Bits[i];
198 // Return true if we have any bits in common with RHS
199 bool intersects(const SparseBitVectorElement &RHS) const {
200 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
201 if (RHS.Bits[i] & Bits[i])
207 // Intersect this Element with RHS and return true if this one changed.
208 // BecameZero is set to true if this element became all-zero bits.
209 bool intersectWith(const SparseBitVectorElement &RHS,
211 bool changed = false;
215 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
216 BitWord old = changed ? 0 : Bits[i];
218 Bits[i] &= RHS.Bits[i];
225 BecameZero = !allzero;
228 // Intersect this Element with the complement of RHS and return true if this
229 // one changed. BecameZero is set to true if this element became all-zero
231 bool intersectWithComplement(const SparseBitVectorElement &RHS,
233 bool changed = false;
237 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
238 BitWord old = changed ? 0 : Bits[i];
240 Bits[i] &= ~RHS.Bits[i];
247 BecameZero = !allzero;
250 // Three argument version of intersectWithComplement that intersects
251 // RHS1 & ~RHS2 into this element
252 void intersectWithComplement(const SparseBitVectorElement &RHS1,
253 const SparseBitVectorElement &RHS2,
258 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
259 Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
263 BecameZero = !allzero;
268 template <unsigned ElementSize = 128>
269 class SparseBitVector {
270 typedef std::list<SparseBitVectorElement<ElementSize> *> ElementList;
271 typedef typename ElementList::iterator ElementListIter;
272 typedef typename ElementList::const_iterator ElementListConstIter;
274 BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
277 // Pointer to our current Element.
278 ElementListIter CurrElementIter;
279 ElementList Elements;
281 // This is like std::lower_bound, except we do linear searching from the
283 ElementListIter FindLowerBound(unsigned ElementIndex) {
285 if (Elements.empty()) {
286 CurrElementIter = Elements.begin();
287 return Elements.begin();
290 // Make sure our current iterator is valid.
291 if (CurrElementIter == Elements.end())
294 // Search from our current iterator, either backwards or forwards,
295 // depending on what element we are looking for.
296 ElementListIter ElementIter = CurrElementIter;
297 if ((*CurrElementIter)->index() == ElementIndex) {
299 } else if ((*CurrElementIter)->index() > ElementIndex) {
300 while (ElementIter != Elements.begin()
301 && (*ElementIter)->index() > ElementIndex)
304 while (ElementIter != Elements.end() &&
305 (*ElementIter)->index() <= ElementIndex)
309 CurrElementIter = ElementIter;
313 // Iterator to walk set bits in the bitmap. This iterator is a lot uglier
314 // than it would be, in order to be efficient.
315 class SparseBitVectorIterator {
319 const SparseBitVector<ElementSize> *BitVector;
321 // Current element inside of bitmap.
322 ElementListConstIter Iter;
324 // Current bit number inside of our bitmap.
327 // Current word number inside of our element.
330 // Current bits from the element.
331 typename SparseBitVectorElement<ElementSize>::BitWord Bits;
333 // Move our iterator to the first non-zero bit in the bitmap.
334 void AdvanceToFirstNonZero() {
337 if (BitVector->Elements.empty()) {
341 Iter = BitVector->Elements.begin();
342 BitNumber = (*Iter)->index() * ElementSize;
343 unsigned BitPos = (*Iter)->find_first();
345 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
346 Bits = (*Iter)->word(WordNumber);
347 Bits >>= BitPos % BITWORD_SIZE;
350 // Move our iterator to the next non-zero bit.
351 void AdvanceToNextNonZero() {
355 while (Bits && !(Bits & 1)) {
360 // See if we ran out of Bits in this word.
362 int NextSetBitNumber = (*Iter)->find_next(BitNumber % ElementSize) ;
363 // If we ran out of set bits in this element, move to next element.
364 if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
368 // We may run out of elements in the bitmap.
369 if (Iter == BitVector->Elements.end()) {
373 // Set up for next non zero word in bitmap.
374 BitNumber = (*Iter)->index() * ElementSize;
375 NextSetBitNumber = (*Iter)->find_first();
376 BitNumber += NextSetBitNumber;
377 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
378 Bits = (*Iter)->word(WordNumber);
379 Bits >>= NextSetBitNumber % BITWORD_SIZE;
381 WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
382 Bits = (*Iter)->word(WordNumber);
383 Bits >>= NextSetBitNumber % BITWORD_SIZE;
389 inline SparseBitVectorIterator& operator++() {
392 AdvanceToNextNonZero();
397 inline SparseBitVectorIterator operator++(int) {
398 SparseBitVectorIterator tmp = *this;
403 // Return the current set bit number.
404 unsigned operator*() const {
408 bool operator==(const SparseBitVectorIterator &RHS) const {
409 // If they are both at the end, ignore the rest of the fields.
410 if (AtEnd == RHS.AtEnd)
412 // Otherwise they are the same if they have the same bit number and
414 return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
416 bool operator!=(const SparseBitVectorIterator &RHS) const {
417 return !(*this == RHS);
419 SparseBitVectorIterator(): BitVector(NULL) {
423 SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
424 bool end = false):BitVector(RHS) {
425 Iter = BitVector->Elements.begin();
430 AdvanceToFirstNonZero();
434 typedef SparseBitVectorIterator iterator;
437 CurrElementIter = Elements.begin ();
441 for_each(Elements.begin(), Elements.end(),
442 deleter<SparseBitVectorElement<ElementSize> >);
445 // SparseBitVector copy ctor.
446 SparseBitVector(const SparseBitVector &RHS) {
447 ElementListConstIter ElementIter = RHS.Elements.begin();
448 while (ElementIter != RHS.Elements.end()) {
449 SparseBitVectorElement<ElementSize> *ElementCopy;
450 ElementCopy = new SparseBitVectorElement<ElementSize>(*(*ElementIter));
451 Elements.push_back(ElementCopy);
454 CurrElementIter = Elements.begin ();
457 // Test, Reset, and Set a bit in the bitmap.
458 bool test(unsigned Idx) {
459 if (Elements.empty())
462 unsigned ElementIndex = Idx / ElementSize;
463 ElementListIter ElementIter = FindLowerBound(ElementIndex);
465 // If we can't find an element that is supposed to contain this bit, there
466 // is nothing more to do.
467 if (ElementIter == Elements.end() ||
468 (*ElementIter)->index() != ElementIndex)
470 return (*ElementIter)->test(Idx % ElementSize);
473 void reset(unsigned Idx) {
474 if (Elements.empty())
477 unsigned ElementIndex = Idx / ElementSize;
478 ElementListIter ElementIter = FindLowerBound(ElementIndex);
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)
485 (*ElementIter)->reset(Idx % ElementSize);
487 // When the element is zeroed out, delete it.
488 if ((*ElementIter)->empty()) {
489 delete (*ElementIter);
491 Elements.erase(ElementIter);
495 void set(unsigned Idx) {
496 SparseBitVectorElement<ElementSize> *Element;
497 unsigned ElementIndex = Idx / ElementSize;
499 if (Elements.empty()) {
500 Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
501 Elements.push_back(Element);
503 ElementListIter ElementIter = FindLowerBound(ElementIndex);
505 if (ElementIter != Elements.end() &&
506 (*ElementIter)->index() == ElementIndex)
507 Element = *ElementIter;
509 Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
510 // Insert does insert before, and lower bound gives the one before.
511 Elements.insert(++ElementIter, Element);
514 Element->set(Idx % ElementSize);
517 bool test_and_set (unsigned Idx) {
518 bool old = test(Idx);
524 // Union our bitmap with the RHS and return true if we changed.
525 bool operator|=(const SparseBitVector &RHS) {
526 bool changed = false;
527 ElementListIter Iter1 = Elements.begin();
528 ElementListConstIter Iter2 = RHS.Elements.begin();
530 // IE They may both be end
534 // See if the first bitmap element is the same in both. This is only
535 // possible if they are the same bitmap.
536 if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
537 if (*Iter1 == *Iter2)
540 while (Iter2 != RHS.Elements.end()) {
541 if (Iter1 == Elements.end() || (*Iter1)->index() > (*Iter2)->index()) {
542 SparseBitVectorElement<ElementSize> *NewElem;
544 NewElem = new SparseBitVectorElement<ElementSize>(*(*Iter2));
545 Elements.insert(Iter1, NewElem);
548 } else if ((*Iter1)->index() == (*Iter2)->index()) {
549 changed |= (*Iter1)->unionWith(*(*Iter2));
556 CurrElementIter = Elements.begin();
560 // Intersect our bitmap with the RHS and return true if ours changed.
561 bool operator&=(const SparseBitVector &RHS) {
562 bool changed = false;
563 ElementListIter Iter1 = Elements.begin();
564 ElementListConstIter Iter2 = RHS.Elements.begin();
566 // IE They may both be end.
570 // See if the first bitmap element is the same in both. This is only
571 // possible if they are the same bitmap.
572 if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
573 if (*Iter1 == *Iter2)
576 // Loop through, intersecting as we go, erasing elements when necessary.
577 while (Iter2 != RHS.Elements.end()) {
578 if (Iter1 == Elements.end())
581 if ((*Iter1)->index() > (*Iter2)->index()) {
583 } else if ((*Iter1)->index() == (*Iter2)->index()) {
585 changed |= (*Iter1)->intersectWith(*(*Iter2), BecameZero);
587 ElementListIter IterTmp = Iter1;
589 Elements.erase(IterTmp);
594 ElementListIter IterTmp = Iter1;
597 Elements.erase(IterTmp);
600 for_each(Iter1, Elements.end(),
601 deleter<SparseBitVectorElement<ElementSize> >);
602 Elements.erase(Iter1, Elements.end());
603 CurrElementIter = Elements.begin();
607 // Intersect our bitmap with the complement of the RHS and return true if ours
609 bool intersectWithComplement(const SparseBitVector &RHS) {
610 bool changed = false;
611 ElementListIter Iter1 = Elements.begin();
612 ElementListConstIter Iter2 = RHS.Elements.begin();
614 // IE They may both be end.
618 // See if the first bitmap element is the same in both. This is only
619 // possible if they are the same bitmap.
620 if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
621 if (*Iter1 == *Iter2) {
622 for_each(Elements.begin(), Elements.end(),
623 deleter<SparseBitVectorElement<ElementSize> >);
628 // Loop through, intersecting as we go, erasing elements when necessary.
629 while (Iter2 != RHS.Elements.end()) {
630 if (Iter1 == Elements.end())
633 if ((*Iter1)->index() > (*Iter2)->index()) {
635 } else if ((*Iter1)->index() == (*Iter2)->index()) {
637 changed |= (*Iter1)->intersectWithComplement(*(*Iter2), BecameZero);
639 ElementListIter IterTmp = Iter1;
641 Elements.erase(IterTmp);
646 ElementListIter IterTmp = Iter1;
649 Elements.erase(IterTmp);
652 CurrElementIter = Elements.begin();
656 bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
657 return intersectWithComplement(*RHS);
661 // Three argument version of intersectWithComplement. Result of RHS1 & ~RHS2
662 // is stored into this bitmap.
663 void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
664 const SparseBitVector<ElementSize> &RHS2)
666 for_each(Elements.begin(), Elements.end(),
667 deleter<SparseBitVectorElement<ElementSize> >);
670 ElementListConstIter Iter1 = RHS1.Elements.begin();
671 ElementListConstIter Iter2 = RHS2.Elements.begin();
673 // IE They may both be end.
677 // See if the first bitmap element is the same in both. This is only
678 // possible if they are the same bitmap.
679 if (Iter1 != RHS1.Elements.end() && Iter2 != RHS2.Elements.end())
680 if (*Iter1 == *Iter2) {
684 // Loop through, intersecting as we go, erasing elements when necessary.
685 while (Iter2 != RHS2.Elements.end()) {
686 if (Iter1 == RHS1.Elements.end())
689 if ((*Iter1)->index() > (*Iter2)->index()) {
691 } else if ((*Iter1)->index() == (*Iter2)->index()) {
692 bool BecameZero = false;
693 SparseBitVectorElement<ElementSize> *NewElement =
694 new SparseBitVectorElement<ElementSize>((*Iter1)->index());
696 NewElement->intersectWithComplement(*(*Iter1), *(*Iter2), BecameZero);
700 Elements.push_back(NewElement);
709 // copy the remaining elements
711 while (Iter1 != RHS1.Elements.end()) {
712 SparseBitVectorElement<ElementSize> *NewElement =
713 new SparseBitVectorElement<ElementSize>(*(*Iter1));
714 Elements.push_back(NewElement);
717 CurrElementIter = Elements.begin();
721 void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
722 const SparseBitVector<ElementSize> *RHS2) {
723 intersectWithComplement(*RHS1, *RHS2);
726 bool intersects(const SparseBitVector<ElementSize> *RHS) const {
727 return intersects(*RHS);
730 // Return true if we share any bits in common with RHS
731 bool intersects(const SparseBitVector<ElementSize> &RHS) const {
732 ElementListConstIter Iter1 = Elements.begin();
733 ElementListConstIter Iter2 = RHS.Elements.begin();
735 // IE They may both be end.
739 // See if the first bitmap element is the same in both. This is only
740 // possible if they are the same bitmap.
741 if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
742 if (*Iter1 == *Iter2) {
746 // Loop through, intersecting stopping when we hit bits in common.
747 while (Iter2 != RHS.Elements.end()) {
748 if (Iter1 == Elements.end())
751 if ((*Iter1)->index() > (*Iter2)->index()) {
753 } else if ((*Iter1)->index() == (*Iter2)->index()) {
754 if ((*Iter1)->intersects(*(*Iter2)))
765 // Return the first set bit in the bitmap. Return -1 if no bits are set.
766 int find_first() const {
767 if (Elements.empty())
769 const SparseBitVectorElement<ElementSize> *First = *(Elements.begin());
770 return (First->index() * ElementSize) + First->find_first();
773 // Return true if the SparseBitVector is empty
775 return Elements.empty();
778 unsigned count() const {
779 unsigned BitCount = 0;
780 for (ElementListConstIter Iter = Elements.begin();
781 Iter != Elements.end();
783 BitCount += (*Iter)->count();
787 iterator begin() const {
788 return iterator(this);
791 iterator end() const {
792 return iterator(this, ~0);
796 // Convenience functions to allow Or and And without dereferencing in the user
799 template <unsigned ElementSize>
800 inline bool operator |=(SparseBitVector<ElementSize> &LHS,
801 const SparseBitVector<ElementSize> *RHS) {
805 template <unsigned ElementSize>
806 inline bool operator |=(SparseBitVector<ElementSize> *LHS,
807 const SparseBitVector<ElementSize> &RHS) {
808 return LHS->operator|=(RHS);
811 template <unsigned ElementSize>
812 inline bool operator &=(SparseBitVector<ElementSize> *LHS,
813 const SparseBitVector<ElementSize> &RHS) {
814 return LHS->operator&=(RHS);
817 template <unsigned ElementSize>
818 inline bool operator &=(SparseBitVector<ElementSize> &LHS,
819 const SparseBitVector<ElementSize> *RHS) {
820 return LHS &= (*RHS);