[SmallSet] Add SmallSetIterator.

[fhahn]

Summary

This patch adds a simple const_iterator implementation for SmallSet by
delegating to either a SmallVector::const_iterator or
std::set::const_iterator, depending on which storage is used by the
SmallSet.

The motivation for adding this is D46827, where it is helpful to iterate
over a SmallSet.

[dblaikie]

include/llvm/ADT/SmallSet.h

31

Any chance using iterator_facade (in include/llvm/ADT/iterator.h) would help simplify this implementation?

36

Might make sense to put isSmall after the union for packing reasons (eg: if the iterators are 24 bits long and require 32 bit alignment - the existing ordering would create a 64 bit total size, but swapping it around would allow a 32 bit size, I think?)?

unittests/ADT/SmallSetTest.cpp

72–84

Does this test both the small and non-small cases?

[fhahn]

Thanks for having a look. I've updated the patch to use iterator_facade_base and changed the test to test both the big and small case.

[dblaikie]

include/llvm/ADT/SmallSet.h

32

I imagine this type needs user-defined special members (copy/move ctors and copy/move assignment operators) - the usual "rule of 5" (the user-defined dtor being an indicator here)

unittests/ADT/SmallSetTest.cpp

77–78

I'd probably put a blank line between these two lines - can look a bit confusing otherwise (similarly below).

And/or maybe skip the explicit scopes here - could move the std::vector declaration up to the s1 declaration, and replace the iter+iter ctor with v.assign(iter, iter) instead.

[fhahn]

include/llvm/ADT/SmallSet.h

32

It looks like both the set and SmallVector iterators have trivial ctors/dtors and move/assignment operators. So it seems like the destructor is not needed either, at least the compiler does not complain about any missing functions. Would it be safe to get rid of the dtor instead in this case?

[dblaikie]

include/llvm/ADT/SmallSet.h

32

Might be OK to remove them if you add in some static_asserts that all the relevant members (all 5) are trivial?

[fhahn]

Replace unneeded destructor with static assertion making sure everything required by the rule of five is trivial. I also updated the test as suggested and added another test with a type with non-trivial ctors/dtor.

[dblaikie]

