Open addressing hash table with double hashing collision resolution. More...

#include <tpl_odhash.H>

Inheritance diagram for Aleph::ODhashTable< Key, Cmp >:

Collaboration diagram for Aleph::ODhashTable< Key, Cmp >:

Classes
struct	Bucket

Public Types
enum	Status { EMPTY , BUSY , DELETED }

enum	Probe { NO_PROBED , FIRST_PROBE , SECOND_PROBE , LINEAR_PROBE }

using	Key_Type = Key

using	Item_Type = Key

using	Hash_Fct = std::function< size_t(const Key &)>

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

using	Stats = typename OhashCommon< ODhashTable< Key, Cmp >, Key >::Stats

Public Types inherited from StlAlephIterator< SetName >
using	iterator = StlIterator< SetName >

using	const_iterator = StlConstIterator< SetName >

Public Member Functions
constexpr const Cmp &	get_compare () const noexcept

constexpr Cmp &	get_compare () noexcept

void	swap (ODhashTable &other) noexcept

	ODhashTable (size_t len=Primes::DefaultPrime, Hash_Fct_Ptr first_hash_fct=Aleph::dft_hash_fct< Key >, Hash_Fct_Ptr second_hash_fct=Aleph::snd_hash_fct< Key >, Cmp cmp=Cmp(), float lower_alpha=hash_default_lower_alpha, float upper_alpha=hash_default_upper_alpha, bool with_resize=true)
	Instantiate a closed hash table with collision resolution by double hashing.

	~ODhashTable ()
	Free the whole hash table.

	ODhashTable (const ODhashTable &other)

	ODhashTable (ODhashTable &&other) noexcept

template<template< typename > class List>
	ODhashTable (const List< Key > &l)

template<class It >
	ODhashTable (It b, It e)

	ODhashTable (std::initializer_list< Key > l)

ODhashTable &	operator= (const ODhashTable &other)

ODhashTable &	operator= (ODhashTable &&other) noexcept

Hash_Fct	get_hash_fct () const noexcept

void	set_hash_fct (Hash_Fct fct) noexcept

void	set_hash_fct (Hash_Fct_Ptr fct) noexcept

Key *	search (const Key &key) const noexcept
	searches the table for the key.

constexpr Hash_Fct	get_second_hash_fct () const noexcept

void	set_second_hash_fct (Hash_Fct fct) noexcept

void	set_second_hash_fct (Hash_Fct_Ptr fct) noexcept

void	remove (const Key &key)
	Remove a key from the hash table.

Stats	stats () const

Public Member Functions inherited from OhashCommon< HashTbl, Key >
constexpr float	get_lower_alpha () const noexcept
	Returns the lower load factor threshold for automatic shrinking.

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

void	copy_from_table (const HashTbl &other)
	Copies all entries from another hash table.

void	clean_table ()
	Removes all entries from the table without deallocating storage.

void	check_resize_before_insert ()
	Checks if resize is needed before inserting and performs it.

Key *	insert (const Key &key)
	Inserts a key into the hash table (copy version).

Key *	insert (Key &&key)
	Inserts a key into the hash table (move version).

Key *	search_or_insert (const Key &key)
	Searches for a key, inserting it if not found (copy version).

Key *	search_or_insert (Key &&key)
	Searches for a key, inserting it if not found (move version).

std::pair< Key *, bool >	contains_or_insert (const Key &key)
	Searches for a key, inserting if not found, with existence flag (copy version).

std::pair< Key *, bool >	contains_or_insert (Key &&key)
	Searches for a key, inserting if not found, with existence flag (move version).

Key *	append (const Key &key)
	Alias for insert() (copy version).

Key *	append (Key &&key)
	Alias for insert() (move version).

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

constexpr bool	contains (const Key &key) const noexcept
	Alias for has().

Key &	find (const Key &key)
	Finds a key and returns a reference to it.

const Key &	find (const Key &key) const
	Finds a key and returns a const reference to it.

const Key &	operator[] (const Key &key) const
	Subscript operator for const access.

const Key &	operator[] (const Key &key)
	Subscript operator with insertion semantics.

void	remove_ptr (Key *key)
	Removes an entry by pointer.

size_t	resize (size_t new_size)
	Resizes the hash table to a new capacity.

void	rehash ()
	Rebuilds the hash table with the same capacity.

void	empty ()
	Clears all entries and resets to default capacity.

constexpr size_t	size () const noexcept
	Returns the number of entries in the table.

constexpr bool	is_empty () const noexcept
	Checks if the table is empty.

constexpr size_t	capacity () const noexcept
	Returns the current capacity of the table.

DynList< Key >	keys () const
	Returns a list containing all keys in the table.

auto	items () const
	Alias for keys().

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

constexpr float	current_alpha () const noexcept
	Returns the current load factor (alpha).

