alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling > Struct Template Reference

Description:

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>
struct alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >

Base struct of HashTable providing internals.

Note

The separation of the internals of class HashTable to this type in namespace detail has no benefit on compilation speed or other positive "technical" effect, nor is it a matter of software design.
A user of derived class HashTable finds all interface methods and types in one place, which is not cluttered by the documentation of the internals found here. Otherwise, the separation is exclusively supporting source code organization.

See also

For a description of the template parameters and a general introduction to this module's hash table implementation, see the reference documentation of class HashTable.

Definition at line 124 of file hashtablebase.inl.

Inheritance diagram for alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >:

Collaboration diagram for alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >:

Inner Type Index:
class	TIterator
class	TLocalIterator

Public Type Index:
using	base
	Our base type.
using	Element = typename HTElementSelector<TValueDescriptor, THashCaching>::Type
	The type stored in the bucket of class HashTable.
using	FwdList = lang::SidiListHook<Element>
	Type of a single linked node list.
using	Node = lang::SidiNodeBase<Element>
	Type of a node in the List.
using	recyclerType
	Type of a single linked node list.
using	SharedRecyclerType
using	T = typename TValueDescriptor::StoredType
	Type definition publishing template parameter T.
using	TKey = typename TValueDescriptor::KeyType
	Type definition publishing template parameter TKey.
using	TMapped = typename TValueDescriptor::MappedType
	Type definition publishing template parameter TKey.

Public Static Method Index:
static size_t	getHashCode (Element *elem)
static constexpr bool	IsCachingHashes ()

Public Field Index:
float	baseLoadFactor
	The load factor that is set when the table is rehashed automatically.
uinteger	bucketCount
	The number of buckets managed by this tree.
FwdList *	buckets
	The list of buckets.
float	maxLoadFactor
	The maximum quotient of size and bucketCount that triggers a rehash.
integer	size
	The number of elements stored.
integer	sizeLimitToRehash
	Calculated once with rehash. Product of maxLoadFactor and bucketCount.

Public Method Index:
	HashTableBase (float pBaseLoadFactor, float pMaxLoadFactor)
	HashTableBase (TAllocator &pAllocator, float pBaseLoadFactor, float pMaxLoadFactor)
template<typename TSharedRecycler = SharedRecyclerType> requires (!std::same_as<TSharedRecycler , void>)
	HashTableBase (TSharedRecycler &pSharedRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)
	~HashTableBase ()
Element *	allocElement (const size_t hashCode)
bool	areEqual (Element *elem, const TKey &key, size_t keyHashCode) const
bool	areEqual (Element *lhs, Element *rhs) const
void	clear ()
	Destructs and removes all entries from this hash table.
Element *	findElement (uinteger bucketIdx, const TKey &key, size_t keyHashCode) const
Node *	findElementBefore (uinteger bucketIdx, size_t keyHashCode, const TKey &key) const
std::pair< TIterator< T >, TIterator< T > >	findRange (const TKey &key)
size_t	increaseSize (integer increase, const size_t hashCode=0)
std::pair< TIterator< T >, bool >	insertIfNotExists (const TKey &key, size_t hashCode)
uinteger	insertInBucket (Element *element, const size_t hashCode)
std::pair< TIterator< T >, bool >	insertOrGet (const TKey &key, size_t hashCode)
void	rehash (uinteger newMinBucketCount)
void	setMaxLoadFactor (float pMaxLoadFactor)

Type Definition Details:

base

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

using alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::base

Initial value:

 typename RecyclingSelector<TRecycling>:: template Type< TAllocator,
                                    typename HTElementSelector<TValueDescriptor, THashCaching>::Type >

Our base type.

Definition at line 129 of file hashtablebase.inl.

Element

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

using alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::Element = typename HTElementSelector<TValueDescriptor, THashCaching>::Type

The type stored in the bucket of class HashTable.

Definition at line 151 of file hashtablebase.inl.

FwdList

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

using alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::FwdList = lang::SidiListHook<Element>

Type of a single linked node list.

Definition at line 174 of file hashtablebase.inl.

Node

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

using alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::Node = lang::SidiNodeBase<Element>

Type of a node in the List.

Definition at line 177 of file hashtablebase.inl.

recyclerType

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

using alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::recyclerType

Initial value:

  typename RecyclingSelector<TRecycling>:: template Type< TAllocator,
                                             typename HTElementSelector<TValueDescriptor, THashCaching>::Type >

Type of a single linked node list.

Definition at line 159 of file hashtablebase.inl.

SharedRecyclerType

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

using alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::SharedRecyclerType

Initial value:

  typename detail::RecyclingSelector<TRecycling>
                    :: template HookType<TAllocator,
                                         typename HTElementSelector<TValueDescriptor, THashCaching>::Type>

This type definition may be used to define an externally managed shared recycler, which can be passed to the alternative constructor of this class when template parameter TRecycling equals Shared.

