LLVM 17.0.0git
SparseBitVector.h
Go to the documentation of this file.
1//===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector --*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
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
21#include <cassert>
22#include <climits>
23#include <cstring>
24#include <iterator>
25#include <list>
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
42template <unsigned ElementSize = 128> struct SparseBitVectorElement {
43public:
44 using BitWord = unsigned long;
46 enum {
47 BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
49 BITS_PER_ELEMENT = ElementSize
50 };
51
52private:
53 // Index of Element in terms of where first bit starts.
54 unsigned ElementIndex;
56
58 ElementIndex = ~0U;
59 memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
60 }
61
62public:
63 explicit SparseBitVectorElement(unsigned Idx) {
64 ElementIndex = Idx;
65 memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
66 }
67
68 // Comparison.
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
79 return !(*this == RHS);
80 }
81
82 // Return the bits that make up word Idx in our element.
83 BitWord word(unsigned Idx) const {
85 return Bits[Idx];
86 }
87
88 unsigned index() const {
89 return ElementIndex;
90 }
91
92 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
99 void set(unsigned Idx) {
100 Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
101 }
102
103 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
112 void reset(unsigned Idx) {
113 Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
114 }
115
116 bool test(unsigned Idx) const {
117 return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
118 }
119
120 size_type count() const {
121 unsigned NumBits = 0;
122 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
123 NumBits += llvm::popcount(Bits[i]);
124 return NumBits;
125 }
126
127 /// find_first - Returns the index of the first set bit.
128 int find_first() const {
129 for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
130 if (Bits[i] != 0)
131 return i * BITWORD_SIZE + llvm::countr_zero(Bits[i]);
132 llvm_unreachable("Illegal empty element");
133 }
134
135 /// find_last - Returns the index of the last set bit.
136 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 llvm::countl_zero(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.
148 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];
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 + llvm::countr_zero(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 + llvm::countr_zero(Bits[i]);
168 return -1;
169 }
170
171 // Union this element with RHS and return true if this one changed.
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
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.
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.
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
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
255template <unsigned ElementSize = 128>
257 using ElementList = std::list<SparseBitVectorElement<ElementSize>>;
258 using ElementListIter = typename ElementList::iterator;
259 using ElementListConstIter = typename ElementList::const_iterator;
260 enum {
262 };
263
264 ElementList Elements;
265 // Pointer to our current Element. This has no visible effect on the external
266 // state of a SparseBitVector, it's just used to improve performance in the
267 // common case of testing/modifying bits with similar indices.
268 mutable ElementListIter CurrElementIter;
269
270 // This is like std::lower_bound, except we do linear searching from the
271 // current position.
272 ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const {
273
274 // We cache a non-const iterator so we're forced to resort to const_cast to
275 // get the begin/end in the case where 'this' is const. To avoid duplication
276 // of code with the only difference being whether the const cast is present
277 // 'this' is always const in this particular function and we sort out the
278 // difference in FindLowerBound and FindLowerBoundConst.
279 ElementListIter Begin =
280 const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin();
281 ElementListIter End =
282 const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end();
283
284 if (Elements.empty()) {
285 CurrElementIter = Begin;
286 return CurrElementIter;
287 }
288
289 // Make sure our current iterator is valid.
290 if (CurrElementIter == End)
291 --CurrElementIter;
292
293 // Search from our current iterator, either backwards or forwards,
294 // depending on what element we are looking for.
295 ElementListIter ElementIter = CurrElementIter;
296 if (CurrElementIter->index() == ElementIndex) {
297 return ElementIter;
298 } else if (CurrElementIter->index() > ElementIndex) {
299 while (ElementIter != Begin
300 && ElementIter->index() > ElementIndex)
301 --ElementIter;
302 } else {
303 while (ElementIter != End &&
304 ElementIter->index() < ElementIndex)
305 ++ElementIter;
306 }
307 CurrElementIter = ElementIter;
308 return ElementIter;
309 }
310 ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const {
311 return FindLowerBoundImpl(ElementIndex);
312 }
313 ElementListIter FindLowerBound(unsigned ElementIndex) {
314 return FindLowerBoundImpl(ElementIndex);
315 }
316
317 // Iterator to walk set bits in the bitmap. This iterator is a lot uglier
318 // than it would be, in order to be efficient.
319 class SparseBitVectorIterator {
320 private:
321 bool AtEnd;
322
324
325 // Current element inside of bitmap.
326 ElementListConstIter Iter;
327
328 // Current bit number inside of our bitmap.
329 unsigned BitNumber;
330
331 // Current word number inside of our element.
332 unsigned WordNumber;
333
334 // Current bits from the element.
336
337 // Move our iterator to the first non-zero bit in the bitmap.
338 void AdvanceToFirstNonZero() {
339 if (AtEnd)
340 return;
341 if (BitVector->Elements.empty()) {
342 AtEnd = true;
343 return;
344 }
345 Iter = BitVector->Elements.begin();
346 BitNumber = Iter->index() * ElementSize;
347 unsigned BitPos = Iter->find_first();
348 BitNumber += BitPos;
349 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
350 Bits = Iter->word(WordNumber);
351 Bits >>= BitPos % BITWORD_SIZE;
352 }
353
354 // Move our iterator to the next non-zero bit.
355 void AdvanceToNextNonZero() {
356 if (AtEnd)
357 return;
358
359 while (Bits && !(Bits & 1)) {
360 Bits >>= 1;
361 BitNumber += 1;
362 }
363
364 // See if we ran out of Bits in this word.
365 if (!Bits) {
366 int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
367 // If we ran out of set bits in this element, move to next element.
368 if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
369 ++Iter;
370 WordNumber = 0;
371
372 // We may run out of elements in the bitmap.
373 if (Iter == BitVector->Elements.end()) {
374 AtEnd = true;
375 return;
376 }
377 // Set up for next non-zero word in bitmap.
378 BitNumber = Iter->index() * ElementSize;
379 NextSetBitNumber = Iter->find_first();
380 BitNumber += NextSetBitNumber;
381 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
382 Bits = Iter->word(WordNumber);
383 Bits >>= NextSetBitNumber % BITWORD_SIZE;
384 } else {
385 WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
386 Bits = Iter->word(WordNumber);
387 Bits >>= NextSetBitNumber % BITWORD_SIZE;
388 BitNumber = Iter->index() * ElementSize;
389 BitNumber += NextSetBitNumber;
390 }
391 }
392 }
393
394 public:
395 SparseBitVectorIterator() = default;
396
397 SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
398 bool end = false):BitVector(RHS) {
399 Iter = BitVector->Elements.begin();
400 BitNumber = 0;
401 Bits = 0;
402 WordNumber = ~0;
403 AtEnd = end;
404 AdvanceToFirstNonZero();
405 }
406
407 // Preincrement.
408 inline SparseBitVectorIterator& operator++() {
409 ++BitNumber;
410 Bits >>= 1;
411 AdvanceToNextNonZero();
412 return *this;
413 }
414
415 // Postincrement.
416 inline SparseBitVectorIterator operator++(int) {
417 SparseBitVectorIterator tmp = *this;
418 ++*this;
419 return tmp;
420 }
421
422 // Return the current set bit number.
423 unsigned operator*() const {
424 return BitNumber;
425 }
426
427 bool operator==(const SparseBitVectorIterator &RHS) const {
428 // If they are both at the end, ignore the rest of the fields.
429 if (AtEnd && RHS.AtEnd)
430 return true;
431 // Otherwise they are the same if they have the same bit number and
432 // bitmap.
433 return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
434 }
435
436 bool operator!=(const SparseBitVectorIterator &RHS) const {
437 return !(*this == RHS);
438 }
439 };
440
441public:
442 using iterator = SparseBitVectorIterator;
443
444 SparseBitVector() : Elements(), CurrElementIter(Elements.begin()) {}
445
447 : Elements(RHS.Elements), CurrElementIter(Elements.begin()) {}
449 : Elements(std::move(RHS.Elements)), CurrElementIter(Elements.begin()) {}
450
451 // Clear.
452 void clear() {
453 Elements.clear();
454 }
455
456 // Assignment
458 if (this == &RHS)
459 return *this;
460
461 Elements = RHS.Elements;
462 CurrElementIter = Elements.begin();
463 return *this;
464 }
466 Elements = std::move(RHS.Elements);
467 CurrElementIter = Elements.begin();
468 return *this;
469 }
470
471 // Test, Reset, and Set a bit in the bitmap.
472 bool test(unsigned Idx) const {
473 if (Elements.empty())
474 return false;
475
476 unsigned ElementIndex = Idx / ElementSize;
477 ElementListConstIter ElementIter = FindLowerBoundConst(ElementIndex);
478
479 // If we can't find an element that is supposed to contain this bit, there
480 // is nothing more to do.
481 if (ElementIter == Elements.end() ||
482 ElementIter->index() != ElementIndex)
483 return false;
484 return ElementIter->test(Idx % ElementSize);
485 }
486
487 void reset(unsigned Idx) {
488 if (Elements.empty())
489 return;
490
491 unsigned ElementIndex = Idx / ElementSize;
492 ElementListIter ElementIter = FindLowerBound(ElementIndex);
493
494 // If we can't find an element that is supposed to contain this bit, there
495 // is nothing more to do.
496 if (ElementIter == Elements.end() ||
497 ElementIter->index() != ElementIndex)
498 return;
499 ElementIter->reset(Idx % ElementSize);
500
501 // When the element is zeroed out, delete it.
502 if (ElementIter->empty()) {
503 ++CurrElementIter;
504 Elements.erase(ElementIter);
505 }
506 }
507
508 void set(unsigned Idx) {
509 unsigned ElementIndex = Idx / ElementSize;
510 ElementListIter ElementIter;
511 if (Elements.empty()) {
512 ElementIter = Elements.emplace(Elements.end(), ElementIndex);
513 } else {
514 ElementIter = FindLowerBound(ElementIndex);
515
516 if (ElementIter == Elements.end() ||
517 ElementIter->index() != ElementIndex) {
518 // We may have hit the beginning of our SparseBitVector, in which case,
519 // we may need to insert right after this element, which requires moving
520 // the current iterator forward one, because insert does insert before.
521 if (ElementIter != Elements.end() &&
522 ElementIter->index() < ElementIndex)
523 ++ElementIter;
524 ElementIter = Elements.emplace(ElementIter, ElementIndex);
525 }
526 }
527 CurrElementIter = ElementIter;
528
529 ElementIter->set(Idx % ElementSize);
530 }
531
532 bool test_and_set(unsigned Idx) {
533 bool old = test(Idx);
534 if (!old) {
535 set(Idx);
536 return true;
537 }
538 return false;
539 }
540
541 bool operator!=(const SparseBitVector &RHS) const {
542 return !(*this == RHS);
543 }
544
545 bool operator==(const SparseBitVector &RHS) const {
546 ElementListConstIter Iter1 = Elements.begin();
547 ElementListConstIter Iter2 = RHS.Elements.begin();
548
549 for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
550 ++Iter1, ++Iter2) {
551 if (*Iter1 != *Iter2)
552 return false;
553 }
554 return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
555 }
556
557 // Union our bitmap with the RHS and return true if we changed.
559 if (this == &RHS)
560 return false;
561
562 bool changed = false;
563 ElementListIter Iter1 = Elements.begin();
564 ElementListConstIter Iter2 = RHS.Elements.begin();
565
566 // If RHS is empty, we are done
567 if (RHS.Elements.empty())
568 return false;
569
570 while (Iter2 != RHS.Elements.end()) {
571 if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
572 Elements.insert(Iter1, *Iter2);
573 ++Iter2;
574 changed = true;
575 } else if (Iter1->index() == Iter2->index()) {
576 changed |= Iter1->unionWith(*Iter2);
577 ++Iter1;
578 ++Iter2;
579 } else {
580 ++Iter1;
581 }
582 }
583 CurrElementIter = Elements.begin();
584 return changed;
585 }
586
587 // Intersect our bitmap with the RHS and return true if ours changed.
589 if (this == &RHS)
590 return false;
591
592 bool changed = false;
593 ElementListIter Iter1 = Elements.begin();
594 ElementListConstIter Iter2 = RHS.Elements.begin();
595
596 // Check if both bitmaps are empty.
597 if (Elements.empty() && RHS.Elements.empty())
598 return false;
599
600 // Loop through, intersecting as we go, erasing elements when necessary.
601 while (Iter2 != RHS.Elements.end()) {
602 if (Iter1 == Elements.end()) {
603 CurrElementIter = Elements.begin();
604 return changed;
605 }
606
607 if (Iter1->index() > Iter2->index()) {
608 ++Iter2;
609 } else if (Iter1->index() == Iter2->index()) {
610 bool BecameZero;
611 changed |= Iter1->intersectWith(*Iter2, BecameZero);
612 if (BecameZero) {
613 ElementListIter IterTmp = Iter1;
614 ++Iter1;
615 Elements.erase(IterTmp);
616 } else {
617 ++Iter1;
618 }
619 ++Iter2;
620 } else {
621 ElementListIter IterTmp = Iter1;
622 ++Iter1;
623 Elements.erase(IterTmp);
624 changed = true;
625 }
626 }
627 if (Iter1 != Elements.end()) {
628 Elements.erase(Iter1, Elements.end());
629 changed = true;
630 }
631 CurrElementIter = Elements.begin();
632 return changed;
633 }
634
635 // Intersect our bitmap with the complement of the RHS and return true
636 // if ours changed.
638 if (this == &RHS) {
639 if (!empty()) {
640 clear();
641 return true;
642 }
643 return false;
644 }
645
646 bool changed = false;
647 ElementListIter Iter1 = Elements.begin();
648 ElementListConstIter Iter2 = RHS.Elements.begin();
649
650 // If either our bitmap or RHS is empty, we are done
651 if (Elements.empty() || RHS.Elements.empty())
652 return false;
653
654 // Loop through, intersecting as we go, erasing elements when necessary.
655 while (Iter2 != RHS.Elements.end()) {
656 if (Iter1 == Elements.end()) {
657 CurrElementIter = Elements.begin();
658 return changed;
659 }
660
661 if (Iter1->index() > Iter2->index()) {
662 ++Iter2;
663 } else if (Iter1->index() == Iter2->index()) {
664 bool BecameZero;
665 changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
666 if (BecameZero) {
667 ElementListIter IterTmp = Iter1;
668 ++Iter1;
669 Elements.erase(IterTmp);
670 } else {
671 ++Iter1;
672 }
673 ++Iter2;
674 } else {
675 ++Iter1;
676 }
677 }
678 CurrElementIter = Elements.begin();
679 return changed;
680 }
681
684 }
685
686 // Three argument version of intersectWithComplement.
687 // Result of RHS1 & ~RHS2 is stored into this bitmap.
690 {
691 if (this == &RHS1) {
693 return;
694 } else if (this == &RHS2) {
695 SparseBitVector RHS2Copy(RHS2);
696 intersectWithComplement(RHS1, RHS2Copy);
697 return;
698 }
699
700 Elements.clear();
701 CurrElementIter = Elements.begin();
702 ElementListConstIter Iter1 = RHS1.Elements.begin();
703 ElementListConstIter Iter2 = RHS2.Elements.begin();
704
705 // If RHS1 is empty, we are done
706 // If RHS2 is empty, we still have to copy RHS1
707 if (RHS1.Elements.empty())
708 return;
709
710 // Loop through, intersecting as we go, erasing elements when necessary.
711 while (Iter2 != RHS2.Elements.end()) {
712 if (Iter1 == RHS1.Elements.end())
713 return;
714
715 if (Iter1->index() > Iter2->index()) {
716 ++Iter2;
717 } else if (Iter1->index() == Iter2->index()) {
718 bool BecameZero = false;
719 Elements.emplace_back(Iter1->index());
720 Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
721 if (BecameZero)
722 Elements.pop_back();
723 ++Iter1;
724 ++Iter2;
725 } else {
726 Elements.push_back(*Iter1++);
727 }
728 }
729
730 // copy the remaining elements
731 std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements));
732 }
733
735 const SparseBitVector<ElementSize> *RHS2) {
736 intersectWithComplement(*RHS1, *RHS2);
737 }
738
740 return intersects(*RHS);
741 }
742
743 // Return true if we share any bits in common with RHS
745 ElementListConstIter Iter1 = Elements.begin();
746 ElementListConstIter Iter2 = RHS.Elements.begin();
747
748 // Check if both bitmaps are empty.
749 if (Elements.empty() && RHS.Elements.empty())
750 return false;
751
752 // Loop through, intersecting stopping when we hit bits in common.
753 while (Iter2 != RHS.Elements.end()) {
754 if (Iter1 == Elements.end())
755 return false;
756
757 if (Iter1->index() > Iter2->index()) {
758 ++Iter2;
759 } else if (Iter1->index() == Iter2->index()) {
760 if (Iter1->intersects(*Iter2))
761 return true;
762 ++Iter1;
763 ++Iter2;
764 } else {
765 ++Iter1;
766 }
767 }
768 return false;
769 }
770
771 // Return true iff all bits set in this SparseBitVector are
772 // also set in RHS.
774 SparseBitVector<ElementSize> Result(*this);
775 Result &= RHS;
776 return (Result == RHS);
777 }
778
779 // Return the first set bit in the bitmap. Return -1 if no bits are set.
780 int find_first() const {
781 if (Elements.empty())
782 return -1;
783 const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
784 return (First.index() * ElementSize) + First.find_first();
785 }
786
787 // Return the last set bit in the bitmap. Return -1 if no bits are set.
788 int find_last() const {
789 if (Elements.empty())
790 return -1;
791 const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
792 return (Last.index() * ElementSize) + Last.find_last();
793 }
794
795 // Return true if the SparseBitVector is empty
796 bool empty() const {
797 return Elements.empty();
798 }
799
800 unsigned count() const {
801 unsigned BitCount = 0;
802 for (ElementListConstIter Iter = Elements.begin();
803 Iter != Elements.end();
804 ++Iter)
805 BitCount += Iter->count();
806
807 return BitCount;
808 }
809
810 iterator begin() const {
811 return iterator(this);
812 }
813
814 iterator end() const {
815 return iterator(this, true);
816 }
817};
818
819// Convenience functions to allow Or and And without dereferencing in the user
820// code.
821
822template <unsigned ElementSize>
825 return LHS |= *RHS;
826}
827
828template <unsigned ElementSize>
831 return LHS->operator|=(RHS);
832}
833
834template <unsigned ElementSize>
837 return LHS->operator&=(RHS);
838}
839
840template <unsigned ElementSize>
843 return LHS &= *RHS;
844}
845
846// Convenience functions for infix union, intersection, difference operators.
847
848template <unsigned ElementSize>
849inline SparseBitVector<ElementSize>
853 Result |= RHS;
854 return Result;
855}
856
857template <unsigned ElementSize>
858inline SparseBitVector<ElementSize>
862 Result &= RHS;
863 return Result;
864}
865
866template <unsigned ElementSize>
867inline SparseBitVector<ElementSize>
871 Result.intersectWithComplement(LHS, RHS);
872 return Result;
873}
874
875// Dump a SparseBitVector to a stream
876template <unsigned ElementSize>
878 out << "[";
879
880 typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
881 be = LHS.end();
882 if (bi != be) {
883 out << *bi;
884 for (++bi; bi != be; ++bi) {
885 out << " " << *bi;
886 }
887 }
888 out << "]\n";
889}
890
891} // end namespace llvm
892
893#endif // LLVM_ADT_SPARSEBITVECTOR_H
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define I(x, y, z)
Definition: MD5.cpp:58
modulo schedule test
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Value * LHS
bool empty() const
empty - Tests whether there are no bits in this bitvector.
Definition: BitVector.h:149
bool operator!=(const SparseBitVector &RHS) const
bool intersects(const SparseBitVector< ElementSize > &RHS) const
bool operator==(const SparseBitVector &RHS) const
SparseBitVector & operator=(const SparseBitVector &RHS)
iterator begin() const
void set(unsigned Idx)
unsigned count() const
bool test_and_set(unsigned Idx)
void intersectWithComplement(const SparseBitVector< ElementSize > *RHS1, const SparseBitVector< ElementSize > *RHS2)
bool contains(const SparseBitVector< ElementSize > &RHS) const
void intersectWithComplement(const SparseBitVector< ElementSize > &RHS1, const SparseBitVector< ElementSize > &RHS2)
SparseBitVector(const SparseBitVector &RHS)
bool operator|=(const SparseBitVector &RHS)
iterator end() const
bool test(unsigned Idx) const
void reset(unsigned Idx)
bool operator&=(const SparseBitVector &RHS)
SparseBitVector & operator=(SparseBitVector &&RHS)
bool intersectWithComplement(const SparseBitVector< ElementSize > *RHS) const
bool intersectWithComplement(const SparseBitVector &RHS)
bool intersects(const SparseBitVector< ElementSize > *RHS) const
SparseBitVectorIterator iterator
SparseBitVector(SparseBitVector &&RHS)
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
int popcount(T Value) noexcept
Count the number of set bits in a value.
Definition: bit.h:349
APInt operator&(APInt a, const APInt &b)
Definition: APInt.h:2050
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2162
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2040
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Definition: bit.h:179
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
Definition: bit.h:245
bool operator&=(SparseBitVector< ElementSize > *LHS, const SparseBitVector< ElementSize > &RHS)
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1862
APInt operator-(APInt)
Definition: APInt.h:2115
bool operator|=(SparseBitVector< ElementSize > &LHS, const SparseBitVector< ElementSize > *RHS)
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:2070
Definition: BitVector.h:851
SparseBitVector is an implementation of a bitvector that is sparse by only storing the elements that ...
bool operator==(const SparseBitVectorElement &RHS) const
int find_next(unsigned Curr) const
find_next - Returns the index of the next set bit starting from the "Curr" bit.
bool unionWith(const SparseBitVectorElement &RHS)
int find_last() const
find_last - Returns the index of the last set bit.
SparseBitVectorElement(unsigned Idx)
void intersectWithComplement(const SparseBitVectorElement &RHS1, const SparseBitVectorElement &RHS2, bool &BecameZero)
bool intersectWith(const SparseBitVectorElement &RHS, bool &BecameZero)
bool operator!=(const SparseBitVectorElement &RHS) const
bool test_and_set(unsigned Idx)
BitWord word(unsigned Idx) const
bool test(unsigned Idx) const
bool intersectWithComplement(const SparseBitVectorElement &RHS, bool &BecameZero)
int find_first() const
find_first - Returns the index of the first set bit.
bool intersects(const SparseBitVectorElement &RHS) const