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" 19de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Support/PointerLikeTypeTraits.h" 2023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner#include <cstring> 21dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include <utility> 2223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 2323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnernamespace llvm { 246ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner template<typename ValueT> 256ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner class StringMapConstIterator; 266ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner template<typename ValueT> 276ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner class StringMapIterator; 28d7205e6ba16480ef0a7ee2b6097d0a13097e8a0fChris Lattner template<typename ValueTy> 29d7205e6ba16480ef0a7ee2b6097d0a13097e8a0fChris Lattner class StringMapEntry; 306ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 31ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// StringMapEntryBase - Shared base class of StringMapEntry instances. 32ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerclass StringMapEntryBase { 33ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner unsigned StrLen; 34f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 35ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerpublic: 36adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} 3775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 38ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner unsigned getKeyLength() const { return StrLen; } 39ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner}; 4075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 41bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner/// StringMapImpl - This is the base class of StringMap that is shared among 4223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// all of its instantiations. 43bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerclass StringMapImpl { 446ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerprotected: 45c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer // Array of NumBuckets pointers to entries, null pointers are holes. 46745bf82ebac69b390911d5af0b1664fa7ff6410eEli Bendersky // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed 47c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer // by an array of the actual hash values as unsigned integers. 48c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase **TheTable; 4923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NumBuckets; 5023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NumItems; 5144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner unsigned NumTombstones; 5223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned ItemSize; 53f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 5423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerprotected: 55dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines explicit StringMapImpl(unsigned itemSize) 56dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : TheTable(nullptr), 57dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Initialize the map with zero buckets to allocation. 58dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NumBuckets(0), NumItems(0), NumTombstones(0), ItemSize(itemSize) {} 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines StringMapImpl(StringMapImpl &&RHS) 60dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets), 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones), 62dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ItemSize(RHS.ItemSize) { 63dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.TheTable = nullptr; 64dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.NumBuckets = 0; 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.NumItems = 0; 66dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.NumTombstones = 0; 67c6402013c8767d5718d4c7ae5625969361182771Chris Lattner } 68dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 69bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner StringMapImpl(unsigned InitSize, unsigned ItemSize); 70c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines unsigned RehashTable(unsigned BucketNo = 0); 7175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 7223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// LookupBucketFor - Look up the bucket that the specified string should end 7323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// up in. If it already exists as a key in the map, the Item pointer for the 7423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// specified bucket will be non-null. Otherwise, it will be null. In either 7523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// case, the FullHashValue field of the bucket will be set to the hash value 7623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// of the string. 772928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar unsigned LookupBucketFor(StringRef Key); 7875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 79b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// FindKey - Look up the bucket that contains the specified key. If it exists 80b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// in the map, return the bucket number of the key. Otherwise return -1. 81b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// This does not modify the map. 822928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar int FindKey(StringRef Key) const; 8344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 8444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 8544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// delete it. This aborts if the value isn't in the table. 8644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner void RemoveKey(StringMapEntryBase *V); 8744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 8844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// RemoveKey - Remove the StringMapEntry for the specified key from the 8944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// table, returning it. If the key is not in the table, this returns null. 902928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar StringMapEntryBase *RemoveKey(StringRef Key); 91f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 92de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Allocate the table with the specified number of buckets and otherwise 93de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// setup the map as empty. 94794a014809d810b7ee9a96be76774185561f0dccChris Lattner void init(unsigned Size); 95f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 9623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerpublic: 976ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner static StringMapEntryBase *getTombstoneVal() { 98de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar uintptr_t Val = static_cast<uintptr_t>(-1); 99de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable; 100de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return reinterpret_cast<StringMapEntryBase *>(Val); 1016ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 10275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 10323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned getNumBuckets() const { return NumBuckets; } 10423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned getNumItems() const { return NumItems; } 10523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 1066ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool empty() const { return NumItems == 0; } 1076ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner unsigned size() const { return NumItems; } 108284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner 109284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner void swap(StringMapImpl &Other) { 110284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(TheTable, Other.TheTable); 111284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(NumBuckets, Other.NumBuckets); 112284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(NumItems, Other.NumItems); 113284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner std::swap(NumTombstones, Other.NumTombstones); 114284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner } 11523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 11623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 117ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// StringMapEntry - This is used to represent one value that is inserted into 118ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// a StringMap. It contains the Value itself and the key: the string length 119ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// and data. 120ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnertemplate<typename ValueTy> 121ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerclass StringMapEntry : public StringMapEntryBase { 122ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines StringMapEntry(StringMapEntry &E) = delete; 123f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 124ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerpublic: 125713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov ValueTy second; 126713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 1278032020cf209721bc104648f28b1c4b45fb88691Bill Wendling explicit StringMapEntry(unsigned strLen) 1288032020cf209721bc104648f28b1c4b45fb88691Bill Wendling : StringMapEntryBase(strLen), second() {} 129de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar template <typename... InitTy> 130de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StringMapEntry(unsigned strLen, InitTy &&... InitVals) 131de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {} 132ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 1336d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov StringRef getKey() const { 1346d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov return StringRef(getKeyData(), getKeyLength()); 1356316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar } 1366316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar 137713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov const ValueTy &getValue() const { return second; } 138713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov ValueTy &getValue() { return second; } 13975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 140713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov void setValue(const ValueTy &V) { second = V; } 14175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 142ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// getKeyData - Return the start of the string data that is the key for this 143ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// value. The string data is always stored immediately after the 144ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// StringMapEntry object. 145ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 14675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 147d7c027322ebccd9666c3f46d9a5236ba76fda434Chris Lattner StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } 148713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 149de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Create a StringMapEntry for the specified key construct the value using 150de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \p InitiVals. 151de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar template <typename AllocatorTy, typename... InitTy> 15237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator, 153de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InitTy &&... InitVals) { 154c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines unsigned KeyLength = Key.size(); 15575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Allocate a new item with space for the string at the end and a null 1579cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // terminator. 15834cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 15934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng KeyLength+1; 16016c3b647eb100fe404ee65f106d563ddef6c74b7Chris Lattner unsigned Alignment = alignOf<StringMapEntry>(); 16175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1626740463c74a7b98ec3136211c871ddd29df39887Ted Kremenek StringMapEntry *NewItem = 1636740463c74a7b98ec3136211c871ddd29df39887Ted Kremenek static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 16475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 165de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Construct the value. 166de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...); 16775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1689cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Copy the string information. 1699cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 170f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (KeyLength > 0) 171f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar memcpy(StrBuffer, Key.data(), KeyLength); 1729cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 1739cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner return NewItem; 1749cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 17575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1769cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Create - Create a StringMapEntry with normal malloc/free. 177de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar template <typename... InitType> 178de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) { 1799cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 180de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Create(Key, A, std::forward<InitType>(InitVal)...); 181aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner } 182aec78708c24a85a99b757ada086e5c05a4c123edChris Lattner 183c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines static StringMapEntry *Create(StringRef Key) { 184c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return Create(Key, ValueTy()); 1859cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 18675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 1878ee076961219c9066b651ff686c450d92e81c27aChris Lattner /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 1888ee076961219c9066b651ff686c450d92e81c27aChris Lattner /// into a StringMapEntry, return the StringMapEntry itself. 1898ee076961219c9066b651ff686c450d92e81c27aChris Lattner static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { 1908ee076961219c9066b651ff686c450d92e81c27aChris Lattner char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>); 1918ee076961219c9066b651ff686c450d92e81c27aChris Lattner return *reinterpret_cast<StringMapEntry*>(Ptr); 1928ee076961219c9066b651ff686c450d92e81c27aChris Lattner } 1936d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 1949cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy - Destroy this StringMapEntry, releasing memory back to the 1959cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// specified allocator. 1969cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner template<typename AllocatorTy> 1979cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy(AllocatorTy &Allocator) { 1989cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Free memory referenced by the item. 199dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines unsigned AllocSize = 200dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1; 2019cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner this->~StringMapEntry(); 202dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Allocator.Deallocate(static_cast<void *>(this), AllocSize); 2039cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 20475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 2059cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy this object, releasing memory back to the malloc allocator. 2069cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy() { 2079cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 2089cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner Destroy(A); 2099cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 210ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner}; 211ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 212bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner/// StringMap - This is an unconventional map that is specialized for handling 213ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// keys that are "strings", which are basically ranges of bytes. This does some 21423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// funky memory allocation and hashing things to make it extremely efficient, 21523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// storing the string data *after* the value in the map. 21623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnertemplate<typename ValueTy, typename AllocatorTy = MallocAllocator> 217bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerclass StringMap : public StringMapImpl { 21823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner AllocatorTy Allocator; 219f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 22023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerpublic: 221e55bbfe145cf8dcb9594865f0242321d2be681d6Chris Lattner typedef StringMapEntry<ValueTy> MapEntryTy; 222f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 22334cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 224adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit StringMap(unsigned InitialSize) 22534cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 2266d31c0b79a06483d7a80209bba34226ccf9088bbMikhail Glushenkov 227a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner explicit StringMap(AllocatorTy A) 228a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 229a23650bc0161716aadba97e2e5f92eac7c11d80bChris Lattner 2303735573343614644ead7a8bae674c312db8b1eb1Argyrios Kyrtzidis StringMap(unsigned InitialSize, AllocatorTy A) 23147f39340211f537cf79610832194c1884d420d62Argyrios Kyrtzidis : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), 23247f39340211f537cf79610832194c1884d420d62Argyrios Kyrtzidis Allocator(A) {} 2333735573343614644ead7a8bae674c312db8b1eb1Argyrios Kyrtzidis 234f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List) 235de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) { 236f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (const auto &P : List) { 237f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar insert(P); 238f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 239f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 240f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 241dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines StringMap(StringMap &&RHS) 242dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {} 243dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 244dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines StringMap &operator=(StringMap RHS) { 245dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines StringMapImpl::swap(RHS); 246dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::swap(Allocator, RHS.Allocator); 247dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return *this; 2484715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner } 2494715f6395ef152fd92c9b74d5f3e62e2cff29d27Chris Lattner 250de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StringMap(const StringMap &RHS) : 251de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), 252de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Allocator(RHS.Allocator) { 253de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (RHS.empty()) 254de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return; 255de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 256de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Allocate TheTable of the same size as RHS's TheTable, and set the 257de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // sentinel appropriately (and NumBuckets). 258de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar init(RHS.NumBuckets); 259de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1), 260de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1); 261de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 262de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NumItems = RHS.NumItems; 263de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NumTombstones = RHS.NumTombstones; 264de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 265de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StringMapEntryBase *Bucket = RHS.TheTable[I]; 266de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Bucket || Bucket == getTombstoneVal()) { 267de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TheTable[I] = Bucket; 268de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 269de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 270de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 271de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TheTable[I] = MapEntryTy::Create( 272de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator, 273de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar static_cast<MapEntryTy *>(Bucket)->getValue()); 274de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar HashTable[I] = RHSHashTable[I]; 275de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 276de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 277de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Note that here we've copied everything from the RHS into this object, 278de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // tombstones included. We could, instead, have re-probed for each key to 279de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // instantiate this new object without any tombstone buckets. The 280de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // assumption here is that items are rarely deleted from most StringMaps, 281de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // and so tombstones are rare, so the cost of re-probing for all inputs is 282de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // not worthwhile. 283de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 284dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 285dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AllocatorTy &getAllocator() { return Allocator; } 286dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const AllocatorTy &getAllocator() const { return Allocator; } 28723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 288713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef const char* key_type; 289713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef ValueTy mapped_type; 290713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef StringMapEntry<ValueTy> value_type; 291713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov typedef size_t size_type; 292713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 2936ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapConstIterator<ValueTy> const_iterator; 2946ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapIterator<ValueTy> iterator; 29575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 296794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator begin() { 297794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable, NumBuckets == 0); 298794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 299794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator end() { 300794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable+NumBuckets, true); 301794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 302794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator begin() const { 303794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable, NumBuckets == 0); 304794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 305794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator end() const { 306794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable+NumBuckets, true); 307794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 30875fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 3092928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar iterator find(StringRef Key) { 3106316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 311b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 31285c07ce0481daa8f462943f621efdb7f21f6d3efBenjamin Kramer return iterator(TheTable+Bucket, true); 313b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 314b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 3152928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar const_iterator find(StringRef Key) const { 3166316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 317b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 31885c07ce0481daa8f462943f621efdb7f21f6d3efBenjamin Kramer return const_iterator(TheTable+Bucket, true); 3196c1645ce7da8495c79e3d38bbf91ce77bf489c10Chris Lattner } 320713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 321745bf82ebac69b390911d5af0b1664fa7ff6410eEli Bendersky /// lookup - Return the entry for the specified key, or a default 322e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar /// constructed value if no such entry exists. 3232928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar ValueTy lookup(StringRef Key) const { 324e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar const_iterator it = find(Key); 325e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar if (it != end()) 326e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar return it->second; 327e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar return ValueTy(); 328e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar } 329e889d837a4d226280525b1eafe5a6317c594ebf3Daniel Dunbar 330de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Lookup the ValueTy for the \p Key, or create a default constructed value 331de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// if the key is not in the map. 33239ff10a293012fe6f2db682c5518e1be2c50ca67Chris Lattner ValueTy &operator[](StringRef Key) { 333de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return emplace_second(Key).first->second; 334ec3e5c8a39c3dae7457d0eb18f98685decb23fcdAnton Korobeynikov } 335713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 33636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// count - Return 1 if the element is in the map, 0 otherwise. 3372928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar size_type count(StringRef Key) const { 3386316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar return find(Key) == end() ? 0 : 1; 339ec3e5c8a39c3dae7457d0eb18f98685decb23fcdAnton Korobeynikov } 340713a13906aedef33669f5bc961140bd41e6241d2Anton Korobeynikov 34144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert - Insert the specified key/value pair into the map. If the key 34244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// already exists in the map, return false and ignore the request, otherwise 34344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert it and return true. 34444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner bool insert(MapEntryTy *KeyValue) { 3456316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 346c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *&Bucket = TheTable[BucketNo]; 347c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket && Bucket != getTombstoneVal()) 34844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return false; // Already exists in map. 34975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 350c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket == getTombstoneVal()) 35144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumTombstones; 352c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer Bucket = KeyValue; 35344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner ++NumItems; 35403ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen assert(NumItems + NumTombstones <= NumBuckets); 35575fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 356aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen RehashTable(); 35744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return true; 35844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 35975fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 360c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines /// insert - Inserts the specified key/value pair into the map if the key 361c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines /// isn't already in the map. The bool component of the returned pair is true 362c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines /// if and only if the insertion takes place, and the iterator component of 363c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines /// the pair points to the element with key equivalent to the key of the pair. 364c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) { 365de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return emplace_second(KV.first, std::move(KV.second)); 366de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 367de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 368de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Emplace a new element for the specified key into the map if the key isn't 369de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// already in the map. The bool component of the returned pair is true 370de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// if and only if the insertion takes place, and the iterator component of 371de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// the pair points to the element with key equivalent to the key of the pair. 372de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar template <typename... ArgsTy> 373de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::pair<iterator, bool> emplace_second(StringRef Key, ArgsTy &&... Args) { 374de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned BucketNo = LookupBucketFor(Key); 375c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines StringMapEntryBase *&Bucket = TheTable[BucketNo]; 376c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (Bucket && Bucket != getTombstoneVal()) 377c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return std::make_pair(iterator(TheTable + BucketNo, false), 378c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines false); // Already exists in map. 379c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 380c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (Bucket == getTombstoneVal()) 381c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines --NumTombstones; 382de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...); 383c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ++NumItems; 384c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(NumItems + NumTombstones <= NumBuckets); 385c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 386c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines BucketNo = RehashTable(BucketNo); 387c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return std::make_pair(iterator(TheTable + BucketNo, false), true); 388c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 389c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 390fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner // clear - Empties out the StringMap 391fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner void clear() { 392509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner if (empty()) return; 3938bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 394509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner // Zap all values, resetting the keys back to non-present (not tombstone), 395509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner // which is safe because we're removing all elements. 396c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 397c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *&Bucket = TheTable[I]; 398c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket && Bucket != getTombstoneVal()) { 399c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 400509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner } 401dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Bucket = nullptr; 402509e4f30e85355540dc3bf52629d2356cfd4c1bfChris Lattner } 4038bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 4048bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman NumItems = 0; 40503ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen NumTombstones = 0; 406fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner } 407fce6e546aab64602c41eeb83381b7617f97d0069Chris Lattner 40844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// remove - Remove the specified key/value pair from the map, but do not 40944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// erase it. This aborts if the key is not in the map. 41044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner void remove(MapEntryTy *KeyValue) { 41144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner RemoveKey(KeyValue); 41244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 41375fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 414c6402013c8767d5718d4c7ae5625969361182771Chris Lattner void erase(iterator I) { 415c6402013c8767d5718d4c7ae5625969361182771Chris Lattner MapEntryTy &V = *I; 416c6402013c8767d5718d4c7ae5625969361182771Chris Lattner remove(&V); 417c6402013c8767d5718d4c7ae5625969361182771Chris Lattner V.Destroy(Allocator); 41884701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman } 41984701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman 4202928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbar bool erase(StringRef Key) { 42184701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman iterator I = find(Key); 42284701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman if (I == end()) return false; 42384701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman erase(I); 42484701836bfb1889e2e26e361ebd5d29d972ab396Dan Gohman return true; 425c6402013c8767d5718d4c7ae5625969361182771Chris Lattner } 42675fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 427bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner ~StringMap() { 42836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Delete all the elements in the map, but don't reset the elements 42936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // to default values. This is a copy of clear(), but avoids unnecessary 43036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // work not required in the destructor. 43136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!empty()) { 43236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 43336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines StringMapEntryBase *Bucket = TheTable[I]; 43436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Bucket && Bucket != getTombstoneVal()) { 43536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 43636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 43736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 43836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 439d2f197da59a3c937c1809997907918c029f9f884Chris Lattner free(TheTable); 44023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 44123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 44275fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 443f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainartemplate <typename ValueTy> class StringMapConstIterator { 44444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattnerprotected: 445c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase **Ptr; 446f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 4476ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerpublic: 4489f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek typedef StringMapEntry<ValueTy> value_type; 4498bb5e9901346f448461289f2d0079ed6d534b571Misha Brukman 450dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines StringMapConstIterator() : Ptr(nullptr) { } 451284ffa3863bc58f18a3eb879e49e05fdbe792413Reid Kleckner 452c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer explicit StringMapConstIterator(StringMapEntryBase **Bucket, 453adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman bool NoAdvance = false) 454794a014809d810b7ee9a96be76774185561f0dccChris Lattner : Ptr(Bucket) { 455794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (!NoAdvance) AdvancePastEmptyBuckets(); 4566ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 45775fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4589f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek const value_type &operator*() const { 459c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return *static_cast<StringMapEntry<ValueTy>*>(*Ptr); 4606ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4619f1f00ab1b347953da0efb0e20352be5e0709276Ted Kremenek const value_type *operator->() const { 462c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return static_cast<StringMapEntry<ValueTy>*>(*Ptr); 4636ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 46475fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4656ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator==(const StringMapConstIterator &RHS) const { 4666ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr == RHS.Ptr; 4676ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4686ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator!=(const StringMapConstIterator &RHS) const { 4696ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr != RHS.Ptr; 4706ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 47175fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 472745bf82ebac69b390911d5af0b1664fa7ff6410eEli Bendersky inline StringMapConstIterator& operator++() { // Preincrement 4736ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 4746ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner AdvancePastEmptyBuckets(); 4756ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return *this; 4766ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4776ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator operator++(int) { // Postincrement 4786ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator tmp = *this; ++*this; return tmp; 4796ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 48075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikov 4816ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerprivate: 4826ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner void AdvancePastEmptyBuckets() { 483dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) 4846ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 4856ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4866ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 4876ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 4886ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnertemplate<typename ValueTy> 4896ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerclass StringMapIterator : public StringMapConstIterator<ValueTy> { 49075fb496fc6b1ef5301d7262f40a842a2385f3930Anton Korobeynikovpublic: 4919e8dbe0d2de41d9f993d07f438f5f967fdfd9974Reid Kleckner StringMapIterator() {} 492c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer explicit StringMapIterator(StringMapEntryBase **Bucket, 493ded2b0d0fb0d4fa09198e3d05da529d2c97214c3Dan Gohman bool NoAdvance = false) 494794a014809d810b7ee9a96be76774185561f0dccChris Lattner : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 4956ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4966ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> &operator*() const { 497c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 4986ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 4996ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> *operator->() const { 500c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 5016ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 5026ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 50323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 50423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 505463c4a1ae9af56b6a944b74f0898e17d9a3b52ebChris Lattner#endif 506