See also

Chapter 4.3 Shared Recycling of the Programmer's Manual for this ALib Module.

Definition at line 168 of file hashtablebase.inl.

T

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

using alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::T = typename TValueDescriptor::StoredType

Type definition publishing template parameter T.

Definition at line 133 of file hashtablebase.inl.

TKey

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

using alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::TKey = typename TValueDescriptor::KeyType

Type definition publishing template parameter TKey.

Definition at line 136 of file hashtablebase.inl.

TMapped

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

using alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::TMapped = typename TValueDescriptor::MappedType

Type definition publishing template parameter TKey.

Definition at line 139 of file hashtablebase.inl.

Field Details:

baseLoadFactor

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

float alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::baseLoadFactor

The load factor that is set when the table is rehashed automatically.

Definition at line 573 of file hashtablebase.inl.

bucketCount

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

uinteger alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::bucketCount

The number of buckets managed by this tree.

Definition at line 567 of file hashtablebase.inl.

buckets

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

FwdList* alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::buckets

The list of buckets.

Definition at line 570 of file hashtablebase.inl.

maxLoadFactor

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

float alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::maxLoadFactor

The maximum quotient of size and bucketCount that triggers a rehash.

Definition at line 576 of file hashtablebase.inl.

size

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

integer alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::size

The number of elements stored.

Definition at line 579 of file hashtablebase.inl.

sizeLimitToRehash

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

integer alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::sizeLimitToRehash

Calculated once with rehash. Product of maxLoadFactor and bucketCount.

Definition at line 582 of file hashtablebase.inl.

Constructor(s) / Destructor Details:

HashTableBase() [1/3]

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::HashTableBase ( TAllocator & pAllocator, float pBaseLoadFactor, float pMaxLoadFactor )

inline

Constructor.

Parameters

pAllocator	The allocator to use.
pBaseLoadFactor	The base load factor.
pMaxLoadFactor	The maximum load factor.

Definition at line 686 of file hashtablebase.inl.

HashTableBase() [2/3]

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::HashTableBase ( float pBaseLoadFactor, float pMaxLoadFactor )

inline

Constructor using HeapAllocator.

Parameters

pBaseLoadFactor	The base load factor.
pMaxLoadFactor	The maximum load factor.

Definition at line 705 of file hashtablebase.inl.

HashTableBase() [3/3]

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

template<typename TSharedRecycler = SharedRecyclerType>
requires (!std::same_as<TSharedRecycler , void>)

alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::HashTableBase ( TSharedRecycler & pSharedRecycler, float pBaseLoadFactor = 1.0, float pMaxLoadFactor = 2.0 )

inline

Constructor taking a shared recycler.

Parameters

pSharedRecycler	The shared recycler hook.
pBaseLoadFactor	The base load factor.
pMaxLoadFactor	The maximum load factor.

Template Parameters

TSharedRecycler

Used to select this constructor. Deduced by the compiler.

Definition at line 726 of file hashtablebase.inl.

~HashTableBase()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::~HashTableBase ( )

inline

Destructor. Destructs all elements in this object. Deletes recyclables, buckets and bucket array.

Definition at line 744 of file hashtablebase.inl.

Method Details:

allocElement()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

Element * alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::allocElement ( const size_t hashCode )

inline

Returns either a recycled or newly allocated element.

Parameters

hashCode

The hashCode of the new element. Used only in cached case.

Returns

A pointer to the element created or recycled.

Definition at line 198 of file hashtablebase.inl.

areEqual() [1/2]

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

bool alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::areEqual ( Element * elem, const TKey & key, size_t keyHashCode ) const

inline

Compares a key and a node. If cached mode, the hash codes are compared before the keys.

Parameters

elem	The element to compare.
key	The key to compare.
keyHashCode	The hash code of key.

Returns

The result of the comparison.

Definition at line 606 of file hashtablebase.inl.

Here is the call graph for this function:

areEqual() [2/2]

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

bool alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::areEqual ( Element * lhs, Element * rhs ) const

inline

Compares two elements. If cached mode, the hash code is compared before the keys.

Parameters

lhs	The first node to compare.
rhs	The second node to compare.

Returns

The result of the comparison.

Definition at line 593 of file hashtablebase.inl.

Here is the call graph for this function:

clear()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

void alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::clear ( )

inline

Destructs and removes all entries from this hash table.

Definition at line 768 of file hashtablebase.inl.

findElement()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

Element * alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::findElement ( uinteger bucketIdx, const TKey & key, size_t keyHashCode ) const

inline

Searches the first element equal to key in bucket bucketIdx.

Parameters

bucketIdx	The bucket number to search in (hash code divided by bucketCount).
key	The key-portion of the element to search.
keyHashCode	The hash code of key.

Returns

A pointer to the element searched, respectively nullptr if not found.

Definition at line 618 of file hashtablebase.inl.

Here is the call graph for this function:

