From 4bb87cbac50098acc6816390c00fad419d3434fc Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Wed, 18 Apr 2012 10:37:32 +0000 Subject: [PATCH] SmallPtrSet: Reuse DenseMapInfo's pointer hash function instead of inventing a bad one ourselves. DenseMap's hash function uses slightly more entropy and reduces hash collisions significantly. I also experimented with Hashing.h, but it didn't gave a lot of improvement while being much more expensive to compute. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154996 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/SmallPtrSet.h | 3 --- lib/Support/SmallPtrSet.cpp | 3 ++- 2 files changed, 2 insertions(+), 4 deletions(-) diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 70693d5b9aa..498a0345d8b 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -126,9 +126,6 @@ protected: private: bool isSmall() const { return CurArray == SmallArray; } - unsigned Hash(const void *Ptr) const { - return static_cast(((uintptr_t)Ptr >> 4) & (CurArraySize-1)); - } const void * const *FindBucketFor(const void *Ptr) const; void shrink_and_clear(); diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index 68d9c29411f..3b53e9ff49f 100644 --- a/lib/Support/SmallPtrSet.cpp +++ b/lib/Support/SmallPtrSet.cpp @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/DenseMapInfo.h" #include "llvm/Support/MathExtras.h" #include #include @@ -102,7 +103,7 @@ bool SmallPtrSetImpl::erase_imp(const void * Ptr) { } const void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const { - unsigned Bucket = Hash(Ptr); + unsigned Bucket = DenseMapInfo::getHashValue(Ptr) & (CurArraySize-1); unsigned ArraySize = CurArraySize; unsigned ProbeAmt = 1; const void *const *Array = CurArray; -- 2.11.0