8 #ifndef SPARSEBITVECTOR_H
9 #define SPARSEBITVECTOR_H
21 # define HAS_CLZ __has_builtin(__builtin_clz)
22 # define HAS_CLZLL __has_builtin(__builtin_clzll)
23 # define HAS_CTZ __has_builtin(__builtin_ctz)
24 # define HAS_CTZLL __has_builtin(__builtin_ctzll)
51 return std::numeric_limits<T>::digits;
56 unsigned ZeroBits = 0;
57 T Shift = std::numeric_limits<T>::digits >> 1;
58 T Mask = std::numeric_limits<T>::max() >> Shift;
61 if ((Val & Mask) == 0)
73 #if defined(__GNUC__) || defined(_MSC_VER)
74 template <
typename T>
struct TrailingZerosCounter<T, 4>
81 #if HAS_CTZ || defined(__GNUC__)
82 return __builtin_ctz(Val);
83 #elif defined(_MSC_VER)
85 _BitScanForward(&Index, Val);
91 #if !defined(_MSC_VER) || defined(_M_X64)
92 template <
typename T>
struct TrailingZerosCounter<T, 8>
99 #if HAS_CTZLL || defined(__GNUC__)
100 return __builtin_ctzll(Val);
101 #elif defined(_MSC_VER)
103 _BitScanForward64(&Index, Val);
118 template <
typename T>
121 static_assert(std::numeric_limits<T>::is_integer &&
122 !std::numeric_limits<T>::is_signed,
123 "Only unsigned integral types are allowed.");
132 static_assert(SizeOfT <= 4,
"Not implemented!");
133 #if defined(__GNUC__)
134 return __builtin_popcount(
Value);
137 v = v - ((v >> 1) & 0x55555555);
138 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
139 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
149 return std::numeric_limits<T>::digits;
152 unsigned ZeroBits = 0;
153 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1)
155 T Tmp = Val >> Shift;
165 #if defined(__GNUC__) || defined(_MSC_VER)
166 template <
typename T>
struct LeadingZerosCounter<T, 4>
173 #if defined(__GNUC__) || HAS_CLZ
174 return __builtin_clz(Val);
175 #elif defined(_MSC_VER)
177 _BitScanReverse(&Index, Val);
183 #if !defined(_MSC_VER) || defined(_M_X64)
184 template <
typename T>
struct LeadingZerosCounter<T, 8>
191 #if defined(__GNUC__) || HAS_CLZLL
192 return __builtin_clzll(Val);
193 #elif defined(_MSC_VER)
195 _BitScanReverse64(&Index, Val);
210 template <
typename T>
213 static_assert(std::numeric_limits<T>::is_integer &&
214 !std::numeric_limits<T>::is_signed,
215 "Only unsigned integral types are allowed.");
223 #if defined(__GNUC__)
224 return __builtin_popcountll(
Value);
227 v = v - ((v >> 1) & 0x5555555555555555ULL);
228 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
229 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
230 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
238 template <
typename T>
241 static_assert(std::numeric_limits<T>::is_integer &&
242 !std::numeric_limits<T>::is_signed,
243 "Only unsigned integral types are allowed.");
299 return !(*
this == RHS);
329 bool old =
test(Idx);
350 unsigned NumBits = 0;
362 assert(
false &&
"SBV: find_first: SBV cannot be empty");
376 assert(
false &&
"SBV: find_last: SBV cannot be empty");
391 &&
"Word Position outside of element");
394 Copy &= ~0UL << BitPos;
409 bool changed =
false;
415 if (!changed && old !=
Bits[i])
437 bool changed =
false;
449 if (!changed && old !=
Bits[i])
452 BecameZero = allzero;
462 bool changed =
false;
474 if (!changed && old !=
Bits[i])
477 BecameZero = allzero;
496 BecameZero = allzero;
500 template <
unsigned ElementSize = 128>
506 using ElementList = std::list<SparseBitVectorElement<ElementSize>>;
554 while (ElementIter != Begin
555 && ElementIter->index() > ElementIndex)
560 while (ElementIter != End &&
561 ElementIter->index() < ElementIndex)
609 unsigned BitPos =
Iter->find_first();
631 int NextSetBitNumber =
Iter->find_next(
BitNumber % ElementSize) ;
633 if (NextSetBitNumber == -1 || (
BitNumber % ElementSize == 0))
646 NextSetBitNumber =
Iter->find_first();
712 return !(*
this == RHS);
755 unsigned ElementIndex = Idx / ElementSize;
760 if (ElementIter ==
Elements.end() ||
761 ElementIter->index() != ElementIndex)
763 return ElementIter->test(Idx % ElementSize);
771 unsigned ElementIndex = Idx / ElementSize;
776 if (ElementIter ==
Elements.end() ||
777 ElementIter->index() != ElementIndex)
779 ElementIter->reset(Idx % ElementSize);
782 if (ElementIter->empty())
791 unsigned ElementIndex = Idx / ElementSize;
801 if (ElementIter ==
Elements.end() ||
802 ElementIter->index() != ElementIndex)
807 if (ElementIter !=
Elements.end() &&
808 ElementIter->index() < ElementIndex)
810 ElementIter =
Elements.emplace(ElementIter, ElementIndex);
815 ElementIter->set(Idx % ElementSize);
820 bool old =
test(Idx);
831 return !(*
this == RHS);
842 if (*Iter1 != *Iter2)
854 bool changed =
false;
864 if (Iter1 ==
Elements.end() || Iter1->index() > Iter2->index())
870 else if (Iter1->index() == Iter2->index())
872 changed |= Iter1->unionWith(*Iter2);
891 bool changed =
false;
908 if (Iter1->index() > Iter2->index())
912 else if (Iter1->index() == Iter2->index())
915 changed |= Iter1->intersectWith(*Iter2, BecameZero);
959 bool changed =
false;
976 if (Iter1->index() > Iter2->index())
980 else if (Iter1->index() == Iter2->index())
983 changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
1020 else if (
this == &RHS2)
1038 while (Iter2 != RHS2.
Elements.end())
1043 if (Iter1->index() > Iter2->index())
1047 else if (Iter1->index() == Iter2->index())
1049 bool BecameZero =
false;
1050 Elements.emplace_back(Iter1->index());
1051 Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
1089 while (Iter2 != RHS.
Elements.end())
1094 if (Iter1->index() > Iter2->index())
1098 else if (Iter1->index() == Iter2->index())
1100 if (Iter1->intersects(*Iter2))
1119 return (Result == RHS);
1148 unsigned BitCount = 0;
1152 BitCount += Iter->count();
1171 template <
unsigned ElementSize>
1178 template <
unsigned ElementSize>
1182 return LHS->operator|=(RHS);
1185 template <
unsigned ElementSize>
1189 return LHS->operator&=(RHS);
1192 template <
unsigned ElementSize>
1201 template <
unsigned ElementSize>
1202 inline SparseBitVector<ElementSize>
1211 template <
unsigned ElementSize>
1212 inline SparseBitVector<ElementSize>
1221 template <
unsigned ElementSize>
1222 inline SparseBitVector<ElementSize>
1232 template <
unsigned ElementSize>
1242 for (++bi; bi != be; ++bi)
const_iterator begin(void) const
const_iterator end(void) const
bool empty(void) const
Returns true if no bits are set.
SparseBitVectorIterator()=delete
void AdvanceToNextNonZero()
ElementListConstIter Iter
bool operator!=(const SparseBitVectorIterator &RHS) const
void AdvanceToFirstNonZero()
SparseBitVectorIterator(const SparseBitVector< ElementSize > *RHS, bool end=false)
SparseBitVectorIterator & operator++()
bool operator==(const SparseBitVectorIterator &RHS) const
SparseBitVectorIterator operator++(int)
unsigned operator*() const
SparseBitVectorElement< ElementSize >::BitWord Bits
SparseBitVectorIterator iterator
bool test(unsigned Idx) const
bool operator&=(const SparseBitVector &RHS)
bool intersects(const SparseBitVector< ElementSize > *RHS) const
void intersectWithComplement(const SparseBitVector< ElementSize > *RHS1, const SparseBitVector< ElementSize > *RHS2)
bool test_and_set(unsigned Idx)
typename ElementList::iterator ElementListIter
bool operator|=(const SparseBitVector &RHS)
bool intersects(const SparseBitVector< ElementSize > &RHS) const
std::list< SparseBitVectorElement< ElementSize > > ElementList
SparseBitVector & operator=(SparseBitVector &&RHS)
bool operator==(const SparseBitVector &RHS) const
bool intersectWithComplement(const SparseBitVector &RHS)
SparseBitVector(SparseBitVector &&RHS) noexcept
SparseBitVector(const SparseBitVector &RHS)
bool intersectWithComplement(const SparseBitVector< ElementSize > *RHS) const
ElementListIter FindLowerBound(unsigned ElementIndex)
ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const
bool contains(const SparseBitVector< ElementSize > &RHS) const
bool operator!=(const SparseBitVector &RHS) const
typename ElementList::const_iterator ElementListConstIter
ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const
ElementListIter CurrElementIter
SparseBitVector & operator=(const SparseBitVector &RHS)
void intersectWithComplement(const SparseBitVector< ElementSize > &RHS1, const SparseBitVector< ElementSize > &RHS2)
constexpr std::remove_reference< T >::type && move(T &&t) noexcept
IntervalValue operator-(const IntervalValue &lhs, const IntervalValue &rhs)
Subtract IntervalValues.
unsigned countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
bool operator&=(SparseBitVector< ElementSize > *LHS, const SparseBitVector< ElementSize > &RHS)
IntervalValue operator&(const IntervalValue &lhs, const IntervalValue &rhs)
Bitwise AND of IntervalValues.
llvm::Value Value
LLVM Basic classes.
bool operator|=(SparseBitVector< ElementSize > &LHS, const SparseBitVector< ElementSize > *RHS)
void dump(const SparseBitVector< ElementSize > &LHS, std::ostream &out)
IntervalValue operator|(const IntervalValue &lhs, const IntervalValue &rhs)
Bitwise OR of IntervalValues.
unsigned countPopulation(T Value)
ZeroBehavior
The behavior an operation has on an input of 0.
@ ZB_Undefined
The returned value is undefined.
@ ZB_Max
The returned value is numeric_limits<T>::max()
@ ZB_Width
The returned value is numeric_limits<T>::digits.
unsigned countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
static unsigned count(T Val, ZeroBehavior)
static unsigned count(T Value)
static unsigned count(T Value)
int find_last() const
find_last - Returns the index of the last set bit.
int find_first() const
find_first - Returns the index of the first set bit.
bool intersects(const SparseBitVectorElement &RHS) const
bool intersectWith(const SparseBitVectorElement &RHS, bool &BecameZero)
bool unionWith(const SparseBitVectorElement &RHS)
bool test(unsigned Idx) const
BitWord Bits[BITWORDS_PER_ELEMENT]
BitWord word(unsigned Idx) const
int find_next(unsigned Curr) const
void intersectWithComplement(const SparseBitVectorElement &RHS1, const SparseBitVectorElement &RHS2, bool &BecameZero)
SparseBitVectorElement(unsigned Idx)
bool test_and_set(unsigned Idx)
SparseBitVectorElement()=default
bool operator==(const SparseBitVectorElement &RHS) const
bool operator!=(const SparseBitVectorElement &RHS) const
bool intersectWithComplement(const SparseBitVectorElement &RHS, bool &BecameZero)
static unsigned count(T Val, ZeroBehavior)