Blender
V3.3
|
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. 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 |
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 176 of file gim_hash_table.h.
|
protected |
Definition at line 179 of file gim_hash_table.h.
|
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 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, and NULL.
|
inline |
Definition at line 575 of file gim_hash_table.h.
References gim_hash_table< T >::_destroy().
|
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 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().
|
inlineprotected |
Clear all memory for the hash table.
Definition at line 268 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().
|
inlineprotected |
Destroy hash table memory.
Definition at line 317 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().
|
inlineprotected |
erase by index in hash table
Definition at line 339 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, and gim_hash_table< T >::m_nodes.
Referenced by gim_hash_table< T >::erase_by_index(), and gim_hash_table< T >::erase_by_index_unsorted().
|
inlineprotected |
erase by key in hash table
Definition at line 357 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().
|
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, gim_hash_table< T >::m_nodes, and gim_hash_table< T >::m_sorted.
Referenced by gim_hash_table< T >::erase_by_index(), and gim_hash_table< T >::erase_by_key().
|
inlineprotected |
faster, but unsorted
Definition at line 439 of file gim_hash_table.h.
References 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_hash_table< T >::m_sorted.
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().
|
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, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_node_size, gim_hash_table< T >::m_nodes, and gim_hash_table< T >::m_table_size.
Referenced by gim_hash_table< T >::_assign_hash_table_cell(), and gim_hash_table< T >::_rehash().
|
inlineprotected |
Returns the cell index.
Definition at line 194 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, and gim_hash_table< T >::m_table_size.
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().
|
inlineprotected |
insert an element in hash table
If the element exists, this won't insert the element
Definition at line 377 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, and gim_hash_table< T >::m_nodes.
Referenced by gim_hash_table< T >::insert(), and gim_hash_table< T >::insert_unsorted().
|
inlineprotected |
insert an element in hash table.
If the element exists, this replaces the element.
Definition at line 404 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, and gim_hash_table< T >::m_nodes.
Referenced by gim_hash_table< T >::insert_override().
|
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 gim_hash_table< T >::check_for_switching_to_hashtable(), gim_hash_table< T >::m_nodes, and pos.
Referenced by gim_hash_table< T >::_insert_sorted(), and gim_hash_table< T >::_insert_sorted_replace().
|
inlineprotected |
Insert an element in an ordered array.
Definition at line 472 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, ptr, and gim_hash_table< T >::size().
Referenced by gim_hash_table< T >::insert().
|
inlineprotected |
Definition at line 501 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, ptr, and gim_hash_table< T >::size().
Referenced by gim_hash_table< T >::insert_override().
|
inlineprotected |
Fast insertion in m_nodes array.
Definition at line 530 of file gim_hash_table.h.
References GIM_INVALID_HASH, gim_hash_table< T >::m_nodes, and gim_hash_table< T >::m_sorted.
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().
|
inlineprotected |
Definition at line 258 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, and gim_hash_table< T >::m_table_size.
Referenced by gim_hash_table< T >::_rehash(), and gim_hash_table< T >::gim_hash_table().
|
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 gim_hash_table< T >::_find_avaliable_cell(), gim_hash_table< T >::_invalidate_keys(), btAssert, GIM_INVALID_HASH, GUINT, gim_hash_table< T >::m_hash_table, GIM_HASH_TABLE_NODE< T >::m_key, and gim_hash_table< T >::m_nodes.
Referenced by gim_hash_table< T >::_resize_table(), and gim_hash_table< T >::sort().
|
inlineprotected |
reserves the memory for the hash table.
Definition at line 244 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().
|
inlineprotected |
Resize hash table indices.
Definition at line 306 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().
|
inline |
If the container reaches the.
Definition at line 633 of file gim_hash_table.h.
References gim_hash_table< T >::_resize_table(), GIM_DEFAULT_HASH_TABLE_NODE_SIZE, gim_hash_table< T >::m_min_hash_table_size, gim_hash_table< T >::m_node_size, and gim_hash_table< T >::m_nodes.
Referenced by gim_hash_table< T >::_insert_in_pos().
|
inline |
Definition at line 792 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_sorted, gim_hash_table< T >::m_table_size, and NULL.
|
inline |
|
inline |
Definition at line 754 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, and NULL.
|
inline |
Definition at line 772 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().
|
inline |
Finds the index of the element with the key.
Definition at line 690 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, and ptr.
Referenced by gim_hash_table< T >::erase_by_key(), and gim_hash_table< T >::get_value().
|
inline |
Retrieves the hash key.
Definition at line 662 of file gim_hash_table.h.
References gim_hash_table< T >::m_nodes.
|
inline |
Retrieves the value associated with the index.
Definition at line 723 of file gim_hash_table.h.
References gim_hash_table< T >::find(), GIM_INVALID_HASH, GUINT, gim_hash_table< T >::m_nodes, and NULL.
|
inline |
Retrieves the value by index.
Definition at line 670 of file gim_hash_table.h.
References gim_hash_table< T >::m_nodes.
|
inline |
Insert an element into the hash.
Definition at line 812 of file gim_hash_table.h.
References gim_hash_table< T >::_insert_hash_table(), gim_hash_table< T >::_insert_sorted(), gim_hash_table< T >::_insert_unsorted(), element, gim_hash_table< T >::is_sorted(), and gim_hash_table< T >::m_hash_table.
|
inline |
Insert an element into the hash, and could overrite an existing object with the same hash.
Definition at line 830 of file gim_hash_table.h.
References gim_hash_table< T >::_insert_hash_table_replace(), gim_hash_table< T >::_insert_sorted_replace(), gim_hash_table< T >::_insert_unsorted(), element, gim_hash_table< T >::is_sorted(), gim_hash_table< T >::m_hash_table, and gim_hash_table< T >::m_nodes.
|
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 gim_hash_table< T >::_insert_hash_table(), gim_hash_table< T >::_insert_unsorted(), element, and gim_hash_table< T >::m_hash_table.
|
inline |
Definition at line 580 of file gim_hash_table.h.
References gim_hash_table< T >::m_hash_table.
|
inline |
Definition at line 586 of file gim_hash_table.h.
References gim_hash_table< T >::m_sorted, and gim_hash_table< T >::size().
Referenced by gim_hash_table< T >::erase_by_index(), gim_hash_table< T >::erase_by_key(), gim_hash_table< T >::insert(), gim_hash_table< T >::insert_override(), and gim_hash_table< T >::sort().
|
inline |
Definition at line 680 of file gim_hash_table.h.
References gim_hash_table< T >::m_nodes.
|
inline |
Definition at line 675 of file gim_hash_table.h.
References gim_hash_table< T >::m_nodes.
|
inline |
Definition at line 650 of file gim_hash_table.h.
References gim_hash_table< T >::m_sorted.
|
inline |
Retrieves the amount of keys.
Definition at line 656 of file gim_hash_table.h.
References gim_hash_table< T >::m_nodes.
Referenced by gim_hash_table< T >::_insert_sorted(), gim_hash_table< T >::_insert_sorted_replace(), gim_hash_table< T >::erase_by_key(), and gim_hash_table< T >::is_sorted().
|
inline |
Definition at line 592 of file gim_hash_table.h.
References gim_hash_table< T >::_rehash(), gim_sort_hash_node_array(), GUINT, gim_hash_table< T >::is_sorted(), gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_nodes, gim_hash_table< T >::m_sorted, and ptr.
Referenced by gim_hash_table< T >::switch_to_sorted_array().
|
inline |
Definition at line 609 of file gim_hash_table.h.
References gim_hash_table< T >::_resize_table(), GIM_DEFAULT_HASH_TABLE_NODE_SIZE, GIM_DEFAULT_HASH_TABLE_SIZE, gim_hash_table< T >::m_hash_table, gim_hash_table< T >::m_node_size, and gim_hash_table< T >::m_nodes.
|
inline |
Definition at line 625 of file gim_hash_table.h.
References gim_hash_table< T >::_clear_table_memory(), gim_hash_table< T >::m_hash_table, NULL, and gim_hash_table< T >::sort().
|
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 gim_hash_table< T >::_clear_table_memory(), gim_hash_table< T >::_destroy(), gim_hash_table< T >::_erase_by_index_hash_table(), gim_hash_table< T >::_erase_hash_table(), gim_hash_table< T >::_erase_unsorted(), gim_hash_table< T >::_find_avaliable_cell(), gim_hash_table< T >::_find_cell(), gim_hash_table< T >::_insert_hash_table(), gim_hash_table< T >::_insert_hash_table_replace(), gim_hash_table< T >::_invalidate_keys(), gim_hash_table< T >::_rehash(), gim_hash_table< T >::_reserve_table_memory(), gim_hash_table< T >::clear(), gim_hash_table< T >::erase_by_index(), gim_hash_table< T >::erase_by_index_unsorted(), gim_hash_table< T >::erase_by_key(), gim_hash_table< T >::find(), gim_hash_table< T >::gim_hash_table(), gim_hash_table< T >::insert(), gim_hash_table< T >::insert_override(), gim_hash_table< T >::insert_unsorted(), gim_hash_table< T >::is_hash_table(), gim_hash_table< T >::sort(), gim_hash_table< T >::switch_to_hashtable(), and gim_hash_table< T >::switch_to_sorted_array().
|
protected |
Definition at line 191 of file gim_hash_table.h.
Referenced by gim_hash_table< T >::check_for_switching_to_hashtable(), and gim_hash_table< T >::gim_hash_table().
|
protected |
Definition at line 190 of file gim_hash_table.h.
Referenced by gim_hash_table< T >::_find_avaliable_cell(), gim_hash_table< T >::_find_cell(), gim_hash_table< T >::_invalidate_keys(), gim_hash_table< T >::_reserve_table_memory(), gim_hash_table< T >::check_for_switching_to_hashtable(), gim_hash_table< T >::clear(), gim_hash_table< T >::gim_hash_table(), and gim_hash_table< T >::switch_to_hashtable().
|
protected |
The nodes.
Definition at line 183 of file gim_hash_table.h.
Referenced by 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 >::_find_avaliable_cell(), gim_hash_table< T >::_find_cell(), gim_hash_table< T >::_insert_hash_table(), gim_hash_table< T >::_insert_hash_table_replace(), gim_hash_table< T >::_insert_in_pos(), gim_hash_table< T >::_insert_sorted(), gim_hash_table< T >::_insert_sorted_replace(), gim_hash_table< T >::_insert_unsorted(), gim_hash_table< T >::_rehash(), gim_hash_table< T >::check_for_switching_to_hashtable(), gim_hash_table< T >::clear(), gim_hash_table< T >::erase_by_index(), gim_hash_table< T >::erase_by_index_unsorted(), gim_hash_table< T >::find(), gim_hash_table< T >::get_key(), gim_hash_table< T >::get_value(), gim_hash_table< T >::get_value_by_index(), gim_hash_table< T >::gim_hash_table(), gim_hash_table< T >::insert_override(), gim_hash_table< T >::operator[](), gim_hash_table< T >::size(), gim_hash_table< T >::sort(), and gim_hash_table< T >::switch_to_hashtable().
|
protected |
Definition at line 185 of file gim_hash_table.h.
Referenced by gim_hash_table< T >::_erase_sorted(), gim_hash_table< T >::_erase_unsorted(), gim_hash_table< T >::_insert_unsorted(), gim_hash_table< T >::clear(), gim_hash_table< T >::find(), gim_hash_table< T >::gim_hash_table(), gim_hash_table< T >::is_sorted(), gim_hash_table< T >::set_sorted(), and gim_hash_table< T >::sort().
|
protected |
Definition at line 189 of file gim_hash_table.h.
Referenced by gim_hash_table< T >::_assign_hash_table_cell(), gim_hash_table< T >::_clear_table_memory(), gim_hash_table< T >::_find_avaliable_cell(), gim_hash_table< T >::_find_cell(), gim_hash_table< T >::_invalidate_keys(), gim_hash_table< T >::_reserve_table_memory(), gim_hash_table< T >::clear(), and gim_hash_table< T >::gim_hash_table().