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 22 namespace 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. 31 class StringMapEntryBase { 32 unsigned StrLen; 33 public: 34 explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} 35 36 unsigned getKeyLength() const { return StrLen; } 37 }; 38 39 /// StringMapImpl - This is the base class of StringMap that is shared among 40 /// all of its instantiations. 41 class StringMapImpl { 42 protected: 43 // Array of NumBuckets pointers to entries, null pointers are holes. 44 // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed 45 // by an array of the actual hash values as unsigned integers. 46 StringMapEntryBase **TheTable; 47 unsigned NumBuckets; 48 unsigned NumItems; 49 unsigned NumTombstones; 50 unsigned ItemSize; 51 protected: 52 explicit StringMapImpl(unsigned itemSize) 53 : TheTable(nullptr), 54 // Initialize the map with zero buckets to allocation. 55 NumBuckets(0), NumItems(0), NumTombstones(0), ItemSize(itemSize) {} 56 StringMapImpl(StringMapImpl &&RHS) 57 : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets), 58 NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones), 59 ItemSize(RHS.ItemSize) { 60 RHS.TheTable = nullptr; 61 RHS.NumBuckets = 0; 62 RHS.NumItems = 0; 63 RHS.NumTombstones = 0; 64 } 65 66 StringMapImpl(unsigned InitSize, unsigned ItemSize); 67 unsigned RehashTable(unsigned BucketNo = 0); 68 69 /// LookupBucketFor - Look up the bucket that the specified string should end 70 /// up in. If it already exists as a key in the map, the Item pointer for the 71 /// specified bucket will be non-null. Otherwise, it will be null. In either 72 /// case, the FullHashValue field of the bucket will be set to the hash value 73 /// of the string. 74 unsigned LookupBucketFor(StringRef Key); 75 76 /// FindKey - Look up the bucket that contains the specified key. If it exists 77 /// in the map, return the bucket number of the key. Otherwise return -1. 78 /// This does not modify the map. 79 int FindKey(StringRef Key) const; 80 81 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 82 /// delete it. This aborts if the value isn't in the table. 83 void RemoveKey(StringMapEntryBase *V); 84 85 /// RemoveKey - Remove the StringMapEntry for the specified key from the 86 /// table, returning it. If the key is not in the table, this returns null. 87 StringMapEntryBase *RemoveKey(StringRef Key); 88 private: 89 void init(unsigned Size); 90 public: 91 static StringMapEntryBase *getTombstoneVal() { 92 return (StringMapEntryBase*)-1; 93 } 94 95 unsigned getNumBuckets() const { return NumBuckets; } 96 unsigned getNumItems() const { return NumItems; } 97 98 bool empty() const { return NumItems == 0; } 99 unsigned size() const { return NumItems; } 100 101 void swap(StringMapImpl &Other) { 102 std::swap(TheTable, Other.TheTable); 103 std::swap(NumBuckets, Other.NumBuckets); 104 std::swap(NumItems, Other.NumItems); 105 std::swap(NumTombstones, Other.NumTombstones); 106 } 107 }; 108 109 /// StringMapEntry - This is used to represent one value that is inserted into 110 /// a StringMap. It contains the Value itself and the key: the string length 111 /// and data. 112 template<typename ValueTy> 113 class StringMapEntry : public StringMapEntryBase { 114 StringMapEntry(StringMapEntry &E) LLVM_DELETED_FUNCTION; 115 public: 116 ValueTy second; 117 118 explicit StringMapEntry(unsigned strLen) 119 : StringMapEntryBase(strLen), second() {} 120 StringMapEntry(unsigned strLen, ValueTy V) 121 : StringMapEntryBase(strLen), second(std::move(V)) {} 122 123 StringRef getKey() const { 124 return StringRef(getKeyData(), getKeyLength()); 125 } 126 127 const ValueTy &getValue() const { return second; } 128 ValueTy &getValue() { return second; } 129 130 void setValue(const ValueTy &V) { second = V; } 131 132 /// getKeyData - Return the start of the string data that is the key for this 133 /// value. The string data is always stored immediately after the 134 /// StringMapEntry object. 135 const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);} 136 137 StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } 138 139 /// Create - Create a StringMapEntry for the specified key and default 140 /// construct the value. 141 template<typename AllocatorTy, typename InitType> 142 static StringMapEntry *Create(StringRef Key, 143 AllocatorTy &Allocator, 144 InitType InitVal) { 145 unsigned KeyLength = Key.size(); 146 147 // Allocate a new item with space for the string at the end and a null 148 // terminator. 149 unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+ 150 KeyLength+1; 151 unsigned Alignment = alignOf<StringMapEntry>(); 152 153 StringMapEntry *NewItem = 154 static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); 155 156 // Default construct the value. 157 new (NewItem) StringMapEntry(KeyLength, std::move(InitVal)); 158 159 // Copy the string information. 160 char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); 161 memcpy(StrBuffer, Key.data(), KeyLength); 162 StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. 163 return NewItem; 164 } 165 166 template<typename AllocatorTy> 167 static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator) { 168 return Create(Key, Allocator, ValueTy()); 169 } 170 171 /// Create - Create a StringMapEntry with normal malloc/free. 172 template<typename InitType> 173 static StringMapEntry *Create(StringRef Key, InitType InitVal) { 174 MallocAllocator A; 175 return Create(Key, A, std::move(InitVal)); 176 } 177 178 static StringMapEntry *Create(StringRef Key) { 179 return Create(Key, ValueTy()); 180 } 181 182 /// GetStringMapEntryFromValue - Given a value that is known to be embedded 183 /// into a StringMapEntry, return the StringMapEntry itself. 184 static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { 185 StringMapEntry *EPtr = 0; 186 char *Ptr = reinterpret_cast<char*>(&V) - 187 (reinterpret_cast<char*>(&EPtr->second) - 188 reinterpret_cast<char*>(EPtr)); 189 return *reinterpret_cast<StringMapEntry*>(Ptr); 190 } 191 static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { 192 return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); 193 } 194 195 /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 196 /// into a StringMapEntry, return the StringMapEntry itself. 197 static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { 198 char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>); 199 return *reinterpret_cast<StringMapEntry*>(Ptr); 200 } 201 202 /// Destroy - Destroy this StringMapEntry, releasing memory back to the 203 /// specified allocator. 204 template<typename AllocatorTy> 205 void Destroy(AllocatorTy &Allocator) { 206 // Free memory referenced by the item. 207 unsigned AllocSize = 208 static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1; 209 this->~StringMapEntry(); 210 Allocator.Deallocate(static_cast<void *>(this), AllocSize); 211 } 212 213 /// Destroy this object, releasing memory back to the malloc allocator. 214 void Destroy() { 215 MallocAllocator A; 216 Destroy(A); 217 } 218 }; 219 220 221 /// StringMap - This is an unconventional map that is specialized for handling 222 /// keys that are "strings", which are basically ranges of bytes. This does some 223 /// funky memory allocation and hashing things to make it extremely efficient, 224 /// storing the string data *after* the value in the map. 225 template<typename ValueTy, typename AllocatorTy = MallocAllocator> 226 class StringMap : public StringMapImpl { 227 AllocatorTy Allocator; 228 public: 229 typedef StringMapEntry<ValueTy> MapEntryTy; 230 231 StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 232 explicit StringMap(unsigned InitialSize) 233 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 234 235 explicit StringMap(AllocatorTy A) 236 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} 237 238 StringMap(unsigned InitialSize, AllocatorTy A) 239 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), 240 Allocator(A) {} 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 GetOrCreateValue(Key).getValue(); 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 /// GetOrCreateValue - Look up the specified key in the table. If a value 367 /// exists, return it. Otherwise, default construct a value, insert it, and 368 /// return. 369 template <typename InitTy> 370 MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { 371 return *insert(std::make_pair(Key, std::move(Val))).first; 372 } 373 374 MapEntryTy &GetOrCreateValue(StringRef Key) { 375 return GetOrCreateValue(Key, ValueTy()); 376 } 377 378 /// remove - Remove the specified key/value pair from the map, but do not 379 /// erase it. This aborts if the key is not in the map. 380 void remove(MapEntryTy *KeyValue) { 381 RemoveKey(KeyValue); 382 } 383 384 void erase(iterator I) { 385 MapEntryTy &V = *I; 386 remove(&V); 387 V.Destroy(Allocator); 388 } 389 390 bool erase(StringRef Key) { 391 iterator I = find(Key); 392 if (I == end()) return false; 393 erase(I); 394 return true; 395 } 396 397 ~StringMap() { 398 // Delete all the elements in the map, but don't reset the elements 399 // to default values. This is a copy of clear(), but avoids unnecessary 400 // work not required in the destructor. 401 if (!empty()) { 402 for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 403 StringMapEntryBase *Bucket = TheTable[I]; 404 if (Bucket && Bucket != getTombstoneVal()) { 405 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); 406 } 407 } 408 } 409 free(TheTable); 410 } 411 }; 412 413 414 template<typename ValueTy> 415 class StringMapConstIterator { 416 protected: 417 StringMapEntryBase **Ptr; 418 public: 419 typedef StringMapEntry<ValueTy> value_type; 420 421 StringMapConstIterator() : Ptr(nullptr) { } 422 423 explicit StringMapConstIterator(StringMapEntryBase **Bucket, 424 bool NoAdvance = false) 425 : Ptr(Bucket) { 426 if (!NoAdvance) AdvancePastEmptyBuckets(); 427 } 428 429 const value_type &operator*() const { 430 return *static_cast<StringMapEntry<ValueTy>*>(*Ptr); 431 } 432 const value_type *operator->() const { 433 return static_cast<StringMapEntry<ValueTy>*>(*Ptr); 434 } 435 436 bool operator==(const StringMapConstIterator &RHS) const { 437 return Ptr == RHS.Ptr; 438 } 439 bool operator!=(const StringMapConstIterator &RHS) const { 440 return Ptr != RHS.Ptr; 441 } 442 443 inline StringMapConstIterator& operator++() { // Preincrement 444 ++Ptr; 445 AdvancePastEmptyBuckets(); 446 return *this; 447 } 448 StringMapConstIterator operator++(int) { // Postincrement 449 StringMapConstIterator tmp = *this; ++*this; return tmp; 450 } 451 452 private: 453 void AdvancePastEmptyBuckets() { 454 while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) 455 ++Ptr; 456 } 457 }; 458 459 template<typename ValueTy> 460 class StringMapIterator : public StringMapConstIterator<ValueTy> { 461 public: 462 StringMapIterator() {} 463 explicit StringMapIterator(StringMapEntryBase **Bucket, 464 bool NoAdvance = false) 465 : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { 466 } 467 StringMapEntry<ValueTy> &operator*() const { 468 return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 469 } 470 StringMapEntry<ValueTy> *operator->() const { 471 return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); 472 } 473 }; 474 475 } 476 477 #endif 478