Public Member Functions inherited from GenericTraverse< Container >
template<class Operation >
bool	traverse (Operation &operation) noexcept(traverse_is_noexcept< Operation >())
	Traverse the container via its iterator and performs a conditioned operation on each item.

template<class Operation >
bool	traverse (Operation &operation) const noexcept(traverse_is_noexcept< Operation >())
	Const overload of `traverse(Operation&)`.

template<class Operation >
bool	traverse (Operation &&operation) const noexcept(traverse_is_noexcept< Operation >())
	Overload of `traverse(Operation&) const` that accepts rvalues.

template<class Operation >
bool	traverse (Operation &&operation) noexcept(traverse_is_noexcept< Operation >())
	Overload of `traverse(Operation&)` that accepts rvalues.

Public Member Functions inherited from LocateFunctions< Container, Type >
auto	get_it () const
	Return a properly initialized iterator positioned at the first item on the container.

auto	get_it (const size_t pos) const
	Return a properly initialized iterator positioned at the `pos` item on the container.

auto	get_itor () const
	Alias of `get_it()`.

Type &	nth_ne (const size_t n) noexcept
	Return the n‑th element without bounds checking.

const Type &	nth_ne (const size_t n) const noexcept
	Const overload of `nth_ne(size_t)`.

Type &	nth (const size_t n)
	Return the n-th item of container.

const Type &	nth (const size_t n) const
	Const overload of `nth(size_t)`.

template<class Operation >
Type *	find_ptr (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Find a pointer to an item in the container according to a searching criteria.

template<class Operation >
const Type *	find_ptr (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Const overload of `find_ptr(Operation&)`.

template<class Operation >
const Type *	find_ptr (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of `find_ptr(Operation&) const` that accepts rvalues.

template<class Operation >
Type *	find_ptr (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of `find_ptr(Operation&)` that accepts rvalues.

template<class Operation >
size_t	find_index (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Find the position of an item in the container according to a searching criteria.

template<class Operation >
size_t	find_index (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of `find_index(Operation&)` that accepts rvalues.

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Safe sequential searching of an item matching a criteria.

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &operation) const noexcept(operation_is_noexcept< Operation >())

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &&operation) noexcept(operation_is_noexcept< Operation >())

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())

Public Member Functions inherited from FunctionalMethods< Container, T >
template<typename ... Args>
void	emplace (Args &&... args)
	Appends a new element into the container by constructing it in-place with the given args.

template<typename ... Args>
void	emplace_end (Args &&... args)

template<typename ... Args>
void	emplace_ins (Args &&... args)
	Insert a new element into the container by constructing it in-place with the given args.

template<typename ... Args>
size_t	ninsert (Args ... args)
	Insert n variadic items.

template<typename ... Args>
size_t	nappend (Args ... args)
	Append n variadic items.

template<class Operation >
void	for_each (Operation &operation)
	Traverse all the container and performs an operation on each element.

template<class Operation >
void	for_each (Operation &operation) const
	Const overload of `for_each(Operation&)`.

template<class Operation >
void	for_each (Operation &&operation) const
	Overload of `for_each(Operation&) const` that accepts rvalues.

template<class Operation >
void	for_each (Operation &&operation)
	Overload of `for_each(Operation&)` that accepts rvalues.

template<class Operation >
void	each (Operation &operation)
	Alias of `for_each(Operation&)`.

template<class Operation >
void	each (Operation &operation) const
	Const alias of `for_each(Operation&)`.

template<class Operation >
void	each (Operation &&operation) const
	Const alias of `for_each(Operation&)` that accepts rvalues.

template<class Operation >
void	each (Operation &&operation)
	Alias of `for_each(Operation&)` that accepts rvalues.

template<class Operation >
void	each (size_t pos, const size_t slice, Operation &operation) const
	Traverse the container starting at `pos` taking one item every `slice`, performing a mutable operation on each visited element.

template<class Operation >
void	each (const size_t pos, const size_t slice, Operation &&operation) const

template<class Operation >
void	mutable_for_each (Operation &operation)

template<class Operation >
void	mutable_for_each (Operation &&operation)

template<class Operation >
bool	all (Operation &operation) const
	Check if all the elements of container satisfy a condition.

template<class Operation >
bool	all (Operation &&operation) const
	Overload of `all(Operation&)` that accepts rvalues.

template<class Operation >
bool	exists (Operation &op) const
	Test for existence in the container of an element satisfying a criteria.

template<class Operation >
bool	exists (Operation &&op) const
	Overload of `exists(Operation&)` that accepts rvalues.

template<typename __T = T, class Operation = Aleph::Dft_Map_Op<T, __T>>
Aleph::DynList< __T >	maps (Operation &op) const
	Map the elements of the container.

template<typename __T = T, class Operation = Aleph::Dft_Map_Op<__T, __T>>
Aleph::DynList< __T >	maps (Operation &&op) const
	Overload of `maps(Operation&)` that accepts rvalues.

template<typename __T = T, class Prop , class Operation >
Aleph::DynList< __T >	maps_if (Prop prop, Operation &op) const
	Conditional mapping of the elements of the container.

template<typename __T = T, class Prop , class Operation >
Aleph::DynList< __T >	maps_if (Prop prop, Operation &&op) const
	Overload of `maps_if(Prop, Operation&)` that accepts rvalues.

Aleph::DynList< T >	to_dynlist () const
	Convert container to DynList.

std::vector< T >	to_vector () const
	Convert container to std::vector.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &op) const
	Fold the elements of the container to a specific result.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &&op=Op()) const
	Overload of `foldl(const __T&, Op&)` that accepts rvalues.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &op) const
	Alias for foldl with the same accumulator type.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &&op=Op()) const
	Overload of `fold_left(const __T&, Op&)` that accepts rvalues.

