1 #ifndef GIM_HASH_TABLE_H_INCLUDED 2 #define GIM_HASH_TABLE_H_INCLUDED 38 #define GIM_INVALID_HASH 0xffffffff 39 #define GIM_DEFAULT_HASH_TABLE_SIZE 380 40 #define GIM_DEFAULT_HASH_TABLE_NODE_SIZE 4 41 #define GIM_HASH_TABLE_GROW_FACTOR 2 43 #define GIM_MIN_RADIX_SORT_SIZE 860 66 bool operator <(const GIM_HASH_TABLE_NODE<T> & other)
const 69 if(m_key < other.m_key)
return true;
76 if(m_key > other.
m_key)
return true;
83 if(m_key == other.
m_key)
return true;
106 inline int operator() (
const T& a,
GUINT key)
108 return ((
int)(a.m_key - key));
117 inline int operator() (
const T& a,
const T& b )
119 return ((
int)(a.m_key - b.m_key));
151 #define GIM_NUM_PRIME 28 155 53ul, 97ul, 193ul, 389ul, 769ul,
156 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
157 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
158 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
159 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
160 1610612741ul, 3221225473ul, 4294967291ul
166 GUINT result_ind = 0;
213 _node_type * nodesptr = m_nodes.
pointer();
214 GUINT start_index = (hashkey%m_table_size)*m_node_size;
215 GUINT end_index = start_index + m_node_size;
217 while(start_index<end_index)
219 GUINT value = m_hash_table[start_index];
222 if(nodesptr[value].
m_key == hashkey)
return start_index;
232 _node_type * nodesptr = m_nodes.
pointer();
234 GUINT start_index = (hashkey%m_table_size)*m_node_size;
235 GUINT end_index = start_index + m_node_size;
237 while(start_index<end_index)
239 GUINT value = m_hash_table[start_index];
244 avaliable_index = start_index;
247 else if(nodesptr[value].
m_key == hashkey)
253 return avaliable_index;
265 if(newtablesize==0)
return;
266 if(m_node_size==0)
return;
272 GUINT datasize = m_table_size*m_node_size;
279 GUINT datasize = m_table_size*m_node_size;
280 for(
GUINT i=0;i<datasize;i++)
289 if(m_hash_table==NULL)
return;
300 _node_type * nodesptr = m_nodes.
pointer();
307 GUINT index = _find_avaliable_cell(nodekey);
312 btAssert(m_hash_table[index]==nodekey);
319 m_hash_table[index] = i;
329 _clear_table_memory();
331 _reserve_table_memory(newsize);
339 if(m_hash_table==NULL)
return;
340 _clear_table_memory();
346 GUINT cell_index = _find_avaliable_cell(hashkey);
351 _resize_table(m_table_size+1);
352 GUINT cell_index = _find_avaliable_cell(hashkey);
361 if(index >= m_nodes.
size())
return false;
365 GUINT cell_index = _find_cell(m_nodes[index].
m_key);
368 btAssert(m_hash_table[cell_index]==index);
373 return this->_erase_unsorted(index);
382 GUINT cell_index = _find_cell(hashkey);
385 GUINT index = m_hash_table[cell_index];
388 return this->_erase_unsorted(index);
404 _insert_unsorted(hashkey,value);
408 GUINT cell_index = _assign_hash_table_cell(hashkey);
410 GUINT value_key = m_hash_table[cell_index];
414 m_hash_table[cell_index] = m_nodes.
size();
416 _insert_unsorted(hashkey,value);
431 _insert_unsorted(hashkey,value);
435 GUINT cell_index = _assign_hash_table_cell(hashkey);
437 GUINT value_key = m_hash_table[cell_index];
441 m_nodes[value_key] = _node_type(hashkey,value);
445 m_hash_table[cell_index] = m_nodes.
size();
447 _insert_unsorted(hashkey,value);
456 if(index>=(
GUINT)m_nodes.
size())
return false;
458 if(m_nodes.
size()<2) m_sorted =
false;
465 if(index>=m_nodes.
size())
return false;
468 if(index<lastindex && m_hash_table!=0)
470 GUINT hashkey = m_nodes[lastindex].m_key;
474 GUINT cell_index = _find_cell(hashkey);
477 m_hash_table[cell_index] = index;
480 m_nodes.
erase(index);
491 m_nodes.
insert(_node_type(hashkey,value),pos);
492 this->check_for_switching_to_hashtable();
500 m_nodes.
push_back(_node_type(hashkey,value));
509 _node_type * ptr = m_nodes.
pointer();
522 _insert_in_pos(hashkey, value, result_ind);
531 m_nodes.
push_back(_node_type(hashkey,value));
538 _node_type * ptr = m_nodes.
pointer();
546 m_nodes[result_ind] = _node_type(hashkey,value);
550 _insert_in_pos(hashkey, value, result_ind);
558 m_nodes.
push_back(_node_type(hashkey,value));
580 m_node_size = node_size;
581 m_min_hash_table_size = min_hash_table_size;
588 _reserve_table_memory(reserve_size);
598 else if(reserve_size!=0)
612 if(m_hash_table)
return true;
618 if(
size()<2)
return true;
624 if(is_sorted())
return true;
625 if(m_nodes.
size()<2)
return false;
628 _node_type * ptr = m_nodes.
pointer();
644 if(m_hash_table)
return false;
652 _resize_table(m_nodes.
size()+1);
660 if(m_hash_table==NULL)
return true;
661 _clear_table_memory();
668 if(this->m_hash_table)
return true;
670 if(!(m_nodes.
size()< m_min_hash_table_size))
677 _resize_table(m_nodes.
size()+1);
691 return m_nodes.
size();
697 return m_nodes[index].m_key;
705 return &m_nodes[index].
m_data;
710 return m_nodes[index].
m_data;
715 return m_nodes[index].
m_data;
727 GUINT cell_index = _find_cell(hashkey);
729 return m_hash_table[cell_index];
735 if(m_nodes[0].
m_key == hashkey)
return 0;
741 GUINT result_ind = 0;
743 _node_type * ptr = m_nodes.
pointer();
748 if(found)
return result_ind;
759 GUINT index = find(hashkey);
761 return &m_nodes[index].
m_data;
769 if(index > m_nodes.
size())
return false;
771 if(m_hash_table == NULL)
775 return this->_erase_sorted(index);
779 return this->_erase_unsorted(index);
784 return this->_erase_by_index_hash_table(index);
793 if(index > m_nodes.
size())
return false;
795 if(m_hash_table == NULL)
797 return this->_erase_unsorted(index);
801 return this->_erase_by_index_hash_table(index);
813 if(
size()==0)
return false;
817 return this->_erase_hash_table(hashkey);
821 if(is_sorted()==
false)
return false;
823 GUINT result_ind = find(hashkey);
826 return this->_erase_sorted(result_ind);
835 if(m_hash_table==NULL)
return;
836 GUINT datasize = m_table_size*m_node_size;
839 for(i=0;i<datasize;i++)
855 return this->_insert_hash_table(hashkey,element);
857 if(this->is_sorted())
859 return this->_insert_sorted(hashkey,element);
861 return this->_insert_unsorted(hashkey,element);
873 return this->_insert_hash_table_replace(hashkey,element);
875 if(this->is_sorted())
877 return this->_insert_sorted_replace(hashkey,element);
879 this->_insert_unsorted(hashkey,element);
880 return m_nodes.
size();
892 return this->_insert_hash_table(hashkey,element);
894 return this->_insert_unsorted(hashkey,element);
902 #endif // GIM_CONTAINERS_H_INCLUDED bool erase_by_index_unsorted(GUINT index)
void erase(GUINT index)
fast erase
Macro for comparing Hash nodes.
bool switch_to_hashtable()
GIM_HASH_TABLE_NODE(const GIM_HASH_TABLE_NODE &value)
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...
GIM_HASH_TABLE_NODE< T > _node_type
void _rehash()
Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys.
Prototype for copying elements.
static const GUINT gim_prime_list[GIM_NUM_PRIME]
void insert(const T &obj, GUINT index)
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
GUINT operator()(const T &a)
GUINT _assign_hash_table_cell(GUINT hashkey)
Finds an avaliable hash table cell, and resizes the table if there isn't space.
bool gim_binary_search(const T *_array, GUINT _start_i, GUINT _end_i, const T &_search_key, GUINT &_result_index)
Failsafe Iterative binary search,Template version.
bool switch_to_sorted_array()
GUINT _insert_sorted_replace(GUINT hashkey, const T &value)
#define GIM_DEFAULT_HASH_TABLE_NODE_SIZE
const T & operator[](GUINT index) const
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 get_key(GUINT index) const
Retrieves the hash key.
void gim_heap_sort(T *pArr, GUINT element_count, COMP_CLASS CompareFunc)
void _resize_table(GUINT newsize)
Resize hash table indices.
void set_sorted(bool value)
void erase_sorted(GUINT index)
GUINT _insert_hash_table(GUINT hashkey, const T &value)
insert an element in hash table
GUINT _find_cell(GUINT hashkey)
Returns the cell index.
GUINT insert(GUINT hashkey, const T &element)
Insert an element into the hash.
GUINT _insert_unsorted(GUINT hashkey, const T &value)
Fast insertion in m_nodes array.
bool _erase_sorted(GUINT index)
Sorted array data management. The hash table has the indices to the corresponding m_nodes array...
T * get_value_by_index(GUINT index)
Retrieves the value by index.
bool erase_by_index(GUINT index)
GUINT gim_next_prime(GUINT number)
GIM_HASH_TABLE_NODE(GUINT key, const T &data)
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...
Very simple array container with fast access and simd memory.
GUINT find(GUINT hashkey)
Finds the index of the element with the key.
bool erase_by_key(GUINT hashkey)
GUINT m_min_hash_table_size
bool gim_binary_search_ex(const T *_array, GUINT _start_i, GUINT _end_i, GUINT &_result_index, const KEYCLASS &_search_key, COMP_CLASS _comp_macro)
Failsafe Iterative binary search,.
GUINT size() const
Retrieves the amount of keys.
bool operator==(const GIM_HASH_TABLE_NODE< T > &other) const
void _clear_table_memory()
Clear all memory for the hash table.
GUINT _insert_hash_table_replace(GUINT hashkey, const T &value)
insert an element in hash table.
GUINT insert_override(GUINT hashkey, const T &element)
Insert an element into the hash, and could overrite an existing object with the same hash...
void _insert_in_pos(GUINT hashkey, const T &value, GUINT pos)
Insert in position ordered.
Macro for getting the key.
void gim_radix_sort(T *array, GUINT element_count, GETKEY_CLASS get_uintkey_macro, COPY_CLASS copy_elements_macro)
Sorts array in place. For generic use.
GUINT _insert_sorted(GUINT hashkey, const T &value)
Insert an element in an ordered array.
void _reserve_table_memory(GUINT newtablesize)
reserves the memory for the hash table.
void * gim_alloc(size_t size)
Standar Memory functions.
void _destroy()
Destroy hash table memory.
A compact hash table implementation.
GUINT * m_hash_table
Hash table data management. The hash table has the indices to the corresponding m_nodes array...
static DBVT_INLINE btDbvtNode * sort(btDbvtNode *n, btDbvtNode *&r)
bool _erase_by_index_hash_table(GUINT index)
erase by index in hash table
#define GIM_DEFAULT_HASH_TABLE_SIZE
gim_array< _node_type > m_nodes
The nodes.
void gim_sort_hash_node_array(T *array, GUINT array_count)
Sorting for hash table.
bool reserve(GUINT size)
public operations
#define GIM_MIN_RADIX_SORT_SIZE
calibrated on a PIII
void push_back(const T &obj)
bool operator>(const GIM_HASH_TABLE_NODE< T > &other) const
T & operator[](GUINT index)
bool _erase_unsorted(GUINT index)
faster, but unsorted
#define GIM_INVALID_HASH
A very very high value.
Macro for comparing the key and the element.
T * get_value(GUINT hashkey)
Retrieves the value associated with the index.
bool _erase_hash_table(GUINT hashkey)
erase by key in hash table
bool check_for_switching_to_hashtable()
If the container reaches the.