StringMap.h revision 6d31c0b79a06483d7a80209bba34226ccf9088bb
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 245template <typename T> struct ReferenceAdder { typedef T& result; }; 246template <typename T> struct ReferenceAdder<T&> { typedef T result; }; 247 248/// StringMap - This is an unconventional map that is specialized for handling 249/// keys that are "strings", which are basically ranges of bytes. This does some 250/// funky memory allocation and hashing things to make it extremely efficient, 251/// storing the string data *after* the value in the map. 252template<typename ValueTy, typename AllocatorTy = MallocAllocator> 253class StringMap : public StringMapImpl { 254 AllocatorTy Allocator; 255 typedef StringMapEntry<ValueTy> MapEntryTy; 256public: 257 StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 258 explicit StringMap(unsigned InitialSize) 259 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 260 261 explicit StringMap(AllocatorTy A) 262 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 263 264 explicit StringMap(const StringMap &RHS) 265 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) { 266 assert(RHS.empty() && 267 "Copy ctor from non-empty stringmap not implemented yet!"); 268 } 269 void operator=(const StringMap &RHS) { 270 assert(RHS.empty() && 271 "assignment from non-empty stringmap not implemented yet!"); 272 clear(); 273 } 274 275 typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; 276 typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; 277 AllocatorRefTy getAllocator() { return Allocator; } 278 AllocatorCRefTy getAllocator() const { return Allocator; } 279 280 typedef const char* key_type; 281 typedef ValueTy mapped_type; 282 typedef StringMapEntry<ValueTy> value_type; 283 typedef size_t size_type; 284 285 typedef StringMapConstIterator<ValueTy> const_iterator; 286 typedef StringMapIterator<ValueTy> iterator; 287 288 iterator begin() { 289 return iterator(TheTable, NumBuckets == 0); 290 } 291 iterator end() { 292 return iterator(TheTable+NumBuckets, true); 293 } 294 const_iterator begin() const { 295 return const_iterator(TheTable, NumBuckets == 0); 296 } 297 const_iterator end() const { 298 return const_iterator(TheTable+NumBuckets, true); 299 } 300 301 iterator find(StringRef Key) { 302 int Bucket = FindKey(Key); 303 if (Bucket == -1) return end(); 304 return iterator(TheTable+Bucket); 305 } 306 307 const_iterator find(StringRef Key) const { 308 int Bucket = FindKey(Key); 309 if (Bucket == -1) return end(); 310 return const_iterator(TheTable+Bucket); 311 } 312 313 /// lookup - Return the entry for the specified key, or a default 314 /// constructed value if no such entry exists. 315 ValueTy lookup(StringRef Key) const { 316 const_iterator it = find(Key); 317 if (it != end()) 318 return it->second; 319 return ValueTy(); 320 } 321 322 ValueTy& operator[](StringRef Key) { 323 return GetOrCreateValue(Key).getValue(); 324 } 325 326 size_type count(StringRef Key) const { 327 return find(Key) == end() ? 0 : 1; 328 } 329 330 /// insert - Insert the specified key/value pair into the map. If the key 331 /// already exists in the map, return false and ignore the request, otherwise 332 /// insert it and return true. 333 bool insert(MapEntryTy *KeyValue) { 334 unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 335 ItemBucket &Bucket = TheTable[BucketNo]; 336 if (Bucket.Item && Bucket.Item != getTombstoneVal()) 337 return false; // Already exists in map. 338 339 if (Bucket.Item == getTombstoneVal()) 340 --NumTombstones; 341 Bucket.Item = KeyValue; 342 ++NumItems; 343 344 if (ShouldRehash()) 345 RehashTable(); 346 return true; 347 } 348 349 // clear - Empties out the StringMap 350 void clear() { 351 if (empty()) return; 352 353 // Zap all values, resetting the keys back to non-present (not tombstone), 354 // which is safe because we're removing all elements. 355 for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { 356 if (I->Item && I->Item != getTombstoneVal()) { 357 static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator); 358 I->Item = 0; 359 } 360 } 361 362 NumItems = 0; 363 } 364 365 /// GetOrCreateValue - Look up the specified key in the table. If a value 366 /// exists, return it. Otherwise, default construct a value, insert it, and 367 /// return. 368 template <typename InitTy> 369 StringMapEntry<ValueTy> &GetOrCreateValue(StringRef Key, 370 InitTy Val) { 371 unsigned BucketNo = LookupBucketFor(Key); 372 ItemBucket &Bucket = TheTable[BucketNo]; 373 if (Bucket.Item && Bucket.Item != getTombstoneVal()) 374 return *static_cast<MapEntryTy*>(Bucket.Item); 375 376 MapEntryTy *NewItem = 377 MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); 378 379 if (Bucket.Item == getTombstoneVal()) 380 --NumTombstones; 381 ++NumItems; 382 383 // Fill in the bucket for the hash table. The FullHashValue was already 384 // filled in by LookupBucketFor. 385 Bucket.Item = NewItem; 386 387 if (ShouldRehash()) 388 RehashTable(); 389 return *NewItem; 390 } 391 392 StringMapEntry<ValueTy> &GetOrCreateValue(StringRef Key) { 393 return GetOrCreateValue(Key, ValueTy()); 394 } 395 396 template <typename InitTy> 397 StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, 398 const char *KeyEnd, 399 InitTy Val) { 400 return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart), Val); 401 } 402 403 StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, 404 const char *KeyEnd) { 405 return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart)); 406 } 407 408 /// remove - Remove the specified key/value pair from the map, but do not 409 /// erase it. This aborts if the key is not in the map. 410 void remove(MapEntryTy *KeyValue) { 411 RemoveKey(KeyValue); 412 } 413 414 void erase(iterator I) { 415 MapEntryTy &V = *I; 416 remove(&V); 417 V.Destroy(Allocator); 418 } 419 420 bool erase(StringRef Key) { 421 iterator I = find(Key); 422 if (I == end()) return false; 423 erase(I); 424 return true; 425 } 426 427 ~StringMap() { 428 clear(); 429 free(TheTable); 430 } 431}; 432 433 434template<typename ValueTy> 435class StringMapConstIterator { 436protected: 437 StringMapImpl::ItemBucket *Ptr; 438public: 439 typedef StringMapEntry<ValueTy> value_type; 440 441 explicit StringMapConstIterator(StringMapImpl::ItemBucket *Bucket, 442 bool NoAdvance = false) 443 : Ptr(Bucket) { 444 if (!NoAdvance) AdvancePastEmptyBuckets(); 445 } 446 447 const value_type &operator*() const { 448 return *static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 449 } 450 const value_type *operator->() const { 451 return static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 452 } 453 454 bool operator==(const StringMapConstIterator &RHS) const { 455 return Ptr == RHS.Ptr; 456 } 457 bool operator!=(const StringMapConstIterator &RHS) const { 458 return Ptr != RHS.Ptr; 459 } 460 461 inline StringMapConstIterator& operator++() { // Preincrement 462 ++Ptr; 463 AdvancePastEmptyBuckets(); 464 return *this; 465 } 466 StringMapConstIterator operator++(int) { // Postincrement 467 StringMapConstIterator tmp = *this; ++*this; return tmp; 468 } 469 470private: 471 void AdvancePastEmptyBuckets() { 472 while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal()) 473 ++Ptr; 474 } 475}; 476 477template<typename ValueTy> 478class StringMapIterator : public StringMapConstIterator<ValueTy> { 479public: 480 explicit StringMapIterator(StringMapImpl::ItemBucket *Bucket, 481 bool NoAdvance = false) 482 : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 483 } 484 StringMapEntry<ValueTy> &operator*() const { 485 return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 486 } 487 StringMapEntry<ValueTy> *operator->() const { 488 return static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 489 } 490}; 491 492} 493 494#endif 495