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 191 of file gim_hash_table.h.

Member Typedef Documentation

template<class T >

typedef GIM_HASH_TABLE_NODE<T> gim_hash_table< T >::_node_type [protected]

Definition at line 194 of file gim_hash_table.h.

Constructor & Destructor Documentation

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 573 of file gim_hash_table.h.

References gim_hash_table< T >::_invalidate_keys(), gim_hash_table< T >::_reserve_table_memory(), GIM_DEFAULT_HASH_TABLE_SIZE, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_min_hash_table_size, gim_hash_table< T >::m_node_size, gim_hash_table< T >::m_nodes, gim_hash_table< T >::m_sorted, gim_hash_table< T >::m_table_size, NULL, and gim_array< T >::reserve().

template<class T >

gim_hash_table< T >::~gim_hash_table ( ) [inline]

Definition at line 605 of file gim_hash_table.h.

References gim_hash_table< T >::_destroy().

Member Function Documentation

template<class T >

GUINT gim_hash_table< T >::_assign_hash_table_cell ( GUINT hashkey ) [inline, protected]

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

Definition at line 344 of file gim_hash_table.h.

References gim_hash_table< T >::_find_avaliable_cell(), gim_hash_table< T >::_resize_table(), btAssert, GIM_INVALID_HASH, GUINT, and gim_hash_table< T >::m_table_size.

Referenced by gim_hash_table< T >::_insert_hash_table(), and gim_hash_table< T >::_insert_hash_table_replace().

template<class T >

void gim_hash_table< T >::_clear_table_memory ( ) [inline, protected]

Clear all memory for the hash table.

Definition at line 287 of file gim_hash_table.h.

References gim_free(), gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_table_size, and NULL.

Referenced by gim_hash_table< T >::_destroy(), gim_hash_table< T >::_resize_table(), and gim_hash_table< T >::switch_to_sorted_array().

template<class T >

void gim_hash_table< T >::_destroy ( ) [inline, protected]

Destroy hash table memory.

Definition at line 337 of file gim_hash_table.h.

References gim_hash_table< T >::_clear_table_memory(), gim_hash_table< T >::m_hash_table, and NULL.

Referenced by gim_hash_table< T >::~gim_hash_table().

template<class T >

bool gim_hash_table< T >::_erase_by_index_hash_table ( GUINT index ) [inline, protected]

erase by index in hash table

Definition at line 359 of file gim_hash_table.h.

References gim_hash_table< T >::_erase_unsorted(), gim_hash_table< T >::_find_cell(), btAssert, GIM_INVALID_HASH, GUINT, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_nodes, and gim_array< T >::size().

Referenced by gim_hash_table< T >::erase_by_index(), and gim_hash_table< T >::erase_by_index_unsorted().

template<class T >

bool gim_hash_table< T >::_erase_hash_table ( GUINT hashkey ) [inline, protected]

erase by key in hash table

Definition at line 377 of file gim_hash_table.h.

References gim_hash_table< T >::_erase_unsorted(), gim_hash_table< T >::_find_cell(), GIM_INVALID_HASH, GUINT, and gim_hash_table< T >::m_hash_table.

Referenced by gim_hash_table< T >::erase_by_key().

template<class T >

bool gim_hash_table< T >::_erase_sorted ( GUINT index ) [inline, protected]

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

Definition at line 454 of file gim_hash_table.h.

References gim_array< T >::erase_sorted(), GUINT, gim_hash_table< T >::m_nodes, gim_hash_table< T >::m_sorted, and gim_array< T >::size().

Referenced by gim_hash_table< T >::erase_by_index(), and gim_hash_table< T >::erase_by_key().

template<class T >

bool gim_hash_table< T >::_erase_unsorted ( GUINT index ) [inline, protected]

faster, but unsorted

Definition at line 463 of file gim_hash_table.h.

References gim_hash_table< T >::_find_cell(), btAssert, gim_array< T >::erase(), GIM_INVALID_HASH, GUINT, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_nodes, gim_hash_table< T >::m_sorted, and gim_array< T >::size().

Referenced by gim_hash_table< T >::_erase_by_index_hash_table(), gim_hash_table< T >::_erase_hash_table(), gim_hash_table< T >::erase_by_index(), and gim_hash_table< T >::erase_by_index_unsorted().

template<class T >

GUINT gim_hash_table< T >::_find_avaliable_cell ( GUINT hashkey ) [inline, protected]

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

