[sanitizer] Fix DenseMap for compiler-rt

[vitalybuka]

Summary

Depends on D114047.

[vitalybuka]

rebase

[vitalybuka]

rebase

[vitalybuka]

fix missed tests

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h

73

Now it's more reasonable to rename Val to Key.

78

Now it's more reasonable to rename Val to Key.

84

Now it's more reasonable to rename Val to Key.

287

I think we can use existing RoundUpToPowerOfTwo here.

622

I think we can use existing RoundUpToPowerOfTwo here if remove - 1.

[melver]

compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h

80

If the header <type_traits> is safe to use from compiler-rt, we could static_assert(is_trivially_destructible<ValueT>....).

448

I think there's no reason for us to loose perfect forwarding.

We just have to open-code forward/move, like we already do for New() in compiler-rt/lib/tsan/rtl/tsan_mman.h.

This means we should also be able to provide emplace().

[vitalybuka]

use type_traits

compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h

80

I copied some stuff into sanitizer_type_traits.h and supported non trivially copiable/destructable types

compiler-rt/lib/sanitizer_common/CMakeLists.txt

set(SANITIZER_IMPL_HEADERS
   sanitizer_common_interceptors_ioctl.inc
   sanitizer_common_interface.inc
   sanitizer_common_interface_posix.inc
   sanitizer_common_syscalls.inc
   sanitizer_coverage_interface.inc
   sanitizer_dbghelp.h
   sanitizer_deadlock_detector.h
   sanitizer_deadlock_detector_interface.h
+  sanitizer_dense_map.h
+  sanitizer_dense_map_info.h
   sanitizer_errno.h
   sanitizer_errno_codes.h
   sanitizer_file.h
   sanitizer_flag_parser.h
   sanitizer_flags.h
   sanitizer_flags.inc
   sanitizer_flat_map.h
   sanitizer_freebsd.h

compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h

 //===- 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.
+// 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 {
-namespace detail {
-
-// We extend a pair to allow users to override the bucket type with their own
-// implementation without requiring two members.
-template <typename KeyT, typename ValueT>
-struct DenseMapPair : public std::pair<KeyT, ValueT> {
-  using std::pair<KeyT, ValueT>::pair;
-
-  KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }
-  const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }
-  ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; }
-  const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; }
-};
-
-}  // end namespace detail
-
-template <typename KeyT, typename ValueT,
-          typename KeyInfoT = DenseMapInfo<KeyT>,
-          typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>,
-          bool IsConst = false>
-class DenseMapIterator;
 
 template <typename DerivedT, 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;
-
+class DenseMapBase {
  public:
   using size_type = unsigned;
   using key_type = KeyT;
   using mapped_type = ValueT;
   using value_type = BucketT;
 
-  LLVM_NODISCARD bool empty() const { return getNumEntries() == 0; }
+  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);
-    incrementEpoch();
     if (NumBuckets > getNumBuckets())
       grow(NumBuckets);
   }
 
   void clear() {
-    incrementEpoch();
     if (getNumEntries() == 0 && getNumTombstones() == 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;
-    }
-
     const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
-    if (std::is_trivially_destructible<ValueT>::value) {
+    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;
         }
       }
-      assert(NumEntries == 0 && "Node count imbalance!");
+      CHECK_EQ(NumEntries, 0);
     }
     setNumEntries(0);
     setNumTombstones(0);
   }
 
   /// Return 1 if the specified key is in the map, 0 otherwise.
