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 181809536 : explicit StringMapEntryBase(size_t Len) : StrLen(Len) {}
44 :
45 0 : 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 12009928 : : ItemSize(itemSize) {}
64 : StringMapImpl(StringMapImpl &&RHS)
65 191849 : : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
66 191849 : NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
67 290557 : ItemSize(RHS.ItemSize) {
68 142495 : RHS.TheTable = nullptr;
69 142495 : RHS.NumBuckets = 0;
70 142495 : RHS.NumItems = 0;
71 142495 : 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 0 : unsigned getNumBuckets() const { return NumBuckets; }
109 0 : unsigned getNumItems() const { return NumItems; }
110 :
111 8 : bool empty() const { return NumItems == 0; }
112 0 : 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 167985 : class StringMapEntry : public StringMapEntryBase {
127 : public:
128 : ValueTy second;
129 :
130 6496959 : explicit StringMapEntry(size_t strLen)
131 6243625 : : StringMapEntryBase(strLen), second() {}
132 : template <typename... InitTy>
133 175238168 : StringMapEntry(size_t strLen, InitTy &&... InitVals)
134 175312395 : : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
135 0 : StringMapEntry(StringMapEntry &E) = delete;
136 0 :
137 0 : StringRef getKey() const {
138 201976860 : return StringRef(getKeyData(), getKeyLength());
139 0 : }
140 0 :
141 34704 : const ValueTy &getValue() const { return second; }
142 1203533 : ValueTy &getValue() { return second; }
143 :
144 2383191 : 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 3 : /// StringMapEntry object.
149 1176639147 : const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
150 :
151 31990155 : StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
152 :
153 : /// Create a StringMapEntry for the specified key construct the value using
154 : /// \p InitiVals.
155 1 : template <typename AllocatorTy, typename... InitTy>
156 181809225 : static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
157 2 : 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 181809225 : size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1;
163 : size_t Alignment = alignof(StringMapEntry);
164 :
165 : StringMapEntry *NewItem =
166 181805635 : static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
167 : assert(NewItem && "Unhandled out-of-memory");
168 0 :
169 : // Construct the value.
170 0 : new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
171 :
172 : // Copy the string information.
173 : char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
174 181809164 : if (KeyLength > 0)
175 181808759 : memcpy(StrBuffer, Key.data(), KeyLength);
176 181809164 : StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
177 181809164 : return NewItem;
178 : }
179 19064717 :
180 0 : /// Create - Create a StringMapEntry with normal malloc/free.
181 0 : template <typename... InitType>
182 0 : static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
183 0 : MallocAllocator A;
184 2370889 : return Create(Key, A, std::forward<InitType>(InitVal)...);
185 19064717 : }
186 :
187 : static StringMapEntry *Create(StringRef Key) {
188 2370889 : return Create(Key, ValueTy());
189 19064715 : }
190 :
191 0 : /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
192 : /// into a StringMapEntry, return the StringMapEntry itself.
193 0 : static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
194 : char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
195 : return *reinterpret_cast<StringMapEntry*>(Ptr);
196 : }
197 19064717 :
198 19064467 : /// Destroy - Destroy this StringMapEntry, releasing memory back to the
199 19064717 : /// specified allocator.
200 19064717 : template<typename AllocatorTy>
201 0 : void Destroy(AllocatorTy &Allocator) {
202 489888 : // Free memory referenced by the item.
203 0 : size_t AllocSize = sizeof(StringMapEntry) + getKeyLength() + 1;
204 0 : this->~StringMapEntry();
205 0 : Allocator.Deallocate(static_cast<void *>(this), AllocSize);
206 0 : }
207 0 :
208 489888 : /// Destroy this object, releasing memory back to the malloc allocator.
209 : void Destroy() {
210 : MallocAllocator A;
211 : Destroy(A);
212 489888 : }
213 0 : };
214 0 :
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 0 : /// storing the string data *after* the value in the map.
219 0 : template<typename ValueTy, typename AllocatorTy = MallocAllocator>
220 489888 : class StringMap : public StringMapImpl {
221 489663 : AllocatorTy Allocator;
222 489888 :
223 489888 : public:
224 0 : using MapEntryTy = StringMapEntry<ValueTy>;
225 6768513 :
226 5601365 : StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
227 0 :
228 633715 : explicit StringMap(unsigned InitialSize)
229 633715 : : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
230 0 :
231 6822544 : explicit StringMap(AllocatorTy A)
232 54031 : : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
233 :
234 : StringMap(unsigned InitialSize, AllocatorTy A)
235 6768513 : : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
236 0 : Allocator(A) {}
237 0 :
238 37292 : StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
239 1584 : : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
240 6759 : for (const auto &P : List) {
241 5175 : insert(P);
242 0 : }
243 6770098 : }
244 6794235 :
245 6768520 : StringMap(StringMap &&RHS)
246 6768514 : : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
247 0 :
248 75397 : StringMap(const StringMap &RHS) :
249 0 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
250 28570 : Allocator(RHS.Allocator) {
251 134 : if (RHS.empty())
252 0 : return;
253 0 :
254 75263 : // Allocate TheTable of the same size as RHS's TheTable, and set the
255 134905 : // sentinel appropriately (and NumBuckets).
256 173575 : init(RHS.NumBuckets);
257 111 : unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
258 75374 : *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
259 0 :
260 113 : NumItems = RHS.NumItems;
261 111 : NumTombstones = RHS.NumTombstones;
262 1928 : for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
263 1754 : StringMapEntryBase *Bucket = RHS.TheTable[I];
264 1752 : if (!Bucket || Bucket == getTombstoneVal()) {
265 1553 : TheTable[I] = Bucket;
266 76892 : continue;
267 75263 : }
268 75341 :
269 75540 : TheTable[I] = MapEntryTy::Create(
270 2 : static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
271 5604168 : static_cast<MapEntryTy *>(Bucket)->getValue());
272 118000 : HashTable[I] = RHSHashTable[I];
273 2 : }
274 110 :
275 108 : // Note that here we've copied everything from the RHS into this object,
276 98 : // tombstones included. We could, instead, have re-probed for each key to
277 5604198 : // instantiate this new object without any tombstone buckets. The
278 96 : // assumption here is that items are rarely deleted from most StringMaps,
279 66 : // and so tombstones are rare, so the cost of re-probing for all inputs is
280 3004 : // not worthwhile.
281 5607168 : }
282 2938 :
283 1497 : StringMap &operator=(StringMap RHS) {
284 1208226 : StringMapImpl::swap(RHS);
285 10 : std::swap(Allocator, RHS.Allocator);
286 335088 : return *this;
287 253551 : }
288 160 :
289 11723268 : ~StringMap() {
290 5606698 : // Delete all the elements in the map, but don't reset the elements
291 5604169 : // to default values. This is a copy of clear(), but avoids unnecessary
292 5604170 : // work not required in the destructor.
293 6118379 : if (!empty()) {
294 291884105 : for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
295 290977569 : StringMapEntryBase *Bucket = TheTable[I];
296 291038518 : if (Bucket && Bucket != getTombstoneVal()) {
297 548972 : static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
298 532185 : }
299 473162 : }
300 16 : }
301 7129090 : free(TheTable);
302 6119030 : }
303 106 :
304 149257707 : AllocatorTy &getAllocator() { return Allocator; }
305 952370 : const AllocatorTy &getAllocator() const { return Allocator; }
306 813267 :
307 1088524 : using key_type = const char*;
308 1217925 : using mapped_type = ValueTy;
309 70167 : using value_type = StringMapEntry<ValueTy>;
310 2056 : using size_type = size_t;
311 21902 :
312 178950 : using const_iterator = StringMapConstIterator<ValueTy>;
313 1476460 : using iterator = StringMapIterator<ValueTy>;
314 1120237 :
315 490597 : iterator begin() {
316 18 : return iterator(TheTable, NumBuckets == 0);
317 172013 : }
318 235184 : iterator end() {
319 1735500 : return iterator(TheTable+NumBuckets, true);
320 383007 : }
321 181563 : const_iterator begin() const {
322 129427 : return const_iterator(TheTable, NumBuckets == 0);
323 4675 : }
324 2603 : const_iterator end() const {
325 3822637 : return const_iterator(TheTable+NumBuckets, true);
326 260377 : }
327 563861 :
328 560641 : iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
329 479455 : return make_range(StringMapKeyIterator<ValueTy>(begin()),
330 2652 : StringMapKeyIterator<ValueTy>(end()));
331 54432 : }
332 97777 :
333 1131935 : iterator find(StringRef Key) {
334 1336033 : int Bucket = FindKey(Key);
335 1323379 : if (Bucket == -1) return end();
336 930760 : return iterator(TheTable+Bucket, true);
337 72016 : }
338 6609 :
339 683679 : const_iterator find(StringRef Key) const {
340 1359027 : int Bucket = FindKey(Key);
341 1821607 : if (Bucket == -1) return end();
342 1590344 : return const_iterator(TheTable+Bucket, true);
343 23916 : }
344 49305 :
345 36914 : /// lookup - Return the entry for the specified key, or a default
346 8024 : /// constructed value if no such entry exists.
347 1820171 : ValueTy lookup(StringRef Key) const {
348 272441 : const_iterator it = find(Key);
349 581745 : if (it != end())
350 566660 : return it->second;
351 1940283 : return ValueTy();
352 66715755 : }
353 66267824 :
354 66136814 : /// Lookup the ValueTy for the \p Key, or create a default constructed value
355 1022392 : /// if the key is not in the map.
356 31734387 : ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
357 109057 :
358 111139 : /// count - Return 1 if the element is in the map, 0 otherwise.
359 2186574 : size_type count(StringRef Key) const {
360 2039692 : return find(Key) == end() ? 0 : 1;
361 424385 : }
362 422385 :
363 30193 : /// insert - Insert the specified key/value pair into the map. If the key
364 259776 : /// already exists in the map, return false and ignore the request, otherwise
365 3202167 : /// insert it and return true.
366 63700508 : bool insert(MapEntryTy *KeyValue) {
367 63340786 : unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
368 63340506 : StringMapEntryBase *&Bucket = TheTable[BucketNo];
369 2649344 : if (Bucket && Bucket != getTombstoneVal())
370 317074 : return false; // Already exists in map.
371 604177 :
372 2157387 : if (Bucket == getTombstoneVal())
373 513643 : --NumTombstones;
374 2756408 : Bucket = KeyValue;
375 5360166 : ++NumItems;
376 10087428 : assert(NumItems + NumTombstones <= NumBuckets);
377 9748950 :
378 10361050 : RehashTable();
379 3399080 : return true;
380 5702223 : }
381 10340235 :
382 10624689 : /// insert - Inserts the specified key/value pair into the map if the key
383 6358613 : /// isn't already in the map. The bool component of the returned pair is true
384 678193 : /// if and only if the insertion takes place, and the iterator component of
385 518660 : /// the pair points to the element with key equivalent to the key of the pair.
386 514059 : std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
387 1135035483 : return try_emplace(KV.first, std::move(KV.second));
388 7852186 : }
389 7311812 :
390 10430202 : /// Emplace a new element for the specified key into the map if the key isn't
391 2321670 : /// already in the map. The bool component of the returned pair is true
392 1521529 : /// if and only if the insertion takes place, and the iterator component of
393 47614 : /// the pair points to the element with key equivalent to the key of the pair.
394 122073 : template <typename... ArgsTy>
395 1159946679 : std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
396 1159935066 : unsigned BucketNo = LookupBucketFor(Key);
397 1160017437 : StringMapEntryBase *&Bucket = TheTable[BucketNo];
398 1159648542 : if (Bucket && Bucket != getTombstoneVal())
399 297492 : return std::make_pair(iterator(TheTable + BucketNo, false),
400 12254 : false); // Already exists in map.
401 305026 :
402 342974435 : if (Bucket == getTombstoneVal())
403 1123034 : --NumTombstones;
404 343375879 : Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
405 346544072 : ++NumItems;
406 662695 : assert(NumItems + NumTombstones <= NumBuckets);
407 219221 :
408 344439979 : BucketNo = RehashTable(BucketNo);
409 346137400 : return std::make_pair(iterator(TheTable + BucketNo, false), true);
410 4257982 : }
411 61421390 :
412 322701 : // clear - Empties out the StringMap
413 1578210 : void clear() {
414 1330919 : if (empty()) return;
415 4797822 :
416 4876645 : // Zap all values, resetting the keys back to non-present (not tombstone),
417 5279775 : // which is safe because we're removing all elements.
418 7261034 : for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
419 9989212 : StringMapEntryBase *&Bucket = TheTable[I];
420 9786149 : if (Bucket && Bucket != getTombstoneVal()) {
421 3198643 : static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
422 1741224 : }
423 1041042 : Bucket = nullptr;
424 1001901 : }
425 1122206 :
426 291036 : NumItems = 0;
427 1261780 : NumTombstones = 0;
428 4072258 : }
429 2495973 :
430 1522469 : /// remove - Remove the specified key/value pair from the map, but do not
431 35127735 : /// erase it. This aborts if the key is not in the map.
432 36080865 : void remove(MapEntryTy *KeyValue) {
433 139514786 : RemoveKey(KeyValue);
434 112113666 : }
435 100108932 :
436 5675013 : void erase(iterator I) {
437 4241008 : MapEntryTy &V = *I;
438 4216073 : remove(&V);
439 2914239 : V.Destroy(Allocator);
440 2636238 : }
441 31998670 :
442 31990671 : bool erase(StringRef Key) {
443 32868829 : iterator I = find(Key);
444 10921201 : if (I == end()) return false;
445 3897272 : erase(I);
446 2574944 : return true;
447 1517867 : }
448 5421666 : };
449 35984785 :
450 35875129 : template <typename DerivedTy, typename ValueTy>
451 37353976 : class StringMapIterBase
452 12245192 : : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
453 4042892 : ValueTy> {
454 6925144 : protected:
455 6298766 : StringMapEntryBase **Ptr = nullptr;
456 8050426 :
457 6244580 : public:
458 4575973 : StringMapIterBase() = default;
459 1862055 :
460 1258060 : explicit StringMapIterBase(StringMapEntryBase **Bucket,
461 39878375 : bool NoAdvance = false)
462 32080519 : : Ptr(Bucket) {
463 35997229 : if (!NoAdvance) AdvancePastEmptyBuckets();
464 7904005 : }
465 3957048 :
466 1099304 : DerivedTy &operator=(const DerivedTy &Other) {
467 591829 : Ptr = Other.Ptr;
468 221509 : return static_cast<DerivedTy &>(*this);
469 10752635 : }
470 12338952 :
471 11463351 : bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
472 10671824 :
473 135056990 : DerivedTy &operator++() { // Preincrement
474 116780353 : ++Ptr;
475 544242 : AdvancePastEmptyBuckets();
476 4480089 : return static_cast<DerivedTy &>(*this);
477 555007 : }
478 4068699 :
479 4483151 : DerivedTy operator++(int) { // Post-increment
480 2765052 : DerivedTy Tmp(Ptr);
481 137246254 : ++*this;
482 142136720 : return Tmp;
483 139882424 : }
484 135475781 :
485 5996444 : private:
486 36036526 : void AdvancePastEmptyBuckets() {
487 1397759075 : while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
488 136895446 : ++Ptr;
489 100498593 : }
490 117713469 : };
491 115636914 :
492 5962043 : template <typename ValueTy>
493 413774 : class StringMapConstIterator
494 20543993 : : public StringMapIterBase<StringMapConstIterator<ValueTy>,
495 19803729 : const StringMapEntry<ValueTy>> {
496 2486894 : using base = StringMapIterBase<StringMapConstIterator<ValueTy>,
497 136553199 : const StringMapEntry<ValueTy>>;
498 137841022 :
499 296807599 : public:
500 264609904 : StringMapConstIterator() = default;
501 27714629 : explicit StringMapConstIterator(StringMapEntryBase **Bucket,
502 3372273 : bool NoAdvance = false)
503 3369624 : : base(Bucket, NoAdvance) {}
504 24169661 :
505 4280326 : const StringMapEntry<ValueTy> &operator*() const {
506 21160461 : return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
507 20738298 : }
508 1114065 : };
509 24768202 :
510 41323720 : template <typename ValueTy>
511 43659898 : class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
512 23890635 : StringMapEntry<ValueTy>> {
513 3391918 : using base =
514 9666418 : StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
515 1392850 :
516 25083940 : public:
517 3320725 : StringMapIterator() = default;
518 26562113 : explicit StringMapIterator(StringMapEntryBase **Bucket,
519 23779655 : bool NoAdvance = false)
520 4402044 : : base(Bucket, NoAdvance) {}
521 2448841 :
522 26588066 : StringMapEntry<ValueTy> &operator*() const {
523 770495104 : return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
524 188089 : }
525 23454009 :
526 23566592 : operator StringMapConstIterator<ValueTy>() const {
527 25865672 : return StringMapConstIterator<ValueTy>(this->Ptr, true);
528 23303731 : }
529 2372673 : };
530 31895801 :
531 139091108 : template <typename ValueTy>
532 23296440 : class StringMapKeyIterator
533 2396757 : : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
534 25665218 : StringMapConstIterator<ValueTy>,
535 27075340 : std::forward_iterator_tag, StringRef> {
536 2751106 : using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
537 2780842 : StringMapConstIterator<ValueTy>,
538 26050784 : std::forward_iterator_tag, StringRef>;
539 24033563 :
540 179521 : public:
541 529587 : StringMapKeyIterator() = default;
542 1147576 : explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
543 626530 : : base(std::move(Iter)) {}
544 1250879 :
545 763511 : StringRef &operator*() {
546 125133 : Key = this->wrapped()->getKey();
547 202669 : return Key;
548 1859253 : }
549 1468944 :
550 1426471 : private:
551 1777952 : StringRef Key;
552 14896251 : };
553 4031532 :
554 4369523 : } // end namespace llvm
555 10013269 :
556 5113341 : #endif // LLVM_ADT_STRINGMAP_H
|
