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