+ /// 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);
+ }
+