[ADT] Add a 'find_as' operation to DenseSet.

This operation is analogous to its counterpart in DenseMap: It allows lookup
via cheap-to-construct keys (provided that getHashValue and isEqual are
implemented for the cheap key-type in the DenseMapInfo specialization).

Thanks to Chandler for the review.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220168 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/ADT/DenseSet.h b/include/llvm/ADT/DenseSet.h
index 37a81b0c7ee2d70918897f8daec38c287d6be407..ae7328cc19a558226aa8c337c55b7a42343ccc60 100644 (file)
--- a/include/llvm/ADT/DenseSet.h
+++ b/include/llvm/ADT/DenseSet.h
@@ -110,6 +110,21 @@ public:
   const_iterator end() const { return ConstIterator(TheMap.end()); }
 
   iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); }
   const_iterator end() const { return ConstIterator(TheMap.end()); }
 
   iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); }

+
+  /// Alternative version of find() which allows a different, and possibly less
+  /// expensive, key type.
+  /// The DenseMapInfo is responsible for supplying methods
+  /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
+  /// used.
+  template <class LookupKeyT>
+  iterator find_as(const LookupKeyT &Val) {
+    return Iterator(TheMap.find_as(Val));
+  }
+  template <class LookupKeyT>
+  const_iterator find_as(const LookupKeyT &Val) const {
+    return ConstIterator(TheMap.find_as(Val));
+  }
+

   void erase(Iterator I) { return TheMap.erase(I.I); }
   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
 
   void erase(Iterator I) { return TheMap.erase(I.I); }
   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
 

diff --git a/unittests/ADT/DenseSetTest.cpp b/unittests/ADT/DenseSetTest.cpp
index 154c5892d5fd51c1a2681ce3b44f85117eb4bb87..5952353034fdc91aac4a69ab00ed6c7b43636c8a 100644 (file)
--- a/unittests/ADT/DenseSetTest.cpp
+++ b/unittests/ADT/DenseSetTest.cpp
@@ -27,4 +27,42 @@ TEST_F(DenseSetTest, DoubleEntrySetTest) {
   EXPECT_EQ(0u, set.count(2));
 }
 
   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());
+}
+

 }
 }