A compact hash table implementation. More...

#include <gim_hash_table.h>

Public Member Functions
	gim_hash_table (GUINT reserve_size=GIM_DEFAULT_HASH_TABLE_SIZE, GUINT node_size=GIM_DEFAULT_HASH_TABLE_NODE_SIZE, GUINT min_hash_table_size=GIM_INVALID_HASH)
	~gim_hash_table ()
bool	is_hash_table ()
bool	is_sorted ()
bool	sort ()
bool	switch_to_hashtable ()
bool	switch_to_sorted_array ()
bool	check_for_switching_to_hashtable ()
	If the container reaches the.
void	set_sorted (bool value)
GUINT	size () const
	Retrieves the amount of keys.
GUINT	get_key (GUINT index) const
	Retrieves the hash key.
T *	get_value_by_index (GUINT index)
	Retrieves the value by index.
const T &	operator[] (GUINT index) const
T &	operator[] (GUINT index)
GUINT	find (GUINT hashkey)
	Finds the index of the element with the key.
T *	get_value (GUINT hashkey)
	Retrieves the value associated with the index.
bool	erase_by_index (GUINT index)
bool	erase_by_index_unsorted (GUINT index)
bool	erase_by_key (GUINT hashkey)
void	clear ()
GUINT	insert (GUINT hashkey, const T &element)
	Insert an element into the hash.
GUINT	insert_override (GUINT hashkey, const T &element)
	Insert an element into the hash, and could overrite an existing object with the same hash.
GUINT	insert_unsorted (GUINT hashkey, const T &element)
	Insert an element into the hash,But if this container is a sorted array, this inserts it unsorted.

Protected Types
typedef GIM_HASH_TABLE_NODE< T >	_node_type

Protected Member Functions
GUINT	_find_cell (GUINT hashkey)
	Returns the cell index.
GUINT	_find_avaliable_cell (GUINT hashkey)
	Find the avaliable cell for the hashkey, and return an existing cell if it has the same hash key.
void	_reserve_table_memory (GUINT newtablesize)
	reserves the memory for the hash table.
void	_invalidate_keys ()
void	_clear_table_memory ()
	Clear all memory for the hash table.
void	_rehash ()
	Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys.
void	_resize_table (GUINT newsize)
	Resize hash table indices.
void	_destroy ()
	Destroy hash table memory.
GUINT	_assign_hash_table_cell (GUINT hashkey)
	Finds an avaliable hash table cell, and resizes the table if there isn't space.
bool	_erase_by_index_hash_table (GUINT index)
	erase by index in hash table
bool	_erase_hash_table (GUINT hashkey)
	erase by key in hash table
GUINT	_insert_hash_table (GUINT hashkey, const T &value)
	insert an element in hash table
GUINT	_insert_hash_table_replace (GUINT hashkey, const T &value)
	insert an element in hash table.
bool	_erase_sorted (GUINT index)
	Sorted array data management. The hash table has the indices to the corresponding m_nodes array.
bool	_erase_unsorted (GUINT index)
	faster, but unsorted
void	_insert_in_pos (GUINT hashkey, const T &value, GUINT pos)
	Insert in position ordered.
GUINT	_insert_sorted (GUINT hashkey, const T &value)
	Insert an element in an ordered array.
GUINT	_insert_sorted_replace (GUINT hashkey, const T &value)
GUINT	_insert_unsorted (GUINT hashkey, const T &value)
	Fast insertion in m_nodes array.

Protected Attributes
gim_array< _node_type >	m_nodes
	The nodes.
bool	m_sorted
GUINT *	m_hash_table
	Hash table data management. The hash table has the indices to the corresponding m_nodes array.
GUINT	m_table_size
GUINT	m_node_size
GUINT	m_min_hash_table_size

Detailed Description

template<class T>
class gim_hash_table< T >

A compact hash table implementation.

A memory aligned compact hash table that coud be treated as an array. It could be a simple sorted array without the overhead of the hash key bucked, or could be a formely hash table with an array of keys. You can use switch_to_hashtable() and switch_to_sorted_array for saving space or increase speed.

