1cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman//===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===// 2cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// 3cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// The LLVM Compiler Infrastructure 4cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// 5cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// This file is distributed under the University of Illinois Open Source 6cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// License. See LICENSE.TXT for details. 7cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// 8cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman//===----------------------------------------------------------------------===// 9cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// 10cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// This file implements the SmallBitVector class. 11cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// 12cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman//===----------------------------------------------------------------------===// 13cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 14cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#ifndef LLVM_ADT_SMALLBITVECTOR_H 15cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#define LLVM_ADT_SMALLBITVECTOR_H 16cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 17cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#include "llvm/ADT/BitVector.h" 18693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer#include "llvm/Support/Compiler.h" 19cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#include "llvm/Support/MathExtras.h" 20cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#include <cassert> 21cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 22cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmannamespace llvm { 23cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 24cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// SmallBitVector - This is a 'bitvector' (really, a variable-sized bit array), 25cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// optimized for the case when the array is small. It contains one 26cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// pointer-sized field, which is directly used as a plain collection of bits 27cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// when possible, or as a pointer to a larger heap-allocated array when 28cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// necessary. This allows normal "small" cases to be fast without losing 29cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// generality for large inputs. 30cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// 31cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmanclass SmallBitVector { 32cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // TODO: In "large" mode, a pointer to a BitVector is used, leading to an 33cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // unnecessary level of indirection. It would be more efficient to use a 34cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // pointer to memory containing size, allocation size, and the array of bits. 351e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer uintptr_t X; 36cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 371e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer enum { 381e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // The number of bits in this class. 391e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer NumBaseBits = sizeof(uintptr_t) * CHAR_BIT, 40cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 411e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // One bit is used to discriminate between small and large mode. The 421e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // remaining bits are used for the small-mode representation. 431e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer SmallNumRawBits = NumBaseBits - 1, 44cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 451e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // A few more bits are used to store the size of the bit set in small mode. 461e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // Theoretically this is a ceil-log2. These bits are encoded in the most 471e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // significant bits of the raw bits. 481e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer SmallNumSizeBits = (NumBaseBits == 32 ? 5 : 491e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer NumBaseBits == 64 ? 6 : 501e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer SmallNumRawBits), 51cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 521e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // The remaining bits are used to store the actual set in small mode. 531e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits 541e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer }; 55cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 56b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramerpublic: 57cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typedef unsigned size_type; 58b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer // Encapsulation of a single bit. 59b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer class reference { 60b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer SmallBitVector &TheVector; 61b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer unsigned BitPos; 62b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 63b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer public: 64b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} 65b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 66b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer reference& operator=(reference t) { 67b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer *this = bool(t); 68b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer return *this; 69b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer } 70b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 71b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer reference& operator=(bool t) { 72b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer if (t) 73b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer TheVector.set(BitPos); 74b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer else 75b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer TheVector.reset(BitPos); 76b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer return *this; 77b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer } 78b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 79b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer operator bool() const { 80b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); 81b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer } 82b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer }; 83b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 84b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramerprivate: 85cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool isSmall() const { 861e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return X & uintptr_t(1); 871e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer } 881e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer 891e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer BitVector *getPointer() const { 901e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer assert(!isSmall()); 911e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return reinterpret_cast<BitVector *>(X); 92cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 93cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 94cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { 951e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer X = 1; 96cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallSize(NewSize); 97cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(NewSmallBits); 98cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 99cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 100cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void switchToLarge(BitVector *BV) { 1011e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer X = reinterpret_cast<uintptr_t>(BV); 1021e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer assert(!isSmall() && "Tried to use an unaligned pointer"); 103cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 104cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 105cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Return all the bits used for the "small" representation; this includes 106cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // bits for the size as well as the element bits. 107cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t getSmallRawBits() const { 1081e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer assert(isSmall()); 1091e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return X >> 1; 110cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 111cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 112cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void setSmallRawBits(uintptr_t NewRawBits) { 1131e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer assert(isSmall()); 114b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer X = (NewRawBits << 1) | uintptr_t(1); 115cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 116cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 117cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Return the size. 118cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman size_t getSmallSize() const { 119cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return getSmallRawBits() >> SmallNumDataBits; 120cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 121cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 122cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void setSmallSize(size_t Size) { 123cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); 124cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 125cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 126cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Return the element bits. 127cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t getSmallBits() const { 1281e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); 129cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 130cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 131cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void setSmallBits(uintptr_t NewBits) { 132b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | 1331e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer (getSmallSize() << SmallNumDataBits)); 134cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 135cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 136cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmanpublic: 137cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// SmallBitVector default ctor - Creates an empty bitvector. 1381e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer SmallBitVector() : X(1) {} 139cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 140cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// SmallBitVector ctor - Creates a bitvector of specified number of bits. All 141cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// bits are initialized to the specified value. 1421e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer explicit SmallBitVector(unsigned s, bool t = false) { 1431e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer if (s <= SmallNumDataBits) 144cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman switchToSmall(t ? ~uintptr_t(0) : 0, s); 145cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 146cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman switchToLarge(new BitVector(s, t)); 147cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 148cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 149cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// SmallBitVector copy ctor. 150cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector(const SmallBitVector &RHS) { 151cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (RHS.isSmall()) 152cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman X = RHS.X; 153cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 1541e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer switchToLarge(new BitVector(*RHS.getPointer())); 155cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 156cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 157693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { 158693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer RHS.X = 1; 159693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer } 160693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 161cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman ~SmallBitVector() { 162cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (!isSmall()) 1631e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer delete getPointer(); 164cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 165cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 166cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// empty - Tests whether there are no bits in this bitvector. 167cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool empty() const { 1681e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); 169cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 170cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 171cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// size - Returns the number of bits in this bitvector. 172cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman size_t size() const { 1731e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return isSmall() ? getSmallSize() : getPointer()->size(); 174cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 175cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 176cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// count - Returns the number of bits which are set. 177cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines size_type count() const { 178cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) { 179cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t Bits = getSmallBits(); 180d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 32) 181cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return CountPopulation_32(Bits); 182d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 64) 183cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return CountPopulation_64(Bits); 18450bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 185cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 1861e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->count(); 187cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 188cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 189cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// any - Returns true if any bit is set. 190cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool any() const { 191cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 192cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return getSmallBits() != 0; 1931e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->any(); 194cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 195cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 196fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman /// all - Returns true if all bits are set. 197fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman bool all() const { 198fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman if (isSmall()) 199fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; 200fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman return getPointer()->all(); 201fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman } 202fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman 203cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// none - Returns true if none of the bits are set. 204cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool none() const { 205cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 206cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return getSmallBits() == 0; 2071e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->none(); 208cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 209cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 210cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// find_first - Returns the index of the first set bit, -1 if none 211cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// of the bits are set. 212cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman int find_first() const { 213cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) { 214cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t Bits = getSmallBits(); 2156340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer if (Bits == 0) 2166340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer return -1; 217d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 32) 218c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return countTrailingZeros(Bits); 219d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 64) 220c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return countTrailingZeros(Bits); 22150bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 222cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 2231e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->find_first(); 224cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 225cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 226cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// find_next - Returns the index of the next set bit following the 227cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// "Prev" bit. Returns -1 if the next set bit is not found. 228cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman int find_next(unsigned Prev) const { 229cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) { 230cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t Bits = getSmallBits(); 231cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Mask off previous bits. 2321e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer Bits &= ~uintptr_t(0) << (Prev + 1); 2336340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer if (Bits == 0 || Prev + 1 >= getSmallSize()) 2346340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer return -1; 235d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 32) 236c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return countTrailingZeros(Bits); 237d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 64) 238c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return countTrailingZeros(Bits); 23950bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 240cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 2411e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->find_next(Prev); 242cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 243cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 244cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// clear - Clear all bits. 245cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void clear() { 246cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (!isSmall()) 2471e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer delete getPointer(); 248cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman switchToSmall(0, 0); 249cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 250cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 251cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// resize - Grow or shrink the bitvector. 252cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void resize(unsigned N, bool t = false) { 253cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (!isSmall()) { 2541e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->resize(N, t); 2551e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer } else if (SmallNumDataBits >= N) { 2561e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; 257cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallSize(N); 2581e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer setSmallBits(NewBits | getSmallBits()); 259cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } else { 260cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman BitVector *BV = new BitVector(N, t); 261cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t OldBits = getSmallBits(); 262cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman for (size_t i = 0, e = getSmallSize(); i != e; ++i) 263cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman (*BV)[i] = (OldBits >> i) & 1; 264cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman switchToLarge(BV); 265cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 266cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 267cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 268cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void reserve(unsigned N) { 269cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) { 270cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (N > SmallNumDataBits) { 271cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t OldBits = getSmallRawBits(); 272cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman size_t SmallSize = getSmallSize(); 273cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman BitVector *BV = new BitVector(SmallSize); 274cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman for (size_t i = 0; i < SmallSize; ++i) 275cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if ((OldBits >> i) & 1) 276cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman BV->set(i); 277cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman BV->reserve(N); 278cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman switchToLarge(BV); 279cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 280cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } else { 2811e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->reserve(N); 282cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 283cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 284cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 285cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Set, reset, flip 286cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &set() { 287cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 288cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(~uintptr_t(0)); 289cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 2901e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->set(); 291cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 292cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 293cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 294cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &set(unsigned Idx) { 295cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 296cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); 297cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 2981e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->set(Idx); 299cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 300cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 301cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 3023a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson /// set - Efficiently set a range of bits in [I, E) 3033a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson SmallBitVector &set(unsigned I, unsigned E) { 3043a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(I <= E && "Attempted to set backwards range!"); 3053a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(E <= size() && "Attempted to set out-of-bounds range!"); 3063a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson if (I == E) return *this; 3073a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson if (isSmall()) { 30882e9bc2f57c00c200d7227b94891f272462d9292Owen Anderson uintptr_t EMask = ((uintptr_t)1) << E; 30982e9bc2f57c00c200d7227b94891f272462d9292Owen Anderson uintptr_t IMask = ((uintptr_t)1) << I; 3103a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson uintptr_t Mask = EMask - IMask; 3113a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson setSmallBits(getSmallBits() | Mask); 3123a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } else 3133a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson getPointer()->set(I, E); 3143a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson return *this; 3153a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } 3163a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 317cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &reset() { 318cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 319cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(0); 320cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 3211e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->reset(); 322cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 323cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 324cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 325cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &reset(unsigned Idx) { 326cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 327cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); 328cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 3291e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->reset(Idx); 330cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 331cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 332cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 3333a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson /// reset - Efficiently reset a range of bits in [I, E) 3343a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson SmallBitVector &reset(unsigned I, unsigned E) { 3353a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(I <= E && "Attempted to reset backwards range!"); 3363a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(E <= size() && "Attempted to reset out-of-bounds range!"); 3373a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson if (I == E) return *this; 3383a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson if (isSmall()) { 33982e9bc2f57c00c200d7227b94891f272462d9292Owen Anderson uintptr_t EMask = ((uintptr_t)1) << E; 34082e9bc2f57c00c200d7227b94891f272462d9292Owen Anderson uintptr_t IMask = ((uintptr_t)1) << I; 3413a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson uintptr_t Mask = EMask - IMask; 3423a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson setSmallBits(getSmallBits() & ~Mask); 3433a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } else 3443a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson getPointer()->reset(I, E); 3453a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson return *this; 3463a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } 3473a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 348cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &flip() { 349cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 350cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(~getSmallBits()); 351cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 3521e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->flip(); 353cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 354cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 355cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 356cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &flip(unsigned Idx) { 357cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 358cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); 359cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 3601e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->flip(Idx); 361cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 362cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 363cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 364cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // No argument flip. 365cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector operator~() const { 366cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return SmallBitVector(*this).flip(); 367cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 368cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 369cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Indexing. 370b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer reference operator[](unsigned Idx) { 371b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer assert(Idx < size() && "Out-of-bounds Bit access."); 372b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer return reference(*this, Idx); 373b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer } 374b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 375cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool operator[](unsigned Idx) const { 376cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman assert(Idx < size() && "Out-of-bounds Bit access."); 377cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 378cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return ((getSmallBits() >> Idx) & 1) != 0; 3791e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->operator[](Idx); 380cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 381cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 382cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool test(unsigned Idx) const { 383cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return (*this)[Idx]; 384cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 385cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 386904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// Test if any common bits are set. 387904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer bool anyCommon(const SmallBitVector &RHS) const { 388904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (isSmall() && RHS.isSmall()) 389904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer return (getSmallBits() & RHS.getSmallBits()) != 0; 390904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (!isSmall() && !RHS.isSmall()) 391904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer return getPointer()->anyCommon(*RHS.getPointer()); 392904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 393904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 394904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (test(i) && RHS.test(i)) 395904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer return true; 396904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer return false; 397904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 398904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 399cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Comparison operators. 400cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool operator==(const SmallBitVector &RHS) const { 401cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (size() != RHS.size()) 402cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return false; 403cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 404cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return getSmallBits() == RHS.getSmallBits(); 405cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 4061e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return *getPointer() == *RHS.getPointer(); 407cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 408cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 409cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool operator!=(const SmallBitVector &RHS) const { 410cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return !(*this == RHS); 411cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 412cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 413cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Intersection, union, disjoint union. 414e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector &operator&=(const SmallBitVector &RHS) { 415e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman resize(std::max(size(), RHS.size())); 416e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman if (isSmall()) 417e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman setSmallBits(getSmallBits() & RHS.getSmallBits()); 418e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else if (!RHS.isSmall()) 4191e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator&=(*RHS.getPointer()); 420e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else { 421e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector Copy = RHS; 422e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman Copy.resize(size()); 4231e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator&=(*Copy.getPointer()); 424e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 425e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman return *this; 426e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 427459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer 428459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. 429459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer SmallBitVector &reset(const SmallBitVector &RHS) { 430459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer if (isSmall() && RHS.isSmall()) 431459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer setSmallBits(getSmallBits() & ~RHS.getSmallBits()); 432459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer else if (!isSmall() && !RHS.isSmall()) 433459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer getPointer()->reset(*RHS.getPointer()); 434459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer else 435459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 436459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer if (RHS.test(i)) 437459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer reset(i); 438459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer 439459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer return *this; 440459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer } 441459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer 442459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer /// test - Check if (This - RHS) is zero. 443459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer /// This is the same as reset(RHS) and any(). 444459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer bool test(const SmallBitVector &RHS) const { 445459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer if (isSmall() && RHS.isSmall()) 446459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer return (getSmallBits() & ~RHS.getSmallBits()) != 0; 447459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer if (!isSmall() && !RHS.isSmall()) 448459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer return getPointer()->test(*RHS.getPointer()); 449459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer 450459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer unsigned i, e; 451459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 452459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer if (test(i) && !RHS.test(i)) 453459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer return true; 454459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer 455459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer for (e = size(); i != e; ++i) 456459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer if (test(i)) 457459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer return true; 458459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer 459459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer return false; 460459d7bf8f6f1577c67d50c060bff7115d30f9fb9Benjamin Kramer } 461cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 462e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector &operator|=(const SmallBitVector &RHS) { 463e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman resize(std::max(size(), RHS.size())); 464e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman if (isSmall()) 465e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman setSmallBits(getSmallBits() | RHS.getSmallBits()); 466e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else if (!RHS.isSmall()) 4671e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator|=(*RHS.getPointer()); 468e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else { 469e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector Copy = RHS; 470e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman Copy.resize(size()); 4711e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator|=(*Copy.getPointer()); 472e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 473e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman return *this; 474e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 475cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 476e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector &operator^=(const SmallBitVector &RHS) { 477e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman resize(std::max(size(), RHS.size())); 478e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman if (isSmall()) 479e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman setSmallBits(getSmallBits() ^ RHS.getSmallBits()); 480e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else if (!RHS.isSmall()) 4811e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator^=(*RHS.getPointer()); 482e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else { 483e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector Copy = RHS; 484e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman Copy.resize(size()); 4851e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator^=(*Copy.getPointer()); 486e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 487e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman return *this; 488e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 489cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 490cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Assignment operator. 491cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman const SmallBitVector &operator=(const SmallBitVector &RHS) { 492cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) { 493cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (RHS.isSmall()) 494cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman X = RHS.X; 495cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 4961e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer switchToLarge(new BitVector(*RHS.getPointer())); 497cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } else { 498cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (!RHS.isSmall()) 4991e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer *getPointer() = *RHS.getPointer(); 500cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else { 5011e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer delete getPointer(); 502cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman X = RHS.X; 503cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 504cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 505cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 506cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 507cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 508693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer const SmallBitVector &operator=(SmallBitVector &&RHS) { 509693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer if (this != &RHS) { 510693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer clear(); 511693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer swap(RHS); 512693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer } 513693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer return *this; 514693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer } 515693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 516cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void swap(SmallBitVector &RHS) { 517cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman std::swap(X, RHS.X); 518cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 519904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 520904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. 521904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// This computes "*this |= Mask". 522904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 523904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (isSmall()) 524904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer applyMask<true, false>(Mask, MaskWords); 525904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else 526904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer getPointer()->setBitsInMask(Mask, MaskWords); 527904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 528904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 529904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// clearBitsInMask - Clear any bits in this vector that are set in Mask. 530904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// Don't resize. This computes "*this &= ~Mask". 531904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 532904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (isSmall()) 533904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer applyMask<false, false>(Mask, MaskWords); 534904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else 535904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer getPointer()->clearBitsInMask(Mask, MaskWords); 536904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 537904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 538904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. 539904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// Don't resize. This computes "*this |= ~Mask". 540904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 541904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (isSmall()) 542904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer applyMask<true, true>(Mask, MaskWords); 543904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else 544904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer getPointer()->setBitsNotInMask(Mask, MaskWords); 545904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 546904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 547904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. 548904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// Don't resize. This computes "*this &= Mask". 549904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 550904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (isSmall()) 551904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer applyMask<false, true>(Mask, MaskWords); 552904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else 553904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer getPointer()->clearBitsNotInMask(Mask, MaskWords); 554904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 555904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 556904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramerprivate: 557904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer template<bool AddBits, bool InvertMask> 558904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer void applyMask(const uint32_t *Mask, unsigned MaskWords) { 559904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer assert((NumBaseBits == 64 || NumBaseBits == 32) && "Unsupported word size"); 560904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (NumBaseBits == 64 && MaskWords >= 2) { 561904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer uint64_t M = Mask[0] | (uint64_t(Mask[1]) << 32); 562904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (InvertMask) M = ~M; 563904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (AddBits) setSmallBits(getSmallBits() | M); 564904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else setSmallBits(getSmallBits() & ~M); 565904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } else { 566904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer uint32_t M = Mask[0]; 567904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (InvertMask) M = ~M; 568904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (AddBits) setSmallBits(getSmallBits() | M); 569904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else setSmallBits(getSmallBits() & ~M); 570904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 571904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 572cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman}; 573cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 574cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmaninline SmallBitVector 575cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmanoperator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { 576cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector Result(LHS); 577cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman Result &= RHS; 578cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return Result; 579cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} 580cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 581cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmaninline SmallBitVector 582cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmanoperator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { 583cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector Result(LHS); 584cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman Result |= RHS; 585cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return Result; 586cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} 587cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 588cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmaninline SmallBitVector 589cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmanoperator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { 590cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector Result(LHS); 591cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman Result ^= RHS; 592cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return Result; 593cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} 594cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 595cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} // End llvm namespace 596cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 597cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmannamespace std { 598cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// Implement std::swap in terms of BitVector swap. 599cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman inline void 600cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { 601cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman LHS.swap(RHS); 602cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 603cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} 604cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 605cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#endif 606