Introduce BitSet: A BitVector based class behaving like std::set/DenseSet

[dblaikie]

Test cases?
Got a usage in mind?

[MatzeB]

Implement insert() and erase() in SmallBitVector as well and add tests.

[MatzeB]

In D18578#386549, @dblaikie wrote:

Test cases?
Got a usage in mind?

The concrete usage I have in mind is using a BitVector for Set type parameter of a SetVector. This is in the context of http://reviews.llvm.org/D18427.

And if you think about it: Even though the class is called a BitVector most of the time you really use it more like a set where you insert and remove elements from and not like a vector there is no BitVector::push_back() or iterators after all. So having operations compatible with std::set and DenseSet makes sense.

[MatzeB]

Also added the count(X) method. count(X) is another operand from std::set/DenseSet and was required to get all of SetVector<> working.

[MatzeB]

New revision introducing a new proxy class acting like a set but backed by a BitVector.

Also comes with more extensive unittests for set classes.

[dblaikie]

This seems to have strange behavior - returning the size/empty status of
the BitVector for the BitSets operations is probably wrong, no? (the
BitVector's length is the length of the field, not the number of set (1)
bits in it)

[MatzeB]

In D18578#400148, @dblaikie wrote:

This seems to have strange behavior - returning the size/empty status of
the BitVector for the BitSets operations is probably wrong, no? (the
BitVector's length is the length of the field, not the number of set (1)
bits in it)

BitSet::size() should return the number of elements in the set which corresponds to the number of set bits in the bitvector which should be BitVector::count().

empty() checks BitSet::size() against 0 which should be equivalent to BitVector::count() == 0.

[MatzeB]

Address review comments.

[MatzeB]

Address review comments.

[mehdi_amini]

It is nice to have a separate BitSet instead of adding the API to the BitVector, but at the same time I wonder about some inefficiencies due the wrapping here? See inline for instance.

include/llvm/ADT/BitSet.h

58

This is requerying the Vector uselessly here (or post-increment is not good anyway but still).

65

Could the iterator be lazy and not do anything on creation? (that would solve the point above by the way)

112

Again that's 3 queries to the vector instead of one, I wonder if the compiler CSE perfectly the generated code.

[MatzeB]

Address review comments.

include/llvm/ADT/BitSet.h

112

The new version of the code should avoid the advance() calls in the iterator. This is just the way the STL set APIs work, unfortunately this is will always be an extra load and pair<> creation even if most users don't need the return value. You can only hope the compiler inlines properly and throws the return value and extra queries away.

[MatzeB]

ping

[MatzeB]

Abandoning for lack of progress and use case. The motivating pass simply uses a combination of BitVector+Set instead of a SetVector now.

include/llvm/ADT/BitSet.h

