1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===--- StringMap.h - String Hash table map interface ----------*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file defines the StringMap class. 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_ADT_STRINGMAP_H 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_ADT_STRINGMAP_H 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/StringRef.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Allocator.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <cstring> 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename ValueT> 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class StringMapConstIterator; 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename ValueT> 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class StringMapIterator; 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename ValueTy> 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class StringMapEntry; 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// StringMapEntryInitializer - This datatype can be partially specialized for 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// various datatypes in a stringmap to allow them to be initialized when an 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// entry is default constructed for the map. 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename ValueTy> 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass StringMapEntryInitializer { 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template <typename InitTy> 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static void Initialize(StringMapEntry<ValueTy> &T, InitTy InitVal) { 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman T.second = InitVal; 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// StringMapEntryBase - Shared base class of StringMapEntry instances. 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass StringMapEntryBase { 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned StrLen; 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getKeyLength() const { return StrLen; } 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// StringMapImpl - This is the base class of StringMap that is shared among 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// all of its instantiations. 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass StringMapImpl { 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// ItemBucket - The hash table consists of an array of these. If Item is 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// non-null, this is an extant entry, otherwise, it is a hole. 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct ItemBucket { 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// FullHashValue - This remembers the full hash value of the key for 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// easy scanning. 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned FullHashValue; 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Item - This is a pointer to the actual item object. 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntryBase *Item; 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprotected: 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ItemBucket *TheTable; 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumBuckets; 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumItems; 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumTombstones; 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned ItemSize; 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprotected: 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) { 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Initialize the map with zero buckets to allocation. 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheTable = 0; 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumBuckets = 0; 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumItems = 0; 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumTombstones = 0; 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapImpl(unsigned InitSize, unsigned ItemSize); 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void RehashTable(); 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// LookupBucketFor - Look up the bucket that the specified string should end 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// up in. If it already exists as a key in the map, the Item pointer for the 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// specified bucket will be non-null. Otherwise, it will be null. In either 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// case, the FullHashValue field of the bucket will be set to the hash value 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// of the string. 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned LookupBucketFor(StringRef Key); 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// FindKey - Look up the bucket that contains the specified key. If it exists 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// in the map, return the bucket number of the key. Otherwise return -1. 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// This does not modify the map. 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int FindKey(StringRef Key) const; 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// delete it. This aborts if the value isn't in the table. 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void RemoveKey(StringMapEntryBase *V); 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// RemoveKey - Remove the StringMapEntry for the specified key from the 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// table, returning it. If the key is not in the table, this returns null. 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntryBase *RemoveKey(StringRef Key); 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprivate: 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void init(unsigned Size); 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static StringMapEntryBase *getTombstoneVal() { 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return (StringMapEntryBase*)-1; 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getNumBuckets() const { return NumBuckets; } 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getNumItems() const { return NumItems; } 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool empty() const { return NumItems == 0; } 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned size() const { return NumItems; } 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// StringMapEntry - This is used to represent one value that is inserted into 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// a StringMap. It contains the Value itself and the key: the string length 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// and data. 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename ValueTy> 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass StringMapEntry : public StringMapEntryBase { 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueTy second; 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit StringMapEntry(unsigned strLen) 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : StringMapEntryBase(strLen), second() {} 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntry(unsigned strLen, const ValueTy &V) 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : StringMapEntryBase(strLen), second(V) {} 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman StringRef getKey() const { 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return StringRef(getKeyData(), getKeyLength()); 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const ValueTy &getValue() const { return second; } 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueTy &getValue() { return second; } 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setValue(const ValueTy &V) { second = V; } 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getKeyData - Return the start of the string data that is the key for this 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// value. The string data is always stored immediately after the 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// StringMapEntry object. 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Create - Create a StringMapEntry for the specified key and default 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// construct the value. 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename AllocatorTy, typename InitType> 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllocatorTy &Allocator, 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InitType InitVal) { 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned KeyLength = static_cast<unsigned>(KeyEnd-KeyStart); 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // in. Allocate a new item with space for the string at the end and a null 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // terminator. 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman KeyLength+1; 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Alignment = alignOf<StringMapEntry>(); 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntry *NewItem = 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Default construct the value. 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new (NewItem) StringMapEntry(KeyLength); 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Copy the string information. 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman memcpy(StrBuffer, KeyStart, KeyLength); 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Initialize the value if the client wants to. 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntryInitializer<ValueTy>::Initialize(*NewItem, InitVal); 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NewItem; 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename AllocatorTy> 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllocatorTy &Allocator) { 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Create(KeyStart, KeyEnd, Allocator, 0); 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Create - Create a StringMapEntry with normal malloc/free. 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename InitType> 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InitType InitVal) { 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MallocAllocator A; 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Create(KeyStart, KeyEnd, A, InitVal); 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Create(KeyStart, KeyEnd, ValueTy()); 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// GetStringMapEntryFromValue - Given a value that is known to be embedded 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// into a StringMapEntry, return the StringMapEntry itself. 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntry *EPtr = 0; 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman char *Ptr = reinterpret_cast<char*>(&V) - 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (reinterpret_cast<char*>(&EPtr->second) - 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman reinterpret_cast<char*>(EPtr)); 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *reinterpret_cast<StringMapEntry*>(Ptr); 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 20819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// into a StringMapEntry, return the StringMapEntry itself. 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>); 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *reinterpret_cast<StringMapEntry*>(Ptr); 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Destroy - Destroy this StringMapEntry, releasing memory back to the 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// specified allocator. 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename AllocatorTy> 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void Destroy(AllocatorTy &Allocator) { 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Free memory referenced by the item. 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman this->~StringMapEntry(); 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Allocator.Deallocate(this); 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Destroy this object, releasing memory back to the malloc allocator. 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void Destroy() { 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MallocAllocator A; 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Destroy(A); 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// StringMap - This is an unconventional map that is specialized for handling 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// keys that are "strings", which are basically ranges of bytes. This does some 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// funky memory allocation and hashing things to make it extremely efficient, 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// storing the string data *after* the value in the map. 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename ValueTy, typename AllocatorTy = MallocAllocator> 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass StringMap : public StringMapImpl { 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllocatorTy Allocator; 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef StringMapEntry<ValueTy> MapEntryTy; 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit StringMap(unsigned InitialSize) 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 24619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit StringMap(AllocatorTy A) 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit StringMap(const StringMap &RHS) 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) { 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(RHS.empty() && 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Copy ctor from non-empty stringmap not implemented yet!"); 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)RHS; 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void operator=(const StringMap &RHS) { 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(RHS.empty() && 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "assignment from non-empty stringmap not implemented yet!"); 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)RHS; 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman clear(); 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 26319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AllocatorRefTy getAllocator() { return Allocator; } 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AllocatorCRefTy getAllocator() const { return Allocator; } 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef const char* key_type; 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef ValueTy mapped_type; 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef StringMapEntry<ValueTy> value_type; 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef size_t size_type; 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef StringMapConstIterator<ValueTy> const_iterator; 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef StringMapIterator<ValueTy> iterator; 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator begin() { 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return iterator(TheTable, NumBuckets == 0); 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator end() { 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return iterator(TheTable+NumBuckets, true); 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator begin() const { 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return const_iterator(TheTable, NumBuckets == 0); 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator end() const { 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return const_iterator(TheTable+NumBuckets, true); 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator find(StringRef Key) { 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int Bucket = FindKey(Key); 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Bucket == -1) return end(); 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return iterator(TheTable+Bucket); 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator find(StringRef Key) const { 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int Bucket = FindKey(Key); 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Bucket == -1) return end(); 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return const_iterator(TheTable+Bucket); 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// lookup - Return the entry for the specified key, or a default 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// constructed value if no such entry exists. 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueTy lookup(StringRef Key) const { 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator it = find(Key); 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (it != end()) 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return it->second; 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return ValueTy(); 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValueTy &operator[](StringRef Key) { 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return GetOrCreateValue(Key).getValue(); 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman size_type count(StringRef Key) const { 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return find(Key) == end() ? 0 : 1; 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// insert - Insert the specified key/value pair into the map. If the key 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// already exists in the map, return false and ignore the request, otherwise 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// insert it and return true. 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool insert(MapEntryTy *KeyValue) { 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ItemBucket &Bucket = TheTable[BucketNo]; 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Bucket.Item && Bucket.Item != getTombstoneVal()) 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; // Already exists in map. 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Bucket.Item == getTombstoneVal()) 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumTombstones; 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Bucket.Item = KeyValue; 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumItems; 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(NumItems + NumTombstones <= NumBuckets); 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RehashTable(); 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // clear - Empties out the StringMap 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void clear() { 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (empty()) return; 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Zap all values, resetting the keys back to non-present (not tombstone), 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // which is safe because we're removing all elements. 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->Item && I->Item != getTombstoneVal()) { 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator); 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->Item = 0; 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumItems = 0; 35119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NumTombstones = 0; 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 353894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// GetOrCreateValue - Look up the specified key in the table. If a value 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// exists, return it. Otherwise, default construct a value, insert it, and 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// return. 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template <typename InitTy> 35819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned BucketNo = LookupBucketFor(Key); 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ItemBucket &Bucket = TheTable[BucketNo]; 361894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Bucket.Item && Bucket.Item != getTombstoneVal()) 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *static_cast<MapEntryTy*>(Bucket.Item); 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MapEntryTy *NewItem = 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Bucket.Item == getTombstoneVal()) 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumTombstones; 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumItems; 37019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(NumItems + NumTombstones <= NumBuckets); 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Fill in the bucket for the hash table. The FullHashValue was already 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // filled in by LookupBucketFor. 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Bucket.Item = NewItem; 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 37619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RehashTable(); 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *NewItem; 378894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 38019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MapEntryTy &GetOrCreateValue(StringRef Key) { 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return GetOrCreateValue(Key, ValueTy()); 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// remove - Remove the specified key/value pair from the map, but do not 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// erase it. This aborts if the key is not in the map. 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void remove(MapEntryTy *KeyValue) { 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemoveKey(KeyValue); 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void erase(iterator I) { 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MapEntryTy &V = *I; 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman remove(&V); 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V.Destroy(Allocator); 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 395894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool erase(StringRef Key) { 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator I = find(Key); 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I == end()) return false; 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman erase(I); 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 403894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ~StringMap() { 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman clear(); 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman free(TheTable); 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename ValueTy> 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass StringMapConstIterator { 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprotected: 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapImpl::ItemBucket *Ptr; 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef StringMapEntry<ValueTy> value_type; 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit StringMapConstIterator(StringMapImpl::ItemBucket *Bucket, 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool NoAdvance = false) 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : Ptr(Bucket) { 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!NoAdvance) AdvancePastEmptyBuckets(); 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 422894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const value_type &operator*() const { 424894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const value_type *operator->() const { 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator==(const StringMapConstIterator &RHS) const { 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Ptr == RHS.Ptr; 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator!=(const StringMapConstIterator &RHS) const { 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Ptr != RHS.Ptr; 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline StringMapConstIterator& operator++() { // Preincrement 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Ptr; 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AdvancePastEmptyBuckets(); 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *this; 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapConstIterator operator++(int) { // Postincrement 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapConstIterator tmp = *this; ++*this; return tmp; 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprivate: 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void AdvancePastEmptyBuckets() { 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal()) 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Ptr; 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename ValueTy> 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass StringMapIterator : public StringMapConstIterator<ValueTy> { 455894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 456894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit StringMapIterator(StringMapImpl::ItemBucket *Bucket, 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool NoAdvance = false) 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntry<ValueTy> &operator*() const { 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 462894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 463894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntry<ValueTy> *operator->() const { 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 471