StringMap.h revision 164dfb094df947db2117c182ae033ea85c6c42a1
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> 2023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 2123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnernamespace llvm { 226ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner template<typename ValueT> 236ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner class StringMapConstIterator; 246ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner template<typename ValueT> 256ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner class StringMapIterator; 26d7205e6ba16480ef0a7ee2b6097d0a13097e8a0fChris Lattner template<typename ValueTy> 27d7205e6ba16480ef0a7ee2b6097d0a13097e8a0fChris Lattner class StringMapEntry; 286ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 29aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner/// StringMapEntryInitializer - This datatype can be partially specialized for 3075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov/// various datatypes in a stringmap to allow them to be initialized when an 31aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner/// entry is default constructed for the map. 32aec78708c24a85a99b757ada086e5c05a4c123edChris Lattnertemplate<typename ValueTy> 33aec78708c24a85a99b757ada086e5c05a4c123edChris Lattnerclass StringMapEntryInitializer { 34aec78708c24a85a99b757ada086e5c05a4c123edChris Lattnerpublic: 35aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template <typename InitTy> 36d7205e6ba16480ef0a7ee2b6097d0a13097e8a0fChris Lattner static void Initialize(StringMapEntry<ValueTy> &T, InitTy InitVal) { 374715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner T.second = InitVal; 38aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 39aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner}; 4075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 42ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// StringMapEntryBase - Shared base class of StringMapEntry instances. 43ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerclass StringMapEntryBase { 44ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner unsigned StrLen; 45ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerpublic: 46adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} 4775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 48ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner unsigned getKeyLength() const { return StrLen; } 49ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner}; 5075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 51bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner/// StringMapImpl - This is the base class of StringMap that is shared among 5223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// all of its instantiations. 53bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerclass StringMapImpl { 546ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerprotected: 55c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer // Array of NumBuckets pointers to entries, null pointers are holes. 56c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer // TheTable[NumBuckets] contains a sentinel value for easy iteration. Follwed 57c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer // by an array of the actual hash values as unsigned integers. 58c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase **TheTable; 5923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NumBuckets; 6023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NumItems; 6144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner unsigned NumTombstones; 6223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned ItemSize; 6323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerprotected: 64adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) { 65c6402013c8767d5718d4c7ae5625969361182771Chris Lattner // Initialize the map with zero buckets to allocation. 66c6402013c8767d5718d4c7ae5625969361182771Chris Lattner TheTable = 0; 67c6402013c8767d5718d4c7ae5625969361182771Chris Lattner NumBuckets = 0; 68c6402013c8767d5718d4c7ae5625969361182771Chris Lattner NumItems = 0; 69c6402013c8767d5718d4c7ae5625969361182771Chris Lattner NumTombstones = 0; 70c6402013c8767d5718d4c7ae5625969361182771Chris Lattner } 71bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner StringMapImpl(unsigned InitSize, unsigned ItemSize); 7223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner void RehashTable(); 7375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 7423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// LookupBucketFor - Look up the bucket that the specified string should end 7523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// up in. If it already exists as a key in the map, the Item pointer for the 7623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// specified bucket will be non-null. Otherwise, it will be null. In either 7723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// case, the FullHashValue field of the bucket will be set to the hash value 7823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// of the string. 792928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar unsigned LookupBucketFor(StringRef Key); 8075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 81b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// FindKey - Look up the bucket that contains the specified key. If it exists 82b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// in the map, return the bucket number of the key. Otherwise return -1. 83b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// This does not modify the map. 842928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar int FindKey(StringRef Key) const; 8544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 8644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 8744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// delete it. This aborts if the value isn't in the table. 8844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner void RemoveKey(StringMapEntryBase *V); 8944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 9044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// RemoveKey - Remove the StringMapEntry for the specified key from the 9144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// table, returning it. If the key is not in the table, this returns null. 922928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar StringMapEntryBase *RemoveKey(StringRef Key); 93794a014809d810b7ee9a96be76774185561f0dccChris Lattnerprivate: 94794a014809d810b7ee9a96be76774185561f0dccChris Lattner void init(unsigned Size); 9523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerpublic: 966ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner static StringMapEntryBase *getTombstoneVal() { 976ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return (StringMapEntryBase*)-1; 986ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 9975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 10023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned getNumBuckets() const { return NumBuckets; } 10123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned getNumItems() const { return NumItems; } 10223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 1036ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool empty() const { return NumItems == 0; } 1046ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner unsigned size() const { return NumItems; } 10523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 10623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 107ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// StringMapEntry - This is used to represent one value that is inserted into 108ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// a StringMap. It contains the Value itself and the key: the string length 109ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// and data. 110ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnertemplate<typename ValueTy> 111ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerclass StringMapEntry : public StringMapEntryBase { 112ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerpublic: 113713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov ValueTy second; 114713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 1158032020cf209721bc104648f28b1c4b45fb88691Bill Wendling explicit StringMapEntry(unsigned strLen) 1168032020cf209721bc104648f28b1c4b45fb88691Bill Wendling : StringMapEntryBase(strLen), second() {} 1178032020cf209721bc104648f28b1c4b45fb88691Bill Wendling StringMapEntry(unsigned strLen, const ValueTy &V) 1188032020cf209721bc104648f28b1c4b45fb88691Bill Wendling : StringMapEntryBase(strLen), second(V) {} 119ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 1206d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov StringRef getKey() const { 1216d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov return StringRef(getKeyData(), getKeyLength()); 1226316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar } 1236316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar 124713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov const ValueTy &getValue() const { return second; } 125713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov ValueTy &getValue() { return second; } 12675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 127713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov void setValue(const ValueTy &V) { second = V; } 12875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 129ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// getKeyData - Return the start of the string data that is the key for this 130ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// value. The string data is always stored immediately after the 131ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// StringMapEntry object. 132ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 13375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 134d7c027322ebccd9666c3f46d9a5236ba76fda434Chris Lattner StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } 135713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 1369cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Create - Create a StringMapEntry for the specified key and default 1379cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// construct the value. 138aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename AllocatorTy, typename InitType> 1399cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 140aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner AllocatorTy &Allocator, 141aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner InitType InitVal) { 14234cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned KeyLength = static_cast<unsigned>(KeyEnd-KeyStart); 14375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1449cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill 1459cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // in. Allocate a new item with space for the string at the end and a null 1469cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // terminator. 14775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 14834cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 14934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng KeyLength+1; 15016c3b647eb100fe404ee65f106d563ddef6c74b7Chris Lattner unsigned Alignment = alignOf<StringMapEntry>(); 15175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1526740463c74a7b98ec3136211c871ddd29df39887Ted Kremenek StringMapEntry *NewItem = 1536740463c74a7b98ec3136211c871ddd29df39887Ted Kremenek static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 15475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1559cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Default construct the value. 1569cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner new (NewItem) StringMapEntry(KeyLength); 15775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1589cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Copy the string information. 1599cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 1609cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner memcpy(StrBuffer, KeyStart, KeyLength); 1619cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 16275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 163aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner // Initialize the value if the client wants to. 164d7205e6ba16480ef0a7ee2b6097d0a13097e8a0fChris Lattner StringMapEntryInitializer<ValueTy>::Initialize(*NewItem, InitVal); 1659cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner return NewItem; 1669cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 16775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 168aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename AllocatorTy> 169aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 170aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner AllocatorTy &Allocator) { 17138593664b02bca98904c4b1883b0a489b5aaacbeBill Wendling return Create(KeyStart, KeyEnd, Allocator, 0); 172aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 17375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 17475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1759cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Create - Create a StringMapEntry with normal malloc/free. 176aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename InitType> 177aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 178aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner InitType InitVal) { 1799cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 180aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner return Create(KeyStart, KeyEnd, A, InitVal); 181aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 182aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner 183aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { 1844715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner return Create(KeyStart, KeyEnd, ValueTy()); 1859cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 18675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1871bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner /// GetStringMapEntryFromValue - Given a value that is known to be embedded 1881bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner /// into a StringMapEntry, return the StringMapEntry itself. 1891bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { 190b89f67e3e659da1f11c01f2aac1be3463dc60f07Chris Lattner StringMapEntry *EPtr = 0; 19175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov char *Ptr = reinterpret_cast<char*>(&V) - 192713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov (reinterpret_cast<char*>(&EPtr->second) - 1931ff2ddda083a3c71a04789fe9845d41f7aaaa0ecChris Lattner reinterpret_cast<char*>(EPtr)); 194b89f67e3e659da1f11c01f2aac1be3463dc60f07Chris Lattner return *reinterpret_cast<StringMapEntry*>(Ptr); 1951bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner } 1961bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { 1971bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); 1981bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner } 1996d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 2008ee076961219c9066b651ff686c450d92e81c27aChris Lattner /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 2018ee076961219c9066b651ff686c450d92e81c27aChris Lattner /// into a StringMapEntry, return the StringMapEntry itself. 2028ee076961219c9066b651ff686c450d92e81c27aChris Lattner static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { 2038ee076961219c9066b651ff686c450d92e81c27aChris Lattner char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>); 2048ee076961219c9066b651ff686c450d92e81c27aChris Lattner return *reinterpret_cast<StringMapEntry*>(Ptr); 2058ee076961219c9066b651ff686c450d92e81c27aChris Lattner } 2066d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 20775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 2089cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy - Destroy this StringMapEntry, releasing memory back to the 2099cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// specified allocator. 2109cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner template<typename AllocatorTy> 2119cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy(AllocatorTy &Allocator) { 2129cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Free memory referenced by the item. 2139cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner this->~StringMapEntry(); 2149cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner Allocator.Deallocate(this); 2159cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 21675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 2179cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy this object, releasing memory back to the malloc allocator. 2189cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy() { 2199cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 2209cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner Destroy(A); 2219cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 222ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner}; 223ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 22423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 225bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner/// StringMap - This is an unconventional map that is specialized for handling 226ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// keys that are "strings", which are basically ranges of bytes. This does some 22723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// funky memory allocation and hashing things to make it extremely efficient, 22823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// storing the string data *after* the value in the map. 22923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnertemplate<typename ValueTy, typename AllocatorTy = MallocAllocator> 230bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerclass StringMap : public StringMapImpl { 23123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner AllocatorTy Allocator; 23223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerpublic: 233e55bbfe145cf8dcb9594865f0242321d2be681d6Chris Lattner typedef StringMapEntry<ValueTy> MapEntryTy; 234e55bbfe145cf8dcb9594865f0242321d2be681d6Chris Lattner 23534cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 236adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMap(unsigned InitialSize) 23734cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 2386d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 239a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner explicit StringMap(AllocatorTy A) 240a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 241a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner 242164dfb094df947db2117c182ae033ea85c6c42a1Benjamin Kramer StringMap(const StringMap &RHS) 2434715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) { 2444715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner assert(RHS.empty() && 2454715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner "Copy ctor from non-empty stringmap not implemented yet!"); 2461c3f050309592e034972dc77a2eb4025680ff293Frits van Bommel (void)RHS; 2474715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner } 2484715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner void operator=(const StringMap &RHS) { 2494715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner assert(RHS.empty() && 2504715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner "assignment from non-empty stringmap not implemented yet!"); 2511c3f050309592e034972dc77a2eb4025680ff293Frits van Bommel (void)RHS; 2524715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner clear(); 2534715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner } 2544715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner 255061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; 256061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; 257061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner AllocatorRefTy getAllocator() { return Allocator; } 258061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner AllocatorCRefTy getAllocator() const { return Allocator; } 25923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 260713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef const char* key_type; 261713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef ValueTy mapped_type; 262713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef StringMapEntry<ValueTy> value_type; 263713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef size_t size_type; 264713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 2656ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapConstIterator<ValueTy> const_iterator; 2666ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapIterator<ValueTy> iterator; 26775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 268794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator begin() { 269794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable, NumBuckets == 0); 270794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 271794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator end() { 272794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable+NumBuckets, true); 273794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 274794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator begin() const { 275794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable, NumBuckets == 0); 276794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 277794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator end() const { 278794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable+NumBuckets, true); 279794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 28075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 2812928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar iterator find(StringRef Key) { 2826316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 283b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 28485c07ce0481daa8f462943f621efdb7f21f6d3efBenjamin Kramer return iterator(TheTable+Bucket, true); 285b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 286b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 2872928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar const_iterator find(StringRef Key) const { 2886316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 289b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 29085c07ce0481daa8f462943f621efdb7f21f6d3efBenjamin Kramer return const_iterator(TheTable+Bucket, true); 2916c1645ce7da8495c79e3d38bbf91ce77bf489c10Chris Lattner } 292713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 293e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar /// lookup - Return the entry for the specified key, or a default 294e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar /// constructed value if no such entry exists. 2952928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar ValueTy lookup(StringRef Key) const { 296e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar const_iterator it = find(Key); 297e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar if (it != end()) 298e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar return it->second; 299e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar return ValueTy(); 300e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar } 301e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar 30239ff10a293012fe6f2db682c5518e1be2c50ca67Chris Lattner ValueTy &operator[](StringRef Key) { 3036316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return GetOrCreateValue(Key).getValue(); 304ec3e5c8a39c3dae7457d0eb18f98685decb23fcdAnton Korobeynikov } 305713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 3062928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar size_type count(StringRef Key) const { 3076316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return find(Key) == end() ? 0 : 1; 308ec3e5c8a39c3dae7457d0eb18f98685decb23fcdAnton Korobeynikov } 309713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 31044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert - Insert the specified key/value pair into the map. If the key 31144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// already exists in the map, return false and ignore the request, otherwise 31244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert it and return true. 31344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner bool insert(MapEntryTy *KeyValue) { 3146316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 315c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *&Bucket = TheTable[BucketNo]; 316c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket && Bucket != getTombstoneVal()) 31744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return false; // Already exists in map. 31875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 319c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket == getTombstoneVal()) 32044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumTombstones; 321c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer Bucket = KeyValue; 32244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner ++NumItems; 32303ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen assert(NumItems + NumTombstones <= NumBuckets); 32475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 325aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen RehashTable(); 32644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return true; 32744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 32875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 329fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner // clear - Empties out the StringMap 330fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner void clear() { 331509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner if (empty()) return; 3328bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 333509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner // Zap all values, resetting the keys back to non-present (not tombstone), 334509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner // which is safe because we're removing all elements. 335c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 336c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *&Bucket = TheTable[I]; 337c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket && Bucket != getTombstoneVal()) { 338c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 339c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer Bucket = 0; 340509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner } 341509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner } 3428bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 3438bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman NumItems = 0; 34403ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen NumTombstones = 0; 345fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner } 346fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner 34723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// GetOrCreateValue - Look up the specified key in the table. If a value 34823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// exists, return it. Otherwise, default construct a value, insert it, and 34923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// return. 350aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template <typename InitTy> 35139ff10a293012fe6f2db682c5518e1be2c50ca67Chris Lattner MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { 3526316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar unsigned BucketNo = LookupBucketFor(Key); 353c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *&Bucket = TheTable[BucketNo]; 354c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket && Bucket != getTombstoneVal()) 355c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return *static_cast<MapEntryTy*>(Bucket); 35675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 3576316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar MapEntryTy *NewItem = 3586316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); 35975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 360c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket == getTombstoneVal()) 36144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumTombstones; 36223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ++NumItems; 36303ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen assert(NumItems + NumTombstones <= NumBuckets); 36475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 36523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Fill in the bucket for the hash table. The FullHashValue was already 36623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // filled in by LookupBucketFor. 367c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer Bucket = NewItem; 36875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 369aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen RehashTable(); 37023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner return *NewItem; 37123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 37275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 37339ff10a293012fe6f2db682c5518e1be2c50ca67Chris Lattner MapEntryTy &GetOrCreateValue(StringRef Key) { 3746316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return GetOrCreateValue(Key, ValueTy()); 3756316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar } 3766316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar 37744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// remove - Remove the specified key/value pair from the map, but do not 37844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// erase it. This aborts if the key is not in the map. 37944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner void remove(MapEntryTy *KeyValue) { 38044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner RemoveKey(KeyValue); 38144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 38275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 383c6402013c8767d5718d4c7ae5625969361182771Chris Lattner void erase(iterator I) { 384c6402013c8767d5718d4c7ae5625969361182771Chris Lattner MapEntryTy &V = *I; 385c6402013c8767d5718d4c7ae5625969361182771Chris Lattner remove(&V); 386c6402013c8767d5718d4c7ae5625969361182771Chris Lattner V.Destroy(Allocator); 38784701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman } 38884701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman 3892928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar bool erase(StringRef Key) { 39084701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman iterator I = find(Key); 39184701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman if (I == end()) return false; 39284701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman erase(I); 39384701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman return true; 394c6402013c8767d5718d4c7ae5625969361182771Chris Lattner } 39575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 396bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner ~StringMap() { 397509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner clear(); 398d2f197da59a3c937c1809997907918c029f9f884Chris Lattner free(TheTable); 39923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 40023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 40175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4026ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 4036ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnertemplate<typename ValueTy> 4046ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerclass StringMapConstIterator { 40544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattnerprotected: 406c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase **Ptr; 4076ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerpublic: 4089f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek typedef StringMapEntry<ValueTy> value_type; 4098bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 410c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer explicit StringMapConstIterator(StringMapEntryBase **Bucket, 411adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman bool NoAdvance = false) 412794a014809d810b7ee9a96be76774185561f0dccChris Lattner : Ptr(Bucket) { 413794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (!NoAdvance) AdvancePastEmptyBuckets(); 4146ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 41575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4169f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek const value_type &operator*() const { 417c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return *static_cast<StringMapEntry<ValueTy>*>(*Ptr); 4186ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4199f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek const value_type *operator->() const { 420c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return static_cast<StringMapEntry<ValueTy>*>(*Ptr); 4216ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 42275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4236ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator==(const StringMapConstIterator &RHS) const { 4246ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr == RHS.Ptr; 4256ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4266ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator!=(const StringMapConstIterator &RHS) const { 4276ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr != RHS.Ptr; 4286ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 42975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4306ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner inline StringMapConstIterator& operator++() { // Preincrement 4316ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 4326ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner AdvancePastEmptyBuckets(); 4336ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return *this; 4346ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4356ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator operator++(int) { // Postincrement 4366ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator tmp = *this; ++*this; return tmp; 4376ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 43875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4396ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerprivate: 4406ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner void AdvancePastEmptyBuckets() { 441c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal()) 4426ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 4436ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4446ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 4456ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 4466ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnertemplate<typename ValueTy> 4476ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerclass StringMapIterator : public StringMapConstIterator<ValueTy> { 44875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikovpublic: 449c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer explicit StringMapIterator(StringMapEntryBase **Bucket, 450ded2b0d0fb0d4fa09198e3d05da529d2c97214c3Dan Gohman bool NoAdvance = false) 451794a014809d810b7ee9a96be76774185561f0dccChris Lattner : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 4526ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4536ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> &operator*() const { 454c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 4556ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4566ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> *operator->() const { 457c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 4586ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4596ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 4606ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 46123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 46223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 463463c4a1ae9af56b6a944b74f0898e17d9a3b52ebChris Lattner#endif 464