uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType > Class Template Reference

#include <HashTable.h>

Classes
class	Iterator
struct	SEntry

Public Member Functions
	THashTable (AllocatorArgsType &&... AllocatorArgs)
	THashTable (const THashTable &Other)=delete
	THashTable (THashTable &&Other)
THashTable &	operator= (THashTable Other)
void	Swap (THashTable &Other)
	~THashTable ()
ULANG_FORCEINLINE uint32_t	Num () const
ULANG_FORCEINLINE bool	Contains (const KeyType &Key) const
ULANG_FORCEINLINE KeyValueType *	Find (const KeyType &Key)
ULANG_FORCEINLINE const KeyValueType *	Find (const KeyType &Key) const
template<typename Predicate >
const KeyValueType *	FindByPredicate (Predicate Pred) const
template<typename Predicate >
KeyValueType *	FindByPredicate (Predicate Pred)
KeyValueType &	Insert (const KeyValueType &KeyValue)
KeyValueType &	Insert (KeyValueType &&KeyValue)
KeyValueType &	FindOrInsert (KeyValueType &&KeyValue)
bool	Remove (const KeyType &Key)
bool	IsEmpty () const
void	Empty ()
ULANG_FORCEINLINE Iterator< false >	begin ()
ULANG_FORCEINLINE Iterator< false >	end ()
ULANG_FORCEINLINE Iterator< true >	begin () const
ULANG_FORCEINLINE Iterator< false >	end () const
ULANG_FORCEINLINE Iterator< true >	cbegin () const
ULANG_FORCEINLINE Iterator< true >	cend () const

Protected Member Functions
ULANG_FORCEINLINE uint32_t	DesiredPos (uint32_t Hash) const
ULANG_FORCEINLINE uint32_t	ProbeDistance (uint32_t Hash, uint32_t Pos) const
KeyValueType &	InsertInternal (KeyValueType &&KeyValue)
uint32_t	InsertInternal (uint32_t Hash, KeyValueType &&Value, bool *bAlreadyExists)
ULANG_FORCEINLINE uint32_t	Lookup (const KeyType &Key) const
void	Allocate ()
void	Grow ()

Static Protected Member Functions
static ULANG_FORCEINLINE uint32_t	ComputeNonZeroHash (const KeyType &Key)

Protected Attributes
SEntry *	_Entries {}
uint32_t	_NumEntries {}
uint32_t	_NumOccupied {}
AllocatorType	_Allocator

Static Protected Attributes
static constexpr uint64_t	MaxLoadFactorNumerator = 7
static constexpr uint64_t	MaxLoadFactorDenominator = 8

Detailed Description

template<class KeyType, class KeyValueType, class HashTraits, class AllocatorType, typename... AllocatorArgsType>
class uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >

A Robin-Hood hash table Inspired by https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/ and http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/

Constructor & Destructor Documentation

THashTable() [1/3]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::THashTable ( AllocatorArgsType &&...  AllocatorArgs )

inline

THashTable() [2/3]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::THashTable ( const THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType > &  Other )

delete

THashTable() [3/3]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::THashTable ( THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType > &&  Other )

inline

~THashTable()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::~THashTable ( )

inline

Member Function Documentation

Allocate()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

void uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Allocate ( )

inlineprotected

begin() [1/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE Iterator< false > uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::begin ( )

inline

begin() [2/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE Iterator< true > uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::begin ( ) const

inline

cbegin()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE Iterator< true > uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::cbegin ( ) const

inline

cend()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE Iterator< true > uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::cend ( ) const

inline

ComputeNonZeroHash()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

static ULANG_FORCEINLINE uint32_t uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::ComputeNonZeroHash ( const KeyType &  Key )

inlinestaticprotected

Contains()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE bool uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Contains ( const KeyType &  Key ) const

inline

DesiredPos()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE uint32_t uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::DesiredPos ( uint32_t  Hash ) const

inlineprotected

Empty()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

void uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Empty ( )

inline

end() [1/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE Iterator< false > uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::end ( )

inline

end() [2/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE Iterator< false > uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::end ( ) const

inline

Find() [1/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE KeyValueType * uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Find ( const KeyType &  Key )

inline

Find() [2/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE const KeyValueType * uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Find ( const KeyType &  Key ) const

inline

FindByPredicate() [1/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

template<typename Predicate >

KeyValueType * uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::FindByPredicate ( Predicate  Pred )

inline

Finds a key-value pair which matches a predicate functor. The predicate must take a TKeyValuePair<KeyType, ValueType>.

Parameters

Pred	The functor to apply to each key-value pair. true, or nullptr if none is found.

Returns

Pointer to the first key-value pair for which the predicate returns true, or nullptr if none is found.

See also

FilterByPredicate, ContainsByPredicate

FindByPredicate() [2/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

template<typename Predicate >

const KeyValueType * uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::FindByPredicate ( Predicate  Pred ) const

inline

Finds an key-value pair which matches a predicate functor. The predicate must take a TKeyValuePair<KeyType, ValueType>.

Parameters

Pred	The functor to apply to each key-value pair.

Returns

Pointer to the first key-value pair for which the predicate returns true, or nullptr if none is found.

See also

FilterByPredicate, ContainsByPredicate

FindOrInsert()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

KeyValueType & uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::FindOrInsert ( KeyValueType &&  KeyValue )

inline

Grow()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

void uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Grow ( )

inlineprotected

Insert() [1/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

KeyValueType & uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Insert ( const KeyValueType &  KeyValue )

inline

Insert() [2/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

KeyValueType & uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Insert ( KeyValueType &&  KeyValue )

inline

InsertInternal() [1/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

KeyValueType & uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::InsertInternal ( KeyValueType &&  KeyValue )

inlineprotected

InsertInternal() [2/2]

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

uint32_t uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::InsertInternal ( uint32_t  Hash, KeyValueType &&  Value, bool *  bAlreadyExists  )

inlineprotected

IsEmpty()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

bool uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::IsEmpty ( ) const

inline

Lookup()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE uint32_t uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Lookup ( const KeyType &  Key ) const

inlineprotected

Num()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE uint32_t uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Num ( ) const

inline

operator=()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

THashTable & uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::operator= ( THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >  Other )

inline

ProbeDistance()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

ULANG_FORCEINLINE uint32_t uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::ProbeDistance ( uint32_t  Hash, uint32_t  Pos  ) const

inlineprotected

Remove()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

bool uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Remove ( const KeyType &  Key )

inline

Swap()

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

void uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::Swap ( THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType > &  Other )

inline

Member Data Documentation

_Allocator

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

AllocatorType uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::_Allocator

protected

How to allocate the memory This allocator can be 0 in size

_Entries

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

SEntry* uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::_Entries {}

protected

_NumEntries

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

uint32_t uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::_NumEntries {}

protected

_NumOccupied

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

uint32_t uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::_NumOccupied {}

protected

MaxLoadFactorDenominator

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

constexpr uint64_t uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::MaxLoadFactorDenominator = 8

staticconstexprprotected

MaxLoadFactorNumerator

template<class KeyType , class KeyValueType , class HashTraits , class AllocatorType , typename... AllocatorArgsType>

constexpr uint64_t uLang::THashTable< KeyType, KeyValueType, HashTraits, AllocatorType, AllocatorArgsType >::MaxLoadFactorNumerator = 7

staticconstexprprotected

---

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

• Engine/Source/Runtime/Solaris/uLangCore/Public/uLang/Common/Containers/HashTable.h