Definition at line 230 of file gim_hash_table.h.

References GIM_INVALID_HASH, GUINT, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_node_size, gim_hash_table< T >::m_nodes, gim_hash_table< T >::m_table_size, and gim_array< T >::pointer().

Referenced by gim_hash_table< T >::_assign_hash_table_cell(), and gim_hash_table< T >::_rehash().

template<class T >

GUINT gim_hash_table< T >::_find_cell ( GUINT hashkey ) [inline, protected]

Returns the cell index.

Definition at line 211 of file gim_hash_table.h.

References GIM_INVALID_HASH, GUINT, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_node_size, gim_hash_table< T >::m_nodes, gim_hash_table< T >::m_table_size, and gim_array< T >::pointer().

Referenced by gim_hash_table< T >::_erase_by_index_hash_table(), gim_hash_table< T >::_erase_hash_table(), gim_hash_table< T >::_erase_unsorted(), and gim_hash_table< T >::find().

template<class T >

GUINT gim_hash_table< T >::_insert_hash_table	(	GUINT	hashkey,
		const T &	value
	)		`[inline, protected]`

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 399 of file gim_hash_table.h.

References gim_hash_table< T >::_assign_hash_table_cell(), gim_hash_table< T >::_insert_unsorted(), GIM_INVALID_HASH, GUINT, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_nodes, and gim_array< T >::size().

Referenced by gim_hash_table< T >::insert(), and gim_hash_table< T >::insert_unsorted().

template<class T >

GUINT gim_hash_table< T >::_insert_hash_table_replace	(	GUINT	hashkey,
		const T &	value
	)		`[inline, protected]`

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 426 of file gim_hash_table.h.

References gim_hash_table< T >::_assign_hash_table_cell(), gim_hash_table< T >::_insert_unsorted(), GIM_INVALID_HASH, GUINT, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_nodes, and gim_array< T >::size().

Referenced by gim_hash_table< T >::insert_override().

template<class T >

void gim_hash_table< T >::_insert_in_pos	(	GUINT	hashkey,
		const T &	value,
		GUINT	pos
	)		`[inline, protected]`

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 489 of file gim_hash_table.h.

References gim_hash_table< T >::check_for_switching_to_hashtable(), gim_array< T >::insert(), and gim_hash_table< T >::m_nodes.

Referenced by gim_hash_table< T >::_insert_sorted(), and gim_hash_table< T >::_insert_sorted_replace().

template<class T >

GUINT gim_hash_table< T >::_insert_sorted	(	GUINT	hashkey,
		const T &	value
	)		`[inline, protected]`

Insert an element in an ordered array.

Definition at line 496 of file gim_hash_table.h.

References gim_hash_table< T >::_insert_in_pos(), gim_binary_search_ex(), GIM_INVALID_HASH, GUINT, gim_hash_table< T >::m_nodes, gim_array< T >::pointer(), gim_array< T >::push_back(), gim_hash_table< T >::size(), and gim_array< T >::size().

Referenced by gim_hash_table< T >::insert().

template<class T >

GUINT gim_hash_table< T >::_insert_sorted_replace	(	GUINT	hashkey,
		const T &	value
	)		`[inline, protected]`

Definition at line 527 of file gim_hash_table.h.

References gim_hash_table< T >::_insert_in_pos(), gim_binary_search_ex(), GIM_INVALID_HASH, GUINT, gim_hash_table< T >::m_nodes, gim_array< T >::pointer(), gim_array< T >::push_back(), gim_hash_table< T >::size(), and gim_array< T >::size().

Referenced by gim_hash_table< T >::insert_override().

template<class T >

GUINT gim_hash_table< T >::_insert_unsorted	(	GUINT	hashkey,
		const T &	value
	)		`[inline, protected]`

Fast insertion in m_nodes array.

Definition at line 556 of file gim_hash_table.h.

References GIM_INVALID_HASH, gim_hash_table< T >::m_nodes, gim_hash_table< T >::m_sorted, and gim_array< T >::push_back().

Referenced by gim_hash_table< T >::_insert_hash_table(), gim_hash_table< T >::_insert_hash_table_replace(), gim_hash_table< T >::insert(), gim_hash_table< T >::insert_override(), and gim_hash_table< T >::insert_unsorted().

template<class T >

