include/llvm/ADT/BitSetVector.h

   1 //===-- BitVectorSet.h - A bit-vector representation of sets ----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This is an implementation of the bit-vector representation of sets.  Unlike
  11 // vector<bool>, this allows much more efficient parallel set operations on
  12 // bits, by using the bitset template.  The bitset template unfortunately can
  13 // only represent sets with a size chosen at compile-time.  We therefore use a
  14 // vector of bitsets.  The maxmimum size of our sets (i.e., the size of the
  15 // universal set) can be chosen at creation time.
  16 //
  17 // External functions:
  18 //
  19 // bool Disjoint(const BitSetVector& set1, const BitSetVector& set2):
  20 //    Tests if two sets have an empty intersection.
  21 //    This is more efficient than !(set1 & set2).any().
  22 //
  23 //===----------------------------------------------------------------------===//
  24
  25 #ifndef SUPPORT_BITSETVECTOR_H
  26 #define SUPPORT_BITSETVECTOR_H
  27
  28 #include <bitset>
  29 #include <vector>
  30 #include <functional>
  31 #include <iostream>
  32
  33 namespace llvm {
  34
  35 class BitSetVector {
  36   enum { BITSET_WORDSIZE = sizeof(long)*8 };
  37
  38   // Types used internal to the representation
  39   typedef std::bitset<BITSET_WORDSIZE> bitword;
  40   typedef bitword::reference reference;
  41
  42   // Data used in the representation
  43   std::vector<bitword> bitsetVec;
  44   unsigned maxSize;
  45
  46 private:
  47   // Utility functions for the representation
  48   static unsigned NumWords(unsigned Size) {
  49     return (Size+BITSET_WORDSIZE-1)/BITSET_WORDSIZE;
  50   }
  51   static unsigned LastWordSize(unsigned Size) { return Size % BITSET_WORDSIZE; }
  52
  53   // Clear the unused bits in the last word.
  54   // The unused bits are the high (BITSET_WORDSIZE - LastWordSize()) bits
  55   void ClearUnusedBits() {
  56     unsigned long usedBits = (1U << LastWordSize(size())) - 1;
  57     bitsetVec.back() &= bitword(usedBits);
  58   }
  59
  60   const bitword& getWord(unsigned i) const { return bitsetVec[i]; }
  61         bitword& getWord(unsigned i)       { return bitsetVec[i]; }
  62
  63   friend bool Disjoint(const BitSetVector& set1,
  64                        const BitSetVector& set2);
  65
  66   BitSetVector();                       // do not implement!
  67
  68 public:
  69   class iterator;
  70   ///
  71   /// Constructor: create a set of the maximum size maxSetSize.
  72   /// The set is initialized to empty.
  73   ///
  74   BitSetVector(unsigned maxSetSize)
  75     : bitsetVec(NumWords(maxSetSize)), maxSize(maxSetSize) { }
  76
  77   /// size - Return the number of bits tracked by this bit vector...
  78   unsigned size() const { return maxSize; }
  79
  80   ///
  81   ///  Modifier methods: reset, set for entire set, operator[] for one element.
  82   ///
  83   void reset() {
  84     for (unsigned i=0, N = bitsetVec.size(); i < N; ++i)
  85       bitsetVec[i].reset();
  86   }
  87   void set() {
  88     for (unsigned i=0, N = bitsetVec.size(); i < N; ++i) // skip last word
  89       bitsetVec[i].set();
  90     ClearUnusedBits();
  91   }
  92   reference operator[](unsigned n) {
  93     assert(n  < size() && "BitSetVector: Bit number out of range");
  94     unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE;
  95     return bitsetVec[ndiv][nmod];
  96   }
  97   iterator begin() { return iterator::begin(*this); }
  98   iterator end()   { return iterator::end(*this);   }
  99
 100   ///
 101   ///  Comparison operations: equal, not equal
 102   ///
 103   bool operator == (const BitSetVector& set2) const {
 104     assert(maxSize == set2.maxSize && "Illegal == comparison");
 105     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 106       if (getWord(i) != set2.getWord(i))
 107         return false;
 108     return true;
 109   }
 110   bool operator != (const BitSetVector& set2) const {
 111     return ! (*this == set2);
 112   }
 113
 114   ///
 115   ///  Set membership operations: single element, any, none, count
 116   ///
 117   bool test(unsigned n) const {
 118     assert(n  < size() && "BitSetVector: Bit number out of range");
 119     unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE;
 120     return bitsetVec[ndiv].test(nmod);
 121   }
 122   bool any() const {
 123     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 124       if (bitsetVec[i].any())
 125         return true;
 126     return false;
 127   }
 128   bool none() const {
 129     return ! any();
 130   }
 131   unsigned count() const {
 132     unsigned n = 0;
 133     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 134       n += bitsetVec[i].count();
 135     return n;
 136   }
 137   bool all() const {
 138     return (count() == size());
 139   }
 140
 141   ///
 142   ///  Set operations: intersection, union, disjoint union, complement.
 143   ///
 144   BitSetVector operator& (const BitSetVector& set2) const {
 145     assert(maxSize == set2.maxSize && "Illegal intersection");
 146     BitSetVector result(maxSize);
 147     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 148       result.getWord(i) = getWord(i) & set2.getWord(i);
 149     return result;
 150   }
 151   BitSetVector operator| (const BitSetVector& set2) const {
 152     assert(maxSize == set2.maxSize && "Illegal intersection");
 153     BitSetVector result(maxSize);
 154     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 155       result.getWord(i) = getWord(i) | set2.getWord(i);
 156     return result;
 157   }
 158   BitSetVector operator^ (const BitSetVector& set2) const {
 159     assert(maxSize == set2.maxSize && "Illegal intersection");
 160     BitSetVector result(maxSize);
 161     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 162       result.getWord(i) = getWord(i) ^ set2.getWord(i);
 163     return result;
 164   }
 165   BitSetVector operator~ () const {
 166     BitSetVector result(maxSize);
 167     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 168       (result.getWord(i) = getWord(i)).flip();
 169     result.ClearUnusedBits();
 170     return result;
 171   }
 172
 173   ///
 174   ///  Printing and debugging support
 175   ///
 176   void print(std::ostream &O) const;
 177   void dump() const { print(std::cerr); }
 178
 179 public:
 180   //
 181   // An iterator to enumerate the bits in a BitSetVector.
 182   // Eventually, this needs to inherit from bidirectional_iterator.
 183   // But this iterator may not be as useful as I once thought and
 184   // may just go away.
 185   //
 186   class iterator {
 187     unsigned   currentBit;
 188     unsigned   currentWord;
 189     BitSetVector* bitvec;
 190     iterator(unsigned B, unsigned W, BitSetVector& _bitvec)
 191       : currentBit(B), currentWord(W), bitvec(&_bitvec) { }
 192   public:
 193     iterator(BitSetVector& _bitvec)
 194       : currentBit(0), currentWord(0), bitvec(&_bitvec) { }
 195     iterator(const iterator& I)
 196       : currentBit(I.currentBit),currentWord(I.currentWord),bitvec(I.bitvec) { }
 197     iterator& operator=(const iterator& I) {
 198       currentWord = I.currentWord;
 199       currentBit = I.currentBit;
 200       bitvec = I.bitvec;
 201       return *this;
 202     }
 203
 204     // Increment and decrement operators (pre and post)
 205     iterator& operator++() {
 206       if (++currentBit == BITSET_WORDSIZE)
 207         { currentBit = 0; if (currentWord < bitvec->size()) ++currentWord; }
 208       return *this;
 209     }
 210     iterator& operator--() {
 211       if (currentBit == 0) {
 212         currentBit = BITSET_WORDSIZE-1;
 213         currentWord = (currentWord == 0)? bitvec->size() : --currentWord;
 214       }
 215       else
 216         --currentBit;
 217       return *this;
 218     }
 219     iterator operator++(int) { iterator copy(*this); ++*this; return copy; }
 220     iterator operator--(int) { iterator copy(*this); --*this; return copy; }
 221
 222     // Dereferencing operators
 223     reference operator*() {
 224       assert(currentWord < bitvec->size() &&
 225              "Dereferencing iterator past the end of a BitSetVector");
 226       return bitvec->getWord(currentWord)[currentBit];
 227     }
 228
 229     // Comparison operator
 230     bool operator==(const iterator& I) {
 231       return (I.bitvec == bitvec &&
 232               I.currentWord == currentWord && I.currentBit == currentBit);
 233     }
 234
 235   protected:
 236     static iterator begin(BitSetVector& _bitvec) { return iterator(_bitvec); }
 237     static iterator end(BitSetVector& _bitvec)   { return iterator(0,
 238                                                     _bitvec.size(), _bitvec); }
 239     friend class BitSetVector;
 240   };
 241 };
 242
 243
 244 inline void BitSetVector::print(std::ostream& O) const
 245 {
 246   for (std::vector<bitword>::const_iterator
 247          I=bitsetVec.begin(), E=bitsetVec.end(); I != E; ++I)
 248     O << "<" << (*I) << ">" << (I+1 == E? "\n" : ", ");
 249 }
 250
 251 inline std::ostream& operator<< (std::ostream& O, const BitSetVector& bset)
 252 {
 253   bset.print(O);
 254   return O;
 255 };
 256
 257
 258 ///
 259 /// Optimized versions of fundamental comparison operations
 260 ///
 261 inline bool Disjoint(const BitSetVector& set1,
 262                      const BitSetVector& set2)
 263 {
 264   assert(set1.size() == set2.size() && "Illegal intersection");
 265   for (unsigned i = 0; i < set1.bitsetVec.size(); ++i)
 266     if ((set1.getWord(i) & set2.getWord(i)).any())
 267       return false;
 268   return true;
 269 }
 270
 271 } // End llvm namespace
 272 #endif