BitVector.h revision b5aabee33073068f1f6bb71c1da9000b03b16181
1//===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Evan Cheng and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the BitVector class. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ADT_BITVECTOR_H 15#define LLVM_ADT_BITVECTOR_H 16 17#include "llvm/Support/MathExtras.h" 18 19namespace llvm { 20 21class BitVector { 22 typedef unsigned long BitWord; 23 24 enum { BITS_PER_WORD = sizeof(BitWord) * 8 }; 25 26 BitWord *Bits; // Actual bits. 27 unsigned Size; // Size of bitvector in bits. 28 unsigned Capacity; // Size of allocated memory in BitWord. 29 30public: 31 // Encapsulation of a single bit. 32 class reference { 33 friend class BitVector; 34 35 BitWord *WordRef; 36 unsigned BitPos; 37 38 reference(); // Undefined 39 40 public: 41 reference(BitVector &b, unsigned Idx) { 42 WordRef = &b.Bits[Idx / BITS_PER_WORD]; 43 BitPos = Idx % BITS_PER_WORD; 44 } 45 46 ~reference() {} 47 48 reference& operator=(bool t) { 49 if (t) 50 *WordRef |= 1L << BitPos; 51 else 52 *WordRef &= ~(1L << BitPos); 53 return *this; 54 } 55 56 operator bool() const { 57 return (*WordRef) & (1L << BitPos); 58 } 59 }; 60 61 62 /// BitVector default ctor - Creates an empty bitvector. 63 BitVector() : Size(0), Capacity(0) { 64 Bits = NULL; 65 } 66 67 /// BitVector ctor - Creates a bitvector of specified number of bits. All 68 /// bits are initialized to the specified value. 69 explicit BitVector(unsigned s, bool t = false) : Size(s) { 70 Capacity = NumBitWords(s); 71 Bits = new BitWord[Capacity]; 72 init_words(Bits, Capacity, t); 73 if (t) 74 clear_unused_bits(); 75 } 76 77 /// BitVector copy ctor. 78 BitVector(const BitVector &RHS) : Size(RHS.size()) { 79 if (Size == 0) { 80 Bits = NULL; 81 Capacity = 0; 82 return; 83 } 84 85 Capacity = NumBitWords(RHS.size()); 86 Bits = new BitWord[Capacity]; 87 std::copy(RHS.Bits, &RHS.Bits[Capacity], Bits); 88 } 89 90 /// size - Returns the number of bits in this bitvector. 91 unsigned size() const { return Size; } 92 93 /// count - Returns the number of bits which are set. 94 unsigned count() const { 95 unsigned NumBits = 0; 96 for (unsigned i = 0; i < NumBitWords(size()); ++i) 97 if (sizeof(BitWord) == 4) 98 NumBits += CountPopulation_32(Bits[i]); 99 else if (sizeof(BitWord) == 8) 100 NumBits += CountPopulation_64(Bits[i]); 101 else 102 assert(0 && "Unsupported!"); 103 return NumBits; 104 } 105 106 /// any - Returns true if any bit is set. 107 bool any() const { 108 for (unsigned i = 0; i < NumBitWords(size()); ++i) 109 if (Bits[i] != 0) 110 return true; 111 return false; 112 } 113 114 /// none - Returns true if none of the bits are set. 115 bool none() const { 116 return !any(); 117 } 118 119 /// find_first - Returns the index of the first set bit, -1 if none 120 /// of the bits are set. 121 int find_first() const { 122 for (unsigned i = 0; i < NumBitWords(size()); ++i) 123 if (Bits[i] != 0) 124 return i * BITS_PER_WORD + CountTrailingZeros_32(Bits[i]); 125 return -1; 126 } 127 128 /// find_next - Returns the index of the next set bit following the 129 /// "Prev" bit. Returns -1 if the next set bit is not found. 130 int find_next(unsigned Prev) const { 131 ++Prev; 132 if (Prev >= Size) 133 return -1; 134 135 unsigned WordPos = Prev / BITS_PER_WORD; 136 unsigned BitPos = Prev % BITS_PER_WORD; 137 BitWord Copy = Bits[WordPos]; 138 // Mask off previous bits. 139 Copy &= ~0 << BitPos; 140 141 if (Copy != 0) 142 return WordPos * BITS_PER_WORD + CountTrailingZeros_32(Copy); 143 144 // Check subsequent words. 145 for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i) 146 if (Bits[i] != 0) 147 return i * BITS_PER_WORD + CountTrailingZeros_32(Bits[i]); 148 return -1; 149 } 150 151 /// clear - Clear all bits. 152 void clear() { 153 Size = 0; 154 } 155 156 /// resize - Grow or shrink the bitvector. 157 void resize(unsigned N, bool t = false) { 158 if (N > Capacity * BITS_PER_WORD) { 159 unsigned OldCapacity = Capacity; 160 grow(N); 161 init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t); 162 } 163 Size = N; 164 clear_unused_bits(); 165 } 166 167 void reserve(unsigned N) { 168 if (N > Capacity * BITS_PER_WORD) 169 grow(N); 170 } 171 172 // Set, reset, flip 173 BitVector &set() { 174 init_words(Bits, Capacity, true); 175 clear_unused_bits(); 176 return *this; 177 } 178 179 BitVector &set(unsigned Idx) { 180 Bits[Idx / BITS_PER_WORD] |= 1L << (Idx % BITS_PER_WORD); 181 return *this; 182 } 183 184 BitVector &reset() { 185 init_words(Bits, Capacity, false); 186 return *this; 187 } 188 189 BitVector &reset(unsigned Idx) { 190 Bits[Idx / BITS_PER_WORD] &= ~(1L << (Idx % BITS_PER_WORD)); 191 return *this; 192 } 193 194 BitVector &flip() { 195 for (unsigned i = 0; i < NumBitWords(size()); ++i) 196 Bits[i] = ~Bits[i]; 197 clear_unused_bits(); 198 return *this; 199 } 200 201 BitVector &flip(unsigned Idx) { 202 Bits[Idx / BITS_PER_WORD] ^= 1L << (Idx % BITS_PER_WORD); 203 return *this; 204 } 205 206 // No argument flip. 207 BitVector operator~() const { 208 return BitVector(*this).flip(); 209 } 210 211 // Indexing. 212 reference operator[](unsigned Idx) { 213 return reference(*this, Idx); 214 } 215 216 bool operator[](unsigned Idx) const { 217 BitWord Mask = 1L << (Idx % BITS_PER_WORD); 218 return (Bits[Idx / BITS_PER_WORD] & Mask) != 0; 219 } 220 221 bool test(unsigned Idx) const { 222 return (*this)[Idx]; 223 } 224 225 // Comparison operators. 226 bool operator==(const BitVector &RHS) const { 227 if (Size != RHS.Size) 228 return false; 229 230 for (unsigned i = 0; i < NumBitWords(size()); ++i) 231 if (Bits[i] != RHS.Bits[i]) 232 return false; 233 return true; 234 } 235 236 bool operator!=(const BitVector &RHS) const { 237 return !(*this == RHS); 238 } 239 240 // Intersection, union, disjoint union. 241 BitVector operator&=(const BitVector &RHS) { 242 assert(Size == RHS.Size && "Illegal operation!"); 243 for (unsigned i = 0; i < NumBitWords(size()); ++i) 244 Bits[i] &= RHS.Bits[i]; 245 return *this; 246 } 247 248 BitVector operator|=(const BitVector &RHS) { 249 assert(Size == RHS.Size && "Illegal operation!"); 250 for (unsigned i = 0; i < NumBitWords(size()); ++i) 251 Bits[i] |= RHS.Bits[i]; 252 return *this; 253 } 254 255 BitVector operator^=(const BitVector &RHS) { 256 assert(Size == RHS.Size && "Illegal operation!"); 257 for (unsigned i = 0; i < NumBitWords(size()); ++i) 258 Bits[i] ^= RHS.Bits[i]; 259 return *this; 260 } 261 262 // Assignment operator. 263 const BitVector &operator=(const BitVector &RHS) { 264 if (this == &RHS) return *this; 265 266 Size = RHS.size(); 267 unsigned RHSWords = NumBitWords(Size); 268 if (Size <= Capacity * BITS_PER_WORD) { 269 std::copy(RHS.Bits, &RHS.Bits[RHSWords], Bits); 270 clear_unused_bits(); 271 return *this; 272 } 273 274 // Grow the bitvector to have enough elements. 275 Capacity = NumBitWords(Size); 276 BitWord *NewBits = new BitWord[Capacity]; 277 std::copy(RHS.Bits, &RHS.Bits[RHSWords], NewBits); 278 279 // Destroy the old bits. 280 delete[] Bits; 281 Bits = NewBits; 282 283 return *this; 284 } 285 286private: 287 unsigned NumBitWords(unsigned S) const { 288 return (S + BITS_PER_WORD-1) / BITS_PER_WORD; 289 } 290 291 // Clear the unused top bits in the high word. 292 void clear_unused_bits() { 293 unsigned ExtraBits = Size % BITS_PER_WORD; 294 if (ExtraBits) { 295 unsigned index = Size / BITS_PER_WORD; 296 Bits[index] &= ~(~0L << ExtraBits); 297 } 298 } 299 300 void grow(unsigned NewSize) { 301 unsigned OldCapacity = Capacity; 302 Capacity = NumBitWords(NewSize); 303 BitWord *NewBits = new BitWord[Capacity]; 304 305 // Copy the old bits over. 306 if (OldCapacity != 0) 307 std::copy(Bits, &Bits[OldCapacity], NewBits); 308 309 // Destroy the old bits. 310 delete[] Bits; 311 Bits = NewBits; 312 } 313 314 void init_words(BitWord *B, unsigned NumWords, bool t) { 315 memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); 316 } 317}; 318 319inline BitVector operator&(const BitVector &LHS, const BitVector &RHS) { 320 BitVector Result(LHS); 321 Result &= RHS; 322 return Result; 323} 324 325inline BitVector operator|(const BitVector &LHS, const BitVector &RHS) { 326 BitVector Result(LHS); 327 Result |= RHS; 328 return Result; 329} 330 331inline BitVector operator^(const BitVector &LHS, const BitVector &RHS) { 332 BitVector Result(LHS); 333 Result ^= RHS; 334 return Result; 335} 336 337} // End llvm namespace 338#endif 339