Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes
gim_hash_table< T > Class Template Reference

A compact hash table implementation. More...

#include <gim_hash_table.h>

List of all members.

Public Member Functions

bool check_for_switching_to_hashtable ()
 If the container reaches the.
void clear ()
bool erase_by_index (GUINT index)
bool erase_by_index_unsorted (GUINT index)
bool erase_by_key (GUINT hashkey)
GUINT find (GUINT hashkey)
 Finds the index of the element with the key.
GUINT get_key (GUINT index) const
 Retrieves the hash key.
T * get_value (GUINT hashkey)
 Retrieves the value associated with the index.
T * get_value_by_index (GUINT index)
 Retrieves the value by index.
 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)
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.
bool is_hash_table ()
bool is_sorted ()
const T & operator[] (GUINT index) const
T & operator[] (GUINT index)
void set_sorted (bool value)
GUINT size () const
 Retrieves the amount of keys.
bool sort ()
bool switch_to_hashtable ()
bool switch_to_sorted_array ()
 ~gim_hash_table ()

Protected Types

typedef GIM_HASH_TABLE_NODE< T > _node_type

Protected Member Functions

GUINT _assign_hash_table_cell (GUINT hashkey)
 Finds an avaliable hash table cell, and resizes the table if there isn't space.
void _clear_table_memory ()
 Clear all memory for the hash table.
void _destroy ()
 Destroy hash table memory.
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
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
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.
GUINT _find_cell (GUINT hashkey)
 Returns the cell index.
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.
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.
void _invalidate_keys ()
void _rehash ()
 Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys.
void _reserve_table_memory (GUINT newtablesize)
 reserves the memory for the hash table.
void _resize_table (GUINT newsize)
 Resize hash table indices.

Protected Attributes

GUINTm_hash_table
 Hash table data management. The hash table has the indices to the corresponding m_nodes array.
GUINT m_min_hash_table_size
GUINT m_node_size
gim_array< _node_typem_nodes
 The nodes.
bool m_sorted
GUINT m_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.

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.

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

Definition at line 605 of file gim_hash_table.h.


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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

Definition at line 277 of file gim_hash_table.h.

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.

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.

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.

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.

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

Definition at line 831 of file gim_hash_table.h.

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

Definition at line 767 of file gim_hash_table.h.

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.

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

Definition at line 811 of file gim_hash_table.h.

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.

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.

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

template<class T >
T* gim_hash_table< T >::get_value_by_index ( GUINT  index) [inline]

Retrieves the value by index.

Definition at line 703 of file gim_hash_table.h.

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

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

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

template<class T >
bool gim_hash_table< T >::is_hash_table ( ) [inline]

Definition at line 610 of file gim_hash_table.h.

template<class T >
bool gim_hash_table< T >::is_sorted ( ) [inline]

Definition at line 616 of file gim_hash_table.h.

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

Definition at line 708 of file gim_hash_table.h.

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

Definition at line 713 of file gim_hash_table.h.

template<class T >
void gim_hash_table< T >::set_sorted ( bool  value) [inline]

Definition at line 683 of file gim_hash_table.h.

template<class T >
GUINT gim_hash_table< T >::size ( ) const [inline]

Retrieves the amount of keys.

Definition at line 689 of file gim_hash_table.h.

template<class T >
bool gim_hash_table< T >::sort ( ) [inline]

Definition at line 622 of file gim_hash_table.h.

template<class T >
bool gim_hash_table< T >::switch_to_hashtable ( ) [inline]

Definition at line 642 of file gim_hash_table.h.

template<class T >
bool gim_hash_table< T >::switch_to_sorted_array ( ) [inline]

Definition at line 658 of file gim_hash_table.h.


Member Data Documentation

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

template<class T >
GUINT gim_hash_table< T >::m_min_hash_table_size [protected]

Definition at line 206 of file gim_hash_table.h.

template<class T >
GUINT gim_hash_table< T >::m_node_size [protected]

Definition at line 205 of file gim_hash_table.h.

template<class T >
gim_array< _node_type > gim_hash_table< T >::m_nodes [protected]

The nodes.

Definition at line 198 of file gim_hash_table.h.

template<class T >
bool gim_hash_table< T >::m_sorted [protected]

Definition at line 200 of file gim_hash_table.h.

template<class T >
GUINT gim_hash_table< T >::m_table_size [protected]

Definition at line 204 of file gim_hash_table.h.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines


bullet
Author(s): Erwin Coumans, ROS package maintained by Tully Foote
autogenerated on Wed Oct 31 2012 07:54:33