#ifndef LLVM_ADT_SPARSEBITVECTOR_H
#define LLVM_ADT_SPARSEBITVECTOR_H
-#include <cassert>
-#include <climits>
-#include <cstring>
-#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
+#include <cassert>
+#include <climits>
namespace llvm {
template <unsigned ElementSize = 128>
struct SparseBitVectorElement
- : ilist_node<SparseBitVectorElement<ElementSize> > {
+ : public ilist_node<SparseBitVectorElement<ElementSize> > {
public:
typedef unsigned long BitWord;
enum {
else if (sizeof(BitWord) == 8)
NumBits += CountPopulation_64(Bits[i]);
else
- assert(0 && "Unsupported!");
+ llvm_unreachable("Unsupported!");
return NumBits;
}
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]);
- else if (sizeof(BitWord) == 8)
- return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
- else
- assert(0 && "Unsupported!");
+ return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
+ if (sizeof(BitWord) == 8)
+ return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
+ llvm_unreachable("Unsupported!");
}
- assert(0 && "Illegal empty element");
- return 0; // Not reached
+ llvm_unreachable("Illegal empty element");
}
/// find_next - Returns the index of the next set bit starting from the
&& "Word Position outside of element");
// Mask off previous bits.
- Copy &= ~0L << BitPos;
+ Copy &= ~0UL << BitPos;
if (Copy != 0) {
if (sizeof(BitWord) == 4)
- return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy);
- else if (sizeof(BitWord) == 8)
- return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
- else
- assert(0 && "Unsupported!");
+ return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
+ if (sizeof(BitWord) == 8)
+ return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
+ llvm_unreachable("Unsupported!");
}
// 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]);
- else if (sizeof(BitWord) == 8)
- return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
- else
- assert(0 && "Unsupported!");
+ return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
+ if (sizeof(BitWord) == 8)
+ return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
+ llvm_unreachable("Unsupported!");
}
return -1;
}
}
BecameZero = allzero;
}
+};
- // Get a hash value for this element;
- uint64_t getHashValue() const {
- uint64_t HashVal = 0;
- for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
- HashVal ^= Bits[i];
- }
- return HashVal;
- }
+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>
iterator end() const {
return iterator(this, true);
}
-
- // Get a hash value for this bitmap.
- uint64_t getHashValue() const {
- uint64_t HashVal = 0;
- for (ElementListConstIter Iter = Elements.begin();
- Iter != Elements.end();
- ++Iter) {
- HashVal ^= Iter->index();
- HashVal ^= Iter->getHashValue();
- }
- return HashVal;
- }
};
// Convenience functions to allow Or and And without dereferencing in the user
// Dump a SparseBitVector to a stream
template <unsigned ElementSize>
void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
- out << "[ ";
-
- typename SparseBitVector<ElementSize>::iterator bi;
- for (bi = LHS.begin(); bi != LHS.end(); ++bi) {
- out << *bi << " ";
+ out << "[";
+
+ typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
+ be = LHS.end();
+ if (bi != be) {
+ out << *bi;
+ for (++bi; bi != be; ++bi) {
+ out << " " << *bi;
+ }
}
- out << " ]\n";
+ out << "]\n";
}
} // end namespace llvm