StringMap.h revision 1c3f050309592e034972dc77a2eb4025680ff293
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> 20ec3e5c8a39c3dae7457d0eb18f98685decb23fcdAnton Korobeynikov#include <string> 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 30aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner/// StringMapEntryInitializer - This datatype can be partially specialized for 3175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov/// various datatypes in a stringmap to allow them to be initialized when an 32aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner/// entry is default constructed for the map. 33aec78708c24a85a99b757ada086e5c05a4c123edChris Lattnertemplate<typename ValueTy> 34aec78708c24a85a99b757ada086e5c05a4c123edChris Lattnerclass StringMapEntryInitializer { 35aec78708c24a85a99b757ada086e5c05a4c123edChris Lattnerpublic: 36aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template <typename InitTy> 37d7205e6ba16480ef0a7ee2b6097d0a13097e8a0fChris Lattner static void Initialize(StringMapEntry<ValueTy> &T, InitTy InitVal) { 384715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner T.second = InitVal; 39aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 40aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner}; 4175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 43ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// StringMapEntryBase - Shared base class of StringMapEntry instances. 44ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerclass StringMapEntryBase { 45ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner unsigned StrLen; 46ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerpublic: 47adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} 4875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 49ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner unsigned getKeyLength() const { return StrLen; } 50ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner}; 5175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 52bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner/// StringMapImpl - This is the base class of StringMap that is shared among 5323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// all of its instantiations. 54bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerclass StringMapImpl { 556ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerpublic: 5623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// ItemBucket - The hash table consists of an array of these. If Item is 5723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// non-null, this is an extant entry, otherwise, it is a hole. 5823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner struct ItemBucket { 5923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// FullHashValue - This remembers the full hash value of the key for 6023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// easy scanning. 6123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned FullHashValue; 6275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 6323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// Item - This is a pointer to the actual item object. 64ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner StringMapEntryBase *Item; 6523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner }; 6675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 676ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerprotected: 6823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ItemBucket *TheTable; 6923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NumBuckets; 7023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NumItems; 7144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner unsigned NumTombstones; 7223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned ItemSize; 7323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerprotected: 74adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) { 75c6402013c8767d5718d4c7ae5625969361182771Chris Lattner // Initialize the map with zero buckets to allocation. 76c6402013c8767d5718d4c7ae5625969361182771Chris Lattner TheTable = 0; 77c6402013c8767d5718d4c7ae5625969361182771Chris Lattner NumBuckets = 0; 78c6402013c8767d5718d4c7ae5625969361182771Chris Lattner NumItems = 0; 79c6402013c8767d5718d4c7ae5625969361182771Chris Lattner NumTombstones = 0; 80c6402013c8767d5718d4c7ae5625969361182771Chris Lattner } 81bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner StringMapImpl(unsigned InitSize, unsigned ItemSize); 8223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner void RehashTable(); 8375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 84a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner /// ShouldRehash - Return true if the table should be rehashed after a new 85a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner /// element was recently inserted. 86a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner bool ShouldRehash() const { 87a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner // If the hash table is now more than 3/4 full, or if fewer than 1/8 of 88a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 89a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner // grow the table. 90a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner return NumItems*4 > NumBuckets*3 || 91a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner NumBuckets-(NumItems+NumTombstones) < NumBuckets/8; 92a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner } 9375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 9423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// LookupBucketFor - Look up the bucket that the specified string should end 9523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// up in. If it already exists as a key in the map, the Item pointer for the 9623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// specified bucket will be non-null. Otherwise, it will be null. In either 9723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// case, the FullHashValue field of the bucket will be set to the hash value 9823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// of the string. 992928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar unsigned LookupBucketFor(StringRef Key); 10075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 101b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// FindKey - Look up the bucket that contains the specified key. If it exists 102b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// in the map, return the bucket number of the key. Otherwise return -1. 103b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// This does not modify the map. 1042928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar int FindKey(StringRef Key) const; 10544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 10644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 10744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// delete it. This aborts if the value isn't in the table. 10844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner void RemoveKey(StringMapEntryBase *V); 10944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 11044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// RemoveKey - Remove the StringMapEntry for the specified key from the 11144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// table, returning it. If the key is not in the table, this returns null. 1122928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar StringMapEntryBase *RemoveKey(StringRef Key); 113794a014809d810b7ee9a96be76774185561f0dccChris Lattnerprivate: 114794a014809d810b7ee9a96be76774185561f0dccChris Lattner void init(unsigned Size); 11523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerpublic: 1166ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner static StringMapEntryBase *getTombstoneVal() { 1176ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return (StringMapEntryBase*)-1; 1186ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 11975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 12023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned getNumBuckets() const { return NumBuckets; } 12123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned getNumItems() const { return NumItems; } 12223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 1236ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool empty() const { return NumItems == 0; } 1246ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner unsigned size() const { return NumItems; } 12523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 12623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 127ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// StringMapEntry - This is used to represent one value that is inserted into 128ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// a StringMap. It contains the Value itself and the key: the string length 129ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// and data. 130ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnertemplate<typename ValueTy> 131ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerclass StringMapEntry : public StringMapEntryBase { 132ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerpublic: 133713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov ValueTy second; 134713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 1358032020cf209721bc104648f28b1c4b45fb88691Bill Wendling explicit StringMapEntry(unsigned strLen) 1368032020cf209721bc104648f28b1c4b45fb88691Bill Wendling : StringMapEntryBase(strLen), second() {} 1378032020cf209721bc104648f28b1c4b45fb88691Bill Wendling StringMapEntry(unsigned strLen, const ValueTy &V) 1388032020cf209721bc104648f28b1c4b45fb88691Bill Wendling : StringMapEntryBase(strLen), second(V) {} 139ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 1406d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov StringRef getKey() const { 1416d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov return StringRef(getKeyData(), getKeyLength()); 1426316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar } 1436316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar 144713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov const ValueTy &getValue() const { return second; } 145713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov ValueTy &getValue() { return second; } 14675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 147713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov void setValue(const ValueTy &V) { second = V; } 14875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 149ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// getKeyData - Return the start of the string data that is the key for this 150ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// value. The string data is always stored immediately after the 151ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// StringMapEntry object. 152ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 15375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 154713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov const char *first() const { return getKeyData(); } 155713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 1569cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Create - Create a StringMapEntry for the specified key and default 1579cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// construct the value. 158aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename AllocatorTy, typename InitType> 1599cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 160aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner AllocatorTy &Allocator, 161aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner InitType InitVal) { 16234cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned KeyLength = static_cast<unsigned>(KeyEnd-KeyStart); 16375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1649cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill 1659cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // in. Allocate a new item with space for the string at the end and a null 1669cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // terminator. 16775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 16834cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 16934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng KeyLength+1; 17016c3b647eb100fe404ee65f106d563ddef6c74b7Chris Lattner unsigned Alignment = alignOf<StringMapEntry>(); 17175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1726740463c74a7b98ec3136211c871ddd29df39887Ted Kremenek StringMapEntry *NewItem = 1736740463c74a7b98ec3136211c871ddd29df39887Ted Kremenek static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 17475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1759cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Default construct the value. 1769cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner new (NewItem) StringMapEntry(KeyLength); 17775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1789cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Copy the string information. 1799cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 1809cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner memcpy(StrBuffer, KeyStart, KeyLength); 1819cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 18275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 183aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner // Initialize the value if the client wants to. 184d7205e6ba16480ef0a7ee2b6097d0a13097e8a0fChris Lattner StringMapEntryInitializer<ValueTy>::Initialize(*NewItem, InitVal); 1859cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner return NewItem; 1869cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 18775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 188aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename AllocatorTy> 189aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 190aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner AllocatorTy &Allocator) { 19138593664b02bca98904c4b1883b0a489b5aaacbeBill Wendling return Create(KeyStart, KeyEnd, Allocator, 0); 192aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 19375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 19475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1959cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Create - Create a StringMapEntry with normal malloc/free. 196aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template<typename InitType> 197aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 198aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner InitType InitVal) { 1999cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 200aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner return Create(KeyStart, KeyEnd, A, InitVal); 201aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 202aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner 203aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { 2044715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner return Create(KeyStart, KeyEnd, ValueTy()); 2059cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 20675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 2071bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner /// GetStringMapEntryFromValue - Given a value that is known to be embedded 2081bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner /// into a StringMapEntry, return the StringMapEntry itself. 2091bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { 210b89f67e3e659da1f11c01f2aac1be3463dc60f07Chris Lattner StringMapEntry *EPtr = 0; 21175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov char *Ptr = reinterpret_cast<char*>(&V) - 212713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov (reinterpret_cast<char*>(&EPtr->second) - 2131ff2ddda083a3c71a04789fe9845d41f7aaaa0ecChris Lattner reinterpret_cast<char*>(EPtr)); 214b89f67e3e659da1f11c01f2aac1be3463dc60f07Chris Lattner return *reinterpret_cast<StringMapEntry*>(Ptr); 2151bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner } 2161bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { 2171bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); 2181bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner } 2196d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 2208ee076961219c9066b651ff686c450d92e81c27aChris Lattner /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 2218ee076961219c9066b651ff686c450d92e81c27aChris Lattner /// into a StringMapEntry, return the StringMapEntry itself. 2228ee076961219c9066b651ff686c450d92e81c27aChris Lattner static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { 2238ee076961219c9066b651ff686c450d92e81c27aChris Lattner char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>); 2248ee076961219c9066b651ff686c450d92e81c27aChris Lattner return *reinterpret_cast<StringMapEntry*>(Ptr); 2258ee076961219c9066b651ff686c450d92e81c27aChris Lattner } 2266d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 22775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 2289cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy - Destroy this StringMapEntry, releasing memory back to the 2299cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// specified allocator. 2309cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner template<typename AllocatorTy> 2319cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy(AllocatorTy &Allocator) { 2329cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Free memory referenced by the item. 2339cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner this->~StringMapEntry(); 2349cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner Allocator.Deallocate(this); 2359cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 23675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 2379cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy this object, releasing memory back to the malloc allocator. 2389cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy() { 2399cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 2409cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner Destroy(A); 2419cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 242ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner}; 243ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 24423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 245061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattnertemplate <typename T> struct ReferenceAdder { typedef T& result; }; 246061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattnertemplate <typename T> struct ReferenceAdder<T&> { typedef T result; }; 2476d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 248bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner/// StringMap - This is an unconventional map that is specialized for handling 249ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// keys that are "strings", which are basically ranges of bytes. This does some 25023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// funky memory allocation and hashing things to make it extremely efficient, 25123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// storing the string data *after* the value in the map. 25223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnertemplate<typename ValueTy, typename AllocatorTy = MallocAllocator> 253bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerclass StringMap : public StringMapImpl { 25423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner AllocatorTy Allocator; 255ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner typedef StringMapEntry<ValueTy> MapEntryTy; 25623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerpublic: 25734cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 258adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMap(unsigned InitialSize) 25934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 2606d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 261a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner explicit StringMap(AllocatorTy A) 262a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 263a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner 2644715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner explicit StringMap(const StringMap &RHS) 2654715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) { 2664715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner assert(RHS.empty() && 2674715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner "Copy ctor from non-empty stringmap not implemented yet!"); 2681c3f050309592e034972dc77a2eb4025680ff293Frits van Bommel (void)RHS; 2694715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner } 2704715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner void operator=(const StringMap &RHS) { 2714715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner assert(RHS.empty() && 2724715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner "assignment from non-empty stringmap not implemented yet!"); 2731c3f050309592e034972dc77a2eb4025680ff293Frits van Bommel (void)RHS; 2744715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner clear(); 2754715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner } 2764715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner 277061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; 278061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; 279061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner AllocatorRefTy getAllocator() { return Allocator; } 280061d21eaf8fcdb19b85db0755c208acbba7c8ef4Chris Lattner AllocatorCRefTy getAllocator() const { return Allocator; } 28123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 282713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef const char* key_type; 283713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef ValueTy mapped_type; 284713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef StringMapEntry<ValueTy> value_type; 285713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef size_t size_type; 286713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 2876ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapConstIterator<ValueTy> const_iterator; 2886ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapIterator<ValueTy> iterator; 28975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 290794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator begin() { 291794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable, NumBuckets == 0); 292794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 293794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator end() { 294794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable+NumBuckets, true); 295794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 296794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator begin() const { 297794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable, NumBuckets == 0); 298794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 299794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator end() const { 300794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable+NumBuckets, true); 301794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 30275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 3032928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar iterator find(StringRef Key) { 3046316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 305b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 306b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner return iterator(TheTable+Bucket); 307b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 308b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 3092928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar const_iterator find(StringRef Key) const { 3106316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 311b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 312b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner return const_iterator(TheTable+Bucket); 3136c1645ce7da8495c79e3d38bbf91ce77bf489c10Chris Lattner } 314713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 315e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar /// lookup - Return the entry for the specified key, or a default 316e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar /// constructed value if no such entry exists. 3172928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar ValueTy lookup(StringRef Key) const { 318e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar const_iterator it = find(Key); 319e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar if (it != end()) 320e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar return it->second; 321e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar return ValueTy(); 322e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar } 323e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar 3242928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar ValueTy& operator[](StringRef Key) { 3256316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return GetOrCreateValue(Key).getValue(); 326ec3e5c8a39c3dae7457d0eb18f98685decb23fcdAnton Korobeynikov } 327713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 3282928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar size_type count(StringRef Key) const { 3296316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return find(Key) == end() ? 0 : 1; 330ec3e5c8a39c3dae7457d0eb18f98685decb23fcdAnton Korobeynikov } 331713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 33244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert - Insert the specified key/value pair into the map. If the key 33344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// already exists in the map, return false and ignore the request, otherwise 33444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert it and return true. 33544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner bool insert(MapEntryTy *KeyValue) { 3366316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 33744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner ItemBucket &Bucket = TheTable[BucketNo]; 33875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov if (Bucket.Item && Bucket.Item != getTombstoneVal()) 33944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return false; // Already exists in map. 34075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 34144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (Bucket.Item == getTombstoneVal()) 34244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumTombstones; 34344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner Bucket.Item = KeyValue; 34444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner ++NumItems; 34575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 346a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner if (ShouldRehash()) 34744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner RehashTable(); 34844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return true; 34944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 35075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 351fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner // clear - Empties out the StringMap 352fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner void clear() { 353509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner if (empty()) return; 3548bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 355509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner // Zap all values, resetting the keys back to non-present (not tombstone), 356509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner // which is safe because we're removing all elements. 357509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { 358509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner if (I->Item && I->Item != getTombstoneVal()) { 359509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator); 360509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner I->Item = 0; 361509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner } 362509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner } 3638bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 3648bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman NumItems = 0; 365fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner } 366fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner 36723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// GetOrCreateValue - Look up the specified key in the table. If a value 36823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// exists, return it. Otherwise, default construct a value, insert it, and 36923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// return. 370aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner template <typename InitTy> 3712928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar StringMapEntry<ValueTy> &GetOrCreateValue(StringRef Key, 372aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner InitTy Val) { 3736316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar unsigned BucketNo = LookupBucketFor(Key); 37423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ItemBucket &Bucket = TheTable[BucketNo]; 37544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (Bucket.Item && Bucket.Item != getTombstoneVal()) 376ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner return *static_cast<MapEntryTy*>(Bucket.Item); 37775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 3786316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar MapEntryTy *NewItem = 3796316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); 38075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 38144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (Bucket.Item == getTombstoneVal()) 38244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumTombstones; 38323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ++NumItems; 38475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 38523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Fill in the bucket for the hash table. The FullHashValue was already 38623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // filled in by LookupBucketFor. 38723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner Bucket.Item = NewItem; 38875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 389a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner if (ShouldRehash()) 39023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner RehashTable(); 39123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner return *NewItem; 39223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 39375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 3942928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar StringMapEntry<ValueTy> &GetOrCreateValue(StringRef Key) { 3956316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return GetOrCreateValue(Key, ValueTy()); 3966316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar } 3976316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar 3986316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar template <typename InitTy> 3996316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, 4006316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar const char *KeyEnd, 4016316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar InitTy Val) { 4026316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart), Val); 4036316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar } 4046316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar 40575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, 406aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner const char *KeyEnd) { 4076316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart)); 408aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 40975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 41044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// remove - Remove the specified key/value pair from the map, but do not 41144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// erase it. This aborts if the key is not in the map. 41244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner void remove(MapEntryTy *KeyValue) { 41344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner RemoveKey(KeyValue); 41444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 41575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 416c6402013c8767d5718d4c7ae5625969361182771Chris Lattner void erase(iterator I) { 417c6402013c8767d5718d4c7ae5625969361182771Chris Lattner MapEntryTy &V = *I; 418c6402013c8767d5718d4c7ae5625969361182771Chris Lattner remove(&V); 419c6402013c8767d5718d4c7ae5625969361182771Chris Lattner V.Destroy(Allocator); 42084701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman } 42184701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman 4222928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar bool erase(StringRef Key) { 42384701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman iterator I = find(Key); 42484701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman if (I == end()) return false; 42584701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman erase(I); 42684701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman return true; 427c6402013c8767d5718d4c7ae5625969361182771Chris Lattner } 42875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 429bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner ~StringMap() { 430509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner clear(); 431d2f197da59a3c937c1809997907918c029f9f884Chris Lattner free(TheTable); 43223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 43323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 43475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4356ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 4366ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnertemplate<typename ValueTy> 4376ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerclass StringMapConstIterator { 43844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattnerprotected: 4396ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapImpl::ItemBucket *Ptr; 4406ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerpublic: 4419f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek typedef StringMapEntry<ValueTy> value_type; 4428bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 443adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMapConstIterator(StringMapImpl::ItemBucket *Bucket, 444adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman bool NoAdvance = false) 445794a014809d810b7ee9a96be76774185561f0dccChris Lattner : Ptr(Bucket) { 446794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (!NoAdvance) AdvancePastEmptyBuckets(); 4476ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 44875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4499f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek const value_type &operator*() const { 4506ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return *static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 4516ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4529f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek const value_type *operator->() const { 4536ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 4546ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 45575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4566ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator==(const StringMapConstIterator &RHS) const { 4576ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr == RHS.Ptr; 4586ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4596ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator!=(const StringMapConstIterator &RHS) const { 4606ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr != RHS.Ptr; 4616ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 46275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4636ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner inline StringMapConstIterator& operator++() { // Preincrement 4646ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 4656ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner AdvancePastEmptyBuckets(); 4666ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return *this; 4676ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4686ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator operator++(int) { // Postincrement 4696ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator tmp = *this; ++*this; return tmp; 4706ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 47175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4726ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerprivate: 4736ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner void AdvancePastEmptyBuckets() { 4746ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal()) 4756ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 4766ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4776ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 4786ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 4796ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnertemplate<typename ValueTy> 4806ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerclass StringMapIterator : public StringMapConstIterator<ValueTy> { 48175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikovpublic: 482ded2b0d0fb0d4fa09198e3d05da529d2c97214c3Dan Gohman explicit StringMapIterator(StringMapImpl::ItemBucket *Bucket, 483ded2b0d0fb0d4fa09198e3d05da529d2c97214c3Dan Gohman bool NoAdvance = false) 484794a014809d810b7ee9a96be76774185561f0dccChris Lattner : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 4856ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4866ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> &operator*() const { 4876ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 4886ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4896ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> *operator->() const { 4906ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 4916ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4926ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 4936ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 49423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 49523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 496463c4a1ae9af56b6a944b74f0898e17d9a3b52ebChris Lattner#endif 497