include/llvm/ADT/BitVector.h

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