Open addressing hash table with linear probing collision resolution. More...

#include <tpl_olhash.H>

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

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

Classes
struct	Bucket

Public Types
enum	Status { EMPTY , BUSY , DELETED }

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< OLhashTable< 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

	OLhashTable (const size_t l, Hash_Fct hash_f, Cmp cmp_f, const float l_alpha, const float u_alpha, const bool resize)
	Instantiate a hash table with hash function __hash_fct and dimension len.

	OLhashTable (size_t len, Hash_Fct hash_fct, Hash_Fct, Cmp cmp, float lower_alpha, float upper_alpha, bool with_resize)

	OLhashTable (size_t len=Primes::DefaultPrime, Hash_Fct_Ptr hash_fct=Aleph::dft_hash_fct< Key >, Cmp cmp=Cmp(), float lower_alpha=hash_default_lower_alpha, float upper_alpha=0.70f, bool with_resize=true)

	OLhashTable (size_t len, Hash_Fct_Ptr hash_fct, Hash_Fct_Ptr, Cmp cmp, float lower_alpha, float upper_alpha, bool with_resize)

	OLhashTable (size_t len, Hash_Fct hash_fct, Hash_Fct_Ptr, Cmp cmp, float lower_alpha, float upper_alpha, bool with_resize)
	Constructor with two hash functions for metaprogramming compatibility with ODhashTable type.

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

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

	OLhashTable (std::initializer_list< Key > l)

	~OLhashTable ()
	Release all occupied memory.

void	swap (OLhashTable &other) noexcept

	OLhashTable (const OLhashTable &other)

	OLhashTable (OLhashTable &&other) noexcept

OLhashTable &	operator= (const OLhashTable &other)

OLhashTable &	operator= (OLhashTable &&other) noexcept

Key *	search (const Key &key) const noexcept
	Finds the key and returns the associated record if key is find inside the table; otherwise, nullptr is returned.

void	remove (const Key &key)
	Remove the key referenced by key.

Hash_Fct	get_hash_fct () const noexcept

void	set_hash_fct (Hash_Fct fct) noexcept

void	set_hash_fct (Hash_Fct_Ptr fct) noexcept

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

size_t	N = 0

Protected Member Functions
Bucket *	allocate_bucket (const Key &key) noexcept

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

size_t	prev_index (const size_t i) const noexcept
	Index of previous bucket (handles wrap-around)

size_t	next_index (const size_t i) const noexcept
	Index of next bucket (handles wrap-around)

void	cleanup_deleted_chain (size_t idx) noexcept
	Cleanup DELETED entries that are at the end of collision chains.

void	deallocate_bucket (Bucket *bucket)
	Removes the record pointed to by record from the table.

Protected Attributes
size_t	len

float	lower_alpha

float	upper_alpha

Cmp	cmp

Private Member Functions
bool	is_valid_bucket (Bucket *bucket) const noexcept

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

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

Private Attributes
Hash_Fct	hash_fct

bool	with_resize

Friends
class	OhashCommon< OLhashTable< 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::OLhashTable< Key, Cmp >

Open addressing hash table with linear probing collision resolution.

This class implements a closed hash table (contiguous memory array) that resolves collisions using linear probing. When a collision occurs, consecutive buckets are checked sequentially until an empty slot is found.

Linear probing has better cache locality than double hashing but may suffer from primary clustering. It is simpler and often faster for small to medium-sized tables.

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:: Linear probing from hash_fct(key) % len, incrementing by 1 until an empty bucket is found.

Example:: OLhashTable<std::string> table;

table.insert("hello");

table.insert("world");

auto ptr = table.search("hello");

if (ptr != nullptr)

std::cout << "Found: " << *ptr << '\n';

Aleph::OLhashTable
Open addressing hash table with linear probing collision resolution.
Definition tpl_olhash.H:168

Aleph::OLhashTable::table
Bucket * table
Definition tpl_olhash.H:203

