1 //===- llvm/ADT/SmallBitVector.h - 'Normally small' 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 SmallBitVector class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_SMALLBITVECTOR_H 15 #define LLVM_ADT_SMALLBITVECTOR_H 16 17 #include "llvm/ADT/BitVector.h" 18 #include "llvm/Support/MathExtras.h" 19 #include <cassert> 20 21 namespace llvm { 22 23 /// SmallBitVector - This is a 'bitvector' (really, a variable-sized bit array), 24 /// optimized for the case when the array is small. It contains one 25 /// pointer-sized field, which is directly used as a plain collection of bits 26 /// when possible, or as a pointer to a larger heap-allocated array when 27 /// necessary. This allows normal "small" cases to be fast without losing 28 /// generality for large inputs. 29 /// 30 class SmallBitVector { 31 // TODO: In "large" mode, a pointer to a BitVector is used, leading to an 32 // unnecessary level of indirection. It would be more efficient to use a 33 // pointer to memory containing size, allocation size, and the array of bits. 34 uintptr_t X; 35 36 enum { 37 // The number of bits in this class. 38 NumBaseBits = sizeof(uintptr_t) * CHAR_BIT, 39 40 // One bit is used to discriminate between small and large mode. The 41 // remaining bits are used for the small-mode representation. 42 SmallNumRawBits = NumBaseBits - 1, 43 44 // A few more bits are used to store the size of the bit set in small mode. 45 // Theoretically this is a ceil-log2. These bits are encoded in the most 46 // significant bits of the raw bits. 47 SmallNumSizeBits = (NumBaseBits == 32 ? 5 : 48 NumBaseBits == 64 ? 6 : 49 SmallNumRawBits), 50 51 // The remaining bits are used to store the actual set in small mode. 52 SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits 53 }; 54 55 public: 56 // Encapsulation of a single bit. 57 class reference { 58 SmallBitVector &TheVector; 59 unsigned BitPos; 60 61 public: reference(SmallBitVector & b,unsigned Idx)62 reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} 63 64 reference& operator=(reference t) { 65 *this = bool(t); 66 return *this; 67 } 68 69 reference& operator=(bool t) { 70 if (t) 71 TheVector.set(BitPos); 72 else 73 TheVector.reset(BitPos); 74 return *this; 75 } 76 77 operator bool() const { 78 return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); 79 } 80 }; 81 82 private: isSmall()83 bool isSmall() const { 84 return X & uintptr_t(1); 85 } 86 getPointer()87 BitVector *getPointer() const { 88 assert(!isSmall()); 89 return reinterpret_cast<BitVector *>(X); 90 } 91 switchToSmall(uintptr_t NewSmallBits,size_t NewSize)92 void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { 93 X = 1; 94 setSmallSize(NewSize); 95 setSmallBits(NewSmallBits); 96 } 97 switchToLarge(BitVector * BV)98 void switchToLarge(BitVector *BV) { 99 X = reinterpret_cast<uintptr_t>(BV); 100 assert(!isSmall() && "Tried to use an unaligned pointer"); 101 } 102 103 // Return all the bits used for the "small" representation; this includes 104 // bits for the size as well as the element bits. getSmallRawBits()105 uintptr_t getSmallRawBits() const { 106 assert(isSmall()); 107 return X >> 1; 108 } 109 setSmallRawBits(uintptr_t NewRawBits)110 void setSmallRawBits(uintptr_t NewRawBits) { 111 assert(isSmall()); 112 X = (NewRawBits << 1) | uintptr_t(1); 113 } 114 115 // Return the size. getSmallSize()116 size_t getSmallSize() const { 117 return getSmallRawBits() >> SmallNumDataBits; 118 } 119 setSmallSize(size_t Size)120 void setSmallSize(size_t Size) { 121 setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); 122 } 123 124 // Return the element bits. getSmallBits()125 uintptr_t getSmallBits() const { 126 return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); 127 } 128 setSmallBits(uintptr_t NewBits)129 void setSmallBits(uintptr_t NewBits) { 130 setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | 131 (getSmallSize() << SmallNumDataBits)); 132 } 133 134 public: 135 /// SmallBitVector default ctor - Creates an empty bitvector. SmallBitVector()136 SmallBitVector() : X(1) {} 137 138 /// SmallBitVector ctor - Creates a bitvector of specified number of bits. All 139 /// bits are initialized to the specified value. 140 explicit SmallBitVector(unsigned s, bool t = false) { 141 if (s <= SmallNumDataBits) 142 switchToSmall(t ? ~uintptr_t(0) : 0, s); 143 else 144 switchToLarge(new BitVector(s, t)); 145 } 146 147 /// SmallBitVector copy ctor. SmallBitVector(const SmallBitVector & RHS)148 SmallBitVector(const SmallBitVector &RHS) { 149 if (RHS.isSmall()) 150 X = RHS.X; 151 else 152 switchToLarge(new BitVector(*RHS.getPointer())); 153 } 154 ~SmallBitVector()155 ~SmallBitVector() { 156 if (!isSmall()) 157 delete getPointer(); 158 } 159 160 /// empty - Tests whether there are no bits in this bitvector. empty()161 bool empty() const { 162 return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); 163 } 164 165 /// size - Returns the number of bits in this bitvector. size()166 size_t size() const { 167 return isSmall() ? getSmallSize() : getPointer()->size(); 168 } 169 170 /// count - Returns the number of bits which are set. count()171 unsigned count() const { 172 if (isSmall()) { 173 uintptr_t Bits = getSmallBits(); 174 if (sizeof(uintptr_t) * CHAR_BIT == 32) 175 return CountPopulation_32(Bits); 176 if (sizeof(uintptr_t) * CHAR_BIT == 64) 177 return CountPopulation_64(Bits); 178 assert(0 && "Unsupported!"); 179 } 180 return getPointer()->count(); 181 } 182 183 /// any - Returns true if any bit is set. any()184 bool any() const { 185 if (isSmall()) 186 return getSmallBits() != 0; 187 return getPointer()->any(); 188 } 189 190 /// none - Returns true if none of the bits are set. none()191 bool none() const { 192 if (isSmall()) 193 return getSmallBits() == 0; 194 return getPointer()->none(); 195 } 196 197 /// find_first - Returns the index of the first set bit, -1 if none 198 /// of the bits are set. find_first()199 int find_first() const { 200 if (isSmall()) { 201 uintptr_t Bits = getSmallBits(); 202 if (Bits == 0) 203 return -1; 204 if (sizeof(uintptr_t) * CHAR_BIT == 32) 205 return CountTrailingZeros_32(Bits); 206 if (sizeof(uintptr_t) * CHAR_BIT == 64) 207 return CountTrailingZeros_64(Bits); 208 assert(0 && "Unsupported!"); 209 } 210 return getPointer()->find_first(); 211 } 212 213 /// find_next - Returns the index of the next set bit following the 214 /// "Prev" bit. Returns -1 if the next set bit is not found. find_next(unsigned Prev)215 int find_next(unsigned Prev) const { 216 if (isSmall()) { 217 uintptr_t Bits = getSmallBits(); 218 // Mask off previous bits. 219 Bits &= ~uintptr_t(0) << (Prev + 1); 220 if (Bits == 0 || Prev + 1 >= getSmallSize()) 221 return -1; 222 if (sizeof(uintptr_t) * CHAR_BIT == 32) 223 return CountTrailingZeros_32(Bits); 224 if (sizeof(uintptr_t) * CHAR_BIT == 64) 225 return CountTrailingZeros_64(Bits); 226 assert(0 && "Unsupported!"); 227 } 228 return getPointer()->find_next(Prev); 229 } 230 231 /// clear - Clear all bits. clear()232 void clear() { 233 if (!isSmall()) 234 delete getPointer(); 235 switchToSmall(0, 0); 236 } 237 238 /// resize - Grow or shrink the bitvector. 239 void resize(unsigned N, bool t = false) { 240 if (!isSmall()) { 241 getPointer()->resize(N, t); 242 } else if (SmallNumDataBits >= N) { 243 uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; 244 setSmallSize(N); 245 setSmallBits(NewBits | getSmallBits()); 246 } else { 247 BitVector *BV = new BitVector(N, t); 248 uintptr_t OldBits = getSmallBits(); 249 for (size_t i = 0, e = getSmallSize(); i != e; ++i) 250 (*BV)[i] = (OldBits >> i) & 1; 251 switchToLarge(BV); 252 } 253 } 254 reserve(unsigned N)255 void reserve(unsigned N) { 256 if (isSmall()) { 257 if (N > SmallNumDataBits) { 258 uintptr_t OldBits = getSmallRawBits(); 259 size_t SmallSize = getSmallSize(); 260 BitVector *BV = new BitVector(SmallSize); 261 for (size_t i = 0; i < SmallSize; ++i) 262 if ((OldBits >> i) & 1) 263 BV->set(i); 264 BV->reserve(N); 265 switchToLarge(BV); 266 } 267 } else { 268 getPointer()->reserve(N); 269 } 270 } 271 272 // Set, reset, flip set()273 SmallBitVector &set() { 274 if (isSmall()) 275 setSmallBits(~uintptr_t(0)); 276 else 277 getPointer()->set(); 278 return *this; 279 } 280 set(unsigned Idx)281 SmallBitVector &set(unsigned Idx) { 282 if (isSmall()) 283 setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); 284 else 285 getPointer()->set(Idx); 286 return *this; 287 } 288 reset()289 SmallBitVector &reset() { 290 if (isSmall()) 291 setSmallBits(0); 292 else 293 getPointer()->reset(); 294 return *this; 295 } 296 reset(unsigned Idx)297 SmallBitVector &reset(unsigned Idx) { 298 if (isSmall()) 299 setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); 300 else 301 getPointer()->reset(Idx); 302 return *this; 303 } 304 flip()305 SmallBitVector &flip() { 306 if (isSmall()) 307 setSmallBits(~getSmallBits()); 308 else 309 getPointer()->flip(); 310 return *this; 311 } 312 flip(unsigned Idx)313 SmallBitVector &flip(unsigned Idx) { 314 if (isSmall()) 315 setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); 316 else 317 getPointer()->flip(Idx); 318 return *this; 319 } 320 321 // No argument flip. 322 SmallBitVector operator~() const { 323 return SmallBitVector(*this).flip(); 324 } 325 326 // Indexing. 327 reference operator[](unsigned Idx) { 328 assert(Idx < size() && "Out-of-bounds Bit access."); 329 return reference(*this, Idx); 330 } 331 332 bool operator[](unsigned Idx) const { 333 assert(Idx < size() && "Out-of-bounds Bit access."); 334 if (isSmall()) 335 return ((getSmallBits() >> Idx) & 1) != 0; 336 return getPointer()->operator[](Idx); 337 } 338 test(unsigned Idx)339 bool test(unsigned Idx) const { 340 return (*this)[Idx]; 341 } 342 343 // Comparison operators. 344 bool operator==(const SmallBitVector &RHS) const { 345 if (size() != RHS.size()) 346 return false; 347 if (isSmall()) 348 return getSmallBits() == RHS.getSmallBits(); 349 else 350 return *getPointer() == *RHS.getPointer(); 351 } 352 353 bool operator!=(const SmallBitVector &RHS) const { 354 return !(*this == RHS); 355 } 356 357 // Intersection, union, disjoint union. 358 SmallBitVector &operator&=(const SmallBitVector &RHS) { 359 resize(std::max(size(), RHS.size())); 360 if (isSmall()) 361 setSmallBits(getSmallBits() & RHS.getSmallBits()); 362 else if (!RHS.isSmall()) 363 getPointer()->operator&=(*RHS.getPointer()); 364 else { 365 SmallBitVector Copy = RHS; 366 Copy.resize(size()); 367 getPointer()->operator&=(*Copy.getPointer()); 368 } 369 return *this; 370 } 371 372 SmallBitVector &operator|=(const SmallBitVector &RHS) { 373 resize(std::max(size(), RHS.size())); 374 if (isSmall()) 375 setSmallBits(getSmallBits() | RHS.getSmallBits()); 376 else if (!RHS.isSmall()) 377 getPointer()->operator|=(*RHS.getPointer()); 378 else { 379 SmallBitVector Copy = RHS; 380 Copy.resize(size()); 381 getPointer()->operator|=(*Copy.getPointer()); 382 } 383 return *this; 384 } 385 386 SmallBitVector &operator^=(const SmallBitVector &RHS) { 387 resize(std::max(size(), RHS.size())); 388 if (isSmall()) 389 setSmallBits(getSmallBits() ^ RHS.getSmallBits()); 390 else if (!RHS.isSmall()) 391 getPointer()->operator^=(*RHS.getPointer()); 392 else { 393 SmallBitVector Copy = RHS; 394 Copy.resize(size()); 395 getPointer()->operator^=(*Copy.getPointer()); 396 } 397 return *this; 398 } 399 400 // Assignment operator. 401 const SmallBitVector &operator=(const SmallBitVector &RHS) { 402 if (isSmall()) { 403 if (RHS.isSmall()) 404 X = RHS.X; 405 else 406 switchToLarge(new BitVector(*RHS.getPointer())); 407 } else { 408 if (!RHS.isSmall()) 409 *getPointer() = *RHS.getPointer(); 410 else { 411 delete getPointer(); 412 X = RHS.X; 413 } 414 } 415 return *this; 416 } 417 swap(SmallBitVector & RHS)418 void swap(SmallBitVector &RHS) { 419 std::swap(X, RHS.X); 420 } 421 }; 422 423 inline SmallBitVector 424 operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { 425 SmallBitVector Result(LHS); 426 Result &= RHS; 427 return Result; 428 } 429 430 inline SmallBitVector 431 operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { 432 SmallBitVector Result(LHS); 433 Result |= RHS; 434 return Result; 435 } 436 437 inline SmallBitVector 438 operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { 439 SmallBitVector Result(LHS); 440 Result ^= RHS; 441 return Result; 442 } 443 444 } // End llvm namespace 445 446 namespace std { 447 /// Implement std::swap in terms of BitVector swap. 448 inline void swap(llvm::SmallBitVector & LHS,llvm::SmallBitVector & RHS)449 swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { 450 LHS.swap(RHS); 451 } 452 } 453 454 #endif 455