DenseMap.h

Go to the documentation of this file.

//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file defines the DenseMap class.
///
/// The hash table is linear-probing open addressing with tombstone-free
/// deletion (Knuth TAOCP 6.4 Algorithm R), power-of-two capacity, and a 0.75
/// maximum load factor. No sentinel key. Occupancy is stored in a packed
/// 1-bit-per-bucket "used" array.
///
/// `SmallDenseMap` adds an inline small buffer optimization.
///
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_ADT_DENSEMAP_H
#define LLVM_ADT_DENSEMAP_H
 
#include "llvm/ADT/ADL.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/EpochTracker.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/STLForwardCompat.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/MemAlloc.h"
#include "llvm/Support/ReverseIteration.h"
#include "llvm/Support/type_traits.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstring>
#include <initializer_list>
#include <iterator>
#include <new>
#include <type_traits>
#include <utility>
 
namespace llvm {
 
namespace detail {
// A bucket holds a key and a value. Don't use std::pair, which has a
// non-trivial copy assignment, which costs is_trivially_copyable.
template <typename KeyT, typename ValueT> struct DenseMapPair {
  using first_type = KeyT;
  using second_type = ValueT;
 
  KeyT first;
  ValueT second;
 
  DenseMapPair() : first(), second() {}
  DenseMapPair(const KeyT &Key, const ValueT &Value)
      : first(Key), second(Value) {}
  DenseMapPair(KeyT &&Key, ValueT &&Value)
      : first(std::move(Key)), second(std::move(Value)) {}
  DenseMapPair(const std::pair<KeyT, ValueT> &P)
      : first(P.first), second(P.second) {}
  DenseMapPair(std::pair<KeyT, ValueT> &&P)
      : first(std::move(P.first)), second(std::move(P.second)) {}
  template <typename U1, typename U2>
  DenseMapPair(const DenseMapPair<U1, U2> &P)
      : first(P.first), second(P.second) {}
  template <typename U1, typename U2>
  DenseMapPair(DenseMapPair<U1, U2> &&P)
      : first(std::move(P.first)), second(std::move(P.second)) {}
 
  operator std::pair<KeyT, ValueT>() const { return {first, second}; }
  operator std::pair<const KeyT, ValueT>() const { return {first, second}; }
 
  friend bool operator==(const DenseMapPair &LHS, const DenseMapPair &RHS) {
    return LHS.first == RHS.first && LHS.second == RHS.second;
  }
  friend bool operator!=(const DenseMapPair &LHS, const DenseMapPair &RHS) {
    return !(LHS == RHS);
  }
 
  KeyT &getFirst() { return first; }
  const KeyT &getFirst() const { return first; }
  ValueT &getSecond() { return second; }
  const ValueT &getSecond() const { return second; }
};
 
} // end namespace detail
 
namespace densemap::detail {
// Relocating copy-constructs and runs no destructor, so it does not need
// trivial assignment, which a std::pair value type lacks.
template <typename BucketT>
inline constexpr bool isRelocatableBucket =
    std::is_trivially_copy_constructible_v<BucketT> &&
    std::is_trivially_destructible_v<BucketT>;
 
// Move-construct *Dst from *Src, then destroy *Src. Dst is raw storage.
template <typename BucketT> void relocateBucket(BucketT *Dst, BucketT *Src) {
  using KeyT = std::remove_reference_t<decltype(Dst->getFirst())>;
  using ValueT = std::remove_reference_t<decltype(Dst->getSecond())>;
  ::new (&Dst->getFirst()) KeyT(std::move(Src->getFirst()));
  ::new (&Dst->getSecond()) ValueT(std::move(Src->getSecond()));
  Src->getSecond().~ValueT();
  Src->getFirst().~KeyT();
}
 
using UsedT = uint32_t;
 
// Number of used words backing N buckets where N is zero or a power of two.
constexpr size_t usedWords(size_t N) {
  assert((N == 0 || isPowerOf2_64(N)) &&
         "bucket count must be zero or a power of two");
  return (N + 31) / 32;
}
 
inline bool used(const UsedT *U, size_t I) {
  return (U[I >> 5] >> (I & 31)) & 1;
}
inline void setUsed(UsedT *U, size_t I) { U[I >> 5] |= UsedT(1) << (I & 31); }
inline void unsetUsed(UsedT *U, size_t I) {
  U[I >> 5] &= ~(UsedT(1) << (I & 31));
}
inline void clearUsed(UsedT *U, unsigned Num) {
  std::memset(U, 0, usedWords(Num) * sizeof(UsedT));
}
 
// Invoke Func(I) for each occupied bucket index I in [0, N). Set always_inline;
// otherwise, for a heavy caller such as moveFrom's rehash, the inliner can
// leave it out of line and the per-element call dwarfs the work.
template <typename Fn>
LLVM_ATTRIBUTE_ALWAYS_INLINE void forEachUsed(const UsedT *U, unsigned N,
                                              Fn Func) {
  const unsigned NW = usedWords(N);
  for (unsigned W = 0; W != NW; ++W) {
    UsedT Bits = U[W];
    while (Bits) {
      Func((W << 5) + llvm::countr_zero(Bits));
      Bits &= Bits - 1;
    }
  }
}
 
// Buckets and the used array share one allocation: the bucket array first, then
// the used words.  NumBuckets is a power of two >= 4, so the bucket region size
// is a multiple of sizeof(UsedT) and the trailing used words are aligned.
template <typename BucketT> constexpr size_t allocAlign() {
  return std::max(alignof(BucketT), alignof(UsedT));
}
inline size_t allocBytes(size_t BucketSize, unsigned Num) {
  return BucketSize * static_cast<size_t>(Num) + usedWords(Num) * sizeof(UsedT);
}
template <typename BucketT> size_t allocBytes(unsigned Num) {
  return allocBytes(sizeof(BucketT), Num);
}
inline UsedT *usedFor(void *Buckets, size_t BucketSize, unsigned Num) {
  assert(BucketSize * static_cast<size_t>(Num) % alignof(UsedT) == 0 &&
         "used array would be misaligned");
  return reinterpret_cast<UsedT *>(static_cast<char *>(Buckets) +
                                   BucketSize * static_cast<size_t>(Num));
}
 
/// Hashes the key, at offset 0 in a bucket. Null asks the out-of-line rehash
/// loop in DenseMap.cpp to inline the pointer hash.
using BucketHasher = unsigned (*)(const void *Key);
 
// True when the map hashes a pointer key by its value: the primary
// DenseMapInfo<T *> declares PointerValueHash naming itself, which a
// specialization or derived info for one pointer type does not. Only the
// primary is asked, since GCC without DR1170 errors on a lookup that reaches a
// private base, as clang::WeakInfo's info has.
template <typename KeyT, typename KeyInfoT, typename = void>
inline constexpr bool hashesPointerValue = false;
template <typename T>
inline constexpr bool hashesPointerValue<
    T *, DenseMapInfo<T *>,
    std::enable_if_t<std::is_same_v<
        typename DenseMapInfo<T *>::PointerValueHash, DenseMapInfo<T *>>>> =
    true;
 
// Kept out of DenseMapBase so that map types sharing a key share one thunk.
template <typename KeyT, typename KeyInfoT> constexpr BucketHasher hasherFor() {
  if constexpr (hashesPointerValue<KeyT, KeyInfoT>)
    return nullptr;
  else
    return [](const void *Key) -> unsigned {
      return KeyInfoT::getHashValue(*static_cast<const KeyT *>(Key));
    };
}
 
/// Rehash the live buckets of \p Src into the empty \p Dst, which must have
/// room for all of them.
LLVM_ABI void rehashRelocatable(void *Dst, UsedT *DstUsed,
                                unsigned DstNumBuckets, const void *Src,
                                const UsedT *SrcUsed, unsigned SrcNumBuckets,
                                size_t BucketSize, BucketHasher Hasher);
 
/// Allocate a table of \p NewNumBuckets buckets and rehash the \p OldNumBuckets
/// buckets at \p OldBuckets into it, freeing them if \p FreeOld.
LLVM_ABI void *growRelocatable(void *OldBuckets, const UsedT *OldUsed,
                               unsigned OldNumBuckets, unsigned NewNumBuckets,
                               size_t BucketSize, size_t Align,
                               BucketHasher Hasher, bool FreeOld);
 
// A snapshot of the three fields the hot lookup paths need. Fetching them
// together lets SmallDenseMap test its Small discriminator once rather than
// once per accessor; for plain DenseMap it is three member loads either way.
template <typename BucketT> struct StorageRep {
  const BucketT *Buckets;
  const UsedT *Used;
  unsigned NumBuckets;
};
 
template <typename BucketT> class DenseMapStorage {
  BucketT *Buckets = nullptr;
  UsedT *Used = nullptr;
  unsigned NumEntries = 0;
  unsigned NumBuckets = 0;
 
public:
  unsigned getNumEntries() const { return NumEntries; }
  void setNumEntries(unsigned Num) { NumEntries = Num; }
 
  BucketT *getBuckets() const { return Buckets; }
  UsedT *getUsed() const { return Used; }
  unsigned getNumBuckets() const { return NumBuckets; }
  StorageRep<BucketT> getRep() const { return {Buckets, Used, NumBuckets}; }
 
  void swap(DenseMapStorage &RHS) {
    std::swap(Buckets, RHS.Buckets);
    std::swap(Used, RHS.Used);
    std::swap(NumEntries, RHS.NumEntries);
    std::swap(NumBuckets, RHS.NumBuckets);
  }
 
  void setStorage(void *Storage, unsigned Num) {
    Buckets = static_cast<BucketT *>(Storage);
    Used = usedFor(Storage, sizeof(BucketT), Num);
    NumBuckets = Num;
  }
 
  void grow(unsigned MinNumBuckets, BucketHasher Hasher) {
    unsigned NewNumBuckets = roundUpNumBuckets(MinNumBuckets);
    setStorage(growRelocatable(Buckets, Used, NumBuckets, NewNumBuckets,
                               sizeof(BucketT), allocAlign<BucketT>(), Hasher,
                               /*FreeOld=*/true),
               NewNumBuckets);
  }
 
  void deallocateBuckets() {
    if (NumBuckets == 0)
      return;
    deallocate_buffer(Buckets, allocBytes<BucketT>(NumBuckets),
                      allocAlign<BucketT>());
    Buckets = nullptr;
    Used = nullptr;
    NumBuckets = 0;
  }
 
  bool allocateBuckets(unsigned Num) {
    if (Num == 0) {
      Buckets = nullptr;
      Used = nullptr;
      NumBuckets = 0;
      return false;
    }
    setStorage(allocate_buffer(allocBytes<BucketT>(Num), allocAlign<BucketT>()),
               Num);
    return true;
  }
 
  static unsigned roundUpNumBuckets(unsigned MinNumBuckets) {
    return std::max(64u, MinNumBuckets);
  }
 
  // Plan how to shrink the bucket table. Return:
  // - {false, 0} to reuse the existing bucket table
  // - {true, N} to reallocate a bucket table with N entries
  std::pair<bool, unsigned> planShrinkAndClear() const {
    unsigned NewNumBuckets = 0;
    if (NumEntries)
      NewNumBuckets = std::max(64u, 1u << (Log2_32_Ceil(NumEntries) + 1));
    if (NewNumBuckets == NumBuckets)
      return {false, 0};          // Reuse.
    return {true, NewNumBuckets}; // Reallocate.
  }
 
  bool maybeMoveFast(DenseMapStorage &&Other) {
    *this = Other;
    return true;
  }
};
 
template <typename BucketT, unsigned InlineBuckets = 4>
class SmallDenseMapStorage {
  static_assert(isPowerOf2_64(InlineBuckets),
                "InlineBuckets must be a power of 2.");
 