See also: ODhashTable for double hashing variant.; OhashCommon for shared hash table operations.

Definition at line 161 of file tpl_olhash.H.

Member Typedef Documentation

◆ Hash_Fct

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

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

Definition at line 177 of file tpl_olhash.H.

◆ Hash_Fct_Ptr

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

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

Definition at line 179 of file tpl_olhash.H.

◆ Item_Type

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

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

Definition at line 175 of file tpl_olhash.H.

◆ Key_Type

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

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

Definition at line 173 of file tpl_olhash.H.

◆ Stats

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

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

Definition at line 551 of file tpl_olhash.H.

Member Enumeration Documentation

◆ Status

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

enum Aleph::OLhashTable::Status

Enumerator
EMPTY
BUSY
DELETED

Definition at line 181 of file tpl_olhash.H.

Constructor & Destructor Documentation

◆ OLhashTable() [1/10]

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

Aleph::OLhashTable< Key, Cmp >::OLhashTable	(	const size_t	l,
		Hash_Fct	hash_f,
		Cmp	cmp_f,
		const float	l_alpha,
		const float	u_alpha,
		const bool	resize
	)

inline

Instantiate a hash table with hash function __hash_fct and dimension len.

Definition at line 246 of file tpl_olhash.H.

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

◆ OLhashTable() [2/10]

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

Aleph::OLhashTable< Key, Cmp >::OLhashTable	(	size_t	len,
		Hash_Fct	hash_fct,
		Hash_Fct	,
		Cmp	cmp,
		float	lower_alpha,
		float	upper_alpha,
		bool	with_resize
	)

inline

Definition at line 255 of file tpl_olhash.H.

◆ OLhashTable() [3/10]

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

Aleph::OLhashTable< Key, Cmp >::OLhashTable	(	size_t	len = `Primes::DefaultPrime`,
		Hash_Fct_Ptr	hash_fct = `Aleph::dft_hash_fct<Key>`,
		Cmp	cmp = `Cmp()`,
		float	lower_alpha = `hash_default_lower_alpha`,
		float	upper_alpha = `0.70f`,
		bool	with_resize = `true`
	)

inline

Definition at line 259 of file tpl_olhash.H.

◆ OLhashTable() [4/10]

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

Aleph::OLhashTable< Key, Cmp >::OLhashTable	(	size_t	len,
		Hash_Fct_Ptr	hash_fct,
		Hash_Fct_Ptr	,
		Cmp	cmp,
		float	lower_alpha,
		float	upper_alpha,
		bool	with_resize
	)

inline

Definition at line 268 of file tpl_olhash.H.

◆ OLhashTable() [5/10]

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

Aleph::OLhashTable< Key, Cmp >::OLhashTable	(	size_t	len,
		Hash_Fct	hash_fct,
		Hash_Fct_Ptr	,
		Cmp	cmp,
		float	lower_alpha,
		float	upper_alpha,
		bool	with_resize
	)

inline

Constructor with two hash functions for metaprogramming compatibility with ODhashTable type.

Definition at line 276 of file tpl_olhash.H.

◆ OLhashTable() [6/10]

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

template<template< typename > class List>

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

inline

Definition at line 281 of file tpl_olhash.H.

◆ OLhashTable() [7/10]

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

template<class It >

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

inline

Definition at line 281 of file tpl_olhash.H.

◆ OLhashTable() [8/10]

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

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

inline

Definition at line 281 of file tpl_olhash.H.

◆ ~OLhashTable()

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

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

inline

Release all occupied memory.

Definition at line 284 of file tpl_olhash.H.

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

◆ OLhashTable() [9/10]

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

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

inline

Definition at line 302 of file tpl_olhash.H.

References OhashCommon< HashTbl, Key >::copy_from_table().

◆ OLhashTable() [10/10]

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

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

inlinenoexcept

Definition at line 309 of file tpl_olhash.H.

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

Member Function Documentation

◆ allocate_bucket()

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

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