Seems good to me (:

[fhahn]

I had to revert this, as libstdc++ 4.8 does not have the is_trivially_XXX<T> helpers https://gcc.gnu.org/onlinedocs/gcc-4.8.3/libstdc++/manual/manual/status.html#status.iso.2011 :(

[fhahn]

Recommitted as rL336805, with only the subset of is_trivially_XXX provided by GCC 4.8 and llvm/Support/type_traits.h

[fhahn]

The windows bots have surfaced another problem: set<T>::const_iterator is not trivially copy constructible... Not sure how to best work around that yet.

[fhahn]

err, hit send too soon: not trivially copy constructible in MSVC's STL.

[Szelethus]

It might worth updating the Programmer's Manual, it still states that SmallSet has no support for iteration.

include/llvm/ADT/SmallSet.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_SMALLSET_H
 #define LLVM_ADT_SMALLSET_H
 
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator.h"
 #include "llvm/Support/Compiler.h"
 #include <cstddef>
 #include <functional>
 #include <set>
 #include <utility>
 
 namespace llvm {
 
+/// SmallSetIterator - This class implements a const_iterator for SmallSet by
+/// delegating to the underlying SmallVector or Set iterators.
+template <typename T, unsigned N, typename C>
+class SmallSetIterator
+    : public iterator_facade_base<SmallSetIterator<T, N, C>,
+                                  std::forward_iterator_tag, T> {
+private:
+  using SetIterTy = typename std::set<T, C>::const_iterator;
+  using VecIterTy = typename SmallVector<T, N>::const_iterator;
+
+  /// Iterators to the parts of the SmallSet containing the data. They are set
+  /// depending on isSmall.
+  union {
+    SetIterTy SetIter;
+    VecIterTy VecIter;
+  };
+
+  bool isSmall;
+
+public:
+  SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {}
+  SmallSetIterator(VecIterTy VecIter) : VecIter(VecIter), isSmall(true) {}
+
+  ~SmallSetIterator() {
+    // Destruct underlying iterator object depending on size.
+    if (isSmall)
+      VecIter.~VecIterTy();
+    else
+      SetIter.~SetIterTy();
+  }
+
+  bool operator==(const SmallSetIterator &RHS) const {
+    if (isSmall != RHS.isSmall)
+      return false;
+    if (isSmall)
+      return VecIter == RHS.VecIter;
+    return SetIter == RHS.SetIter;
+  }
+
+  SmallSetIterator &operator++() { // Preincrement
+    if (isSmall)
+      VecIter++;
+    else
+      SetIter++;
+    return *this;
+  }
+
+  const T &operator*() const { return isSmall ? *VecIter : *SetIter; }
+};
+
 /// SmallSet - This maintains a set of unique values, optimizing for the case
 /// when the set is small (less than N).  In this case, the set can be
 /// maintained with no mallocs.  If the set gets large, we expand to using an
 /// std::set to maintain reasonable lookup times.
 ///
 /// Note that this set does not provide a way to iterate over members in the
 /// set.
 template <typename T, unsigned N, typename C = std::less<T>>
class SmallSet {
 
   // In small mode SmallPtrSet uses linear search for the elements, so it is
   // not a good idea to choose this value too high. You may consider using a
   // DenseSet<> instead if you expect many elements in the set.
   static_assert(N <= 32, "N should be small");
 
 public:
   using size_type = size_t;
+  using const_iterator = SmallSetIterator<T, N, C>;
 
   SmallSet() = default;
 
   LLVM_NODISCARD bool empty() const {
     return Vector.empty() && Set.empty();
   }
 
   size_type size() const {
bool erase(const T &V) {
     return false;
   }
 
   void clear() {
     Vector.clear();
     Set.clear();
   }
 
+  const_iterator begin() const {
+    if (isSmall())
+      return {Vector.begin()};
+    return {Set.begin()};
+  }
+
+  const_iterator end() const {
+    if (isSmall())
+      return {Vector.end()};
+    return {Set.end()};
+  }
+
 private:
   bool isSmall() const { return Set.empty(); }
 
   VIterator vfind(const T &V) const {
     for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
       if (*I == V)
         return I;
     return Vector.end();

unittests/ADT/SmallSetTest.cpp

TEST(SmallSetTest, Insert) {
   for (int i = 0; i < 4; i++)
     s1.insert(i);
 
   EXPECT_EQ(4u, s1.size());
 
   for (int i = 0; i < 4; i++)
     EXPECT_EQ(1u, s1.count(i));
 
-<<<<<<< 458a792747d59ffe24a712aadf91104d2d9cd1ee
-=======
-  EXPECT_EQ(0u, s1.count(99));
->>>>>>> [SmallSet] Add some simple unit tests.
   EXPECT_EQ(0u, s1.count(4));
 }
 
 TEST(SmallSetTest, Grow) {
   SmallSet<int, 4> s1;
 
   for (int i = 0; i < 8; i++)
     s1.insert(i);
 
   EXPECT_EQ(8u, s1.size());
 
   for (int i = 0; i < 8; i++)
     EXPECT_EQ(1u, s1.count(i));
 
-<<<<<<< 458a792747d59ffe24a712aadf91104d2d9cd1ee
   EXPECT_EQ(0u, s1.count(8));
-=======
-  EXPECT_EQ(0u, s1.count(99));
-  EXPECT_EQ(0u, s1.count(10));
->>>>>>> [SmallSet] Add some simple unit tests.
 }
 
 TEST(SmallSetTest, Erase) {
   SmallSet<int, 4> s1;
 
   for (int i = 0; i < 8; i++)
     s1.insert(i);
 
   EXPECT_EQ(8u, s1.size());
 
   // Remove elements one by one and check if all other elements are still there.
   for (int i = 0; i < 8; i++) {
     EXPECT_EQ(1u, s1.count(i));
     EXPECT_TRUE(s1.erase(i));
     EXPECT_EQ(0u, s1.count(i));
     EXPECT_EQ(8u - i - 1, s1.size());
     for (int j = i + 1; j < 8; j++)
       EXPECT_EQ(1u, s1.count(j));
   }
 
   EXPECT_EQ(0u, s1.count(8));
 }
+
+TEST(SmallSetTest, Iterator) {
+  SmallSet<int, 4> s1;
+
+  // Test the 'small' case.
+  for (int i = 0; i < 3; i++)
+    s1.insert(i);
+  {
+    std::vector<int> V(s1.begin(), s1.end());
+    // Make sure the elements are in the expected order.
+    std::sort(V.begin(), V.end());
+    for (int i = 0; i < 3; i++)
+      EXPECT_EQ(i, V[i]);
+  }
+
+  // Test the 'big' case by adding a few more elements to switch to std::set
+  // internally.
+  for (int i = 3; i < 6; i++)
+    s1.insert(i);
+  {
+    std::vector<int> V(s1.begin(), s1.end());
+    // Make sure the elements are in the expected order.
+    std::sort(V.begin(), V.end());
+    for (int i = 0; i < 6; i++)
+      EXPECT_EQ(i, V[i]);
+  }
+}