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 <algorithm> 23#include <cassert> 24#include <cstdint> 25#include <cstdlib> 26#include <cstring> 27#include <initializer_list> 28#include <iterator> 29#include <utility> 30 31namespace llvm { 32 33template<typename ValueTy> class StringMapConstIterator; 34template<typename ValueTy> class StringMapIterator; 35template<typename ValueTy> class StringMapKeyIterator; 36 37/// StringMapEntryBase - Shared base class of StringMapEntry instances. 38class StringMapEntryBase { 39 unsigned StrLen; 40 41public: 42 explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} 43 44 unsigned getKeyLength() const { return StrLen; } 45}; 46 47/// StringMapImpl - This is the base class of StringMap that is shared among 48/// all of its instantiations. 49class StringMapImpl { 50protected: 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 60protected: 61 explicit StringMapImpl(unsigned itemSize) 62 : ItemSize(itemSize) {} 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 100public: 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 107 unsigned getNumBuckets() const { return NumBuckets; } 108 unsigned getNumItems() const { return NumItems; } 109 110 bool empty() const { return NumItems == 0; } 111 unsigned size() const { return NumItems; } 112 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. 124template<typename ValueTy> 125class StringMapEntry : public StringMapEntryBase { 126public: 127 ValueTy second; 128 129 explicit StringMapEntry(unsigned strLen) 130 : StringMapEntryBase(strLen), second() {} 131 template <typename... InitTy> 132 StringMapEntry(unsigned strLen, InitTy &&... InitVals) 133 : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {} 134 StringMapEntry(StringMapEntry &E) = delete; 135 136 StringRef getKey() const { 137 return StringRef(getKeyData(), getKeyLength()); 138 } 139 140 const ValueTy &getValue() const { return second; } 141 ValueTy &getValue() { return second; } 142 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. 148 const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 149 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> 155 static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator, 156 InitTy &&... InitVals) { 157 unsigned KeyLength = Key.size(); 158 159 // Allocate a new item with space for the string at the end and a null 160 // terminator. 161 unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 162 KeyLength+1; 163 unsigned Alignment = alignof(StringMapEntry); 164 165 StringMapEntry *NewItem = 166 static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 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> 181 static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) { 182 MallocAllocator A; 183 return Create(Key, A, std::forward<InitType>(InitVal)...); 184 } 185 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. 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> 200 void Destroy(AllocatorTy &Allocator) { 201 // Free memory referenced by the item. 202 unsigned AllocSize = 203 static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1; 204 this->~StringMapEntry(); 205 Allocator.Deallocate(static_cast<void *>(this), AllocSize); 206 } 207 208 /// Destroy this object, releasing memory back to the malloc allocator. 209 void Destroy() { 210 MallocAllocator A; 211 Destroy(A); 212 } 213}; 214 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. 219template<typename ValueTy, typename AllocatorTy = MallocAllocator> 220class StringMap : public StringMapImpl { 221 AllocatorTy Allocator; 222 223public: 224 using MapEntryTy = StringMapEntry<ValueTy>; 225 226 StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 227 228 explicit StringMap(unsigned InitialSize) 229 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 230 231 explicit StringMap(AllocatorTy A) 232 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 233 234 StringMap(unsigned InitialSize, AllocatorTy A) 235 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), 236 Allocator(A) {} 237 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) { 241 insert(P); 242 } 243 } 244 245 StringMap(StringMap &&RHS) 246 : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {} 247 248 StringMap(const StringMap &RHS) : 249 StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), 250 Allocator(RHS.Allocator) { 251 if (RHS.empty()) 252 return; 253 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); 259 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; 266 continue; 267 } 268 269 TheTable[I] = MapEntryTy::Create( 270 static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator, 271 static_cast<MapEntryTy *>(Bucket)->getValue()); 272 HashTable[I] = RHSHashTable[I]; 273 } 274 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 280 // not worthwhile. 281 } 282 283 StringMap &operator=(StringMap RHS) { 284 StringMapImpl::swap(RHS); 285 std::swap(Allocator, RHS.Allocator); 286 return *this; 287 } 288 289 ~StringMap() { 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. 293 if (!empty()) { 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); 298 } 299 } 300 } 301 free(TheTable); 302 } 303 304 AllocatorTy &getAllocator() { return Allocator; } 305 const AllocatorTy &getAllocator() const { return Allocator; } 306 307 using key_type = const char*; 308 using mapped_type = ValueTy; 309 using value_type = StringMapEntry<ValueTy>; 310 using size_type = size_t; 311 312 using const_iterator = StringMapConstIterator<ValueTy>; 313 using iterator = StringMapIterator<ValueTy>; 314 315 iterator begin() { 316 return iterator(TheTable, NumBuckets == 0); 317 } 318 iterator end() { 319 return iterator(TheTable+NumBuckets, true); 320 } 321 const_iterator begin() const { 322 return const_iterator(TheTable, NumBuckets == 0); 323 } 324 const_iterator end() const { 325 return const_iterator(TheTable+NumBuckets, true); 326 } 327 328 iterator_range<StringMapKeyIterator<ValueTy>> keys() const { 329 return make_range(StringMapKeyIterator<ValueTy>(begin()), 330 StringMapKeyIterator<ValueTy>(end())); 331 } 332 333 iterator find(StringRef Key) { 334 int Bucket = FindKey(Key); 335 if (Bucket == -1) return end(); 336 return iterator(TheTable+Bucket, true); 337 } 338 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); 343 } 344 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); 349 if (it != end()) 350 return it->second; 351 return ValueTy(); 352 } 353 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; } 357 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; 361 } 362 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. 371 372 if (Bucket == getTombstoneVal()) 373 --NumTombstones; 374 Bucket = KeyValue; 375 ++NumItems; 376 assert(NumItems + NumTombstones <= NumBuckets); 377 378 RehashTable(); 379 return true; 380 } 381 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)); 388 } 389 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. 401 402 if (Bucket == getTombstoneVal()) 403 --NumTombstones; 404 Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...); 405 ++NumItems; 406 assert(NumItems + NumTombstones <= NumBuckets); 407 408 BucketNo = RehashTable(BucketNo); 409 return std::make_pair(iterator(TheTable + BucketNo, false), true); 410 } 411 412 // clear - Empties out the StringMap 413 void clear() { 414 if (empty()) return; 415 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); 422 } 423 Bucket = nullptr; 424 } 425 426 NumItems = 0; 427 NumTombstones = 0; 428 } 429 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) { 433 RemoveKey(KeyValue); 434 } 435 436 void erase(iterator I) { 437 MapEntryTy &V = *I; 438 remove(&V); 439 V.Destroy(Allocator); 440 } 441 442 bool erase(StringRef Key) { 443 iterator I = find(Key); 444 if (I == end()) return false; 445 erase(I); 446 return true; 447 } 448}; 449 450template <typename DerivedTy, typename ValueTy> 451class StringMapIterBase 452 : public iterator_facade_base<DerivedTy, std::forward_iterator_tag, 453 ValueTy> { 454protected: 455 StringMapEntryBase **Ptr = nullptr; 456 457public: 458 StringMapIterBase() = default; 459 460 explicit StringMapIterBase(StringMapEntryBase **Bucket, 461 bool NoAdvance = false) 462 : Ptr(Bucket) { 463 if (!NoAdvance) AdvancePastEmptyBuckets(); 464 } 465 466 DerivedTy &operator=(const DerivedTy &Other) { 467 Ptr = Other.Ptr; 468 return static_cast<DerivedTy &>(*this); 469 } 470 471 bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; } 472 473 DerivedTy &operator++() { // Preincrement 474 ++Ptr; 475 AdvancePastEmptyBuckets(); 476 return static_cast<DerivedTy &>(*this); 477 } 478 479 DerivedTy operator++(int) { // Post-increment 480 DerivedTy Tmp(Ptr); 481 ++*this; 482 return Tmp; 483 } 484 485private: 486 void AdvancePastEmptyBuckets() { 487 while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) 488 ++Ptr; 489 } 490}; 491 492template <typename ValueTy> 493class StringMapConstIterator 494 : public StringMapIterBase<StringMapConstIterator<ValueTy>, 495 const StringMapEntry<ValueTy>> { 496 using base = StringMapIterBase<StringMapConstIterator<ValueTy>, 497 const StringMapEntry<ValueTy>>; 498 499public: 500 StringMapConstIterator() = default; 501 explicit StringMapConstIterator(StringMapEntryBase **Bucket, 502 bool NoAdvance = false) 503 : base(Bucket, NoAdvance) {} 504 505 const StringMapEntry<ValueTy> &operator*() const { 506 return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr); 507 } 508}; 509 510template <typename ValueTy> 511class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>, 512 StringMapEntry<ValueTy>> { 513 using base = 514 StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>; 515 516public: 517 StringMapIterator() = default; 518 explicit StringMapIterator(StringMapEntryBase **Bucket, 519 bool NoAdvance = false) 520 : base(Bucket, NoAdvance) {} 521 522 StringMapEntry<ValueTy> &operator*() const { 523 return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr); 524 } 525 526 operator StringMapConstIterator<ValueTy>() const { 527 return StringMapConstIterator<ValueTy>(this->Ptr, true); 528 } 529}; 530 531template <typename ValueTy> 532class 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>; 539 540public: 541 StringMapKeyIterator() = default; 542 explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter) 543 : base(std::move(Iter)) {} 544 545 StringRef &operator*() { 546 Key = this->wrapped()->getKey(); 547 return Key; 548 } 549 550private: 551 StringRef Key; 552}; 553 554} // end namespace llvm 555 556#endif // LLVM_ADT_STRINGMAP_H 557