[ADT] Teach DenseMap to support StringRef keys.
authorChandler Carruth <chandlerc@gmail.com>
Wed, 24 Jun 2015 10:06:29 +0000 (10:06 +0000)
committerChandler Carruth <chandlerc@gmail.com>
Wed, 24 Jun 2015 10:06:29 +0000 (10:06 +0000)
While often you want to use something specialized like StringMap, when
the strings already have persistent storage a normal densemap over them
can be more efficient.

This can't go into StringRef.h because of really obnoxious header chains
from the hashing code to the endian detection code to CPU feature
detection code to StringMap.

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

include/llvm/ADT/DenseMapInfo.h
unittests/ADT/DenseMapTest.cpp

index 6f17a64..b0a0530 100644 (file)
@@ -14,6 +14,8 @@
 #ifndef LLVM_ADT_DENSEMAPINFO_H
 #define LLVM_ADT_DENSEMAPINFO_H
 
+#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include "llvm/Support/type_traits.h"
 
@@ -163,6 +165,31 @@ struct DenseMapInfo<std::pair<T, U> > {
   }
 };
 
+// Provide DenseMapInfo for StringRefs.
+template <> struct DenseMapInfo<StringRef> {
+  static inline StringRef getEmptyKey() {
+    return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(0)),
+                     0);
+  }
+  static inline StringRef getTombstoneKey() {
+    return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(1)),
+                     0);
+  }
+  static unsigned getHashValue(StringRef Val) {
+    assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
+    assert(Val.data() != getTombstoneKey().data() &&
+           "Cannot hash the tombstone key!");
+    return (unsigned)(hash_value(Val));
+  }
+  static bool isEqual(StringRef LHS, StringRef RHS) {
+    if (RHS.data() == getEmptyKey().data())
+      return LHS.data() == getEmptyKey().data();
+    if (RHS.data() == getTombstoneKey().data())
+      return LHS.data() == getTombstoneKey().data();
+    return LHS == RHS;
+  }
+};
+
 } // end namespace llvm
 
 #endif
index 9780777..2c6fe35 100644 (file)
@@ -323,6 +323,31 @@ TYPED_TEST(DenseMapTest, ConstIteratorTest) {
   EXPECT_TRUE(cit == cit2);
 }
 
+// Make sure DenseMap works with StringRef keys.
+TEST(DenseMapCustomTest, StringRefTest) {
+  DenseMap<StringRef, int> M;
+
+  M["a"] = 1;
+  M["b"] = 2;
+  M["c"] = 3;
+
+  EXPECT_EQ(3u, M.size());
+  EXPECT_EQ(1, M.lookup("a"));
+  EXPECT_EQ(2, M.lookup("b"));
+  EXPECT_EQ(3, M.lookup("c"));
+
+  EXPECT_EQ(0, M.lookup("q"));
+
+  // Test the empty string, spelled various ways.
+  EXPECT_EQ(0, M.lookup(""));
+  EXPECT_EQ(0, M.lookup(StringRef()));
+  EXPECT_EQ(0, M.lookup(StringRef("a", 0)));
+  M[""] = 42;
+  EXPECT_EQ(42, M.lookup(""));
+  EXPECT_EQ(42, M.lookup(StringRef()));
+  EXPECT_EQ(42, M.lookup(StringRef("a", 0)));
+}
+
 // Key traits that allows lookup with either an unsigned or char* key;
 // In the latter case, "a" == 0, "b" == 1 and so on.
 struct TestDenseMapInfo {