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 25namespace llvm { 26 27class 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 36public: 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: 48 reference(BitVector &b, unsigned Idx) { 49 WordRef = &b.Bits[Idx / BITWORD_SIZE]; 50 BitPos = Idx % BITWORD_SIZE; 51 } 52 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. 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. 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. 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 102 BitVector(BitVector &&RHS) 103 : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) { 104 RHS.Bits = nullptr; 105 } 106 107 ~BitVector() { 108 std::free(Bits); 109 } 110 111 /// empty - Tests whether there are no bits in this bitvector. 112 bool empty() const { return Size == 0; } 113 114 /// size - Returns the number of bits in this bitvector. 115 size_type size() const { return Size; } 116 117 /// count - Returns the number of bits which are set. 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. 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. 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. 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. 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. 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. 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 229 void reserve(unsigned N) { 230 if (N > Capacity * BITWORD_SIZE) 231 grow(N); 232 } 233 234 // Set, reset, flip 235 BitVector &set() { 236 init_words(Bits, Capacity, true); 237 clear_unused_bits(); 238 return *this; 239 } 240 241 BitVector &set(unsigned Idx) { 242 Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE); 243 return *this; 244 } 245 246 /// set - Efficiently set a range of bits in [I, E) 247 BitVector &set(unsigned I, unsigned E) { 248 assert(I <= E && "Attempted to set backwards range!"); 249 assert(E <= size() && "Attempted to set out-of-bounds range!"); 250 251 if (I == E) return *this; 252 253 if (I / BITWORD_SIZE == E / BITWORD_SIZE) { 254 BitWord EMask = 1UL << (E % BITWORD_SIZE); 255 BitWord IMask = 1UL << (I % BITWORD_SIZE); 256 BitWord Mask = EMask - IMask; 257 Bits[I / BITWORD_SIZE] |= Mask; 258 return *this; 259 } 260 261 BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); 262 Bits[I / BITWORD_SIZE] |= PrefixMask; 263 I = RoundUpToAlignment(I, BITWORD_SIZE); 264 265 for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) 266 Bits[I / BITWORD_SIZE] = ~0UL; 267 268 BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; 269 if (I < E) 270 Bits[I / BITWORD_SIZE] |= PostfixMask; 271 272 return *this; 273 } 274 275 BitVector &reset() { 276 init_words(Bits, Capacity, false); 277 return *this; 278 } 279 280 BitVector &reset(unsigned Idx) { 281 Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE)); 282 return *this; 283 } 284 285 /// reset - Efficiently reset a range of bits in [I, E) 286 BitVector &reset(unsigned I, unsigned E) { 287 assert(I <= E && "Attempted to reset backwards range!"); 288 assert(E <= size() && "Attempted to reset out-of-bounds range!"); 289 290 if (I == E) return *this; 291 292 if (I / BITWORD_SIZE == E / BITWORD_SIZE) { 293 BitWord EMask = 1UL << (E % BITWORD_SIZE); 294 BitWord IMask = 1UL << (I % BITWORD_SIZE); 295 BitWord Mask = EMask - IMask; 296 Bits[I / BITWORD_SIZE] &= ~Mask; 297 return *this; 298 } 299 300 BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); 301 Bits[I / BITWORD_SIZE] &= ~PrefixMask; 302 I = RoundUpToAlignment(I, BITWORD_SIZE); 303 304 for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) 305 Bits[I / BITWORD_SIZE] = 0UL; 306 307 BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; 308 if (I < E) 309 Bits[I / BITWORD_SIZE] &= ~PostfixMask; 310 311 return *this; 312 } 313 314 BitVector &flip() { 315 for (unsigned i = 0; i < NumBitWords(size()); ++i) 316 Bits[i] = ~Bits[i]; 317 clear_unused_bits(); 318 return *this; 319 } 320 321 BitVector &flip(unsigned Idx) { 322 Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE); 323 return *this; 324 } 325 326 // Indexing. 327 reference operator[](unsigned Idx) { 328 assert (Idx < Size && "Out-of-bounds Bit access."); 329 return reference(*this, Idx); 330 } 331 332 bool operator[](unsigned Idx) const { 333 assert (Idx < Size && "Out-of-bounds Bit access."); 334 BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE); 335 return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; 336 } 337 338 bool test(unsigned Idx) const { 339 return (*this)[Idx]; 340 } 341 342 /// Test if any common bits are set. 343 bool anyCommon(const BitVector &RHS) const { 344 unsigned ThisWords = NumBitWords(size()); 345 unsigned RHSWords = NumBitWords(RHS.size()); 346 for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i) 347 if (Bits[i] & RHS.Bits[i]) 348 return true; 349 return false; 350 } 351 352 // Comparison operators. 353 bool operator==(const BitVector &RHS) const { 354 unsigned ThisWords = NumBitWords(size()); 355 unsigned RHSWords = NumBitWords(RHS.size()); 356 unsigned i; 357 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 358 if (Bits[i] != RHS.Bits[i]) 359 return false; 360 361 // Verify that any extra words are all zeros. 362 if (i != ThisWords) { 363 for (; i != ThisWords; ++i) 364 if (Bits[i]) 365 return false; 366 } else if (i != RHSWords) { 367 for (; i != RHSWords; ++i) 368 if (RHS.Bits[i]) 369 return false; 370 } 371 return true; 372 } 373 374 bool operator!=(const BitVector &RHS) const { 375 return !(*this == RHS); 376 } 377 378 /// Intersection, union, disjoint union. 379 BitVector &operator&=(const BitVector &RHS) { 380 unsigned ThisWords = NumBitWords(size()); 381 unsigned RHSWords = NumBitWords(RHS.size()); 382 unsigned i; 383 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 384 Bits[i] &= RHS.Bits[i]; 385 386 // Any bits that are just in this bitvector become zero, because they aren't 387 // in the RHS bit vector. Any words only in RHS are ignored because they 388 // are already zero in the LHS. 389 for (; i != ThisWords; ++i) 390 Bits[i] = 0; 391 392 return *this; 393 } 394 395 /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. 396 BitVector &reset(const BitVector &RHS) { 397 unsigned ThisWords = NumBitWords(size()); 398 unsigned RHSWords = NumBitWords(RHS.size()); 399 unsigned i; 400 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 401 Bits[i] &= ~RHS.Bits[i]; 402 return *this; 403 } 404 405 /// test - Check if (This - RHS) is zero. 406 /// This is the same as reset(RHS) and any(). 407 bool test(const BitVector &RHS) const { 408 unsigned ThisWords = NumBitWords(size()); 409 unsigned RHSWords = NumBitWords(RHS.size()); 410 unsigned i; 411 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 412 if ((Bits[i] & ~RHS.Bits[i]) != 0) 413 return true; 414 415 for (; i != ThisWords ; ++i) 416 if (Bits[i] != 0) 417 return true; 418 419 return false; 420 } 421 422 BitVector &operator|=(const BitVector &RHS) { 423 if (size() < RHS.size()) 424 resize(RHS.size()); 425 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 426 Bits[i] |= RHS.Bits[i]; 427 return *this; 428 } 429 430 BitVector &operator^=(const BitVector &RHS) { 431 if (size() < RHS.size()) 432 resize(RHS.size()); 433 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 434 Bits[i] ^= RHS.Bits[i]; 435 return *this; 436 } 437 438 // Assignment operator. 439 const BitVector &operator=(const BitVector &RHS) { 440 if (this == &RHS) return *this; 441 442 Size = RHS.size(); 443 unsigned RHSWords = NumBitWords(Size); 444 if (Size <= Capacity * BITWORD_SIZE) { 445 if (Size) 446 std::memcpy(Bits, RHS.Bits, RHSWords * sizeof(BitWord)); 447 clear_unused_bits(); 448 return *this; 449 } 450 451 // Grow the bitvector to have enough elements. 452 Capacity = RHSWords; 453 BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 454 std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord)); 455 456 // Destroy the old bits. 457 std::free(Bits); 458 Bits = NewBits; 459 460 return *this; 461 } 462 463 const BitVector &operator=(BitVector &&RHS) { 464 if (this == &RHS) return *this; 465 466 std::free(Bits); 467 Bits = RHS.Bits; 468 Size = RHS.Size; 469 Capacity = RHS.Capacity; 470 471 RHS.Bits = nullptr; 472 473 return *this; 474 } 475 476 void swap(BitVector &RHS) { 477 std::swap(Bits, RHS.Bits); 478 std::swap(Size, RHS.Size); 479 std::swap(Capacity, RHS.Capacity); 480 } 481 482 //===--------------------------------------------------------------------===// 483 // Portable bit mask operations. 484 //===--------------------------------------------------------------------===// 485 // 486 // These methods all operate on arrays of uint32_t, each holding 32 bits. The 487 // fixed word size makes it easier to work with literal bit vector constants 488 // in portable code. 489 // 490 // The LSB in each word is the lowest numbered bit. The size of a portable 491 // bit mask is always a whole multiple of 32 bits. If no bit mask size is 492 // given, the bit mask is assumed to cover the entire BitVector. 493 494 /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. 495 /// This computes "*this |= Mask". 496 void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 497 applyMask<true, false>(Mask, MaskWords); 498 } 499 500 /// clearBitsInMask - Clear any bits in this vector that are set in Mask. 501 /// Don't resize. This computes "*this &= ~Mask". 502 void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 503 applyMask<false, false>(Mask, MaskWords); 504 } 505 506 /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. 507 /// Don't resize. This computes "*this |= ~Mask". 508 void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 509 applyMask<true, true>(Mask, MaskWords); 510 } 511 512 /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. 513 /// Don't resize. This computes "*this &= Mask". 514 void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 515 applyMask<false, true>(Mask, MaskWords); 516 } 517 518private: 519 unsigned NumBitWords(unsigned S) const { 520 return (S + BITWORD_SIZE-1) / BITWORD_SIZE; 521 } 522 523 // Set the unused bits in the high words. 524 void set_unused_bits(bool t = true) { 525 // Set high words first. 526 unsigned UsedWords = NumBitWords(Size); 527 if (Capacity > UsedWords) 528 init_words(&Bits[UsedWords], (Capacity-UsedWords), t); 529 530 // Then set any stray high bits of the last used word. 531 unsigned ExtraBits = Size % BITWORD_SIZE; 532 if (ExtraBits) { 533 BitWord ExtraBitMask = ~0UL << ExtraBits; 534 if (t) 535 Bits[UsedWords-1] |= ExtraBitMask; 536 else 537 Bits[UsedWords-1] &= ~ExtraBitMask; 538 } 539 } 540 541 // Clear the unused bits in the high words. 542 void clear_unused_bits() { 543 set_unused_bits(false); 544 } 545 546 void grow(unsigned NewSize) { 547 Capacity = std::max(NumBitWords(NewSize), Capacity * 2); 548 Bits = (BitWord *)std::realloc(Bits, Capacity * sizeof(BitWord)); 549 550 clear_unused_bits(); 551 } 552 553 void init_words(BitWord *B, unsigned NumWords, bool t) { 554 memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); 555 } 556 557 template<bool AddBits, bool InvertMask> 558 void applyMask(const uint32_t *Mask, unsigned MaskWords) { 559 assert(BITWORD_SIZE % 32 == 0 && "Unsupported BitWord size."); 560 MaskWords = std::min(MaskWords, (size() + 31) / 32); 561 const unsigned Scale = BITWORD_SIZE / 32; 562 unsigned i; 563 for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) { 564 BitWord BW = Bits[i]; 565 // This inner loop should unroll completely when BITWORD_SIZE > 32. 566 for (unsigned b = 0; b != BITWORD_SIZE; b += 32) { 567 uint32_t M = *Mask++; 568 if (InvertMask) M = ~M; 569 if (AddBits) BW |= BitWord(M) << b; 570 else BW &= ~(BitWord(M) << b); 571 } 572 Bits[i] = BW; 573 } 574 for (unsigned b = 0; MaskWords; b += 32, --MaskWords) { 575 uint32_t M = *Mask++; 576 if (InvertMask) M = ~M; 577 if (AddBits) Bits[i] |= BitWord(M) << b; 578 else Bits[i] &= ~(BitWord(M) << b); 579 } 580 if (AddBits) 581 clear_unused_bits(); 582 } 583}; 584 585} // End llvm namespace 586 587namespace std { 588 /// Implement std::swap in terms of BitVector swap. 589 inline void 590 swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { 591 LHS.swap(RHS); 592 } 593} 594 595#endif 596