if node_size = 0, then this container becomes a simple sorted array allocator. reserve_size is used for reserve memory in m_nodes. When the array size reaches the size equivalent to 'min_hash_table_size', then it becomes a hash table by calling check_for_switching_to_hashtable.
If node_size != 0, then this container becomes a hash table for ever

Definition at line 176 of file gim_hash_table.h.

Member Typedef Documentation

◆ _node_type

template<class T>

typedef GIM_HASH_TABLE_NODE<T> gim_hash_table< T >::_node_type

protected

Definition at line 179 of file gim_hash_table.h.

Constructor & Destructor Documentation

◆ gim_hash_table()

template<class T>

gim_hash_table< T >::gim_hash_table	(	GUINT	reserve_size = GIM_DEFAULT_HASH_TABLE_SIZE,
		GUINT	node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE,
		GUINT	min_hash_table_size = GIM_INVALID_HASH )

inline

if node_size = 0, then this container becomes a simple sorted array allocator. reserve_size is used for reserve memory in m_nodes. When the array size reaches the size equivalent to 'min_hash_table_size', then it becomes a hash table by calling check_for_switching_to_hashtable. If node_size != 0, then this container becomes a hash table for ever

Definition at line 544 of file gim_hash_table.h.

References _invalidate_keys(), _reserve_table_memory(), GIM_DEFAULT_HASH_TABLE_NODE_SIZE, GIM_DEFAULT_HASH_TABLE_SIZE, GIM_INVALID_HASH, GUINT, m_hash_table, m_min_hash_table_size, m_node_size, m_nodes, m_sorted, and m_table_size.

◆ ~gim_hash_table()

template<class T>

gim_hash_table< T >::~gim_hash_table ( )

inline

Definition at line 575 of file gim_hash_table.h.

References _destroy().

Member Function Documentation

◆ _assign_hash_table_cell()

template<class T>

GUINT gim_hash_table< T >::_assign_hash_table_cell ( GUINT hashkey )

inlineprotected

Finds an avaliable hash table cell, and resizes the table if there isn't space.

Definition at line 324 of file gim_hash_table.h.

References _find_avaliable_cell(), _resize_table(), btAssert, GIM_INVALID_HASH, GUINT, and m_table_size.

Referenced by _insert_hash_table(), and _insert_hash_table_replace().

◆ _clear_table_memory()

template<class T>

void gim_hash_table< T >::_clear_table_memory ( )

inlineprotected

Clear all memory for the hash table.

Definition at line 268 of file gim_hash_table.h.

References gim_free(), m_hash_table, and m_table_size.

Referenced by _destroy(), _resize_table(), and switch_to_sorted_array().

◆ _destroy()

template<class T>

void gim_hash_table< T >::_destroy ( )

inlineprotected

Destroy hash table memory.

Definition at line 317 of file gim_hash_table.h.

References _clear_table_memory(), and m_hash_table.

Referenced by ~gim_hash_table().

◆ _erase_by_index_hash_table()

template<class T>

bool gim_hash_table< T >::_erase_by_index_hash_table ( GUINT index )

inlineprotected

erase by index in hash table

Definition at line 339 of file gim_hash_table.h.

References _erase_unsorted(), _find_cell(), btAssert, GIM_INVALID_HASH, GUINT, m_hash_table, and m_nodes.

Referenced by erase_by_index(), and erase_by_index_unsorted().

◆ _erase_hash_table()

template<class T>

bool gim_hash_table< T >::_erase_hash_table ( GUINT hashkey )

inlineprotected

erase by key in hash table

Definition at line 357 of file gim_hash_table.h.

References _erase_unsorted(), _find_cell(), GIM_INVALID_HASH, GUINT, and m_hash_table.

Referenced by erase_by_key().

◆ _erase_sorted()

template<class T>

bool gim_hash_table< T >::_erase_sorted ( GUINT index )

inlineprotected

Sorted array data management. The hash table has the indices to the corresponding m_nodes array.

Definition at line 430 of file gim_hash_table.h.

References GUINT, m_nodes, and m_sorted.