template<class Operation >
T	fold (const T &init, Operation &operation) const
	Simplified version of foldl() where the folded type is the same type of elements stored in the container.

template<class Operation >
T	fold (const T &init, Operation &&operation) const
	Overload of `fold(const T&, Operation&)` that accepts rvalues.

template<class Operation >
Aleph::DynList< T >	filter (Operation &operation) const
	Filter the elements of a container according to a matching criteria.

template<class Operation >
Aleph::DynList< T >	filter (Operation &&operation) const
	Overload of `filter(Operation&)` that accepts rvalues.

template<class Operation >
Aleph::DynList< const T * >	ptr_filter (Operation &operation) const
	Filter the elements of a container according to a matching criteria and return a pointer to the matched items in the container.

template<class Operation >
Aleph::DynList< const T * >	ptr_filter (Operation &&operation) const
	Overload of `ptr_filter(Operation&)` that accepts rvalues.

template<class Operation >
Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &operation) const
	Filter the elements of a container according to a matching criteria and determine its positions respect to the traversal of container.

template<class Operation >
Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &&operation) const
	Overload of `pfilter(Operation&)` that accepts rvalues.

template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &op) const
	Exclusive partition of container according to a filter criteria.

template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &&op) const
	Overload of `partition(Operation&)` that accepts rvalues.

template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (size_t n) const
	Exclusive partition of container in the nth item.

std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	split_half () const
	Split the container into two halves by alternating elements.

template<class Operation >
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &op) const
	Exclusive partition of container according to a filter criteria.

template<class Operation >
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &&op) const
	Overload of `tpartition(Operation&)` that accepts rvalues.

size_t	length () const noexcept
	Count the number of elements of a container.

Aleph::DynList< T >	rev () const
	Return a list with the elements of container in reverse order respect to its traversal order.

Aleph::DynList< T >	take (const size_t n) const
	Return a list with the first n elements seen in the container during its traversal.

Aleph::DynList< T >	take (size_t i, const size_t j, const size_t step=1) const
	Return a list with elements seen in the container between i and j position respect to its traversal.

Aleph::DynList< T >	drop (const size_t n) const
	Drop the first n elements seen in the container during its traversal.

void	mutable_drop (const size_t n)
	Drop the first n elements seen from container.

Public Member Functions inherited from EqualToMethod< Container >
bool	equal_to (const Container &r) const noexcept
	Test if elements of `this` are exactly contained in another container.

bool	operator== (const Container &r) const noexcept

bool	operator!= (const Container &r) const noexcept
	Negation of equal_to()

Public Member Functions inherited from StlAlephIterator< SetName >
iterator	begin () noexcept
	Return an STL-compatible iterator to the first element.

iterator	end () noexcept
	Return an STL-compatible end iterator.

const_iterator	begin () const noexcept
	Return a const iterator to the first element.

const_iterator	end () const noexcept
	Return a const end iterator.

const_iterator	cbegin () const noexcept
	Return a const iterator to the first element.

const_iterator	cend () const noexcept
	Return a const end iterator.

Static Public Member Functions
static Bucket *	key_to_bucket (Key *rec) noexcept

Public Attributes
Bucket *	table = nullptr

Hash_Fct	hash_fct = nullptr

Hash_Fct	second_hash_fct = nullptr

Cmp	cmp

Protected Member Functions
	ODhashTable (const size_t l, Hash_Fct fst_hash_fct, Hash_Fct snd_hash_fct, Cmp cpm_fct, const float lower, const float upper, const bool resize)

Protected Attributes
size_t	len

float	lower_alpha

float	upper_alpha

Private Member Functions
Bucket *	allocate_bucket (Bucket &bucket, unsigned char probe_type) noexcept

