From 393b2b594f39985e10f5dfec25909975f905a279 Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Fri, 20 Jun 2014 00:23:03 +0000 Subject: [PATCH] Revert "Add StringMap::insert(pair) consistent with the standard associative container concept." This reverts commit r211309. It looks like it broke some bots: http://lab.llvm.org:8011/builders/clang-x86_64-ubuntu-gdb-75/builds/15563/steps/compile/logs/stdio llvm-svn: 211328 --- llvm/include/llvm/ADT/StringMap.h | 43 ++++++++++++++++-------------------- llvm/lib/Support/StringMap.cpp | 10 ++------- llvm/unittests/ADT/StringMapTest.cpp | 38 ------------------------------- 3 files changed, 21 insertions(+), 70 deletions(-) diff --git a/llvm/include/llvm/ADT/StringMap.h b/llvm/include/llvm/ADT/StringMap.h index c40e5e2..5b18681 100644 --- a/llvm/include/llvm/ADT/StringMap.h +++ b/llvm/include/llvm/ADT/StringMap.h @@ -64,7 +64,7 @@ protected: } StringMapImpl(unsigned InitSize, unsigned ItemSize); - unsigned RehashTable(unsigned BucketNo = 0); + void RehashTable(); /// LookupBucketFor - Look up the bucket that the specified string should end /// up in. If it already exists as a key in the map, the Item pointer for the @@ -323,28 +323,6 @@ public: return true; } - /// insert - Inserts the specified key/value pair into the map if the key - /// isn't already in the map. The bool component of the returned pair is true - /// if and only if the insertion takes place, and the iterator component of - /// the pair points to the element with key equivalent to the key of the pair. - std::pair insert(std::pair KV) { - unsigned BucketNo = LookupBucketFor(KV.first); - StringMapEntryBase *&Bucket = TheTable[BucketNo]; - if (Bucket && Bucket != getTombstoneVal()) - return std::make_pair(iterator(TheTable + BucketNo, false), - false); // Already exists in map. - - if (Bucket == getTombstoneVal()) - --NumTombstones; - Bucket = - MapEntryTy::Create(KV.first, Allocator, std::move(KV.second)); - ++NumItems; - assert(NumItems + NumTombstones <= NumBuckets); - - BucketNo = RehashTable(BucketNo); - return std::make_pair(iterator(TheTable + BucketNo, false), true); - } - // clear - Empties out the StringMap void clear() { if (empty()) return; @@ -368,7 +346,24 @@ public: /// return. template MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { - return *insert(std::make_pair(Key, std::move(Val))).first; + unsigned BucketNo = LookupBucketFor(Key); + StringMapEntryBase *&Bucket = TheTable[BucketNo]; + if (Bucket && Bucket != getTombstoneVal()) + return *static_cast(Bucket); + + MapEntryTy *NewItem = MapEntryTy::Create(Key, Allocator, std::move(Val)); + + if (Bucket == getTombstoneVal()) + --NumTombstones; + ++NumItems; + assert(NumItems + NumTombstones <= NumBuckets); + + // Fill in the bucket for the hash table. The FullHashValue was already + // filled in by LookupBucketFor. + Bucket = NewItem; + + RehashTable(); + return *NewItem; } MapEntryTy &GetOrCreateValue(StringRef Key) { diff --git a/llvm/lib/Support/StringMap.cpp b/llvm/lib/Support/StringMap.cpp index ddb7349..72a6d82 100644 --- a/llvm/lib/Support/StringMap.cpp +++ b/llvm/lib/Support/StringMap.cpp @@ -181,7 +181,7 @@ StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { /// RehashTable - Grow the table, redistributing values into the buckets with /// the appropriate mod-of-hashtable-size. -unsigned StringMapImpl::RehashTable(unsigned BucketNo) { +void StringMapImpl::RehashTable() { unsigned NewSize; unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); @@ -193,10 +193,9 @@ unsigned StringMapImpl::RehashTable(unsigned BucketNo) { } else if (NumBuckets-(NumItems+NumTombstones) <= NumBuckets/8) { NewSize = NumBuckets; } else { - return BucketNo; + return; } - unsigned NewBucketNo = BucketNo; // Allocate one extra bucket which will always be non-empty. This allows the // iterators to stop at end. StringMapEntryBase **NewTableArray = @@ -216,8 +215,6 @@ unsigned StringMapImpl::RehashTable(unsigned BucketNo) { if (!NewTableArray[NewBucket]) { NewTableArray[FullHash & (NewSize-1)] = Bucket; NewHashArray[FullHash & (NewSize-1)] = FullHash; - if (I == BucketNo) - NewBucketNo = NewBucket; continue; } @@ -230,8 +227,6 @@ unsigned StringMapImpl::RehashTable(unsigned BucketNo) { // Finally found a slot. Fill it in. NewTableArray[NewBucket] = Bucket; NewHashArray[NewBucket] = FullHash; - if (I == BucketNo) - NewBucketNo = NewBucket; } } @@ -240,5 +235,4 @@ unsigned StringMapImpl::RehashTable(unsigned BucketNo) { TheTable = NewTableArray; NumBuckets = NewSize; NumTombstones = 0; - return NewBucketNo; } diff --git a/llvm/unittests/ADT/StringMapTest.cpp b/llvm/unittests/ADT/StringMapTest.cpp index 215d3df..70eec87 100644 --- a/llvm/unittests/ADT/StringMapTest.cpp +++ b/llvm/unittests/ADT/StringMapTest.cpp @@ -10,7 +10,6 @@ #include "gtest/gtest.h" #include "llvm/ADT/StringMap.h" #include "llvm/Support/DataTypes.h" -#include using namespace llvm; namespace { @@ -204,43 +203,6 @@ TEST_F(StringMapTest, InsertTest) { assertSingleItemMap(); } -// Test insert(pair) method -TEST_F(StringMapTest, InsertPairTest) { - bool Inserted; - StringMap::iterator NewIt; - std::tie(NewIt, Inserted) = - testMap.insert(std::make_pair(testKeyFirst, testValue)); - EXPECT_EQ(1u, testMap.size()); - EXPECT_EQ(testValue, testMap[testKeyFirst]); - EXPECT_EQ(testKeyFirst, NewIt->first()); - EXPECT_EQ(testValue, NewIt->second); - EXPECT_TRUE(Inserted); - - StringMap::iterator ExistingIt; - std::tie(ExistingIt, Inserted) = - testMap.insert(std::make_pair(testKeyFirst, testValue + 1)); - EXPECT_EQ(1u, testMap.size()); - EXPECT_EQ(testValue, testMap[testKeyFirst]); - EXPECT_FALSE(Inserted); - EXPECT_EQ(NewIt, ExistingIt); -} - -// Test insert(pair) method when rehashing occurs -TEST_F(StringMapTest, InsertRehashingPairTest) { - // Check that the correct iterator is returned when the inserted element is - // moved to a different bucket during internal rehashing. This depends on - // the particular key, and the implementation of StringMap and HashString. - // Changes to those might result in this test not actually checking that. - StringMap t(1); - EXPECT_EQ(1u, t.getNumBuckets()); - - StringMap::iterator It = - t.insert(std::make_pair("abcdef", 42)).first; - EXPECT_EQ(2u, t.getNumBuckets()); - EXPECT_EQ("abcdef", It->first()); - EXPECT_EQ(42u, It->second); -} - // Create a non-default constructable value struct StringMapTestStruct { StringMapTestStruct(int i) : i(i) {} -- 2.7.4