StringMap.h revision ee182422ff0b638b17c5ee802c19b8680107c2bb
1//===--- CStringMap.h - CString Hash table map interface --------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Chris Lattner and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the CStringMap class. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ADT_CSTRINGMAP_H 15#define LLVM_ADT_CSTRINGMAP_H 16 17#include "llvm/Support/Allocator.h" 18#include <cstring> 19 20namespace llvm { 21 22/// StringMapEntryBase - Shared base class of StringMapEntry instances. 23class StringMapEntryBase { 24 unsigned StrLen; 25public: 26 StringMapEntryBase(unsigned Len) : StrLen(Len) {} 27 28 unsigned getKeyLength() const { return StrLen; } 29}; 30 31/// CStringMapVisitor - Subclasses of this class may be implemented to walk all 32/// of the items in a CStringMap. 33class CStringMapVisitor { 34public: 35 virtual ~CStringMapVisitor(); 36 virtual void Visit(const char *Key, StringMapEntryBase *Value) const = 0; 37}; 38 39/// CStringMapImpl - This is the base class of CStringMap that is shared among 40/// all of its instantiations. 41class CStringMapImpl { 42protected: 43 /// ItemBucket - The hash table consists of an array of these. If Item is 44 /// non-null, this is an extant entry, otherwise, it is a hole. 45 struct ItemBucket { 46 /// FullHashValue - This remembers the full hash value of the key for 47 /// easy scanning. 48 unsigned FullHashValue; 49 50 /// Item - This is a pointer to the actual item object. 51 StringMapEntryBase *Item; 52 }; 53 54 ItemBucket *TheTable; 55 unsigned NumBuckets; 56 unsigned NumItems; 57 unsigned ItemSize; 58protected: 59 CStringMapImpl(unsigned InitSize, unsigned ItemSize); 60 void RehashTable(); 61 62 /// LookupBucketFor - Look up the bucket that the specified string should end 63 /// up in. If it already exists as a key in the map, the Item pointer for the 64 /// specified bucket will be non-null. Otherwise, it will be null. In either 65 /// case, the FullHashValue field of the bucket will be set to the hash value 66 /// of the string. 67 unsigned LookupBucketFor(const char *KeyStart, const char *KeyEnd); 68 69public: 70 unsigned getNumBuckets() const { return NumBuckets; } 71 unsigned getNumItems() const { return NumItems; } 72 73 void VisitEntries(const CStringMapVisitor &Visitor) const; 74}; 75 76/// StringMapEntry - This is used to represent one value that is inserted into 77/// a StringMap. It contains the Value itself and the key: the string length 78/// and data. 79template<typename ValueTy> 80class StringMapEntry : public StringMapEntryBase { 81 ValueTy Val; 82public: 83 StringMapEntry(unsigned StrLen) 84 : StringMapEntryBase(StrLen), Val() {} 85 StringMapEntry(unsigned StrLen, const ValueTy &V) 86 : StringMapEntryBase(StrLen), Val(V) {} 87 88 const ValueTy &getValue() const { return Val; } 89 ValueTy &getValue() { return Val; } 90 91 void setValue(const ValueTy &V) { Val = V; } 92 93 /// getKeyData - Return the start of the string data that is the key for this 94 /// value. The string data is always stored immediately after the 95 /// StringMapEntry object. 96 const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 97}; 98 99 100/// CStringMap - This is an unconventional map that is specialized for handling 101/// keys that are "strings", which are basically ranges of bytes. This does some 102/// funky memory allocation and hashing things to make it extremely efficient, 103/// storing the string data *after* the value in the map. 104template<typename ValueTy, typename AllocatorTy = MallocAllocator> 105class CStringMap : public CStringMapImpl { 106 AllocatorTy Allocator; 107 typedef StringMapEntry<ValueTy> MapEntryTy; 108public: 109 CStringMap(unsigned InitialSize = 0) 110 : CStringMapImpl(InitialSize, sizeof(MapEntryTy)) {} 111 112 AllocatorTy &getAllocator() { return Allocator; } 113 const AllocatorTy &getAllocator() const { return Allocator; } 114 115 /// FindValue - Look up the specified key in the map. If it exists, return a 116 /// pointer to the element, otherwise return null. 117 MapEntryTy *FindValue(const char *KeyStart, const char *KeyEnd) { 118 unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd); 119 return static_cast<MapEntryTy*>(TheTable[BucketNo].Item); 120 } 121 122 /// GetOrCreateValue - Look up the specified key in the table. If a value 123 /// exists, return it. Otherwise, default construct a value, insert it, and 124 /// return. 125 StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, 126 const char *KeyEnd) { 127 unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd); 128 ItemBucket &Bucket = TheTable[BucketNo]; 129 if (Bucket.Item) 130 return *static_cast<MapEntryTy*>(Bucket.Item); 131 132 unsigned KeyLength = KeyEnd-KeyStart; 133 134 // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill 135 // in. Allocate a new item with space for the string at the end and a null 136 // terminator. 137 unsigned AllocSize = sizeof(MapEntryTy)+KeyLength+1; 138 139#ifdef __GNUC__ 140 unsigned Alignment = __alignof__(MapEntryTy); 141#else 142 // FIXME: ugly. 143 unsigned Alignment = 8; 144#endif 145 MapEntryTy *NewItem = 146 static_cast<MapEntryTy*>(Allocator.Allocate(AllocSize, Alignment)); 147 148 // Default construct the value. 149 new (NewItem) MapEntryTy(KeyLength); 150 ++NumItems; 151 152 // Copy the string information. 153 char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 154 memcpy(StrBuffer, KeyStart, KeyLength); 155 StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 156 157 // Fill in the bucket for the hash table. The FullHashValue was already 158 // filled in by LookupBucketFor. 159 Bucket.Item = NewItem; 160 161 // If the hash table is now more than 3/4 full, rehash into a larger table. 162 if (NumItems > NumBuckets*3/4) 163 RehashTable(); 164 return *NewItem; 165 } 166 167 ~CStringMap() { 168 for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { 169 if (MapEntryTy *Id = static_cast<MapEntryTy*>(I->Item)) { 170 // Free memory referenced by the item. 171 Id->~MapEntryTy(); 172 Allocator.Deallocate(Id); 173 } 174 } 175 delete [] TheTable; 176 } 177}; 178 179} 180 181#endif 182 183