inlineprotectednoexcept

Definition at line 370 of file tpl_olhash.H.

References Aleph::OLhashTable< Key, Cmp >::BUSY, Aleph::OLhashTable< Key, Cmp >::cmp, Aleph::OLhashTable< Key, Cmp >::EMPTY, Aleph::OLhashTable< Key, Cmp >::hash_fct, Aleph::OLhashTable< Key, Cmp >::len, FunctionalMethods< Container, T >::maps(), Aleph::OLhashTable< Key, Cmp >::N, Aleph::OLhashTable< Key, Cmp >::Bucket::status, and Aleph::OLhashTable< Key, Cmp >::table.

◆ cleanup_deleted_chain()

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

void Aleph::OLhashTable< Key, Cmp >::cleanup_deleted_chain ( size_t idx )

inlineprotectednoexcept

Cleanup DELETED entries that are at the end of collision chains.

If the bucket at idx has a following EMPTY bucket, it can be marked EMPTY instead of DELETED. Then propagate backwards to clean any DELETED buckets that now also end in EMPTY. This implements Knuth's optimization to avoid tombstone accumulation.

Definition at line 477 of file tpl_olhash.H.

References Aleph::count(), Aleph::OLhashTable< Key, Cmp >::DELETED, Aleph::OLhashTable< Key, Cmp >::EMPTY, Aleph::OLhashTable< Key, Cmp >::len, FunctionalMethods< Container, T >::maps(), Aleph::OLhashTable< Key, Cmp >::next_index(), Aleph::OLhashTable< Key, Cmp >::prev_index(), Aleph::OLhashTable< Key, Cmp >::Bucket::status, and Aleph::OLhashTable< Key, Cmp >::table.

Referenced by Aleph::OLhashTable< Key, Cmp >::deallocate_bucket(), and Aleph::OLhashTable< Key, Cmp >::remove().

◆ deallocate_bucket()

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

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

inlineprotected

Removes the record pointed to by record from the table.

Obviously, record must point to an entry returned by insert() or search(). Fires invalid_argument exceptions if record is not an address within table range or domain_error if bucket of the registry is not busy.

Definition at line 503 of file tpl_olhash.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::OLhashTable< Key, Cmp >::BUSY, Aleph::OLhashTable< Key, Cmp >::cleanup_deleted_chain(), Aleph::OLhashTable< Key, Cmp >::DELETED, Aleph::OLhashTable< Key, Cmp >::is_valid_bucket(), FunctionalMethods< Container, T >::maps(), Aleph::OLhashTable< Key, Cmp >::N, Aleph::OLhashTable< Key, Cmp >::Bucket::status, and Aleph::OLhashTable< Key, Cmp >::table.

◆ get_compare() [1/2]

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

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

inlineconstexprnoexcept

Definition at line 238 of file tpl_olhash.H.

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

◆ get_compare() [2/2]

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

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

inlineconstexprnoexcept

Definition at line 240 of file tpl_olhash.H.

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

◆ get_hash_fct()

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

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

inlinenoexcept

Definition at line 549 of file tpl_olhash.H.

◆ hard_allocate_bucket()

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

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

inlineprotectednoexcept

Definition at line 417 of file tpl_olhash.H.

References Aleph::OLhashTable< Key, Cmp >::BUSY, Aleph::OLhashTable< Key, Cmp >::cmp, Aleph::OLhashTable< Key, Cmp >::EMPTY, Aleph::OLhashTable< Key, Cmp >::hash_fct, Aleph::OLhashTable< Key, Cmp >::len, FunctionalMethods< Container, T >::maps(), Aleph::OLhashTable< Key, Cmp >::N, Aleph::OLhashTable< Key, Cmp >::Bucket::status, and Aleph::OLhashTable< Key, Cmp >::table.

◆ is_valid_bucket()

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

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

inlineprivatenoexcept

Definition at line 218 of file tpl_olhash.H.

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

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

◆ key_to_bucket()

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

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

