StringMap.h revision 1bcc79666dcdcc948b7b998f7f661c77c268a893
1bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner//===--- StringMap.h - String Hash table map interface ----------*- C++ -*-===// 223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// The LLVM Compiler Infrastructure 423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// This file was developed by Chris Lattner and is distributed under 623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// the University of Illinois Open Source 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 1723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner#include "llvm/Support/Allocator.h" 1823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner#include <cstring> 1923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 2023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnernamespace llvm { 216ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner template<typename ValueT> 226ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner class StringMapConstIterator; 236ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner template<typename ValueT> 246ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner class StringMapIterator; 256ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 2623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 27ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// StringMapEntryBase - Shared base class of StringMapEntry instances. 28ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerclass StringMapEntryBase { 29ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner unsigned StrLen; 30ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerpublic: 31ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner StringMapEntryBase(unsigned Len) : StrLen(Len) {} 32ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 33ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner unsigned getKeyLength() const { return StrLen; } 34ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner}; 35ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 36bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner/// StringMapImpl - This is the base class of StringMap that is shared among 3723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// all of its instantiations. 38bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerclass StringMapImpl { 396ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerpublic: 4023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// ItemBucket - The hash table consists of an array of these. If Item is 4123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// non-null, this is an extant entry, otherwise, it is a hole. 4223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner struct ItemBucket { 4323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// FullHashValue - This remembers the full hash value of the key for 4423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// easy scanning. 4523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned FullHashValue; 4623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 4723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// Item - This is a pointer to the actual item object. 48ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner StringMapEntryBase *Item; 4923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner }; 5023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 516ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerprotected: 5223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ItemBucket *TheTable; 5323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NumBuckets; 5423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NumItems; 5544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner unsigned NumTombstones; 5623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned ItemSize; 5723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerprotected: 58c6402013c8767d5718d4c7ae5625969361182771Chris Lattner StringMapImpl(unsigned itemSize) : ItemSize(itemSize) { 59c6402013c8767d5718d4c7ae5625969361182771Chris Lattner // Initialize the map with zero buckets to allocation. 60c6402013c8767d5718d4c7ae5625969361182771Chris Lattner TheTable = 0; 61c6402013c8767d5718d4c7ae5625969361182771Chris Lattner NumBuckets = 0; 62c6402013c8767d5718d4c7ae5625969361182771Chris Lattner NumItems = 0; 63c6402013c8767d5718d4c7ae5625969361182771Chris Lattner NumTombstones = 0; 64c6402013c8767d5718d4c7ae5625969361182771Chris Lattner } 65bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner StringMapImpl(unsigned InitSize, unsigned ItemSize); 6623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner void RehashTable(); 6723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 68a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner /// ShouldRehash - Return true if the table should be rehashed after a new 69a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner /// element was recently inserted. 70a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner bool ShouldRehash() const { 71a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner // If the hash table is now more than 3/4 full, or if fewer than 1/8 of 72a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 73a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner // grow the table. 74a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner return NumItems*4 > NumBuckets*3 || 75a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner NumBuckets-(NumItems+NumTombstones) < NumBuckets/8; 76a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner } 77a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner 7823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// LookupBucketFor - Look up the bucket that the specified string should end 7923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// up in. If it already exists as a key in the map, the Item pointer for the 8023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// specified bucket will be non-null. Otherwise, it will be null. In either 8123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// case, the FullHashValue field of the bucket will be set to the hash value 8223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// of the string. 8323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned LookupBucketFor(const char *KeyStart, const char *KeyEnd); 8423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 85b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// FindKey - Look up the bucket that contains the specified key. If it exists 86b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// in the map, return the bucket number of the key. Otherwise return -1. 87b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner /// This does not modify the map. 88b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner int FindKey(const char *KeyStart, const char *KeyEnd) const; 8944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 9044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 9144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// delete it. This aborts if the value isn't in the table. 9244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner void RemoveKey(StringMapEntryBase *V); 9344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 9444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// RemoveKey - Remove the StringMapEntry for the specified key from the 9544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// table, returning it. If the key is not in the table, this returns null. 9644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner StringMapEntryBase *RemoveKey(const char *KeyStart, const char *KeyEnd); 97794a014809d810b7ee9a96be76774185561f0dccChris Lattnerprivate: 98794a014809d810b7ee9a96be76774185561f0dccChris Lattner void init(unsigned Size); 9923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerpublic: 1006ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner static StringMapEntryBase *getTombstoneVal() { 1016ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return (StringMapEntryBase*)-1; 1026ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 1036ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 10423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned getNumBuckets() const { return NumBuckets; } 10523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned getNumItems() const { return NumItems; } 10623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 1076ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool empty() const { return NumItems == 0; } 1086ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner unsigned size() const { return NumItems; } 10923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 11023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 111ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// StringMapEntry - This is used to represent one value that is inserted into 112ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// a StringMap. It contains the Value itself and the key: the string length 113ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// and data. 114ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnertemplate<typename ValueTy> 115ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerclass StringMapEntry : public StringMapEntryBase { 116ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner ValueTy Val; 117ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattnerpublic: 118ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner StringMapEntry(unsigned StrLen) 119ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner : StringMapEntryBase(StrLen), Val() {} 120ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner StringMapEntry(unsigned StrLen, const ValueTy &V) 121ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner : StringMapEntryBase(StrLen), Val(V) {} 122ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 123ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner const ValueTy &getValue() const { return Val; } 124ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner ValueTy &getValue() { return Val; } 125ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 126ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner void setValue(const ValueTy &V) { Val = V; } 127ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 128ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// getKeyData - Return the start of the string data that is the key for this 129ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// value. The string data is always stored immediately after the 130ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner /// StringMapEntry object. 131ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 1329cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner 1339cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Create - Create a StringMapEntry for the specified key and default 1349cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// construct the value. 1359cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner template<typename AllocatorTy> 1369cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 1379cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner AllocatorTy &Allocator) { 1389cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner unsigned KeyLength = KeyEnd-KeyStart; 1399cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner 1409cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill 1419cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // in. Allocate a new item with space for the string at the end and a null 1429cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // terminator. 1439cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner unsigned AllocSize = sizeof(StringMapEntry)+KeyLength+1; 1449cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner 1459cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner#ifdef __GNUC__ 1469cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner unsigned Alignment = __alignof__(StringMapEntry); 1479cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner#else 1489cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // FIXME: ugly. 1499cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner unsigned Alignment = 8; 1509cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner#endif 1519cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner StringMapEntry *NewItem = 1529cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize, Alignment)); 1539cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner 1549cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Default construct the value. 1559cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner new (NewItem) StringMapEntry(KeyLength); 1569cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner 1579cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Copy the string information. 1589cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 1599cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner memcpy(StrBuffer, KeyStart, KeyLength); 1609cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 1619cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner return NewItem; 1629cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 1639cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner 1649cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Create - Create a StringMapEntry with normal malloc/free. 1659cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { 1669cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 1679cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner return Create(KeyStart, KeyEnd, A); 1689cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 1691bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner 1701bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner 1711bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner /// GetStringMapEntryFromValue - Given a value that is known to be embedded 1721bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner /// into a StringMapEntry, return the StringMapEntry itself. 1731bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { 1741bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner return *reinterpret_cast<StringMapEntry*>(reinterpret_cast<char*>(&V) - 1751bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner sizeof(StringMapEntryBase)); 1761bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner } 1771bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { 1781bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); 1791bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner } 1801bcc79666dcdcc948b7b998f7f661c77c268a893Chris Lattner 1819cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy - Destroy this StringMapEntry, releasing memory back to the 1829cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// specified allocator. 1839cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner template<typename AllocatorTy> 1849cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy(AllocatorTy &Allocator) { 1859cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner // Free memory referenced by the item. 1869cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner this->~StringMapEntry(); 1879cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner Allocator.Deallocate(this); 1889cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 1899cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner 1909cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner /// Destroy this object, releasing memory back to the malloc allocator. 1919cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner void Destroy() { 1929cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MallocAllocator A; 1939cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner Destroy(A); 1949cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner } 195ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner}; 196ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner 19723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 198bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner/// StringMap - This is an unconventional map that is specialized for handling 199ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner/// keys that are "strings", which are basically ranges of bytes. This does some 20023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// funky memory allocation and hashing things to make it extremely efficient, 20123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// storing the string data *after* the value in the map. 20223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnertemplate<typename ValueTy, typename AllocatorTy = MallocAllocator> 203bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerclass StringMap : public StringMapImpl { 20423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner AllocatorTy Allocator; 205ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner typedef StringMapEntry<ValueTy> MapEntryTy; 20623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerpublic: 207794a014809d810b7ee9a96be76774185561f0dccChris Lattner StringMap() : StringMapImpl(sizeof(MapEntryTy)) {} 208794a014809d810b7ee9a96be76774185561f0dccChris Lattner StringMap(unsigned InitialSize) 209bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner : StringMapImpl(InitialSize, sizeof(MapEntryTy)) {} 21023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 21123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner AllocatorTy &getAllocator() { return Allocator; } 21223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner const AllocatorTy &getAllocator() const { return Allocator; } 21323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 2146ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapConstIterator<ValueTy> const_iterator; 2156ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner typedef StringMapIterator<ValueTy> iterator; 2166ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 217794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator begin() { 218794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable, NumBuckets == 0); 219794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 220794a014809d810b7ee9a96be76774185561f0dccChris Lattner iterator end() { 221794a014809d810b7ee9a96be76774185561f0dccChris Lattner return iterator(TheTable+NumBuckets, true); 222794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 223794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator begin() const { 224794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable, NumBuckets == 0); 225794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 226794a014809d810b7ee9a96be76774185561f0dccChris Lattner const_iterator end() const { 227794a014809d810b7ee9a96be76774185561f0dccChris Lattner return const_iterator(TheTable+NumBuckets, true); 228794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 229b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 230b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner iterator find(const char *KeyStart, const char *KeyEnd) { 231b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner int Bucket = FindKey(KeyStart, KeyEnd); 232b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 233b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner return iterator(TheTable+Bucket); 234b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 235b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 236b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner const_iterator find(const char *KeyStart, const char *KeyEnd) const { 237b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner int Bucket = FindKey(KeyStart, KeyEnd); 238b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (Bucket == -1) return end(); 239b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner return const_iterator(TheTable+Bucket); 2406c1645ce7da8495c79e3d38bbf91ce77bf489c10Chris Lattner } 2416c1645ce7da8495c79e3d38bbf91ce77bf489c10Chris Lattner 24244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert - Insert the specified key/value pair into the map. If the key 24344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// already exists in the map, return false and ignore the request, otherwise 24444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// insert it and return true. 24544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner bool insert(MapEntryTy *KeyValue) { 24644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner unsigned BucketNo = 24744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner LookupBucketFor(KeyValue->getKeyData(), 24844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner KeyValue->getKeyData()+KeyValue->getKeyLength()); 24944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner ItemBucket &Bucket = TheTable[BucketNo]; 25044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (Bucket.Item && Bucket.Item != getTombstoneVal()) 25144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return false; // Already exists in map. 25244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 25344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (Bucket.Item == getTombstoneVal()) 25444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumTombstones; 25544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner Bucket.Item = KeyValue; 25644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner ++NumItems; 25744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 258a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner if (ShouldRehash()) 25944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner RehashTable(); 26044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return true; 26144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 26244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 26323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// GetOrCreateValue - Look up the specified key in the table. If a value 26423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// exists, return it. Otherwise, default construct a value, insert it, and 26523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner /// return. 266ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, 267ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner const char *KeyEnd) { 26823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd); 26923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ItemBucket &Bucket = TheTable[BucketNo]; 27044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (Bucket.Item && Bucket.Item != getTombstoneVal()) 271ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner return *static_cast<MapEntryTy*>(Bucket.Item); 27223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 2739cc2d3dce87c2f4666a5d6a97321d865ade930daChris Lattner MapEntryTy *NewItem = MapEntryTy::Create(KeyStart, KeyEnd, Allocator); 27444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 27544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (Bucket.Item == getTombstoneVal()) 27644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumTombstones; 27723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ++NumItems; 27823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 27923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Fill in the bucket for the hash table. The FullHashValue was already 28023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // filled in by LookupBucketFor. 28123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner Bucket.Item = NewItem; 28223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 283a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner if (ShouldRehash()) 28423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner RehashTable(); 28523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner return *NewItem; 28623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 28723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 28844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// remove - Remove the specified key/value pair from the map, but do not 28944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner /// erase it. This aborts if the key is not in the map. 29044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner void remove(MapEntryTy *KeyValue) { 29144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner RemoveKey(KeyValue); 29244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 29344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 294c6402013c8767d5718d4c7ae5625969361182771Chris Lattner void erase(iterator I) { 295c6402013c8767d5718d4c7ae5625969361182771Chris Lattner MapEntryTy &V = *I; 296c6402013c8767d5718d4c7ae5625969361182771Chris Lattner remove(&V); 297c6402013c8767d5718d4c7ae5625969361182771Chris Lattner V.Destroy(Allocator); 298c6402013c8767d5718d4c7ae5625969361182771Chris Lattner } 299c6402013c8767d5718d4c7ae5625969361182771Chris Lattner 300bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner ~StringMap() { 30123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { 302a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner if (I->Item && I->Item != getTombstoneVal()) 303a96b4ee7ff408f2fe23fa9b2788c1ed9cf87caf4Chris Lattner static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator); 30423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 305d2f197da59a3c937c1809997907918c029f9f884Chris Lattner free(TheTable); 30623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 307c6402013c8767d5718d4c7ae5625969361182771Chris Lattnerprivate: 308c6402013c8767d5718d4c7ae5625969361182771Chris Lattner StringMap(const StringMap &); // FIXME: Implement. 309c6402013c8767d5718d4c7ae5625969361182771Chris Lattner void operator=(const StringMap &); // FIXME: Implement. 31023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner}; 31123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 3126ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 3136ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnertemplate<typename ValueTy> 3146ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerclass StringMapConstIterator { 31544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattnerprotected: 3166ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapImpl::ItemBucket *Ptr; 3176ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerpublic: 318794a014809d810b7ee9a96be76774185561f0dccChris Lattner StringMapConstIterator(StringMapImpl::ItemBucket *Bucket, 319794a014809d810b7ee9a96be76774185561f0dccChris Lattner bool NoAdvance = false) 320794a014809d810b7ee9a96be76774185561f0dccChris Lattner : Ptr(Bucket) { 321794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (!NoAdvance) AdvancePastEmptyBuckets(); 3226ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 3236ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 3246ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner const StringMapEntry<ValueTy> &operator*() const { 3256ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return *static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 3266ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 3276ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner const StringMapEntry<ValueTy> *operator->() const { 3286ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 3296ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 3306ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 3316ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator==(const StringMapConstIterator &RHS) const { 3326ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr == RHS.Ptr; 3336ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 3346ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner bool operator!=(const StringMapConstIterator &RHS) const { 3356ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return Ptr != RHS.Ptr; 3366ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 3376ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 3386ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner inline StringMapConstIterator& operator++() { // Preincrement 3396ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 3406ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner AdvancePastEmptyBuckets(); 3416ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return *this; 3426ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 3436ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator operator++(int) { // Postincrement 3446ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapConstIterator tmp = *this; ++*this; return tmp; 3456ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 3466ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 3476ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerprivate: 3486ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner void AdvancePastEmptyBuckets() { 3496ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal()) 3506ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner ++Ptr; 3516ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 3526ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 3536ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 3546ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnertemplate<typename ValueTy> 3556ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerclass StringMapIterator : public StringMapConstIterator<ValueTy> { 3566ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattnerpublic: 357794a014809d810b7ee9a96be76774185561f0dccChris Lattner StringMapIterator(StringMapImpl::ItemBucket *Bucket, 358794a014809d810b7ee9a96be76774185561f0dccChris Lattner bool NoAdvance = false) 359794a014809d810b7ee9a96be76774185561f0dccChris Lattner : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 3606ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 3616ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> &operator*() const { 3626ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 3636ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 3646ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner StringMapEntry<ValueTy> *operator->() const { 3656ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner return static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 3666ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner } 3676ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner}; 3686ccadf6f7f196b6c27a0eb966a90b8c39812b780Chris Lattner 36923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 37023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 371463c4a1ae9af56b6a944b74f0898e17d9a3b52ebChris Lattner#endif 372463c4a1ae9af56b6a944b74f0898e17d9a3b52ebChris Lattner 373