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#include <tuple> 14using namespace llvm; 15 16namespace { 17 18// Test fixture 19class StringMapTest : public testing::Test { 20protected: 21 StringMap<uint32_t> testMap; 22 23 static const char testKey[]; 24 static const uint32_t testValue; 25 static const char* testKeyFirst; 26 static size_t testKeyLength; 27 static const std::string testKeyStr; 28 29 void assertEmptyMap() { 30 // Size tests 31 EXPECT_EQ(0u, testMap.size()); 32 EXPECT_TRUE(testMap.empty()); 33 34 // Iterator tests 35 EXPECT_TRUE(testMap.begin() == testMap.end()); 36 37 // Lookup tests 38 EXPECT_EQ(0u, testMap.count(testKey)); 39 EXPECT_EQ(0u, testMap.count(StringRef(testKeyFirst, testKeyLength))); 40 EXPECT_EQ(0u, testMap.count(testKeyStr)); 41 EXPECT_TRUE(testMap.find(testKey) == testMap.end()); 42 EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == 43 testMap.end()); 44 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.end()); 45 } 46 47 void assertSingleItemMap() { 48 // Size tests 49 EXPECT_EQ(1u, testMap.size()); 50 EXPECT_FALSE(testMap.begin() == testMap.end()); 51 EXPECT_FALSE(testMap.empty()); 52 53 // Iterator tests 54 StringMap<uint32_t>::iterator it = testMap.begin(); 55 EXPECT_STREQ(testKey, it->first().data()); 56 EXPECT_EQ(testValue, it->second); 57 ++it; 58 EXPECT_TRUE(it == testMap.end()); 59 60 // Lookup tests 61 EXPECT_EQ(1u, testMap.count(testKey)); 62 EXPECT_EQ(1u, testMap.count(StringRef(testKeyFirst, testKeyLength))); 63 EXPECT_EQ(1u, testMap.count(testKeyStr)); 64 EXPECT_TRUE(testMap.find(testKey) == testMap.begin()); 65 EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == 66 testMap.begin()); 67 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.begin()); 68 } 69}; 70 71const char StringMapTest::testKey[] = "key"; 72const uint32_t StringMapTest::testValue = 1u; 73const char* StringMapTest::testKeyFirst = testKey; 74size_t StringMapTest::testKeyLength = sizeof(testKey) - 1; 75const std::string StringMapTest::testKeyStr(testKey); 76 77// Empty map tests. 78TEST_F(StringMapTest, EmptyMapTest) { 79 assertEmptyMap(); 80} 81 82// Constant map tests. 83TEST_F(StringMapTest, ConstEmptyMapTest) { 84 const StringMap<uint32_t>& constTestMap = testMap; 85 86 // Size tests 87 EXPECT_EQ(0u, constTestMap.size()); 88 EXPECT_TRUE(constTestMap.empty()); 89 90 // Iterator tests 91 EXPECT_TRUE(constTestMap.begin() == constTestMap.end()); 92 93 // Lookup tests 94 EXPECT_EQ(0u, constTestMap.count(testKey)); 95 EXPECT_EQ(0u, constTestMap.count(StringRef(testKeyFirst, testKeyLength))); 96 EXPECT_EQ(0u, constTestMap.count(testKeyStr)); 97 EXPECT_TRUE(constTestMap.find(testKey) == constTestMap.end()); 98 EXPECT_TRUE(constTestMap.find(StringRef(testKeyFirst, testKeyLength)) == 99 constTestMap.end()); 100 EXPECT_TRUE(constTestMap.find(testKeyStr) == constTestMap.end()); 101} 102 103// A map with a single entry. 104TEST_F(StringMapTest, SingleEntryMapTest) { 105 testMap[testKey] = testValue; 106 assertSingleItemMap(); 107} 108 109// Test clear() method. 110TEST_F(StringMapTest, ClearTest) { 111 testMap[testKey] = testValue; 112 testMap.clear(); 113 assertEmptyMap(); 114} 115 116// Test erase(iterator) method. 117TEST_F(StringMapTest, EraseIteratorTest) { 118 testMap[testKey] = testValue; 119 testMap.erase(testMap.begin()); 120 assertEmptyMap(); 121} 122 123// Test erase(value) method. 124TEST_F(StringMapTest, EraseValueTest) { 125 testMap[testKey] = testValue; 126 testMap.erase(testKey); 127 assertEmptyMap(); 128} 129 130// Test inserting two values and erasing one. 131TEST_F(StringMapTest, InsertAndEraseTest) { 132 testMap[testKey] = testValue; 133 testMap["otherKey"] = 2; 134 testMap.erase("otherKey"); 135 assertSingleItemMap(); 136} 137 138TEST_F(StringMapTest, SmallFullMapTest) { 139 // StringMap has a tricky corner case when the map is small (<8 buckets) and 140 // it fills up through a balanced pattern of inserts and erases. This can 141 // lead to inf-loops in some cases (PR13148) so we test it explicitly here. 142 llvm::StringMap<int> Map(2); 143 144 Map["eins"] = 1; 145 Map["zwei"] = 2; 146 Map["drei"] = 3; 147 Map.erase("drei"); 148 Map.erase("eins"); 149 Map["veir"] = 4; 150 Map["funf"] = 5; 151 152 EXPECT_EQ(3u, Map.size()); 153 EXPECT_EQ(0, Map.lookup("eins")); 154 EXPECT_EQ(2, Map.lookup("zwei")); 155 EXPECT_EQ(0, Map.lookup("drei")); 156 EXPECT_EQ(4, Map.lookup("veir")); 157 EXPECT_EQ(5, Map.lookup("funf")); 158} 159 160// A more complex iteration test. 161TEST_F(StringMapTest, IterationTest) { 162 bool visited[100]; 163 164 // Insert 100 numbers into the map 165 for (int i = 0; i < 100; ++i) { 166 std::stringstream ss; 167 ss << "key_" << i; 168 testMap[ss.str()] = i; 169 visited[i] = false; 170 } 171 172 // Iterate over all numbers and mark each one found. 173 for (StringMap<uint32_t>::iterator it = testMap.begin(); 174 it != testMap.end(); ++it) { 175 std::stringstream ss; 176 ss << "key_" << it->second; 177 ASSERT_STREQ(ss.str().c_str(), it->first().data()); 178 visited[it->second] = true; 179 } 180 181 // Ensure every number was visited. 182 for (int i = 0; i < 100; ++i) { 183 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited"; 184 } 185} 186 187// Test StringMapEntry::Create() method. 188TEST_F(StringMapTest, StringMapEntryTest) { 189 StringMap<uint32_t>::value_type* entry = 190 StringMap<uint32_t>::value_type::Create( 191 StringRef(testKeyFirst, testKeyLength), 1u); 192 EXPECT_STREQ(testKey, entry->first().data()); 193 EXPECT_EQ(1u, entry->second); 194 free(entry); 195} 196 197// Test insert() method. 198TEST_F(StringMapTest, InsertTest) { 199 SCOPED_TRACE("InsertTest"); 200 testMap.insert( 201 StringMap<uint32_t>::value_type::Create( 202 StringRef(testKeyFirst, testKeyLength), 203 testMap.getAllocator(), 1u)); 204 assertSingleItemMap(); 205} 206 207// Test insert(pair<K, V>) method 208TEST_F(StringMapTest, InsertPairTest) { 209 bool Inserted; 210 StringMap<uint32_t>::iterator NewIt; 211 std::tie(NewIt, Inserted) = 212 testMap.insert(std::make_pair(testKeyFirst, testValue)); 213 EXPECT_EQ(1u, testMap.size()); 214 EXPECT_EQ(testValue, testMap[testKeyFirst]); 215 EXPECT_EQ(testKeyFirst, NewIt->first()); 216 EXPECT_EQ(testValue, NewIt->second); 217 EXPECT_TRUE(Inserted); 218 219 StringMap<uint32_t>::iterator ExistingIt; 220 std::tie(ExistingIt, Inserted) = 221 testMap.insert(std::make_pair(testKeyFirst, testValue + 1)); 222 EXPECT_EQ(1u, testMap.size()); 223 EXPECT_EQ(testValue, testMap[testKeyFirst]); 224 EXPECT_FALSE(Inserted); 225 EXPECT_EQ(NewIt, ExistingIt); 226} 227 228// Test insert(pair<K, V>) method when rehashing occurs 229TEST_F(StringMapTest, InsertRehashingPairTest) { 230 // Check that the correct iterator is returned when the inserted element is 231 // moved to a different bucket during internal rehashing. This depends on 232 // the particular key, and the implementation of StringMap and HashString. 233 // Changes to those might result in this test not actually checking that. 234 StringMap<uint32_t> t(1); 235 EXPECT_EQ(1u, t.getNumBuckets()); 236 237 StringMap<uint32_t>::iterator It = 238 t.insert(std::make_pair("abcdef", 42)).first; 239 EXPECT_EQ(2u, t.getNumBuckets()); 240 EXPECT_EQ("abcdef", It->first()); 241 EXPECT_EQ(42u, It->second); 242} 243 244// Create a non-default constructable value 245struct StringMapTestStruct { 246 StringMapTestStruct(int i) : i(i) {} 247 StringMapTestStruct() LLVM_DELETED_FUNCTION; 248 int i; 249}; 250 251TEST_F(StringMapTest, NonDefaultConstructable) { 252 StringMap<StringMapTestStruct> t; 253 t.GetOrCreateValue("Test", StringMapTestStruct(123)); 254 StringMap<StringMapTestStruct>::iterator iter = t.find("Test"); 255 ASSERT_NE(iter, t.end()); 256 ASSERT_EQ(iter->second.i, 123); 257} 258 259struct MoveOnly { 260 int i; 261 MoveOnly(int i) : i(i) {} 262 MoveOnly(MoveOnly &&RHS) : i(RHS.i) {} 263 MoveOnly &operator=(MoveOnly &&RHS) { 264 i = RHS.i; 265 return *this; 266 } 267 268private: 269 MoveOnly(const MoveOnly &) LLVM_DELETED_FUNCTION; 270 MoveOnly &operator=(const MoveOnly &) LLVM_DELETED_FUNCTION; 271}; 272 273TEST_F(StringMapTest, MoveOnlyKey) { 274 StringMap<MoveOnly> t; 275 t.GetOrCreateValue("Test", MoveOnly(42)); 276 StringRef Key = "Test"; 277 StringMapEntry<MoveOnly>::Create(Key, MoveOnly(42)) 278 ->Destroy(); 279} 280 281TEST_F(StringMapTest, MoveConstruct) { 282 StringMap<int> A; 283 A.GetOrCreateValue("x", 42); 284 StringMap<int> B = std::move(A); 285 ASSERT_EQ(A.size(), 0u); 286 ASSERT_EQ(B.size(), 1u); 287 ASSERT_EQ(B["x"], 42); 288 ASSERT_EQ(B.count("y"), 0u); 289} 290 291TEST_F(StringMapTest, MoveAssignment) { 292 StringMap<int> A; 293 A["x"] = 42; 294 StringMap<int> B; 295 B["y"] = 117; 296 A = std::move(B); 297 ASSERT_EQ(A.size(), 1u); 298 ASSERT_EQ(B.size(), 0u); 299 ASSERT_EQ(A["y"], 117); 300 ASSERT_EQ(B.count("x"), 0u); 301} 302 303struct Countable { 304 int &InstanceCount; 305 int Number; 306 Countable(int Number, int &InstanceCount) 307 : InstanceCount(InstanceCount), Number(Number) { 308 ++InstanceCount; 309 } 310 Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) { 311 ++InstanceCount; 312 C.Number = -1; 313 } 314 Countable(const Countable &C) 315 : InstanceCount(C.InstanceCount), Number(C.Number) { 316 ++InstanceCount; 317 } 318 Countable &operator=(Countable C) { 319 Number = C.Number; 320 return *this; 321 } 322 ~Countable() { --InstanceCount; } 323}; 324 325TEST_F(StringMapTest, MoveDtor) { 326 int InstanceCount = 0; 327 StringMap<Countable> A; 328 A.GetOrCreateValue("x", Countable(42, InstanceCount)); 329 ASSERT_EQ(InstanceCount, 1); 330 auto I = A.find("x"); 331 ASSERT_NE(I, A.end()); 332 ASSERT_EQ(I->second.Number, 42); 333 334 StringMap<Countable> B; 335 B = std::move(A); 336 ASSERT_EQ(InstanceCount, 1); 337 ASSERT_TRUE(A.empty()); 338 I = B.find("x"); 339 ASSERT_NE(I, B.end()); 340 ASSERT_EQ(I->second.Number, 42); 341 342 B = StringMap<Countable>(); 343 ASSERT_EQ(InstanceCount, 0); 344 ASSERT_TRUE(B.empty()); 345} 346 347} // end anonymous namespace 348