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