LLVM API Documentation
00001 //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the BitVector class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_ADT_BITVECTOR_H 00015 #define LLVM_ADT_BITVECTOR_H 00016 00017 #include "llvm/Support/MathExtras.h" 00018 #include <algorithm> 00019 #include <cassert> 00020 #include <climits> 00021 #include <cstring> 00022 00023 namespace llvm { 00024 00025 class BitVector { 00026 typedef unsigned long BitWord; 00027 00028 enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; 00029 00030 BitWord *Bits; // Actual bits. 00031 unsigned Size; // Size of bitvector in bits. 00032 unsigned Capacity; // Size of allocated memory in BitWord. 00033 00034 public: 00035 // Encapsulation of a single bit. 00036 class reference { 00037 friend class BitVector; 00038 00039 BitWord *WordRef; 00040 unsigned BitPos; 00041 00042 reference(); // Undefined 00043 00044 public: 00045 reference(BitVector &b, unsigned Idx) { 00046 WordRef = &b.Bits[Idx / BITWORD_SIZE]; 00047 BitPos = Idx % BITWORD_SIZE; 00048 } 00049 00050 ~reference() {} 00051 00052 reference& operator=(bool t) { 00053 if (t) 00054 *WordRef |= 1L << BitPos; 00055 else 00056 *WordRef &= ~(1L << BitPos); 00057 return *this; 00058 } 00059 00060 operator bool() const { 00061 return ((*WordRef) & (1L << BitPos)) ? true : false; 00062 } 00063 }; 00064 00065 00066 /// BitVector default ctor - Creates an empty bitvector. 00067 BitVector() : Size(0), Capacity(0) { 00068 Bits = 0; 00069 } 00070 00071 /// BitVector ctor - Creates a bitvector of specified number of bits. All 00072 /// bits are initialized to the specified value. 00073 explicit BitVector(unsigned s, bool t = false) : Size(s) { 00074 Capacity = NumBitWords(s); 00075 Bits = new BitWord[Capacity]; 00076 init_words(Bits, Capacity, t); 00077 if (t) 00078 clear_unused_bits(); 00079 } 00080 00081 /// BitVector copy ctor. 00082 BitVector(const BitVector &RHS) : Size(RHS.size()) { 00083 if (Size == 0) { 00084 Bits = 0; 00085 Capacity = 0; 00086 return; 00087 } 00088 00089 Capacity = NumBitWords(RHS.size()); 00090 Bits = new BitWord[Capacity]; 00091 std::copy(RHS.Bits, &RHS.Bits[Capacity], Bits); 00092 } 00093 00094 ~BitVector() { 00095 delete[] Bits; 00096 } 00097 00098 /// size - Returns the number of bits in this bitvector. 00099 unsigned size() const { return Size; } 00100 00101 /// count - Returns the number of bits which are set. 00102 unsigned count() const { 00103 unsigned NumBits = 0; 00104 for (unsigned i = 0; i < NumBitWords(size()); ++i) 00105 if (sizeof(BitWord) == 4) 00106 NumBits += CountPopulation_32((uint32_t)Bits[i]); 00107 else if (sizeof(BitWord) == 8) 00108 NumBits += CountPopulation_64(Bits[i]); 00109 else 00110 assert(0 && "Unsupported!"); 00111 return NumBits; 00112 } 00113 00114 /// any - Returns true if any bit is set. 00115 bool any() const { 00116 for (unsigned i = 0; i < NumBitWords(size()); ++i) 00117 if (Bits[i] != 0) 00118 return true; 00119 return false; 00120 } 00121 00122 /// none - Returns true if none of the bits are set. 00123 bool none() const { 00124 return !any(); 00125 } 00126 00127 /// find_first - Returns the index of the first set bit, -1 if none 00128 /// of the bits are set. 00129 int find_first() const { 00130 for (unsigned i = 0; i < NumBitWords(size()); ++i) 00131 if (Bits[i] != 0) { 00132 if (sizeof(BitWord) == 4) 00133 return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); 00134 else if (sizeof(BitWord) == 8) 00135 return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 00136 else 00137 assert(0 && "Unsupported!"); 00138 } 00139 return -1; 00140 } 00141 00142 /// find_next - Returns the index of the next set bit following the 00143 /// "Prev" bit. Returns -1 if the next set bit is not found. 00144 int find_next(unsigned Prev) const { 00145 ++Prev; 00146 if (Prev >= Size) 00147 return -1; 00148 00149 unsigned WordPos = Prev / BITWORD_SIZE; 00150 unsigned BitPos = Prev % BITWORD_SIZE; 00151 BitWord Copy = Bits[WordPos]; 00152 // Mask off previous bits. 00153 Copy &= ~0L << BitPos; 00154 00155 if (Copy != 0) { 00156 if (sizeof(BitWord) == 4) 00157 return WordPos * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Copy); 00158 else if (sizeof(BitWord) == 8) 00159 return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); 00160 else 00161 assert(0 && "Unsupported!"); 00162 } 00163 00164 // Check subsequent words. 00165 for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i) 00166 if (Bits[i] != 0) { 00167 if (sizeof(BitWord) == 4) 00168 return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); 00169 else if (sizeof(BitWord) == 8) 00170 return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 00171 else 00172 assert(0 && "Unsupported!"); 00173 } 00174 return -1; 00175 } 00176 00177 /// clear - Clear all bits. 00178 void clear() { 00179 Size = 0; 00180 } 00181 00182 /// resize - Grow or shrink the bitvector. 00183 void resize(unsigned N, bool t = false) { 00184 if (N > Capacity * BITWORD_SIZE) { 00185 unsigned OldCapacity = Capacity; 00186 grow(N); 00187 init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t); 00188 } 00189 00190 // Set any old unused bits that are now included in the BitVector. This 00191 // may set bits that are not included in the new vector, but we will clear 00192 // them back out below. 00193 if (N > Size) 00194 set_unused_bits(t); 00195 00196 // Update the size, and clear out any bits that are now unused 00197 unsigned OldSize = Size; 00198 Size = N; 00199 if (t || N < OldSize) 00200 clear_unused_bits(); 00201 } 00202 00203 void reserve(unsigned N) { 00204 if (N > Capacity * BITWORD_SIZE) 00205 grow(N); 00206 } 00207 00208 // Set, reset, flip 00209 BitVector &set() { 00210 init_words(Bits, Capacity, true); 00211 clear_unused_bits(); 00212 return *this; 00213 } 00214 00215 BitVector &set(unsigned Idx) { 00216 Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); 00217 return *this; 00218 } 00219 00220 BitVector &reset() { 00221 init_words(Bits, Capacity, false); 00222 return *this; 00223 } 00224 00225 BitVector &reset(unsigned Idx) { 00226 Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); 00227 return *this; 00228 } 00229 00230 BitVector &flip() { 00231 for (unsigned i = 0; i < NumBitWords(size()); ++i) 00232 Bits[i] = ~Bits[i]; 00233 clear_unused_bits(); 00234 return *this; 00235 } 00236 00237 BitVector &flip(unsigned Idx) { 00238 Bits[Idx / BITWORD_SIZE] ^= 1L << (Idx % BITWORD_SIZE); 00239 return *this; 00240 } 00241 00242 // No argument flip. 00243 BitVector operator~() const { 00244 return BitVector(*this).flip(); 00245 } 00246 00247 // Indexing. 00248 reference operator[](unsigned Idx) { 00249 assert (Idx < Size && "Out-of-bounds Bit access."); 00250 return reference(*this, Idx); 00251 } 00252 00253 bool operator[](unsigned Idx) const { 00254 assert (Idx < Size && "Out-of-bounds Bit access."); 00255 BitWord Mask = 1L << (Idx % BITWORD_SIZE); 00256 return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; 00257 } 00258 00259 bool test(unsigned Idx) const { 00260 return (*this)[Idx]; 00261 } 00262 00263 // Comparison operators. 00264 bool operator==(const BitVector &RHS) const { 00265 unsigned ThisWords = NumBitWords(size()); 00266 unsigned RHSWords = NumBitWords(RHS.size()); 00267 unsigned i; 00268 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 00269 if (Bits[i] != RHS.Bits[i]) 00270 return false; 00271 00272 // Verify that any extra words are all zeros. 00273 if (i != ThisWords) { 00274 for (; i != ThisWords; ++i) 00275 if (Bits[i]) 00276 return false; 00277 } else if (i != RHSWords) { 00278 for (; i != RHSWords; ++i) 00279 if (RHS.Bits[i]) 00280 return false; 00281 } 00282 return true; 00283 } 00284 00285 bool operator!=(const BitVector &RHS) const { 00286 return !(*this == RHS); 00287 } 00288 00289 // Intersection, union, disjoint union. 00290 BitVector &operator&=(const BitVector &RHS) { 00291 unsigned ThisWords = NumBitWords(size()); 00292 unsigned RHSWords = NumBitWords(RHS.size()); 00293 unsigned i; 00294 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 00295 Bits[i] &= RHS.Bits[i]; 00296 00297 // Any bits that are just in this bitvector become zero, because they aren't 00298 // in the RHS bit vector. Any words only in RHS are ignored because they 00299 // are already zero in the LHS. 00300 for (; i != ThisWords; ++i) 00301 Bits[i] = 0; 00302 00303 return *this; 00304 } 00305 00306 BitVector &operator|=(const BitVector &RHS) { 00307 assert(Size == RHS.Size && "Illegal operation!"); 00308 for (unsigned i = 0; i < NumBitWords(size()); ++i) 00309 Bits[i] |= RHS.Bits[i]; 00310 return *this; 00311 } 00312 00313 BitVector &operator^=(const BitVector &RHS) { 00314 assert(Size == RHS.Size && "Illegal operation!"); 00315 for (unsigned i = 0; i < NumBitWords(size()); ++i) 00316 Bits[i] ^= RHS.Bits[i]; 00317 return *this; 00318 } 00319 00320 // Assignment operator. 00321 const BitVector &operator=(const BitVector &RHS) { 00322 if (this == &RHS) return *this; 00323 00324 Size = RHS.size(); 00325 unsigned RHSWords = NumBitWords(Size); 00326 if (Size <= Capacity * BITWORD_SIZE) { 00327 std::copy(RHS.Bits, &RHS.Bits[RHSWords], Bits); 00328 clear_unused_bits(); 00329 return *this; 00330 } 00331 00332 // Grow the bitvector to have enough elements. 00333 Capacity = RHSWords; 00334 BitWord *NewBits = new BitWord[Capacity]; 00335 std::copy(RHS.Bits, &RHS.Bits[RHSWords], NewBits); 00336 00337 // Destroy the old bits. 00338 delete[] Bits; 00339 Bits = NewBits; 00340 00341 return *this; 00342 } 00343 00344 private: 00345 unsigned NumBitWords(unsigned S) const { 00346 return (S + BITWORD_SIZE-1) / BITWORD_SIZE; 00347 } 00348 00349 // Set the unused bits in the high words. 00350 void set_unused_bits(bool t = true) { 00351 // Set high words first. 00352 unsigned UsedWords = NumBitWords(Size); 00353 if (Capacity > UsedWords) 00354 init_words(&Bits[UsedWords], (Capacity-UsedWords), t); 00355 00356 // Then set any stray high bits of the last used word. 00357 unsigned ExtraBits = Size % BITWORD_SIZE; 00358 if (ExtraBits) { 00359 Bits[UsedWords-1] &= ~(~0L << ExtraBits); 00360 Bits[UsedWords-1] |= (0 - (BitWord)t) << ExtraBits; 00361 } 00362 } 00363 00364 // Clear the unused bits in the high words. 00365 void clear_unused_bits() { 00366 set_unused_bits(false); 00367 } 00368 00369 void grow(unsigned NewSize) { 00370 unsigned OldCapacity = Capacity; 00371 Capacity = NumBitWords(NewSize); 00372 BitWord *NewBits = new BitWord[Capacity]; 00373 00374 // Copy the old bits over. 00375 if (OldCapacity != 0) 00376 std::copy(Bits, &Bits[OldCapacity], NewBits); 00377 00378 // Destroy the old bits. 00379 delete[] Bits; 00380 Bits = NewBits; 00381 00382 clear_unused_bits(); 00383 } 00384 00385 void init_words(BitWord *B, unsigned NumWords, bool t) { 00386 memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); 00387 } 00388 }; 00389 00390 inline BitVector operator&(const BitVector &LHS, const BitVector &RHS) { 00391 BitVector Result(LHS); 00392 Result &= RHS; 00393 return Result; 00394 } 00395 00396 inline BitVector operator|(const BitVector &LHS, const BitVector &RHS) { 00397 BitVector Result(LHS); 00398 Result |= RHS; 00399 return Result; 00400 } 00401 00402 inline BitVector operator^(const BitVector &LHS, const BitVector &RHS) { 00403 BitVector Result(LHS); 00404 Result ^= RHS; 00405 return Result; 00406 } 00407 00408 } // End llvm namespace 00409 #endif