Generic linear hash table. More...

#include <tpl_linHash.H>

Inheritance diagram for Aleph::GenLinearHashTable< Key, BucketType, Cmp >:

Collaboration diagram for Aleph::GenLinearHashTable< Key, BucketType, Cmp >:

Classes
class	Iterator

Public Types
using	Hash_Fct = std::function< size_t(const Key &)>
	The hash function type.

using	Hash_Fct_Ptr = size_t(*)(const Key &)

using	Bucket = BucketType< Key >
	The bucket type.

using	Key_Type = Key

using	Item_Type = Key

Public Member Functions
void	set_hash_fct (Hash_Fct fct) noexcept
	Set the internal hash function.

void	set_hash_fct (Hash_Fct_Ptr fct) noexcept

Hash_Fct	get_hash_fct () const noexcept

Cmp &	get_compare () noexcept

const Cmp &	get_compare () const noexcept

float	current_alpha () const noexcept
	return the current table load

	GenLinearHashTable (size_t len=Primes::DefaultPrime, Hash_Fct_Ptr hash_fct=Aleph::dft_hash_ptr_fct< Key >, Cmp cmp=Cmp(), float lower_alpha=hash_default_lower_alpha, float upper_alpha=hash_default_upper_alpha, bool remove_all_buckets=true, bool with_resize=true)
	Instantiate a generic linear hash table.

void	swap (GenLinearHashTable &other) noexcept

void	empty () noexcept
	Empty the entire table.

void	clear () noexcept
	Empties the container.

bool	contains (const Key &key) const noexcept
	Checks if a key exists in the table.

	~GenLinearHashTable ()

Bucket *	search (const Key &key) const noexcept
	Search for key in the linear hash table.

const size_t &	size () const noexcept
	Returns the number of elements in the table.

bool	is_empty () const noexcept
	return true is table is empty

const size_t &	capacity () const noexcept
	Returns the table capacity.

const size_t &	busy_slots () const noexcept
	Returns the number of busy slots in the table.

const size_t &	expansions () const noexcept
	Returns the expansion level performed on the table.

Bucket *	insert (Bucket *bucket)
	Insert bucket in the table.

Bucket *	search_or_insert (Bucket *bucket)

size_t	resize (size_t) noexcept
	Provided for generic programming compatibility.

Bucket *	remove (Bucket *bucket) noexcept
	Remove bucket from table.

void	print ()

Public Member Functions inherited from HashStats< HashTbl >
Stats	stats () const
	Computes statistics about chain length distribution.

void	print_stats (const Stats &stats) const
	Prints statistics to standard output.

void	set_upper_alpha (float _upper_alpha)
	Sets the upper load factor threshold.

void	set_lower_alpha (float _lower_alpha)
	Sets the lower load factor threshold.

constexpr float	get_lower_alpha () const noexcept
	Returns the lower load factor threshold.

constexpr float	get_upper_alpha () const noexcept
	Returns the upper load factor threshold.

Protected Member Functions
	GenLinearHashTable (size_t __len, Hash_Fct __hash_fct, Cmp __cmp, float __lower_alpha, float __upper_alpha, bool __remove_all_buckets, bool)

Protected Attributes
Hash_Fct	hash_fct

Cmp	cmp

float	upper_alpha

float	lower_alpha

size_t	len

Private Types
using	BucketList = Dnode< Key >

using	BucketItor = typename Dnode< Key >::Iterator

Private Member Functions
size_t	call_hash_fct (const Key &key) const

void	expand ()

void	contract () noexcept

Bucket *	search_in_bucket_list (BucketList *list, const Key &key) const

Bucket *	remove_bucket (Bucket *bucket) noexcept

Static Private Member Functions
static size_t	multiply_by_two (size_t n) noexcept

static size_t	divide_by_two (size_t n) noexcept

Private Attributes
DynArray< BucketList >	table

Dlink	entries_list

size_t	M

size_t	N

size_t	busy_slots_counter

bool	remove_all_buckets

size_t	p

size_t	l

size_t	MP

size_t	MM

