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: 37ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Encapsulation of a single bit. 38ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng class reference { 39ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng friend class BitVector; 40ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 41ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitWord *WordRef; 42ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned BitPos; 43ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 44ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng reference(); // Undefined 45ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 46ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng public: 47ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng reference(BitVector &b, unsigned Idx) { 482864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen WordRef = &b.Bits[Idx / BITWORD_SIZE]; 492864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen BitPos = Idx % BITWORD_SIZE; 50ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 51ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 52ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng ~reference() {} 53ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 543f5e91565273e3f4639d37ee5a5b856699e8c9e5Dan Gohman reference &operator=(reference t) { 553f5e91565273e3f4639d37ee5a5b856699e8c9e5Dan Gohman *this = bool(t); 563f5e91565273e3f4639d37ee5a5b856699e8c9e5Dan Gohman return *this; 573f5e91565273e3f4639d37ee5a5b856699e8c9e5Dan Gohman } 583f5e91565273e3f4639d37ee5a5b856699e8c9e5Dan Gohman 59ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng reference& operator=(bool t) { 60ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng if (t) 61057f8e084515ca8e10eac5c37c8a9485b844343cEvan Cheng *WordRef |= 1L << BitPos; 62ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng else 63057f8e084515ca8e10eac5c37c8a9485b844343cEvan Cheng *WordRef &= ~(1L << BitPos); 64ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 65ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 66ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 67ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng operator bool() const { 68efd4a5144b03f61ebfd53d0245176f95e1170fb8Hartmut Kaiser return ((*WordRef) & (1L << BitPos)) ? true : false; 69ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 70ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng }; 71ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 72ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 73ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// BitVector default ctor - Creates an empty bitvector. 74ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector() : Size(0), Capacity(0) { 751baa88e3de8947b02d9ef4caa73e5860f048ec6eDan Gohman Bits = 0; 76ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 77ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 78ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// BitVector ctor - Creates a bitvector of specified number of bits. All 79ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// bits are initialized to the specified value. 80334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng explicit BitVector(unsigned s, bool t = false) : Size(s) { 81ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Capacity = NumBitWords(s); 8228116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 83ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng init_words(Bits, Capacity, t); 84334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng if (t) 85334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng clear_unused_bits(); 86ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 87ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 88ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// BitVector copy ctor. 89ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector(const BitVector &RHS) : Size(RHS.size()) { 90334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng if (Size == 0) { 911baa88e3de8947b02d9ef4caa73e5860f048ec6eDan Gohman Bits = 0; 929d1597b086114d643a8c5db71fffa72ae8bb06f3Reid Spencer Capacity = 0; 93334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng return; 94334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng } 95334df9d83f7a9f189d21c25a2d32afcd50bd0a9aEvan Cheng 96ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Capacity = NumBitWords(RHS.size()); 9728116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 9828116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord)); 99ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 1003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 101693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer#if LLVM_USE_RVALUE_REFERENCES 102693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer BitVector(BitVector &&RHS) 103693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) { 104693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer RHS.Bits = 0; 105693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer } 106693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer#endif 107693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 108b9174dd5dc2a782e617fe45200ec462bcef26ceeChris Lattner ~BitVector() { 10928116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer std::free(Bits); 110b9174dd5dc2a782e617fe45200ec462bcef26ceeChris Lattner } 111ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 112cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// empty - Tests whether there are no bits in this bitvector. 113cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool empty() const { return Size == 0; } 114cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 115ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// size - Returns the number of bits in this bitvector. 116ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned size() const { return Size; } 117ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 118ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// count - Returns the number of bits which are set. 119ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned count() const { 120ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned NumBits = 0; 121ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng for (unsigned i = 0; i < NumBitWords(size()); ++i) 1227bf26c1d68f75de9c1c8520620228b016bf9a0ebEvan Cheng if (sizeof(BitWord) == 4) 12334cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng NumBits += CountPopulation_32((uint32_t)Bits[i]); 1247bf26c1d68f75de9c1c8520620228b016bf9a0ebEvan Cheng else if (sizeof(BitWord) == 8) 1257bf26c1d68f75de9c1c8520620228b016bf9a0ebEvan Cheng NumBits += CountPopulation_64(Bits[i]); 1267bf26c1d68f75de9c1c8520620228b016bf9a0ebEvan Cheng else 12750bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 128ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return NumBits; 129ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 130ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 131ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// any - Returns true if any bit is set. 132ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool any() const { 133ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng for (unsigned i = 0; i < NumBitWords(size()); ++i) 134ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng if (Bits[i] != 0) 135ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return true; 136ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return false; 137ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 138ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 139fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman /// all - Returns true if all bits are set. 140fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman bool all() const { 141fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman // TODO: Optimize this. 142fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman return count() == size(); 143fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman } 144fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman 145ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// none - Returns true if none of the bits are set. 146ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool none() const { 147ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return !any(); 148ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 149ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 150ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// find_first - Returns the index of the first set bit, -1 if none 151ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// of the bits are set. 152ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng int find_first() const { 153ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng for (unsigned i = 0; i < NumBitWords(size()); ++i) 1540eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng if (Bits[i] != 0) { 155bed2946a96ecb15b0b636fa74cb26ce61b1c648eAnton Korobeynikov if (sizeof(BitWord) == 4) 15634cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); 15750bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 1582864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 15950bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 1600eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng } 161ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return -1; 162ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 163ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 164ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// find_next - Returns the index of the next set bit following the 165ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// "Prev" bit. Returns -1 if the next set bit is not found. 166ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng int find_next(unsigned Prev) const { 167ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng ++Prev; 168ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng if (Prev >= Size) 169ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return -1; 170ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 1712864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen unsigned WordPos = Prev / BITWORD_SIZE; 1722864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen unsigned BitPos = Prev % BITWORD_SIZE; 173ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitWord Copy = Bits[WordPos]; 174ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Mask off previous bits. 1751144af3c9b4da48cd581156e05b24261c8de366aRichard Smith Copy &= ~0UL << BitPos; 176ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 1770eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng if (Copy != 0) { 1780eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng if (sizeof(BitWord) == 4) 17934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng return WordPos * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Copy); 18050bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 1812864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); 18250bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 1830eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng } 184ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 185ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Check subsequent words. 186ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i) 1870eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng if (Bits[i] != 0) { 188bed2946a96ecb15b0b636fa74cb26ce61b1c648eAnton Korobeynikov if (sizeof(BitWord) == 4) 18934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); 19050bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 1912864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 19250bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 1930eca22af62c1e1500b1a937ccdec6d5ffe6ecd8aEvan Cheng } 194ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return -1; 195ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 196ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 197ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// clear - Clear all bits. 198ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng void clear() { 199ccae61c5da270b0684c4c7d2450d9bf3ff35aac7Evan Cheng Size = 0; 200ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 201ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 202ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng /// resize - Grow or shrink the bitvector. 203c761df18ae4979a8f2a0d3c5c35cda41db2a3f0bEvan Cheng void resize(unsigned N, bool t = false) { 2042864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen if (N > Capacity * BITWORD_SIZE) { 205ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned OldCapacity = Capacity; 206ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng grow(N); 207ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t); 208ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 2093a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman // Set any old unused bits that are now included in the BitVector. This 2113a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman // may set bits that are not included in the new vector, but we will clear 212b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // them back out below. 213b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth if (N > Size) 214b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth set_unused_bits(t); 2153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 216b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // Update the size, and clear out any bits that are now unused 217b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth unsigned OldSize = Size; 218ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Size = N; 219b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth if (t || N < OldSize) 220b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth clear_unused_bits(); 221ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 222ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 223ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng void reserve(unsigned N) { 2242864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen if (N > Capacity * BITWORD_SIZE) 225ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng grow(N); 226ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 227ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 228ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Set, reset, flip 229ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &set() { 2301f46998b3f05bea569db27b3de78a091aa943ca3Evan Cheng init_words(Bits, Capacity, true); 2311f46998b3f05bea569db27b3de78a091aa943ca3Evan Cheng clear_unused_bits(); 232ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 233ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 234ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 235ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &set(unsigned Idx) { 2362864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); 237ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 238ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 239ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 240ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &reset() { 2411f46998b3f05bea569db27b3de78a091aa943ca3Evan Cheng init_words(Bits, Capacity, false); 242ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 243ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 244ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 245ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &reset(unsigned Idx) { 2462864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); 247ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 248ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 249ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 250ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &flip() { 251ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng for (unsigned i = 0; i < NumBitWords(size()); ++i) 252ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Bits[i] = ~Bits[i]; 253ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng clear_unused_bits(); 254ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 255ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 256ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 257ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng BitVector &flip(unsigned Idx) { 2582864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen Bits[Idx / BITWORD_SIZE] ^= 1L << (Idx % BITWORD_SIZE); 259ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 260ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 261ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 262ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Indexing. 263ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng reference operator[](unsigned Idx) { 2649324665a7845d6ffd23e3bd53443d28cbf2e75faTed Kremenek assert (Idx < Size && "Out-of-bounds Bit access."); 265ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return reference(*this, Idx); 266ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 267ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 268ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool operator[](unsigned Idx) const { 2693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman assert (Idx < Size && "Out-of-bounds Bit access."); 2702864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen BitWord Mask = 1L << (Idx % BITWORD_SIZE); 2712864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; 272ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 273ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 274ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool test(unsigned Idx) const { 275ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return (*this)[Idx]; 276ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 277ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 27803a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen /// Test if any common bits are set. 27903a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen bool anyCommon(const BitVector &RHS) const { 28003a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen unsigned ThisWords = NumBitWords(size()); 28103a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen unsigned RHSWords = NumBitWords(RHS.size()); 28203a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i) 28303a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen if (Bits[i] & RHS.Bits[i]) 28403a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen return true; 28503a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen return false; 28603a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen } 28703a3811ab48139f45cf47f1168788e630af0d40bJakob Stoklund Olesen 288ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Comparison operators. 289ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool operator==(const BitVector &RHS) const { 290886636445deeeb9283d262411a6fbe83b65056abChris Lattner unsigned ThisWords = NumBitWords(size()); 291886636445deeeb9283d262411a6fbe83b65056abChris Lattner unsigned RHSWords = NumBitWords(RHS.size()); 292886636445deeeb9283d262411a6fbe83b65056abChris Lattner unsigned i; 293886636445deeeb9283d262411a6fbe83b65056abChris Lattner for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 294ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng if (Bits[i] != RHS.Bits[i]) 295ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return false; 2963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 297886636445deeeb9283d262411a6fbe83b65056abChris Lattner // Verify that any extra words are all zeros. 298886636445deeeb9283d262411a6fbe83b65056abChris Lattner if (i != ThisWords) { 299886636445deeeb9283d262411a6fbe83b65056abChris Lattner for (; i != ThisWords; ++i) 300886636445deeeb9283d262411a6fbe83b65056abChris Lattner if (Bits[i]) 301886636445deeeb9283d262411a6fbe83b65056abChris Lattner return false; 302886636445deeeb9283d262411a6fbe83b65056abChris Lattner } else if (i != RHSWords) { 303886636445deeeb9283d262411a6fbe83b65056abChris Lattner for (; i != RHSWords; ++i) 304886636445deeeb9283d262411a6fbe83b65056abChris Lattner if (RHS.Bits[i]) 305886636445deeeb9283d262411a6fbe83b65056abChris Lattner return false; 306886636445deeeb9283d262411a6fbe83b65056abChris Lattner } 307ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return true; 308ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 309ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 310ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng bool operator!=(const BitVector &RHS) const { 311ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return !(*this == RHS); 312ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 313ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 314c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Intersection, union, disjoint union. 3158d8a0c36b70dacc73baa47ff6e92e5e774338117Roman Levenstein BitVector &operator&=(const BitVector &RHS) { 316343960af3177b056266fc719489e6ec7a5d869deChris Lattner unsigned ThisWords = NumBitWords(size()); 317343960af3177b056266fc719489e6ec7a5d869deChris Lattner unsigned RHSWords = NumBitWords(RHS.size()); 318343960af3177b056266fc719489e6ec7a5d869deChris Lattner unsigned i; 319343960af3177b056266fc719489e6ec7a5d869deChris Lattner for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 320ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Bits[i] &= RHS.Bits[i]; 3213a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 322343960af3177b056266fc719489e6ec7a5d869deChris Lattner // Any bits that are just in this bitvector become zero, because they aren't 323343960af3177b056266fc719489e6ec7a5d869deChris Lattner // in the RHS bit vector. Any words only in RHS are ignored because they 324343960af3177b056266fc719489e6ec7a5d869deChris Lattner // are already zero in the LHS. 325343960af3177b056266fc719489e6ec7a5d869deChris Lattner for (; i != ThisWords; ++i) 326343960af3177b056266fc719489e6ec7a5d869deChris Lattner Bits[i] = 0; 3273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 328ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 329ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 330ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 331c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. 33219de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen BitVector &reset(const BitVector &RHS) { 33319de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen unsigned ThisWords = NumBitWords(size()); 33419de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen unsigned RHSWords = NumBitWords(RHS.size()); 33519de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen unsigned i; 33619de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 33719de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen Bits[i] &= ~RHS.Bits[i]; 33819de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen return *this; 33919de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen } 34019de016955f744cf2466fadcd28e9bf8847dd260Jakob Stoklund Olesen 341c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// test - Check if (This - RHS) is zero. 342c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// This is the same as reset(RHS) and any(). 343c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool test(const BitVector &RHS) const { 344c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned ThisWords = NumBitWords(size()); 345c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned RHSWords = NumBitWords(RHS.size()); 346c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned i; 347c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (i = 0; i != std::min(ThisWords, RHSWords); ++i) 348c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if ((Bits[i] & ~RHS.Bits[i]) != 0) 349c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return true; 350c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 351c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (; i != ThisWords ; ++i) 352c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (Bits[i] != 0) 353c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return true; 354c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 355c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return false; 356c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 357c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 3588d8a0c36b70dacc73baa47ff6e92e5e774338117Roman Levenstein BitVector &operator|=(const BitVector &RHS) { 359e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman if (size() < RHS.size()) 360e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman resize(RHS.size()); 361e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 362ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Bits[i] |= RHS.Bits[i]; 363ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 364ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 365ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 3668d8a0c36b70dacc73baa47ff6e92e5e774338117Roman Levenstein BitVector &operator^=(const BitVector &RHS) { 367e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman if (size() < RHS.size()) 368e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman resize(RHS.size()); 369e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) 370ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Bits[i] ^= RHS.Bits[i]; 371ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 372ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 3733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 374ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Assignment operator. 375ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng const BitVector &operator=(const BitVector &RHS) { 376ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng if (this == &RHS) return *this; 377ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 378506e89949024a055fb9fc7258e96bf4b581135e4Evan Cheng Size = RHS.size(); 379506e89949024a055fb9fc7258e96bf4b581135e4Evan Cheng unsigned RHSWords = NumBitWords(Size); 3802864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen if (Size <= Capacity * BITWORD_SIZE) { 381730f743c013c85d15d902a137aef8f38916af616Chris Lattner if (Size) 38228116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer std::memcpy(Bits, RHS.Bits, RHSWords * sizeof(BitWord)); 383ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng clear_unused_bits(); 384ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 385ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 3863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 387ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Grow the bitvector to have enough elements. 388b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth Capacity = RHSWords; 38928116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); 39028116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord)); 391ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 392ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng // Destroy the old bits. 39328116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer std::free(Bits); 394ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng Bits = NewBits; 395ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 396ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng return *this; 397ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 398ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 399693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer#if LLVM_USE_RVALUE_REFERENCES 400693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer const BitVector &operator=(BitVector &&RHS) { 401693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer if (this == &RHS) return *this; 402693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 403693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer std::free(Bits); 404693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer Bits = RHS.Bits; 405693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer Size = RHS.Size; 406693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer Capacity = RHS.Capacity; 407693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 408693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer RHS.Bits = 0; 409693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 410693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer return *this; 411693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer } 412693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer#endif 413693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 414cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void swap(BitVector &RHS) { 415cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman std::swap(Bits, RHS.Bits); 416cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman std::swap(Size, RHS.Size); 417cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman std::swap(Capacity, RHS.Capacity); 418cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 419cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 420ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 421ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // Portable bit mask operations. 422ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 423ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // 424ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // These methods all operate on arrays of uint32_t, each holding 32 bits. The 425ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // fixed word size makes it easier to work with literal bit vector constants 426ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // in portable code. 427ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // 428ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // The LSB in each word is the lowest numbered bit. The size of a portable 429ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // bit mask is always a whole multiple of 32 bits. If no bit mask size is 430ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // given, the bit mask is assumed to cover the entire BitVector. 431ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 432ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. 433ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// This computes "*this |= Mask". 434ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 435ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen applyMask<true, false>(Mask, MaskWords); 436ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 437ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 438ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// clearBitsInMask - Clear any bits in this vector that are set in Mask. 439ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// Don't resize. This computes "*this &= ~Mask". 440ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 441ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen applyMask<false, false>(Mask, MaskWords); 442ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 443ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 444ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. 445ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// Don't resize. This computes "*this |= ~Mask". 446ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 447ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen applyMask<true, true>(Mask, MaskWords); 448ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 449ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 450ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. 451ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen /// Don't resize. This computes "*this &= Mask". 452ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 453ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen applyMask<false, true>(Mask, MaskWords); 454ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 455ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 456ad1d5c3bc55249b3291338288c90773ce80df11aEvan Chengprivate: 457ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng unsigned NumBitWords(unsigned S) const { 4582864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen return (S + BITWORD_SIZE-1) / BITWORD_SIZE; 459ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 4603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 461b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // Set the unused bits in the high words. 462b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth void set_unused_bits(bool t = true) { 463b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // Set high words first. 464b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth unsigned UsedWords = NumBitWords(Size); 465b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth if (Capacity > UsedWords) 466b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth init_words(&Bits[UsedWords], (Capacity-UsedWords), t); 4673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 468b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // Then set any stray high bits of the last used word. 4692864b77efc986a5c80c262c753a8f9df0cf789edJeff Cohen unsigned ExtraBits = Size % BITWORD_SIZE; 470b5aabee33073068f1f6bb71c1da9000b03b16181Evan Cheng if (ExtraBits) { 4711144af3c9b4da48cd581156e05b24261c8de366aRichard Smith BitWord ExtraBitMask = ~0UL << ExtraBits; 4721144af3c9b4da48cd581156e05b24261c8de366aRichard Smith if (t) 4731144af3c9b4da48cd581156e05b24261c8de366aRichard Smith Bits[UsedWords-1] |= ExtraBitMask; 4741144af3c9b4da48cd581156e05b24261c8de366aRichard Smith else 4751144af3c9b4da48cd581156e05b24261c8de366aRichard Smith Bits[UsedWords-1] &= ~ExtraBitMask; 4765f92ce4696eaeca9d8b99b1a1fa784e78479d516Evan Cheng } 477ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 478ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 479b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth // Clear the unused bits in the high words. 480b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth void clear_unused_bits() { 481b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth set_unused_bits(false); 482b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth } 483b1183c1ff3b17689c036d5e7443b7343074d2f6fChandler Carruth 484ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng void grow(unsigned NewSize) { 48528116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer Capacity = std::max(NumBitWords(NewSize), Capacity * 2); 48628116c9f498ec3b40dae90b3a94ba4ceb1a2081cBenjamin Kramer Bits = (BitWord *)std::realloc(Bits, Capacity * sizeof(BitWord)); 4873a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4889324665a7845d6ffd23e3bd53443d28cbf2e75faTed Kremenek clear_unused_bits(); 489ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng } 490ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 491ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng void init_words(BitWord *B, unsigned NumWords, bool t) { 4921f46998b3f05bea569db27b3de78a091aa943ca3Evan Cheng memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); 4933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 494ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen 495ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen template<bool AddBits, bool InvertMask> 496ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen void applyMask(const uint32_t *Mask, unsigned MaskWords) { 497ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen assert(BITWORD_SIZE % 32 == 0 && "Unsupported BitWord size."); 498ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen MaskWords = std::min(MaskWords, (size() + 31) / 32); 499ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen const unsigned Scale = BITWORD_SIZE / 32; 500ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen unsigned i; 501ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) { 502ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen BitWord BW = Bits[i]; 503ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen // This inner loop should unroll completely when BITWORD_SIZE > 32. 504ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen for (unsigned b = 0; b != BITWORD_SIZE; b += 32) { 505ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen uint32_t M = *Mask++; 506ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen if (InvertMask) M = ~M; 507ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen if (AddBits) BW |= BitWord(M) << b; 508ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen else BW &= ~(BitWord(M) << b); 509ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 510ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen Bits[i] = BW; 511ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 512ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen for (unsigned b = 0; MaskWords; b += 32, --MaskWords) { 513ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen uint32_t M = *Mask++; 514ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen if (InvertMask) M = ~M; 515ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen if (AddBits) Bits[i] |= BitWord(M) << b; 516ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen else Bits[i] &= ~(BitWord(M) << b); 517ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 518ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen if (AddBits) 519ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen clear_unused_bits(); 520ff5bad078782b6472d6cd0974bf08fe3473050e6Jakob Stoklund Olesen } 521ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng}; 522ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng 523ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng} // End llvm namespace 524cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 525cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmannamespace std { 526cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// Implement std::swap in terms of BitVector swap. 527cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman inline void 528cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { 529cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman LHS.swap(RHS); 530cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 531cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} 532cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 533ad1d5c3bc55249b3291338288c90773ce80df11aEvan Cheng#endif 534