1 //===- llvm/unittest/ADT/DenseMapMap.cpp - DenseMap unit tests --*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "gtest/gtest.h" 11 #include "llvm/ADT/DenseMap.h" 12 #include <map> 13 14 using namespace llvm; 15 16 namespace { 17 18 uint32_t getTestKey(int i, uint32_t *) { return i; } 19 uint32_t getTestValue(int i, uint32_t *) { return 42 + i; } 20 21 uint32_t *getTestKey(int i, uint32_t **) { 22 static uint32_t dummy_arr1[8192]; 23 assert(i < 8192 && "Only support 8192 dummy keys."); 24 return &dummy_arr1[i]; 25 } 26 uint32_t *getTestValue(int i, uint32_t **) { 27 static uint32_t dummy_arr1[8192]; 28 assert(i < 8192 && "Only support 8192 dummy keys."); 29 return &dummy_arr1[i]; 30 } 31 32 // Test fixture, with helper functions implemented by forwarding to global 33 // function overloads selected by component types of the type parameter. This 34 // allows all of the map implementations to be tested with shared 35 // implementations of helper routines. 36 template <typename T> 37 class DenseMapTest : public ::testing::Test { 38 protected: 39 T Map; 40 41 static typename T::key_type *const dummy_key_ptr; 42 static typename T::mapped_type *const dummy_value_ptr; 43 44 typename T::key_type getKey(int i = 0) { 45 return getTestKey(i, dummy_key_ptr); 46 } 47 typename T::mapped_type getValue(int i = 0) { 48 return getTestValue(i, dummy_value_ptr); 49 } 50 }; 51 52 template <typename T> 53 typename T::key_type *const DenseMapTest<T>::dummy_key_ptr = 0; 54 template <typename T> 55 typename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = 0; 56 57 // Register these types for testing. 58 typedef ::testing::Types<DenseMap<uint32_t, uint32_t>, 59 DenseMap<uint32_t *, uint32_t *>, 60 SmallDenseMap<uint32_t, uint32_t>, 61 SmallDenseMap<uint32_t *, uint32_t *> 62 > DenseMapTestTypes; 63 TYPED_TEST_CASE(DenseMapTest, DenseMapTestTypes); 64 65 // Empty map tests 66 TYPED_TEST(DenseMapTest, EmptyIntMapTest) { 67 // Size tests 68 EXPECT_EQ(0u, this->Map.size()); 69 EXPECT_TRUE(this->Map.empty()); 70 71 // Iterator tests 72 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 73 74 // Lookup tests 75 EXPECT_FALSE(this->Map.count(this->getKey())); 76 EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.end()); 77 #ifndef _MSC_VER 78 EXPECT_EQ(typename TypeParam::mapped_type(), 79 this->Map.lookup(this->getKey())); 80 #else 81 // MSVC, at least old versions, cannot parse the typename to disambiguate 82 // TypeParam::mapped_type as a type. However, because MSVC doesn't implement 83 // two-phase name lookup, it also doesn't require the typename. Deal with 84 // this mutual incompatibility through specialized code. 85 EXPECT_EQ(TypeParam::mapped_type(), 86 this->Map.lookup(this->getKey())); 87 #endif 88 } 89 90 // Constant map tests 91 TYPED_TEST(DenseMapTest, ConstEmptyMapTest) { 92 const TypeParam &ConstMap = this->Map; 93 EXPECT_EQ(0u, ConstMap.size()); 94 EXPECT_TRUE(ConstMap.empty()); 95 EXPECT_TRUE(ConstMap.begin() == ConstMap.end()); 96 } 97 98 // A map with a single entry 99 TYPED_TEST(DenseMapTest, SingleEntryMapTest) { 100 this->Map[this->getKey()] = this->getValue(); 101 102 // Size tests 103 EXPECT_EQ(1u, this->Map.size()); 104 EXPECT_FALSE(this->Map.begin() == this->Map.end()); 105 EXPECT_FALSE(this->Map.empty()); 106 107 // Iterator tests 108 typename TypeParam::iterator it = this->Map.begin(); 109 EXPECT_EQ(this->getKey(), it->first); 110 EXPECT_EQ(this->getValue(), it->second); 111 ++it; 112 EXPECT_TRUE(it == this->Map.end()); 113 114 // Lookup tests 115 EXPECT_TRUE(this->Map.count(this->getKey())); 116 EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.begin()); 117 EXPECT_EQ(this->getValue(), this->Map.lookup(this->getKey())); 118 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 119 } 120 121 // Test clear() method 122 TYPED_TEST(DenseMapTest, ClearTest) { 123 this->Map[this->getKey()] = this->getValue(); 124 this->Map.clear(); 125 126 EXPECT_EQ(0u, this->Map.size()); 127 EXPECT_TRUE(this->Map.empty()); 128 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 129 } 130 131 // Test erase(iterator) method 132 TYPED_TEST(DenseMapTest, EraseTest) { 133 this->Map[this->getKey()] = this->getValue(); 134 this->Map.erase(this->Map.begin()); 135 136 EXPECT_EQ(0u, this->Map.size()); 137 EXPECT_TRUE(this->Map.empty()); 138 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 139 } 140 141 // Test erase(value) method 142 TYPED_TEST(DenseMapTest, EraseTest2) { 143 this->Map[this->getKey()] = this->getValue(); 144 this->Map.erase(this->getKey()); 145 146 EXPECT_EQ(0u, this->Map.size()); 147 EXPECT_TRUE(this->Map.empty()); 148 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 149 } 150 151 // Test insert() method 152 TYPED_TEST(DenseMapTest, InsertTest) { 153 this->Map.insert(std::make_pair(this->getKey(), this->getValue())); 154 EXPECT_EQ(1u, this->Map.size()); 155 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 156 } 157 158 // Test copy constructor method 159 TYPED_TEST(DenseMapTest, CopyConstructorTest) { 160 this->Map[this->getKey()] = this->getValue(); 161 TypeParam copyMap(this->Map); 162 163 EXPECT_EQ(1u, copyMap.size()); 164 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); 165 } 166 167 // Test assignment operator method 168 TYPED_TEST(DenseMapTest, AssignmentTest) { 169 this->Map[this->getKey()] = this->getValue(); 170 TypeParam copyMap = this->Map; 171 172 EXPECT_EQ(1u, copyMap.size()); 173 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); 174 } 175 176 // A more complex iteration test 177 TYPED_TEST(DenseMapTest, IterationTest) { 178 bool visited[100]; 179 std::map<typename TypeParam::key_type, unsigned> visitedIndex; 180 181 // Insert 100 numbers into the map 182 for (int i = 0; i < 100; ++i) { 183 visited[i] = false; 184 visitedIndex[this->getKey(i)] = i; 185 186 this->Map[this->getKey(i)] = this->getValue(i); 187 } 188 189 // Iterate over all numbers and mark each one found. 190 for (typename TypeParam::iterator it = this->Map.begin(); 191 it != this->Map.end(); ++it) 192 visited[visitedIndex[it->first]] = true; 193 194 // Ensure every number was visited. 195 for (int i = 0; i < 100; ++i) 196 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited"; 197 } 198 199 // const_iterator test 200 TYPED_TEST(DenseMapTest, ConstIteratorTest) { 201 // Check conversion from iterator to const_iterator. 202 typename TypeParam::iterator it = this->Map.begin(); 203 typename TypeParam::const_iterator cit(it); 204 EXPECT_TRUE(it == cit); 205 206 // Check copying of const_iterators. 207 typename TypeParam::const_iterator cit2(cit); 208 EXPECT_TRUE(cit == cit2); 209 } 210 211 // Key traits that allows lookup with either an unsigned or char* key; 212 // In the latter case, "a" == 0, "b" == 1 and so on. 213 struct TestDenseMapInfo { 214 static inline unsigned getEmptyKey() { return ~0; } 215 static inline unsigned getTombstoneKey() { return ~0U - 1; } 216 static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 217 static unsigned getHashValue(const char* Val) { 218 return (unsigned)(Val[0] - 'a') * 37U; 219 } 220 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 221 return LHS == RHS; 222 } 223 static bool isEqual(const char* LHS, const unsigned& RHS) { 224 return (unsigned)(LHS[0] - 'a') == RHS; 225 } 226 }; 227 228 // find_as() tests 229 TEST(DenseMapCustomTest, FindAsTest) { 230 DenseMap<unsigned, unsigned, TestDenseMapInfo> map; 231 map[0] = 1; 232 map[1] = 2; 233 map[2] = 3; 234 235 // Size tests 236 EXPECT_EQ(3u, map.size()); 237 238 // Normal lookup tests 239 EXPECT_EQ(1, map.count(1)); 240 EXPECT_EQ(1u, map.find(0)->second); 241 EXPECT_EQ(2u, map.find(1)->second); 242 EXPECT_EQ(3u, map.find(2)->second); 243 EXPECT_TRUE(map.find(3) == map.end()); 244 245 // find_as() tests 246 EXPECT_EQ(1u, map.find_as("a")->second); 247 EXPECT_EQ(2u, map.find_as("b")->second); 248 EXPECT_EQ(3u, map.find_as("c")->second); 249 EXPECT_TRUE(map.find_as("d") == map.end()); 250 } 251 252 } 253