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