[sanitizer_common] DenseMap: replace tombstone deletion with TAOCP 6.4 Algorithm R#202231
Merged
Merged
Conversation
…4 Algorithm R sanitizer_dense_map.h is a fork of llvm/ADT/DenseMap.h, which uses quadratic probing with lazy deletion: an erased entry becomes a tombstone, a third bucket state alongside empty and live that every find/insert must inspect. Port the upstream llvm#200595 and getTombstoneKey() removal.
|
@llvm/pr-subscribers-compiler-rt-sanitizer Author: Fangrui Song (MaskRay) Changessanitizer_dense_map.h is a fork of llvm/ADT/DenseMap.h, which uses Port the upstream #200595 and getTombstoneKey() removal. Aided by Claude Opus 4.8 Patch is 21.35 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/202231.diff 4 Files Affected:
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h
index c63788653de75..9dc196de851f3 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h
@@ -44,10 +44,10 @@ class DenseMapBase {
}
void clear() {
- if (getNumEntries() == 0 && getNumTombstones() == 0)
+ if (getNumEntries() == 0)
return;
- const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
+ const KeyT EmptyKey = getEmptyKey();
if (__sanitizer::is_trivially_destructible<ValueT>::value) {
// Use a simpler loop when values don't need destruction.
for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P)
@@ -56,17 +56,14 @@ class DenseMapBase {
unsigned NumEntries = getNumEntries();
for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {
- if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
- P->getSecond().~ValueT();
- --NumEntries;
- }
+ P->getSecond().~ValueT();
+ --NumEntries;
P->getFirst() = EmptyKey;
}
}
CHECK_EQ(NumEntries, 0);
}
setNumEntries(0);
- setNumTombstones(0);
}
/// Return true if the specified key is in the map, false otherwise.
@@ -171,20 +168,13 @@ class DenseMapBase {
if (!TheBucket)
return false; // not in map.
- TheBucket->getSecond().~ValueT();
- TheBucket->getFirst() = getTombstoneKey();
- decrementNumEntries();
- incrementNumTombstones();
+ eraseFromFilledBucket(TheBucket);
return true;
}
void erase(value_type *I) {
CHECK_NE(I, nullptr);
- BucketT *TheBucket = &*I;
- TheBucket->getSecond().~ValueT();
- TheBucket->getFirst() = getTombstoneKey();
- decrementNumEntries();
- incrementNumTombstones();
+ eraseFromFilledBucket(I);
}
value_type &FindAndConstruct(const KeyT &Key) {
@@ -214,11 +204,10 @@ class DenseMapBase {
/// Function can return fast to stop the process.
template <class Fn>
void forEach(Fn fn) {
- const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
+ const KeyT EmptyKey = getEmptyKey();
for (auto *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
const KeyT K = P->getFirst();
- if (!KeyInfoT::isEqual(K, EmptyKey) &&
- !KeyInfoT::isEqual(K, TombstoneKey)) {
+ if (!KeyInfoT::isEqual(K, EmptyKey)) {
if (!fn(*P))
return;
}
@@ -238,10 +227,9 @@ class DenseMapBase {
if (getNumBuckets() == 0) // Nothing to do.
return;
- const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
+ const KeyT EmptyKey = getEmptyKey();
for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
- if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
- !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
+ if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey))
P->getSecond().~ValueT();
P->getFirst().~KeyT();
}
@@ -249,7 +237,6 @@ class DenseMapBase {
void initEmpty() {
setNumEntries(0);
- setNumTombstones(0);
CHECK_EQ((getNumBuckets() & (getNumBuckets() - 1)), 0);
const KeyT EmptyKey = getEmptyKey();
@@ -273,10 +260,8 @@ class DenseMapBase {
// Insert all the old elements.
const KeyT EmptyKey = getEmptyKey();
- const KeyT TombstoneKey = getTombstoneKey();
for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
- if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&
- !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) {
+ if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey)) {
// Insert the key/value into the new table.
BucketT *DestBucket;
bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
@@ -301,7 +286,6 @@ class DenseMapBase {
CHECK_EQ(getNumBuckets(), other.getNumBuckets());
setNumEntries(other.getNumEntries());
- setNumTombstones(other.getNumTombstones());
if (__sanitizer::is_trivially_copyable<KeyT>::value &&
__sanitizer::is_trivially_copyable<ValueT>::value)
@@ -311,8 +295,7 @@ class DenseMapBase {
for (uptr i = 0; i < getNumBuckets(); ++i) {
::new (&getBuckets()[i].getFirst())
KeyT(other.getBuckets()[i].getFirst());
- if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
- !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
+ if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()))
::new (&getBuckets()[i].getSecond())
ValueT(other.getBuckets()[i].getSecond());
}
@@ -329,9 +312,40 @@ class DenseMapBase {
static const KeyT getEmptyKey() { return KeyInfoT::getEmptyKey(); }
- static const KeyT getTombstoneKey() { return KeyInfoT::getTombstoneKey(); }
-
private:
+ /// Erase the entry at \p TheBucket and close the resulting hole via Knuth
+ /// TAOCP 6.4 Algorithm R: walk forward over the cluster, shifting back any
+ /// entry whose linear-probe chain from its home bucket passes through the
+ /// hole, until an empty bucket terminates the cluster.
+ void eraseFromFilledBucket(BucketT* TheBucket) {
+ TheBucket->getSecond().~ValueT();
+ decrementNumEntries();
+
+ BucketT* BucketsPtr = getBuckets();
+ const unsigned NumBuckets = getNumBuckets();
+ const unsigned Mask = NumBuckets - 1;
+ const KeyT EmptyKey = getEmptyKey();
+ unsigned I = static_cast<unsigned>(TheBucket - BucketsPtr);
+ unsigned J = I;
+ while (true) {
+ J = (J + 1) & Mask;
+ BucketT& BJ = BucketsPtr[J];
+ if (KeyInfoT::isEqual(BJ.getFirst(), EmptyKey))
+ break;
+ unsigned Ideal = getHashValue(BJ.getFirst()) & Mask;
+ // If the hole (I) lies on the linear-probe chain from the home bucket
+ // (Ideal) to J, shift J into the hole and make J the new hole.
+ if (((I - Ideal) & Mask) < ((J - Ideal) & Mask)) {
+ BucketT& BI = BucketsPtr[I];
+ BI.getFirst() = __sanitizer::move(BJ.getFirst());
+ ::new (&BI.getSecond()) ValueT(__sanitizer::move(BJ.getSecond()));
+ BJ.getSecond().~ValueT();
+ I = J;
+ }
+ }
+ BucketsPtr[I].getFirst() = EmptyKey;
+ }
+
unsigned getNumEntries() const {
return static_cast<const DerivedT *>(this)->getNumEntries();
}
@@ -344,18 +358,6 @@ class DenseMapBase {
void decrementNumEntries() { setNumEntries(getNumEntries() - 1); }
- unsigned getNumTombstones() const {
- return static_cast<const DerivedT *>(this)->getNumTombstones();
- }
-
- void setNumTombstones(unsigned Num) {
- static_cast<DerivedT *>(this)->setNumTombstones(Num);
- }
-
- void incrementNumTombstones() { setNumTombstones(getNumTombstones() + 1); }
-
- void decrementNumTombstones() { setNumTombstones(getNumTombstones() - 1); }
-
const BucketT *getBuckets() const {
return static_cast<const DerivedT *>(this)->getBuckets();
}
@@ -398,25 +400,16 @@ class DenseMapBase {
template <typename LookupKeyT>
BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
BucketT *TheBucket) {
- // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
- // the buckets are empty (meaning that many are filled with tombstones),
- // grow the table.
- //
- // The later case is tricky. For example, if we had one empty bucket with
- // tons of tombstones, failing lookups (e.g. for insertion) would have to
- // probe almost the entire table until it found the empty bucket. If the
- // table completely filled with tombstones, no lookup would ever succeed,
- // causing infinite loops in lookup.
+ // Grow the table if the load factor would exceed 3/4 after insertion.
+ // Linear probing with gap-closing deletion (Knuth Algorithm R) keeps every
+ // chain compact and bounded by the table's empty-bucket count, so no
+ // tombstone-driven resize is needed.
unsigned NewNumEntries = getNumEntries() + 1;
unsigned NumBuckets = getNumBuckets();
if (UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
this->grow(NumBuckets * 2);
LookupBucketFor(Lookup, TheBucket);
NumBuckets = getNumBuckets();
- } else if (UNLIKELY(NumBuckets - (NewNumEntries + getNumTombstones()) <=
- NumBuckets / 8)) {
- this->grow(NumBuckets);
- LookupBucketFor(Lookup, TheBucket);
}
CHECK(TheBucket);
@@ -424,11 +417,6 @@ class DenseMapBase {
// 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;
}
@@ -441,7 +429,6 @@ class DenseMapBase {
const KeyT EmptyKey = getEmptyKey();
unsigned BucketNo = getHashValue(Val) & (NumBuckets - 1);
- unsigned ProbeAmt = 1;
while (true) {
BucketT *Bucket = BucketsPtr + BucketNo;
if (LIKELY(KeyInfoT::isEqual(Val, Bucket->getFirst())))
@@ -449,10 +436,8 @@ class DenseMapBase {
if (LIKELY(KeyInfoT::isEqual(Bucket->getFirst(), EmptyKey)))
return nullptr;
- // Otherwise, it's a hash collision or a tombstone, continue quadratic
- // probing.
- BucketNo += ProbeAmt++;
- BucketNo &= NumBuckets - 1;
+ // Hash collision: continue linear probing.
+ BucketNo = (BucketNo + 1) & (NumBuckets - 1);
}
}
@@ -463,8 +448,8 @@ class DenseMapBase {
/// 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.
+ /// true, otherwise it returns a bucket with an empty marker and returns
+ /// false.
template <typename LookupKeyT>
bool LookupBucketFor(const LookupKeyT &Val,
const BucketT *&FoundBucket) const {
@@ -476,15 +461,10 @@ class DenseMapBase {
return false;
}
- // FoundTombstone - Keep track of whether we find a tombstone while probing.
- const BucketT *FoundTombstone = nullptr;
const KeyT EmptyKey = getEmptyKey();
- const KeyT TombstoneKey = getTombstoneKey();
CHECK(!KeyInfoT::isEqual(Val, EmptyKey));
- CHECK(!KeyInfoT::isEqual(Val, TombstoneKey));
unsigned BucketNo = getHashValue(Val) & (NumBuckets - 1);
- unsigned ProbeAmt = 1;
while (true) {
const BucketT *ThisBucket = BucketsPtr + BucketNo;
// Found Val's bucket? If so, return it.
@@ -494,24 +474,14 @@ class DenseMapBase {
}
// If we found an empty bucket, the key doesn't exist in the set.
- // Insert it and return the default value.
+ // Return it as the insertion point.
if (LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
- // If we've already seen a tombstone while probing, fill it in instead
- // of the empty bucket we eventually probed to.
- FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
+ FoundBucket = ThisBucket;
return false;
}
- // If this is a tombstone, remember it. If Val ends up not in the map, we
- // prefer to return it than something that would require more probing.
- if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
- !FoundTombstone)
- FoundTombstone = ThisBucket; // Remember the first tombstone found.
-
- // Otherwise, it's a hash collision or a tombstone, continue quadratic
- // probing.
- BucketNo += ProbeAmt++;
- BucketNo &= (NumBuckets - 1);
+ // Hash collision: continue linear probing.
+ BucketNo = (BucketNo + 1) & (NumBuckets - 1);
}
}
@@ -587,7 +557,6 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
BucketT *Buckets = nullptr;
unsigned NumEntries = 0;
- unsigned NumTombstones = 0;
unsigned NumBuckets = 0;
public:
@@ -614,7 +583,6 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
void swap(DenseMap &RHS) {
Swap(Buckets, RHS.Buckets);
Swap(NumEntries, RHS.NumEntries);
- Swap(NumTombstones, RHS.NumTombstones);
Swap(NumBuckets, RHS.NumBuckets);
}
@@ -639,7 +607,6 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
this->BaseT::copyFrom(other);
} else {
NumEntries = 0;
- NumTombstones = 0;
}
}
@@ -649,7 +616,6 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
this->BaseT::initEmpty();
} else {
NumEntries = 0;
- NumTombstones = 0;
}
}
@@ -675,10 +641,6 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
void setNumEntries(unsigned Num) { NumEntries = Num; }
- unsigned getNumTombstones() const { return NumTombstones; }
-
- void setNumTombstones(unsigned Num) { NumTombstones = Num; }
-
BucketT *getBuckets() const { return Buckets; }
unsigned getNumBuckets() const { return NumBuckets; }
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 f4640369ae588..a3c7b6d9571ed 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h
@@ -62,7 +62,6 @@ struct DenseMapPair {
template <typename T>
struct DenseMapInfo {
// static T getEmptyKey();
- // static T getTombstoneKey();
// static unsigned getHashValue(const T &Val);
// static bool isEqual(const T &LHS, const T &RHS);
};
@@ -86,12 +85,6 @@ struct DenseMapInfo<T *> {
return reinterpret_cast<T *>(Val);
}
- static constexpr T *getTombstoneKey() {
- uptr Val = static_cast<uptr>(-2);
- Val <<= Log2MaxAlign;
- return reinterpret_cast<T *>(Val);
- }
-
static constexpr unsigned getHashValue(const T *PtrVal) {
return (unsigned((uptr)PtrVal) >> 4) ^ (unsigned((uptr)PtrVal) >> 9);
}
@@ -105,7 +98,6 @@ struct DenseMapInfo<T *> {
template <>
struct DenseMapInfo<char> {
static constexpr char getEmptyKey() { return ~0; }
- static constexpr char getTombstoneKey() { return ~0 - 1; }
static constexpr unsigned getHashValue(const char &Val) { return Val * 37U; }
static constexpr bool isEqual(const char &LHS, const char &RHS) {
@@ -117,7 +109,6 @@ struct DenseMapInfo<char> {
template <>
struct DenseMapInfo<unsigned char> {
static constexpr unsigned char getEmptyKey() { return ~0; }
- static constexpr unsigned char getTombstoneKey() { return ~0 - 1; }
static constexpr unsigned getHashValue(const unsigned char &Val) {
return Val * 37U;
}
@@ -132,7 +123,6 @@ struct DenseMapInfo<unsigned char> {
template <>
struct DenseMapInfo<unsigned short> {
static constexpr unsigned short getEmptyKey() { return 0xFFFF; }
- static constexpr unsigned short getTombstoneKey() { return 0xFFFF - 1; }
static constexpr unsigned getHashValue(const unsigned short &Val) {
return Val * 37U;
}
@@ -147,7 +137,6 @@ struct DenseMapInfo<unsigned short> {
template <>
struct DenseMapInfo<unsigned> {
static constexpr unsigned getEmptyKey() { return ~0U; }
- static constexpr unsigned getTombstoneKey() { return ~0U - 1; }
static constexpr unsigned getHashValue(const unsigned &Val) {
return Val * 37U;
}
@@ -161,7 +150,6 @@ struct DenseMapInfo<unsigned> {
template <>
struct DenseMapInfo<unsigned long> {
static constexpr unsigned long getEmptyKey() { return ~0UL; }
- static constexpr unsigned long getTombstoneKey() { return ~0UL - 1L; }
static constexpr unsigned getHashValue(const unsigned long &Val) {
return (unsigned)(Val * 37UL);
@@ -177,7 +165,6 @@ struct DenseMapInfo<unsigned long> {
template <>
struct DenseMapInfo<unsigned long long> {
static constexpr unsigned long long getEmptyKey() { return ~0ULL; }
- static constexpr unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
static constexpr unsigned getHashValue(const unsigned long long &Val) {
return (unsigned)(Val * 37ULL);
@@ -193,7 +180,6 @@ struct DenseMapInfo<unsigned long long> {
template <>
struct DenseMapInfo<short> {
static constexpr short getEmptyKey() { return 0x7FFF; }
- static constexpr short getTombstoneKey() { return -0x7FFF - 1; }
static constexpr unsigned getHashValue(const short &Val) { return Val * 37U; }
static constexpr bool isEqual(const short &LHS, const short &RHS) {
return LHS == RHS;
@@ -204,7 +190,6 @@ struct DenseMapInfo<short> {
template <>
struct DenseMapInfo<int> {
static constexpr int getEmptyKey() { return 0x7fffffff; }
- static constexpr int getTombstoneKey() { return -0x7fffffff - 1; }
static constexpr unsigned getHashValue(const int &Val) {
return (unsigned)(Val * 37U);
}
@@ -221,8 +206,6 @@ struct DenseMapInfo<long> {
return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
}
- static constexpr long getTombstoneKey() { return getEmptyKey() - 1L; }
-
static constexpr unsigned getHashValue(const long &Val) {
return (unsigned)(Val * 37UL);
}
@@ -236,9 +219,6 @@ struct DenseMapInfo<long> {
template <>
struct DenseMapInfo<long long> {
static constexpr long long getEmptyKey() { return 0x7fffffffffffffffLL; }
- static constexpr long long getTombstoneKey() {
- return -0x7fffffffffffffffLL - 1;
- }
static constexpr unsigned getHashValue(const long long &Val) {
return (unsigned)(Val * 37ULL);
@@ -261,11 +241,6 @@ struct DenseMapInfo<detail::DenseMapPair<T, U>> {
SecondInfo::getEmptyKey());
}
- static constexpr Pair getTombstoneKey() {
- return detail::DenseMapPair<T, U>(FirstInfo::getTombstoneKey(),
- SecondInfo::getTombstoneKey());
- }
-
static constexpr unsigned getHashValue(const Pair &PairVal) {
return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first),
SecondInfo::getHashValue(PairVal.second));
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_lzw.h b/compiler-rt/lib/sanitizer_common/sanitizer_lzw.h
index 42acfbdcea092..d8e7d1f217627 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_lzw.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_lzw.h
@@ -26,9 +26,7 @@ ItOut LzwEncode(ItIn begin, ItIn end, ItOut out) {
// Sentinel value for substrings of len 1.
static constexpr LzwCodeType kNoPrefix =
- Min(DenseMapInfo<Substring>::getEmptyKey().first,
- DenseMapInfo<Substring>::getTombstoneKey().first) -
- 1;
+ DenseMapInfo<Substring>::getEmptyKey().first - 1;
DenseMap<Substring, LzwCodeType> prefix_to_code;
{
// Add all substring of len 1 as initial dictionary.
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 1336f1d85eac7..f122c32d1124e 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
@@ -83,7 +83,6 @@ std::set<CtorTester *> CtorTester::Constructed;
struct CtorTesterMapInfo {
static inline CtorTester getEmptyKey() { return CtorTester(-1); }
- static inline CtorTester getTombstoneKey() { return CtorTester(-2); }
static unsigned getHashValue(const CtorTester &Val) {
return Val.getValue() * 37u;
}
@@ -476,7 +475,6 @@ TEST(DenseMapCustomTest, ReserveTest) {
// 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) {
return (unsigned)(Val[0] - 'a') * 37U;
@@ -489,6 +487,47 @@ struct TestDenseMapInfo {
}
};
+// Hashes every key to the same home bucket, so the table degenerates into a
+// single long linear-probe cluster -- the worst case f...
[truncated]
|
vitalybuka
approved these changes
Jun 8, 2026
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
sanitizer_dense_map.h is a fork of llvm/ADT/DenseMap.h, which uses
quadratic probing with lazy deletion: an erased entry becomes a
tombstone, a third bucket state alongside empty and live that every
find/insert must inspect.
Port the upstream #200595 and getTombstoneKey() removal.
Aided by Claude Opus 4.8