include/llvm/ADT/StringMap.h

   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:
  42   explicit StringMapEntryBase(size_t Len) : StrLen(Len) {}
  43
  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:
  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
 100 public:
 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.
 124 template<typename ValueTy>
 125 class StringMapEntry : public StringMapEntryBase {
 126 public:
 127   ValueTy second;
 128
 129   explicit StringMapEntry(size_t strLen)
 130     : StringMapEntryBase(strLen), second() {}
 131   template <typename... InitTy>
 132   StringMapEntry(size_t 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     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>
 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     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.
 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
 225   StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
 226
 227   explicit StringMap(unsigned InitialSize)
 228     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
 229
 230   explicit StringMap(AllocatorTy A)
 231     : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
 232
 233   StringMap(unsigned InitialSize, AllocatorTy A)
 234     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
 235       Allocator(A) {}
 236
 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
 244   StringMap(StringMap &&RHS)
 245       : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
 246
 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
 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
 303   AllocatorTy &getAllocator() { return Allocator; }
 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
 314   iterator begin() {
 315     return iterator(TheTable, NumBuckets == 0);
 316   }
 317   iterator end() {
 318     return iterator(TheTable+NumBuckets, true);
 319   }
 320   const_iterator begin() const {
 321     return const_iterator(TheTable, NumBuckets == 0);
 322   }
 323   const_iterator end() const {
 324     return const_iterator(TheTable+NumBuckets, true);
 325   }
 326
 327   iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
 328     return make_range(StringMapKeyIterator<ValueTy>(begin()),
 329                       StringMapKeyIterator<ValueTy>(end()));
 330   }
 331
 332   iterator find(StringRef Key) {
 333     int Bucket = FindKey(Key);
 334     if (Bucket == -1) return end();
 335     return iterator(TheTable+Bucket, true);
 336   }
 337
 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.
 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.
 358   size_type count(StringRef Key) const {
 359     return find(Key) == end() ? 0 : 1;
 360   }
 361
 362   /// insert - Insert the specified key/value pair into the map.  If the key
 363   /// already exists in the map, return false and ignore the request, otherwise
 364   /// insert it and return true.
 365   bool insert(MapEntryTy *KeyValue) {
 366     unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
 367     StringMapEntryBase *&Bucket = TheTable[BucketNo];
 368     if (Bucket && Bucket != getTombstoneVal())
 369       return false;  // Already exists in map.
 370
 371     if (Bucket == getTombstoneVal())
 372       --NumTombstones;
 373     Bucket = KeyValue;
 374     ++NumItems;
 375     assert(NumItems + NumTombstones <= NumBuckets);
 376
 377     RehashTable();
 378     return true;
 379   }
 380
 381   /// insert - Inserts the specified key/value pair into the map if the key
 382   /// isn't already in the map. The bool component of the returned pair is true
 383   /// if and only if the insertion takes place, and the iterator component of
 384   /// the pair points to the element with key equivalent to the key of the pair.
 385   std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
 386     return try_emplace(KV.first, std::move(KV.second));
 387   }
 388
 389   /// Emplace a new element for the specified key into the map if the key isn't
 390   /// already in the map. The bool component of the returned pair is true
 391   /// if and only if the insertion takes place, and the iterator component of
 392   /// the pair points to the element with key equivalent to the key of the pair.
 393   template <typename... ArgsTy>
 394   std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
 395     unsigned BucketNo = LookupBucketFor(Key);
 396     StringMapEntryBase *&Bucket = TheTable[BucketNo];
 397     if (Bucket && Bucket != getTombstoneVal())
 398       return std::make_pair(iterator(TheTable + BucketNo, false),
 399                             false); // Already exists in map.
 400
 401     if (Bucket == getTombstoneVal())
 402       --NumTombstones;
 403     Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
 404     ++NumItems;
 405     assert(NumItems + NumTombstones <= NumBuckets);
 406
 407     BucketNo = RehashTable(BucketNo);
 408     return std::make_pair(iterator(TheTable + BucketNo, false), true);
 409   }
 410
 411   // clear - Empties out the StringMap
 412   void clear() {
 413     if (empty()) return;
 414
 415     // Zap all values, resetting the keys back to non-present (not tombstone),
 416     // which is safe because we're removing all elements.
 417     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
 418       StringMapEntryBase *&Bucket = TheTable[I];
 419       if (Bucket && Bucket != getTombstoneVal()) {
 420         static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
 421       }
 422       Bucket = nullptr;
 423     }
 424
 425     NumItems = 0;
 426     NumTombstones = 0;
 427   }
 428
 429   /// remove - Remove the specified key/value pair from the map, but do not
 430   /// erase it.  This aborts if the key is not in the map.
 431   void remove(MapEntryTy *KeyValue) {
 432     RemoveKey(KeyValue);
 433   }
 434
 435   void erase(iterator I) {
 436     MapEntryTy &V = *I;
 437     remove(&V);
 438     V.Destroy(Allocator);
 439   }
 440
 441   bool erase(StringRef Key) {
 442     iterator I = find(Key);
 443     if (I == end()) return false;
 444     erase(I);
 445     return true;
 446   }
 447 };
 448
 449 template <typename DerivedTy, typename ValueTy>
 450 class StringMapIterBase
 451     : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
 452                                   ValueTy> {
 453 protected:
 454   StringMapEntryBase **Ptr = nullptr;
 455
 456 public:
 457   StringMapIterBase() = default;
 458
 459   explicit StringMapIterBase(StringMapEntryBase **Bucket,
 460                              bool NoAdvance = false)
 461       : Ptr(Bucket) {
 462     if (!NoAdvance) AdvancePastEmptyBuckets();
 463   }
 464
 465   DerivedTy &operator=(const DerivedTy &Other) {
 466     Ptr = Other.Ptr;
 467     return static_cast<DerivedTy &>(*this);
 468   }
 469
 470   bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
 471
 472   DerivedTy &operator++() { // Preincrement
 473     ++Ptr;
 474     AdvancePastEmptyBuckets();
 475     return static_cast<DerivedTy &>(*this);
 476   }
 477
 478   DerivedTy operator++(int) { // Post-increment
 479     DerivedTy Tmp(Ptr);
 480     ++*this;
 481     return Tmp;
 482   }
 483
 484 private:
 485   void AdvancePastEmptyBuckets() {
 486     while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
 487       ++Ptr;
 488   }
 489 };
 490
 491 template <typename ValueTy>
 492 class StringMapConstIterator
 493     : public StringMapIterBase<StringMapConstIterator<ValueTy>,
 494                                const StringMapEntry<ValueTy>> {
 495   using base = StringMapIterBase<StringMapConstIterator<ValueTy>,
 496                                  const StringMapEntry<ValueTy>>;
 497
 498 public:
 499   StringMapConstIterator() = default;
 500   explicit StringMapConstIterator(StringMapEntryBase **Bucket,
 501                                   bool NoAdvance = false)
 502       : base(Bucket, NoAdvance) {}
 503
 504   const StringMapEntry<ValueTy> &operator*() const {
 505     return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
 506   }
 507 };
 508
 509 template <typename ValueTy>
 510 class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
 511                                                    StringMapEntry<ValueTy>> {
 512   using base =
 513       StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
 514
 515 public:
 516   StringMapIterator() = default;
 517   explicit StringMapIterator(StringMapEntryBase **Bucket,
 518                              bool NoAdvance = false)
 519       : base(Bucket, NoAdvance) {}
 520
 521   StringMapEntry<ValueTy> &operator*() const {
 522     return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
 523   }
 524
 525   operator StringMapConstIterator<ValueTy>() const {
 526     return StringMapConstIterator<ValueTy>(this->Ptr, true);
 527   }
 528 };
 529
 530 template <typename ValueTy>
 531 class StringMapKeyIterator
 532     : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
 533                                    StringMapConstIterator<ValueTy>,
 534                                    std::forward_iterator_tag, StringRef> {
 535   using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
 536                                      StringMapConstIterator<ValueTy>,
 537                                      std::forward_iterator_tag, StringRef>;
 538
 539 public:
 540   StringMapKeyIterator() = default;
 541   explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
 542       : base(std::move(Iter)) {}
 543
 544   StringRef &operator*() {
 545     Key = this->wrapped()->getKey();
 546     return Key;
 547   }
 548
 549 private:
 550   StringRef Key;
 551 };
 552
 553 } // end namespace llvm
 554
 555 #endif // LLVM_ADT_STRINGMAP_H