Description:

template<typename T, typename TStored, typename TKey, typename TIfMapped, typename THash, typename TEqual, typename TAccess, lang::Caching THashCaching, typename TRecycling>
struct alib::monomem::detail::HashTableBase< T, TStored, TKey, TIfMapped, THash, TEqual, TAccess, 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.

Template Parameters

T	See reference documentation of class HashTable.
TStored	See reference documentation of class HashTable.
TKey	See reference documentation of class HashTable.
TIfMapped	See reference documentation of class HashTable.
THash	See reference documentation of class HashTable.
TEqual	See reference documentation of class HashTable.
TAccess	See reference documentation of class HashTable.
THashCaching	See reference documentation of class HashTable.
TRecycling	See reference documentation of class HashTable.

Definition at line 245 of file hashtablebase.inl.

Inheritance diagram for HashTableBase< T, TStored, TKey, TIfMapped, THash, TEqual, TAccess, THashCaching, TRecycling >:

[legend]

Collaboration diagram for HashTableBase< T, TStored, TKey, TIfMapped, THash, TEqual, TAccess, THashCaching, TRecycling >:

[legend]

Inner Type Index:
struct	NO_MAPPING

class	TIterator

class	TLocalIterator

Public Type Index:
using	Element = typename HashTableElementType<T,TStored,TKey,THashCaching>::type

using	List = lang::SidiListHelper<Element>

using	Node = lang::SidiNodeBase<Element>

using	TMapped = ATMP_IF_T_F( ATMP_EQ(TIfMapped, void), NO_MAPPING, TIfMapped )

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

static TKey &	keyPortion (Element *element)

static TMapped &	mappedPortion (Element *element)

Public Field Index:
MonoAllocator *	allocator

float	baseLoadFactor

uinteger	bucketCount

List *	buckets

float	maxLoadFactor

HashTableRecycler< T, TStored, TKey, THashCaching, TRecycling >::type	recycler

integer	size

integer	sizeLimitToRehash

Public Method Index:
	HashTableBase (MonoAllocator *pAllocator, float pBaseLoadFactor, float pMaxLoadFactor)

	HashTableBase (MonoAllocator *pAllocator, List &pRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)

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 ()

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	reset ()

void	setMaxLoadFactor (float pMaxLoadFactor)

Type Definition Details:

◆ Element

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

using Element = typename HashTableElementType<T,TStored,TKey,THashCaching>::type

The type stored in bucket List.

Definition at line 266 of file hashtablebase.inl.

◆ List

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

using List = lang::SidiListHelper<Element>

Type of a single linked node list.

Definition at line 269 of file hashtablebase.inl.

◆ Node

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

using Node = lang::SidiNodeBase<Element>

Type of a node in the List.

Definition at line 272 of file hashtablebase.inl.

◆ TMapped

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

using TMapped = ATMP_IF_T_F( ATMP_EQ(TIfMapped, void), NO_MAPPING, TIfMapped )

Equals template parameter TIfMapped in case this is not void, and helper struct NO_MAPPING if it is.

Definition at line 263 of file hashtablebase.inl.

Field Details:

◆ allocator

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

MonoAllocator* allocator

The allocator assigned.

Definition at line 713 of file hashtablebase.inl.

◆ baseLoadFactor

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

float baseLoadFactor

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

Definition at line 722 of file hashtablebase.inl.

◆ bucketCount

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

uinteger bucketCount

The number of buckets managed by this tree.

Definition at line 716 of file hashtablebase.inl.

◆ buckets

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

List* buckets

The list of buckets.

Definition at line 719 of file hashtablebase.inl.

◆ maxLoadFactor

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

float maxLoadFactor

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

Definition at line 725 of file hashtablebase.inl.

◆ recycler

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

HashTableRecycler<T,TStored,TKey,THashCaching,TRecycling>::type recycler

The recycler. Its type depends on template parameter TRecycling .

Definition at line 259 of file hashtablebase.inl.

◆ size

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

integer size

The number of elements stored.

Definition at line 728 of file hashtablebase.inl.

◆ sizeLimitToRehash

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

integer sizeLimitToRehash

Calculated once with rehash. Product of maxLoadFactor and bucketCount.

Definition at line 731 of file hashtablebase.inl.

Constructor(s) / Destructor Details::

