llvm::ConcurrentHashTableByPtr

Synopsis

Declared in <llvm/ADT/ConcurrentHashtable.h>

template<
    typename KeyTy,
    typename KeyDataTy,
    typename AllocatorTy,
    typename Info = ConcurrentHashTableInfoByPtr<KeyTy, KeyDataTy, AllocatorTy>>
class ConcurrentHashTableByPtr;

Description

Values are allocated from an external thread-safe allocator. The table supports only concurrent insertions and keeps a single copy of each key. Keys map to a 64-bit hash whose low bits select a bucket and higher bits choose the first probe slot. Buckets resize and rehash independently so inserts do not need a whole-table lock. Resizing is limited to a factor of about 2^31 overall.

BucketsArray stores each bucket's entry pointers and extended hash bits:


BucketsArray[BucketIdx].Hashes[EntryIdx]
BucketsArray[BucketIdx].Entries[EntryIdx]

Member Functions

Name	Description
`ConcurrentHashTableByPtr` [constructor]	Build a table sized for about `EstimatedSize` entries and `ThreadsNum` concurrent inserters, starting with `InitialNumberOfBuckets` buckets.
`~ConcurrentHashTableByPtr` [destructor] [virtual]	Destroy the table and free per-bucket hash and entry arrays.
`insert`	Insert new value `NewValue` or return already existing entry.
`printStatistic`	Print information about current state of hash table structures.

Protected Types

Name	Description
`Bucket`	Independently locked slot group holding hash bits and value pointers.

Protected Type Aliases

Name	Description
`DataPtr`	Pointer to the per-bucket array of value pointers.
`EntryDataTy`	Pointer to an allocated table value.
`ExtHashBitsTy`	High bits of a key hash stored beside each bucket entry.
`HashesPtr`	Pointer to the per-bucket array of extended hash bits.

Protected Member Functions

Name	Description
`RehashBucket`	Double `CurBucket` and rehash its entries when load is high enough.
`getBucketIdx`	Map `Hash` to a bucket index using the table's hash mask.
`getExtHashBits`	Extract the extended probe bits from full hash `Hash.`
`getStartIdx`	Compute the first probe index inside a bucket from extended hash bits.

Protected Data Members

Name	Description
`BucketsArray`	Contiguous storage of all hash-table buckets.
`ExtHashMask`	Mask selecting bucket index plus extended probe bits from a full hash.
`HashBitsNum`	Number of low hash bits used to select a bucket.
`HashMask`	Mask selecting the bucket index from a full hash.
`InitialBucketSize`	Starting capacity assigned to each bucket at construction.
`MaxBucketSize`	Largest power-of-two capacity allowed for any single bucket.
`MultiThreadAllocator`	Allocator used to create inserted `KeyDataTy` values.
`NumberOfBuckets`	Current number of buckets in `BucketsArray.`

Derived Classes

Name	Description
`StringPool`	Concurrent string pool used by the DWARF linker.