106f32e7eSjoerg //===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===// 206f32e7eSjoerg // 306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information. 506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 606f32e7eSjoerg // 706f32e7eSjoerg //===----------------------------------------------------------------------===// 806f32e7eSjoerg // 906f32e7eSjoerg // This file implements the SmallBitVector class. 1006f32e7eSjoerg // 1106f32e7eSjoerg //===----------------------------------------------------------------------===// 1206f32e7eSjoerg 1306f32e7eSjoerg #ifndef LLVM_ADT_SMALLBITVECTOR_H 1406f32e7eSjoerg #define LLVM_ADT_SMALLBITVECTOR_H 1506f32e7eSjoerg 1606f32e7eSjoerg #include "llvm/ADT/BitVector.h" 1706f32e7eSjoerg #include "llvm/ADT/iterator_range.h" 1806f32e7eSjoerg #include "llvm/Support/MathExtras.h" 1906f32e7eSjoerg #include <algorithm> 2006f32e7eSjoerg #include <cassert> 2106f32e7eSjoerg #include <climits> 2206f32e7eSjoerg #include <cstddef> 2306f32e7eSjoerg #include <cstdint> 2406f32e7eSjoerg #include <limits> 2506f32e7eSjoerg #include <utility> 2606f32e7eSjoerg 2706f32e7eSjoerg namespace llvm { 2806f32e7eSjoerg 2906f32e7eSjoerg /// This is a 'bitvector' (really, a variable-sized bit array), optimized for 3006f32e7eSjoerg /// the case when the array is small. It contains one pointer-sized field, which 3106f32e7eSjoerg /// is directly used as a plain collection of bits when possible, or as a 3206f32e7eSjoerg /// pointer to a larger heap-allocated array when necessary. This allows normal 3306f32e7eSjoerg /// "small" cases to be fast without losing generality for large inputs. 3406f32e7eSjoerg class SmallBitVector { 3506f32e7eSjoerg // TODO: In "large" mode, a pointer to a BitVector is used, leading to an 3606f32e7eSjoerg // unnecessary level of indirection. It would be more efficient to use a 3706f32e7eSjoerg // pointer to memory containing size, allocation size, and the array of bits. 3806f32e7eSjoerg uintptr_t X = 1; 3906f32e7eSjoerg 4006f32e7eSjoerg enum { 4106f32e7eSjoerg // The number of bits in this class. 4206f32e7eSjoerg NumBaseBits = sizeof(uintptr_t) * CHAR_BIT, 4306f32e7eSjoerg 4406f32e7eSjoerg // One bit is used to discriminate between small and large mode. The 4506f32e7eSjoerg // remaining bits are used for the small-mode representation. 4606f32e7eSjoerg SmallNumRawBits = NumBaseBits - 1, 4706f32e7eSjoerg 4806f32e7eSjoerg // A few more bits are used to store the size of the bit set in small mode. 4906f32e7eSjoerg // Theoretically this is a ceil-log2. These bits are encoded in the most 5006f32e7eSjoerg // significant bits of the raw bits. 5106f32e7eSjoerg SmallNumSizeBits = (NumBaseBits == 32 ? 5 : 5206f32e7eSjoerg NumBaseBits == 64 ? 6 : 5306f32e7eSjoerg SmallNumRawBits), 5406f32e7eSjoerg 5506f32e7eSjoerg // The remaining bits are used to store the actual set in small mode. 5606f32e7eSjoerg SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits 5706f32e7eSjoerg }; 5806f32e7eSjoerg 5906f32e7eSjoerg static_assert(NumBaseBits == 64 || NumBaseBits == 32, 6006f32e7eSjoerg "Unsupported word size"); 6106f32e7eSjoerg 6206f32e7eSjoerg public: 6306f32e7eSjoerg using size_type = unsigned; 6406f32e7eSjoerg 6506f32e7eSjoerg // Encapsulation of a single bit. 6606f32e7eSjoerg class reference { 6706f32e7eSjoerg SmallBitVector &TheVector; 6806f32e7eSjoerg unsigned BitPos; 6906f32e7eSjoerg 7006f32e7eSjoerg public: reference(SmallBitVector & b,unsigned Idx)7106f32e7eSjoerg reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} 7206f32e7eSjoerg 7306f32e7eSjoerg reference(const reference&) = default; 7406f32e7eSjoerg 7506f32e7eSjoerg reference& operator=(reference t) { 7606f32e7eSjoerg *this = bool(t); 7706f32e7eSjoerg return *this; 7806f32e7eSjoerg } 7906f32e7eSjoerg 8006f32e7eSjoerg reference& operator=(bool t) { 8106f32e7eSjoerg if (t) 8206f32e7eSjoerg TheVector.set(BitPos); 8306f32e7eSjoerg else 8406f32e7eSjoerg TheVector.reset(BitPos); 8506f32e7eSjoerg return *this; 8606f32e7eSjoerg } 8706f32e7eSjoerg 8806f32e7eSjoerg operator bool() const { 8906f32e7eSjoerg return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); 9006f32e7eSjoerg } 9106f32e7eSjoerg }; 9206f32e7eSjoerg 9306f32e7eSjoerg private: getPointer()9406f32e7eSjoerg BitVector *getPointer() const { 9506f32e7eSjoerg assert(!isSmall()); 9606f32e7eSjoerg return reinterpret_cast<BitVector *>(X); 9706f32e7eSjoerg } 9806f32e7eSjoerg switchToSmall(uintptr_t NewSmallBits,size_t NewSize)9906f32e7eSjoerg void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { 10006f32e7eSjoerg X = 1; 10106f32e7eSjoerg setSmallSize(NewSize); 10206f32e7eSjoerg setSmallBits(NewSmallBits); 10306f32e7eSjoerg } 10406f32e7eSjoerg switchToLarge(BitVector * BV)10506f32e7eSjoerg void switchToLarge(BitVector *BV) { 10606f32e7eSjoerg X = reinterpret_cast<uintptr_t>(BV); 10706f32e7eSjoerg assert(!isSmall() && "Tried to use an unaligned pointer"); 10806f32e7eSjoerg } 10906f32e7eSjoerg 11006f32e7eSjoerg // Return all the bits used for the "small" representation; this includes 11106f32e7eSjoerg // bits for the size as well as the element bits. getSmallRawBits()11206f32e7eSjoerg uintptr_t getSmallRawBits() const { 11306f32e7eSjoerg assert(isSmall()); 11406f32e7eSjoerg return X >> 1; 11506f32e7eSjoerg } 11606f32e7eSjoerg setSmallRawBits(uintptr_t NewRawBits)11706f32e7eSjoerg void setSmallRawBits(uintptr_t NewRawBits) { 11806f32e7eSjoerg assert(isSmall()); 11906f32e7eSjoerg X = (NewRawBits << 1) | uintptr_t(1); 12006f32e7eSjoerg } 12106f32e7eSjoerg 12206f32e7eSjoerg // Return the size. getSmallSize()12306f32e7eSjoerg size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; } 12406f32e7eSjoerg setSmallSize(size_t Size)12506f32e7eSjoerg void setSmallSize(size_t Size) { 12606f32e7eSjoerg setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); 12706f32e7eSjoerg } 12806f32e7eSjoerg 12906f32e7eSjoerg // Return the element bits. getSmallBits()13006f32e7eSjoerg uintptr_t getSmallBits() const { 13106f32e7eSjoerg return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); 13206f32e7eSjoerg } 13306f32e7eSjoerg setSmallBits(uintptr_t NewBits)13406f32e7eSjoerg void setSmallBits(uintptr_t NewBits) { 13506f32e7eSjoerg setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | 13606f32e7eSjoerg (getSmallSize() << SmallNumDataBits)); 13706f32e7eSjoerg } 13806f32e7eSjoerg 13906f32e7eSjoerg public: 14006f32e7eSjoerg /// Creates an empty bitvector. 14106f32e7eSjoerg SmallBitVector() = default; 14206f32e7eSjoerg 14306f32e7eSjoerg /// Creates a bitvector of specified number of bits. All bits are initialized 14406f32e7eSjoerg /// to the specified value. 14506f32e7eSjoerg explicit SmallBitVector(unsigned s, bool t = false) { 14606f32e7eSjoerg if (s <= SmallNumDataBits) 14706f32e7eSjoerg switchToSmall(t ? ~uintptr_t(0) : 0, s); 14806f32e7eSjoerg else 14906f32e7eSjoerg switchToLarge(new BitVector(s, t)); 15006f32e7eSjoerg } 15106f32e7eSjoerg 15206f32e7eSjoerg /// SmallBitVector copy ctor. SmallBitVector(const SmallBitVector & RHS)15306f32e7eSjoerg SmallBitVector(const SmallBitVector &RHS) { 15406f32e7eSjoerg if (RHS.isSmall()) 15506f32e7eSjoerg X = RHS.X; 15606f32e7eSjoerg else 15706f32e7eSjoerg switchToLarge(new BitVector(*RHS.getPointer())); 15806f32e7eSjoerg } 15906f32e7eSjoerg SmallBitVector(SmallBitVector && RHS)16006f32e7eSjoerg SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { 16106f32e7eSjoerg RHS.X = 1; 16206f32e7eSjoerg } 16306f32e7eSjoerg ~SmallBitVector()16406f32e7eSjoerg ~SmallBitVector() { 16506f32e7eSjoerg if (!isSmall()) 16606f32e7eSjoerg delete getPointer(); 16706f32e7eSjoerg } 16806f32e7eSjoerg 16906f32e7eSjoerg using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>; 17006f32e7eSjoerg using set_iterator = const_set_bits_iterator; 17106f32e7eSjoerg set_bits_begin()17206f32e7eSjoerg const_set_bits_iterator set_bits_begin() const { 17306f32e7eSjoerg return const_set_bits_iterator(*this); 17406f32e7eSjoerg } 17506f32e7eSjoerg set_bits_end()17606f32e7eSjoerg const_set_bits_iterator set_bits_end() const { 17706f32e7eSjoerg return const_set_bits_iterator(*this, -1); 17806f32e7eSjoerg } 17906f32e7eSjoerg set_bits()18006f32e7eSjoerg iterator_range<const_set_bits_iterator> set_bits() const { 18106f32e7eSjoerg return make_range(set_bits_begin(), set_bits_end()); 18206f32e7eSjoerg } 18306f32e7eSjoerg isSmall()18406f32e7eSjoerg bool isSmall() const { return X & uintptr_t(1); } 18506f32e7eSjoerg 18606f32e7eSjoerg /// Tests whether there are no bits in this bitvector. empty()18706f32e7eSjoerg bool empty() const { 18806f32e7eSjoerg return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); 18906f32e7eSjoerg } 19006f32e7eSjoerg 19106f32e7eSjoerg /// Returns the number of bits in this bitvector. size()19206f32e7eSjoerg size_t size() const { 19306f32e7eSjoerg return isSmall() ? getSmallSize() : getPointer()->size(); 19406f32e7eSjoerg } 19506f32e7eSjoerg 19606f32e7eSjoerg /// Returns the number of bits which are set. count()19706f32e7eSjoerg size_type count() const { 19806f32e7eSjoerg if (isSmall()) { 19906f32e7eSjoerg uintptr_t Bits = getSmallBits(); 20006f32e7eSjoerg return countPopulation(Bits); 20106f32e7eSjoerg } 20206f32e7eSjoerg return getPointer()->count(); 20306f32e7eSjoerg } 20406f32e7eSjoerg 20506f32e7eSjoerg /// Returns true if any bit is set. any()20606f32e7eSjoerg bool any() const { 20706f32e7eSjoerg if (isSmall()) 20806f32e7eSjoerg return getSmallBits() != 0; 20906f32e7eSjoerg return getPointer()->any(); 21006f32e7eSjoerg } 21106f32e7eSjoerg 21206f32e7eSjoerg /// Returns true if all bits are set. all()21306f32e7eSjoerg bool all() const { 21406f32e7eSjoerg if (isSmall()) 21506f32e7eSjoerg return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; 21606f32e7eSjoerg return getPointer()->all(); 21706f32e7eSjoerg } 21806f32e7eSjoerg 21906f32e7eSjoerg /// Returns true if none of the bits are set. none()22006f32e7eSjoerg bool none() const { 22106f32e7eSjoerg if (isSmall()) 22206f32e7eSjoerg return getSmallBits() == 0; 22306f32e7eSjoerg return getPointer()->none(); 22406f32e7eSjoerg } 22506f32e7eSjoerg 22606f32e7eSjoerg /// Returns the index of the first set bit, -1 if none of the bits are set. find_first()22706f32e7eSjoerg int find_first() const { 22806f32e7eSjoerg if (isSmall()) { 22906f32e7eSjoerg uintptr_t Bits = getSmallBits(); 23006f32e7eSjoerg if (Bits == 0) 23106f32e7eSjoerg return -1; 23206f32e7eSjoerg return countTrailingZeros(Bits); 23306f32e7eSjoerg } 23406f32e7eSjoerg return getPointer()->find_first(); 23506f32e7eSjoerg } 23606f32e7eSjoerg find_last()23706f32e7eSjoerg int find_last() const { 23806f32e7eSjoerg if (isSmall()) { 23906f32e7eSjoerg uintptr_t Bits = getSmallBits(); 24006f32e7eSjoerg if (Bits == 0) 24106f32e7eSjoerg return -1; 24206f32e7eSjoerg return NumBaseBits - countLeadingZeros(Bits) - 1; 24306f32e7eSjoerg } 24406f32e7eSjoerg return getPointer()->find_last(); 24506f32e7eSjoerg } 24606f32e7eSjoerg 24706f32e7eSjoerg /// Returns the index of the first unset bit, -1 if all of the bits are set. find_first_unset()24806f32e7eSjoerg int find_first_unset() const { 24906f32e7eSjoerg if (isSmall()) { 25006f32e7eSjoerg if (count() == getSmallSize()) 25106f32e7eSjoerg return -1; 25206f32e7eSjoerg 25306f32e7eSjoerg uintptr_t Bits = getSmallBits(); 25406f32e7eSjoerg return countTrailingOnes(Bits); 25506f32e7eSjoerg } 25606f32e7eSjoerg return getPointer()->find_first_unset(); 25706f32e7eSjoerg } 25806f32e7eSjoerg find_last_unset()25906f32e7eSjoerg int find_last_unset() const { 26006f32e7eSjoerg if (isSmall()) { 26106f32e7eSjoerg if (count() == getSmallSize()) 26206f32e7eSjoerg return -1; 26306f32e7eSjoerg 26406f32e7eSjoerg uintptr_t Bits = getSmallBits(); 26506f32e7eSjoerg // Set unused bits. 26606f32e7eSjoerg Bits |= ~uintptr_t(0) << getSmallSize(); 26706f32e7eSjoerg return NumBaseBits - countLeadingOnes(Bits) - 1; 26806f32e7eSjoerg } 26906f32e7eSjoerg return getPointer()->find_last_unset(); 27006f32e7eSjoerg } 27106f32e7eSjoerg 27206f32e7eSjoerg /// Returns the index of the next set bit following the "Prev" bit. 27306f32e7eSjoerg /// Returns -1 if the next set bit is not found. find_next(unsigned Prev)27406f32e7eSjoerg int find_next(unsigned Prev) const { 27506f32e7eSjoerg if (isSmall()) { 27606f32e7eSjoerg uintptr_t Bits = getSmallBits(); 27706f32e7eSjoerg // Mask off previous bits. 27806f32e7eSjoerg Bits &= ~uintptr_t(0) << (Prev + 1); 27906f32e7eSjoerg if (Bits == 0 || Prev + 1 >= getSmallSize()) 28006f32e7eSjoerg return -1; 28106f32e7eSjoerg return countTrailingZeros(Bits); 28206f32e7eSjoerg } 28306f32e7eSjoerg return getPointer()->find_next(Prev); 28406f32e7eSjoerg } 28506f32e7eSjoerg 28606f32e7eSjoerg /// Returns the index of the next unset bit following the "Prev" bit. 28706f32e7eSjoerg /// Returns -1 if the next unset bit is not found. find_next_unset(unsigned Prev)28806f32e7eSjoerg int find_next_unset(unsigned Prev) const { 28906f32e7eSjoerg if (isSmall()) { 29006f32e7eSjoerg uintptr_t Bits = getSmallBits(); 29106f32e7eSjoerg // Mask in previous bits. 292*da58b97aSjoerg Bits |= (uintptr_t(1) << (Prev + 1)) - 1; 293*da58b97aSjoerg // Mask in unused bits. 294*da58b97aSjoerg Bits |= ~uintptr_t(0) << getSmallSize(); 29506f32e7eSjoerg 29606f32e7eSjoerg if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize()) 29706f32e7eSjoerg return -1; 29806f32e7eSjoerg return countTrailingOnes(Bits); 29906f32e7eSjoerg } 30006f32e7eSjoerg return getPointer()->find_next_unset(Prev); 30106f32e7eSjoerg } 30206f32e7eSjoerg 30306f32e7eSjoerg /// find_prev - Returns the index of the first set bit that precedes the 30406f32e7eSjoerg /// the bit at \p PriorTo. Returns -1 if all previous bits are unset. find_prev(unsigned PriorTo)30506f32e7eSjoerg int find_prev(unsigned PriorTo) const { 30606f32e7eSjoerg if (isSmall()) { 30706f32e7eSjoerg if (PriorTo == 0) 30806f32e7eSjoerg return -1; 30906f32e7eSjoerg 31006f32e7eSjoerg --PriorTo; 31106f32e7eSjoerg uintptr_t Bits = getSmallBits(); 31206f32e7eSjoerg Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1); 31306f32e7eSjoerg if (Bits == 0) 31406f32e7eSjoerg return -1; 31506f32e7eSjoerg 31606f32e7eSjoerg return NumBaseBits - countLeadingZeros(Bits) - 1; 31706f32e7eSjoerg } 31806f32e7eSjoerg return getPointer()->find_prev(PriorTo); 31906f32e7eSjoerg } 32006f32e7eSjoerg 32106f32e7eSjoerg /// Clear all bits. clear()32206f32e7eSjoerg void clear() { 32306f32e7eSjoerg if (!isSmall()) 32406f32e7eSjoerg delete getPointer(); 32506f32e7eSjoerg switchToSmall(0, 0); 32606f32e7eSjoerg } 32706f32e7eSjoerg 32806f32e7eSjoerg /// Grow or shrink the bitvector. 32906f32e7eSjoerg void resize(unsigned N, bool t = false) { 33006f32e7eSjoerg if (!isSmall()) { 33106f32e7eSjoerg getPointer()->resize(N, t); 33206f32e7eSjoerg } else if (SmallNumDataBits >= N) { 33306f32e7eSjoerg uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; 33406f32e7eSjoerg setSmallSize(N); 33506f32e7eSjoerg setSmallBits(NewBits | getSmallBits()); 33606f32e7eSjoerg } else { 33706f32e7eSjoerg BitVector *BV = new BitVector(N, t); 33806f32e7eSjoerg uintptr_t OldBits = getSmallBits(); 33906f32e7eSjoerg for (size_t i = 0, e = getSmallSize(); i != e; ++i) 34006f32e7eSjoerg (*BV)[i] = (OldBits >> i) & 1; 34106f32e7eSjoerg switchToLarge(BV); 34206f32e7eSjoerg } 34306f32e7eSjoerg } 34406f32e7eSjoerg reserve(unsigned N)34506f32e7eSjoerg void reserve(unsigned N) { 34606f32e7eSjoerg if (isSmall()) { 34706f32e7eSjoerg if (N > SmallNumDataBits) { 34806f32e7eSjoerg uintptr_t OldBits = getSmallRawBits(); 34906f32e7eSjoerg size_t SmallSize = getSmallSize(); 35006f32e7eSjoerg BitVector *BV = new BitVector(SmallSize); 35106f32e7eSjoerg for (size_t i = 0; i < SmallSize; ++i) 35206f32e7eSjoerg if ((OldBits >> i) & 1) 35306f32e7eSjoerg BV->set(i); 35406f32e7eSjoerg BV->reserve(N); 35506f32e7eSjoerg switchToLarge(BV); 35606f32e7eSjoerg } 35706f32e7eSjoerg } else { 35806f32e7eSjoerg getPointer()->reserve(N); 35906f32e7eSjoerg } 36006f32e7eSjoerg } 36106f32e7eSjoerg 36206f32e7eSjoerg // Set, reset, flip set()36306f32e7eSjoerg SmallBitVector &set() { 36406f32e7eSjoerg if (isSmall()) 36506f32e7eSjoerg setSmallBits(~uintptr_t(0)); 36606f32e7eSjoerg else 36706f32e7eSjoerg getPointer()->set(); 36806f32e7eSjoerg return *this; 36906f32e7eSjoerg } 37006f32e7eSjoerg set(unsigned Idx)37106f32e7eSjoerg SmallBitVector &set(unsigned Idx) { 37206f32e7eSjoerg if (isSmall()) { 37306f32e7eSjoerg assert(Idx <= static_cast<unsigned>( 37406f32e7eSjoerg std::numeric_limits<uintptr_t>::digits) && 37506f32e7eSjoerg "undefined behavior"); 37606f32e7eSjoerg setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); 37706f32e7eSjoerg } 37806f32e7eSjoerg else 37906f32e7eSjoerg getPointer()->set(Idx); 38006f32e7eSjoerg return *this; 38106f32e7eSjoerg } 38206f32e7eSjoerg 38306f32e7eSjoerg /// Efficiently set a range of bits in [I, E) set(unsigned I,unsigned E)38406f32e7eSjoerg SmallBitVector &set(unsigned I, unsigned E) { 38506f32e7eSjoerg assert(I <= E && "Attempted to set backwards range!"); 38606f32e7eSjoerg assert(E <= size() && "Attempted to set out-of-bounds range!"); 38706f32e7eSjoerg if (I == E) return *this; 38806f32e7eSjoerg if (isSmall()) { 38906f32e7eSjoerg uintptr_t EMask = ((uintptr_t)1) << E; 39006f32e7eSjoerg uintptr_t IMask = ((uintptr_t)1) << I; 39106f32e7eSjoerg uintptr_t Mask = EMask - IMask; 39206f32e7eSjoerg setSmallBits(getSmallBits() | Mask); 39306f32e7eSjoerg } else 39406f32e7eSjoerg getPointer()->set(I, E); 39506f32e7eSjoerg return *this; 39606f32e7eSjoerg } 39706f32e7eSjoerg reset()39806f32e7eSjoerg SmallBitVector &reset() { 39906f32e7eSjoerg if (isSmall()) 40006f32e7eSjoerg setSmallBits(0); 40106f32e7eSjoerg else 40206f32e7eSjoerg getPointer()->reset(); 40306f32e7eSjoerg return *this; 40406f32e7eSjoerg } 40506f32e7eSjoerg reset(unsigned Idx)40606f32e7eSjoerg SmallBitVector &reset(unsigned Idx) { 40706f32e7eSjoerg if (isSmall()) 40806f32e7eSjoerg setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); 40906f32e7eSjoerg else 41006f32e7eSjoerg getPointer()->reset(Idx); 41106f32e7eSjoerg return *this; 41206f32e7eSjoerg } 41306f32e7eSjoerg 41406f32e7eSjoerg /// Efficiently reset a range of bits in [I, E) reset(unsigned I,unsigned E)41506f32e7eSjoerg SmallBitVector &reset(unsigned I, unsigned E) { 41606f32e7eSjoerg assert(I <= E && "Attempted to reset backwards range!"); 41706f32e7eSjoerg assert(E <= size() && "Attempted to reset out-of-bounds range!"); 41806f32e7eSjoerg if (I == E) return *this; 41906f32e7eSjoerg if (isSmall()) { 42006f32e7eSjoerg uintptr_t EMask = ((uintptr_t)1) << E; 42106f32e7eSjoerg uintptr_t IMask = ((uintptr_t)1) << I; 42206f32e7eSjoerg uintptr_t Mask = EMask - IMask; 42306f32e7eSjoerg setSmallBits(getSmallBits() & ~Mask); 42406f32e7eSjoerg } else 42506f32e7eSjoerg getPointer()->reset(I, E); 42606f32e7eSjoerg return *this; 42706f32e7eSjoerg } 42806f32e7eSjoerg flip()42906f32e7eSjoerg SmallBitVector &flip() { 43006f32e7eSjoerg if (isSmall()) 43106f32e7eSjoerg setSmallBits(~getSmallBits()); 43206f32e7eSjoerg else 43306f32e7eSjoerg getPointer()->flip(); 43406f32e7eSjoerg return *this; 43506f32e7eSjoerg } 43606f32e7eSjoerg flip(unsigned Idx)43706f32e7eSjoerg SmallBitVector &flip(unsigned Idx) { 43806f32e7eSjoerg if (isSmall()) 43906f32e7eSjoerg setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); 44006f32e7eSjoerg else 44106f32e7eSjoerg getPointer()->flip(Idx); 44206f32e7eSjoerg return *this; 44306f32e7eSjoerg } 44406f32e7eSjoerg 44506f32e7eSjoerg // No argument flip. 44606f32e7eSjoerg SmallBitVector operator~() const { 44706f32e7eSjoerg return SmallBitVector(*this).flip(); 44806f32e7eSjoerg } 44906f32e7eSjoerg 45006f32e7eSjoerg // Indexing. 45106f32e7eSjoerg reference operator[](unsigned Idx) { 45206f32e7eSjoerg assert(Idx < size() && "Out-of-bounds Bit access."); 45306f32e7eSjoerg return reference(*this, Idx); 45406f32e7eSjoerg } 45506f32e7eSjoerg 45606f32e7eSjoerg bool operator[](unsigned Idx) const { 45706f32e7eSjoerg assert(Idx < size() && "Out-of-bounds Bit access."); 45806f32e7eSjoerg if (isSmall()) 45906f32e7eSjoerg return ((getSmallBits() >> Idx) & 1) != 0; 46006f32e7eSjoerg return getPointer()->operator[](Idx); 46106f32e7eSjoerg } 46206f32e7eSjoerg test(unsigned Idx)46306f32e7eSjoerg bool test(unsigned Idx) const { 46406f32e7eSjoerg return (*this)[Idx]; 46506f32e7eSjoerg } 46606f32e7eSjoerg 46706f32e7eSjoerg // Push single bit to end of vector. push_back(bool Val)46806f32e7eSjoerg void push_back(bool Val) { 46906f32e7eSjoerg resize(size() + 1, Val); 47006f32e7eSjoerg } 47106f32e7eSjoerg 47206f32e7eSjoerg /// Test if any common bits are set. anyCommon(const SmallBitVector & RHS)47306f32e7eSjoerg bool anyCommon(const SmallBitVector &RHS) const { 47406f32e7eSjoerg if (isSmall() && RHS.isSmall()) 47506f32e7eSjoerg return (getSmallBits() & RHS.getSmallBits()) != 0; 47606f32e7eSjoerg if (!isSmall() && !RHS.isSmall()) 47706f32e7eSjoerg return getPointer()->anyCommon(*RHS.getPointer()); 47806f32e7eSjoerg 47906f32e7eSjoerg for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 48006f32e7eSjoerg if (test(i) && RHS.test(i)) 48106f32e7eSjoerg return true; 48206f32e7eSjoerg return false; 48306f32e7eSjoerg } 48406f32e7eSjoerg 48506f32e7eSjoerg // Comparison operators. 48606f32e7eSjoerg bool operator==(const SmallBitVector &RHS) const { 48706f32e7eSjoerg if (size() != RHS.size()) 48806f32e7eSjoerg return false; 48906f32e7eSjoerg if (isSmall() && RHS.isSmall()) 49006f32e7eSjoerg return getSmallBits() == RHS.getSmallBits(); 49106f32e7eSjoerg else if (!isSmall() && !RHS.isSmall()) 49206f32e7eSjoerg return *getPointer() == *RHS.getPointer(); 49306f32e7eSjoerg else { 49406f32e7eSjoerg for (size_t i = 0, e = size(); i != e; ++i) { 49506f32e7eSjoerg if ((*this)[i] != RHS[i]) 49606f32e7eSjoerg return false; 49706f32e7eSjoerg } 49806f32e7eSjoerg return true; 49906f32e7eSjoerg } 50006f32e7eSjoerg } 50106f32e7eSjoerg 50206f32e7eSjoerg bool operator!=(const SmallBitVector &RHS) const { 50306f32e7eSjoerg return !(*this == RHS); 50406f32e7eSjoerg } 50506f32e7eSjoerg 50606f32e7eSjoerg // Intersection, union, disjoint union. 50706f32e7eSjoerg // FIXME BitVector::operator&= does not resize the LHS but this does 50806f32e7eSjoerg SmallBitVector &operator&=(const SmallBitVector &RHS) { 50906f32e7eSjoerg resize(std::max(size(), RHS.size())); 51006f32e7eSjoerg if (isSmall() && RHS.isSmall()) 51106f32e7eSjoerg setSmallBits(getSmallBits() & RHS.getSmallBits()); 51206f32e7eSjoerg else if (!isSmall() && !RHS.isSmall()) 51306f32e7eSjoerg getPointer()->operator&=(*RHS.getPointer()); 51406f32e7eSjoerg else { 51506f32e7eSjoerg size_t i, e; 51606f32e7eSjoerg for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 51706f32e7eSjoerg (*this)[i] = test(i) && RHS.test(i); 51806f32e7eSjoerg for (e = size(); i != e; ++i) 51906f32e7eSjoerg reset(i); 52006f32e7eSjoerg } 52106f32e7eSjoerg return *this; 52206f32e7eSjoerg } 52306f32e7eSjoerg 52406f32e7eSjoerg /// Reset bits that are set in RHS. Same as *this &= ~RHS. reset(const SmallBitVector & RHS)52506f32e7eSjoerg SmallBitVector &reset(const SmallBitVector &RHS) { 52606f32e7eSjoerg if (isSmall() && RHS.isSmall()) 52706f32e7eSjoerg setSmallBits(getSmallBits() & ~RHS.getSmallBits()); 52806f32e7eSjoerg else if (!isSmall() && !RHS.isSmall()) 52906f32e7eSjoerg getPointer()->reset(*RHS.getPointer()); 53006f32e7eSjoerg else 53106f32e7eSjoerg for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 53206f32e7eSjoerg if (RHS.test(i)) 53306f32e7eSjoerg reset(i); 53406f32e7eSjoerg 53506f32e7eSjoerg return *this; 53606f32e7eSjoerg } 53706f32e7eSjoerg 53806f32e7eSjoerg /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any(). test(const SmallBitVector & RHS)53906f32e7eSjoerg bool test(const SmallBitVector &RHS) const { 54006f32e7eSjoerg if (isSmall() && RHS.isSmall()) 54106f32e7eSjoerg return (getSmallBits() & ~RHS.getSmallBits()) != 0; 54206f32e7eSjoerg if (!isSmall() && !RHS.isSmall()) 54306f32e7eSjoerg return getPointer()->test(*RHS.getPointer()); 54406f32e7eSjoerg 54506f32e7eSjoerg unsigned i, e; 54606f32e7eSjoerg for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 54706f32e7eSjoerg if (test(i) && !RHS.test(i)) 54806f32e7eSjoerg return true; 54906f32e7eSjoerg 55006f32e7eSjoerg for (e = size(); i != e; ++i) 55106f32e7eSjoerg if (test(i)) 55206f32e7eSjoerg return true; 55306f32e7eSjoerg 55406f32e7eSjoerg return false; 55506f32e7eSjoerg } 55606f32e7eSjoerg 55706f32e7eSjoerg SmallBitVector &operator|=(const SmallBitVector &RHS) { 55806f32e7eSjoerg resize(std::max(size(), RHS.size())); 55906f32e7eSjoerg if (isSmall() && RHS.isSmall()) 56006f32e7eSjoerg setSmallBits(getSmallBits() | RHS.getSmallBits()); 56106f32e7eSjoerg else if (!isSmall() && !RHS.isSmall()) 56206f32e7eSjoerg getPointer()->operator|=(*RHS.getPointer()); 56306f32e7eSjoerg else { 56406f32e7eSjoerg for (size_t i = 0, e = RHS.size(); i != e; ++i) 56506f32e7eSjoerg (*this)[i] = test(i) || RHS.test(i); 56606f32e7eSjoerg } 56706f32e7eSjoerg return *this; 56806f32e7eSjoerg } 56906f32e7eSjoerg 57006f32e7eSjoerg SmallBitVector &operator^=(const SmallBitVector &RHS) { 57106f32e7eSjoerg resize(std::max(size(), RHS.size())); 57206f32e7eSjoerg if (isSmall() && RHS.isSmall()) 57306f32e7eSjoerg setSmallBits(getSmallBits() ^ RHS.getSmallBits()); 57406f32e7eSjoerg else if (!isSmall() && !RHS.isSmall()) 57506f32e7eSjoerg getPointer()->operator^=(*RHS.getPointer()); 57606f32e7eSjoerg else { 57706f32e7eSjoerg for (size_t i = 0, e = RHS.size(); i != e; ++i) 57806f32e7eSjoerg (*this)[i] = test(i) != RHS.test(i); 57906f32e7eSjoerg } 58006f32e7eSjoerg return *this; 58106f32e7eSjoerg } 58206f32e7eSjoerg 58306f32e7eSjoerg SmallBitVector &operator<<=(unsigned N) { 58406f32e7eSjoerg if (isSmall()) 58506f32e7eSjoerg setSmallBits(getSmallBits() << N); 58606f32e7eSjoerg else 58706f32e7eSjoerg getPointer()->operator<<=(N); 58806f32e7eSjoerg return *this; 58906f32e7eSjoerg } 59006f32e7eSjoerg 59106f32e7eSjoerg SmallBitVector &operator>>=(unsigned N) { 59206f32e7eSjoerg if (isSmall()) 59306f32e7eSjoerg setSmallBits(getSmallBits() >> N); 59406f32e7eSjoerg else 59506f32e7eSjoerg getPointer()->operator>>=(N); 59606f32e7eSjoerg return *this; 59706f32e7eSjoerg } 59806f32e7eSjoerg 59906f32e7eSjoerg // Assignment operator. 60006f32e7eSjoerg const SmallBitVector &operator=(const SmallBitVector &RHS) { 60106f32e7eSjoerg if (isSmall()) { 60206f32e7eSjoerg if (RHS.isSmall()) 60306f32e7eSjoerg X = RHS.X; 60406f32e7eSjoerg else 60506f32e7eSjoerg switchToLarge(new BitVector(*RHS.getPointer())); 60606f32e7eSjoerg } else { 60706f32e7eSjoerg if (!RHS.isSmall()) 60806f32e7eSjoerg *getPointer() = *RHS.getPointer(); 60906f32e7eSjoerg else { 61006f32e7eSjoerg delete getPointer(); 61106f32e7eSjoerg X = RHS.X; 61206f32e7eSjoerg } 61306f32e7eSjoerg } 61406f32e7eSjoerg return *this; 61506f32e7eSjoerg } 61606f32e7eSjoerg 61706f32e7eSjoerg const SmallBitVector &operator=(SmallBitVector &&RHS) { 61806f32e7eSjoerg if (this != &RHS) { 61906f32e7eSjoerg clear(); 62006f32e7eSjoerg swap(RHS); 62106f32e7eSjoerg } 62206f32e7eSjoerg return *this; 62306f32e7eSjoerg } 62406f32e7eSjoerg swap(SmallBitVector & RHS)62506f32e7eSjoerg void swap(SmallBitVector &RHS) { 62606f32e7eSjoerg std::swap(X, RHS.X); 62706f32e7eSjoerg } 62806f32e7eSjoerg 62906f32e7eSjoerg /// Add '1' bits from Mask to this vector. Don't resize. 63006f32e7eSjoerg /// This computes "*this |= Mask". 63106f32e7eSjoerg void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 63206f32e7eSjoerg if (isSmall()) 63306f32e7eSjoerg applyMask<true, false>(Mask, MaskWords); 63406f32e7eSjoerg else 63506f32e7eSjoerg getPointer()->setBitsInMask(Mask, MaskWords); 63606f32e7eSjoerg } 63706f32e7eSjoerg 63806f32e7eSjoerg /// Clear any bits in this vector that are set in Mask. Don't resize. 63906f32e7eSjoerg /// This computes "*this &= ~Mask". 64006f32e7eSjoerg void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 64106f32e7eSjoerg if (isSmall()) 64206f32e7eSjoerg applyMask<false, false>(Mask, MaskWords); 64306f32e7eSjoerg else 64406f32e7eSjoerg getPointer()->clearBitsInMask(Mask, MaskWords); 64506f32e7eSjoerg } 64606f32e7eSjoerg 64706f32e7eSjoerg /// Add a bit to this vector for every '0' bit in Mask. Don't resize. 64806f32e7eSjoerg /// This computes "*this |= ~Mask". 64906f32e7eSjoerg void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 65006f32e7eSjoerg if (isSmall()) 65106f32e7eSjoerg applyMask<true, true>(Mask, MaskWords); 65206f32e7eSjoerg else 65306f32e7eSjoerg getPointer()->setBitsNotInMask(Mask, MaskWords); 65406f32e7eSjoerg } 65506f32e7eSjoerg 65606f32e7eSjoerg /// Clear a bit in this vector for every '0' bit in Mask. Don't resize. 65706f32e7eSjoerg /// This computes "*this &= Mask". 65806f32e7eSjoerg void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 65906f32e7eSjoerg if (isSmall()) 66006f32e7eSjoerg applyMask<false, true>(Mask, MaskWords); 66106f32e7eSjoerg else 66206f32e7eSjoerg getPointer()->clearBitsNotInMask(Mask, MaskWords); 66306f32e7eSjoerg } 66406f32e7eSjoerg invalid()665*da58b97aSjoerg void invalid() { 666*da58b97aSjoerg assert(empty()); 667*da58b97aSjoerg X = (uintptr_t)-1; 668*da58b97aSjoerg } isInvalid()669*da58b97aSjoerg bool isInvalid() const { return X == (uintptr_t)-1; } 670*da58b97aSjoerg getData(uintptr_t & Store)671*da58b97aSjoerg ArrayRef<uintptr_t> getData(uintptr_t &Store) const { 672*da58b97aSjoerg if (!isSmall()) 673*da58b97aSjoerg return getPointer()->getData(); 674*da58b97aSjoerg Store = getSmallBits(); 675*da58b97aSjoerg return makeArrayRef(Store); 676*da58b97aSjoerg } 677*da58b97aSjoerg 67806f32e7eSjoerg private: 67906f32e7eSjoerg template <bool AddBits, bool InvertMask> applyMask(const uint32_t * Mask,unsigned MaskWords)68006f32e7eSjoerg void applyMask(const uint32_t *Mask, unsigned MaskWords) { 68106f32e7eSjoerg assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!"); 68206f32e7eSjoerg uintptr_t M = Mask[0]; 68306f32e7eSjoerg if (NumBaseBits == 64) 68406f32e7eSjoerg M |= uint64_t(Mask[1]) << 32; 68506f32e7eSjoerg if (InvertMask) 68606f32e7eSjoerg M = ~M; 68706f32e7eSjoerg if (AddBits) 68806f32e7eSjoerg setSmallBits(getSmallBits() | M); 68906f32e7eSjoerg else 69006f32e7eSjoerg setSmallBits(getSmallBits() & ~M); 69106f32e7eSjoerg } 69206f32e7eSjoerg }; 69306f32e7eSjoerg 69406f32e7eSjoerg inline SmallBitVector 69506f32e7eSjoerg operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { 69606f32e7eSjoerg SmallBitVector Result(LHS); 69706f32e7eSjoerg Result &= RHS; 69806f32e7eSjoerg return Result; 69906f32e7eSjoerg } 70006f32e7eSjoerg 70106f32e7eSjoerg inline SmallBitVector 70206f32e7eSjoerg operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { 70306f32e7eSjoerg SmallBitVector Result(LHS); 70406f32e7eSjoerg Result |= RHS; 70506f32e7eSjoerg return Result; 70606f32e7eSjoerg } 70706f32e7eSjoerg 70806f32e7eSjoerg inline SmallBitVector 70906f32e7eSjoerg operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { 71006f32e7eSjoerg SmallBitVector Result(LHS); 71106f32e7eSjoerg Result ^= RHS; 71206f32e7eSjoerg return Result; 71306f32e7eSjoerg } 71406f32e7eSjoerg 715*da58b97aSjoerg template <> struct DenseMapInfo<SmallBitVector> { 716*da58b97aSjoerg static inline SmallBitVector getEmptyKey() { return SmallBitVector(); } 717*da58b97aSjoerg static inline SmallBitVector getTombstoneKey() { 718*da58b97aSjoerg SmallBitVector V; 719*da58b97aSjoerg V.invalid(); 720*da58b97aSjoerg return V; 721*da58b97aSjoerg } 722*da58b97aSjoerg static unsigned getHashValue(const SmallBitVector &V) { 723*da58b97aSjoerg uintptr_t Store; 724*da58b97aSjoerg return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue( 725*da58b97aSjoerg std::make_pair(V.size(), V.getData(Store))); 726*da58b97aSjoerg } 727*da58b97aSjoerg static bool isEqual(const SmallBitVector &LHS, const SmallBitVector &RHS) { 728*da58b97aSjoerg if (LHS.isInvalid() || RHS.isInvalid()) 729*da58b97aSjoerg return LHS.isInvalid() == RHS.isInvalid(); 730*da58b97aSjoerg return LHS == RHS; 731*da58b97aSjoerg } 732*da58b97aSjoerg }; 73306f32e7eSjoerg } // end namespace llvm 73406f32e7eSjoerg 73506f32e7eSjoerg namespace std { 73606f32e7eSjoerg 73706f32e7eSjoerg /// Implement std::swap in terms of BitVector swap. 73806f32e7eSjoerg inline void 73906f32e7eSjoerg swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { 74006f32e7eSjoerg LHS.swap(RHS); 74106f32e7eSjoerg } 74206f32e7eSjoerg 74306f32e7eSjoerg } // end namespace std 74406f32e7eSjoerg 74506f32e7eSjoerg #endif // LLVM_ADT_SMALLBITVECTOR_H 746