xref: /llvm-project/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h (revision 65b4a7704beaf87c5eb12b672a837501a981a77a)

//===- sanitizer_dense_map.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
//
//===----------------------------------------------------------------------===//
//
// This is fork of llvm/ADT/DenseMap.h class with the following changes:
//  * Use mmap to allocate.
//  * No iterators.
//  * Does not shrink.
//
//===----------------------------------------------------------------------===//

#ifndef SANITIZER_DENSE_MAP_H
#define SANITIZER_DENSE_MAP_H

#include "sanitizer_common.h"
#include "sanitizer_dense_map_info.h"
#include "sanitizer_internal_defs.h"
#include "sanitizer_type_traits.h"

namespace __sanitizer {

template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
          typename BucketT>
class DenseMapBase {
 public:
  using size_type = unsigned;
  using key_type = KeyT;
  using mapped_type = ValueT;
  using value_type = BucketT;

  WARN_UNUSED_RESULT bool empty() const { return getNumEntries() == 0; }
  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);
    if (NumBuckets > getNumBuckets())
      grow(NumBuckets);
  }

  void clear() {
    if (getNumEntries() == 0 && getNumTombstones() == 0)
      return;

    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
    if (__sanitizer::is_trivially_destructible<ValueT>::value) {
      // Use a simpler loop when values don't need destruction.
      for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P)
        P->getFirst() = EmptyKey;
    } else {
      unsigned NumEntries = getNumEntries();
      for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
        if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {
          if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
            P->getSecond().~ValueT();
            --NumEntries;
          }
          P->getFirst() = EmptyKey;
        }
      }
      CHECK_EQ(NumEntries, 0);
    }
    setNumEntries(0);
    setNumTombstones(0);
  }

  /// Return true if the specified key is in the map, false otherwise.
  bool contains(const KeyT &Key) const { return doFind(Key) != nullptr; }

  /// Return 1 if the specified key is in the map, 0 otherwise.
  size_type count(const KeyT &Key) const { return contains(Key) ? 1 : 0; }

  value_type *find(const KeyT &Key) { return doFind(Key); }
  const value_type *find(const KeyT &Key) const { return doFind(Key); }

  /// 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>
  value_type *find_as(const LookupKeyT &Key) {
    return doFind(Key);
  }
  template <class LookupKeyT>
  const value_type *find_as(const LookupKeyT &Key) const {
    return doFind(Key);
  }

  /// lookup - Return the entry for the specified key, or a default
  /// constructed value if no such entry exists.
  ValueT lookup(const KeyT &Key) const {
    if (const BucketT *Bucket = doFind(Key))
      return Bucket->getSecond();
    return ValueT();
  }

  // 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.
  detail::DenseMapPair<value_type *, bool> insert(const value_type &KV) {
    return try_emplace(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.
  detail::DenseMapPair<value_type *, bool> insert(value_type &&KV) {
    return try_emplace(__sanitizer::move(KV.first),
                       __sanitizer::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>
  detail::DenseMapPair<value_type *, bool> try_emplace(KeyT &&Key,
                                                       Ts &&...Args) {
    BucketT *TheBucket;
    if (LookupBucketFor(Key, TheBucket))
      return {TheBucket, false};  // Already in map.

    // Otherwise, insert the new element.
    TheBucket = InsertIntoBucket(TheBucket, __sanitizer::move(Key),
                                 __sanitizer::forward<Ts>(Args)...);
    return {TheBucket, true};
  }

  // 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>
  detail::DenseMapPair<value_type *, bool> try_emplace(const KeyT &Key,
                                                       Ts &&...Args) {
    BucketT *TheBucket;
    if (LookupBucketFor(Key, TheBucket))
      return {TheBucket, false};  // Already in map.

    // Otherwise, insert the new element.
    TheBucket =
        InsertIntoBucket(TheBucket, Key, __sanitizer::forward<Ts>(Args)...);
    return {TheBucket, true};
  }

  /// 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>
  detail::DenseMapPair<value_type *, bool> insert_as(value_type &&KV,
                                                     const LookupKeyT &Val) {
    BucketT *TheBucket;
    if (LookupBucketFor(Val, TheBucket))
      return {TheBucket, false};  // Already in map.

    // Otherwise, insert the new element.
    TheBucket =
        InsertIntoBucketWithLookup(TheBucket, __sanitizer::move(KV.first),
                                   __sanitizer::move(KV.second), Val);
    return {TheBucket, true};
  }

  bool erase(const KeyT &Val) {
    BucketT *TheBucket = doFind(Val);
    if (!TheBucket)
      return false;  // not in map.

    TheBucket->getSecond().~ValueT();
    TheBucket->getFirst() = getTombstoneKey();
    decrementNumEntries();
    incrementNumTombstones();
    return true;
  }

  void erase(value_type *I) {
    CHECK_NE(I, nullptr);
    BucketT *TheBucket = &*I;
    TheBucket->getSecond().~ValueT();
    TheBucket->getFirst() = getTombstoneKey();
    decrementNumEntries();
    incrementNumTombstones();
  }

  value_type &FindAndConstruct(const KeyT &Key) {
    BucketT *TheBucket;
    if (LookupBucketFor(Key, TheBucket))
      return *TheBucket;

    return *InsertIntoBucket(TheBucket, Key);
  }

  ValueT &operator[](const KeyT &Key) { return FindAndConstruct(Key).second; }

  value_type &FindAndConstruct(KeyT &&Key) {
    BucketT *TheBucket;
    if (LookupBucketFor(Key, TheBucket))
      return *TheBucket;

    return *InsertIntoBucket(TheBucket, __sanitizer::move(Key));
  }

  ValueT &operator[](KeyT &&Key) {
    return FindAndConstruct(__sanitizer::move(Key)).second;
  }

  /// Iterate over active entries of the container.
  ///
  /// Function can return fast to stop the process.
  template <class Fn>
  void forEach(Fn fn) {
    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
    for (auto *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
      const KeyT K = P->getFirst();
      if (!KeyInfoT::isEqual(K, EmptyKey) &&
          !KeyInfoT::isEqual(K, TombstoneKey)) {
        if (!fn(*P))
          return;
      }
    }
  }

  template <class Fn>
  void forEach(Fn fn) const {
    const_cast<DenseMapBase *>(this)->forEach(
        [&](const value_type &KV) { return fn(KV); });
  }

 protected:
  DenseMapBase() = default;

  void destroyAll() {
    if (getNumBuckets() == 0)  // Nothing to do.
      return;

    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
    for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
      if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
          !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
        P->getSecond().~ValueT();
      P->getFirst().~KeyT();
    }
  }

  void initEmpty() {
    setNumEntries(0);
    setNumTombstones(0);

    CHECK_EQ((getNumBuckets() & (getNumBuckets() - 1)), 0);
    const KeyT EmptyKey = getEmptyKey();
    for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
      ::new (&B->getFirst()) KeyT(EmptyKey);
  }

  /// 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 equality.
    // For example if NumEntries is 48, we need to return 401.
    return RoundUpToPowerOfTwo((NumEntries * 4 / 3 + 1) + /* NextPowerOf2 */ 1);
  }

  void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
    initEmpty();

    // Insert all the old elements.
    const KeyT EmptyKey = getEmptyKey();
    const KeyT TombstoneKey = getTombstoneKey();
    for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
      if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&
          !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) {
        // Insert the key/value into the new table.
        BucketT *DestBucket;
        bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
        (void)FoundVal;  // silence warning.
        CHECK(!FoundVal);
        DestBucket->getFirst() = __sanitizer::move(B->getFirst());
        ::new (&DestBucket->getSecond())
            ValueT(__sanitizer::move(B->getSecond()));
        incrementNumEntries();

        // Free the value.
        B->getSecond().~ValueT();
      }
      B->getFirst().~KeyT();
    }
  }

  template <typename OtherBaseT>
  void copyFrom(
      const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) {
    CHECK_NE(&other, this);
    CHECK_EQ(getNumBuckets(), other.getNumBuckets());

    setNumEntries(other.getNumEntries());
    setNumTombstones(other.getNumTombstones());

    if (__sanitizer::is_trivially_copyable<KeyT>::value &&
        __sanitizer::is_trivially_copyable<ValueT>::value)
      internal_memcpy(reinterpret_cast<void *>(getBuckets()),
                      other.getBuckets(), getNumBuckets() * sizeof(BucketT));
    else
      for (uptr i = 0; i < getNumBuckets(); ++i) {
        ::new (&getBuckets()[i].getFirst())
            KeyT(other.getBuckets()[i].getFirst());
        if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
            !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
          ::new (&getBuckets()[i].getSecond())
              ValueT(other.getBuckets()[i].getSecond());
      }
  }

  static unsigned getHashValue(const KeyT &Val) {
    return KeyInfoT::getHashValue(Val);
  }

  template <typename LookupKeyT>
  static unsigned getHashValue(const LookupKeyT &Val) {
    return KeyInfoT::getHashValue(Val);
  }

  static const KeyT getEmptyKey() { return KeyInfoT::getEmptyKey(); }

  static const KeyT getTombstoneKey() { return KeyInfoT::getTombstoneKey(); }

 private:
  unsigned getNumEntries() const {
    return static_cast<const DerivedT *>(this)->getNumEntries();
  }

  void setNumEntries(unsigned Num) {
    static_cast<DerivedT *>(this)->setNumEntries(Num);
  }

  void incrementNumEntries() { setNumEntries(getNumEntries() + 1); }

  void decrementNumEntries() { setNumEntries(getNumEntries() - 1); }

  unsigned getNumTombstones() const {
    return static_cast<const DerivedT *>(this)->getNumTombstones();
  }

  void setNumTombstones(unsigned Num) {
    static_cast<DerivedT *>(this)->setNumTombstones(Num);
  }

  void incrementNumTombstones() { setNumTombstones(getNumTombstones() + 1); }

  void decrementNumTombstones() { setNumTombstones(getNumTombstones() - 1); }

  const BucketT *getBuckets() const {
    return static_cast<const DerivedT *>(this)->getBuckets();
  }

  BucketT *getBuckets() { return static_cast<DerivedT *>(this)->getBuckets(); }

  unsigned getNumBuckets() const {
    return static_cast<const DerivedT *>(this)->getNumBuckets();
  }

  BucketT *getBucketsEnd() { return getBuckets() + getNumBuckets(); }

  const BucketT *getBucketsEnd() const {
    return getBuckets() + getNumBuckets();
  }

  void grow(unsigned AtLeast) { static_cast<DerivedT *>(this)->grow(AtLeast); }

  template <typename KeyArg, typename... ValueArgs>
  BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
                            ValueArgs &&...Values) {
    TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);

    TheBucket->getFirst() = __sanitizer::forward<KeyArg>(Key);
    ::new (&TheBucket->getSecond())
        ValueT(__sanitizer::forward<ValueArgs>(Values)...);
    return TheBucket;
  }

  template <typename LookupKeyT>
  BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key,
                                      ValueT &&Value, LookupKeyT &Lookup) {
    TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);

    TheBucket->getFirst() = __sanitizer::move(Key);
    ::new (&TheBucket->getSecond()) ValueT(__sanitizer::move(Value));
    return TheBucket;
  }

  template <typename LookupKeyT>
  BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
                                BucketT *TheBucket) {
    // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
    // the buckets are empty (meaning that many are filled with tombstones),
    // grow the table.
    //
    // The later case is tricky.  For example, if we had one empty bucket with
    // tons of tombstones, failing lookups (e.g. for insertion) would have to
    // probe almost the entire table until it found the empty bucket.  If the
    // table completely filled with tombstones, no lookup would ever succeed,
    // causing infinite loops in lookup.
    unsigned NewNumEntries = getNumEntries() + 1;
    unsigned NumBuckets = getNumBuckets();
    if (UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
      this->grow(NumBuckets * 2);
      LookupBucketFor(Lookup, TheBucket);
      NumBuckets = getNumBuckets();
    } else if (UNLIKELY(NumBuckets - (NewNumEntries + getNumTombstones()) <=
                        NumBuckets / 8)) {
      this->grow(NumBuckets);
      LookupBucketFor(Lookup, TheBucket);
    }
    CHECK(TheBucket);

    // Only update the state after we've grown our bucket space appropriately
    // so that when growing buckets we have self-consistent entry count.
    incrementNumEntries();

    // If we are writing over a tombstone, remember this.
    const KeyT EmptyKey = getEmptyKey();
    if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
      decrementNumTombstones();

    return TheBucket;
  }

  template <typename LookupKeyT>
  BucketT *doFind(const LookupKeyT &Val) {
    BucketT *BucketsPtr = getBuckets();
    const unsigned NumBuckets = getNumBuckets();
    if (NumBuckets == 0)
      return nullptr;

    const KeyT EmptyKey = getEmptyKey();
    unsigned BucketNo = getHashValue(Val) & (NumBuckets - 1);
    unsigned ProbeAmt = 1;
    while (true) {
      BucketT *Bucket = BucketsPtr + BucketNo;
      if (LIKELY(KeyInfoT::isEqual(Val, Bucket->getFirst())))
        return Bucket;
      if (LIKELY(KeyInfoT::isEqual(Bucket->getFirst(), EmptyKey)))
        return nullptr;

      // Otherwise, it's a hash collision or a tombstone, continue quadratic
      // probing.
      BucketNo += ProbeAmt++;
      BucketNo &= NumBuckets - 1;
    }
  }

  template <typename LookupKeyT>
  const BucketT *doFind(const LookupKeyT &Val) const {
    return const_cast<DenseMapBase *>(this)->doFind(Val);
  }

  /// LookupBucketFor - 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 or tombstone and
  /// returns false.
  template <typename LookupKeyT>
  bool LookupBucketFor(const LookupKeyT &Val,
                       const BucketT *&FoundBucket) const {
    const BucketT *BucketsPtr = getBuckets();
    const unsigned NumBuckets = getNumBuckets();

    if (NumBuckets == 0) {
      FoundBucket = nullptr;
      return false;
    }

    // FoundTombstone - Keep track of whether we find a tombstone while probing.
    const BucketT *FoundTombstone = nullptr;
    const KeyT EmptyKey = getEmptyKey();
    const KeyT TombstoneKey = getTombstoneKey();
    CHECK(!KeyInfoT::isEqual(Val, EmptyKey));
    CHECK(!KeyInfoT::isEqual(Val, TombstoneKey));

    unsigned BucketNo = getHashValue(Val) & (NumBuckets - 1);
    unsigned ProbeAmt = 1;
    while (true) {
      const BucketT *ThisBucket = BucketsPtr + BucketNo;
      // Found Val's bucket?  If so, return it.
      if (LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
        FoundBucket = ThisBucket;
        return true;
      }

      // If we found an empty bucket, the key doesn't exist in the set.
      // Insert it and return the default value.
      if (LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
        // If we've already seen a tombstone while probing, fill it in instead
        // of the empty bucket we eventually probed to.
        FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
        return false;
      }

      // If this is a tombstone, remember it.  If Val ends up not in the map, we
      // prefer to return it than something that would require more probing.
      if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
          !FoundTombstone)
        FoundTombstone = ThisBucket;  // Remember the first tombstone found.

      // Otherwise, it's a hash collision or a tombstone, continue quadratic
      // probing.
      BucketNo += ProbeAmt++;
      BucketNo &= (NumBuckets - 1);
    }
  }

  template <typename LookupKeyT>
  bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
    const BucketT *ConstFoundBucket;
    bool Result = const_cast<const DenseMapBase *>(this)->LookupBucketFor(
        Val, ConstFoundBucket);
    FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
    return Result;
  }

 public:
  /// 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.
  uptr getMemorySize() const {
    return RoundUpTo(getNumBuckets() * sizeof(BucketT), GetPageSizeCached());
  }
};

