llvm::ThreadSafeTrieRawHashMapBase Class Reference

TrieRawHashMap - is a lock-free thread-safe trie that is can be used to store/index data based on a hash value. More...

#include "llvm/ADT/TrieRawHashMap.h"

Inheritance diagram for llvm::ThreadSafeTrieRawHashMapBase:

Classes
class	ImplType
class	PointerBase
	Result of a lookup. More...

Public Member Functions
void	operator delete (void *Ptr)
LLVM_DUMP_METHOD void	dump () const
void	print (raw_ostream &OS) const

Static Public Member Functions
static void *	operator new (size_t Size)

Static Public Attributes
static constexpr size_t	TrieContentBaseSize = 4
static constexpr size_t	DefaultNumRootBits = 6
static constexpr size_t	DefaultNumSubtrieBits = 4

Protected Member Functions
PointerBase	find (ArrayRef< uint8_t > Hash) const
	Find the stored content with hash.
PointerBase	insert (PointerBase Hint, ArrayRef< uint8_t > Hash, function_ref< const uint8_t *(void *Mem, ArrayRef< uint8_t > Hash)> Constructor)
	Insert and return the stored content.
	ThreadSafeTrieRawHashMapBase ()=delete
	ThreadSafeTrieRawHashMapBase (size_t ContentAllocSize, size_t ContentAllocAlign, size_t ContentOffset, std::optional< size_t > NumRootBits=std::nullopt, std::optional< size_t > NumSubtrieBits=std::nullopt)
	~ThreadSafeTrieRawHashMapBase ()
	Destructor, which asserts if there's anything to do.
void	destroyImpl (function_ref< void(void *ValueMem)> Destructor)
	ThreadSafeTrieRawHashMapBase (ThreadSafeTrieRawHashMapBase &&RHS)
ThreadSafeTrieRawHashMapBase &	operator= (ThreadSafeTrieRawHashMapBase &&RHS)=delete
	ThreadSafeTrieRawHashMapBase (const ThreadSafeTrieRawHashMapBase &)=delete
ThreadSafeTrieRawHashMapBase &	operator= (const ThreadSafeTrieRawHashMapBase &)=delete
PointerBase	getRoot () const
unsigned	getStartBit (PointerBase P) const
unsigned	getNumBits (PointerBase P) const
unsigned	getNumSlotUsed (PointerBase P) const
std::string	getTriePrefixAsString (PointerBase P) const
unsigned	getNumTries () const
PointerBase	getNextTrie (PointerBase P) const

Static Protected Attributes
template<class T >
static constexpr size_t	DefaultContentAllocSize = sizeof(AllocValueType<T>)
template<class T >
static constexpr size_t	DefaultContentAllocAlign = alignof(AllocValueType<T>)
template<class T >
static constexpr size_t	DefaultContentOffset

Friends
class	TrieRawHashMapTestHelper

Detailed Description

TrieRawHashMap - is a lock-free thread-safe trie that is can be used to store/index data based on a hash value.

It can be customized to work with any hash algorithm or store any data.

Data structure: Data node stored in the Trie contains both hash and data: struct { HashT Hash; DataT Data; };

Data is stored/indexed via a prefix tree, where each node in the tree can be either the root, a sub-trie or a data node. Assuming a 4-bit hash and two data objects {0001, A} and {0100, B}, it can be stored in a trie (assuming Root has 2 bits, SubTrie has 1 bit): +-----—+ |Root[00]| -> {0001, A} | [01]| -> {0100, B} | [10]| (empty) | [11]| (empty) +-----—+

Inserting a new object {0010, C} will result in: +-----—+ +-------—+ |Root[00]| -> |SubTrie[0]| -> {0001, A} | | | [1]| -> {0010, C} | | +-------—+ | [01]| -> {0100, B} | [10]| (empty) | [11]| (empty) +-----—+ Note object A is sunk down to a sub-trie during the insertion. All the nodes are inserted through compare-exchange to ensure thread-safe and lock-free.

To find an object in the trie, walk the tree with prefix of the hash until the data node is found. Then the hash is compared with the hash stored in the data node to see if the is the same object.

Hash collision is not allowed so it is recommended to use trie with a "strong" hashing algorithm. A well-distributed hash can also result in better performance and memory usage.