  // Number of used words backing the inline buckets (>= 1).
  static constexpr unsigned InlineUsedWords = usedWords(InlineBuckets);
 
  unsigned Small : 1;
  unsigned NumEntries : 31;
 
  // Inline storage: the bucket array followed by the parallel used words.
  struct InlineRep {
    alignas(BucketT) char Buckets[sizeof(BucketT) * InlineBuckets];
    UsedT Used[InlineUsedWords];
  };
  struct LargeRep {
    BucketT *Buckets;
    UsedT *Used;
    unsigned NumBuckets;
  };
 
  // Discriminated by the Small bit.
  union {
    InlineRep Inline;
    LargeRep Large;
  } storage;
 
  const BucketT *getInlineBuckets() const {
    assert(Small);
    // Note that this cast does not violate aliasing rules as we assert that
    // the memory's dynamic type is the small, inline bucket buffer, and the
    // 'storage' is a POD containing a char buffer.
    return reinterpret_cast<const BucketT *>(storage.Inline.Buckets);
  }
 
  BucketT *getInlineBuckets() {
    assert(Small);
    return reinterpret_cast<BucketT *>(storage.Inline.Buckets);
  }
 
  const UsedT *getInlineUsed() const {
    assert(Small);
    return storage.Inline.Used;
  }
 
  UsedT *getInlineUsed() {
    assert(Small);
    return storage.Inline.Used;
  }
 
