1//===- StringMap.h - String Hash table map interface ------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the StringMap class. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ADT_STRINGMAP_H 15#define LLVM_ADT_STRINGMAP_H 16 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" 23#include <algorithm> 24#include <cassert> 25#include <cstdint> 26#include <cstdlib> 27#include <cstring> 28#include <initializer_list> 29#include <iterator> 30#include <utility> 31 32namespace llvm { 33 34template<typename ValueTy> class StringMapConstIterator; 35template<typename ValueTy> class StringMapIterator; 36template<typename ValueTy> class StringMapKeyIterator; 37 38/// StringMapEntryBase - Shared base class of StringMapEntry instances. 39class StringMapEntryBase { 40 unsigned StrLen; 41 42public: 43 explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} 44 45 unsigned getKeyLength() const { return StrLen; } 46}; 47 48/// StringMapImpl - This is the base class of StringMap that is shared among 49/// all of its instantiations. 50class StringMapImpl { 51protected: 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; 59 unsigned ItemSize; 60 61protected: 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; 69 RHS.NumBuckets = 0; 70 RHS.NumItems = 0; 71 RHS.NumTombstones = 0; 72 } 73 74 StringMapImpl(unsigned InitSize, unsigned ItemSize); 75 unsigned RehashTable(unsigned BucketNo = 0); 76 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 81 /// of the string. 82 unsigned LookupBucketFor(StringRef Key); 83 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; 88 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); 92 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); 96 97 /// Allocate the table with the specified number of buckets and otherwise 98 /// setup the map as empty. 99 void init(unsigned Size); 100 101public: 102 static StringMapEntryBase *getTombstoneVal() { 103 uintptr_t Val = static_cast<uintptr_t>(-1); 104 Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable; 105 return reinterpret_cast<StringMapEntryBase *>(Val); 106 } 107 108 unsigned getNumBuckets() const { return NumBuckets; } 109 unsigned getNumItems() const { return NumItems; } 110 111 bool empty() const { return NumItems == 0; } 112 unsigned size() const { return NumItems; } 113 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); 119 } 120}; 121 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 124/// and data. 125template<typename ValueTy> 126class StringMapEntry : public StringMapEntryBase { 127public: 128 ValueTy second; 129 130 explicit StringMapEntry(unsigned strLen) 131 : StringMapEntryBase(strLen), second() {} 132 template <typename... InitTy> 133 StringMapEntry(unsigned strLen, InitTy &&... InitVals) 134 : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {} 135 StringMapEntry(StringMapEntry &E) = delete; 136 137 StringRef getKey() const { 138 return StringRef(getKeyData(), getKeyLength()); 139 } 140 141 const ValueTy &getValue() const { return second; } 142 ValueTy &getValue() { return second; } 143 144 void setValue(const ValueTy &V) { second = V; } 145 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);} 150 151 StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } 152 153 /// Create a StringMapEntry for the specified key construct the value using 154 /// \p InitiVals. 155 template <typename AllocatorTy, typename... InitTy> 156 static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator, 157 InitTy &&... InitVals) { 158 unsigned KeyLength = Key.size(); 159 160 // Allocate a new item with space for the string at the end and a null 161 // terminator. 162 unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 163 KeyLength+1; 164 unsigned Alignment = alignof(StringMapEntry); 165 166 StringMapEntry *NewItem = 167 static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 168 169 if (NewItem == nullptr) 170 report_bad_alloc_error("Allocation of StringMap entry failed."); 171 172 // Construct the value. 173 new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...); 174 175 // Copy the string information. 176 char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 177 if (KeyLength > 0) 178 memcpy(StrBuffer, Key.data(), KeyLength); 179 StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 180 return NewItem; 181 } 182 183 /// Create - Create a StringMapEntry with normal malloc/free. 184 template <typename... InitType> 185 static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) { 186 MallocAllocator A; 187 return Create(Key, A, std::forward<InitType>(InitVal)...); 188 } 189 190 static StringMapEntry *Create(StringRef Key) { 191 return Create(Key, ValueTy()); 192 } 193 194 /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 195 /// into a StringMapEntry, return the StringMapEntry itself. 196 static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { 197 char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>); 198 return *reinterpret_cast<StringMapEntry*>(Ptr); 199 } 200 201 /// Destroy - Destroy this StringMapEntry, releasing memory back to the 202 /// specified allocator. 203 template<typename AllocatorTy> 204 void Destroy(AllocatorTy &Allocator) { 205 // Free memory referenced by the item. 206 unsigned AllocSize = 207 static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1; 208 this->~StringMapEntry(); 209 Allocator.Deallocate(static_cast<void *>(this), AllocSize); 210 } 211 212 /// Destroy this object, releasing memory back to the malloc allocator. 213 void Destroy() { 214 MallocAllocator A; 215 Destroy(A); 216 } 217}; 218 219/// StringMap - This is an unconventional map that is specialized for handling 220/// keys that are "strings", which are basically ranges of bytes. This does some 221/// funky memory allocation and hashing things to make it extremely efficient, 222/// storing the string data *after* the value in the map. 223template<typename ValueTy, typename AllocatorTy = MallocAllocator> 224class StringMap : public StringMapImpl { 225 AllocatorTy Allocator; 226 227public: 228 using MapEntryTy = StringMapEntry<ValueTy>; 229 230 StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 231 232 explicit StringMap(unsigned InitialSize) 233 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 234 235 explicit StringMap(AllocatorTy A) 236 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 237 238 StringMap(unsigned InitialSize, AllocatorTy A) 239 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), 240 Allocator(A) {} 241 242 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List) 243 : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) { 244 for (const auto &P : List) { 245 insert(P); 246 } 247 } 248 249 StringMap(StringMap &&RHS) 250 : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {} 251 252 StringMap(const StringMap &RHS) : 253 StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), 254 Allocator(RHS.Allocator) { 255 if (RHS.empty()) 256 return; 257 258 // Allocate TheTable of the same size as RHS's TheTable, and set the 259 // sentinel appropriately (and NumBuckets). 260 init(RHS.NumBuckets); 261 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1), 262 *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1); 263 264 NumItems = RHS.NumItems; 265 NumTombstones = RHS.NumTombstones; 266 for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 267 StringMapEntryBase *Bucket = RHS.TheTable[I]; 268 if (!Bucket || Bucket == getTombstoneVal()) { 269 TheTable[I] = Bucket; 270 continue; 271 } 272 273 TheTable[I] = MapEntryTy::Create( 274 static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator, 275 static_cast<MapEntryTy *>(Bucket)->getValue()); 276 HashTable[I] = RHSHashTable[I]; 277 } 278 279 // Note that here we've copied everything from the RHS into this object, 280 // tombstones included. We could, instead, have re-probed for each key to 281 // instantiate this new object without any tombstone buckets. The 282 // assumption here is that items are rarely deleted from most StringMaps, 283 // and so tombstones are rare, so the cost of re-probing for all inputs is 284 // not worthwhile. 285 } 286 287 StringMap &operator=(StringMap RHS) { 288 StringMapImpl::swap(RHS); 289 std::swap(Allocator, RHS.Allocator); 290 return *this; 291 } 292 293 ~StringMap() { 294 // Delete all the elements in the map, but don't reset the elements 295 // to default values. This is a copy of clear(), but avoids unnecessary 296 // work not required in the destructor. 297 if (!empty()) { 298 for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 299 StringMapEntryBase *Bucket = TheTable[I]; 300 if (Bucket && Bucket != getTombstoneVal()) { 301 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 302 } 303 } 304 } 305 free(TheTable); 306 } 307 308 AllocatorTy &getAllocator() { return Allocator; } 309 const AllocatorTy &getAllocator() const { return Allocator; } 310 311 using key_type = const char*; 312 using mapped_type = ValueTy; 313 using value_type = StringMapEntry<ValueTy>; 314 using size_type = size_t; 315 316 using const_iterator = StringMapConstIterator<ValueTy>; 317 using iterator = StringMapIterator<ValueTy>; 318 319 iterator begin() { 320 return iterator(TheTable, NumBuckets == 0); 321 } 322 iterator end() { 323 return iterator(TheTable+NumBuckets, true); 324 } 325 const_iterator begin() const { 326 return const_iterator(TheTable, NumBuckets == 0); 327 } 328 const_iterator end() const { 329 return const_iterator(TheTable+NumBuckets, true); 330 } 331 332 iterator_range<StringMapKeyIterator<ValueTy>> keys() const { 333 return make_range(StringMapKeyIterator<ValueTy>(begin()), 334 StringMapKeyIterator<ValueTy>(end())); 335 } 336 337 iterator find(StringRef Key) { 338 int Bucket = FindKey(Key); 339 if (Bucket == -1) return end(); 340 return iterator(TheTable+Bucket, true); 341 } 342 343 const_iterator find(StringRef Key) const { 344 int Bucket = FindKey(Key); 345 if (Bucket == -1) return end(); 346 return const_iterator(TheTable+Bucket, true); 347 } 348 349 /// lookup - Return the entry for the specified key, or a default 350 /// constructed value if no such entry exists. 351 ValueTy lookup(StringRef Key) const { 352 const_iterator it = find(Key); 353 if (it != end()) 354 return it->second; 355 return ValueTy(); 356 } 357 358 /// Lookup the ValueTy for the \p Key, or create a default constructed value 359 /// if the key is not in the map. 360 ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; } 361 362 /// count - Return 1 if the element is in the map, 0 otherwise. 363 size_type count(StringRef Key) const { 364 return find(Key) == end() ? 0 : 1; 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. 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. 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> 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 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. 436 void remove(MapEntryTy *KeyValue) { 437 RemoveKey(KeyValue); 438 } 439 440 void erase(iterator I) { 441 MapEntryTy &V = *I; 442 remove(&V); 443 V.Destroy(Allocator); 444 } 445 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 454template <typename DerivedTy, typename ValueTy> 455class StringMapIterBase 456 : public iterator_facade_base<DerivedTy, std::forward_iterator_tag, 457 ValueTy> { 458protected: 459 StringMapEntryBase **Ptr = nullptr; 460 461public: 462 StringMapIterBase() = default; 463 464 explicit StringMapIterBase(StringMapEntryBase **Bucket, 465 bool NoAdvance = false) 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 489private: 490 void AdvancePastEmptyBuckets() { 491 while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) 492 ++Ptr; 493 } 494}; 495 496template <typename ValueTy> 497class StringMapConstIterator 498 : public StringMapIterBase<StringMapConstIterator<ValueTy>, 499 const StringMapEntry<ValueTy>> { 500 using base = StringMapIterBase<StringMapConstIterator<ValueTy>, 501 const StringMapEntry<ValueTy>>; 502 503public: 504 StringMapConstIterator() = default; 505 explicit StringMapConstIterator(StringMapEntryBase **Bucket, 506 bool NoAdvance = false) 507 : base(Bucket, NoAdvance) {} 508 509 const StringMapEntry<ValueTy> &operator*() const { 510 return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr); 511 } 512}; 513 514template <typename ValueTy> 515class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>, 516 StringMapEntry<ValueTy>> { 517 using base = 518 StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>; 519 520public: 521 StringMapIterator() = default; 522 explicit StringMapIterator(StringMapEntryBase **Bucket, 523 bool NoAdvance = false) 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 535template <typename ValueTy> 536class 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 544public: 545 StringMapKeyIterator() = default; 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 554private: 555 StringRef Key; 556}; 557 558} // end namespace llvm 559 560#endif // LLVM_ADT_STRINGMAP_H 561