From 2a79116940012acaad9cc70efef79d7359f27513 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Tue, 19 Jun 2012 17:40:35 +0000 Subject: Fix PR13148, an inf-loop in StringMap. StringMap suffered from the same bug as DenseMap: when you explicitly construct it with a small number of buckets, you can arrange for the tombstone-based growth path to be followed when the number of buckets was less than '8'. In that case, even with a full map, it would compare '0' as not less than '0', and refuse to grow the table, leading to inf-loops trying to find an empty bucket on the next insertion. The fix is very simple: use '<=' as the comparison. The same fix was applied to DenseMap as well during its recent refactoring. Thanks to Alex Bolz for the great report and test case. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158725 91177308-0d34-0410-b5e6-96231b3b80d8 --- unittests/ADT/StringMapTest.cpp | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'unittests') diff --git a/unittests/ADT/StringMapTest.cpp b/unittests/ADT/StringMapTest.cpp index 66e0493..5bb65cb 100644 --- a/unittests/ADT/StringMapTest.cpp +++ b/unittests/ADT/StringMapTest.cpp @@ -134,6 +134,28 @@ TEST_F(StringMapTest, InsertAndEraseTest) { assertSingleItemMap(); } +TEST_F(StringMapTest, SmallFullMapTest) { + // StringMap has a tricky corner case when the map is small (<8 buckets) and + // it fills up through a balanced pattern of inserts and erases. This can + // lead to inf-loops in some cases (PR13148) so we test it explicitly here. + llvm::StringMap Map(2); + + Map["eins"] = 1; + Map["zwei"] = 2; + Map["drei"] = 3; + Map.erase("drei"); + Map.erase("eins"); + Map["veir"] = 4; + Map["funf"] = 5; + + EXPECT_EQ(3u, Map.size()); + EXPECT_EQ(0, Map.lookup("eins")); + EXPECT_EQ(2, Map.lookup("zwei")); + EXPECT_EQ(0, Map.lookup("drei")); + EXPECT_EQ(4, Map.lookup("veir")); + EXPECT_EQ(5, Map.lookup("funf")); +} + // A more complex iteration test. TEST_F(StringMapTest, IterationTest) { bool visited[100]; -- cgit v1.1