Add SparseBitVector::find_last()

[zturner]

Summary

I didn't add a find_prev because I don't need it, although I can without much additional effort. Otherwise, this is pretty self explanatory, just an analogue of find_first() but for searching in reverse.

[zturner]

(Note that I also added some tests for find_last, and while doing so noticed that there were no tests for find_first(), so I added those too.

[• dberlin]

llvm/include/llvm/ADT/SparseBitVector.h

141 ↗

(On Diff #84707)

Don't you really just want counttrailingzeros, and the index is bitword_size - count trailing zeros?

[zturner]

llvm/include/llvm/ADT/SparseBitVector.h

141 ↗

(On Diff #84707)

I made the same mistake at first. Because the LSB is the bit with the lowest "index", we have to use countLeadingZeros. i.e. 0b00000000000000000000000000000110 has bits 1 and 2 set. The value we want returned from the function is 2.

[• dberlin]

llvm/include/llvm/ADT/SparseBitVector.h

141 ↗

(On Diff #84707)

This assumes we store these little endian.
If we store them big endian, ...

Anyway, i think you are correct, and if not, the test will fail, so :)

llvm/trunk/include/llvm/ADT/SparseBitVector.h

public:
   /// find_first - Returns the index of the first set bit.
   int find_first() const {
     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
       if (Bits[i] != 0)
         return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
     llvm_unreachable("Illegal empty element");
   }
 
+  /// find_last - Returns the index of the last set bit.
+  int find_last() const {
+    for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; ++I) {
+      unsigned Idx = BITWORDS_PER_ELEMENT - I - 1;
+      if (Bits[Idx] != 0)
+        return Idx * BITWORD_SIZE + BITWORD_SIZE -
+               countLeadingZeros(Bits[Idx]) - 1;
+    }
+    llvm_unreachable("Illegal empty element");
+  }
+
   /// find_next - Returns the index of the next set bit starting from the
   /// "Curr" bit. Returns -1 if the next set bit is not found.
   int find_next(unsigned Curr) const {
     if (Curr >= BITS_PER_ELEMENT)
       return -1;
 
     unsigned WordPos = Curr / BITWORD_SIZE;
     unsigned BitPos = Curr % BITWORD_SIZE;
public:
   // Return the first set bit in the bitmap.  Return -1 if no bits are set.
   int find_first() const {
     if (Elements.empty())
       return -1;
     const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
     return (First.index() * ElementSize) + First.find_first();
   }
 
+  // Return the last set bit in the bitmap.  Return -1 if no bits are set.
+  int find_last() const {
+    if (Elements.empty())
+      return -1;
+    const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
+    return (Last.index() * ElementSize) + Last.find_last();
+  }
+
   // Return true if the SparseBitVector is empty
   bool empty() const {
     return Elements.empty();
   }
 
   unsigned count() const {
     unsigned BitCount = 0;
     for (ElementListConstIter Iter = Elements.begin();

llvm/trunk/unittests/ADT/SparseBitVectorTest.cpp

TEST(SparseBitVectorTest, SelfAssignment) {
   Vec.set(1);
   Other.clear();
   Other.set(59);
   Other.set(75);
   Vec.intersectWithComplement(Other, Other);
   EXPECT_TRUE(Vec.empty());
 }
 
+TEST(SparseBitVectorTest, Find) {
+  SparseBitVector<> Vec;
+  Vec.set(1);
+  EXPECT_EQ(1, Vec.find_first());
+  EXPECT_EQ(1, Vec.find_last());
+
+  Vec.set(2);
+  EXPECT_EQ(1, Vec.find_first());
+  EXPECT_EQ(2, Vec.find_last());
+
+  Vec.set(0);
+  Vec.set(3);
+  EXPECT_EQ(0, Vec.find_first());
+  EXPECT_EQ(3, Vec.find_last());
+
+  Vec.reset(1);
+  Vec.reset(0);
+  Vec.reset(3);
+  EXPECT_EQ(2, Vec.find_first());
+  EXPECT_EQ(2, Vec.find_last());
+
+  // Set some large bits to ensure we are pulling bits from more than just a
+  // single bitword.
+  Vec.set(500);
+  Vec.set(2000);
+  Vec.set(3000);
+  Vec.set(4000);
+  Vec.reset(2);
+  EXPECT_EQ(500, Vec.find_first());
+  EXPECT_EQ(4000, Vec.find_last());
+
+  Vec.reset(500);
+  Vec.reset(3000);
+  Vec.reset(4000);
+  EXPECT_EQ(2000, Vec.find_first());
+  EXPECT_EQ(2000, Vec.find_last());
+
+  Vec.clear();
+}
 }