Referenced by erase_by_index(), and erase_by_key().

◆ _erase_unsorted()

template<class T>

bool gim_hash_table< T >::_erase_unsorted ( GUINT index )

inlineprotected

faster, but unsorted

Definition at line 439 of file gim_hash_table.h.

References _find_cell(), btAssert, GIM_INVALID_HASH, GUINT, m_hash_table, m_nodes, and m_sorted.

Referenced by _erase_by_index_hash_table(), _erase_hash_table(), erase_by_index(), and erase_by_index_unsorted().

◆ _find_avaliable_cell()

template<class T>

GUINT gim_hash_table< T >::_find_avaliable_cell ( GUINT hashkey )

inlineprotected

Find the avaliable cell for the hashkey, and return an existing cell if it has the same hash key.

Definition at line 213 of file gim_hash_table.h.

References GIM_INVALID_HASH, GUINT, m_hash_table, m_node_size, m_nodes, and m_table_size.

Referenced by _assign_hash_table_cell(), and _rehash().

◆ _find_cell()

template<class T>

GUINT gim_hash_table< T >::_find_cell ( GUINT hashkey )

inlineprotected

Returns the cell index.

Definition at line 194 of file gim_hash_table.h.

References GIM_INVALID_HASH, GUINT, m_hash_table, m_node_size, m_nodes, and m_table_size.

Referenced by _erase_by_index_hash_table(), _erase_hash_table(), _erase_unsorted(), and find().

◆ _insert_hash_table()

template<class T>

GUINT gim_hash_table< T >::_insert_hash_table	(	GUINT	hashkey,
		const T &	value )

inlineprotected

insert an element in hash table

If the element exists, this won't insert the element

Returns: the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted If so, the element has been inserted at the last position of the array.

Definition at line 377 of file gim_hash_table.h.

References _assign_hash_table_cell(), _insert_unsorted(), GIM_INVALID_HASH, GUINT, m_hash_table, m_nodes, and T.

Referenced by insert(), and insert_unsorted().

◆ _insert_hash_table_replace()

template<class T>

GUINT gim_hash_table< T >::_insert_hash_table_replace	(	GUINT	hashkey,
		const T &	value )

inlineprotected

insert an element in hash table.

If the element exists, this replaces the element.

Returns: the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted If so, the element has been inserted at the last position of the array.

Definition at line 404 of file gim_hash_table.h.

References _assign_hash_table_cell(), _insert_unsorted(), GIM_INVALID_HASH, GUINT, m_hash_table, m_nodes, and T.

Referenced by insert_override().

◆ _insert_in_pos()

template<class T>

void gim_hash_table< T >::_insert_in_pos	(	GUINT	hashkey,
		const T &	value,
		GUINT	pos )

inlineprotected

Insert in position ordered.

Also checks if it is needed to transform this container to a hash table, by calling check_for_switching_to_hashtable

Definition at line 465 of file gim_hash_table.h.

References check_for_switching_to_hashtable(), GUINT, m_nodes, pos, and T.

Referenced by _insert_sorted(), and _insert_sorted_replace().

◆ _insert_sorted()

template<class T>

GUINT gim_hash_table< T >::_insert_sorted	(	GUINT	hashkey,
		const T &	value )

inlineprotected

Insert an element in an ordered array.

Definition at line 472 of file gim_hash_table.h.

References _insert_in_pos(), gim_binary_search_ex(), GIM_INVALID_HASH, GUINT, m_nodes, ptr, size(), and T.

Referenced by insert().

◆ _insert_sorted_replace()

template<class T>

GUINT gim_hash_table< T >::_insert_sorted_replace	(	GUINT	hashkey,
		const T &	value )

inlineprotected

Definition at line 501 of file gim_hash_table.h.

References _insert_in_pos(), gim_binary_search_ex(), GIM_INVALID_HASH, GUINT, m_nodes, ptr, size(), and T.

Referenced by insert_override().

◆ _insert_unsorted()

template<class T>

GUINT gim_hash_table< T >::_insert_unsorted	(	GUINT	hashkey,
		const T &	value )

inlineprotected