inlinestaticnoexcept

Definition at line 195 of file tpl_olhash.H.

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

◆ next_index()

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

size_t Aleph::OLhashTable< Key, Cmp >::next_index ( const size_t i ) const

inlineprotectednoexcept

Index of next bucket (handles wrap-around)

Definition at line 467 of file tpl_olhash.H.

References Aleph::OLhashTable< Key, Cmp >::len.

Referenced by Aleph::OLhashTable< Key, Cmp >::cleanup_deleted_chain().

◆ operator=() [1/2]

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

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

inline

Definition at line 314 of file tpl_olhash.H.

References OhashCommon< HashTbl, Key >::clean_table(), Aleph::OLhashTable< Key, Cmp >::cmp, OhashCommon< HashTbl, Key >::copy_from_table(), Aleph::OLhashTable< Key, Cmp >::hash_fct, Aleph::OLhashTable< Key, Cmp >::len, Aleph::OLhashTable< Key, Cmp >::lower_alpha, FunctionalMethods< Container, T >::maps(), Aleph::OLhashTable< Key, Cmp >::N, Aleph::OLhashTable< Key, Cmp >::table, and Aleph::OLhashTable< Key, Cmp >::upper_alpha.

◆ operator=() [2/2]

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

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

inlinenoexcept

Definition at line 339 of file tpl_olhash.H.

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

◆ prev_index()

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

size_t Aleph::OLhashTable< Key, Cmp >::prev_index ( const size_t i ) const

inlineprotectednoexcept

Index of previous bucket (handles wrap-around)

Definition at line 461 of file tpl_olhash.H.

References Aleph::OLhashTable< Key, Cmp >::len.

Referenced by Aleph::OLhashTable< Key, Cmp >::cleanup_deleted_chain().

◆ remove()

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

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

inline

Remove the key referenced by key.

key must be a valid reference to the key previously inserted or retrieved in the table. If the key is not in the table, then a domain_error exception is thrown.

Definition at line 523 of file tpl_olhash.H.

References ah_domain_error, Aleph::OLhashTable< Key, Cmp >::BUSY, Aleph::OLhashTable< Key, Cmp >::cleanup_deleted_chain(), Aleph::OLhashTable< Key, Cmp >::cmp, Aleph::OLhashTable< Key, Cmp >::DELETED, Aleph::OLhashTable< Key, Cmp >::EMPTY, Aleph::OLhashTable< Key, Cmp >::hash_fct, Aleph::OLhashTable< Key, Cmp >::len, FunctionalMethods< Container, T >::maps(), Aleph::OLhashTable< Key, Cmp >::N, Aleph::OLhashTable< Key, Cmp >::Bucket::status, and Aleph::OLhashTable< Key, Cmp >::table.

◆ search()

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

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

inlinenoexcept

Finds the key and returns the associated record if key is find inside the table; otherwise, nullptr is returned.

Definition at line 347 of file tpl_olhash.H.

References Aleph::OLhashTable< Key, Cmp >::BUSY, Aleph::OLhashTable< Key, Cmp >::cmp, Aleph::OLhashTable< Key, Cmp >::EMPTY, Aleph::OLhashTable< Key, Cmp >::hash_fct, Aleph::OLhashTable< Key, Cmp >::len, FunctionalMethods< Container, T >::maps(), and Aleph::OLhashTable< Key, Cmp >::table.

Referenced by TEST().

◆ set_hash_fct() [1/2]

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

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

inlinenoexcept

Definition at line 549 of file tpl_olhash.H.

◆ set_hash_fct() [2/2]

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

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

inlinenoexcept

Definition at line 549 of file tpl_olhash.H.

◆ stats()

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

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

inline

Definition at line 553 of file tpl_olhash.H.

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

◆ swap()

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

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

inlinenoexcept

Definition at line 290 of file tpl_olhash.H.

