LLVM API Documentation
00001 //===-- llvm/ADT/BitVectorSet.h - A bit-vector rep. of sets -----*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This is an implementation of the bit-vector representation of sets. Unlike 00011 // vector<bool>, this allows much more efficient parallel set operations on 00012 // bits, by using the bitset template. The bitset template unfortunately can 00013 // only represent sets with a size chosen at compile-time. We therefore use a 00014 // vector of bitsets. The maxmimum size of our sets (i.e., the size of the 00015 // universal set) can be chosen at creation time. 00016 // 00017 // External functions: 00018 // 00019 // bool Disjoint(const BitSetVector& set1, const BitSetVector& set2): 00020 // Tests if two sets have an empty intersection. 00021 // This is more efficient than !(set1 & set2).any(). 00022 // 00023 //===----------------------------------------------------------------------===// 00024 00025 #ifndef LLVM_ADT_BITSETVECTOR_H 00026 #define LLVM_ADT_BITSETVECTOR_H 00027 00028 #include <bitset> 00029 #include <vector> 00030 #include <functional> 00031 #include <iostream> 00032 00033 namespace llvm { 00034 00035 class BitSetVector { 00036 enum { BITSET_WORDSIZE = sizeof(long)*8 }; 00037 00038 // Types used internal to the representation 00039 typedef std::bitset<BITSET_WORDSIZE> bitword; 00040 typedef bitword::reference reference; 00041 00042 // Data used in the representation 00043 std::vector<bitword> bitsetVec; 00044 unsigned maxSize; 00045 00046 private: 00047 // Utility functions for the representation 00048 static unsigned NumWords(unsigned Size) { 00049 return (Size+BITSET_WORDSIZE-1)/BITSET_WORDSIZE; 00050 } 00051 static unsigned LastWordSize(unsigned Size) { return Size % BITSET_WORDSIZE; } 00052 00053 // Clear the unused bits in the last word. 00054 // The unused bits are the high (BITSET_WORDSIZE - LastWordSize()) bits 00055 void ClearUnusedBits() { 00056 unsigned long usedBits = (1U << LastWordSize(size())) - 1; 00057 bitsetVec.back() &= bitword(usedBits); 00058 } 00059 00060 const bitword& getWord(unsigned i) const { return bitsetVec[i]; } 00061 bitword& getWord(unsigned i) { return bitsetVec[i]; } 00062 00063 friend bool Disjoint(const BitSetVector& set1, 00064 const BitSetVector& set2); 00065 00066 BitSetVector(); // do not implement! 00067 00068 public: 00069 class iterator; 00070 /// 00071 /// Constructor: create a set of the maximum size maxSetSize. 00072 /// The set is initialized to empty. 00073 /// 00074 BitSetVector(unsigned maxSetSize) 00075 : bitsetVec(NumWords(maxSetSize)), maxSize(maxSetSize) { } 00076 00077 /// size - Return the number of bits tracked by this bit vector... 00078 unsigned size() const { return maxSize; } 00079 00080 /// 00081 /// Modifier methods: reset, set for entire set, operator[] for one element. 00082 /// 00083 void reset() { 00084 for (unsigned i=0, N = bitsetVec.size(); i < N; ++i) 00085 bitsetVec[i].reset(); 00086 } 00087 void set() { 00088 for (unsigned i=0, N = bitsetVec.size(); i < N; ++i) // skip last word 00089 bitsetVec[i].set(); 00090 ClearUnusedBits(); 00091 } 00092 reference operator[](unsigned n) { 00093 assert(n < size() && "BitSetVector: Bit number out of range"); 00094 unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE; 00095 return bitsetVec[ndiv][nmod]; 00096 } 00097 iterator begin() { return iterator::begin(*this); } 00098 iterator end() { return iterator::end(*this); } 00099 00100 /// 00101 /// Comparison operations: equal, not equal 00102 /// 00103 bool operator == (const BitSetVector& set2) const { 00104 assert(maxSize == set2.maxSize && "Illegal == comparison"); 00105 for (unsigned i = 0; i < bitsetVec.size(); ++i) 00106 if (getWord(i) != set2.getWord(i)) 00107 return false; 00108 return true; 00109 } 00110 bool operator != (const BitSetVector& set2) const { 00111 return ! (*this == set2); 00112 } 00113 00114 /// 00115 /// Set membership operations: single element, any, none, count 00116 /// 00117 bool test(unsigned n) const { 00118 assert(n < size() && "BitSetVector: Bit number out of range"); 00119 unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE; 00120 return bitsetVec[ndiv].test(nmod); 00121 } 00122 bool any() const { 00123 for (unsigned i = 0; i < bitsetVec.size(); ++i) 00124 if (bitsetVec[i].any()) 00125 return true; 00126 return false; 00127 } 00128 bool none() const { 00129 return ! any(); 00130 } 00131 unsigned count() const { 00132 unsigned n = 0; 00133 for (unsigned i = 0; i < bitsetVec.size(); ++i) 00134 n += bitsetVec[i].count(); 00135 return n; 00136 } 00137 bool all() const { 00138 return (count() == size()); 00139 } 00140 00141 /// 00142 /// Set operations: intersection, union, disjoint union, complement. 00143 /// 00144 BitSetVector operator& (const BitSetVector& set2) const { 00145 assert(maxSize == set2.maxSize && "Illegal intersection"); 00146 BitSetVector result(maxSize); 00147 for (unsigned i = 0; i < bitsetVec.size(); ++i) 00148 result.getWord(i) = getWord(i) & set2.getWord(i); 00149 return result; 00150 } 00151 BitSetVector operator| (const BitSetVector& set2) const { 00152 assert(maxSize == set2.maxSize && "Illegal intersection"); 00153 BitSetVector result(maxSize); 00154 for (unsigned i = 0; i < bitsetVec.size(); ++i) 00155 result.getWord(i) = getWord(i) | set2.getWord(i); 00156 return result; 00157 } 00158 BitSetVector operator^ (const BitSetVector& set2) const { 00159 assert(maxSize == set2.maxSize && "Illegal intersection"); 00160 BitSetVector result(maxSize); 00161 for (unsigned i = 0; i < bitsetVec.size(); ++i) 00162 result.getWord(i) = getWord(i) ^ set2.getWord(i); 00163 return result; 00164 } 00165 BitSetVector operator~ () const { 00166 BitSetVector result(maxSize); 00167 for (unsigned i = 0; i < bitsetVec.size(); ++i) 00168 (result.getWord(i) = getWord(i)).flip(); 00169 result.ClearUnusedBits(); 00170 return result; 00171 } 00172 00173 /// 00174 /// Printing and debugging support 00175 /// 00176 void print(std::ostream &O) const; 00177 void dump() const { print(std::cerr); } 00178 00179 public: 00180 // 00181 // An iterator to enumerate the bits in a BitSetVector. 00182 // Eventually, this needs to inherit from bidirectional_iterator. 00183 // But this iterator may not be as useful as I once thought and 00184 // may just go away. 00185 // 00186 class iterator { 00187 unsigned currentBit; 00188 unsigned currentWord; 00189 BitSetVector* bitvec; 00190 iterator(unsigned B, unsigned W, BitSetVector& _bitvec) 00191 : currentBit(B), currentWord(W), bitvec(&_bitvec) { } 00192 public: 00193 iterator(BitSetVector& _bitvec) 00194 : currentBit(0), currentWord(0), bitvec(&_bitvec) { } 00195 iterator(const iterator& I) 00196 : currentBit(I.currentBit),currentWord(I.currentWord),bitvec(I.bitvec) { } 00197 iterator& operator=(const iterator& I) { 00198 currentWord = I.currentWord; 00199 currentBit = I.currentBit; 00200 bitvec = I.bitvec; 00201 return *this; 00202 } 00203 00204 // Increment and decrement operators (pre and post) 00205 iterator& operator++() { 00206 if (++currentBit == BITSET_WORDSIZE) 00207 { currentBit = 0; if (currentWord < bitvec->size()) ++currentWord; } 00208 return *this; 00209 } 00210 iterator& operator--() { 00211 if (currentBit == 0) { 00212 currentBit = BITSET_WORDSIZE-1; 00213 currentWord = (currentWord == 0)? bitvec->size() : --currentWord; 00214 } 00215 else 00216 --currentBit; 00217 return *this; 00218 } 00219 iterator operator++(int) { iterator copy(*this); ++*this; return copy; } 00220 iterator operator--(int) { iterator copy(*this); --*this; return copy; } 00221 00222 // Dereferencing operators 00223 reference operator*() { 00224 assert(currentWord < bitvec->size() && 00225 "Dereferencing iterator past the end of a BitSetVector"); 00226 return bitvec->getWord(currentWord)[currentBit]; 00227 } 00228 00229 // Comparison operator 00230 bool operator==(const iterator& I) { 00231 return (I.bitvec == bitvec && 00232 I.currentWord == currentWord && I.currentBit == currentBit); 00233 } 00234 00235 protected: 00236 static iterator begin(BitSetVector& _bitvec) { return iterator(_bitvec); } 00237 static iterator end(BitSetVector& _bitvec) { return iterator(0, 00238 _bitvec.size(), _bitvec); } 00239 friend class BitSetVector; 00240 }; 00241 }; 00242 00243 00244 inline void BitSetVector::print(std::ostream& O) const 00245 { 00246 for (std::vector<bitword>::const_iterator 00247 I=bitsetVec.begin(), E=bitsetVec.end(); I != E; ++I) 00248 O << "<" << (*I) << ">" << (I+1 == E? "\n" : ", "); 00249 } 00250 00251 inline std::ostream& operator<< (std::ostream& O, const BitSetVector& bset) 00252 { 00253 bset.print(O); 00254 return O; 00255 } 00256 00257 00258 /// 00259 /// Optimized versions of fundamental comparison operations 00260 /// 00261 inline bool Disjoint(const BitSetVector& set1, 00262 const BitSetVector& set2) 00263 { 00264 assert(set1.size() == set2.size() && "Illegal intersection"); 00265 for (unsigned i = 0; i < set1.bitsetVec.size(); ++i) 00266 if ((set1.getWord(i) & set2.getWord(i)).any()) 00267 return false; 00268 return true; 00269 } 00270 00271 } // End llvm namespace 00272 #endif