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
LLVM_ABI 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
LLVM_ABI PointerBase	find (ArrayRef< uint8_t > Hash) const
	Find the stored content with hash.
LLVM_ABI 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
LLVM_ABI	ThreadSafeTrieRawHashMapBase (size_t ContentAllocSize, size_t ContentAllocAlign, size_t ContentOffset, std::optional< size_t > NumRootBits=std::nullopt, std::optional< size_t > NumSubtrieBits=std::nullopt)
LLVM_ABI	~ThreadSafeTrieRawHashMapBase ()
	Destructor, which asserts if there's anything to do.
LLVM_ABI void	destroyImpl (function_ref< void(void *ValueMem)> Destructor)
LLVM_ABI	ThreadSafeTrieRawHashMapBase (ThreadSafeTrieRawHashMapBase &&RHS)
ThreadSafeTrieRawHashMapBase &	operator= (ThreadSafeTrieRawHashMapBase &&RHS)=delete
	ThreadSafeTrieRawHashMapBase (const ThreadSafeTrieRawHashMapBase &)=delete
ThreadSafeTrieRawHashMapBase &	operator= (const ThreadSafeTrieRawHashMapBase &)=delete
LLVM_ABI PointerBase	getRoot () const
LLVM_ABI unsigned	getStartBit (PointerBase P) const
LLVM_ABI unsigned	getNumBits (PointerBase P) const
LLVM_ABI unsigned	getNumSlotUsed (PointerBase P) const
LLVM_ABI std::string	getTriePrefixAsString (PointerBase P) const
LLVM_ABI unsigned	getNumTries () const
LLVM_ABI 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 67 of file TrieRawHashMap.h.

Constructor & Destructor Documentation

◆ ThreadSafeTrieRawHashMapBase() [1/4]

llvm::ThreadSafeTrieRawHashMapBase::ThreadSafeTrieRawHashMapBase ( )

protecteddelete

References LLVM_ABI, RHS, and ThreadSafeTrieRawHashMapBase().

Referenced by operator=(), operator=(), llvm::ThreadSafeTrieRawHashMap< DataT, sizeof(HashType)>::ThreadSafeTrieRawHashMap(), ThreadSafeTrieRawHashMapBase(), ThreadSafeTrieRawHashMapBase(), ThreadSafeTrieRawHashMapBase(), and llvm::ThreadSafeTrieRawHashMapBase::ImplType::TrailingObjects.

◆ 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(), DefaultNumRootBits, and DefaultNumSubtrieBits.

◆ ~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 ThreadSafeTrieRawHashMapBase().

◆ ThreadSafeTrieRawHashMapBase() [4/4]

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

protecteddelete

References ThreadSafeTrieRawHashMapBase().

Member Function Documentation

◆ destroyImpl()

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

protected

Definition at line 362 of file TrieRawHashMap.cpp.

References llvm::dyn_cast_or_null(), I, and llvm::Next.

Referenced by llvm::ThreadSafeTrieRawHashMap< DataT, sizeof(HashType)>::~ThreadSafeTrieRawHashMap().

◆ dump()

LLVM_DUMP_METHOD void llvm::ThreadSafeTrieRawHashMapBase::dump ( ) const

References LLVM_DUMP_METHOD.

◆ 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::cast(), llvm::dyn_cast(), llvm::ArrayRef< T >::empty(), llvm::TrieHashIndexGenerator::end(), llvm_unreachable, llvm::TrieHashIndexGenerator::next(), and llvm::TrieHashIndexGenerator::StartBit.

Referenced by llvm::ThreadSafeTrieRawHashMap< DataT, sizeof(HashType)>::find(), and llvm::ThreadSafeTrieRawHashMap< DataT, sizeof(HashType)>::find().

◆ getNextTrie()

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

protected

Definition at line 504 of file TrieRawHashMap.cpp.

References assert(), llvm::dyn_cast(), and P.

◆ getNumBits()

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

protected

Definition at line 407 of file TrieRawHashMap.cpp.

References assert(), llvm::dyn_cast(), and P.

◆ getNumSlotUsed()

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

protected

Definition at line 417 of file TrieRawHashMap.cpp.

References assert(), llvm::dyn_cast(), I, and P.

◆ getNumTries()

unsigned ThreadSafeTrieRawHashMapBase::getNumTries ( ) const

protected

Definition at line 493 of file TrieRawHashMap.cpp.

◆ getRoot()

ThreadSafeTrieRawHashMapBase::PointerBase ThreadSafeTrieRawHashMapBase::getRoot ( ) const

protected

Definition at line 390 of file TrieRawHashMap.cpp.

◆ getStartBit()

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

protected

Definition at line 397 of file TrieRawHashMap.cpp.

References assert(), llvm::dyn_cast(), and P.

