LCOV - code coverage report
Current view: top level - include/llvm/ADT - StringMap.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 135 136 99.3 %
Date: 2018-05-20 00:06:23 Functions: 1201 1607 74.7 %
Legend: Lines: hit not hit

          Line data    Source code
       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             : 
      32             : namespace llvm {
      33             : 
      34             : template<typename ValueTy> class StringMapConstIterator;
      35             : template<typename ValueTy> class StringMapIterator;
      36             : template<typename ValueTy> class StringMapKeyIterator;
      37             : 
      38             : /// StringMapEntryBase - Shared base class of StringMapEntry instances.
      39             : class StringMapEntryBase {
      40             :   size_t StrLen;
      41             : 
      42             : public:
      43   372085461 :   explicit StringMapEntryBase(size_t Len) : StrLen(Len) {}
      44             : 
      45  1254711267 :   size_t getKeyLength() const { return StrLen; }
      46             : };
      47             : 
      48             : /// StringMapImpl - This is the base class of StringMap that is shared among
      49             : /// all of its instantiations.
      50             : class StringMapImpl {
      51             : protected:
      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             : 
      61             : protected:
      62             :   explicit StringMapImpl(unsigned itemSize)
      63     6837547 :       : ItemSize(itemSize) {}
      64             :   StringMapImpl(StringMapImpl &&RHS)
      65      225313 :       : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
      66      225313 :         NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
      67      345821 :         ItemSize(RHS.ItemSize) {
      68      165059 :     RHS.TheTable = nullptr;
      69      165059 :     RHS.NumBuckets = 0;
      70      165059 :     RHS.NumItems = 0;
      71      165059 :     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             : 
     101             : public:
     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           8 :   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.
     125             : template<typename ValueTy>
     126     2082048 : class StringMapEntry : public StringMapEntryBase {
     127             : public:
     128             :   ValueTy second;
     129             : 
     130    34465801 :   explicit StringMapEntry(size_t strLen)
     131    28482466 :     : StringMapEntryBase(strLen), second() {}
     132             :   template <typename... InitTy>
     133   337619660 :   StringMapEntry(size_t strLen, InitTy &&... InitVals)
     134   337097570 :       : 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       29153 :   const ValueTy &getValue() const { return second; }
     142     1918028 :   ValueTy &getValue() { return second; }
     143             : 
     144     1271437 :   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  1162605670 :   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   372085496 :   static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
     157             :                                 InitTy &&... InitVals) {
     158             :     size_t KeyLength = Key.size();
     159             : 
     160             :     // Allocate a new item with space for the string at the end and a null
     161             :     // terminator.
     162   372085496 :     size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1;
     163             :     size_t Alignment = alignof(StringMapEntry);
     164             : 
     165   144817532 :     StringMapEntry *NewItem =
     166             :       static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
     167             : 
     168   227267980 :     if (NewItem == nullptr)
     169           0 :       report_bad_alloc_error("Allocation of StringMap entry failed.");
     170             : 
     171             :     // Construct the value.
     172   227267980 :     new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
     173             : 
     174             :     // Copy the string information.
     175             :     char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
     176   372085465 :     if (KeyLength > 0)
     177   371879112 :       memcpy(StrBuffer, Key.data(), KeyLength);
     178   372085465 :     StrBuffer[KeyLength] = 0;  // Null terminate for convenience of clients.
     179   372085465 :     return NewItem;
     180             :   }
     181             : 
     182             :   /// Create - Create a StringMapEntry with normal malloc/free.
     183             :   template <typename... InitType>
     184             :   static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
     185             :     MallocAllocator A;
     186     1258848 :     return Create(Key, A, std::forward<InitType>(InitVal)...);
     187             :   }
     188             : 
     189             :   static StringMapEntry *Create(StringRef Key) {
     190     2517689 :     return Create(Key, ValueTy());
     191             :   }
     192             : 
     193             :   /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
     194             :   /// into a StringMapEntry, return the StringMapEntry itself.
     195             :   static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
     196             :     char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
     197             :     return *reinterpret_cast<StringMapEntry*>(Ptr);
     198             :   }
     199             : 
     200             :   /// Destroy - Destroy this StringMapEntry, releasing memory back to the
     201             :   /// specified allocator.
     202             :   template<typename AllocatorTy>
     203     1937280 :   void Destroy(AllocatorTy &Allocator) {
     204             :     // Free memory referenced by the item.
     205             :     size_t AllocSize = sizeof(StringMapEntry) + getKeyLength() + 1;
     206             :     this->~StringMapEntry();
     207             :     Allocator.Deallocate(static_cast<void *>(this), AllocSize);
     208     1937280 :   }
     209             : 
     210             :   /// Destroy this object, releasing memory back to the malloc allocator.
     211             :   void Destroy() {
     212             :     MallocAllocator A;
     213             :     Destroy(A);
     214             :   }
     215             : };
     216             : 
     217             : /// StringMap - This is an unconventional map that is specialized for handling
     218             : /// keys that are "strings", which are basically ranges of bytes. This does some
     219             : /// funky memory allocation and hashing things to make it extremely efficient,
     220             : /// storing the string data *after* the value in the map.
     221             : template<typename ValueTy, typename AllocatorTy = MallocAllocator>
     222             : class StringMap : public StringMapImpl {
     223             :   AllocatorTy Allocator;
     224             : 
     225             : public:
     226             :   using MapEntryTy = StringMapEntry<ValueTy>;
     227             : 
     228     6464787 :   StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
     229             : 
     230      914676 :   explicit StringMap(unsigned InitialSize)
     231      914676 :     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
     232             : 
     233      217089 :   explicit StringMap(AllocatorTy A)
     234      217089 :     : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
     235             : 
     236             :   StringMap(unsigned InitialSize, AllocatorTy A)
     237             :     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
     238             :       Allocator(A) {}
     239             : 
     240       49398 :   StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
     241       49398 :       : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
     242      895510 :     for (const auto &P : List) {
     243      392859 :       insert(P);
     244             :     }
     245       49398 :   }
     246             : 
     247      165040 :   StringMap(StringMap &&RHS)
     248             :       : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
     249             : 
     250       21617 :   StringMap(const StringMap &RHS) :
     251             :     StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
     252       21617 :     Allocator(RHS.Allocator) {
     253       21617 :     if (RHS.empty())
     254             :       return;
     255             : 
     256             :     // Allocate TheTable of the same size as RHS's TheTable, and set the
     257             :     // sentinel appropriately (and NumBuckets).
     258       17474 :     init(RHS.NumBuckets);
     259       17474 :     unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
     260       17474 :              *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
     261             : 
     262       17474 :     NumItems = RHS.NumItems;
     263       17474 :     NumTombstones = RHS.NumTombstones;
     264     1606682 :     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     265      794604 :       StringMapEntryBase *Bucket = RHS.TheTable[I];
     266     1192847 :       if (!Bucket || Bucket == getTombstoneVal()) {
     267      398243 :         TheTable[I] = Bucket;
     268      398243 :         continue;
     269             :       }
     270             : 
     271      396361 :       TheTable[I] = MapEntryTy::Create(
     272             :           static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
     273             :           static_cast<MapEntryTy *>(Bucket)->getValue());
     274      396361 :       HashTable[I] = RHSHashTable[I];
     275             :     }
     276             : 
     277             :     // Note that here we've copied everything from the RHS into this object,
     278             :     // tombstones included. We could, instead, have re-probed for each key to
     279             :     // instantiate this new object without any tombstone buckets. The
     280             :     // assumption here is that items are rarely deleted from most StringMaps,
     281             :     // and so tombstones are rare, so the cost of re-probing for all inputs is
     282             :     // not worthwhile.
     283             :   }
     284             : 
     285             :   StringMap &operator=(StringMap RHS) {
     286             :     StringMapImpl::swap(RHS);
     287             :     std::swap(Allocator, RHS.Allocator);
     288             :     return *this;
     289             :   }
     290             : 
     291     6398800 :   ~StringMap() {
     292             :     // Delete all the elements in the map, but don't reset the elements
     293             :     // to default values.  This is a copy of clear(), but avoids unnecessary
     294             :     // work not required in the destructor.
     295     6398290 :     if (!empty()) {
     296   411701291 :       for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     297   409536900 :         StringMapEntryBase *Bucket = TheTable[I];
     298   409536900 :         if (Bucket && Bucket != getTombstoneVal()) {
     299     1895546 :           static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
     300             :         }
     301             :       }
     302             :     }
     303     6895738 :     free(TheTable);
     304     6852313 :   }
     305             : 
     306   120375460 :   AllocatorTy &getAllocator() { return Allocator; }
     307           5 :   const AllocatorTy &getAllocator() const { return Allocator; }
     308             : 
     309             :   using key_type = const char*;
     310             :   using mapped_type = ValueTy;
     311             :   using value_type = StringMapEntry<ValueTy>;
     312             :   using size_type = size_t;
     313             : 
     314             :   using const_iterator = StringMapConstIterator<ValueTy>;
     315             :   using iterator = StringMapIterator<ValueTy>;
     316             : 
     317             :   iterator begin() {
     318             :     return iterator(TheTable, NumBuckets == 0);
     319             :   }
     320             :   iterator end() {
     321    12924599 :     return iterator(TheTable+NumBuckets, true);
     322             :   }
     323             :   const_iterator begin() const {
     324             :     return const_iterator(TheTable, NumBuckets == 0);
     325             :   }
     326             :   const_iterator end() const {
     327    29911181 :     return const_iterator(TheTable+NumBuckets, true);
     328             :   }
     329             : 
     330             :   iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
     331          30 :     return make_range(StringMapKeyIterator<ValueTy>(begin()),
     332             :                       StringMapKeyIterator<ValueTy>(end()));
     333             :   }
     334             : 
     335     7193420 :   iterator find(StringRef Key) {
     336     7193420 :     int Bucket = FindKey(Key);
     337     7193430 :     if (Bucket == -1) return end();
     338     3307649 :     return iterator(TheTable+Bucket, true);
     339             :   }
     340             : 
     341    20326594 :   const_iterator find(StringRef Key) const {
     342    20326594 :     int Bucket = FindKey(Key);
     343    20326597 :     if (Bucket == -1) return end();
     344    10496847 :     return const_iterator(TheTable+Bucket, true);
     345             :   }
     346             : 
     347             :   /// lookup - Return the entry for the specified key, or a default
     348             :   /// constructed value if no such entry exists.
     349    13645320 :   ValueTy lookup(StringRef Key) const {
     350    13645320 :     const_iterator it = find(Key);
     351    27290638 :     if (it != end())
     352     5978167 :       return it->second;
     353      205527 :     return ValueTy();
     354             :   }
     355             : 
     356             :   /// Lookup the ValueTy for the \p Key, or create a default constructed value
     357             :   /// if the key is not in the map.
     358    92049847 :   ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
     359             : 
     360             :   /// count - Return 1 if the element is in the map, 0 otherwise.
     361             :   size_type count(StringRef Key) const {
     362     9336406 :     return find(Key) == end() ? 0 : 1;
     363             :   }
     364             : 
     365             :   /// insert - Insert the specified key/value pair into the map.  If the key
     366             :   /// already exists in the map, return false and ignore the request, otherwise
     367             :   /// insert it and return true.
     368     1203262 :   bool insert(MapEntryTy *KeyValue) {
     369     2406524 :     unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
     370     1203262 :     StringMapEntryBase *&Bucket = TheTable[BucketNo];
     371     1203262 :     if (Bucket && Bucket != getTombstoneVal())
     372             :       return false;  // Already exists in map.
     373             : 
     374     1056564 :     if (Bucket == getTombstoneVal())
     375      108768 :       --NumTombstones;
     376     1056564 :     Bucket = KeyValue;
     377     1056564 :     ++NumItems;
     378             :     assert(NumItems + NumTombstones <= NumBuckets);
     379             : 
     380     1056564 :     RehashTable();
     381     1056564 :     return true;
     382             :   }
     383             : 
     384             :   /// insert - Inserts the specified key/value pair into the map if the key
     385             :   /// isn't already in the map. The bool component of the returned pair is true
     386             :   /// if and only if the insertion takes place, and the iterator component of
     387             :   /// the pair points to the element with key equivalent to the key of the pair.
     388             :   std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
     389   733386681 :     return try_emplace(KV.first, std::move(KV.second));
     390             :   }
     391             : 
     392             :   /// Emplace a new element for the specified key into the map if the key isn't
     393             :   /// already in the map. The bool component of the returned pair is true
     394             :   /// if and only if the insertion takes place, and the iterator component of
     395             :   /// the pair points to the element with key equivalent to the key of the pair.
     396             :   template <typename... ArgsTy>
     397   780842080 :   std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
     398   780842080 :     unsigned BucketNo = LookupBucketFor(Key);
     399   780842765 :     StringMapEntryBase *&Bucket = TheTable[BucketNo];
     400   780842765 :     if (Bucket && Bucket != getTombstoneVal())
     401             :       return std::make_pair(iterator(TheTable + BucketNo, false),
     402             :                             false); // Already exists in map.
     403             : 
     404   370425922 :     if (Bucket == getTombstoneVal())
     405       30403 :       --NumTombstones;
     406   370425922 :     Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
     407   370430193 :     ++NumItems;
     408             :     assert(NumItems + NumTombstones <= NumBuckets);
     409             : 
     410   370430193 :     BucketNo = RehashTable(BucketNo);
     411   370430266 :     return std::make_pair(iterator(TheTable + BucketNo, false), true);
     412             :   }
     413             : 
     414             :   // clear - Empties out the StringMap
     415      629447 :   void clear() {
     416      695790 :     if (empty()) return;
     417             : 
     418             :     // Zap all values, resetting the keys back to non-present (not tombstone),
     419             :     // which is safe because we're removing all elements.
     420    14331659 :     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     421    14116032 :       StringMapEntryBase *&Bucket = TheTable[I];
     422     4602864 :       if (Bucket && Bucket != getTombstoneVal()) {
     423       41421 :         static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
     424             :       }
     425    14116032 :       Bucket = nullptr;
     426             :     }
     427             : 
     428      215627 :     NumItems = 0;
     429      215627 :     NumTombstones = 0;
     430             :   }
     431             : 
     432             :   /// remove - Remove the specified key/value pair from the map, but do not
     433             :   /// erase it.  This aborts if the key is not in the map.
     434             :   void remove(MapEntryTy *KeyValue) {
     435     4279351 :     RemoveKey(KeyValue);
     436             :   }
     437             : 
     438        8162 :   void erase(iterator I) {
     439             :     MapEntryTy &V = *I;
     440             :     remove(&V);
     441         313 :     V.Destroy(Allocator);
     442        8162 :   }
     443             : 
     444      697751 :   bool erase(StringRef Key) {
     445      697751 :     iterator I = find(Key);
     446     1395502 :     if (I == end()) return false;
     447          10 :     erase(I);
     448      697743 :     return true;
     449             :   }
     450             : };
     451             : 
     452             : template <typename DerivedTy, typename ValueTy>
     453             : class StringMapIterBase
     454             :     : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
     455             :                                   ValueTy> {
     456             : protected:
     457             :   StringMapEntryBase **Ptr = nullptr;
     458             : 
     459             : public:
     460          11 :   StringMapIterBase() = default;
     461             : 
     462             :   explicit StringMapIterBase(StringMapEntryBase **Bucket,
     463             :                              bool NoAdvance = false)
     464             :       : Ptr(Bucket) {
     465     3850744 :     if (!NoAdvance) AdvancePastEmptyBuckets();
     466             :   }
     467             : 
     468             :   DerivedTy &operator=(const DerivedTy &Other) {
     469             :     Ptr = Other.Ptr;
     470             :     return static_cast<DerivedTy &>(*this);
     471             :   }
     472             : 
     473     5076372 :   bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
     474             : 
     475             :   DerivedTy &operator++() { // Preincrement
     476   140839688 :     ++Ptr;
     477             :     AdvancePastEmptyBuckets();
     478             :     return static_cast<DerivedTy &>(*this);
     479             :   }
     480             : 
     481             :   DerivedTy operator++(int) { // Post-increment
     482             :     DerivedTy Tmp(Ptr);
     483             :     ++*this;
     484             :     return Tmp;
     485             :   }
     486             : 
     487             : private:
     488             :   void AdvancePastEmptyBuckets() {
     489  1255451674 :     while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
     490   330305396 :       ++Ptr;
     491             :   }
     492             : };
     493             : 
     494             : template <typename ValueTy>
     495             : class StringMapConstIterator
     496             :     : public StringMapIterBase<StringMapConstIterator<ValueTy>,
     497             :                                const StringMapEntry<ValueTy>> {
     498             :   using base = StringMapIterBase<StringMapConstIterator<ValueTy>,
     499             :                                  const StringMapEntry<ValueTy>>;
     500             : 
     501             : public:
     502             :   StringMapConstIterator() = default;
     503             :   explicit StringMapConstIterator(StringMapEntryBase **Bucket,
     504             :                                   bool NoAdvance = false)
     505             :       : base(Bucket, NoAdvance) {}
     506             : 
     507             :   const StringMapEntry<ValueTy> &operator*() const {
     508    54438718 :     return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
     509             :   }
     510             : };
     511             : 
     512             : template <typename ValueTy>
     513             : class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
     514             :                                                    StringMapEntry<ValueTy>> {
     515             :   using base =
     516             :       StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
     517             : 
     518             : public:
     519             :   StringMapIterator() = default;
     520             :   explicit StringMapIterator(StringMapEntryBase **Bucket,
     521             :                              bool NoAdvance = false)
     522             :       : base(Bucket, NoAdvance) {}
     523             : 
     524             :   StringMapEntry<ValueTy> &operator*() const {
     525   521080357 :     return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
     526             :   }
     527             : 
     528             :   operator StringMapConstIterator<ValueTy>() const {
     529     1377547 :     return StringMapConstIterator<ValueTy>(this->Ptr, true);
     530             :   }
     531             : };
     532             : 
     533             : template <typename ValueTy>
     534             : class StringMapKeyIterator
     535             :     : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
     536             :                                    StringMapConstIterator<ValueTy>,
     537             :                                    std::forward_iterator_tag, StringRef> {
     538             :   using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
     539             :                                      StringMapConstIterator<ValueTy>,
     540             :                                      std::forward_iterator_tag, StringRef>;
     541             : 
     542             : public:
     543             :   StringMapKeyIterator() = default;
     544             :   explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
     545             :       : base(std::move(Iter)) {}
     546             : 
     547             :   StringRef &operator*() {
     548             :     Key = this->wrapped()->getKey();
     549             :     return Key;
     550             :   }
     551             : 
     552             : private:
     553             :   StringRef Key;
     554             : };
     555             : 
     556             : } // end namespace llvm
     557             : 
     558             : #endif // LLVM_ADT_STRINGMAP_H

Generated by: LCOV version 1.13