1193323Sed//===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the BitVector class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#ifndef LLVM_ADT_BITVECTOR_H 15193323Sed#define LLVM_ADT_BITVECTOR_H 16193323Sed 17239462Sdim#include "llvm/Support/Compiler.h" 18234353Sdim#include "llvm/Support/ErrorHandling.h" 19193323Sed#include "llvm/Support/MathExtras.h" 20193323Sed#include <algorithm> 21193323Sed#include <cassert> 22193323Sed#include <climits> 23218893Sdim#include <cstdlib> 24193323Sed 25193323Sednamespace llvm { 26193323Sed 27193323Sedclass BitVector { 28193323Sed typedef unsigned long BitWord; 29193323Sed 30193323Sed enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; 31193323Sed 32193323Sed BitWord *Bits; // Actual bits. 33193323Sed unsigned Size; // Size of bitvector in bits. 34193323Sed unsigned Capacity; // Size of allocated memory in BitWord. 35193323Sed 36193323Sedpublic: 37193323Sed // Encapsulation of a single bit. 38193323Sed class reference { 39193323Sed friend class BitVector; 40193323Sed 41193323Sed BitWord *WordRef; 42193323Sed unsigned BitPos; 43193323Sed 44193323Sed reference(); // Undefined 45193323Sed 46193323Sed public: 47193323Sed reference(BitVector &b, unsigned Idx) { 48193323Sed WordRef = &b.Bits[Idx / BITWORD_SIZE]; 49193323Sed BitPos = Idx % BITWORD_SIZE; 50193323Sed } 51193323Sed 52193323Sed ~reference() {} 53193323Sed 54207618Srdivacky reference &operator=(reference t) { 55207618Srdivacky *this = bool(t); 56207618Srdivacky return *this; 57207618Srdivacky } 58207618Srdivacky 59193323Sed reference& operator=(bool t) { 60193323Sed if (t) 61193323Sed *WordRef |= 1L << BitPos; 62193323Sed else 63193323Sed *WordRef &= ~(1L << BitPos); 64193323Sed return *this; 65193323Sed } 66193323Sed 67193323Sed operator bool() const { 68193323Sed return ((*WordRef) & (1L << BitPos)) ? true : false; 69193323Sed } 70193323Sed }; 71193323Sed 72193323Sed 73193323Sed /// BitVector default ctor - Creates an empty bitvector. 74193323Sed BitVector() : Size(0), Capacity(0) { 75193323Sed Bits = 0; 76193323Sed } 77193323Sed 78193323Sed /// BitVector ctor - Creates a bitvector of specified number of bits. All 79193323Sed /// bits are initialized to the specified value. 80193323Sed explicit BitVector(unsigned s, bool t = false) : Size(s) { 81193323Sed Capacity = NumBitWords(s); 82218893Sdim Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 83193323Sed init_words(Bits, Capacity, t); 84193323Sed if (t) 85193323Sed clear_unused_bits(); 86193323Sed } 87193323Sed 88193323Sed /// BitVector copy ctor. 89193323Sed BitVector(const BitVector &RHS) : Size(RHS.size()) { 90193323Sed if (Size == 0) { 91193323Sed Bits = 0; 92193323Sed Capacity = 0; 93193323Sed return; 94193323Sed } 95193323Sed 96193323Sed Capacity = NumBitWords(RHS.size()); 97218893Sdim Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 98218893Sdim std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord)); 99193323Sed } 100193323Sed 101249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 102239462Sdim BitVector(BitVector &&RHS) 103239462Sdim : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) { 104239462Sdim RHS.Bits = 0; 105239462Sdim } 106239462Sdim#endif 107239462Sdim 108193323Sed ~BitVector() { 109218893Sdim std::free(Bits); 110193323Sed } 111193323Sed 112202375Srdivacky /// empty - Tests whether there are no bits in this bitvector. 113202375Srdivacky bool empty() const { return Size == 0; } 114202375Srdivacky 115193323Sed /// size - Returns the number of bits in this bitvector. 116193323Sed unsigned size() const { return Size; } 117193323Sed 118193323Sed /// count - Returns the number of bits which are set. 119193323Sed unsigned count() const { 120193323Sed unsigned NumBits = 0; 121193323Sed for (unsigned i = 0; i < NumBitWords(size()); ++i) 122193323Sed if (sizeof(BitWord) == 4) 123193323Sed NumBits += CountPopulation_32((uint32_t)Bits[i]); 124193323Sed else if (sizeof(BitWord) == 8) 125193323Sed NumBits += CountPopulation_64(Bits[i]); 126193323Sed else 127234353Sdim llvm_unreachable("Unsupported!"); 128193323Sed return NumBits; 129193323Sed } 130193323Sed 131193323Sed /// any - Returns true if any bit is set. 132193323Sed bool any() const { 133193323Sed for (unsigned i = 0; i < NumBitWords(size()); ++i) 134193323Sed if (Bits[i] != 0) 135193323Sed return true; 136193323Sed return false; 137193323Sed } 138193323Sed 139218893Sdim /// all - Returns true if all bits are set. 140218893Sdim bool all() const { 141263508Sdim for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i) 142263508Sdim if (Bits[i] != ~0UL) 143263508Sdim return false; 144263508Sdim 145263508Sdim // If bits remain check that they are ones. The unused bits are always zero. 146263508Sdim if (unsigned Remainder = Size % BITWORD_SIZE) 147263508Sdim return Bits[Size / BITWORD_SIZE] == (1UL << Remainder) - 1; 148263508Sdim 149263508Sdim return true; 150218893Sdim } 151218893Sdim 152193323Sed /// none - Returns true if none of the bits are set. 153193323Sed bool none() const { 154193323Sed return !any(); 155193323Sed } 156193323Sed 157193323Sed /// find_first - Returns the index of the first set bit, -1 if none 158193323Sed /// of the bits are set. 159193323Sed int find_first() const { 160193323Sed for (unsigned i = 0; i < NumBitWords(size()); ++i) 161193323Sed if (Bits[i] != 0) { 162193323Sed if (sizeof(BitWord) == 4) 163263508Sdim return i * BITWORD_SIZE + countTrailingZeros((uint32_t)Bits[i]); 164234353Sdim if (sizeof(BitWord) == 8) 165263508Sdim return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); 166234353Sdim llvm_unreachable("Unsupported!"); 167193323Sed } 168193323Sed return -1; 169193323Sed } 170193323Sed 171193323Sed /// find_next - Returns the index of the next set bit following the 172193323Sed /// "Prev" bit. Returns -1 if the next set bit is not found. 173193323Sed int find_next(unsigned Prev) const { 174193323Sed ++Prev; 175193323Sed if (Prev >= Size) 176193323Sed return -1; 177193323Sed 178193323Sed unsigned WordPos = Prev / BITWORD_SIZE; 179193323Sed unsigned BitPos = Prev % BITWORD_SIZE; 180193323Sed BitWord Copy = Bits[WordPos]; 181193323Sed // Mask off previous bits. 182243830Sdim Copy &= ~0UL << BitPos; 183193323Sed 184193323Sed if (Copy != 0) { 185193323Sed if (sizeof(BitWord) == 4) 186263508Sdim return WordPos * BITWORD_SIZE + countTrailingZeros((uint32_t)Copy); 187234353Sdim if (sizeof(BitWord) == 8) 188263508Sdim return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); 189234353Sdim llvm_unreachable("Unsupported!"); 190193323Sed } 191193323Sed 192193323Sed // Check subsequent words. 193193323Sed for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i) 194193323Sed if (Bits[i] != 0) { 195193323Sed if (sizeof(BitWord) == 4) 196263508Sdim return i * BITWORD_SIZE + countTrailingZeros((uint32_t)Bits[i]); 197234353Sdim if (sizeof(BitWord) == 8) 198263508Sdim return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); 199234353Sdim llvm_unreachable("Unsupported!"); 200193323Sed } 201193323Sed return -1; 202193323Sed } 203193323Sed 204193323Sed /// clear - Clear all bits. 205193323Sed void clear() { 206193323Sed Size = 0; 207193323Sed } 208193323Sed 209193323Sed /// resize - Grow or shrink the bitvector. 210193323Sed void resize(unsigned N, bool t = false) { 211193323Sed if (N > Capacity * BITWORD_SIZE) { 212193323Sed unsigned OldCapacity = Capacity; 213193323Sed grow(N); 214193323Sed init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t); 215193323Sed } 216193323Sed 217193323Sed // Set any old unused bits that are now included in the BitVector. This 218193323Sed // may set bits that are not included in the new vector, but we will clear 219193323Sed // them back out below. 220193323Sed if (N > Size) 221193323Sed set_unused_bits(t); 222193323Sed 223193323Sed // Update the size, and clear out any bits that are now unused 224193323Sed unsigned OldSize = Size; 225193323Sed Size = N; 226193323Sed if (t || N < OldSize) 227193323Sed clear_unused_bits(); 228193323Sed } 229193323Sed 230193323Sed void reserve(unsigned N) { 231193323Sed if (N > Capacity * BITWORD_SIZE) 232193323Sed grow(N); 233193323Sed } 234193323Sed 235193323Sed // Set, reset, flip 236193323Sed BitVector &set() { 237193323Sed init_words(Bits, Capacity, true); 238193323Sed clear_unused_bits(); 239193323Sed return *this; 240193323Sed } 241193323Sed 242193323Sed BitVector &set(unsigned Idx) { 243193323Sed Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); 244193323Sed return *this; 245193323Sed } 246193323Sed 247243830Sdim /// set - Efficiently set a range of bits in [I, E) 248243830Sdim BitVector &set(unsigned I, unsigned E) { 249243830Sdim assert(I <= E && "Attempted to set backwards range!"); 250243830Sdim assert(E <= size() && "Attempted to set out-of-bounds range!"); 251243830Sdim 252243830Sdim if (I == E) return *this; 253243830Sdim 254243830Sdim if (I / BITWORD_SIZE == E / BITWORD_SIZE) { 255243830Sdim BitWord EMask = 1UL << (E % BITWORD_SIZE); 256243830Sdim BitWord IMask = 1UL << (I % BITWORD_SIZE); 257243830Sdim BitWord Mask = EMask - IMask; 258243830Sdim Bits[I / BITWORD_SIZE] |= Mask; 259243830Sdim return *this; 260243830Sdim } 261243830Sdim 262243830Sdim BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); 263243830Sdim Bits[I / BITWORD_SIZE] |= PrefixMask; 264243830Sdim I = RoundUpToAlignment(I, BITWORD_SIZE); 265243830Sdim 266243830Sdim for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) 267243830Sdim Bits[I / BITWORD_SIZE] = ~0UL; 268243830Sdim 269243830Sdim BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; 270243830Sdim Bits[I / BITWORD_SIZE] |= PostfixMask; 271243830Sdim 272243830Sdim return *this; 273243830Sdim } 274243830Sdim 275193323Sed BitVector &reset() { 276193323Sed init_words(Bits, Capacity, false); 277193323Sed return *this; 278193323Sed } 279193323Sed 280193323Sed BitVector &reset(unsigned Idx) { 281193323Sed Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); 282193323Sed return *this; 283193323Sed } 284193323Sed 285243830Sdim /// reset - Efficiently reset a range of bits in [I, E) 286243830Sdim BitVector &reset(unsigned I, unsigned E) { 287243830Sdim assert(I <= E && "Attempted to reset backwards range!"); 288243830Sdim assert(E <= size() && "Attempted to reset out-of-bounds range!"); 289243830Sdim 290243830Sdim if (I == E) return *this; 291243830Sdim 292243830Sdim if (I / BITWORD_SIZE == E / BITWORD_SIZE) { 293243830Sdim BitWord EMask = 1UL << (E % BITWORD_SIZE); 294243830Sdim BitWord IMask = 1UL << (I % BITWORD_SIZE); 295243830Sdim BitWord Mask = EMask - IMask; 296243830Sdim Bits[I / BITWORD_SIZE] &= ~Mask; 297243830Sdim return *this; 298243830Sdim } 299243830Sdim 300243830Sdim BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); 301243830Sdim Bits[I / BITWORD_SIZE] &= ~PrefixMask; 302243830Sdim I = RoundUpToAlignment(I, BITWORD_SIZE); 303243830Sdim 304243830Sdim for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) 305243830Sdim Bits[I / BITWORD_SIZE] = 0UL; 306243830Sdim 307243830Sdim BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; 308243830Sdim Bits[I / BITWORD_SIZE] &= ~PostfixMask; 309243830Sdim 310243830Sdim return *this; 311243830Sdim } 312243830Sdim 313193323Sed BitVector &flip() { 314193323Sed for (unsigned i = 0; i < NumBitWords(size()); ++i) 315193323Sed Bits[i] = ~Bits[i]; 316193323Sed clear_unused_bits(); 317193323Sed return *this; 318193323Sed } 319193323Sed 320193323Sed BitVector &flip(unsigned Idx) { 321193323Sed Bits[Idx / BITWORD_SIZE] ^= 1L << (Idx % BITWORD_SIZE); 322193323Sed return *this; 323193323Sed } 324193323Sed 325193323Sed // Indexing. 326193323Sed reference operator[](unsigned Idx) { 327193323Sed assert (Idx < Size && "Out-of-bounds Bit access."); 328193323Sed return reference(*this, Idx); 329193323Sed } 330193323Sed 331193323Sed bool operator[](unsigned Idx) const { 332193323Sed assert (Idx < Size && "Out-of-bounds Bit access."); 333193323Sed BitWord Mask = 1L << (Idx % BITWORD_SIZE); 334193323Sed return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; 335193323Sed } 336193323Sed 337193323Sed bool test(unsigned Idx) const { 338193323Sed return (*this)[Idx]; 339193323Sed } 340193323Sed 341239462Sdim /// Test if any common bits are set. 342239462Sdim bool anyCommon(const BitVector &RHS) const { 343239462Sdim unsigned ThisWords = NumBitWords(size()); 344239462Sdim unsigned RHSWords = NumBitWords(RHS.size()); 345239462Sdim for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i) 346239462Sdim if (Bits[i] & RHS.Bits[i]) 347239462Sdim return true; 348239462Sdim return false; 349239462Sdim } 350239462Sdim 351193323Sed // Comparison operators. 352193323Sed bool operator==(const BitVector &RHS) const { 353193323Sed unsigned ThisWords = NumBitWords(size()); 354193323Sed unsigned RHSWords = NumBitWords(RHS.size()); 355193323Sed unsigned i; 356193323Sed for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 357193323Sed if (Bits[i] != RHS.Bits[i]) 358193323Sed return false; 359193323Sed 360193323Sed // Verify that any extra words are all zeros. 361193323Sed if (i != ThisWords) { 362193323Sed for (; i != ThisWords; ++i) 363193323Sed if (Bits[i]) 364193323Sed return false; 365193323Sed } else if (i != RHSWords) { 366193323Sed for (; i != RHSWords; ++i) 367193323Sed if (RHS.Bits[i]) 368193323Sed return false; 369193323Sed } 370193323Sed return true; 371193323Sed } 372193323Sed 373193323Sed bool operator!=(const BitVector &RHS) const { 374193323Sed return !(*this == RHS); 375193323Sed } 376193323Sed 377243830Sdim /// Intersection, union, disjoint union. 378193323Sed BitVector &operator&=(const BitVector &RHS) { 379193323Sed unsigned ThisWords = NumBitWords(size()); 380193323Sed unsigned RHSWords = NumBitWords(RHS.size()); 381193323Sed unsigned i; 382193323Sed for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 383193323Sed Bits[i] &= RHS.Bits[i]; 384193323Sed 385193323Sed // Any bits that are just in this bitvector become zero, because they aren't 386193323Sed // in the RHS bit vector. Any words only in RHS are ignored because they 387193323Sed // are already zero in the LHS. 388193323Sed for (; i != ThisWords; ++i) 389193323Sed Bits[i] = 0; 390193323Sed 391193323Sed return *this; 392193323Sed } 393193323Sed 394243830Sdim /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. 395234353Sdim BitVector &reset(const BitVector &RHS) { 396234353Sdim unsigned ThisWords = NumBitWords(size()); 397234353Sdim unsigned RHSWords = NumBitWords(RHS.size()); 398234353Sdim unsigned i; 399234353Sdim for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 400234353Sdim Bits[i] &= ~RHS.Bits[i]; 401234353Sdim return *this; 402234353Sdim } 403234353Sdim 404243830Sdim /// test - Check if (This - RHS) is zero. 405243830Sdim /// This is the same as reset(RHS) and any(). 406243830Sdim bool test(const BitVector &RHS) const { 407243830Sdim unsigned ThisWords = NumBitWords(size()); 408243830Sdim unsigned RHSWords = NumBitWords(RHS.size()); 409243830Sdim unsigned i; 410243830Sdim for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 411243830Sdim if ((Bits[i] & ~RHS.Bits[i]) != 0) 412243830Sdim return true; 413243830Sdim 414243830Sdim for (; i != ThisWords ; ++i) 415243830Sdim if (Bits[i] != 0) 416243830Sdim return true; 417243830Sdim 418243830Sdim return false; 419243830Sdim } 420243830Sdim 421193323Sed BitVector &operator|=(const BitVector &RHS) { 422203954Srdivacky if (size() < RHS.size()) 423203954Srdivacky resize(RHS.size()); 424203954Srdivacky for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 425193323Sed Bits[i] |= RHS.Bits[i]; 426193323Sed return *this; 427193323Sed } 428193323Sed 429193323Sed BitVector &operator^=(const BitVector &RHS) { 430203954Srdivacky if (size() < RHS.size()) 431203954Srdivacky resize(RHS.size()); 432203954Srdivacky for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 433193323Sed Bits[i] ^= RHS.Bits[i]; 434193323Sed return *this; 435193323Sed } 436193323Sed 437193323Sed // Assignment operator. 438193323Sed const BitVector &operator=(const BitVector &RHS) { 439193323Sed if (this == &RHS) return *this; 440193323Sed 441193323Sed Size = RHS.size(); 442193323Sed unsigned RHSWords = NumBitWords(Size); 443193323Sed if (Size <= Capacity * BITWORD_SIZE) { 444205407Srdivacky if (Size) 445218893Sdim std::memcpy(Bits, RHS.Bits, RHSWords * sizeof(BitWord)); 446193323Sed clear_unused_bits(); 447193323Sed return *this; 448193323Sed } 449193323Sed 450193323Sed // Grow the bitvector to have enough elements. 451193323Sed Capacity = RHSWords; 452218893Sdim BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 453218893Sdim std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord)); 454193323Sed 455193323Sed // Destroy the old bits. 456218893Sdim std::free(Bits); 457193323Sed Bits = NewBits; 458193323Sed 459193323Sed return *this; 460193323Sed } 461193323Sed 462249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 463239462Sdim const BitVector &operator=(BitVector &&RHS) { 464239462Sdim if (this == &RHS) return *this; 465239462Sdim 466239462Sdim std::free(Bits); 467239462Sdim Bits = RHS.Bits; 468239462Sdim Size = RHS.Size; 469239462Sdim Capacity = RHS.Capacity; 470239462Sdim 471239462Sdim RHS.Bits = 0; 472239462Sdim 473239462Sdim return *this; 474239462Sdim } 475239462Sdim#endif 476239462Sdim 477202375Srdivacky void swap(BitVector &RHS) { 478202375Srdivacky std::swap(Bits, RHS.Bits); 479202375Srdivacky std::swap(Size, RHS.Size); 480202375Srdivacky std::swap(Capacity, RHS.Capacity); 481202375Srdivacky } 482202375Srdivacky 483234353Sdim //===--------------------------------------------------------------------===// 484234353Sdim // Portable bit mask operations. 485234353Sdim //===--------------------------------------------------------------------===// 486234353Sdim // 487234353Sdim // These methods all operate on arrays of uint32_t, each holding 32 bits. The 488234353Sdim // fixed word size makes it easier to work with literal bit vector constants 489234353Sdim // in portable code. 490234353Sdim // 491234353Sdim // The LSB in each word is the lowest numbered bit. The size of a portable 492234353Sdim // bit mask is always a whole multiple of 32 bits. If no bit mask size is 493234353Sdim // given, the bit mask is assumed to cover the entire BitVector. 494234353Sdim 495234353Sdim /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. 496234353Sdim /// This computes "*this |= Mask". 497234353Sdim void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 498234353Sdim applyMask<true, false>(Mask, MaskWords); 499234353Sdim } 500234353Sdim 501234353Sdim /// clearBitsInMask - Clear any bits in this vector that are set in Mask. 502234353Sdim /// Don't resize. This computes "*this &= ~Mask". 503234353Sdim void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 504234353Sdim applyMask<false, false>(Mask, MaskWords); 505234353Sdim } 506234353Sdim 507234353Sdim /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. 508234353Sdim /// Don't resize. This computes "*this |= ~Mask". 509234353Sdim void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 510234353Sdim applyMask<true, true>(Mask, MaskWords); 511234353Sdim } 512234353Sdim 513234353Sdim /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. 514234353Sdim /// Don't resize. This computes "*this &= Mask". 515234353Sdim void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 516234353Sdim applyMask<false, true>(Mask, MaskWords); 517234353Sdim } 518234353Sdim 519193323Sedprivate: 520193323Sed unsigned NumBitWords(unsigned S) const { 521193323Sed return (S + BITWORD_SIZE-1) / BITWORD_SIZE; 522193323Sed } 523193323Sed 524193323Sed // Set the unused bits in the high words. 525193323Sed void set_unused_bits(bool t = true) { 526193323Sed // Set high words first. 527193323Sed unsigned UsedWords = NumBitWords(Size); 528193323Sed if (Capacity > UsedWords) 529193323Sed init_words(&Bits[UsedWords], (Capacity-UsedWords), t); 530193323Sed 531193323Sed // Then set any stray high bits of the last used word. 532193323Sed unsigned ExtraBits = Size % BITWORD_SIZE; 533193323Sed if (ExtraBits) { 534243830Sdim BitWord ExtraBitMask = ~0UL << ExtraBits; 535243830Sdim if (t) 536243830Sdim Bits[UsedWords-1] |= ExtraBitMask; 537243830Sdim else 538243830Sdim Bits[UsedWords-1] &= ~ExtraBitMask; 539193323Sed } 540193323Sed } 541193323Sed 542193323Sed // Clear the unused bits in the high words. 543193323Sed void clear_unused_bits() { 544193323Sed set_unused_bits(false); 545193323Sed } 546193323Sed 547193323Sed void grow(unsigned NewSize) { 548218893Sdim Capacity = std::max(NumBitWords(NewSize), Capacity * 2); 549218893Sdim Bits = (BitWord *)std::realloc(Bits, Capacity * sizeof(BitWord)); 550193323Sed 551193323Sed clear_unused_bits(); 552193323Sed } 553193323Sed 554193323Sed void init_words(BitWord *B, unsigned NumWords, bool t) { 555193323Sed memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); 556193323Sed } 557234353Sdim 558234353Sdim template<bool AddBits, bool InvertMask> 559234353Sdim void applyMask(const uint32_t *Mask, unsigned MaskWords) { 560234353Sdim assert(BITWORD_SIZE % 32 == 0 && "Unsupported BitWord size."); 561234353Sdim MaskWords = std::min(MaskWords, (size() + 31) / 32); 562234353Sdim const unsigned Scale = BITWORD_SIZE / 32; 563234353Sdim unsigned i; 564234353Sdim for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) { 565234353Sdim BitWord BW = Bits[i]; 566234353Sdim // This inner loop should unroll completely when BITWORD_SIZE > 32. 567234353Sdim for (unsigned b = 0; b != BITWORD_SIZE; b += 32) { 568234353Sdim uint32_t M = *Mask++; 569234353Sdim if (InvertMask) M = ~M; 570234353Sdim if (AddBits) BW |= BitWord(M) << b; 571234353Sdim else BW &= ~(BitWord(M) << b); 572234353Sdim } 573234353Sdim Bits[i] = BW; 574234353Sdim } 575234353Sdim for (unsigned b = 0; MaskWords; b += 32, --MaskWords) { 576234353Sdim uint32_t M = *Mask++; 577234353Sdim if (InvertMask) M = ~M; 578234353Sdim if (AddBits) Bits[i] |= BitWord(M) << b; 579234353Sdim else Bits[i] &= ~(BitWord(M) << b); 580234353Sdim } 581234353Sdim if (AddBits) 582234353Sdim clear_unused_bits(); 583234353Sdim } 584193323Sed}; 585193323Sed 586193323Sed} // End llvm namespace 587202375Srdivacky 588202375Srdivackynamespace std { 589202375Srdivacky /// Implement std::swap in terms of BitVector swap. 590202375Srdivacky inline void 591202375Srdivacky swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { 592202375Srdivacky LHS.swap(RHS); 593202375Srdivacky } 594202375Srdivacky} 595202375Srdivacky 596193323Sed#endif 597