+//===- llvm/ADT/BitSet.h - Bit sets -----------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file.
+/// This file implements the BitSet class, a set for unsigned numbers backed
+/// by a BitVector.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_BITSET_H
+#define LLVM_ADT_BITSET_H
+
+namespace llvm {
+
+/// A set of unsigned numbers smaller than a previously given maximum. The set
+/// internally uses a BitVector for storage.
+template<typename BitVectorT>
+class BitSetBase {
+public:
+  typedef unsigned key_type;
+  typedef unsigned value_type;
+  typedef typename BitVectorT::size_type size_type;
+
+  class const_iterator
+  {
+  public:
+    const_iterator(const const_iterator&) = default;
+
+    const_iterator &operator=(const const_iterator &I) = default;
+
+    unsigned operator*() const { return E; }
+
+    bool operator==(const const_iterator &RHS) const {
+      return E == RHS.E && Vector == RHS.Vector;
+    }
+
+    bool operator !=(const const_iterator &RHS) const {
+      return !(*this == RHS);
+    }
+
+    const_iterator &operator++() {
+      ++E;
+      advance();
+      return *this;
+    }
+
+    const_iterator operator++(int) {
+      const_iterator Prev(*this);
+      ++E;
+      advance();
+      return Prev;
+    }
+
+  private:
+    friend class BitSetBase<BitVectorT>;
+    /// Construct new iterator pointing to element \p E of \p Vector. E must
+    /// point to a set bit or be equal to the size of the vector.
+    const_iterator(const BitVectorT *Vector, unsigned E)
+      : Vector(Vector), E(E) {
+    }
+    const_iterator(const BitVectorT *Vector)
+      : Vector(Vector), E(0) {
+      advance();
+    }
+
+    void advance() {
+      int next = Vector->find_next_at(E);
+      if (next == -1)
+        E = Vector->size();
+      else
+        E = (unsigned)next;
+    }
+
+    const BitVectorT *Vector;
+    unsigned E;
+  };
+  typedef const_iterator iterator;
+
+  /// Initializes an empty set for values smaller than \p Max.
+  BitSetBase(unsigned Max = 0) : Vector(Max) {}
+
+  /// Returns true if the set contains no elements.
+  bool empty() const { return Vector.none(); }
+
+  /// Returns the number of elements in the set.
+  size_type size() const { return Vector.count(); }
+
+  /// Change the size of the underlying bitvector so the set can hold elements
+  /// smaller than \p Max. Removes elements bigger than \p Max from the set.
+  void reserve(unsigned Max) { Vector.resize(Max); }
+
+  /// Removes all elements from the set.
+  void clear() { Vector.reset(); }
+
+  /// Returns iterator to first element in set or end() if set is empty.
+  const_iterator begin() const {
+    return const_iterator(&Vector);
+  }
+
+  /// Returns iterator pointing past the last element of the set.
+  const_iterator end() const {
+    return const_iterator(&Vector, Vector.size());
+  }
+
+  /// Insert element \p Idx into the set. \p Idx must be smaller than the number
+  /// used in the last reserve() or constructor call.
+  std::pair<iterator, bool> insert(unsigned Idx) {
+    bool Res = !Vector[Idx];
+    Vector[Idx] = true;
+    return std::make_pair(iterator(&Vector, Idx), Res);
+  }
+
+  /// Remove element \p Idx from the set. \p Idx must be smaller than the number
+  /// used in the last reserve() or constructor call. Does nothing if \p Idx is
+  /// not contained in the set.
+  size_type erase(unsigned Idx) {
+    size_type Res = Vector[Idx];
+    Vector[Idx] = false;
+    return Res;
+  }
+
+  /// Remove element pointed to by iterator \p I. Returns iterator to the
+  /// element following the removed element or end().
+  iterator erase(iterator I) {
+    iterator Res = I;
+    Vector[*I] = false;
+    return ++Res;
+  }
+
+  /// Returns 1 if \p Idx is contained in the set, 0 otherwise. \p Idx must be
+  /// smaller than the number used in the last reserve() or constructor call.
+  size_type count(unsigned Idx) const {
+    return Vector.test(Idx);
+  }
+
+private:
+  BitVectorT Vector;
+};
+
+class BitVector;
+typedef BitSetBase<BitVector> BitSet;
+
+class SmallBitVector;
+typedef BitSetBase<SmallBitVector> SmallBitSet;
+
+} // End llvm namespace
+
+#endif

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_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)
+  /// Returns the index of the next set bit at bit \p Pos or following.
+  /// Returns -1 if the next set bit is not found.
+  int find_next_at(unsigned Pos) const {
+    if (Pos >= Size)
       return -1;
 
-    unsigned WordPos = Prev / BITWORD_SIZE;
-    unsigned BitPos = Prev % BITWORD_SIZE;
+    unsigned WordPos = Pos / BITWORD_SIZE;
+    unsigned BitPos = Pos % 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;
   }
 