Friends
class	HashStats< GenLinearHashTable< Key, BucketType, Cmp > >

Detailed Description

template<typename Key, template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>
requires EqualityComparator<Cmp, Key>
class Aleph::GenLinearHashTable< Key, BucketType, Cmp >

Generic linear hash table.

Basically, a linear hash table is a hash table with collision resolution by separate chaining but with the difference that the table size increases dynamically to ensure that the load factor, typically called \(\alpha\), is bounded between two lower and upper values, respectively.

Internally, the table uses a dynamic array of type DynArray. This leads to memory savings for table entries that have not been written.

This type is generic and is not intended to be used directly. Instead, use LinearHashTable or LinearHashTableVtl depending on whether you want buckets without or with a virtual destructor.

Parameters

Key	the key type by which the table is indexed.
BucketType	the bucket type between LinHashBucket or LinHashBucketVtl.
Cmp	comparison class between keys.

See also: DynArray LinearHashTable LinearHashTableVtl

Definition at line 158 of file tpl_linHash.H.

Member Typedef Documentation

◆ Bucket

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

using Aleph::GenLinearHashTable< Key, BucketType, Cmp >::Bucket = BucketType<Key>

The bucket type.

Definition at line 171 of file tpl_linHash.H.

◆ BucketItor

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

using Aleph::GenLinearHashTable< Key, BucketType, Cmp >::BucketItor = typename Dnode<Key>::Iterator

private

Definition at line 181 of file tpl_linHash.H.

◆ BucketList

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

using Aleph::GenLinearHashTable< Key, BucketType, Cmp >::BucketList = Dnode<Key>

private

Definition at line 179 of file tpl_linHash.H.

◆ Hash_Fct

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

using Aleph::GenLinearHashTable< Key, BucketType, Cmp >::Hash_Fct = std::function<size_t(const Key &)>

The hash function type.

Must return pseudo-random positive values, between zero and the largest possible number.

Definition at line 167 of file tpl_linHash.H.

◆ Hash_Fct_Ptr

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

using Aleph::GenLinearHashTable< Key, BucketType, Cmp >::Hash_Fct_Ptr = size_t (*) (const Key &)

Definition at line 168 of file tpl_linHash.H.

◆ Item_Type

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

using Aleph::GenLinearHashTable< Key, BucketType, Cmp >::Item_Type = Key

Definition at line 175 of file tpl_linHash.H.

◆ Key_Type

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

using Aleph::GenLinearHashTable< Key, BucketType, Cmp >::Key_Type = Key

Definition at line 173 of file tpl_linHash.H.

Constructor & Destructor Documentation

◆ GenLinearHashTable() [1/2]

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Aleph::GenLinearHashTable< Key, BucketType, Cmp >::GenLinearHashTable	(	size_t	__len,
		Hash_Fct	__hash_fct,
		Cmp	__cmp,
		float	__lower_alpha,
		float	__upper_alpha,
		bool	__remove_all_buckets,
		bool
	)

inlineprotected

Definition at line 333 of file tpl_linHash.H.

References ah_domain_error_if, ah_length_error_if, Aleph::GenLinearHashTable< Key, BucketType, Cmp >::lower_alpha, Aleph::GenLinearHashTable< Key, BucketType, Cmp >::M, Aleph::GenLinearHashTable< Key, BucketType, Cmp >::MM, Aleph::GenLinearHashTable< Key, BucketType, Cmp >::table, and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::upper_alpha.

◆ GenLinearHashTable() [2/2]

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Aleph::GenLinearHashTable< Key, BucketType, Cmp >::GenLinearHashTable	(	size_t	len = `Primes::DefaultPrime`,
		Hash_Fct_Ptr	hash_fct = `Aleph::dft_hash_ptr_fct<Key>`,
		Cmp	cmp = `Cmp()`,
		float	lower_alpha = `hash_default_lower_alpha`,
		float	upper_alpha = `hash_default_upper_alpha`,
		bool	remove_all_buckets = `true`,
		bool	with_resize = `true`
	)

inline

Instantiate a generic linear hash table.