  void setLarge(void *Storage, unsigned NumBuckets) {
    Small = false;
    storage.Large = {static_cast<BucketT *>(Storage),
                     usedFor(Storage, sizeof(BucketT), NumBuckets), NumBuckets};
  }
 
public:
  unsigned getNumEntries() const { return NumEntries; }
 
  void setNumEntries(unsigned Num) {
    // NumEntries is hardcoded to be 31 bits wide.
    assert(Num < (1U << 31) && "Cannot support more than 1<<31 entries");
    NumEntries = Num;
  }
 
  const BucketT *getBuckets() const {
    return Small ? getInlineBuckets() : storage.Large.Buckets;
  }
 
  BucketT *getBuckets() {
    return const_cast<BucketT *>(
        const_cast<const SmallDenseMapStorage *>(this)->getBuckets());
  }
 
  const UsedT *getUsed() const {
    return Small ? getInlineUsed() : storage.Large.Used;
  }
 
  UsedT *getUsed() {
    return const_cast<UsedT *>(
        const_cast<const SmallDenseMapStorage *>(this)->getUsed());
  }
 
  unsigned getNumBuckets() const {
    return Small ? InlineBuckets : storage.Large.NumBuckets;
  }
 
  StorageRep<BucketT> getRep() const {
    if (Small)
      return {getInlineBuckets(), getInlineUsed(), InlineBuckets};
    return {storage.Large.Buckets, storage.Large.Used,
            storage.Large.NumBuckets};
  }
 
  void swap(SmallDenseMapStorage &RHS) {
    unsigned TmpNumEntries = RHS.NumEntries;
    RHS.NumEntries = NumEntries;
    NumEntries = TmpNumEntries;
 
    if (Small && RHS.Small) {
      // Both inline: swap the live bucket contents slot by slot, then the used
      // words. Buckets are raw storage, so a value may only move in one
      // direction when exactly one side is occupied.
      UsedT *LU = getInlineUsed(), *RU = RHS.getInlineUsed();
      BucketT *LB = getInlineBuckets(), *RB = RHS.getInlineBuckets();
      for (unsigned I = 0; I != InlineBuckets; ++I) {
        bool L = used(LU, I);
        bool R = used(RU, I);
        if (L && R) {
          // Both occupied: exchange through a temporary.
          alignas(BucketT) char Tmp[sizeof(BucketT)];
          BucketT *T = reinterpret_cast<BucketT *>(Tmp);
          relocateBucket(T, &LB[I]);
          relocateBucket(&LB[I], &RB[I]);
          relocateBucket(&RB[I], T);
        } else if (L) {
          relocateBucket(&RB[I], &LB[I]);
        } else if (R) {
          relocateBucket(&LB[I], &RB[I]);
        }
      }
      for (unsigned W = 0; W != InlineUsedWords; ++W)
        std::swap(LU[W], RU[W]);
      return;
    }
    if (!Small && !RHS.Small) {
      std::swap(storage.Large, RHS.storage.Large);
      return;
    }
 
    SmallDenseMapStorage &SmallSide = Small ? *this : RHS;
    SmallDenseMapStorage &LargeSide = Small ? RHS : *this;
 
    // Stash the large rep, then move the small side's inline contents into the
    // large side (which becomes inline), and finally install the rep on the
    // small side (which becomes large).
    LargeRep TmpRep = LargeSide.storage.Large;
    LargeSide.Small = true;
    {
      UsedT *SU = SmallSide.getInlineUsed(), *LU = LargeSide.getInlineUsed();
      BucketT *SB = SmallSide.getInlineBuckets(),
              *LB = LargeSide.getInlineBuckets();
      for (unsigned I = 0; I != InlineBuckets; ++I)
        if (used(SU, I))
          relocateBucket(&LB[I], &SB[I]);
      for (unsigned W = 0; W != InlineUsedWords; ++W)
        LU[W] = SU[W];
    }
    SmallSide.Small = false;
    SmallSide.storage.Large = TmpRep;
  }
 
  void grow(unsigned MinNumBuckets, BucketHasher Hasher) {
    unsigned NewNumBuckets = roundUpNumBuckets(MinNumBuckets);
    // remove_if asks for the count it already has: rehash in place.
    if (Small && NewNumBuckets <= InlineBuckets) {
      InlineRep Old = storage.Inline;
      clearUsed(getInlineUsed(), InlineBuckets);
      rehashRelocatable(getInlineBuckets(), getInlineUsed(), InlineBuckets,
                        Old.Buckets, Old.Used, InlineBuckets, sizeof(BucketT),
                        Hasher);
      return;
    }
    void *Storage = growRelocatable(
        getBuckets(), getUsed(), getNumBuckets(), NewNumBuckets,
        sizeof(BucketT), allocAlign<BucketT>(), Hasher, /*FreeOld=*/!Small);
    setLarge(Storage, NewNumBuckets);
  }
 
  void deallocateBuckets() {
    if (Small)
      return;
 
    deallocate_buffer(storage.Large.Buckets,
                      allocBytes<BucketT>(storage.Large.NumBuckets),
                      allocAlign<BucketT>());
  }
 
  bool allocateBuckets(unsigned Num) {
    if (Num <= InlineBuckets) {
      Small = true;
      return true;
    }
    setLarge(allocate_buffer(allocBytes<BucketT>(Num), allocAlign<BucketT>()),
             Num);
    return true;
  }
 
  static unsigned roundUpNumBuckets(unsigned MinNumBuckets) {
    if (MinNumBuckets <= InlineBuckets)
      return InlineBuckets;
    return std::max(64u, MinNumBuckets);
  }
 
  // Plan how to shrink the bucket table. Return:
  // - {false, 0} to reuse the existing bucket table
  // - {true, N} to reallocate a bucket table with N entries
  std::pair<bool, unsigned> planShrinkAndClear() const {
    unsigned NewNumBuckets = 0;
    if (NumEntries) {
      NewNumBuckets = 1u << (Log2_32_Ceil(NumEntries) + 1);
      if (NewNumBuckets > InlineBuckets)
        NewNumBuckets = std::max(64u, NewNumBuckets);
    }
    bool Reuse = Small ? NewNumBuckets <= InlineBuckets
                       : NewNumBuckets == storage.Large.NumBuckets;
    if (Reuse)
      return {false, 0};          // Reuse.
    return {true, NewNumBuckets}; // Reallocate.
  }
 
  bool maybeMoveFast(SmallDenseMapStorage &&Other) {
    if (Other.Small)
      return false;
 
    Small = false;
    NumEntries = Other.NumEntries;
    storage.Large = Other.storage.Large;
    return true;
  }
};
 
} // namespace densemap::detail
 
template <typename KeyT, typename ValueT,
          typename KeyInfoT = DenseMapInfo<KeyT>,
          typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>,
          bool IsConst = false>
class DenseMapIterator : DebugEpochBase::HandleBase {
  friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
  friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>;
 
