1193323Sed//===--- StringMap.h - String Hash table map interface ----------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the StringMap class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#ifndef LLVM_ADT_STRINGMAP_H 15193323Sed#define LLVM_ADT_STRINGMAP_H 16193323Sed 17198090Srdivacky#include "llvm/ADT/StringRef.h" 18193323Sed#include "llvm/Support/Allocator.h" 19193323Sed#include <cstring> 20193323Sed 21193323Sednamespace llvm { 22193323Sed template<typename ValueT> 23193323Sed class StringMapConstIterator; 24193323Sed template<typename ValueT> 25193323Sed class StringMapIterator; 26193323Sed template<typename ValueTy> 27193323Sed class StringMapEntry; 28193323Sed 29193323Sed/// StringMapEntryInitializer - This datatype can be partially specialized for 30193323Sed/// various datatypes in a stringmap to allow them to be initialized when an 31193323Sed/// entry is default constructed for the map. 32193323Sedtemplate<typename ValueTy> 33193323Sedclass StringMapEntryInitializer { 34193323Sedpublic: 35193323Sed template <typename InitTy> 36193323Sed static void Initialize(StringMapEntry<ValueTy> &T, InitTy InitVal) { 37193323Sed T.second = InitVal; 38193323Sed } 39193323Sed}; 40193323Sed 41193323Sed 42193323Sed/// StringMapEntryBase - Shared base class of StringMapEntry instances. 43193323Sedclass StringMapEntryBase { 44193323Sed unsigned StrLen; 45193323Sedpublic: 46193323Sed explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} 47193323Sed 48193323Sed unsigned getKeyLength() const { return StrLen; } 49193323Sed}; 50193323Sed 51193323Sed/// StringMapImpl - This is the base class of StringMap that is shared among 52193323Sed/// all of its instantiations. 53193323Sedclass StringMapImpl { 54193323Sedprotected: 55234353Sdim // Array of NumBuckets pointers to entries, null pointers are holes. 56249423Sdim // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed 57234353Sdim // by an array of the actual hash values as unsigned integers. 58234353Sdim StringMapEntryBase **TheTable; 59193323Sed unsigned NumBuckets; 60193323Sed unsigned NumItems; 61193323Sed unsigned NumTombstones; 62193323Sed unsigned ItemSize; 63193323Sedprotected: 64193323Sed explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) { 65193323Sed // Initialize the map with zero buckets to allocation. 66193323Sed TheTable = 0; 67193323Sed NumBuckets = 0; 68193323Sed NumItems = 0; 69193323Sed NumTombstones = 0; 70193323Sed } 71193323Sed StringMapImpl(unsigned InitSize, unsigned ItemSize); 72193323Sed void RehashTable(); 73193323Sed 74193323Sed /// LookupBucketFor - Look up the bucket that the specified string should end 75193323Sed /// up in. If it already exists as a key in the map, the Item pointer for the 76193323Sed /// specified bucket will be non-null. Otherwise, it will be null. In either 77193323Sed /// case, the FullHashValue field of the bucket will be set to the hash value 78193323Sed /// of the string. 79199481Srdivacky unsigned LookupBucketFor(StringRef Key); 80193323Sed 81193323Sed /// FindKey - Look up the bucket that contains the specified key. If it exists 82193323Sed /// in the map, return the bucket number of the key. Otherwise return -1. 83193323Sed /// This does not modify the map. 84199481Srdivacky int FindKey(StringRef Key) const; 85193323Sed 86193323Sed /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 87193323Sed /// delete it. This aborts if the value isn't in the table. 88193323Sed void RemoveKey(StringMapEntryBase *V); 89193323Sed 90193323Sed /// RemoveKey - Remove the StringMapEntry for the specified key from the 91193323Sed /// table, returning it. If the key is not in the table, this returns null. 92199481Srdivacky StringMapEntryBase *RemoveKey(StringRef Key); 93193323Sedprivate: 94193323Sed void init(unsigned Size); 95193323Sedpublic: 96193323Sed static StringMapEntryBase *getTombstoneVal() { 97193323Sed return (StringMapEntryBase*)-1; 98193323Sed } 99193323Sed 100193323Sed unsigned getNumBuckets() const { return NumBuckets; } 101193323Sed unsigned getNumItems() const { return NumItems; } 102193323Sed 103193323Sed bool empty() const { return NumItems == 0; } 104193323Sed unsigned size() const { return NumItems; } 105193323Sed}; 106193323Sed 107193323Sed/// StringMapEntry - This is used to represent one value that is inserted into 108193323Sed/// a StringMap. It contains the Value itself and the key: the string length 109193323Sed/// and data. 110193323Sedtemplate<typename ValueTy> 111193323Sedclass StringMapEntry : public StringMapEntryBase { 112193323Sedpublic: 113193323Sed ValueTy second; 114193323Sed 115193323Sed explicit StringMapEntry(unsigned strLen) 116193323Sed : StringMapEntryBase(strLen), second() {} 117193323Sed StringMapEntry(unsigned strLen, const ValueTy &V) 118193323Sed : StringMapEntryBase(strLen), second(V) {} 119193323Sed 120218893Sdim StringRef getKey() const { 121218893Sdim return StringRef(getKeyData(), getKeyLength()); 122198090Srdivacky } 123198090Srdivacky 124193323Sed const ValueTy &getValue() const { return second; } 125193323Sed ValueTy &getValue() { return second; } 126193323Sed 127193323Sed void setValue(const ValueTy &V) { second = V; } 128193323Sed 129193323Sed /// getKeyData - Return the start of the string data that is the key for this 130193323Sed /// value. The string data is always stored immediately after the 131193323Sed /// StringMapEntry object. 132193323Sed const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 133193323Sed 134224145Sdim StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } 135193323Sed 136193323Sed /// Create - Create a StringMapEntry for the specified key and default 137193323Sed /// construct the value. 138193323Sed template<typename AllocatorTy, typename InitType> 139193323Sed static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 140193323Sed AllocatorTy &Allocator, 141193323Sed InitType InitVal) { 142193323Sed unsigned KeyLength = static_cast<unsigned>(KeyEnd-KeyStart); 143193323Sed 144193323Sed // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill 145193323Sed // in. Allocate a new item with space for the string at the end and a null 146193323Sed // terminator. 147193323Sed 148193323Sed unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 149193323Sed KeyLength+1; 150218893Sdim unsigned Alignment = alignOf<StringMapEntry>(); 151193323Sed 152193323Sed StringMapEntry *NewItem = 153193323Sed static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 154193323Sed 155193323Sed // Default construct the value. 156193323Sed new (NewItem) StringMapEntry(KeyLength); 157193323Sed 158193323Sed // Copy the string information. 159193323Sed char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 160193323Sed memcpy(StrBuffer, KeyStart, KeyLength); 161193323Sed StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 162193323Sed 163193323Sed // Initialize the value if the client wants to. 164193323Sed StringMapEntryInitializer<ValueTy>::Initialize(*NewItem, InitVal); 165193323Sed return NewItem; 166193323Sed } 167193323Sed 168193323Sed template<typename AllocatorTy> 169193323Sed static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 170193323Sed AllocatorTy &Allocator) { 171193323Sed return Create(KeyStart, KeyEnd, Allocator, 0); 172193323Sed } 173193323Sed 174193323Sed /// Create - Create a StringMapEntry with normal malloc/free. 175193323Sed template<typename InitType> 176193323Sed static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 177193323Sed InitType InitVal) { 178193323Sed MallocAllocator A; 179193323Sed return Create(KeyStart, KeyEnd, A, InitVal); 180193323Sed } 181193323Sed 182193323Sed static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { 183193323Sed return Create(KeyStart, KeyEnd, ValueTy()); 184193323Sed } 185193323Sed 186193323Sed /// GetStringMapEntryFromValue - Given a value that is known to be embedded 187193323Sed /// into a StringMapEntry, return the StringMapEntry itself. 188193323Sed static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { 189193323Sed StringMapEntry *EPtr = 0; 190193323Sed char *Ptr = reinterpret_cast<char*>(&V) - 191193323Sed (reinterpret_cast<char*>(&EPtr->second) - 192193323Sed reinterpret_cast<char*>(EPtr)); 193193323Sed return *reinterpret_cast<StringMapEntry*>(Ptr); 194193323Sed } 195193323Sed static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { 196193323Sed return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); 197193323Sed } 198218893Sdim 199206083Srdivacky /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 200206083Srdivacky /// into a StringMapEntry, return the StringMapEntry itself. 201206083Srdivacky static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { 202206083Srdivacky char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>); 203206083Srdivacky return *reinterpret_cast<StringMapEntry*>(Ptr); 204206083Srdivacky } 205193323Sed 206193323Sed /// Destroy - Destroy this StringMapEntry, releasing memory back to the 207193323Sed /// specified allocator. 208193323Sed template<typename AllocatorTy> 209193323Sed void Destroy(AllocatorTy &Allocator) { 210193323Sed // Free memory referenced by the item. 211193323Sed this->~StringMapEntry(); 212193323Sed Allocator.Deallocate(this); 213193323Sed } 214193323Sed 215193323Sed /// Destroy this object, releasing memory back to the malloc allocator. 216193323Sed void Destroy() { 217193323Sed MallocAllocator A; 218193323Sed Destroy(A); 219193323Sed } 220193323Sed}; 221193323Sed 222193323Sed 223193323Sed/// StringMap - This is an unconventional map that is specialized for handling 224193323Sed/// keys that are "strings", which are basically ranges of bytes. This does some 225193323Sed/// funky memory allocation and hashing things to make it extremely efficient, 226193323Sed/// storing the string data *after* the value in the map. 227193323Sedtemplate<typename ValueTy, typename AllocatorTy = MallocAllocator> 228193323Sedclass StringMap : public StringMapImpl { 229193323Sed AllocatorTy Allocator; 230234353Sdimpublic: 231193323Sed typedef StringMapEntry<ValueTy> MapEntryTy; 232234353Sdim 233193323Sed StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 234193323Sed explicit StringMap(unsigned InitialSize) 235193323Sed : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 236218893Sdim 237212904Sdim explicit StringMap(AllocatorTy A) 238212904Sdim : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 239212904Sdim 240249423Sdim StringMap(unsigned InitialSize, AllocatorTy A) 241249423Sdim : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), 242249423Sdim Allocator(A) {} 243249423Sdim 244234982Sdim StringMap(const StringMap &RHS) 245193323Sed : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) { 246193323Sed assert(RHS.empty() && 247193323Sed "Copy ctor from non-empty stringmap not implemented yet!"); 248218893Sdim (void)RHS; 249193323Sed } 250193323Sed void operator=(const StringMap &RHS) { 251193323Sed assert(RHS.empty() && 252193323Sed "assignment from non-empty stringmap not implemented yet!"); 253218893Sdim (void)RHS; 254193323Sed clear(); 255193323Sed } 256193323Sed 257218893Sdim typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; 258218893Sdim typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; 259218893Sdim AllocatorRefTy getAllocator() { return Allocator; } 260218893Sdim AllocatorCRefTy getAllocator() const { return Allocator; } 261193323Sed 262193323Sed typedef const char* key_type; 263193323Sed typedef ValueTy mapped_type; 264193323Sed typedef StringMapEntry<ValueTy> value_type; 265193323Sed typedef size_t size_type; 266193323Sed 267193323Sed typedef StringMapConstIterator<ValueTy> const_iterator; 268193323Sed typedef StringMapIterator<ValueTy> iterator; 269193323Sed 270193323Sed iterator begin() { 271193323Sed return iterator(TheTable, NumBuckets == 0); 272193323Sed } 273193323Sed iterator end() { 274193323Sed return iterator(TheTable+NumBuckets, true); 275193323Sed } 276193323Sed const_iterator begin() const { 277193323Sed return const_iterator(TheTable, NumBuckets == 0); 278193323Sed } 279193323Sed const_iterator end() const { 280193323Sed return const_iterator(TheTable+NumBuckets, true); 281193323Sed } 282193323Sed 283199481Srdivacky iterator find(StringRef Key) { 284198090Srdivacky int Bucket = FindKey(Key); 285193323Sed if (Bucket == -1) return end(); 286234353Sdim return iterator(TheTable+Bucket, true); 287193323Sed } 288193323Sed 289199481Srdivacky const_iterator find(StringRef Key) const { 290198090Srdivacky int Bucket = FindKey(Key); 291193323Sed if (Bucket == -1) return end(); 292234353Sdim return const_iterator(TheTable+Bucket, true); 293193323Sed } 294193323Sed 295249423Sdim /// lookup - Return the entry for the specified key, or a default 296193323Sed /// constructed value if no such entry exists. 297199481Srdivacky ValueTy lookup(StringRef Key) const { 298193323Sed const_iterator it = find(Key); 299193323Sed if (it != end()) 300193323Sed return it->second; 301193323Sed return ValueTy(); 302193323Sed } 303193323Sed 304224145Sdim ValueTy &operator[](StringRef Key) { 305198090Srdivacky return GetOrCreateValue(Key).getValue(); 306193323Sed } 307193323Sed 308199481Srdivacky size_type count(StringRef Key) const { 309198090Srdivacky return find(Key) == end() ? 0 : 1; 310193323Sed } 311193323Sed 312193323Sed /// insert - Insert the specified key/value pair into the map. If the key 313193323Sed /// already exists in the map, return false and ignore the request, otherwise 314193323Sed /// insert it and return true. 315193323Sed bool insert(MapEntryTy *KeyValue) { 316198090Srdivacky unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 317234353Sdim StringMapEntryBase *&Bucket = TheTable[BucketNo]; 318234353Sdim if (Bucket && Bucket != getTombstoneVal()) 319193323Sed return false; // Already exists in map. 320193323Sed 321234353Sdim if (Bucket == getTombstoneVal()) 322193323Sed --NumTombstones; 323234353Sdim Bucket = KeyValue; 324193323Sed ++NumItems; 325221345Sdim assert(NumItems + NumTombstones <= NumBuckets); 326193323Sed 327221345Sdim RehashTable(); 328193323Sed return true; 329193323Sed } 330193323Sed 331193323Sed // clear - Empties out the StringMap 332193323Sed void clear() { 333193323Sed if (empty()) return; 334193323Sed 335193323Sed // Zap all values, resetting the keys back to non-present (not tombstone), 336193323Sed // which is safe because we're removing all elements. 337234353Sdim for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 338234353Sdim StringMapEntryBase *&Bucket = TheTable[I]; 339234353Sdim if (Bucket && Bucket != getTombstoneVal()) { 340234353Sdim static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 341193323Sed } 342249423Sdim Bucket = 0; 343193323Sed } 344193323Sed 345193323Sed NumItems = 0; 346221345Sdim NumTombstones = 0; 347193323Sed } 348193323Sed 349193323Sed /// GetOrCreateValue - Look up the specified key in the table. If a value 350193323Sed /// exists, return it. Otherwise, default construct a value, insert it, and 351193323Sed /// return. 352193323Sed template <typename InitTy> 353224145Sdim MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { 354198090Srdivacky unsigned BucketNo = LookupBucketFor(Key); 355234353Sdim StringMapEntryBase *&Bucket = TheTable[BucketNo]; 356234353Sdim if (Bucket && Bucket != getTombstoneVal()) 357234353Sdim return *static_cast<MapEntryTy*>(Bucket); 358193323Sed 359198090Srdivacky MapEntryTy *NewItem = 360198090Srdivacky MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); 361193323Sed 362234353Sdim if (Bucket == getTombstoneVal()) 363193323Sed --NumTombstones; 364193323Sed ++NumItems; 365221345Sdim assert(NumItems + NumTombstones <= NumBuckets); 366193323Sed 367193323Sed // Fill in the bucket for the hash table. The FullHashValue was already 368193323Sed // filled in by LookupBucketFor. 369234353Sdim Bucket = NewItem; 370193323Sed 371221345Sdim RehashTable(); 372193323Sed return *NewItem; 373193323Sed } 374193323Sed 375224145Sdim MapEntryTy &GetOrCreateValue(StringRef Key) { 376198090Srdivacky return GetOrCreateValue(Key, ValueTy()); 377198090Srdivacky } 378198090Srdivacky 379193323Sed /// remove - Remove the specified key/value pair from the map, but do not 380193323Sed /// erase it. This aborts if the key is not in the map. 381193323Sed void remove(MapEntryTy *KeyValue) { 382193323Sed RemoveKey(KeyValue); 383193323Sed } 384193323Sed 385193323Sed void erase(iterator I) { 386193323Sed MapEntryTy &V = *I; 387193323Sed remove(&V); 388193323Sed V.Destroy(Allocator); 389193323Sed } 390193323Sed 391199481Srdivacky bool erase(StringRef Key) { 392193323Sed iterator I = find(Key); 393193323Sed if (I == end()) return false; 394193323Sed erase(I); 395193323Sed return true; 396193323Sed } 397193323Sed 398193323Sed ~StringMap() { 399193323Sed clear(); 400193323Sed free(TheTable); 401193323Sed } 402193323Sed}; 403193323Sed 404193323Sed 405193323Sedtemplate<typename ValueTy> 406193323Sedclass StringMapConstIterator { 407193323Sedprotected: 408234353Sdim StringMapEntryBase **Ptr; 409193323Sedpublic: 410193323Sed typedef StringMapEntry<ValueTy> value_type; 411193323Sed 412234353Sdim explicit StringMapConstIterator(StringMapEntryBase **Bucket, 413193323Sed bool NoAdvance = false) 414193323Sed : Ptr(Bucket) { 415193323Sed if (!NoAdvance) AdvancePastEmptyBuckets(); 416193323Sed } 417193323Sed 418193323Sed const value_type &operator*() const { 419234353Sdim return *static_cast<StringMapEntry<ValueTy>*>(*Ptr); 420193323Sed } 421193323Sed const value_type *operator->() const { 422234353Sdim return static_cast<StringMapEntry<ValueTy>*>(*Ptr); 423193323Sed } 424193323Sed 425193323Sed bool operator==(const StringMapConstIterator &RHS) const { 426193323Sed return Ptr == RHS.Ptr; 427193323Sed } 428193323Sed bool operator!=(const StringMapConstIterator &RHS) const { 429193323Sed return Ptr != RHS.Ptr; 430193323Sed } 431193323Sed 432249423Sdim inline StringMapConstIterator& operator++() { // Preincrement 433193323Sed ++Ptr; 434193323Sed AdvancePastEmptyBuckets(); 435193323Sed return *this; 436193323Sed } 437193323Sed StringMapConstIterator operator++(int) { // Postincrement 438193323Sed StringMapConstIterator tmp = *this; ++*this; return tmp; 439193323Sed } 440193323Sed 441193323Sedprivate: 442193323Sed void AdvancePastEmptyBuckets() { 443234353Sdim while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal()) 444193323Sed ++Ptr; 445193323Sed } 446193323Sed}; 447193323Sed 448193323Sedtemplate<typename ValueTy> 449193323Sedclass StringMapIterator : public StringMapConstIterator<ValueTy> { 450193323Sedpublic: 451234353Sdim explicit StringMapIterator(StringMapEntryBase **Bucket, 452193323Sed bool NoAdvance = false) 453193323Sed : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 454193323Sed } 455193323Sed StringMapEntry<ValueTy> &operator*() const { 456234353Sdim return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 457193323Sed } 458193323Sed StringMapEntry<ValueTy> *operator->() const { 459234353Sdim return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 460193323Sed } 461193323Sed}; 462193323Sed 463193323Sed} 464193323Sed 465193323Sed#endif 466