-  size_type count(const_arg_type_t<KeyT> Val) const {
+  size_type count(const KeyT &Key) const {
     const BucketT *TheBucket;
-    return LookupBucketFor(Val, TheBucket) ? 1 : 0;
+    return LookupBucketFor(Key, TheBucket) ? 1 : 0;
   }
 
-  iterator find(const_arg_type_t<KeyT> Val) {
+  value_type *find(const KeyT &Key) {
     BucketT *TheBucket;
-    if (LookupBucketFor(Val, TheBucket))
-      return makeIterator(
-          TheBucket,
-          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
-          true);
-    return end();
+    if (LookupBucketFor(Key, TheBucket))
+      return TheBucket;
+    return nullptr;
   }
-  const_iterator find(const_arg_type_t<KeyT> Val) const {
+  const value_type *find(const KeyT &Key) const {
     const BucketT *TheBucket;
-    if (LookupBucketFor(Val, TheBucket))
-      return makeConstIterator(
-          TheBucket,
-          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
-          true);
-    return end();
+    if (LookupBucketFor(Key, TheBucket))
+      return TheBucket;
+    return nullptr;
   }
 
   /// 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>
-  iterator find_as(const LookupKeyT &Val) {
+  value_type *find_as(const LookupKeyT &Key) {
     BucketT *TheBucket;
-    if (LookupBucketFor(Val, TheBucket))
-      return makeIterator(
-          TheBucket,
-          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
-          true);
-    return end();
+    if (LookupBucketFor(Key, TheBucket))
+      return TheBucket;
+    return nullptr;
   }
   template <class LookupKeyT>
-  const_iterator find_as(const LookupKeyT &Val) const {
+  const value_type *find_as(const LookupKeyT &Key) const {
     const BucketT *TheBucket;
-    if (LookupBucketFor(Val, TheBucket))
-      return makeConstIterator(
-          TheBucket,
-          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
-          true);
-    return end();
+    if (LookupBucketFor(Key, TheBucket))
+      return TheBucket;
+    return nullptr;
   }
 
   /// lookup - Return the entry for the specified key, or a default
   /// constructed value if no such entry exists.
-  ValueT lookup(const_arg_type_t<KeyT> Val) const {
+  ValueT lookup(const KeyT &Key) const {
     const BucketT *TheBucket;
-    if (LookupBucketFor(Val, TheBucket))
+    if (LookupBucketFor(Key, TheBucket))
       return TheBucket->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.
-  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
+  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.
-  std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
-    return try_emplace(std::move(KV.first), std::move(KV.second));
+  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>
-  std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&...Args) {
+  detail::DenseMapPair<value_type *, bool> try_emplace(KeyT &&Key,
+                                                       Ts &&...Args) {
     BucketT *TheBucket;
     if (LookupBucketFor(Key, TheBucket))
-      return std::make_pair(
-          makeIterator(
-              TheBucket,
-              shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-              *this, true),
-          false);  // Already in map.
+      return {TheBucket, false};  // Already in map.
 
     // Otherwise, insert the new element.
-    TheBucket =
-        InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
-    return std::make_pair(
-        makeIterator(
-            TheBucket,
-            shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-            *this, true),
-        true);
+    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>
-  std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&...Args) {
+  detail::DenseMapPair<value_type *, bool> try_emplace(const KeyT &Key,
+                                                       Ts &&...Args) {
     BucketT *TheBucket;
     if (LookupBucketFor(Key, TheBucket))
-      return std::make_pair(
-          makeIterator(
-              TheBucket,
-              shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-              *this, true),
-          false);  // Already in map.
+      return {TheBucket, false};  // Already in map.
 
     // Otherwise, insert the new element.
-    TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
-    return std::make_pair(
-        makeIterator(
-            TheBucket,
-            shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-            *this, true),
-        true);
+    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>
-  std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,
+  detail::DenseMapPair<value_type *, bool> insert_as(value_type &&KV,
                                                      const LookupKeyT &Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return std::make_pair(
-          makeIterator(
-              TheBucket,
-              shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-              *this, true),
-          false);  // Already in map.
+      return {TheBucket, false};  // Already in map.
 
     // Otherwise, insert the new element.
-    TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
-                                           std::move(KV.second), Val);
-    return std::make_pair(
-        makeIterator(
-            TheBucket,
-            shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-            *this, true),
-        true);
-  }
-
-  /// insert - Range insertion of pairs.
-  template <typename InputIt>
-  void insert(InputIt I, InputIt E) {
-    for (; I != E; ++I) insert(*I);
+    TheBucket =
+        InsertIntoBucketWithLookup(TheBucket, __sanitizer::move(KV.first),
+                                   __sanitizer::move(KV.second), Val);
+    return {TheBucket, true};
   }
 
   bool erase(const KeyT &Val) {
     BucketT *TheBucket;
     if (!LookupBucketFor(Val, TheBucket))
       return false;  // not in map.
 
     TheBucket->getSecond().~ValueT();
     TheBucket->getFirst() = getTombstoneKey();
     decrementNumEntries();
     incrementNumTombstones();
     return true;
   }
-  void erase(iterator I) {
+
+  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, std::move(Key));
+    return *InsertIntoBucket(TheBucket, __sanitizer::move(Key));
   }
 
   ValueT &operator[](KeyT &&Key) {
-    return FindAndConstruct(std::move(Key)).second;
+    return FindAndConstruct(__sanitizer::move(Key)).second;
+  }
+
+  /// 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).
+  bool operator==(const DenseMapBase &RHS) const {
+    if (size() != RHS.size())
+      return false;
+
+    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)) {
+        const auto *I = RHS.find(K);
+        if (!I || P->getSecond() != I->getSecond())
+          return false;
+      }
+    }
+
+    return true;
   }
 
  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);
 
-    assert((getNumBuckets() & (getNumBuckets() - 1)) == 0 &&
-           "# initial buckets must be a power of two!");
+    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 NextPowerOf2(NumEntries * 4 / 3 + 1);
+    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.
-        assert(!FoundVal && "Key already in new map?");
-        DestBucket->getFirst() = std::move(B->getFirst());
-        ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
+        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) {
-    assert(&other != this);
-    assert(getNumBuckets() == other.getNumBuckets());
+    CHECK_NE(&other, this);
+    CHECK_EQ(getNumBuckets(), other.getNumBuckets());
 
     setNumEntries(other.getNumEntries());
     setNumTombstones(other.getNumTombstones());
 
-    if (std::is_trivially_copyable<KeyT>::value &&
-        std::is_trivially_copyable<ValueT>::value)
-      memcpy(reinterpret_cast<void *>(getBuckets()), other.getBuckets(),
-             getNumBuckets() * sizeof(BucketT));
+    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 (size_t i = 0; i < getNumBuckets(); ++i) {
+      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() {
-    static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
-                  "Must pass the derived type to this template!");
-    return KeyInfoT::getEmptyKey();
-  }
+  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();
   }
 
private:
   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() = std::forward<KeyArg>(Key);
-    ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
+    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() = std::move(Key);
-    ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
+    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 (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
+    if (UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
       this->grow(NumBuckets * 2);
       LookupBucketFor(Lookup, TheBucket);
       NumBuckets = getNumBuckets();
-    } else if (LLVM_UNLIKELY(NumBuckets -
-                                 (NewNumEntries + getNumTombstones()) <=
-                             NumBuckets / 8)) {
+    } else if (UNLIKELY(NumBuckets - (NewNumEntries + getNumTombstones()) <=
       this->grow(NumBuckets);
       LookupBucketFor(Lookup, TheBucket);
     }
-    assert(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))
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();
-    assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
-           !KeyInfoT::isEqual(Val, TombstoneKey) &&
-           "Empty/Tombstone value shouldn't be inserted into map!");
+    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 (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
+      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 (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
+      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.
bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
     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.
-  size_t getMemorySize() const { return getNumBuckets() * sizeof(BucketT); }
+  uptr getMemorySize() const {
+    return RoundUpTo(getNumBuckets() * sizeof(BucketT), GetPageSizeCached());
+  }
 };
 
 /// 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 = llvm::detail::DenseMapPair<KeyT, ValueT>>
+          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;
-  unsigned NumEntries;
-  unsigned NumTombstones;
-  unsigned NumBuckets;
+  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 = 0) { init(InitialReserve); }
+  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);
   }
 
