StringMap.h revision 284ffa3863bc58f18a3eb879e49e05fdbe792413
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. 56745bf82ebac69b390911d5af0b1664fa7ff6410eEli Bendersky // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed 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; } 105284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner 106284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner void swap(StringMapImpl &Other) { 107284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(TheTable, Other.TheTable); 108284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(NumBuckets, Other.NumBuckets); 109284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(NumItems, Other.NumItems); 110284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(NumTombstones, Other.NumTombstones); 111284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner } 11223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 11323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 114ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// StringMapEntry - This is used to represent one value that is inserted into 115ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// a StringMap. It contains the Value itself and the key: the string length 116ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// and data. 117ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnertemplate<typename ValueTy> 118ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerclass StringMapEntry : public StringMapEntryBase { 119ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerpublic: 120713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov ValueTy second; 121713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 1228032020cf209721bc104648f28b1c4b45fb88691Bill Wendling explicit StringMapEntry(unsigned strLen) 1238032020cf209721bc104648f28b1c4b45fb88691Bill Wendling : StringMapEntryBase(strLen), second() {} 1248032020cf209721bc104648f28b1c4b45fb88691Bill Wendling StringMapEntry(unsigned strLen, const ValueTy &V) 1258032020cf209721bc104648f28b1c4b45fb88691Bill Wendling : StringMapEntryBase(strLen), second(V) {} 126ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 1276d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov StringRef getKey() const { 1286d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov return StringRef(getKeyData(), getKeyLength()); 1296316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar } 1306316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar 131713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov const ValueTy &getValue() const { return second; } 132713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov ValueTy &getValue() { return second; } 13375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 134713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov void setValue(const ValueTy &V) { second = V; } 13575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 136ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// getKeyData - Return the start of the string data that is the key for this 137ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// value. The string data is always stored immediately after the 138ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// StringMapEntry object. 139ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 14075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 141d7c027322ebccd9666c3f46d9a5236ba76fda434Chris Lattner StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } 142713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 1439cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Create - Create a StringMapEntry for the specified key and default 1449cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// construct the value. 145aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename AllocatorTy, typename InitType> 1469cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 147aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner AllocatorTy &Allocator, 148aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner InitType InitVal) { 14934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned KeyLength = static_cast<unsigned>(KeyEnd-KeyStart); 15075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1519cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill 1529cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // in. Allocate a new item with space for the string at the end and a null 1539cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // terminator. 15475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 15534cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 15634cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng KeyLength+1; 15716c3b647eb100fe404ee65f106d563ddef6c74b7Chris Lattner unsigned Alignment = alignOf<StringMapEntry>(); 15875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1596740463c74a7b98ec3136211c871ddd29df39887Ted Kremenek StringMapEntry *NewItem = 1606740463c74a7b98ec3136211c871ddd29df39887Ted Kremenek static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 16175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1629cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Default construct the value. 1639cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner new (NewItem) StringMapEntry(KeyLength); 16475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1659cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Copy the string information. 1669cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 1679cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner memcpy(StrBuffer, KeyStart, KeyLength); 1689cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 16975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 170aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner // Initialize the value if the client wants to. 171d7205e6ba16480ef0a7ee2b6097d0a13097e8a0fChris Lattner StringMapEntryInitializer<ValueTy>::Initialize(*NewItem, InitVal); 1729cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner return NewItem; 1739cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 17475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 175aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename AllocatorTy> 176aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 177aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner AllocatorTy &Allocator) { 17838593664b02bca98904c4b1883b0a489b5aaacbeBill Wendling return Create(KeyStart, KeyEnd, Allocator, 0); 179aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 18075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1819cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Create - Create a StringMapEntry with normal malloc/free. 182aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename InitType> 183aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 184aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner InitType InitVal) { 1859cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 186aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner return Create(KeyStart, KeyEnd, A, InitVal); 187aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 188aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner 189aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { 1904715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner return Create(KeyStart, KeyEnd, ValueTy()); 1919cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 19275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1931bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner /// GetStringMapEntryFromValue - Given a value that is known to be embedded 1941bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner /// into a StringMapEntry, return the StringMapEntry itself. 1951bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { 196b89f67e3e659da1f11c01f2aac1be3463dc60f07Chris Lattner StringMapEntry *EPtr = 0; 19775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov char *Ptr = reinterpret_cast<char*>(&V) - 198713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov (reinterpret_cast<char*>(&EPtr->second) - 1991ff2ddda083a3c71a04789fe9845d41f7aaaa0ecChris Lattner reinterpret_cast<char*>(EPtr)); 200b89f67e3e659da1f11c01f2aac1be3463dc60f07Chris Lattner return *reinterpret_cast<StringMapEntry*>(Ptr); 2011bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner } 2021bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { 2031bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); 2041bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner } 2056d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 2068ee076961219c9066b651ff686c450d92e81c27aChris Lattner /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 2078ee076961219c9066b651ff686c450d92e81c27aChris Lattner /// into a StringMapEntry, return the StringMapEntry itself. 2088ee076961219c9066b651ff686c450d92e81c27aChris Lattner static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { 2098ee076961219c9066b651ff686c450d92e81c27aChris Lattner char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>); 2108ee076961219c9066b651ff686c450d92e81c27aChris Lattner return *reinterpret_cast<StringMapEntry*>(Ptr); 2118ee076961219c9066b651ff686c450d92e81c27aChris Lattner } 2126d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 2139cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy - Destroy this StringMapEntry, releasing memory back to the 2149cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// specified allocator. 2159cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner template<typename AllocatorTy> 2169cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy(AllocatorTy &Allocator) { 2179cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Free memory referenced by the item. 2189cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner this->~StringMapEntry(); 2199cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner Allocator.Deallocate(this); 2209cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 22175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 2229cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy this object, releasing memory back to the malloc allocator. 2239cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy() { 2249cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 2259cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner Destroy(A); 2269cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 227ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner}; 228ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 22923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 230bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner/// StringMap - This is an unconventional map that is specialized for handling 231ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// keys that are "strings", which are basically ranges of bytes. This does some 23223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// funky memory allocation and hashing things to make it extremely efficient, 23323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// storing the string data *after* the value in the map. 23423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnertemplate<typename ValueTy, typename AllocatorTy = MallocAllocator> 235bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerclass StringMap : public StringMapImpl { 23623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner AllocatorTy Allocator; 23723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerpublic: 238e55bbfe145cf8dcb9594865f0242321d2be681d6Chris Lattner typedef StringMapEntry<ValueTy> MapEntryTy; 239e55bbfe145cf8dcb9594865f0242321d2be681d6Chris Lattner 24034cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 241adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMap(unsigned InitialSize) 24234cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 2436d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 244a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner explicit StringMap(AllocatorTy A) 245a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 246a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner 2473735573343614644ead7a8bae674c312db8b1eb1Argyrios Kyrtzidis StringMap(unsigned InitialSize, AllocatorTy A) 24847f39340211f537cf79610832194c1884d420d62Argyrios Kyrtzidis : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), 24947f39340211f537cf79610832194c1884d420d62Argyrios Kyrtzidis Allocator(A) {} 2503735573343614644ead7a8bae674c312db8b1eb1Argyrios Kyrtzidis 251164dfb094df947db2117c182ae033ea85c6c42a1Benjamin Kramer StringMap(const StringMap &RHS) 2524715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) { 2534715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner assert(RHS.empty() && 2544715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner "Copy ctor from non-empty stringmap not implemented yet!"); 2551c3f050309592e034972dc77a2eb4025680ff293Frits van Bommel (void)RHS; 2564715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner } 2574715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner void operator=(const StringMap &RHS) { 2584715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner assert(RHS.empty() && 2594715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner "assignment from non-empty stringmap not implemented yet!"); 2601c3f050309592e034972dc77a2eb4025680ff293Frits van Bommel (void)RHS; 2614715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner clear(); 2624715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner } 2634715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner 264061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; 265061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; 266061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner AllocatorRefTy getAllocator() { return Allocator; } 267061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner AllocatorCRefTy getAllocator() const { return Allocator; } 26823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 269713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef const char* key_type; 270713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef ValueTy mapped_type; 271713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef StringMapEntry<ValueTy> value_type; 272713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef size_t size_type; 273713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 2746ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapConstIterator<ValueTy> const_iterator; 2756ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapIterator<ValueTy> iterator; 27675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 277794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator begin() { 278794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable, NumBuckets == 0); 279794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 280794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator end() { 281794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable+NumBuckets, true); 282794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 283794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator begin() const { 284794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable, NumBuckets == 0); 285794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 286794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator end() const { 287794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable+NumBuckets, true); 288794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 28975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 2902928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar iterator find(StringRef Key) { 2916316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 292b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 29385c07ce0481daa8f462943f621efdb7f21f6d3efBenjamin Kramer return iterator(TheTable+Bucket, true); 294b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 295b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 2962928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar const_iterator find(StringRef Key) const { 2976316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 298b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 29985c07ce0481daa8f462943f621efdb7f21f6d3efBenjamin Kramer return const_iterator(TheTable+Bucket, true); 3006c1645ce7da8495c79e3d38bbf91ce77bf489c10Chris Lattner } 301713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 302745bf82ebac69b390911d5af0b1664fa7ff6410eEli Bendersky /// lookup - Return the entry for the specified key, or a default 303e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar /// constructed value if no such entry exists. 3042928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar ValueTy lookup(StringRef Key) const { 305e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar const_iterator it = find(Key); 306e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar if (it != end()) 307e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar return it->second; 308e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar return ValueTy(); 309e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar } 310e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar 31139ff10a293012fe6f2db682c5518e1be2c50ca67Chris Lattner ValueTy &operator[](StringRef Key) { 3126316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return GetOrCreateValue(Key).getValue(); 313ec3e5c8a39c3dae7457d0eb18f98685decb23fcdAnton Korobeynikov } 314713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 3152928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar size_type count(StringRef Key) const { 3166316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return find(Key) == end() ? 0 : 1; 317ec3e5c8a39c3dae7457d0eb18f98685decb23fcdAnton Korobeynikov } 318713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 31944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert - Insert the specified key/value pair into the map. If the key 32044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// already exists in the map, return false and ignore the request, otherwise 32144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert it and return true. 32244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner bool insert(MapEntryTy *KeyValue) { 3236316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 324c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *&Bucket = TheTable[BucketNo]; 325c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket && Bucket != getTombstoneVal()) 32644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return false; // Already exists in map. 32775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 328c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket == getTombstoneVal()) 32944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumTombstones; 330c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer Bucket = KeyValue; 33144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner ++NumItems; 33203ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen assert(NumItems + NumTombstones <= NumBuckets); 33375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 334aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen RehashTable(); 33544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return true; 33644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 33775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 338fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner // clear - Empties out the StringMap 339fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner void clear() { 340509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner if (empty()) return; 3418bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 342509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner // Zap all values, resetting the keys back to non-present (not tombstone), 343509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner // which is safe because we're removing all elements. 344c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 345c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *&Bucket = TheTable[I]; 346c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket && Bucket != getTombstoneVal()) { 347c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 348509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner } 349633e24dc043c32ddfcfcf6181fe976e218dcb57aPedro Artigas Bucket = 0; 350509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner } 3518bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 3528bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman NumItems = 0; 35303ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen NumTombstones = 0; 354fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner } 355fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner 35623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// GetOrCreateValue - Look up the specified key in the table. If a value 35723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// exists, return it. Otherwise, default construct a value, insert it, and 35823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// return. 359aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template <typename InitTy> 36039ff10a293012fe6f2db682c5518e1be2c50ca67Chris Lattner MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { 3616316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar unsigned BucketNo = LookupBucketFor(Key); 362c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *&Bucket = TheTable[BucketNo]; 363c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket && Bucket != getTombstoneVal()) 364c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return *static_cast<MapEntryTy*>(Bucket); 36575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 3666316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar MapEntryTy *NewItem = 3676316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); 36875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 369c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket == getTombstoneVal()) 37044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumTombstones; 37123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ++NumItems; 37203ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen assert(NumItems + NumTombstones <= NumBuckets); 37375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 37423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Fill in the bucket for the hash table. The FullHashValue was already 37523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // filled in by LookupBucketFor. 376c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer Bucket = NewItem; 37775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 378aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen RehashTable(); 37923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner return *NewItem; 38023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 38175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 38239ff10a293012fe6f2db682c5518e1be2c50ca67Chris Lattner MapEntryTy &GetOrCreateValue(StringRef Key) { 3836316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return GetOrCreateValue(Key, ValueTy()); 3846316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar } 3856316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar 38644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// remove - Remove the specified key/value pair from the map, but do not 38744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// erase it. This aborts if the key is not in the map. 38844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner void remove(MapEntryTy *KeyValue) { 38944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner RemoveKey(KeyValue); 39044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 39175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 392c6402013c8767d5718d4c7ae5625969361182771Chris Lattner void erase(iterator I) { 393c6402013c8767d5718d4c7ae5625969361182771Chris Lattner MapEntryTy &V = *I; 394c6402013c8767d5718d4c7ae5625969361182771Chris Lattner remove(&V); 395c6402013c8767d5718d4c7ae5625969361182771Chris Lattner V.Destroy(Allocator); 39684701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman } 39784701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman 3982928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar bool erase(StringRef Key) { 39984701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman iterator I = find(Key); 40084701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman if (I == end()) return false; 40184701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman erase(I); 40284701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman return true; 403c6402013c8767d5718d4c7ae5625969361182771Chris Lattner } 40475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 405bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner ~StringMap() { 406509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner clear(); 407d2f197da59a3c937c1809997907918c029f9f884Chris Lattner free(TheTable); 40823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 40923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 41075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4116ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 4126ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnertemplate<typename ValueTy> 4136ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerclass StringMapConstIterator { 41444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattnerprotected: 415c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase **Ptr; 4166ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerpublic: 4179f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek typedef StringMapEntry<ValueTy> value_type; 4188bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 419284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner StringMapConstIterator() : Ptr(0) { } 420284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner 421c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer explicit StringMapConstIterator(StringMapEntryBase **Bucket, 422adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman bool NoAdvance = false) 423794a014809d810b7ee9a96be76774185561f0dccChris Lattner : Ptr(Bucket) { 424794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (!NoAdvance) AdvancePastEmptyBuckets(); 4256ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 42675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4279f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek const value_type &operator*() const { 428c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return *static_cast<StringMapEntry<ValueTy>*>(*Ptr); 4296ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4309f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek const value_type *operator->() const { 431c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return static_cast<StringMapEntry<ValueTy>*>(*Ptr); 4326ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 43375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4346ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator==(const StringMapConstIterator &RHS) const { 4356ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr == RHS.Ptr; 4366ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4376ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator!=(const StringMapConstIterator &RHS) const { 4386ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr != RHS.Ptr; 4396ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 44075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 441745bf82ebac69b390911d5af0b1664fa7ff6410eEli Bendersky inline StringMapConstIterator& operator++() { // Preincrement 4426ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 4436ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner AdvancePastEmptyBuckets(); 4446ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return *this; 4456ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4466ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator operator++(int) { // Postincrement 4476ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator tmp = *this; ++*this; return tmp; 4486ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 44975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4506ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerprivate: 4516ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner void AdvancePastEmptyBuckets() { 452c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal()) 4536ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 4546ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4556ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 4566ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 4576ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnertemplate<typename ValueTy> 4586ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerclass StringMapIterator : public StringMapConstIterator<ValueTy> { 45975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikovpublic: 460284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner StringMapIterator() : StringMapConstIterator() {} 461c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer explicit StringMapIterator(StringMapEntryBase **Bucket, 462ded2b0d0fb0d4fa09198e3d05da529d2c97214c3Dan Gohman bool NoAdvance = false) 463794a014809d810b7ee9a96be76774185561f0dccChris Lattner : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 4646ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4656ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> &operator*() const { 466c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 4676ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4686ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> *operator->() const { 469c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 4706ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4716ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 4726ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 47323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 47423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 475463c4a1ae9af56b6a944b74f0898e17d9a3b52ebChris Lattner#endif 476