include/llvm/ADT/SmallBitVector.h

   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/ADT/PointerIntPair.h"
  19 #include "llvm/Support/MathExtras.h"
  20 #include <cassert>
  21
  22 namespace llvm {
  23
  24 /// SmallBitVector - This is a 'bitvector' (really, a variable-sized bit array),
  25 /// optimized for the case when the array is small.  It contains one
  26 /// pointer-sized field, which is directly used as a plain collection of bits
  27 /// when possible, or as a pointer to a larger heap-allocated array when
  28 /// necessary.  This allows normal "small" cases to be fast without losing
  29 /// generality for large inputs.
  30 ///
  31 class SmallBitVector {
  32   // TODO: In "large" mode, a pointer to a BitVector is used, leading to an
  33   // unnecessary level of indirection. It would be more efficient to use a
  34   // pointer to memory containing size, allocation size, and the array of bits.
  35   PointerIntPair<BitVector *, 1, uintptr_t> X;
  36
  37   // The number of bits in this class.
  38   static const size_t NumBaseBits = sizeof(X) * CHAR_BIT;
  39
  40   // One bit is used to discriminate between small and large mode. The
  41   // remaining bits are used for the small-mode representation.
  42   static const size_t SmallNumRawBits = NumBaseBits - 1;
  43
  44   // A few more bits are used to store the size of the bit set in small mode.
  45   // Theoretically this is a ceil-log2. These bits are encoded in the most
  46   // significant bits of the raw bits.
  47   static const size_t SmallNumSizeBits = (NumBaseBits == 32 ? 5 :
  48                                           NumBaseBits == 64 ? 6 :
  49                                           SmallNumRawBits);
  50
  51   // The remaining bits are used to store the actual set in small mode.
  52   static const size_t SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits;
  53
  54   bool isSmall() const {
  55     return X.getInt();
  56   }
  57
  58   void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
  59     X.setInt(true);
  60     setSmallSize(NewSize);
  61     setSmallBits(NewSmallBits);
  62   }
  63
  64   void switchToLarge(BitVector *BV) {
  65     X.setInt(false);
  66     X.setPointer(BV);
  67   }
  68
  69   // Return all the bits used for the "small" representation; this includes
  70   // bits for the size as well as the element bits.
  71   uintptr_t getSmallRawBits() const {
  72     return reinterpret_cast<uintptr_t>(X.getPointer()) >> 1;
  73   }
  74
  75   void setSmallRawBits(uintptr_t NewRawBits) {
  76     return X.setPointer(reinterpret_cast<BitVector *>(NewRawBits << 1));
  77   }
  78
  79   // Return the size.
  80   size_t getSmallSize() const {
  81     return getSmallRawBits() >> SmallNumDataBits;
  82   }
  83
  84   void setSmallSize(size_t Size) {
  85     setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
  86   }
  87
  88   // Return the element bits.
  89   uintptr_t getSmallBits() const {
  90     return getSmallRawBits() & ~(~uintptr_t(0) << SmallNumDataBits);
  91   }
  92
  93   void setSmallBits(uintptr_t NewBits) {
  94     setSmallRawBits((getSmallRawBits() & (~uintptr_t(0) << SmallNumDataBits)) |
  95                     (NewBits & ~(~uintptr_t(0) << getSmallSize())));
  96   }
  97
  98 public:
  99   /// SmallBitVector default ctor - Creates an empty bitvector.
 100   SmallBitVector() : X(0, 1) {}
 101
 102   /// SmallBitVector ctor - Creates a bitvector of specified number of bits. All
 103   /// bits are initialized to the specified value.
 104   explicit SmallBitVector(unsigned s, bool t = false) : X(0, 1) {
 105     if (s <= SmallNumRawBits)
 106       switchToSmall(t ? ~uintptr_t(0) : 0, s);
 107     else
 108       switchToLarge(new BitVector(s, t));
 109   }
 110
 111   /// SmallBitVector copy ctor.
 112   SmallBitVector(const SmallBitVector &RHS) {
 113     if (RHS.isSmall())
 114       X = RHS.X;
 115     else
 116       switchToLarge(new BitVector(*RHS.X.getPointer()));
 117   }
 118
 119   ~SmallBitVector() {
 120     if (!isSmall())
 121       delete X.getPointer();
 122   }
 123
 124   /// empty - Tests whether there are no bits in this bitvector.
 125   bool empty() const {
 126     return isSmall() ? getSmallSize() == 0 : X.getPointer()->empty();
 127   }
 128
 129   /// size - Returns the number of bits in this bitvector.
 130   size_t size() const {
 131     return isSmall() ? getSmallSize() : X.getPointer()->size();
 132   }
 133
 134   /// count - Returns the number of bits which are set.
 135   unsigned count() const {
 136     if (isSmall()) {
 137       uintptr_t Bits = getSmallBits();
 138       if (sizeof(uintptr_t) * CHAR_BIT == 32)
 139         return CountPopulation_32(Bits);
 140       if (sizeof(uintptr_t) * CHAR_BIT == 64)
 141         return CountPopulation_64(Bits);
 142       assert(0 && "Unsupported!");
 143     }
 144     return X.getPointer()->count();
 145   }
 146
 147   /// any - Returns true if any bit is set.
 148   bool any() const {
 149     if (isSmall())
 150       return getSmallBits() != 0;
 151     return X.getPointer()->any();
 152   }
 153
 154   /// none - Returns true if none of the bits are set.
 155   bool none() const {
 156     if (isSmall())
 157       return getSmallBits() == 0;
 158     return X.getPointer()->none();
 159   }
 160
 161   /// find_first - Returns the index of the first set bit, -1 if none
 162   /// of the bits are set.
 163   int find_first() const {
 164     if (isSmall()) {
 165       uintptr_t Bits = getSmallBits();
 166       if (sizeof(uintptr_t) * CHAR_BIT == 32)
 167         return CountTrailingZeros_32(Bits);
 168       if (sizeof(uintptr_t) * CHAR_BIT == 64)
 169         return CountTrailingZeros_64(Bits);
 170       assert(0 && "Unsupported!");
 171     }
 172     return X.getPointer()->find_first();
 173   }
 174
 175   /// find_next - Returns the index of the next set bit following the
 176   /// "Prev" bit. Returns -1 if the next set bit is not found.
 177   int find_next(unsigned Prev) const {
 178     if (isSmall()) {
 179       uintptr_t Bits = getSmallBits();
 180       // Mask off previous bits.
 181       Bits &= ~uintptr_t(0) << Prev;
 182       if (sizeof(uintptr_t) * CHAR_BIT == 32)
 183         return CountTrailingZeros_32(Bits);
 184       if (sizeof(uintptr_t) * CHAR_BIT == 64)
 185         return CountTrailingZeros_64(Bits);
 186       assert(0 && "Unsupported!");
 187     }
 188     return X.getPointer()->find_next(Prev);
 189   }
 190
 191   /// clear - Clear all bits.
 192   void clear() {
 193     if (!isSmall())
 194       delete X.getPointer();
 195     switchToSmall(0, 0);
 196   }
 197
 198   /// resize - Grow or shrink the bitvector.
 199   void resize(unsigned N, bool t = false) {
 200     if (!isSmall()) {
 201       X.getPointer()->resize(N, t);
 202     } else if (getSmallSize() >= N) {
 203       setSmallSize(N);
 204       setSmallBits(getSmallBits());
 205     } else {
 206       BitVector *BV = new BitVector(N, t);
 207       uintptr_t OldBits = getSmallBits();
 208       for (size_t i = 0, e = getSmallSize(); i != e; ++i)
 209         (*BV)[i] = (OldBits >> i) & 1;
 210       switchToLarge(BV);
 211     }
 212   }
 213
 214   void reserve(unsigned N) {
 215     if (isSmall()) {
 216       if (N > SmallNumDataBits) {
 217         uintptr_t OldBits = getSmallRawBits();
 218         size_t SmallSize = getSmallSize();
 219         BitVector *BV = new BitVector(SmallSize);
 220         for (size_t i = 0; i < SmallSize; ++i)
 221           if ((OldBits >> i) & 1)
 222             BV->set(i);
 223         BV->reserve(N);
 224         switchToLarge(BV);
 225       }
 226     } else {
 227       X.getPointer()->reserve(N);
 228     }
 229   }
 230
 231   // Set, reset, flip
 232   SmallBitVector &set() {
 233     if (isSmall())
 234       setSmallBits(~uintptr_t(0));
 235     else
 236       X.getPointer()->set();
 237     return *this;
 238   }
 239
 240   SmallBitVector &set(unsigned Idx) {
 241     if (isSmall())
 242       setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
 243     else
 244       X.getPointer()->set(Idx);
 245     return *this;
 246   }
 247
 248   SmallBitVector &reset() {
 249     if (isSmall())
 250       setSmallBits(0);
 251     else
 252       X.getPointer()->reset();
 253     return *this;
 254   }
 255
 256   SmallBitVector &reset(unsigned Idx) {
 257     if (isSmall())
 258       setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
 259     else
 260       X.getPointer()->reset(Idx);
 261     return *this;
 262   }
 263
 264   SmallBitVector &flip() {
 265     if (isSmall())
 266       setSmallBits(~getSmallBits());
 267     else
 268       X.getPointer()->flip();
 269     return *this;
 270   }
 271
 272   SmallBitVector &flip(unsigned Idx) {
 273     if (isSmall())
 274       setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
 275     else
 276       X.getPointer()->flip(Idx);
 277     return *this;
 278   }
 279
 280   // No argument flip.
 281   SmallBitVector operator~() const {
 282     return SmallBitVector(*this).flip();
 283   }
 284
 285   // Indexing.
 286   // TODO: Add an index operator which returns a "reference" (proxy class).
 287   bool operator[](unsigned Idx) const {
 288     assert(Idx < size() && "Out-of-bounds Bit access.");
 289     if (isSmall())
 290       return ((getSmallBits() >> Idx) & 1) != 0;
 291     return X.getPointer()->operator[](Idx);
 292   }
 293
 294   bool test(unsigned Idx) const {
 295     return (*this)[Idx];
 296   }
 297
 298   // Comparison operators.
 299   bool operator==(const SmallBitVector &RHS) const {
 300     if (size() != RHS.size())
 301       return false;
 302     if (isSmall())
 303       return getSmallBits() == RHS.getSmallBits();
 304     else
 305       return *X.getPointer() == *RHS.X.getPointer();
 306   }
 307
 308   bool operator!=(const SmallBitVector &RHS) const {
 309     return !(*this == RHS);
 310   }
 311
 312   // Intersection, union, disjoint union.
 313   BitVector &operator&=(const SmallBitVector &RHS); // TODO: implement
 314
 315   BitVector &operator|=(const SmallBitVector &RHS); // TODO: implement
 316
 317   BitVector &operator^=(const SmallBitVector &RHS); // TODO: implement
 318
 319   // Assignment operator.
 320   const SmallBitVector &operator=(const SmallBitVector &RHS) {
 321     if (isSmall()) {
 322       if (RHS.isSmall())
 323         X = RHS.X;
 324       else
 325         switchToLarge(new BitVector(*RHS.X.getPointer()));
 326     } else {
 327       if (!RHS.isSmall())
 328         *X.getPointer() = *RHS.X.getPointer();
 329       else {
 330         delete X.getPointer();
 331         X = RHS.X;
 332       }
 333     }
 334     return *this;
 335   }
 336
 337   void swap(SmallBitVector &RHS) {
 338     std::swap(X, RHS.X);
 339   }
 340 };
 341
 342 inline SmallBitVector
 343 operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
 344   SmallBitVector Result(LHS);
 345   Result &= RHS;
 346   return Result;
 347 }
 348
 349 inline SmallBitVector
 350 operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
 351   SmallBitVector Result(LHS);
 352   Result |= RHS;
 353   return Result;
 354 }
 355
 356 inline SmallBitVector
 357 operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
 358   SmallBitVector Result(LHS);
 359   Result ^= RHS;
 360   return Result;
 361 }
 362
 363 } // End llvm namespace
 364
 365 namespace std {
 366   /// Implement std::swap in terms of BitVector swap.
 367   inline void
 368   swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
 369     LHS.swap(RHS);
 370   }
 371 }
 372
 373 #endif