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 next set bit following the "Prev" bit. 220 /// Returns -1 if the next set bit is not found. 221 int find_next(unsigned Prev) const { 222 if (isSmall()) { 223 uintptr_t Bits = getSmallBits(); 224 // Mask off previous bits. 225 Bits &= ~uintptr_t(0) << (Prev + 1); 226 if (Bits == 0 || Prev + 1 >= getSmallSize()) 227 return -1; 228 return countTrailingZeros(Bits); 229 } 230 return getPointer()->find_next(Prev); 231 } 232 233 /// Clear all bits. 234 void clear() { 235 if (!isSmall()) 236 delete getPointer(); 237 switchToSmall(0, 0); 238 } 239 240 /// Grow or shrink the bitvector. 241 void resize(unsigned N, bool t = false) { 242 if (!isSmall()) { 243 getPointer()->resize(N, t); 244 } else if (SmallNumDataBits >= N) { 245 uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; 246 setSmallSize(N); 247 setSmallBits(NewBits | getSmallBits()); 248 } else { 249 BitVector *BV = new BitVector(N, t); 250 uintptr_t OldBits = getSmallBits(); 251 for (size_t i = 0, e = getSmallSize(); i != e; ++i) 252 (*BV)[i] = (OldBits >> i) & 1; 253 switchToLarge(BV); 254 } 255 } 256 257 void reserve(unsigned N) { 258 if (isSmall()) { 259 if (N > SmallNumDataBits) { 260 uintptr_t OldBits = getSmallRawBits(); 261 size_t SmallSize = getSmallSize(); 262 BitVector *BV = new BitVector(SmallSize); 263 for (size_t i = 0; i < SmallSize; ++i) 264 if ((OldBits >> i) & 1) 265 BV->set(i); 266 BV->reserve(N); 267 switchToLarge(BV); 268 } 269 } else { 270 getPointer()->reserve(N); 271 } 272 } 273 274 // Set, reset, flip 275 SmallBitVector &set() { 276 if (isSmall()) 277 setSmallBits(~uintptr_t(0)); 278 else 279 getPointer()->set(); 280 return *this; 281 } 282 283 SmallBitVector &set(unsigned Idx) { 284 if (isSmall()) { 285 assert(Idx <= static_cast<unsigned>( 286 std::numeric_limits<uintptr_t>::digits) && 287 "undefined behavior"); 288 setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); 289 } 290 else 291 getPointer()->set(Idx); 292 return *this; 293 } 294 295 /// Efficiently set a range of bits in [I, E) 296 SmallBitVector &set(unsigned I, unsigned E) { 297 assert(I <= E && "Attempted to set backwards range!"); 298 assert(E <= size() && "Attempted to set out-of-bounds range!"); 299 if (I == E) return *this; 300 if (isSmall()) { 301 uintptr_t EMask = ((uintptr_t)1) << E; 302 uintptr_t IMask = ((uintptr_t)1) << I; 303 uintptr_t Mask = EMask - IMask; 304 setSmallBits(getSmallBits() | Mask); 305 } else 306 getPointer()->set(I, E); 307 return *this; 308 } 309 310 SmallBitVector &reset() { 311 if (isSmall()) 312 setSmallBits(0); 313 else 314 getPointer()->reset(); 315 return *this; 316 } 317 318 SmallBitVector &reset(unsigned Idx) { 319 if (isSmall()) 320 setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); 321 else 322 getPointer()->reset(Idx); 323 return *this; 324 } 325 326 /// Efficiently reset a range of bits in [I, E) 327 SmallBitVector &reset(unsigned I, unsigned E) { 328 assert(I <= E && "Attempted to reset backwards range!"); 329 assert(E <= size() && "Attempted to reset out-of-bounds range!"); 330 if (I == E) return *this; 331 if (isSmall()) { 332 uintptr_t EMask = ((uintptr_t)1) << E; 333 uintptr_t IMask = ((uintptr_t)1) << I; 334 uintptr_t Mask = EMask - IMask; 335 setSmallBits(getSmallBits() & ~Mask); 336 } else 337 getPointer()->reset(I, E); 338 return *this; 339 } 340 341 SmallBitVector &flip() { 342 if (isSmall()) 343 setSmallBits(~getSmallBits()); 344 else 345 getPointer()->flip(); 346 return *this; 347 } 348 349 SmallBitVector &flip(unsigned Idx) { 350 if (isSmall()) 351 setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); 352 else 353 getPointer()->flip(Idx); 354 return *this; 355 } 356 357 // No argument flip. 358 SmallBitVector operator~() const { 359 return SmallBitVector(*this).flip(); 360 } 361 362 // Indexing. 363 reference operator[](unsigned Idx) { 364 assert(Idx < size() && "Out-of-bounds Bit access."); 365 return reference(*this, Idx); 366 } 367 368 bool operator[](unsigned Idx) const { 369 assert(Idx < size() && "Out-of-bounds Bit access."); 370 if (isSmall()) 371 return ((getSmallBits() >> Idx) & 1) != 0; 372 return getPointer()->operator[](Idx); 373 } 374 375 bool test(unsigned Idx) const { 376 return (*this)[Idx]; 377 } 378 379 /// Test if any common bits are set. 380 bool anyCommon(const SmallBitVector &RHS) const { 381 if (isSmall() && RHS.isSmall()) 382 return (getSmallBits() & RHS.getSmallBits()) != 0; 383 if (!isSmall() && !RHS.isSmall()) 384 return getPointer()->anyCommon(*RHS.getPointer()); 385 386 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 387 if (test(i) && RHS.test(i)) 388 return true; 389 return false; 390 } 391 392 // Comparison operators. 393 bool operator==(const SmallBitVector &RHS) const { 394 if (size() != RHS.size()) 395 return false; 396 if (isSmall()) 397 return getSmallBits() == RHS.getSmallBits(); 398 else 399 return *getPointer() == *RHS.getPointer(); 400 } 401 402 bool operator!=(const SmallBitVector &RHS) const { 403 return !(*this == RHS); 404 } 405 406 // Intersection, union, disjoint union. 407 SmallBitVector &operator&=(const SmallBitVector &RHS) { 408 resize(std::max(size(), RHS.size())); 409 if (isSmall()) 410 setSmallBits(getSmallBits() & RHS.getSmallBits()); 411 else if (!RHS.isSmall()) 412 getPointer()->operator&=(*RHS.getPointer()); 413 else { 414 SmallBitVector Copy = RHS; 415 Copy.resize(size()); 416 getPointer()->operator&=(*Copy.getPointer()); 417 } 418 return *this; 419 } 420 421 /// Reset bits that are set in RHS. Same as *this &= ~RHS. 422 SmallBitVector &reset(const SmallBitVector &RHS) { 423 if (isSmall() && RHS.isSmall()) 424 setSmallBits(getSmallBits() & ~RHS.getSmallBits()); 425 else if (!isSmall() && !RHS.isSmall()) 426 getPointer()->reset(*RHS.getPointer()); 427 else 428 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 429 if (RHS.test(i)) 430 reset(i); 431 432 return *this; 433 } 434 435 /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any(). 436 bool test(const SmallBitVector &RHS) const { 437 if (isSmall() && RHS.isSmall()) 438 return (getSmallBits() & ~RHS.getSmallBits()) != 0; 439 if (!isSmall() && !RHS.isSmall()) 440 return getPointer()->test(*RHS.getPointer()); 441 442 unsigned i, e; 443 for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 444 if (test(i) && !RHS.test(i)) 445 return true; 446 447 for (e = size(); i != e; ++i) 448 if (test(i)) 449 return true; 450 451 return false; 452 } 453 454 SmallBitVector &operator|=(const SmallBitVector &RHS) { 455 resize(std::max(size(), RHS.size())); 456 if (isSmall()) 457 setSmallBits(getSmallBits() | RHS.getSmallBits()); 458 else if (!RHS.isSmall()) 459 getPointer()->operator|=(*RHS.getPointer()); 460 else { 461 SmallBitVector Copy = RHS; 462 Copy.resize(size()); 463 getPointer()->operator|=(*Copy.getPointer()); 464 } 465 return *this; 466 } 467 468 SmallBitVector &operator^=(const SmallBitVector &RHS) { 469 resize(std::max(size(), RHS.size())); 470 if (isSmall()) 471 setSmallBits(getSmallBits() ^ RHS.getSmallBits()); 472 else if (!RHS.isSmall()) 473 getPointer()->operator^=(*RHS.getPointer()); 474 else { 475 SmallBitVector Copy = RHS; 476 Copy.resize(size()); 477 getPointer()->operator^=(*Copy.getPointer()); 478 } 479 return *this; 480 } 481 482 // Assignment operator. 483 const SmallBitVector &operator=(const SmallBitVector &RHS) { 484 if (isSmall()) { 485 if (RHS.isSmall()) 486 X = RHS.X; 487 else 488 switchToLarge(new BitVector(*RHS.getPointer())); 489 } else { 490 if (!RHS.isSmall()) 491 *getPointer() = *RHS.getPointer(); 492 else { 493 delete getPointer(); 494 X = RHS.X; 495 } 496 } 497 return *this; 498 } 499 500 const SmallBitVector &operator=(SmallBitVector &&RHS) { 501 if (this != &RHS) { 502 clear(); 503 swap(RHS); 504 } 505 return *this; 506 } 507 508 void swap(SmallBitVector &RHS) { 509 std::swap(X, RHS.X); 510 } 511 512 /// Add '1' bits from Mask to this vector. Don't resize. 513 /// This computes "*this |= Mask". 514 void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 515 if (isSmall()) 516 applyMask<true, false>(Mask, MaskWords); 517 else 518 getPointer()->setBitsInMask(Mask, MaskWords); 519 } 520 521 /// Clear any bits in this vector that are set in Mask. Don't resize. 522 /// This computes "*this &= ~Mask". 523 void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 524 if (isSmall()) 525 applyMask<false, false>(Mask, MaskWords); 526 else 527 getPointer()->clearBitsInMask(Mask, MaskWords); 528 } 529 530 /// Add a bit to this vector for every '0' bit in Mask. Don't resize. 531 /// This computes "*this |= ~Mask". 532 void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 533 if (isSmall()) 534 applyMask<true, true>(Mask, MaskWords); 535 else 536 getPointer()->setBitsNotInMask(Mask, MaskWords); 537 } 538 539 /// Clear a bit in this vector for every '0' bit in Mask. Don't resize. 540 /// This computes "*this &= Mask". 541 void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 542 if (isSmall()) 543 applyMask<false, true>(Mask, MaskWords); 544 else 545 getPointer()->clearBitsNotInMask(Mask, MaskWords); 546 } 547 548 private: 549 template <bool AddBits, bool InvertMask> 550 void applyMask(const uint32_t *Mask, unsigned MaskWords) { 551 assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!"); 552 uintptr_t M = Mask[0]; 553 if (NumBaseBits == 64) 554 M |= uint64_t(Mask[1]) << 32; 555 if (InvertMask) 556 M = ~M; 557 if (AddBits) 558 setSmallBits(getSmallBits() | M); 559 else 560 setSmallBits(getSmallBits() & ~M); 561 } 562 }; 563 564 inline SmallBitVector 565 operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { 566 SmallBitVector Result(LHS); 567 Result &= RHS; 568 return Result; 569 } 570 571 inline SmallBitVector 572 operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { 573 SmallBitVector Result(LHS); 574 Result |= RHS; 575 return Result; 576 } 577 578 inline SmallBitVector 579 operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { 580 SmallBitVector Result(LHS); 581 Result ^= RHS; 582 return Result; 583 } 584 585 } // End llvm namespace 586 587 namespace std { 588 /// Implement std::swap in terms of BitVector swap. 589 inline void 590 swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { 591 LHS.swap(RHS); 592 } 593 } 594 595 #endif 596