hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ > Class Template Reference

#include <hxhash_table.hpp>

Classes
class	const_iterator
class	iterator

Public Types
using	node_t = node_t_
using	key_t = typename node_t_::key_t

Public Member Functions
	hxhash_table (deleter_t_ deleter_=deleter_t_())
	~hxhash_table (void)
const_iterator	begin (void) const
iterator	begin (void)
hxsize_t	bucket_count (void) const
const_iterator	cbegin (void) const
const_iterator	cend (void) const
template<typename deleter_u_>
void	clear (deleter_u_ &&deleter_) noexcept
void	clear (void) noexcept
hxsize_t	count (const typename node_t_::key_t &key_) const
template<hxsystem_allocator_t allocator_ = hxsystem_allocator_current, hxalignment_t align_ = hxalignment, bool multi_ = multi_t_, class... args_t_>
hxenable_if_t< multi_, iterator >	emplace (args_t_ &&... args_) noexcept
bool	empty (void) const
const_iterator	end (void) const
iterator	end (void)
template<typename deleter_u_>
hxsize_t	erase (const typename node_t_::key_t &key_, deleter_u_ &&deleter_) noexcept
hxsize_t	erase (const typename node_t_::key_t &key_) noexcept
iterator	erase (const const_iterator &it_) noexcept
hxptr< node_t_, deleter_t_ >	extract (const typename node_t_::key_t &key_) noexcept
node_t_ *	find (const typename node_t_::key_t &key_, const node_t_ *previous_=0)
const node_t_ *	find (const typename node_t_::key_t &key_, const node_t_ *previous_=0) const
const deleter_t_ &	deleter (void) const
deleter_t_ &	deleter (void)
iterator	insert (node_t_ *ptr_) noexcept
template<typename deleter_u_>
iterator	insert (hxptr< node_t_, deleter_u_ > &&ptr_) noexcept
float	load_factor (void) const
hxsize_t	load_max (void) const
void	release_all (void)
hxsize_t	release_key (const typename node_t_::key_t &key_)
hxptr< node_t_, deleter_t_ >	replace (node_t_ *ptr_) noexcept
void	set_size_bits (hxhash_t bits_)
hxsize_t	size (void) const
template<hxsystem_allocator_t allocator_ = hxsystem_allocator_current, hxalignment_t align_ = hxalignment, bool multi_ = multi_t_, class... args_t_>
hxenable_if_t<!multi_, iterator >	try_emplace (const typename node_t_::key_t &key_, args_t_ &&... args_) noexcept

Detailed Description

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>
class hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >

hxhash_table - A hash table that operates without reallocating memory or copying data.

Each bucket uses an embedded singly-linked list. This design tries to use a sparse table that allocates the maximum amount of memory upfront and then uses a high quality hash instead of relying on linear probing for cache efficiency. Hash tables can act as either an unordered map or an unordered set and support operations that allow for unique or duplicate keys.

Any node T using key K will work as long as it has the following fields and K has an operator== or an hxkey_equal overload.

class T {
  using key_t = K;               // Tell the hash table what key to use.
  T* hash_next() const;          // Next node in hxhash_table's embedded linked list.
  void set_hash_next(node_t_*);        // Sets the next node in the embedded linked list.
  const key_t& hash_key() const; // Returns key constructed with.
  hxhash_t hash_value() const;   // Returns hash of key constructed with.
};

hxhash_table_set_node and hxhash_table_map_node are provided and recommended as replacements for std::unordered_set and std::unordered_map. Custom key types will require either an operator== or an hxkey_equal overload and will require an hxkey_hash overload.

They might be used as follows:

// An unordered set of allowed or blocked internet addresses.
using ipv6_set_t = hxhash_table<hxhash_table_set_node<ipv6_address_t>>;
 
// A fixed-size unordered map of material identifiers to material
// properties. Missing materials can be safely resolved.
using material_db_t = hxhash_table<hxhash_table_map_node<material_id_t,
                                 material_t>, hxdefault_delete, true, 1024>;

hx/hxhash_table_nodes.hpp also provides specializations of the hxhash_table::node_t template parameter for integers and strings.

