1 //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the BitVector class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_BITVECTOR_H 15 #define LLVM_ADT_BITVECTOR_H 16 17 #include "llvm/Support/MathExtras.h" 18 #include <algorithm> 19 #include <cassert> 20 #include <climits> 21 #include <cstring> 22 23 namespace llvm { 24 25 class BitVector { 26 typedef unsigned long BitWord; 27 28 enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; 29 30 BitWord *Bits; // Actual bits. 31 unsigned Size; // Size of bitvector in bits. 32 unsigned Capacity; // Size of allocated memory in BitWord. 33 34 public: 35 // Encapsulation of a single bit. 36 class reference { 37 friend class BitVector; 38 39 BitWord *WordRef; 40 unsigned BitPos; 41 42 reference(); // Undefined 43 44 public: reference(BitVector & b,unsigned Idx)45 reference(BitVector &b, unsigned Idx) { 46 WordRef = &b.Bits[Idx / BITWORD_SIZE]; 47 BitPos = Idx % BITWORD_SIZE; 48 } 49 ~reference()50 ~reference() {} 51 52 reference &operator=(reference t) { 53 *this = bool(t); 54 return *this; 55 } 56 57 reference& operator=(bool t) { 58 if (t) 59 *WordRef |= 1L << BitPos; 60 else 61 *WordRef &= ~(1L << BitPos); 62 return *this; 63 } 64 65 operator bool() const { 66 return ((*WordRef) & (1L << BitPos)) ? true : false; 67 } 68 }; 69 70 71 /// BitVector default ctor - Creates an empty bitvector. BitVector()72 BitVector() : Size(0), Capacity(0) { 73 Bits = 0; 74 } 75 76 /// BitVector ctor - Creates a bitvector of specified number of bits. All 77 /// bits are initialized to the specified value. Size(s)78 explicit BitVector(unsigned s, bool t = false) : Size(s) { 79 Capacity = NumBitWords(s); 80 Bits = new BitWord[Capacity]; 81 init_words(Bits, Capacity, t); 82 if (t) 83 clear_unused_bits(); 84 } 85 86 /// BitVector copy ctor. BitVector(const BitVector & RHS)87 BitVector(const BitVector &RHS) : Size(RHS.size()) { 88 if (Size == 0) { 89 Bits = 0; 90 Capacity = 0; 91 return; 92 } 93 94 Capacity = NumBitWords(RHS.size()); 95 Bits = new BitWord[Capacity]; 96 std::copy(RHS.Bits, &RHS.Bits[Capacity], Bits); 97 } 98 ~BitVector()99 ~BitVector() { 100 delete[] Bits; 101 } 102 103 /// empty - Tests whether there are no bits in this bitvector. empty()104 bool empty() const { return Size == 0; } 105 106 /// size - Returns the number of bits in this bitvector. size()107 unsigned size() const { return Size; } 108 109 /// count - Returns the number of bits which are set. count()110 unsigned count() const { 111 unsigned NumBits = 0; 112 for (unsigned i = 0; i < NumBitWords(size()); ++i) 113 if (sizeof(BitWord) == 4) 114 NumBits += CountPopulation_32((uint32_t)Bits[i]); 115 else if (sizeof(BitWord) == 8) 116 NumBits += CountPopulation_64(Bits[i]); 117 else 118 assert(0 && "Unsupported!"); 119 return NumBits; 120 } 121 122 /// any - Returns true if any bit is set. any()123 bool any() const { 124 for (unsigned i = 0; i < NumBitWords(size()); ++i) 125 if (Bits[i] != 0) 126 return true; 127 return false; 128 } 129 130 /// none - Returns true if none of the bits are set. none()131 bool none() const { 132 return !any(); 133 } 134 135 /// find_first - Returns the index of the first set bit, -1 if none 136 /// of the bits are set. find_first()137 int find_first() const { 138 for (unsigned i = 0; i < NumBitWords(size()); ++i) 139 if (Bits[i] != 0) { 140 if (sizeof(BitWord) == 4) 141 return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); 142 else if (sizeof(BitWord) == 8) 143 return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 144 else 145 assert(0 && "Unsupported!"); 146 } 147 return -1; 148 } 149 150 /// find_next - Returns the index of the next set bit following the 151 /// "Prev" bit. Returns -1 if the next set bit is not found. find_next(unsigned Prev)152 int find_next(unsigned Prev) const { 153 ++Prev; 154 if (Prev >= Size) 155 return -1; 156 157 unsigned WordPos = Prev / BITWORD_SIZE; 158 unsigned BitPos = Prev % BITWORD_SIZE; 159 BitWord Copy = Bits[WordPos]; 160 // Mask off previous bits. 161 Copy &= ~0L << BitPos; 162 163 if (Copy != 0) { 164 if (sizeof(BitWord) == 4) 165 return WordPos * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Copy); 166 else if (sizeof(BitWord) == 8) 167 return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); 168 else 169 assert(0 && "Unsupported!"); 170 } 171 172 // Check subsequent words. 173 for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i) 174 if (Bits[i] != 0) { 175 if (sizeof(BitWord) == 4) 176 return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); 177 else if (sizeof(BitWord) == 8) 178 return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 179 else 180 assert(0 && "Unsupported!"); 181 } 182 return -1; 183 } 184 185 /// clear - Clear all bits. clear()186 void clear() { 187 Size = 0; 188 } 189 190 /// resize - Grow or shrink the bitvector. 191 void resize(unsigned N, bool t = false) { 192 if (N > Capacity * BITWORD_SIZE) { 193 unsigned OldCapacity = Capacity; 194 grow(N); 195 init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t); 196 } 197 198 // Set any old unused bits that are now included in the BitVector. This 199 // may set bits that are not included in the new vector, but we will clear 200 // them back out below. 201 if (N > Size) 202 set_unused_bits(t); 203 204 // Update the size, and clear out any bits that are now unused 205 unsigned OldSize = Size; 206 Size = N; 207 if (t || N < OldSize) 208 clear_unused_bits(); 209 } 210 reserve(unsigned N)211 void reserve(unsigned N) { 212 if (N > Capacity * BITWORD_SIZE) 213 grow(N); 214 } 215 216 // Set, reset, flip set()217 BitVector &set() { 218 init_words(Bits, Capacity, true); 219 clear_unused_bits(); 220 return *this; 221 } 222 set(unsigned Idx)223 BitVector &set(unsigned Idx) { 224 Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); 225 return *this; 226 } 227 reset()228 BitVector &reset() { 229 init_words(Bits, Capacity, false); 230 return *this; 231 } 232 reset(unsigned Idx)233 BitVector &reset(unsigned Idx) { 234 Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); 235 return *this; 236 } 237 flip()238 BitVector &flip() { 239 for (unsigned i = 0; i < NumBitWords(size()); ++i) 240 Bits[i] = ~Bits[i]; 241 clear_unused_bits(); 242 return *this; 243 } 244 flip(unsigned Idx)245 BitVector &flip(unsigned Idx) { 246 Bits[Idx / BITWORD_SIZE] ^= 1L << (Idx % BITWORD_SIZE); 247 return *this; 248 } 249 250 // No argument flip. 251 BitVector operator~() const { 252 return BitVector(*this).flip(); 253 } 254 255 // Indexing. 256 reference operator[](unsigned Idx) { 257 assert (Idx < Size && "Out-of-bounds Bit access."); 258 return reference(*this, Idx); 259 } 260 261 bool operator[](unsigned Idx) const { 262 assert (Idx < Size && "Out-of-bounds Bit access."); 263 BitWord Mask = 1L << (Idx % BITWORD_SIZE); 264 return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; 265 } 266 test(unsigned Idx)267 bool test(unsigned Idx) const { 268 return (*this)[Idx]; 269 } 270 271 // Comparison operators. 272 bool operator==(const BitVector &RHS) const { 273 unsigned ThisWords = NumBitWords(size()); 274 unsigned RHSWords = NumBitWords(RHS.size()); 275 unsigned i; 276 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 277 if (Bits[i] != RHS.Bits[i]) 278 return false; 279 280 // Verify that any extra words are all zeros. 281 if (i != ThisWords) { 282 for (; i != ThisWords; ++i) 283 if (Bits[i]) 284 return false; 285 } else if (i != RHSWords) { 286 for (; i != RHSWords; ++i) 287 if (RHS.Bits[i]) 288 return false; 289 } 290 return true; 291 } 292 293 bool operator!=(const BitVector &RHS) const { 294 return !(*this == RHS); 295 } 296 297 // Intersection, union, disjoint union. 298 BitVector &operator&=(const BitVector &RHS) { 299 unsigned ThisWords = NumBitWords(size()); 300 unsigned RHSWords = NumBitWords(RHS.size()); 301 unsigned i; 302 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 303 Bits[i] &= RHS.Bits[i]; 304 305 // Any bits that are just in this bitvector become zero, because they aren't 306 // in the RHS bit vector. Any words only in RHS are ignored because they 307 // are already zero in the LHS. 308 for (; i != ThisWords; ++i) 309 Bits[i] = 0; 310 311 return *this; 312 } 313 314 BitVector &operator|=(const BitVector &RHS) { 315 if (size() < RHS.size()) 316 resize(RHS.size()); 317 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 318 Bits[i] |= RHS.Bits[i]; 319 return *this; 320 } 321 322 BitVector &operator^=(const BitVector &RHS) { 323 if (size() < RHS.size()) 324 resize(RHS.size()); 325 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 326 Bits[i] ^= RHS.Bits[i]; 327 return *this; 328 } 329 330 // Assignment operator. 331 const BitVector &operator=(const BitVector &RHS) { 332 if (this == &RHS) return *this; 333 334 Size = RHS.size(); 335 unsigned RHSWords = NumBitWords(Size); 336 if (Size <= Capacity * BITWORD_SIZE) { 337 if (Size) 338 std::copy(RHS.Bits, &RHS.Bits[RHSWords], Bits); 339 clear_unused_bits(); 340 return *this; 341 } 342 343 // Grow the bitvector to have enough elements. 344 Capacity = RHSWords; 345 BitWord *NewBits = new BitWord[Capacity]; 346 std::copy(RHS.Bits, &RHS.Bits[RHSWords], NewBits); 347 348 // Destroy the old bits. 349 delete[] Bits; 350 Bits = NewBits; 351 352 return *this; 353 } 354 swap(BitVector & RHS)355 void swap(BitVector &RHS) { 356 std::swap(Bits, RHS.Bits); 357 std::swap(Size, RHS.Size); 358 std::swap(Capacity, RHS.Capacity); 359 } 360 361 private: NumBitWords(unsigned S)362 unsigned NumBitWords(unsigned S) const { 363 return (S + BITWORD_SIZE-1) / BITWORD_SIZE; 364 } 365 366 // Set the unused bits in the high words. 367 void set_unused_bits(bool t = true) { 368 // Set high words first. 369 unsigned UsedWords = NumBitWords(Size); 370 if (Capacity > UsedWords) 371 init_words(&Bits[UsedWords], (Capacity-UsedWords), t); 372 373 // Then set any stray high bits of the last used word. 374 unsigned ExtraBits = Size % BITWORD_SIZE; 375 if (ExtraBits) { 376 Bits[UsedWords-1] &= ~(~0L << ExtraBits); 377 Bits[UsedWords-1] |= (0 - (BitWord)t) << ExtraBits; 378 } 379 } 380 381 // Clear the unused bits in the high words. clear_unused_bits()382 void clear_unused_bits() { 383 set_unused_bits(false); 384 } 385 grow(unsigned NewSize)386 void grow(unsigned NewSize) { 387 unsigned OldCapacity = Capacity; 388 Capacity = NumBitWords(NewSize); 389 BitWord *NewBits = new BitWord[Capacity]; 390 391 // Copy the old bits over. 392 if (OldCapacity != 0) 393 std::copy(Bits, &Bits[OldCapacity], NewBits); 394 395 // Destroy the old bits. 396 delete[] Bits; 397 Bits = NewBits; 398 399 clear_unused_bits(); 400 } 401 init_words(BitWord * B,unsigned NumWords,bool t)402 void init_words(BitWord *B, unsigned NumWords, bool t) { 403 memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); 404 } 405 }; 406 407 inline BitVector operator&(const BitVector &LHS, const BitVector &RHS) { 408 BitVector Result(LHS); 409 Result &= RHS; 410 return Result; 411 } 412 413 inline BitVector operator|(const BitVector &LHS, const BitVector &RHS) { 414 BitVector Result(LHS); 415 Result |= RHS; 416 return Result; 417 } 418 419 inline BitVector operator^(const BitVector &LHS, const BitVector &RHS) { 420 BitVector Result(LHS); 421 Result ^= RHS; 422 return Result; 423 } 424 425 } // End llvm namespace 426 427 namespace std { 428 /// Implement std::swap in terms of BitVector swap. 429 inline void swap(llvm::BitVector & LHS,llvm::BitVector & RHS)430 swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { 431 LHS.swap(RHS); 432 } 433 } 434 435 #endif 436