1202375Srdivacky//===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===// 2202375Srdivacky// 3202375Srdivacky// The LLVM Compiler Infrastructure 4202375Srdivacky// 5202375Srdivacky// This file is distributed under the University of Illinois Open Source 6202375Srdivacky// License. See LICENSE.TXT for details. 7202375Srdivacky// 8202375Srdivacky//===----------------------------------------------------------------------===// 9202375Srdivacky// 10202375Srdivacky// This file implements the SmallBitVector class. 11202375Srdivacky// 12202375Srdivacky//===----------------------------------------------------------------------===// 13202375Srdivacky 14202375Srdivacky#ifndef LLVM_ADT_SMALLBITVECTOR_H 15202375Srdivacky#define LLVM_ADT_SMALLBITVECTOR_H 16202375Srdivacky 17202375Srdivacky#include "llvm/ADT/BitVector.h" 18245431Sdim#include "llvm/Support/Compiler.h" 19202375Srdivacky#include "llvm/Support/MathExtras.h" 20202375Srdivacky#include <cassert> 21202375Srdivacky 22202375Srdivackynamespace llvm { 23202375Srdivacky 24202375Srdivacky/// SmallBitVector - This is a 'bitvector' (really, a variable-sized bit array), 25202375Srdivacky/// optimized for the case when the array is small. It contains one 26202375Srdivacky/// pointer-sized field, which is directly used as a plain collection of bits 27202375Srdivacky/// when possible, or as a pointer to a larger heap-allocated array when 28202375Srdivacky/// necessary. This allows normal "small" cases to be fast without losing 29202375Srdivacky/// generality for large inputs. 30202375Srdivacky/// 31202375Srdivackyclass SmallBitVector { 32202375Srdivacky // TODO: In "large" mode, a pointer to a BitVector is used, leading to an 33202375Srdivacky // unnecessary level of indirection. It would be more efficient to use a 34202375Srdivacky // pointer to memory containing size, allocation size, and the array of bits. 35207618Srdivacky uintptr_t X; 36202375Srdivacky 37207618Srdivacky enum { 38207618Srdivacky // The number of bits in this class. 39207618Srdivacky NumBaseBits = sizeof(uintptr_t) * CHAR_BIT, 40202375Srdivacky 41207618Srdivacky // One bit is used to discriminate between small and large mode. The 42207618Srdivacky // remaining bits are used for the small-mode representation. 43207618Srdivacky SmallNumRawBits = NumBaseBits - 1, 44202375Srdivacky 45207618Srdivacky // A few more bits are used to store the size of the bit set in small mode. 46207618Srdivacky // Theoretically this is a ceil-log2. These bits are encoded in the most 47207618Srdivacky // significant bits of the raw bits. 48207618Srdivacky SmallNumSizeBits = (NumBaseBits == 32 ? 5 : 49207618Srdivacky NumBaseBits == 64 ? 6 : 50207618Srdivacky SmallNumRawBits), 51202375Srdivacky 52207618Srdivacky // The remaining bits are used to store the actual set in small mode. 53207618Srdivacky SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits 54207618Srdivacky }; 55202375Srdivacky 56207618Srdivackypublic: 57207618Srdivacky // Encapsulation of a single bit. 58207618Srdivacky class reference { 59207618Srdivacky SmallBitVector &TheVector; 60207618Srdivacky unsigned BitPos; 61207618Srdivacky 62207618Srdivacky public: 63207618Srdivacky reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} 64207618Srdivacky 65207618Srdivacky reference& operator=(reference t) { 66207618Srdivacky *this = bool(t); 67207618Srdivacky return *this; 68207618Srdivacky } 69207618Srdivacky 70207618Srdivacky reference& operator=(bool t) { 71207618Srdivacky if (t) 72207618Srdivacky TheVector.set(BitPos); 73207618Srdivacky else 74207618Srdivacky TheVector.reset(BitPos); 75207618Srdivacky return *this; 76207618Srdivacky } 77207618Srdivacky 78207618Srdivacky operator bool() const { 79207618Srdivacky return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); 80207618Srdivacky } 81207618Srdivacky }; 82207618Srdivacky 83207618Srdivackyprivate: 84202375Srdivacky bool isSmall() const { 85207618Srdivacky return X & uintptr_t(1); 86202375Srdivacky } 87202375Srdivacky 88207618Srdivacky BitVector *getPointer() const { 89207618Srdivacky assert(!isSmall()); 90207618Srdivacky return reinterpret_cast<BitVector *>(X); 91207618Srdivacky } 92207618Srdivacky 93202375Srdivacky void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { 94207618Srdivacky X = 1; 95202375Srdivacky setSmallSize(NewSize); 96202375Srdivacky setSmallBits(NewSmallBits); 97202375Srdivacky } 98202375Srdivacky 99202375Srdivacky void switchToLarge(BitVector *BV) { 100207618Srdivacky X = reinterpret_cast<uintptr_t>(BV); 101207618Srdivacky assert(!isSmall() && "Tried to use an unaligned pointer"); 102202375Srdivacky } 103202375Srdivacky 104202375Srdivacky // Return all the bits used for the "small" representation; this includes 105202375Srdivacky // bits for the size as well as the element bits. 106202375Srdivacky uintptr_t getSmallRawBits() const { 107207618Srdivacky assert(isSmall()); 108207618Srdivacky return X >> 1; 109202375Srdivacky } 110202375Srdivacky 111202375Srdivacky void setSmallRawBits(uintptr_t NewRawBits) { 112207618Srdivacky assert(isSmall()); 113207618Srdivacky X = (NewRawBits << 1) | uintptr_t(1); 114202375Srdivacky } 115202375Srdivacky 116202375Srdivacky // Return the size. 117202375Srdivacky size_t getSmallSize() const { 118202375Srdivacky return getSmallRawBits() >> SmallNumDataBits; 119202375Srdivacky } 120202375Srdivacky 121202375Srdivacky void setSmallSize(size_t Size) { 122202375Srdivacky setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); 123202375Srdivacky } 124202375Srdivacky 125202375Srdivacky // Return the element bits. 126202375Srdivacky uintptr_t getSmallBits() const { 127207618Srdivacky return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); 128202375Srdivacky } 129202375Srdivacky 130202375Srdivacky void setSmallBits(uintptr_t NewBits) { 131207618Srdivacky setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | 132207618Srdivacky (getSmallSize() << SmallNumDataBits)); 133202375Srdivacky } 134202375Srdivacky 135202375Srdivackypublic: 136202375Srdivacky /// SmallBitVector default ctor - Creates an empty bitvector. 137207618Srdivacky SmallBitVector() : X(1) {} 138202375Srdivacky 139202375Srdivacky /// SmallBitVector ctor - Creates a bitvector of specified number of bits. All 140202375Srdivacky /// bits are initialized to the specified value. 141207618Srdivacky explicit SmallBitVector(unsigned s, bool t = false) { 142207618Srdivacky if (s <= SmallNumDataBits) 143202375Srdivacky switchToSmall(t ? ~uintptr_t(0) : 0, s); 144202375Srdivacky else 145202375Srdivacky switchToLarge(new BitVector(s, t)); 146202375Srdivacky } 147202375Srdivacky 148202375Srdivacky /// SmallBitVector copy ctor. 149202375Srdivacky SmallBitVector(const SmallBitVector &RHS) { 150202375Srdivacky if (RHS.isSmall()) 151202375Srdivacky X = RHS.X; 152202375Srdivacky else 153207618Srdivacky switchToLarge(new BitVector(*RHS.getPointer())); 154202375Srdivacky } 155202375Srdivacky 156252723Sdim#if LLVM_HAS_RVALUE_REFERENCES 157245431Sdim SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { 158245431Sdim RHS.X = 1; 159245431Sdim } 160245431Sdim#endif 161245431Sdim 162202375Srdivacky ~SmallBitVector() { 163202375Srdivacky if (!isSmall()) 164207618Srdivacky delete getPointer(); 165202375Srdivacky } 166202375Srdivacky 167202375Srdivacky /// empty - Tests whether there are no bits in this bitvector. 168202375Srdivacky bool empty() const { 169207618Srdivacky return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); 170202375Srdivacky } 171202375Srdivacky 172202375Srdivacky /// size - Returns the number of bits in this bitvector. 173202375Srdivacky size_t size() const { 174207618Srdivacky return isSmall() ? getSmallSize() : getPointer()->size(); 175202375Srdivacky } 176202375Srdivacky 177202375Srdivacky /// count - Returns the number of bits which are set. 178202375Srdivacky unsigned count() const { 179202375Srdivacky if (isSmall()) { 180202375Srdivacky uintptr_t Bits = getSmallBits(); 181252723Sdim if (NumBaseBits == 32) 182202375Srdivacky return CountPopulation_32(Bits); 183252723Sdim if (NumBaseBits == 64) 184202375Srdivacky return CountPopulation_64(Bits); 185235633Sdim llvm_unreachable("Unsupported!"); 186202375Srdivacky } 187207618Srdivacky return getPointer()->count(); 188202375Srdivacky } 189202375Srdivacky 190202375Srdivacky /// any - Returns true if any bit is set. 191202375Srdivacky bool any() const { 192202375Srdivacky if (isSmall()) 193202375Srdivacky return getSmallBits() != 0; 194207618Srdivacky return getPointer()->any(); 195202375Srdivacky } 196202375Srdivacky 197218893Sdim /// all - Returns true if all bits are set. 198218893Sdim bool all() const { 199218893Sdim if (isSmall()) 200218893Sdim return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; 201218893Sdim return getPointer()->all(); 202218893Sdim } 203218893Sdim 204202375Srdivacky /// none - Returns true if none of the bits are set. 205202375Srdivacky bool none() const { 206202375Srdivacky if (isSmall()) 207202375Srdivacky return getSmallBits() == 0; 208207618Srdivacky return getPointer()->none(); 209202375Srdivacky } 210202375Srdivacky 211202375Srdivacky /// find_first - Returns the index of the first set bit, -1 if none 212202375Srdivacky /// of the bits are set. 213202375Srdivacky int find_first() const { 214202375Srdivacky if (isSmall()) { 215202375Srdivacky uintptr_t Bits = getSmallBits(); 216207618Srdivacky if (Bits == 0) 217207618Srdivacky return -1; 218252723Sdim if (NumBaseBits == 32) 219263509Sdim return countTrailingZeros(Bits); 220252723Sdim if (NumBaseBits == 64) 221263509Sdim return countTrailingZeros(Bits); 222235633Sdim llvm_unreachable("Unsupported!"); 223202375Srdivacky } 224207618Srdivacky return getPointer()->find_first(); 225202375Srdivacky } 226202375Srdivacky 227202375Srdivacky /// find_next - Returns the index of the next set bit following the 228202375Srdivacky /// "Prev" bit. Returns -1 if the next set bit is not found. 229202375Srdivacky int find_next(unsigned Prev) const { 230202375Srdivacky if (isSmall()) { 231202375Srdivacky uintptr_t Bits = getSmallBits(); 232202375Srdivacky // Mask off previous bits. 233207618Srdivacky Bits &= ~uintptr_t(0) << (Prev + 1); 234207618Srdivacky if (Bits == 0 || Prev + 1 >= getSmallSize()) 235207618Srdivacky return -1; 236252723Sdim if (NumBaseBits == 32) 237263509Sdim return countTrailingZeros(Bits); 238252723Sdim if (NumBaseBits == 64) 239263509Sdim return countTrailingZeros(Bits); 240235633Sdim llvm_unreachable("Unsupported!"); 241202375Srdivacky } 242207618Srdivacky return getPointer()->find_next(Prev); 243202375Srdivacky } 244202375Srdivacky 245202375Srdivacky /// clear - Clear all bits. 246202375Srdivacky void clear() { 247202375Srdivacky if (!isSmall()) 248207618Srdivacky delete getPointer(); 249202375Srdivacky switchToSmall(0, 0); 250202375Srdivacky } 251202375Srdivacky 252202375Srdivacky /// resize - Grow or shrink the bitvector. 253202375Srdivacky void resize(unsigned N, bool t = false) { 254202375Srdivacky if (!isSmall()) { 255207618Srdivacky getPointer()->resize(N, t); 256207618Srdivacky } else if (SmallNumDataBits >= N) { 257207618Srdivacky uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; 258202375Srdivacky setSmallSize(N); 259207618Srdivacky setSmallBits(NewBits | getSmallBits()); 260202375Srdivacky } else { 261202375Srdivacky BitVector *BV = new BitVector(N, t); 262202375Srdivacky uintptr_t OldBits = getSmallBits(); 263202375Srdivacky for (size_t i = 0, e = getSmallSize(); i != e; ++i) 264202375Srdivacky (*BV)[i] = (OldBits >> i) & 1; 265202375Srdivacky switchToLarge(BV); 266202375Srdivacky } 267202375Srdivacky } 268202375Srdivacky 269202375Srdivacky void reserve(unsigned N) { 270202375Srdivacky if (isSmall()) { 271202375Srdivacky if (N > SmallNumDataBits) { 272202375Srdivacky uintptr_t OldBits = getSmallRawBits(); 273202375Srdivacky size_t SmallSize = getSmallSize(); 274202375Srdivacky BitVector *BV = new BitVector(SmallSize); 275202375Srdivacky for (size_t i = 0; i < SmallSize; ++i) 276202375Srdivacky if ((OldBits >> i) & 1) 277202375Srdivacky BV->set(i); 278202375Srdivacky BV->reserve(N); 279202375Srdivacky switchToLarge(BV); 280202375Srdivacky } 281202375Srdivacky } else { 282207618Srdivacky getPointer()->reserve(N); 283202375Srdivacky } 284202375Srdivacky } 285202375Srdivacky 286202375Srdivacky // Set, reset, flip 287202375Srdivacky SmallBitVector &set() { 288202375Srdivacky if (isSmall()) 289202375Srdivacky setSmallBits(~uintptr_t(0)); 290202375Srdivacky else 291207618Srdivacky getPointer()->set(); 292202375Srdivacky return *this; 293202375Srdivacky } 294202375Srdivacky 295202375Srdivacky SmallBitVector &set(unsigned Idx) { 296202375Srdivacky if (isSmall()) 297202375Srdivacky setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); 298202375Srdivacky else 299207618Srdivacky getPointer()->set(Idx); 300202375Srdivacky return *this; 301202375Srdivacky } 302202375Srdivacky 303245431Sdim /// set - Efficiently set a range of bits in [I, E) 304245431Sdim SmallBitVector &set(unsigned I, unsigned E) { 305245431Sdim assert(I <= E && "Attempted to set backwards range!"); 306245431Sdim assert(E <= size() && "Attempted to set out-of-bounds range!"); 307245431Sdim if (I == E) return *this; 308245431Sdim if (isSmall()) { 309245431Sdim uintptr_t EMask = ((uintptr_t)1) << E; 310245431Sdim uintptr_t IMask = ((uintptr_t)1) << I; 311245431Sdim uintptr_t Mask = EMask - IMask; 312245431Sdim setSmallBits(getSmallBits() | Mask); 313245431Sdim } else 314245431Sdim getPointer()->set(I, E); 315245431Sdim return *this; 316245431Sdim } 317245431Sdim 318202375Srdivacky SmallBitVector &reset() { 319202375Srdivacky if (isSmall()) 320202375Srdivacky setSmallBits(0); 321202375Srdivacky else 322207618Srdivacky getPointer()->reset(); 323202375Srdivacky return *this; 324202375Srdivacky } 325202375Srdivacky 326202375Srdivacky SmallBitVector &reset(unsigned Idx) { 327202375Srdivacky if (isSmall()) 328202375Srdivacky setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); 329202375Srdivacky else 330207618Srdivacky getPointer()->reset(Idx); 331202375Srdivacky return *this; 332202375Srdivacky } 333202375Srdivacky 334245431Sdim /// reset - Efficiently reset a range of bits in [I, E) 335245431Sdim SmallBitVector &reset(unsigned I, unsigned E) { 336245431Sdim assert(I <= E && "Attempted to reset backwards range!"); 337245431Sdim assert(E <= size() && "Attempted to reset out-of-bounds range!"); 338245431Sdim if (I == E) return *this; 339245431Sdim if (isSmall()) { 340245431Sdim uintptr_t EMask = ((uintptr_t)1) << E; 341245431Sdim uintptr_t IMask = ((uintptr_t)1) << I; 342245431Sdim uintptr_t Mask = EMask - IMask; 343245431Sdim setSmallBits(getSmallBits() & ~Mask); 344245431Sdim } else 345245431Sdim getPointer()->reset(I, E); 346245431Sdim return *this; 347245431Sdim } 348245431Sdim 349202375Srdivacky SmallBitVector &flip() { 350202375Srdivacky if (isSmall()) 351202375Srdivacky setSmallBits(~getSmallBits()); 352202375Srdivacky else 353207618Srdivacky getPointer()->flip(); 354202375Srdivacky return *this; 355202375Srdivacky } 356202375Srdivacky 357202375Srdivacky SmallBitVector &flip(unsigned Idx) { 358202375Srdivacky if (isSmall()) 359202375Srdivacky setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); 360202375Srdivacky else 361207618Srdivacky getPointer()->flip(Idx); 362202375Srdivacky return *this; 363202375Srdivacky } 364202375Srdivacky 365202375Srdivacky // No argument flip. 366202375Srdivacky SmallBitVector operator~() const { 367202375Srdivacky return SmallBitVector(*this).flip(); 368202375Srdivacky } 369202375Srdivacky 370202375Srdivacky // Indexing. 371207618Srdivacky reference operator[](unsigned Idx) { 372207618Srdivacky assert(Idx < size() && "Out-of-bounds Bit access."); 373207618Srdivacky return reference(*this, Idx); 374207618Srdivacky } 375207618Srdivacky 376202375Srdivacky bool operator[](unsigned Idx) const { 377202375Srdivacky assert(Idx < size() && "Out-of-bounds Bit access."); 378202375Srdivacky if (isSmall()) 379202375Srdivacky return ((getSmallBits() >> Idx) & 1) != 0; 380207618Srdivacky return getPointer()->operator[](Idx); 381202375Srdivacky } 382202375Srdivacky 383202375Srdivacky bool test(unsigned Idx) const { 384202375Srdivacky return (*this)[Idx]; 385202375Srdivacky } 386202375Srdivacky 387245431Sdim /// Test if any common bits are set. 388245431Sdim bool anyCommon(const SmallBitVector &RHS) const { 389245431Sdim if (isSmall() && RHS.isSmall()) 390245431Sdim return (getSmallBits() & RHS.getSmallBits()) != 0; 391245431Sdim if (!isSmall() && !RHS.isSmall()) 392245431Sdim return getPointer()->anyCommon(*RHS.getPointer()); 393245431Sdim 394245431Sdim for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 395245431Sdim if (test(i) && RHS.test(i)) 396245431Sdim return true; 397245431Sdim return false; 398245431Sdim } 399245431Sdim 400202375Srdivacky // Comparison operators. 401202375Srdivacky bool operator==(const SmallBitVector &RHS) const { 402202375Srdivacky if (size() != RHS.size()) 403202375Srdivacky return false; 404202375Srdivacky if (isSmall()) 405202375Srdivacky return getSmallBits() == RHS.getSmallBits(); 406202375Srdivacky else 407207618Srdivacky return *getPointer() == *RHS.getPointer(); 408202375Srdivacky } 409202375Srdivacky 410202375Srdivacky bool operator!=(const SmallBitVector &RHS) const { 411202375Srdivacky return !(*this == RHS); 412202375Srdivacky } 413202375Srdivacky 414202375Srdivacky // Intersection, union, disjoint union. 415203954Srdivacky SmallBitVector &operator&=(const SmallBitVector &RHS) { 416203954Srdivacky resize(std::max(size(), RHS.size())); 417203954Srdivacky if (isSmall()) 418203954Srdivacky setSmallBits(getSmallBits() & RHS.getSmallBits()); 419203954Srdivacky else if (!RHS.isSmall()) 420207618Srdivacky getPointer()->operator&=(*RHS.getPointer()); 421203954Srdivacky else { 422203954Srdivacky SmallBitVector Copy = RHS; 423203954Srdivacky Copy.resize(size()); 424207618Srdivacky getPointer()->operator&=(*Copy.getPointer()); 425203954Srdivacky } 426203954Srdivacky return *this; 427203954Srdivacky } 428202375Srdivacky 429263509Sdim /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. 430263509Sdim SmallBitVector &reset(const SmallBitVector &RHS) { 431263509Sdim if (isSmall() && RHS.isSmall()) 432263509Sdim setSmallBits(getSmallBits() & ~RHS.getSmallBits()); 433263509Sdim else if (!isSmall() && !RHS.isSmall()) 434263509Sdim getPointer()->reset(*RHS.getPointer()); 435263509Sdim else 436263509Sdim for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 437263509Sdim if (RHS.test(i)) 438263509Sdim reset(i); 439263509Sdim 440263509Sdim return *this; 441263509Sdim } 442263509Sdim 443263509Sdim /// test - Check if (This - RHS) is zero. 444263509Sdim /// This is the same as reset(RHS) and any(). 445263509Sdim bool test(const SmallBitVector &RHS) const { 446263509Sdim if (isSmall() && RHS.isSmall()) 447263509Sdim return (getSmallBits() & ~RHS.getSmallBits()) != 0; 448263509Sdim if (!isSmall() && !RHS.isSmall()) 449263509Sdim return getPointer()->test(*RHS.getPointer()); 450263509Sdim 451263509Sdim unsigned i, e; 452263509Sdim for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 453263509Sdim if (test(i) && !RHS.test(i)) 454263509Sdim return true; 455263509Sdim 456263509Sdim for (e = size(); i != e; ++i) 457263509Sdim if (test(i)) 458263509Sdim return true; 459263509Sdim 460263509Sdim return false; 461263509Sdim } 462263509Sdim 463203954Srdivacky SmallBitVector &operator|=(const SmallBitVector &RHS) { 464203954Srdivacky resize(std::max(size(), RHS.size())); 465203954Srdivacky if (isSmall()) 466203954Srdivacky setSmallBits(getSmallBits() | RHS.getSmallBits()); 467203954Srdivacky else if (!RHS.isSmall()) 468207618Srdivacky getPointer()->operator|=(*RHS.getPointer()); 469203954Srdivacky else { 470203954Srdivacky SmallBitVector Copy = RHS; 471203954Srdivacky Copy.resize(size()); 472207618Srdivacky getPointer()->operator|=(*Copy.getPointer()); 473203954Srdivacky } 474203954Srdivacky return *this; 475203954Srdivacky } 476202375Srdivacky 477203954Srdivacky SmallBitVector &operator^=(const SmallBitVector &RHS) { 478203954Srdivacky resize(std::max(size(), RHS.size())); 479203954Srdivacky if (isSmall()) 480203954Srdivacky setSmallBits(getSmallBits() ^ RHS.getSmallBits()); 481203954Srdivacky else if (!RHS.isSmall()) 482207618Srdivacky getPointer()->operator^=(*RHS.getPointer()); 483203954Srdivacky else { 484203954Srdivacky SmallBitVector Copy = RHS; 485203954Srdivacky Copy.resize(size()); 486207618Srdivacky getPointer()->operator^=(*Copy.getPointer()); 487203954Srdivacky } 488203954Srdivacky return *this; 489203954Srdivacky } 490202375Srdivacky 491202375Srdivacky // Assignment operator. 492202375Srdivacky const SmallBitVector &operator=(const SmallBitVector &RHS) { 493202375Srdivacky if (isSmall()) { 494202375Srdivacky if (RHS.isSmall()) 495202375Srdivacky X = RHS.X; 496202375Srdivacky else 497207618Srdivacky switchToLarge(new BitVector(*RHS.getPointer())); 498202375Srdivacky } else { 499202375Srdivacky if (!RHS.isSmall()) 500207618Srdivacky *getPointer() = *RHS.getPointer(); 501202375Srdivacky else { 502207618Srdivacky delete getPointer(); 503202375Srdivacky X = RHS.X; 504202375Srdivacky } 505202375Srdivacky } 506202375Srdivacky return *this; 507202375Srdivacky } 508202375Srdivacky 509252723Sdim#if LLVM_HAS_RVALUE_REFERENCES 510245431Sdim const SmallBitVector &operator=(SmallBitVector &&RHS) { 511245431Sdim if (this != &RHS) { 512245431Sdim clear(); 513245431Sdim swap(RHS); 514245431Sdim } 515245431Sdim return *this; 516245431Sdim } 517245431Sdim#endif 518245431Sdim 519202375Srdivacky void swap(SmallBitVector &RHS) { 520202375Srdivacky std::swap(X, RHS.X); 521202375Srdivacky } 522245431Sdim 523245431Sdim /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. 524245431Sdim /// This computes "*this |= Mask". 525245431Sdim void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 526245431Sdim if (isSmall()) 527245431Sdim applyMask<true, false>(Mask, MaskWords); 528245431Sdim else 529245431Sdim getPointer()->setBitsInMask(Mask, MaskWords); 530245431Sdim } 531245431Sdim 532245431Sdim /// clearBitsInMask - Clear any bits in this vector that are set in Mask. 533245431Sdim /// Don't resize. This computes "*this &= ~Mask". 534245431Sdim void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 535245431Sdim if (isSmall()) 536245431Sdim applyMask<false, false>(Mask, MaskWords); 537245431Sdim else 538245431Sdim getPointer()->clearBitsInMask(Mask, MaskWords); 539245431Sdim } 540245431Sdim 541245431Sdim /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. 542245431Sdim /// Don't resize. This computes "*this |= ~Mask". 543245431Sdim void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 544245431Sdim if (isSmall()) 545245431Sdim applyMask<true, true>(Mask, MaskWords); 546245431Sdim else 547245431Sdim getPointer()->setBitsNotInMask(Mask, MaskWords); 548245431Sdim } 549245431Sdim 550245431Sdim /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. 551245431Sdim /// Don't resize. This computes "*this &= Mask". 552245431Sdim void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 553245431Sdim if (isSmall()) 554245431Sdim applyMask<false, true>(Mask, MaskWords); 555245431Sdim else 556245431Sdim getPointer()->clearBitsNotInMask(Mask, MaskWords); 557245431Sdim } 558245431Sdim 559245431Sdimprivate: 560245431Sdim template<bool AddBits, bool InvertMask> 561245431Sdim void applyMask(const uint32_t *Mask, unsigned MaskWords) { 562245431Sdim assert((NumBaseBits == 64 || NumBaseBits == 32) && "Unsupported word size"); 563245431Sdim if (NumBaseBits == 64 && MaskWords >= 2) { 564245431Sdim uint64_t M = Mask[0] | (uint64_t(Mask[1]) << 32); 565245431Sdim if (InvertMask) M = ~M; 566245431Sdim if (AddBits) setSmallBits(getSmallBits() | M); 567245431Sdim else setSmallBits(getSmallBits() & ~M); 568245431Sdim } else { 569245431Sdim uint32_t M = Mask[0]; 570245431Sdim if (InvertMask) M = ~M; 571245431Sdim if (AddBits) setSmallBits(getSmallBits() | M); 572245431Sdim else setSmallBits(getSmallBits() & ~M); 573245431Sdim } 574245431Sdim } 575202375Srdivacky}; 576202375Srdivacky 577202375Srdivackyinline SmallBitVector 578202375Srdivackyoperator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { 579202375Srdivacky SmallBitVector Result(LHS); 580202375Srdivacky Result &= RHS; 581202375Srdivacky return Result; 582202375Srdivacky} 583202375Srdivacky 584202375Srdivackyinline SmallBitVector 585202375Srdivackyoperator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { 586202375Srdivacky SmallBitVector Result(LHS); 587202375Srdivacky Result |= RHS; 588202375Srdivacky return Result; 589202375Srdivacky} 590202375Srdivacky 591202375Srdivackyinline SmallBitVector 592202375Srdivackyoperator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { 593202375Srdivacky SmallBitVector Result(LHS); 594202375Srdivacky Result ^= RHS; 595202375Srdivacky return Result; 596202375Srdivacky} 597202375Srdivacky 598202375Srdivacky} // End llvm namespace 599202375Srdivacky 600202375Srdivackynamespace std { 601202375Srdivacky /// Implement std::swap in terms of BitVector swap. 602202375Srdivacky inline void 603202375Srdivacky swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { 604202375Srdivacky LHS.swap(RHS); 605202375Srdivacky } 606202375Srdivacky} 607202375Srdivacky 608202375Srdivacky#endif 609