It currently does not support iteration and deletion. Base class for a lock-free thread-safe hash-mapped trie.

Definition at line 66 of file TrieRawHashMap.h.

Constructor & Destructor Documentation

ThreadSafeTrieRawHashMapBase() [1/4]

llvm::ThreadSafeTrieRawHashMapBase::ThreadSafeTrieRawHashMapBase ( )

protecteddelete

ThreadSafeTrieRawHashMapBase() [2/4]

ThreadSafeTrieRawHashMapBase::ThreadSafeTrieRawHashMapBase ( size_t  ContentAllocSize, size_t  ContentAllocAlign, size_t  ContentOffset, std::optional< size_t >  NumRootBits = std::nullopt, std::optional< size_t >  NumSubtrieBits = std::nullopt  )

protected

Definition at line 331 of file TrieRawHashMap.cpp.

References assert().

~ThreadSafeTrieRawHashMapBase()

ThreadSafeTrieRawHashMapBase::~ThreadSafeTrieRawHashMapBase ( )

protected

Destructor, which asserts if there's anything to do.

Subclasses should call destroyImpl().

Precondition

destroyImpl() was already called.

Definition at line 358 of file TrieRawHashMap.cpp.

References assert().

ThreadSafeTrieRawHashMapBase() [3/4]

ThreadSafeTrieRawHashMapBase::ThreadSafeTrieRawHashMapBase ( ThreadSafeTrieRawHashMapBase &&  RHS )

protected

Definition at line 348 of file TrieRawHashMap.cpp.

References RHS.

ThreadSafeTrieRawHashMapBase() [4/4]

llvm::ThreadSafeTrieRawHashMapBase::ThreadSafeTrieRawHashMapBase ( const ThreadSafeTrieRawHashMapBase &  )

protecteddelete

Member Function Documentation

destroyImpl()

void ThreadSafeTrieRawHashMapBase::destroyImpl ( function_ref< void(void *ValueMem)>  Destructor )

protected

Definition at line 362 of file TrieRawHashMap.cpp.

References Content, and I.

Referenced by llvm::ThreadSafeTrieRawHashMap< T, NumHashBytes >::~ThreadSafeTrieRawHashMap().

dump()

LLVM_DUMP_METHOD void llvm::ThreadSafeTrieRawHashMapBase::dump

(

)

const

find()

ThreadSafeTrieRawHashMapBase::PointerBase ThreadSafeTrieRawHashMapBase::find ( ArrayRef< uint8_t >  Hash ) const

protected

Find the stored content with hash.

Definition at line 231 of file TrieRawHashMap.cpp.

References assert(), llvm::ArrayRef< T >::empty(), llvm::ThreadSafeTrieRawHashMapBase::ImplType::getRoot(), Index, and llvm_unreachable.

Referenced by llvm::ThreadSafeTrieRawHashMap< T, NumHashBytes >::find().

getNextTrie()

ThreadSafeTrieRawHashMapBase::PointerBase ThreadSafeTrieRawHashMapBase::getNextTrie ( ThreadSafeTrieRawHashMapBase::PointerBase  P ) const

protected

Definition at line 504 of file TrieRawHashMap.cpp.

References assert(), E, and P.

getNumBits()

unsigned ThreadSafeTrieRawHashMapBase::getNumBits ( ThreadSafeTrieRawHashMapBase::PointerBase  P ) const

protected

Definition at line 407 of file TrieRawHashMap.cpp.

References assert(), and P.

getNumSlotUsed()

unsigned ThreadSafeTrieRawHashMapBase::getNumSlotUsed ( ThreadSafeTrieRawHashMapBase::PointerBase  P ) const

protected

Definition at line 417 of file TrieRawHashMap.cpp.

References assert(), E, I, and P.

getNumTries()

unsigned ThreadSafeTrieRawHashMapBase::getNumTries ( ) const

protected

Definition at line 493 of file TrieRawHashMap.cpp.

References llvm::ThreadSafeTrieRawHashMapBase::ImplType::getRoot().

getRoot()

ThreadSafeTrieRawHashMapBase::PointerBase ThreadSafeTrieRawHashMapBase::getRoot ( ) const

protected

Definition at line 390 of file TrieRawHashMap.cpp.

References llvm::ThreadSafeTrieRawHashMapBase::ImplType::getRoot().

