contrib/llvm-project/llvm/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/StringMapEntry.h"
  17 #include "llvm/Support/AllocatorBase.h"
  18 #include "llvm/Support/PointerLikeTypeTraits.h"
  19 #include <initializer_list>
  20 #include <iterator>
  21
  22 namespace llvm {
  23
  24 template <typename ValueTy> class StringMapConstIterator;
  25 template <typename ValueTy> class StringMapIterator;
  26 template <typename ValueTy> class StringMapKeyIterator;
  27
  28 /// StringMapImpl - This is the base class of StringMap that is shared among
  29 /// all of its instantiations.
  30 class StringMapImpl {
  31 protected:
  32   // Array of NumBuckets pointers to entries, null pointers are holes.
  33   // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
  34   // by an array of the actual hash values as unsigned integers.
  35   StringMapEntryBase **TheTable = nullptr;
  36   unsigned NumBuckets = 0;
  37   unsigned NumItems = 0;
  38   unsigned NumTombstones = 0;
  39   unsigned ItemSize;
  40
  41 protected:
  42   explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) {}
  43   StringMapImpl(StringMapImpl &&RHS)
  44       : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
  45         NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
  46         ItemSize(RHS.ItemSize) {
  47     RHS.TheTable = nullptr;
  48     RHS.NumBuckets = 0;
  49     RHS.NumItems = 0;
  50     RHS.NumTombstones = 0;
  51   }
  52
  53   StringMapImpl(unsigned InitSize, unsigned ItemSize);
  54   unsigned RehashTable(unsigned BucketNo = 0);
  55
  56   /// LookupBucketFor - Look up the bucket that the specified string should end
  57   /// up in.  If it already exists as a key in the map, the Item pointer for the
  58   /// specified bucket will be non-null.  Otherwise, it will be null.  In either
  59   /// case, the FullHashValue field of the bucket will be set to the hash value
  60   /// of the string.
  61   unsigned LookupBucketFor(StringRef Key);
  62
  63   /// FindKey - Look up the bucket that contains the specified key. If it exists
  64   /// in the map, return the bucket number of the key.  Otherwise return -1.
  65   /// This does not modify the map.
  66   int FindKey(StringRef Key) const;
  67
  68   /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
  69   /// delete it.  This aborts if the value isn't in the table.
  70   void RemoveKey(StringMapEntryBase *V);
  71
  72   /// RemoveKey - Remove the StringMapEntry for the specified key from the
  73   /// table, returning it.  If the key is not in the table, this returns null.
  74   StringMapEntryBase *RemoveKey(StringRef Key);
  75
  76   /// Allocate the table with the specified number of buckets and otherwise
  77   /// setup the map as empty.
  78   void init(unsigned Size);
  79
  80 public:
  81   static StringMapEntryBase *getTombstoneVal() {
  82     uintptr_t Val = static_cast<uintptr_t>(-1);
  83     Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
  84     return reinterpret_cast<StringMapEntryBase *>(Val);
  85   }
  86
  87   unsigned getNumBuckets() const { return NumBuckets; }
  88   unsigned getNumItems() const { return NumItems; }
  89
  90   bool empty() const { return NumItems == 0; }
  91   unsigned size() const { return NumItems; }
  92
  93   void swap(StringMapImpl &Other) {
  94     std::swap(TheTable, Other.TheTable);
  95     std::swap(NumBuckets, Other.NumBuckets);
  96     std::swap(NumItems, Other.NumItems);
  97     std::swap(NumTombstones, Other.NumTombstones);
  98   }
  99 };
 100
 101 /// StringMap - This is an unconventional map that is specialized for handling
 102 /// keys that are "strings", which are basically ranges of bytes. This does some
 103 /// funky memory allocation and hashing things to make it extremely efficient,
 104 /// storing the string data *after* the value in the map.
 105 template <typename ValueTy, typename AllocatorTy = MallocAllocator>
 106 class StringMap : public StringMapImpl {
 107   AllocatorTy Allocator;
 108
 109 public:
 110   using MapEntryTy = StringMapEntry<ValueTy>;
 111
 112   StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
 113
 114   explicit StringMap(unsigned InitialSize)
 115       : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
 116
 117   explicit StringMap(AllocatorTy A)
 118       : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {
 119   }
 120
 121   StringMap(unsigned InitialSize, AllocatorTy A)
 122       : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
 123         Allocator(A) {}
 124
 125   StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
 126       : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
 127     for (const auto &P : List) {
 128       insert(P);
 129     }
 130   }
 131
 132   StringMap(StringMap &&RHS)
 133       : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
 134
 135   StringMap(const StringMap &RHS)
 136       : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
 137         Allocator(RHS.Allocator) {
 138     if (RHS.empty())
 139       return;
 140
 141     // Allocate TheTable of the same size as RHS's TheTable, and set the
 142     // sentinel appropriately (and NumBuckets).
 143     init(RHS.NumBuckets);
 144     unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
 145              *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
 146
 147     NumItems = RHS.NumItems;
 148     NumTombstones = RHS.NumTombstones;
 149     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
 150       StringMapEntryBase *Bucket = RHS.TheTable[I];
 151       if (!Bucket || Bucket == getTombstoneVal()) {
 152         TheTable[I] = Bucket;
 153         continue;
 154       }
 155
 156       TheTable[I] = MapEntryTy::Create(
 157           static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
 158           static_cast<MapEntryTy *>(Bucket)->getValue());
 159       HashTable[I] = RHSHashTable[I];
 160     }
 161
 162     // Note that here we've copied everything from the RHS into this object,
 163     // tombstones included. We could, instead, have re-probed for each key to
 164     // instantiate this new object without any tombstone buckets. The
 165     // assumption here is that items are rarely deleted from most StringMaps,
 166     // and so tombstones are rare, so the cost of re-probing for all inputs is
 167     // not worthwhile.
 168   }
 169
 170   StringMap &operator=(StringMap RHS) {
 171     StringMapImpl::swap(RHS);
 172     std::swap(Allocator, RHS.Allocator);
 173     return *this;
 174   }
 175
 176   ~StringMap() {
 177     // Delete all the elements in the map, but don't reset the elements
 178     // to default values.  This is a copy of clear(), but avoids unnecessary
 179     // work not required in the destructor.
 180     if (!empty()) {
 181       for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
 182         StringMapEntryBase *Bucket = TheTable[I];
 183         if (Bucket && Bucket != getTombstoneVal()) {
 184           static_cast<MapEntryTy *>(Bucket)->Destroy(Allocator);
 185         }
 186       }
 187     }
 188     free(TheTable);
 189   }
 190
 191   AllocatorTy &getAllocator() { return Allocator; }
 192   const AllocatorTy &getAllocator() const { return Allocator; }
 193
 194   using key_type = const char *;
 195   using mapped_type = ValueTy;
 196   using value_type = StringMapEntry<ValueTy>;
 197   using size_type = size_t;
 198
 199   using const_iterator = StringMapConstIterator<ValueTy>;
 200   using iterator = StringMapIterator<ValueTy>;
 201
 202   iterator begin() { return iterator(TheTable, NumBuckets == 0); }
 203   iterator end() { return iterator(TheTable + NumBuckets, true); }
 204   const_iterator begin() const {
 205     return const_iterator(TheTable, NumBuckets == 0);
 206   }
 207   const_iterator end() const {
 208     return const_iterator(TheTable + NumBuckets, true);
 209   }
 210
 211   iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
 212     return make_range(StringMapKeyIterator<ValueTy>(begin()),
 213                       StringMapKeyIterator<ValueTy>(end()));
 214   }
 215
 216   iterator find(StringRef Key) {
 217     int Bucket = FindKey(Key);
 218     if (Bucket == -1)
 219       return end();
 220     return iterator(TheTable + Bucket, true);
 221   }
 222
 223   const_iterator find(StringRef Key) const {
 224     int Bucket = FindKey(Key);
 225     if (Bucket == -1)
 226       return end();
 227     return const_iterator(TheTable + Bucket, true);
 228   }
 229
 230   /// lookup - Return the entry for the specified key, or a default
 231   /// constructed value if no such entry exists.
 232   ValueTy lookup(StringRef Key) const {
 233     const_iterator it = find(Key);
 234     if (it != end())
 235       return it->second;
 236     return ValueTy();
 237   }
 238
 239   /// Lookup the ValueTy for the \p Key, or create a default constructed value
 240   /// if the key is not in the map.
 241   ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
 242
 243   /// count - Return 1 if the element is in the map, 0 otherwise.
 244   size_type count(StringRef Key) const { return find(Key) == end() ? 0 : 1; }
 245
 246   template <typename InputTy>
 247   size_type count(const StringMapEntry<InputTy> &MapEntry) const {
 248     return count(MapEntry.getKey());
 249   }
 250
 251   /// equal - check whether both of the containers are equal.
 252   bool operator==(const StringMap &RHS) const {
 253     if (size() != RHS.size())
 254       return false;
 255
 256     for (const auto &KeyValue : *this) {
 257       auto FindInRHS = RHS.find(KeyValue.getKey());
 258
 259       if (FindInRHS == RHS.end())
 260         return false;
 261
 262       if (!(KeyValue.getValue() == FindInRHS->getValue()))
 263         return false;
 264     }
 265
 266     return true;
 267   }
 268
 269   bool operator!=(const StringMap &RHS) const { return !(*this == RHS); }
 270
 271   /// insert - Insert the specified key/value pair into the map.  If the key
 272   /// already exists in the map, return false and ignore the request, otherwise
 273   /// insert it and return true.
 274   bool insert(MapEntryTy *KeyValue) {
 275     unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
 276     StringMapEntryBase *&Bucket = TheTable[BucketNo];
 277     if (Bucket && Bucket != getTombstoneVal())
 278       return false; // Already exists in map.
 279
 280     if (Bucket == getTombstoneVal())
 281       --NumTombstones;
 282     Bucket = KeyValue;
 283     ++NumItems;
 284     assert(NumItems + NumTombstones <= NumBuckets);
 285
 286     RehashTable();
 287     return true;
 288   }
 289
 290   /// insert - Inserts the specified key/value pair into the map if the key
 291   /// isn't already in the map. The bool component of the returned pair is true
 292   /// if and only if the insertion takes place, and the iterator component of
 293   /// the pair points to the element with key equivalent to the key of the pair.
 294   std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
 295     return try_emplace(KV.first, std::move(KV.second));
 296   }
 297
 298   /// Inserts an element or assigns to the current element if the key already
 299   /// exists. The return type is the same as try_emplace.
 300   template <typename V>
 301   std::pair<iterator, bool> insert_or_assign(StringRef Key, V &&Val) {
 302     auto Ret = try_emplace(Key, std::forward<V>(Val));
 303     if (!Ret.second)
 304       Ret.first->second = std::forward<V>(Val);
 305     return Ret;
 306   }
 307
 308   /// Emplace a new element for the specified key into the map if the key isn't
 309   /// already in the map. The bool component of the returned pair is true
 310   /// if and only if the insertion takes place, and the iterator component of
 311   /// the pair points to the element with key equivalent to the key of the pair.
 312   template <typename... ArgsTy>
 313   std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
 314     unsigned BucketNo = LookupBucketFor(Key);
 315     StringMapEntryBase *&Bucket = TheTable[BucketNo];
 316     if (Bucket && Bucket != getTombstoneVal())
 317       return std::make_pair(iterator(TheTable + BucketNo, false),
 318                             false); // Already exists in map.
 319
 320     if (Bucket == getTombstoneVal())
 321       --NumTombstones;
 322     Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
 323     ++NumItems;
 324     assert(NumItems + NumTombstones <= NumBuckets);
 325
 326     BucketNo = RehashTable(BucketNo);
 327     return std::make_pair(iterator(TheTable + BucketNo, false), true);
 328   }
 329
 330   // clear - Empties out the StringMap
 331   void clear() {
 332     if (empty())
 333       return;
 334
 335     // Zap all values, resetting the keys back to non-present (not tombstone),
 336     // which is safe because we're removing all elements.
 337     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
 338       StringMapEntryBase *&Bucket = TheTable[I];
 339       if (Bucket && Bucket != getTombstoneVal()) {
 340         static_cast<MapEntryTy *>(Bucket)->Destroy(Allocator);
 341       }
 342       Bucket = nullptr;
 343     }
 344
 345     NumItems = 0;
 346     NumTombstones = 0;
 347   }
 348
 349   /// remove - Remove the specified key/value pair from the map, but do not
 350   /// erase it.  This aborts if the key is not in the map.
 351   void remove(MapEntryTy *KeyValue) { RemoveKey(KeyValue); }
 352
 353   void erase(iterator I) {
 354     MapEntryTy &V = *I;
 355     remove(&V);
 356     V.Destroy(Allocator);
 357   }
 358
 359   bool erase(StringRef Key) {
 360     iterator I = find(Key);
 361     if (I == end())
 362       return false;
 363     erase(I);
 364     return true;
 365   }
 366 };
 367
 368 template <typename DerivedTy, typename ValueTy>
 369 class StringMapIterBase
 370     : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
 371                                   ValueTy> {
 372 protected:
 373   StringMapEntryBase **Ptr = nullptr;
 374
 375 public:
 376   StringMapIterBase() = default;
 377
 378   explicit StringMapIterBase(StringMapEntryBase **Bucket,
 379                              bool NoAdvance = false)
 380       : Ptr(Bucket) {
 381     if (!NoAdvance)
 382       AdvancePastEmptyBuckets();
 383   }
 384
 385   DerivedTy &operator=(const DerivedTy &Other) {
 386     Ptr = Other.Ptr;
 387     return static_cast<DerivedTy &>(*this);
 388   }
 389
 390   bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
 391
 392   DerivedTy &operator++() { // Preincrement
 393     ++Ptr;
 394     AdvancePastEmptyBuckets();
 395     return static_cast<DerivedTy &>(*this);
 396   }
 397
 398   DerivedTy operator++(int) { // Post-increment
 399     DerivedTy Tmp(Ptr);
 400     ++*this;
 401     return Tmp;
 402   }
 403
 404 private:
 405   void AdvancePastEmptyBuckets() {
 406     while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
 407       ++Ptr;
 408   }
 409 };
 410
 411 template <typename ValueTy>
 412 class StringMapConstIterator
 413     : public StringMapIterBase<StringMapConstIterator<ValueTy>,
 414                                const StringMapEntry<ValueTy>> {
 415   using base = StringMapIterBase<StringMapConstIterator<ValueTy>,
 416                                  const StringMapEntry<ValueTy>>;
 417
 418 public:
 419   StringMapConstIterator() = default;
 420   explicit StringMapConstIterator(StringMapEntryBase **Bucket,
 421                                   bool NoAdvance = false)
 422       : base(Bucket, NoAdvance) {}
 423
 424   const StringMapEntry<ValueTy> &operator*() const {
 425     return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
 426   }
 427 };
 428
 429 template <typename ValueTy>
 430 class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
 431                                                    StringMapEntry<ValueTy>> {
 432   using base =
 433       StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
 434
 435 public:
 436   StringMapIterator() = default;
 437   explicit StringMapIterator(StringMapEntryBase **Bucket,
 438                              bool NoAdvance = false)
 439       : base(Bucket, NoAdvance) {}
 440
 441   StringMapEntry<ValueTy> &operator*() const {
 442     return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
 443   }
 444
 445   operator StringMapConstIterator<ValueTy>() const {
 446     return StringMapConstIterator<ValueTy>(this->Ptr, true);
 447   }
 448 };
 449
 450 template <typename ValueTy>
 451 class StringMapKeyIterator
 452     : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
 453                                    StringMapConstIterator<ValueTy>,
 454                                    std::forward_iterator_tag, StringRef> {
 455   using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
 456                                      StringMapConstIterator<ValueTy>,
 457                                      std::forward_iterator_tag, StringRef>;
 458
 459 public:
 460   StringMapKeyIterator() = default;
 461   explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
 462       : base(std::move(Iter)) {}
 463
 464   StringRef &operator*() {
 465     Key = this->wrapped()->getKey();
 466     return Key;
 467   }
 468
 469 private:
 470   StringRef Key;
 471 };
 472
 473 } // end namespace llvm
 474
 475 #endif // LLVM_ADT_STRINGMAP_H