DenseMapTest.cpp revision 7027ba92dd7381188d3014d2ae1d9bedef9a218e
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 18// Test fixture 19template <typename T> 20class DenseMapTest : public testing::Test { 21protected: 22 T Map; 23 24 typename T::key_type getKey(int i = 0); 25 typename T::mapped_type getValue(int i = 0); 26}; 27 28template <> 29uint32_t DenseMapTest<DenseMap<uint32_t, uint32_t> >::getKey(int i) { 30 return i; 31} 32 33template <> 34uint32_t DenseMapTest<DenseMap<uint32_t, uint32_t> >::getValue(int i) { 35 return 42 + i; 36} 37 38template <> 39uint32_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 45template <> 46uint32_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. 53typedef ::testing::Types<DenseMap<uint32_t, uint32_t>, 54 DenseMap<uint32_t *, uint32_t *> > DenseMapTestTypes; 55TYPED_TEST_CASE(DenseMapTest, DenseMapTestTypes); 56 57// Empty map tests 58TYPED_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 83TYPED_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 91TYPED_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 114TYPED_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 124TYPED_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 134TYPED_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 144TYPED_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 151TYPED_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 160TYPED_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 169TYPED_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 192TYPED_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. 205struct 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 221TEST(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