Add methods to find the next *unset* bits in a bit vector

[zturner]

Summary

It's nice to be able to find the next set bit, but often you have a clump of them and you want to find where they stop, i.e. by locating the next unset bit. This patch does that.

[amccarth]

Not really in the scope of this change, but, since BitVector has these STL-like methods, 'twould be nice if there were a BitVector::npos analogous to std::basic_string::npos rather than having all the users of the class have to hardcode the magic value or make vague checks like >= 0.

I realize that these methods are returning an int rather than a size_type like the corresponding methods on strings. Still, magic sentinel values are magic sentinel values, and the usage would be more consistent.

[• dberlin]

In D31802#721254, @amccarth wrote:

Not really in the scope of this change, but, since BitVector has these STL-like methods, 'twould be nice if there were a BitVector::npos analogous to std::basic_string::npos rather than having all the users of the class have to hardcode the magic value or make vague checks like >= 0.

I realize that these methods are returning an int rather than a size_type like the corresponding methods on strings. Still, magic sentinel values are magic sentinel values, and the usage would be more consistent.

Yes, it would be nice for bitvecrtor and sparsebitvector to be more stl like.

[• dberlin]

llvm/include/llvm/ADT/BitVector.h

206 ↗

(On Diff #94479)

Remind me what endianness we use ?
I would have expected it to simply be << some number of bits, then countleadingones.
It looks reversed, so i'm assuming i'm thinking the wrong way around :)

220 ↗

(On Diff #94479)

It would be nice to factor this out with the copy above the loop into a little helper function that takes and Bits.

[zturner]

Fixed an issue where find_first_unset() was returning BV.size() if all bits were set, and added a unit test for that case.

[zturner]

llvm/include/llvm/ADT/BitVector.h

206 ↗

(On Diff #94479)

Yea, we had this same confusion last time. Didn't you write this thing! :)

If you want the 0'th bit, it's the rightmost bit. So using an example, say Prev is 4, which means you've got something like XXXXXXXXXXXXYYYY where the Y's are the bits you don't care about, and the rightmost X is the bit you want to start searching from, leftwards. So, we set all the Y bits to 1 by producing the bit pattern 10000 and then subtracting 1, and then or that in. Then we count the number of trailing 1s.

The check below that looks if there is at least one zero-bit, and if there is it finds the last one by counting the number of trailing 1s. But the confusion doesn't stop there, because if your word size is, say, 64 bits, but your BitVector only represents 10 bits, then then the left most 54 bits are going to be 0 even though they are out of bounds. So we need the Result < size() check there as well.

[zturner]

Factored the return statement into a small helper function.

llvm/trunk/include/llvm/ADT/BitVector.h

public:
   /// 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_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;
+      }
+    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)
       return -1;
 
     unsigned WordPos = Prev / BITWORD_SIZE;
     unsigned BitPos = Prev % BITWORD_SIZE;
     BitWord Copy = Bits[WordPos];
     // Mask off previous bits.
     Copy &= ~0UL << BitPos;
 
     if (Copy != 0)
       return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
 
     // Check subsequent words.
     for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i)
       if (Bits[i] != 0)
         return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
     return -1;
   }
 
