1bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner//===--- StringMap.h - String Hash table map interface ----------*- C++ -*-===// 223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// The LLVM Compiler Infrastructure 423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner//===----------------------------------------------------------------------===// 923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 10bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner// This file defines the StringMap class. 1123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 1223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner//===----------------------------------------------------------------------===// 1323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 14bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner#ifndef LLVM_ADT_STRINGMAP_H 15bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner#define LLVM_ADT_STRINGMAP_H 1623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 176316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar#include "llvm/ADT/StringRef.h" 1823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner#include "llvm/Support/Allocator.h" 1923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner#include <cstring> 20dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include <utility> 2123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 2223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnernamespace llvm { 236ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner template<typename ValueT> 246ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner class StringMapConstIterator; 256ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner template<typename ValueT> 266ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner class StringMapIterator; 27d7205e6ba16480ef0a7ee2b6097d0a13097e8a0fChris Lattner template<typename ValueTy> 28d7205e6ba16480ef0a7ee2b6097d0a13097e8a0fChris Lattner class StringMapEntry; 296ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 30ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// StringMapEntryBase - Shared base class of StringMapEntry instances. 31ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerclass StringMapEntryBase { 32ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner unsigned StrLen; 33ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerpublic: 34adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} 3575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 36ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner unsigned getKeyLength() const { return StrLen; } 37ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner}; 3875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 39bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner/// StringMapImpl - This is the base class of StringMap that is shared among 4023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// all of its instantiations. 41bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerclass StringMapImpl { 426ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerprotected: 43c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer // Array of NumBuckets pointers to entries, null pointers are holes. 44745bf82ebac69b390911d5af0b1664fa7ff6410eEli Bendersky // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed 45c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer // by an array of the actual hash values as unsigned integers. 46c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase **TheTable; 4723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NumBuckets; 4823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NumItems; 4944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner unsigned NumTombstones; 5023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned ItemSize; 5123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerprotected: 52dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines explicit StringMapImpl(unsigned itemSize) 53dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : TheTable(nullptr), 54dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Initialize the map with zero buckets to allocation. 55dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NumBuckets(0), NumItems(0), NumTombstones(0), ItemSize(itemSize) {} 56dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines StringMapImpl(StringMapImpl &&RHS) 57dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets), 58dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones), 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ItemSize(RHS.ItemSize) { 60dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.TheTable = nullptr; 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.NumBuckets = 0; 62dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.NumItems = 0; 63dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.NumTombstones = 0; 64c6402013c8767d5718d4c7ae5625969361182771Chris Lattner } 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 66bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner StringMapImpl(unsigned InitSize, unsigned ItemSize); 67cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned RehashTable(unsigned BucketNo = 0); 6875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 6923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// LookupBucketFor - Look up the bucket that the specified string should end 7023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// up in. If it already exists as a key in the map, the Item pointer for the 7123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// specified bucket will be non-null. Otherwise, it will be null. In either 7223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// case, the FullHashValue field of the bucket will be set to the hash value 7323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// of the string. 742928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar unsigned LookupBucketFor(StringRef Key); 7575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 76b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// FindKey - Look up the bucket that contains the specified key. If it exists 77b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// in the map, return the bucket number of the key. Otherwise return -1. 78b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// This does not modify the map. 792928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar int FindKey(StringRef Key) const; 8044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 8144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 8244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// delete it. This aborts if the value isn't in the table. 8344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner void RemoveKey(StringMapEntryBase *V); 8444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 8544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// RemoveKey - Remove the StringMapEntry for the specified key from the 8644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// table, returning it. If the key is not in the table, this returns null. 872928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar StringMapEntryBase *RemoveKey(StringRef Key); 88794a014809d810b7ee9a96be76774185561f0dccChris Lattnerprivate: 89794a014809d810b7ee9a96be76774185561f0dccChris Lattner void init(unsigned Size); 9023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerpublic: 916ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner static StringMapEntryBase *getTombstoneVal() { 926ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return (StringMapEntryBase*)-1; 936ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 9475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 9523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned getNumBuckets() const { return NumBuckets; } 9623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned getNumItems() const { return NumItems; } 9723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 986ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool empty() const { return NumItems == 0; } 996ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner unsigned size() const { return NumItems; } 100284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner 101284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner void swap(StringMapImpl &Other) { 102284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(TheTable, Other.TheTable); 103284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(NumBuckets, Other.NumBuckets); 104284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(NumItems, Other.NumItems); 105284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(NumTombstones, Other.NumTombstones); 106284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner } 10723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 10823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 109ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// StringMapEntry - This is used to represent one value that is inserted into 110ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// a StringMap. It contains the Value itself and the key: the string length 111ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// and data. 112ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnertemplate<typename ValueTy> 113ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerclass StringMapEntry : public StringMapEntryBase { 11403abfc7114ce60ef69c4335c16eb264957340fadChris Lattner StringMapEntry(StringMapEntry &E) LLVM_DELETED_FUNCTION; 115ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerpublic: 116713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov ValueTy second; 117713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 1188032020cf209721bc104648f28b1c4b45fb88691Bill Wendling explicit StringMapEntry(unsigned strLen) 1198032020cf209721bc104648f28b1c4b45fb88691Bill Wendling : StringMapEntryBase(strLen), second() {} 120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines StringMapEntry(unsigned strLen, ValueTy V) 121dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : StringMapEntryBase(strLen), second(std::move(V)) {} 122ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 1236d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov StringRef getKey() const { 1246d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov return StringRef(getKeyData(), getKeyLength()); 1256316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar } 1266316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar 127713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov const ValueTy &getValue() const { return second; } 128713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov ValueTy &getValue() { return second; } 12975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 130713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov void setValue(const ValueTy &V) { second = V; } 13175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 132ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// getKeyData - Return the start of the string data that is the key for this 133ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// value. The string data is always stored immediately after the 134ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// StringMapEntry object. 135ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 13675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 137d7c027322ebccd9666c3f46d9a5236ba76fda434Chris Lattner StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } 138713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 1399cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Create - Create a StringMapEntry for the specified key and default 1409cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// construct the value. 141aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename AllocatorTy, typename InitType> 142cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines static StringMapEntry *Create(StringRef Key, 143aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner AllocatorTy &Allocator, 144aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner InitType InitVal) { 145cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned KeyLength = Key.size(); 14675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 14736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Allocate a new item with space for the string at the end and a null 1489cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // terminator. 14934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 15034cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng KeyLength+1; 15116c3b647eb100fe404ee65f106d563ddef6c74b7Chris Lattner unsigned Alignment = alignOf<StringMapEntry>(); 15275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1536740463c74a7b98ec3136211c871ddd29df39887Ted Kremenek StringMapEntry *NewItem = 1546740463c74a7b98ec3136211c871ddd29df39887Ted Kremenek static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 15575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1569cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Default construct the value. 157dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines new (NewItem) StringMapEntry(KeyLength, std::move(InitVal)); 15875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1599cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Copy the string information. 1609cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 161cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines memcpy(StrBuffer, Key.data(), KeyLength); 1629cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 1639cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner return NewItem; 1649cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 16575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 166aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename AllocatorTy> 167cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator) { 168cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Create(Key, Allocator, ValueTy()); 169aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 17075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1719cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Create - Create a StringMapEntry with normal malloc/free. 172aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename InitType> 173cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines static StringMapEntry *Create(StringRef Key, InitType InitVal) { 1749cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 175cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Create(Key, A, std::move(InitVal)); 176aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 177aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner 178cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines static StringMapEntry *Create(StringRef Key) { 179cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Create(Key, ValueTy()); 1809cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 18175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1821bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner /// GetStringMapEntryFromValue - Given a value that is known to be embedded 1831bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner /// into a StringMapEntry, return the StringMapEntry itself. 1841bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { 185b89f67e3e659da1f11c01f2aac1be3463dc60f07Chris Lattner StringMapEntry *EPtr = 0; 18675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov char *Ptr = reinterpret_cast<char*>(&V) - 187713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov (reinterpret_cast<char*>(&EPtr->second) - 1881ff2ddda083a3c71a04789fe9845d41f7aaaa0ecChris Lattner reinterpret_cast<char*>(EPtr)); 189b89f67e3e659da1f11c01f2aac1be3463dc60f07Chris Lattner return *reinterpret_cast<StringMapEntry*>(Ptr); 1901bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner } 1911bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { 1921bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); 1931bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner } 1946d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 1958ee076961219c9066b651ff686c450d92e81c27aChris Lattner /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 1968ee076961219c9066b651ff686c450d92e81c27aChris Lattner /// into a StringMapEntry, return the StringMapEntry itself. 1978ee076961219c9066b651ff686c450d92e81c27aChris Lattner static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { 1988ee076961219c9066b651ff686c450d92e81c27aChris Lattner char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>); 1998ee076961219c9066b651ff686c450d92e81c27aChris Lattner return *reinterpret_cast<StringMapEntry*>(Ptr); 2008ee076961219c9066b651ff686c450d92e81c27aChris Lattner } 2016d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 2029cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy - Destroy this StringMapEntry, releasing memory back to the 2039cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// specified allocator. 2049cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner template<typename AllocatorTy> 2059cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy(AllocatorTy &Allocator) { 2069cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Free memory referenced by the item. 207dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines unsigned AllocSize = 208dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1; 2099cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner this->~StringMapEntry(); 210dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Allocator.Deallocate(static_cast<void *>(this), AllocSize); 2119cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 21275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 2139cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy this object, releasing memory back to the malloc allocator. 2149cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy() { 2159cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 2169cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner Destroy(A); 2179cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 218ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner}; 219ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 22023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 221bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner/// StringMap - This is an unconventional map that is specialized for handling 222ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// keys that are "strings", which are basically ranges of bytes. This does some 22323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// funky memory allocation and hashing things to make it extremely efficient, 22423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// storing the string data *after* the value in the map. 22523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnertemplate<typename ValueTy, typename AllocatorTy = MallocAllocator> 226bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerclass StringMap : public StringMapImpl { 22723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner AllocatorTy Allocator; 22823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerpublic: 229e55bbfe145cf8dcb9594865f0242321d2be681d6Chris Lattner typedef StringMapEntry<ValueTy> MapEntryTy; 230e55bbfe145cf8dcb9594865f0242321d2be681d6Chris Lattner 23134cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 232adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMap(unsigned InitialSize) 23334cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 2346d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 235a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner explicit StringMap(AllocatorTy A) 236a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 237a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner 2383735573343614644ead7a8bae674c312db8b1eb1Argyrios Kyrtzidis StringMap(unsigned InitialSize, AllocatorTy A) 23947f39340211f537cf79610832194c1884d420d62Argyrios Kyrtzidis : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), 24047f39340211f537cf79610832194c1884d420d62Argyrios Kyrtzidis Allocator(A) {} 2413735573343614644ead7a8bae674c312db8b1eb1Argyrios Kyrtzidis 242dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines StringMap(StringMap &&RHS) 243dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {} 244dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 245dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines StringMap &operator=(StringMap RHS) { 246dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines StringMapImpl::swap(RHS); 247dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::swap(Allocator, RHS.Allocator); 248dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return *this; 2494715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner } 2504715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner 251dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // FIXME: Implement copy operations if/when they're needed. 252dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 253dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AllocatorTy &getAllocator() { return Allocator; } 254dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const AllocatorTy &getAllocator() const { return Allocator; } 25523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 256713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef const char* key_type; 257713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef ValueTy mapped_type; 258713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef StringMapEntry<ValueTy> value_type; 259713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef size_t size_type; 260713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 2616ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapConstIterator<ValueTy> const_iterator; 2626ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapIterator<ValueTy> iterator; 26375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 264794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator begin() { 265794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable, NumBuckets == 0); 266794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 267794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator end() { 268794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable+NumBuckets, true); 269794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 270794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator begin() const { 271794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable, NumBuckets == 0); 272794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 273794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator end() const { 274794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable+NumBuckets, true); 275794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 27675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 2772928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar iterator find(StringRef Key) { 2786316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 279b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 28085c07ce0481daa8f462943f621efdb7f21f6d3efBenjamin Kramer return iterator(TheTable+Bucket, true); 281b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 282b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 2832928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar const_iterator find(StringRef Key) const { 2846316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 285b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 28685c07ce0481daa8f462943f621efdb7f21f6d3efBenjamin Kramer return const_iterator(TheTable+Bucket, true); 2876c1645ce7da8495c79e3d38bbf91ce77bf489c10Chris Lattner } 288713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 289745bf82ebac69b390911d5af0b1664fa7ff6410eEli Bendersky /// lookup - Return the entry for the specified key, or a default 290e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar /// constructed value if no such entry exists. 2912928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar ValueTy lookup(StringRef Key) const { 292e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar const_iterator it = find(Key); 293e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar if (it != end()) 294e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar return it->second; 295e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar return ValueTy(); 296e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar } 297e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar 29839ff10a293012fe6f2db682c5518e1be2c50ca67Chris Lattner ValueTy &operator[](StringRef Key) { 2996316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return GetOrCreateValue(Key).getValue(); 300ec3e5c8a39c3dae7457d0eb18f98685decb23fcdAnton Korobeynikov } 301713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 30236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// count - Return 1 if the element is in the map, 0 otherwise. 3032928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar size_type count(StringRef Key) const { 3046316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return find(Key) == end() ? 0 : 1; 305ec3e5c8a39c3dae7457d0eb18f98685decb23fcdAnton Korobeynikov } 306713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 30744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert - Insert the specified key/value pair into the map. If the key 30844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// already exists in the map, return false and ignore the request, otherwise 30944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert it and return true. 31044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner bool insert(MapEntryTy *KeyValue) { 3116316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 312c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *&Bucket = TheTable[BucketNo]; 313c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket && Bucket != getTombstoneVal()) 31444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return false; // Already exists in map. 31575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 316c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket == getTombstoneVal()) 31744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumTombstones; 318c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer Bucket = KeyValue; 31944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner ++NumItems; 32003ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen assert(NumItems + NumTombstones <= NumBuckets); 32175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 322aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen RehashTable(); 32344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return true; 32444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 32575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 326cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// insert - Inserts the specified key/value pair into the map if the key 327cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// isn't already in the map. The bool component of the returned pair is true 328cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// if and only if the insertion takes place, and the iterator component of 329cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// the pair points to the element with key equivalent to the key of the pair. 330cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) { 331cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned BucketNo = LookupBucketFor(KV.first); 332cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines StringMapEntryBase *&Bucket = TheTable[BucketNo]; 333cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Bucket && Bucket != getTombstoneVal()) 334cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return std::make_pair(iterator(TheTable + BucketNo, false), 335cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines false); // Already exists in map. 336cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 337cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Bucket == getTombstoneVal()) 338cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines --NumTombstones; 339cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Bucket = 340cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines MapEntryTy::Create(KV.first, Allocator, std::move(KV.second)); 341cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ++NumItems; 342cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines assert(NumItems + NumTombstones <= NumBuckets); 343cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 344cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BucketNo = RehashTable(BucketNo); 345cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return std::make_pair(iterator(TheTable + BucketNo, false), true); 346cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 347cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 348fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner // clear - Empties out the StringMap 349fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner void clear() { 350509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner if (empty()) return; 3518bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 352509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner // Zap all values, resetting the keys back to non-present (not tombstone), 353509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner // which is safe because we're removing all elements. 354c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 355c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *&Bucket = TheTable[I]; 356c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket && Bucket != getTombstoneVal()) { 357c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 358509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner } 359dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Bucket = nullptr; 360509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner } 3618bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 3628bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman NumItems = 0; 36303ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen NumTombstones = 0; 364fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner } 365fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner 36623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// GetOrCreateValue - Look up the specified key in the table. If a value 36723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// exists, return it. Otherwise, default construct a value, insert it, and 36823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// return. 369aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template <typename InitTy> 37039ff10a293012fe6f2db682c5518e1be2c50ca67Chris Lattner MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { 371cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return *insert(std::make_pair(Key, std::move(Val))).first; 37223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 37375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 37439ff10a293012fe6f2db682c5518e1be2c50ca67Chris Lattner MapEntryTy &GetOrCreateValue(StringRef Key) { 3756316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return GetOrCreateValue(Key, ValueTy()); 3766316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar } 3776316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar 37844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// remove - Remove the specified key/value pair from the map, but do not 37944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// erase it. This aborts if the key is not in the map. 38044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner void remove(MapEntryTy *KeyValue) { 38144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner RemoveKey(KeyValue); 38244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 38375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 384c6402013c8767d5718d4c7ae5625969361182771Chris Lattner void erase(iterator I) { 385c6402013c8767d5718d4c7ae5625969361182771Chris Lattner MapEntryTy &V = *I; 386c6402013c8767d5718d4c7ae5625969361182771Chris Lattner remove(&V); 387c6402013c8767d5718d4c7ae5625969361182771Chris Lattner V.Destroy(Allocator); 38884701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman } 38984701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman 3902928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar bool erase(StringRef Key) { 39184701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman iterator I = find(Key); 39284701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman if (I == end()) return false; 39384701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman erase(I); 39484701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman return true; 395c6402013c8767d5718d4c7ae5625969361182771Chris Lattner } 39675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 397bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner ~StringMap() { 39836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Delete all the elements in the map, but don't reset the elements 39936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // to default values. This is a copy of clear(), but avoids unnecessary 40036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // work not required in the destructor. 40136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!empty()) { 40236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 40336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines StringMapEntryBase *Bucket = TheTable[I]; 40436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Bucket && Bucket != getTombstoneVal()) { 40536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 40636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 40736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 40836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 409d2f197da59a3c937c1809997907918c029f9f884Chris Lattner free(TheTable); 41023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 41123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 41275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4136ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 4146ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnertemplate<typename ValueTy> 4156ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerclass StringMapConstIterator { 41644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattnerprotected: 417c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase **Ptr; 4186ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerpublic: 4199f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek typedef StringMapEntry<ValueTy> value_type; 4208bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 421dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines StringMapConstIterator() : Ptr(nullptr) { } 422284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner 423c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer explicit StringMapConstIterator(StringMapEntryBase **Bucket, 424adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman bool NoAdvance = false) 425794a014809d810b7ee9a96be76774185561f0dccChris Lattner : Ptr(Bucket) { 426794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (!NoAdvance) AdvancePastEmptyBuckets(); 4276ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 42875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4299f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek const value_type &operator*() const { 430c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return *static_cast<StringMapEntry<ValueTy>*>(*Ptr); 4316ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4329f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek const value_type *operator->() const { 433c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return static_cast<StringMapEntry<ValueTy>*>(*Ptr); 4346ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 43575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4366ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator==(const StringMapConstIterator &RHS) const { 4376ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr == RHS.Ptr; 4386ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4396ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator!=(const StringMapConstIterator &RHS) const { 4406ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr != RHS.Ptr; 4416ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 44275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 443745bf82ebac69b390911d5af0b1664fa7ff6410eEli Bendersky inline StringMapConstIterator& operator++() { // Preincrement 4446ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 4456ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner AdvancePastEmptyBuckets(); 4466ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return *this; 4476ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4486ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator operator++(int) { // Postincrement 4496ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator tmp = *this; ++*this; return tmp; 4506ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 45175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4526ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerprivate: 4536ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner void AdvancePastEmptyBuckets() { 454dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) 4556ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 4566ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4576ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 4586ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 4596ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnertemplate<typename ValueTy> 4606ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerclass StringMapIterator : public StringMapConstIterator<ValueTy> { 46175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikovpublic: 4629e8dbe0d2de41d9f993d07f438f5f967fdfd9974Reid Kleckner StringMapIterator() {} 463c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer explicit StringMapIterator(StringMapEntryBase **Bucket, 464ded2b0d0fb0d4fa09198e3d05da529d2c97214c3Dan Gohman bool NoAdvance = false) 465794a014809d810b7ee9a96be76774185561f0dccChris Lattner : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 4666ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4676ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> &operator*() const { 468c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 4696ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4706ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> *operator->() const { 471c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 4726ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4736ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 4746ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 47523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 47623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 477463c4a1ae9af56b6a944b74f0898e17d9a3b52ebChris Lattner#endif 478