include/llvm/ADT/BitSetVector.h

   1 //===-- llvm/ADT/BitVectorSet.h - A bit-vector rep. 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 LLVM_ADT_BITSETVECTOR_H
  26 #define LLVM_ADT_BITSETVECTOR_H
  27
  28 #include "llvm/Support/Streams.h"
  29 #include <bitset>
  30 #include <functional>
  31
  32 namespace llvm {
  33
  34 class BitSetVector {
  35   enum { BITSET_WORDSIZE = sizeof(long)*8 };
  36
  37   // Types used internal to the representation
  38   typedef std::bitset<BITSET_WORDSIZE> bitword;
  39   typedef bitword::reference reference;
  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   class iterator;
  69   ///
  70   /// Constructor: create a set of the maximum size maxSetSize.
  71   /// The set is initialized to empty.
  72   ///
  73   BitSetVector(unsigned maxSetSize)
  74     : bitsetVec(NumWords(maxSetSize)), maxSize(maxSetSize) { }
  75
  76   /// size - Return the number of bits tracked by this bit vector...
  77   unsigned size() const { return maxSize; }
  78
  79   ///
  80   ///  Modifier methods: reset, set for entire set, operator[] for one element.
  81   ///
  82   void reset() {
  83     for (unsigned i=0, N = bitsetVec.size(); i < N; ++i)
  84       bitsetVec[i].reset();
  85   }
  86   void set() {
  87     for (unsigned i=0, N = bitsetVec.size(); i < N; ++i) // skip last word
  88       bitsetVec[i].set();
  89     ClearUnusedBits();
  90   }
  91   reference operator[](unsigned n) {
  92     assert(n  < size() && "BitSetVector: Bit number out of range");
  93     unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE;
  94     return bitsetVec[ndiv][nmod];
  95   }
  96   iterator begin() { return iterator::begin(*this); }
  97   iterator end()   { return iterator::end(*this);   }
  98
  99   ///
 100   ///  Comparison operations: equal, not equal
 101   ///
 102   bool operator == (const BitSetVector& set2) const {
 103     assert(maxSize == set2.maxSize && "Illegal == comparison");
 104     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 105       if (getWord(i) != set2.getWord(i))
 106         return false;
 107     return true;
 108   }
 109   bool operator != (const BitSetVector& set2) const {
 110     return ! (*this == set2);
 111   }
 112
 113   ///
 114   ///  Set membership operations: single element, any, none, count
 115   ///
 116   bool test(unsigned n) const {
 117     assert(n  < size() && "BitSetVector: Bit number out of range");
 118     unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE;
 119     return bitsetVec[ndiv].test(nmod);
 120   }
 121   bool any() const {
 122     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 123       if (bitsetVec[i].any())
 124         return true;
 125     return false;
 126   }
 127   bool none() const {
 128     return ! any();
 129   }
 130   unsigned count() const {
 131     unsigned n = 0;
 132     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 133       n += bitsetVec[i].count();
 134     return n;
 135   }
 136   bool all() const {
 137     return (count() == size());
 138   }
 139
 140   ///
 141   ///  Set operations: intersection, union, disjoint union, complement.
 142   ///
 143   BitSetVector operator& (const BitSetVector& set2) const {
 144     assert(maxSize == set2.maxSize && "Illegal intersection");
 145     BitSetVector result(maxSize);
 146     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 147       result.getWord(i) = getWord(i) & set2.getWord(i);
 148     return result;
 149   }
 150   BitSetVector operator| (const BitSetVector& set2) const {
 151     assert(maxSize == set2.maxSize && "Illegal intersection");
 152     BitSetVector result(maxSize);
 153     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 154       result.getWord(i) = getWord(i) | set2.getWord(i);
 155     return result;
 156   }
 157   BitSetVector operator^ (const BitSetVector& set2) const {
 158     assert(maxSize == set2.maxSize && "Illegal intersection");
 159     BitSetVector result(maxSize);
 160     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 161       result.getWord(i) = getWord(i) ^ set2.getWord(i);
 162     return result;
 163   }
 164   BitSetVector operator~ () const {
 165     BitSetVector result(maxSize);
 166     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 167       (result.getWord(i) = getWord(i)).flip();
 168     result.ClearUnusedBits();
 169     return result;
 170   }
 171
 172   ///
 173   ///  Printing and debugging support
 174   ///
 175   void print(std::ostream &O) const;
 176   void print(std::ostream *O) const { if (O) print(*O); }
 177   void dump() const { print(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     bool operator!=(const iterator& I) {
 235       return !(*this == I);
 236     }
 237
 238   protected:
 239     static iterator begin(BitSetVector& _bitvec) { return iterator(_bitvec); }
 240     static iterator end(BitSetVector& _bitvec)   { return iterator(0,
 241                                                     _bitvec.size(), _bitvec); }
 242     friend class BitSetVector;
 243   };
 244 };
 245
 246
 247 inline void BitSetVector::print(std::ostream& O) const
 248 {
 249   for (std::vector<bitword>::const_iterator
 250          I=bitsetVec.begin(), E=bitsetVec.end(); I != E; ++I)
 251     O << "<" << (*I) << ">" << (I+1 == E? "\n" : ", ");
 252 }
 253
 254 inline std::ostream& operator<<(std::ostream& O, const BitSetVector& bset) {
 255   bset.print(O);
 256   return O;
 257 }
 258
 259 ///
 260 /// Optimized versions of fundamental comparison operations
 261 ///
 262 inline bool Disjoint(const BitSetVector& set1,
 263                      const BitSetVector& set2)
 264 {
 265   assert(set1.size() == set2.size() && "Illegal intersection");
 266   for (unsigned i = 0; i < set1.bitsetVec.size(); ++i)
 267     if ((set1.getWord(i) & set2.getWord(i)).any())
 268       return false;
 269   return true;
 270 }
 271
 272 } // End llvm namespace
 273 #endif