LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

BitSetVector.h

Go to the documentation of this file.
00001 //===-- llvm/ADT/BitVectorSet.h - A bit-vector rep. of sets -----*- C++ -*-===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This is an implementation of the bit-vector representation of sets.  Unlike
00011 // vector<bool>, this allows much more efficient parallel set operations on
00012 // bits, by using the bitset template.  The bitset template unfortunately can
00013 // only represent sets with a size chosen at compile-time.  We therefore use a
00014 // vector of bitsets.  The maxmimum size of our sets (i.e., the size of the
00015 // universal set) can be chosen at creation time.
00016 //
00017 // External functions:
00018 // 
00019 // bool Disjoint(const BitSetVector& set1, const BitSetVector& set2):
00020 //    Tests if two sets have an empty intersection.
00021 //    This is more efficient than !(set1 & set2).any().
00022 // 
00023 //===----------------------------------------------------------------------===//
00024 
00025 #ifndef LLVM_ADT_BITSETVECTOR_H
00026 #define LLVM_ADT_BITSETVECTOR_H
00027 
00028 #include <bitset>
00029 #include <vector>
00030 #include <functional>
00031 #include <iostream>
00032 
00033 namespace llvm {
00034 
00035 class BitSetVector {
00036   enum { BITSET_WORDSIZE = sizeof(long)*8 };
00037 
00038   // Types used internal to the representation
00039   typedef std::bitset<BITSET_WORDSIZE> bitword;
00040   typedef bitword::reference reference;
00041 
00042   // Data used in the representation
00043   std::vector<bitword> bitsetVec;
00044   unsigned maxSize;
00045 
00046 private:
00047   // Utility functions for the representation
00048   static unsigned NumWords(unsigned Size) {
00049     return (Size+BITSET_WORDSIZE-1)/BITSET_WORDSIZE;
00050   } 
00051   static unsigned LastWordSize(unsigned Size) { return Size % BITSET_WORDSIZE; }
00052 
00053   // Clear the unused bits in the last word.
00054   // The unused bits are the high (BITSET_WORDSIZE - LastWordSize()) bits
00055   void ClearUnusedBits() {
00056     unsigned long usedBits = (1U << LastWordSize(size())) - 1;
00057     bitsetVec.back() &= bitword(usedBits);
00058   }
00059 
00060   const bitword& getWord(unsigned i) const { return bitsetVec[i]; }
00061         bitword& getWord(unsigned i)       { return bitsetVec[i]; }
00062 
00063   friend bool Disjoint(const BitSetVector& set1,
00064                        const BitSetVector& set2);
00065 
00066   BitSetVector();                       // do not implement!
00067 
00068 public:
00069   class iterator;
00070   /// 
00071   /// Constructor: create a set of the maximum size maxSetSize.
00072   /// The set is initialized to empty.
00073   ///
00074   BitSetVector(unsigned maxSetSize)
00075     : bitsetVec(NumWords(maxSetSize)), maxSize(maxSetSize) { }
00076 
00077   /// size - Return the number of bits tracked by this bit vector...
00078   unsigned size() const { return maxSize; }
00079 
00080   /// 
00081   ///  Modifier methods: reset, set for entire set, operator[] for one element.
00082   ///  
00083   void reset() {
00084     for (unsigned i=0, N = bitsetVec.size(); i < N; ++i)
00085       bitsetVec[i].reset();
00086   }
00087   void set() {
00088     for (unsigned i=0, N = bitsetVec.size(); i < N; ++i) // skip last word
00089       bitsetVec[i].set();
00090     ClearUnusedBits();
00091   }
00092   reference operator[](unsigned n) {
00093     assert(n  < size() && "BitSetVector: Bit number out of range");
00094     unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE;
00095     return bitsetVec[ndiv][nmod];
00096   }
00097   iterator begin() { return iterator::begin(*this); }
00098   iterator end()   { return iterator::end(*this);   } 
00099 
00100   /// 
00101   ///  Comparison operations: equal, not equal
00102   /// 
00103   bool operator == (const BitSetVector& set2) const {
00104     assert(maxSize == set2.maxSize && "Illegal == comparison");
00105     for (unsigned i = 0; i < bitsetVec.size(); ++i)
00106       if (getWord(i) != set2.getWord(i))
00107         return false;
00108     return true;
00109   }
00110   bool operator != (const BitSetVector& set2) const {
00111     return ! (*this == set2);
00112   }
00113 
00114   /// 
00115   ///  Set membership operations: single element, any, none, count
00116   ///  
00117   bool test(unsigned n) const {
00118     assert(n  < size() && "BitSetVector: Bit number out of range");
00119     unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE;
00120     return bitsetVec[ndiv].test(nmod);
00121   }
00122   bool any() const {
00123     for (unsigned i = 0; i < bitsetVec.size(); ++i)
00124       if (bitsetVec[i].any())
00125         return true;
00126     return false;
00127   }
00128   bool none() const {
00129     return ! any();
00130   }
00131   unsigned count() const {
00132     unsigned n = 0;
00133     for (unsigned i = 0; i < bitsetVec.size(); ++i)
00134       n += bitsetVec[i].count();
00135     return n;
00136   }
00137   bool all() const {
00138     return (count() == size());
00139   }
00140 
00141   /// 
00142   ///  Set operations: intersection, union, disjoint union, complement.
00143   ///  
00144   BitSetVector operator& (const BitSetVector& set2) const {
00145     assert(maxSize == set2.maxSize && "Illegal intersection");
00146     BitSetVector result(maxSize);
00147     for (unsigned i = 0; i < bitsetVec.size(); ++i)
00148       result.getWord(i) = getWord(i) & set2.getWord(i);
00149     return result;
00150   }
00151   BitSetVector operator| (const BitSetVector& set2) const {
00152     assert(maxSize == set2.maxSize && "Illegal intersection");
00153     BitSetVector result(maxSize);
00154     for (unsigned i = 0; i < bitsetVec.size(); ++i)
00155       result.getWord(i) = getWord(i) | set2.getWord(i);
00156     return result;
00157   }
00158   BitSetVector operator^ (const BitSetVector& set2) const {
00159     assert(maxSize == set2.maxSize && "Illegal intersection");
00160     BitSetVector result(maxSize);
00161     for (unsigned i = 0; i < bitsetVec.size(); ++i)
00162       result.getWord(i) = getWord(i) ^ set2.getWord(i);
00163     return result;
00164   }
00165   BitSetVector operator~ () const {
00166     BitSetVector result(maxSize);
00167     for (unsigned i = 0; i < bitsetVec.size(); ++i)
00168       (result.getWord(i) = getWord(i)).flip();
00169     result.ClearUnusedBits();
00170     return result;
00171   }
00172 
00173   /// 
00174   ///  Printing and debugging support
00175   ///  
00176   void print(std::ostream &O) const;
00177   void dump() const { print(std::cerr); }
00178 
00179 public:
00180   // 
00181   // An iterator to enumerate the bits in a BitSetVector.
00182   // Eventually, this needs to inherit from bidirectional_iterator.
00183   // But this iterator may not be as useful as I once thought and
00184   // may just go away.
00185   // 
00186   class iterator {
00187     unsigned   currentBit;
00188     unsigned   currentWord;
00189     BitSetVector* bitvec;
00190     iterator(unsigned B, unsigned W, BitSetVector& _bitvec)
00191       : currentBit(B), currentWord(W), bitvec(&_bitvec) { }
00192   public:
00193     iterator(BitSetVector& _bitvec)
00194       : currentBit(0), currentWord(0), bitvec(&_bitvec) { }
00195     iterator(const iterator& I)
00196       : currentBit(I.currentBit),currentWord(I.currentWord),bitvec(I.bitvec) { }
00197     iterator& operator=(const iterator& I) {
00198       currentWord = I.currentWord;
00199       currentBit = I.currentBit;
00200       bitvec = I.bitvec;
00201       return *this;
00202     }
00203 
00204     // Increment and decrement operators (pre and post)
00205     iterator& operator++() {
00206       if (++currentBit == BITSET_WORDSIZE)
00207         { currentBit = 0; if (currentWord < bitvec->size()) ++currentWord; }
00208       return *this;
00209     }
00210     iterator& operator--() {
00211       if (currentBit == 0) {
00212         currentBit = BITSET_WORDSIZE-1;
00213         currentWord = (currentWord == 0)? bitvec->size() : --currentWord;
00214       }
00215       else
00216         --currentBit;
00217       return *this;
00218     }
00219     iterator operator++(int) { iterator copy(*this); ++*this; return copy; }
00220     iterator operator--(int) { iterator copy(*this); --*this; return copy; }
00221 
00222     // Dereferencing operators
00223     reference operator*() {
00224       assert(currentWord < bitvec->size() &&
00225              "Dereferencing iterator past the end of a BitSetVector");
00226       return bitvec->getWord(currentWord)[currentBit];
00227     }
00228 
00229     // Comparison operator
00230     bool operator==(const iterator& I) {
00231       return (I.bitvec == bitvec &&
00232               I.currentWord == currentWord && I.currentBit == currentBit);
00233     }
00234 
00235   protected:
00236     static iterator begin(BitSetVector& _bitvec) { return iterator(_bitvec); }
00237     static iterator end(BitSetVector& _bitvec)   { return iterator(0,
00238                                                     _bitvec.size(), _bitvec); }
00239     friend class BitSetVector;
00240   };
00241 };
00242 
00243 
00244 inline void BitSetVector::print(std::ostream& O) const
00245 {
00246   for (std::vector<bitword>::const_iterator
00247          I=bitsetVec.begin(), E=bitsetVec.end(); I != E; ++I)
00248     O << "<" << (*I) << ">" << (I+1 == E? "\n" : ", ");
00249 }
00250 
00251 inline std::ostream& operator<< (std::ostream& O, const BitSetVector& bset)
00252 {
00253   bset.print(O);
00254   return O;
00255 };
00256 
00257 
00258 ///
00259 /// Optimized versions of fundamental comparison operations
00260 /// 
00261 inline bool Disjoint(const BitSetVector& set1,
00262                      const BitSetVector& set2)
00263 {
00264   assert(set1.size() == set2.size() && "Illegal intersection");
00265   for (unsigned i = 0; i < set1.bitsetVec.size(); ++i)
00266     if ((set1.getWord(i) & set2.getWord(i)).any())
00267       return false;
00268   return true;
00269 }
00270 
00271 } // End llvm namespace
00272 #endif