15 #ifndef LLVM_ADT_SPARSEBITVECTOR_H
16 #define LLVM_ADT_SPARSEBITVECTOR_H
54 unsigned ElementIndex;
70 if (ElementIndex !=
RHS.ElementIndex)
73 if (Bits[
i] !=
RHS.Bits[
i])
79 return !(*
this ==
RHS);
99 void set(
unsigned Idx) {
116 bool test(
unsigned Idx)
const {
121 unsigned NumBits = 0;
156 &&
"Word Position outside of element");
159 Copy &= ~0UL << BitPos;
173 bool changed =
false;
177 Bits[
i] |=
RHS.Bits[
i];
178 if (!changed &&
old != Bits[
i])
187 if (
RHS.Bits[
i] & Bits[
i])
197 bool changed =
false;
204 Bits[
i] &=
RHS.Bits[
i];
208 if (!changed &&
old != Bits[
i])
211 BecameZero = allzero;
220 bool changed =
false;
227 Bits[
i] &= ~
RHS.Bits[
i];
231 if (!changed &&
old != Bits[
i])
234 BecameZero = allzero;
247 Bits[
i] = RHS1.Bits[
i] & ~RHS2.Bits[
i];
251 BecameZero = allzero;
255 template <
unsigned ElementSize = 128>
257 using ElementList = std::list<SparseBitVectorElement<ElementSize>>;
258 using ElementListIter =
typename ElementList::iterator;
259 using ElementListConstIter =
typename ElementList::const_iterator;
264 ElementList Elements;
268 mutable ElementListIter CurrElementIter;
272 ElementListIter FindLowerBoundImpl(
unsigned ElementIndex)
const {
279 ElementListIter Begin =
281 ElementListIter End =
284 if (Elements.empty()) {
285 CurrElementIter = Begin;
286 return CurrElementIter;
290 if (CurrElementIter == End)
295 ElementListIter ElementIter = CurrElementIter;
296 if (CurrElementIter->index() == ElementIndex) {
298 }
else if (CurrElementIter->index() > ElementIndex) {
299 while (ElementIter != Begin
300 && ElementIter->index() > ElementIndex)
303 while (ElementIter != End &&
304 ElementIter->index() < ElementIndex)
307 CurrElementIter = ElementIter;
310 ElementListConstIter FindLowerBoundConst(
unsigned ElementIndex)
const {
311 return FindLowerBoundImpl(ElementIndex);
313 ElementListIter FindLowerBound(
unsigned ElementIndex) {
314 return FindLowerBoundImpl(ElementIndex);
319 class SparseBitVectorIterator {
326 ElementListConstIter Iter;
338 void AdvanceToFirstNonZero() {
346 BitNumber = Iter->index() * ElementSize;
349 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
350 Bits = Iter->word(WordNumber);
351 Bits >>= BitPos % BITWORD_SIZE;
355 void AdvanceToNextNonZero() {
366 int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
368 if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
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;
385 WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
386 Bits = Iter->word(WordNumber);
387 Bits >>= NextSetBitNumber % BITWORD_SIZE;
388 BitNumber = Iter->index() * ElementSize;
389 BitNumber += NextSetBitNumber;
395 SparseBitVectorIterator() =
default;
404 AdvanceToFirstNonZero();
408 inline SparseBitVectorIterator& operator++() {
411 AdvanceToNextNonZero();
416 inline SparseBitVectorIterator operator++(
int) {
417 SparseBitVectorIterator
tmp = *
this;
429 if (AtEnd &&
RHS.AtEnd)
433 return AtEnd ==
RHS.AtEnd &&
RHS.BitNumber == BitNumber;
437 return !(*
this ==
RHS);
447 : Elements(
RHS.Elements), CurrElementIter(Elements.
begin()) {}
449 : Elements(
std::
move(
RHS.Elements)), CurrElementIter(Elements.
begin()) {}
461 Elements =
RHS.Elements;
462 CurrElementIter = Elements.begin();
467 CurrElementIter = Elements.begin();
472 bool test(
unsigned Idx)
const {
473 if (Elements.empty())
476 unsigned ElementIndex = Idx / ElementSize;
477 ElementListConstIter ElementIter = FindLowerBoundConst(ElementIndex);
481 if (ElementIter == Elements.end() ||
482 ElementIter->index() != ElementIndex)
484 return ElementIter->test(Idx % ElementSize);
488 if (Elements.empty())
491 unsigned ElementIndex = Idx / ElementSize;
492 ElementListIter ElementIter = FindLowerBound(ElementIndex);
496 if (ElementIter == Elements.end() ||
497 ElementIter->index() != ElementIndex)
499 ElementIter->reset(Idx % ElementSize);
502 if (ElementIter->empty()) {
504 Elements.erase(ElementIter);
509 unsigned ElementIndex = Idx / ElementSize;
510 ElementListIter ElementIter;
511 if (Elements.empty()) {
512 ElementIter = Elements.emplace(Elements.end(), ElementIndex);
514 ElementIter = FindLowerBound(ElementIndex);
516 if (ElementIter == Elements.end() ||
517 ElementIter->index() != ElementIndex) {
521 if (ElementIter != Elements.end() &&
522 ElementIter->index() < ElementIndex)
524 ElementIter = Elements.emplace(ElementIter, ElementIndex);
527 CurrElementIter = ElementIter;
529 ElementIter->set(Idx % ElementSize);
542 return !(*
this ==
RHS);
546 ElementListConstIter Iter1 = Elements.begin();
547 ElementListConstIter Iter2 =
RHS.Elements.begin();
549 for (; Iter1 != Elements.end() && Iter2 !=
RHS.Elements.end();
551 if (*Iter1 != *Iter2)
554 return Iter1 == Elements.end() && Iter2 ==
RHS.Elements.end();
562 bool changed =
false;
563 ElementListIter Iter1 = Elements.begin();
564 ElementListConstIter Iter2 =
RHS.Elements.begin();
567 if (
RHS.Elements.empty())
570 while (Iter2 !=
RHS.Elements.end()) {
571 if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
572 Elements.insert(Iter1, *Iter2);
575 }
else if (Iter1->index() == Iter2->index()) {
576 changed |= Iter1->unionWith(*Iter2);
583 CurrElementIter = Elements.begin();
592 bool changed =
false;
593 ElementListIter Iter1 = Elements.begin();
594 ElementListConstIter Iter2 =
RHS.Elements.begin();
597 if (Elements.empty() &&
RHS.Elements.empty())
601 while (Iter2 !=
RHS.Elements.end()) {
602 if (Iter1 == Elements.end()) {
603 CurrElementIter = Elements.begin();
607 if (Iter1->index() > Iter2->index()) {
609 }
else if (Iter1->index() == Iter2->index()) {
611 changed |= Iter1->intersectWith(*Iter2, BecameZero);
613 ElementListIter IterTmp = Iter1;
615 Elements.erase(IterTmp);
621 ElementListIter IterTmp = Iter1;
623 Elements.erase(IterTmp);
627 if (Iter1 != Elements.end()) {
628 Elements.erase(Iter1, Elements.end());
631 CurrElementIter = Elements.begin();
646 bool changed =
false;
647 ElementListIter Iter1 = Elements.begin();
648 ElementListConstIter Iter2 =
RHS.Elements.begin();
651 if (Elements.empty() ||
RHS.Elements.empty())
655 while (Iter2 !=
RHS.Elements.end()) {
656 if (Iter1 == Elements.end()) {
657 CurrElementIter = Elements.begin();
661 if (Iter1->index() > Iter2->index()) {
663 }
else if (Iter1->index() == Iter2->index()) {
665 changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
667 ElementListIter IterTmp = Iter1;
669 Elements.erase(IterTmp);
678 CurrElementIter = Elements.begin();
694 }
else if (
this == &RHS2) {
701 CurrElementIter = Elements.begin();
702 ElementListConstIter Iter1 = RHS1.Elements.begin();
703 ElementListConstIter Iter2 = RHS2.Elements.begin();
707 if (RHS1.Elements.empty())
711 while (Iter2 != RHS2.Elements.end()) {
712 if (Iter1 == RHS1.Elements.end())
715 if (Iter1->index() > Iter2->index()) {
717 }
else if (Iter1->index() == Iter2->index()) {
718 bool BecameZero =
false;
719 Elements.emplace_back(Iter1->index());
720 Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
726 Elements.push_back(*Iter1++);
731 std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements));
745 ElementListConstIter Iter1 = Elements.begin();
746 ElementListConstIter Iter2 =
RHS.Elements.begin();
749 if (Elements.empty() &&
RHS.Elements.empty())
753 while (Iter2 !=
RHS.Elements.end()) {
754 if (Iter1 == Elements.end())
757 if (Iter1->index() > Iter2->index()) {
759 }
else if (Iter1->index() == Iter2->index()) {
760 if (Iter1->intersects(*Iter2))
776 return (Result ==
RHS);
781 if (Elements.empty())
784 return (
First.index() * ElementSize) +
First.find_first();
789 if (Elements.empty())
792 return (
Last.index() * ElementSize) +
Last.find_last();
797 return Elements.empty();
801 unsigned BitCount = 0;
802 for (ElementListConstIter Iter = Elements.begin();
803 Iter != Elements.end();
805 BitCount += Iter->count();
822 template <
unsigned ElementSize>
828 template <
unsigned ElementSize>
831 return LHS->operator|=(
RHS);
834 template <
unsigned ElementSize>
837 return LHS->operator&=(
RHS);
840 template <
unsigned ElementSize>
848 template <
unsigned ElementSize>
849 inline SparseBitVector<ElementSize>
857 template <
unsigned ElementSize>
858 inline SparseBitVector<ElementSize>
866 template <
unsigned ElementSize>
867 inline SparseBitVector<ElementSize>
871 Result.intersectWithComplement(
LHS,
RHS);
876 template <
unsigned ElementSize>
884 for (++bi; bi !=
be; ++bi) {
893 #endif // LLVM_ADT_SPARSEBITVECTOR_H