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