-  template <typename InputIt>
-  DenseMap(const InputIt &I, const InputIt &E) {
-    init(std::distance(I, E));
-    this->insert(I, E);
-  }
-
-  DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
-    init(Vals.size());
-    this->insert(Vals.begin(), Vals.end());
-  }
-
   ~DenseMap() {
     this->destroyAll();
-    deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
+    deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets);
   }
 
   void swap(DenseMap &RHS) {
-    this->incrementEpoch();
-    RHS.incrementEpoch();
-    std::swap(Buckets, RHS.Buckets);
-    std::swap(NumEntries, RHS.NumEntries);
-    std::swap(NumTombstones, RHS.NumTombstones);
-    std::swap(NumBuckets, RHS.NumBuckets);
+    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, alignof(BucketT));
+    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(std::max<unsigned>(
-        64, static_cast<unsigned>(NextPowerOf2(AtLeast - 1))));
-    assert(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,
-                      alignof(BucketT));
+    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;
     }
 
-    Buckets = static_cast<BucketT *>(
-        allocate_buffer(sizeof(BucketT) * NumBuckets, alignof(BucketT)));
+    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

compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h

 //===- sanitizer_dense_map_info.h - Type traits for DenseMap ----*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SANITIZER_DENSE_MAP_INFO_H
 #define SANITIZER_DENSE_MAP_INFO_H
 
+#include "sanitizer_common.h"
 #include "sanitizer_internal_defs.h"