+  /// 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 {
+    return find_next_at(Prev + 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) {

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 next set bit following the "Prev" bit.
+  /// Returns the index of the next set bit at bit \p Pos or following.
   /// Returns -1 if the next set bit is not found.
-  int find_next(unsigned Prev) const {
+  int find_next_at(unsigned Pos) const {
     if (isSmall()) {
       uintptr_t Bits = getSmallBits();
       // Mask off previous bits.
-      Bits &= ~uintptr_t(0) << (Prev + 1);
-      if (Bits == 0 || Prev + 1 >= getSmallSize())
+      Bits &= ~uintptr_t(0) << Pos;
+      if (Bits == 0 || Pos >= getSmallSize())
         return -1;
       return countTrailingZeros(Bits);
     }
-    return getPointer()->find_next(Prev);
+    return getPointer()->find_next_at(Pos);
+  }
+
+  /// 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 {
+    return find_next_at(Prev + 1);
   }
 
   /// Clear all bits.
   void clear() {
     if (!isSmall())
       delete getPointer();
     switchToSmall(0, 0);
   }

unittests/ADT/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 set(ADTSources
   APFloatTest.cpp
   APIntTest.cpp
   APSIntTest.cpp
   ArrayRefTest.cpp
   BitVectorTest.cpp
   DAGDeltaAlgorithmTest.cpp
   DeltaAlgorithmTest.cpp
   DenseMapTest.cpp
-  DenseSetTest.cpp
   FoldingSet.cpp
   FunctionRefTest.cpp
   HashingTest.cpp
   ilistTest.cpp
   ImmutableMapTest.cpp
   ImmutableSetTest.cpp
   IntEqClassesTest.cpp
   IntervalMapTest.cpp
   IntrusiveRefCntPtrTest.cpp
   MakeUniqueTest.cpp
   MapVectorTest.cpp
   OptionalTest.cpp
   PackedVectorTest.cpp
   PointerEmbeddedIntTest.cpp
   PointerIntPairTest.cpp
   PointerSumTypeTest.cpp
   PointerUnionTest.cpp
   PostOrderIteratorTest.cpp
   RangeAdapterTest.cpp
   SCCIteratorTest.cpp
+  SetTest.cpp
   SetVectorTest.cpp
   SmallPtrSetTest.cpp
   SmallStringTest.cpp
   SmallVectorTest.cpp
   SparseBitVectorTest.cpp
   SparseMultiSetTest.cpp
   SparseSetTest.cpp
   StringMapTest.cpp

unittests/ADT/DenseSetTest.cpp

-//===- llvm/unittest/ADT/DenseSetTest.cpp - DenseSet unit tests --*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "gtest/gtest.h"
-#include "llvm/ADT/DenseSet.h"
-
-using namespace llvm;
-
-namespace {
-
-// Test fixture
-class DenseSetTest : public testing::Test {
-};
-
-// Test hashing with a set of only two entries.
-TEST_F(DenseSetTest, DoubleEntrySetTest) {
-  llvm::DenseSet<unsigned> set(2);
-  set.insert(0);
-  set.insert(1);
-  // Original failure was an infinite loop in this call:
-  EXPECT_EQ(0u, set.count(2));
-}
-
-struct TestDenseSetInfo {
-  static inline unsigned getEmptyKey() { return ~0; }
-  static inline unsigned getTombstoneKey() { return ~0U - 1; }
-  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
-  static unsigned getHashValue(const char* Val) {
-    return (unsigned)(Val[0] - 'a') * 37U;
-  }
-  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
-    return LHS == RHS;
-  }
-  static bool isEqual(const char* LHS, const unsigned& RHS) {
-    return (unsigned)(LHS[0] - 'a') == RHS;
-  }
-};
-
-TEST(DenseSetCustomTest, FindAsTest) {
-  DenseSet<unsigned, TestDenseSetInfo> set;
-  set.insert(0);
-  set.insert(1);
-  set.insert(2);
-
-  // Size tests
-  EXPECT_EQ(3u, set.size());
-
-  // Normal lookup tests
-  EXPECT_EQ(1u, set.count(1));
-  EXPECT_EQ(0u, *set.find(0));
-  EXPECT_EQ(1u, *set.find(1));
-  EXPECT_EQ(2u, *set.find(2));
-  EXPECT_TRUE(set.find(3) == set.end());
-
-  // find_as() tests
-  EXPECT_EQ(0u, *set.find_as("a"));
-  EXPECT_EQ(1u, *set.find_as("b"));
-  EXPECT_EQ(2u, *set.find_as("c"));
-  EXPECT_TRUE(set.find_as("d") == set.end());
-}
-
-}

unittests/ADT/SetTest.cpp

+//===- llvm/unittest/ADT/DenseSetTest.cpp - DenseSet unit tests --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/SmallBitVector.h"
+#include "llvm/ADT/BitSet.h"
+
+using namespace llvm;
+
+namespace {
+
+// Test hashing with a set of only two entries.
+TEST(SetTest, DoubleEntrySetTest) {
+  llvm::DenseSet<unsigned> set(2);
+  set.insert(0);
+  set.insert(1);
+  // Original failure was an infinite loop in this call:
+  EXPECT_EQ(0u, set.count(2));
+}
+
+template<typename T>
+void testInsertErase(T &X) {
+  EXPECT_EQ(X.size(), 0u);
+  EXPECT_TRUE(X.empty());
+
+  EXPECT_TRUE(X.insert(7).second);
+  EXPECT_EQ(X.size(), 1u);
+  EXPECT_FALSE(X.insert(7).second);
+  EXPECT_EQ(X.size(), 1u);
+  EXPECT_EQ(X.count(7), 1u);
+
+  X.insert(10);
+  EXPECT_FALSE(X.insert(10).second);
+  EXPECT_EQ(X.count(10), 1u);
+  EXPECT_EQ(X.size(), 2u);
+
+  auto P0 = X.insert(12);
+  EXPECT_TRUE(P0.second);
+  EXPECT_EQ(X.count(12), 1u);
+  EXPECT_EQ(*P0.first, 12u);
+  EXPECT_EQ(X.size(), 3u);
+
+  auto P1 = X.insert(10);
+  EXPECT_FALSE(P1.second);
+  EXPECT_EQ(X.count(10), 1u);
+  EXPECT_EQ(*P1.first, 10u);
+  EXPECT_EQ(X.size(), 3u);
+
+  EXPECT_FALSE(X.erase(3));
+  EXPECT_EQ(X.size(), 3u);
+  X.insert(77);
+  EXPECT_TRUE(X.erase(77));
+  EXPECT_EQ(X.size(), 3u);
+  EXPECT_FALSE(X.erase(77));
+  EXPECT_EQ(X.size(), 3u);
+  EXPECT_FALSE(X.empty());
+}
+
+template<typename T>
+void testIterator(T &X) {
+  ASSERT_EQ(X.begin(), X.end());
+
+  X.insert(7);
+  X.insert(3);
+  X.insert(27);
+  X.insert(9);
+
+  bool found7 = false;
+  bool found3 = false;
+  bool found27 = false;
+  bool found9 = false;
+  for (typename T::iterator I = X.begin(); I != X.end(); ++I) {
+    switch (*I) {
+    case 3: ASSERT_FALSE(found3); found3 = true; break;
+    case 7: ASSERT_FALSE(found7); found7 = true; break;
+    case 9: ASSERT_FALSE(found9); found9 = true; break;
+    case 27: ASSERT_FALSE(found27); found27 = true; break;
+    default: ADD_FAILURE(); break;
+    }
+  }
+  ASSERT_TRUE(found3);
+  ASSERT_TRUE(found7);
+  ASSERT_TRUE(found9);
+  ASSERT_TRUE(found27);
+
+  X.clear();
+  ASSERT_EQ(X.begin(), X.end());
+}
+
+template<typename T>
+void testEraseIterator(T &X) {
+  ASSERT_EQ(X.begin(), X.end());
+
+  X.insert(7);
+  X.insert(3);
+  X.insert(27);
+  X.insert(9);
+
+  bool found7 = false;
+  bool found3 = false;
+  bool found27 = false;
+  bool found9 = false;
+  for (typename T::iterator I = X.begin(); I != X.end(); ) {
+    switch (*I) {
+    case 3: ASSERT_FALSE(found3); found3 = true; break;
+    case 7: ASSERT_FALSE(found7); found7 = true; break;
+    case 9: ASSERT_FALSE(found9); found9 = true; break;
+    case 27: ASSERT_FALSE(found27); found27 = true; break;
+    default: ADD_FAILURE(); break;
+    }
+    if (*I == 9)
+      I = X.erase(I);
+    else
+      ++I;
+  }
+  ASSERT_TRUE(found3);
+  ASSERT_TRUE(found7);
+  ASSERT_TRUE(found9);
+  ASSERT_TRUE(found27);
+
+  ASSERT_EQ(X.count(3), 1u);
+  ASSERT_EQ(X.count(7), 1u);
+  ASSERT_EQ(X.count(9), 0u);
+  ASSERT_EQ(X.count(27), 1u);
+  ASSERT_EQ(X.size(), 3u);
+}
+
+struct TestDenseSetInfo {
+  static inline unsigned getEmptyKey() { return ~0; }
+  static inline unsigned getTombstoneKey() { return ~0U - 1; }
+  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
+  static unsigned getHashValue(const char* Val) {
+    return (unsigned)(Val[0] - 'a') * 37U;
+  }
+  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
+    return LHS == RHS;
+  }
+  static bool isEqual(const char* LHS, const unsigned& RHS) {
+    return (unsigned)(LHS[0] - 'a') == RHS;
+  }
+};
+
+TEST(SetTest, FindAsTest) {
+  DenseSet<unsigned, TestDenseSetInfo> set;
+  set.insert(0);
+  set.insert(1);
+  set.insert(2);
+
+  // Size tests
+  EXPECT_EQ(3u, set.size());
+
+  // Normal lookup tests
+  EXPECT_EQ(1u, set.count(1));
+  EXPECT_EQ(0u, *set.find(0));
+  EXPECT_EQ(1u, *set.find(1));
+  EXPECT_EQ(2u, *set.find(2));
+  EXPECT_TRUE(set.find(3) == set.end());
+
+  // find_as() tests
+  EXPECT_EQ(0u, *set.find_as("a"));
+  EXPECT_EQ(1u, *set.find_as("b"));
+  EXPECT_EQ(2u, *set.find_as("c"));
+  EXPECT_TRUE(set.find_as("d") == set.end());
+}
+
+TEST(SetTest, InsertEraseDenseSetCustom) {
+  DenseSet<unsigned, TestDenseSetInfo> Set;
+  testInsertErase(Set);
+
+  DenseSet<unsigned, TestDenseSetInfo> Set2;
+  testIterator(Set2);
+}
+
+TEST(SetTest, TestBitSet) {
+  BitSet Set(89);
+  testInsertErase(Set);
+
+  BitSet Set2(29);
+  testIterator(Set2);
+  Set2.clear();
+  testEraseIterator(Set2);
+}
+
+TEST(SetTest, InsertEraseSmallBitSet) {
+  BitSet Set(89);
+  testInsertErase(Set);
+
+  SmallBitSet Set2(29);
+  testIterator(Set2);
+  Set2.clear();
+  testEraseIterator(Set2);
+}
+
+}