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