StringMapTest.cpp revision 2a79116940012acaad9cc70efef79d7359f27513
11ed3663b49c7a00fa2bec8a70ee59fe05b9173ecBill Wendling//===- llvm/unittest/ADT/StringMapMap.cpp - StringMap unit tests ----------===// 28bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman// 38bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman// The LLVM Compiler Infrastructure 48bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman// 58bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman// This file is distributed under the University of Illinois Open Source 68bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman// License. See LICENSE.TXT for details. 78bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman// 88bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman//===----------------------------------------------------------------------===// 98bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 108bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman#include "gtest/gtest.h" 118bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman#include "llvm/ADT/StringMap.h" 121f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/DataTypes.h" 138bb5e9901346f448461289f2d0079ed6d534b571Misha Brukmanusing namespace llvm; 148bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 158bb5e9901346f448461289f2d0079ed6d534b571Misha Brukmannamespace { 168bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 178bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman// Test fixture 188bb5e9901346f448461289f2d0079ed6d534b571Misha Brukmanclass StringMapTest : public testing::Test { 198bb5e9901346f448461289f2d0079ed6d534b571Misha Brukmanprotected: 208bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman StringMap<uint32_t> testMap; 218bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 228bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman static const char testKey[]; 238bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman static const uint32_t testValue; 248bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman static const char* testKeyFirst; 256316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar static size_t testKeyLength; 268bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman static const std::string testKeyStr; 278bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 288bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman void assertEmptyMap() { 298bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Size tests 308bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_EQ(0u, testMap.size()); 318bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_TRUE(testMap.empty()); 328bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 338bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Iterator tests 348bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_TRUE(testMap.begin() == testMap.end()); 358bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 368bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Lookup tests 378bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_EQ(0u, testMap.count(testKey)); 386316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar EXPECT_EQ(0u, testMap.count(StringRef(testKeyFirst, testKeyLength))); 398bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_EQ(0u, testMap.count(testKeyStr)); 408bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_TRUE(testMap.find(testKey) == testMap.end()); 416316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == 426316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar testMap.end()); 438bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_TRUE(testMap.find(testKeyStr) == testMap.end()); 448bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman } 458bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 468bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman void assertSingleItemMap() { 478bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Size tests 488bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_EQ(1u, testMap.size()); 498bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_FALSE(testMap.begin() == testMap.end()); 508bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_FALSE(testMap.empty()); 518bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 528bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Iterator tests 538bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman StringMap<uint32_t>::iterator it = testMap.begin(); 54d7c027322ebccd9666c3f46d9a5236ba76fda434Chris Lattner EXPECT_STREQ(testKey, it->first().data()); 558bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_EQ(testValue, it->second); 568bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman ++it; 578bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_TRUE(it == testMap.end()); 588bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 598bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Lookup tests 608bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_EQ(1u, testMap.count(testKey)); 616316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar EXPECT_EQ(1u, testMap.count(StringRef(testKeyFirst, testKeyLength))); 628bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_EQ(1u, testMap.count(testKeyStr)); 638bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_TRUE(testMap.find(testKey) == testMap.begin()); 646316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == 656316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar testMap.begin()); 668bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_TRUE(testMap.find(testKeyStr) == testMap.begin()); 678bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman } 688bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman}; 698bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 708bb5e9901346f448461289f2d0079ed6d534b571Misha Brukmanconst char StringMapTest::testKey[] = "key"; 718bb5e9901346f448461289f2d0079ed6d534b571Misha Brukmanconst uint32_t StringMapTest::testValue = 1u; 728bb5e9901346f448461289f2d0079ed6d534b571Misha Brukmanconst char* StringMapTest::testKeyFirst = testKey; 736316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbarsize_t StringMapTest::testKeyLength = sizeof(testKey) - 1; 748bb5e9901346f448461289f2d0079ed6d534b571Misha Brukmanconst std::string StringMapTest::testKeyStr(testKey); 758bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 766b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling// Empty map tests. 778bb5e9901346f448461289f2d0079ed6d534b571Misha BrukmanTEST_F(StringMapTest, EmptyMapTest) { 788bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman assertEmptyMap(); 798bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman} 808bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 816b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling// Constant map tests. 828bb5e9901346f448461289f2d0079ed6d534b571Misha BrukmanTEST_F(StringMapTest, ConstEmptyMapTest) { 838bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman const StringMap<uint32_t>& constTestMap = testMap; 848bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 858bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Size tests 868bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_EQ(0u, constTestMap.size()); 878bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_TRUE(constTestMap.empty()); 888bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 898bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Iterator tests 908bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_TRUE(constTestMap.begin() == constTestMap.end()); 918bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 928bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Lookup tests 938bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_EQ(0u, constTestMap.count(testKey)); 946316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar EXPECT_EQ(0u, constTestMap.count(StringRef(testKeyFirst, testKeyLength))); 958bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_EQ(0u, constTestMap.count(testKeyStr)); 968bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_TRUE(constTestMap.find(testKey) == constTestMap.end()); 976316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar EXPECT_TRUE(constTestMap.find(StringRef(testKeyFirst, testKeyLength)) == 986b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling constTestMap.end()); 998bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman EXPECT_TRUE(constTestMap.find(testKeyStr) == constTestMap.end()); 1008bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman} 1018bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 1026b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling// A map with a single entry. 1038bb5e9901346f448461289f2d0079ed6d534b571Misha BrukmanTEST_F(StringMapTest, SingleEntryMapTest) { 1048bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman testMap[testKey] = testValue; 1058bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman assertSingleItemMap(); 1068bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman} 1078bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 1086b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling// Test clear() method. 1098bb5e9901346f448461289f2d0079ed6d534b571Misha BrukmanTEST_F(StringMapTest, ClearTest) { 1108bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman testMap[testKey] = testValue; 1118bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman testMap.clear(); 1128bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman assertEmptyMap(); 1138bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman} 1148bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 1156b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling// Test erase(iterator) method. 1168bb5e9901346f448461289f2d0079ed6d534b571Misha BrukmanTEST_F(StringMapTest, EraseIteratorTest) { 1178bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman testMap[testKey] = testValue; 1188bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman testMap.erase(testMap.begin()); 1198bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman assertEmptyMap(); 1208bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman} 1218bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 1226b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling// Test erase(value) method. 1238bb5e9901346f448461289f2d0079ed6d534b571Misha BrukmanTEST_F(StringMapTest, EraseValueTest) { 1248bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman testMap[testKey] = testValue; 1258bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman testMap.erase(testKey); 1268bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman assertEmptyMap(); 1278bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman} 1288bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 1296b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling// Test inserting two values and erasing one. 1308bb5e9901346f448461289f2d0079ed6d534b571Misha BrukmanTEST_F(StringMapTest, InsertAndEraseTest) { 1318bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman testMap[testKey] = testValue; 1328bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman testMap["otherKey"] = 2; 1338bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman testMap.erase("otherKey"); 1348bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman assertSingleItemMap(); 1358bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman} 1368bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 1372a79116940012acaad9cc70efef79d7359f27513Chandler CarruthTEST_F(StringMapTest, SmallFullMapTest) { 1382a79116940012acaad9cc70efef79d7359f27513Chandler Carruth // StringMap has a tricky corner case when the map is small (<8 buckets) and 1392a79116940012acaad9cc70efef79d7359f27513Chandler Carruth // it fills up through a balanced pattern of inserts and erases. This can 1402a79116940012acaad9cc70efef79d7359f27513Chandler Carruth // lead to inf-loops in some cases (PR13148) so we test it explicitly here. 1412a79116940012acaad9cc70efef79d7359f27513Chandler Carruth llvm::StringMap<int> Map(2); 1422a79116940012acaad9cc70efef79d7359f27513Chandler Carruth 1432a79116940012acaad9cc70efef79d7359f27513Chandler Carruth Map["eins"] = 1; 1442a79116940012acaad9cc70efef79d7359f27513Chandler Carruth Map["zwei"] = 2; 1452a79116940012acaad9cc70efef79d7359f27513Chandler Carruth Map["drei"] = 3; 1462a79116940012acaad9cc70efef79d7359f27513Chandler Carruth Map.erase("drei"); 1472a79116940012acaad9cc70efef79d7359f27513Chandler Carruth Map.erase("eins"); 1482a79116940012acaad9cc70efef79d7359f27513Chandler Carruth Map["veir"] = 4; 1492a79116940012acaad9cc70efef79d7359f27513Chandler Carruth Map["funf"] = 5; 1502a79116940012acaad9cc70efef79d7359f27513Chandler Carruth 1512a79116940012acaad9cc70efef79d7359f27513Chandler Carruth EXPECT_EQ(3u, Map.size()); 1522a79116940012acaad9cc70efef79d7359f27513Chandler Carruth EXPECT_EQ(0, Map.lookup("eins")); 1532a79116940012acaad9cc70efef79d7359f27513Chandler Carruth EXPECT_EQ(2, Map.lookup("zwei")); 1542a79116940012acaad9cc70efef79d7359f27513Chandler Carruth EXPECT_EQ(0, Map.lookup("drei")); 1552a79116940012acaad9cc70efef79d7359f27513Chandler Carruth EXPECT_EQ(4, Map.lookup("veir")); 1562a79116940012acaad9cc70efef79d7359f27513Chandler Carruth EXPECT_EQ(5, Map.lookup("funf")); 1572a79116940012acaad9cc70efef79d7359f27513Chandler Carruth} 1582a79116940012acaad9cc70efef79d7359f27513Chandler Carruth 1596b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling// A more complex iteration test. 1608bb5e9901346f448461289f2d0079ed6d534b571Misha BrukmanTEST_F(StringMapTest, IterationTest) { 1618bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman bool visited[100]; 1628bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 1638bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Insert 100 numbers into the map 1648bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman for (int i = 0; i < 100; ++i) { 1658bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman std::stringstream ss; 1668bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman ss << "key_" << i; 1678bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman testMap[ss.str()] = i; 1688bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman visited[i] = false; 1698bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman } 1708bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 1718bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Iterate over all numbers and mark each one found. 1728bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman for (StringMap<uint32_t>::iterator it = testMap.begin(); 1738bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman it != testMap.end(); ++it) { 1748bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman std::stringstream ss; 1758bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman ss << "key_" << it->second; 176d7c027322ebccd9666c3f46d9a5236ba76fda434Chris Lattner ASSERT_STREQ(ss.str().c_str(), it->first().data()); 1778bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman visited[it->second] = true; 1788bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman } 1798bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 1808bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman // Ensure every number was visited. 1818bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman for (int i = 0; i < 100; ++i) { 1828bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited"; 1838bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman } 1848bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman} 1858bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 1866b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling} // end anonymous namespace 1876b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling 1886b223d71e5e5e123137f0f056541de4212f5c878Bill Wendlingnamespace llvm { 1896b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling 1906b223d71e5e5e123137f0f056541de4212f5c878Bill Wendlingtemplate <> 1916b223d71e5e5e123137f0f056541de4212f5c878Bill Wendlingclass StringMapEntryInitializer<uint32_t> { 1926b223d71e5e5e123137f0f056541de4212f5c878Bill Wendlingpublic: 1936b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling template <typename InitTy> 1946b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling static void Initialize(StringMapEntry<uint32_t> &T, InitTy InitVal) { 1956b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling T.second = InitVal; 1966b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling } 1976b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling}; 1986b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling 1996b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling} // end llvm namespace 2006b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling 2016b223d71e5e5e123137f0f056541de4212f5c878Bill Wendlingnamespace { 2026b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling 2036b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling// Test StringMapEntry::Create() method. 2046b223d71e5e5e123137f0f056541de4212f5c878Bill WendlingTEST_F(StringMapTest, StringMapEntryTest) { 2056b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling StringMap<uint32_t>::value_type* entry = 2066b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling StringMap<uint32_t>::value_type::Create( 2076316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar testKeyFirst, testKeyFirst + testKeyLength, 1u); 208d7c027322ebccd9666c3f46d9a5236ba76fda434Chris Lattner EXPECT_STREQ(testKey, entry->first().data()); 2096b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling EXPECT_EQ(1u, entry->second); 210d8735356a36fb04dfcfd9520f9785c0c3739b4a1Jeffrey Yasskin free(entry); 2116b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling} 2126b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling 2136b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling// Test insert() method. 2146b223d71e5e5e123137f0f056541de4212f5c878Bill WendlingTEST_F(StringMapTest, InsertTest) { 2156b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling SCOPED_TRACE("InsertTest"); 2166b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling testMap.insert( 2176b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling StringMap<uint32_t>::value_type::Create( 2186316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar testKeyFirst, testKeyFirst + testKeyLength, 2196316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar testMap.getAllocator(), 1u)); 2206b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling assertSingleItemMap(); 2218bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman} 2226b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling 2236b223d71e5e5e123137f0f056541de4212f5c878Bill Wendling} // end anonymous namespace 224