[NFC][sanitizer] Clang format copied code

[vitalybuka]

Summary

No other changes.

Depends on D114045.

compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h

 //===- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the DenseMap class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_DENSEMAP_H
 #define LLVM_ADT_DENSEMAP_H
 
-#include "llvm/ADT/DenseMapInfo.h"
-#include "llvm/ADT/EpochTracker.h"
-#include "llvm/Support/AlignOf.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>
 
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/EpochTracker.h"
+#include "llvm/Support/AlignOf.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"
+
 namespace llvm {
 
 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
+}  // 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;
 
  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>;
inline const_iterator begin() const {
     if (shouldReverseIterate<KeyT>())
       return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this);
     return makeConstIterator(getBuckets(), getBucketsEnd(), *this);
   }
   inline const_iterator end() const {
     return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
   }
 
-  LLVM_NODISCARD bool empty() const {
-    return getNumEntries() == 0;
-  }
+  LLVM_NODISCARD 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 (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;
     }
 
public:
   size_type count(const_arg_type_t<KeyT> Val) const {
     const BucketT *TheBucket;
     return LookupBucketFor(Val, TheBucket) ? 1 : 0;
   }
 
   iterator find(const_arg_type_t<KeyT> Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return makeIterator(TheBucket,
-                          shouldReverseIterate<KeyT>() ? getBuckets()
-                                                       : getBucketsEnd(),
-                          *this, true);
+      return makeIterator(
+          TheBucket,
+          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
+          true);
     return end();
   }
   const_iterator find(const_arg_type_t<KeyT> Val) const {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return makeConstIterator(TheBucket,
-                               shouldReverseIterate<KeyT>() ? getBuckets()
-                                                            : getBucketsEnd(),
-                               *this, true);
+      return makeConstIterator(
+          TheBucket,
+          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
+          true);
     return end();
   }
 
   /// 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>
+  template <class LookupKeyT>
   iterator find_as(const LookupKeyT &Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return makeIterator(TheBucket,
-                          shouldReverseIterate<KeyT>() ? getBuckets()
-                                                       : getBucketsEnd(),
-                          *this, true);
+      return makeIterator(
+          TheBucket,
+          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
+          true);
     return end();
   }
-  template<class LookupKeyT>
+  template <class LookupKeyT>
   const_iterator find_as(const LookupKeyT &Val) const {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return makeConstIterator(TheBucket,
-                               shouldReverseIterate<KeyT>() ? getBuckets()
-                                                            : getBucketsEnd(),
-                               *this, true);
+      return makeConstIterator(
+          TheBucket,
+          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
+          true);
     return end();
   }
 
   /// 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 {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
