StringMap.h revision a91cfa9cd09635a6d046e144d07e68d924ac0fbb
1//===--- StringMap.h - String Hash table map interface ----------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the StringMap class. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ADT_STRINGMAP_H 15#define LLVM_ADT_STRINGMAP_H 16 17#include "llvm/Support/Allocator.h" 18#include <cstring> 19 20namespace llvm { 21 template<typename ValueT> 22 class StringMapConstIterator; 23 template<typename ValueT> 24 class StringMapIterator; 25 template<typename ValueTy> 26 class StringMapEntry; 27 28/// StringMapEntryInitializer - This datatype can be partially specialized for 29/// various datatypes in a stringmap to allow them to be initialized when an 30/// entry is default constructed for the map. 31template<typename ValueTy> 32class StringMapEntryInitializer { 33public: 34 template <typename InitTy> 35 static void Initialize(StringMapEntry<ValueTy> &T, InitTy InitVal) { 36 } 37}; 38 39 40/// StringMapEntryBase - Shared base class of StringMapEntry instances. 41class StringMapEntryBase { 42 unsigned StrLen; 43public: 44 explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} 45 46 unsigned getKeyLength() const { return StrLen; } 47}; 48 49/// StringMapImpl - This is the base class of StringMap that is shared among 50/// all of its instantiations. 51class StringMapImpl { 52public: 53 /// ItemBucket - The hash table consists of an array of these. If Item is 54 /// non-null, this is an extant entry, otherwise, it is a hole. 55 struct ItemBucket { 56 /// FullHashValue - This remembers the full hash value of the key for 57 /// easy scanning. 58 unsigned FullHashValue; 59 60 /// Item - This is a pointer to the actual item object. 61 StringMapEntryBase *Item; 62 }; 63 64protected: 65 ItemBucket *TheTable; 66 unsigned NumBuckets; 67 unsigned NumItems; 68 unsigned NumTombstones; 69 unsigned ItemSize; 70protected: 71 explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) { 72 // Initialize the map with zero buckets to allocation. 73 TheTable = 0; 74 NumBuckets = 0; 75 NumItems = 0; 76 NumTombstones = 0; 77 } 78 StringMapImpl(unsigned InitSize, unsigned ItemSize); 79 void RehashTable(); 80 81 /// ShouldRehash - Return true if the table should be rehashed after a new 82 /// element was recently inserted. 83 bool ShouldRehash() const { 84 // If the hash table is now more than 3/4 full, or if fewer than 1/8 of 85 // the buckets are empty (meaning that many are filled with tombstones), 86 // grow the table. 87 return NumItems*4 > NumBuckets*3 || 88 NumBuckets-(NumItems+NumTombstones) < NumBuckets/8; 89 } 90 91 /// LookupBucketFor - Look up the bucket that the specified string should end 92 /// up in. If it already exists as a key in the map, the Item pointer for the 93 /// specified bucket will be non-null. Otherwise, it will be null. In either 94 /// case, the FullHashValue field of the bucket will be set to the hash value 95 /// of the string. 96 unsigned LookupBucketFor(const char *KeyStart, const char *KeyEnd); 97 98 /// FindKey - Look up the bucket that contains the specified key. If it exists 99 /// in the map, return the bucket number of the key. Otherwise return -1. 100 /// This does not modify the map. 101 int FindKey(const char *KeyStart, const char *KeyEnd) const; 102 103 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 104 /// delete it. This aborts if the value isn't in the table. 105 void RemoveKey(StringMapEntryBase *V); 106 107 /// RemoveKey - Remove the StringMapEntry for the specified key from the 108 /// table, returning it. If the key is not in the table, this returns null. 109 StringMapEntryBase *RemoveKey(const char *KeyStart, const char *KeyEnd); 110private: 111 void init(unsigned Size); 112public: 113 static StringMapEntryBase *getTombstoneVal() { 114 return (StringMapEntryBase*)-1; 115 } 116 117 unsigned getNumBuckets() const { return NumBuckets; } 118 unsigned getNumItems() const { return NumItems; } 119 120 bool empty() const { return NumItems == 0; } 121 unsigned size() const { return NumItems; } 122}; 123 124/// StringMapEntry - This is used to represent one value that is inserted into 125/// a StringMap. It contains the Value itself and the key: the string length 126/// and data. 127template<typename ValueTy> 128class StringMapEntry : public StringMapEntryBase { 129 ValueTy Val; 130public: 131 explicit StringMapEntry(unsigned StrLen) 132 : StringMapEntryBase(StrLen), Val() {} 133 StringMapEntry(unsigned StrLen, const ValueTy &V) 134 : StringMapEntryBase(StrLen), Val(V) {} 135 136 const ValueTy &getValue() const { return Val; } 137 ValueTy &getValue() { return Val; } 138 139 void setValue(const ValueTy &V) { Val = V; } 140 141 /// getKeyData - Return the start of the string data that is the key for this 142 /// value. The string data is always stored immediately after the 143 /// StringMapEntry object. 144 const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 145 146 /// Create - Create a StringMapEntry for the specified key and default 147 /// construct the value. 148 template<typename AllocatorTy, typename InitType> 149 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 150 AllocatorTy &Allocator, 151 InitType InitVal) { 152 unsigned KeyLength = KeyEnd-KeyStart; 153 154 // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill 155 // in. Allocate a new item with space for the string at the end and a null 156 // terminator. 157 158 unsigned AllocSize = sizeof(StringMapEntry)+KeyLength+1; 159 unsigned Alignment = alignof<StringMapEntry>(); 160 161 StringMapEntry *NewItem = 162 static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 163 164 // Default construct the value. 165 new (NewItem) StringMapEntry(KeyLength); 166 167 // Copy the string information. 168 char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 169 memcpy(StrBuffer, KeyStart, KeyLength); 170 StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 171 172 // Initialize the value if the client wants to. 173 StringMapEntryInitializer<ValueTy>::Initialize(*NewItem, InitVal); 174 return NewItem; 175 } 176 177 template<typename AllocatorTy> 178 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 179 AllocatorTy &Allocator) { 180 return Create(KeyStart, KeyEnd, Allocator, (void*)0); 181 } 182 183 184 /// Create - Create a StringMapEntry with normal malloc/free. 185 template<typename InitType> 186 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 187 InitType InitVal) { 188 MallocAllocator A; 189 return Create(KeyStart, KeyEnd, A, InitVal); 190 } 191 192 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { 193 return Create(KeyStart, KeyEnd, (void*)0); 194 } 195 196 /// GetStringMapEntryFromValue - Given a value that is known to be embedded 197 /// into a StringMapEntry, return the StringMapEntry itself. 198 static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { 199 StringMapEntry *EPtr = 0; 200 char *Ptr = reinterpret_cast<char*>(&V) - 201 (reinterpret_cast<char*>(&EPtr->Val) - 202 reinterpret_cast<char*>(EPtr)); 203 return *reinterpret_cast<StringMapEntry*>(Ptr); 204 } 205 static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { 206 return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); 207 } 208 209 /// Destroy - Destroy this StringMapEntry, releasing memory back to the 210 /// specified allocator. 211 template<typename AllocatorTy> 212 void Destroy(AllocatorTy &Allocator) { 213 // Free memory referenced by the item. 214 this->~StringMapEntry(); 215 Allocator.Deallocate(this); 216 } 217 218 /// Destroy this object, releasing memory back to the malloc allocator. 219 void Destroy() { 220 MallocAllocator A; 221 Destroy(A); 222 } 223}; 224 225 226/// StringMap - This is an unconventional map that is specialized for handling 227/// keys that are "strings", which are basically ranges of bytes. This does some 228/// funky memory allocation and hashing things to make it extremely efficient, 229/// storing the string data *after* the value in the map. 230template<typename ValueTy, typename AllocatorTy = MallocAllocator> 231class StringMap : public StringMapImpl { 232 AllocatorTy Allocator; 233 typedef StringMapEntry<ValueTy> MapEntryTy; 234public: 235 StringMap() : StringMapImpl(sizeof(MapEntryTy)) {} 236 explicit StringMap(unsigned InitialSize) 237 : StringMapImpl(InitialSize, sizeof(MapEntryTy)) {} 238 239 AllocatorTy &getAllocator() { return Allocator; } 240 const AllocatorTy &getAllocator() const { return Allocator; } 241 242 typedef StringMapConstIterator<ValueTy> const_iterator; 243 typedef StringMapIterator<ValueTy> iterator; 244 245 iterator begin() { 246 return iterator(TheTable, NumBuckets == 0); 247 } 248 iterator end() { 249 return iterator(TheTable+NumBuckets, true); 250 } 251 const_iterator begin() const { 252 return const_iterator(TheTable, NumBuckets == 0); 253 } 254 const_iterator end() const { 255 return const_iterator(TheTable+NumBuckets, true); 256 } 257 258 iterator find(const char *KeyStart, const char *KeyEnd) { 259 int Bucket = FindKey(KeyStart, KeyEnd); 260 if (Bucket == -1) return end(); 261 return iterator(TheTable+Bucket); 262 } 263 264 const_iterator find(const char *KeyStart, const char *KeyEnd) const { 265 int Bucket = FindKey(KeyStart, KeyEnd); 266 if (Bucket == -1) return end(); 267 return const_iterator(TheTable+Bucket); 268 } 269 270 /// insert - Insert the specified key/value pair into the map. If the key 271 /// already exists in the map, return false and ignore the request, otherwise 272 /// insert it and return true. 273 bool insert(MapEntryTy *KeyValue) { 274 unsigned BucketNo = 275 LookupBucketFor(KeyValue->getKeyData(), 276 KeyValue->getKeyData()+KeyValue->getKeyLength()); 277 ItemBucket &Bucket = TheTable[BucketNo]; 278 if (Bucket.Item && Bucket.Item != getTombstoneVal()) 279 return false; // Already exists in map. 280 281 if (Bucket.Item == getTombstoneVal()) 282 --NumTombstones; 283 Bucket.Item = KeyValue; 284 ++NumItems; 285 286 if (ShouldRehash()) 287 RehashTable(); 288 return true; 289 } 290 291 /// GetOrCreateValue - Look up the specified key in the table. If a value 292 /// exists, return it. Otherwise, default construct a value, insert it, and 293 /// return. 294 template <typename InitTy> 295 StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, 296 const char *KeyEnd, 297 InitTy Val) { 298 unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd); 299 ItemBucket &Bucket = TheTable[BucketNo]; 300 if (Bucket.Item && Bucket.Item != getTombstoneVal()) 301 return *static_cast<MapEntryTy*>(Bucket.Item); 302 303 MapEntryTy *NewItem = MapEntryTy::Create(KeyStart, KeyEnd, Allocator, Val); 304 305 if (Bucket.Item == getTombstoneVal()) 306 --NumTombstones; 307 ++NumItems; 308 309 // Fill in the bucket for the hash table. The FullHashValue was already 310 // filled in by LookupBucketFor. 311 Bucket.Item = NewItem; 312 313 if (ShouldRehash()) 314 RehashTable(); 315 return *NewItem; 316 } 317 318 StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, 319 const char *KeyEnd) { 320 return GetOrCreateValue(KeyStart, KeyEnd, (void*)0); 321 } 322 323 /// remove - Remove the specified key/value pair from the map, but do not 324 /// erase it. This aborts if the key is not in the map. 325 void remove(MapEntryTy *KeyValue) { 326 RemoveKey(KeyValue); 327 } 328 329 void erase(iterator I) { 330 MapEntryTy &V = *I; 331 remove(&V); 332 V.Destroy(Allocator); 333 } 334 335 ~StringMap() { 336 for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { 337 if (I->Item && I->Item != getTombstoneVal()) 338 static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator); 339 } 340 free(TheTable); 341 } 342private: 343 StringMap(const StringMap &); // FIXME: Implement. 344 void operator=(const StringMap &); // FIXME: Implement. 345}; 346 347 348template<typename ValueTy> 349class StringMapConstIterator { 350protected: 351 StringMapImpl::ItemBucket *Ptr; 352public: 353 explicit StringMapConstIterator(StringMapImpl::ItemBucket *Bucket, 354 bool NoAdvance = false) 355 : Ptr(Bucket) { 356 if (!NoAdvance) AdvancePastEmptyBuckets(); 357 } 358 359 const StringMapEntry<ValueTy> &operator*() const { 360 return *static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 361 } 362 const StringMapEntry<ValueTy> *operator->() const { 363 return static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 364 } 365 366 bool operator==(const StringMapConstIterator &RHS) const { 367 return Ptr == RHS.Ptr; 368 } 369 bool operator!=(const StringMapConstIterator &RHS) const { 370 return Ptr != RHS.Ptr; 371 } 372 373 inline StringMapConstIterator& operator++() { // Preincrement 374 ++Ptr; 375 AdvancePastEmptyBuckets(); 376 return *this; 377 } 378 StringMapConstIterator operator++(int) { // Postincrement 379 StringMapConstIterator tmp = *this; ++*this; return tmp; 380 } 381 382private: 383 void AdvancePastEmptyBuckets() { 384 while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal()) 385 ++Ptr; 386 } 387}; 388 389template<typename ValueTy> 390class StringMapIterator : public StringMapConstIterator<ValueTy> { 391public: 392 explicit StringMapIterator(StringMapImpl::ItemBucket *Bucket, 393 bool NoAdvance = false) 394 : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 395 } 396 StringMapEntry<ValueTy> &operator*() const { 397 return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 398 } 399 StringMapEntry<ValueTy> *operator->() const { 400 return static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 401 } 402}; 403 404} 405 406#endif 407