DenseMapTest.cpp revision e5c7bc65c30feabed5f05eecee1ff1433e35d381
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 EXPECT_EQ(typename TypeParam::mapped_type(), 70 this->Map.lookup(this->getKey())); 71} 72 73// Constant map tests 74TYPED_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 82TYPED_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 105TYPED_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 115TYPED_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 125TYPED_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 135TYPED_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 142TYPED_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 151TYPED_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 160TYPED_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 183TYPED_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. 196struct 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 212TEST(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