public:
   std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
     return try_emplace(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) {
+  std::pair<iterator, 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 std::make_pair(
+          makeIterator(
+              TheBucket,
+              shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
+          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);
+    return std::make_pair(
+        makeIterator(
+            TheBucket,
+            shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
   }
 
   // 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) {
+  std::pair<iterator, 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 std::make_pair(
+          makeIterator(
+              TheBucket,
+              shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
+          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);
+    return std::make_pair(
+        makeIterator(
+            TheBucket,
+            shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
   }
 
   /// 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 std::make_pair(makeIterator(TheBucket,
-                                         shouldReverseIterate<KeyT>()
-                                             ? getBuckets()
-                                             : getBucketsEnd(),
-                                         *this, true),
-                            false); // Already in map.
+      return std::make_pair(
+          makeIterator(
+              TheBucket,
+              shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
+          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);
+    return std::make_pair(
+        makeIterator(
+            TheBucket,
+            shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
   }
 
   /// insert - Range insertion of pairs.
-  template<typename InputIt>
+  template <typename InputIt>
   void insert(InputIt I, InputIt E) {
-    for (; I != E; ++I)
-      insert(*I);
+    for (; I != E; ++I) insert(*I);
   }
 
   bool erase(const KeyT &Val) {
     BucketT *TheBucket;
     if (!LookupBucketFor(Val, TheBucket))
-      return false; // not in map.
+      return false;  // not in map.
 
     TheBucket->getSecond().~ValueT();
     TheBucket->getFirst() = getTombstoneKey();
     decrementNumEntries();
     incrementNumTombstones();
     return true;
   }
   void erase(iterator I) {
     BucketT *TheBucket = &*I;
     TheBucket->getSecond().~ValueT();
     TheBucket->getFirst() = getTombstoneKey();
     decrementNumEntries();
     incrementNumTombstones();
   }
 
-  value_type& FindAndConstruct(const KeyT &Key) {
+  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;
-  }
+  ValueT &operator[](const KeyT &Key) { return FindAndConstruct(Key).second; }
 
-  value_type& FindAndConstruct(KeyT &&Key) {
+  value_type &FindAndConstruct(KeyT &&Key) {
     BucketT *TheBucket;
     if (LookupBucketFor(Key, TheBucket))
       return *TheBucket;
 
     return *InsertIntoBucket(TheBucket, std::move(Key));
   }
 
   ValueT &operator[](KeyT &&Key) {
     return FindAndConstruct(std::move(Key)).second;
   }
 
   /// isPointerIntoBucketsArray - Return true if the specified pointer points
   /// somewhere into the DenseMap's array of buckets (i.e. either to a key or
   /// value in the DenseMap).
   bool isPointerIntoBucketsArray(const void *Ptr) const {
     return Ptr >= getBuckets() && Ptr < getBucketsEnd();
   }
 
   /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
   /// array.  In conjunction with the previous method, this can be used to
   /// determine whether an insertion caused the DenseMap to reallocate.
   const void *getPointerIntoBucketsArray() const { return getBuckets(); }
 
  protected:
   DenseMapBase() = default;
 
   void destroyAll() {
-    if (getNumBuckets() == 0) // Nothing to do.
+    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 &&
+    assert((getNumBuckets() & (getNumBuckets() - 1)) == 0 &&
            "# initial buckets must be a power of two!");
     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().
void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
     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.
+        (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()));
         incrementNumEntries();
 
         // Free the value.
         B->getSecond().~ValueT();
       }
else
               ValueT(other.getBuckets()[i].getSecond());
       }
   }
 
   static unsigned getHashValue(const KeyT &Val) {
     return KeyInfoT::getHashValue(Val);
   }
 
-  template<typename LookupKeyT>
+  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 getTombstoneKey() {
-    return KeyInfoT::getTombstoneKey();
-  }
+  static const KeyT getTombstoneKey() { return KeyInfoT::getTombstoneKey(); }
 
  private:
-  iterator makeIterator(BucketT *P, BucketT *E,
-                        DebugEpochBase &Epoch,
-                        bool NoAdvance=false) {
+  iterator makeIterator(BucketT *P, BucketT *E, DebugEpochBase &Epoch,
+                        bool NoAdvance = false) {
     if (shouldReverseIterate<KeyT>()) {
       BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
       return iterator(B, E, Epoch, NoAdvance);
     }
     return iterator(P, E, Epoch, NoAdvance);
   }
 
   const_iterator makeConstIterator(const BucketT *P, const BucketT *E,
                                    const DebugEpochBase &Epoch,
-                                   const bool NoAdvance=false) const {
+                                   const bool NoAdvance = false) const {
     if (shouldReverseIterate<KeyT>()) {
       const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
       return const_iterator(B, E, Epoch, NoAdvance);
     }
     return const_iterator(P, E, Epoch, NoAdvance);
   }
 
   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 incrementNumEntries() { setNumEntries(getNumEntries() + 1); }
 
-  void decrementNumEntries() {
-    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 incrementNumTombstones() { setNumTombstones(getNumTombstones() + 1); }
 
-  void decrementNumTombstones() {
-    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();
-  }
+  BucketT *getBuckets() { return static_cast<DerivedT *>(this)->getBuckets(); }
 
   unsigned getNumBuckets() const {
     return static_cast<const DerivedT *>(this)->getNumBuckets();
   }
 
-  BucketT *getBucketsEnd() {
-    return getBuckets() + getNumBuckets();
-  }
+  BucketT *getBucketsEnd() { return getBuckets() + getNumBuckets(); }
 
   const BucketT *getBucketsEnd() const {
     return getBuckets() + getNumBuckets();
   }
 
-  void grow(unsigned AtLeast) {
-    static_cast<DerivedT *>(this)->grow(AtLeast);
-  }
+  void grow(unsigned AtLeast) { static_cast<DerivedT *>(this)->grow(AtLeast); }
 
-  void shrink_and_clear() {
-    static_cast<DerivedT *>(this)->shrink_and_clear();
-  }
+  void shrink_and_clear() { static_cast<DerivedT *>(this)->shrink_and_clear(); }
 
   template <typename KeyArg, typename... ValueArgs>
   BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
-                            ValueArgs &&... Values) {
+                            ValueArgs &&...Values) {
     TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
 
     TheBucket->getFirst() = std::forward<KeyArg>(Key);
     ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
     return TheBucket;
   }
 
   template <typename LookupKeyT>
BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
     // 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)) {
       this->grow(NumBuckets * 2);
       LookupBucketFor(Lookup, TheBucket);
       NumBuckets = getNumBuckets();
-    } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
-                             NumBuckets/8)) {
+    } else if (LLVM_UNLIKELY(NumBuckets -
+                                 (NewNumEntries + getNumTombstones()) <=
+                             NumBuckets / 8)) {
       this->grow(NumBuckets);
       LookupBucketFor(Lookup, TheBucket);
     }
     assert(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;
   }
 
   /// 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>
+  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();
     assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
            !KeyInfoT::isEqual(Val, TombstoneKey) &&
            "Empty/Tombstone value shouldn't be inserted into map!");
 
