1 //===- llvm/ADT/SmallBitVector.h - 'Normally small' 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 SmallBitVector class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_SMALLBITVECTOR_H 15 #define LLVM_ADT_SMALLBITVECTOR_H 16 17 #include "llvm/ADT/BitVector.h" 18 #include "llvm/Support/MathExtras.h" 19 #include <cassert> 20 21 namespace llvm { 22 23 /// This is a 'bitvector' (really, a variable-sized bit array), optimized for 24 /// the case when the array is small. It contains one pointer-sized field, which 25 /// is directly used as a plain collection of bits when possible, or as a 26 /// pointer to a larger heap-allocated array when necessary. This allows normal 27 /// "small" cases to be fast without losing generality for large inputs. 28 class SmallBitVector { 29 // TODO: In "large" mode, a pointer to a BitVector is used, leading to an 30 // unnecessary level of indirection. It would be more efficient to use a 31 // pointer to memory containing size, allocation size, and the array of bits. 32 uintptr_t X; 33 34 enum { 35 // The number of bits in this class. 36 NumBaseBits = sizeof(uintptr_t) * CHAR_BIT, 37 38 // One bit is used to discriminate between small and large mode. The 39 // remaining bits are used for the small-mode representation. 40 SmallNumRawBits = NumBaseBits - 1, 41 42 // A few more bits are used to store the size of the bit set in small mode. 43 // Theoretically this is a ceil-log2. These bits are encoded in the most 44 // significant bits of the raw bits. 45 SmallNumSizeBits = (NumBaseBits == 32 ? 5 : 46 NumBaseBits == 64 ? 6 : 47 SmallNumRawBits), 48 49 // The remaining bits are used to store the actual set in small mode. 50 SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits 51 }; 52 53 static_assert(NumBaseBits == 64 || NumBaseBits == 32, 54 "Unsupported word size"); 55 56 public: 57 typedef unsigned size_type; 58 // Encapsulation of a single bit. 59 class reference { 60 SmallBitVector &TheVector; 61 unsigned BitPos; 62 63 public: 64 reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} 65 66 reference(const reference&) = default; 67 68 reference& operator=(reference t) { 69 *this = bool(t); 70 return *this; 71 } 72 73 reference& operator=(bool t) { 74 if (t) 75 TheVector.set(BitPos); 76 else 77 TheVector.reset(BitPos); 78 return *this; 79 } 80 81 operator bool() const { 82 return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); 83 } 84 }; 85 86 private: 87 bool isSmall() const { 88 return X & uintptr_t(1); 89 } 90 91 BitVector *getPointer() const { 92 assert(!isSmall()); 93 return reinterpret_cast<BitVector *>(X); 94 } 95 96 void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { 97 X = 1; 98 setSmallSize(NewSize); 99 setSmallBits(NewSmallBits); 100 } 101 102 void switchToLarge(BitVector *BV) { 103 X = reinterpret_cast<uintptr_t>(BV); 104 assert(!isSmall() && "Tried to use an unaligned pointer"); 105 } 106 107 // Return all the bits used for the "small" representation; this includes 108 // bits for the size as well as the element bits. 109 uintptr_t getSmallRawBits() const { 110 assert(isSmall()); 111 return X >> 1; 112 } 113 114 void setSmallRawBits(uintptr_t NewRawBits) { 115 assert(isSmall()); 116 X = (NewRawBits << 1) | uintptr_t(1); 117 } 118 119 // Return the size. 120 size_t getSmallSize() const { 121 return getSmallRawBits() >> SmallNumDataBits; 122 } 123 124 void setSmallSize(size_t Size) { 125 setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); 126 } 127 128 // Return the element bits. 129 uintptr_t getSmallBits() const { 130 return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); 131 } 132 133 void setSmallBits(uintptr_t NewBits) { 134 setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | 135 (getSmallSize() << SmallNumDataBits)); 136 } 137 138 public: 139 /// Creates an empty bitvector. 140 SmallBitVector() : X(1) {} 141 142 /// Creates a bitvector of specified number of bits. All bits are initialized 143 /// to the specified value. 144 explicit SmallBitVector(unsigned s, bool t = false) { 145 if (s <= SmallNumDataBits) 146 switchToSmall(t ? ~uintptr_t(0) : 0, s); 147 else 148 switchToLarge(new BitVector(s, t)); 149 } 150 151 /// SmallBitVector copy ctor. 152 SmallBitVector(const SmallBitVector &RHS) { 153 if (RHS.isSmall()) 154 X = RHS.X; 155 else 156 switchToLarge(new BitVector(*RHS.getPointer())); 157 } 158 159 SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { 160 RHS.X = 1; 161 } 162 163 ~SmallBitVector() { 164 if (!isSmall()) 165 delete getPointer(); 166 } 167 168 /// Tests whether there are no bits in this bitvector. 169 bool empty() const { 170 return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); 171 } 172 173 /// Returns the number of bits in this bitvector. 174 size_t size() const { 175 return isSmall() ? getSmallSize() : getPointer()->size(); 176 } 177 178 /// Returns the number of bits which are set. 179 size_type count() const { 180 if (isSmall()) { 181 uintptr_t Bits = getSmallBits(); 182 return countPopulation(Bits); 183 } 184 return getPointer()->count(); 185 } 186 187 /// Returns true if any bit is set. 188 bool any() const { 189 if (isSmall()) 190 return getSmallBits() != 0; 191 return getPointer()->any(); 192 } 193 194 /// Returns true if all bits are set. 195 bool all() const { 196 if (isSmall()) 197 return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; 198 return getPointer()->all(); 199 } 200 201 /// Returns true if none of the bits are set. 202 bool none() const { 203 if (isSmall()) 204 return getSmallBits() == 0; 205 return getPointer()->none(); 206 } 207 208 /// Returns the index of the first set bit, -1 if none of the bits are set. 209 int find_first() const { 210 if (isSmall()) { 211 uintptr_t Bits = getSmallBits(); 212 if (Bits == 0) 213 return -1; 214 return countTrailingZeros(Bits); 215 } 216 return getPointer()->find_first(); 217 } 218 219 /// Returns the index of the first unset bit, -1 if all of the bits are set. 220 int find_first_unset() const { 221 if (isSmall()) { 222 if (count() == getSmallSize()) 223 return -1; 224 225 uintptr_t Bits = getSmallBits(); 226 return countTrailingOnes(Bits); 227 } 228 return getPointer()->find_first_unset(); 229 } 230 231 /// Returns the index of the next set bit following the "Prev" bit. 232 /// Returns -1 if the next set bit is not found. 233 int find_next(unsigned Prev) const { 234 if (isSmall()) { 235 uintptr_t Bits = getSmallBits(); 236 // Mask off previous bits. 237 Bits &= ~uintptr_t(0) << (Prev + 1); 238 if (Bits == 0 || Prev + 1 >= getSmallSize()) 239 return -1; 240 return countTrailingZeros(Bits); 241 } 242 return getPointer()->find_next(Prev); 243 } 244 245 /// Returns the index of the next unset bit following the "Prev" bit. 246 /// Returns -1 if the next unset bit is not found. 247 int find_next_unset(unsigned Prev) const { 248 if (isSmall()) { 249 ++Prev; 250 uintptr_t Bits = getSmallBits(); 251 // Mask in previous bits. 252 uintptr_t Mask = (1 << Prev) - 1; 253 Bits |= Mask; 254 255 if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize()) 256 return -1; 257 return countTrailingOnes(Bits); 258 } 259 return getPointer()->find_next_unset(Prev); 260 } 261 262 /// Clear all bits. 263 void clear() { 264 if (!isSmall()) 265 delete getPointer(); 266 switchToSmall(0, 0); 267 } 268 269 /// Grow or shrink the bitvector. 270 void resize(unsigned N, bool t = false) { 271 if (!isSmall()) { 272 getPointer()->resize(N, t); 273 } else if (SmallNumDataBits >= N) { 274 uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; 275 setSmallSize(N); 276 setSmallBits(NewBits | getSmallBits()); 277 } else { 278 BitVector *BV = new BitVector(N, t); 279 uintptr_t OldBits = getSmallBits(); 280 for (size_t i = 0, e = getSmallSize(); i != e; ++i) 281 (*BV)[i] = (OldBits >> i) & 1; 282 switchToLarge(BV); 283 } 284 } 285 286 void reserve(unsigned N) { 287 if (isSmall()) { 288 if (N > SmallNumDataBits) { 289 uintptr_t OldBits = getSmallRawBits(); 290 size_t SmallSize = getSmallSize(); 291 BitVector *BV = new BitVector(SmallSize); 292 for (size_t i = 0; i < SmallSize; ++i) 293 if ((OldBits >> i) & 1) 294 BV->set(i); 295 BV->reserve(N); 296 switchToLarge(BV); 297 } 298 } else { 299 getPointer()->reserve(N); 300 } 301 } 302 303 // Set, reset, flip 304 SmallBitVector &set() { 305 if (isSmall()) 306 setSmallBits(~uintptr_t(0)); 307 else 308 getPointer()->set(); 309 return *this; 310 } 311 312 SmallBitVector &set(unsigned Idx) { 313 if (isSmall()) { 314 assert(Idx <= static_cast<unsigned>( 315 std::numeric_limits<uintptr_t>::digits) && 316 "undefined behavior"); 317 setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); 318 } 319 else 320 getPointer()->set(Idx); 321 return *this; 322 } 323 324 /// Efficiently set a range of bits in [I, E) 325 SmallBitVector &set(unsigned I, unsigned E) { 326 assert(I <= E && "Attempted to set backwards range!"); 327 assert(E <= size() && "Attempted to set out-of-bounds range!"); 328 if (I == E) return *this; 329 if (isSmall()) { 330 uintptr_t EMask = ((uintptr_t)1) << E; 331 uintptr_t IMask = ((uintptr_t)1) << I; 332 uintptr_t Mask = EMask - IMask; 333 setSmallBits(getSmallBits() | Mask); 334 } else 335 getPointer()->set(I, E); 336 return *this; 337 } 338 339 SmallBitVector &reset() { 340 if (isSmall()) 341 setSmallBits(0); 342 else 343 getPointer()->reset(); 344 return *this; 345 } 346 347 SmallBitVector &reset(unsigned Idx) { 348 if (isSmall()) 349 setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); 350 else 351 getPointer()->reset(Idx); 352 return *this; 353 } 354 355 /// Efficiently reset a range of bits in [I, E) 356 SmallBitVector &reset(unsigned I, unsigned E) { 357 assert(I <= E && "Attempted to reset backwards range!"); 358 assert(E <= size() && "Attempted to reset out-of-bounds range!"); 359 if (I == E) return *this; 360 if (isSmall()) { 361 uintptr_t EMask = ((uintptr_t)1) << E; 362 uintptr_t IMask = ((uintptr_t)1) << I; 363 uintptr_t Mask = EMask - IMask; 364 setSmallBits(getSmallBits() & ~Mask); 365 } else 366 getPointer()->reset(I, E); 367 return *this; 368 } 369 370 SmallBitVector &flip() { 371 if (isSmall()) 372 setSmallBits(~getSmallBits()); 373 else 374 getPointer()->flip(); 375 return *this; 376 } 377 378 SmallBitVector &flip(unsigned Idx) { 379 if (isSmall()) 380 setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); 381 else 382 getPointer()->flip(Idx); 383 return *this; 384 } 385 386 // No argument flip. 387 SmallBitVector operator~() const { 388 return SmallBitVector(*this).flip(); 389 } 390 391 // Indexing. 392 reference operator[](unsigned Idx) { 393 assert(Idx < size() && "Out-of-bounds Bit access."); 394 return reference(*this, Idx); 395 } 396 397 bool operator[](unsigned Idx) const { 398 assert(Idx < size() && "Out-of-bounds Bit access."); 399 if (isSmall()) 400 return ((getSmallBits() >> Idx) & 1) != 0; 401 return getPointer()->operator[](Idx); 402 } 403 404 bool test(unsigned Idx) const { 405 return (*this)[Idx]; 406 } 407 408 /// Test if any common bits are set. 409 bool anyCommon(const SmallBitVector &RHS) const { 410 if (isSmall() && RHS.isSmall()) 411 return (getSmallBits() & RHS.getSmallBits()) != 0; 412 if (!isSmall() && !RHS.isSmall()) 413 return getPointer()->anyCommon(*RHS.getPointer()); 414 415 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 416 if (test(i) && RHS.test(i)) 417 return true; 418 return false; 419 } 420 421 // Comparison operators. 422 bool operator==(const SmallBitVector &RHS) const { 423 if (size() != RHS.size()) 424 return false; 425 if (isSmall()) 426 return getSmallBits() == RHS.getSmallBits(); 427 else 428 return *getPointer() == *RHS.getPointer(); 429 } 430 431 bool operator!=(const SmallBitVector &RHS) const { 432 return !(*this == RHS); 433 } 434 435 // Intersection, union, disjoint union. 436 SmallBitVector &operator&=(const SmallBitVector &RHS) { 437 resize(std::max(size(), RHS.size())); 438 if (isSmall()) 439 setSmallBits(getSmallBits() & RHS.getSmallBits()); 440 else if (!RHS.isSmall()) 441 getPointer()->operator&=(*RHS.getPointer()); 442 else { 443 SmallBitVector Copy = RHS; 444 Copy.resize(size()); 445 getPointer()->operator&=(*Copy.getPointer()); 446 } 447 return *this; 448 } 449 450 /// Reset bits that are set in RHS. Same as *this &= ~RHS. 451 SmallBitVector &reset(const SmallBitVector &RHS) { 452 if (isSmall() && RHS.isSmall()) 453 setSmallBits(getSmallBits() & ~RHS.getSmallBits()); 454 else if (!isSmall() && !RHS.isSmall()) 455 getPointer()->reset(*RHS.getPointer()); 456 else 457 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 458 if (RHS.test(i)) 459 reset(i); 460 461 return *this; 462 } 463 464 /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any(). 465 bool test(const SmallBitVector &RHS) const { 466 if (isSmall() && RHS.isSmall()) 467 return (getSmallBits() & ~RHS.getSmallBits()) != 0; 468 if (!isSmall() && !RHS.isSmall()) 469 return getPointer()->test(*RHS.getPointer()); 470 471 unsigned i, e; 472 for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 473 if (test(i) && !RHS.test(i)) 474 return true; 475 476 for (e = size(); i != e; ++i) 477 if (test(i)) 478 return true; 479 480 return false; 481 } 482 483 SmallBitVector &operator|=(const SmallBitVector &RHS) { 484 resize(std::max(size(), RHS.size())); 485 if (isSmall()) 486 setSmallBits(getSmallBits() | RHS.getSmallBits()); 487 else if (!RHS.isSmall()) 488 getPointer()->operator|=(*RHS.getPointer()); 489 else { 490 SmallBitVector Copy = RHS; 491 Copy.resize(size()); 492 getPointer()->operator|=(*Copy.getPointer()); 493 } 494 return *this; 495 } 496 497 SmallBitVector &operator^=(const SmallBitVector &RHS) { 498 resize(std::max(size(), RHS.size())); 499 if (isSmall()) 500 setSmallBits(getSmallBits() ^ RHS.getSmallBits()); 501 else if (!RHS.isSmall()) 502 getPointer()->operator^=(*RHS.getPointer()); 503 else { 504 SmallBitVector Copy = RHS; 505 Copy.resize(size()); 506 getPointer()->operator^=(*Copy.getPointer()); 507 } 508 return *this; 509 } 510 511 // Assignment operator. 512 const SmallBitVector &operator=(const SmallBitVector &RHS) { 513 if (isSmall()) { 514 if (RHS.isSmall()) 515 X = RHS.X; 516 else 517 switchToLarge(new BitVector(*RHS.getPointer())); 518 } else { 519 if (!RHS.isSmall()) 520 *getPointer() = *RHS.getPointer(); 521 else { 522 delete getPointer(); 523 X = RHS.X; 524 } 525 } 526 return *this; 527 } 528 529 const SmallBitVector &operator=(SmallBitVector &&RHS) { 530 if (this != &RHS) { 531 clear(); 532 swap(RHS); 533 } 534 return *this; 535 } 536 537 void swap(SmallBitVector &RHS) { 538 std::swap(X, RHS.X); 539 } 540 541 /// Add '1' bits from Mask to this vector. Don't resize. 542 /// This computes "*this |= Mask". 543 void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 544 if (isSmall()) 545 applyMask<true, false>(Mask, MaskWords); 546 else 547 getPointer()->setBitsInMask(Mask, MaskWords); 548 } 549 550 /// Clear any bits in this vector that are set in Mask. Don't resize. 551 /// This computes "*this &= ~Mask". 552 void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 553 if (isSmall()) 554 applyMask<false, false>(Mask, MaskWords); 555 else 556 getPointer()->clearBitsInMask(Mask, MaskWords); 557 } 558 559 /// Add a bit to this vector for every '0' bit in Mask. Don't resize. 560 /// This computes "*this |= ~Mask". 561 void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 562 if (isSmall()) 563 applyMask<true, true>(Mask, MaskWords); 564 else 565 getPointer()->setBitsNotInMask(Mask, MaskWords); 566 } 567 568 /// Clear a bit in this vector for every '0' bit in Mask. Don't resize. 569 /// This computes "*this &= Mask". 570 void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 571 if (isSmall()) 572 applyMask<false, true>(Mask, MaskWords); 573 else 574 getPointer()->clearBitsNotInMask(Mask, MaskWords); 575 } 576 577 private: 578 template <bool AddBits, bool InvertMask> 579 void applyMask(const uint32_t *Mask, unsigned MaskWords) { 580 assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!"); 581 uintptr_t M = Mask[0]; 582 if (NumBaseBits == 64) 583 M |= uint64_t(Mask[1]) << 32; 584 if (InvertMask) 585 M = ~M; 586 if (AddBits) 587 setSmallBits(getSmallBits() | M); 588 else 589 setSmallBits(getSmallBits() & ~M); 590 } 591 }; 592 593 inline SmallBitVector 594 operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { 595 SmallBitVector Result(LHS); 596 Result &= RHS; 597 return Result; 598 } 599 600 inline SmallBitVector 601 operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { 602 SmallBitVector Result(LHS); 603 Result |= RHS; 604 return Result; 605 } 606 607 inline SmallBitVector 608 operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { 609 SmallBitVector Result(LHS); 610 Result ^= RHS; 611 return Result; 612 } 613 614 } // End llvm namespace 615 616 namespace std { 617 /// Implement std::swap in terms of BitVector swap. 618 inline void 619 swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { 620 LHS.swap(RHS); 621 } 622 } 623 624 #endif 625