  using UsedT = llvm::densemap::detail::UsedT;
 
public:
  using difference_type = ptrdiff_t;
  using value_type = std::conditional_t<IsConst, const Bucket, Bucket>;
  using pointer = value_type *;
  using reference = value_type &;
  using iterator_category = std::forward_iterator_tag;
 
private:
  using BucketItTy =
      std::conditional_t<shouldReverseIterate<KeyT>(),
                         std::reverse_iterator<pointer>, pointer>;
 
  BucketItTy Ptr = {};
  BucketItTy End = {};
  // The non-reversed bucket base and the parallel used array.  They map a
  // bucket back to its index so AdvancePastEmptyBuckets can consult the bits.
  pointer Buckets = {};
  const UsedT *Used = {};
 
  DenseMapIterator(BucketItTy Pos, BucketItTy E, pointer BucketsBase,
                   const UsedT *U, const DebugEpochBase &Epoch)
      : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E),
        Buckets(BucketsBase), Used(U) {
    assert(isHandleInSync() && "invalid construction!");
  }
 
public:
  DenseMapIterator() = default;
 
  static DenseMapIterator makeBegin(pointer Buckets, const UsedT *Used,
                                    unsigned NumBuckets, bool IsEmpty,
                                    const DebugEpochBase &Epoch) {
    // When the map is empty, avoid the overhead of advancing/retreating past
    // empty buckets.
    if (IsEmpty)
      return makeEnd(Buckets, Used, NumBuckets, Epoch);
    auto R = maybeReverse(llvm::make_range(Buckets, Buckets + NumBuckets));
    DenseMapIterator Iter(R.begin(), R.end(), Buckets, Used, Epoch);
    Iter.AdvancePastEmptyBuckets();
    return Iter;
  }
 
  static DenseMapIterator makeEnd(pointer Buckets, const UsedT *Used,
                                  unsigned NumBuckets,
                                  const DebugEpochBase &Epoch) {
    auto R = maybeReverse(llvm::make_range(Buckets, Buckets + NumBuckets));
    return DenseMapIterator(R.end(), R.end(), Buckets, Used, Epoch);
  }
 
  static DenseMapIterator makeIterator(pointer P, pointer Buckets,
                                       const UsedT *Used, unsigned NumBuckets,
                                       const DebugEpochBase &Epoch) {
    auto R = maybeReverse(llvm::make_range(Buckets, Buckets + NumBuckets));
    constexpr int Offset = shouldReverseIterate<KeyT>() ? 1 : 0;
    return DenseMapIterator(BucketItTy(P + Offset), R.end(), Buckets, Used,
                            Epoch);
  }
 
  // Converting ctor from non-const iterators to const iterators. SFINAE'd out
  // for const iterator destinations so it doesn't end up as a user defined copy
  // constructor.
  template <bool IsConstSrc,
            typename = std::enable_if_t<!IsConstSrc && IsConst>>
  DenseMapIterator(
      const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I)
      : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End),
        Buckets(I.Buckets), Used(I.Used) {}
 
  [[nodiscard]] reference operator*() const {
    assert(isHandleInSync() && "invalid iterator access!");
    assert(Ptr != End && "dereferencing end() iterator");
    return *Ptr;
  }
  [[nodiscard]] pointer operator->() const { return &operator*(); }
 
  [[nodiscard]] friend bool operator==(const DenseMapIterator &LHS,
                                       const DenseMapIterator &RHS) {
    assert(LHS.isComparableWith(RHS) && "incomparable iterators!");
    return LHS.Ptr == RHS.Ptr;
  }
 
  [[nodiscard]] friend bool operator!=(const DenseMapIterator &LHS,
                                       const DenseMapIterator &RHS) {
    return !(LHS == RHS);
  }
 
  inline DenseMapIterator &operator++() { // Preincrement
    assert(isHandleInSync() && "invalid iterator access!");
    assert(Ptr != End && "incrementing end() iterator");
    ++Ptr;
    AdvancePastEmptyBuckets();
    return *this;
  }
  DenseMapIterator operator++(int) { // Postincrement
    assert(isHandleInSync() && "invalid iterator access!");
    DenseMapIterator tmp = *this;
    ++*this;
    return tmp;
  }
 
private:
  void AdvancePastEmptyBuckets() {
    if constexpr (shouldReverseIterate<KeyT>()) {
      while (Ptr != End && !llvm::densemap::detail::used(Used, &*Ptr - Buckets))
        ++Ptr;
    } else {
      // Forward iteration skips empty buckets a used-word (32 buckets) at a
      // time: scan from the current index for the next set occupancy bit.
      const size_t N = End - Buckets;
      size_t I = Ptr - Buckets;
      if (I >= N) {
        Ptr = End;
        return;
      }
      const size_t NW = llvm::densemap::detail::usedWords(N);
      size_t W = I >> 5;
      UsedT Bits = Used[W] & (~UsedT(0) << (I & 31));
      while (Bits == 0) {
        if (++W == NW) {
          Ptr = End;
          return;
        }
        Bits = Used[W];
      }
      Ptr = Buckets + ((W << 5) + llvm::countr_zero(Bits));
    }
  }
 
  static auto maybeReverse(iterator_range<pointer> Range) {
    if constexpr (shouldReverseIterate<KeyT>())
      return reverse(Range);
    else
      return Range;
  }
};
 
template <typename StorageT, typename KeyT, typename ValueT, typename KeyInfoT,
          typename BucketT>
class DenseMapBase : public DebugEpochBase {
  template <typename T>
  using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
 
  using UsedT = llvm::densemap::detail::UsedT;
 
public:
  using size_type = unsigned;
  using key_type = KeyT;
  using mapped_type = ValueT;
  using value_type = BucketT;
 
  using iterator = DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT>;
  using const_iterator =
      DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>;
 
  [[nodiscard]] inline iterator begin() {
    return iterator::makeBegin(getBuckets(), getUsed(), getNumBuckets(),
                               empty(), *this);
  }
  [[nodiscard]] inline iterator end() {
    return iterator::makeEnd(getBuckets(), getUsed(), getNumBuckets(), *this);
  }
  [[nodiscard]] inline const_iterator begin() const {
    return const_iterator::makeBegin(getBuckets(), getUsed(), getNumBuckets(),
                                     empty(), *this);
  }
  [[nodiscard]] inline const_iterator end() const {
    return const_iterator::makeEnd(getBuckets(), getUsed(), getNumBuckets(),
                                   *this);
  }
 
  // Return an iterator to iterate over keys in the map.
  [[nodiscard]] inline auto keys() {
    return map_range(*this, [](const BucketT &P) { return P.getFirst(); });
  }
 
