9#ifndef LLVM_ADT_CONCURRENTHASHTABLE_H
10#define LLVM_ADT_CONCURRENTHASHTABLE_H
75template <
typename KeyTy,
typename KeyDataTy,
typename AllocatorTy>
89 static inline const KeyTy &
getKey(
const KeyDataTy &KeyData) {
90 return KeyData.getKey();
99template <
typename KeyTy,
typename KeyDataTy,
typename AllocatorTy,
101 ConcurrentHashTableInfoByPtr<KeyTy, KeyDataTy, AllocatorTy>>
107 size_t InitialNumberOfBuckets = 128)
109 assert((ThreadsNum > 0) &&
"ThreadsNum must be greater than 0");
110 assert((InitialNumberOfBuckets > 0) &&
111 "InitialNumberOfBuckets must be greater than 0");
114 uint64_t EstimatedNumberOfBuckets = ThreadsNum;
115 if (ThreadsNum > 1) {
116 EstimatedNumberOfBuckets *= InitialNumberOfBuckets;
117 EstimatedNumberOfBuckets *= std::max(
122 EstimatedNumberOfBuckets =
PowerOf2Ceil(EstimatedNumberOfBuckets);
124 std::min(EstimatedNumberOfBuckets, (
uint64_t)(1Ull << 31));
154 MaxBucketSize = 1Ull << (std::min((
size_t)31, LeadingZerosNumber));
172 std::pair<KeyDataTy *, bool>
insert(
const KeyTy &NewValue) {
174 uint64_t Hash = Info::getHashValue(NewValue);
178#if LLVM_ENABLE_THREADS
180 CurBucket.Guard.lock();
188 uint32_t CurEntryHashBits = BucketHashes[CurEntryIdx];
190 if (CurEntryHashBits == 0 && BucketEntries[CurEntryIdx] ==
nullptr) {
193 BucketEntries[CurEntryIdx] = NewData;
194 BucketHashes[CurEntryIdx] = ExtHashBits;
199#if LLVM_ENABLE_THREADS
200 CurBucket.Guard.unlock();
203 return {NewData,
true};
206 if (CurEntryHashBits == ExtHashBits) {
208 KeyDataTy *EntryData = BucketEntries[CurEntryIdx];
209 if (Info::isEqual(Info::getKey(*EntryData), NewValue)) {
211#if LLVM_ENABLE_THREADS
212 CurBucket.Guard.unlock();
215 return {EntryData,
false};
220 CurEntryIdx &= (CurBucket.
Size - 1);
229 OS <<
"\n--- HashTable statistic:\n";
233 uint64_t NumberOfNonEmptyBuckets = 0;
234 uint64_t NumberOfEntriesPlusEmpty = 0;
235 uint64_t OverallNumberOfEntries = 0;
244 BucketSizesMap[CurBucket.
Size]++;
247 NumberOfNonEmptyBuckets++;
248 NumberOfEntriesPlusEmpty += CurBucket.
Size;
254 OS <<
"\nOverall number of entries = " << OverallNumberOfEntries;
255 OS <<
"\nOverall number of non empty buckets = " << NumberOfNonEmptyBuckets;
256 for (
auto &BucketSize : BucketSizesMap)
257 OS <<
"\n Number of buckets with size " << BucketSize.first <<
": "
258 << BucketSize.second;
260 std::stringstream stream;
261 stream << std::fixed << std::setprecision(2)
262 << ((float)OverallNumberOfEntries / (
float)NumberOfEntriesPlusEmpty);
263 std::string str = stream.str();
265 OS <<
"\nLoad factor = " << str;
266 OS <<
"\nOverall allocated size = " << OverallSize;
292#if LLVM_ENABLE_THREADS
300 assert((CurBucket.
Size > 0) &&
"Uninitialised bucket");
310 "New bucket size less than size of current bucket");
318 memset(DestHashes, 0,
sizeof(
ExtHashBitsTy) * NewBucketSize);
321 memset(DestEntries, 0,
sizeof(
EntryDataTy) * NewBucketSize);
324 for (
uint32_t CurSrcEntryIdx = 0; CurSrcEntryIdx < CurBucket.
Size;
326 uint32_t CurSrcEntryHashBits = SrcHashes[CurSrcEntryIdx];
329 if (CurSrcEntryHashBits == 0 && SrcEntries[CurSrcEntryIdx] ==
nullptr)
336 uint32_t CurDestEntryHashBits = DestHashes[StartDestIdx];
338 if (CurDestEntryHashBits == 0 && DestEntries[StartDestIdx] ==
nullptr) {
340 DestHashes[StartDestIdx] = CurSrcEntryHashBits;
341 DestEntries[StartDestIdx] = SrcEntries[CurSrcEntryIdx];
346 StartDestIdx = StartDestIdx & (NewBucketSize - 1);
351 CurBucket.
Hashes = DestHashes;
352 CurBucket.
Entries = DestEntries;
353 CurBucket.
Size = NewBucketSize;
356 if (SrcHashes !=
nullptr)
358 if (SrcEntries !=
nullptr)
369 assert((BucketSize > 0) &&
"Empty bucket");
371 return ExtHashBits & (BucketSize - 1);
This file defines the BumpPtrAllocator interface.
Analysis containing CSE Info
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
std::pair< KeyDataTy *, bool > insert(const KeyTy &NewValue)
Insert new value NewValue or return already existing entry.
uint32_t getStartIdx(uint32_t ExtHashBits, uint32_t BucketSize)
virtual ~ConcurrentHashTableByPtr()
std::unique_ptr< Bucket[]> BucketsArray
uint32_t getBucketIdx(hash_code Hash)
void printStatistic(raw_ostream &OS)
Print information about current state of hash table structures.
void RehashBucket(Bucket &CurBucket)
uint32_t InitialBucketSize
uint32_t getExtHashBits(uint64_t Hash)
ConcurrentHashTableByPtr(AllocatorTy &Allocator, uint64_t EstimatedSize=100000, size_t ThreadsNum=parallel::strategy.compute_thread_count(), size_t InitialNumberOfBuckets=128)
AllocatorTy & MultiThreadAllocator
ConcurrentHashTable - is a resizeable concurrent hashtable.
static KeyDataTy * create(const KeyTy &Key, AllocatorTy &Allocator)
static const KeyTy & getKey(const KeyDataTy &KeyData)
static bool isEqual(const KeyTy &LHS, const KeyTy &RHS)
static uint64_t getHashValue(const KeyTy &Key)
An opaque object representing a hash code.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ThreadPoolStrategy strategy
This is an optimization pass for GlobalISel generic memory operations.
uint64_t xxh3_64bits(ArrayRef< uint8_t > data)
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.