Index: llvm/trunk/include/llvm/ADT/BitVector.h =================================================================== --- llvm/trunk/include/llvm/ADT/BitVector.h +++ llvm/trunk/include/llvm/ADT/BitVector.h @@ -203,138 +203,164 @@ return !any(); } - /// find_first - Returns the index of the first set bit, -1 if none - /// of the bits are set. - int find_first() const { - for (unsigned i = 0; i < NumBitWords(size()); ++i) - if (Bits[i] != 0) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); - return -1; - } - - /// find_last - Returns the index of the last set bit, -1 if none of the bits - /// are set. - int find_last() const { - if (Size == 0) + /// find_first_in - Returns the index of the first set bit in the range + /// [Begin, End). Returns -1 if all bits in the range are unset. + int find_first_in(unsigned Begin, unsigned End) const { + assert(Begin <= End && End <= Size); + if (Begin == End) return -1; - unsigned N = NumBitWords(size()); - assert(N > 0); + unsigned FirstWord = Begin / BITWORD_SIZE; + unsigned LastWord = (End - 1) / BITWORD_SIZE; - unsigned i = N - 1; - while (i > 0 && Bits[i] == BitWord(0)) - --i; + // Check subsequent words. + for (unsigned i = FirstWord; i <= LastWord; ++i) { + BitWord Copy = Bits[i]; - return int((i + 1) * BITWORD_SIZE - countLeadingZeros(Bits[i])) - 1; - } + if (i == FirstWord) { + unsigned FirstBit = Begin % BITWORD_SIZE; + Copy &= maskTrailingZeros(FirstBit); + } - /// find_first_unset - Returns the index of the first unset bit, -1 if all - /// of the bits are set. - int find_first_unset() const { - for (unsigned i = 0; i < NumBitWords(size()); ++i) - if (Bits[i] != ~0UL) { - unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Bits[i]); - return Result < size() ? Result : -1; + if (i == LastWord) { + unsigned LastBit = (End - 1) % BITWORD_SIZE; + Copy &= maskTrailingOnes(LastBit + 1); } + if (Copy != 0) + return i * BITWORD_SIZE + countTrailingZeros(Copy); + } return -1; } - /// find_last_unset - Returns the index of the last unset bit, -1 if all of - /// the bits are set. - int find_last_unset() const { - if (Size == 0) + /// find_last_in - Returns the index of the last set bit in the range + /// [Begin, End). Returns -1 if all bits in the range are unset. + int find_last_in(unsigned Begin, unsigned End) const { + assert(Begin <= End && End <= Size); + if (Begin == End) return -1; - const unsigned N = NumBitWords(size()); - assert(N > 0); + unsigned LastWord = (End - 1) / BITWORD_SIZE; + unsigned FirstWord = Begin / BITWORD_SIZE; - unsigned i = N - 1; - BitWord W = Bits[i]; + for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) { + unsigned CurrentWord = i - 1; - // The last word in the BitVector has some unused bits, so we need to set - // them all to 1 first. Set them all to 1 so they don't get treated as - // valid unset bits. - unsigned UnusedCount = BITWORD_SIZE - size() % BITWORD_SIZE; - W |= maskLeadingOnes(UnusedCount); + BitWord Copy = Bits[CurrentWord]; + if (CurrentWord == LastWord) { + unsigned LastBit = (End - 1) % BITWORD_SIZE; + Copy &= maskTrailingOnes(LastBit + 1); + } - while (W == ~BitWord(0) && --i > 0) - W = Bits[i]; + if (CurrentWord == FirstWord) { + unsigned FirstBit = Begin % BITWORD_SIZE; + Copy &= maskTrailingZeros(FirstBit); + } - return int((i + 1) * BITWORD_SIZE - countLeadingOnes(W)) - 1; + if (Copy != 0) + return (CurrentWord + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1; + } + + return -1; } - /// find_next - Returns the index of the next set bit following the - /// "Prev" bit. Returns -1 if the next set bit is not found. - int find_next(unsigned Prev) const { - ++Prev; - if (Prev >= Size) + /// find_first_unset_in - Returns the index of the first unset bit in the + /// range [Begin, End). Returns -1 if all bits in the range are set. + int find_first_unset_in(unsigned Begin, unsigned End) const { + assert(Begin <= End && End <= Size); + if (Begin == End) return -1; - unsigned WordPos = Prev / BITWORD_SIZE; - unsigned BitPos = Prev % BITWORD_SIZE; - BitWord Copy = Bits[WordPos]; - // Mask off previous bits. - Copy &= maskTrailingZeros(BitPos); - - if (Copy != 0) - return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); + unsigned FirstWord = Begin / BITWORD_SIZE; + unsigned LastWord = (End - 1) / BITWORD_SIZE; // Check subsequent words. - for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i) - if (Bits[i] != 0) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); + for (unsigned i = FirstWord; i <= LastWord; ++i) { + BitWord Copy = Bits[i]; + + if (i == FirstWord) { + unsigned FirstBit = Begin % BITWORD_SIZE; + Copy |= maskTrailingOnes(FirstBit); + } + + if (i == LastWord) { + unsigned LastBit = (End - 1) % BITWORD_SIZE; + Copy |= maskTrailingZeros(LastBit + 1); + } + if (Copy != ~0UL) { + unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Copy); + return Result < size() ? Result : -1; + } + } return -1; } - /// find_next_unset - Returns the index of the next unset bit following the - /// "Prev" bit. Returns -1 if all remaining bits are set. - int find_next_unset(unsigned Prev) const { - ++Prev; - if (Prev >= Size) + /// find_last_unset_in - Returns the index of the last unset bit in the + /// range [Begin, End). Returns -1 if all bits in the range are set. + int find_last_unset_in(unsigned Begin, unsigned End) const { + assert(Begin <= End && End <= Size); + if (Begin == End) return -1; - unsigned WordPos = Prev / BITWORD_SIZE; - unsigned BitPos = Prev % BITWORD_SIZE; - BitWord Copy = Bits[WordPos]; - // Mask in previous bits. - BitWord Mask = (1 << BitPos) - 1; - Copy |= Mask; + unsigned LastWord = (End - 1) / BITWORD_SIZE; + unsigned FirstWord = Begin / BITWORD_SIZE; - if (Copy != ~0UL) - return next_unset_in_word(WordPos, Copy); + for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) { + unsigned CurrentWord = i - 1; - // Check subsequent words. - for (unsigned i = WordPos + 1; i < NumBitWords(size()); ++i) - if (Bits[i] != ~0UL) - return next_unset_in_word(i, Bits[i]); + BitWord Copy = Bits[CurrentWord]; + if (CurrentWord == LastWord) { + unsigned LastBit = (End - 1) % BITWORD_SIZE; + Copy |= maskTrailingZeros(LastBit + 1); + } + + if (CurrentWord == FirstWord) { + unsigned FirstBit = Begin % BITWORD_SIZE; + Copy |= maskTrailingOnes(FirstBit); + } + + if (Copy != ~0UL) { + unsigned Result = + (CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1; + return Result < Size ? Result : -1; + } + } return -1; } + /// find_first - Returns the index of the first set bit, -1 if none + /// of the bits are set. + int find_first() const { return find_first_in(0, Size); } + + /// find_last - Returns the index of the last set bit, -1 if none of the bits + /// are set. + int find_last() const { return find_last_in(0, Size); } + + /// find_next - Returns the index of the next set bit following the + /// "Prev" bit. Returns -1 if the next set bit is not found. + int find_next(unsigned Prev) const { return find_first_in(Prev + 1, Size); } + /// find_prev - Returns the index of the first set bit that precedes the /// the bit at \p PriorTo. Returns -1 if all previous bits are unset. - int find_prev(unsigned PriorTo) const { - if (PriorTo == 0) - return -1; + int find_prev(unsigned PriorTo) const { return find_last_in(0, PriorTo); } - --PriorTo; + /// find_first_unset - Returns the index of the first unset bit, -1 if all + /// of the bits are set. + int find_first_unset() const { return find_first_unset_in(0, Size); } - unsigned WordPos = PriorTo / BITWORD_SIZE; - unsigned BitPos = PriorTo % BITWORD_SIZE; - BitWord Copy = Bits[WordPos]; - // Mask off next bits. - Copy &= maskTrailingOnes(BitPos + 1); - - if (Copy != 0) - return (WordPos + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1; - - // Check previous words. - for (unsigned i = 1; i <= WordPos; ++i) { - unsigned Index = WordPos - i; - if (Bits[Index] == 0) - continue; - return (Index + 1) * BITWORD_SIZE - countLeadingZeros(Bits[Index]) - 1; - } - return -1; + /// find_next_unset - Returns the index of the next unset bit following the + /// "Prev" bit. Returns -1 if all remaining bits are set. + int find_next_unset(unsigned Prev) const { + return find_first_unset_in(Prev + 1, Size); + } + + /// find_last_unset - Returns the index of the last unset bit, -1 if all of + /// the bits are set. + int find_last_unset() const { return find_last_unset_in(0, Size); } + + /// find_prev_unset - Returns the index of the first unset bit that precedes + /// the bit at \p PriorTo. Returns -1 if all previous bits are set. + int find_prev_unset(unsigned PriorTo) { + return find_last_unset_in(0, PriorTo); } /// clear - Removes all bits from the bitvector. Does not change capacity. Index: llvm/trunk/unittests/ADT/BitVectorTest.cpp =================================================================== --- llvm/trunk/unittests/ADT/BitVectorTest.cpp +++ llvm/trunk/unittests/ADT/BitVectorTest.cpp @@ -182,15 +182,13 @@ EXPECT_TRUE(Vec.empty()); } -TYPED_TEST(BitVectorTest, FindOperations) { +TYPED_TEST(BitVectorTest, SimpleFindOps) { // Test finding in an empty BitVector. TypeParam A; EXPECT_EQ(-1, A.find_first()); EXPECT_EQ(-1, A.find_last()); EXPECT_EQ(-1, A.find_first_unset()); EXPECT_EQ(-1, A.find_last_unset()); - EXPECT_EQ(-1, A.find_next(0)); - EXPECT_EQ(-1, A.find_next_unset(0)); // Test finding next set and unset bits in a BitVector with multiple words A.resize(100); @@ -222,9 +220,10 @@ A.set(0, 100); EXPECT_EQ(100U, A.count()); EXPECT_EQ(0, A.find_first()); - EXPECT_EQ(99, A.find_last()); EXPECT_EQ(-1, A.find_first_unset()); EXPECT_EQ(-1, A.find_last_unset()); + EXPECT_EQ(99, A.find_last()); + EXPECT_EQ(99, A.find_next(98)); A.reset(0, 100); EXPECT_EQ(0U, A.count()); @@ -232,6 +231,7 @@ EXPECT_EQ(-1, A.find_last()); EXPECT_EQ(0, A.find_first_unset()); EXPECT_EQ(99, A.find_last_unset()); + EXPECT_EQ(99, A.find_next_unset(98)); // Also test with a vector that is small enough to fit in 1 word. A.resize(20); @@ -258,6 +258,153 @@ EXPECT_EQ(17, A.find_next_unset(15)); } +TEST(BitVectorTest, FindInRangeMultiWord) { + BitVector Vec; + + Vec.resize(200); + Vec.set(3, 7); + Vec.set(24, 35); + Vec.set(50, 70); + Vec.set(150); + Vec.set(152); + Vec.set(154); + + // find first + EXPECT_EQ(-1, Vec.find_first_in(0, 0)); + EXPECT_EQ(-1, Vec.find_first_in(24, 24)); + EXPECT_EQ(-1, Vec.find_first_in(7, 24)); + + EXPECT_EQ(3, Vec.find_first_in(0, 10)); + EXPECT_EQ(4, Vec.find_first_in(4, 10)); + EXPECT_EQ(150, Vec.find_first_in(100, 200)); + EXPECT_EQ(152, Vec.find_first_in(151, 200)); + EXPECT_EQ(154, Vec.find_first_in(153, 200)); + + EXPECT_EQ(-1, Vec.find_first_in(155, 200)); + Vec.set(199); + EXPECT_EQ(199, Vec.find_first_in(199, 200)); + Vec.reset(199); + + // find last + EXPECT_EQ(-1, Vec.find_last_in(0, 0)); + EXPECT_EQ(-1, Vec.find_last_in(24, 24)); + EXPECT_EQ(-1, Vec.find_last_in(7, 24)); + + EXPECT_EQ(6, Vec.find_last_in(0, 10)); + EXPECT_EQ(5, Vec.find_last_in(0, 6)); + EXPECT_EQ(154, Vec.find_last_in(100, 155)); + EXPECT_EQ(152, Vec.find_last_in(100, 154)); + EXPECT_EQ(150, Vec.find_last_in(100, 152)); + EXPECT_EQ(-1, Vec.find_last_in(100, 150)); + Vec.set(199); + EXPECT_EQ(199, Vec.find_last_in(199, 200)); + Vec.reset(199); + + // find first unset + EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0)); + EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23)); + EXPECT_EQ(-1, Vec.find_first_unset_in(24, 35)); + + EXPECT_EQ(0, Vec.find_first_unset_in(0, 10)); + EXPECT_EQ(1, Vec.find_first_unset_in(1, 10)); + EXPECT_EQ(7, Vec.find_first_unset_in(5, 25)); + EXPECT_EQ(151, Vec.find_first_unset_in(150, 200)); + EXPECT_EQ(151, Vec.find_first_unset_in(151, 200)); + EXPECT_EQ(153, Vec.find_first_unset_in(152, 200)); + EXPECT_EQ(153, Vec.find_first_unset_in(153, 200)); + EXPECT_EQ(155, Vec.find_first_unset_in(154, 200)); + EXPECT_EQ(155, Vec.find_first_unset_in(155, 200)); + EXPECT_EQ(199, Vec.find_first_unset_in(199, 200)); + + // find last unset + EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0)); + EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23)); + EXPECT_EQ(-1, Vec.find_last_unset_in(24, 35)); + + EXPECT_EQ(9, Vec.find_last_unset_in(0, 10)); + EXPECT_EQ(8, Vec.find_last_unset_in(0, 9)); + EXPECT_EQ(2, Vec.find_last_unset_in(0, 7)); + EXPECT_EQ(149, Vec.find_last_unset_in(100, 151)); + EXPECT_EQ(151, Vec.find_last_unset_in(100, 152)); + EXPECT_EQ(151, Vec.find_last_unset_in(100, 153)); + EXPECT_EQ(153, Vec.find_last_unset_in(100, 154)); + EXPECT_EQ(153, Vec.find_last_unset_in(100, 155)); + EXPECT_EQ(155, Vec.find_last_unset_in(100, 156)); + EXPECT_EQ(199, Vec.find_last_unset_in(199, 200)); +} + +TEST(BitVectorTest, FindInRangeSingleWord) { + // When the bit vector contains only a single word, this is slightly different + // than when the bit vector contains multiple words, because masks are applied + // to the front and back of the same word. So make sure this works. + BitVector Vec; + + Vec.resize(25); + Vec.set(2, 4); + Vec.set(6, 9); + Vec.set(12, 15); + Vec.set(19); + Vec.set(21); + Vec.set(23); + + // find first + EXPECT_EQ(-1, Vec.find_first_in(0, 0)); + EXPECT_EQ(-1, Vec.find_first_in(24, 24)); + EXPECT_EQ(-1, Vec.find_first_in(9, 12)); + + EXPECT_EQ(2, Vec.find_first_in(0, 10)); + EXPECT_EQ(6, Vec.find_first_in(4, 10)); + EXPECT_EQ(19, Vec.find_first_in(18, 25)); + EXPECT_EQ(21, Vec.find_first_in(20, 25)); + EXPECT_EQ(23, Vec.find_first_in(22, 25)); + EXPECT_EQ(-1, Vec.find_first_in(24, 25)); + + // find last + EXPECT_EQ(-1, Vec.find_last_in(0, 0)); + EXPECT_EQ(-1, Vec.find_last_in(24, 24)); + EXPECT_EQ(-1, Vec.find_last_in(9, 12)); + + EXPECT_EQ(8, Vec.find_last_in(0, 10)); + EXPECT_EQ(3, Vec.find_last_in(0, 6)); + EXPECT_EQ(23, Vec.find_last_in(18, 25)); + EXPECT_EQ(21, Vec.find_last_in(18, 23)); + EXPECT_EQ(19, Vec.find_last_in(18, 21)); + EXPECT_EQ(-1, Vec.find_last_in(18, 19)); + + // find first unset + EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0)); + EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23)); + EXPECT_EQ(-1, Vec.find_first_unset_in(6, 9)); + + EXPECT_EQ(0, Vec.find_first_unset_in(0, 6)); + EXPECT_EQ(1, Vec.find_first_unset_in(1, 6)); + EXPECT_EQ(9, Vec.find_first_unset_in(7, 13)); + EXPECT_EQ(18, Vec.find_first_unset_in(18, 25)); + EXPECT_EQ(20, Vec.find_first_unset_in(19, 25)); + EXPECT_EQ(20, Vec.find_first_unset_in(20, 25)); + EXPECT_EQ(22, Vec.find_first_unset_in(21, 25)); + EXPECT_EQ(22, Vec.find_first_unset_in(22, 25)); + EXPECT_EQ(24, Vec.find_first_unset_in(23, 25)); + EXPECT_EQ(24, Vec.find_first_unset_in(24, 25)); + + // find last unset + EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0)); + EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23)); + EXPECT_EQ(-1, Vec.find_last_unset_in(6, 9)); + + EXPECT_EQ(5, Vec.find_last_unset_in(0, 6)); + EXPECT_EQ(4, Vec.find_last_unset_in(0, 5)); + EXPECT_EQ(1, Vec.find_last_unset_in(0, 4)); + EXPECT_EQ(11, Vec.find_last_unset_in(7, 13)); + EXPECT_EQ(24, Vec.find_last_unset_in(18, 25)); + EXPECT_EQ(22, Vec.find_last_unset_in(18, 24)); + EXPECT_EQ(22, Vec.find_last_unset_in(18, 23)); + EXPECT_EQ(20, Vec.find_last_unset_in(18, 22)); + EXPECT_EQ(20, Vec.find_last_unset_in(18, 21)); + EXPECT_EQ(18, Vec.find_last_unset_in(18, 20)); + EXPECT_EQ(18, Vec.find_last_unset_in(18, 19)); +} + TYPED_TEST(BitVectorTest, CompoundAssignment) { TypeParam A; A.resize(10);