void	decrease_probe_counter (Bucket *bucket) noexcept

void	deallocate_bucket (Bucket *bucket) noexcept

size_t	index_forward (size_t &i) const noexcept

size_t	index_backward (size_t &i) const noexcept

bool	is_valid_bucket (Bucket *bucket) const noexcept

size_t	bucket_to_index (Bucket *bucket) const noexcept

bool	is_key_in_table (const Key &key) const noexcept
	Returns true if the key reference points to a key inside the table.

Bucket *	key_in_table_to_bucket (const Key &key) noexcept
	Converts a key reference inside the table to its containing bucket.

template<typename RecordBucket >
void	deallocate_bucket_with_record (Bucket *bucket, RecordBucket &&record_bucket) noexcept
	Template version of deallocate_bucket that accepts a callback to record modified buckets before decrementing their probe_counter.

Key *	test_resize (Bucket *curr_bucket, const Key &key)

Bucket *	allocate_bucket (const Key &key) noexcept

std::tuple< Bucket *, bool >	hard_allocate_bucket (const Key &key) noexcept

void	remove_bucket (Bucket *bucket)
	Delete the record from the table.

Static Private Member Functions
static void	update_stat_len (DynArray< size_t > &lens, size_t i)

Private Attributes
size_t	N

bool	with_resize

Friends
class	OhashCommon< ODhashTable< Key, Cmp >, Key >

Additional Inherited Members
Related Symbols inherited from FunctionalMethods< Container, T >
	each

	each

	each

Detailed Description

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

Open addressing hash table with double hashing collision resolution.

This class implements a closed hash table (contiguous memory array) that resolves collisions using double hashing. When a collision occurs, a second hash function is called to probe for an available bucket. If the second probe also collides, linear probing continues from that index.

The table uses a probe counter mechanism that enables O(1) deletion without relocation. Each bucket tracks how many keys depend on it being in the collision chain, allowing efficient garbage collection of DELETED entries.

Based on the algorithms described in Knuth's "The Art of Computer Programming", Volume 3.

Template Parameters

Key	The type of keys stored in the table.
Cmp	Comparison functor for keys (default: Aleph::equal_to<Key>). Must return true if two keys are equal.

Collision Resolution Strategy:

First probe: hash_fct(key) % len
Second probe: second_hash_fct(key) % len
Linear probing from second probe position

Example:: ODhashTable<int> table;

table.insert(42);

table.insert(17);

if (table.has(42))

std::cout << "Found 42" << '\n';

table.remove(42);

Aleph::ODhashTable
Open addressing hash table with double hashing collision resolution.
Definition tpl_odhash.H:180

Aleph::ODhashTable::table
Bucket * table
Definition tpl_odhash.H:253

See also: OLhashTable for linear probing variant.; OhashCommon for shared hash table operations.

Definition at line 173 of file tpl_odhash.H.

Member Typedef Documentation

◆ Hash_Fct

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

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

Definition at line 188 of file tpl_odhash.H.

◆ Hash_Fct_Ptr

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

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

Definition at line 190 of file tpl_odhash.H.

◆ Item_Type

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

using Aleph::ODhashTable< Key, Cmp >::Item_Type = Key

Definition at line 186 of file tpl_odhash.H.

◆ Key_Type

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

using Aleph::ODhashTable< Key, Cmp >::Key_Type = Key

Definition at line 184 of file tpl_odhash.H.

◆ Stats

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

using Aleph::ODhashTable< Key, Cmp >::Stats = typename OhashCommon<ODhashTable<Key, Cmp>, Key>::Stats

Definition at line 977 of file tpl_odhash.H.

Member Enumeration Documentation

◆ Probe

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

enum Aleph::ODhashTable::Probe

Enumerator
NO_PROBED
FIRST_PROBE
SECOND_PROBE
LINEAR_PROBE

Definition at line 194 of file tpl_odhash.H.

◆ Status

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

enum Aleph::ODhashTable::Status

Enumerator
EMPTY
BUSY
DELETED

Definition at line 192 of file tpl_odhash.H.

Constructor & Destructor Documentation

◆ ODhashTable() [1/7]

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

Aleph::ODhashTable< Key, Cmp >::ODhashTable	(	const size_t	l,
		Hash_Fct	fst_hash_fct,
		Hash_Fct	snd_hash_fct,
		Cmp	cpm_fct,
		const float	lower,
		const float	upper,
		const bool	resize
	)

inlineprotected

Definition at line 429 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::len, and Aleph::ODhashTable< Key, Cmp >::table.

◆ ODhashTable() [2/7]

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

