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