References Aleph::OLhashTable< Key, Cmp >::cmp, Aleph::OLhashTable< Key, Cmp >::hash_fct, Aleph::OLhashTable< Key, Cmp >::len, Aleph::OLhashTable< Key, Cmp >::lower_alpha, FunctionalMethods< Container, T >::maps(), Aleph::OLhashTable< Key, Cmp >::N, Aleph::OLhashTable< Key, Cmp >::table, Aleph::OLhashTable< Key, Cmp >::upper_alpha, and Aleph::OLhashTable< Key, Cmp >::with_resize.

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

◆ test_resize()

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

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

inlineprivate

Definition at line 549 of file tpl_olhash.H.

◆ update_stat_len()

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

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

inlinestaticprivate

Definition at line 549 of file tpl_olhash.H.

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

Friends And Related Symbol Documentation

◆ OhashCommon< OLhashTable< Key, Cmp >, Key >

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

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

friend

Definition at line 1 of file tpl_olhash.H.

Member Data Documentation

◆ cmp

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

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

protected

Definition at line 211 of file tpl_olhash.H.

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

◆ hash_fct

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

Hash_Fct Aleph::OLhashTable< Key, Cmp >::hash_fct

private

Definition at line 215 of file tpl_olhash.H.

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

◆ len

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

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

protected

Definition at line 208 of file tpl_olhash.H.

◆ lower_alpha

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

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

protected

Definition at line 209 of file tpl_olhash.H.

Referenced by Aleph::OLhashTable< Key, Cmp >::operator=(), and Aleph::OLhashTable< Key, Cmp >::swap().

◆ N

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

size_t Aleph::OLhashTable< Key, Cmp >::N = 0

Definition at line 204 of file tpl_olhash.H.

Referenced by Aleph::OLhashTable< Key, Cmp >::allocate_bucket(), Aleph::OLhashTable< Key, Cmp >::deallocate_bucket(), Aleph::OLhashTable< Key, Cmp >::hard_allocate_bucket(), Aleph::OLhashTable< Key, Cmp >::operator=(), Aleph::OLhashTable< Key, Cmp >::remove(), and Aleph::OLhashTable< Key, Cmp >::swap().

◆ table

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

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

Definition at line 203 of file tpl_olhash.H.

◆ upper_alpha

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

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

protected

Definition at line 210 of file tpl_olhash.H.

Referenced by Aleph::OLhashTable< Key, Cmp >::operator=(), and Aleph::OLhashTable< Key, Cmp >::swap().

◆ with_resize

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

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

private

Definition at line 216 of file tpl_olhash.H.

Referenced by Aleph::OLhashTable< Key, Cmp >::swap().

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

tpl_olhash.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

◆ Status

Constructor & Destructor Documentation

◆ OLhashTable() [1/10]

◆ OLhashTable() [2/10]

◆ OLhashTable() [3/10]

◆ OLhashTable() [4/10]

◆ OLhashTable() [5/10]

◆ OLhashTable() [6/10]

◆ OLhashTable() [7/10]

◆ OLhashTable() [8/10]

◆ ~OLhashTable()

◆ OLhashTable() [9/10]

◆ OLhashTable() [10/10]

Member Function Documentation

◆ allocate_bucket()

◆ cleanup_deleted_chain()

◆ deallocate_bucket()

◆ get_compare() [1/2]

◆ get_compare() [2/2]

◆ get_hash_fct()

◆ hard_allocate_bucket()

◆ is_valid_bucket()

◆ key_to_bucket()

◆ next_index()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ prev_index()

◆ remove()

◆ search()

◆ set_hash_fct() [1/2]

◆ set_hash_fct() [2/2]

◆ stats()

◆ swap()

◆ test_resize()

◆ update_stat_len()

Friends And Related Symbol Documentation

◆ OhashCommon< OLhashTable< Key, Cmp >, Key >

Member Data Documentation

◆ cmp

◆ hash_fct

◆ len

◆ lower_alpha

◆ N

◆ table

◆ upper_alpha

◆ with_resize