LLVM API Documentation

BitVector.h

Go to the documentation of this file.
00001 //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the BitVector class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_ADT_BITVECTOR_H
00015 #define LLVM_ADT_BITVECTOR_H
00016 
00017 #include "llvm/Support/MathExtras.h"
00018 #include <algorithm>
00019 #include <cassert>
00020 #include <climits>
00021 #include <cstring>
00022 
00023 namespace llvm {
00024 
00025 class BitVector {
00026   typedef unsigned long BitWord;
00027 
00028   enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
00029 
00030   BitWord  *Bits;        // Actual bits.
00031   unsigned Size;         // Size of bitvector in bits.
00032   unsigned Capacity;     // Size of allocated memory in BitWord.
00033 
00034 public:
00035   // Encapsulation of a single bit.
00036   class reference {
00037     friend class BitVector;
00038 
00039     BitWord *WordRef;
00040     unsigned BitPos;
00041 
00042     reference();  // Undefined
00043 
00044   public:
00045     reference(BitVector &b, unsigned Idx) {
00046       WordRef = &b.Bits[Idx / BITWORD_SIZE];
00047       BitPos = Idx % BITWORD_SIZE;
00048     }
00049 
00050     ~reference() {}
00051 
00052     reference& operator=(bool t) {
00053       if (t)
00054         *WordRef |= 1L << BitPos;
00055       else
00056         *WordRef &= ~(1L << BitPos);
00057       return *this;
00058     }
00059 
00060     operator bool() const {
00061       return ((*WordRef) & (1L << BitPos)) ? true : false;
00062     }
00063   };
00064 
00065 
00066   /// BitVector default ctor - Creates an empty bitvector.
00067   BitVector() : Size(0), Capacity(0) {
00068     Bits = 0;
00069   }
00070 
00071   /// BitVector ctor - Creates a bitvector of specified number of bits. All
00072   /// bits are initialized to the specified value.
00073   explicit BitVector(unsigned s, bool t = false) : Size(s) {
00074     Capacity = NumBitWords(s);
00075     Bits = new BitWord[Capacity];
00076     init_words(Bits, Capacity, t);
00077     if (t)
00078       clear_unused_bits();
00079   }
00080 
00081   /// BitVector copy ctor.
00082   BitVector(const BitVector &RHS) : Size(RHS.size()) {
00083     if (Size == 0) {
00084       Bits = 0;
00085       Capacity = 0;
00086       return;
00087     }
00088 
00089     Capacity = NumBitWords(RHS.size());
00090     Bits = new BitWord[Capacity];
00091     std::copy(RHS.Bits, &RHS.Bits[Capacity], Bits);
00092   }
00093 
00094   ~BitVector() {
00095     delete[] Bits;
00096   }
00097 
00098   /// size - Returns the number of bits in this bitvector.
00099   unsigned size() const { return Size; }
00100 
00101   /// count - Returns the number of bits which are set.
00102   unsigned count() const {
00103     unsigned NumBits = 0;
00104     for (unsigned i = 0; i < NumBitWords(size()); ++i)
00105       if (sizeof(BitWord) == 4)
00106         NumBits += CountPopulation_32((uint32_t)Bits[i]);
00107       else if (sizeof(BitWord) == 8)
00108         NumBits += CountPopulation_64(Bits[i]);
00109       else
00110         assert(0 && "Unsupported!");
00111     return NumBits;
00112   }
00113 
00114   /// any - Returns true if any bit is set.
00115   bool any() const {
00116     for (unsigned i = 0; i < NumBitWords(size()); ++i)
00117       if (Bits[i] != 0)
00118         return true;
00119     return false;
00120   }
00121 
00122   /// none - Returns true if none of the bits are set.
00123   bool none() const {
00124     return !any();
00125   }
00126 
00127   /// find_first - Returns the index of the first set bit, -1 if none
00128   /// of the bits are set.
00129   int find_first() const {
00130     for (unsigned i = 0; i < NumBitWords(size()); ++i)
00131       if (Bits[i] != 0) {
00132         if (sizeof(BitWord) == 4)
00133           return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]);
00134         else if (sizeof(BitWord) == 8)
00135           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
00136         else
00137           assert(0 && "Unsupported!");
00138       }
00139     return -1;
00140   }
00141 
00142   /// find_next - Returns the index of the next set bit following the
00143   /// "Prev" bit. Returns -1 if the next set bit is not found.
00144   int find_next(unsigned Prev) const {
00145     ++Prev;
00146     if (Prev >= Size)
00147       return -1;
00148 
00149     unsigned WordPos = Prev / BITWORD_SIZE;
00150     unsigned BitPos = Prev % BITWORD_SIZE;
00151     BitWord Copy = Bits[WordPos];
00152     // Mask off previous bits.
00153     Copy &= ~0L << BitPos;
00154 
00155     if (Copy != 0) {
00156       if (sizeof(BitWord) == 4)
00157         return WordPos * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Copy);
00158       else if (sizeof(BitWord) == 8)
00159         return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
00160       else
00161         assert(0 && "Unsupported!");
00162     }
00163 
00164     // Check subsequent words.
00165     for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i)
00166       if (Bits[i] != 0) {
00167         if (sizeof(BitWord) == 4)
00168           return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]);
00169         else if (sizeof(BitWord) == 8)
00170           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
00171         else
00172           assert(0 && "Unsupported!");
00173       }
00174     return -1;
00175   }
00176 
00177   /// clear - Clear all bits.
00178   void clear() {
00179     Size = 0;
00180   }
00181 
00182   /// resize - Grow or shrink the bitvector.
00183   void resize(unsigned N, bool t = false) {
00184     if (N > Capacity * BITWORD_SIZE) {
00185       unsigned OldCapacity = Capacity;
00186       grow(N);
00187       init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t);
00188     }
00189 
00190     // Set any old unused bits that are now included in the BitVector. This
00191     // may set bits that are not included in the new vector, but we will clear
00192     // them back out below.
00193     if (N > Size)
00194       set_unused_bits(t);
00195 
00196     // Update the size, and clear out any bits that are now unused
00197     unsigned OldSize = Size;
00198     Size = N;
00199     if (t || N < OldSize)
00200       clear_unused_bits();
00201   }
00202 
00203   void reserve(unsigned N) {
00204     if (N > Capacity * BITWORD_SIZE)
00205       grow(N);
00206   }
00207 
00208   // Set, reset, flip
00209   BitVector &set() {
00210     init_words(Bits, Capacity, true);
00211     clear_unused_bits();
00212     return *this;
00213   }
00214 
00215   BitVector &set(unsigned Idx) {
00216     Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
00217     return *this;
00218   }
00219 
00220   BitVector &reset() {
00221     init_words(Bits, Capacity, false);
00222     return *this;
00223   }
00224 
00225   BitVector &reset(unsigned Idx) {
00226     Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
00227     return *this;
00228   }
00229 
00230   BitVector &flip() {
00231     for (unsigned i = 0; i < NumBitWords(size()); ++i)
00232       Bits[i] = ~Bits[i];
00233     clear_unused_bits();
00234     return *this;
00235   }
00236 
00237   BitVector &flip(unsigned Idx) {
00238     Bits[Idx / BITWORD_SIZE] ^= 1L << (Idx % BITWORD_SIZE);
00239     return *this;
00240   }
00241 
00242   // No argument flip.
00243   BitVector operator~() const {
00244     return BitVector(*this).flip();
00245   }
00246 
00247   // Indexing.
00248   reference operator[](unsigned Idx) {
00249     assert (Idx < Size && "Out-of-bounds Bit access.");
00250     return reference(*this, Idx);
00251   }
00252 
00253   bool operator[](unsigned Idx) const {
00254     assert (Idx < Size && "Out-of-bounds Bit access.");
00255     BitWord Mask = 1L << (Idx % BITWORD_SIZE);
00256     return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
00257   }
00258 
00259   bool test(unsigned Idx) const {
00260     return (*this)[Idx];
00261   }
00262 
00263   // Comparison operators.
00264   bool operator==(const BitVector &RHS) const {
00265     unsigned ThisWords = NumBitWords(size());
00266     unsigned RHSWords  = NumBitWords(RHS.size());
00267     unsigned i;
00268     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
00269       if (Bits[i] != RHS.Bits[i])
00270         return false;
00271 
00272     // Verify that any extra words are all zeros.
00273     if (i != ThisWords) {
00274       for (; i != ThisWords; ++i)
00275         if (Bits[i])
00276           return false;
00277     } else if (i != RHSWords) {
00278       for (; i != RHSWords; ++i)
00279         if (RHS.Bits[i])
00280           return false;
00281     }
00282     return true;
00283   }
00284 
00285   bool operator!=(const BitVector &RHS) const {
00286     return !(*this == RHS);
00287   }
00288 
00289   // Intersection, union, disjoint union.
00290   BitVector &operator&=(const BitVector &RHS) {
00291     unsigned ThisWords = NumBitWords(size());
00292     unsigned RHSWords  = NumBitWords(RHS.size());
00293     unsigned i;
00294     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
00295       Bits[i] &= RHS.Bits[i];
00296 
00297     // Any bits that are just in this bitvector become zero, because they aren't
00298     // in the RHS bit vector.  Any words only in RHS are ignored because they
00299     // are already zero in the LHS.
00300     for (; i != ThisWords; ++i)
00301       Bits[i] = 0;
00302 
00303     return *this;
00304   }
00305 
00306   BitVector &operator|=(const BitVector &RHS) {
00307     assert(Size == RHS.Size && "Illegal operation!");
00308     for (unsigned i = 0; i < NumBitWords(size()); ++i)
00309       Bits[i] |= RHS.Bits[i];
00310     return *this;
00311   }
00312 
00313   BitVector &operator^=(const BitVector &RHS) {
00314     assert(Size == RHS.Size && "Illegal operation!");
00315     for (unsigned i = 0; i < NumBitWords(size()); ++i)
00316       Bits[i] ^= RHS.Bits[i];
00317     return *this;
00318   }
00319 
00320   // Assignment operator.
00321   const BitVector &operator=(const BitVector &RHS) {
00322     if (this == &RHS) return *this;
00323 
00324     Size = RHS.size();
00325     unsigned RHSWords = NumBitWords(Size);
00326     if (Size <= Capacity * BITWORD_SIZE) {
00327       std::copy(RHS.Bits, &RHS.Bits[RHSWords], Bits);
00328       clear_unused_bits();
00329       return *this;
00330     }
00331 
00332     // Grow the bitvector to have enough elements.
00333     Capacity = RHSWords;
00334     BitWord *NewBits = new BitWord[Capacity];
00335     std::copy(RHS.Bits, &RHS.Bits[RHSWords], NewBits);
00336 
00337     // Destroy the old bits.
00338     delete[] Bits;
00339     Bits = NewBits;
00340 
00341     return *this;
00342   }
00343 
00344 private:
00345   unsigned NumBitWords(unsigned S) const {
00346     return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
00347   }
00348 
00349   // Set the unused bits in the high words.
00350   void set_unused_bits(bool t = true) {
00351     //  Set high words first.
00352     unsigned UsedWords = NumBitWords(Size);
00353     if (Capacity > UsedWords)
00354       init_words(&Bits[UsedWords], (Capacity-UsedWords), t);
00355 
00356     //  Then set any stray high bits of the last used word.
00357     unsigned ExtraBits = Size % BITWORD_SIZE;
00358     if (ExtraBits) {
00359       Bits[UsedWords-1] &= ~(~0L << ExtraBits);
00360       Bits[UsedWords-1] |= (0 - (BitWord)t) << ExtraBits;
00361     }
00362   }
00363 
00364   // Clear the unused bits in the high words.
00365   void clear_unused_bits() {
00366     set_unused_bits(false);
00367   }
00368 
00369   void grow(unsigned NewSize) {
00370     unsigned OldCapacity = Capacity;
00371     Capacity = NumBitWords(NewSize);
00372     BitWord *NewBits = new BitWord[Capacity];
00373 
00374     // Copy the old bits over.
00375     if (OldCapacity != 0)
00376       std::copy(Bits, &Bits[OldCapacity], NewBits);
00377 
00378     // Destroy the old bits.
00379     delete[] Bits;
00380     Bits = NewBits;
00381 
00382     clear_unused_bits();
00383   }
00384 
00385   void init_words(BitWord *B, unsigned NumWords, bool t) {
00386     memset(B, 0 - (int)t, NumWords*sizeof(BitWord));
00387   }
00388 };
00389 
00390 inline BitVector operator&(const BitVector &LHS, const BitVector &RHS) {
00391   BitVector Result(LHS);
00392   Result &= RHS;
00393   return Result;
00394 }
00395 
00396 inline BitVector operator|(const BitVector &LHS, const BitVector &RHS) {
00397   BitVector Result(LHS);
00398   Result |= RHS;
00399   return Result;
00400 }
00401 
00402 inline BitVector operator^(const BitVector &LHS, const BitVector &RHS) {
00403   BitVector Result(LHS);
00404   Result ^= RHS;
00405   return Result;
00406 }
00407 
00408 } // End llvm namespace
00409 #endif