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