1//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- 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 DenseMap class. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ADT_DENSEMAP_H 15#define LLVM_ADT_DENSEMAP_H 16 17#include "llvm/ADT/DenseMapInfo.h" 18#include "llvm/ADT/EpochTracker.h" 19#include "llvm/Support/AlignOf.h" 20#include "llvm/Support/Compiler.h" 21#include "llvm/Support/MathExtras.h" 22#include "llvm/Support/type_traits.h" 23#include <algorithm> 24#include <cassert> 25#include <cstddef> 26#include <cstring> 27#include <iterator> 28#include <new> 29#include <type_traits> 30#include <utility> 31 32namespace llvm { 33 34namespace detail { 35 36// We extend a pair to allow users to override the bucket type with their own 37// implementation without requiring two members. 38template <typename KeyT, typename ValueT> 39struct DenseMapPair : public std::pair<KeyT, ValueT> { 40 KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; } 41 const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; } 42 ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; } 43 const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; } 44}; 45 46} // end namespace detail 47 48template < 49 typename KeyT, typename ValueT, typename KeyInfoT = DenseMapInfo<KeyT>, 50 typename Bucket = detail::DenseMapPair<KeyT, ValueT>, bool IsConst = false> 51class DenseMapIterator; 52 53template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, 54 typename BucketT> 55class DenseMapBase : public DebugEpochBase { 56 template <typename T> 57 using const_arg_type_t = typename const_pointer_or_const_ref<T>::type; 58 59public: 60 using size_type = unsigned; 61 using key_type = KeyT; 62 using mapped_type = ValueT; 63 using value_type = BucketT; 64 65 using iterator = DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT>; 66 using const_iterator = 67 DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>; 68 69 inline iterator begin() { 70 // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). 71 return empty() ? end() : iterator(getBuckets(), getBucketsEnd(), *this); 72 } 73 inline iterator end() { 74 return iterator(getBucketsEnd(), getBucketsEnd(), *this, true); 75 } 76 inline const_iterator begin() const { 77 return empty() ? end() 78 : const_iterator(getBuckets(), getBucketsEnd(), *this); 79 } 80 inline const_iterator end() const { 81 return const_iterator(getBucketsEnd(), getBucketsEnd(), *this, true); 82 } 83 84 LLVM_NODISCARD bool empty() const { 85 return getNumEntries() == 0; 86 } 87 unsigned size() const { return getNumEntries(); } 88 89 /// Grow the densemap so that it can contain at least \p NumEntries items 90 /// before resizing again. 91 void reserve(size_type NumEntries) { 92 auto NumBuckets = getMinBucketToReserveForEntries(NumEntries); 93 incrementEpoch(); 94 if (NumBuckets > getNumBuckets()) 95 grow(NumBuckets); 96 } 97 98 void clear() { 99 incrementEpoch(); 100 if (getNumEntries() == 0 && getNumTombstones() == 0) return; 101 102 // If the capacity of the array is huge, and the # elements used is small, 103 // shrink the array. 104 if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { 105 shrink_and_clear(); 106 return; 107 } 108 109 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 110 unsigned NumEntries = getNumEntries(); 111 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 112 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) { 113 if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { 114 P->getSecond().~ValueT(); 115 --NumEntries; 116 } 117 P->getFirst() = EmptyKey; 118 } 119 } 120 assert(NumEntries == 0 && "Node count imbalance!"); 121 setNumEntries(0); 122 setNumTombstones(0); 123 } 124 125 /// Return 1 if the specified key is in the map, 0 otherwise. 126 size_type count(const_arg_type_t<KeyT> Val) const { 127 const BucketT *TheBucket; 128 return LookupBucketFor(Val, TheBucket) ? 1 : 0; 129 } 130 131 iterator find(const_arg_type_t<KeyT> Val) { 132 BucketT *TheBucket; 133 if (LookupBucketFor(Val, TheBucket)) 134 return iterator(TheBucket, getBucketsEnd(), *this, true); 135 return end(); 136 } 137 const_iterator find(const_arg_type_t<KeyT> Val) const { 138 const BucketT *TheBucket; 139 if (LookupBucketFor(Val, TheBucket)) 140 return const_iterator(TheBucket, getBucketsEnd(), *this, true); 141 return end(); 142 } 143 144 /// Alternate version of find() which allows a different, and possibly 145 /// less expensive, key type. 146 /// The DenseMapInfo is responsible for supplying methods 147 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key 148 /// type used. 149 template<class LookupKeyT> 150 iterator find_as(const LookupKeyT &Val) { 151 BucketT *TheBucket; 152 if (LookupBucketFor(Val, TheBucket)) 153 return iterator(TheBucket, getBucketsEnd(), *this, true); 154 return end(); 155 } 156 template<class LookupKeyT> 157 const_iterator find_as(const LookupKeyT &Val) const { 158 const BucketT *TheBucket; 159 if (LookupBucketFor(Val, TheBucket)) 160 return const_iterator(TheBucket, getBucketsEnd(), *this, true); 161 return end(); 162 } 163 164 /// lookup - Return the entry for the specified key, or a default 165 /// constructed value if no such entry exists. 166 ValueT lookup(const_arg_type_t<KeyT> Val) const { 167 const BucketT *TheBucket; 168 if (LookupBucketFor(Val, TheBucket)) 169 return TheBucket->getSecond(); 170 return ValueT(); 171 } 172 173 // Inserts key,value pair into the map if the key isn't already in the map. 174 // If the key is already in the map, it returns false and doesn't update the 175 // value. 176 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 177 return try_emplace(KV.first, KV.second); 178 } 179 180 // Inserts key,value pair into the map if the key isn't already in the map. 181 // If the key is already in the map, it returns false and doesn't update the 182 // value. 183 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { 184 return try_emplace(std::move(KV.first), std::move(KV.second)); 185 } 186 187 // Inserts key,value pair into the map if the key isn't already in the map. 188 // The value is constructed in-place if the key is not in the map, otherwise 189 // it is not moved. 190 template <typename... Ts> 191 std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) { 192 BucketT *TheBucket; 193 if (LookupBucketFor(Key, TheBucket)) 194 return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), 195 false); // Already in map. 196 197 // Otherwise, insert the new element. 198 TheBucket = 199 InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...); 200 return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), 201 true); 202 } 203 204 // Inserts key,value pair into the map if the key isn't already in the map. 205 // The value is constructed in-place if the key is not in the map, otherwise 206 // it is not moved. 207 template <typename... Ts> 208 std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) { 209 BucketT *TheBucket; 210 if (LookupBucketFor(Key, TheBucket)) 211 return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), 212 false); // Already in map. 213 214 // Otherwise, insert the new element. 215 TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...); 216 return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), 217 true); 218 } 219 220 /// Alternate version of insert() which allows a different, and possibly 221 /// less expensive, key type. 222 /// The DenseMapInfo is responsible for supplying methods 223 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key 224 /// type used. 225 template <typename LookupKeyT> 226 std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV, 227 const LookupKeyT &Val) { 228 BucketT *TheBucket; 229 if (LookupBucketFor(Val, TheBucket)) 230 return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), 231 false); // Already in map. 232 233 // Otherwise, insert the new element. 234 TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first), 235 std::move(KV.second), Val); 236 return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), 237 true); 238 } 239 240 /// insert - Range insertion of pairs. 241 template<typename InputIt> 242 void insert(InputIt I, InputIt E) { 243 for (; I != E; ++I) 244 insert(*I); 245 } 246 247 bool erase(const KeyT &Val) { 248 BucketT *TheBucket; 249 if (!LookupBucketFor(Val, TheBucket)) 250 return false; // not in map. 251 252 TheBucket->getSecond().~ValueT(); 253 TheBucket->getFirst() = getTombstoneKey(); 254 decrementNumEntries(); 255 incrementNumTombstones(); 256 return true; 257 } 258 void erase(iterator I) { 259 BucketT *TheBucket = &*I; 260 TheBucket->getSecond().~ValueT(); 261 TheBucket->getFirst() = getTombstoneKey(); 262 decrementNumEntries(); 263 incrementNumTombstones(); 264 } 265 266 value_type& FindAndConstruct(const KeyT &Key) { 267 BucketT *TheBucket; 268 if (LookupBucketFor(Key, TheBucket)) 269 return *TheBucket; 270 271 return *InsertIntoBucket(TheBucket, Key); 272 } 273 274 ValueT &operator[](const KeyT &Key) { 275 return FindAndConstruct(Key).second; 276 } 277 278 value_type& FindAndConstruct(KeyT &&Key) { 279 BucketT *TheBucket; 280 if (LookupBucketFor(Key, TheBucket)) 281 return *TheBucket; 282 283 return *InsertIntoBucket(TheBucket, std::move(Key)); 284 } 285 286 ValueT &operator[](KeyT &&Key) { 287 return FindAndConstruct(std::move(Key)).second; 288 } 289 290 /// isPointerIntoBucketsArray - Return true if the specified pointer points 291 /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 292 /// value in the DenseMap). 293 bool isPointerIntoBucketsArray(const void *Ptr) const { 294 return Ptr >= getBuckets() && Ptr < getBucketsEnd(); 295 } 296 297 /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 298 /// array. In conjunction with the previous method, this can be used to 299 /// determine whether an insertion caused the DenseMap to reallocate. 300 const void *getPointerIntoBucketsArray() const { return getBuckets(); } 301 302protected: 303 DenseMapBase() = default; 304 305 void destroyAll() { 306 if (getNumBuckets() == 0) // Nothing to do. 307 return; 308 309 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 310 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 311 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) && 312 !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) 313 P->getSecond().~ValueT(); 314 P->getFirst().~KeyT(); 315 } 316 } 317 318 void initEmpty() { 319 setNumEntries(0); 320 setNumTombstones(0); 321 322 assert((getNumBuckets() & (getNumBuckets()-1)) == 0 && 323 "# initial buckets must be a power of two!"); 324 const KeyT EmptyKey = getEmptyKey(); 325 for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) 326 ::new (&B->getFirst()) KeyT(EmptyKey); 327 } 328 329 /// Returns the number of buckets to allocate to ensure that the DenseMap can 330 /// accommodate \p NumEntries without need to grow(). 331 unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { 332 // Ensure that "NumEntries * 4 < NumBuckets * 3" 333 if (NumEntries == 0) 334 return 0; 335 // +1 is required because of the strict equality. 336 // For example if NumEntries is 48, we need to return 401. 337 return NextPowerOf2(NumEntries * 4 / 3 + 1); 338 } 339 340 void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { 341 initEmpty(); 342 343 // Insert all the old elements. 344 const KeyT EmptyKey = getEmptyKey(); 345 const KeyT TombstoneKey = getTombstoneKey(); 346 for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { 347 if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) && 348 !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) { 349 // Insert the key/value into the new table. 350 BucketT *DestBucket; 351 bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket); 352 (void)FoundVal; // silence warning. 353 assert(!FoundVal && "Key already in new map?"); 354 DestBucket->getFirst() = std::move(B->getFirst()); 355 ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond())); 356 incrementNumEntries(); 357 358 // Free the value. 359 B->getSecond().~ValueT(); 360 } 361 B->getFirst().~KeyT(); 362 } 363 } 364 365 template <typename OtherBaseT> 366 void copyFrom( 367 const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) { 368 assert(&other != this); 369 assert(getNumBuckets() == other.getNumBuckets()); 370 371 setNumEntries(other.getNumEntries()); 372 setNumTombstones(other.getNumTombstones()); 373 374 if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) 375 memcpy(getBuckets(), other.getBuckets(), 376 getNumBuckets() * sizeof(BucketT)); 377 else 378 for (size_t i = 0; i < getNumBuckets(); ++i) { 379 ::new (&getBuckets()[i].getFirst()) 380 KeyT(other.getBuckets()[i].getFirst()); 381 if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) && 382 !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey())) 383 ::new (&getBuckets()[i].getSecond()) 384 ValueT(other.getBuckets()[i].getSecond()); 385 } 386 } 387 388 static unsigned getHashValue(const KeyT &Val) { 389 return KeyInfoT::getHashValue(Val); 390 } 391 392 template<typename LookupKeyT> 393 static unsigned getHashValue(const LookupKeyT &Val) { 394 return KeyInfoT::getHashValue(Val); 395 } 396 397 static const KeyT getEmptyKey() { 398 static_assert(std::is_base_of<DenseMapBase, DerivedT>::value, 399 "Must pass the derived type to this template!"); 400 return KeyInfoT::getEmptyKey(); 401 } 402 403 static const KeyT getTombstoneKey() { 404 return KeyInfoT::getTombstoneKey(); 405 } 406 407private: 408 unsigned getNumEntries() const { 409 return static_cast<const DerivedT *>(this)->getNumEntries(); 410 } 411 412 void setNumEntries(unsigned Num) { 413 static_cast<DerivedT *>(this)->setNumEntries(Num); 414 } 415 416 void incrementNumEntries() { 417 setNumEntries(getNumEntries() + 1); 418 } 419 420 void decrementNumEntries() { 421 setNumEntries(getNumEntries() - 1); 422 } 423 424 unsigned getNumTombstones() const { 425 return static_cast<const DerivedT *>(this)->getNumTombstones(); 426 } 427 428 void setNumTombstones(unsigned Num) { 429 static_cast<DerivedT *>(this)->setNumTombstones(Num); 430 } 431 432 void incrementNumTombstones() { 433 setNumTombstones(getNumTombstones() + 1); 434 } 435 436 void decrementNumTombstones() { 437 setNumTombstones(getNumTombstones() - 1); 438 } 439 440 const BucketT *getBuckets() const { 441 return static_cast<const DerivedT *>(this)->getBuckets(); 442 } 443 444 BucketT *getBuckets() { 445 return static_cast<DerivedT *>(this)->getBuckets(); 446 } 447 448 unsigned getNumBuckets() const { 449 return static_cast<const DerivedT *>(this)->getNumBuckets(); 450 } 451 452 BucketT *getBucketsEnd() { 453 return getBuckets() + getNumBuckets(); 454 } 455 456 const BucketT *getBucketsEnd() const { 457 return getBuckets() + getNumBuckets(); 458 } 459 460 void grow(unsigned AtLeast) { 461 static_cast<DerivedT *>(this)->grow(AtLeast); 462 } 463 464 void shrink_and_clear() { 465 static_cast<DerivedT *>(this)->shrink_and_clear(); 466 } 467 468 template <typename KeyArg, typename... ValueArgs> 469 BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key, 470 ValueArgs &&... Values) { 471 TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket); 472 473 TheBucket->getFirst() = std::forward<KeyArg>(Key); 474 ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...); 475 return TheBucket; 476 } 477 478 template <typename LookupKeyT> 479 BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key, 480 ValueT &&Value, LookupKeyT &Lookup) { 481 TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket); 482 483 TheBucket->getFirst() = std::move(Key); 484 ::new (&TheBucket->getSecond()) ValueT(std::move(Value)); 485 return TheBucket; 486 } 487 488 template <typename LookupKeyT> 489 BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup, 490 BucketT *TheBucket) { 491 incrementEpoch(); 492 493 // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 494 // the buckets are empty (meaning that many are filled with tombstones), 495 // grow the table. 496 // 497 // The later case is tricky. For example, if we had one empty bucket with 498 // tons of tombstones, failing lookups (e.g. for insertion) would have to 499 // probe almost the entire table until it found the empty bucket. If the 500 // table completely filled with tombstones, no lookup would ever succeed, 501 // causing infinite loops in lookup. 502 unsigned NewNumEntries = getNumEntries() + 1; 503 unsigned NumBuckets = getNumBuckets(); 504 if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) { 505 this->grow(NumBuckets * 2); 506 LookupBucketFor(Lookup, TheBucket); 507 NumBuckets = getNumBuckets(); 508 } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <= 509 NumBuckets/8)) { 510 this->grow(NumBuckets); 511 LookupBucketFor(Lookup, TheBucket); 512 } 513 assert(TheBucket); 514 515 // Only update the state after we've grown our bucket space appropriately 516 // so that when growing buckets we have self-consistent entry count. 517 incrementNumEntries(); 518 519 // If we are writing over a tombstone, remember this. 520 const KeyT EmptyKey = getEmptyKey(); 521 if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey)) 522 decrementNumTombstones(); 523 524 return TheBucket; 525 } 526 527 /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 528 /// FoundBucket. If the bucket contains the key and a value, this returns 529 /// true, otherwise it returns a bucket with an empty marker or tombstone and 530 /// returns false. 531 template<typename LookupKeyT> 532 bool LookupBucketFor(const LookupKeyT &Val, 533 const BucketT *&FoundBucket) const { 534 const BucketT *BucketsPtr = getBuckets(); 535 const unsigned NumBuckets = getNumBuckets(); 536 537 if (NumBuckets == 0) { 538 FoundBucket = nullptr; 539 return false; 540 } 541 542 // FoundTombstone - Keep track of whether we find a tombstone while probing. 543 const BucketT *FoundTombstone = nullptr; 544 const KeyT EmptyKey = getEmptyKey(); 545 const KeyT TombstoneKey = getTombstoneKey(); 546 assert(!KeyInfoT::isEqual(Val, EmptyKey) && 547 !KeyInfoT::isEqual(Val, TombstoneKey) && 548 "Empty/Tombstone value shouldn't be inserted into map!"); 549 550 unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); 551 unsigned ProbeAmt = 1; 552 while (true) { 553 const BucketT *ThisBucket = BucketsPtr + BucketNo; 554 // Found Val's bucket? If so, return it. 555 if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) { 556 FoundBucket = ThisBucket; 557 return true; 558 } 559 560 // If we found an empty bucket, the key doesn't exist in the set. 561 // Insert it and return the default value. 562 if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) { 563 // If we've already seen a tombstone while probing, fill it in instead 564 // of the empty bucket we eventually probed to. 565 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 566 return false; 567 } 568 569 // If this is a tombstone, remember it. If Val ends up not in the map, we 570 // prefer to return it than something that would require more probing. 571 if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) && 572 !FoundTombstone) 573 FoundTombstone = ThisBucket; // Remember the first tombstone found. 574 575 // Otherwise, it's a hash collision or a tombstone, continue quadratic 576 // probing. 577 BucketNo += ProbeAmt++; 578 BucketNo &= (NumBuckets-1); 579 } 580 } 581 582 template <typename LookupKeyT> 583 bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) { 584 const BucketT *ConstFoundBucket; 585 bool Result = const_cast<const DenseMapBase *>(this) 586 ->LookupBucketFor(Val, ConstFoundBucket); 587 FoundBucket = const_cast<BucketT *>(ConstFoundBucket); 588 return Result; 589 } 590 591public: 592 /// Return the approximate size (in bytes) of the actual map. 593 /// This is just the raw memory used by DenseMap. 594 /// If entries are pointers to objects, the size of the referenced objects 595 /// are not included. 596 size_t getMemorySize() const { 597 return getNumBuckets() * sizeof(BucketT); 598 } 599}; 600 601template <typename KeyT, typename ValueT, 602 typename KeyInfoT = DenseMapInfo<KeyT>, 603 typename BucketT = detail::DenseMapPair<KeyT, ValueT>> 604class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>, 605 KeyT, ValueT, KeyInfoT, BucketT> { 606 friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>; 607 608 // Lift some types from the dependent base class into this class for 609 // simplicity of referring to them. 610 using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>; 611 612 BucketT *Buckets; 613 unsigned NumEntries; 614 unsigned NumTombstones; 615 unsigned NumBuckets; 616 617public: 618 /// Create a DenseMap wth an optional \p InitialReserve that guarantee that 619 /// this number of elements can be inserted in the map without grow() 620 explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); } 621 622 DenseMap(const DenseMap &other) : BaseT() { 623 init(0); 624 copyFrom(other); 625 } 626 627 DenseMap(DenseMap &&other) : BaseT() { 628 init(0); 629 swap(other); 630 } 631 632 template<typename InputIt> 633 DenseMap(const InputIt &I, const InputIt &E) { 634 init(std::distance(I, E)); 635 this->insert(I, E); 636 } 637 638 ~DenseMap() { 639 this->destroyAll(); 640 operator delete(Buckets); 641 } 642 643 void swap(DenseMap& RHS) { 644 this->incrementEpoch(); 645 RHS.incrementEpoch(); 646 std::swap(Buckets, RHS.Buckets); 647 std::swap(NumEntries, RHS.NumEntries); 648 std::swap(NumTombstones, RHS.NumTombstones); 649 std::swap(NumBuckets, RHS.NumBuckets); 650 } 651 652 DenseMap& operator=(const DenseMap& other) { 653 if (&other != this) 654 copyFrom(other); 655 return *this; 656 } 657 658 DenseMap& operator=(DenseMap &&other) { 659 this->destroyAll(); 660 operator delete(Buckets); 661 init(0); 662 swap(other); 663 return *this; 664 } 665 666 void copyFrom(const DenseMap& other) { 667 this->destroyAll(); 668 operator delete(Buckets); 669 if (allocateBuckets(other.NumBuckets)) { 670 this->BaseT::copyFrom(other); 671 } else { 672 NumEntries = 0; 673 NumTombstones = 0; 674 } 675 } 676 677 void init(unsigned InitNumEntries) { 678 auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries); 679 if (allocateBuckets(InitBuckets)) { 680 this->BaseT::initEmpty(); 681 } else { 682 NumEntries = 0; 683 NumTombstones = 0; 684 } 685 } 686 687 void grow(unsigned AtLeast) { 688 unsigned OldNumBuckets = NumBuckets; 689 BucketT *OldBuckets = Buckets; 690 691 allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1)))); 692 assert(Buckets); 693 if (!OldBuckets) { 694 this->BaseT::initEmpty(); 695 return; 696 } 697 698 this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); 699 700 // Free the old table. 701 operator delete(OldBuckets); 702 } 703 704 void shrink_and_clear() { 705 unsigned OldNumEntries = NumEntries; 706 this->destroyAll(); 707 708 // Reduce the number of buckets. 709 unsigned NewNumBuckets = 0; 710 if (OldNumEntries) 711 NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); 712 if (NewNumBuckets == NumBuckets) { 713 this->BaseT::initEmpty(); 714 return; 715 } 716 717 operator delete(Buckets); 718 init(NewNumBuckets); 719 } 720 721private: 722 unsigned getNumEntries() const { 723 return NumEntries; 724 } 725 726 void setNumEntries(unsigned Num) { 727 NumEntries = Num; 728 } 729 730 unsigned getNumTombstones() const { 731 return NumTombstones; 732 } 733 734 void setNumTombstones(unsigned Num) { 735 NumTombstones = Num; 736 } 737 738 BucketT *getBuckets() const { 739 return Buckets; 740 } 741 742 unsigned getNumBuckets() const { 743 return NumBuckets; 744 } 745 746 bool allocateBuckets(unsigned Num) { 747 NumBuckets = Num; 748 if (NumBuckets == 0) { 749 Buckets = nullptr; 750 return false; 751 } 752 753 Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 754 return true; 755 } 756}; 757 758template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4, 759 typename KeyInfoT = DenseMapInfo<KeyT>, 760 typename BucketT = detail::DenseMapPair<KeyT, ValueT>> 761class SmallDenseMap 762 : public DenseMapBase< 763 SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT, 764 ValueT, KeyInfoT, BucketT> { 765 friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>; 766 767 // Lift some types from the dependent base class into this class for 768 // simplicity of referring to them. 769 using BaseT = DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>; 770 771 static_assert(isPowerOf2_64(InlineBuckets), 772 "InlineBuckets must be a power of 2."); 773 774 unsigned Small : 1; 775 unsigned NumEntries : 31; 776 unsigned NumTombstones; 777 778 struct LargeRep { 779 BucketT *Buckets; 780 unsigned NumBuckets; 781 }; 782 783 /// A "union" of an inline bucket array and the struct representing 784 /// a large bucket. This union will be discriminated by the 'Small' bit. 785 AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage; 786 787public: 788 explicit SmallDenseMap(unsigned NumInitBuckets = 0) { 789 init(NumInitBuckets); 790 } 791 792 SmallDenseMap(const SmallDenseMap &other) : BaseT() { 793 init(0); 794 copyFrom(other); 795 } 796 797 SmallDenseMap(SmallDenseMap &&other) : BaseT() { 798 init(0); 799 swap(other); 800 } 801 802 template<typename InputIt> 803 SmallDenseMap(const InputIt &I, const InputIt &E) { 804 init(NextPowerOf2(std::distance(I, E))); 805 this->insert(I, E); 806 } 807 808 ~SmallDenseMap() { 809 this->destroyAll(); 810 deallocateBuckets(); 811 } 812 813 void swap(SmallDenseMap& RHS) { 814 unsigned TmpNumEntries = RHS.NumEntries; 815 RHS.NumEntries = NumEntries; 816 NumEntries = TmpNumEntries; 817 std::swap(NumTombstones, RHS.NumTombstones); 818 819 const KeyT EmptyKey = this->getEmptyKey(); 820 const KeyT TombstoneKey = this->getTombstoneKey(); 821 if (Small && RHS.Small) { 822 // If we're swapping inline bucket arrays, we have to cope with some of 823 // the tricky bits of DenseMap's storage system: the buckets are not 824 // fully initialized. Thus we swap every key, but we may have 825 // a one-directional move of the value. 826 for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 827 BucketT *LHSB = &getInlineBuckets()[i], 828 *RHSB = &RHS.getInlineBuckets()[i]; 829 bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) && 830 !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey)); 831 bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) && 832 !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey)); 833 if (hasLHSValue && hasRHSValue) { 834 // Swap together if we can... 835 std::swap(*LHSB, *RHSB); 836 continue; 837 } 838 // Swap separately and handle any assymetry. 839 std::swap(LHSB->getFirst(), RHSB->getFirst()); 840 if (hasLHSValue) { 841 ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond())); 842 LHSB->getSecond().~ValueT(); 843 } else if (hasRHSValue) { 844 ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond())); 845 RHSB->getSecond().~ValueT(); 846 } 847 } 848 return; 849 } 850 if (!Small && !RHS.Small) { 851 std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets); 852 std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets); 853 return; 854 } 855 856 SmallDenseMap &SmallSide = Small ? *this : RHS; 857 SmallDenseMap &LargeSide = Small ? RHS : *this; 858 859 // First stash the large side's rep and move the small side across. 860 LargeRep TmpRep = std::move(*LargeSide.getLargeRep()); 861 LargeSide.getLargeRep()->~LargeRep(); 862 LargeSide.Small = true; 863 // This is similar to the standard move-from-old-buckets, but the bucket 864 // count hasn't actually rotated in this case. So we have to carefully 865 // move construct the keys and values into their new locations, but there 866 // is no need to re-hash things. 867 for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 868 BucketT *NewB = &LargeSide.getInlineBuckets()[i], 869 *OldB = &SmallSide.getInlineBuckets()[i]; 870 ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst())); 871 OldB->getFirst().~KeyT(); 872 if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) && 873 !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) { 874 ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond())); 875 OldB->getSecond().~ValueT(); 876 } 877 } 878 879 // The hard part of moving the small buckets across is done, just move 880 // the TmpRep into its new home. 881 SmallSide.Small = false; 882 new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep)); 883 } 884 885 SmallDenseMap& operator=(const SmallDenseMap& other) { 886 if (&other != this) 887 copyFrom(other); 888 return *this; 889 } 890 891 SmallDenseMap& operator=(SmallDenseMap &&other) { 892 this->destroyAll(); 893 deallocateBuckets(); 894 init(0); 895 swap(other); 896 return *this; 897 } 898 899 void copyFrom(const SmallDenseMap& other) { 900 this->destroyAll(); 901 deallocateBuckets(); 902 Small = true; 903 if (other.getNumBuckets() > InlineBuckets) { 904 Small = false; 905 new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets())); 906 } 907 this->BaseT::copyFrom(other); 908 } 909 910 void init(unsigned InitBuckets) { 911 Small = true; 912 if (InitBuckets > InlineBuckets) { 913 Small = false; 914 new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets)); 915 } 916 this->BaseT::initEmpty(); 917 } 918 919 void grow(unsigned AtLeast) { 920 if (AtLeast >= InlineBuckets) 921 AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1)); 922 923 if (Small) { 924 if (AtLeast < InlineBuckets) 925 return; // Nothing to do. 926 927 // First move the inline buckets into a temporary storage. 928 AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage; 929 BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer); 930 BucketT *TmpEnd = TmpBegin; 931 932 // Loop over the buckets, moving non-empty, non-tombstones into the 933 // temporary storage. Have the loop move the TmpEnd forward as it goes. 934 const KeyT EmptyKey = this->getEmptyKey(); 935 const KeyT TombstoneKey = this->getTombstoneKey(); 936 for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) { 937 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) && 938 !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { 939 assert(size_t(TmpEnd - TmpBegin) < InlineBuckets && 940 "Too many inline buckets!"); 941 ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst())); 942 ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond())); 943 ++TmpEnd; 944 P->getSecond().~ValueT(); 945 } 946 P->getFirst().~KeyT(); 947 } 948 949 // Now make this map use the large rep, and move all the entries back 950 // into it. 951 Small = false; 952 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 953 this->moveFromOldBuckets(TmpBegin, TmpEnd); 954 return; 955 } 956 957 LargeRep OldRep = std::move(*getLargeRep()); 958 getLargeRep()->~LargeRep(); 959 if (AtLeast <= InlineBuckets) { 960 Small = true; 961 } else { 962 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 963 } 964 965 this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets); 966 967 // Free the old table. 968 operator delete(OldRep.Buckets); 969 } 970 971 void shrink_and_clear() { 972 unsigned OldSize = this->size(); 973 this->destroyAll(); 974 975 // Reduce the number of buckets. 976 unsigned NewNumBuckets = 0; 977 if (OldSize) { 978 NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1); 979 if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u) 980 NewNumBuckets = 64; 981 } 982 if ((Small && NewNumBuckets <= InlineBuckets) || 983 (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) { 984 this->BaseT::initEmpty(); 985 return; 986 } 987 988 deallocateBuckets(); 989 init(NewNumBuckets); 990 } 991 992private: 993 unsigned getNumEntries() const { 994 return NumEntries; 995 } 996 997 void setNumEntries(unsigned Num) { 998 // NumEntries is hardcoded to be 31 bits wide. 999 assert(Num < (1U << 31) && "Cannot support more than 1<<31 entries"); 1000 NumEntries = Num; 1001 } 1002 1003 unsigned getNumTombstones() const { 1004 return NumTombstones; 1005 } 1006 1007 void setNumTombstones(unsigned Num) { 1008 NumTombstones = Num; 1009 } 1010 1011 const BucketT *getInlineBuckets() const { 1012 assert(Small); 1013 // Note that this cast does not violate aliasing rules as we assert that 1014 // the memory's dynamic type is the small, inline bucket buffer, and the 1015 // 'storage.buffer' static type is 'char *'. 1016 return reinterpret_cast<const BucketT *>(storage.buffer); 1017 } 1018 1019 BucketT *getInlineBuckets() { 1020 return const_cast<BucketT *>( 1021 const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); 1022 } 1023 1024 const LargeRep *getLargeRep() const { 1025 assert(!Small); 1026 // Note, same rule about aliasing as with getInlineBuckets. 1027 return reinterpret_cast<const LargeRep *>(storage.buffer); 1028 } 1029 1030 LargeRep *getLargeRep() { 1031 return const_cast<LargeRep *>( 1032 const_cast<const SmallDenseMap *>(this)->getLargeRep()); 1033 } 1034 1035 const BucketT *getBuckets() const { 1036 return Small ? getInlineBuckets() : getLargeRep()->Buckets; 1037 } 1038 1039 BucketT *getBuckets() { 1040 return const_cast<BucketT *>( 1041 const_cast<const SmallDenseMap *>(this)->getBuckets()); 1042 } 1043 1044 unsigned getNumBuckets() const { 1045 return Small ? InlineBuckets : getLargeRep()->NumBuckets; 1046 } 1047 1048 void deallocateBuckets() { 1049 if (Small) 1050 return; 1051 1052 operator delete(getLargeRep()->Buckets); 1053 getLargeRep()->~LargeRep(); 1054 } 1055 1056 LargeRep allocateBuckets(unsigned Num) { 1057 assert(Num > InlineBuckets && "Must allocate more buckets than are inline"); 1058 LargeRep Rep = { 1059 static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num 1060 }; 1061 return Rep; 1062 } 1063}; 1064 1065template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket, 1066 bool IsConst> 1067class DenseMapIterator : DebugEpochBase::HandleBase { 1068 friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>; 1069 friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>; 1070 1071 using ConstIterator = DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>; 1072 1073public: 1074 using difference_type = ptrdiff_t; 1075 using value_type = 1076 typename std::conditional<IsConst, const Bucket, Bucket>::type; 1077 using pointer = value_type *; 1078 using reference = value_type &; 1079 using iterator_category = std::forward_iterator_tag; 1080 1081private: 1082 pointer Ptr = nullptr; 1083 pointer End = nullptr; 1084 1085public: 1086 DenseMapIterator() = default; 1087 1088 DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch, 1089 bool NoAdvance = false) 1090 : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { 1091 assert(isHandleInSync() && "invalid construction!"); 1092 if (!NoAdvance) AdvancePastEmptyBuckets(); 1093 } 1094 1095 // Converting ctor from non-const iterators to const iterators. SFINAE'd out 1096 // for const iterator destinations so it doesn't end up as a user defined copy 1097 // constructor. 1098 template <bool IsConstSrc, 1099 typename = typename std::enable_if<!IsConstSrc && IsConst>::type> 1100 DenseMapIterator( 1101 const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I) 1102 : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {} 1103 1104 reference operator*() const { 1105 assert(isHandleInSync() && "invalid iterator access!"); 1106 return *Ptr; 1107 } 1108 pointer operator->() const { 1109 assert(isHandleInSync() && "invalid iterator access!"); 1110 return Ptr; 1111 } 1112 1113 bool operator==(const ConstIterator &RHS) const { 1114 assert((!Ptr || isHandleInSync()) && "handle not in sync!"); 1115 assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!"); 1116 assert(getEpochAddress() == RHS.getEpochAddress() && 1117 "comparing incomparable iterators!"); 1118 return Ptr == RHS.Ptr; 1119 } 1120 bool operator!=(const ConstIterator &RHS) const { 1121 assert((!Ptr || isHandleInSync()) && "handle not in sync!"); 1122 assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!"); 1123 assert(getEpochAddress() == RHS.getEpochAddress() && 1124 "comparing incomparable iterators!"); 1125 return Ptr != RHS.Ptr; 1126 } 1127 1128 inline DenseMapIterator& operator++() { // Preincrement 1129 assert(isHandleInSync() && "invalid iterator access!"); 1130 ++Ptr; 1131 AdvancePastEmptyBuckets(); 1132 return *this; 1133 } 1134 DenseMapIterator operator++(int) { // Postincrement 1135 assert(isHandleInSync() && "invalid iterator access!"); 1136 DenseMapIterator tmp = *this; ++*this; return tmp; 1137 } 1138 1139private: 1140 void AdvancePastEmptyBuckets() { 1141 const KeyT Empty = KeyInfoT::getEmptyKey(); 1142 const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 1143 1144 while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) || 1145 KeyInfoT::isEqual(Ptr->getFirst(), Tombstone))) 1146 ++Ptr; 1147 } 1148}; 1149 1150template<typename KeyT, typename ValueT, typename KeyInfoT> 1151static inline size_t 1152capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { 1153 return X.getMemorySize(); 1154} 1155 1156} // end namespace llvm 1157 1158#endif // LLVM_ADT_DENSEMAP_H 1159