/// 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 DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
          typename BucketT>
bool operator==(
    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
  if (LHS.size() != RHS.size())
    return false;

  bool R = true;
  LHS.forEach(
      [&](const typename DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT,
                                      BucketT>::value_type &KV) -> bool {
        const auto *I = RHS.find(KV.first);
        if (!I || I->second != KV.second) {
          R = false;
          return false;
        }
        return true;
      });

  return R;
}

/// Inequality comparison for DenseMap.
///
/// Equivalent to !(LHS == RHS). See operator== for performance notes.
template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
          typename BucketT>
bool operator!=(
    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
  return !(LHS == RHS);
}

template <typename KeyT, typename ValueT,
          typename KeyInfoT = DenseMapInfo<KeyT>,
          typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
                                     KeyT, ValueT, KeyInfoT, BucketT> {
  friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

  // Lift some types from the dependent base class into this class for
  // simplicity of referring to them.
  using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

  BucketT *Buckets = nullptr;
  unsigned NumEntries = 0;
  unsigned NumTombstones = 0;
  unsigned NumBuckets = 0;

 public:
  /// Create a DenseMap with an optional \p InitialReserve that guarantee that
  /// this number of elements can be inserted in the map without grow()
  explicit DenseMap(unsigned InitialReserve) { init(InitialReserve); }
  constexpr DenseMap() = default;

  DenseMap(const DenseMap &other) : BaseT() {
    init(0);
    copyFrom(other);
  }

  DenseMap(DenseMap &&other) : BaseT() {
    init(0);
    swap(other);
  }

  ~DenseMap() {
    this->destroyAll();
    deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets);
  }

  void swap(DenseMap &RHS) {
    Swap(Buckets, RHS.Buckets);
    Swap(NumEntries, RHS.NumEntries);
    Swap(NumTombstones, RHS.NumTombstones);
    Swap(NumBuckets, RHS.NumBuckets);
  }

  DenseMap &operator=(const DenseMap &other) {
    if (&other != this)
      copyFrom(other);
    return *this;
  }

  DenseMap &operator=(DenseMap &&other) {
    this->destroyAll();
    deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
    init(0);
    swap(other);
    return *this;
  }

  void copyFrom(const DenseMap &other) {
    this->destroyAll();
    deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets);
    if (allocateBuckets(other.NumBuckets)) {
      this->BaseT::copyFrom(other);
    } else {
      NumEntries = 0;
      NumTombstones = 0;
    }
  }

  void init(unsigned InitNumEntries) {
    auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
    if (allocateBuckets(InitBuckets)) {
      this->BaseT::initEmpty();
    } else {
      NumEntries = 0;
      NumTombstones = 0;
    }
  }

  void grow(unsigned AtLeast) {
    unsigned OldNumBuckets = NumBuckets;
    BucketT *OldBuckets = Buckets;

    allocateBuckets(RoundUpToPowerOfTwo(Max<unsigned>(64, AtLeast)));
    CHECK(Buckets);
    if (!OldBuckets) {
      this->BaseT::initEmpty();
      return;
    }

    this->moveFromOldBuckets(OldBuckets, OldBuckets + OldNumBuckets);

    // Free the old table.
    deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets);
  }

 private:
  unsigned getNumEntries() const { return NumEntries; }

  void setNumEntries(unsigned Num) { NumEntries = Num; }

  unsigned getNumTombstones() const { return NumTombstones; }

  void setNumTombstones(unsigned Num) { NumTombstones = Num; }

  BucketT *getBuckets() const { return Buckets; }

  unsigned getNumBuckets() const { return NumBuckets; }

  bool allocateBuckets(unsigned Num) {
    NumBuckets = Num;
    if (NumBuckets == 0) {
      Buckets = nullptr;
      return false;
    }

    uptr Size = sizeof(BucketT) * NumBuckets;
    if (Size * 2 <= GetPageSizeCached()) {
      // We always allocate at least a page, so use entire space.
      unsigned Log2 = MostSignificantSetBitIndex(GetPageSizeCached() / Size);
      Size <<= Log2;
      NumBuckets <<= Log2;
      CHECK_EQ(Size, sizeof(BucketT) * NumBuckets);
      CHECK_GT(Size * 2, GetPageSizeCached());
    }
    Buckets = static_cast<BucketT *>(allocate_buffer(Size));
    return true;
  }

  static void *allocate_buffer(uptr Size) {
    return MmapOrDie(RoundUpTo(Size, GetPageSizeCached()), "DenseMap");
  }

  static void deallocate_buffer(void *Ptr, uptr Size) {
    UnmapOrDie(Ptr, RoundUpTo(Size, GetPageSizeCached()));
  }
};

}  // namespace __sanitizer

#endif  // SANITIZER_DENSE_MAP_H