  // Return an iterator to iterate over values in the map.
  [[nodiscard]] inline auto values() {
    return map_range(*this, [](const BucketT &P) { return P.getSecond(); });
  }
 
  [[nodiscard]] inline auto keys() const {
    return map_range(*this, [](const BucketT &P) { return P.getFirst(); });
  }
 
  [[nodiscard]] inline auto values() const {
    return map_range(*this, [](const BucketT &P) { return P.getSecond(); });
  }
 
  [[nodiscard]] bool empty() const { return getNumEntries() == 0; }
  [[nodiscard]] unsigned size() const { return getNumEntries(); }
 
  /// Grow the densemap so that it can contain at least \p NumEntries items
  /// before resizing again.
  void reserve(size_type NumEntries) {
    auto NumBuckets = getMinBucketToReserveForEntries(NumEntries);
    incrementEpoch();
    if (NumBuckets > getNumBuckets())
      grow(NumBuckets);
  }
 
  void clear() {
    incrementEpoch();
    if (getNumEntries() == 0)
      return;
 
    // If the capacity of the array is huge, and the # elements used is small,
    // shrink the array.
    if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
      shrink_and_clear();
      return;
    }
 
    destroyAll();
    llvm::densemap::detail::clearUsed(getUsed(), getNumBuckets());
    setNumEntries(0);
  }
 
  void shrink_and_clear() {
    auto [Reallocate, NewNumBuckets] = Storage.planShrinkAndClear();
    destroyAll();
    if (!Reallocate) {
      initEmpty(Storage);
      return;
    }
    Storage.deallocateBuckets();
    initWithExactBucketCount(Storage, NewNumBuckets);
  }
 
  /// Return true if the specified key is in the map, false otherwise.
  [[nodiscard]] bool contains(const_arg_type_t<KeyT> Val) const {
    return doFind(Val) != nullptr;
  }
 
  /// Return 1 if the specified key is in the map, 0 otherwise.
  [[nodiscard]] size_type count(const_arg_type_t<KeyT> Val) const {
    return contains(Val) ? 1 : 0;
  }
 
  [[nodiscard]] iterator find(const_arg_type_t<KeyT> Val) {
    return find_as(Val);
  }
  [[nodiscard]] const_iterator find(const_arg_type_t<KeyT> Val) const {
    return find_as(Val);
  }
 
  /// Alternate version of find() which allows a different, and possibly
  /// less expensive, key type.
  /// The DenseMapInfo is responsible for supplying methods
  /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
  /// type used.
  template <class LookupKeyT>
  [[nodiscard]] iterator find_as(const LookupKeyT &Val) {
    if (BucketT *Bucket = doFind(Val))
      return makeIterator(Bucket);
    return end();
  }
  template <class LookupKeyT>
  [[nodiscard]] const_iterator find_as(const LookupKeyT &Val) const {
    if (const BucketT *Bucket = doFind(Val))
      return makeConstIterator(Bucket);
    return end();
  }
 
  /// Return the entry for the specified key, or a default constructed value if
  /// no such entry exists.
  [[nodiscard]] ValueT lookup(const_arg_type_t<KeyT> Val) const {
    if (const BucketT *Bucket = doFind(Val))
      return Bucket->getSecond();
    return ValueT();
  }
 
  // Return the entry with the specified key, or \p Default. This variant is
  // useful, because `lookup` cannot be used with non-default-constructible
  // values.
  template <typename U = std::remove_cv_t<ValueT>>
  [[nodiscard]] ValueT lookup_or(const_arg_type_t<KeyT> Val,
                                 U &&Default) const {
    if (const BucketT *Bucket = doFind(Val))
      return Bucket->getSecond();
    return Default;
  }
 
  /// Return the entry for the specified key, or abort if no such entry exists.
  [[nodiscard]] ValueT &at(const_arg_type_t<KeyT> Val) {
    auto Iter = this->find(std::move(Val));
    assert(Iter != this->end() && "DenseMap::at failed due to a missing key");
    return Iter->second;
  }
 
  /// Return the entry for the specified key, or abort if no such entry exists.
  [[nodiscard]] const ValueT &at(const_arg_type_t<KeyT> Val) const {
    auto Iter = this->find(std::move(Val));
    assert(Iter != this->end() && "DenseMap::at failed due to a missing key");
    return Iter->second;
  }
 
  // Inserts key,value pair into the map if the key isn't already in the map.
  // If the key is already in the map, it returns false and doesn't update the
  // value.
  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
    return try_emplace_impl(KV.first, KV.second);
  }
 
  // Inserts key,value pair into the map if the key isn't already in the map.
  // If the key is already in the map, it returns false and doesn't update the
  // value.
  std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
    return try_emplace_impl(std::move(KV.first), std::move(KV.second));
  }
 
  template <
      typename B = BucketT,
      typename = std::enable_if_t<!std::is_same_v<B, std::pair<KeyT, ValueT>>>>
  std::pair<iterator, bool> insert(const BucketT &KV) {
    return try_emplace_impl(KV.first, KV.second);
  }
 
  template <
      typename B = BucketT,
      typename = std::enable_if_t<!std::is_same_v<B, std::pair<KeyT, ValueT>>>>
  std::pair<iterator, bool> insert(BucketT &&KV) {
    return try_emplace_impl(std::move(KV.first), std::move(KV.second));
  }
 
  // Inserts key,value pair into the map if the key isn't already in the map.
  // The value is constructed in-place if the key is not in the map, otherwise
  // it is not moved.
  template <typename... Ts>
  std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&...Args) {
    return try_emplace_impl(std::move(Key), std::forward<Ts>(Args)...);
  }
 
  // Inserts key,value pair into the map if the key isn't already in the map.
  // The value is constructed in-place if the key is not in the map, otherwise
  // it is not moved.
  template <typename... Ts>
  std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&...Args) {
    return try_emplace_impl(Key, std::forward<Ts>(Args)...);
  }
 
  /// Alternate version of insert() which allows a different, and possibly
  /// less expensive, key type.
  /// The DenseMapInfo is responsible for supplying methods
  /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
  /// type used.
  template <typename LookupKeyT>
  std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,
                                      const LookupKeyT &Val) {
    BucketT *TheBucket;
    if (LookupBucketFor(Val, TheBucket))
      return {makeIterator(TheBucket), false}; // Already in map.
 
    // Otherwise, insert the new element.
    TheBucket = findBucketForInsertion(Val, TheBucket);
    ::new (&TheBucket->getFirst()) KeyT(std::move(KV.first));
    ::new (&TheBucket->getSecond()) ValueT(std::move(KV.second));
    return {makeIterator(TheBucket), true};
  }
 
  /// Range insertion of pairs.
  template <typename InputIt> void insert(InputIt I, InputIt E) {
    for (; I != E; ++I)
      insert(*I);
  }
 
  /// Inserts range of 'std::pair<KeyT, ValueT>' values into the map.
  template <typename Range> void insert_range(Range &&R) {
    insert(adl_begin(R), adl_end(R));
  }
 
  template <typename V>
  std::pair<iterator, bool> insert_or_assign(const KeyT &Key, V &&Val) {
    auto Ret = try_emplace(Key, std::forward<V>(Val));
    if (!Ret.second)
      Ret.first->second = std::forward<V>(Val);
    return Ret;
  }
 
  template <typename V>
  std::pair<iterator, bool> insert_or_assign(KeyT &&Key, V &&Val) {
    auto Ret = try_emplace(std::move(Key), std::forward<V>(Val));
    if (!Ret.second)
      Ret.first->second = std::forward<V>(Val);
    return Ret;
  }
 
  template <typename... Ts>
  std::pair<iterator, bool> emplace_or_assign(const KeyT &Key, Ts &&...Args) {
    auto Ret = try_emplace(Key, std::forward<Ts>(Args)...);
    if (!Ret.second)
      Ret.first->second = ValueT(std::forward<Ts>(Args)...);
    return Ret;
  }
 
  template <typename... Ts>
  std::pair<iterator, bool> emplace_or_assign(KeyT &&Key, Ts &&...Args) {
    auto Ret = try_emplace(std::move(Key), std::forward<Ts>(Args)...);
    if (!Ret.second)
      Ret.first->second = ValueT(std::forward<Ts>(Args)...);
    return Ret;
  }
 
  bool erase(const KeyT &Val) {
    BucketT *TheBucket = doFind(Val);
    if (!TheBucket)
      return false; // not in map.
 
    eraseFromFilledBucket(TheBucket);
    return true;
  }
  void erase(iterator I) { eraseFromFilledBucket(&*I); }
 
  /// Remove entries that match the given predicate. \p Pred is invoked
  /// with a reference to each live bucket and must not access the map being
  /// modified. This is the safe replacement for erase-while-iterating.
  ///
  /// Returns whether anything was removed. If so, all iterators and references
  /// into the map are invalidated.
  template <typename Predicate> bool remove_if(Predicate Pred) {
    UsedT *U = getUsed();
    unsigned NumBuckets = getNumBuckets();
    BucketT *B = getBuckets();
    bool Removed = false;
    for (unsigned I = 0; I != NumBuckets; ++I) {
      if (!llvm::densemap::detail::used(U, I))
        continue;
      if (Pred(B[I])) {
        B[I].getSecond().~ValueT();
        B[I].getFirst().~KeyT();
        llvm::densemap::detail::unsetUsed(U, I);
        decrementNumEntries();
        Removed = true;
      }
    }
    if (Removed) {
      incrementEpoch();
      this->grow(NumBuckets);
    }
    return Removed;
  }
 
  ValueT &operator[](const KeyT &Key) {
    return lookupOrInsertIntoBucket(Key).first->second;
  }
 
  ValueT &operator[](KeyT &&Key) {
    return lookupOrInsertIntoBucket(std::move(Key)).first->second;
  }
 
  void swap(DenseMapBase &RHS) {
    this->incrementEpoch();
    RHS.incrementEpoch();
    Storage.swap(RHS.Storage);
  }
 
  DenseMapBase() : DenseMapBase(0) {}
 
  /// Create a DenseMap with an optional \p NumElementsToReserve to guarantee
  /// that this number of elements can be inserted in the map without grow().
  explicit DenseMapBase(unsigned NumElementsToReserve) {
    initWithExactBucketCount(
        Storage, getMinBucketToReserveForEntries(NumElementsToReserve));
  }
 
  DenseMapBase(const DenseMapBase &other) : DenseMapBase() {
    this->copyFrom(other);
  }
 
  DenseMapBase(DenseMapBase &&other) : DenseMapBase() { this->swap(other); }
 
  template <typename InputIt>
  DenseMapBase(const InputIt &I, const InputIt &E)
      : DenseMapBase(std::distance(I, E)) {
    this->insert(I, E);
  }
 
  template <typename RangeT>
  DenseMapBase(llvm::from_range_t, const RangeT &Range)
      : DenseMapBase(adl_begin(Range), adl_end(Range)) {}
 
  DenseMapBase(std::initializer_list<value_type> Vals)
      : DenseMapBase(Vals.begin(), Vals.end()) {}
 
  ~DenseMapBase() {
    this->destroyAll();
    Storage.deallocateBuckets();
  }
 
  DenseMapBase &operator=(const DenseMapBase &other) {
    if (&other != this)
      this->copyFrom(other);
    return *this;
  }
 
  DenseMapBase &operator=(DenseMapBase &&other) {
    this->destroyAll();
    Storage.deallocateBuckets();
    initWithExactBucketCount(Storage, 0);
    this->swap(other);
    return *this;
  }
 
  /// Return the approximate size (in bytes) of the actual map.
  /// This is just the raw memory used by DenseMap.
  /// If entries are pointers to objects, the size of the referenced objects
  /// are not included.
  [[nodiscard]] size_t getMemorySize() const {
    return llvm::densemap::detail::allocBytes<BucketT>(getNumBuckets());
  }
 