• node_t : Must implement the interface/concept described above.
• deleter_t : A class type invoked as deleter(T*) to free the owned pointer. See also hxdo_not_delete.
• multi_t : When falseand a node with an equal key already exists, insertion into the list will fail when a node with the same key already exists.
• table_size_bits : If non-zero, table_size_bits configures the hash table size to 2^table_size_bits. Otherwise use set_size_bits to to configure hash bits dynamically.

Member Typedef Documentation

key_t

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

using hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::key_t = typename node_t_::key_t

node_t

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

using hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::node_t = node_t_

Constructor & Destructor Documentation

hxhash_table()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::hxhash_table ( deleter_t_ deleter_ = deleter_t_() )

explicit

Constructs an empty hash table with a capacity of 2^table_size_bits and an optional deleter instance.

• deleter : Callable with signature bool deleter(node_t_*).

~hxhash_table()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::~hxhash_table ( void )

inline

Destructs the hash table and deletes all resources.

Member Function Documentation

begin() [1/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

iterator hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::begin ( void )

inline

Returns an iterator pointing to the beginning of the hash table.

begin() [2/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

const_iterator hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::begin ( void ) const

inline

Returns a const iterator pointing to the beginning of the hash table.

bucket_count()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

hxsize_t hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::bucket_count ( void ) const

inline

Returns the number of buckets in the hash table.

cbegin()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

const_iterator hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::cbegin ( void ) const

inline

Returns a const iterator pointing to the beginning of the hash table.

cend()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

const_iterator hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::cend ( void ) const

inline

Returns a const iterator pointing to the end of the hash table.

clear() [1/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

template<typename deleter_u_>

void hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::clear ( deleter_u_ && deleter_ )

noexcept

Removes all nodes and if deleter is true then calls deleter() on every node.

• deleter : Callable with signature bool deleter(node_t_*).

clear() [2/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

void hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::clear ( void )

inlinenoexcept

Removes all nodes and calls the stored deleter on every node.

count()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

hxsize_t hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::count

(

const typename node_t_::key_t &

key_

)

const

Counts the number of nodes with the given key.

• key : The key to count occurrences of in the hash table.

deleter() [1/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

deleter_t_ & hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::deleter

(

void

)

Returns a reference to the stored deleter.

deleter() [2/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

const deleter_t_ & hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::deleter

(

void

)

const

Returns a const reference to the stored deleter.

emplace()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

template<hxsystem_allocator_t allocator_ = hxsystem_allocator_current, hxalignment_t align_ = hxalignment, bool multi_ = multi_t_, class... args_t_>

hxenable_if_t< multi_, iterator > hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::emplace ( args_t_ &&... args_ )

noexcept

emplace - Returns an iterator to the node constructed with hxnew.

The table must have multi_t set to true.

• allocator : The memory manager ID to use for allocation. Defaults to hxsystem_allocator_current.
• align : Alignment to use when allocating new pointers. Defaults to hxalignment.
• args : Arguments forwarded to the node constructor.

empty()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

bool hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::empty ( void ) const

inline

Checks if the hash table is empty.

end() [1/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

iterator hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::end ( void )

inline

Returns an iterator pointing to the end of the hash table.

end() [2/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

const_iterator hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::end ( void ) const

inline

Returns a const iterator pointing to the end of the hash table.

erase() [1/3]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

iterator hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::erase ( const const_iterator & it_ )

noexcept

Removes the node_t referenced by it without invoking the deleter.

Returns an iterator to the node following it, or end().

• it : A valid iterator into this hash table.

erase() [2/3]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

hxsize_t hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::erase ( const typename node_t_::key_t & key_ )

noexcept

Removes and calls the stored deleter on nodes with an equivalent key.

• key : The key to search for and remove from the hash table.

erase() [3/3]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

template<typename deleter_u_>

hxsize_t hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::erase ( const typename node_t_::key_t & key_, deleter_u_ && deleter_ )

noexcept

Releases all nodes matching key and calls deleter on every node.

Returns the number of nodes released. Deleter can be functions with signature void deleter(node_t*) and callables supporting operator()(node_t*) and with an operator bool. e.g., a free list or a null pointer.

• key : The key to search for and remove from the hash table.
• deleter : Callable with signature bool deleter(node_t_*).

extract()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

hxptr< node_t_, deleter_t_ > hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::extract ( const typename node_t_::key_t & key_ )

noexcept

extract - Returns an hxptr owning the first node_t with the given key, or an empty hxptr if no matching node is found.

• key : The key to search for and remove from the hash table.

find() [1/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

node_t_ * hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::find	(	const typename node_t_::key_t &	key_,
		const node_t_ *	previous_ = 0 )

Returns a node_t matching key if any.

If previous is non-null it must be a node previously returned from find() with the same key and that has not been removed. Then find() will return a subsequent node if any. The previous object is non-const as it may be modified.

• key : The key to search for in the hash table.
• previous : A previously found node_t with the same key, or hxnull.

find() [2/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

const node_t_ * hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::find	(	const typename node_t_::key_t &	key_,
		const node_t_ *	previous_ = 0 ) const

const version of find.

• key : The key to search for in the hash table.
• previous : A previously found node_t with the same key, or hxnull.

insert() [1/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

template<typename deleter_u_>

iterator hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::insert ( hxptr< node_t_, deleter_u_ > && ptr_ )

noexcept

insert - Returns an iterator to the inserted node.

When multi_t is false and a node with an equal key already exists, returns an iterator to the existing node and invokes the deleter on ptr. ptr must not be null.

• ptr : The hxptr owning the node to insert.

insert() [2/2]

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

iterator hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::insert ( node_t_ * ptr_ )

noexcept

insert - Returns an iterator to the inserted node.

When multi_t is false and a node with an equal key already exists, invokes deleter_t on ptr and returns an iterator to the existing node. ptr must not be null.

• ptr : The node to insert.

load_factor()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

float hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::load_factor

(

void

)

const

Returns the average number of nodes per bucket.

load_max()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

hxsize_t hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::load_max

(

void

)

const

Returns the size of the largest bucket.

release_all()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

void hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::release_all

(

void

)

Clears the hash table without deleting any nodes.

release_key()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

hxsize_t hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::release_key

(

const typename node_t_::key_t &

key_

)

Removes all nodes matching the given key without deleting them.

• key : The key to search for and release from the hash table.

replace()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

hxptr< node_t_, deleter_t_ > hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::replace ( node_t_ * ptr_ )

noexcept

replace - Replaces the first node_t matching ptr's key, if any, with ptr and returns an hxptr owning the replaced node.

Returns an empty hxptr and inserts ptr as a new node if no match is found. Avoids the extra lookup an erase followed by insert would require. ptr must not be null.

• ptr : The node to insert in place of any matching node.

set_size_bits()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

void hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::set_size_bits

(

hxhash_t

bits_

)

Sets the number of hash bits and allocate memory for the table.

(only for dynamic capacity).

• bits : The number of hash bits to set for the hash table.

size()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

hxsize_t hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::size ( void ) const

inline

Returns the number of elements in the hash table.

try_emplace()

template<hxhash_table_concept_ node_t_, typename deleter_t_ = hxdefault_delete, bool multi_t_ = false, uint32_t table_size_bits_ = hxallocator_dynamic_capacity>

template<hxsystem_allocator_t allocator_ = hxsystem_allocator_current, hxalignment_t align_ = hxalignment, bool multi_ = multi_t_, class... args_t_>

hxenable_if_t<!multi_, iterator > hxhash_table< node_t_, deleter_t_, multi_t_, table_size_bits_ >::try_emplace ( const typename node_t_::key_t & key_, args_t_ &&... args_ )

noexcept

try_emplace - Returns an iterator to the node if it was inserted, or an iterator to the existing node if a node with an equal key already exists.

The table must have multi_t set to false.

• allocator : The memory manager ID to use for allocation. Defaults to hxsystem_allocator_current.
• align : Alignment to use when allocating new pointers. Defaults to hxalignment.
• key : The key the node will have once constructed.
• args : Arguments forwarded to the node constructor.

---

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

• include/hx/hxhash_table.hpp