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