LLVM API Documentation
00001 //===--- StringMap.h - String Hash table map interface ----------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines the StringMap class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_ADT_STRINGMAP_H 00015 #define LLVM_ADT_STRINGMAP_H 00016 00017 #include "llvm/ADT/StringRef.h" 00018 #include "llvm/Support/Allocator.h" 00019 #include <cstring> 00020 #include <string> 00021 00022 namespace llvm { 00023 template<typename ValueT> 00024 class StringMapConstIterator; 00025 template<typename ValueT> 00026 class StringMapIterator; 00027 template<typename ValueTy> 00028 class StringMapEntry; 00029 00030 /// StringMapEntryInitializer - This datatype can be partially specialized for 00031 /// various datatypes in a stringmap to allow them to be initialized when an 00032 /// entry is default constructed for the map. 00033 template<typename ValueTy> 00034 class StringMapEntryInitializer { 00035 public: 00036 template <typename InitTy> 00037 static void Initialize(StringMapEntry<ValueTy> &T, InitTy InitVal) { 00038 T.second = InitVal; 00039 } 00040 }; 00041 00042 00043 /// StringMapEntryBase - Shared base class of StringMapEntry instances. 00044 class StringMapEntryBase { 00045 unsigned StrLen; 00046 public: 00047 explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} 00048 00049 unsigned getKeyLength() const { return StrLen; } 00050 }; 00051 00052 /// StringMapImpl - This is the base class of StringMap that is shared among 00053 /// all of its instantiations. 00054 class StringMapImpl { 00055 public: 00056 /// ItemBucket - The hash table consists of an array of these. If Item is 00057 /// non-null, this is an extant entry, otherwise, it is a hole. 00058 struct ItemBucket { 00059 /// FullHashValue - This remembers the full hash value of the key for 00060 /// easy scanning. 00061 unsigned FullHashValue; 00062 00063 /// Item - This is a pointer to the actual item object. 00064 StringMapEntryBase *Item; 00065 }; 00066 00067 protected: 00068 ItemBucket *TheTable; 00069 unsigned NumBuckets; 00070 unsigned NumItems; 00071 unsigned NumTombstones; 00072 unsigned ItemSize; 00073 protected: 00074 explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) { 00075 // Initialize the map with zero buckets to allocation. 00076 TheTable = 0; 00077 NumBuckets = 0; 00078 NumItems = 0; 00079 NumTombstones = 0; 00080 } 00081 StringMapImpl(unsigned InitSize, unsigned ItemSize); 00082 void RehashTable(); 00083 00084 /// ShouldRehash - Return true if the table should be rehashed after a new 00085 /// element was recently inserted. 00086 bool ShouldRehash() const { 00087 // If the hash table is now more than 3/4 full, or if fewer than 1/8 of 00088 // the buckets are empty (meaning that many are filled with tombstones), 00089 // grow the table. 00090 return NumItems*4 > NumBuckets*3 || 00091 NumBuckets-(NumItems+NumTombstones) < NumBuckets/8; 00092 } 00093 00094 /// LookupBucketFor - Look up the bucket that the specified string should end 00095 /// up in. If it already exists as a key in the map, the Item pointer for the 00096 /// specified bucket will be non-null. Otherwise, it will be null. In either 00097 /// case, the FullHashValue field of the bucket will be set to the hash value 00098 /// of the string. 00099 unsigned LookupBucketFor(const StringRef &Key); 00100 00101 /// FindKey - Look up the bucket that contains the specified key. If it exists 00102 /// in the map, return the bucket number of the key. Otherwise return -1. 00103 /// This does not modify the map. 00104 int FindKey(const StringRef &Key) const; 00105 00106 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 00107 /// delete it. This aborts if the value isn't in the table. 00108 void RemoveKey(StringMapEntryBase *V); 00109 00110 /// RemoveKey - Remove the StringMapEntry for the specified key from the 00111 /// table, returning it. If the key is not in the table, this returns null. 00112 StringMapEntryBase *RemoveKey(const StringRef &Key); 00113 private: 00114 void init(unsigned Size); 00115 public: 00116 static StringMapEntryBase *getTombstoneVal() { 00117 return (StringMapEntryBase*)-1; 00118 } 00119 00120 unsigned getNumBuckets() const { return NumBuckets; } 00121 unsigned getNumItems() const { return NumItems; } 00122 00123 bool empty() const { return NumItems == 0; } 00124 unsigned size() const { return NumItems; } 00125 }; 00126 00127 /// StringMapEntry - This is used to represent one value that is inserted into 00128 /// a StringMap. It contains the Value itself and the key: the string length 00129 /// and data. 00130 template<typename ValueTy> 00131 class StringMapEntry : public StringMapEntryBase { 00132 public: 00133 ValueTy second; 00134 00135 explicit StringMapEntry(unsigned strLen) 00136 : StringMapEntryBase(strLen), second() {} 00137 StringMapEntry(unsigned strLen, const ValueTy &V) 00138 : StringMapEntryBase(strLen), second(V) {} 00139 00140 StringRef getKey() const { 00141 return StringRef(getKeyData(), getKeyLength()); 00142 } 00143 00144 const ValueTy &getValue() const { return second; } 00145 ValueTy &getValue() { return second; } 00146 00147 void setValue(const ValueTy &V) { second = V; } 00148 00149 /// getKeyData - Return the start of the string data that is the key for this 00150 /// value. The string data is always stored immediately after the 00151 /// StringMapEntry object. 00152 const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 00153 00154 const char *first() const { return getKeyData(); } 00155 00156 /// Create - Create a StringMapEntry for the specified key and default 00157 /// construct the value. 00158 template<typename AllocatorTy, typename InitType> 00159 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 00160 AllocatorTy &Allocator, 00161 InitType InitVal) { 00162 unsigned KeyLength = static_cast<unsigned>(KeyEnd-KeyStart); 00163 00164 // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill 00165 // in. Allocate a new item with space for the string at the end and a null 00166 // terminator. 00167 00168 unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 00169 KeyLength+1; 00170 unsigned Alignment = alignof<StringMapEntry>(); 00171 00172 StringMapEntry *NewItem = 00173 static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 00174 00175 // Default construct the value. 00176 new (NewItem) StringMapEntry(KeyLength); 00177 00178 // Copy the string information. 00179 char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 00180 memcpy(StrBuffer, KeyStart, KeyLength); 00181 StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 00182 00183 // Initialize the value if the client wants to. 00184 StringMapEntryInitializer<ValueTy>::Initialize(*NewItem, InitVal); 00185 return NewItem; 00186 } 00187 00188 template<typename AllocatorTy> 00189 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 00190 AllocatorTy &Allocator) { 00191 return Create(KeyStart, KeyEnd, Allocator, 0); 00192 } 00193 00194 00195 /// Create - Create a StringMapEntry with normal malloc/free. 00196 template<typename InitType> 00197 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, 00198 InitType InitVal) { 00199 MallocAllocator A; 00200 return Create(KeyStart, KeyEnd, A, InitVal); 00201 } 00202 00203 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { 00204 return Create(KeyStart, KeyEnd, ValueTy()); 00205 } 00206 00207 /// GetStringMapEntryFromValue - Given a value that is known to be embedded 00208 /// into a StringMapEntry, return the StringMapEntry itself. 00209 static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { 00210 StringMapEntry *EPtr = 0; 00211 char *Ptr = reinterpret_cast<char*>(&V) - 00212 (reinterpret_cast<char*>(&EPtr->second) - 00213 reinterpret_cast<char*>(EPtr)); 00214 return *reinterpret_cast<StringMapEntry*>(Ptr); 00215 } 00216 static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { 00217 return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); 00218 } 00219 00220 /// Destroy - Destroy this StringMapEntry, releasing memory back to the 00221 /// specified allocator. 00222 template<typename AllocatorTy> 00223 void Destroy(AllocatorTy &Allocator) { 00224 // Free memory referenced by the item. 00225 this->~StringMapEntry(); 00226 Allocator.Deallocate(this); 00227 } 00228 00229 /// Destroy this object, releasing memory back to the malloc allocator. 00230 void Destroy() { 00231 MallocAllocator A; 00232 Destroy(A); 00233 } 00234 }; 00235 00236 00237 /// StringMap - This is an unconventional map that is specialized for handling 00238 /// keys that are "strings", which are basically ranges of bytes. This does some 00239 /// funky memory allocation and hashing things to make it extremely efficient, 00240 /// storing the string data *after* the value in the map. 00241 template<typename ValueTy, typename AllocatorTy = MallocAllocator> 00242 class StringMap : public StringMapImpl { 00243 AllocatorTy Allocator; 00244 typedef StringMapEntry<ValueTy> MapEntryTy; 00245 public: 00246 StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 00247 explicit StringMap(unsigned InitialSize) 00248 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 00249 explicit StringMap(const StringMap &RHS) 00250 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) { 00251 assert(RHS.empty() && 00252 "Copy ctor from non-empty stringmap not implemented yet!"); 00253 } 00254 void operator=(const StringMap &RHS) { 00255 assert(RHS.empty() && 00256 "assignment from non-empty stringmap not implemented yet!"); 00257 clear(); 00258 } 00259 00260 00261 AllocatorTy &getAllocator() { return Allocator; } 00262 const AllocatorTy &getAllocator() const { return Allocator; } 00263 00264 typedef const char* key_type; 00265 typedef ValueTy mapped_type; 00266 typedef StringMapEntry<ValueTy> value_type; 00267 typedef size_t size_type; 00268 00269 typedef StringMapConstIterator<ValueTy> const_iterator; 00270 typedef StringMapIterator<ValueTy> iterator; 00271 00272 iterator begin() { 00273 return iterator(TheTable, NumBuckets == 0); 00274 } 00275 iterator end() { 00276 return iterator(TheTable+NumBuckets, true); 00277 } 00278 const_iterator begin() const { 00279 return const_iterator(TheTable, NumBuckets == 0); 00280 } 00281 const_iterator end() const { 00282 return const_iterator(TheTable+NumBuckets, true); 00283 } 00284 00285 iterator find(const StringRef &Key) { 00286 int Bucket = FindKey(Key); 00287 if (Bucket == -1) return end(); 00288 return iterator(TheTable+Bucket); 00289 } 00290 00291 const_iterator find(const StringRef &Key) const { 00292 int Bucket = FindKey(Key); 00293 if (Bucket == -1) return end(); 00294 return const_iterator(TheTable+Bucket); 00295 } 00296 00297 /// lookup - Return the entry for the specified key, or a default 00298 /// constructed value if no such entry exists. 00299 ValueTy lookup(const StringRef &Key) const { 00300 const_iterator it = find(Key); 00301 if (it != end()) 00302 return it->second; 00303 return ValueTy(); 00304 } 00305 00306 ValueTy& operator[](const StringRef &Key) { 00307 return GetOrCreateValue(Key).getValue(); 00308 } 00309 00310 size_type count(const StringRef &Key) const { 00311 return find(Key) == end() ? 0 : 1; 00312 } 00313 00314 /// insert - Insert the specified key/value pair into the map. If the key 00315 /// already exists in the map, return false and ignore the request, otherwise 00316 /// insert it and return true. 00317 bool insert(MapEntryTy *KeyValue) { 00318 unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 00319 ItemBucket &Bucket = TheTable[BucketNo]; 00320 if (Bucket.Item && Bucket.Item != getTombstoneVal()) 00321 return false; // Already exists in map. 00322 00323 if (Bucket.Item == getTombstoneVal()) 00324 --NumTombstones; 00325 Bucket.Item = KeyValue; 00326 ++NumItems; 00327 00328 if (ShouldRehash()) 00329 RehashTable(); 00330 return true; 00331 } 00332 00333 // clear - Empties out the StringMap 00334 void clear() { 00335 if (empty()) return; 00336 00337 // Zap all values, resetting the keys back to non-present (not tombstone), 00338 // which is safe because we're removing all elements. 00339 for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { 00340 if (I->Item && I->Item != getTombstoneVal()) { 00341 static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator); 00342 I->Item = 0; 00343 } 00344 } 00345 00346 NumItems = 0; 00347 } 00348 00349 /// GetOrCreateValue - Look up the specified key in the table. If a value 00350 /// exists, return it. Otherwise, default construct a value, insert it, and 00351 /// return. 00352 template <typename InitTy> 00353 StringMapEntry<ValueTy> &GetOrCreateValue(const StringRef &Key, 00354 InitTy Val) { 00355 unsigned BucketNo = LookupBucketFor(Key); 00356 ItemBucket &Bucket = TheTable[BucketNo]; 00357 if (Bucket.Item && Bucket.Item != getTombstoneVal()) 00358 return *static_cast<MapEntryTy*>(Bucket.Item); 00359 00360 MapEntryTy *NewItem = 00361 MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); 00362 00363 if (Bucket.Item == getTombstoneVal()) 00364 --NumTombstones; 00365 ++NumItems; 00366 00367 // Fill in the bucket for the hash table. The FullHashValue was already 00368 // filled in by LookupBucketFor. 00369 Bucket.Item = NewItem; 00370 00371 if (ShouldRehash()) 00372 RehashTable(); 00373 return *NewItem; 00374 } 00375 00376 StringMapEntry<ValueTy> &GetOrCreateValue(const StringRef &Key) { 00377 return GetOrCreateValue(Key, ValueTy()); 00378 } 00379 00380 template <typename InitTy> 00381 StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, 00382 const char *KeyEnd, 00383 InitTy Val) { 00384 return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart), Val); 00385 } 00386 00387 StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, 00388 const char *KeyEnd) { 00389 return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart)); 00390 } 00391 00392 /// remove - Remove the specified key/value pair from the map, but do not 00393 /// erase it. This aborts if the key is not in the map. 00394 void remove(MapEntryTy *KeyValue) { 00395 RemoveKey(KeyValue); 00396 } 00397 00398 void erase(iterator I) { 00399 MapEntryTy &V = *I; 00400 remove(&V); 00401 V.Destroy(Allocator); 00402 } 00403 00404 bool erase(const StringRef &Key) { 00405 iterator I = find(Key); 00406 if (I == end()) return false; 00407 erase(I); 00408 return true; 00409 } 00410 00411 ~StringMap() { 00412 clear(); 00413 free(TheTable); 00414 } 00415 }; 00416 00417 00418 template<typename ValueTy> 00419 class StringMapConstIterator { 00420 protected: 00421 StringMapImpl::ItemBucket *Ptr; 00422 public: 00423 typedef StringMapEntry<ValueTy> value_type; 00424 00425 explicit StringMapConstIterator(StringMapImpl::ItemBucket *Bucket, 00426 bool NoAdvance = false) 00427 : Ptr(Bucket) { 00428 if (!NoAdvance) AdvancePastEmptyBuckets(); 00429 } 00430 00431 const value_type &operator*() const { 00432 return *static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 00433 } 00434 const value_type *operator->() const { 00435 return static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); 00436 } 00437 00438 bool operator==(const StringMapConstIterator &RHS) const { 00439 return Ptr == RHS.Ptr; 00440 } 00441 bool operator!=(const StringMapConstIterator &RHS) const { 00442 return Ptr != RHS.Ptr; 00443 } 00444 00445 inline StringMapConstIterator& operator++() { // Preincrement 00446 ++Ptr; 00447 AdvancePastEmptyBuckets(); 00448 return *this; 00449 } 00450 StringMapConstIterator operator++(int) { // Postincrement 00451 StringMapConstIterator tmp = *this; ++*this; return tmp; 00452 } 00453 00454 private: 00455 void AdvancePastEmptyBuckets() { 00456 while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal()) 00457 ++Ptr; 00458 } 00459 }; 00460 00461 template<typename ValueTy> 00462 class StringMapIterator : public StringMapConstIterator<ValueTy> { 00463 public: 00464 explicit StringMapIterator(StringMapImpl::ItemBucket *Bucket, 00465 bool NoAdvance = false) 00466 : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 00467 } 00468 StringMapEntry<ValueTy> &operator*() const { 00469 return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 00470 } 00471 StringMapEntry<ValueTy> *operator->() const { 00472 return static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); 00473 } 00474 }; 00475 00476 } 00477 00478 #endif