summaryrefslogtreecommitdiff
path: root/include/llvm/ADT/StringMap.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/ADT/StringMap.h')
-rw-r--r--include/llvm/ADT/StringMap.h92
1 files changed, 67 insertions, 25 deletions
diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h
index 700bb9e10ef7b..260275295c993 100644
--- a/include/llvm/ADT/StringMap.h
+++ b/include/llvm/ADT/StringMap.h
@@ -16,6 +16,7 @@
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Allocator.h"
+#include "llvm/Support/PointerLikeTypeTraits.h"
#include <cstring>
#include <utility>
@@ -88,12 +89,15 @@ protected:
/// 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;
+ uintptr_t Val = static_cast<uintptr_t>(-1);
+ Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
+ return reinterpret_cast<StringMapEntryBase *>(Val);
}
unsigned getNumBuckets() const { return NumBuckets; }
@@ -122,9 +126,9 @@ public:
explicit StringMapEntry(unsigned strLen)
: StringMapEntryBase(strLen), second() {}
- template <class InitTy>
- StringMapEntry(unsigned strLen, InitTy &&V)
- : StringMapEntryBase(strLen), second(std::forward<InitTy>(V)) {}
+ template <typename... InitTy>
+ StringMapEntry(unsigned strLen, InitTy &&... InitVals)
+ : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
StringRef getKey() const {
return StringRef(getKeyData(), getKeyLength());
@@ -142,11 +146,11 @@ public:
StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
- /// Create - Create a StringMapEntry for the specified key and default
- /// construct the value.
- template <typename AllocatorTy, typename InitType>
+ /// Create a StringMapEntry for the specified key construct the value using
+ /// \p InitiVals.
+ template <typename AllocatorTy, typename... InitTy>
static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
- InitType &&InitVal) {
+ InitTy &&... InitVals) {
unsigned KeyLength = Key.size();
// Allocate a new item with space for the string at the end and a null
@@ -158,8 +162,8 @@ public:
StringMapEntry *NewItem =
static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
- // Default construct the value.
- new (NewItem) StringMapEntry(KeyLength, std::forward<InitType>(InitVal));
+ // Construct the value.
+ new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
// Copy the string information.
char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
@@ -169,16 +173,11 @@ public:
return NewItem;
}
- template<typename AllocatorTy>
- static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator) {
- return Create(Key, Allocator, ValueTy());
- }
-
/// Create - Create a StringMapEntry with normal malloc/free.
- template<typename InitType>
- static StringMapEntry *Create(StringRef Key, InitType &&InitVal) {
+ template <typename... InitType>
+ static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
MallocAllocator A;
- return Create(Key, A, std::forward<InitType>(InitVal));
+ return Create(Key, A, std::forward<InitType>(InitVal)...);
}
static StringMapEntry *Create(StringRef Key) {
@@ -233,7 +232,7 @@ public:
Allocator(A) {}
StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
- : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {
+ : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
for (const auto &P : List) {
insert(P);
}
@@ -248,7 +247,40 @@ public:
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) {
+ StringMapEntryBase *Bucket = RHS.TheTable[I];
+ if (!Bucket || Bucket == getTombstoneVal()) {
+ TheTable[I] = Bucket;
+ continue;
+ }
+
+ TheTable[I] = MapEntryTy::Create(
+ static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
+ static_cast<MapEntryTy *>(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; }
@@ -295,8 +327,10 @@ public:
return ValueTy();
}
+ /// Lookup the ValueTy for the \p Key, or create a default constructed value
+ /// if the key is not in the map.
ValueTy &operator[](StringRef Key) {
- return insert(std::make_pair(Key, ValueTy())).first->second;
+ return emplace_second(Key).first->second;
}
/// count - Return 1 if the element is in the map, 0 otherwise.
@@ -328,7 +362,16 @@ public:
/// 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);
+ return emplace_second(KV.first, std::move(KV.second));
+ }
+
+ /// Emplace a new element for the specified key 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.
+ template <typename... ArgsTy>
+ std::pair<iterator, bool> emplace_second(StringRef Key, ArgsTy &&... Args) {
+ unsigned BucketNo = LookupBucketFor(Key);
StringMapEntryBase *&Bucket = TheTable[BucketNo];
if (Bucket && Bucket != getTombstoneVal())
return std::make_pair(iterator(TheTable + BucketNo, false),
@@ -336,8 +379,7 @@ public:
if (Bucket == getTombstoneVal())
--NumTombstones;
- Bucket =
- MapEntryTy::Create(KV.first, Allocator, std::move(KV.second));
+ Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
++NumItems;
assert(NumItems + NumTombstones <= NumBuckets);