include/llvm/ADT/BitVector.h

   1 //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Evan Cheng and is distributed under
   6 // the University of Illinois Open Source 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/MathExtras.h"
  18
  19 namespace llvm {
  20
  21 class BitVector {
  22   typedef unsigned long BitWord;
  23
  24   enum { BITS_PER_WORD = sizeof(BitWord) * 8 };
  25
  26   BitWord  *Bits;        // Actual bits.
  27   unsigned Size;         // Size of bitvector in bits.
  28   unsigned Capacity;     // Size of allocated memory in BitWord.
  29
  30 public:
  31   // Encapsulation of a single bit.
  32   class reference {
  33     friend class BitVector;
  34
  35     BitWord *WordRef;
  36     unsigned BitPos;
  37
  38     reference();  // Undefined
  39
  40   public:
  41     reference(BitVector &b, unsigned Idx) {
  42       WordRef = &b.Bits[Idx / BITS_PER_WORD];
  43       BitPos = Idx % BITS_PER_WORD;
  44     }
  45
  46     ~reference() {}
  47
  48     reference& operator=(bool t) {
  49       if (t)
  50         *WordRef |= 1 << BitPos;
  51       else
  52         *WordRef &= ~(1 << BitPos);
  53       return *this;
  54     }
  55
  56     reference& operator=(const reference& rhs) {
  57       if (*rhs.WordRef & (1 << rhs.BitPos))
  58         *WordRef |= 1 << BitPos;
  59       else
  60         *WordRef &= ~(1 << BitPos);
  61       return *this;
  62     }
  63
  64     operator bool() const {
  65       return (*WordRef) & (1 << BitPos);
  66     }
  67   };
  68
  69
  70   /// BitVector default ctor - Creates an empty bitvector.
  71   BitVector() : Size(0), Capacity(0) {
  72     Bits = new BitWord[0];
  73   }
  74
  75   /// BitVector ctor - Creates a bitvector of specified number of bits. All
  76   /// bits are initialized to false;
  77   BitVector(unsigned s) : Size(s) {
  78     Capacity = NumBitWords(s);
  79     Bits = new BitWord[Capacity];
  80     init_words(Bits, Capacity, false);
  81   }
  82
  83   /// BitVector ctor - Creates a bitvector of specified number of bits. All
  84   /// bits are initialized to the specified value.
  85   BitVector(unsigned s, bool t) : Size(s) {
  86     Capacity = NumBitWords(s);
  87     Bits = new BitWord[Capacity];
  88     init_words(Bits, Capacity, t);
  89   }
  90
  91   /// BitVector copy ctor.
  92   BitVector(const BitVector &RHS) : Size(RHS.size()) {
  93     Capacity = NumBitWords(RHS.size());
  94     Bits = new BitWord[Capacity];
  95     std::copy(RHS.Bits, &RHS.Bits[Capacity], Bits);
  96   }
  97
  98   /// size - Returns the number of bits in this bitvector.
  99   unsigned size() const { return Size; }
 100
 101   /// count - Returns the number of bits which are set.
 102   unsigned count() const {
 103     unsigned NumBits = 0;
 104     for (unsigned i = 0; i < NumBitWords(size()); ++i)
 105       NumBits = CountPopulation_32(Bits[i]);
 106     return NumBits;
 107   }
 108
 109   /// any - Returns true if any bit is set.
 110   bool any() const {
 111     for (unsigned i = 0; i < NumBitWords(size()); ++i)
 112       if (Bits[i] != 0)
 113         return true;
 114     return false;
 115   }
 116
 117   /// none - Returns true if none of the bits are set.
 118   bool none() const {
 119     return !any();
 120   }
 121
 122   /// find_first - Returns the index of the first set bit, -1 if none
 123   /// of the bits are set.
 124   int find_first() const {
 125     for (unsigned i = 0; i < NumBitWords(size()); ++i)
 126       if (Bits[i] != 0)
 127         return i * BITS_PER_WORD + CountTrailingZeros_32(Bits[i]);
 128     return -1;
 129   }
 130
 131   /// find_next - Returns the index of the next set bit following the
 132   /// "Prev" bit. Returns -1 if the next set bit is not found.
 133   int find_next(unsigned Prev) const {
 134     ++Prev;
 135     if (Prev >= Size)
 136       return -1;
 137
 138     unsigned WordPos = Prev / BITS_PER_WORD;
 139     unsigned BitPos = Prev % BITS_PER_WORD;
 140     BitWord Copy = Bits[WordPos];
 141     // Mask off previous bits.
 142     Copy &= ~0 << BitPos;
 143
 144     if (Copy != 0)
 145       return WordPos * BITS_PER_WORD + CountTrailingZeros_32(Copy);
 146
 147     // Check subsequent words.
 148     for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i)
 149       if (Bits[i] != 0)
 150         return i * BITS_PER_WORD + CountTrailingZeros_32(Bits[i]);
 151     return -1;
 152   }
 153
 154   /// clear - Clear all bits.
 155   void clear() {
 156     delete[] Bits;
 157     Bits = new BitWord[0];
 158     Size = Capacity = 0;
 159   }
 160
 161   /// resize - Grow or shrink the bitvector.
 162   void resize(unsigned N) {
 163     if (N > Capacity * BITS_PER_WORD) {
 164       unsigned OldCapacity = Capacity;
 165       grow(N);
 166       init_words(&Bits[OldCapacity], (Capacity-OldCapacity), false);
 167     }
 168     Size = N;
 169   }
 170
 171   void resize(unsigned N, bool t) {
 172     if (N > Capacity * BITS_PER_WORD) {
 173       unsigned OldCapacity = Capacity;
 174       grow(N);
 175       init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t);
 176     }
 177     Size = N;
 178   }
 179
 180   void reserve(unsigned N) {
 181     if (N > Capacity * BITS_PER_WORD)
 182       grow(N);
 183   }
 184
 185   // Set, reset, flip
 186   BitVector &set() {
 187     init_words(Bits, Capacity, true);
 188     clear_unused_bits();
 189     return *this;
 190   }
 191
 192   BitVector &set(unsigned Idx) {
 193     Bits[Idx / BITS_PER_WORD] |= 1 << (Idx % BITS_PER_WORD);
 194     return *this;
 195   }
 196
 197   BitVector &reset() {
 198     init_words(Bits, Capacity, false);
 199     return *this;
 200   }
 201
 202   BitVector &reset(unsigned Idx) {
 203     Bits[Idx / BITS_PER_WORD] &= ~(1 << (Idx % BITS_PER_WORD));
 204     return *this;
 205   }
 206
 207   BitVector &flip() {
 208     for (unsigned i = 0; i < NumBitWords(size()); ++i)
 209       Bits[i] = ~Bits[i];
 210     clear_unused_bits();
 211     return *this;
 212   }
 213
 214   BitVector &flip(unsigned Idx) {
 215     Bits[Idx / BITS_PER_WORD] ^= 1 << (Idx % BITS_PER_WORD);
 216     return *this;
 217   }
 218
 219   // No argument flip.
 220   BitVector operator~() const {
 221     return BitVector(*this).flip();
 222   }
 223
 224   // Indexing.
 225   reference operator[](unsigned Idx) {
 226     return reference(*this, Idx);
 227   }
 228
 229   bool operator[](unsigned Idx) const {
 230     BitWord Mask = 1 << (Idx % BITS_PER_WORD);
 231     return (Bits[Idx / BITS_PER_WORD] & Mask) != 0;
 232   }
 233
 234   bool test(unsigned Idx) const {
 235     return (*this)[Idx];
 236   }
 237
 238   // Comparison operators.
 239   bool operator==(const BitVector &RHS) const {
 240     assert(Size == RHS.Size && "Illegal operation!");
 241     for (unsigned i = 0; i < NumBitWords(size()); ++i)
 242       if (Bits[i] != RHS.Bits[i])
 243         return false;
 244     return true;
 245   }
 246
 247   bool operator!=(const BitVector &RHS) const {
 248     return !(*this == RHS);
 249   }
 250
 251   // Intersection, union, disjoint union.
 252   BitVector operator&=(const BitVector &RHS) {
 253     assert(Size == RHS.Size && "Illegal operation!");
 254     for (unsigned i = 0; i < NumBitWords(size()); ++i)
 255       Bits[i] &= RHS.Bits[i];
 256     return *this;
 257   }
 258
 259   BitVector operator|=(const BitVector &RHS) {
 260     assert(Size == RHS.Size && "Illegal operation!");
 261     for (unsigned i = 0; i < NumBitWords(size()); ++i)
 262       Bits[i] |= RHS.Bits[i];
 263     return *this;
 264   }
 265
 266   BitVector operator^=(const BitVector &RHS) {
 267     assert(Size == RHS.Size && "Illegal operation!");
 268     for (unsigned i = 0; i < NumBitWords(size()); ++i)
 269       Bits[i] ^= RHS.Bits[i];
 270     return *this;
 271   }
 272
 273   // Assignment operator.
 274   const BitVector &operator=(const BitVector &RHS) {
 275     if (this == &RHS) return *this;
 276
 277     unsigned RHSWords = NumBitWords(RHS.size());
 278     unsigned NewSize = RHS.size();
 279     if (NewSize <= Capacity * BITS_PER_WORD) {
 280       std::copy(RHS.Bits, &RHS.Bits[RHSWords], Bits);
 281       Size = NewSize;
 282       clear_unused_bits();
 283       return *this;
 284     }
 285
 286     // Grow the bitvector to have enough elements.
 287     Capacity = NumBitWords(NewSize);
 288     BitWord *NewBits = new BitWord[Capacity];
 289     std::copy(RHS.Bits, &RHS.Bits[RHSWords], NewBits);
 290
 291     // Destroy the old bits.
 292     delete[] Bits;
 293     Bits = NewBits;
 294
 295     return *this;
 296   }
 297
 298 private:
 299   unsigned NumBitWords(unsigned S) const {
 300     return (S + BITS_PER_WORD-1) / BITS_PER_WORD;
 301   }
 302
 303   // Clear the unused top bits in the high word.
 304   void clear_unused_bits() {
 305     unsigned ExtraBits = Size % BITS_PER_WORD;
 306     Bits[Size / BITS_PER_WORD] &= ~(~0 << ExtraBits);
 307   }
 308
 309   void grow(unsigned NewSize) {
 310     unsigned OldCapacity = Capacity;
 311     Capacity = NumBitWords(NewSize);
 312     BitWord *NewBits = new BitWord[Capacity];
 313
 314     // Copy the old bits over.
 315     if (OldCapacity != 0)
 316       std::copy(Bits, &Bits[OldCapacity], NewBits);
 317
 318     // Destroy the old bits.
 319     delete[] Bits;
 320     Bits = NewBits;
 321   }
 322
 323   void init_words(BitWord *B, unsigned NumWords, bool t) {
 324     memset(B, 0 - (int)t, NumWords*sizeof(BitWord));
 325   }
 326 };
 327
 328 inline BitVector operator&(const BitVector &LHS, const BitVector &RHS) {
 329   BitVector Result(LHS);
 330   Result &= RHS;
 331   return Result;
 332 }
 333
 334 inline BitVector operator|(const BitVector &LHS, const BitVector &RHS) {
 335   BitVector Result(LHS);
 336   Result |= RHS;
 337   return Result;
 338 }
 339
 340 inline BitVector operator^(const BitVector &LHS, const BitVector &RHS) {
 341   BitVector Result(LHS);
 342   Result ^= RHS;
 343   return Result;
 344 }
 345
 346 } // End llvm namespace
 347 #endif