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 (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
 446       this->grow(NumBuckets * 2);
 447       LookupBucketFor(Key, TheBucket);
 448       NumBuckets = getNumBuckets();
 449     } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
 450                              NumBuckets/8)) {
 451       this->grow(NumBuckets);
 452       LookupBucketFor(Key, TheBucket);
 453     }
 454     assert(TheBucket);
 455
 456     // Only update the state after we've grown our bucket space appropriately
 457     // so that when growing buckets we have self-consistent entry count.
 458     incrementNumEntries();
 459
 460     // If we are writing over a tombstone, remember this.
 461     const KeyT EmptyKey = getEmptyKey();
 462     if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
 463       decrementNumTombstones();
 464
 465     return TheBucket;
 466   }
 467
 468   /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
 469   /// FoundBucket.  If the bucket contains the key and a value, this returns
 470   /// true, otherwise it returns a bucket with an empty marker or tombstone and
 471   /// returns false.
 472   template<typename LookupKeyT>
 473   bool LookupBucketFor(const LookupKeyT &Val,
 474                        const BucketT *&FoundBucket) const {
 475     const BucketT *BucketsPtr = getBuckets();
 476     const unsigned NumBuckets = getNumBuckets();
 477
 478     if (NumBuckets == 0) {
 479       FoundBucket = nullptr;
 480       return false;
 481     }
 482
 483     // FoundTombstone - Keep track of whether we find a tombstone while probing.
 484     const BucketT *FoundTombstone = nullptr;
 485     const KeyT EmptyKey = getEmptyKey();
 486     const KeyT TombstoneKey = getTombstoneKey();
 487     assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
 488            !KeyInfoT::isEqual(Val, TombstoneKey) &&
 489            "Empty/Tombstone value shouldn't be inserted into map!");
 490
 491     unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
 492     unsigned ProbeAmt = 1;
 493     while (1) {
 494       const BucketT *ThisBucket = BucketsPtr + BucketNo;
 495       // Found Val's bucket?  If so, return it.
 496       if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
 497         FoundBucket = ThisBucket;
 498         return true;
 499       }
 500
 501       // If we found an empty bucket, the key doesn't exist in the set.
 502       // Insert it and return the default value.
 503       if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
 504         // If we've already seen a tombstone while probing, fill it in instead
 505         // of the empty bucket we eventually probed to.
 506         FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
 507         return false;
 508       }
 509
 510       // If this is a tombstone, remember it.  If Val ends up not in the map, we
 511       // prefer to return it than something that would require more probing.
 512       if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
 513           !FoundTombstone)
 514         FoundTombstone = ThisBucket;  // Remember the first tombstone found.
 515
 516       // Otherwise, it's a hash collision or a tombstone, continue quadratic
 517       // probing.
 518       BucketNo += ProbeAmt++;
 519       BucketNo &= (NumBuckets-1);
 520     }
 521   }
 522
 523   template <typename LookupKeyT>
 524   bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
 525     const BucketT *ConstFoundBucket;
 526     bool Result = const_cast<const DenseMapBase *>(this)
 527       ->LookupBucketFor(Val, ConstFoundBucket);
 528     FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
 529     return Result;
 530   }
 531
 532 public:
 533   /// Return the approximate size (in bytes) of the actual map.
 534   /// This is just the raw memory used by DenseMap.
 535   /// If entries are pointers to objects, the size of the referenced objects
 536   /// are not included.
 537   size_t getMemorySize() const {
 538     return getNumBuckets() * sizeof(BucketT);
 539   }
 540 };
 541
 542 template <typename KeyT, typename ValueT,
 543           typename KeyInfoT = DenseMapInfo<KeyT>,
 544           typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
 545 class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
 546                                      KeyT, ValueT, KeyInfoT, BucketT> {
 547   // Lift some types from the dependent base class into this class for
 548   // simplicity of referring to them.
 549   typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT> BaseT;
 550   friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
 551
 552   BucketT *Buckets;
 553   unsigned NumEntries;
 554   unsigned NumTombstones;
 555   unsigned NumBuckets;
 556
 557 public:
 558   explicit DenseMap(unsigned NumInitBuckets = 0) {
 559     init(NumInitBuckets);
 560   }
 561
 562   DenseMap(const DenseMap &other) : BaseT() {
 563     init(0);
 564     copyFrom(other);
 565   }
 566
 567   DenseMap(DenseMap &&other) : BaseT() {
 568     init(0);
 569     swap(other);
 570   }
 571
 572   template<typename InputIt>
 573   DenseMap(const InputIt &I, const InputIt &E) {
 574     init(NextPowerOf2(std::distance(I, E)));
 575     this->insert(I, E);
 576   }
 577
 578   ~DenseMap() {
 579     this->destroyAll();
 580     operator delete(Buckets);
 581   }
 582
 583   void swap(DenseMap& RHS) {
 584     std::swap(Buckets, RHS.Buckets);
 585     std::swap(NumEntries, RHS.NumEntries);
 586     std::swap(NumTombstones, RHS.NumTombstones);
 587     std::swap(NumBuckets, RHS.NumBuckets);
 588   }
 589
 590   DenseMap& operator=(const DenseMap& other) {
 591     if (&other != this)
 592       copyFrom(other);
 593     return *this;
 594   }
 595
 596   DenseMap& operator=(DenseMap &&other) {
 597     this->destroyAll();
 598     operator delete(Buckets);
 599     init(0);
 600     swap(other);
 601     return *this;
 602   }
 603
 604   void copyFrom(const DenseMap& other) {
 605     this->destroyAll();
 606     operator delete(Buckets);
 607     if (allocateBuckets(other.NumBuckets)) {
 608       this->BaseT::copyFrom(other);
 609     } else {
 610       NumEntries = 0;
 611       NumTombstones = 0;
 612     }
 613   }
 614
 615   void init(unsigned InitBuckets) {
 616     if (allocateBuckets(InitBuckets)) {
 617       this->BaseT::initEmpty();
 618     } else {
 619       NumEntries = 0;
 620       NumTombstones = 0;
 621     }
 622   }
 623
 624   void grow(unsigned AtLeast) {
 625     unsigned OldNumBuckets = NumBuckets;
 626     BucketT *OldBuckets = Buckets;
 627
 628     allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1))));
 629     assert(Buckets);
 630     if (!OldBuckets) {
 631       this->BaseT::initEmpty();
 632       return;
 633     }
 634
 635     this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
 636
 637     // Free the old table.
 638     operator delete(OldBuckets);
 639   }
 640
 641   void shrink_and_clear() {
 642     unsigned OldNumEntries = NumEntries;
 643     this->destroyAll();
 644
 645     // Reduce the number of buckets.
 646     unsigned NewNumBuckets = 0;
 647     if (OldNumEntries)
 648       NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1));
 649     if (NewNumBuckets == NumBuckets) {
 650       this->BaseT::initEmpty();
 651       return;
 652     }
 653
 654     operator delete(Buckets);
 655     init(NewNumBuckets);
 656   }
 657
 658 private:
 659   unsigned getNumEntries() const {
 660     return NumEntries;
 661   }
 662   void setNumEntries(unsigned Num) {
 663     NumEntries = Num;
 664   }
 665
 666   unsigned getNumTombstones() const {
 667     return NumTombstones;
 668   }
 669   void setNumTombstones(unsigned Num) {
 670     NumTombstones = Num;
 671   }
 672
 673   BucketT *getBuckets() const {
 674     return Buckets;
 675   }
 676
 677   unsigned getNumBuckets() const {
 678     return NumBuckets;
 679   }
 680
 681   bool allocateBuckets(unsigned Num) {
 682     NumBuckets = Num;
 683     if (NumBuckets == 0) {
 684       Buckets = nullptr;
 685       return false;
 686     }
 687
 688     Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets));
 689     return true;
 690   }
 691 };
 692
 693 template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4,
 694           typename KeyInfoT = DenseMapInfo<KeyT>,
 695           typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
 696 class SmallDenseMap
 697     : public DenseMapBase<
 698           SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
 699           ValueT, KeyInfoT, BucketT> {
 700   // Lift some types from the dependent base class into this class for
 701   // simplicity of referring to them.
 702   typedef DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT> BaseT;
 703   friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
 704
 705   unsigned Small : 1;
 706   unsigned NumEntries : 31;
 707   unsigned NumTombstones;
 708
 709   struct LargeRep {
 710     BucketT *Buckets;
 711     unsigned NumBuckets;
 712   };
 713
 714   /// A "union" of an inline bucket array and the struct representing
 715   /// a large bucket. This union will be discriminated by the 'Small' bit.
 716   AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;
 717
 718 public:
 719   explicit SmallDenseMap(unsigned NumInitBuckets = 0) {
 720     init(NumInitBuckets);
 721   }
 722
 723   SmallDenseMap(const SmallDenseMap &other) : BaseT() {
 724     init(0);
 725     copyFrom(other);
 726   }
 727
 728   SmallDenseMap(SmallDenseMap &&other) : BaseT() {
 729     init(0);
 730     swap(other);
 731   }
 732
 733   template<typename InputIt>
 734   SmallDenseMap(const InputIt &I, const InputIt &E) {
 735     init(NextPowerOf2(std::distance(I, E)));
 736     this->insert(I, E);
 737   }
 738
 739   ~SmallDenseMap() {
 740     this->destroyAll();
 741     deallocateBuckets();
 742   }
 743
 744   void swap(SmallDenseMap& RHS) {
 745     unsigned TmpNumEntries = RHS.NumEntries;
 746     RHS.NumEntries = NumEntries;
 747     NumEntries = TmpNumEntries;
 748     std::swap(NumTombstones, RHS.NumTombstones);
 749
 750     const KeyT EmptyKey = this->getEmptyKey();
 751     const KeyT TombstoneKey = this->getTombstoneKey();
 752     if (Small && RHS.Small) {
 753       // If we're swapping inline bucket arrays, we have to cope with some of
 754       // the tricky bits of DenseMap's storage system: the buckets are not
 755       // fully initialized. Thus we swap every key, but we may have
 756       // a one-directional move of the value.
 757       for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
 758         BucketT *LHSB = &getInlineBuckets()[i],
 759                 *RHSB = &RHS.getInlineBuckets()[i];
 760         bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&
 761                             !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));
 762         bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&
 763                             !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));
 764         if (hasLHSValue && hasRHSValue) {
 765           // Swap together if we can...
 766           std::swap(*LHSB, *RHSB);
 767           continue;
 768         }
 769         // Swap separately and handle any assymetry.
 770         std::swap(LHSB->getFirst(), RHSB->getFirst());
 771         if (hasLHSValue) {
 772           new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
 773           LHSB->getSecond().~ValueT();
 774         } else if (hasRHSValue) {
 775           new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
 776           RHSB->getSecond().~ValueT();
 777         }
 778       }
 779       return;
 780     }
 781     if (!Small && !RHS.Small) {
 782       std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets);
 783       std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets);
 784       return;
 785     }
 786
 787     SmallDenseMap &SmallSide = Small ? *this : RHS;
 788     SmallDenseMap &LargeSide = Small ? RHS : *this;
 789
 790     // First stash the large side's rep and move the small side across.
 791     LargeRep TmpRep = std::move(*LargeSide.getLargeRep());
 792     LargeSide.getLargeRep()->~LargeRep();
 793     LargeSide.Small = true;
 794     // This is similar to the standard move-from-old-buckets, but the bucket
 795     // count hasn't actually rotated in this case. So we have to carefully
 796     // move construct the keys and values into their new locations, but there
 797     // is no need to re-hash things.
 798     for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
 799       BucketT *NewB = &LargeSide.getInlineBuckets()[i],
 800               *OldB = &SmallSide.getInlineBuckets()[i];
 801       new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
 802       OldB->getFirst().~KeyT();
 803       if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
 804           !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
 805         new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
 806         OldB->getSecond().~ValueT();
 807       }
 808     }
 809
 810     // The hard part of moving the small buckets across is done, just move
 811     // the TmpRep into its new home.
 812     SmallSide.Small = false;
 813     new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
 814   }
 815
 816   SmallDenseMap& operator=(const SmallDenseMap& other) {
 817     if (&other != this)
 818       copyFrom(other);
 819     return *this;
 820   }
 821
 822   SmallDenseMap& operator=(SmallDenseMap &&other) {
 823     this->destroyAll();
 824     deallocateBuckets();
 825     init(0);
 826     swap(other);
 827     return *this;
 828   }
 829
 830   void copyFrom(const SmallDenseMap& other) {
 831     this->destroyAll();
 832     deallocateBuckets();
 833     Small = true;
 834     if (other.getNumBuckets() > InlineBuckets) {
 835       Small = false;
 836       new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets()));
 837     }
 838     this->BaseT::copyFrom(other);
 839   }
 840
 841   void init(unsigned InitBuckets) {
 842     Small = true;
 843     if (InitBuckets > InlineBuckets) {
 844       Small = false;
 845       new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets));
 846     }
 847     this->BaseT::initEmpty();
 848   }
 849
 850   void grow(unsigned AtLeast) {
 851     if (AtLeast >= InlineBuckets)
 852       AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1));
 853
 854     if (Small) {
 855       if (AtLeast < InlineBuckets)
 856         return; // Nothing to do.
 857
 858       // First move the inline buckets into a temporary storage.
 859       AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage;
 860       BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer);
 861       BucketT *TmpEnd = TmpBegin;
 862
 863       // Loop over the buckets, moving non-empty, non-tombstones into the
 864       // temporary storage. Have the loop move the TmpEnd forward as it goes.
 865       const KeyT EmptyKey = this->getEmptyKey();
 866       const KeyT TombstoneKey = this->getTombstoneKey();
 867       for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) {
 868         if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
 869             !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
 870           assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&
 871                  "Too many inline buckets!");
 872           new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
 873           new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
 874           ++TmpEnd;
 875           P->getSecond().~ValueT();
 876         }
 877         P->getFirst().~KeyT();
 878       }
 879
 880       // Now make this map use the large rep, and move all the entries back
 881       // into it.
 882       Small = false;
 883       new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
 884       this->moveFromOldBuckets(TmpBegin, TmpEnd);
 885       return;
 886     }
 887
 888     LargeRep OldRep = std::move(*getLargeRep());
 889     getLargeRep()->~LargeRep();
 890     if (AtLeast <= InlineBuckets) {
 891       Small = true;
 892     } else {
 893       new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
 894     }
 895
 896     this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets);
 897
 898     // Free the old table.
 899     operator delete(OldRep.Buckets);
 900   }
 901
 902   void shrink_and_clear() {
 903     unsigned OldSize = this->size();
 904     this->destroyAll();
 905
 906     // Reduce the number of buckets.
 907     unsigned NewNumBuckets = 0;
 908     if (OldSize) {
 909       NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1);
 910       if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)
 911         NewNumBuckets = 64;
 912     }
 913     if ((Small && NewNumBuckets <= InlineBuckets) ||
 914         (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {
 915       this->BaseT::initEmpty();
 916       return;
 917     }
 918
 919     deallocateBuckets();
 920     init(NewNumBuckets);
 921   }
 922
 923 private:
 924   unsigned getNumEntries() const {
 925     return NumEntries;
 926   }
 927   void setNumEntries(unsigned Num) {
 928     assert(Num < INT_MAX && "Cannot support more than INT_MAX entries");
 929     NumEntries = Num;
 930   }
 931
 932   unsigned getNumTombstones() const {
 933     return NumTombstones;
 934   }
 935   void setNumTombstones(unsigned Num) {
 936     NumTombstones = Num;
 937   }
 938
 939   const BucketT *getInlineBuckets() const {
 940     assert(Small);
 941     // Note that this cast does not violate aliasing rules as we assert that
 942     // the memory's dynamic type is the small, inline bucket buffer, and the
 943     // 'storage.buffer' static type is 'char *'.
 944     return reinterpret_cast<const BucketT *>(storage.buffer);
 945   }
 946   BucketT *getInlineBuckets() {
 947     return const_cast<BucketT *>(
 948       const_cast<const SmallDenseMap *>(this)->getInlineBuckets());
 949   }
 950   const LargeRep *getLargeRep() const {
 951     assert(!Small);
 952     // Note, same rule about aliasing as with getInlineBuckets.
 953     return reinterpret_cast<const LargeRep *>(storage.buffer);
 954   }
 955   LargeRep *getLargeRep() {
 956     return const_cast<LargeRep *>(
 957       const_cast<const SmallDenseMap *>(this)->getLargeRep());
 958   }
 959
 960   const BucketT *getBuckets() const {
 961     return Small ? getInlineBuckets() : getLargeRep()->Buckets;
 962   }
 963   BucketT *getBuckets() {
 964     return const_cast<BucketT *>(
 965       const_cast<const SmallDenseMap *>(this)->getBuckets());
 966   }
 967   unsigned getNumBuckets() const {
 968     return Small ? InlineBuckets : getLargeRep()->NumBuckets;
 969   }
 970
 971   void deallocateBuckets() {
 972     if (Small)
 973       return;
 974
 975     operator delete(getLargeRep()->Buckets);
 976     getLargeRep()->~LargeRep();
 977   }
 978
 979   LargeRep allocateBuckets(unsigned Num) {
 980     assert(Num > InlineBuckets && "Must allocate more buckets than are inline");
 981     LargeRep Rep = {
 982       static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num
 983     };
 984     return Rep;
 985   }
 986 };
 987
 988 template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
 989           bool IsConst>
 990 class DenseMapIterator {
 991   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true> ConstIterator;
 992   friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
 993
 994 public:
 995   typedef ptrdiff_t difference_type;
 996   typedef typename std::conditional<IsConst, const Bucket, Bucket>::type
 997   value_type;
 998   typedef value_type *pointer;
 999   typedef value_type &reference;
1000   typedef std::forward_iterator_tag iterator_category;
1001 private:
1002   pointer Ptr, End;
1003 public:
1004   DenseMapIterator() : Ptr(nullptr), End(nullptr) {}
1005
1006   DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false)
1007     : Ptr(Pos), End(E) {
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       : Ptr(I.Ptr), End(I.End) {}
1019
1020   reference operator*() const {
1021     return *Ptr;
1022   }
1023   pointer operator->() const {
1024     return Ptr;
1025   }
1026
1027   bool operator==(const ConstIterator &RHS) const {
1028     return Ptr == RHS.operator->();
1029   }
1030   bool operator!=(const ConstIterator &RHS) const {
1031     return Ptr != RHS.operator->();
1032   }
1033
1034   inline DenseMapIterator& operator++() {  // Preincrement
1035     ++Ptr;
1036     AdvancePastEmptyBuckets();
1037     return *this;
1038   }
1039   DenseMapIterator operator++(int) {  // Postincrement
1040     DenseMapIterator tmp = *this; ++*this; return tmp;
1041   }
1042
1043 private:
1044   void AdvancePastEmptyBuckets() {
1045     const KeyT Empty = KeyInfoT::getEmptyKey();
1046     const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1047
1048     while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
1049                           KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
1050       ++Ptr;
1051   }
1052 };
1053
1054 template<typename KeyT, typename ValueT, typename KeyInfoT>
1055 static inline size_t
1056 capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) {
1057   return X.getMemorySize();
1058 }
1059
1060 } // end namespace llvm
1061
1062 #endif