diff options
author | Vitaly Buka <vitalybuka@google.com> | 2021-11-16 12:41:06 -0800 |
---|---|---|
committer | Vitaly Buka <vitalybuka@google.com> | 2021-11-17 19:10:20 -0800 |
commit | 234a8301cd6275b948b7e89fb84accc370cb71ae (patch) | |
tree | 8dc73184c92bfa5f6e9c0760f7fe2098e6d4a719 | |
parent | 54adc1675eb893a416e1d2f97a8a4c79a8b5a0aa (diff) | |
download | llvm-234a8301cd6275b948b7e89fb84accc370cb71ae.tar.gz |
[NFC][sanitizer] Clang format copied code
Depends on D114045.
Differential Revision: https://reviews.llvm.org/D114046
3 files changed, 235 insertions, 279 deletions
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h index 595eabd0ffb4..66d934b1c54b 100644 --- a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h +++ b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h @@ -13,14 +13,6 @@ #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> @@ -31,6 +23,15 @@ #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 { @@ -47,7 +48,7 @@ struct DenseMapPair : public std::pair<KeyT, ValueT> { 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>, @@ -61,7 +62,7 @@ class DenseMapBase : public DebugEpochBase { template <typename T> using const_arg_type_t = typename const_pointer_or_const_ref<T>::type; -public: + public: using size_type = unsigned; using key_type = KeyT; using mapped_type = ValueT; @@ -94,9 +95,7 @@ public: 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 @@ -110,7 +109,8 @@ public: 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. @@ -150,19 +150,19 @@ public: 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(); } @@ -171,24 +171,24 @@ public: /// 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(); } @@ -219,49 +219,49 @@ public: // 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(), + *this, true), + 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(), + *this, true), + 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) { + 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(), + *this, true), + 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(), + *this, true), + true); } /// Alternate version of insert() which allows a different, and possibly @@ -274,35 +274,34 @@ public: 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(), + *this, true), + 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(), + *this, true), + true); } /// 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(); @@ -318,7 +317,7 @@ public: incrementNumTombstones(); } - value_type& FindAndConstruct(const KeyT &Key) { + value_type &FindAndConstruct(const KeyT &Key) { BucketT *TheBucket; if (LookupBucketFor(Key, TheBucket)) return *TheBucket; @@ -326,11 +325,9 @@ public: 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; @@ -354,11 +351,11 @@ public: /// determine whether an insertion caused the DenseMap to reallocate. const void *getPointerIntoBucketsArray() const { return getBuckets(); } -protected: + protected: DenseMapBase() = default; void destroyAll() { - if (getNumBuckets() == 0) // Nothing to do. + if (getNumBuckets() == 0) // Nothing to do. return; const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); @@ -374,7 +371,7 @@ protected: 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) @@ -404,7 +401,7 @@ protected: // 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())); @@ -445,7 +442,7 @@ protected: return KeyInfoT::getHashValue(Val); } - template<typename LookupKeyT> + template <typename LookupKeyT> static unsigned getHashValue(const LookupKeyT &Val) { return KeyInfoT::getHashValue(Val); } @@ -456,14 +453,11 @@ protected: 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) { + private: + 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); @@ -473,7 +467,7 @@ private: 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); @@ -489,13 +483,9 @@ private: 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(); @@ -505,45 +495,33 @@ private: 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); @@ -581,8 +559,9 @@ private: 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); } @@ -604,7 +583,7 @@ private: /// 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(); @@ -623,7 +602,7 @@ private: !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; @@ -651,27 +630,25 @@ private: // 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: + 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. @@ -724,7 +701,7 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>, unsigned NumTombstones; unsigned NumBuckets; -public: + 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); } @@ -739,7 +716,7 @@ public: swap(other); } - template<typename InputIt> + template <typename InputIt> DenseMap(const InputIt &I, const InputIt &E) { init(std::distance(I, E)); this->insert(I, E); @@ -755,7 +732,7 @@ public: 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); @@ -764,13 +741,13 @@ public: 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); @@ -778,7 +755,7 @@ public: 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)) { @@ -803,14 +780,15 @@ public: 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, @@ -836,30 +814,18 @@ public: init(NewNumBuckets); } -private: - unsigned getNumEntries() const { - return NumEntries; - } + private: + 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; @@ -903,10 +869,8 @@ class SmallDenseMap /// 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); - } + public: + explicit SmallDenseMap(unsigned NumInitBuckets = 0) { init(NumInitBuckets); } SmallDenseMap(const SmallDenseMap &other) : BaseT() { init(0); @@ -918,7 +882,7 @@ public: 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); @@ -932,7 +896,7 @@ public: deallocateBuckets(); } - void swap(SmallDenseMap& RHS) { + void swap(SmallDenseMap &RHS) { unsigned TmpNumEntries = RHS.NumEntries; RHS.NumEntries = NumEntries; NumEntries = TmpNumEntries; @@ -1004,13 +968,13 @@ public: 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); @@ -1018,7 +982,7 @@ public: return *this; } - void copyFrom(const SmallDenseMap& other) { + void copyFrom(const SmallDenseMap &other) { this->destroyAll(); deallocateBuckets(); Small = true; @@ -1040,7 +1004,7 @@ public: 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. @@ -1084,7 +1048,8 @@ public: 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, @@ -1112,10 +1077,8 @@ public: init(NewNumBuckets); } -private: - unsigned getNumEntries() const { - return NumEntries; - } + private: + unsigned getNumEntries() const { return NumEntries; } void setNumEntries(unsigned Num) { // NumEntries is hardcoded to be 31 bits wide. @@ -1123,13 +1086,9 @@ private: 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); @@ -1141,7 +1100,7 @@ private: BucketT *getInlineBuckets() { return const_cast<BucketT *>( - const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); + const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); } const LargeRep *getLargeRep() const { @@ -1152,7 +1111,7 @@ private: LargeRep *getLargeRep() { return const_cast<LargeRep *>( - const_cast<const SmallDenseMap *>(this)->getLargeRep()); + const_cast<const SmallDenseMap *>(this)->getLargeRep()); } const BucketT *getBuckets() const { @@ -1161,7 +1120,7 @@ private: BucketT *getBuckets() { return const_cast<BucketT *>( - const_cast<const SmallDenseMap *>(this)->getBuckets()); + const_cast<const SmallDenseMap *>(this)->getBuckets()); } unsigned getNumBuckets() const { @@ -1193,7 +1152,7 @@ class DenseMapIterator : DebugEpochBase::HandleBase { friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>; friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>; -public: + public: using difference_type = ptrdiff_t; using value_type = typename std::conditional<IsConst, const Bucket, Bucket>::type; @@ -1201,11 +1160,11 @@ public: using reference = value_type &; using iterator_category = std::forward_iterator_tag; -private: + private: pointer Ptr = nullptr; pointer End = nullptr; -public: + public: DenseMapIterator() = default; DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch, @@ -1213,7 +1172,8 @@ public: : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { assert(isHandleInSync() && "invalid construction!"); - if (NoAdvance) return; + if (NoAdvance) + return; if (shouldReverseIterate<KeyT>()) { RetreatPastEmptyBuckets(); return; @@ -1259,7 +1219,7 @@ public: 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>()) { @@ -1273,10 +1233,12 @@ public: } DenseMapIterator operator++(int) { // Postincrement assert(isHandleInSync() && "invalid iterator access!"); - DenseMapIterator tmp = *this; ++*this; return tmp; + DenseMapIterator tmp = *this; + ++*this; + return tmp; } -private: + private: void AdvancePastEmptyBuckets() { assert(Ptr <= End); const KeyT Empty = KeyInfoT::getEmptyKey(); @@ -1303,6 +1265,6 @@ 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 diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h index 74c833ac2522..e50ec2b71da0 100644 --- a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h +++ b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h @@ -37,14 +37,14 @@ static inline unsigned combineHashValue(unsigned a, unsigned b) { 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 @@ -52,24 +52,24 @@ struct DenseMapInfo { // 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) { @@ -81,18 +81,18 @@ struct DenseMapInfo<T*> { }; // 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; } @@ -103,7 +103,8 @@ template <> struct DenseMapInfo<unsigned char> { }; // 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; } @@ -114,47 +115,51 @@ template <> struct DenseMapInfo<unsigned short> { }; // 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; } @@ -162,58 +167,57 @@ template <> struct DenseMapInfo<short> { }; // 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() { @@ -221,7 +225,7 @@ struct DenseMapInfo<std::pair<T, U>> { 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)); } @@ -233,7 +237,8 @@ struct DenseMapInfo<std::pair<T, U>> { }; // 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() { @@ -282,6 +287,6 @@ template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> { } }; -} // end namespace llvm +} // end namespace llvm -#endif // LLVM_ADT_DENSEMAPINFO_H +#endif // LLVM_ADT_DENSEMAPINFO_H diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp b/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp index 352270adec0f..a8eca06182d6 100644 --- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp +++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp @@ -6,11 +6,12 @@ // //===----------------------------------------------------------------------===// -#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 { @@ -35,7 +36,7 @@ class CtorTester { static std::set<CtorTester *> Constructed; int Value; -public: + public: explicit CtorTester(int Value = 0) : Value(Value) { EXPECT_TRUE(Constructed.insert(this).second); } @@ -46,9 +47,7 @@ public: 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; } @@ -77,7 +76,7 @@ CtorTester getTestValue(int i, CtorTester *) { return CtorTester(42 + i); } // implementations of helper routines. template <typename T> class DenseMapTest : public ::testing::Test { -protected: + protected: T Map; static typename T::key_type *const dummy_key_ptr; @@ -97,14 +96,12 @@ 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 *>, + DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>, + SmallDenseMap<uint32_t, uint32_t>, SmallDenseMap<uint32_t *, uint32_t *>, + SmallDenseMap<CtorTester, CtorTester, 4, CtorTesterMapInfo>> + DenseMapTestTypes; TYPED_TEST_SUITE(DenseMapTest, DenseMapTestTypes, ); // Empty map tests @@ -276,8 +273,7 @@ TYPED_TEST(DenseMapTest, SwapTest) { 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()); @@ -350,7 +346,7 @@ struct CountCopyAndMove { int CountCopyAndMove::Copy = 0; int CountCopyAndMove::Move = 0; -} // anonymous namespace +} // anonymous namespace // Test initializer list construction. TEST(DenseMapCustomTest, InitializerList) { @@ -442,8 +438,7 @@ 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; @@ -511,14 +506,14 @@ TEST(DenseMapCustomTest, StringRefTest) { 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; } }; @@ -559,8 +554,8 @@ TEST(DenseMapCustomTest, SmallDenseMapInitializerList) { 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; } }; @@ -572,12 +567,9 @@ TEST(DenseMapCustomTest, SmallDenseMapGrowTest) { // 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()); @@ -592,14 +584,11 @@ TEST(DenseMapCustomTest, SmallDenseMapGrowTest) { 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 @@ -655,4 +644,4 @@ TEST(DenseMapCustomTest, OpaquePointerKey) { EXPECT_EQ(Map.find(K2), Map.end()); EXPECT_EQ(Map.find(K3), Map.end()); } -} +} // namespace |