Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

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