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