DenseMapTest.cpp revision dd9d38d57bbd2161e04af90a9e03011afb039b16
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 14using namespace llvm; 15 16namespace { 17 18uint32_t getTestKey(int i, uint32_t *) { return i; } 19uint32_t getTestValue(int i, uint32_t *) { return 42 + i; } 20 21uint32_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} 26uint32_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. 36template <typename T> 37class DenseMapTest : public ::testing::Test { 38protected: 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 52template <typename T> 53typename T::key_type *const DenseMapTest<T>::dummy_key_ptr = 0; 54template <typename T> 55typename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = 0; 56 57// Register these types for testing. 58typedef ::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; 63TYPED_TEST_CASE(DenseMapTest, DenseMapTestTypes); 64 65// Empty map tests 66TYPED_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 91TYPED_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 99TYPED_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 122TYPED_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 132TYPED_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 142TYPED_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 152TYPED_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 159TYPED_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 168TYPED_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 177TYPED_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 200TYPED_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. 213struct 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 229TEST(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