src/llvm/include/llvm/ADT/DenseMap.h

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