-    unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
+    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()))) {
         FoundBucket = ThisBucket;
         return true;
       }
while (true) {
       // 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);
+      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);
+    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.
-  size_t getMemorySize() const {
-    return getNumBuckets() * sizeof(BucketT);
-  }
+  size_t getMemorySize() const { return getNumBuckets() * sizeof(BucketT); }
 };
 
 /// 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).
class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
   // simplicity of referring to them.
   using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
 
   BucketT *Buckets;
   unsigned NumEntries;
   unsigned NumTombstones;
   unsigned NumBuckets;
 
  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); }
 
   DenseMap(const DenseMap &other) : BaseT() {
     init(0);
     copyFrom(other);
   }
 
   DenseMap(DenseMap &&other) : BaseT() {
     init(0);
     swap(other);
   }
 
-  template<typename InputIt>
+  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));
   }
 
-  void swap(DenseMap& RHS) {
+  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);
   }
 
-  DenseMap& operator=(const DenseMap& other) {
+  DenseMap &operator=(const DenseMap &other) {
     if (&other != this)
       copyFrom(other);
     return *this;
   }
 
-  DenseMap& operator=(DenseMap &&other) {
+  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) {
+  void copyFrom(const DenseMap &other) {
     this->destroyAll();
     deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
     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))));
+    allocateBuckets(std::max<unsigned>(
+        64, static_cast<unsigned>(NextPowerOf2(AtLeast - 1))));
     assert(Buckets);
     if (!OldBuckets) {
       this->BaseT::initEmpty();
       return;
     }
 
-    this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
+    this->moveFromOldBuckets(OldBuckets, OldBuckets + OldNumBuckets);
 
     // Free the old table.
     deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets,
                       alignof(BucketT));
   }
 
   void shrink_and_clear() {
     unsigned OldNumBuckets = NumBuckets;
if (NewNumBuckets == NumBuckets) {
       return;
     }
 
     deallocate_buffer(Buckets, sizeof(BucketT) * OldNumBuckets,
                       alignof(BucketT));
     init(NewNumBuckets);
   }
 
  private:
-  unsigned getNumEntries() const {
-    return NumEntries;
-  }
+  unsigned getNumEntries() const { return NumEntries; }
 
-  void setNumEntries(unsigned Num) {
-    NumEntries = Num;
-  }
+  void setNumEntries(unsigned Num) { NumEntries = Num; }
 
-  unsigned getNumTombstones() const {
-    return NumTombstones;
-  }
+  unsigned getNumTombstones() const { return NumTombstones; }
 
-  void setNumTombstones(unsigned Num) {
-    NumTombstones = Num;
-  }
+  void setNumTombstones(unsigned Num) { NumTombstones = Num; }
 
-  BucketT *getBuckets() const {
-    return Buckets;
-  }
+  BucketT *getBuckets() const { return Buckets; }
 
