1ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng//===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===// 2ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng// 3ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng// The LLVM Compiler Infrastructure 4ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 7ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng// 8ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng//===----------------------------------------------------------------------===// 9ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng// 10ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng// This file implements the BitVector class. 11ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng// 12ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng//===----------------------------------------------------------------------===// 13ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 14ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng#ifndef LLVM_ADT_BITVECTOR_H 15ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng#define LLVM_ADT_BITVECTOR_H 16ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 17693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer#include "llvm/Support/Compiler.h" 1850bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper#include "llvm/Support/ErrorHandling.h" 19ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng#include "llvm/Support/MathExtras.h" 205502bf67cd49221583c15472150905ce13184d36Anton Korobeynikov#include <algorithm> 21ecd276a49898a79404728ab476fc3c74e8ab8581Lauro Ramos Venancio#include <cassert> 22de551f91d8816632a76a065084caab9fab6aacffDan Gohman#include <climits> 2328116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer#include <cstdlib> 24ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 25ad1d5c3bc55249b3291338288c90773ce80df11aEvan Chengnamespace llvm { 26ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 27ad1d5c3bc55249b3291338288c90773ce80df11aEvan Chengclass BitVector { 28ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng typedef unsigned long BitWord; 29ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 30de551f91d8816632a76a065084caab9fab6aacffDan Gohman enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; 31ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman BitWord *Bits; // Actual bits. 33ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned Size; // Size of bitvector in bits. 34ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned Capacity; // Size of allocated memory in BitWord. 35ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 36ad1d5c3bc55249b3291338288c90773ce80df11aEvan Chengpublic: 37cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typedef unsigned size_type; 38ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Encapsulation of a single bit. 39ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng class reference { 40ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng friend class BitVector; 41ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 42ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitWord *WordRef; 43ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned BitPos; 44ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 45ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng reference(); // Undefined 46ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 47ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng public: 48ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng reference(BitVector &b, unsigned Idx) { 492864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen WordRef = &b.Bits[Idx / BITWORD_SIZE]; 502864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen BitPos = Idx % BITWORD_SIZE; 51ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 52ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 53ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng ~reference() {} 54ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 553f5e91565273e3f4639d37ee5a5b856699e8c9e5Dan Gohman reference &operator=(reference t) { 563f5e91565273e3f4639d37ee5a5b856699e8c9e5Dan Gohman *this = bool(t); 573f5e91565273e3f4639d37ee5a5b856699e8c9e5Dan Gohman return *this; 583f5e91565273e3f4639d37ee5a5b856699e8c9e5Dan Gohman } 593f5e91565273e3f4639d37ee5a5b856699e8c9e5Dan Gohman 60ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng reference& operator=(bool t) { 61ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng if (t) 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines *WordRef |= BitWord(1) << BitPos; 63ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng else 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines *WordRef &= ~(BitWord(1) << BitPos); 65ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 66ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 67ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 68ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng operator bool() const { 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return ((*WordRef) & (BitWord(1) << BitPos)) ? true : false; 70ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 71ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng }; 72ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 73ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 74ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// BitVector default ctor - Creates an empty bitvector. 75ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector() : Size(0), Capacity(0) { 76dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Bits = nullptr; 77ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 78ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 79ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// BitVector ctor - Creates a bitvector of specified number of bits. All 80ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// bits are initialized to the specified value. 81334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng explicit BitVector(unsigned s, bool t = false) : Size(s) { 82ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Capacity = NumBitWords(s); 8328116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 84ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng init_words(Bits, Capacity, t); 85334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng if (t) 86334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng clear_unused_bits(); 87ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 88ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 89ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// BitVector copy ctor. 90ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector(const BitVector &RHS) : Size(RHS.size()) { 91334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng if (Size == 0) { 92dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Bits = nullptr; 939d1597b086114d643a8c5db71fffa72ae8bb06f3Reid Spencer Capacity = 0; 94334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng return; 95334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng } 96334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng 97ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Capacity = NumBitWords(RHS.size()); 9828116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 9928116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord)); 100ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 1013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 102693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer BitVector(BitVector &&RHS) 103693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) { 104dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.Bits = nullptr; 105693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer } 106693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 107b9174dd5dc2a782e617fe45200ec462bcef26ceeChris Lattner ~BitVector() { 10828116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer std::free(Bits); 109b9174dd5dc2a782e617fe45200ec462bcef26ceeChris Lattner } 110ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 111cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// empty - Tests whether there are no bits in this bitvector. 112cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool empty() const { return Size == 0; } 113cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 114ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// size - Returns the number of bits in this bitvector. 115cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines size_type size() const { return Size; } 116ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 117ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// count - Returns the number of bits which are set. 118cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines size_type count() const { 119ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned NumBits = 0; 120ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng for (unsigned i = 0; i < NumBitWords(size()); ++i) 1217bf26c1d68f75de9c1c8520620228b016bf9a0ebEvan Cheng if (sizeof(BitWord) == 4) 12234cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng NumBits += CountPopulation_32((uint32_t)Bits[i]); 1237bf26c1d68f75de9c1c8520620228b016bf9a0ebEvan Cheng else if (sizeof(BitWord) == 8) 1247bf26c1d68f75de9c1c8520620228b016bf9a0ebEvan Cheng NumBits += CountPopulation_64(Bits[i]); 1257bf26c1d68f75de9c1c8520620228b016bf9a0ebEvan Cheng else 12650bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 127ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return NumBits; 128ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 129ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 130ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// any - Returns true if any bit is set. 131ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool any() const { 132ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng for (unsigned i = 0; i < NumBitWords(size()); ++i) 133ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng if (Bits[i] != 0) 134ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return true; 135ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return false; 136ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 137ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 138fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman /// all - Returns true if all bits are set. 139fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman bool all() const { 140a77376dae1e26572f94aa52b63f89749b785bc33Benjamin Kramer for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i) 141597253da97ec4fa5fa4a03c2230ed026b1b6aad6Benjamin Kramer if (Bits[i] != ~0UL) 142597253da97ec4fa5fa4a03c2230ed026b1b6aad6Benjamin Kramer return false; 143597253da97ec4fa5fa4a03c2230ed026b1b6aad6Benjamin Kramer 144a77376dae1e26572f94aa52b63f89749b785bc33Benjamin Kramer // If bits remain check that they are ones. The unused bits are always zero. 145a77376dae1e26572f94aa52b63f89749b785bc33Benjamin Kramer if (unsigned Remainder = Size % BITWORD_SIZE) 146a77376dae1e26572f94aa52b63f89749b785bc33Benjamin Kramer return Bits[Size / BITWORD_SIZE] == (1UL << Remainder) - 1; 147a77376dae1e26572f94aa52b63f89749b785bc33Benjamin Kramer 148a77376dae1e26572f94aa52b63f89749b785bc33Benjamin Kramer return true; 149fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman } 150fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman 151ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// none - Returns true if none of the bits are set. 152ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool none() const { 153ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return !any(); 154ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 155ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 156ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// find_first - Returns the index of the first set bit, -1 if none 157ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// of the bits are set. 158ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng int find_first() const { 159ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng for (unsigned i = 0; i < NumBitWords(size()); ++i) 1600eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng if (Bits[i] != 0) { 161bed2946a96ecb15b0b636fa74cb26ce61b1c648eAnton Korobeynikov if (sizeof(BitWord) == 4) 162c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return i * BITWORD_SIZE + countTrailingZeros((uint32_t)Bits[i]); 16350bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 164c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); 16550bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 1660eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng } 167ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return -1; 168ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 169ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 170ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// find_next - Returns the index of the next set bit following the 171ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// "Prev" bit. Returns -1 if the next set bit is not found. 172ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng int find_next(unsigned Prev) const { 173ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng ++Prev; 174ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng if (Prev >= Size) 175ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return -1; 176ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 1772864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen unsigned WordPos = Prev / BITWORD_SIZE; 1782864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen unsigned BitPos = Prev % BITWORD_SIZE; 179ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitWord Copy = Bits[WordPos]; 180ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Mask off previous bits. 1811144af3c9b4da48cd581156e05b24261c8de366aRichard Smith Copy &= ~0UL << BitPos; 182ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 1830eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng if (Copy != 0) { 1840eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng if (sizeof(BitWord) == 4) 185c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return WordPos * BITWORD_SIZE + countTrailingZeros((uint32_t)Copy); 18650bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 187c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); 18850bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 1890eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng } 190ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 191ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Check subsequent words. 192ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i) 1930eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng if (Bits[i] != 0) { 194bed2946a96ecb15b0b636fa74cb26ce61b1c648eAnton Korobeynikov if (sizeof(BitWord) == 4) 195c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return i * BITWORD_SIZE + countTrailingZeros((uint32_t)Bits[i]); 19650bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 197c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); 19850bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 1990eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng } 200ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return -1; 201ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 202ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 203ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// clear - Clear all bits. 204ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng void clear() { 205ccae61c5da270b0684c4c7d2450d9bf3ff35aac7Evan Cheng Size = 0; 206ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 207ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 208ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// resize - Grow or shrink the bitvector. 209c761df18ae4979a8f2a0d3c5c35cda41db2a3f0bEvan Cheng void resize(unsigned N, bool t = false) { 2102864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen if (N > Capacity * BITWORD_SIZE) { 211ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned OldCapacity = Capacity; 212ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng grow(N); 213ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t); 214ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 2153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman // Set any old unused bits that are now included in the BitVector. This 2173a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman // may set bits that are not included in the new vector, but we will clear 218b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // them back out below. 219b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth if (N > Size) 220b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth set_unused_bits(t); 2213a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 222b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // Update the size, and clear out any bits that are now unused 223b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth unsigned OldSize = Size; 224ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Size = N; 225b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth if (t || N < OldSize) 226b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth clear_unused_bits(); 227ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 228ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 229ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng void reserve(unsigned N) { 2302864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen if (N > Capacity * BITWORD_SIZE) 231ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng grow(N); 232ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 233ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 234ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Set, reset, flip 235ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &set() { 2361f46998b3f05bea569db27b3de78a091aa943ca3Evan Cheng init_words(Bits, Capacity, true); 2371f46998b3f05bea569db27b3de78a091aa943ca3Evan Cheng clear_unused_bits(); 238ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 239ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 240ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 241ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &set(unsigned Idx) { 24236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE); 243ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 244ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 245ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 2463a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson /// set - Efficiently set a range of bits in [I, E) 2473a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson BitVector &set(unsigned I, unsigned E) { 2483a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(I <= E && "Attempted to set backwards range!"); 2493a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(E <= size() && "Attempted to set out-of-bounds range!"); 2503a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 2513a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson if (I == E) return *this; 2523a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 253e3f7be36c75ddcafb24b52c36c55c3dc17215db3Owen Anderson if (I / BITWORD_SIZE == E / BITWORD_SIZE) { 254e3f7be36c75ddcafb24b52c36c55c3dc17215db3Owen Anderson BitWord EMask = 1UL << (E % BITWORD_SIZE); 255e3f7be36c75ddcafb24b52c36c55c3dc17215db3Owen Anderson BitWord IMask = 1UL << (I % BITWORD_SIZE); 2563a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson BitWord Mask = EMask - IMask; 2573a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson Bits[I / BITWORD_SIZE] |= Mask; 2583a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson return *this; 2593a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } 2603a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 2613a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); 2623a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson Bits[I / BITWORD_SIZE] |= PrefixMask; 2633a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson I = RoundUpToAlignment(I, BITWORD_SIZE); 2643a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 2653a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) 2663a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson Bits[I / BITWORD_SIZE] = ~0UL; 2673a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 2683a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I < E) 27036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Bits[I / BITWORD_SIZE] |= PostfixMask; 2713a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 2723a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson return *this; 2733a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } 2743a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 275ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &reset() { 2761f46998b3f05bea569db27b3de78a091aa943ca3Evan Cheng init_words(Bits, Capacity, false); 277ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 278ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 279ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 280ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &reset(unsigned Idx) { 28136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE)); 282ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 283ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 284ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 2853a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson /// reset - Efficiently reset a range of bits in [I, E) 2863a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson BitVector &reset(unsigned I, unsigned E) { 2873a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(I <= E && "Attempted to reset backwards range!"); 2883a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(E <= size() && "Attempted to reset out-of-bounds range!"); 2893a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 2903a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson if (I == E) return *this; 2913a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 292e3f7be36c75ddcafb24b52c36c55c3dc17215db3Owen Anderson if (I / BITWORD_SIZE == E / BITWORD_SIZE) { 293e3f7be36c75ddcafb24b52c36c55c3dc17215db3Owen Anderson BitWord EMask = 1UL << (E % BITWORD_SIZE); 294e3f7be36c75ddcafb24b52c36c55c3dc17215db3Owen Anderson BitWord IMask = 1UL << (I % BITWORD_SIZE); 2953a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson BitWord Mask = EMask - IMask; 2963a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson Bits[I / BITWORD_SIZE] &= ~Mask; 2973a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson return *this; 2983a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } 2993a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 3003a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); 3013a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson Bits[I / BITWORD_SIZE] &= ~PrefixMask; 3023a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson I = RoundUpToAlignment(I, BITWORD_SIZE); 3033a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 3043a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) 3053a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson Bits[I / BITWORD_SIZE] = 0UL; 3063a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 3073a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; 30836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I < E) 30936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Bits[I / BITWORD_SIZE] &= ~PostfixMask; 3103a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 3113a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson return *this; 3123a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } 3133a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 314ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &flip() { 315ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng for (unsigned i = 0; i < NumBitWords(size()); ++i) 316ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Bits[i] = ~Bits[i]; 317ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng clear_unused_bits(); 318ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 319ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 320ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 321ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &flip(unsigned Idx) { 32236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE); 323ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 324ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 325ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 326ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Indexing. 327ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng reference operator[](unsigned Idx) { 3289324665a7845d6ffd23e3bd53443d28cbf2e75faTed Kremenek assert (Idx < Size && "Out-of-bounds Bit access."); 329ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return reference(*this, Idx); 330ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 331ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 332ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool operator[](unsigned Idx) const { 3333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman assert (Idx < Size && "Out-of-bounds Bit access."); 33436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE); 3352864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; 336ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 337ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 338ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool test(unsigned Idx) const { 339ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return (*this)[Idx]; 340ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 341ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 34203a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen /// Test if any common bits are set. 34303a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen bool anyCommon(const BitVector &RHS) const { 34403a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen unsigned ThisWords = NumBitWords(size()); 34503a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen unsigned RHSWords = NumBitWords(RHS.size()); 34603a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i) 34703a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen if (Bits[i] & RHS.Bits[i]) 34803a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen return true; 34903a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen return false; 35003a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen } 35103a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen 352ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Comparison operators. 353ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool operator==(const BitVector &RHS) const { 354886636445deeeb9283d262411a6fbe83b65056abChris Lattner unsigned ThisWords = NumBitWords(size()); 355886636445deeeb9283d262411a6fbe83b65056abChris Lattner unsigned RHSWords = NumBitWords(RHS.size()); 356886636445deeeb9283d262411a6fbe83b65056abChris Lattner unsigned i; 357886636445deeeb9283d262411a6fbe83b65056abChris Lattner for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 358ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng if (Bits[i] != RHS.Bits[i]) 359ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return false; 3603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 361886636445deeeb9283d262411a6fbe83b65056abChris Lattner // Verify that any extra words are all zeros. 362886636445deeeb9283d262411a6fbe83b65056abChris Lattner if (i != ThisWords) { 363886636445deeeb9283d262411a6fbe83b65056abChris Lattner for (; i != ThisWords; ++i) 364886636445deeeb9283d262411a6fbe83b65056abChris Lattner if (Bits[i]) 365886636445deeeb9283d262411a6fbe83b65056abChris Lattner return false; 366886636445deeeb9283d262411a6fbe83b65056abChris Lattner } else if (i != RHSWords) { 367886636445deeeb9283d262411a6fbe83b65056abChris Lattner for (; i != RHSWords; ++i) 368886636445deeeb9283d262411a6fbe83b65056abChris Lattner if (RHS.Bits[i]) 369886636445deeeb9283d262411a6fbe83b65056abChris Lattner return false; 370886636445deeeb9283d262411a6fbe83b65056abChris Lattner } 371ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return true; 372ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 373ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 374ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool operator!=(const BitVector &RHS) const { 375ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return !(*this == RHS); 376ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 377ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 378c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Intersection, union, disjoint union. 3798d8a0c36b70dacc73baa47ff6e92e5e774338117Roman Levenstein BitVector &operator&=(const BitVector &RHS) { 380343960af3177b056266fc719489e6ec7a5d869deChris Lattner unsigned ThisWords = NumBitWords(size()); 381343960af3177b056266fc719489e6ec7a5d869deChris Lattner unsigned RHSWords = NumBitWords(RHS.size()); 382343960af3177b056266fc719489e6ec7a5d869deChris Lattner unsigned i; 383343960af3177b056266fc719489e6ec7a5d869deChris Lattner for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 384ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Bits[i] &= RHS.Bits[i]; 3853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 386343960af3177b056266fc719489e6ec7a5d869deChris Lattner // Any bits that are just in this bitvector become zero, because they aren't 387343960af3177b056266fc719489e6ec7a5d869deChris Lattner // in the RHS bit vector. Any words only in RHS are ignored because they 388343960af3177b056266fc719489e6ec7a5d869deChris Lattner // are already zero in the LHS. 389343960af3177b056266fc719489e6ec7a5d869deChris Lattner for (; i != ThisWords; ++i) 390343960af3177b056266fc719489e6ec7a5d869deChris Lattner Bits[i] = 0; 3913a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 392ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 393ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 394ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 395c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. 39619de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen BitVector &reset(const BitVector &RHS) { 39719de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen unsigned ThisWords = NumBitWords(size()); 39819de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen unsigned RHSWords = NumBitWords(RHS.size()); 39919de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen unsigned i; 40019de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 40119de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen Bits[i] &= ~RHS.Bits[i]; 40219de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen return *this; 40319de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen } 40419de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen 405c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// test - Check if (This - RHS) is zero. 406c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// This is the same as reset(RHS) and any(). 407c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool test(const BitVector &RHS) const { 408c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned ThisWords = NumBitWords(size()); 409c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned RHSWords = NumBitWords(RHS.size()); 410c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned i; 411c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 412c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if ((Bits[i] & ~RHS.Bits[i]) != 0) 413c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return true; 414c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 415c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (; i != ThisWords ; ++i) 416c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (Bits[i] != 0) 417c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return true; 418c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 419c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return false; 420c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 421c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 4228d8a0c36b70dacc73baa47ff6e92e5e774338117Roman Levenstein BitVector &operator|=(const BitVector &RHS) { 423e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman if (size() < RHS.size()) 424e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman resize(RHS.size()); 425e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 426ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Bits[i] |= RHS.Bits[i]; 427ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 428ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 429ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 4308d8a0c36b70dacc73baa47ff6e92e5e774338117Roman Levenstein BitVector &operator^=(const BitVector &RHS) { 431e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman if (size() < RHS.size()) 432e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman resize(RHS.size()); 433e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 434ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Bits[i] ^= RHS.Bits[i]; 435ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 436ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 4373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 438ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Assignment operator. 439ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng const BitVector &operator=(const BitVector &RHS) { 440ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng if (this == &RHS) return *this; 441ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 442506e89949024a055fb9fc7258e96bf4b581135e4Evan Cheng Size = RHS.size(); 443506e89949024a055fb9fc7258e96bf4b581135e4Evan Cheng unsigned RHSWords = NumBitWords(Size); 4442864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen if (Size <= Capacity * BITWORD_SIZE) { 445730f743c013c85d15d902a137aef8f38916af616Chris Lattner if (Size) 44628116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer std::memcpy(Bits, RHS.Bits, RHSWords * sizeof(BitWord)); 447ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng clear_unused_bits(); 448ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 449ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 4503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 451ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Grow the bitvector to have enough elements. 452b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth Capacity = RHSWords; 45328116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 45428116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord)); 455ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 456ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Destroy the old bits. 45728116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer std::free(Bits); 458ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Bits = NewBits; 459ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 460ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 461ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 462ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 463693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer const BitVector &operator=(BitVector &&RHS) { 464693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer if (this == &RHS) return *this; 465693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 466693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer std::free(Bits); 467693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer Bits = RHS.Bits; 468693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer Size = RHS.Size; 469693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer Capacity = RHS.Capacity; 470693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 471dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.Bits = nullptr; 472693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 473693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer return *this; 474693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer } 475693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 476cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void swap(BitVector &RHS) { 477cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman std::swap(Bits, RHS.Bits); 478cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman std::swap(Size, RHS.Size); 479cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman std::swap(Capacity, RHS.Capacity); 480cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 481cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 482ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 483ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // Portable bit mask operations. 484ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 485ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // 486ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // These methods all operate on arrays of uint32_t, each holding 32 bits. The 487ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // fixed word size makes it easier to work with literal bit vector constants 488ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // in portable code. 489ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // 490ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // The LSB in each word is the lowest numbered bit. The size of a portable 491ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // bit mask is always a whole multiple of 32 bits. If no bit mask size is 492ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // given, the bit mask is assumed to cover the entire BitVector. 493ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 494ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. 495ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// This computes "*this |= Mask". 496ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 497ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen applyMask<true, false>(Mask, MaskWords); 498ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 499ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 500ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// clearBitsInMask - Clear any bits in this vector that are set in Mask. 501ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// Don't resize. This computes "*this &= ~Mask". 502ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 503ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen applyMask<false, false>(Mask, MaskWords); 504ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 505ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 506ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. 507ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// Don't resize. This computes "*this |= ~Mask". 508ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 509ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen applyMask<true, true>(Mask, MaskWords); 510ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 511ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 512ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. 513ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// Don't resize. This computes "*this &= Mask". 514ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 515ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen applyMask<false, true>(Mask, MaskWords); 516ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 517ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 518ad1d5c3bc55249b3291338288c90773ce80df11aEvan Chengprivate: 519ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned NumBitWords(unsigned S) const { 5202864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen return (S + BITWORD_SIZE-1) / BITWORD_SIZE; 521ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 5223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 523b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // Set the unused bits in the high words. 524b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth void set_unused_bits(bool t = true) { 525b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // Set high words first. 526b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth unsigned UsedWords = NumBitWords(Size); 527b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth if (Capacity > UsedWords) 528b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth init_words(&Bits[UsedWords], (Capacity-UsedWords), t); 5293a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 530b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // Then set any stray high bits of the last used word. 5312864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen unsigned ExtraBits = Size % BITWORD_SIZE; 532b5aabee33073068f1f6bb71c1da9000b03b16181Evan Cheng if (ExtraBits) { 5331144af3c9b4da48cd581156e05b24261c8de366aRichard Smith BitWord ExtraBitMask = ~0UL << ExtraBits; 5341144af3c9b4da48cd581156e05b24261c8de366aRichard Smith if (t) 5351144af3c9b4da48cd581156e05b24261c8de366aRichard Smith Bits[UsedWords-1] |= ExtraBitMask; 5361144af3c9b4da48cd581156e05b24261c8de366aRichard Smith else 5371144af3c9b4da48cd581156e05b24261c8de366aRichard Smith Bits[UsedWords-1] &= ~ExtraBitMask; 5385f92ce4696eaeca9d8b99b1a1fa784e78479d516Evan Cheng } 539ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 540ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 541b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // Clear the unused bits in the high words. 542b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth void clear_unused_bits() { 543b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth set_unused_bits(false); 544b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth } 545b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth 546ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng void grow(unsigned NewSize) { 54728116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer Capacity = std::max(NumBitWords(NewSize), Capacity * 2); 54828116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer Bits = (BitWord *)std::realloc(Bits, Capacity * sizeof(BitWord)); 5493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5509324665a7845d6ffd23e3bd53443d28cbf2e75faTed Kremenek clear_unused_bits(); 551ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 552ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 553ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng void init_words(BitWord *B, unsigned NumWords, bool t) { 5541f46998b3f05bea569db27b3de78a091aa943ca3Evan Cheng memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); 5553a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 556ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 557ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen template<bool AddBits, bool InvertMask> 558ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen void applyMask(const uint32_t *Mask, unsigned MaskWords) { 559ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen assert(BITWORD_SIZE % 32 == 0 && "Unsupported BitWord size."); 560ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen MaskWords = std::min(MaskWords, (size() + 31) / 32); 561ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen const unsigned Scale = BITWORD_SIZE / 32; 562ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen unsigned i; 563ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) { 564ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen BitWord BW = Bits[i]; 565ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // This inner loop should unroll completely when BITWORD_SIZE > 32. 566ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen for (unsigned b = 0; b != BITWORD_SIZE; b += 32) { 567ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen uint32_t M = *Mask++; 568ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen if (InvertMask) M = ~M; 569ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen if (AddBits) BW |= BitWord(M) << b; 570ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen else BW &= ~(BitWord(M) << b); 571ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 572ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen Bits[i] = BW; 573ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 574ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen for (unsigned b = 0; MaskWords; b += 32, --MaskWords) { 575ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen uint32_t M = *Mask++; 576ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen if (InvertMask) M = ~M; 577ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen if (AddBits) Bits[i] |= BitWord(M) << b; 578ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen else Bits[i] &= ~(BitWord(M) << b); 579ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 580ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen if (AddBits) 581ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen clear_unused_bits(); 582ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 583ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng}; 584ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 585ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng} // End llvm namespace 586cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 587cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmannamespace std { 588cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// Implement std::swap in terms of BitVector swap. 589cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman inline void 590cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { 591cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman LHS.swap(RHS); 592cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 593cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} 594cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 595ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng#endif 596