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