Aleph::ODhashTable< Key, Cmp >::ODhashTable	(	size_t	len = `Primes::DefaultPrime`,
		Hash_Fct_Ptr	first_hash_fct = `Aleph::dft_hash_fct<Key>`,
		Hash_Fct_Ptr	second_hash_fct = `Aleph::snd_hash_fct<Key>`,
		Cmp	cmp = `Cmp()`,
		float	lower_alpha = `hash_default_lower_alpha`,
		float	upper_alpha = `hash_default_upper_alpha`,
		bool	with_resize = `true`
	)

inline

Instantiate a closed hash table with collision resolution by double hashing.

Parameters

[in]	first_hash_fct	hash function for the first probe.
[in]	second_hash_fct	hash function for the second probe.
	cmp	comparison functor for keys. Must return true if two keys are equal. By default, Aleph::equal_to<Key> is used.
	lower_alpha	lower load factor threshold for resizing. When the load factor goes below this value, the table shrinks. 0 < lower_alpha < upper_alpha < 1. 0.25 is a reasonable default. 0.1 gives faster operations but uses more memory.
	upper_alpha	upper load factor threshold for resizing. When the load factor goes above this value, the table expands. 0 < lower_alpha < upper_alpha < 1. 0.5 is a reasonable default. 0.7 gives faster operations but uses more memory.
	with_resize	if true, the table resizes automatically when load factor thresholds are crossed.
[in]	len	table size.

Exceptions

bad_alloc if there is no memory for the bucket table.

Definition at line 466 of file tpl_odhash.H.

◆ ~ODhashTable()

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

Aleph::ODhashTable< Key, Cmp >::~ODhashTable ( )

inline

Free the whole hash table.

Definition at line 477 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::table.

◆ ODhashTable() [3/7]

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

Aleph::ODhashTable< Key, Cmp >::ODhashTable ( const ODhashTable< Key, Cmp > & other )

inline

Definition at line 483 of file tpl_odhash.H.

References OhashCommon< HashTbl, Key >::copy_from_table(), FunctionalMethods< Container, T >::maps(), and Aleph::ODhashTable< Key, Cmp >::table.

◆ ODhashTable() [4/7]

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

Aleph::ODhashTable< Key, Cmp >::ODhashTable ( ODhashTable< Key, Cmp > && other )

inlinenoexcept

Definition at line 491 of file tpl_odhash.H.

References FunctionalMethods< Container, T >::maps(), Aleph::ODhashTable< Key, Cmp >::swap(), and Aleph::ODhashTable< Key, Cmp >::table.

◆ ODhashTable() [5/7]

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

template<template< typename > class List>

Aleph::ODhashTable< Key, Cmp >::ODhashTable ( const List< Key > & l )

inline

Definition at line 498 of file tpl_odhash.H.

◆ ODhashTable() [6/7]

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

template<class It >

Aleph::ODhashTable< Key, Cmp >::ODhashTable	(	It	b,
		It	e
	)

inline

Definition at line 498 of file tpl_odhash.H.

◆ ODhashTable() [7/7]

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

Aleph::ODhashTable< Key, Cmp >::ODhashTable ( std::initializer_list< Key > l )

inline

Definition at line 498 of file tpl_odhash.H.

Member Function Documentation

◆ allocate_bucket() [1/2]

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

Bucket * Aleph::ODhashTable< Key, Cmp >::allocate_bucket	(	Bucket &	bucket,
		unsigned char	probe_type
	)

inlineprivatenoexcept

Definition at line 268 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::BUSY, FunctionalMethods< Container, T >::maps(), and Aleph::ODhashTable< Key, Cmp >::N.

Referenced by Aleph::ODhashTable< Key, Cmp >::allocate_bucket(), and Aleph::ODhashTable< Key, Cmp >::hard_allocate_bucket().

◆ allocate_bucket() [2/2]

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

Bucket * Aleph::ODhashTable< Key, Cmp >::allocate_bucket ( const Key & key )

inlineprivatenoexcept

Definition at line 620 of file tpl_odhash.H.

◆ bucket_to_index()

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

size_t Aleph::ODhashTable< Key, Cmp >::bucket_to_index ( Bucket * bucket ) const

inlineprivatenoexcept

Definition at line 327 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::is_valid_bucket(), FunctionalMethods< Container, T >::maps(), and Aleph::ODhashTable< Key, Cmp >::table.

◆ deallocate_bucket()

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

void Aleph::ODhashTable< Key, Cmp >::deallocate_bucket ( Bucket * bucket )

inlineprivatenoexcept

Definition at line 289 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::deallocate_bucket_with_record().

Referenced by Aleph::ODhashTable< Key, Cmp >::remove(), and Aleph::ODhashTable< Key, Cmp >::remove_bucket().

◆ deallocate_bucket_with_record()

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

template<typename RecordBucket >

void Aleph::ODhashTable< Key, Cmp >::deallocate_bucket_with_record	(	Bucket *	bucket,
		RecordBucket &&	record_bucket
	)