Instantiate a generic linear hash table of size len.

Parameters

[in]	len	initial and minimum table size.
[in]	hash_fct	hash function.
[in]	cmp	comparison functor for keys.
[in]	lower_alpha	lower threshold at which the table should contract.
[in]	upper_alpha	upper threshold at which the table should expand.
[in]	remove_all_buckets	if true, then the table's buckets are freed. Otherwise, they remain intact. By default the value is true.
[in]	with_resize	if true, the table will resize automatically based on load factors.

Exceptions

length_error	if `len` is equal or greater than the maximum dimension allowed for a dynamic array.
domain_error	if `upper_alpha` is less than or equal to `lower_alpha`.
bad_alloc	if there is not enough memory
overflow_error	if an overflow occurs from DynArray (caused by its internal calculations).

Definition at line 375 of file tpl_linHash.H.

◆ ~GenLinearHashTable()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Aleph::GenLinearHashTable< Key, BucketType, Cmp >::~GenLinearHashTable ( )

inline

Definition at line 439 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::remove_all_buckets.

Member Function Documentation

◆ busy_slots()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

const size_t & Aleph::GenLinearHashTable< Key, BucketType, Cmp >::busy_slots ( ) const

inlinenoexcept

Returns the number of busy slots in the table.

Definition at line 488 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::busy_slots_counter.

Referenced by print_stats(), TEST(), and TEST().

◆ call_hash_fct()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::call_hash_fct ( const Key & key ) const

inlineprivate

