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 EXPECT_EQ(typename TypeParam::mapped_type(), 70 this->Map.lookup(this->getKey())); 71 } 72 73 // Constant map tests 74 TYPED_TEST(DenseMapTest, ConstEmptyMapTest) { 75 const TypeParam &ConstMap = this->Map; 76 EXPECT_EQ(0u, ConstMap.size()); 77 EXPECT_TRUE(ConstMap.empty()); 78 EXPECT_TRUE(ConstMap.begin() == ConstMap.end()); 79 } 80 81 // A map with a single entry 82 TYPED_TEST(DenseMapTest, SingleEntryMapTest) { 83 this->Map[this->getKey()] = this->getValue(); 84 85 // Size tests 86 EXPECT_EQ(1u, this->Map.size()); 87 EXPECT_FALSE(this->Map.begin() == this->Map.end()); 88 EXPECT_FALSE(this->Map.empty()); 89 90 // Iterator tests 91 typename TypeParam::iterator it = this->Map.begin(); 92 EXPECT_EQ(this->getKey(), it->first); 93 EXPECT_EQ(this->getValue(), it->second); 94 ++it; 95 EXPECT_TRUE(it == this->Map.end()); 96 97 // Lookup tests 98 EXPECT_TRUE(this->Map.count(this->getKey())); 99 EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.begin()); 100 EXPECT_EQ(this->getValue(), this->Map.lookup(this->getKey())); 101 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 102 } 103 104 // Test clear() method 105 TYPED_TEST(DenseMapTest, ClearTest) { 106 this->Map[this->getKey()] = this->getValue(); 107 this->Map.clear(); 108 109 EXPECT_EQ(0u, this->Map.size()); 110 EXPECT_TRUE(this->Map.empty()); 111 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 112 } 113 114 // Test erase(iterator) method 115 TYPED_TEST(DenseMapTest, EraseTest) { 116 this->Map[this->getKey()] = this->getValue(); 117 this->Map.erase(this->Map.begin()); 118 119 EXPECT_EQ(0u, this->Map.size()); 120 EXPECT_TRUE(this->Map.empty()); 121 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 122 } 123 124 // Test erase(value) method 125 TYPED_TEST(DenseMapTest, EraseTest2) { 126 this->Map[this->getKey()] = this->getValue(); 127 this->Map.erase(this->getKey()); 128 129 EXPECT_EQ(0u, this->Map.size()); 130 EXPECT_TRUE(this->Map.empty()); 131 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 132 } 133 134 // Test insert() method 135 TYPED_TEST(DenseMapTest, InsertTest) { 136 this->Map.insert(std::make_pair(this->getKey(), this->getValue())); 137 EXPECT_EQ(1u, this->Map.size()); 138 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 139 } 140 141 // Test copy constructor method 142 TYPED_TEST(DenseMapTest, CopyConstructorTest) { 143 this->Map[this->getKey()] = this->getValue(); 144 TypeParam copyMap(this->Map); 145 146 EXPECT_EQ(1u, copyMap.size()); 147 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); 148 } 149 150 // Test assignment operator method 151 TYPED_TEST(DenseMapTest, AssignmentTest) { 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 // A more complex iteration test 160 TYPED_TEST(DenseMapTest, IterationTest) { 161 bool visited[100]; 162 std::map<typename TypeParam::key_type, unsigned> visitedIndex; 163 164 // Insert 100 numbers into the map 165 for (int i = 0; i < 100; ++i) { 166 visited[i] = false; 167 visitedIndex[this->getKey(i)] = i; 168 169 this->Map[this->getKey(i)] = this->getValue(i); 170 } 171 172 // Iterate over all numbers and mark each one found. 173 for (typename TypeParam::iterator it = this->Map.begin(); 174 it != this->Map.end(); ++it) 175 visited[visitedIndex[it->first]] = true; 176 177 // Ensure every number was visited. 178 for (int i = 0; i < 100; ++i) 179 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited"; 180 } 181 182 // const_iterator test 183 TYPED_TEST(DenseMapTest, ConstIteratorTest) { 184 // Check conversion from iterator to const_iterator. 185 typename TypeParam::iterator it = this->Map.begin(); 186 typename TypeParam::const_iterator cit(it); 187 EXPECT_TRUE(it == cit); 188 189 // Check copying of const_iterators. 190 typename TypeParam::const_iterator cit2(cit); 191 EXPECT_TRUE(cit == cit2); 192 } 193 194 // Key traits that allows lookup with either an unsigned or char* key; 195 // In the latter case, "a" == 0, "b" == 1 and so on. 196 struct TestDenseMapInfo { 197 static inline unsigned getEmptyKey() { return ~0; } 198 static inline unsigned getTombstoneKey() { return ~0U - 1; } 199 static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 200 static unsigned getHashValue(const char* Val) { 201 return (unsigned)(Val[0] - 'a') * 37U; 202 } 203 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 204 return LHS == RHS; 205 } 206 static bool isEqual(const char* LHS, const unsigned& RHS) { 207 return (unsigned)(LHS[0] - 'a') == RHS; 208 } 209 }; 210 211 // find_as() tests 212 TEST(DenseMapCustomTest, FindAsTest) { 213 DenseMap<unsigned, unsigned, TestDenseMapInfo> map; 214 map[0] = 1; 215 map[1] = 2; 216 map[2] = 3; 217 218 // Size tests 219 EXPECT_EQ(3u, map.size()); 220 221 // Normal lookup tests 222 EXPECT_EQ(1, map.count(1)); 223 EXPECT_EQ(1u, map.find(0)->second); 224 EXPECT_EQ(2u, map.find(1)->second); 225 EXPECT_EQ(3u, map.find(2)->second); 226 EXPECT_TRUE(map.find(3) == map.end()); 227 228 // find_as() tests 229 EXPECT_EQ(1u, map.find_as("a")->second); 230 EXPECT_EQ(2u, map.find_as("b")->second); 231 EXPECT_EQ(3u, map.find_as("c")->second); 232 EXPECT_TRUE(map.find_as("d") == map.end()); 233 } 234 235 } 236