15 #ifndef LLVM_ADT_SPARSEBITVECTOR_H
16 #define LLVM_ADT_SPARSEBITVECTOR_H
20 #include "llvm/Support/DataTypes.h"
43 template <
unsigned ElementSize = 128>
45 :
public ilist_node<SparseBitVectorElement<ElementSize> > {
56 unsigned ElementIndex;
73 if (ElementIndex != RHS.ElementIndex)
76 if (
Bits[i] != RHS.Bits[i])
82 return !(*
this == RHS);
107 bool old =
test(Idx);
119 bool test(
unsigned Idx)
const {
124 unsigned NumBits = 0;
158 &&
"Word Position outside of element");
161 Copy &= ~0UL << BitPos;
185 bool changed =
false;
189 Bits[i] |= RHS.Bits[i];
190 if (!changed && old !=
Bits[i])
199 if (RHS.Bits[i] &
Bits[i])
209 bool changed =
false;
216 Bits[i] &= RHS.Bits[i];
220 if (!changed && old !=
Bits[i])
223 BecameZero = allzero;
231 bool changed =
false;
238 Bits[i] &= ~RHS.Bits[i];
242 if (!changed && old !=
Bits[i])
245 BecameZero = allzero;
257 Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
261 BecameZero = allzero;
265 template <
unsigned ElementSize>
281 template <
unsigned ElementSize = 128>
291 ElementListIter CurrElementIter;
296 ElementListIter FindLowerBound(
unsigned ElementIndex) {
298 if (Elements.
empty()) {
299 CurrElementIter = Elements.
begin();
300 return Elements.
begin();
304 if (CurrElementIter == Elements.
end())
309 ElementListIter ElementIter = CurrElementIter;
310 if (CurrElementIter->index() == ElementIndex) {
312 }
else if (CurrElementIter->index() > ElementIndex) {
313 while (ElementIter != Elements.
begin()
314 && ElementIter->index() > ElementIndex)
317 while (ElementIter != Elements.
end() &&
318 ElementIter->index() < ElementIndex)
321 CurrElementIter = ElementIter;
327 class SparseBitVectorIterator {
346 void AdvanceToFirstNonZero() {
354 BitNumber = Iter->index() * ElementSize;
357 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
358 Bits = Iter->word(WordNumber);
359 Bits >>= BitPos % BITWORD_SIZE;
363 void AdvanceToNextNonZero() {
374 int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
376 if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
386 BitNumber = Iter->index() * ElementSize;
387 NextSetBitNumber = Iter->find_first();
388 BitNumber += NextSetBitNumber;
389 WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
390 Bits = Iter->word(WordNumber);
391 Bits >>= NextSetBitNumber % BITWORD_SIZE;
393 WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
394 Bits = Iter->word(WordNumber);
395 Bits >>= NextSetBitNumber % BITWORD_SIZE;
396 BitNumber = Iter->index() * ElementSize;
397 BitNumber += NextSetBitNumber;
403 inline SparseBitVectorIterator& operator++() {
406 AdvanceToNextNonZero();
411 inline SparseBitVectorIterator operator++(
int) {
412 SparseBitVectorIterator tmp = *
this;
418 unsigned operator*()
const {
422 bool operator==(
const SparseBitVectorIterator &RHS)
const {
424 if (AtEnd && RHS.AtEnd)
428 return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
430 bool operator!=(
const SparseBitVectorIterator &RHS)
const {
431 return !(*
this == RHS);
433 SparseBitVectorIterator():
BitVector(NULL) {
444 AdvanceToFirstNonZero();
451 CurrElementIter = Elements.
begin ();
460 while (ElementIter != RHS.Elements.
end()) {
465 CurrElementIter = Elements.
begin ();
478 while (ElementIter != RHS.Elements.
end()) {
483 CurrElementIter = Elements.
begin ();
490 if (Elements.
empty())
493 unsigned ElementIndex = Idx / ElementSize;
494 ElementListIter ElementIter = FindLowerBound(ElementIndex);
498 if (ElementIter == Elements.
end() ||
499 ElementIter->index() != ElementIndex)
501 return ElementIter->test(Idx % ElementSize);
505 if (Elements.
empty())
508 unsigned ElementIndex = Idx / ElementSize;
509 ElementListIter ElementIter = FindLowerBound(ElementIndex);
513 if (ElementIter == Elements.
end() ||
514 ElementIter->index() != ElementIndex)
516 ElementIter->reset(Idx % ElementSize);
519 if (ElementIter->empty()) {
521 Elements.
erase(ElementIter);
526 unsigned ElementIndex = Idx / ElementSize;
528 ElementListIter ElementIter;
529 if (Elements.
empty()) {
531 ElementIter = Elements.
insert(Elements.
end(), Element);
534 ElementIter = FindLowerBound(ElementIndex);
536 if (ElementIter == Elements.
end() ||
537 ElementIter->index() != ElementIndex) {
542 if (ElementIter != Elements.
end() &&
543 ElementIter->index() < ElementIndex)
544 ElementIter = Elements.
insert(++ElementIter, Element);
546 ElementIter = Elements.
insert(ElementIter, Element);
549 CurrElementIter = ElementIter;
551 ElementIter->set(Idx % ElementSize);
555 bool old =
test(Idx);
564 return !(*
this == RHS);
571 for (; Iter1 != Elements.
end() && Iter2 != RHS.Elements.
end();
573 if (*Iter1 != *Iter2)
576 return Iter1 == Elements.
end() && Iter2 == RHS.Elements.
end();
581 bool changed =
false;
582 ElementListIter Iter1 = Elements.
begin();
586 if (RHS.Elements.
empty())
589 while (Iter2 != RHS.Elements.
end()) {
590 if (Iter1 == Elements.
end() || Iter1->index() > Iter2->index()) {
595 }
else if (Iter1->index() == Iter2->index()) {
596 changed |= Iter1->unionWith(*Iter2);
603 CurrElementIter = Elements.
begin();
609 bool changed =
false;
610 ElementListIter Iter1 = Elements.
begin();
618 while (Iter2 != RHS.Elements.
end()) {
619 if (Iter1 == Elements.
end()) {
620 CurrElementIter = Elements.
begin();
624 if (Iter1->index() > Iter2->index()) {
626 }
else if (Iter1->index() == Iter2->index()) {
628 changed |= Iter1->intersectWith(*Iter2, BecameZero);
630 ElementListIter IterTmp = Iter1;
632 Elements.
erase(IterTmp);
638 ElementListIter IterTmp = Iter1;
640 Elements.
erase(IterTmp);
643 Elements.
erase(Iter1, Elements.
end());
644 CurrElementIter = Elements.
begin();
651 bool changed =
false;
652 ElementListIter Iter1 = Elements.
begin();
660 while (Iter2 != RHS.Elements.
end()) {
661 if (Iter1 == Elements.
end()) {
662 CurrElementIter = Elements.
begin();
666 if (Iter1->index() > Iter2->index()) {
668 }
else if (Iter1->index() == Iter2->index()) {
670 changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
672 ElementListIter IterTmp = Iter1;
674 Elements.
erase(IterTmp);
683 CurrElementIter = Elements.
begin();
698 CurrElementIter = Elements.
begin();
704 if (RHS1.Elements.
empty())
708 while (Iter2 != RHS2.Elements.
end()) {
709 if (Iter1 == RHS1.Elements.
end())
712 if (Iter1->index() > Iter2->index()) {
714 }
else if (Iter1->index() == Iter2->index()) {
715 bool BecameZero =
false;
735 while (Iter1 != RHS1.Elements.
end()) {
764 while (Iter2 != RHS.Elements.
end()) {
765 if (Iter1 == Elements.
end())
768 if (Iter1->index() > Iter2->index()) {
770 }
else if (Iter1->index() == Iter2->index()) {
771 if (Iter1->intersects(*Iter2))
787 return (Result == RHS);
792 if (Elements.
empty())
800 return Elements.
empty();
804 unsigned BitCount = 0;
806 Iter != Elements.
end();
808 BitCount += Iter->count();
824 template <
unsigned ElementSize>
830 template <
unsigned ElementSize>
833 return LHS->operator|=(RHS);
836 template <
unsigned ElementSize>
839 return LHS->operator&=(RHS);
842 template <
unsigned ElementSize>
850 template <
unsigned ElementSize>
851 inline SparseBitVector<ElementSize>
859 template <
unsigned ElementSize>
860 inline SparseBitVector<ElementSize>
868 template <
unsigned ElementSize>
869 inline SparseBitVector<ElementSize>
881 template <
unsigned ElementSize>
889 for (++bi; bi != be; ++bi) {
void operator-(int, ilist_iterator< T >) LLVM_DELETED_FUNCTION
iplist< SparseBitVectorElement< ElementSize > >::iterator iterator
SparseBitVector & operator=(const SparseBitVector &RHS)
Element * createSentinel() const
void intersectWithComplement(const SparseBitVector< ElementSize > &RHS1, const SparseBitVector< ElementSize > &RHS2)
SmallBitVector operator&(const SmallBitVector &LHS, const SmallBitVector &RHS)
bool intersects(const SparseBitVector< ElementSize > &RHS) const
bool intersectWithComplement(const SparseBitVector< ElementSize > *RHS) const
bool test(unsigned Idx) const
bool operator!=(const SparseBitVector &RHS) const
SparseBitVectorElement(unsigned Idx)
bool unionWith(const SparseBitVectorElement &RHS)
bool operator|=(const SparseBitVector &RHS)
bool operator!=(const SparseBitVectorElement &RHS) const
bool intersectWithComplement(const SparseBitVectorElement &RHS, bool &BecameZero)
int find_first() const
find_first - Returns the index of the first set bit.
#define llvm_unreachable(msg)
void intersectWithComplement(const SparseBitVector< ElementSize > *RHS1, const SparseBitVector< ElementSize > *RHS2)
SmallBitVector operator|(const SmallBitVector &LHS, const SmallBitVector &RHS)
Element * ensureHead(Element *) const
enable_if_c< std::numeric_limits< T >::is_integer &&!std::numeric_limits< T >::is_signed, std::size_t >::type countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the least significant bit to the most stopping at the first 1...
bool operator|=(SparseBitVector< ElementSize > &LHS, const SparseBitVector< ElementSize > *RHS)
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool test_and_set(unsigned Idx)
bool operator&=(const SparseBitVector &RHS)
bool empty() const
empty - Tests whether there are no bits in this bitvector.
iterator insert(iterator where, const NodeTy &val)
static void destroySentinel(Element *)
bool operator==(const SparseBitVector &RHS) const
unsigned CountPopulation_64(uint64_t Value)
iterator erase(iterator where)
bool operator==(const SparseBitVectorElement &RHS) const
bool intersectWith(const SparseBitVectorElement &RHS, bool &BecameZero)
unsigned CountPopulation_32(uint32_t Value)
void intersectWithComplement(const SparseBitVectorElement &RHS1, const SparseBitVectorElement &RHS2, bool &BecameZero)
BitWord word(unsigned Idx) const
Element * provideInitialHead() const
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
SparseBitVectorElement< ElementSize > Element
bool intersectWithComplement(const SparseBitVector &RHS)
bool test_and_set(unsigned Idx)
bool intersects(const SparseBitVector< ElementSize > *RHS) const
int find_next(unsigned Curr) const
SparseBitVector(const SparseBitVector &RHS)
static NodeTy * createSentinel()
createSentinel - create the dynamic sentinel
SparseBitVectorIterator iterator
static void noteHead(Element *, Element *)
bool operator&=(SparseBitVector< ElementSize > *LHS, const SparseBitVector< ElementSize > &RHS)
bool intersects(const SparseBitVectorElement &RHS) const
void push_back(const NodeTy &val)
bool contains(const SparseBitVector< ElementSize > &RHS) const