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