+ for (int i = 0; i < 100; ++i)
+ ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited";
+}
+
+// const_iterator test
+TYPED_TEST(DenseMapTest, ConstIteratorTest) {
+ // Check conversion from iterator to const_iterator.
+ typename TypeParam::iterator it = this->Map.begin();
+ typename TypeParam::const_iterator cit(it);
+ EXPECT_TRUE(it == cit);
+
+ // Check copying of const_iterators.
+ typename TypeParam::const_iterator cit2(cit);
+ 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 {
+ 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;