LCOV - code coverage report
Current view: top level - include/llvm/ADT - StringMap.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 134 134 100.0 %
Date: 2018-07-13 00:08:38 Functions: 1264 1706 74.1 %
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   369676310 :   explicit StringMapEntryBase(size_t Len) : StrLen(Len) {}
      44             : 
      45  1232233322 :   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     7263842 :       : ItemSize(itemSize) {}
      64             :   StringMapImpl(StringMapImpl &&RHS)
      65      224179 :       : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
      66      224179 :         NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
      67      345379 :         ItemSize(RHS.ItemSize) {
      68      163579 :     RHS.TheTable = nullptr;
      69      163579 :     RHS.NumBuckets = 0;
      70      163579 :     RHS.NumItems = 0;
      71      163579 :     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     2157356 : class StringMapEntry : public StringMapEntryBase {
     127             : public:
     128             :   ValueTy second;
     129             : 
     130    36796383 :   explicit StringMapEntry(size_t strLen)
     131    31196584 :     : StringMapEntryBase(strLen), second() {}
     132             :   template <typename... InitTy>
     133   332879927 :   StringMapEntry(size_t strLen, InitTy &&... InitVals)
     134   332438537 :       : 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       29422 :   const ValueTy &getValue() const { return second; }
     142     1778612 :   ValueTy &getValue() { return second; }
     143             : 
     144     1310738 :   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  1154968363 :   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   369676343 :   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   369676343 :     size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1;
     163             :     size_t Alignment = alignof(StringMapEntry);
     164             : 
     165   136194510 :     StringMapEntry *NewItem =
     166             :       static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
     167             :     assert(NewItem && "Unhandled out-of-memory");
     168             : 
     169             :     // Construct the value.
     170         374 :     new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
     171             : 
     172             :     // Copy the string information.
     173             :     char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
     174   369676308 :     if (KeyLength > 0)
     175   369436668 :       memcpy(StrBuffer, Key.data(), KeyLength);
     176   369676308 :     StrBuffer[KeyLength] = 0;  // Null terminate for convenience of clients.
     177   369676308 :     return NewItem;
     178             :   }
     179             : 
     180             :   /// Create - Create a StringMapEntry with normal malloc/free.
     181             :   template <typename... InitType>
     182             :   static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
     183             :     MallocAllocator A;
     184     1297515 :     return Create(Key, A, std::forward<InitType>(InitVal)...);
     185             :   }
     186             : 
     187             :   static StringMapEntry *Create(StringRef Key) {
     188     2595024 :     return Create(Key, ValueTy());
     189             :   }
     190             : 
     191             :   /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
     192             :   /// into a StringMapEntry, return the StringMapEntry itself.
     193             :   static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
     194             :     char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
     195             :     return *reinterpret_cast<StringMapEntry*>(Ptr);
     196             :   }
     197             : 
     198             :   /// Destroy - Destroy this StringMapEntry, releasing memory back to the
     199             :   /// specified allocator.
     200             :   template<typename AllocatorTy>
     201     1993174 :   void Destroy(AllocatorTy &Allocator) {
     202             :     // Free memory referenced by the item.
     203             :     size_t AllocSize = sizeof(StringMapEntry) + getKeyLength() + 1;
     204             :     this->~StringMapEntry();
     205             :     Allocator.Deallocate(static_cast<void *>(this), AllocSize);
     206     1993174 :   }
     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.
     219             : template<typename ValueTy, typename AllocatorTy = MallocAllocator>
     220             : class StringMap : public StringMapImpl {
     221             :   AllocatorTy Allocator;
     222             : 
     223             : public:
     224             :   using MapEntryTy = StringMapEntry<ValueTy>;
     225             : 
     226     6884146 :   StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
     227             : 
     228      941645 :   explicit StringMap(unsigned InitialSize)
     229      941645 :     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
     230             : 
     231      220374 :   explicit StringMap(AllocatorTy A)
     232      220374 :     : 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       46492 :   StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
     239       46492 :       : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
     240      860430 :     for (const auto &P : List) {
     241      369380 :       insert(P);
     242             :     }
     243       46492 :   }
     244             : 
     245      163560 :   StringMap(StringMap &&RHS)
     246             :       : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
     247             : 
     248       21653 :   StringMap(const StringMap &RHS) :
     249             :     StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
     250       21653 :     Allocator(RHS.Allocator) {
     251       21653 :     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       17372 :     init(RHS.NumBuckets);
     257       17372 :     unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
     258       17372 :              *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
     259             : 
     260       17372 :     NumItems = RHS.NumItems;
     261       17372 :     NumTombstones = RHS.NumTombstones;
     262     1574260 :     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     263      778444 :       StringMapEntryBase *Bucket = RHS.TheTable[I];
     264     1171200 :       if (!Bucket || Bucket == getTombstoneVal()) {
     265      392756 :         TheTable[I] = Bucket;
     266      392756 :         continue;
     267             :       }
     268             : 
     269      385688 :       TheTable[I] = MapEntryTy::Create(
     270             :           static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
     271             :           static_cast<MapEntryTy *>(Bucket)->getValue());
     272      385688 :       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     7130667 :   ~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     7130093 :     if (!empty()) {
     294   415251658 :       for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     295   412878178 :         StringMapEntryBase *Bucket = TheTable[I];
     296   412878178 :         if (Bucket && Bucket != getTombstoneVal()) {
     297     1986239 :           static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
     298             :         }
     299             :       }
     300             :     }
     301     7670287 :     free(TheTable);
     302     7626852 :   }
     303             : 
     304   117707107 :   AllocatorTy &getAllocator() { return Allocator; }
     305           5 :   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    12589012 :     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    29037085 :     return const_iterator(TheTable+NumBuckets, true);
     326             :   }
     327             : 
     328             :   iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
     329          30 :     return make_range(StringMapKeyIterator<ValueTy>(begin()),
     330             :                       StringMapKeyIterator<ValueTy>(end()));
     331             :   }
     332             : 
     333     6904400 :   iterator find(StringRef Key) {
     334     6904400 :     int Bucket = FindKey(Key);
     335     6904404 :     if (Bucket == -1) return end();
     336     2989221 :     return iterator(TheTable+Bucket, true);
     337             :   }
     338             : 
     339    18100908 :   const_iterator find(StringRef Key) const {
     340    18100908 :     int Bucket = FindKey(Key);
     341    18100908 :     if (Bucket == -1) return end();
     342     8141926 :     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    13932719 :   ValueTy lookup(StringRef Key) const {
     348    13932719 :     const_iterator it = find(Key);
     349    27865438 :     if (it != end())
     350     6149610 :       return it->second;
     351      208636 :     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    97639134 :   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     4316228 :     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     1243120 :   bool insert(MapEntryTy *KeyValue) {
     367     2486240 :     unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
     368     1243120 :     StringMapEntryBase *&Bucket = TheTable[BucketNo];
     369     1243120 :     if (Bucket && Bucket != getTombstoneVal())
     370             :       return false;  // Already exists in map.
     371             : 
     372     1096550 :     if (Bucket == getTombstoneVal())
     373      113058 :       --NumTombstones;
     374     1096550 :     Bucket = KeyValue;
     375     1096550 :     ++NumItems;
     376             :     assert(NumItems + NumTombstones <= NumBuckets);
     377             : 
     378     1096550 :     RehashTable();
     379     1096550 :     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   715678500 :     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   765806756 :   std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
     396   765806756 :     unsigned BucketNo = LookupBucketFor(Key);
     397   765805949 :     StringMapEntryBase *&Bucket = TheTable[BucketNo];
     398   765805949 :     if (Bucket && Bucket != getTombstoneVal())
     399             :       return std::make_pair(iterator(TheTable + BucketNo, false),
     400             :                             false); // Already exists in map.
     401             : 
     402   367990268 :     if (Bucket == getTombstoneVal())
     403       34531 :       --NumTombstones;
     404   367990268 :     Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
     405   367993372 :     ++NumItems;
     406             :     assert(NumItems + NumTombstones <= NumBuckets);
     407             : 
     408   367993372 :     BucketNo = RehashTable(BucketNo);
     409   367993431 :     return std::make_pair(iterator(TheTable + BucketNo, false), true);
     410             :   }
     411             : 
     412             :   // clear - Empties out the StringMap
     413      684359 :   void clear() {
     414      753827 :     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    14567567 :     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     419    14347168 :       StringMapEntryBase *&Bucket = TheTable[I];
     420     4658432 :       if (Bucket && Bucket != getTombstoneVal()) {
     421        6555 :         static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
     422             :       }
     423    14347168 :       Bucket = nullptr;
     424             :     }
     425             : 
     426      220399 :     NumItems = 0;
     427      220399 :     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     4545524 :     RemoveKey(KeyValue);
     434             :   }
     435             : 
     436        8666 :   void erase(iterator I) {
     437             :     MapEntryTy &V = *I;
     438             :     remove(&V);
     439         380 :     V.Destroy(Allocator);
     440        8666 :   }
     441             : 
     442      707279 :   bool erase(StringRef Key) {
     443      707279 :     iterator I = find(Key);
     444     1414558 :     if (I == end()) return false;
     445           8 :     erase(I);
     446      707270 :     return true;
     447             :   }
     448             : };
     449             : 
     450             : template <typename DerivedTy, typename ValueTy>
     451             : class StringMapIterBase
     452             :     : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
     453             :                                   ValueTy> {
     454             : protected:
     455             :   StringMapEntryBase **Ptr = nullptr;
     456             : 
     457             : public:
     458          11 :   StringMapIterBase() = default;
     459             : 
     460             :   explicit StringMapIterBase(StringMapEntryBase **Bucket,
     461             :                              bool NoAdvance = false)
     462             :       : Ptr(Bucket) {
     463     3694857 :     if (!NoAdvance) AdvancePastEmptyBuckets();
     464             :   }
     465             : 
     466             :   DerivedTy &operator=(const DerivedTy &Other) {
     467             :     Ptr = Other.Ptr;
     468             :     return static_cast<DerivedTy &>(*this);
     469             :   }
     470             : 
     471     3884316 :   bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
     472             : 
     473             :   DerivedTy &operator++() { // Preincrement
     474   144565770 :     ++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             : 
     485             : private:
     486             :   void AdvancePastEmptyBuckets() {
     487  1242879263 :     while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
     488   329245658 :       ++Ptr;
     489             :   }
     490             : };
     491             : 
     492             : template <typename ValueTy>
     493             : class StringMapConstIterator
     494             :     : public StringMapIterBase<StringMapConstIterator<ValueTy>,
     495             :                                const StringMapEntry<ValueTy>> {
     496             :   using base = StringMapIterBase<StringMapConstIterator<ValueTy>,
     497             :                                  const StringMapEntry<ValueTy>>;
     498             : 
     499             : public:
     500             :   StringMapConstIterator() = default;
     501             :   explicit StringMapConstIterator(StringMapEntryBase **Bucket,
     502             :                                   bool NoAdvance = false)
     503             :       : base(Bucket, NoAdvance) {}
     504             : 
     505             :   const StringMapEntry<ValueTy> &operator*() const {
     506    52893034 :     return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
     507             :   }
     508             : };
     509             : 
     510             : template <typename ValueTy>
     511             : class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
     512             :                                                    StringMapEntry<ValueTy>> {
     513             :   using base =
     514             :       StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
     515             : 
     516             : public:
     517             :   StringMapIterator() = default;
     518             :   explicit StringMapIterator(StringMapEntryBase **Bucket,
     519             :                              bool NoAdvance = false)
     520             :       : base(Bucket, NoAdvance) {}
     521             : 
     522             :   StringMapEntry<ValueTy> &operator*() const {
     523   514926859 :     return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
     524             :   }
     525             : 
     526             :   operator StringMapConstIterator<ValueTy>() const {
     527     1380891 :     return StringMapConstIterator<ValueTy>(this->Ptr, true);
     528             :   }
     529             : };
     530             : 
     531             : template <typename ValueTy>
     532             : class 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             : 
     540             : public:
     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             : 
     550             : private:
     551             :   StringRef Key;
     552             : };
     553             : 
     554             : } // end namespace llvm
     555             : 
     556             : #endif // LLVM_ADT_STRINGMAP_H

Generated by: LCOV version 1.13