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