Fast insertion in m_nodes array.

Definition at line 530 of file gim_hash_table.h.

References GIM_INVALID_HASH, GUINT, m_nodes, m_sorted, and T.

Referenced by _insert_hash_table(), _insert_hash_table_replace(), insert(), insert_override(), and insert_unsorted().

◆ _invalidate_keys()

template<class T>

void gim_hash_table< T >::_invalidate_keys ( )

inlineprotected

Definition at line 258 of file gim_hash_table.h.

References GIM_INVALID_HASH, GUINT, i, m_hash_table, m_node_size, and m_table_size.

Referenced by _rehash(), and gim_hash_table().

◆ _rehash()

template<class T>

void gim_hash_table< T >::_rehash ( )

inlineprotected

Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys.

Definition at line 277 of file gim_hash_table.h.

References _find_avaliable_cell(), _invalidate_keys(), btAssert, GIM_INVALID_HASH, GUINT, i, m_hash_table, GIM_HASH_TABLE_NODE< T >::m_key, and m_nodes.

Referenced by _resize_table(), and sort().

◆ _reserve_table_memory()

template<class T>

void gim_hash_table< T >::_reserve_table_memory ( GUINT newtablesize )

inlineprotected

reserves the memory for the hash table.

Precondition: hash table must be empty

Postcondition: reserves the memory for the hash table, an initializes all elements to GIM_INVALID_HASH.

Definition at line 244 of file gim_hash_table.h.

References gim_alloc(), gim_next_prime(), GUINT, m_hash_table, m_node_size, and m_table_size.

Referenced by _resize_table(), and gim_hash_table().

◆ _resize_table()

template<class T>

void gim_hash_table< T >::_resize_table ( GUINT newsize )

inlineprotected

Resize hash table indices.

Definition at line 306 of file gim_hash_table.h.

References _clear_table_memory(), _rehash(), _reserve_table_memory(), and GUINT.

Referenced by _assign_hash_table_cell(), check_for_switching_to_hashtable(), and switch_to_hashtable().

◆ check_for_switching_to_hashtable()

template<class T>

bool gim_hash_table< T >::check_for_switching_to_hashtable ( )

inline

If the container reaches the.

Definition at line 633 of file gim_hash_table.h.

References _resize_table(), GIM_DEFAULT_HASH_TABLE_NODE_SIZE, m_min_hash_table_size, m_node_size, and m_nodes.

Referenced by _insert_in_pos().

◆ clear()

template<class T>

void gim_hash_table< T >::clear ( )

inline

Definition at line 792 of file gim_hash_table.h.

References GIM_INVALID_HASH, GUINT, i, m_hash_table, m_node_size, m_nodes, m_sorted, and m_table_size.

◆ erase_by_index()

template<class T>

bool gim_hash_table< T >::erase_by_index ( GUINT index )

inline

Definition at line 732 of file gim_hash_table.h.

References _erase_by_index_hash_table(), _erase_sorted(), _erase_unsorted(), GUINT, is_sorted(), m_hash_table, and m_nodes.

◆ erase_by_index_unsorted()

template<class T>

bool gim_hash_table< T >::erase_by_index_unsorted ( GUINT index )

inline

Definition at line 754 of file gim_hash_table.h.

References _erase_by_index_hash_table(), _erase_unsorted(), GUINT, m_hash_table, and m_nodes.

◆ erase_by_key()

template<class T>

bool gim_hash_table< T >::erase_by_key ( GUINT hashkey )

inline

Definition at line 772 of file gim_hash_table.h.

References _erase_hash_table(), _erase_sorted(), find(), GIM_INVALID_HASH, GUINT, is_sorted(), m_hash_table, and size().

◆ find()

template<class T>

GUINT gim_hash_table< T >::find ( GUINT hashkey )

inline

Finds the index of the element with the key.

Returns: the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted If so, the element has been inserted at the last position of the array.

Definition at line 690 of file gim_hash_table.h.

References _find_cell(), gim_binary_search_ex(), GIM_INVALID_HASH, GUINT, m_hash_table, m_nodes, m_sorted, and ptr.

