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: 55235633Sdim // Array of NumBuckets pointers to entries, null pointers are holes. 56252723Sdim // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed 57235633Sdim // by an array of the actual hash values as unsigned integers. 58235633Sdim 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; } 105263509Sdim 106263509Sdim void swap(StringMapImpl &Other) { 107263509Sdim std::swap(TheTable, Other.TheTable); 108263509Sdim std::swap(NumBuckets, Other.NumBuckets); 109263509Sdim std::swap(NumItems, Other.NumItems); 110263509Sdim std::swap(NumTombstones, Other.NumTombstones); 111263509Sdim } 112193323Sed}; 113193323Sed 114193323Sed/// StringMapEntry - This is used to represent one value that is inserted into 115193323Sed/// a StringMap. It contains the Value itself and the key: the string length 116193323Sed/// and data. 117193323Sedtemplate<typename ValueTy> 118193323Sedclass StringMapEntry : public StringMapEntryBase { 119263509Sdim StringMapEntry(StringMapEntry &E) LLVM_DELETED_FUNCTION; 120193323Sedpublic: 121193323Sed ValueTy second; 122193323Sed 123193323Sed explicit StringMapEntry(unsigned strLen) 124193323Sed : StringMapEntryBase(strLen), second() {} 125193323Sed StringMapEntry(unsigned strLen, const ValueTy &V) 126193323Sed : StringMapEntryBase(strLen), second(V) {} 127193323Sed 128218893Sdim StringRef getKey() const { 129218893Sdim return StringRef(getKeyData(), getKeyLength()); 130198090Srdivacky } 131198090Srdivacky 132193323Sed const ValueTy &getValue() const { return second; } 133193323Sed ValueTy &getValue() { return second; } 134193323Sed 135193323Sed void setValue(const ValueTy &V) { second = V; } 136193323Sed 137193323Sed /// getKeyData - Return the start of the string data that is the key for this 138193323Sed /// value. The string data is always stored immediately after the 139193323Sed /// StringMapEntry object. 140193323Sed const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 141193323Sed 142224145Sdim StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } 143193323Sed 144193323Sed /// Create - Create a StringMapEntry for the specified key and default 145193323Sed /// construct the value. 146193323Sed template<typename AllocatorTy, typename InitType> 147193323Sed static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 148193323Sed AllocatorTy &Allocator, 149193323Sed InitType InitVal) { 150193323Sed unsigned KeyLength = static_cast<unsigned>(KeyEnd-KeyStart); 151193323Sed 152193323Sed // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill 153193323Sed // in. Allocate a new item with space for the string at the end and a null 154193323Sed // terminator. 155193323Sed 156193323Sed unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 157193323Sed KeyLength+1; 158218893Sdim unsigned Alignment = alignOf<StringMapEntry>(); 159193323Sed 160193323Sed StringMapEntry *NewItem = 161193323Sed static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 162193323Sed 163193323Sed // Default construct the value. 164193323Sed new (NewItem) StringMapEntry(KeyLength); 165193323Sed 166193323Sed // Copy the string information. 167193323Sed char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 168193323Sed memcpy(StrBuffer, KeyStart, KeyLength); 169193323Sed StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 170193323Sed 171193323Sed // Initialize the value if the client wants to. 172193323Sed StringMapEntryInitializer<ValueTy>::Initialize(*NewItem, InitVal); 173193323Sed return NewItem; 174193323Sed } 175193323Sed 176193323Sed template<typename AllocatorTy> 177193323Sed static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 178193323Sed AllocatorTy &Allocator) { 179193323Sed return Create(KeyStart, KeyEnd, Allocator, 0); 180193323Sed } 181193323Sed 182193323Sed /// Create - Create a StringMapEntry with normal malloc/free. 183193323Sed template<typename InitType> 184193323Sed static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 185193323Sed InitType InitVal) { 186193323Sed MallocAllocator A; 187193323Sed return Create(KeyStart, KeyEnd, A, InitVal); 188193323Sed } 189193323Sed 190193323Sed static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { 191193323Sed return Create(KeyStart, KeyEnd, ValueTy()); 192193323Sed } 193193323Sed 194193323Sed /// GetStringMapEntryFromValue - Given a value that is known to be embedded 195193323Sed /// into a StringMapEntry, return the StringMapEntry itself. 196193323Sed static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { 197193323Sed StringMapEntry *EPtr = 0; 198193323Sed char *Ptr = reinterpret_cast<char*>(&V) - 199193323Sed (reinterpret_cast<char*>(&EPtr->second) - 200193323Sed reinterpret_cast<char*>(EPtr)); 201193323Sed return *reinterpret_cast<StringMapEntry*>(Ptr); 202193323Sed } 203193323Sed static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { 204193323Sed return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); 205193323Sed } 206218893Sdim 207206083Srdivacky /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 208206083Srdivacky /// into a StringMapEntry, return the StringMapEntry itself. 209206083Srdivacky static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { 210206083Srdivacky char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>); 211206083Srdivacky return *reinterpret_cast<StringMapEntry*>(Ptr); 212206083Srdivacky } 213193323Sed 214193323Sed /// Destroy - Destroy this StringMapEntry, releasing memory back to the 215193323Sed /// specified allocator. 216193323Sed template<typename AllocatorTy> 217193323Sed void Destroy(AllocatorTy &Allocator) { 218193323Sed // Free memory referenced by the item. 219193323Sed this->~StringMapEntry(); 220193323Sed Allocator.Deallocate(this); 221193323Sed } 222193323Sed 223193323Sed /// Destroy this object, releasing memory back to the malloc allocator. 224193323Sed void Destroy() { 225193323Sed MallocAllocator A; 226193323Sed Destroy(A); 227193323Sed } 228193323Sed}; 229193323Sed 230193323Sed 231193323Sed/// StringMap - This is an unconventional map that is specialized for handling 232193323Sed/// keys that are "strings", which are basically ranges of bytes. This does some 233193323Sed/// funky memory allocation and hashing things to make it extremely efficient, 234193323Sed/// storing the string data *after* the value in the map. 235193323Sedtemplate<typename ValueTy, typename AllocatorTy = MallocAllocator> 236193323Sedclass StringMap : public StringMapImpl { 237193323Sed AllocatorTy Allocator; 238235633Sdimpublic: 239193323Sed typedef StringMapEntry<ValueTy> MapEntryTy; 240235633Sdim 241193323Sed StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 242193323Sed explicit StringMap(unsigned InitialSize) 243193323Sed : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 244218893Sdim 245212904Sdim explicit StringMap(AllocatorTy A) 246212904Sdim : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 247212904Sdim 248252723Sdim StringMap(unsigned InitialSize, AllocatorTy A) 249252723Sdim : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), 250252723Sdim Allocator(A) {} 251252723Sdim 252235633Sdim StringMap(const StringMap &RHS) 253193323Sed : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) { 254193323Sed assert(RHS.empty() && 255193323Sed "Copy ctor from non-empty stringmap not implemented yet!"); 256218893Sdim (void)RHS; 257193323Sed } 258193323Sed void operator=(const StringMap &RHS) { 259193323Sed assert(RHS.empty() && 260193323Sed "assignment from non-empty stringmap not implemented yet!"); 261218893Sdim (void)RHS; 262193323Sed clear(); 263193323Sed } 264193323Sed 265218893Sdim typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; 266218893Sdim typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; 267218893Sdim AllocatorRefTy getAllocator() { return Allocator; } 268218893Sdim AllocatorCRefTy getAllocator() const { return Allocator; } 269193323Sed 270193323Sed typedef const char* key_type; 271193323Sed typedef ValueTy mapped_type; 272193323Sed typedef StringMapEntry<ValueTy> value_type; 273193323Sed typedef size_t size_type; 274193323Sed 275193323Sed typedef StringMapConstIterator<ValueTy> const_iterator; 276193323Sed typedef StringMapIterator<ValueTy> iterator; 277193323Sed 278193323Sed iterator begin() { 279193323Sed return iterator(TheTable, NumBuckets == 0); 280193323Sed } 281193323Sed iterator end() { 282193323Sed return iterator(TheTable+NumBuckets, true); 283193323Sed } 284193323Sed const_iterator begin() const { 285193323Sed return const_iterator(TheTable, NumBuckets == 0); 286193323Sed } 287193323Sed const_iterator end() const { 288193323Sed return const_iterator(TheTable+NumBuckets, true); 289193323Sed } 290193323Sed 291199481Srdivacky iterator find(StringRef Key) { 292198090Srdivacky int Bucket = FindKey(Key); 293193323Sed if (Bucket == -1) return end(); 294235633Sdim return iterator(TheTable+Bucket, true); 295193323Sed } 296193323Sed 297199481Srdivacky const_iterator find(StringRef Key) const { 298198090Srdivacky int Bucket = FindKey(Key); 299193323Sed if (Bucket == -1) return end(); 300235633Sdim return const_iterator(TheTable+Bucket, true); 301193323Sed } 302193323Sed 303252723Sdim /// lookup - Return the entry for the specified key, or a default 304193323Sed /// constructed value if no such entry exists. 305199481Srdivacky ValueTy lookup(StringRef Key) const { 306193323Sed const_iterator it = find(Key); 307193323Sed if (it != end()) 308193323Sed return it->second; 309193323Sed return ValueTy(); 310193323Sed } 311193323Sed 312224145Sdim ValueTy &operator[](StringRef Key) { 313198090Srdivacky return GetOrCreateValue(Key).getValue(); 314193323Sed } 315193323Sed 316199481Srdivacky size_type count(StringRef Key) const { 317198090Srdivacky return find(Key) == end() ? 0 : 1; 318193323Sed } 319193323Sed 320193323Sed /// insert - Insert the specified key/value pair into the map. If the key 321193323Sed /// already exists in the map, return false and ignore the request, otherwise 322193323Sed /// insert it and return true. 323193323Sed bool insert(MapEntryTy *KeyValue) { 324198090Srdivacky unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 325235633Sdim StringMapEntryBase *&Bucket = TheTable[BucketNo]; 326235633Sdim if (Bucket && Bucket != getTombstoneVal()) 327193323Sed return false; // Already exists in map. 328193323Sed 329235633Sdim if (Bucket == getTombstoneVal()) 330193323Sed --NumTombstones; 331235633Sdim Bucket = KeyValue; 332193323Sed ++NumItems; 333221345Sdim assert(NumItems + NumTombstones <= NumBuckets); 334193323Sed 335221345Sdim RehashTable(); 336193323Sed return true; 337193323Sed } 338193323Sed 339193323Sed // clear - Empties out the StringMap 340193323Sed void clear() { 341193323Sed if (empty()) return; 342193323Sed 343193323Sed // Zap all values, resetting the keys back to non-present (not tombstone), 344193323Sed // which is safe because we're removing all elements. 345235633Sdim for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 346235633Sdim StringMapEntryBase *&Bucket = TheTable[I]; 347235633Sdim if (Bucket && Bucket != getTombstoneVal()) { 348235633Sdim static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 349193323Sed } 350252723Sdim Bucket = 0; 351193323Sed } 352193323Sed 353193323Sed NumItems = 0; 354221345Sdim NumTombstones = 0; 355193323Sed } 356193323Sed 357193323Sed /// GetOrCreateValue - Look up the specified key in the table. If a value 358193323Sed /// exists, return it. Otherwise, default construct a value, insert it, and 359193323Sed /// return. 360193323Sed template <typename InitTy> 361224145Sdim MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { 362198090Srdivacky unsigned BucketNo = LookupBucketFor(Key); 363235633Sdim StringMapEntryBase *&Bucket = TheTable[BucketNo]; 364235633Sdim if (Bucket && Bucket != getTombstoneVal()) 365235633Sdim return *static_cast<MapEntryTy*>(Bucket); 366193323Sed 367198090Srdivacky MapEntryTy *NewItem = 368198090Srdivacky MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); 369193323Sed 370235633Sdim if (Bucket == getTombstoneVal()) 371193323Sed --NumTombstones; 372193323Sed ++NumItems; 373221345Sdim assert(NumItems + NumTombstones <= NumBuckets); 374193323Sed 375193323Sed // Fill in the bucket for the hash table. The FullHashValue was already 376193323Sed // filled in by LookupBucketFor. 377235633Sdim Bucket = NewItem; 378193323Sed 379221345Sdim RehashTable(); 380193323Sed return *NewItem; 381193323Sed } 382193323Sed 383224145Sdim MapEntryTy &GetOrCreateValue(StringRef Key) { 384198090Srdivacky return GetOrCreateValue(Key, ValueTy()); 385198090Srdivacky } 386198090Srdivacky 387193323Sed /// remove - Remove the specified key/value pair from the map, but do not 388193323Sed /// erase it. This aborts if the key is not in the map. 389193323Sed void remove(MapEntryTy *KeyValue) { 390193323Sed RemoveKey(KeyValue); 391193323Sed } 392193323Sed 393193323Sed void erase(iterator I) { 394193323Sed MapEntryTy &V = *I; 395193323Sed remove(&V); 396193323Sed V.Destroy(Allocator); 397193323Sed } 398193323Sed 399199481Srdivacky bool erase(StringRef Key) { 400193323Sed iterator I = find(Key); 401193323Sed if (I == end()) return false; 402193323Sed erase(I); 403193323Sed return true; 404193323Sed } 405193323Sed 406193323Sed ~StringMap() { 407193323Sed clear(); 408193323Sed free(TheTable); 409193323Sed } 410193323Sed}; 411193323Sed 412193323Sed 413193323Sedtemplate<typename ValueTy> 414193323Sedclass StringMapConstIterator { 415193323Sedprotected: 416235633Sdim StringMapEntryBase **Ptr; 417193323Sedpublic: 418193323Sed typedef StringMapEntry<ValueTy> value_type; 419193323Sed 420263509Sdim StringMapConstIterator() : Ptr(0) { } 421263509Sdim 422235633Sdim explicit StringMapConstIterator(StringMapEntryBase **Bucket, 423193323Sed bool NoAdvance = false) 424193323Sed : Ptr(Bucket) { 425193323Sed if (!NoAdvance) AdvancePastEmptyBuckets(); 426193323Sed } 427193323Sed 428193323Sed const value_type &operator*() const { 429235633Sdim return *static_cast<StringMapEntry<ValueTy>*>(*Ptr); 430193323Sed } 431193323Sed const value_type *operator->() const { 432235633Sdim return static_cast<StringMapEntry<ValueTy>*>(*Ptr); 433193323Sed } 434193323Sed 435193323Sed bool operator==(const StringMapConstIterator &RHS) const { 436193323Sed return Ptr == RHS.Ptr; 437193323Sed } 438193323Sed bool operator!=(const StringMapConstIterator &RHS) const { 439193323Sed return Ptr != RHS.Ptr; 440193323Sed } 441193323Sed 442252723Sdim inline StringMapConstIterator& operator++() { // Preincrement 443193323Sed ++Ptr; 444193323Sed AdvancePastEmptyBuckets(); 445193323Sed return *this; 446193323Sed } 447193323Sed StringMapConstIterator operator++(int) { // Postincrement 448193323Sed StringMapConstIterator tmp = *this; ++*this; return tmp; 449193323Sed } 450193323Sed 451193323Sedprivate: 452193323Sed void AdvancePastEmptyBuckets() { 453235633Sdim while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal()) 454193323Sed ++Ptr; 455193323Sed } 456193323Sed}; 457193323Sed 458193323Sedtemplate<typename ValueTy> 459193323Sedclass StringMapIterator : public StringMapConstIterator<ValueTy> { 460193323Sedpublic: 461263509Sdim StringMapIterator() {} 462235633Sdim explicit StringMapIterator(StringMapEntryBase **Bucket, 463193323Sed bool NoAdvance = false) 464193323Sed : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 465193323Sed } 466193323Sed StringMapEntry<ValueTy> &operator*() const { 467235633Sdim return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 468193323Sed } 469193323Sed StringMapEntry<ValueTy> *operator->() const { 470235633Sdim return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 471193323Sed } 472193323Sed}; 473193323Sed 474193323Sed} 475193323Sed 476193323Sed#endif 477