inlineprivatenoexcept

Template version of deallocate_bucket that accepts a callback to record modified buckets before decrementing their probe_counter.

Definition at line 360 of file tpl_odhash.H.

Referenced by Aleph::ODhashTable< Key, Cmp >::deallocate_bucket().

◆ decrease_probe_counter()

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

void Aleph::ODhashTable< Key, Cmp >::decrease_probe_counter ( Bucket * bucket )

inlineprivatenoexcept

Definition at line 280 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::BUSY, Aleph::ODhashTable< Key, Cmp >::DELETED, Aleph::ODhashTable< Key, Cmp >::EMPTY, and FunctionalMethods< Container, T >::maps().

Referenced by Aleph::ODhashTable< Key, Cmp >::deallocate_bucket_with_record().

◆ get_compare() [1/2]

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

constexpr const Cmp & Aleph::ODhashTable< Key, Cmp >::get_compare ( ) const

inlineconstexprnoexcept

Definition at line 414 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::cmp.

◆ get_compare() [2/2]

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

constexpr Cmp & Aleph::ODhashTable< Key, Cmp >::get_compare ( )

inlineconstexprnoexcept

Definition at line 416 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::cmp.

◆ get_hash_fct()

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

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

inlinenoexcept

Definition at line 533 of file tpl_odhash.H.

◆ get_second_hash_fct()

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

constexpr Hash_Fct Aleph::ODhashTable< Key, Cmp >::get_second_hash_fct ( ) const

inlineconstexprnoexcept

Definition at line 607 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::second_hash_fct.

◆ hard_allocate_bucket()

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

std::tuple< Bucket *, bool > Aleph::ODhashTable< Key, Cmp >::hard_allocate_bucket ( const Key & key )

inlineprivatenoexcept

Definition at line 746 of file tpl_odhash.H.

◆ index_backward()

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

size_t Aleph::ODhashTable< Key, Cmp >::index_backward ( size_t & i ) const

inlineprivatenoexcept

Definition at line 302 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::len, and FunctionalMethods< Container, T >::maps().

◆ index_forward()

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

size_t Aleph::ODhashTable< Key, Cmp >::index_forward ( size_t & i ) const

inlineprivatenoexcept

Definition at line 294 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::len, and FunctionalMethods< Container, T >::maps().

Referenced by Aleph::ODhashTable< Key, Cmp >::allocate_bucket(), Aleph::ODhashTable< Key, Cmp >::deallocate_bucket_with_record(), Aleph::ODhashTable< Key, Cmp >::hard_allocate_bucket(), Aleph::ODhashTable< Key, Cmp >::remove(), Aleph::ODhashTable< Key, Cmp >::search(), and Aleph::ODhashTable< Key, Cmp >::stats().

◆ is_key_in_table()

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

bool Aleph::ODhashTable< Key, Cmp >::is_key_in_table ( const Key & key ) const

inlineprivatenoexcept

Returns true if the key reference points to a key inside the table.

Definition at line 334 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::len, FunctionalMethods< Container, T >::maps(), and Aleph::ODhashTable< Key, Cmp >::table.

Referenced by Aleph::ODhashTable< Key, Cmp >::key_in_table_to_bucket(), and Aleph::ODhashTable< Key, Cmp >::remove().

◆ is_valid_bucket()

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

bool Aleph::ODhashTable< Key, Cmp >::is_valid_bucket ( Bucket * bucket ) const

inlineprivatenoexcept

Definition at line 310 of file tpl_odhash.H.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::ODhashTable< Key, Cmp >::len, FunctionalMethods< Container, T >::maps(), and Aleph::ODhashTable< Key, Cmp >::table.

Referenced by Aleph::ODhashTable< Key, Cmp >::bucket_to_index(), and Aleph::ODhashTable< Key, Cmp >::remove_bucket().

◆ key_in_table_to_bucket()

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

Bucket * Aleph::ODhashTable< Key, Cmp >::key_in_table_to_bucket ( const Key & key )

inlineprivatenoexcept

Converts a key reference inside the table to its containing bucket.

Definition at line 351 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::is_key_in_table(), Aleph::ODhashTable< Key, Cmp >::key_to_bucket(), and FunctionalMethods< Container, T >::maps().

Referenced by Aleph::ODhashTable< Key, Cmp >::remove().

◆ key_to_bucket()

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

static Bucket * Aleph::ODhashTable< Key, Cmp >::key_to_bucket ( Key * rec )

inlinestaticnoexcept

Definition at line 407 of file tpl_odhash.H.

References LocateFunctions< Container, Type >::base(), FunctionalMethods< Container, T >::maps(), and offset.

Referenced by Aleph::ODhashTable< Key, Cmp >::key_in_table_to_bucket().

◆ operator=() [1/2]

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