◆ getTriePrefixAsString()

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

protected

Definition at line 432 of file TrieRawHashMap.cpp.

References assert(), llvm::dyn_cast(), I, llvm::Next, llvm::Offset, P, llvm::Sub, llvm::StringRef::take_front(), llvm::toHex(), and llvm::toStringRef().

◆ 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(), llvm::cast(), llvm::dyn_cast(), llvm::ArrayRef< T >::empty(), llvm::TrieHashIndexGenerator::end(), llvm::TrieHashIndexGenerator::getCollidingBits(), llvm::TrieHashIndexGenerator::getNumBits(), llvm::TrieHashIndexGenerator::hint(), llvm_unreachable, llvm::TrieHashIndexGenerator::next(), and llvm::ArrayRef< T >::size().

Referenced by llvm::ThreadSafeTrieRawHashMap< DataT, sizeof(HashType)>::insertLazy().

◆ operator delete()

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

inline

Definition at line 92 of file TrieRawHashMap.h.

References Ptr.

◆ operator new()

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

inlinestatic

Definition at line 91 of file TrieRawHashMap.h.

References Size.

◆ operator=() [1/2]

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

protecteddelete

References LLVM_ABI, P, and ThreadSafeTrieRawHashMapBase().

◆ operator=() [2/2]

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

protecteddelete

References RHS, and ThreadSafeTrieRawHashMapBase().

◆ print()

LLVM_ABI void llvm::ThreadSafeTrieRawHashMapBase::print ( raw_ostream & OS ) const

References LLVM_ABI.

◆ TrieRawHashMapTestHelper

friend class TrieRawHashMapTestHelper

friend

Definition at line 170 of file TrieRawHashMap.h.

References TrieRawHashMapTestHelper.

Referenced by TrieRawHashMapTestHelper.

Member Data Documentation

◆ DefaultContentAllocAlign

template<class T>

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

staticconstexprprotected

Definition at line 84 of file TrieRawHashMap.h.

Referenced by llvm::ThreadSafeTrieRawHashMap< DataT, sizeof(HashType)>::ThreadSafeTrieRawHashMap().

◆ DefaultContentAllocSize

template<class T>

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

staticconstexprprotected

Definition at line 81 of file TrieRawHashMap.h.

Referenced by llvm::ThreadSafeTrieRawHashMap< DataT, sizeof(HashType)>::ThreadSafeTrieRawHashMap().

◆ DefaultContentOffset

template<class T>

size_t llvm::ThreadSafeTrieRawHashMapBase::DefaultContentOffset

staticconstexprprotected

Initial value:

=

offsetof(AllocValueType<T>, Content)

offsetof

#define offsetof(TYPE, MEMBER)

Definition at line 87 of file TrieRawHashMap.h.

Referenced by llvm::ThreadSafeTrieRawHashMap< DataT, sizeof(HashType)>::ThreadSafeTrieRawHashMap().

◆ DefaultNumRootBits

size_t llvm::ThreadSafeTrieRawHashMapBase::DefaultNumRootBits = 6

staticconstexpr

Definition at line 70 of file TrieRawHashMap.h.

Referenced by ThreadSafeTrieRawHashMapBase().

◆ DefaultNumSubtrieBits

size_t llvm::ThreadSafeTrieRawHashMapBase::DefaultNumSubtrieBits = 4

staticconstexpr

Definition at line 71 of file TrieRawHashMap.h.

Referenced by ThreadSafeTrieRawHashMapBase().

◆ TrieContentBaseSize

size_t llvm::ThreadSafeTrieRawHashMapBase::TrieContentBaseSize = 4

staticconstexpr

Definition at line 69 of file TrieRawHashMap.h.

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

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

Classes

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Static Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ ThreadSafeTrieRawHashMapBase() [1/4]

◆ ThreadSafeTrieRawHashMapBase() [2/4]

◆ ~ThreadSafeTrieRawHashMapBase()

◆ ThreadSafeTrieRawHashMapBase() [3/4]

◆ ThreadSafeTrieRawHashMapBase() [4/4]

Member Function Documentation

◆ destroyImpl()

◆ dump()

◆ find()

◆ getNextTrie()

◆ getNumBits()

◆ getNumSlotUsed()

◆ getNumTries()

◆ getRoot()

◆ getStartBit()

◆ getTriePrefixAsString()

◆ insert()

◆ operator delete()

◆ operator new()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ print()

Friends And Related Symbol Documentation

◆ TrieRawHashMapTestHelper

Member Data Documentation

◆ DefaultContentAllocAlign

◆ DefaultContentAllocSize

◆ DefaultContentOffset

◆ DefaultNumRootBits

◆ DefaultNumSubtrieBits

◆ TrieContentBaseSize