findElementBefore()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

Node * alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::findElementBefore ( uinteger bucketIdx, size_t keyHashCode, const TKey & key ) const

inline

Searches the predecessor of the first element equal to key in bucket bucketIdx.

Parameters

bucketIdx	The bucket number to search in (hash code divided by bucketCount).
key	The key-portion of the element to search.
keyHashCode	The hash code of key.

Returns

A pointer to the element before the searched one, respectively nullptr if not found.

Definition at line 638 of file hashtablebase.inl.

Here is the call graph for this function:

findRange()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

std::pair< TIterator< T >, TIterator< T > > alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::findRange ( const TKey & key )

inline

Searches the first and last element stored according to given key. Returns a pare of iterators that define a range containing all elements with key key of the container.
Parameter resultStart is set to the first element of the matching range and parameter resultEnd is set to point past the last element of the range.

If no element with key key is found, both iterators are set to end.

Parameters

key	The key-portion of the elements to find.

Returns

A pair of iterators defining the range of elements with key key.

Definition at line 875 of file hashtablebase.inl.

Here is the call graph for this function:

getHashCode()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

size_t alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::getHashCode ( Element * elem )

inlinestatic

Either returns the cached hash code or calculates it.

Parameters

elem	The element to receive the hashcode for.

Returns

The hash code of the given element.

Definition at line 187 of file hashtablebase.inl.

increaseSize()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

size_t alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::increaseSize ( integer increase, const size_t hashCode = 0 )

inline

Increases field size and checks for a rehash.

Parameters

increase	The amount to increase.
hashCode	A hashCode that caller might want to have converted into a new actual bucket index.

Returns

The bucket index of hashCode.

Definition at line 671 of file hashtablebase.inl.

Here is the call graph for this function:

insertIfNotExists()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

std::pair< TIterator< T >, bool > alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::insertIfNotExists ( const TKey & key, size_t hashCode )

inline

Searches (a first) element with the given key. If not found, an invalid iterator to the bucket is returned with a nulled element pointer. Before this counter size is increased and, if a load limit is reached, a re-hash is performed.

If otherwise an element was found, its valid iterator is returned.

Note: Used by HashMap::EmplaceIfNotExistent.

Parameters

key	The key to the (first) element to find.
hashCode	The hash code of parameter key.

Returns

A pair of an iterator referring to the found or inserted element and a boolean that is true if the insertion took place and false nothing was changed.

Definition at line 911 of file hashtablebase.inl.

Here is the call graph for this function:

insertInBucket()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

uinteger alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::insertInBucket ( Element * element, const size_t hashCode )

inline

Inserts the given element into the bucket. If an element of the same key exists, then the element is put in front of that element. Otherwise it is added to the start of the bucket.

Parameters

element	The element to insert to its bucket.
hashCode	The hash code of parameter element.

Returns

The bucket number that the element was inserted to.

Definition at line 654 of file hashtablebase.inl.

Here is the call graph for this function:

insertOrGet()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

std::pair< TIterator< T >, bool > alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::insertOrGet ( const TKey & key, size_t hashCode )

inline

Inserts the topmost recyclable element if no element with the same key-portion of its value exists.

Parameters

key	Pointer to the key to search elements for deletion.
hashCode	The hash code of parameter key.

Returns

A pair containing an iterator referring to the element added. The bool component is true if the insertion took place and false if a new element was created.

Definition at line 935 of file hashtablebase.inl.

Here is the call graph for this function:

IsCachingHashes()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

constexpr bool alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::IsCachingHashes ( )

inlinestaticconstexpr

Determines whether hash codes are stored with the elements. It is done in case the given template parameter THashCashing equals Caching::Enabled or if it equals Caching::Auto and the key type is an arithmetic type.

Returns

true if hash codes are stored for reuse, false if not.

Definition at line 147 of file hashtablebase.inl.

rehash()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

void alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::rehash ( uinteger newMinBucketCount )

inline

Changes the number of buckets to be at least the higher value of a) the given newMinBucketCount, and
b) the quotient of the current size and the maximum load factor.

The result of the above, is increased to the next higher prime number. Rehash is only performed if bucket size increases. It never is decreased.

Parameters

newMinBucketCount

The minimum new bucket count requested.

Definition at line 807 of file hashtablebase.inl.

Here is the call graph for this function:

setMaxLoadFactor()

template<typename TAllocator, typename TValueDescriptor, typename THash, typename TEqual, lang::Caching THashCaching, Recycling TRecycling>

void alib::containers::detail::HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >::setMaxLoadFactor ( float pMaxLoadFactor )

inline

Changes the maximum load factor value and invokes rehash providing the actual bucket count as the minimum bucket count that is to be chosen.

Parameters

pMaxLoadFactor

The maximum load factor used to determine the need of re-hashing.

Definition at line 790 of file hashtablebase.inl.

Here is the call graph for this function:

---

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

• hashtablebase.inl