Definition at line 221 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::hash_fct, Aleph::GenLinearHashTable< Key, BucketType, Cmp >::M, Aleph::GenLinearHashTable< Key, BucketType, Cmp >::MM, and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::p.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::insert(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_or_insert().

◆ capacity()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

const size_t & Aleph::GenLinearHashTable< Key, BucketType, Cmp >::capacity ( ) const

inlinenoexcept

Returns the table capacity.

Definition at line 485 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::MP.

Referenced by print_stats(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ clear()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

void Aleph::GenLinearHashTable< Key, BucketType, Cmp >::clear ( )

inlinenoexcept

Empties the container.

Exceptions

none

See also: empty()

Definition at line 429 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty().

◆ contains()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

bool Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contains ( const Key & key ) const

inlinenoexcept

Checks if a key exists in the table.

Parameters

[in] key key to search for.

Returns: true if key is present, false otherwise.

Exceptions

none

Definition at line 437 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search().

◆ contract()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

void Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract ( )

inlineprivatenoexcept

Definition at line 276 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::remove_bucket().

◆ current_alpha()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

float Aleph::GenLinearHashTable< Key, BucketType, Cmp >::current_alpha ( ) const

inlinenoexcept

return the current table load

Definition at line 329 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::MP, and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::N.

Referenced by TEST().

◆ divide_by_two()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

static size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::divide_by_two ( size_t n )

inlinestaticprivatenoexcept

Definition at line 185 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract().

◆ empty()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

void Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty ( )

inlinenoexcept

Empty the entire table.

All buckets are freed and the size is adjusted to the initial one.

Definition at line 408 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::~GenLinearHashTable(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::clear(), and TEST().

◆ expand()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

void Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand ( )

inlineprivate

Definition at line 228 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::insert(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_or_insert().

◆ expansions()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

const size_t & Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expansions ( ) const

inlinenoexcept

Returns the expansion level performed on the table.

Definition at line 491 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::l.

Referenced by print_stats(), TEST(), TEST(), and TEST().

◆ get_compare() [1/2]

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

const Cmp & Aleph::GenLinearHashTable< Key, BucketType, Cmp >::get_compare ( ) const

inlinenoexcept

Definition at line 326 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::cmp.

◆ get_compare() [2/2]

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Cmp & Aleph::GenLinearHashTable< Key, BucketType, Cmp >::get_compare ( )

inlinenoexcept

Definition at line 324 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::cmp.

Referenced by TEST().

◆ get_hash_fct()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Hash_Fct Aleph::GenLinearHashTable< Key, BucketType, Cmp >::get_hash_fct ( ) const

inlinenoexcept

Definition at line 322 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::hash_fct.

Referenced by TEST().

◆ insert()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Bucket * Aleph::GenLinearHashTable< Key, BucketType, Cmp >::insert ( Bucket * bucket )

inline

Insert bucket in the table.

Return bucket if bucket->get_key() is not in the table, nullptr otherwise

Definition at line 495 of file tpl_linHash.H.

References Aleph::Dlink::append(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::busy_slots_counter, Aleph::GenLinearHashTable< Key, BucketType, Cmp >::call_hash_fct(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::entries_list, Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand(), Aleph::Dnode< T >::get_key(), Aleph::Dlink::is_empty(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::N, Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_in_bucket_list(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::table.

Referenced by main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ is_empty()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

bool Aleph::GenLinearHashTable< Key, BucketType, Cmp >::is_empty ( ) const

inlinenoexcept

return true is table is empty

Definition at line 482 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::N.

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().

◆ multiply_by_two()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

static size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::multiply_by_two ( size_t n )

inlinestaticprivatenoexcept

Definition at line 183 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand().

◆ print()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

void Aleph::GenLinearHashTable< Key, BucketType, Cmp >::print ( )

inline

Definition at line 569 of file tpl_linHash.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Dlink::is_empty(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::MP, and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::table.

Referenced by main().

◆ remove()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Bucket * Aleph::GenLinearHashTable< Key, BucketType, Cmp >::remove ( Bucket * bucket )

inlinenoexcept

Remove bucket from table.

Warning: it is not verified whether the bucket belongs to the table.

Definition at line 563 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::remove_bucket().

Referenced by main(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ remove_bucket()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Bucket * Aleph::GenLinearHashTable< Key, BucketType, Cmp >::remove_bucket ( Bucket * bucket )

inlineprivatenoexcept

Definition at line 541 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::busy_slots_counter, Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract(), Aleph::divide_and_conquer_partition_dp(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::N, Aleph::next(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search().

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::Iterator::del(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::remove().

◆ resize()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::resize ( size_t )

inlinenoexcept

Provided for generic programming compatibility.

Definition at line 533 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::MP.

Referenced by TEST().

◆ search()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Bucket * Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search ( const Key & key ) const

inlinenoexcept

Search for key in the linear hash table.

Returns a pointer to the bucket containing key if it is found in the table; nullptr otherwise.

Definition at line 465 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::call_hash_fct(), Aleph::Dlink::is_empty(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_in_bucket_list(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::table.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contains(), main(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::remove_bucket(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ search_in_bucket_list()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Bucket * Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_in_bucket_list	(	BucketList *	list,
		const Key &	key
	)		const

inlineprivate

Definition at line 448 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::cmp.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::insert(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_or_insert().

◆ search_or_insert()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Bucket * Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_or_insert ( Bucket * bucket )

inline

Definition at line 513 of file tpl_linHash.H.

Referenced by TEST(), and TEST().

◆ set_hash_fct() [1/2]

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

void Aleph::GenLinearHashTable< Key, BucketType, Cmp >::set_hash_fct ( Hash_Fct fct )

inlinenoexcept

Set the internal hash function.

Definition at line 312 of file tpl_linHash.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::hash_fct.

Referenced by TEST().

◆ set_hash_fct() [2/2]

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

void Aleph::GenLinearHashTable< Key, BucketType, Cmp >::set_hash_fct ( Hash_Fct_Ptr fct )

inlinenoexcept

Definition at line 317 of file tpl_linHash.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::hash_fct.

◆ size()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

const size_t & Aleph::GenLinearHashTable< Key, BucketType, Cmp >::size ( ) const

inlinenoexcept

Returns the number of elements in the table.

Definition at line 479 of file tpl_linHash.H.

References Aleph::GenLinearHashTable< Key, BucketType, Cmp >::N.

Referenced by main(), print_stats(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ swap()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

void Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap ( GenLinearHashTable< Key, BucketType, Cmp > & other )

inlinenoexcept

Definition at line 386 of file tpl_linHash.H.

Friends And Related Symbol Documentation

◆ HashStats< GenLinearHashTable< Key, BucketType, Cmp > >

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

friend class HashStats< GenLinearHashTable< Key, BucketType, Cmp > >

friend

Definition at line 127 of file tpl_linHash.H.

Member Data Documentation

◆ busy_slots_counter

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::busy_slots_counter

private

Definition at line 199 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::busy_slots(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::insert(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::remove_bucket(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_or_insert(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ cmp

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Cmp Aleph::GenLinearHashTable< Key, BucketType, Cmp >::cmp

protected

Definition at line 193 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::get_compare(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::get_compare(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_in_bucket_list(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ entries_list

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Dlink Aleph::GenLinearHashTable< Key, BucketType, Cmp >::entries_list

private

Definition at line 188 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::insert(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_or_insert(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ hash_fct

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Hash_Fct Aleph::GenLinearHashTable< Key, BucketType, Cmp >::hash_fct

protected

Definition at line 192 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::call_hash_fct(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::get_hash_fct(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::set_hash_fct(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::set_hash_fct(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ l

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::l

private

Definition at line 211 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expansions(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ len

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::len

mutableprotected

Definition at line 217 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ lower_alpha

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

float Aleph::GenLinearHashTable< Key, BucketType, Cmp >::lower_alpha

protected

Definition at line 206 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::GenLinearHashTable(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ M

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::M

private

Definition at line 197 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::GenLinearHashTable(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::call_hash_fct(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ MM

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::MM

private

Definition at line 213 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::GenLinearHashTable(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::call_hash_fct(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ MP

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::MP

private

Definition at line 212 of file tpl_linHash.H.

◆ N

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::N

private

Definition at line 198 of file tpl_linHash.H.

◆ p

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

size_t Aleph::GenLinearHashTable< Key, BucketType, Cmp >::p

private

Definition at line 210 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::call_hash_fct(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_or_insert(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ remove_all_buckets

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

bool Aleph::GenLinearHashTable< Key, BucketType, Cmp >::remove_all_buckets

private

Definition at line 200 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::~GenLinearHashTable(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ table

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

DynArray<BucketList> Aleph::GenLinearHashTable< Key, BucketType, Cmp >::table

private

Definition at line 187 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::GenLinearHashTable(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::insert(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::print(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_or_insert(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

◆ upper_alpha

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

float Aleph::GenLinearHashTable< Key, BucketType, Cmp >::upper_alpha

protected

Definition at line 205 of file tpl_linHash.H.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::GenLinearHashTable(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand(), and Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap().

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

tpl_linHash.H

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Bucket

◆ BucketItor

◆ BucketList

◆ Hash_Fct

◆ Hash_Fct_Ptr

◆ Item_Type

◆ Key_Type

Constructor & Destructor Documentation

◆ GenLinearHashTable() [1/2]

◆ GenLinearHashTable() [2/2]

◆ ~GenLinearHashTable()

Member Function Documentation

◆ busy_slots()

◆ call_hash_fct()

◆ capacity()

◆ clear()

◆ contains()

◆ contract()

◆ current_alpha()

◆ divide_by_two()

◆ empty()

◆ expand()

◆ expansions()

◆ get_compare() [1/2]

◆ get_compare() [2/2]

◆ get_hash_fct()

◆ insert()

◆ is_empty()

◆ multiply_by_two()

◆ print()

◆ remove()

◆ remove_bucket()

◆ resize()

◆ search()

◆ search_in_bucket_list()

◆ search_or_insert()

◆ set_hash_fct() [1/2]

◆ set_hash_fct() [2/2]

◆ size()

◆ swap()

Friends And Related Symbol Documentation

◆ HashStats< GenLinearHashTable< Key, BucketType, Cmp > >

Member Data Documentation

◆ busy_slots_counter

◆ cmp

◆ entries_list

◆ hash_fct

◆ l

◆ len

◆ lower_alpha

◆ M

◆ MM

◆ MP

◆ N

◆ p

◆ remove_all_buckets

◆ table

◆ upper_alpha