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