// We therefore use a vector of bitsets. The maxmimum size of our sets
// (i.e., the size of the universal set) can be chosen at creation time.
//
-// The size of each Bitset is defined by the macro WORDSIZE.
-//
-// NOTE: The WORDSIZE macro should be made machine-dependent, in order to use
-// 64-bit words or whatever gives most efficient Bitsets on each platform.
-//
-//
// External functions:
//
// bool Disjoint(const BitSetVector& set1, const BitSetVector& set2):
//
//===----------------------------------------------------------------------===//
-#ifndef LLVM_SUPPORT_BITVECTORSET_H
-#define LLVM_SUPPORT_BITVECTORSET_H
+#ifndef SUPPORT_BITSETVECTOR_H
+#define SUPPORT_BITSETVECTOR_H
#include <bitset>
#include <vector>
#include <functional>
#include <iostream>
-
-#define WORDSIZE (32U)
-
-
class BitSetVector {
- typedef std::bitset<WORDSIZE> bitword;
+ enum { BITSET_WORDSIZE = sizeof(long)*8 };
+
+ // Types used internal to the representation
+ typedef std::bitset<BITSET_WORDSIZE> bitword;
typedef bitword::reference reference;
class iterator;
+ // Data used in the representation
std::vector<bitword> bitsetVec;
+ unsigned maxSize;
- static unsigned NumWords(unsigned Size) { return (Size+WORDSIZE-1)/WORDSIZE;}
+private:
+ // Utility functions for the representation
+ static unsigned NumWords(unsigned Size) {
+ return (Size+BITSET_WORDSIZE-1)/BITSET_WORDSIZE;
+ }
+ static unsigned LastWordSize(unsigned Size) { return Size % BITSET_WORDSIZE; }
+
+ // Clear the unused bits in the last word.
+ // The unused bits are the high (BITSET_WORDSIZE - LastWordSize()) bits
+ void ClearUnusedBits() {
+ unsigned long usedBits = (1U << LastWordSize(size())) - 1;
+ bitsetVec.back() &= bitword(usedBits);
+ }
const bitword& getWord(unsigned i) const { return bitsetVec[i]; }
bitword& getWord(unsigned i) { return bitsetVec[i]; }
BitSetVector(); // do not implement!
public:
- unsigned maxSize;
-
///
/// Constructor: create a set of the maximum size maxSetSize.
/// The set is initialized to empty.
///
BitSetVector(unsigned maxSetSize)
- : bitsetVec(BitSetVector::NumWords(maxSetSize)), maxSize(maxSetSize) { }
+ : bitsetVec(NumWords(maxSetSize)), maxSize(maxSetSize) { }
+
+ /// size - Return the number of bits tracked by this bit vector...
+ unsigned size() const { return maxSize; }
///
/// Modifier methods: reset, set for entire set, operator[] for one element.
///
void reset() {
- for(std::vector<bitword>::iterator I=bitsetVec.begin(), E=bitsetVec.end();
- I != E; ++I)
- I->reset();
+ for (unsigned i=0, N = bitsetVec.size(); i < N; ++i)
+ bitsetVec[i].reset();
}
void set() {
- for(std::vector<bitword>::iterator I=bitsetVec.begin(), E=bitsetVec.end();
- I != E; ++I)
- I->set();
+ for (unsigned i=0, N = bitsetVec.size(); i < N; ++i) // skip last word
+ bitsetVec[i].set();
+ ClearUnusedBits();
}
- std::bitset<32>::reference operator[](unsigned n) {
- unsigned ndiv = n / WORDSIZE, nmod = n % WORDSIZE;
- assert(ndiv < bitsetVec.size() && "BitSetVector: Bit number out of range");
+ reference operator[](unsigned n) {
+ assert(n < size() && "BitSetVector: Bit number out of range");
+ unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE;
return bitsetVec[ndiv][nmod];
}
iterator begin() { return iterator::begin(*this); }
iterator end() { return iterator::end(*this); }
+ ///
+ /// Comparison operations: equal, not equal
+ ///
+ bool operator == (const BitSetVector& set2) const {
+ assert(maxSize == set2.maxSize && "Illegal == comparison");
+ for (unsigned i = 0; i < bitsetVec.size(); ++i)
+ if (getWord(i) != set2.getWord(i))
+ return false;
+ return true;
+ }
+ bool operator != (const BitSetVector& set2) const {
+ return ! (*this == set2);
+ }
+
///
/// Set membership operations: single element, any, none, count
///
bool test(unsigned n) const {
- unsigned ndiv = n / WORDSIZE, nmod = n % WORDSIZE;
- assert(ndiv < bitsetVec.size() && "BitSetVector: Bit number out of range");
+ assert(n < size() && "BitSetVector: Bit number out of range");
+ unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE;
return bitsetVec[ndiv].test(nmod);
}
bool any() const {
n += bitsetVec[i].count();
return n;
}
+ bool all() const {
+ return (count() == size());
+ }
///
/// Set operations: intersection, union, disjoint union, complement.
BitSetVector result(maxSize);
for (unsigned i = 0; i < bitsetVec.size(); ++i)
(result.getWord(i) = getWord(i)).flip();
+ result.ClearUnusedBits();
return result;
}
class iterator {
unsigned currentBit;
unsigned currentWord;
- BitSetVector& bitvec;
- iterator(unsigned B, unsigned W, BitSetVector _bitvec)
- : currentBit(B), currentWord(W), bitvec(_bitvec) { }
+ BitSetVector* bitvec;
+ iterator(unsigned B, unsigned W, BitSetVector& _bitvec)
+ : currentBit(B), currentWord(W), bitvec(&_bitvec) { }
public:
iterator(BitSetVector& _bitvec)
- : currentBit(0), currentWord(0), bitvec(_bitvec) { }
+ : currentBit(0), currentWord(0), bitvec(&_bitvec) { }
iterator(const iterator& I)
: currentBit(I.currentBit),currentWord(I.currentWord),bitvec(I.bitvec) { }
iterator& operator=(const iterator& I) {
- currentWord == I.currentWord;
- currentBit == I.currentBit;
+ currentWord = I.currentWord;
+ currentBit = I.currentBit;
bitvec = I.bitvec;
return *this;
}
// Increment and decrement operators (pre and post)
iterator& operator++() {
- if (++currentBit == WORDSIZE)
- { currentBit = 0; if (currentWord < bitvec.maxSize) ++currentWord; }
+ if (++currentBit == BITSET_WORDSIZE)
+ { currentBit = 0; if (currentWord < bitvec->size()) ++currentWord; }
return *this;
}
iterator& operator--() {
if (currentBit == 0) {
- currentBit = WORDSIZE-1;
- currentWord = (currentWord == 0)? bitvec.maxSize : --currentWord;
+ currentBit = BITSET_WORDSIZE-1;
+ currentWord = (currentWord == 0)? bitvec->size() : --currentWord;
}
else
--currentBit;
// Dereferencing operators
reference operator*() {
- assert(currentWord < bitvec.maxSize &&
+ assert(currentWord < bitvec->size() &&
"Dereferencing iterator past the end of a BitSetVector");
- return bitvec.getWord(currentWord)[currentBit];
+ return bitvec->getWord(currentWord)[currentBit];
}
// Comparison operator
bool operator==(const iterator& I) {
- return (&I.bitvec == &bitvec &&
+ return (I.bitvec == bitvec &&
I.currentWord == currentWord && I.currentBit == currentBit);
}
protected:
static iterator begin(BitSetVector& _bitvec) { return iterator(_bitvec); }
static iterator end(BitSetVector& _bitvec) { return iterator(0,
- _bitvec.maxSize, _bitvec); }
+ _bitvec.size(), _bitvec); }
friend class BitSetVector;
};
};
inline bool Disjoint(const BitSetVector& set1,
const BitSetVector& set2)
{
- assert(set1.maxSize == set2.maxSize && "Illegal intersection");
+ assert(set1.size() == set2.size() && "Illegal intersection");
for (unsigned i = 0; i < set1.bitsetVec.size(); ++i)
if ((set1.getWord(i) & set2.getWord(i)).any())
return false;
projects / oota-llvm.git / blobdiff