[ADT] Add BitVector::find_prev

[zturner]

Summary

This almost completes the matrix of all possible find operations.

*EXISTING*
----------
find_first
find_first_unset
find_next
find_next_unset
find_last
find_last_unset

*NEW*
----
find_prev

*STILL MISSING*
---------------
find_prev_unset

[chandlerc]

llvm/include/llvm/ADT/BitVector.h

220

Unrelated change?

232

Feel free to just commit typo fixes etc.

256

I'd really like to move the doxygen comments away from repeating the name. Maybe in a follow-up? Definitely not in this patch.

257–258

I find all the wording really confusing here.

"the next bit set *preceding* the Next bit" huh?

I think the argument would make much more sense named Pos or Index or something. Then you can talk about finding the *previous* bit set to match the name find_prev?

llvm/unittests/ADT/BitVectorTest.cpp

236–258

Feel free to land everything but find_prev right away with a separate patch?

[zturner]

Removed all unrelated changes and committed them separately.

[zturner]

Re-word the comment and parameter name to be more clear.

[chandlerc]

LGTM, nice!

llvm/include/llvm/ADT/BitVector.h

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;
+    Copy &= maskTrailingZeros<BitWord>(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
+  /// 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)
       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;
   }
 
+  /// find_prev - Returns the index of the next set bit *preceding* the
+  /// \p Next bit.  Returns -1 if all previous bits are unset.
+  int find_prev(unsigned Next) {
+    if (Next == 0)
+      return -1;
+
+    --Next;
+
+    unsigned WordPos = Next / BITWORD_SIZE;
+    unsigned BitPos = Next % BITWORD_SIZE;
+    BitWord Copy = Bits[WordPos];
+    // Mask off next bits.
+    Copy &= maskTrailingOnes<BitWord>(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;
+  }
+
   /// clear - Clear all bits.
   void clear() {
     Size = 0;
   }
 
   /// resize - Grow or shrink the bitvector.
   void resize(unsigned N, bool t = false) {
     if (N > getBitCapacity()) {

llvm/include/llvm/ADT/SmallBitVector.h

if (isSmall()) {
 
       if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
         return -1;
       return countTrailingOnes(Bits);
     }
     return getPointer()->find_next_unset(Prev);
   }
 
+  /// find_prev - Returns the index of the next set bit *preceding* the
+  /// \p Next bit.  Returns -1 if all previous bits are unset.
+  int find_prev(unsigned Next) const {
+    if (isSmall()) {
+      if (Next == 0)
+        return -1;
+
+      --Next;
+      uintptr_t Bits = getSmallBits();
+      Bits &= maskTrailingOnes<uintptr_t>(Next + 1);
+      if (Bits == 0)
+        return -1;
+
+      return NumBaseBits - countLeadingZeros(Bits) - 1;
+    }
+    return getPointer()->find_prev(Next);
+  }
+
   /// Clear all bits.
   void clear() {
     if (!isSmall())
       delete getPointer();
     switchToSmall(0, 0);
   }
 
   /// Grow or shrink the bitvector.

llvm/include/llvm/Support/MathExtras.h

 }
 
 /// \brief Create a bitmask with the N left-most bits set to 1, and all other
 /// bits set to 0.  Only unsigned types are allowed.
 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.
 ///
 /// Only unsigned integral types are allowed.
 ///
 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
 ///   valid arguments.
 template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {

llvm/unittests/ADT/BitVectorTest.cpp

TYPED_TEST(BitVectorTest, FindOperations) {
   A.set(75);
 
   EXPECT_EQ(75, A.find_last());
   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(-1, A.find_prev(12));
+  EXPECT_EQ(12, A.find_prev(13));
+  EXPECT_EQ(13, A.find_prev(75));
+  EXPECT_EQ(75, A.find_prev(90));
+
   EXPECT_EQ(0, A.find_first_unset());
   EXPECT_EQ(99, A.find_last_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(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());
 
   A.reset(0, 100);
   EXPECT_EQ(0U, A.count());
   EXPECT_EQ(-1, A.find_first());
   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(-1, A.find_prev(3));
+  EXPECT_EQ(3, A.find_prev(4));
+  EXPECT_EQ(4, A.find_prev(16));
+  EXPECT_EQ(16, A.find_prev(18));
+
+  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) {
   TypeParam A;
   A.resize(10);
   A.set(4);
   A.set(7);