A compact hash table implementation. More...

#include <gim_hash_table.h>

Collaboration diagram for gim_hash_table< T >:

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

void	set_sorted (bool value)

GUINT	size () const
	Retrieves the amount of keys. More...

GUINT	get_key (GUINT index) const
	Retrieves the hash key. More...

T *	get_value_by_index (GUINT index)
	Retrieves the value by index. More...

const T &	operator[] (GUINT index) const

T &	operator[] (GUINT index)

GUINT	find (GUINT hashkey)
	Finds the index of the element with the key. More...

T *	get_value (GUINT hashkey)
	Retrieves the value associated with the index. More...

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

GUINT	insert_override (GUINT hashkey, const T &element)
	Insert an element into the hash, and could overrite an existing object with the same hash. More...

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

Protected Types
typedef GIM_HASH_TABLE_NODE< T >	_node_type

Protected Member Functions
GUINT	_find_cell (GUINT hashkey)
	Returns the cell index. More...

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

void	_reserve_table_memory (GUINT newtablesize)
	reserves the memory for the hash table. More...

void	_invalidate_keys ()

void	_clear_table_memory ()
	Clear all memory for the hash table. More...

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

void	_resize_table (GUINT newsize)
	Resize hash table indices. More...

void	_destroy ()
	Destroy hash table memory. More...

GUINT	_assign_hash_table_cell (GUINT hashkey)
	Finds an avaliable hash table cell, and resizes the table if there isn't space. More...

bool	_erase_by_index_hash_table (GUINT index)
	erase by index in hash table More...

bool	_erase_hash_table (GUINT hashkey)
	erase by key in hash table More...

GUINT	_insert_hash_table (GUINT hashkey, const T &value)
	insert an element in hash table More...

GUINT	_insert_hash_table_replace (GUINT hashkey, const T &value)
	insert an element in hash table. More...

bool	_erase_sorted (GUINT index)
	Sorted array data management. The hash table has the indices to the corresponding m_nodes array. More...

bool	_erase_unsorted (GUINT index)
	faster, but unsorted More...

void	_insert_in_pos (GUINT hashkey, const T &value, GUINT pos)
	Insert in position ordered. More...

GUINT	_insert_sorted (GUINT hashkey, const T &value)
	Insert an element in an ordered array. More...

GUINT	_insert_sorted_replace (GUINT hashkey, const T &value)

GUINT	_insert_unsorted (GUINT hashkey, const T &value)
	Fast insertion in m_nodes array. More...

Protected Attributes
gim_array< _node_type >	m_nodes
	The nodes. More...

bool	m_sorted

GUINT *	m_hash_table
	Hash table data management. The hash table has the indices to the corresponding m_nodes array. More...

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.

◆ ~gim_hash_table()

template<class T >

gim_hash_table< T >::~gim_hash_table ( )

inline

Definition at line 575 of file gim_hash_table.h.

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.

◆ _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.

◆ _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.

◆ _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.

◆ _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.

◆ _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.

◆ _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.

◆ _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.

◆ _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.

◆ _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.

◆ _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.

◆ _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.

◆ _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.

◆ _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.

◆ _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.

◆ _invalidate_keys()

template<class T >

void gim_hash_table< T >::_invalidate_keys ( )

inlineprotected

Definition at line 258 of file gim_hash_table.h.

◆ _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.

◆ _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.

◆ _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.

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

◆ clear()

template<class T >

void gim_hash_table< T >::clear ( )

inline

Definition at line 792 of file gim_hash_table.h.

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

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

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

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

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

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

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

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

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

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

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

◆ is_sorted()

template<class T >

bool gim_hash_table< T >::is_sorted ( )

inline

Definition at line 586 of file gim_hash_table.h.

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

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

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

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

◆ sort()

template<class T >

bool gim_hash_table< T >::sort ( )

inline

Definition at line 592 of file gim_hash_table.h.

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

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

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.

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

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

◆ m_nodes

template<class T >

gim_array<_node_type> gim_hash_table< T >::m_nodes

protected

The nodes.

Definition at line 183 of file gim_hash_table.h.

◆ m_sorted

template<class T >

bool gim_hash_table< T >::m_sorted

protected

Definition at line 185 of file gim_hash_table.h.

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

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