BitVector.h revision 3a54b3dc87a581c203b18050b4f787b4ca28a12c
1//===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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#include <algorithm> 19#include <cassert> 20#include <cstring> 21 22namespace llvm { 23 24class BitVector { 25 typedef unsigned long BitWord; 26 27 enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * 8 }; 28 29 BitWord *Bits; // Actual bits. 30 unsigned Size; // Size of bitvector in bits. 31 unsigned Capacity; // Size of allocated memory in BitWord. 32 33public: 34 // Encapsulation of a single bit. 35 class reference { 36 friend class BitVector; 37 38 BitWord *WordRef; 39 unsigned BitPos; 40 41 reference(); // Undefined 42 43 public: 44 reference(BitVector &b, unsigned Idx) { 45 WordRef = &b.Bits[Idx / BITWORD_SIZE]; 46 BitPos = Idx % BITWORD_SIZE; 47 } 48 49 ~reference() {} 50 51 reference& operator=(bool t) { 52 if (t) 53 *WordRef |= 1L << BitPos; 54 else 55 *WordRef &= ~(1L << BitPos); 56 return *this; 57 } 58 59 operator bool() const { 60 return ((*WordRef) & (1L << BitPos)) ? true : false; 61 } 62 }; 63 64 65 /// BitVector default ctor - Creates an empty bitvector. 66 BitVector() : Size(0), Capacity(0) { 67 Bits = 0; 68 } 69 70 /// BitVector ctor - Creates a bitvector of specified number of bits. All 71 /// bits are initialized to the specified value. 72 explicit BitVector(unsigned s, bool t = false) : Size(s) { 73 Capacity = NumBitWords(s); 74 Bits = new BitWord[Capacity]; 75 init_words(Bits, Capacity, t); 76 if (t) 77 clear_unused_bits(); 78 } 79 80 /// BitVector copy ctor. 81 BitVector(const BitVector &RHS) : Size(RHS.size()) { 82 if (Size == 0) { 83 Bits = 0; 84 Capacity = 0; 85 return; 86 } 87 88 Capacity = NumBitWords(RHS.size()); 89 Bits = new BitWord[Capacity]; 90 std::copy(RHS.Bits, &RHS.Bits[Capacity], Bits); 91 } 92 93 ~BitVector() { 94 delete[] Bits; 95 } 96 97 /// size - Returns the number of bits in this bitvector. 98 unsigned size() const { return Size; } 99 100 /// count - Returns the number of bits which are set. 101 unsigned count() const { 102 unsigned NumBits = 0; 103 for (unsigned i = 0; i < NumBitWords(size()); ++i) 104 if (sizeof(BitWord) == 4) 105 NumBits += CountPopulation_32((uint32_t)Bits[i]); 106 else if (sizeof(BitWord) == 8) 107 NumBits += CountPopulation_64(Bits[i]); 108 else 109 assert(0 && "Unsupported!"); 110 return NumBits; 111 } 112 113 /// any - Returns true if any bit is set. 114 bool any() const { 115 for (unsigned i = 0; i < NumBitWords(size()); ++i) 116 if (Bits[i] != 0) 117 return true; 118 return false; 119 } 120 121 /// none - Returns true if none of the bits are set. 122 bool none() const { 123 return !any(); 124 } 125 126 /// find_first - Returns the index of the first set bit, -1 if none 127 /// of the bits are set. 128 int find_first() const { 129 for (unsigned i = 0; i < NumBitWords(size()); ++i) 130 if (Bits[i] != 0) { 131 if (sizeof(BitWord) == 4) 132 return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); 133 else if (sizeof(BitWord) == 8) 134 return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 135 else 136 assert(0 && "Unsupported!"); 137 } 138 return -1; 139 } 140 141 /// find_next - Returns the index of the next set bit following the 142 /// "Prev" bit. Returns -1 if the next set bit is not found. 143 int find_next(unsigned Prev) const { 144 ++Prev; 145 if (Prev >= Size) 146 return -1; 147 148 unsigned WordPos = Prev / BITWORD_SIZE; 149 unsigned BitPos = Prev % BITWORD_SIZE; 150 BitWord Copy = Bits[WordPos]; 151 // Mask off previous bits. 152 Copy &= ~0L << BitPos; 153 154 if (Copy != 0) { 155 if (sizeof(BitWord) == 4) 156 return WordPos * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Copy); 157 else if (sizeof(BitWord) == 8) 158 return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); 159 else 160 assert(0 && "Unsupported!"); 161 } 162 163 // Check subsequent words. 164 for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i) 165 if (Bits[i] != 0) { 166 if (sizeof(BitWord) == 4) 167 return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); 168 else if (sizeof(BitWord) == 8) 169 return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 170 else 171 assert(0 && "Unsupported!"); 172 } 173 return -1; 174 } 175 176 /// clear - Clear all bits. 177 void clear() { 178 Size = 0; 179 } 180 181 /// resize - Grow or shrink the bitvector. 182 void resize(unsigned N, bool t = false) { 183 if (N > Capacity * BITWORD_SIZE) { 184 unsigned OldCapacity = Capacity; 185 grow(N); 186 init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t); 187 } 188 189 // Set any old unused bits that are now included in the BitVector. This 190 // may set bits that are not included in the new vector, but we will clear 191 // them back out below. 192 if (N > Size) 193 set_unused_bits(t); 194 195 // Update the size, and clear out any bits that are now unused 196 unsigned OldSize = Size; 197 Size = N; 198 if (t || N < OldSize) 199 clear_unused_bits(); 200 } 201 202 void reserve(unsigned N) { 203 if (N > Capacity * BITWORD_SIZE) 204 grow(N); 205 } 206 207 // Set, reset, flip 208 BitVector &set() { 209 init_words(Bits, Capacity, true); 210 clear_unused_bits(); 211 return *this; 212 } 213 214 BitVector &set(unsigned Idx) { 215 Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); 216 return *this; 217 } 218 219 BitVector &reset() { 220 init_words(Bits, Capacity, false); 221 return *this; 222 } 223 224 BitVector &reset(unsigned Idx) { 225 Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); 226 return *this; 227 } 228 229 BitVector &flip() { 230 for (unsigned i = 0; i < NumBitWords(size()); ++i) 231 Bits[i] = ~Bits[i]; 232 clear_unused_bits(); 233 return *this; 234 } 235 236 BitVector &flip(unsigned Idx) { 237 Bits[Idx / BITWORD_SIZE] ^= 1L << (Idx % BITWORD_SIZE); 238 return *this; 239 } 240 241 // No argument flip. 242 BitVector operator~() const { 243 return BitVector(*this).flip(); 244 } 245 246 // Indexing. 247 reference operator[](unsigned Idx) { 248 assert (Idx < Size && "Out-of-bounds Bit access."); 249 return reference(*this, Idx); 250 } 251 252 bool operator[](unsigned Idx) const { 253 assert (Idx < Size && "Out-of-bounds Bit access."); 254 BitWord Mask = 1L << (Idx % BITWORD_SIZE); 255 return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; 256 } 257 258 bool test(unsigned Idx) const { 259 return (*this)[Idx]; 260 } 261 262 // Comparison operators. 263 bool operator==(const BitVector &RHS) const { 264 unsigned ThisWords = NumBitWords(size()); 265 unsigned RHSWords = NumBitWords(RHS.size()); 266 unsigned i; 267 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 268 if (Bits[i] != RHS.Bits[i]) 269 return false; 270 271 // Verify that any extra words are all zeros. 272 if (i != ThisWords) { 273 for (; i != ThisWords; ++i) 274 if (Bits[i]) 275 return false; 276 } else if (i != RHSWords) { 277 for (; i != RHSWords; ++i) 278 if (RHS.Bits[i]) 279 return false; 280 } 281 return true; 282 } 283 284 bool operator!=(const BitVector &RHS) const { 285 return !(*this == RHS); 286 } 287 288 // Intersection, union, disjoint union. 289 BitVector operator&=(const BitVector &RHS) { 290 unsigned ThisWords = NumBitWords(size()); 291 unsigned RHSWords = NumBitWords(RHS.size()); 292 unsigned i; 293 for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 294 Bits[i] &= RHS.Bits[i]; 295 296 // Any bits that are just in this bitvector become zero, because they aren't 297 // in the RHS bit vector. Any words only in RHS are ignored because they 298 // are already zero in the LHS. 299 for (; i != ThisWords; ++i) 300 Bits[i] = 0; 301 302 return *this; 303 } 304 305 BitVector operator|=(const BitVector &RHS) { 306 assert(Size == RHS.Size && "Illegal operation!"); 307 for (unsigned i = 0; i < NumBitWords(size()); ++i) 308 Bits[i] |= RHS.Bits[i]; 309 return *this; 310 } 311 312 BitVector operator^=(const BitVector &RHS) { 313 assert(Size == RHS.Size && "Illegal operation!"); 314 for (unsigned i = 0; i < NumBitWords(size()); ++i) 315 Bits[i] ^= RHS.Bits[i]; 316 return *this; 317 } 318 319 // Assignment operator. 320 const BitVector &operator=(const BitVector &RHS) { 321 if (this == &RHS) return *this; 322 323 Size = RHS.size(); 324 unsigned RHSWords = NumBitWords(Size); 325 if (Size <= Capacity * BITWORD_SIZE) { 326 std::copy(RHS.Bits, &RHS.Bits[RHSWords], Bits); 327 clear_unused_bits(); 328 return *this; 329 } 330 331 // Grow the bitvector to have enough elements. 332 Capacity = RHSWords; 333 BitWord *NewBits = new BitWord[Capacity]; 334 std::copy(RHS.Bits, &RHS.Bits[RHSWords], NewBits); 335 336 // Destroy the old bits. 337 delete[] Bits; 338 Bits = NewBits; 339 340 return *this; 341 } 342 343private: 344 unsigned NumBitWords(unsigned S) const { 345 return (S + BITWORD_SIZE-1) / BITWORD_SIZE; 346 } 347 348 // Set the unused bits in the high words. 349 void set_unused_bits(bool t = true) { 350 // Set high words first. 351 unsigned UsedWords = NumBitWords(Size); 352 if (Capacity > UsedWords) 353 init_words(&Bits[UsedWords], (Capacity-UsedWords), t); 354 355 // Then set any stray high bits of the last used word. 356 unsigned ExtraBits = Size % BITWORD_SIZE; 357 if (ExtraBits) { 358 Bits[UsedWords-1] &= ~(~0L << ExtraBits); 359 Bits[UsedWords-1] |= (0 - (BitWord)t) << ExtraBits; 360 } 361 } 362 363 // Clear the unused bits in the high words. 364 void clear_unused_bits() { 365 set_unused_bits(false); 366 } 367 368 void grow(unsigned NewSize) { 369 unsigned OldCapacity = Capacity; 370 Capacity = NumBitWords(NewSize); 371 BitWord *NewBits = new BitWord[Capacity]; 372 373 // Copy the old bits over. 374 if (OldCapacity != 0) 375 std::copy(Bits, &Bits[OldCapacity], NewBits); 376 377 // Destroy the old bits. 378 delete[] Bits; 379 Bits = NewBits; 380 381 clear_unused_bits(); 382 } 383 384 void init_words(BitWord *B, unsigned NumWords, bool t) { 385 memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); 386 } 387}; 388 389inline BitVector operator&(const BitVector &LHS, const BitVector &RHS) { 390 BitVector Result(LHS); 391 Result &= RHS; 392 return Result; 393} 394 395inline BitVector operator|(const BitVector &LHS, const BitVector &RHS) { 396 BitVector Result(LHS); 397 Result |= RHS; 398 return Result; 399} 400 401inline BitVector operator^(const BitVector &LHS, const BitVector &RHS) { 402 BitVector Result(LHS); 403 Result ^= RHS; 404 return Result; 405} 406 407} // End llvm namespace 408#endif 409