: public ilist_node<SparseBitVectorElement<ElementSize> > {
public:
typedef unsigned long BitWord;
+ typedef unsigned size_type;
enum {
BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
}
- unsigned count() const {
+ size_type count() const {
unsigned NumBits = 0;
for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
- if (sizeof(BitWord) == 4)
- NumBits += CountPopulation_32(Bits[i]);
- else if (sizeof(BitWord) == 8)
- NumBits += CountPopulation_64(Bits[i]);
- else
- llvm_unreachable("Unsupported!");
+ NumBits += countPopulation(Bits[i]);
return NumBits;
}
/// find_first - Returns the index of the first set bit.
int find_first() const {
for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
- if (Bits[i] != 0) {
- if (sizeof(BitWord) == 4)
- return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
- if (sizeof(BitWord) == 8)
- return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
- llvm_unreachable("Unsupported!");
- }
+ if (Bits[i] != 0)
+ return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
llvm_unreachable("Illegal empty element");
}
// Mask off previous bits.
Copy &= ~0UL << BitPos;
- if (Copy != 0) {
- if (sizeof(BitWord) == 4)
- return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy);
- if (sizeof(BitWord) == 8)
- return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
- llvm_unreachable("Unsupported!");
- }
+ if (Copy != 0)
+ return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
// Check subsequent words.
for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
- if (Bits[i] != 0) {
- if (sizeof(BitWord) == 4)
- return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
- if (sizeof(BitWord) == 8)
- return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
- llvm_unreachable("Unsupported!");
- }
+ if (Bits[i] != 0)
+ return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
return -1;
}
}
};
+template <unsigned ElementSize>
+struct ilist_traits<SparseBitVectorElement<ElementSize> >
+ : public ilist_default_traits<SparseBitVectorElement<ElementSize> > {
+ typedef SparseBitVectorElement<ElementSize> Element;
+
+ Element *createSentinel() const { return static_cast<Element *>(&Sentinel); }
+ static void destroySentinel(Element *) {}
+
+ Element *provideInitialHead() const { return createSentinel(); }
+ Element *ensureHead(Element *) const { return createSentinel(); }
+ static void noteHead(Element *, Element *) {}
+
+private:
+ mutable ilist_half_node<Element> Sentinel;
+};
+
template <unsigned ElementSize = 128>
class SparseBitVector {
typedef ilist<SparseBitVectorElement<ElementSize> > ElementList;
AtEnd = true;
return;
}
- // Set up for next non zero word in bitmap.
+ // Set up for next non-zero word in bitmap.
BitNumber = Iter->index() * ElementSize;
NextSetBitNumber = Iter->find_first();
BitNumber += NextSetBitNumber;