+  /// find_next_unset - Returns the index of the next usnet bit following the
+  /// "Prev" bit.  Returns -1 if all remaining bits are set.
+  int find_next_unset(unsigned Prev) const {
+    ++Prev;
+    if (Prev >= Size)
+      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;
+
+    if (Copy != ~0UL)
+      return next_unset_in_word(WordPos, Copy);
+
+    // Check subsequent words.
+    for (unsigned i = WordPos + 1; i < NumBitWords(size()); ++i)
+      if (Bits[i] != ~0UL)
+        return next_unset_in_word(i, Bits[i]);
+    return -1;
+  }
+
   /// clear - Clear all bits.
   void clear() {
     Size = 0;
   }
 
   /// resize - Grow or shrink the bitvector.
   void resize(unsigned N, bool t = false) {
     if (N > Capacity * BITWORD_SIZE) {
public:
 
   /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
   /// Don't resize.  This computes "*this &= Mask".
   void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
     applyMask<false, true>(Mask, MaskWords);
   }
 
 private:
+  int next_unset_in_word(int WordIndex, BitWord Word) const {
+    unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
+    return Result < size() ? Result : -1;
+  }
+
   unsigned NumBitWords(unsigned S) const {
     return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
   }
 
   // Set the unused bits in the high words.
   void set_unused_bits(bool t = true) {
     //  Set high words first.
     unsigned UsedWords = NumBitWords(Size);

llvm/trunk/include/llvm/ADT/SmallBitVector.h

if (isSmall()) {
       uintptr_t Bits = getSmallBits();
       if (Bits == 0)
         return -1;
       return countTrailingZeros(Bits);
     }
     return getPointer()->find_first();
   }
 
+  /// Returns the index of the first unset bit, -1 if all of the bits are set.
+  int find_first_unset() const {
+    if (isSmall()) {
+      if (count() == getSmallSize())
+        return -1;
+
+      uintptr_t Bits = getSmallBits();
+      return countTrailingOnes(Bits);
+    }
+    return getPointer()->find_first_unset();
+  }
+
   /// 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 {
     if (isSmall()) {
       uintptr_t Bits = getSmallBits();
       // Mask off previous bits.
       Bits &= ~uintptr_t(0) << (Prev + 1);
       if (Bits == 0 || Prev + 1 >= getSmallSize())
         return -1;
       return countTrailingZeros(Bits);
     }
     return getPointer()->find_next(Prev);
   }
 
+  /// Returns the index of the next unset bit following the "Prev" bit.
+  /// 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 = (1 << Prev) - 1;
+      Bits |= Mask;
+
+      if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
+        return -1;
+      return countTrailingOnes(Bits);
+    }
+    return getPointer()->find_next_unset(Prev);
+  }
+
   /// Clear all bits.
   void clear() {
     if (!isSmall())
       delete getPointer();
     switchToSmall(0, 0);
   }
 
   /// Grow or shrink the bitvector.

llvm/trunk/unittests/ADT/BitVectorTest.cpp

TYPED_TEST(BitVectorTest, TrivialOperation) {
   EXPECT_EQ(0U, Vec.count());
   EXPECT_EQ(0U, Vec.size());
   EXPECT_FALSE(Vec.any());
   EXPECT_TRUE(Vec.all());
   EXPECT_TRUE(Vec.none());
   EXPECT_TRUE(Vec.empty());
 }
 
+TYPED_TEST(BitVectorTest, FindOperations) {
+  // Test finding in an empty BitVector.
+  TypeParam A;
+  EXPECT_EQ(-1, A.find_first());
+  EXPECT_EQ(-1, A.find_first_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);
+  A.set(12);
+  A.set(13);
+  A.set(75);
+
+  EXPECT_EQ(12, A.find_first());
+  EXPECT_EQ(13, A.find_next(12));
+  EXPECT_EQ(75, A.find_next(13));
+  EXPECT_EQ(-1, A.find_next(75));
+
+  EXPECT_EQ(0, A.find_first_unset());
+  EXPECT_EQ(14, A.find_next_unset(11));
+  EXPECT_EQ(14, A.find_next_unset(12));
+  EXPECT_EQ(14, A.find_next_unset(13));
+  EXPECT_EQ(16, A.find_next_unset(15));
+  EXPECT_EQ(76, A.find_next_unset(74));
+  EXPECT_EQ(76, A.find_next_unset(75));
+  EXPECT_EQ(-1, A.find_next_unset(99));
+
+  A.set(0, 100);
+  EXPECT_EQ(100, A.count());
+  EXPECT_EQ(0, A.find_first());
+  EXPECT_EQ(-1, A.find_first_unset());
+
+  A.reset(0, 100);
+  EXPECT_EQ(0, A.count());
+  EXPECT_EQ(-1, A.find_first());
+  EXPECT_EQ(0, A.find_first_unset());
+}
+
 TYPED_TEST(BitVectorTest, CompoundAssignment) {
   TypeParam A;
   A.resize(10);
   A.set(4);
   A.set(7);
 
   TypeParam B;
   B.resize(50);