private:
  StorageT Storage;
 
  using Rep = llvm::densemap::detail::StorageRep<BucketT>;
 
  static void initEmpty(StorageT &S) {
    S.setNumEntries(0);
 
    assert((S.getNumBuckets() & (S.getNumBuckets() - 1)) == 0 &&
           "# initial buckets must be a power of two!");
    if (S.getNumBuckets())
      llvm::densemap::detail::clearUsed(S.getUsed(), S.getNumBuckets());
  }
 
  static void initWithExactBucketCount(StorageT &S, unsigned NewNumBuckets) {
    if (S.allocateBuckets(NewNumBuckets))
      initEmpty(S);
    else
      S.setNumEntries(0);
  }
 
  void destroyAll() {
    // No need to iterate through the buckets if the bucket is trivially
    // destructible.
    if constexpr (std::is_trivially_destructible_v<BucketT>)
      return;
 
    if (getNumBuckets() == 0) // Nothing to do.
      return;
 
    BucketT *B = getBuckets();
    const UsedT *U = getUsed();
    const unsigned E = getNumBuckets();
    llvm::densemap::detail::forEachUsed(U, E, [&](unsigned I) {
      B[I].getSecond().~ValueT();
      B[I].getFirst().~KeyT();
    });
  }
 
  /// Returns the number of buckets to allocate to ensure that the DenseMap can
  /// accommodate \p NumEntries without need to grow().
  unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
    // Ensure that "NumEntries * 4 < NumBuckets * 3"
    if (NumEntries == 0)
      return 0;
    // +1 is required because of the strict inequality.
    // For example, if NumEntries is 48, we need to return 128.
    return NextPowerOf2(NumEntries * 4 / 3 + 1);
  }
 
  static constexpr llvm::densemap::detail::BucketHasher hasher() {
    return llvm::densemap::detail::hasherFor<KeyT, KeyInfoT>();
  }
 
  // Move key/value from Src to Dst.
  static LLVM_ATTRIBUTE_NOINLINE void moveFrom(StorageT &Dst, StorageT &Src) {
    assert(Dst.getNumEntries() == 0 &&
           "moveFrom requires an empty destination");
    BucketT *SrcB = Src.getBuckets();
    UsedT *SrcU = Src.getUsed();
    const unsigned E = Src.getNumBuckets();
    UsedT *U = Dst.getUsed();
    BucketT *B = Dst.getBuckets();
    const unsigned Mask = Dst.getNumBuckets() - 1;
    llvm::densemap::detail::forEachUsed(SrcU, E, [&](unsigned I) {
      // Find the first empty slot on this key's probe chain; there is no equal
      // key in the destination, so nothing to compare against.
      unsigned BucketNo = KeyInfoT::getHashValue(SrcB[I].getFirst()) & Mask;
      while (llvm::densemap::detail::used(U, BucketNo))
        BucketNo = (BucketNo + 1) & Mask;
      llvm::densemap::detail::relocateBucket(B + BucketNo, &SrcB[I]);
      llvm::densemap::detail::setUsed(U, BucketNo);
    });
    Dst.setNumEntries(Src.getNumEntries());
    Src.deallocateBuckets();
  }
 
  LLVM_ATTRIBUTE_NOINLINE void copyFrom(const DenseMapBase &other) {
    this->destroyAll();
    Storage.deallocateBuckets();
    setNumEntries(0);
    if (!Storage.allocateBuckets(other.getNumBuckets())) {
      // The bucket list is empty.  No work to do.
      return;
    }
 
    assert(&other != this);
    assert(getNumBuckets() == other.getNumBuckets());
 
    setNumEntries(other.getNumEntries());
 
    BucketT *Buckets = getBuckets();
    const BucketT *OtherBuckets = other.getBuckets();
    const unsigned NumBuckets = getNumBuckets();
    UsedT *U = getUsed();
    const UsedT *OtherU = other.getUsed();
    std::memcpy(U, OtherU,
                llvm::densemap::detail::usedWords(NumBuckets) * sizeof(UsedT));
    if constexpr (densemap::detail::isRelocatableBucket<BucketT>) {
      memcpy(reinterpret_cast<void *>(Buckets), OtherBuckets,
             NumBuckets * sizeof(BucketT));
    } else {
      llvm::densemap::detail::forEachUsed(U, NumBuckets, [&](unsigned I) {
        ::new (&Buckets[I].getFirst()) KeyT(OtherBuckets[I].getFirst());
        ::new (&Buckets[I].getSecond()) ValueT(OtherBuckets[I].getSecond());
      });
    }
  }
 
  /// Erase the entry at \p TheBucket and close the resulting hole via Knuth
  /// TAOCP 6.4 Algorithm R.
  LLVM_ATTRIBUTE_NOINLINE void eraseFromFilledBucket(BucketT *TheBucket) {
    incrementEpoch();
    TheBucket->getSecond().~ValueT();
    TheBucket->getFirst().~KeyT();
    decrementNumEntries();
 
    BucketT *BucketsPtr = getBuckets();
    UsedT *U = getUsed();
    const unsigned Mask = getNumBuckets() - 1;
    unsigned I = TheBucket - BucketsPtr;
    unsigned J = I;
    while (true) {
      J = (J + 1) & Mask;
      BucketT &BJ = BucketsPtr[J];
      if (!llvm::densemap::detail::used(U, J))
        break;
      auto Ideal = KeyInfoT::getHashValue(BJ.getFirst());
      // If the hole (I) lies on the linear-probe chain from the home bucket
      // (Ideal) to J, shift J into the hole and make J the new hole.
      if (((I - Ideal) & Mask) < ((J - Ideal) & Mask)) {
        llvm::densemap::detail::relocateBucket(&BucketsPtr[I], &BJ);
        I = J;
      }
    }
    llvm::densemap::detail::unsetUsed(U, I);
  }
 
  template <typename KeyArgT, typename... Ts>
  std::pair<BucketT *, bool> lookupOrInsertIntoBucket(KeyArgT &&Key,
                                                      Ts &&...Args) {
    BucketT *TheBucket = nullptr;
    if (LookupBucketFor(Key, TheBucket))
      return {TheBucket, false}; // Already in the map.
 
    // Otherwise, insert the new element.
    TheBucket = findBucketForInsertion(Key, TheBucket);
    ::new (&TheBucket->getFirst()) KeyT(std::forward<KeyArgT>(Key));
    ::new (&TheBucket->getSecond()) ValueT(std::forward<Ts>(Args)...);
    return {TheBucket, true};
  }
 
  template <typename KeyArgT, typename... Ts>
  std::pair<iterator, bool> try_emplace_impl(KeyArgT &&Key, Ts &&...Args) {
    auto [Bucket, Inserted] = lookupOrInsertIntoBucket(
        std::forward<KeyArgT>(Key), std::forward<Ts>(Args)...);
    return {makeIterator(Bucket), Inserted};
  }
 
  iterator makeIterator(BucketT *TheBucket) {
    return iterator::makeIterator(TheBucket, getBuckets(), getUsed(),
                                  getNumBuckets(), *this);
  }
 
  const_iterator makeConstIterator(const BucketT *TheBucket) const {
    return const_iterator::makeIterator(TheBucket, getBuckets(), getUsed(),
                                        getNumBuckets(), *this);
  }
 
  unsigned getNumEntries() const { return Storage.getNumEntries(); }
 
  void setNumEntries(unsigned Num) { Storage.setNumEntries(Num); }
 
  void incrementNumEntries() { setNumEntries(getNumEntries() + 1); }
 
  void decrementNumEntries() { setNumEntries(getNumEntries() - 1); }
 
  const BucketT *getBuckets() const { return Storage.getBuckets(); }
 
  BucketT *getBuckets() { return Storage.getBuckets(); }
 
  Rep getRep() const { return Storage.getRep(); }
 
  const UsedT *getUsed() const { return Storage.getUsed(); }
 
  UsedT *getUsed() { return Storage.getUsed(); }
 
  unsigned getNumBuckets() const { return Storage.getNumBuckets(); }
 
  LLVM_ATTRIBUTE_NOINLINE void grow(unsigned MinNumBuckets) {
    assert((MinNumBuckets == 0 || isPowerOf2_32(MinNumBuckets)) &&
           "bucket count must be zero or a power of two");
    if constexpr (llvm::densemap::detail::isRelocatableBucket<BucketT>) {
      Storage.grow(MinNumBuckets, hasher());
    } else {
      unsigned NumBuckets = StorageT::roundUpNumBuckets(MinNumBuckets);
      StorageT Tmp;
      initWithExactBucketCount(Tmp, NumBuckets);
      moveFrom(Tmp, Storage);
      if (Storage.maybeMoveFast(std::move(Tmp)))
        return;
      initWithExactBucketCount(Storage, NumBuckets);
      moveFrom(Storage, Tmp);
    }
  }
 
  template <typename LookupKeyT>
  BucketT *findBucketForInsertion(const LookupKeyT &Lookup,
                                  BucketT *TheBucket) {
    incrementEpoch();
 
    // Grow the table if the load factor would exceed 3/4 after insertion.
    // Linear probing with gap-closing deletion (Knuth Algorithm R) keeps
    // every chain compact and bounded by the table's empty-bucket count,
    // so no tombstone-driven resize is needed.
    unsigned NewNumEntries = getNumEntries() + 1;
    unsigned NumBuckets = getNumBuckets();
    if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
      this->grow(NumBuckets * 2);
      LookupBucketFor(Lookup, TheBucket);
    }
    assert(TheBucket);
 
    // Mark used. The caller will placement-construct the raw key/value.
    llvm::densemap::detail::setUsed(getUsed(), TheBucket - getBuckets());
 
    // Only update the state after we've grown our bucket space appropriately
    // so that when growing buckets we have self-consistent entry count.
    incrementNumEntries();
    return TheBucket;
  }
 
  template <typename LookupKeyT>
  const BucketT *doFind(const LookupKeyT &Val) const {
    if (empty())
      return nullptr;
    auto [BucketsPtr, U, NumBuckets] = getRep();
 
    const unsigned Mask = NumBuckets - 1;
    unsigned BucketNo = KeyInfoT::getHashValue(Val) & Mask;
    while (true) {
      // An empty bucket terminates the probe: the key isn't in the map.
      if (LLVM_LIKELY(!llvm::densemap::detail::used(U, BucketNo)))
        return nullptr;
      const BucketT *Bucket = BucketsPtr + BucketNo;
      if (LLVM_LIKELY(KeyInfoT::isEqual(Val, Bucket->getFirst())))
        return Bucket;
 
      // Hash collision: continue linear probing.
      BucketNo = (BucketNo + 1) & Mask;
    }
  }
 
  template <typename LookupKeyT> BucketT *doFind(const LookupKeyT &Val) {
    return const_cast<BucketT *>(
        static_cast<const DenseMapBase *>(this)->doFind(Val));
  }
 
  /// Lookup the appropriate bucket for Val, returning it in FoundBucket. If the
  /// bucket contains the key and a value, this returns true, otherwise it
  /// returns a bucket with an empty marker and returns false.
  template <typename LookupKeyT>
  bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
    auto [CBuckets, U, NumBuckets] = getRep();
    if (NumBuckets == 0) {
      FoundBucket = nullptr;
      return false;
    }
    // getRep() yields const pointers; this object is non-const, so recovering
    // a mutable bucket pointer is safe (mirrors the non-const getBuckets()).
    BucketT *BucketsPtr = const_cast<BucketT *>(CBuckets);
 
    const unsigned Mask = NumBuckets - 1;
    unsigned BucketNo = KeyInfoT::getHashValue(Val) & Mask;
    while (true) {
      BucketT *ThisBucket = BucketsPtr + BucketNo;
      // If we found an empty bucket, the key doesn't exist in the set.
      // Return it as the insertion point.
      if (LLVM_LIKELY(!llvm::densemap::detail::used(U, BucketNo))) {
        FoundBucket = ThisBucket;
        return false;
      }
 
      // Found Val's bucket?  If so, return it.
      if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
        FoundBucket = ThisBucket;
        return true;
      }
 
      // Hash collision: continue linear probing.
      BucketNo = (BucketNo + 1) & Mask;
    }
  }
};
 