ODhashTable & Aleph::ODhashTable< Key, Cmp >::operator= ( const ODhashTable< Key, Cmp > & other )

inline

Definition at line 500 of file tpl_odhash.H.

◆ operator=() [2/2]

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

ODhashTable & Aleph::ODhashTable< Key, Cmp >::operator= ( ODhashTable< Key, Cmp > && other )

inlinenoexcept

Definition at line 527 of file tpl_odhash.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::ODhashTable< Key, Cmp >::swap().

◆ remove()

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

void Aleph::ODhashTable< Key, Cmp >::remove ( const Key & key )

inline

Remove a key from the hash table.

If key is a reference to a key inside the table (from search/insert), it uses the fast path via deallocate_bucket. If key is external, it searches for the key and removes it. Throws domain_error if the key is not found.

Definition at line 897 of file tpl_odhash.H.

Referenced by demo_odhash(), and TEST().

◆ remove_bucket()

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

void Aleph::ODhashTable< Key, Cmp >::remove_bucket ( Bucket * bucket )

inlineprivate

Delete the record from the table.

record must belong to the table and must have been previously determined by a insert or search. The invalid_argument exception is raised if the record does not correspond to a bucket in the table. It shoots domain_error if the record in the table does not contain an element.

Definition at line 883 of file tpl_odhash.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::ODhashTable< Key, Cmp >::BUSY, Aleph::ODhashTable< Key, Cmp >::deallocate_bucket(), Aleph::ODhashTable< Key, Cmp >::is_valid_bucket(), FunctionalMethods< Container, T >::maps(), and Aleph::ODhashTable< Key, Cmp >::Bucket::status.

◆ search()

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

Key * Aleph::ODhashTable< Key, Cmp >::search ( const Key & key ) const

inlinenoexcept

searches the table for the key.

Return a pointer to the record associated with key within the table; nullptr otherwise.

Definition at line 537 of file tpl_odhash.H.

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

◆ set_hash_fct() [1/2]

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

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

inlinenoexcept

Definition at line 533 of file tpl_odhash.H.

◆ set_hash_fct() [2/2]

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

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

inlinenoexcept

Definition at line 533 of file tpl_odhash.H.

◆ set_second_hash_fct() [1/2]

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

void Aleph::ODhashTable< Key, Cmp >::set_second_hash_fct ( Hash_Fct fct )

inlinenoexcept

Definition at line 609 of file tpl_odhash.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::ODhashTable< Key, Cmp >::second_hash_fct.

◆ set_second_hash_fct() [2/2]

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

void Aleph::ODhashTable< Key, Cmp >::set_second_hash_fct ( Hash_Fct_Ptr fct )

inlinenoexcept

Definition at line 614 of file tpl_odhash.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::ODhashTable< Key, Cmp >::second_hash_fct.

◆ stats()

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

Stats Aleph::ODhashTable< Key, Cmp >::stats ( ) const

inline

◆ swap()

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

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

inlinenoexcept

Definition at line 418 of file tpl_odhash.H.

References Aleph::ODhashTable< Key, Cmp >::cmp, Aleph::ODhashTable< Key, Cmp >::hash_fct, Aleph::ODhashTable< Key, Cmp >::len, FunctionalMethods< Container, T >::maps(), Aleph::ODhashTable< Key, Cmp >::N, Aleph::ODhashTable< Key, Cmp >::second_hash_fct, and Aleph::ODhashTable< Key, Cmp >::table.

Referenced by Aleph::ODhashTable< Key, Cmp >::ODhashTable(), Aleph::ODhashTable< Key, Cmp >::operator=(), and TEST().

◆ test_resize()

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

Key * Aleph::ODhashTable< Key, Cmp >::test_resize	(	Bucket *	curr_bucket,
		const Key &	key
	)

inlineprivate

Definition at line 533 of file tpl_odhash.H.

◆ update_stat_len()

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

static void Aleph::ODhashTable< Key, Cmp >::update_stat_len	(	DynArray< size_t > &	lens,
		size_t	i
	)

inlinestaticprivate

Definition at line 533 of file tpl_odhash.H.

Referenced by Aleph::ODhashTable< Key, Cmp >::stats().

Friends And Related Symbol Documentation

◆ OhashCommon< ODhashTable< Key, Cmp >, Key >

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

friend class OhashCommon< ODhashTable< Key, Cmp >, Key >

friend

Definition at line 1 of file tpl_odhash.H.

Member Data Documentation

◆ cmp

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

Cmp Aleph::ODhashTable< Key, Cmp >::cmp

Definition at line 257 of file tpl_odhash.H.

