From a8e5dcb072b1f794883ae8125fb08c06db678d56 Mon Sep 17 00:00:00 2001 From: David Blaikie Date: Thu, 23 Apr 2020 11:46:38 -0700 Subject: [PATCH] Fix bug in SmallBitVector::find_next_unset Summary: find_next_unset was returning size() instead of -1 in small-mode, when no unset bits are found. Reviewed By: dblaikie Differential Revision: https://reviews.llvm.org/D77985 --- llvm/include/llvm/ADT/SmallBitVector.h | 6 +++--- llvm/unittests/ADT/BitVectorTest.cpp | 25 +++++++++++++++++++++++++ 2 files changed, 28 insertions(+), 3 deletions(-) diff --git a/llvm/include/llvm/ADT/SmallBitVector.h b/llvm/include/llvm/ADT/SmallBitVector.h index 14545e2..f570bac 100644 --- a/llvm/include/llvm/ADT/SmallBitVector.h +++ b/llvm/include/llvm/ADT/SmallBitVector.h @@ -287,11 +287,11 @@ public: /// Returns -1 if the next unset bit is not found. int find_next_unset(unsigned Prev) const { if (isSmall()) { - ++Prev; uintptr_t Bits = getSmallBits(); // Mask in previous bits. - uintptr_t Mask = (uintptr_t(1) << Prev) - 1; - Bits |= Mask; + Bits |= (uintptr_t(1) << (Prev + 1)) - 1; + // Mask in unused bits. + Bits |= ~uintptr_t(0) << getSmallSize(); if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize()) return -1; diff --git a/llvm/unittests/ADT/BitVectorTest.cpp b/llvm/unittests/ADT/BitVectorTest.cpp index efefd2b..0f15a47 100644 --- a/llvm/unittests/ADT/BitVectorTest.cpp +++ b/llvm/unittests/ADT/BitVectorTest.cpp @@ -297,6 +297,18 @@ TYPED_TEST(BitVectorTest, SimpleFindOpsSingleWord) { EXPECT_EQ(-1, A.find_last_unset()); A.resize(20); + ASSERT_TRUE(SmallBitVectorIsSmallMode(A)); + EXPECT_EQ(-1, A.find_first()); + EXPECT_EQ(-1, A.find_last()); + EXPECT_EQ(-1, A.find_next(5)); + EXPECT_EQ(-1, A.find_next(19)); + EXPECT_EQ(-1, A.find_prev(5)); + EXPECT_EQ(-1, A.find_prev(20)); + EXPECT_EQ(0, A.find_first_unset()); + EXPECT_EQ(19, A.find_last_unset()); + EXPECT_EQ(6, A.find_next_unset(5)); + EXPECT_EQ(-1, A.find_next_unset(19)); + A.set(3); A.set(4); A.set(16); @@ -319,6 +331,19 @@ TYPED_TEST(BitVectorTest, SimpleFindOpsSingleWord) { EXPECT_EQ(5, A.find_next_unset(4)); EXPECT_EQ(13, A.find_next_unset(12)); EXPECT_EQ(17, A.find_next_unset(15)); + + A.set(); + ASSERT_TRUE(SmallBitVectorIsSmallMode(A)); + EXPECT_EQ(0, A.find_first()); + EXPECT_EQ(19, A.find_last()); + EXPECT_EQ(6, A.find_next(5)); + EXPECT_EQ(-1, A.find_next(19)); + EXPECT_EQ(4, A.find_prev(5)); + EXPECT_EQ(19, A.find_prev(20)); + EXPECT_EQ(-1, A.find_first_unset()); + EXPECT_EQ(-1, A.find_last_unset()); + EXPECT_EQ(-1, A.find_next_unset(5)); + EXPECT_EQ(-1, A.find_next_unset(19)); } TEST(BitVectorTest, FindInRangeMultiWord) { -- 2.7.4