1 //===- llvm/unittest/ADT/StringMapMap.cpp - StringMap unit tests ----------===// 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/StringMap.h" 12 #include "llvm/Support/DataTypes.h" 13 using namespace llvm; 14 15 namespace { 16 17 // Test fixture 18 class StringMapTest : public testing::Test { 19 protected: 20 StringMap<uint32_t> testMap; 21 22 static const char testKey[]; 23 static const uint32_t testValue; 24 static const char* testKeyFirst; 25 static size_t testKeyLength; 26 static const std::string testKeyStr; 27 28 void assertEmptyMap() { 29 // Size tests 30 EXPECT_EQ(0u, testMap.size()); 31 EXPECT_TRUE(testMap.empty()); 32 33 // Iterator tests 34 EXPECT_TRUE(testMap.begin() == testMap.end()); 35 36 // Lookup tests 37 EXPECT_EQ(0u, testMap.count(testKey)); 38 EXPECT_EQ(0u, testMap.count(StringRef(testKeyFirst, testKeyLength))); 39 EXPECT_EQ(0u, testMap.count(testKeyStr)); 40 EXPECT_TRUE(testMap.find(testKey) == testMap.end()); 41 EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == 42 testMap.end()); 43 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.end()); 44 } 45 46 void assertSingleItemMap() { 47 // Size tests 48 EXPECT_EQ(1u, testMap.size()); 49 EXPECT_FALSE(testMap.begin() == testMap.end()); 50 EXPECT_FALSE(testMap.empty()); 51 52 // Iterator tests 53 StringMap<uint32_t>::iterator it = testMap.begin(); 54 EXPECT_STREQ(testKey, it->first().data()); 55 EXPECT_EQ(testValue, it->second); 56 ++it; 57 EXPECT_TRUE(it == testMap.end()); 58 59 // Lookup tests 60 EXPECT_EQ(1u, testMap.count(testKey)); 61 EXPECT_EQ(1u, testMap.count(StringRef(testKeyFirst, testKeyLength))); 62 EXPECT_EQ(1u, testMap.count(testKeyStr)); 63 EXPECT_TRUE(testMap.find(testKey) == testMap.begin()); 64 EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == 65 testMap.begin()); 66 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.begin()); 67 } 68 }; 69 70 const char StringMapTest::testKey[] = "key"; 71 const uint32_t StringMapTest::testValue = 1u; 72 const char* StringMapTest::testKeyFirst = testKey; 73 size_t StringMapTest::testKeyLength = sizeof(testKey) - 1; 74 const std::string StringMapTest::testKeyStr(testKey); 75 76 // Empty map tests. 77 TEST_F(StringMapTest, EmptyMapTest) { 78 assertEmptyMap(); 79 } 80 81 // Constant map tests. 82 TEST_F(StringMapTest, ConstEmptyMapTest) { 83 const StringMap<uint32_t>& constTestMap = testMap; 84 85 // Size tests 86 EXPECT_EQ(0u, constTestMap.size()); 87 EXPECT_TRUE(constTestMap.empty()); 88 89 // Iterator tests 90 EXPECT_TRUE(constTestMap.begin() == constTestMap.end()); 91 92 // Lookup tests 93 EXPECT_EQ(0u, constTestMap.count(testKey)); 94 EXPECT_EQ(0u, constTestMap.count(StringRef(testKeyFirst, testKeyLength))); 95 EXPECT_EQ(0u, constTestMap.count(testKeyStr)); 96 EXPECT_TRUE(constTestMap.find(testKey) == constTestMap.end()); 97 EXPECT_TRUE(constTestMap.find(StringRef(testKeyFirst, testKeyLength)) == 98 constTestMap.end()); 99 EXPECT_TRUE(constTestMap.find(testKeyStr) == constTestMap.end()); 100 } 101 102 // A map with a single entry. 103 TEST_F(StringMapTest, SingleEntryMapTest) { 104 testMap[testKey] = testValue; 105 assertSingleItemMap(); 106 } 107 108 // Test clear() method. 109 TEST_F(StringMapTest, ClearTest) { 110 testMap[testKey] = testValue; 111 testMap.clear(); 112 assertEmptyMap(); 113 } 114 115 // Test erase(iterator) method. 116 TEST_F(StringMapTest, EraseIteratorTest) { 117 testMap[testKey] = testValue; 118 testMap.erase(testMap.begin()); 119 assertEmptyMap(); 120 } 121 122 // Test erase(value) method. 123 TEST_F(StringMapTest, EraseValueTest) { 124 testMap[testKey] = testValue; 125 testMap.erase(testKey); 126 assertEmptyMap(); 127 } 128 129 // Test inserting two values and erasing one. 130 TEST_F(StringMapTest, InsertAndEraseTest) { 131 testMap[testKey] = testValue; 132 testMap["otherKey"] = 2; 133 testMap.erase("otherKey"); 134 assertSingleItemMap(); 135 } 136 137 TEST_F(StringMapTest, SmallFullMapTest) { 138 // StringMap has a tricky corner case when the map is small (<8 buckets) and 139 // it fills up through a balanced pattern of inserts and erases. This can 140 // lead to inf-loops in some cases (PR13148) so we test it explicitly here. 141 llvm::StringMap<int> Map(2); 142 143 Map["eins"] = 1; 144 Map["zwei"] = 2; 145 Map["drei"] = 3; 146 Map.erase("drei"); 147 Map.erase("eins"); 148 Map["veir"] = 4; 149 Map["funf"] = 5; 150 151 EXPECT_EQ(3u, Map.size()); 152 EXPECT_EQ(0, Map.lookup("eins")); 153 EXPECT_EQ(2, Map.lookup("zwei")); 154 EXPECT_EQ(0, Map.lookup("drei")); 155 EXPECT_EQ(4, Map.lookup("veir")); 156 EXPECT_EQ(5, Map.lookup("funf")); 157 } 158 159 // A more complex iteration test. 160 TEST_F(StringMapTest, IterationTest) { 161 bool visited[100]; 162 163 // Insert 100 numbers into the map 164 for (int i = 0; i < 100; ++i) { 165 std::stringstream ss; 166 ss << "key_" << i; 167 testMap[ss.str()] = i; 168 visited[i] = false; 169 } 170 171 // Iterate over all numbers and mark each one found. 172 for (StringMap<uint32_t>::iterator it = testMap.begin(); 173 it != testMap.end(); ++it) { 174 std::stringstream ss; 175 ss << "key_" << it->second; 176 ASSERT_STREQ(ss.str().c_str(), it->first().data()); 177 visited[it->second] = true; 178 } 179 180 // Ensure every number was visited. 181 for (int i = 0; i < 100; ++i) { 182 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited"; 183 } 184 } 185 186 } // end anonymous namespace 187 188 namespace llvm { 189 190 template <> 191 class StringMapEntryInitializer<uint32_t> { 192 public: 193 template <typename InitTy> 194 static void Initialize(StringMapEntry<uint32_t> &T, InitTy InitVal) { 195 T.second = InitVal; 196 } 197 }; 198 199 } // end llvm namespace 200 201 namespace { 202 203 // Test StringMapEntry::Create() method. 204 TEST_F(StringMapTest, StringMapEntryTest) { 205 StringMap<uint32_t>::value_type* entry = 206 StringMap<uint32_t>::value_type::Create( 207 testKeyFirst, testKeyFirst + testKeyLength, 1u); 208 EXPECT_STREQ(testKey, entry->first().data()); 209 EXPECT_EQ(1u, entry->second); 210 free(entry); 211 } 212 213 // Test insert() method. 214 TEST_F(StringMapTest, InsertTest) { 215 SCOPED_TRACE("InsertTest"); 216 testMap.insert( 217 StringMap<uint32_t>::value_type::Create( 218 testKeyFirst, testKeyFirst + testKeyLength, 219 testMap.getAllocator(), 1u)); 220 assertSingleItemMap(); 221 } 222 223 } // end anonymous namespace 224
