llvm::ConcurrentHashTableInfoByPtr< KeyTy, KeyDataTy, AllocatorTy > Class Template Reference

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)

Detailed Description

template<typename KeyTy, typename KeyDataTy, typename AllocatorTy>
class llvm::ConcurrentHashTableInfoByPtr< KeyTy, KeyDataTy, AllocatorTy >

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 76 of file ConcurrentHashtable.h.

Member Function Documentation

create()

template<typename KeyTy , typename KeyDataTy , typename AllocatorTy >

static KeyDataTy * llvm::ConcurrentHashTableInfoByPtr< KeyTy, KeyDataTy, AllocatorTy >::create ( const KeyTy &  Key, AllocatorTy &  Allocator  )

inlinestatic

Returns

newly created object of KeyDataTy type.

Definition at line 94 of file ConcurrentHashtable.h.

References Allocator.

getHashValue()

template<typename KeyTy , typename KeyDataTy , typename AllocatorTy >

static uint64_t llvm::ConcurrentHashTableInfoByPtr< KeyTy, KeyDataTy, AllocatorTy >::getHashValue ( const KeyTy &  Key )

inlinestatic

Returns

Hash value for the specified Key.

Definition at line 79 of file ConcurrentHashtable.h.

References llvm::xxh3_64bits().

getKey()

template<typename KeyTy , typename KeyDataTy , typename AllocatorTy >

static const KeyTy & llvm::ConcurrentHashTableInfoByPtr< KeyTy, KeyDataTy, AllocatorTy >::getKey ( const KeyDataTy &  KeyData )

inlinestatic

Returns

key for the specified KeyData.

Definition at line 89 of file ConcurrentHashtable.h.

isEqual()

template<typename KeyTy , typename KeyDataTy , typename AllocatorTy >

static bool llvm::ConcurrentHashTableInfoByPtr< KeyTy, KeyDataTy, AllocatorTy >::isEqual ( const KeyTy &  LHS, const KeyTy &  RHS  )

inlinestatic

Returns

true if both LHS and RHS are equal.

Definition at line 84 of file ConcurrentHashtable.h.

References LHS, and RHS.

---

The documentation for this class was generated from the following file:

• include/llvm/ADT/ConcurrentHashtable.h