/// Equality comparison for DenseMap.
///
/// Iterates over elements of LHS confirming that each (key, value) pair in LHS
/// is also in RHS, and that no additional pairs are in RHS.
/// Equivalent to N calls to RHS.find and N value comparisons. Amortized
/// complexity is linear, worst case is O(N^2) (if every hash collides).
template <typename Storage1T, typename Storage2T, typename KeyT,
          typename ValueT, typename KeyInfoT, typename BucketT>
[[nodiscard]] bool operator==(
    const DenseMapBase<Storage1T, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
    const DenseMapBase<Storage2T, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
  if (LHS.size() != RHS.size())
    return false;
 
  for (auto &KV : LHS) {
    auto I = RHS.find(KV.first);
    if (I == RHS.end() || I->second != KV.second)
      return false;
  }
 
  return true;
}
 
/// Inequality comparison for DenseMap.
///
/// Equivalent to !(LHS == RHS). See operator== for performance notes.
template <typename Storage1T, typename Storage2T, typename KeyT,
          typename ValueT, typename KeyInfoT, typename BucketT>
[[nodiscard]] bool operator!=(
    const DenseMapBase<Storage1T, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
    const DenseMapBase<Storage2T, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
  return !(LHS == RHS);
}
 
template <typename KeyT, typename ValueT,
          typename KeyInfoT = DenseMapInfo<KeyT>,
          typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
class DenseMap : public DenseMapBase<densemap::detail::DenseMapStorage<BucketT>,
                                     KeyT, ValueT, KeyInfoT, BucketT> {
  using BaseT = DenseMapBase<densemap::detail::DenseMapStorage<BucketT>, KeyT,
                             ValueT, KeyInfoT, BucketT>;
 
public:
  using BaseT::BaseT;
};
 
template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4,
          typename KeyInfoT = DenseMapInfo<KeyT>,
          typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
class SmallDenseMap
    : public DenseMapBase<
          densemap::detail::SmallDenseMapStorage<BucketT, InlineBuckets>, KeyT,
          ValueT, KeyInfoT, BucketT> {
  using BaseT = DenseMapBase<
      densemap::detail::SmallDenseMapStorage<BucketT, InlineBuckets>, KeyT,
      ValueT, KeyInfoT, BucketT>;
 
public:
  using BaseT::BaseT;
};
 
template <typename KeyT, typename ValueT, typename KeyInfoT>
[[nodiscard]] inline size_t
capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) {
  return X.getMemorySize();
}
 
} // end namespace llvm
 
#endif // LLVM_ADT_DENSEMAP_H