X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FBitVector.h;h=9c046efaaddd9cf7bfec7d6d70b37e23f848417e;hb=104cf9e02b0ed94d4173869a598af6c6972a8660;hp=6418f7f66b4b1c1e2da1a8b19d2153e46cd451a7;hpb=2864b77efc986a5c80c262c753a8f9df0cf789ed;p=oota-llvm.git diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index 6418f7f66b4..9c046efaadd 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Evan Cheng and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -16,17 +16,18 @@ #include "llvm/Support/MathExtras.h" #include -#include #include +#include +#include namespace llvm { class BitVector { typedef unsigned long BitWord; - enum { BITWORD_SIZE = sizeof(BitWord) * 8 }; + enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; - BitWord *Bits; // Actual bits. + BitWord *Bits; // Actual bits. unsigned Size; // Size of bitvector in bits. unsigned Capacity; // Size of allocated memory in BitWord. @@ -57,14 +58,14 @@ public: } operator bool() const { - return (*WordRef) & (1L << BitPos); + return ((*WordRef) & (1L << BitPos)) ? true : false; } }; /// BitVector default ctor - Creates an empty bitvector. BitVector() : Size(0), Capacity(0) { - Bits = NULL; + Bits = 0; } /// BitVector ctor - Creates a bitvector of specified number of bits. All @@ -80,7 +81,7 @@ public: /// BitVector copy ctor. BitVector(const BitVector &RHS) : Size(RHS.size()) { if (Size == 0) { - Bits = NULL; + Bits = 0; Capacity = 0; return; } @@ -89,7 +90,7 @@ public: Bits = new BitWord[Capacity]; std::copy(RHS.Bits, &RHS.Bits[Capacity], Bits); } - + ~BitVector() { delete[] Bits; } @@ -102,7 +103,7 @@ public: unsigned NumBits = 0; for (unsigned i = 0; i < NumBitWords(size()); ++i) if (sizeof(BitWord) == 4) - NumBits += CountPopulation_32(Bits[i]); + NumBits += CountPopulation_32((uint32_t)Bits[i]); else if (sizeof(BitWord) == 8) NumBits += CountPopulation_64(Bits[i]); else @@ -129,7 +130,7 @@ public: for (unsigned i = 0; i < NumBitWords(size()); ++i) if (Bits[i] != 0) { if (sizeof(BitWord) == 4) - return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); + return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); else if (sizeof(BitWord) == 8) return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); else @@ -153,7 +154,7 @@ public: if (Copy != 0) { if (sizeof(BitWord) == 4) - return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy); + return WordPos * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Copy); else if (sizeof(BitWord) == 8) return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); else @@ -164,7 +165,7 @@ public: for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i) if (Bits[i] != 0) { if (sizeof(BitWord) == 4) - return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); + return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); else if (sizeof(BitWord) == 8) return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); else @@ -185,8 +186,18 @@ public: grow(N); init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t); } + + // Set any old unused bits that are now included in the BitVector. This + // may set bits that are not included in the new vector, but we will clear + // them back out below. + if (N > Size) + set_unused_bits(t); + + // Update the size, and clear out any bits that are now unused + unsigned OldSize = Size; Size = N; - clear_unused_bits(); + if (t || N < OldSize) + clear_unused_bits(); } void reserve(unsigned N) { @@ -235,10 +246,12 @@ public: // Indexing. reference operator[](unsigned Idx) { + assert (Idx < Size && "Out-of-bounds Bit access."); return reference(*this, Idx); } bool operator[](unsigned Idx) const { + assert (Idx < Size && "Out-of-bounds Bit access."); BitWord Mask = 1L << (Idx % BITWORD_SIZE); return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; } @@ -249,12 +262,23 @@ public: // Comparison operators. bool operator==(const BitVector &RHS) const { - if (Size != RHS.Size) - return false; - - for (unsigned i = 0; i < NumBitWords(size()); ++i) + unsigned ThisWords = NumBitWords(size()); + unsigned RHSWords = NumBitWords(RHS.size()); + unsigned i; + for (i = 0; i != std::min(ThisWords, RHSWords); ++i) if (Bits[i] != RHS.Bits[i]) return false; + + // Verify that any extra words are all zeros. + if (i != ThisWords) { + for (; i != ThisWords; ++i) + if (Bits[i]) + return false; + } else if (i != RHSWords) { + for (; i != RHSWords; ++i) + if (RHS.Bits[i]) + return false; + } return true; } @@ -263,27 +287,36 @@ public: } // Intersection, union, disjoint union. - BitVector operator&=(const BitVector &RHS) { - assert(Size == RHS.Size && "Illegal operation!"); - for (unsigned i = 0; i < NumBitWords(size()); ++i) + BitVector &operator&=(const BitVector &RHS) { + unsigned ThisWords = NumBitWords(size()); + unsigned RHSWords = NumBitWords(RHS.size()); + unsigned i; + for (i = 0; i != std::min(ThisWords, RHSWords); ++i) Bits[i] &= RHS.Bits[i]; + + // Any bits that are just in this bitvector become zero, because they aren't + // in the RHS bit vector. Any words only in RHS are ignored because they + // are already zero in the LHS. + for (; i != ThisWords; ++i) + Bits[i] = 0; + return *this; } - BitVector operator|=(const BitVector &RHS) { + BitVector &operator|=(const BitVector &RHS) { assert(Size == RHS.Size && "Illegal operation!"); for (unsigned i = 0; i < NumBitWords(size()); ++i) Bits[i] |= RHS.Bits[i]; return *this; } - BitVector operator^=(const BitVector &RHS) { + BitVector &operator^=(const BitVector &RHS) { assert(Size == RHS.Size && "Illegal operation!"); for (unsigned i = 0; i < NumBitWords(size()); ++i) Bits[i] ^= RHS.Bits[i]; return *this; } - + // Assignment operator. const BitVector &operator=(const BitVector &RHS) { if (this == &RHS) return *this; @@ -295,9 +328,9 @@ public: clear_unused_bits(); return *this; } - + // Grow the bitvector to have enough elements. - Capacity = NumBitWords(Size); + Capacity = RHSWords; BitWord *NewBits = new BitWord[Capacity]; std::copy(RHS.Bits, &RHS.Bits[RHSWords], NewBits); @@ -313,15 +346,26 @@ private: return (S + BITWORD_SIZE-1) / BITWORD_SIZE; } - // Clear the unused top bits in the high word. - void clear_unused_bits() { + // Set the unused bits in the high words. + void set_unused_bits(bool t = true) { + // Set high words first. + unsigned UsedWords = NumBitWords(Size); + if (Capacity > UsedWords) + init_words(&Bits[UsedWords], (Capacity-UsedWords), t); + + // Then set any stray high bits of the last used word. unsigned ExtraBits = Size % BITWORD_SIZE; if (ExtraBits) { - unsigned index = Size / BITWORD_SIZE; - Bits[index] &= ~(~0L << ExtraBits); + Bits[UsedWords-1] &= ~(~0L << ExtraBits); + Bits[UsedWords-1] |= (0 - (BitWord)t) << ExtraBits; } } + // Clear the unused bits in the high words. + void clear_unused_bits() { + set_unused_bits(false); + } + void grow(unsigned NewSize) { unsigned OldCapacity = Capacity; Capacity = NumBitWords(NewSize); @@ -334,11 +378,13 @@ private: // Destroy the old bits. delete[] Bits; Bits = NewBits; + + clear_unused_bits(); } void init_words(BitWord *B, unsigned NumWords, bool t) { memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); - } + } }; inline BitVector operator&(const BitVector &LHS, const BitVector &RHS) { @@ -358,6 +404,6 @@ inline BitVector operator^(const BitVector &LHS, const BitVector &RHS) { Result ^= RHS; return Result; } - + } // End llvm namespace #endif