include/llvm/ADT/DenseMap.h

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