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