Add a copy constructor to StringMap

[hfinkel]

Summary

I will soon propose a patch that will require that StringMap have a copy constructor (which it does not currently support). This adds one.

[mehdi_amini]

include/llvm/ADT/StringMap.h

248 ↗

(On Diff #51755)

May be explicit?

261 ↗

(On Diff #51755)

I wonder if we really want to keep the tombstones or if it wouldn't be better to reinsert the elements?

272 ↗

(On Diff #51755)

The hashes have to be inserted as well I think (after the buckets), I may miss where it happened?

[hfinkel]

include/llvm/ADT/StringMap.h

248 ↗

(On Diff #51755)

I don't think that I can -- I need the copy-initialization support for:

CustomNameFuncs = TLI.CustomNameFuncs;

in D18513.

261 ↗

(On Diff #51755)

I don't have a good feeling for this; it seems like this could mean one of two things:

1. We start with the same number of buckets as the RHS; in this case keeping the tombstones vs. not just affects whether we write a 0 or -1 into the pointer array for the empty slot (although insertion will prefer that slot over further probing).
2. Start with a minimal number of buckets. Potentially more memory efficient, but essentially leads to "rehashing" (which in this case means re-probing for all inputs).

What do you prefer?

272 ↗

(On Diff #51755)

Yes; that's what the

HashTable[I] = RHSHashTable[I];

does.

[mehdi_amini]

include/llvm/ADT/StringMap.h

261 ↗

(On Diff #51755)

It seems to me that when looking for an entry in the map, the search stops when it find an empty slot, but continue when there is a tombstone. If I understand your 1), it is just replacing tombstones with empty buckets, but that would break the search for existing entries that are after the tombstones.

The 2) is basically what I was thinking of, eventually allocating the same number of buckets, but indeed reinserting each entry (reusing the existing known hash). Not that I have a strong preference, I was rather wondering if you considered this and what is the rational for one or the other (and if there is a reason, I'd rather have it documented in the code for future reference).
I hope David could chime in with an opinion.

272 ↗

(On Diff #51755)

Obviously...

[hfinkel]

include/llvm/ADT/StringMap.h

261 ↗

(On Diff #51755)

It seems to me that when looking for an entry in the map, the search stops when it find an empty slot, but continue when there is a tombstone. If I understand your 1), it is just replacing tombstones with empty buckets, but that would break the search for existing entries that are after the tombstones.

I believe you're correct; scratch that option.

The 2) is basically what I was thinking of, eventually allocating the same number of buckets, but indeed reinserting each entry (reusing the existing known hash). Not that I have a strong preference, I was rather wondering if you considered this and what is the rational for one or the other (and if there is a reason, I'd rather have it documented in the code for future reference).

My thought was the following: Most StringMaps don't have many tombstones, because many use cases don't ever (or only rarely) delete things from their string maps. As a result, just copying the structure as-is (any tombstones included) will be faster than re-probing for all keys with little downside.

I hope David could chime in with an opinion.

[mehdi_amini]

include/llvm/ADT/StringMap.h

261 ↗

(On Diff #51755)

Most StringMaps don't have many tombstones, because many use cases don't ever (or only rarely) delete things from their string maps.

That sounds a good argument to me!

[mehdi_amini]

include/llvm/ADT/StringMap.h

248 ↗

(On Diff #51755)

The issue is only because the copy assignment operator is defined as:

StringMap &operator=(StringMap RHS) {
    StringMapImpl::swap(RHS);
    std::swap(Allocator, RHS.Allocator);
    return *this;
  }

I think we could change it to:

StringMap &operator=(const StringMap &RHS) {
    StringMap Tmp(RHS);
    StringMapImpl::swap(Tmp);
    std::swap(Allocator, Tmp.Allocator);
    return *this;
  }
StringMap &operator=(const StringMap &&RHS) {
    std::swap(Allocator, std::move(RHS.Allocator));
    StringMapImpl::swap(std::move(RHS));
    return *this;
  }

Now the only thing that it buys us is a protection against unexpected/unintended copy construction for a StringMap, is it compelling enough?

[hfinkel]

include/llvm/ADT/StringMap.h

248 ↗

(On Diff #51755)

Now the only thing that it buys us is a protection against unexpected/unintended copy construction for a StringMap, is it compelling enough?

Personally, I don't see a reason to be so careful about copying a StringMap, more careful, that is, than for other similar data structures. We have non-explicit copy constructors on DenseMap, etc. Everyone needs to be just as careful about copying those. As a user of containers, I tend to find such restrictions annoying. Obviously, people have different opinions on this topic ;)

[mehdi_amini]

include/llvm/ADT/StringMap.h

94 ↗

(On Diff #51755)

private -> public is a bit rough, could it be protected maybe?

[hfinkel]

include/llvm/ADT/StringMap.h

94 ↗

(On Diff #51755)

Yes, it is (all of the functions in this block are protected).

[mehdi_amini]

Thanks for all the answers. LGTM then.

include/llvm/ADT/StringMap.h

94 ↗

(On Diff #51755)

OK nevermind then...

llvm/trunk/include/llvm/ADT/StringMap.h

protected:
   /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
   /// delete it.  This aborts if the value isn't in the table.
   void RemoveKey(StringMapEntryBase *V);
 
   /// RemoveKey - Remove the StringMapEntry for the specified key from the
   /// table, returning it.  If the key is not in the table, this returns null.
   StringMapEntryBase *RemoveKey(StringRef Key);
 
-private:
+  /// Allocate the table with the specified number of buckets and otherwise
+  /// setup the map as empty.
   void init(unsigned Size);
 
 public:
   static StringMapEntryBase *getTombstoneVal() {
     return (StringMapEntryBase*)-1;
   }
 
   unsigned getNumBuckets() const { return NumBuckets; }
StringMap(StringMap &&RHS)
       : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
 
   StringMap &operator=(StringMap RHS) {
     StringMapImpl::swap(RHS);
     std::swap(Allocator, RHS.Allocator);
     return *this;
   }
 
-  // FIXME: Implement copy operations if/when they're needed.
+  StringMap(const StringMap &RHS) :
+    StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
+    Allocator(RHS.Allocator) {
+    if (RHS.empty())
+      return;
+
+    // Allocate TheTable of the same size as RHS's TheTable, and set the
+    // sentinel appropriately (and NumBuckets).
+    init(RHS.NumBuckets);
+    unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
+             *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
+
+    NumItems = RHS.NumItems;
+    NumTombstones = RHS.NumTombstones;
+    for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
+      MapEntryTy *Bucket = ((MapEntryTy**) RHS.TheTable)[I];
+      if (!Bucket || Bucket == getTombstoneVal()) {
+        TheTable[I] = Bucket;
+        continue;
+      }
+
+      TheTable[I] = MapEntryTy::Create(Bucket->getKey(), Allocator,
+                                       Bucket->getValue());
+      HashTable[I] = RHSHashTable[I];
+    }
+
+    // Note that here we've copied everything from the RHS into this object,
+    // tombstones included. We could, instead, have re-probed for each key to
+    // instantiate this new object without any tombstone buckets. The
+    // assumption here is that items are rarely deleted from most StringMaps,
+    // and so tombstones are rare, so the cost of re-probing for all inputs is
+    // not worthwhile.
+  }
 
   AllocatorTy &getAllocator() { return Allocator; }
   const AllocatorTy &getAllocator() const { return Allocator; }
 
   typedef const char* key_type;
   typedef ValueTy mapped_type;
   typedef StringMapEntry<ValueTy> value_type;
   typedef size_t size_type;

llvm/trunk/unittests/ADT/StringMapTest.cpp

TEST_F(StringMapTest, SmallFullMapTest) {
   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"));
 }
 
+TEST_F(StringMapTest, CopyCtorTest) {
+  llvm::StringMap<int> Map;
+
+  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"));
+
+  llvm::StringMap<int> Map2(Map);
+  EXPECT_EQ(3u, Map2.size());
+  EXPECT_EQ(0, Map2.lookup("eins"));
+  EXPECT_EQ(2, Map2.lookup("zwei"));
+  EXPECT_EQ(0, Map2.lookup("drei"));
+  EXPECT_EQ(4, Map2.lookup("veir"));
+  EXPECT_EQ(5, Map2.lookup("funf"));
+}
+
 // A more complex iteration test.
 TEST_F(StringMapTest, IterationTest) {
   bool visited[100];
 
   // Insert 100 numbers into the map
   for (int i = 0; i < 100; ++i) {
     std::stringstream ss;
     ss << "key_" << i;