1 //===- StringMap.h - String Hash table map interface ------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the StringMap class.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ADT_STRINGMAP_H
15 #define LLVM_ADT_STRINGMAP_H
17 #include "llvm/ADT/StringRef.h"
18 #include "llvm/ADT/iterator.h"
19 #include "llvm/ADT/iterator_range.h"
20 #include "llvm/Support/Allocator.h"
21 #include "llvm/Support/PointerLikeTypeTraits.h"
22 #include "llvm/Support/ErrorHandling.h"
28 #include <initializer_list>
34 template<typename ValueTy> class StringMapConstIterator;
35 template<typename ValueTy> class StringMapIterator;
36 template<typename ValueTy> class StringMapKeyIterator;
38 /// StringMapEntryBase - Shared base class of StringMapEntry instances.
39 class StringMapEntryBase {
43 explicit StringMapEntryBase(size_t Len) : StrLen(Len) {}
45 size_t getKeyLength() const { return StrLen; }
48 /// StringMapImpl - This is the base class of StringMap that is shared among
49 /// all of its instantiations.
52 // Array of NumBuckets pointers to entries, null pointers are holes.
53 // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
54 // by an array of the actual hash values as unsigned integers.
55 StringMapEntryBase **TheTable = nullptr;
56 unsigned NumBuckets = 0;
57 unsigned NumItems = 0;
58 unsigned NumTombstones = 0;
62 explicit StringMapImpl(unsigned itemSize)
63 : ItemSize(itemSize) {}
64 StringMapImpl(StringMapImpl &&RHS)
65 : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
66 NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
67 ItemSize(RHS.ItemSize) {
68 RHS.TheTable = nullptr;
71 RHS.NumTombstones = 0;
74 StringMapImpl(unsigned InitSize, unsigned ItemSize);
75 unsigned RehashTable(unsigned BucketNo = 0);
77 /// LookupBucketFor - Look up the bucket that the specified string should end
78 /// up in. If it already exists as a key in the map, the Item pointer for the
79 /// specified bucket will be non-null. Otherwise, it will be null. In either
80 /// case, the FullHashValue field of the bucket will be set to the hash value
82 unsigned LookupBucketFor(StringRef Key);
84 /// FindKey - Look up the bucket that contains the specified key. If it exists
85 /// in the map, return the bucket number of the key. Otherwise return -1.
86 /// This does not modify the map.
87 int FindKey(StringRef Key) const;
89 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
90 /// delete it. This aborts if the value isn't in the table.
91 void RemoveKey(StringMapEntryBase *V);
93 /// RemoveKey - Remove the StringMapEntry for the specified key from the
94 /// table, returning it. If the key is not in the table, this returns null.
95 StringMapEntryBase *RemoveKey(StringRef Key);
97 /// Allocate the table with the specified number of buckets and otherwise
98 /// setup the map as empty.
99 void init(unsigned Size);
102 static StringMapEntryBase *getTombstoneVal() {
103 uintptr_t Val = static_cast<uintptr_t>(-1);
104 Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
105 return reinterpret_cast<StringMapEntryBase *>(Val);
108 unsigned getNumBuckets() const { return NumBuckets; }
109 unsigned getNumItems() const { return NumItems; }
111 bool empty() const { return NumItems == 0; }
112 unsigned size() const { return NumItems; }
114 void swap(StringMapImpl &Other) {
115 std::swap(TheTable, Other.TheTable);
116 std::swap(NumBuckets, Other.NumBuckets);
117 std::swap(NumItems, Other.NumItems);
118 std::swap(NumTombstones, Other.NumTombstones);
122 /// StringMapEntry - This is used to represent one value that is inserted into
123 /// a StringMap. It contains the Value itself and the key: the string length
125 template<typename ValueTy>
126 class StringMapEntry : public StringMapEntryBase {
130 explicit StringMapEntry(size_t strLen)
131 : StringMapEntryBase(strLen), second() {}
132 template <typename... InitTy>
133 StringMapEntry(size_t strLen, InitTy &&... InitVals)
134 : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
135 StringMapEntry(StringMapEntry &E) = delete;
137 StringRef getKey() const {
138 return StringRef(getKeyData(), getKeyLength());
141 const ValueTy &getValue() const { return second; }
142 ValueTy &getValue() { return second; }
144 void setValue(const ValueTy &V) { second = V; }
146 /// getKeyData - Return the start of the string data that is the key for this
147 /// value. The string data is always stored immediately after the
148 /// StringMapEntry object.
149 const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
151 StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
153 /// Create a StringMapEntry for the specified key construct the value using
155 template <typename AllocatorTy, typename... InitTy>
156 static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
157 InitTy &&... InitVals) {
158 size_t KeyLength = Key.size();
160 // Allocate a new item with space for the string at the end and a null
162 size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1;
163 size_t Alignment = alignof(StringMapEntry);
165 StringMapEntry *NewItem =
166 static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
167 assert(NewItem && "Unhandled out-of-memory");
169 // Construct the value.
170 new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
172 // Copy the string information.
173 char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
175 memcpy(StrBuffer, Key.data(), KeyLength);
176 StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
180 /// Create - Create a StringMapEntry with normal malloc/free.
181 template <typename... InitType>
182 static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
184 return Create(Key, A, std::forward<InitType>(InitVal)...);
187 static StringMapEntry *Create(StringRef Key) {
188 return Create(Key, ValueTy());
191 /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
192 /// into a StringMapEntry, return the StringMapEntry itself.
193 static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
194 char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
195 return *reinterpret_cast<StringMapEntry*>(Ptr);
198 /// Destroy - Destroy this StringMapEntry, releasing memory back to the
199 /// specified allocator.
200 template<typename AllocatorTy>
201 void Destroy(AllocatorTy &Allocator) {
202 // Free memory referenced by the item.
203 size_t AllocSize = sizeof(StringMapEntry) + getKeyLength() + 1;
204 this->~StringMapEntry();
205 Allocator.Deallocate(static_cast<void *>(this), AllocSize);
208 /// Destroy this object, releasing memory back to the malloc allocator.
215 /// StringMap - This is an unconventional map that is specialized for handling
216 /// keys that are "strings", which are basically ranges of bytes. This does some
217 /// funky memory allocation and hashing things to make it extremely efficient,
218 /// storing the string data *after* the value in the map.
219 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
220 class StringMap : public StringMapImpl {
221 AllocatorTy Allocator;
224 using MapEntryTy = StringMapEntry<ValueTy>;
226 StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
228 explicit StringMap(unsigned InitialSize)
229 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
231 explicit StringMap(AllocatorTy A)
232 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
234 StringMap(unsigned InitialSize, AllocatorTy A)
235 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
238 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
239 : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
240 for (const auto &P : List) {
245 StringMap(StringMap &&RHS)
246 : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
248 StringMap(const StringMap &RHS) :
249 StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
250 Allocator(RHS.Allocator) {
254 // Allocate TheTable of the same size as RHS's TheTable, and set the
255 // sentinel appropriately (and NumBuckets).
256 init(RHS.NumBuckets);
257 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
258 *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
260 NumItems = RHS.NumItems;
261 NumTombstones = RHS.NumTombstones;
262 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
263 StringMapEntryBase *Bucket = RHS.TheTable[I];
264 if (!Bucket || Bucket == getTombstoneVal()) {
265 TheTable[I] = Bucket;
269 TheTable[I] = MapEntryTy::Create(
270 static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
271 static_cast<MapEntryTy *>(Bucket)->getValue());
272 HashTable[I] = RHSHashTable[I];
275 // Note that here we've copied everything from the RHS into this object,
276 // tombstones included. We could, instead, have re-probed for each key to
277 // instantiate this new object without any tombstone buckets. The
278 // assumption here is that items are rarely deleted from most StringMaps,
279 // and so tombstones are rare, so the cost of re-probing for all inputs is
283 StringMap &operator=(StringMap RHS) {
284 StringMapImpl::swap(RHS);
285 std::swap(Allocator, RHS.Allocator);
290 // Delete all the elements in the map, but don't reset the elements
291 // to default values. This is a copy of clear(), but avoids unnecessary
292 // work not required in the destructor.
294 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
295 StringMapEntryBase *Bucket = TheTable[I];
296 if (Bucket && Bucket != getTombstoneVal()) {
297 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
304 AllocatorTy &getAllocator() { return Allocator; }
305 const AllocatorTy &getAllocator() const { return Allocator; }
307 using key_type = const char*;
308 using mapped_type = ValueTy;
309 using value_type = StringMapEntry<ValueTy>;
310 using size_type = size_t;
312 using const_iterator = StringMapConstIterator<ValueTy>;
313 using iterator = StringMapIterator<ValueTy>;
316 return iterator(TheTable, NumBuckets == 0);
319 return iterator(TheTable+NumBuckets, true);
321 const_iterator begin() const {
322 return const_iterator(TheTable, NumBuckets == 0);
324 const_iterator end() const {
325 return const_iterator(TheTable+NumBuckets, true);
328 iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
329 return make_range(StringMapKeyIterator<ValueTy>(begin()),
330 StringMapKeyIterator<ValueTy>(end()));
333 iterator find(StringRef Key) {
334 int Bucket = FindKey(Key);
335 if (Bucket == -1) return end();
336 return iterator(TheTable+Bucket, true);
339 const_iterator find(StringRef Key) const {
340 int Bucket = FindKey(Key);
341 if (Bucket == -1) return end();
342 return const_iterator(TheTable+Bucket, true);
345 /// lookup - Return the entry for the specified key, or a default
346 /// constructed value if no such entry exists.
347 ValueTy lookup(StringRef Key) const {
348 const_iterator it = find(Key);
354 /// Lookup the ValueTy for the \p Key, or create a default constructed value
355 /// if the key is not in the map.
356 ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
358 /// count - Return 1 if the element is in the map, 0 otherwise.
359 size_type count(StringRef Key) const {
360 return find(Key) == end() ? 0 : 1;
363 /// insert - Insert the specified key/value pair into the map. If the key
364 /// already exists in the map, return false and ignore the request, otherwise
365 /// insert it and return true.
366 bool insert(MapEntryTy *KeyValue) {
367 unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
368 StringMapEntryBase *&Bucket = TheTable[BucketNo];
369 if (Bucket && Bucket != getTombstoneVal())
370 return false; // Already exists in map.
372 if (Bucket == getTombstoneVal())
376 assert(NumItems + NumTombstones <= NumBuckets);
382 /// insert - Inserts the specified key/value pair into the map if the key
383 /// isn't already in the map. The bool component of the returned pair is true
384 /// if and only if the insertion takes place, and the iterator component of
385 /// the pair points to the element with key equivalent to the key of the pair.
386 std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
387 return try_emplace(KV.first, std::move(KV.second));
390 /// Emplace a new element for the specified key into the map if the key isn't
391 /// already in the map. The bool component of the returned pair is true
392 /// if and only if the insertion takes place, and the iterator component of
393 /// the pair points to the element with key equivalent to the key of the pair.
394 template <typename... ArgsTy>
395 std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
396 unsigned BucketNo = LookupBucketFor(Key);
397 StringMapEntryBase *&Bucket = TheTable[BucketNo];
398 if (Bucket && Bucket != getTombstoneVal())
399 return std::make_pair(iterator(TheTable + BucketNo, false),
400 false); // Already exists in map.
402 if (Bucket == getTombstoneVal())
404 Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
406 assert(NumItems + NumTombstones <= NumBuckets);
408 BucketNo = RehashTable(BucketNo);
409 return std::make_pair(iterator(TheTable + BucketNo, false), true);
412 // clear - Empties out the StringMap
416 // Zap all values, resetting the keys back to non-present (not tombstone),
417 // which is safe because we're removing all elements.
418 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
419 StringMapEntryBase *&Bucket = TheTable[I];
420 if (Bucket && Bucket != getTombstoneVal()) {
421 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
430 /// remove - Remove the specified key/value pair from the map, but do not
431 /// erase it. This aborts if the key is not in the map.
432 void remove(MapEntryTy *KeyValue) {
436 void erase(iterator I) {
439 V.Destroy(Allocator);
442 bool erase(StringRef Key) {
443 iterator I = find(Key);
444 if (I == end()) return false;
450 template <typename DerivedTy, typename ValueTy>
451 class StringMapIterBase
452 : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
455 StringMapEntryBase **Ptr = nullptr;
458 StringMapIterBase() = default;
460 explicit StringMapIterBase(StringMapEntryBase **Bucket,
461 bool NoAdvance = false)
463 if (!NoAdvance) AdvancePastEmptyBuckets();
466 DerivedTy &operator=(const DerivedTy &Other) {
468 return static_cast<DerivedTy &>(*this);
471 bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
473 DerivedTy &operator++() { // Preincrement
475 AdvancePastEmptyBuckets();
476 return static_cast<DerivedTy &>(*this);
479 DerivedTy operator++(int) { // Post-increment
486 void AdvancePastEmptyBuckets() {
487 while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
492 template <typename ValueTy>
493 class StringMapConstIterator
494 : public StringMapIterBase<StringMapConstIterator<ValueTy>,
495 const StringMapEntry<ValueTy>> {
496 using base = StringMapIterBase<StringMapConstIterator<ValueTy>,
497 const StringMapEntry<ValueTy>>;
500 StringMapConstIterator() = default;
501 explicit StringMapConstIterator(StringMapEntryBase **Bucket,
502 bool NoAdvance = false)
503 : base(Bucket, NoAdvance) {}
505 const StringMapEntry<ValueTy> &operator*() const {
506 return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
510 template <typename ValueTy>
511 class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
512 StringMapEntry<ValueTy>> {
514 StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
517 StringMapIterator() = default;
518 explicit StringMapIterator(StringMapEntryBase **Bucket,
519 bool NoAdvance = false)
520 : base(Bucket, NoAdvance) {}
522 StringMapEntry<ValueTy> &operator*() const {
523 return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
526 operator StringMapConstIterator<ValueTy>() const {
527 return StringMapConstIterator<ValueTy>(this->Ptr, true);
531 template <typename ValueTy>
532 class StringMapKeyIterator
533 : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
534 StringMapConstIterator<ValueTy>,
535 std::forward_iterator_tag, StringRef> {
536 using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
537 StringMapConstIterator<ValueTy>,
538 std::forward_iterator_tag, StringRef>;
541 StringMapKeyIterator() = default;
542 explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
543 : base(std::move(Iter)) {}
545 StringRef &operator*() {
546 Key = this->wrapped()->getKey();
554 } // end namespace llvm
556 #endif // LLVM_ADT_STRINGMAP_H