BitVector.h revision 0c81450a0c1f859738a2f209a89de10f889fcd84
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#include <algorithm> 19#include <cstdlib> 20#include <cassert> 21 22namespace llvm { 23 24class BitVector { 25 typedef unsigned long BitWord; 26 27 enum { BITWORD_SIZE = 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); 61 } 62 }; 63 64 65 /// BitVector default ctor - Creates an empty bitvector. 66 BitVector() : Size(0), Capacity(0) { 67 Bits = NULL; 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 = NULL; 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(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(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(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(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 // If we previously had no size, initialize the low word 190 if (Size == 0) 191 Bits[0] = t; 192 193 Size = N; 194 clear_unused_bits(); 195 } 196 197 void reserve(unsigned N) { 198 if (N > Capacity * BITWORD_SIZE) 199 grow(N); 200 } 201 202 // Set, reset, flip 203 BitVector &set() { 204 init_words(Bits, Capacity, true); 205 clear_unused_bits(); 206 return *this; 207 } 208 209 BitVector &set(unsigned Idx) { 210 Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); 211 return *this; 212 } 213 214 BitVector &reset() { 215 init_words(Bits, Capacity, false); 216 return *this; 217 } 218 219 BitVector &reset(unsigned Idx) { 220 Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); 221 return *this; 222 } 223 224 BitVector &flip() { 225 for (unsigned i = 0; i < NumBitWords(size()); ++i) 226 Bits[i] = ~Bits[i]; 227 clear_unused_bits(); 228 return *this; 229 } 230 231 BitVector &flip(unsigned Idx) { 232 Bits[Idx / BITWORD_SIZE] ^= 1L << (Idx % BITWORD_SIZE); 233 return *this; 234 } 235 236 // No argument flip. 237 BitVector operator~() const { 238 return BitVector(*this).flip(); 239 } 240 241 // Indexing. 242 reference operator[](unsigned Idx) { 243 return reference(*this, Idx); 244 } 245 246 bool operator[](unsigned Idx) const { 247 BitWord Mask = 1L << (Idx % BITWORD_SIZE); 248 return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; 249 } 250 251 bool test(unsigned Idx) const { 252 return (*this)[Idx]; 253 } 254 255 // Comparison operators. 256 bool operator==(const BitVector &RHS) const { 257 if (Size != RHS.Size) 258 return false; 259 260 for (unsigned i = 0; i < NumBitWords(size()); ++i) 261 if (Bits[i] != RHS.Bits[i]) 262 return false; 263 return true; 264 } 265 266 bool operator!=(const BitVector &RHS) const { 267 return !(*this == RHS); 268 } 269 270 // Intersection, union, disjoint union. 271 BitVector operator&=(const BitVector &RHS) { 272 assert(Size == RHS.Size && "Illegal operation!"); 273 for (unsigned i = 0; i < NumBitWords(size()); ++i) 274 Bits[i] &= RHS.Bits[i]; 275 return *this; 276 } 277 278 BitVector operator|=(const BitVector &RHS) { 279 assert(Size == RHS.Size && "Illegal operation!"); 280 for (unsigned i = 0; i < NumBitWords(size()); ++i) 281 Bits[i] |= RHS.Bits[i]; 282 return *this; 283 } 284 285 BitVector operator^=(const BitVector &RHS) { 286 assert(Size == RHS.Size && "Illegal operation!"); 287 for (unsigned i = 0; i < NumBitWords(size()); ++i) 288 Bits[i] ^= RHS.Bits[i]; 289 return *this; 290 } 291 292 // Assignment operator. 293 const BitVector &operator=(const BitVector &RHS) { 294 if (this == &RHS) return *this; 295 296 Size = RHS.size(); 297 unsigned RHSWords = NumBitWords(Size); 298 if (Size <= Capacity * BITWORD_SIZE) { 299 std::copy(RHS.Bits, &RHS.Bits[RHSWords], Bits); 300 clear_unused_bits(); 301 return *this; 302 } 303 304 // Grow the bitvector to have enough elements. 305 Capacity = NumBitWords(Size); 306 BitWord *NewBits = new BitWord[Capacity]; 307 std::copy(RHS.Bits, &RHS.Bits[RHSWords], NewBits); 308 309 // Destroy the old bits. 310 delete[] Bits; 311 Bits = NewBits; 312 313 return *this; 314 } 315 316private: 317 unsigned NumBitWords(unsigned S) const { 318 return (S + BITWORD_SIZE-1) / BITWORD_SIZE; 319 } 320 321 // Clear the unused top bits in the high word. 322 void clear_unused_bits() { 323 unsigned ExtraBits = Size % BITWORD_SIZE; 324 if (ExtraBits) { 325 unsigned index = Size / BITWORD_SIZE; 326 Bits[index] &= ~(~0L << ExtraBits); 327 } 328 } 329 330 void grow(unsigned NewSize) { 331 unsigned OldCapacity = Capacity; 332 Capacity = NumBitWords(NewSize); 333 BitWord *NewBits = new BitWord[Capacity]; 334 335 // Copy the old bits over. 336 if (OldCapacity != 0) 337 std::copy(Bits, &Bits[OldCapacity], NewBits); 338 339 // Destroy the old bits. 340 delete[] Bits; 341 Bits = NewBits; 342 } 343 344 void init_words(BitWord *B, unsigned NumWords, bool t) { 345 memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); 346 } 347}; 348 349inline BitVector operator&(const BitVector &LHS, const BitVector &RHS) { 350 BitVector Result(LHS); 351 Result &= RHS; 352 return Result; 353} 354 355inline BitVector operator|(const BitVector &LHS, const BitVector &RHS) { 356 BitVector Result(LHS); 357 Result |= RHS; 358 return Result; 359} 360 361inline BitVector operator^(const BitVector &LHS, const BitVector &RHS) { 362 BitVector Result(LHS); 363 Result ^= RHS; 364 return Result; 365} 366 367} // End llvm namespace 368#endif 369