LLVM 20.0.0git
|
ConcurrentHashTable - is a resizeable concurrent hashtable. More...
#include "llvm/ADT/ConcurrentHashtable.h"
Static Public Member Functions | |
static uint64_t | getHashValue (const KeyTy &Key) |
static bool | isEqual (const KeyTy &LHS, const KeyTy &RHS) |
static const KeyTy & | getKey (const KeyDataTy &KeyData) |
static KeyDataTy * | create (const KeyTy &Key, AllocatorTy &Allocator) |
ConcurrentHashTable - is a resizeable concurrent hashtable.
The number of resizings limited up to x2^31. This hashtable is useful to have efficient access to aggregate data(like strings, type descriptors...) and to keep only single copy of such an aggregate. The hashtable allows only concurrent insertions:
KeyDataTy* = insert ( const KeyTy& );
Data structure:
Inserted value KeyTy is mapped to 64-bit hash value ->
[------- 64-bit Hash value --------] [ StartEntryIndex ][ Bucket Index ] | | points to the points to first probe the bucket. position inside bucket entries
After initialization, all buckets have an initial size. During insertions, buckets might be extended to contain more entries. Each bucket can be independently resized and rehashed(no need to lock the whole table). Different buckets may have different sizes. If the single bucket is full then the bucket is resized.
BucketsArray keeps all buckets. Each bucket keeps an array of Entries (pointers to KeyDataTy) and another array of entries hashes:
BucketsArray[BucketIdx].Hashes[EntryIdx]: BucketsArray[BucketIdx].Entries[EntryIdx]:
[Bucket 0].Hashes -> [uint32_t][uint32_t] [Bucket 0].Entries -> [KeyDataTy*][KeyDataTy*]
[Bucket 1].Hashes -> [uint32_t][uint32_t][uint32_t][uint32_t] [Bucket 1].Entries -> [KeyDataTy*][KeyDataTy*][KeyDataTy*][KeyDataTy*] ......................... [Bucket N].Hashes -> [uint32_t][uint32_t][uint32_t] [Bucket N].Entries -> [KeyDataTy*][KeyDataTy*][KeyDataTy*]
ConcurrentHashTableByPtr uses an external thread-safe allocator to allocate KeyDataTy items.
Definition at line 75 of file ConcurrentHashtable.h.
|
inlinestatic |
Definition at line 93 of file ConcurrentHashtable.h.
References Allocator.
|
inlinestatic |
Key
. Definition at line 78 of file ConcurrentHashtable.h.
References llvm::xxh3_64bits().
|
inlinestatic |
KeyData
. Definition at line 88 of file ConcurrentHashtable.h.
|
inlinestatic |
LHS
and RHS
are equal. Definition at line 83 of file ConcurrentHashtable.h.