1 //===- StringMap.h - String Hash table map interface ------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the StringMap class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_ADT_STRINGMAP_H 14 #define LLVM_ADT_STRINGMAP_H 15 16 #include "llvm/ADT/StringRef.h" 17 #include "llvm/ADT/iterator.h" 18 #include "llvm/ADT/iterator_range.h" 19 #include "llvm/Support/Allocator.h" 20 #include "llvm/Support/PointerLikeTypeTraits.h" 21 #include "llvm/Support/ErrorHandling.h" 22 #include <algorithm> 23 #include <cassert> 24 #include <cstdint> 25 #include <cstdlib> 26 #include <cstring> 27 #include <initializer_list> 28 #include <iterator> 29 #include <utility> 30 31 namespace llvm { 32 33 template<typename ValueTy> class StringMapConstIterator; 34 template<typename ValueTy> class StringMapIterator; 35 template<typename ValueTy> class StringMapKeyIterator; 36 37 /// StringMapEntryBase - Shared base class of StringMapEntry instances. 38 class StringMapEntryBase { 39 size_t StrLen; 40 41 public: StringMapEntryBase(size_t Len)42 explicit StringMapEntryBase(size_t Len) : StrLen(Len) {} 43 getKeyLength()44 size_t getKeyLength() const { return StrLen; } 45 }; 46 47 /// StringMapImpl - This is the base class of StringMap that is shared among 48 /// all of its instantiations. 49 class StringMapImpl { 50 protected: 51 // Array of NumBuckets pointers to entries, null pointers are holes. 52 // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed 53 // by an array of the actual hash values as unsigned integers. 54 StringMapEntryBase **TheTable = nullptr; 55 unsigned NumBuckets = 0; 56 unsigned NumItems = 0; 57 unsigned NumTombstones = 0; 58 unsigned ItemSize; 59 60 protected: StringMapImpl(unsigned itemSize)61 explicit StringMapImpl(unsigned itemSize) 62 : ItemSize(itemSize) {} StringMapImpl(StringMapImpl && RHS)63 StringMapImpl(StringMapImpl &&RHS) 64 : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets), 65 NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones), 66 ItemSize(RHS.ItemSize) { 67 RHS.TheTable = nullptr; 68 RHS.NumBuckets = 0; 69 RHS.NumItems = 0; 70 RHS.NumTombstones = 0; 71 } 72 73 StringMapImpl(unsigned InitSize, unsigned ItemSize); 74 unsigned RehashTable(unsigned BucketNo = 0); 75 76 /// LookupBucketFor - Look up the bucket that the specified string should end 77 /// up in. If it already exists as a key in the map, the Item pointer for the 78 /// specified bucket will be non-null. Otherwise, it will be null. In either 79 /// case, the FullHashValue field of the bucket will be set to the hash value 80 /// of the string. 81 unsigned LookupBucketFor(StringRef Key); 82 83 /// FindKey - Look up the bucket that contains the specified key. If it exists 84 /// in the map, return the bucket number of the key. Otherwise return -1. 85 /// This does not modify the map. 86 int FindKey(StringRef Key) const; 87 88 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 89 /// delete it. This aborts if the value isn't in the table. 90 void RemoveKey(StringMapEntryBase *V); 91 92 /// RemoveKey - Remove the StringMapEntry for the specified key from the 93 /// table, returning it. If the key is not in the table, this returns null. 94 StringMapEntryBase *RemoveKey(StringRef Key); 95 96 /// Allocate the table with the specified number of buckets and otherwise 97 /// setup the map as empty. 98 void init(unsigned Size); 99 100 public: getTombstoneVal()101 static StringMapEntryBase *getTombstoneVal() { 102 uintptr_t Val = static_cast<uintptr_t>(-1); 103 Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable; 104 return reinterpret_cast<StringMapEntryBase *>(Val); 105 } 106 getNumBuckets()107 unsigned getNumBuckets() const { return NumBuckets; } getNumItems()108 unsigned getNumItems() const { return NumItems; } 109 empty()110 bool empty() const { return NumItems == 0; } size()111 unsigned size() const { return NumItems; } 112 swap(StringMapImpl & Other)113 void swap(StringMapImpl &Other) { 114 std::swap(TheTable, Other.TheTable); 115 std::swap(NumBuckets, Other.NumBuckets); 116 std::swap(NumItems, Other.NumItems); 117 std::swap(NumTombstones, Other.NumTombstones); 118 } 119 }; 120 121 /// StringMapEntry - This is used to represent one value that is inserted into 122 /// a StringMap. It contains the Value itself and the key: the string length 123 /// and data. 124 template<typename ValueTy> 125 class StringMapEntry : public StringMapEntryBase { 126 public: 127 ValueTy second; 128 StringMapEntry(size_t strLen)129 explicit StringMapEntry(size_t strLen) 130 : StringMapEntryBase(strLen), second() {} 131 template <typename... InitTy> StringMapEntry(size_t strLen,InitTy &&...InitVals)132 StringMapEntry(size_t strLen, InitTy &&... InitVals) 133 : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {} 134 StringMapEntry(StringMapEntry &E) = delete; 135 getKey()136 StringRef getKey() const { 137 return StringRef(getKeyData(), getKeyLength()); 138 } 139 getValue()140 const ValueTy &getValue() const { return second; } getValue()141 ValueTy &getValue() { return second; } 142 setValue(const ValueTy & V)143 void setValue(const ValueTy &V) { second = V; } 144 145 /// getKeyData - Return the start of the string data that is the key for this 146 /// value. The string data is always stored immediately after the 147 /// StringMapEntry object. getKeyData()148 const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 149 first()150 StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } 151 152 /// Create a StringMapEntry for the specified key construct the value using 153 /// \p InitiVals. 154 template <typename AllocatorTy, typename... InitTy> Create(StringRef Key,AllocatorTy & Allocator,InitTy &&...InitVals)155 static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator, 156 InitTy &&... InitVals) { 157 size_t KeyLength = Key.size(); 158 159 // Allocate a new item with space for the string at the end and a null 160 // terminator. 161 size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1; 162 size_t Alignment = alignof(StringMapEntry); 163 164 StringMapEntry *NewItem = 165 static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 166 assert(NewItem && "Unhandled out-of-memory"); 167 168 // Construct the value. 169 new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...); 170 171 // Copy the string information. 172 char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 173 if (KeyLength > 0) 174 memcpy(StrBuffer, Key.data(), KeyLength); 175 StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 176 return NewItem; 177 } 178 179 /// Create - Create a StringMapEntry with normal malloc/free. 180 template <typename... InitType> Create(StringRef Key,InitType &&...InitVal)181 static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) { 182 MallocAllocator A; 183 return Create(Key, A, std::forward<InitType>(InitVal)...); 184 } 185 Create(StringRef Key)186 static StringMapEntry *Create(StringRef Key) { 187 return Create(Key, ValueTy()); 188 } 189 190 /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 191 /// into a StringMapEntry, return the StringMapEntry itself. GetStringMapEntryFromKeyData(const char * KeyData)192 static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { 193 char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>); 194 return *reinterpret_cast<StringMapEntry*>(Ptr); 195 } 196 197 /// Destroy - Destroy this StringMapEntry, releasing memory back to the 198 /// specified allocator. 199 template<typename AllocatorTy> Destroy(AllocatorTy & Allocator)200 void Destroy(AllocatorTy &Allocator) { 201 // Free memory referenced by the item. 202 size_t AllocSize = sizeof(StringMapEntry) + getKeyLength() + 1; 203 this->~StringMapEntry(); 204 Allocator.Deallocate(static_cast<void *>(this), AllocSize); 205 } 206 207 /// Destroy this object, releasing memory back to the malloc allocator. Destroy()208 void Destroy() { 209 MallocAllocator A; 210 Destroy(A); 211 } 212 }; 213 214 /// StringMap - This is an unconventional map that is specialized for handling 215 /// keys that are "strings", which are basically ranges of bytes. This does some 216 /// funky memory allocation and hashing things to make it extremely efficient, 217 /// storing the string data *after* the value in the map. 218 template<typename ValueTy, typename AllocatorTy = MallocAllocator> 219 class StringMap : public StringMapImpl { 220 AllocatorTy Allocator; 221 222 public: 223 using MapEntryTy = StringMapEntry<ValueTy>; 224 StringMap()225 StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 226 StringMap(unsigned InitialSize)227 explicit StringMap(unsigned InitialSize) 228 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 229 StringMap(AllocatorTy A)230 explicit StringMap(AllocatorTy A) 231 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 232 StringMap(unsigned InitialSize,AllocatorTy A)233 StringMap(unsigned InitialSize, AllocatorTy A) 234 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), 235 Allocator(A) {} 236 StringMap(std::initializer_list<std::pair<StringRef,ValueTy>> List)237 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List) 238 : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) { 239 for (const auto &P : List) { 240 insert(P); 241 } 242 } 243 StringMap(StringMap && RHS)244 StringMap(StringMap &&RHS) 245 : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {} 246 StringMap(const StringMap & RHS)247 StringMap(const StringMap &RHS) : 248 StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), 249 Allocator(RHS.Allocator) { 250 if (RHS.empty()) 251 return; 252 253 // Allocate TheTable of the same size as RHS's TheTable, and set the 254 // sentinel appropriately (and NumBuckets). 255 init(RHS.NumBuckets); 256 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1), 257 *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1); 258 259 NumItems = RHS.NumItems; 260 NumTombstones = RHS.NumTombstones; 261 for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 262 StringMapEntryBase *Bucket = RHS.TheTable[I]; 263 if (!Bucket || Bucket == getTombstoneVal()) { 264 TheTable[I] = Bucket; 265 continue; 266 } 267 268 TheTable[I] = MapEntryTy::Create( 269 static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator, 270 static_cast<MapEntryTy *>(Bucket)->getValue()); 271 HashTable[I] = RHSHashTable[I]; 272 } 273 274 // Note that here we've copied everything from the RHS into this object, 275 // tombstones included. We could, instead, have re-probed for each key to 276 // instantiate this new object without any tombstone buckets. The 277 // assumption here is that items are rarely deleted from most StringMaps, 278 // and so tombstones are rare, so the cost of re-probing for all inputs is 279 // not worthwhile. 280 } 281 282 StringMap &operator=(StringMap RHS) { 283 StringMapImpl::swap(RHS); 284 std::swap(Allocator, RHS.Allocator); 285 return *this; 286 } 287 ~StringMap()288 ~StringMap() { 289 // Delete all the elements in the map, but don't reset the elements 290 // to default values. This is a copy of clear(), but avoids unnecessary 291 // work not required in the destructor. 292 if (!empty()) { 293 for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 294 StringMapEntryBase *Bucket = TheTable[I]; 295 if (Bucket && Bucket != getTombstoneVal()) { 296 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 297 } 298 } 299 } 300 free(TheTable); 301 } 302 getAllocator()303 AllocatorTy &getAllocator() { return Allocator; } getAllocator()304 const AllocatorTy &getAllocator() const { return Allocator; } 305 306 using key_type = const char*; 307 using mapped_type = ValueTy; 308 using value_type = StringMapEntry<ValueTy>; 309 using size_type = size_t; 310 311 using const_iterator = StringMapConstIterator<ValueTy>; 312 using iterator = StringMapIterator<ValueTy>; 313 begin()314 iterator begin() { 315 return iterator(TheTable, NumBuckets == 0); 316 } end()317 iterator end() { 318 return iterator(TheTable+NumBuckets, true); 319 } begin()320 const_iterator begin() const { 321 return const_iterator(TheTable, NumBuckets == 0); 322 } end()323 const_iterator end() const { 324 return const_iterator(TheTable+NumBuckets, true); 325 } 326 keys()327 iterator_range<StringMapKeyIterator<ValueTy>> keys() const { 328 return make_range(StringMapKeyIterator<ValueTy>(begin()), 329 StringMapKeyIterator<ValueTy>(end())); 330 } 331 find(StringRef Key)332 iterator find(StringRef Key) { 333 int Bucket = FindKey(Key); 334 if (Bucket == -1) return end(); 335 return iterator(TheTable+Bucket, true); 336 } 337 find(StringRef Key)338 const_iterator find(StringRef Key) const { 339 int Bucket = FindKey(Key); 340 if (Bucket == -1) return end(); 341 return const_iterator(TheTable+Bucket, true); 342 } 343 344 /// lookup - Return the entry for the specified key, or a default 345 /// constructed value if no such entry exists. lookup(StringRef Key)346 ValueTy lookup(StringRef Key) const { 347 const_iterator it = find(Key); 348 if (it != end()) 349 return it->second; 350 return ValueTy(); 351 } 352 353 /// Lookup the ValueTy for the \p Key, or create a default constructed value 354 /// if the key is not in the map. 355 ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; } 356 357 /// count - Return 1 if the element is in the map, 0 otherwise. count(StringRef Key)358 size_type count(StringRef Key) const { 359 return find(Key) == end() ? 0 : 1; 360 } 361 362 template <typename InputTy> count(const StringMapEntry<InputTy> & MapEntry)363 size_type count(const StringMapEntry<InputTy> &MapEntry) const { 364 return count(MapEntry.getKey()); 365 } 366 367 /// insert - Insert the specified key/value pair into the map. If the key 368 /// already exists in the map, return false and ignore the request, otherwise 369 /// insert it and return true. insert(MapEntryTy * KeyValue)370 bool insert(MapEntryTy *KeyValue) { 371 unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 372 StringMapEntryBase *&Bucket = TheTable[BucketNo]; 373 if (Bucket && Bucket != getTombstoneVal()) 374 return false; // Already exists in map. 375 376 if (Bucket == getTombstoneVal()) 377 --NumTombstones; 378 Bucket = KeyValue; 379 ++NumItems; 380 assert(NumItems + NumTombstones <= NumBuckets); 381 382 RehashTable(); 383 return true; 384 } 385 386 /// insert - Inserts the specified key/value pair into the map if the key 387 /// isn't already in the map. The bool component of the returned pair is true 388 /// if and only if the insertion takes place, and the iterator component of 389 /// the pair points to the element with key equivalent to the key of the pair. insert(std::pair<StringRef,ValueTy> KV)390 std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) { 391 return try_emplace(KV.first, std::move(KV.second)); 392 } 393 394 /// Emplace a new element for the specified key into the map if the key isn't 395 /// already in the map. The bool component of the returned pair is true 396 /// if and only if the insertion takes place, and the iterator component of 397 /// the pair points to the element with key equivalent to the key of the pair. 398 template <typename... ArgsTy> try_emplace(StringRef Key,ArgsTy &&...Args)399 std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) { 400 unsigned BucketNo = LookupBucketFor(Key); 401 StringMapEntryBase *&Bucket = TheTable[BucketNo]; 402 if (Bucket && Bucket != getTombstoneVal()) 403 return std::make_pair(iterator(TheTable + BucketNo, false), 404 false); // Already exists in map. 405 406 if (Bucket == getTombstoneVal()) 407 --NumTombstones; 408 Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...); 409 ++NumItems; 410 assert(NumItems + NumTombstones <= NumBuckets); 411 412 BucketNo = RehashTable(BucketNo); 413 return std::make_pair(iterator(TheTable + BucketNo, false), true); 414 } 415 416 // clear - Empties out the StringMap clear()417 void clear() { 418 if (empty()) return; 419 420 // Zap all values, resetting the keys back to non-present (not tombstone), 421 // which is safe because we're removing all elements. 422 for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 423 StringMapEntryBase *&Bucket = TheTable[I]; 424 if (Bucket && Bucket != getTombstoneVal()) { 425 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 426 } 427 Bucket = nullptr; 428 } 429 430 NumItems = 0; 431 NumTombstones = 0; 432 } 433 434 /// remove - Remove the specified key/value pair from the map, but do not 435 /// erase it. This aborts if the key is not in the map. remove(MapEntryTy * KeyValue)436 void remove(MapEntryTy *KeyValue) { 437 RemoveKey(KeyValue); 438 } 439 erase(iterator I)440 void erase(iterator I) { 441 MapEntryTy &V = *I; 442 remove(&V); 443 V.Destroy(Allocator); 444 } 445 erase(StringRef Key)446 bool erase(StringRef Key) { 447 iterator I = find(Key); 448 if (I == end()) return false; 449 erase(I); 450 return true; 451 } 452 }; 453 454 template <typename DerivedTy, typename ValueTy> 455 class StringMapIterBase 456 : public iterator_facade_base<DerivedTy, std::forward_iterator_tag, 457 ValueTy> { 458 protected: 459 StringMapEntryBase **Ptr = nullptr; 460 461 public: 462 StringMapIterBase() = default; 463 464 explicit StringMapIterBase(StringMapEntryBase **Bucket, 465 bool NoAdvance = false) Ptr(Bucket)466 : Ptr(Bucket) { 467 if (!NoAdvance) AdvancePastEmptyBuckets(); 468 } 469 470 DerivedTy &operator=(const DerivedTy &Other) { 471 Ptr = Other.Ptr; 472 return static_cast<DerivedTy &>(*this); 473 } 474 475 bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; } 476 477 DerivedTy &operator++() { // Preincrement 478 ++Ptr; 479 AdvancePastEmptyBuckets(); 480 return static_cast<DerivedTy &>(*this); 481 } 482 483 DerivedTy operator++(int) { // Post-increment 484 DerivedTy Tmp(Ptr); 485 ++*this; 486 return Tmp; 487 } 488 489 private: AdvancePastEmptyBuckets()490 void AdvancePastEmptyBuckets() { 491 while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) 492 ++Ptr; 493 } 494 }; 495 496 template <typename ValueTy> 497 class StringMapConstIterator 498 : public StringMapIterBase<StringMapConstIterator<ValueTy>, 499 const StringMapEntry<ValueTy>> { 500 using base = StringMapIterBase<StringMapConstIterator<ValueTy>, 501 const StringMapEntry<ValueTy>>; 502 503 public: 504 StringMapConstIterator() = default; 505 explicit StringMapConstIterator(StringMapEntryBase **Bucket, 506 bool NoAdvance = false) base(Bucket,NoAdvance)507 : base(Bucket, NoAdvance) {} 508 509 const StringMapEntry<ValueTy> &operator*() const { 510 return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr); 511 } 512 }; 513 514 template <typename ValueTy> 515 class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>, 516 StringMapEntry<ValueTy>> { 517 using base = 518 StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>; 519 520 public: 521 StringMapIterator() = default; 522 explicit StringMapIterator(StringMapEntryBase **Bucket, 523 bool NoAdvance = false) base(Bucket,NoAdvance)524 : base(Bucket, NoAdvance) {} 525 526 StringMapEntry<ValueTy> &operator*() const { 527 return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr); 528 } 529 530 operator StringMapConstIterator<ValueTy>() const { 531 return StringMapConstIterator<ValueTy>(this->Ptr, true); 532 } 533 }; 534 535 template <typename ValueTy> 536 class StringMapKeyIterator 537 : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>, 538 StringMapConstIterator<ValueTy>, 539 std::forward_iterator_tag, StringRef> { 540 using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>, 541 StringMapConstIterator<ValueTy>, 542 std::forward_iterator_tag, StringRef>; 543 544 public: 545 StringMapKeyIterator() = default; StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)546 explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter) 547 : base(std::move(Iter)) {} 548 549 StringRef &operator*() { 550 Key = this->wrapped()->getKey(); 551 return Key; 552 } 553 554 private: 555 StringRef Key; 556 }; 557 558 } // end namespace llvm 559 560 #endif // LLVM_ADT_STRINGMAP_H 561