Referenced by Aleph::ODhashTable< Key, Cmp >::allocate_bucket(), Aleph::ODhashTable< Key, Cmp >::get_compare(), Aleph::ODhashTable< Key, Cmp >::get_compare(), Aleph::ODhashTable< Key, Cmp >::hard_allocate_bucket(), Aleph::ODhashTable< Key, Cmp >::operator=(), Aleph::ODhashTable< Key, Cmp >::remove(), Aleph::ODhashTable< Key, Cmp >::search(), Aleph::ODhashTable< Key, Cmp >::stats(), and Aleph::ODhashTable< Key, Cmp >::swap().

◆ hash_fct

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

Hash_Fct Aleph::ODhashTable< Key, Cmp >::hash_fct = nullptr

Definition at line 254 of file tpl_odhash.H.

Referenced by Aleph::ODhashTable< Key, Cmp >::allocate_bucket(), Aleph::ODhashTable< Key, Cmp >::deallocate_bucket_with_record(), Aleph::ODhashTable< Key, Cmp >::hard_allocate_bucket(), Aleph::ODhashTable< Key, Cmp >::operator=(), Aleph::ODhashTable< Key, Cmp >::remove(), Aleph::ODhashTable< Key, Cmp >::search(), Aleph::ODhashTable< Key, Cmp >::stats(), and Aleph::ODhashTable< Key, Cmp >::swap().

◆ len

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

size_t Aleph::ODhashTable< Key, Cmp >::len

protected

Definition at line 260 of file tpl_odhash.H.

◆ lower_alpha

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

float Aleph::ODhashTable< Key, Cmp >::lower_alpha

protected

Definition at line 261 of file tpl_odhash.H.

Referenced by Aleph::ODhashTable< Key, Cmp >::operator=().

◆ N

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

size_t Aleph::ODhashTable< Key, Cmp >::N

private

Definition at line 265 of file tpl_odhash.H.

Referenced by Aleph::ODhashTable< Key, Cmp >::allocate_bucket(), Aleph::ODhashTable< Key, Cmp >::allocate_bucket(), Aleph::ODhashTable< Key, Cmp >::deallocate_bucket_with_record(), Aleph::ODhashTable< Key, Cmp >::hard_allocate_bucket(), Aleph::ODhashTable< Key, Cmp >::operator=(), and Aleph::ODhashTable< Key, Cmp >::swap().

◆ second_hash_fct

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

Hash_Fct Aleph::ODhashTable< Key, Cmp >::second_hash_fct = nullptr

Definition at line 255 of file tpl_odhash.H.

◆ table

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

Bucket* Aleph::ODhashTable< Key, Cmp >::table = nullptr

Definition at line 253 of file tpl_odhash.H.

◆ upper_alpha

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

float Aleph::ODhashTable< Key, Cmp >::upper_alpha

protected

Definition at line 262 of file tpl_odhash.H.

Referenced by Aleph::ODhashTable< Key, Cmp >::operator=().

◆ with_resize

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

bool Aleph::ODhashTable< Key, Cmp >::with_resize

private

Definition at line 266 of file tpl_odhash.H.

Referenced by Aleph::ODhashTable< Key, Cmp >::operator=().

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

tpl_odhash.H

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Hash_Fct

◆ Hash_Fct_Ptr

◆ Item_Type

◆ Key_Type

◆ Stats

Member Enumeration Documentation

◆ Probe

◆ Status

Constructor & Destructor Documentation

◆ ODhashTable() [1/7]

◆ ODhashTable() [2/7]

◆ ~ODhashTable()

◆ ODhashTable() [3/7]

◆ ODhashTable() [4/7]

◆ ODhashTable() [5/7]

◆ ODhashTable() [6/7]

◆ ODhashTable() [7/7]

Member Function Documentation

◆ allocate_bucket() [1/2]

◆ allocate_bucket() [2/2]

◆ bucket_to_index()

◆ deallocate_bucket()

◆ deallocate_bucket_with_record()

◆ decrease_probe_counter()

◆ get_compare() [1/2]

◆ get_compare() [2/2]

◆ get_hash_fct()

◆ get_second_hash_fct()

◆ hard_allocate_bucket()

◆ index_backward()

◆ index_forward()

◆ is_key_in_table()

◆ is_valid_bucket()

◆ key_in_table_to_bucket()

◆ key_to_bucket()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove()

◆ remove_bucket()

◆ search()

◆ set_hash_fct() [1/2]

◆ set_hash_fct() [2/2]

◆ set_second_hash_fct() [1/2]

◆ set_second_hash_fct() [2/2]

◆ stats()

◆ swap()

◆ test_resize()

◆ update_stat_len()

Friends And Related Symbol Documentation

◆ OhashCommon< ODhashTable< Key, Cmp >, Key >

Member Data Documentation

◆ cmp

◆ hash_fct

◆ len

◆ lower_alpha

◆ N

◆ second_hash_fct

◆ table

◆ upper_alpha

◆ with_resize