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 // Intersect this Element with RHS and return true if this one changed.
199 // BecameZero is set to true if this element became all-zero bits.
200 bool intersectWith(const SparseBitVectorElement &RHS,
202 bool changed = false;
206 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
207 BitWord old = changed ? 0 : Bits[i];
209 Bits[i] &= RHS.Bits[i];
216 BecameZero = !allzero;
221 template <unsigned ElementSize = 128>
222 class SparseBitVector {
223 typedef std::list<SparseBitVectorElement<ElementSize> *> ElementList;
224 typedef typename ElementList::iterator ElementListIter;
225 typedef typename ElementList::const_iterator ElementListConstIter;
227 BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
230 // Pointer to our current Element.
231 ElementListIter CurrElementIter;
232 ElementList Elements;
234 // This is like std::lower_bound, except we do linear searching from the
236 ElementListIter FindLowerBound(unsigned ElementIndex) {
238 if (Elements.empty()) {
239 CurrElementIter = Elements.begin();
240 return Elements.begin();
243 // Make sure our current iterator is valid.
244 if (CurrElementIter == Elements.end())
247 // Search from our current iterator, either backwards or forwards,
248 // depending on what element we are looking for.
249 ElementListIter ElementIter = CurrElementIter;
250 if ((*CurrElementIter)->index() == ElementIndex) {
252 } else if ((*CurrElementIter)->index() > ElementIndex) {
253 while (ElementIter != Elements.begin()
254 && (*ElementIter)->index() > ElementIndex)
257 while (ElementIter != Elements.end() &&
258 (*ElementIter)->index() <= ElementIndex)
262 CurrElementIter = ElementIter;
266 // Iterator to walk set bits in the bitmap. This iterator is a lot uglier
267 // than it would be, in order to be efficient.
268 struct SparseBitVectorIterator {
272 SparseBitVector<ElementSize> &BitVector;
274 // Current element inside of bitmap.
275 ElementListConstIter Iter;
277 // Current bit number inside of our bitmap.
280 // Current word number inside of our element.
283 // Current bits from the element.
284 typename SparseBitVectorElement<ElementSize>::BitWord Bits;
286 // Move our iterator to the first non-zero bit in the bitmap.
287 void AdvanceToFirstNonZero() {
290 if (BitVector.Elements.empty()) {
294 Iter = BitVector.Elements.begin();
295 BitNumber = (*Iter)->index() * ElementSize;
296 unsigned BitPos = (*Iter)->find_first();
298 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
299 Bits = (*Iter)->word(WordNumber);
300 Bits >>= BitPos % BITWORD_SIZE;
303 // Move our iterator to the next non-zero bit.
304 void AdvanceToNextNonZero() {
308 while (Bits && !(Bits & 1)) {
313 // See if we ran out of Bits in this word.
315 int NextSetBitNumber = (*Iter)->find_next(BitNumber % ElementSize) ;
316 // If we ran out of set bits in this element, move to next element.
317 if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
321 // We may run out of elements in the bitmap.
322 if (Iter == BitVector.Elements.end()) {
326 // Set up for next non zero word in bitmap.
327 BitNumber = (*Iter)->index() * ElementSize;
328 NextSetBitNumber = (*Iter)->find_first();
329 BitNumber += NextSetBitNumber;
330 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
331 Bits = (*Iter)->word(WordNumber);
332 Bits >>= NextSetBitNumber % BITWORD_SIZE;
334 WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
335 Bits = (*Iter)->word(WordNumber);
336 Bits >>= NextSetBitNumber % BITWORD_SIZE;
342 inline SparseBitVectorIterator& operator++() {
345 AdvanceToNextNonZero();
350 inline SparseBitVectorIterator operator++(int) {
351 SparseBitVectorIterator tmp = *this;
356 // Return the current set bit number.
357 unsigned operator*() const {
361 bool operator==(const SparseBitVectorIterator &RHS) const {
362 // If they are both at the end, ignore the rest of the fields.
363 if (AtEnd == RHS.AtEnd)
365 // Otherwise they are the same if they have the same bit number and
367 return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
369 bool operator!=(const SparseBitVectorIterator &RHS) const {
370 return !(*this == RHS);
373 explicit SparseBitVectorIterator(SparseBitVector<ElementSize> &RHS,
374 bool end = false):BitVector(RHS) {
375 Iter = BitVector.Elements.begin();
380 AdvanceToFirstNonZero();
384 typedef SparseBitVectorIterator iterator;
385 typedef const SparseBitVectorIterator const_iterator;
388 CurrElementIter = Elements.begin ();
392 for_each(Elements.begin(), Elements.end(),
393 deleter<SparseBitVectorElement<ElementSize> >);
396 // SparseBitVector copy ctor.
397 SparseBitVector(const SparseBitVector &RHS) {
398 ElementListConstIter ElementIter = RHS.Elements.begin();
399 while (ElementIter != RHS.Elements.end()) {
400 SparseBitVectorElement<ElementSize> *ElementCopy;
401 ElementCopy = new SparseBitVectorElement<ElementSize>(*(*ElementIter));
402 Elements.push_back(ElementCopy);
405 CurrElementIter = Elements.begin ();
408 // Test, Reset, and Set a bit in the bitmap.
409 bool test(unsigned Idx) {
410 if (Elements.empty())
413 unsigned ElementIndex = Idx / ElementSize;
414 ElementListIter ElementIter = FindLowerBound(ElementIndex);
416 // If we can't find an element that is supposed to contain this bit, there
417 // is nothing more to do.
418 if (ElementIter == Elements.end() ||
419 (*ElementIter)->index() != ElementIndex)
421 return (*ElementIter)->test(Idx % ElementSize);
424 void reset(unsigned Idx) {
425 if (Elements.empty())
428 unsigned ElementIndex = Idx / ElementSize;
429 ElementListIter ElementIter = FindLowerBound(ElementIndex);
431 // If we can't find an element that is supposed to contain this bit, there
432 // is nothing more to do.
433 if (ElementIter == Elements.end() ||
434 (*ElementIter)->index() != ElementIndex)
436 (*ElementIter)->reset(Idx % ElementSize);
438 // When the element is zeroed out, delete it.
439 if ((*ElementIter)->empty()) {
440 delete (*ElementIter);
442 Elements.erase(ElementIter);
446 void set(unsigned Idx) {
447 SparseBitVectorElement<ElementSize> *Element;
448 unsigned ElementIndex = Idx / ElementSize;
450 if (Elements.empty()) {
451 Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
452 Elements.push_back(Element);
454 ElementListIter ElementIter = FindLowerBound(ElementIndex);
456 if (ElementIter != Elements.end() &&
457 (*ElementIter)->index() == ElementIndex)
458 Element = *ElementIter;
460 Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
461 // Insert does insert before, and lower bound gives the one before.
462 Elements.insert(++ElementIter, Element);
465 Element->set(Idx % ElementSize);
468 // Union our bitmap with the RHS and return true if we changed.
469 bool operator|=(const SparseBitVector &RHS) {
470 bool changed = false;
471 ElementListIter Iter1 = Elements.begin();
472 ElementListConstIter Iter2 = RHS.Elements.begin();
474 // IE They may both be end
478 // See if the first bitmap element is the same in both. This is only
479 // possible if they are the same bitmap.
480 if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
481 if (*Iter1 == *Iter2)
484 while (Iter2 != RHS.Elements.end()) {
485 if (Iter1 == Elements.end() || (*Iter1)->index() > (*Iter2)->index()) {
486 SparseBitVectorElement<ElementSize> *NewElem;
488 NewElem = new SparseBitVectorElement<ElementSize>(*(*Iter2));
489 Elements.insert(Iter1, NewElem);
492 } else if ((*Iter1)->index() == (*Iter2)->index()) {
493 changed |= (*Iter1)->unionWith(*(*Iter2));
500 CurrElementIter = Elements.begin();
504 // Intersect our bitmap with the RHS and return true if ours changed.
505 bool operator&=(const SparseBitVector &RHS) {
506 bool changed = false;
507 ElementListIter Iter1 = Elements.begin();
508 ElementListConstIter Iter2 = RHS.Elements.begin();
510 // IE They may both be end.
514 // See if the first bitmap element is the same in both. This is only
515 // possible if they are the same bitmap.
516 if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
517 if (*Iter1 == *Iter2)
520 // Loop through, intersecting as we go, erasing elements when necessary.
521 while (Iter2 != RHS.Elements.end()) {
522 if (Iter1 == Elements.end())
525 if ((*Iter1)->index() > (*Iter2)->index()) {
527 } else if ((*Iter1)->index() == (*Iter2)->index()) {
529 changed |= (*Iter1)->intersectWith(*(*Iter2), BecameZero);
531 ElementListIter IterTmp = Iter1;
533 Elements.erase(IterTmp);
540 ElementListIter IterTmp = Iter1;
543 Elements.erase(IterTmp);
546 CurrElementIter = Elements.begin();
550 iterator begin() const {
551 return iterator(*this);
554 iterator end() const {
555 return iterator(*this, ~0);