getStartBit()

unsigned ThreadSafeTrieRawHashMapBase::getStartBit ( ThreadSafeTrieRawHashMapBase::PointerBase  P ) const

protected

Definition at line 397 of file TrieRawHashMap.cpp.

References assert(), and P.

getTriePrefixAsString()

std::string ThreadSafeTrieRawHashMapBase::getTriePrefixAsString ( ThreadSafeTrieRawHashMapBase::PointerBase  P ) const

protected

Definition at line 432 of file TrieRawHashMap.cpp.

References assert(), Content, E, I, Index, llvm::Offset, P, and llvm::StringRef::take_front().

insert()

ThreadSafeTrieRawHashMapBase::PointerBase ThreadSafeTrieRawHashMapBase::insert ( PointerBase  Hint, ArrayRef< uint8_t >  Hash, function_ref< const uint8_t *(void *Mem, ArrayRef< uint8_t > Hash)>  Constructor  )

protected

Insert and return the stored content.

Definition at line 259 of file TrieRawHashMap.cpp.

References assert(), Content, llvm::ThreadSafeTrieRawHashMapBase::ImplType::ContentAlloc, llvm::ArrayRef< T >::empty(), llvm::ThreadSafeTrieRawHashMapBase::ImplType::getRoot(), Index, llvm_unreachable, and llvm::ArrayRef< T >::size().

Referenced by llvm::ThreadSafeTrieRawHashMap< T, NumHashBytes >::insertLazy().

operator delete()

void llvm::ThreadSafeTrieRawHashMapBase::operator delete ( void *  Ptr )

inline

Definition at line 91 of file TrieRawHashMap.h.

References Ptr.

operator new()

static void * llvm::ThreadSafeTrieRawHashMapBase::operator new ( size_t  Size )

inlinestatic

Definition at line 90 of file TrieRawHashMap.h.

References Size.

operator=() [1/2]

ThreadSafeTrieRawHashMapBase & llvm::ThreadSafeTrieRawHashMapBase::operator= ( const ThreadSafeTrieRawHashMapBase &  )

protecteddelete

operator=() [2/2]

ThreadSafeTrieRawHashMapBase & llvm::ThreadSafeTrieRawHashMapBase::operator= ( ThreadSafeTrieRawHashMapBase &&  RHS )

protecteddelete

print()

void llvm::ThreadSafeTrieRawHashMapBase::print

(

raw_ostream &

OS

)

const

Friends And Related Function Documentation

TrieRawHashMapTestHelper

friend class TrieRawHashMapTestHelper

friend

Definition at line 166 of file TrieRawHashMap.h.

Member Data Documentation

DefaultContentAllocAlign

template<class T >

constexpr size_t llvm::ThreadSafeTrieRawHashMapBase::DefaultContentAllocAlign = alignof(AllocValueType<T>)

staticconstexprprotected

Definition at line 83 of file TrieRawHashMap.h.

DefaultContentAllocSize

template<class T >

constexpr size_t llvm::ThreadSafeTrieRawHashMapBase::DefaultContentAllocSize = sizeof(AllocValueType<T>)

staticconstexprprotected

Definition at line 80 of file TrieRawHashMap.h.

DefaultContentOffset

template<class T >

constexpr size_t llvm::ThreadSafeTrieRawHashMapBase::DefaultContentOffset

staticconstexprprotected

Initial value:

=
      offsetof(AllocValueType<T>, Content)

Definition at line 86 of file TrieRawHashMap.h.

DefaultNumRootBits

constexpr size_t llvm::ThreadSafeTrieRawHashMapBase::DefaultNumRootBits = 6

staticconstexpr

Definition at line 69 of file TrieRawHashMap.h.

DefaultNumSubtrieBits

constexpr size_t llvm::ThreadSafeTrieRawHashMapBase::DefaultNumSubtrieBits = 4

staticconstexpr

Definition at line 70 of file TrieRawHashMap.h.

TrieContentBaseSize

constexpr size_t llvm::ThreadSafeTrieRawHashMapBase::TrieContentBaseSize = 4

staticconstexpr

Definition at line 68 of file TrieRawHashMap.h.

---

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

• include/llvm/ADT/TrieRawHashMap.h
• lib/Support/TrieRawHashMap.cpp