LCOV - code coverage report
Current view: top level - include/llvm/ADT - StringMap.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 173 174 99.4 %
Date: 2017-09-14 15:23:50 Functions: 996 1298 76.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             :   unsigned StrLen;
      41             : 
      42             : public:
      43   242684745 :   explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
      44             : 
      45   889716700 :   unsigned 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     4646120 :       : ItemSize(itemSize) {}
      64             :   StringMapImpl(StringMapImpl &&RHS)
      65       25385 :       : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
      66       25385 :         NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
      67       44091 :         ItemSize(RHS.ItemSize) {
      68       16032 :     RHS.TheTable = nullptr;
      69       16032 :     RHS.NumBuckets = 0;
      70       16032 :     RHS.NumItems = 0;
      71       16032 :     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  1964285390 :     uintptr_t Val = static_cast<uintptr_t>(-1);
     104  1964285390 :     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           7 :   bool empty() const { return NumItems == 0; }
     112             :   unsigned size() const { return NumItems; }
     113             : 
     114             :   void swap(StringMapImpl &Other) {
     115       23912 :     std::swap(TheTable, Other.TheTable);
     116       23912 :     std::swap(NumBuckets, Other.NumBuckets);
     117       23912 :     std::swap(NumItems, Other.NumItems);
     118       23912 :     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     2648904 : class StringMapEntry : public StringMapEntryBase {
     127             : public:
     128             :   ValueTy second;
     129             : 
     130    22072397 :   explicit StringMapEntry(unsigned strLen)
     131    47735587 :     : StringMapEntryBase(strLen), second() {}
     132             :   template <typename... InitTy>
     133   220612348 :   StringMapEntry(unsigned strLen, InitTy &&... InitVals)
     134   441623459 :       : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
     135             :   StringMapEntry(StringMapEntry &E) = delete;
     136             : 
     137             :   StringRef getKey() const {
     138   348182613 :     return StringRef(getKeyData(), getKeyLength());
     139             :   }
     140             : 
     141       15696 :   const ValueTy &getValue() const { return second; }
     142      774738 :   ValueTy &getValue() { return second; }
     143             : 
     144      764232 :   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   734026767 :   const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
     150             : 
     151    38135558 :   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   242684651 :   static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
     157             :                                 InitTy &&... InitVals) {
     158   242684651 :     unsigned KeyLength = Key.size();
     159             : 
     160             :     // Allocate a new item with space for the string at the end and a null
     161             :     // terminator.
     162   242684651 :     unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
     163             :       KeyLength+1;
     164   242684651 :     unsigned Alignment = alignof(StringMapEntry);
     165             : 
     166   242684651 :     StringMapEntry *NewItem =
     167   242684651 :       static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
     168             : 
     169   149062537 :     if (NewItem == nullptr)
     170           0 :       report_bad_alloc_error("Allocation of StringMap entry failed.");
     171             : 
     172             :     // Construct the value.
     173   485369307 :     new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
     174             : 
     175             :     // Copy the string information.
     176   242684655 :     char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
     177   242684655 :     if (KeyLength > 0)
     178   485068064 :       memcpy(StrBuffer, Key.data(), KeyLength);
     179   242684655 :     StrBuffer[KeyLength] = 0;  // Null terminate for convenience of clients.
     180   242684655 :     return NewItem;
     181             :   }
     182             : 
     183             :   /// Create - Create a StringMapEntry with normal malloc/free.
     184             :   template <typename... InitType>
     185             :   static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
     186             :     MallocAllocator A;
     187      751709 :     return Create(Key, A, std::forward<InitType>(InitVal)...);
     188             :   }
     189             : 
     190             :   static StringMapEntry *Create(StringRef Key) {
     191     1503412 :     return Create(Key, ValueTy());
     192             :   }
     193             : 
     194             :   /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
     195             :   /// into a StringMapEntry, return the StringMapEntry itself.
     196             :   static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
     197     2774146 :     char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
     198             :     return *reinterpret_cast<StringMapEntry*>(Ptr);
     199             :   }
     200             : 
     201             :   /// Destroy - Destroy this StringMapEntry, releasing memory back to the
     202             :   /// specified allocator.
     203             :   template<typename AllocatorTy>
     204     1277380 :   void Destroy(AllocatorTy &Allocator) {
     205             :     // Free memory referenced by the item.
     206   135971869 :     unsigned AllocSize =
     207   271553824 :         static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1;
     208     1352233 :     this->~StringMapEntry();
     209   271941173 :     Allocator.Deallocate(static_cast<void *>(this), AllocSize);
     210     1277380 :   }
     211             : 
     212             :   /// Destroy this object, releasing memory back to the malloc allocator.
     213             :   void Destroy() {
     214             :     MallocAllocator A;
     215     5075252 :     Destroy(A);
     216             :   }
     217             : };
     218             : 
     219             : /// StringMap - This is an unconventional map that is specialized for handling
     220             : /// keys that are "strings", which are basically ranges of bytes. This does some
     221             : /// funky memory allocation and hashing things to make it extremely efficient,
     222             : /// storing the string data *after* the value in the map.
     223             : template<typename ValueTy, typename AllocatorTy = MallocAllocator>
     224             : class StringMap : public StringMapImpl {
     225             :   AllocatorTy Allocator;
     226             : 
     227             : public:
     228             :   using MapEntryTy = StringMapEntry<ValueTy>;
     229             : 
     230     9586966 :   StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
     231             : 
     232      716738 :   explicit StringMap(unsigned InitialSize)
     233      932897 :     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
     234             : 
     235      147215 :   explicit StringMap(AllocatorTy A)
     236      294430 :     : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
     237             : 
     238             :   StringMap(unsigned InitialSize, AllocatorTy A)
     239             :     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
     240             :       Allocator(A) {}
     241             : 
     242       31150 :   StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
     243       31150 :       : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
     244      341812 :     for (const auto &P : List) {
     245      776152 :       insert(P);
     246             :     }
     247       31150 :   }
     248             : 
     249       16020 :   StringMap(StringMap &&RHS)
     250       32064 :       : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
     251             : 
     252       16803 :   StringMap(const StringMap &RHS) :
     253             :     StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
     254       33606 :     Allocator(RHS.Allocator) {
     255       16803 :     if (RHS.empty())
     256             :       return;
     257             : 
     258             :     // Allocate TheTable of the same size as RHS's TheTable, and set the
     259             :     // sentinel appropriately (and NumBuckets).
     260       13920 :     init(RHS.NumBuckets);
     261       13920 :     unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
     262       13920 :              *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
     263             : 
     264       13920 :     NumItems = RHS.NumItems;
     265       13920 :     NumTombstones = RHS.NumTombstones;
     266      614076 :     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     267      600156 :       StringMapEntryBase *Bucket = RHS.TheTable[I];
     268     1200313 :       if (!Bucket || Bucket == getTombstoneVal()) {
     269      334406 :         TheTable[I] = Bucket;
     270      334406 :         continue;
     271             :       }
     272             : 
     273      531500 :       TheTable[I] = MapEntryTy::Create(
     274             :           static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
     275             :           static_cast<MapEntryTy *>(Bucket)->getValue());
     276      265750 :       HashTable[I] = RHSHashTable[I];
     277             :     }
     278             : 
     279             :     // Note that here we've copied everything from the RHS into this object,
     280             :     // tombstones included. We could, instead, have re-probed for each key to
     281             :     // instantiate this new object without any tombstone buckets. The
     282             :     // assumption here is that items are rarely deleted from most StringMaps,
     283             :     // and so tombstones are rare, so the cost of re-probing for all inputs is
     284             :     // not worthwhile.
     285             :   }
     286             : 
     287             :   StringMap &operator=(StringMap RHS) {
     288       23912 :     StringMapImpl::swap(RHS);
     289       11956 :     std::swap(Allocator, RHS.Allocator);
     290             :     return *this;
     291             :   }
     292             : 
     293     4079409 :   ~StringMap() {
     294             :     // Delete all the elements in the map, but don't reset the elements
     295             :     // to default values.  This is a copy of clear(), but avoids unnecessary
     296             :     // work not required in the destructor.
     297     4480624 :     if (!empty()) {
     298   278419408 :       for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     299   277043656 :         StringMapEntryBase *Bucket = TheTable[I];
     300   408809096 :         if (Bucket && Bucket != getTombstoneVal()) {
     301   131764996 :           static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
     302             :         }
     303             :       }
     304             :     }
     305     4480625 :     free(TheTable);
     306     4447836 :   }
     307             : 
     308    76267214 :   AllocatorTy &getAllocator() { return Allocator; }
     309           5 :   const AllocatorTy &getAllocator() const { return Allocator; }
     310             : 
     311             :   using key_type = const char*;
     312             :   using mapped_type = ValueTy;
     313             :   using value_type = StringMapEntry<ValueTy>;
     314             :   using size_type = size_t;
     315             : 
     316             :   using const_iterator = StringMapConstIterator<ValueTy>;
     317             :   using iterator = StringMapIterator<ValueTy>;
     318             : 
     319             :   iterator begin() {
     320     2814263 :     return iterator(TheTable, NumBuckets == 0);
     321             :   }
     322             :   iterator end() {
     323    20812184 :     return iterator(TheTable+NumBuckets, true);
     324             :   }
     325             :   const_iterator begin() const {
     326     2878596 :     return const_iterator(TheTable, NumBuckets == 0);
     327             :   }
     328             :   const_iterator end() const {
     329    38804638 :     return const_iterator(TheTable+NumBuckets, true);
     330             :   }
     331             : 
     332             :   iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
     333         193 :     return make_range(StringMapKeyIterator<ValueTy>(begin()),
     334           2 :                       StringMapKeyIterator<ValueTy>(end()));
     335             :   }
     336             : 
     337     5643150 :   iterator find(StringRef Key) {
     338     5643150 :     int Bucket = FindKey(Key);
     339     5643156 :     if (Bucket == -1) return end();
     340     4657684 :     return iterator(TheTable+Bucket, true);
     341             :   }
     342             : 
     343    12588135 :   const_iterator find(StringRef Key) const {
     344    12588135 :     int Bucket = FindKey(Key);
     345    12588135 :     if (Bucket == -1) return end();
     346    12596472 :     return const_iterator(TheTable+Bucket, true);
     347             :   }
     348             : 
     349             :   /// lookup - Return the entry for the specified key, or a default
     350             :   /// constructed value if no such entry exists.
     351     9939875 :   ValueTy lookup(StringRef Key) const {
     352     9939875 :     const_iterator it = find(Key);
     353    29819625 :     if (it != end())
     354     4446604 :       return it->second;
     355      178543 :     return ValueTy();
     356             :   }
     357             : 
     358             :   /// Lookup the ValueTy for the \p Key, or create a default constructed value
     359             :   /// if the key is not in the map.
     360    60818922 :   ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
     361             : 
     362             :   /// count - Return 1 if the element is in the map, 0 otherwise.
     363             :   size_type count(StringRef Key) const {
     364     4103772 :     return find(Key) == end() ? 0 : 1;
     365             :   }
     366             : 
     367             :   /// insert - Insert the specified key/value pair into the map.  If the key
     368             :   /// already exists in the map, return false and ignore the request, otherwise
     369             :   /// insert it and return true.
     370      796332 :   bool insert(MapEntryTy *KeyValue) {
     371     1592664 :     unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
     372      796332 :     StringMapEntryBase *&Bucket = TheTable[BucketNo];
     373      983319 :     if (Bucket && Bucket != getTombstoneVal())
     374             :       return false;  // Already exists in map.
     375             : 
     376      695046 :     if (Bucket == getTombstoneVal())
     377       85701 :       --NumTombstones;
     378      695046 :     Bucket = KeyValue;
     379      695046 :     ++NumItems;
     380             :     assert(NumItems + NumTombstones <= NumBuckets);
     381             : 
     382      695046 :     RehashTable();
     383      695046 :     return true;
     384             :   }
     385             : 
     386             :   /// insert - Inserts the specified key/value pair into the map if the key
     387             :   /// isn't already in the map. The bool component of the returned pair is true
     388             :   /// if and only if the insertion takes place, and the iterator component of
     389             :   /// the pair points to the element with key equivalent to the key of the pair.
     390             :   std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
     391   439999261 :     return try_emplace(KV.first, std::move(KV.second));
     392             :   }
     393             : 
     394             :   /// Emplace a new element for the specified key into the map if the key isn't
     395             :   /// already in the map. The bool component of the returned pair is true
     396             :   /// if and only if the insertion takes place, and the iterator component of
     397             :   /// the pair points to the element with key equivalent to the key of the pair.
     398             :   template <typename... ArgsTy>
     399   470792412 :   std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
     400   470792412 :     unsigned BucketNo = LookupBucketFor(Key);
     401   470792412 :     StringMapEntryBase *&Bucket = TheTable[BucketNo];
     402   699940571 :     if (Bucket && Bucket != getTombstoneVal())
     403   229125217 :       return std::make_pair(iterator(TheTable + BucketNo, false),
     404   458250434 :                             false); // Already exists in map.
     405             : 
     406   241667195 :     if (Bucket == getTombstoneVal())
     407       22942 :       --NumTombstones;
     408   241667195 :     Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
     409   241667192 :     ++NumItems;
     410             :     assert(NumItems + NumTombstones <= NumBuckets);
     411             : 
     412   241667192 :     BucketNo = RehashTable(BucketNo);
     413   725001591 :     return std::make_pair(iterator(TheTable + BucketNo, false), true);
     414             :   }
     415             : 
     416             :   // clear - Empties out the StringMap
     417      560303 :   void clear() {
     418      607682 :     if (empty()) return;
     419             : 
     420             :     // Zap all values, resetting the keys back to non-present (not tombstone),
     421             :     // which is safe because we're removing all elements.
     422    10571166 :     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     423    10387376 :       StringMapEntryBase *&Bucket = TheTable[I];
     424    12027395 :       if (Bucket && Bucket != getTombstoneVal()) {
     425     1277326 :         static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
     426             :       }
     427    10387376 :       Bucket = nullptr;
     428             :     }
     429             : 
     430      183790 :     NumItems = 0;
     431      183790 :     NumTombstones = 0;
     432             :   }
     433             : 
     434             :   /// remove - Remove the specified key/value pair from the map, but do not
     435             :   /// erase it.  This aborts if the key is not in the map.
     436             :   void remove(MapEntryTy *KeyValue) {
     437     2872884 :     RemoveKey(KeyValue);
     438             :   }
     439             : 
     440        7509 :   void erase(iterator I) {
     441      391848 :     MapEntryTy &V = *I;
     442      391848 :     remove(&V);
     443      781760 :     V.Destroy(Allocator);
     444        7509 :   }
     445             : 
     446      383755 :   bool erase(StringRef Key) {
     447      383755 :     iterator I = find(Key);
     448     1151265 :     if (I == end()) return false;
     449      383747 :     erase(I);
     450      383747 :     return true;
     451             :   }
     452             : };
     453             : 
     454             : template <typename DerivedTy, typename ValueTy>
     455             : class StringMapIterBase
     456             :     : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
     457             :                                   ValueTy> {
     458             : protected:
     459             :   StringMapEntryBase **Ptr = nullptr;
     460             : 
     461             : public:
     462          11 :   StringMapIterBase() = default;
     463             : 
     464           4 :   explicit StringMapIterBase(StringMapEntryBase **Bucket,
     465             :                              bool NoAdvance = false)
     466           4 :       : Ptr(Bucket) {
     467     2846569 :     if (!NoAdvance) AdvancePastEmptyBuckets();
     468             :   }
     469             : 
     470             :   DerivedTy &operator=(const DerivedTy &Other) {
     471             :     Ptr = Other.Ptr;
     472             :     return static_cast<DerivedTy &>(*this);
     473             :   }
     474             : 
     475     1751872 :   bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
     476             : 
     477             :   DerivedTy &operator++() { // Preincrement
     478    98866705 :     ++Ptr;
     479          96 :     AdvancePastEmptyBuckets();
     480             :     return static_cast<DerivedTy &>(*this);
     481             :   }
     482             : 
     483             :   DerivedTy operator++(int) { // Post-increment
     484           8 :     DerivedTy Tmp(Ptr);
     485           4 :     ++*this;
     486             :     return Tmp;
     487             :   }
     488             : 
     489             : private:
     490             :   void AdvancePastEmptyBuckets() {
     491  1379177493 :     while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
     492   234426866 :       ++Ptr;
     493             :   }
     494             : };
     495             : 
     496             : template <typename ValueTy>
     497             : class StringMapConstIterator
     498             :     : public StringMapIterBase<StringMapConstIterator<ValueTy>,
     499             :                                const StringMapEntry<ValueTy>> {
     500             :   using base = StringMapIterBase<StringMapConstIterator<ValueTy>,
     501             :                                  const StringMapEntry<ValueTy>>;
     502             : 
     503             : public:
     504             :   StringMapConstIterator() = default;
     505             :   explicit StringMapConstIterator(StringMapEntryBase **Bucket,
     506             :                                   bool NoAdvance = false)
     507    30943252 :       : base(Bucket, NoAdvance) {}
     508             : 
     509             :   const StringMapEntry<ValueTy> &operator*() const {
     510    37027897 :     return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
     511             :   }
     512             : };
     513             : 
     514             : template <typename ValueTy>
     515             : class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
     516             :                                                    StringMapEntry<ValueTy>> {
     517             :   using base =
     518             :       StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
     519             : 
     520             : public:
     521          22 :   StringMapIterator() = default;
     522             :   explicit StringMapIterator(StringMapEntryBase **Bucket,
     523             :                              bool NoAdvance = false)
     524   728008816 :       : base(Bucket, NoAdvance) {}
     525             : 
     526             :   StringMapEntry<ValueTy> &operator*() const {
     527   322706764 :     return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
     528             :   }
     529             : 
     530             :   operator StringMapConstIterator<ValueTy>() const {
     531     4728112 :     return StringMapConstIterator<ValueTy>(this->Ptr, true);
     532             :   }
     533             : };
     534             : 
     535             : template <typename ValueTy>
     536             : class StringMapKeyIterator
     537             :     : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
     538             :                                    StringMapConstIterator<ValueTy>,
     539             :                                    std::forward_iterator_tag, StringRef> {
     540             :   using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
     541             :                                      StringMapConstIterator<ValueTy>,
     542             :                                      std::forward_iterator_tag, StringRef>;
     543             : 
     544             : public:
     545             :   StringMapKeyIterator() = default;
     546             :   explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
     547         130 :       : base(std::move(Iter)) {}
     548             : 
     549             :   StringRef &operator*() {
     550        2337 :     Key = this->wrapped()->getKey();
     551             :     return Key;
     552             :   }
     553             : 
     554             : private:
     555             :   StringRef Key;
     556             : };
     557             : 
     558             : } // end namespace llvm
     559             : 
     560             : #endif // LLVM_ADT_STRINGMAP_H

Generated by: LCOV version 1.13