1 //===- StringMap.h - String Hash table map interface ------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 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/StringMapEntry.h" 18 #include "llvm/ADT/iterator.h" 19 #include "llvm/Support/AllocatorBase.h" 20 #include "llvm/Support/PointerLikeTypeTraits.h" 21 #include <initializer_list> 22 #include <iterator> 23 24 namespace llvm { 25 26 template <typename ValueTy> class StringMapConstIterator; 27 template <typename ValueTy> class StringMapIterator; 28 template <typename ValueTy> class StringMapKeyIterator; 29 30 /// StringMapImpl - This is the base class of StringMap that is shared among 31 /// all of its instantiations. 32 class StringMapImpl { 33 protected: 34 // Array of NumBuckets pointers to entries, null pointers are holes. 35 // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed 36 // by an array of the actual hash values as unsigned integers. 37 StringMapEntryBase **TheTable = nullptr; 38 unsigned NumBuckets = 0; 39 unsigned NumItems = 0; 40 unsigned NumTombstones = 0; 41 unsigned ItemSize; 42 43 protected: 44 explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) {} 45 StringMapImpl(StringMapImpl &&RHS) 46 : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets), 47 NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones), 48 ItemSize(RHS.ItemSize) { 49 RHS.TheTable = nullptr; 50 RHS.NumBuckets = 0; 51 RHS.NumItems = 0; 52 RHS.NumTombstones = 0; 53 } 54 55 StringMapImpl(unsigned InitSize, unsigned ItemSize); 56 unsigned RehashTable(unsigned BucketNo = 0); 57 58 /// LookupBucketFor - Look up the bucket that the specified string should end 59 /// up in. If it already exists as a key in the map, the Item pointer for the 60 /// specified bucket will be non-null. Otherwise, it will be null. In either 61 /// case, the FullHashValue field of the bucket will be set to the hash value 62 /// of the string. 63 unsigned LookupBucketFor(StringRef Key); 64 65 /// FindKey - Look up the bucket that contains the specified key. If it exists 66 /// in the map, return the bucket number of the key. Otherwise return -1. 67 /// This does not modify the map. 68 int FindKey(StringRef Key) const; 69 70 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not 71 /// delete it. This aborts if the value isn't in the table. 72 void RemoveKey(StringMapEntryBase *V); 73 74 /// RemoveKey - Remove the StringMapEntry for the specified key from the 75 /// table, returning it. If the key is not in the table, this returns null. 76 StringMapEntryBase *RemoveKey(StringRef Key); 77 78 /// Allocate the table with the specified number of buckets and otherwise 79 /// setup the map as empty. 80 void init(unsigned Size); 81 82 public: 83 static constexpr uintptr_t TombstoneIntVal = 84 static_cast<uintptr_t>(-1) 85 << PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable; 86 87 static StringMapEntryBase *getTombstoneVal() { 88 return reinterpret_cast<StringMapEntryBase *>(TombstoneIntVal); 89 } 90 91 unsigned getNumBuckets() const { return NumBuckets; } 92 unsigned getNumItems() const { return NumItems; } 93 94 bool empty() const { return NumItems == 0; } 95 unsigned size() const { return NumItems; } 96 97 void swap(StringMapImpl &Other) { 98 std::swap(TheTable, Other.TheTable); 99 std::swap(NumBuckets, Other.NumBuckets); 100 std::swap(NumItems, Other.NumItems); 101 std::swap(NumTombstones, Other.NumTombstones); 102 } 103 }; 104 105 /// StringMap - This is an unconventional map that is specialized for handling 106 /// keys that are "strings", which are basically ranges of bytes. This does some 107 /// funky memory allocation and hashing things to make it extremely efficient, 108 /// storing the string data *after* the value in the map. 109 template <typename ValueTy, typename AllocatorTy = MallocAllocator> 110 class StringMap : public StringMapImpl, 111 private detail::AllocatorHolder<AllocatorTy> { 112 using AllocTy = detail::AllocatorHolder<AllocatorTy>; 113 114 public: 115 using MapEntryTy = StringMapEntry<ValueTy>; 116 117 StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} 118 119 explicit StringMap(unsigned InitialSize) 120 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} 121 122 explicit StringMap(AllocatorTy A) 123 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), AllocTy(A) {} 124 125 StringMap(unsigned InitialSize, AllocatorTy A) 126 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), 127 AllocTy(A) {} 128 129 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List) 130 : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) { 131 insert(List); 132 } 133 134 StringMap(StringMap &&RHS) 135 : StringMapImpl(std::move(RHS)), AllocTy(std::move(RHS.getAllocator())) {} 136 137 StringMap(const StringMap &RHS) 138 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), 139 AllocTy(RHS.getAllocator()) { 140 if (RHS.empty()) 141 return; 142 143 // Allocate TheTable of the same size as RHS's TheTable, and set the 144 // sentinel appropriately (and NumBuckets). 145 init(RHS.NumBuckets); 146 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1), 147 *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1); 148 149 NumItems = RHS.NumItems; 150 NumTombstones = RHS.NumTombstones; 151 for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 152 StringMapEntryBase *Bucket = RHS.TheTable[I]; 153 if (!Bucket || Bucket == getTombstoneVal()) { 154 TheTable[I] = Bucket; 155 continue; 156 } 157 158 TheTable[I] = MapEntryTy::Create( 159 static_cast<MapEntryTy *>(Bucket)->getKey(), getAllocator(), 160 static_cast<MapEntryTy *>(Bucket)->getValue()); 161 HashTable[I] = RHSHashTable[I]; 162 } 163 164 // Note that here we've copied everything from the RHS into this object, 165 // tombstones included. We could, instead, have re-probed for each key to 166 // instantiate this new object without any tombstone buckets. The 167 // assumption here is that items are rarely deleted from most StringMaps, 168 // and so tombstones are rare, so the cost of re-probing for all inputs is 169 // not worthwhile. 170 } 171 172 StringMap &operator=(StringMap RHS) { 173 StringMapImpl::swap(RHS); 174 std::swap(getAllocator(), RHS.getAllocator()); 175 return *this; 176 } 177 178 ~StringMap() { 179 // Delete all the elements in the map, but don't reset the elements 180 // to default values. This is a copy of clear(), but avoids unnecessary 181 // work not required in the destructor. 182 if (!empty()) { 183 for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 184 StringMapEntryBase *Bucket = TheTable[I]; 185 if (Bucket && Bucket != getTombstoneVal()) { 186 static_cast<MapEntryTy *>(Bucket)->Destroy(getAllocator()); 187 } 188 } 189 } 190 free(TheTable); 191 } 192 193 using AllocTy::getAllocator; 194 195 using key_type = const char *; 196 using mapped_type = ValueTy; 197 using value_type = StringMapEntry<ValueTy>; 198 using size_type = size_t; 199 200 using const_iterator = StringMapConstIterator<ValueTy>; 201 using iterator = StringMapIterator<ValueTy>; 202 203 iterator begin() { return iterator(TheTable, NumBuckets == 0); } 204 iterator end() { return iterator(TheTable + NumBuckets, true); } 205 const_iterator begin() const { 206 return const_iterator(TheTable, NumBuckets == 0); 207 } 208 const_iterator end() const { 209 return const_iterator(TheTable + NumBuckets, true); 210 } 211 212 iterator_range<StringMapKeyIterator<ValueTy>> keys() const { 213 return make_range(StringMapKeyIterator<ValueTy>(begin()), 214 StringMapKeyIterator<ValueTy>(end())); 215 } 216 217 iterator find(StringRef Key) { 218 int Bucket = FindKey(Key); 219 if (Bucket == -1) 220 return end(); 221 return iterator(TheTable + Bucket, true); 222 } 223 224 const_iterator find(StringRef Key) const { 225 int Bucket = FindKey(Key); 226 if (Bucket == -1) 227 return end(); 228 return const_iterator(TheTable + Bucket, true); 229 } 230 231 /// lookup - Return the entry for the specified key, or a default 232 /// constructed value if no such entry exists. 233 ValueTy lookup(StringRef Key) const { 234 const_iterator it = find(Key); 235 if (it != end()) 236 return it->second; 237 return ValueTy(); 238 } 239 240 /// Lookup the ValueTy for the \p Key, or create a default constructed value 241 /// if the key is not in the map. 242 ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; } 243 244 /// count - Return 1 if the element is in the map, 0 otherwise. 245 size_type count(StringRef Key) const { return find(Key) == end() ? 0 : 1; } 246 247 template <typename InputTy> 248 size_type count(const StringMapEntry<InputTy> &MapEntry) const { 249 return count(MapEntry.getKey()); 250 } 251 252 /// equal - check whether both of the containers are equal. 253 bool operator==(const StringMap &RHS) const { 254 if (size() != RHS.size()) 255 return false; 256 257 for (const auto &KeyValue : *this) { 258 auto FindInRHS = RHS.find(KeyValue.getKey()); 259 260 if (FindInRHS == RHS.end()) 261 return false; 262 263 if (!(KeyValue.getValue() == FindInRHS->getValue())) 264 return false; 265 } 266 267 return true; 268 } 269 270 bool operator!=(const StringMap &RHS) const { return !(*this == RHS); } 271 272 /// insert - Insert the specified key/value pair into the map. If the key 273 /// already exists in the map, return false and ignore the request, otherwise 274 /// insert it and return true. 275 bool insert(MapEntryTy *KeyValue) { 276 unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); 277 StringMapEntryBase *&Bucket = TheTable[BucketNo]; 278 if (Bucket && Bucket != getTombstoneVal()) 279 return false; // Already exists in map. 280 281 if (Bucket == getTombstoneVal()) 282 --NumTombstones; 283 Bucket = KeyValue; 284 ++NumItems; 285 assert(NumItems + NumTombstones <= NumBuckets); 286 287 RehashTable(); 288 return true; 289 } 290 291 /// insert - Inserts the specified key/value pair into the map if the key 292 /// isn't already in the map. The bool component of the returned pair is true 293 /// if and only if the insertion takes place, and the iterator component of 294 /// the pair points to the element with key equivalent to the key of the pair. 295 std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) { 296 return try_emplace(KV.first, std::move(KV.second)); 297 } 298 299 /// Inserts elements from range [first, last). If multiple elements in the 300 /// range have keys that compare equivalent, it is unspecified which element 301 /// is inserted . 302 template <typename InputIt> void insert(InputIt First, InputIt Last) { 303 for (InputIt It = First; It != Last; ++It) 304 insert(*It); 305 } 306 307 /// Inserts elements from initializer list ilist. If multiple elements in 308 /// the range have keys that compare equivalent, it is unspecified which 309 /// element is inserted 310 void insert(std::initializer_list<std::pair<StringRef, ValueTy>> List) { 311 insert(List.begin(), List.end()); 312 } 313 314 /// Inserts an element or assigns to the current element if the key already 315 /// exists. The return type is the same as try_emplace. 316 template <typename V> 317 std::pair<iterator, bool> insert_or_assign(StringRef Key, V &&Val) { 318 auto Ret = try_emplace(Key, std::forward<V>(Val)); 319 if (!Ret.second) 320 Ret.first->second = std::forward<V>(Val); 321 return Ret; 322 } 323 324 /// Emplace a new element for the specified key into the map if the key isn't 325 /// already in the map. The bool component of the returned pair is true 326 /// if and only if the insertion takes place, and the iterator component of 327 /// the pair points to the element with key equivalent to the key of the pair. 328 template <typename... ArgsTy> 329 std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) { 330 unsigned BucketNo = LookupBucketFor(Key); 331 StringMapEntryBase *&Bucket = TheTable[BucketNo]; 332 if (Bucket && Bucket != getTombstoneVal()) 333 return std::make_pair(iterator(TheTable + BucketNo, false), 334 false); // Already exists in map. 335 336 if (Bucket == getTombstoneVal()) 337 --NumTombstones; 338 Bucket = 339 MapEntryTy::Create(Key, getAllocator(), std::forward<ArgsTy>(Args)...); 340 ++NumItems; 341 assert(NumItems + NumTombstones <= NumBuckets); 342 343 BucketNo = RehashTable(BucketNo); 344 return std::make_pair(iterator(TheTable + BucketNo, false), true); 345 } 346 347 // clear - Empties out the StringMap 348 void clear() { 349 if (empty()) 350 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(getAllocator()); 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) { RemoveKey(KeyValue); } 369 370 void erase(iterator I) { 371 MapEntryTy &V = *I; 372 remove(&V); 373 V.Destroy(getAllocator()); 374 } 375 376 bool erase(StringRef Key) { 377 iterator I = find(Key); 378 if (I == end()) 379 return false; 380 erase(I); 381 return true; 382 } 383 }; 384 385 template <typename DerivedTy, typename ValueTy> 386 class StringMapIterBase 387 : public iterator_facade_base<DerivedTy, std::forward_iterator_tag, 388 ValueTy> { 389 protected: 390 StringMapEntryBase **Ptr = nullptr; 391 392 public: 393 StringMapIterBase() = default; 394 395 explicit StringMapIterBase(StringMapEntryBase **Bucket, 396 bool NoAdvance = false) 397 : Ptr(Bucket) { 398 if (!NoAdvance) 399 AdvancePastEmptyBuckets(); 400 } 401 402 DerivedTy &operator=(const DerivedTy &Other) { 403 Ptr = Other.Ptr; 404 return static_cast<DerivedTy &>(*this); 405 } 406 407 friend bool operator==(const DerivedTy &LHS, const DerivedTy &RHS) { 408 return LHS.Ptr == RHS.Ptr; 409 } 410 411 DerivedTy &operator++() { // Preincrement 412 ++Ptr; 413 AdvancePastEmptyBuckets(); 414 return static_cast<DerivedTy &>(*this); 415 } 416 417 DerivedTy operator++(int) { // Post-increment 418 DerivedTy Tmp(Ptr); 419 ++*this; 420 return Tmp; 421 } 422 423 private: 424 void AdvancePastEmptyBuckets() { 425 while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) 426 ++Ptr; 427 } 428 }; 429 430 template <typename ValueTy> 431 class StringMapConstIterator 432 : public StringMapIterBase<StringMapConstIterator<ValueTy>, 433 const StringMapEntry<ValueTy>> { 434 using base = StringMapIterBase<StringMapConstIterator<ValueTy>, 435 const StringMapEntry<ValueTy>>; 436 437 public: 438 StringMapConstIterator() = default; 439 explicit StringMapConstIterator(StringMapEntryBase **Bucket, 440 bool NoAdvance = false) 441 : base(Bucket, NoAdvance) {} 442 443 const StringMapEntry<ValueTy> &operator*() const { 444 return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr); 445 } 446 }; 447 448 template <typename ValueTy> 449 class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>, 450 StringMapEntry<ValueTy>> { 451 using base = 452 StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>; 453 454 public: 455 StringMapIterator() = default; 456 explicit StringMapIterator(StringMapEntryBase **Bucket, 457 bool NoAdvance = false) 458 : base(Bucket, NoAdvance) {} 459 460 StringMapEntry<ValueTy> &operator*() const { 461 return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr); 462 } 463 464 operator StringMapConstIterator<ValueTy>() const { 465 return StringMapConstIterator<ValueTy>(this->Ptr, true); 466 } 467 }; 468 469 template <typename ValueTy> 470 class StringMapKeyIterator 471 : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>, 472 StringMapConstIterator<ValueTy>, 473 std::forward_iterator_tag, StringRef> { 474 using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>, 475 StringMapConstIterator<ValueTy>, 476 std::forward_iterator_tag, StringRef>; 477 478 public: 479 StringMapKeyIterator() = default; 480 explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter) 481 : base(std::move(Iter)) {} 482 483 StringRef operator*() const { return this->wrapped()->getKey(); } 484 }; 485 486 } // end namespace llvm 487 488 #endif // LLVM_ADT_STRINGMAP_H 489