Referenced by erase_by_key(), and get_value().

◆ get_key()

template<class T>

GUINT gim_hash_table< T >::get_key ( GUINT index ) const

inline

Retrieves the hash key.

Definition at line 662 of file gim_hash_table.h.

References GUINT, and m_nodes.

◆ get_value()

template<class T>

T * gim_hash_table< T >::get_value ( GUINT hashkey )

inline

Retrieves the value associated with the index.

Returns: the found element, or null

Definition at line 723 of file gim_hash_table.h.

References find(), GIM_INVALID_HASH, GUINT, m_nodes, and T.

◆ get_value_by_index()

template<class T>

T * gim_hash_table< T >::get_value_by_index ( GUINT index )

inline

Retrieves the value by index.

Definition at line 670 of file gim_hash_table.h.

References GUINT, m_nodes, and T.

◆ insert()

template<class T>

GUINT gim_hash_table< T >::insert	(	GUINT	hashkey,
		const T &	element )

inline

Insert an element into the hash.

Returns: If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position of the existing element.

Definition at line 812 of file gim_hash_table.h.

References _insert_hash_table(), _insert_sorted(), _insert_unsorted(), element, GUINT, is_sorted(), m_hash_table, and T.

◆ insert_override()

template<class T>

GUINT gim_hash_table< T >::insert_override	(	GUINT	hashkey,
		const T &	element )

inline

Insert an element into the hash, and could overrite an existing object with the same hash.

Returns: If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position of the replaced element.

Definition at line 830 of file gim_hash_table.h.

References _insert_hash_table_replace(), _insert_sorted_replace(), _insert_unsorted(), element, GUINT, is_sorted(), m_hash_table, m_nodes, and T.

◆ insert_unsorted()

template<class T>

GUINT gim_hash_table< T >::insert_unsorted	(	GUINT	hashkey,
		const T &	element )

inline

Insert an element into the hash,But if this container is a sorted array, this inserts it unsorted.

Definition at line 847 of file gim_hash_table.h.

References _insert_hash_table(), _insert_unsorted(), element, GUINT, m_hash_table, and T.

◆ is_hash_table()

template<class T>

bool gim_hash_table< T >::is_hash_table ( )

inline

Definition at line 580 of file gim_hash_table.h.

References m_hash_table.

◆ is_sorted()

template<class T>

bool gim_hash_table< T >::is_sorted ( )

inline

Definition at line 586 of file gim_hash_table.h.

References m_sorted, and size().

Referenced by erase_by_index(), erase_by_key(), insert(), insert_override(), and sort().

◆ operator[]() [1/2]

template<class T>

T & gim_hash_table< T >::operator[] ( GUINT index )

inline

Definition at line 680 of file gim_hash_table.h.

References GUINT, m_nodes, and T.

◆ operator[]() [2/2]

template<class T>

const T & gim_hash_table< T >::operator[] ( GUINT index ) const

inline

Definition at line 675 of file gim_hash_table.h.

References GUINT, m_nodes, and T.

◆ set_sorted()

template<class T>

void gim_hash_table< T >::set_sorted ( bool value )

inline

Definition at line 650 of file gim_hash_table.h.

References m_sorted.

◆ size()

template<class T>

GUINT gim_hash_table< T >::size ( ) const

inline

Retrieves the amount of keys.

Definition at line 656 of file gim_hash_table.h.

References GUINT, and m_nodes.

Referenced by _insert_sorted(), _insert_sorted_replace(), erase_by_key(), and is_sorted().

◆ sort()

template<class T>

bool gim_hash_table< T >::sort ( )

inline

Definition at line 592 of file gim_hash_table.h.

References _rehash(), gim_sort_hash_node_array(), GUINT, is_sorted(), m_hash_table, m_nodes, m_sorted, and ptr.

Referenced by switch_to_sorted_array().

◆ switch_to_hashtable()

template<class T>

bool gim_hash_table< T >::switch_to_hashtable ( )

inline

Definition at line 609 of file gim_hash_table.h.

