diff options
| -rw-r--r-- | llvm/include/llvm/ADT/BitVector.h | 4 | ||||
| -rw-r--r-- | llvm/include/llvm/Support/MathExtras.h | 12 | ||||
| -rw-r--r-- | llvm/unittests/ADT/BitVectorTest.cpp | 19 |
3 files changed, 33 insertions, 2 deletions
diff --git a/llvm/include/llvm/ADT/BitVector.h b/llvm/include/llvm/ADT/BitVector.h index 5aa101591e6..01a3220d0a2 100644 --- a/llvm/include/llvm/ADT/BitVector.h +++ b/llvm/include/llvm/ADT/BitVector.h @@ -217,7 +217,7 @@ public: unsigned BitPos = Prev % BITWORD_SIZE; BitWord Copy = Bits[WordPos]; // Mask off previous bits. - Copy &= ~0UL << BitPos; + Copy &= maskTrailingZeros<BitWord>(BitPos); if (Copy != 0) return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); @@ -229,7 +229,7 @@ public: return -1; } - /// find_next_unset - Returns the index of the next usnet bit following the + /// 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; diff --git a/llvm/include/llvm/Support/MathExtras.h b/llvm/include/llvm/Support/MathExtras.h index 994456f9a68..7f07e8cc3a5 100644 --- a/llvm/include/llvm/Support/MathExtras.h +++ b/llvm/include/llvm/Support/MathExtras.h @@ -214,6 +214,18 @@ template <typename T> T maskLeadingOnes(unsigned N) { return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N); } +/// \brief Create a bitmask with the N right-most bits set to 0, and all other +/// bits set to 1. Only unsigned types are allowed. +template <typename T> T maskTrailingZeros(unsigned N) { + return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N); +} + +/// \brief Create a bitmask with the N left-most bits set to 0, and all other +/// bits set to 1. Only unsigned types are allowed. +template <typename T> T maskLeadingZeros(unsigned N) { + return maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N); +} + /// \brief Get the index of the last set bit starting from the least /// significant bit. /// diff --git a/llvm/unittests/ADT/BitVectorTest.cpp b/llvm/unittests/ADT/BitVectorTest.cpp index ac7429cae36..1a87a561c5f 100644 --- a/llvm/unittests/ADT/BitVectorTest.cpp +++ b/llvm/unittests/ADT/BitVectorTest.cpp @@ -227,6 +227,25 @@ TYPED_TEST(BitVectorTest, FindOperations) { EXPECT_EQ(-1, A.find_last()); EXPECT_EQ(0, A.find_first_unset()); EXPECT_EQ(99, A.find_last_unset()); + + // Also test with a vector that is small enough to fit in 1 word. + A.resize(20); + A.set(3); + A.set(4); + A.set(16); + EXPECT_EQ(16, A.find_last()); + EXPECT_EQ(3, A.find_first()); + EXPECT_EQ(3, A.find_next(1)); + EXPECT_EQ(4, A.find_next(3)); + EXPECT_EQ(16, A.find_next(4)); + EXPECT_EQ(-1, A.find_next(16)); + + EXPECT_EQ(0, A.find_first_unset()); + EXPECT_EQ(19, A.find_last_unset()); + EXPECT_EQ(5, A.find_next_unset(3)); + EXPECT_EQ(5, A.find_next_unset(4)); + EXPECT_EQ(13, A.find_next_unset(12)); + EXPECT_EQ(17, A.find_next_unset(15)); } TYPED_TEST(BitVectorTest, CompoundAssignment) { |