-  unsigned getNumBuckets() const {
-    return NumBuckets;
-  }
+  unsigned getNumBuckets() const { return NumBuckets; }
 
   bool allocateBuckets(unsigned Num) {
     NumBuckets = Num;
     if (NumBuckets == 0) {
       Buckets = nullptr;
       return false;
     }
 
struct LargeRep {
     BucketT *Buckets;
     unsigned NumBuckets;
   };
 
   /// A "union" of an inline bucket array and the struct representing
   /// a large bucket. This union will be discriminated by the 'Small' bit.
   AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;
 
  public:
-  explicit SmallDenseMap(unsigned NumInitBuckets = 0) {
-    init(NumInitBuckets);
-  }
+  explicit SmallDenseMap(unsigned NumInitBuckets = 0) { init(NumInitBuckets); }
 
   SmallDenseMap(const SmallDenseMap &other) : BaseT() {
     init(0);
     copyFrom(other);
   }
 
   SmallDenseMap(SmallDenseMap &&other) : BaseT() {
     init(0);
     swap(other);
   }
 
-  template<typename InputIt>
+  template <typename InputIt>
   SmallDenseMap(const InputIt &I, const InputIt &E) {
     init(NextPowerOf2(std::distance(I, E)));
     this->insert(I, E);
   }
 
   SmallDenseMap(std::initializer_list<typename BaseT::value_type> Vals)
       : SmallDenseMap(Vals.begin(), Vals.end()) {}
 
   ~SmallDenseMap() {
     this->destroyAll();
     deallocateBuckets();
   }
 
-  void swap(SmallDenseMap& RHS) {
+  void swap(SmallDenseMap &RHS) {
     unsigned TmpNumEntries = RHS.NumEntries;
     RHS.NumEntries = NumEntries;
     NumEntries = TmpNumEntries;
     std::swap(NumTombstones, RHS.NumTombstones);
 
     const KeyT EmptyKey = this->getEmptyKey();
     const KeyT TombstoneKey = this->getTombstoneKey();
     if (Small && RHS.Small) {
void swap(SmallDenseMap &RHS) {
     }
 
     // The hard part of moving the small buckets across is done, just move
     // the TmpRep into its new home.
     SmallSide.Small = false;
     new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
   }
 
-  SmallDenseMap& operator=(const SmallDenseMap& other) {
+  SmallDenseMap &operator=(const SmallDenseMap &other) {
     if (&other != this)
       copyFrom(other);
     return *this;
   }
 
-  SmallDenseMap& operator=(SmallDenseMap &&other) {
+  SmallDenseMap &operator=(SmallDenseMap &&other) {
     this->destroyAll();
     deallocateBuckets();
     init(0);
     swap(other);
     return *this;
   }
 
-  void copyFrom(const SmallDenseMap& other) {
+  void copyFrom(const SmallDenseMap &other) {
     this->destroyAll();
     deallocateBuckets();
     Small = true;
     if (other.getNumBuckets() > InlineBuckets) {
       Small = false;
       new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets()));
     }
     this->BaseT::copyFrom(other);
   }
 
   void init(unsigned InitBuckets) {
     Small = true;
     if (InitBuckets > InlineBuckets) {
       Small = false;
       new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets));
     }
     this->BaseT::initEmpty();
   }
 
   void grow(unsigned AtLeast) {
     if (AtLeast > InlineBuckets)
-      AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1));
+      AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast - 1));
 
     if (Small) {
       // First move the inline buckets into a temporary storage.
       AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage;
       BucketT *TmpBegin = reinterpret_cast<BucketT *>(&TmpStorage);
       BucketT *TmpEnd = TmpBegin;
 
       // Loop over the buckets, moving non-empty, non-tombstones into the
void grow(unsigned AtLeast) {
     LargeRep OldRep = std::move(*getLargeRep());
     getLargeRep()->~LargeRep();
     if (AtLeast <= InlineBuckets) {
       Small = true;
     } else {
       new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
     }
 
-    this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets);
+    this->moveFromOldBuckets(OldRep.Buckets,
+                             OldRep.Buckets + OldRep.NumBuckets);
 
     // Free the old table.
     deallocate_buffer(OldRep.Buckets, sizeof(BucketT) * OldRep.NumBuckets,
                       alignof(BucketT));
   }
 
   void shrink_and_clear() {
     unsigned OldSize = this->size();
if ((Small && NewNumBuckets <= InlineBuckets) ||
       this->BaseT::initEmpty();
       return;
     }
 
     deallocateBuckets();
     init(NewNumBuckets);
   }
 
  private:
-  unsigned getNumEntries() const {
-    return NumEntries;
-  }
+  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;
   }
 
-  unsigned getNumTombstones() const {
-    return NumTombstones;
-  }
+  unsigned getNumTombstones() const { return NumTombstones; }
 
-  void setNumTombstones(unsigned Num) {
-    NumTombstones = Num;
-  }
+  void setNumTombstones(unsigned Num) { NumTombstones = Num; }
 
   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);
   }
 
   BucketT *getInlineBuckets() {
     return const_cast<BucketT *>(
         const_cast<const SmallDenseMap *>(this)->getInlineBuckets());
   }
 
   const LargeRep *getLargeRep() const {
     assert(!Small);
     // Note, same rule about aliasing as with getInlineBuckets.
     return reinterpret_cast<const LargeRep *>(&storage);
   }
 
   LargeRep *getLargeRep() {
     return const_cast<LargeRep *>(
         const_cast<const SmallDenseMap *>(this)->getLargeRep());
   }
 
   const BucketT *getBuckets() const {
     return Small ? getInlineBuckets() : getLargeRep()->Buckets;
   }
 
   BucketT *getBuckets() {
     return const_cast<BucketT *>(
         const_cast<const SmallDenseMap *>(this)->getBuckets());
   }
 
   unsigned getNumBuckets() const {
     return Small ? InlineBuckets : getLargeRep()->NumBuckets;
   }
 
   void deallocateBuckets() {
     if (Small)

 };
 
 template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
           bool IsConst>
 class DenseMapIterator : DebugEpochBase::HandleBase {
   friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
   friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>;
 
  public:
   using difference_type = ptrdiff_t;
   using value_type =
       typename std::conditional<IsConst, const Bucket, Bucket>::type;
   using pointer = value_type *;
   using reference = value_type &;
   using iterator_category = std::forward_iterator_tag;
 
  private:
   pointer Ptr = nullptr;
   pointer End = nullptr;
 
  public:
   DenseMapIterator() = default;
 
   DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch,
                    bool NoAdvance = false)
       : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {
     assert(isHandleInSync() && "invalid construction!");
 
-    if (NoAdvance) return;
+    if (NoAdvance)
+      return;
     if (shouldReverseIterate<KeyT>()) {
       RetreatPastEmptyBuckets();
       return;
     }
     AdvancePastEmptyBuckets();
   }
 
   // Converting ctor from non-const iterators to const iterators. SFINAE'd out
