1 //===-- BitVectorSet.h - A bit-vector representation of sets -----*- C++ -*--=//
3 // class BitVectorSet --
5 // An implementation of the bit-vector representation of sets.
6 // Unlike vector<bool>, this allows much more efficient parallel set
7 // operations on bits, by using the bitset template . The bitset template
8 // unfortunately can only represent sets with a size chosen at compile-time.
9 // We therefore use a vector of bitsets. The maxmimum size of our sets
10 // (i.e., the size of the universal set) can be chosen at creation time.
12 // The size of each Bitset is defined by the macro WORDSIZE.
14 // NOTE: The WORDSIZE macro should be made machine-dependent, in order to use
15 // 64-bit words or whatever gives most efficient Bitsets on each platform.
18 // External functions:
20 // bool Disjoint(const BitSetVector& set1, const BitSetVector& set2):
21 // Tests if two sets have an empty intersection.
22 // This is more efficient than !(set1 & set2).any().
24 //===----------------------------------------------------------------------===//
26 #ifndef LLVM_SUPPORT_BITVECTORSET_H
27 #define LLVM_SUPPORT_BITVECTORSET_H
35 #define WORDSIZE (32U)
39 // Types used internal to the representation
40 typedef std::bitset<WORDSIZE> bitword;
41 typedef bitword::reference reference;
44 // Data used in the representation
45 std::vector<bitword> bitsetVec;
49 // Utility functions for the representation
50 static unsigned NumWords(unsigned Size) { return (Size+WORDSIZE-1)/WORDSIZE;}
51 static unsigned LastWordSize(unsigned Size) { return Size % WORDSIZE; }
53 // Clear the unused bits in the last word.
54 // The unused bits are the high (WORDSIZE - LastWordSize()) bits
55 void ClearUnusedBits() {
56 unsigned long usedBits = (1U << LastWordSize(size())) - 1;
57 bitsetVec.back() &= bitword(usedBits);
60 const bitword& getWord(unsigned i) const { return bitsetVec[i]; }
61 bitword& getWord(unsigned i) { return bitsetVec[i]; }
63 friend bool Disjoint(const BitSetVector& set1,
64 const BitSetVector& set2);
66 BitSetVector(); // do not implement!
70 /// Constructor: create a set of the maximum size maxSetSize.
71 /// The set is initialized to empty.
73 BitSetVector(unsigned maxSetSize)
74 : bitsetVec(NumWords(maxSetSize)), maxSize(maxSetSize) { }
76 /// size - Return the number of bits tracked by this bit vector...
77 unsigned size() const { return maxSize; }
80 /// Modifier methods: reset, set for entire set, operator[] for one element.
83 for (unsigned i=0, N = bitsetVec.size(); i < N; ++i)
87 for (unsigned i=0, N = bitsetVec.size(); i < N; ++i) // skip last word
91 reference operator[](unsigned n) {
92 assert(n < size() && "BitSetVector: Bit number out of range");
93 unsigned ndiv = n / WORDSIZE, nmod = n % WORDSIZE;
94 return bitsetVec[ndiv][nmod];
96 iterator begin() { return iterator::begin(*this); }
97 iterator end() { return iterator::end(*this); }
100 /// Comparison operations: equal, not equal
102 bool operator == (const BitSetVector& set2) const {
103 assert(maxSize == set2.maxSize && "Illegal == comparison");
104 for (unsigned i = 0; i < bitsetVec.size(); ++i)
105 if (getWord(i) != set2.getWord(i))
109 bool operator != (const BitSetVector& set2) const {
110 return ! (*this == set2);
114 /// Set membership operations: single element, any, none, count
116 bool test(unsigned n) const {
117 assert(n < size() && "BitSetVector: Bit number out of range");
118 unsigned ndiv = n / WORDSIZE, nmod = n % WORDSIZE;
119 return bitsetVec[ndiv].test(nmod);
122 for (unsigned i = 0; i < bitsetVec.size(); ++i)
123 if (bitsetVec[i].any())
130 unsigned count() const {
132 for (unsigned i = 0; i < bitsetVec.size(); ++i)
133 n += bitsetVec[i].count();
137 return (count() == size());
141 /// Set operations: intersection, union, disjoint union, complement.
143 BitSetVector operator& (const BitSetVector& set2) const {
144 assert(maxSize == set2.maxSize && "Illegal intersection");
145 BitSetVector result(maxSize);
146 for (unsigned i = 0; i < bitsetVec.size(); ++i)
147 result.getWord(i) = getWord(i) & set2.getWord(i);
150 BitSetVector operator| (const BitSetVector& set2) const {
151 assert(maxSize == set2.maxSize && "Illegal intersection");
152 BitSetVector result(maxSize);
153 for (unsigned i = 0; i < bitsetVec.size(); ++i)
154 result.getWord(i) = getWord(i) | set2.getWord(i);
157 BitSetVector operator^ (const BitSetVector& set2) const {
158 assert(maxSize == set2.maxSize && "Illegal intersection");
159 BitSetVector result(maxSize);
160 for (unsigned i = 0; i < bitsetVec.size(); ++i)
161 result.getWord(i) = getWord(i) ^ set2.getWord(i);
164 BitSetVector operator~ () const {
165 BitSetVector result(maxSize);
166 for (unsigned i = 0; i < bitsetVec.size(); ++i)
167 (result.getWord(i) = getWord(i)).flip();
168 result.ClearUnusedBits();
173 /// Printing and debugging support
175 void print(std::ostream &O) const;
176 void dump() const { print(std::cerr); }
180 // An iterator to enumerate the bits in a BitSetVector.
181 // Eventually, this needs to inherit from bidirectional_iterator.
182 // But this iterator may not be as useful as I once thought and
187 unsigned currentWord;
188 BitSetVector* bitvec;
189 iterator(unsigned B, unsigned W, BitSetVector& _bitvec)
190 : currentBit(B), currentWord(W), bitvec(&_bitvec) { }
192 iterator(BitSetVector& _bitvec)
193 : currentBit(0), currentWord(0), bitvec(&_bitvec) { }
194 iterator(const iterator& I)
195 : currentBit(I.currentBit),currentWord(I.currentWord),bitvec(I.bitvec) { }
196 iterator& operator=(const iterator& I) {
197 currentWord = I.currentWord;
198 currentBit = I.currentBit;
203 // Increment and decrement operators (pre and post)
204 iterator& operator++() {
205 if (++currentBit == WORDSIZE)
206 { currentBit = 0; if (currentWord < bitvec->size()) ++currentWord; }
209 iterator& operator--() {
210 if (currentBit == 0) {
211 currentBit = WORDSIZE-1;
212 currentWord = (currentWord == 0)? bitvec->size() : --currentWord;
218 iterator operator++(int) { iterator copy(*this); ++*this; return copy; }
219 iterator operator--(int) { iterator copy(*this); --*this; return copy; }
221 // Dereferencing operators
222 reference operator*() {
223 assert(currentWord < bitvec->size() &&
224 "Dereferencing iterator past the end of a BitSetVector");
225 return bitvec->getWord(currentWord)[currentBit];
228 // Comparison operator
229 bool operator==(const iterator& I) {
230 return (I.bitvec == bitvec &&
231 I.currentWord == currentWord && I.currentBit == currentBit);
235 static iterator begin(BitSetVector& _bitvec) { return iterator(_bitvec); }
236 static iterator end(BitSetVector& _bitvec) { return iterator(0,
237 _bitvec.size(), _bitvec); }
238 friend class BitSetVector;
243 inline void BitSetVector::print(std::ostream& O) const
245 for (std::vector<bitword>::const_iterator
246 I=bitsetVec.begin(), E=bitsetVec.end(); I != E; ++I)
247 O << "<" << (*I) << ">" << (I+1 == E? "\n" : ", ");
250 inline std::ostream& operator<< (std::ostream& O, const BitSetVector& bset)
258 /// Optimized versions of fundamental comparison operations
260 inline bool Disjoint(const BitSetVector& set1,
261 const BitSetVector& set2)
263 assert(set1.size() == set2.size() && "Illegal intersection");
264 for (unsigned i = 0; i < set1.bitsetVec.size(); ++i)
265 if ((set1.getWord(i) & set2.getWord(i)).any())