void gim_hash_table< T >::_invalidate_keys ( ) [inline, protected]

Definition at line 277 of file gim_hash_table.h.

References GIM_INVALID_HASH, GUINT, i, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_node_size, and gim_hash_table< T >::m_table_size.

Referenced by gim_hash_table< T >::_rehash(), and gim_hash_table< T >::gim_hash_table().

template<class T >

void gim_hash_table< T >::_rehash ( ) [inline, protected]

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

Definition at line 296 of file gim_hash_table.h.

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

Referenced by gim_hash_table< T >::_resize_table(), and gim_hash_table< T >::sort().

template<class T >

void gim_hash_table< T >::_reserve_table_memory ( GUINT newtablesize ) [inline, protected]

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 263 of file gim_hash_table.h.

References gim_alloc(), gim_next_prime(), GUINT, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_node_size, and gim_hash_table< T >::m_table_size.

Referenced by gim_hash_table< T >::_resize_table(), and gim_hash_table< T >::gim_hash_table().

template<class T >

void gim_hash_table< T >::_resize_table ( GUINT newsize ) [inline, protected]

Resize hash table indices.

Definition at line 326 of file gim_hash_table.h.

References gim_hash_table< T >::_clear_table_memory(), gim_hash_table< T >::_rehash(), and gim_hash_table< T >::_reserve_table_memory().

Referenced by gim_hash_table< T >::_assign_hash_table_cell(), gim_hash_table< T >::check_for_switching_to_hashtable(), and gim_hash_table< T >::switch_to_hashtable().

template<class T >

bool gim_hash_table< T >::check_for_switching_to_hashtable ( ) [inline]

If the container reaches the.

Definition at line 666 of file gim_hash_table.h.

References gim_hash_table< T >::_resize_table(), GIM_DEFAULT_HASH_TABLE_NODE_SIZE, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_min_hash_table_size, gim_hash_table< T >::m_node_size, gim_hash_table< T >::m_nodes, and gim_array< T >::size().

Referenced by gim_hash_table< T >::_insert_in_pos().

template<class T >

void gim_hash_table< T >::clear ( ) [inline]

Definition at line 831 of file gim_hash_table.h.

References gim_array< T >::clear(), GIM_INVALID_HASH, GUINT, i, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_node_size, gim_hash_table< T >::m_nodes, gim_hash_table< T >::m_sorted, gim_hash_table< T >::m_table_size, and NULL.

template<class T >

bool gim_hash_table< T >::erase_by_index ( GUINT index ) [inline]

Definition at line 767 of file gim_hash_table.h.

References gim_hash_table< T >::_erase_by_index_hash_table(), gim_hash_table< T >::_erase_sorted(), gim_hash_table< T >::_erase_unsorted(), gim_hash_table< T >::is_sorted(), gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_nodes, NULL, and gim_array< T >::size().

template<class T >

bool gim_hash_table< T >::erase_by_index_unsorted ( GUINT index ) [inline]

Definition at line 791 of file gim_hash_table.h.

References gim_hash_table< T >::_erase_by_index_hash_table(), gim_hash_table< T >::_erase_unsorted(), gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_nodes, NULL, and gim_array< T >::size().

template<class T >

bool gim_hash_table< T >::erase_by_key ( GUINT hashkey ) [inline]

Definition at line 811 of file gim_hash_table.h.

References gim_hash_table< T >::_erase_hash_table(), gim_hash_table< T >::_erase_sorted(), gim_hash_table< T >::find(), GIM_INVALID_HASH, GUINT, gim_hash_table< T >::is_sorted(), gim_hash_table< T >::m_hash_table, and gim_hash_table< T >::size().

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 723 of file gim_hash_table.h.

References gim_hash_table< T >::_find_cell(), gim_binary_search_ex(), GIM_INVALID_HASH, GUINT, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_nodes, gim_hash_table< T >::m_sorted, gim_array< T >::pointer(), and gim_array< T >::size().

Referenced by gim_hash_table< T >::erase_by_key(), and gim_hash_table< T >::get_value().

template<class T >

GUINT gim_hash_table< T >::get_key ( GUINT index ) const [inline]

Retrieves the hash key.

Definition at line 695 of file gim_hash_table.h.

References gim_hash_table< T >::m_nodes.

template<class T >

T* gim_hash_table< T >::get_value ( GUINT hashkey ) [inline]

Retrieves the value associated with the index.