friend bool operator==(const DenseMapIterator &LHS,
     return LHS.Ptr == RHS.Ptr;
   }
 
   friend bool operator!=(const DenseMapIterator &LHS,
                          const DenseMapIterator &RHS) {
     return !(LHS == RHS);
   }
 
-  inline DenseMapIterator& operator++() {  // Preincrement
+  inline DenseMapIterator &operator++() {  // Preincrement
     assert(isHandleInSync() && "invalid iterator access!");
     assert(Ptr != End && "incrementing end() iterator");
     if (shouldReverseIterate<KeyT>()) {
       --Ptr;
       RetreatPastEmptyBuckets();
       return *this;
     }
     ++Ptr;
     AdvancePastEmptyBuckets();
     return *this;
   }
   DenseMapIterator operator++(int) {  // Postincrement
     assert(isHandleInSync() && "invalid iterator access!");
-    DenseMapIterator tmp = *this; ++*this; return tmp;
+    DenseMapIterator tmp = *this;
+    ++*this;
+    return tmp;
   }
 
  private:
   void AdvancePastEmptyBuckets() {
     assert(Ptr <= End);
     const KeyT Empty = KeyInfoT::getEmptyKey();
     const KeyT Tombstone = KeyInfoT::getTombstoneKey();
 
     while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
                           KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
       ++Ptr;
private:
   }
 };
 
 template <typename KeyT, typename ValueT, typename KeyInfoT>
 inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) {
   return X.getMemorySize();
 }
 
-} // end namespace llvm
+}  // end namespace llvm
 
-#endif // LLVM_ADT_DENSEMAP_H
+#endif  // LLVM_ADT_DENSEMAP_H

compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h

static inline unsigned combineHashValue(unsigned a, unsigned b) {
   key ^= (key >> 8);
   key += (key << 3);
   key ^= (key >> 15);
   key += ~(key << 27);
   key ^= (key >> 31);
   return (unsigned)key;
 }
 
-} // end namespace detail
+}  // end namespace detail
 
-template<typename T>
+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);
+  // 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*> {
+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 inline T* getEmptyKey() {
+  static inline T *getEmptyKey() {
     uintptr_t Val = static_cast<uintptr_t>(-1);
     Val <<= Log2MaxAlign;
-    return reinterpret_cast<T*>(Val);
+    return reinterpret_cast<T *>(Val);
   }
 
-  static inline T* getTombstoneKey() {
+  static inline T *getTombstoneKey() {
     uintptr_t Val = static_cast<uintptr_t>(-2);
     Val <<= Log2MaxAlign;
-    return reinterpret_cast<T*>(Val);
+    return reinterpret_cast<T *>(Val);
   }
 
   static unsigned getHashValue(const T *PtrVal) {
     return (unsigned((uintptr_t)PtrVal) >> 4) ^
            (unsigned((uintptr_t)PtrVal) >> 9);
   }
 
   static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
 };
 
 // Provide DenseMapInfo for chars.
-template<> struct DenseMapInfo<char> {
+template <>
+struct DenseMapInfo<char> {
   static inline char getEmptyKey() { return ~0; }
   static inline char getTombstoneKey() { return ~0 - 1; }
-  static unsigned getHashValue(const char& Val) { return Val * 37U; }
+  static unsigned getHashValue(const char &Val) { return Val * 37U; }
 
-  static bool isEqual(const char &LHS, const char &RHS) {
-    return LHS == RHS;
-  }
+  static bool isEqual(const char &LHS, const char &RHS) { return LHS == RHS; }
 };
 
 // Provide DenseMapInfo for unsigned chars.
-template <> struct DenseMapInfo<unsigned char> {
+template <>
+struct DenseMapInfo<unsigned char> {
   static inline unsigned char getEmptyKey() { return ~0; }
   static inline unsigned char getTombstoneKey() { return ~0 - 1; }
   static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; }
 
   static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) {
     return LHS == RHS;
   }
 };
 
 // Provide DenseMapInfo for unsigned shorts.
-template <> struct DenseMapInfo<unsigned short> {
+template <>
+struct DenseMapInfo<unsigned short> {
   static inline unsigned short getEmptyKey() { return 0xFFFF; }
   static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; }
   static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
 
   static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
     return LHS == RHS;
   }
 };
 
 // Provide DenseMapInfo for unsigned ints.