+#include "sanitizer_type_traits.h"
 
 namespace __sanitizer {
 
 namespace detail {
 
 /// Simplistic combination of 32-bit hash values into 32-bit hash values.
 static inline unsigned combineHashValue(unsigned a, unsigned b) {
-  uint64_t key = (uint64_t)a << 32 | (uint64_t)b;
+  u64 key = (u64)a << 32 | (u64)b;
   key += ~(key << 32);
   key ^= (key >> 22);
   key += ~(key << 13);
   key ^= (key >> 8);
   key += (key << 3);
   key ^= (key >> 15);
   key += ~(key << 27);
   key ^= (key >> 31);
   return (unsigned)key;
 }
 
+// We extend a pair to allow users to override the bucket type with their own
+// implementation without requiring two members.
+template <typename KeyT, typename ValueT>
+struct DenseMapPair {
+  KeyT first = {};
+  ValueT second = {};
+  DenseMapPair() = default;
+  DenseMapPair(const KeyT &f, const ValueT &s) : first(f), second(s) {}
+
+  template <typename KeyT2, typename ValueT2>
+  DenseMapPair(KeyT2 &&f, ValueT2 &&s)
+      : first(__sanitizer::forward<KeyT2>(f)),
+        second(__sanitizer::forward<ValueT2>(s)) {}
+
+  DenseMapPair(const DenseMapPair &other) = default;
+  DenseMapPair &operator=(const DenseMapPair &other) = default;
+  DenseMapPair(DenseMapPair &&other) = default;
+  DenseMapPair &operator=(DenseMapPair &&other) = default;
+
+  KeyT &getFirst() { return first; }
+  const KeyT &getFirst() const { return first; }
+  ValueT &getSecond() { return second; }
+  const ValueT &getSecond() const { return second; }
+};
+
 }  // end namespace detail
 
 template <typename T>
 struct DenseMapInfo {
   // static inline T getEmptyKey();
   // static inline T getTombstoneKey();
   // static unsigned getHashValue(const T &Val);
   // static bool isEqual(const T &LHS, const T &RHS);
 };
 
 // Provide DenseMapInfo for all pointers. Come up with sentinel pointer values
 // that are aligned to alignof(T) bytes, but try to avoid requiring T to be
 // complete. This allows clients to instantiate DenseMap<T*, ...> with forward
 // declared key types. Assume that no pointer key type requires more than 4096
 // bytes of alignment.
 template <typename T>
 struct DenseMapInfo<T *> {
   // The following should hold, but it would require T to be complete:
   // static_assert(alignof(T) <= (1 << Log2MaxAlign),
   //               "DenseMap does not support pointer keys requiring more than "
   //               "Log2MaxAlign bits of alignment");
-  static constexpr uintptr_t Log2MaxAlign = 12;
+  static constexpr uptr Log2MaxAlign = 12;
 
   static inline T *getEmptyKey() {
-    uintptr_t Val = static_cast<uintptr_t>(-1);
+    uptr Val = static_cast<uptr>(-1);
     Val <<= Log2MaxAlign;
     return reinterpret_cast<T *>(Val);
   }
 
   static inline T *getTombstoneKey() {
-    uintptr_t Val = static_cast<uintptr_t>(-2);
+    uptr Val = static_cast<uptr>(-2);
     Val <<= Log2MaxAlign;
     return reinterpret_cast<T *>(Val);
   }
 
   static unsigned getHashValue(const T *PtrVal) {
-    return (unsigned((uintptr_t)PtrVal) >> 4) ^
-           (unsigned((uintptr_t)PtrVal) >> 9);
+    return (unsigned((uptr)PtrVal) >> 4) ^ (unsigned((uptr)PtrVal) >> 9);
   }
 
   static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
 };
 
 // Provide DenseMapInfo for chars.
 template <>
 struct DenseMapInfo<char> {
struct DenseMapInfo<long long> {
 
   static bool isEqual(const long long &LHS, const long long &RHS) {
     return LHS == RHS;
   }
 };
 
 // Provide DenseMapInfo for all pairs whose members have info.
 template <typename T, typename U>
-struct DenseMapInfo<std::pair<T, U>> {
-  using Pair = std::pair<T, U>;
+struct DenseMapInfo<detail::DenseMapPair<T, U>> {
+  using Pair = detail::DenseMapPair<T, U>;
   using FirstInfo = DenseMapInfo<T>;
   using SecondInfo = DenseMapInfo<U>;
 
   static inline Pair getEmptyKey() {
-    return std::make_pair(FirstInfo::getEmptyKey(), SecondInfo::getEmptyKey());
+    return detail::DenseMapPair<T, U>(FirstInfo::getEmptyKey(),
+                                      SecondInfo::getEmptyKey());
   }
 
   static inline Pair getTombstoneKey() {
-    return std::make_pair(FirstInfo::getTombstoneKey(),
+    return detail::DenseMapPair<T, U>(FirstInfo::getTombstoneKey(),
                                       SecondInfo::getTombstoneKey());
   }
 
   static unsigned getHashValue(const Pair &PairVal) {
     return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first),
                                     SecondInfo::getHashValue(PairVal.second));
   }
 
   static bool isEqual(const Pair &LHS, const Pair &RHS) {
     return FirstInfo::isEqual(LHS.first, RHS.first) &&
            SecondInfo::isEqual(LHS.second, RHS.second);
   }
 };
 
 }  // namespace __sanitizer
 
 #endif  // SANITIZER_DENSE_MAP_INFO_H

compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt

set(SANITIZER_UNITTESTS
   sanitizer_addrhashmap_test.cpp
   sanitizer_allocator_test.cpp
   sanitizer_atomic_test.cpp
   sanitizer_bitvector_test.cpp
   sanitizer_bvgraph_test.cpp
   sanitizer_chained_origin_depot_test.cpp
   sanitizer_common_test.cpp
   sanitizer_deadlock_detector_test.cpp
+  sanitizer_dense_map_test.cpp
   sanitizer_flags_test.cpp
   sanitizer_flat_map_test.cpp
   sanitizer_format_interceptor_test.cpp
   sanitizer_hash_test.cpp
   sanitizer_ioctl_test.cpp
   sanitizer_libc_test.cpp
   sanitizer_linux_test.cpp
   sanitizer_list_test.cpp

compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp

 #include <set>
 
 #include "gtest/gtest.h"
 
 using namespace __sanitizer;
 
 namespace {
 
+// Helps to keep some tests.
+template <typename KeyT, typename ValueT,
+          typename KeyInfoT = DenseMapInfo<KeyT>>
+class TestDenseMap : public DenseMap<KeyT, ValueT, KeyInfoT> {
+  using BaseT = DenseMap<KeyT, ValueT, KeyInfoT>;
+
+ public:
+  using BaseT::BaseT;
+
+  TestDenseMap(std::initializer_list<typename BaseT::value_type> Vals)
+      : BaseT(Vals.size()) {
+    for (const auto &V : Vals) this->BaseT::insert(V);
+  }
+
+  template <typename I>
+  TestDenseMap(I B, I E) : BaseT(std::distance(B, E)) {
+    for (; B != E; ++B) this->BaseT::insert(*B);
+  }
+};
+
+template <typename... T>
+using DenseMap = TestDenseMap<T...>;
+
 uint32_t getTestKey(int i, uint32_t *) { return i; }
 uint32_t getTestValue(int i, uint32_t *) { return 42 + i; }
 
 uint32_t *getTestKey(int i, uint32_t **) {
   static uint32_t dummy_arr1[8192];
   assert(i < 8192 && "Only support 8192 dummy keys.");
   return &dummy_arr1[i];
 }

 };
 
 template <typename T>
 typename T::key_type *const DenseMapTest<T>::dummy_key_ptr = nullptr;
 template <typename T>
 typename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = nullptr;
 
 // Register these types for testing.
-typedef ::testing::Types<
-    DenseMap<uint32_t, uint32_t>, DenseMap<uint32_t *, uint32_t *>,
-    DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>,
-    SmallDenseMap<uint32_t, uint32_t>, SmallDenseMap<uint32_t *, uint32_t *>,
-    SmallDenseMap<CtorTester, CtorTester, 4, CtorTesterMapInfo>>
+typedef ::testing::Types<DenseMap<uint32_t, uint32_t>,
+                         DenseMap<uint32_t *, uint32_t *>,
+                         DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>>
     DenseMapTestTypes;
 TYPED_TEST_SUITE(DenseMapTest, DenseMapTestTypes, );
 
 // Empty map tests
 TYPED_TEST(DenseMapTest, EmptyIntMapTest) {
   // Size tests
   EXPECT_EQ(0u, this->Map.size());
   EXPECT_TRUE(this->Map.empty());
 
-  // Iterator tests
-  EXPECT_TRUE(this->Map.begin() == this->Map.end());
-
   // Lookup tests
   EXPECT_FALSE(this->Map.count(this->getKey()));
-  EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.end());
+  EXPECT_EQ(nullptr, this->Map.find(this->getKey()));
   EXPECT_EQ(typename TypeParam::mapped_type(),
             this->Map.lookup(this->getKey()));
 }
 
 // Constant map tests
 TYPED_TEST(DenseMapTest, ConstEmptyMapTest) {
   const TypeParam &ConstMap = this->Map;
   EXPECT_EQ(0u, ConstMap.size());
   EXPECT_TRUE(ConstMap.empty());
-  EXPECT_TRUE(ConstMap.begin() == ConstMap.end());
 }
 
 // A map with a single entry
 TYPED_TEST(DenseMapTest, SingleEntryMapTest) {
   this->Map[this->getKey()] = this->getValue();
 
   // Size tests
   EXPECT_EQ(1u, this->Map.size());
-  EXPECT_FALSE(this->Map.begin() == this->Map.end());
   EXPECT_FALSE(this->Map.empty());
 
-  // Iterator tests
-  typename TypeParam::iterator it = this->Map.begin();
-  EXPECT_EQ(this->getKey(), it->first);
-  EXPECT_EQ(this->getValue(), it->second);
-  ++it;
-  EXPECT_TRUE(it == this->Map.end());
-
   // Lookup tests
   EXPECT_TRUE(this->Map.count(this->getKey()));
-  EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.begin());
+  EXPECT_NE(nullptr, this->Map.find(this->getKey()));
   EXPECT_EQ(this->getValue(), this->Map.lookup(this->getKey()));
   EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);
 }
 
 // Test clear() method
 TYPED_TEST(DenseMapTest, ClearTest) {
   this->Map[this->getKey()] = this->getValue();
   this->Map.clear();
 
   EXPECT_EQ(0u, this->Map.size());
   EXPECT_TRUE(this->Map.empty());
-  EXPECT_TRUE(this->Map.begin() == this->Map.end());
 }
 
 // Test erase(iterator) method
 TYPED_TEST(DenseMapTest, EraseTest) {
   this->Map[this->getKey()] = this->getValue();
-  this->Map.erase(this->Map.begin());
+  this->Map.erase(this->Map.find(this->getKey()));
 
   EXPECT_EQ(0u, this->Map.size());
   EXPECT_TRUE(this->Map.empty());
-  EXPECT_TRUE(this->Map.begin() == this->Map.end());
 }
 
 // Test erase(value) method
 TYPED_TEST(DenseMapTest, EraseTest2) {
   this->Map[this->getKey()] = this->getValue();
   this->Map.erase(this->getKey());
 
   EXPECT_EQ(0u, this->Map.size());
   EXPECT_TRUE(this->Map.empty());
-  EXPECT_TRUE(this->Map.begin() == this->Map.end());
 }
 
 // Test insert() method
 TYPED_TEST(DenseMapTest, InsertTest) {
-  this->Map.insert(std::make_pair(this->getKey(), this->getValue()));
+  this->Map.insert(
+      typename TypeParam::value_type(this->getKey(), this->getValue()));
   EXPECT_EQ(1u, this->Map.size());
   EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);
 }
 
 // Test copy constructor method
 TYPED_TEST(DenseMapTest, CopyConstructorTest) {
   this->Map[this->getKey()] = this->getValue();
   TypeParam copyMap(this->Map);
TEST(DenseMapCustomTest, EqualityComparison) {
   EXPECT_EQ(M1, M2);
   EXPECT_NE(M1, M3);
 }
 
 // Test for the default minimum size of a DenseMap
 TEST(DenseMapCustomTest, DefaultMinReservedSizeTest) {
   // IF THIS VALUE CHANGE, please update InitialSizeTest, InitFromIterator, and
   // ReserveTest as well!
-  const int ExpectedInitialBucketCount = 64;
+  const int ExpectedInitialBucketCount = 512;
   // Formula from DenseMap::getMinBucketToReserveForEntries()
   const int ExpectedMaxInitialEntries = ExpectedInitialBucketCount * 3 / 4 - 1;
 
   DenseMap<int, CountCopyAndMove> Map;
   // Will allocate 64 buckets
   Map.reserve(1);
   unsigned MemorySize = Map.getMemorySize();
   CountCopyAndMove::Copy = 0;
   CountCopyAndMove::Move = 0;
-  for (int i = 0; i < ExpectedMaxInitialEntries; ++i)
-    Map.insert(std::pair<int, CountCopyAndMove>(std::piecewise_construct,
-                                                std::forward_as_tuple(i),
-                                                std::forward_as_tuple()));
+  for (int i = 0; i < ExpectedMaxInitialEntries; ++i) {
+    detail::DenseMapPair<int, CountCopyAndMove> KV;
+    KV.first = i;
+    Map.insert(move(KV));
+  }
   // Check that we didn't grow
   EXPECT_EQ(MemorySize, Map.getMemorySize());
   // Check that move was called the expected number of times
   EXPECT_EQ(ExpectedMaxInitialEntries, CountCopyAndMove::Move);
   // Check that no copy occurred
   EXPECT_EQ(0, CountCopyAndMove::Copy);
 
   // Adding one extra element should grow the map
-  Map.insert(std::pair<int, CountCopyAndMove>(
-      std::piecewise_construct,
-      std::forward_as_tuple(ExpectedMaxInitialEntries),
-      std::forward_as_tuple()));
+  detail::DenseMapPair<int, CountCopyAndMove> KV;
+  KV.first = ExpectedMaxInitialEntries;
+  Map.insert(move(KV));
   // Check that we grew
   EXPECT_NE(MemorySize, Map.getMemorySize());
   // Check that move was called the expected number of times
   //  This relies on move-construction elision, and cannot be reliably tested.
   //   EXPECT_EQ(ExpectedMaxInitialEntries + 2, CountCopyAndMove::Move);
   // Check that no copy occurred
   EXPECT_EQ(0, CountCopyAndMove::Copy);
 }
 
 // Make sure creating the map with an initial size of N actually gives us enough
 // buckets to insert N items without increasing allocation size.
 TEST(DenseMapCustomTest, InitialSizeTest) {
-  // Test a few different sizes, 48 is *not* a random choice: we need a value
+  // Test a few different size, 341 is *not* a random choice: we need a value
   // that is 2/3 of a power of two to stress the grow() condition, and the power
-  // of two has to be at least 64 because of minimum size allocation in the
-  // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the
-  // 64 default init.
-  for (auto Size : {1, 2, 48, 66}) {
+  // of two has to be at least 512 because of minimum size allocation in the
+  // DenseMap (see DefaultMinReservedSizeTest). 513 is a value just above the
+  // 512 default init.
+  for (auto Size : {1, 2, 48, 66, 341, 513}) {
     DenseMap<int, CountCopyAndMove> Map(Size);
     unsigned MemorySize = Map.getMemorySize();
     CountCopyAndMove::Copy = 0;
     CountCopyAndMove::Move = 0;
-    for (int i = 0; i < Size; ++i)
-      Map.insert(std::pair<int, CountCopyAndMove>(std::piecewise_construct,
-                                                  std::forward_as_tuple(i),
-                                                  std::forward_as_tuple()));
+    for (int i = 0; i < Size; ++i) {
+      detail::DenseMapPair<int, CountCopyAndMove> KV;
+      KV.first = i;
+      Map.insert(move(KV));
+    }
     // Check that we didn't grow
     EXPECT_EQ(MemorySize, Map.getMemorySize());
     // Check that move was called the expected number of times
     EXPECT_EQ(Size, CountCopyAndMove::Move);
     // Check that no copy occurred
     EXPECT_EQ(0, CountCopyAndMove::Copy);
   }
 }
 
 // Make sure creating the map with a iterator range does not trigger grow()
 TEST(DenseMapCustomTest, InitFromIterator) {
-  std::vector<std::pair<int, CountCopyAndMove>> Values;
+  std::vector<detail::DenseMapPair<int, CountCopyAndMove>> Values;
   // The size is a random value greater than 64 (hardcoded DenseMap min init)
   const int Count = 65;
   for (int i = 0; i < Count; i++) Values.emplace_back(i, CountCopyAndMove());
 
   CountCopyAndMove::Move = 0;
   CountCopyAndMove::Copy = 0;
   DenseMap<int, CountCopyAndMove> Map(Values.begin(), Values.end());
   // Check that no move occurred
   EXPECT_EQ(0, CountCopyAndMove::Move);
   // Check that copy was called the expected number of times
   EXPECT_EQ(Count, CountCopyAndMove::Copy);
 }
 
 // Make sure reserve actually gives us enough buckets to insert N items
 // without increasing allocation size.
 TEST(DenseMapCustomTest, ReserveTest) {
-  // Test a few different size, 48 is *not* a random choice: we need a value
+  // Test a few different size, 341 is *not* a random choice: we need a value
   // that is 2/3 of a power of two to stress the grow() condition, and the power
-  // of two has to be at least 64 because of minimum size allocation in the
-  // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the
-  // 64 default init.
-  for (auto Size : {1, 2, 48, 66}) {
+  // of two has to be at least 512 because of minimum size allocation in the
+  // DenseMap (see DefaultMinReservedSizeTest). 513 is a value just above the
+  // 512 default init.
+  for (auto Size : {1, 2, 48, 66, 341, 513}) {
     DenseMap<int, CountCopyAndMove> Map;
     Map.reserve(Size);
     unsigned MemorySize = Map.getMemorySize();
     CountCopyAndMove::Copy = 0;
     CountCopyAndMove::Move = 0;
-    for (int i = 0; i < Size; ++i)
-      Map.insert(std::pair<int, CountCopyAndMove>(std::piecewise_construct,
-                                                  std::forward_as_tuple(i),
-                                                  std::forward_as_tuple()));
+    for (int i = 0; i < Size; ++i) {
+      detail::DenseMapPair<int, CountCopyAndMove> KV;
+      KV.first = i;
+      Map.insert(move(KV));
+    }
     // Check that we didn't grow
     EXPECT_EQ(MemorySize, Map.getMemorySize());
     // Check that move was called the expected number of times
     EXPECT_EQ(Size, CountCopyAndMove::Move);
     // Check that no copy occurred
     EXPECT_EQ(0, CountCopyAndMove::Copy);
   }
 }
TEST(DenseMapCustomTest, FindAsTest) {
   // Size tests
   EXPECT_EQ(3u, map.size());
 
   // Normal lookup tests
   EXPECT_EQ(1u, map.count(1));
   EXPECT_EQ(1u, map.find(0)->second);
   EXPECT_EQ(2u, map.find(1)->second);
   EXPECT_EQ(3u, map.find(2)->second);
-  EXPECT_TRUE(map.find(3) == map.end());
+  EXPECT_EQ(nullptr, map.find(3));
 
   // find_as() tests
   EXPECT_EQ(1u, map.find_as("a")->second);
   EXPECT_EQ(2u, map.find_as("b")->second);
   EXPECT_EQ(3u, map.find_as("c")->second);
-  EXPECT_TRUE(map.find_as("d") == map.end());
+  EXPECT_EQ(nullptr, map.find_as("d"));
 }
 
 TEST(DenseMapCustomTest, TryEmplaceTest) {
   DenseMap<int, std::unique_ptr<int>> Map;
   std::unique_ptr<int> P(new int(2));
   auto Try1 = Map.try_emplace(0, new int(1));
   EXPECT_TRUE(Try1.second);
   auto Try2 = Map.try_emplace(0, std::move(P));
TEST(DenseMapCustomTest, OpaquePointerKey) {
   Map.insert({K1, 1});
   Map.insert({K2, 2});
   Map.insert({K3, 3});
   EXPECT_EQ(Map.count(K1), 1u);
   EXPECT_EQ(Map[K1], 1);
   EXPECT_EQ(Map[K2], 2);
   EXPECT_EQ(Map[K3], 3);
   Map.clear();
-  EXPECT_EQ(Map.find(K1), Map.end());
-  EXPECT_EQ(Map.find(K2), Map.end());
-  EXPECT_EQ(Map.find(K3), Map.end());
+  EXPECT_EQ(nullptr, Map.find(K1));
+  EXPECT_EQ(nullptr, Map.find(K2));
+  EXPECT_EQ(nullptr, Map.find(K3));
 }
 }  // namespace

llvm/utils/gn/secondary/compiler-rt/lib/sanitizer_common/BUILD.gn

sources = [
     "sanitizer_coverage_fuchsia.cpp",
     "sanitizer_coverage_libcdep_new.cpp",
     "sanitizer_coverage_win_sections.cpp",
     "sanitizer_dbghelp.h",
     "sanitizer_deadlock_detector.h",
     "sanitizer_deadlock_detector1.cpp",
     "sanitizer_deadlock_detector2.cpp",
     "sanitizer_deadlock_detector_interface.h",
+    "sanitizer_dense_map.h",
+    "sanitizer_dense_map_info.h",
     "sanitizer_errno.cpp",
     "sanitizer_errno.h",
     "sanitizer_errno_codes.h",
     "sanitizer_file.cpp",
     "sanitizer_file.h",
     "sanitizer_flag_parser.cpp",
     "sanitizer_flag_parser.h",
     "sanitizer_flags.cpp",