References _resize_table(), GIM_DEFAULT_HASH_TABLE_NODE_SIZE, GIM_DEFAULT_HASH_TABLE_SIZE, m_hash_table, m_node_size, and m_nodes.

◆ switch_to_sorted_array()

template<class T>

bool gim_hash_table< T >::switch_to_sorted_array ( )

inline

Definition at line 625 of file gim_hash_table.h.

References _clear_table_memory(), m_hash_table, and sort().

Member Data Documentation

◆ m_hash_table

template<class T>

GUINT* gim_hash_table< T >::m_hash_table

protected

Hash table data management. The hash table has the indices to the corresponding m_nodes array.

Definition at line 188 of file gim_hash_table.h.

Referenced by _clear_table_memory(), _destroy(), _erase_by_index_hash_table(), _erase_hash_table(), _erase_unsorted(), _find_avaliable_cell(), _find_cell(), _insert_hash_table(), _insert_hash_table_replace(), _invalidate_keys(), _rehash(), _reserve_table_memory(), clear(), erase_by_index(), erase_by_index_unsorted(), erase_by_key(), find(), gim_hash_table(), insert(), insert_override(), insert_unsorted(), is_hash_table(), sort(), switch_to_hashtable(), and switch_to_sorted_array().

◆ m_min_hash_table_size

template<class T>

GUINT gim_hash_table< T >::m_min_hash_table_size

protected

Definition at line 191 of file gim_hash_table.h.

Referenced by check_for_switching_to_hashtable(), and gim_hash_table().

◆ m_node_size

template<class T>

GUINT gim_hash_table< T >::m_node_size

protected

Definition at line 190 of file gim_hash_table.h.

Referenced by _find_avaliable_cell(), _find_cell(), _invalidate_keys(), _reserve_table_memory(), check_for_switching_to_hashtable(), clear(), gim_hash_table(), and switch_to_hashtable().

◆ m_nodes

template<class T>

gim_array<_node_type> gim_hash_table< T >::m_nodes

protected

◆ m_sorted

template<class T>

bool gim_hash_table< T >::m_sorted

protected

Definition at line 185 of file gim_hash_table.h.

Referenced by _erase_sorted(), _erase_unsorted(), _insert_unsorted(), clear(), find(), gim_hash_table(), is_sorted(), set_sorted(), and sort().

◆ m_table_size

template<class T>

GUINT gim_hash_table< T >::m_table_size

protected

Definition at line 189 of file gim_hash_table.h.

Referenced by _assign_hash_table_cell(), _clear_table_memory(), _find_avaliable_cell(), _find_cell(), _invalidate_keys(), _reserve_table_memory(), clear(), and gim_hash_table().

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

gim_hash_table.h

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ _node_type

Constructor & Destructor Documentation

◆ gim_hash_table()

◆ ~gim_hash_table()

Member Function Documentation

◆ _assign_hash_table_cell()

◆ _clear_table_memory()

◆ _destroy()

◆ _erase_by_index_hash_table()

◆ _erase_hash_table()

◆ _erase_sorted()

◆ _erase_unsorted()

◆ _find_avaliable_cell()

◆ _find_cell()

◆ _insert_hash_table()

◆ _insert_hash_table_replace()

◆ _insert_in_pos()

◆ _insert_sorted()

◆ _insert_sorted_replace()

◆ _insert_unsorted()

◆ _invalidate_keys()

◆ _rehash()

◆ _reserve_table_memory()

◆ _resize_table()

◆ check_for_switching_to_hashtable()

◆ clear()

◆ erase_by_index()

◆ erase_by_index_unsorted()

◆ erase_by_key()

◆ find()

◆ get_key()

◆ get_value()

◆ get_value_by_index()

◆ insert()

◆ insert_override()

◆ insert_unsorted()

◆ is_hash_table()

◆ is_sorted()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ set_sorted()

◆ size()

◆ sort()

◆ switch_to_hashtable()

◆ switch_to_sorted_array()

Member Data Documentation

◆ m_hash_table

◆ m_min_hash_table_size

◆ m_node_size

◆ m_nodes

◆ m_sorted

◆ m_table_size