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/Compiler.h" 18 #include "llvm/Support/ErrorHandling.h" 19 #include "llvm/Support/MathExtras.h" 20 #include <algorithm> 21 #include <cassert> 22 #include <climits> 23 #include <cstdlib> 24 25 namespace llvm { 26 27 class BitVector { 28 typedef unsigned long BitWord; 29 30 enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; 31 32 BitWord *Bits; // Actual bits. 33 unsigned Size; // Size of bitvector in bits. 34 unsigned Capacity; // Size of allocated memory in BitWord. 35 36 public: 37 typedef unsigned size_type; 38 // Encapsulation of a single bit. 39 class reference { 40 friend class BitVector; 41 42 BitWord *WordRef; 43 unsigned BitPos; 44 45 reference(); // Undefined 46 47 public: reference(BitVector & b,unsigned Idx)48 reference(BitVector &b, unsigned Idx) { 49 WordRef = &b.Bits[Idx / BITWORD_SIZE]; 50 BitPos = Idx % BITWORD_SIZE; 51 } 52 ~reference()53 ~reference() {} 54 55 reference &operator=(reference t) { 56 *this = bool(t); 57 return *this; 58 } 59 60 reference& operator=(bool t) { 61 if (t) 62 *WordRef |= BitWord(1) << BitPos; 63 else 64 *WordRef &= ~(BitWord(1) << BitPos); 65 return *this; 66 } 67 68 operator bool() const { 69 return ((*WordRef) & (BitWord(1) << BitPos)) ? true : false; 70 } 71 }; 72 73 74 /// BitVector default ctor - Creates an empty bitvector. BitVector()75 BitVector() : Size(0), Capacity(0) { 76 Bits = nullptr; 77 } 78 79 /// BitVector ctor - Creates a bitvector of specified number of bits. All 80 /// bits are initialized to the specified value. Size(s)81 explicit BitVector(unsigned s, bool t = false) : Size(s) { 82 Capacity = NumBitWords(s); 83 Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 84 init_words(Bits, Capacity, t); 85 if (t) 86 clear_unused_bits(); 87 } 88 89 /// BitVector copy ctor. BitVector(const BitVector & RHS)90 BitVector(const BitVector &RHS) : Size(RHS.size()) { 91 if (Size == 0) { 92 Bits = nullptr; 93 Capacity = 0; 94 return; 95 } 96 97 Capacity = NumBitWords(RHS.size()); 98 Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 99 std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord)); 100 } 101 BitVector(BitVector && RHS)102 BitVector(BitVector &&RHS) 103 : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) { 104 RHS.Bits = nullptr; 105 } 106 ~BitVector()107 ~BitVector() { 108 std::free(Bits); 109 } 110 111 /// empty - Tests whether there are no bits in this bitvector. empty()112 bool empty() const { return Size == 0; } 113 114 /// size - Returns the number of bits in this bitvector. size()115 size_type size() const { return Size; } 116 117 /// count - Returns the number of bits which are set. count()118 size_type count() const { 119 unsigned NumBits = 0; 120 for (unsigned i = 0; i < NumBitWords(size()); ++i) 121 if (sizeof(BitWord) == 4) 122 NumBits += CountPopulation_32((uint32_t)Bits[i]); 123 else if (sizeof(BitWord) == 8) 124 NumBits += CountPopulation_64(Bits[i]); 125 else 126 llvm_unreachable("Unsupported!"); 127 return NumBits; 128 } 129 130 /// any - Returns true if any bit is set. any()131 bool any() const { 132 for (unsigned i = 0; i < NumBitWords(size()); ++i) 133 if (Bits[i] != 0) 134 return true; 135 return false; 136 } 137 138 /// all - Returns true if all bits are set. all()139 bool all() const { 140 for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i) 141 if (Bits[i] != ~0UL) 142 return false; 143 144 // If bits remain check that they are ones. The unused bits are always zero. 145 if (unsigned Remainder = Size % BITWORD_SIZE) 146 return Bits[Size / BITWORD_SIZE] == (1UL << Remainder) - 1; 147 148 return true; 149 } 150 151 /// none - Returns true if none of the bits are set. none()152 bool none() const { 153 return !any(); 154 } 155 156 /// find_first - Returns the index of the first set bit, -1 if none 157 /// of the bits are set. find_first()158 int find_first() const { 159 for (unsigned i = 0; i < NumBitWords(size()); ++i) 160 if (Bits[i] != 0) { 161 if (sizeof(BitWord) == 4) 162 return i * BITWORD_SIZE + countTrailingZeros((uint32_t)Bits[i]); 163 if (sizeof(BitWord) == 8) 164 return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); 165 llvm_unreachable("Unsupported!"); 166 } 167 return -1; 168 } 169 170 /// find_next - Returns the index of the next set bit following the 171 /// "Prev" bit. Returns -1 if the next set bit is not found. find_next(unsigned Prev)172 int find_next(unsigned Prev) const { 173 ++Prev; 174 if (Prev >= Size) 175 return -1; 176 177 unsigned WordPos = Prev / BITWORD_SIZE; 178 unsigned BitPos = Prev % BITWORD_SIZE; 179 BitWord Copy = Bits[WordPos]; 180 // Mask off previous bits. 181 Copy &= ~0UL << BitPos; 182 183 if (Copy != 0) { 184 if (sizeof(BitWord) == 4) 185 return WordPos * BITWORD_SIZE + countTrailingZeros((uint32_t)Copy); 186 if (sizeof(BitWord) == 8) 187 return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); 188 llvm_unreachable("Unsupported!"); 189 } 190 191 // Check subsequent words. 192 for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i) 193 if (Bits[i] != 0) { 194 if (sizeof(BitWord) == 4) 195 return i * BITWORD_SIZE + countTrailingZeros((uint32_t)Bits[i]); 196 if (sizeof(BitWord) == 8) 197 return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); 198 llvm_unreachable("Unsupported!"); 199 } 200 return -1; 201 } 202 203 /// clear - Clear all bits. clear()204 void clear() { 205 Size = 0; 206 } 207 208 /// resize - Grow or shrink the bitvector. 209 void resize(unsigned N, bool t = false) { 210 if (N > Capacity * BITWORD_SIZE) { 211 unsigned OldCapacity = Capacity; 212 grow(N); 213 init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t); 214 } 215 216 // Set any old unused bits that are now included in the BitVector. This 217 // may set bits that are not included in the new vector, but we will clear 218 // them back out below. 219 if (N > Size) 220 set_unused_bits(t); 221 222 // Update the size, and clear out any bits that are now unused 223 unsigned OldSize = Size; 224 Size = N; 225 if (t || N < OldSize) 226 clear_unused_bits(); 227 } 228 reserve(unsigned N)229 void reserve(unsigned N) { 230 if (N > Capacity * BITWORD_SIZE) 231 grow(N); 232 } 233 234 // Set, reset, flip set()235 BitVector &set() { 236 init_words(Bits, Capacity, true); 237 clear_unused_bits(); 238 return *this; 239 } 240 set(unsigned Idx)241 BitVector &set(unsigned Idx) { 242 assert(Bits && "Bits never allocated"); 243 Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE); 244 return *this; 245 } 246 247 /// set - Efficiently set a range of bits in [I, E) set(unsigned I,unsigned E)248 BitVector &set(unsigned I, unsigned E) { 249 assert(I <= E && "Attempted to set backwards range!"); 250 assert(E <= size() && "Attempted to set out-of-bounds range!"); 251 252 if (I == E) return *this; 253 254 if (I / BITWORD_SIZE == E / BITWORD_SIZE) { 255 BitWord EMask = 1UL << (E % BITWORD_SIZE); 256 BitWord IMask = 1UL << (I % BITWORD_SIZE); 257 BitWord Mask = EMask - IMask; 258 Bits[I / BITWORD_SIZE] |= Mask; 259 return *this; 260 } 261 262 BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); 263 Bits[I / BITWORD_SIZE] |= PrefixMask; 264 I = RoundUpToAlignment(I, BITWORD_SIZE); 265 266 for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) 267 Bits[I / BITWORD_SIZE] = ~0UL; 268 269 BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; 270 if (I < E) 271 Bits[I / BITWORD_SIZE] |= PostfixMask; 272 273 return *this; 274 } 275 reset()276 BitVector &reset() { 277 init_words(Bits, Capacity, false); 278 return *this; 279 } 280 reset(unsigned Idx)281 BitVector &reset(unsigned Idx) { 282 Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE)); 283 return *this; 284 } 285 286 /// reset - Efficiently reset a range of bits in [I, E) reset(unsigned I,unsigned E)287 BitVector &reset(unsigned I, unsigned E) { 288 assert(I <= E && "Attempted to reset backwards range!"); 289 assert(E <= size() && "Attempted to reset out-of-bounds range!"); 290 291 if (I == E) return *this; 292 293 if (I / BITWORD_SIZE == E / BITWORD_SIZE) { 294 BitWord EMask = 1UL << (E % BITWORD_SIZE); 295 BitWord IMask = 1UL << (I % BITWORD_SIZE); 296 BitWord Mask = EMask - IMask; 297 Bits[I / BITWORD_SIZE] &= ~Mask; 298 return *this; 299 } 300 301 BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); 302 Bits[I / BITWORD_SIZE] &= ~PrefixMask; 303 I = RoundUpToAlignment(I, BITWORD_SIZE); 304 305 for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) 306 Bits[I / BITWORD_SIZE] = 0UL; 307 308 BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; 309 if (I < E) 310 Bits[I / BITWORD_SIZE] &= ~PostfixMask; 311 312 return *this; 313 } 314 flip()315 BitVector &flip() { 316 for (unsigned i = 0; i < NumBitWords(size()); ++i) 317 Bits[i] = ~Bits[i]; 318 clear_unused_bits(); 319 return *this; 320 } 321 flip(unsigned Idx)322 BitVector &flip(unsigned Idx) { 323 Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE); 324 return *this; 325 } 326 327 // Indexing. 328 reference operator[](unsigned Idx) { 329 assert (Idx < Size && "Out-of-bounds Bit access."); 330 return reference(*this, Idx); 331 } 332 333 bool operator[](unsigned Idx) const { 334 assert (Idx < Size && "Out-of-bounds Bit access."); 335 BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE); 336 return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; 337 } 338 test(unsigned Idx)339 bool test(unsigned Idx) const { 340 return (*this)[Idx]; 341 } 342 343 /// Test if any common bits are set. anyCommon(const BitVector & RHS)344 bool anyCommon(const BitVector &RHS) const { 345 unsigned ThisWords = NumBitWords(size()); 346 unsigned RHSWords = NumBitWords(RHS.size()); 347 for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i) 348 if (Bits[i] & RHS.Bits[i]) 349 return true; 350 return false; 351 } 352 353 // Comparison operators. 354 bool operator==(const BitVector &RHS) const { 355 unsigned ThisWords = NumBitWords(size()); 356 unsigned RHSWords = NumBitWords(RHS.size()); 357 unsigned i; 358 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 359 if (Bits[i] != RHS.Bits[i]) 360 return false; 361 362 // Verify that any extra words are all zeros. 363 if (i != ThisWords) { 364 for (; i != ThisWords; ++i) 365 if (Bits[i]) 366 return false; 367 } else if (i != RHSWords) { 368 for (; i != RHSWords; ++i) 369 if (RHS.Bits[i]) 370 return false; 371 } 372 return true; 373 } 374 375 bool operator!=(const BitVector &RHS) const { 376 return !(*this == RHS); 377 } 378 379 /// Intersection, union, disjoint union. 380 BitVector &operator&=(const BitVector &RHS) { 381 unsigned ThisWords = NumBitWords(size()); 382 unsigned RHSWords = NumBitWords(RHS.size()); 383 unsigned i; 384 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 385 Bits[i] &= RHS.Bits[i]; 386 387 // Any bits that are just in this bitvector become zero, because they aren't 388 // in the RHS bit vector. Any words only in RHS are ignored because they 389 // are already zero in the LHS. 390 for (; i != ThisWords; ++i) 391 Bits[i] = 0; 392 393 return *this; 394 } 395 396 /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. reset(const BitVector & RHS)397 BitVector &reset(const BitVector &RHS) { 398 unsigned ThisWords = NumBitWords(size()); 399 unsigned RHSWords = NumBitWords(RHS.size()); 400 unsigned i; 401 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 402 Bits[i] &= ~RHS.Bits[i]; 403 return *this; 404 } 405 406 /// test - Check if (This - RHS) is zero. 407 /// This is the same as reset(RHS) and any(). test(const BitVector & RHS)408 bool test(const BitVector &RHS) const { 409 unsigned ThisWords = NumBitWords(size()); 410 unsigned RHSWords = NumBitWords(RHS.size()); 411 unsigned i; 412 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 413 if ((Bits[i] & ~RHS.Bits[i]) != 0) 414 return true; 415 416 for (; i != ThisWords ; ++i) 417 if (Bits[i] != 0) 418 return true; 419 420 return false; 421 } 422 423 BitVector &operator|=(const BitVector &RHS) { 424 if (size() < RHS.size()) 425 resize(RHS.size()); 426 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 427 Bits[i] |= RHS.Bits[i]; 428 return *this; 429 } 430 431 BitVector &operator^=(const BitVector &RHS) { 432 if (size() < RHS.size()) 433 resize(RHS.size()); 434 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 435 Bits[i] ^= RHS.Bits[i]; 436 return *this; 437 } 438 439 // Assignment operator. 440 const BitVector &operator=(const BitVector &RHS) { 441 if (this == &RHS) return *this; 442 443 Size = RHS.size(); 444 unsigned RHSWords = NumBitWords(Size); 445 if (Size <= Capacity * BITWORD_SIZE) { 446 if (Size) 447 std::memcpy(Bits, RHS.Bits, RHSWords * sizeof(BitWord)); 448 clear_unused_bits(); 449 return *this; 450 } 451 452 // Grow the bitvector to have enough elements. 453 Capacity = RHSWords; 454 assert(Capacity > 0 && "negative capacity?"); 455 BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 456 std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord)); 457 458 // Destroy the old bits. 459 std::free(Bits); 460 Bits = NewBits; 461 462 return *this; 463 } 464 465 const BitVector &operator=(BitVector &&RHS) { 466 if (this == &RHS) return *this; 467 468 std::free(Bits); 469 Bits = RHS.Bits; 470 Size = RHS.Size; 471 Capacity = RHS.Capacity; 472 473 RHS.Bits = nullptr; 474 475 return *this; 476 } 477 swap(BitVector & RHS)478 void swap(BitVector &RHS) { 479 std::swap(Bits, RHS.Bits); 480 std::swap(Size, RHS.Size); 481 std::swap(Capacity, RHS.Capacity); 482 } 483 484 //===--------------------------------------------------------------------===// 485 // Portable bit mask operations. 486 //===--------------------------------------------------------------------===// 487 // 488 // These methods all operate on arrays of uint32_t, each holding 32 bits. The 489 // fixed word size makes it easier to work with literal bit vector constants 490 // in portable code. 491 // 492 // The LSB in each word is the lowest numbered bit. The size of a portable 493 // bit mask is always a whole multiple of 32 bits. If no bit mask size is 494 // given, the bit mask is assumed to cover the entire BitVector. 495 496 /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. 497 /// This computes "*this |= Mask". 498 void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 499 applyMask<true, false>(Mask, MaskWords); 500 } 501 502 /// clearBitsInMask - Clear any bits in this vector that are set in Mask. 503 /// Don't resize. This computes "*this &= ~Mask". 504 void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 505 applyMask<false, false>(Mask, MaskWords); 506 } 507 508 /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. 509 /// Don't resize. This computes "*this |= ~Mask". 510 void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 511 applyMask<true, true>(Mask, MaskWords); 512 } 513 514 /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. 515 /// Don't resize. This computes "*this &= Mask". 516 void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 517 applyMask<false, true>(Mask, MaskWords); 518 } 519 520 private: NumBitWords(unsigned S)521 unsigned NumBitWords(unsigned S) const { 522 return (S + BITWORD_SIZE-1) / BITWORD_SIZE; 523 } 524 525 // Set the unused bits in the high words. 526 void set_unused_bits(bool t = true) { 527 // Set high words first. 528 unsigned UsedWords = NumBitWords(Size); 529 if (Capacity > UsedWords) 530 init_words(&Bits[UsedWords], (Capacity-UsedWords), t); 531 532 // Then set any stray high bits of the last used word. 533 unsigned ExtraBits = Size % BITWORD_SIZE; 534 if (ExtraBits) { 535 BitWord ExtraBitMask = ~0UL << ExtraBits; 536 if (t) 537 Bits[UsedWords-1] |= ExtraBitMask; 538 else 539 Bits[UsedWords-1] &= ~ExtraBitMask; 540 } 541 } 542 543 // Clear the unused bits in the high words. clear_unused_bits()544 void clear_unused_bits() { 545 set_unused_bits(false); 546 } 547 grow(unsigned NewSize)548 void grow(unsigned NewSize) { 549 Capacity = std::max(NumBitWords(NewSize), Capacity * 2); 550 assert(Capacity > 0 && "realloc-ing zero space"); 551 Bits = (BitWord *)std::realloc(Bits, Capacity * sizeof(BitWord)); 552 553 clear_unused_bits(); 554 } 555 init_words(BitWord * B,unsigned NumWords,bool t)556 void init_words(BitWord *B, unsigned NumWords, bool t) { 557 memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); 558 } 559 560 template<bool AddBits, bool InvertMask> applyMask(const uint32_t * Mask,unsigned MaskWords)561 void applyMask(const uint32_t *Mask, unsigned MaskWords) { 562 assert(BITWORD_SIZE % 32 == 0 && "Unsupported BitWord size."); 563 MaskWords = std::min(MaskWords, (size() + 31) / 32); 564 const unsigned Scale = BITWORD_SIZE / 32; 565 unsigned i; 566 for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) { 567 BitWord BW = Bits[i]; 568 // This inner loop should unroll completely when BITWORD_SIZE > 32. 569 for (unsigned b = 0; b != BITWORD_SIZE; b += 32) { 570 uint32_t M = *Mask++; 571 if (InvertMask) M = ~M; 572 if (AddBits) BW |= BitWord(M) << b; 573 else BW &= ~(BitWord(M) << b); 574 } 575 Bits[i] = BW; 576 } 577 for (unsigned b = 0; MaskWords; b += 32, --MaskWords) { 578 uint32_t M = *Mask++; 579 if (InvertMask) M = ~M; 580 if (AddBits) Bits[i] |= BitWord(M) << b; 581 else Bits[i] &= ~(BitWord(M) << b); 582 } 583 if (AddBits) 584 clear_unused_bits(); 585 } 586 }; 587 588 } // End llvm namespace 589 590 namespace std { 591 /// Implement std::swap in terms of BitVector swap. 592 inline void swap(llvm::BitVector & LHS,llvm::BitVector & RHS)593 swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { 594 LHS.swap(RHS); 595 } 596 } 597 598 #endif 599