From 8038a28b4ba6b4d3655a19ef3cc2ec4a577caac4 Mon Sep 17 00:00:00 2001
From: Zachary Turner <zturner@google.com>
Date: Fri, 5 May 2017 00:19:57 +0000
Subject: [PATCH] [ADT] A few minor improvements to BitVector

Fixes some spelling mistakes, uses a helper function, and
adds an additional test case.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@302208 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/BitVector.h      |  4 ++--
 include/llvm/Support/MathExtras.h | 12 ++++++++++++
 unittests/ADT/BitVectorTest.cpp   | 19 +++++++++++++++++++
 3 files changed, 33 insertions(+), 2 deletions(-)

diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h
index 5aa101591e6..01a3220d0a2 100644
--- a/include/llvm/ADT/BitVector.h
+++ b/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/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h
index 994456f9a68..7f07e8cc3a5 100644
--- a/include/llvm/Support/MathExtras.h
+++ b/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/unittests/ADT/BitVectorTest.cpp b/unittests/ADT/BitVectorTest.cpp
index ac7429cae36..1a87a561c5f 100644
--- a/unittests/ADT/BitVectorTest.cpp
+++ b/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) {
-- 
2.50.1