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;
252 template <unsigned ElementSize = 128>
253 class SparseBitVector {
254 typedef std::list<SparseBitVectorElement<ElementSize> *> ElementList;
255 typedef typename ElementList::iterator ElementListIter;
256 typedef typename ElementList::const_iterator ElementListConstIter;
258 BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
261 // Pointer to our current Element.
262 ElementListIter CurrElementIter;
263 ElementList Elements;
265 // This is like std::lower_bound, except we do linear searching from the
267 ElementListIter FindLowerBound(unsigned ElementIndex) {
269 if (Elements.empty()) {
270 CurrElementIter = Elements.begin();
271 return Elements.begin();
274 // Make sure our current iterator is valid.
275 if (CurrElementIter == Elements.end())
278 // Search from our current iterator, either backwards or forwards,
279 // depending on what element we are looking for.
280 ElementListIter ElementIter = CurrElementIter;
281 if ((*CurrElementIter)->index() == ElementIndex) {
283 } else if ((*CurrElementIter)->index() > ElementIndex) {
284 while (ElementIter != Elements.begin()
285 && (*ElementIter)->index() > ElementIndex)
288 while (ElementIter != Elements.end() &&
289 (*ElementIter)->index() <= ElementIndex)
293 CurrElementIter = ElementIter;
297 // Iterator to walk set bits in the bitmap. This iterator is a lot uglier
298 // than it would be, in order to be efficient.
299 class SparseBitVectorIterator {
303 const SparseBitVector<ElementSize> *BitVector;
305 // Current element inside of bitmap.
306 ElementListConstIter Iter;
308 // Current bit number inside of our bitmap.
311 // Current word number inside of our element.
314 // Current bits from the element.
315 typename SparseBitVectorElement<ElementSize>::BitWord Bits;
317 // Move our iterator to the first non-zero bit in the bitmap.
318 void AdvanceToFirstNonZero() {
321 if (BitVector->Elements.empty()) {
325 Iter = BitVector->Elements.begin();
326 BitNumber = (*Iter)->index() * ElementSize;
327 unsigned BitPos = (*Iter)->find_first();
329 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
330 Bits = (*Iter)->word(WordNumber);
331 Bits >>= BitPos % BITWORD_SIZE;
334 // Move our iterator to the next non-zero bit.
335 void AdvanceToNextNonZero() {
339 while (Bits && !(Bits & 1)) {
344 // See if we ran out of Bits in this word.
346 int NextSetBitNumber = (*Iter)->find_next(BitNumber % ElementSize) ;
347 // If we ran out of set bits in this element, move to next element.
348 if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
352 // We may run out of elements in the bitmap.
353 if (Iter == BitVector->Elements.end()) {
357 // Set up for next non zero word in bitmap.
358 BitNumber = (*Iter)->index() * ElementSize;
359 NextSetBitNumber = (*Iter)->find_first();
360 BitNumber += NextSetBitNumber;
361 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
362 Bits = (*Iter)->word(WordNumber);
363 Bits >>= NextSetBitNumber % BITWORD_SIZE;
365 WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
366 Bits = (*Iter)->word(WordNumber);
367 Bits >>= NextSetBitNumber % BITWORD_SIZE;
373 inline SparseBitVectorIterator& operator++() {
376 AdvanceToNextNonZero();
381 inline SparseBitVectorIterator operator++(int) {
382 SparseBitVectorIterator tmp = *this;
387 // Return the current set bit number.
388 unsigned operator*() const {
392 bool operator==(const SparseBitVectorIterator &RHS) const {
393 // If they are both at the end, ignore the rest of the fields.
394 if (AtEnd == RHS.AtEnd)
396 // Otherwise they are the same if they have the same bit number and
398 return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
400 bool operator!=(const SparseBitVectorIterator &RHS) const {
401 return !(*this == RHS);
403 SparseBitVectorIterator(): BitVector(NULL) {
407 SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
408 bool end = false):BitVector(RHS) {
409 Iter = BitVector->Elements.begin();
414 AdvanceToFirstNonZero();
418 typedef SparseBitVectorIterator iterator;
421 CurrElementIter = Elements.begin ();
425 for_each(Elements.begin(), Elements.end(),
426 deleter<SparseBitVectorElement<ElementSize> >);
429 // SparseBitVector copy ctor.
430 SparseBitVector(const SparseBitVector &RHS) {
431 ElementListConstIter ElementIter = RHS.Elements.begin();
432 while (ElementIter != RHS.Elements.end()) {
433 SparseBitVectorElement<ElementSize> *ElementCopy;
434 ElementCopy = new SparseBitVectorElement<ElementSize>(*(*ElementIter));
435 Elements.push_back(ElementCopy);
438 CurrElementIter = Elements.begin ();
441 // Test, Reset, and Set a bit in the bitmap.
442 bool test(unsigned Idx) {
443 if (Elements.empty())
446 unsigned ElementIndex = Idx / ElementSize;
447 ElementListIter ElementIter = FindLowerBound(ElementIndex);
449 // If we can't find an element that is supposed to contain this bit, there
450 // is nothing more to do.
451 if (ElementIter == Elements.end() ||
452 (*ElementIter)->index() != ElementIndex)
454 return (*ElementIter)->test(Idx % ElementSize);
457 void reset(unsigned Idx) {
458 if (Elements.empty())
461 unsigned ElementIndex = Idx / ElementSize;
462 ElementListIter ElementIter = FindLowerBound(ElementIndex);
464 // If we can't find an element that is supposed to contain this bit, there
465 // is nothing more to do.
466 if (ElementIter == Elements.end() ||
467 (*ElementIter)->index() != ElementIndex)
469 (*ElementIter)->reset(Idx % ElementSize);
471 // When the element is zeroed out, delete it.
472 if ((*ElementIter)->empty()) {
473 delete (*ElementIter);
475 Elements.erase(ElementIter);
479 void set(unsigned Idx) {
480 SparseBitVectorElement<ElementSize> *Element;
481 unsigned ElementIndex = Idx / ElementSize;
483 if (Elements.empty()) {
484 Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
485 Elements.push_back(Element);
487 ElementListIter ElementIter = FindLowerBound(ElementIndex);
489 if (ElementIter != Elements.end() &&
490 (*ElementIter)->index() == ElementIndex)
491 Element = *ElementIter;
493 Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
494 // Insert does insert before, and lower bound gives the one before.
495 Elements.insert(++ElementIter, Element);
498 Element->set(Idx % ElementSize);
501 bool test_and_set (unsigned Idx) {
502 bool old = test(Idx);
508 // Union our bitmap with the RHS and return true if we changed.
509 bool operator|=(const SparseBitVector &RHS) {
510 bool changed = false;
511 ElementListIter Iter1 = Elements.begin();
512 ElementListConstIter Iter2 = RHS.Elements.begin();
514 // IE They may both be end
518 // See if the first bitmap element is the same in both. This is only
519 // possible if they are the same bitmap.
520 if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
521 if (*Iter1 == *Iter2)
524 while (Iter2 != RHS.Elements.end()) {
525 if (Iter1 == Elements.end() || (*Iter1)->index() > (*Iter2)->index()) {
526 SparseBitVectorElement<ElementSize> *NewElem;
528 NewElem = new SparseBitVectorElement<ElementSize>(*(*Iter2));
529 Elements.insert(Iter1, NewElem);
532 } else if ((*Iter1)->index() == (*Iter2)->index()) {
533 changed |= (*Iter1)->unionWith(*(*Iter2));
540 CurrElementIter = Elements.begin();
544 // Intersect our bitmap with the RHS and return true if ours changed.
545 bool operator&=(const SparseBitVector &RHS) {
546 bool changed = false;
547 ElementListIter Iter1 = Elements.begin();
548 ElementListConstIter Iter2 = RHS.Elements.begin();
550 // IE They may both be end.
554 // See if the first bitmap element is the same in both. This is only
555 // possible if they are the same bitmap.
556 if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
557 if (*Iter1 == *Iter2)
560 // Loop through, intersecting as we go, erasing elements when necessary.
561 while (Iter2 != RHS.Elements.end()) {
562 if (Iter1 == Elements.end())
565 if ((*Iter1)->index() > (*Iter2)->index()) {
567 } else if ((*Iter1)->index() == (*Iter2)->index()) {
569 changed |= (*Iter1)->intersectWith(*(*Iter2), BecameZero);
571 ElementListIter IterTmp = Iter1;
573 Elements.erase(IterTmp);
580 ElementListIter IterTmp = Iter1;
583 Elements.erase(IterTmp);
586 CurrElementIter = Elements.begin();
590 // Intersect our bitmap with the complement of the RHS and return true if ours
592 bool intersectWithComplement(const SparseBitVector &RHS) {
593 bool changed = false;
594 ElementListIter Iter1 = Elements.begin();
595 ElementListConstIter Iter2 = RHS.Elements.begin();
597 // IE They may both be end.
601 // See if the first bitmap element is the same in both. This is only
602 // possible if they are the same bitmap.
603 if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
604 if (*Iter1 == *Iter2) {
609 // Loop through, intersecting as we go, erasing elements when necessary.
610 while (Iter2 != RHS.Elements.end()) {
611 if (Iter1 == Elements.end())
614 if ((*Iter1)->index() > (*Iter2)->index()) {
616 } else if ((*Iter1)->index() == (*Iter2)->index()) {
618 changed |= (*Iter1)->intersectWithComplement(*(*Iter2), BecameZero);
620 ElementListIter IterTmp = Iter1;
622 Elements.erase(IterTmp);
629 ElementListIter IterTmp = Iter1;
632 Elements.erase(IterTmp);
635 CurrElementIter = Elements.begin();
639 bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
640 return intersectWithComplement(*RHS);
644 bool intersects(const SparseBitVector<ElementSize> *RHS) const {
645 return intersects(*RHS);
648 // Return true if we share any bits in common with RHS
649 bool intersects(const SparseBitVector<ElementSize> &RHS) const {
650 ElementListConstIter Iter1 = Elements.begin();
651 ElementListConstIter Iter2 = RHS.Elements.begin();
653 // IE They may both be end.
657 // See if the first bitmap element is the same in both. This is only
658 // possible if they are the same bitmap.
659 if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
660 if (*Iter1 == *Iter2) {
664 // Loop through, intersecting stopping when we hit bits in common.
665 while (Iter2 != RHS.Elements.end()) {
666 if (Iter1 == Elements.end())
669 if ((*Iter1)->index() > (*Iter2)->index()) {
671 } else if ((*Iter1)->index() == (*Iter2)->index()) {
672 if ((*Iter1)->intersects(*(*Iter2)))
683 // Return the first set bit in the bitmap. Return -1 if no bits are set.
684 int find_first() const {
685 if (Elements.empty())
687 const SparseBitVectorElement<ElementSize> *First = *(Elements.begin());
688 return (First->index() * ElementSize) + First->find_first();
691 // Return true if the SparseBitVector is empty
693 return Elements.empty();
696 unsigned count() const {
697 unsigned BitCount = 0;
698 for (ElementListConstIter Iter = Elements.begin();
699 Iter != Elements.end();
701 BitCount += (*Iter)->count();
705 iterator begin() const {
706 return iterator(this);
709 iterator end() const {
710 return iterator(this, ~0);
714 // Convenience functions to allow Or and And without dereferencing in the user
716 template <unsigned ElementSize>
717 inline void operator |=(SparseBitVector<ElementSize> *LHS,
718 const SparseBitVector<ElementSize> &RHS) {
719 LHS->operator|=(RHS);
722 template <unsigned ElementSize>
723 inline void operator |=(SparseBitVector<ElementSize> *LHS,
724 const SparseBitVector<ElementSize> *RHS) {
725 LHS->operator|=(RHS);
728 template <unsigned ElementSize>
729 inline void operator &=(SparseBitVector<ElementSize> *LHS,
730 const SparseBitVector<ElementSize> &RHS) {
731 LHS->operator&=(RHS);
734 template <unsigned ElementSize>
735 inline void operator &=(SparseBitVector<ElementSize> *LHS,
736 const SparseBitVector<ElementSize> *RHS) {
737 LHS->operator&=(RHS);