-template<> struct DenseMapInfo<unsigned> {
+template <>
+struct DenseMapInfo<unsigned> {
   static inline unsigned getEmptyKey() { return ~0U; }
   static inline unsigned getTombstoneKey() { return ~0U - 1; }
-  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
+  static unsigned getHashValue(const unsigned &Val) { return Val * 37U; }
 
-  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
+  static bool isEqual(const unsigned &LHS, const unsigned &RHS) {
     return LHS == RHS;
   }
 };
 
 // Provide DenseMapInfo for unsigned longs.
-template<> struct DenseMapInfo<unsigned long> {
+template <>
+struct DenseMapInfo<unsigned long> {
   static inline unsigned long getEmptyKey() { return ~0UL; }
   static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
 
-  static unsigned getHashValue(const unsigned long& Val) {
+  static unsigned getHashValue(const unsigned long &Val) {
     return (unsigned)(Val * 37UL);
   }
 
-  static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
+  static bool isEqual(const unsigned long &LHS, const unsigned long &RHS) {
     return LHS == RHS;
   }
 };
 
 // Provide DenseMapInfo for unsigned long longs.
-template<> struct DenseMapInfo<unsigned long long> {
+template <>
+struct DenseMapInfo<unsigned long long> {
   static inline unsigned long long getEmptyKey() { return ~0ULL; }
   static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
 
-  static unsigned getHashValue(const unsigned long long& Val) {
+  static unsigned getHashValue(const unsigned long long &Val) {
     return (unsigned)(Val * 37ULL);
   }
 
-  static bool isEqual(const unsigned long long& LHS,
-                      const unsigned long long& RHS) {
+  static bool isEqual(const unsigned long long &LHS,
+                      const unsigned long long &RHS) {
     return LHS == RHS;
   }
 };
 
 // Provide DenseMapInfo for shorts.
-template <> struct DenseMapInfo<short> {
+template <>
+struct DenseMapInfo<short> {
   static inline short getEmptyKey() { return 0x7FFF; }
   static inline short getTombstoneKey() { return -0x7FFF - 1; }
   static unsigned getHashValue(const short &Val) { return Val * 37U; }
   static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; }
 };
 
 // Provide DenseMapInfo for ints.
-template<> struct DenseMapInfo<int> {
+template <>
+struct DenseMapInfo<int> {
   static inline int getEmptyKey() { return 0x7fffffff; }
   static inline int getTombstoneKey() { return -0x7fffffff - 1; }
-  static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
+  static unsigned getHashValue(const int &Val) { return (unsigned)(Val * 37U); }
 
-  static bool isEqual(const int& LHS, const int& RHS) {
-    return LHS == RHS;
-  }
+  static bool isEqual(const int &LHS, const int &RHS) { return LHS == RHS; }
 };
 
 // Provide DenseMapInfo for longs.
-template<> struct DenseMapInfo<long> {
+template <>
+struct DenseMapInfo<long> {
   static inline long getEmptyKey() {
     return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
   }
 
   static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
 
-  static unsigned getHashValue(const long& Val) {
+  static unsigned getHashValue(const long &Val) {
     return (unsigned)(Val * 37UL);
   }
 
-  static bool isEqual(const long& LHS, const long& RHS) {
-    return LHS == RHS;
-  }
+  static bool isEqual(const long &LHS, const long &RHS) { return LHS == RHS; }
 };
 
 // Provide DenseMapInfo for long longs.
-template<> struct DenseMapInfo<long long> {
+template <>
+struct DenseMapInfo<long long> {
   static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
-  static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
+  static inline long long getTombstoneKey() {
+    return -0x7fffffffffffffffLL - 1;
+  }
 
-  static unsigned getHashValue(const long long& Val) {
+  static unsigned getHashValue(const long long &Val) {
     return (unsigned)(Val * 37ULL);
   }
 
-  static bool isEqual(const long long& LHS,
-                      const long long& RHS) {
+  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>
+template <typename T, typename U>
 struct DenseMapInfo<std::pair<T, U>> {
   using Pair = std::pair<T, U>;
   using FirstInfo = DenseMapInfo<T>;
   using SecondInfo = DenseMapInfo<U>;
 
   static inline Pair getEmptyKey() {
-    return std::make_pair(FirstInfo::getEmptyKey(),
-                          SecondInfo::getEmptyKey());
+    return std::make_pair(FirstInfo::getEmptyKey(), SecondInfo::getEmptyKey());
   }
 
   static inline Pair getTombstoneKey() {
     return std::make_pair(FirstInfo::getTombstoneKey(),
                           SecondInfo::getTombstoneKey());
   }
 
-  static unsigned getHashValue(const Pair& PairVal) {
+  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);
   }
 };
 
 // Provide DenseMapInfo for all tuples whose members have info.
-template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> {
+template <typename... Ts>
+struct DenseMapInfo<std::tuple<Ts...>> {
   using Tuple = std::tuple<Ts...>;
 
   static inline Tuple getEmptyKey() {
     return Tuple(DenseMapInfo<Ts>::getEmptyKey()...);
   }
 
   static inline Tuple getTombstoneKey() {
     return Tuple(DenseMapInfo<Ts>::getTombstoneKey()...);
struct DenseMapInfo<std::tuple<Ts...>> {
   }
 
   static bool isEqual(const Tuple &lhs, const Tuple &rhs) {
     std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
     return isEqualImpl<0>(lhs, rhs, atEnd);
   }
 };
 
-} // end namespace llvm
+}  // end namespace llvm
 
-#endif // LLVM_ADT_DENSEMAPINFO_H
+#endif  // LLVM_ADT_DENSEMAPINFO_H

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

 //===- llvm/unittest/ADT/DenseMapMap.cpp - DenseMap unit tests --*- 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
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/ADT/DenseMap.h"
-#include "gtest/gtest.h"
 #include <map>
 #include <set>
 
+#include "gtest/gtest.h"
+#include "llvm/ADT/DenseMap.h"
+
 using namespace llvm;
 
 namespace {
 
 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];
 }
 uint32_t *getTestValue(int i, uint32_t **) {
   static uint32_t dummy_arr1[8192];
   assert(i < 8192 && "Only support 8192 dummy keys.");
   return &dummy_arr1[i];
 }
 
 /// A test class that tries to check that construction and destruction
 /// occur correctly.
 class CtorTester {
   static std::set<CtorTester *> Constructed;
   int Value;
 
  public:
   explicit CtorTester(int Value = 0) : Value(Value) {
     EXPECT_TRUE(Constructed.insert(this).second);
   }
   CtorTester(uint32_t Value) : Value(Value) {
     EXPECT_TRUE(Constructed.insert(this).second);
   }
   CtorTester(const CtorTester &Arg) : Value(Arg.Value) {
     EXPECT_TRUE(Constructed.insert(this).second);
   }
   CtorTester &operator=(const CtorTester &) = default;
-  ~CtorTester() {
-    EXPECT_EQ(1u, Constructed.erase(this));
-  }
+  ~CtorTester() { EXPECT_EQ(1u, Constructed.erase(this)); }
   operator uint32_t() const { return Value; }
 
   int getValue() const { return Value; }
   bool operator==(const CtorTester &RHS) const { return Value == RHS.Value; }
 };
 
 std::set<CtorTester *> CtorTester::Constructed;
 

 CtorTester getTestValue(int i, CtorTester *) { return CtorTester(42 + i); }
 
 // Test fixture, with helper functions implemented by forwarding to global
 // function overloads selected by component types of the type parameter. This
 // allows all of the map implementations to be tested with shared
 // implementations of helper routines.
 template <typename T>
 class DenseMapTest : public ::testing::Test {
  protected:
   T Map;
 
   static typename T::key_type *const dummy_key_ptr;
   static typename T::mapped_type *const dummy_value_ptr;
 
   typename T::key_type getKey(int i = 0) {
     return getTestKey(i, dummy_key_ptr);
   }
   typename T::mapped_type getValue(int i = 0) {
     return getTestValue(i, dummy_value_ptr);
   }
 };
 
 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>
-                         > DenseMapTestTypes;
+typedef ::testing::Types<
+    DenseMap<uint32_t, uint32_t>, DenseMap<uint32_t *, uint32_t *>,
+    SmallDenseMap<uint32_t, uint32_t>, SmallDenseMap<uint32_t *, uint32_t *>,
+    SmallDenseMap<CtorTester, CtorTester, 4, 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());
 
TYPED_TEST(DenseMapTest, SwapTest) {
 
   this->Map.swap(otherMap);
   EXPECT_EQ(0u, otherMap.size());
   EXPECT_TRUE(otherMap.empty());
   EXPECT_EQ(1u, this->Map.size());
   EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);
 
   // Make this more interesting by inserting 100 numbers into the map.
-  for (int i = 0; i < 100; ++i)
-    this->Map[this->getKey(i)] = this->getValue(i);
+  for (int i = 0; i < 100; ++i) this->Map[this->getKey(i)] = this->getValue(i);
 
   this->Map.swap(otherMap);
   EXPECT_EQ(0u, this->Map.size());
   EXPECT_TRUE(this->Map.empty());
   EXPECT_EQ(100u, otherMap.size());
   for (int i = 0; i < 100; ++i)
     EXPECT_EQ(this->getValue(i), otherMap[this->getKey(i)]);
 
struct CountCopyAndMove {
   CountCopyAndMove &operator=(const CountCopyAndMove &&) {
     Move++;
     return *this;
   }
 };
 int CountCopyAndMove::Copy = 0;
 int CountCopyAndMove::Move = 0;
 
-} // anonymous namespace
+}  // anonymous namespace
 
 // Test initializer list construction.
 TEST(DenseMapCustomTest, InitializerList) {
   DenseMap<int, int> M({{0, 0}, {0, 1}, {1, 2}});
   EXPECT_EQ(2u, M.size());
   EXPECT_EQ(1u, M.count(0));
   EXPECT_EQ(0, M[0]);
   EXPECT_EQ(1u, M.count(1));
TEST(DenseMapCustomTest, InitialSizeTest) {
   }
 }
 
 // Make sure creating the map with a iterator range does not trigger grow()
 TEST(DenseMapCustomTest, InitFromIterator) {
   std::vector<std::pair<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());
+  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);
TEST(DenseMapCustomTest, StringRefTest) {
   EXPECT_EQ(42, M.lookup(StringRef("a", 0)));
 }
 
 // Key traits that allows lookup with either an unsigned or char* key;
 // In the latter case, "a" == 0, "b" == 1 and so on.
 struct TestDenseMapInfo {
   static inline unsigned getEmptyKey() { return ~0; }
   static inline unsigned getTombstoneKey() { return ~0U - 1; }
-  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
-  static unsigned getHashValue(const char* Val) {
+  static unsigned getHashValue(const unsigned &Val) { return Val * 37U; }
+  static unsigned getHashValue(const char *Val) {
     return (unsigned)(Val[0] - 'a') * 37U;
   }
-  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
+  static bool isEqual(const unsigned &LHS, const unsigned &RHS) {
     return LHS == RHS;
   }
-  static bool isEqual(const char* LHS, const unsigned& RHS) {
+  static bool isEqual(const char *LHS, const unsigned &RHS) {
     return (unsigned)(LHS[0] - 'a') == RHS;
   }
 };
 
 // find_as() tests
 TEST(DenseMapCustomTest, FindAsTest) {
   DenseMap<unsigned, unsigned, TestDenseMapInfo> map;
   map[0] = 1;
TEST(DenseMapCustomTest, SmallDenseMapInitializerList) {
   EXPECT_EQ(0, M[0]);
   EXPECT_EQ(1u, M.count(1));
   EXPECT_EQ(2, M[1]);
 }
 
 struct ContiguousDenseMapInfo {
   static inline unsigned getEmptyKey() { return ~0; }
   static inline unsigned getTombstoneKey() { return ~0U - 1; }
-  static unsigned getHashValue(const unsigned& Val) { return Val; }
-  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
+  static unsigned getHashValue(const unsigned &Val) { return Val; }
+  static bool isEqual(const unsigned &LHS, const unsigned &RHS) {
     return LHS == RHS;
   }
 };
 
 // Test that filling a small dense map with exactly the number of elements in
 // the map grows to have enough space for an empty bucket.
 TEST(DenseMapCustomTest, SmallDenseMapGrowTest) {
   SmallDenseMap<unsigned, unsigned, 32, ContiguousDenseMapInfo> map;
   // Add some number of elements, then delete a few to leave us some tombstones.
   // If we just filled the map with 32 elements we'd grow because of not enough
   // tombstones which masks the issue here.
-  for (unsigned i = 0; i < 20; ++i)
-    map[i] = i + 1;
-  for (unsigned i = 0; i < 10; ++i)
-    map.erase(i);
-  for (unsigned i = 20; i < 32; ++i)
-    map[i] = i + 1;
+  for (unsigned i = 0; i < 20; ++i) map[i] = i + 1;
+  for (unsigned i = 0; i < 10; ++i) map.erase(i);
+  for (unsigned i = 20; i < 32; ++i) map[i] = i + 1;
 
   // Size tests
   EXPECT_EQ(22u, map.size());
 
   // Try to find an element which doesn't exist.  There was a bug in
   // SmallDenseMap which led to a map with num elements == small capacity not
   // having an empty bucket any more.  Finding an element not in the map would
   // therefore never terminate.
   EXPECT_TRUE(map.find(32) == map.end());
 }
 
 TEST(DenseMapCustomTest, LargeSmallDenseMapCompaction) {
   SmallDenseMap<unsigned, unsigned, 128, ContiguousDenseMapInfo> map;
   // Fill to < 3/4 load.
-  for (unsigned i = 0; i < 95; ++i)
-    map[i] = i;
+  for (unsigned i = 0; i < 95; ++i) map[i] = i;
   // And erase, leaving behind tombstones.
-  for (unsigned i = 0; i < 95; ++i)
-    map.erase(i);
+  for (unsigned i = 0; i < 95; ++i) map.erase(i);
   // Fill further, so that less than 1/8 are empty, but still below 3/4 load.
-  for (unsigned i = 95; i < 128; ++i)
-    map[i] = i;
+  for (unsigned i = 95; i < 128; ++i) map[i] = i;
 
   EXPECT_EQ(33u, map.size());
   // Similar to the previous test, check for a non-existing element, as an
   // indirect check that tombstones have been removed.
   EXPECT_TRUE(map.find(0) == map.end());
 }
 
 TEST(DenseMapCustomTest, TryEmplaceTest) {
TEST(DenseMapCustomTest, OpaquePointerKey) {
   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());
 }
-}
+}  // namespace