diff options
author | David Blaikie <dblaikie@gmail.com> | 2014-06-19 20:08:56 +0000 |
---|---|---|
committer | David Blaikie <dblaikie@gmail.com> | 2014-06-19 20:08:56 +0000 |
commit | 4110a7ac7ac9f5814b6828e498efdb3e75110f66 (patch) | |
tree | 86f40c119d9305e45d66982e4abf5f834f66d421 | |
parent | 594f05c8dae6ec0b08694a1d439aee8bca18a47d (diff) | |
download | llvm-4110a7ac7ac9f5814b6828e498efdb3e75110f66.tar.gz llvm-4110a7ac7ac9f5814b6828e498efdb3e75110f66.tar.bz2 llvm-4110a7ac7ac9f5814b6828e498efdb3e75110f66.tar.xz |
Add StringMap::insert(pair) consistent with the standard associative container concept.
Patch by Agustín Bergé.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211309 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/ADT/StringMap.h | 43 | ||||
-rw-r--r-- | lib/Support/StringMap.cpp | 10 | ||||
-rw-r--r-- | unittests/ADT/StringMapTest.cpp | 38 |
3 files changed, 70 insertions, 21 deletions
diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 5b18681879..c40e5e2b3d 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -64,7 +64,7 @@ protected: } StringMapImpl(unsigned InitSize, unsigned ItemSize); - void RehashTable(); + unsigned RehashTable(unsigned BucketNo = 0); /// 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,6 +323,28 @@ 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<iterator, bool> insert(std::pair<StringRef, ValueTy> 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; @@ -346,24 +368,7 @@ public: /// return. template <typename InitTy> MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { - unsigned BucketNo = LookupBucketFor(Key); - StringMapEntryBase *&Bucket = TheTable[BucketNo]; - if (Bucket && Bucket != getTombstoneVal()) - return *static_cast<MapEntryTy*>(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; + return *insert(std::make_pair(Key, std::move(Val))).first; } MapEntryTy &GetOrCreateValue(StringRef Key) { diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp index 72a6d822d2..ddb73494ff 100644 --- a/lib/Support/StringMap.cpp +++ b/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. -void StringMapImpl::RehashTable() { +unsigned StringMapImpl::RehashTable(unsigned BucketNo) { unsigned NewSize; unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); @@ -193,9 +193,10 @@ void StringMapImpl::RehashTable() { } else if (NumBuckets-(NumItems+NumTombstones) <= NumBuckets/8) { NewSize = NumBuckets; } else { - return; + return BucketNo; } + unsigned NewBucketNo = BucketNo; // Allocate one extra bucket which will always be non-empty. This allows the // iterators to stop at end. StringMapEntryBase **NewTableArray = @@ -215,6 +216,8 @@ void StringMapImpl::RehashTable() { if (!NewTableArray[NewBucket]) { NewTableArray[FullHash & (NewSize-1)] = Bucket; NewHashArray[FullHash & (NewSize-1)] = FullHash; + if (I == BucketNo) + NewBucketNo = NewBucket; continue; } @@ -227,6 +230,8 @@ void StringMapImpl::RehashTable() { // Finally found a slot. Fill it in. NewTableArray[NewBucket] = Bucket; NewHashArray[NewBucket] = FullHash; + if (I == BucketNo) + NewBucketNo = NewBucket; } } @@ -235,4 +240,5 @@ void StringMapImpl::RehashTable() { TheTable = NewTableArray; NumBuckets = NewSize; NumTombstones = 0; + return NewBucketNo; } diff --git a/unittests/ADT/StringMapTest.cpp b/unittests/ADT/StringMapTest.cpp index 70eec873ed..215d3dfa02 100644 --- a/unittests/ADT/StringMapTest.cpp +++ b/unittests/ADT/StringMapTest.cpp @@ -10,6 +10,7 @@ #include "gtest/gtest.h" #include "llvm/ADT/StringMap.h" #include "llvm/Support/DataTypes.h" +#include <tuple> using namespace llvm; namespace { @@ -203,6 +204,43 @@ TEST_F(StringMapTest, InsertTest) { assertSingleItemMap(); } +// Test insert(pair<K, V>) method +TEST_F(StringMapTest, InsertPairTest) { + bool Inserted; + StringMap<uint32_t>::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<uint32_t>::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<K, V>) 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<uint32_t> t(1); + EXPECT_EQ(1u, t.getNumBuckets()); + + StringMap<uint32_t>::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) {} |