◆ HashTableBase() [1/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

HashTableBase	(	MonoAllocator *	pAllocator,
		float	pBaseLoadFactor,
		float	pMaxLoadFactor )

inline

Constructor.

Parameters

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

Definition at line 740 of file hashtablebase.inl.

◆ HashTableBase() [2/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

HashTableBase	(	MonoAllocator *	pAllocator,
		List &	pRecycler,
		float	pBaseLoadFactor = 1.0,
		float	pMaxLoadFactor = 2.0 )

inline

Constructor taking a shared recycler.

Parameters

pAllocator	The monotonic allocator to use.
pRecycler	The shared recycler.
pBaseLoadFactor	The base load factor.
pMaxLoadFactor	The maximum load factor.

Definition at line 761 of file hashtablebase.inl.

Method Details:

◆ allocElement()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

Element * 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 309 of file hashtablebase.inl.

Here is the call graph for this function:

◆ areEqual() [1/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

bool 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 prior to 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 803 of file hashtablebase.inl.

Here is the call graph for this function:

◆ areEqual() [2/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

bool areEqual	(	Element *	lhs,
		Element *	rhs ) const

inline

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

Parameters

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

Returns: The result of the comparison.

Definition at line 789 of file hashtablebase.inl.

Here is the call graph for this function:

◆ clear()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

void clear ( )

inline

Destructs and removes all entries from this hash table.

Definition at line 898 of file hashtablebase.inl.

Here is the call graph for this function:

◆ findElement()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

Element * 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 817 of file hashtablebase.inl.

Here is the call graph for this function:

◆ findElementBefore()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

Node * 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 841 of file hashtablebase.inl.

Here is the call graph for this function:

◆ findRange()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

std::pair< TIterator< T >, TIterator< T > > 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 1036 of file hashtablebase.inl.

Here is the call graph for this function:

◆ getHashCode()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

static size_t 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 298 of file hashtablebase.inl.

Here is the call graph for this function:

◆ increaseSize()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

size_t 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 882 of file hashtablebase.inl.

Here is the call graph for this function:

◆ insertIfNotExists()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

std::pair< TIterator< T >, bool > 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. Prior to 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 1072 of file hashtablebase.inl.

Here is the call graph for this function:

◆ insertInBucket()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

uinteger 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 861 of file hashtablebase.inl.

Here is the call graph for this function:

◆ insertOrGet()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

std::pair< TIterator< T >, bool > 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 1098 of file hashtablebase.inl.

Here is the call graph for this function:

◆ keyPortion()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

static TKey & keyPortion ( Element * element )

inlinestatic

Return the key-portion of a given element.

Parameters

element The element to receive the value from.

Returns: The key value of the element.

Definition at line 282 of file hashtablebase.inl.

◆ mappedPortion()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

static TMapped & mappedPortion ( Element * element )

inlinestatic

Return the mapped-portion of a given element.

Parameters

element The element to receive the value from.

Returns: The key value of the element.

Definition at line 290 of file hashtablebase.inl.

◆ rehash()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

void 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 963 of file hashtablebase.inl.

Here is the call graph for this function:

◆ reset()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

void reset ( )

inline

Resets this object. Invokes clear to destruct all keys and values and disposes all allocated internal management data.

Definition at line 931 of file hashtablebase.inl.

Here is the call graph for this function:

◆ setMaxLoadFactor()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching, typename TRecycling >

void 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 946 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

Description:

Inner Type Index:

Public Type Index:

Public Static Method Index:

Public Field Index:

Public Method Index:

Type Definition Details:

◆ Element

◆ List

◆ Node

◆ TMapped

Field Details:

◆ allocator

◆ baseLoadFactor

◆ bucketCount

◆ buckets

◆ maxLoadFactor

◆ recycler

◆ size

◆ sizeLimitToRehash

Constructor(s) / Destructor Details::

◆ HashTableBase() [1/2]

◆ HashTableBase() [2/2]

Method Details:

◆ allocElement()

◆ areEqual() [1/2]

◆ areEqual() [2/2]

◆ clear()

◆ findElement()

◆ findElementBefore()

◆ findRange()

◆ getHashCode()

◆ increaseSize()

◆ insertIfNotExists()

◆ insertInBucket()

◆ insertOrGet()

◆ keyPortion()

◆ mappedPortion()

◆ rehash()

◆ reset()

◆ setMaxLoadFactor()