Page MenuHome
Differential D8762 Diff 28333 extern/bullet2/src/BulletCollision/Gimpact/gim_hash_table.h

Changeset View

Standalone View

View Options

extern/bullet2/src/BulletCollision/Gimpact/gim_hash_table.h

Show All 28 Lines
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files
GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details. GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details.
----------------------------------------------------------------------------- -----------------------------------------------------------------------------
*/ */
#include "gim_radixsort.h" #include "gim_radixsort.h"
#define GIM_INVALID_HASH 0xffffffff //!< A very very high value #define GIM_INVALID_HASH 0xffffffff //!< A very very high value
#define GIM_DEFAULT_HASH_TABLE_SIZE 380 #define GIM_DEFAULT_HASH_TABLE_SIZE 380
#define GIM_DEFAULT_HASH_TABLE_NODE_SIZE 4 #define GIM_DEFAULT_HASH_TABLE_NODE_SIZE 4
#define GIM_HASH_TABLE_GROW_FACTOR 2 #define GIM_HASH_TABLE_GROW_FACTOR 2
#define GIM_MIN_RADIX_SORT_SIZE 860 //!< calibrated on a PIII #define GIM_MIN_RADIX_SORT_SIZE 860 //!< calibrated on a PIII
template<typename T> template <typename T>
struct GIM_HASH_TABLE_NODE struct GIM_HASH_TABLE_NODE
{ {
GUINT m_key; GUINT m_key;
T m_data; T m_data;
GIM_HASH_TABLE_NODE() GIM_HASH_TABLE_NODE()
{ {
} }
GIM_HASH_TABLE_NODE(const GIM_HASH_TABLE_NODE & value) GIM_HASH_TABLE_NODE(const GIM_HASH_TABLE_NODE& value)
{ {
m_key = value.m_key; m_key = value.m_key;
m_data = value.m_data; m_data = value.m_data;
} }
GIM_HASH_TABLE_NODE(GUINT key, const T & data) GIM_HASH_TABLE_NODE(GUINT key, const T& data)
{ {
m_key = key; m_key = key;
m_data = data; m_data = data;
} }
bool operator <(const GIM_HASH_TABLE_NODE<T> & other) const bool operator<(const GIM_HASH_TABLE_NODE<T>& other) const
{ {
///inverse order, further objects are first ///inverse order, further objects are first
if(m_key < other.m_key) return true; if (m_key < other.m_key) return true;
return false; return false;
} }
bool operator >(const GIM_HASH_TABLE_NODE<T> & other) const bool operator>(const GIM_HASH_TABLE_NODE<T>& other) const
{ {
///inverse order, further objects are first ///inverse order, further objects are first
if(m_key > other.m_key) return true; if (m_key > other.m_key) return true;
return false; return false;
} }
bool operator ==(const GIM_HASH_TABLE_NODE<T> & other) const bool operator==(const GIM_HASH_TABLE_NODE<T>& other) const
{ {
///inverse order, further objects are first ///inverse order, further objects are first
if(m_key == other.m_key) return true; if (m_key == other.m_key) return true;
return false; return false;
} }
}; };
///Macro for getting the key ///Macro for getting the key
class GIM_HASH_NODE_GET_KEY class GIM_HASH_NODE_GET_KEY
{ {
public: public:
template<class T> template <class T>
inline GUINT operator()( const T& a) inline GUINT operator()(const T& a)
{ {
return a.m_key; return a.m_key;
} }
}; };
///Macro for comparing the key and the element ///Macro for comparing the key and the element
class GIM_HASH_NODE_CMP_KEY_MACRO class GIM_HASH_NODE_CMP_KEY_MACRO
{ {
public: public:
template<class T> template <class T>
inline int operator() ( const T& a, GUINT key) inline int operator()(const T& a, GUINT key)
{ {
return ((int)(a.m_key - key)); return ((int)(a.m_key - key));
} }
}; };
///Macro for comparing Hash nodes ///Macro for comparing Hash nodes
class GIM_HASH_NODE_CMP_MACRO class GIM_HASH_NODE_CMP_MACRO
{ {
public: public:
template<class T> template <class T>
inline int operator() ( const T& a, const T& b ) inline int operator()(const T& a, const T& b)
{ {
return ((int)(a.m_key - b.m_key)); return ((int)(a.m_key - b.m_key));
} }
}; };
//! Sorting for hash table //! Sorting for hash table
/*! /*!
switch automatically between quicksort and radixsort switch automatically between quicksort and radixsort
*/ */
template<typename T> template <typename T>
void gim_sort_hash_node_array(T * array, GUINT array_count) void gim_sort_hash_node_array(T* array, GUINT array_count)
{ {
if(array_count<GIM_MIN_RADIX_SORT_SIZE) if (array_count < GIM_MIN_RADIX_SORT_SIZE)
{ {
gim_heap_sort(array,array_count,GIM_HASH_NODE_CMP_MACRO()); gim_heap_sort(array, array_count, GIM_HASH_NODE_CMP_MACRO());
} }
else else
{ {
memcopy_elements_func cmpfunc; memcopy_elements_func cmpfunc;
gim_radix_sort(array,array_count,GIM_HASH_NODE_GET_KEY(),cmpfunc); gim_radix_sort(array, array_count, GIM_HASH_NODE_GET_KEY(), cmpfunc);
} }
} }
// Note: assumes long is at least 32 bits. // Note: assumes long is at least 32 bits.
#define GIM_NUM_PRIME 28 #define GIM_NUM_PRIME 28
static const GUINT gim_prime_list[GIM_NUM_PRIME] = static const GUINT gim_prime_list[GIM_NUM_PRIME] =
{ {
53ul, 97ul, 193ul, 389ul, 769ul, 53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul 1610612741ul, 3221225473ul, 4294967291ul};
};
inline GUINT gim_next_prime(GUINT number) inline GUINT gim_next_prime(GUINT number)
{ {
//Find nearest upper prime //Find nearest upper prime
GUINT result_ind = 0; GUINT result_ind = 0;
gim_binary_search(gim_prime_list,0,(GIM_NUM_PRIME-2),number,result_ind); gim_binary_search(gim_prime_list, 0, (GIM_NUM_PRIME - 2), number, result_ind);
// inv: result_ind < 28 // inv: result_ind < 28
return gim_prime_list[result_ind]; return gim_prime_list[result_ind];
} }
//! A compact hash table implementation //! A compact hash table implementation
/*! /*!
A memory aligned compact hash table that coud be treated as an array. 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 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. 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. You can use switch_to_hashtable() and switch_to_sorted_array for saving space or increase speed.
</br> </br>
<ul> <ul>
<li> if node_size = 0, then this container becomes a simple sorted array allocator. reserve_size is used for reserve memory in m_nodes. <li> 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. 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.
<li> If node_size != 0, then this container becomes a hash table for ever <li> If node_size != 0, then this container becomes a hash table for ever
</ul> </ul>
*/ */
template<class T> template <class T>
class gim_hash_table class gim_hash_table
{ {
protected: protected:
typedef GIM_HASH_TABLE_NODE<T> _node_type; typedef GIM_HASH_TABLE_NODE<T> _node_type;
//!The nodes //!The nodes
//array< _node_type, SuperAllocator<_node_type> > m_nodes; //array< _node_type, SuperAllocator<_node_type> > m_nodes;
gim_array< _node_type > m_nodes; gim_array<_node_type> m_nodes;
//SuperBufferedArray< _node_type > m_nodes; //SuperBufferedArray< _node_type > m_nodes;
bool m_sorted; bool m_sorted;
///Hash table data management. The hash table has the indices to the corresponding m_nodes array ///Hash table data management. The hash table has the indices to the corresponding m_nodes array
GUINT * m_hash_table;//!< GUINT* m_hash_table; //!<
GUINT m_table_size;//!< GUINT m_table_size; //!<
GUINT m_node_size;//!< GUINT m_node_size; //!<
GUINT m_min_hash_table_size; GUINT m_min_hash_table_size;
//! Returns the cell index //! Returns the cell index
inline GUINT _find_cell(GUINT hashkey) inline GUINT _find_cell(GUINT hashkey)
{ {
_node_type * nodesptr = m_nodes.pointer(); _node_type* nodesptr = m_nodes.pointer();
GUINT start_index = (hashkey%m_table_size)*m_node_size; GUINT start_index = (hashkey % m_table_size) * m_node_size;
GUINT end_index = start_index + m_node_size; GUINT end_index = start_index + m_node_size;
while(start_index<end_index) while (start_index < end_index)
{ {
GUINT value = m_hash_table[start_index]; GUINT value = m_hash_table[start_index];
if(value != GIM_INVALID_HASH) if (value != GIM_INVALID_HASH)
{ {
if(nodesptr[value].m_key == hashkey) return start_index; if (nodesptr[value].m_key == hashkey) return start_index;
} }
start_index++; start_index++;
} }
return GIM_INVALID_HASH; return GIM_INVALID_HASH;
} }
//! Find the avaliable cell for the hashkey, and return an existing cell if it has the same hash key //! Find the avaliable cell for the hashkey, and return an existing cell if it has the same hash key
inline GUINT _find_avaliable_cell(GUINT hashkey) inline GUINT _find_avaliable_cell(GUINT hashkey)
{ {
_node_type * nodesptr = m_nodes.pointer(); _node_type* nodesptr = m_nodes.pointer();
GUINT avaliable_index = GIM_INVALID_HASH; GUINT avaliable_index = GIM_INVALID_HASH;
GUINT start_index = (hashkey%m_table_size)*m_node_size; GUINT start_index = (hashkey % m_table_size) * m_node_size;
GUINT end_index = start_index + m_node_size; GUINT end_index = start_index + m_node_size;
while(start_index<end_index) while (start_index < end_index)
{ {
GUINT value = m_hash_table[start_index]; GUINT value = m_hash_table[start_index];
if(value == GIM_INVALID_HASH) if (value == GIM_INVALID_HASH)
{ {
if(avaliable_index==GIM_INVALID_HASH) if (avaliable_index == GIM_INVALID_HASH)
{ {
avaliable_index = start_index; avaliable_index = start_index;
} }
} }
else if(nodesptr[value].m_key == hashkey) else if (nodesptr[value].m_key == hashkey)
{ {
return start_index; return start_index;
} }
start_index++; start_index++;
} }
return avaliable_index; return avaliable_index;
} }
//! reserves the memory for the hash table. //! reserves the memory for the hash table.
/*! /*!
\pre hash table must be empty \pre hash table must be empty
\post reserves the memory for the hash table, an initializes all elements to GIM_INVALID_HASH. \post reserves the memory for the hash table, an initializes all elements to GIM_INVALID_HASH.
*/ */
inline void _reserve_table_memory(GUINT newtablesize) inline void _reserve_table_memory(GUINT newtablesize)
{ {
if(newtablesize==0) return; if (newtablesize == 0) return;
if(m_node_size==0) return; if (m_node_size == 0) return;
//Get a Prime size //Get a Prime size
m_table_size = gim_next_prime(newtablesize); m_table_size = gim_next_prime(newtablesize);
GUINT datasize = m_table_size*m_node_size; GUINT datasize = m_table_size * m_node_size;
//Alloc the data buffer //Alloc the data buffer
m_hash_table = (GUINT *)gim_alloc(datasize*sizeof(GUINT)); m_hash_table = (GUINT*)gim_alloc(datasize * sizeof(GUINT));
} }
inline void _invalidate_keys() inline void _invalidate_keys()
{ {
GUINT datasize = m_table_size*m_node_size; GUINT datasize = m_table_size * m_node_size;
for(GUINT i=0;i<datasize;i++) for (GUINT i = 0; i < datasize; i++)
{ {
m_hash_table[i] = GIM_INVALID_HASH;// invalidate keys m_hash_table[i] = GIM_INVALID_HASH; // invalidate keys
} }
} }
//! Clear all memory for the hash table //! Clear all memory for the hash table
inline void _clear_table_memory() inline void _clear_table_memory()
{ {
if(m_hash_table==NULL) return; if (m_hash_table == NULL) return;
gim_free(m_hash_table); gim_free(m_hash_table);
m_hash_table = NULL; m_hash_table = NULL;
m_table_size = 0; m_table_size = 0;
} }
//! Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys //! Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys
inline void _rehash() inline void _rehash()
{ {
_invalidate_keys(); _invalidate_keys();
_node_type * nodesptr = m_nodes.pointer(); _node_type* nodesptr = m_nodes.pointer();
for(GUINT i=0;i<(GUINT)m_nodes.size();i++) for (GUINT i = 0; i < (GUINT)m_nodes.size(); i++)
{ {
GUINT nodekey = nodesptr[i].m_key; GUINT nodekey = nodesptr[i].m_key;
if(nodekey != GIM_INVALID_HASH) if (nodekey != GIM_INVALID_HASH)
{ {
//Search for the avaliable cell in buffer //Search for the avaliable cell in buffer
GUINT index = _find_avaliable_cell(nodekey); GUINT index = _find_avaliable_cell(nodekey);
if(m_hash_table[index]!=GIM_INVALID_HASH) if (m_hash_table[index] != GIM_INVALID_HASH)
{//The new index is alreade used... discard this new incomming object, repeated key { //The new index is alreade used... discard this new incomming object, repeated key
btAssert(m_hash_table[index]==nodekey); btAssert(m_hash_table[index] == nodekey);
nodesptr[i].m_key = GIM_INVALID_HASH; nodesptr[i].m_key = GIM_INVALID_HASH;
} }
else else
{ {
//; //;
//Assign the value for alloc //Assign the value for alloc
m_hash_table[index] = i; m_hash_table[index] = i;
} }
} }
} }
} }
//! Resize hash table indices //! Resize hash table indices
inline void _resize_table(GUINT newsize) inline void _resize_table(GUINT newsize)
{ {
//Clear memory //Clear memory
_clear_table_memory(); _clear_table_memory();
//Alloc the data //Alloc the data
_reserve_table_memory(newsize); _reserve_table_memory(newsize);
//Invalidate keys and rehash //Invalidate keys and rehash
_rehash(); _rehash();
} }
//! Destroy hash table memory //! Destroy hash table memory
inline void _destroy() inline void _destroy()
{ {
if(m_hash_table==NULL) return; if (m_hash_table == NULL) return;
_clear_table_memory(); _clear_table_memory();
} }
//! Finds an avaliable hash table cell, and resizes the table if there isn't space //! Finds an avaliable hash table cell, and resizes the table if there isn't space
inline GUINT _assign_hash_table_cell(GUINT hashkey) inline GUINT _assign_hash_table_cell(GUINT hashkey)
{ {
GUINT cell_index = _find_avaliable_cell(hashkey); GUINT cell_index = _find_avaliable_cell(hashkey);
if(cell_index==GIM_INVALID_HASH) if (cell_index == GIM_INVALID_HASH)
{ {
//rehashing //rehashing
_resize_table(m_table_size+1); _resize_table(m_table_size + 1);
GUINT cell_index = _find_avaliable_cell(hashkey); GUINT cell_index = _find_avaliable_cell(hashkey);
btAssert(cell_index!=GIM_INVALID_HASH); btAssert(cell_index != GIM_INVALID_HASH);
} }
return cell_index; return cell_index;
} }
//! erase by index in hash table //! erase by index in hash table
inline bool _erase_by_index_hash_table(GUINT index) inline bool _erase_by_index_hash_table(GUINT index)
{ {
if(index >= m_nodes.size()) return false; if (index >= m_nodes.size()) return false;
if(m_nodes[index].m_key != GIM_INVALID_HASH) if (m_nodes[index].m_key != GIM_INVALID_HASH)
{ {
//Search for the avaliable cell in buffer //Search for the avaliable cell in buffer
GUINT cell_index = _find_cell(m_nodes[index].m_key); GUINT cell_index = _find_cell(m_nodes[index].m_key);
btAssert(cell_index!=GIM_INVALID_HASH); btAssert(cell_index != GIM_INVALID_HASH);
btAssert(m_hash_table[cell_index]==index); btAssert(m_hash_table[cell_index] == index);
m_hash_table[cell_index] = GIM_INVALID_HASH; m_hash_table[cell_index] = GIM_INVALID_HASH;
} }
return this->_erase_unsorted(index); return this->_erase_unsorted(index);
} }
//! erase by key in hash table //! erase by key in hash table
inline bool _erase_hash_table(GUINT hashkey) inline bool _erase_hash_table(GUINT hashkey)
{ {
if(hashkey == GIM_INVALID_HASH) return false; if (hashkey == GIM_INVALID_HASH) return false;
//Search for the avaliable cell in buffer //Search for the avaliable cell in buffer
GUINT cell_index = _find_cell(hashkey); GUINT cell_index = _find_cell(hashkey);
if(cell_index ==GIM_INVALID_HASH) return false; if (cell_index == GIM_INVALID_HASH) return false;
GUINT index = m_hash_table[cell_index]; GUINT index = m_hash_table[cell_index];
m_hash_table[cell_index] = GIM_INVALID_HASH; m_hash_table[cell_index] = GIM_INVALID_HASH;
return this->_erase_unsorted(index); return this->_erase_unsorted(index);
} }
//! insert an element in hash table //! insert an element in hash table
/*! /*!
If the element exists, this won't insert the element If the element exists, this won't insert the element
\return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted \return 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. If so, the element has been inserted at the last position of the array.
*/ */
inline GUINT _insert_hash_table(GUINT hashkey, const T & value) inline GUINT _insert_hash_table(GUINT hashkey, const T& value)
{ {
if(hashkey==GIM_INVALID_HASH) if (hashkey == GIM_INVALID_HASH)
{ {
//Insert anyway //Insert anyway
_insert_unsorted(hashkey,value); _insert_unsorted(hashkey, value);
return GIM_INVALID_HASH; return GIM_INVALID_HASH;
} }
GUINT cell_index = _assign_hash_table_cell(hashkey); GUINT cell_index = _assign_hash_table_cell(hashkey);
GUINT value_key = m_hash_table[cell_index]; GUINT value_key = m_hash_table[cell_index];
if(value_key!= GIM_INVALID_HASH) return value_key;// Not overrited if (value_key != GIM_INVALID_HASH) return value_key; // Not overrited
m_hash_table[cell_index] = m_nodes.size(); m_hash_table[cell_index] = m_nodes.size();
_insert_unsorted(hashkey,value); _insert_unsorted(hashkey, value);
return GIM_INVALID_HASH; return GIM_INVALID_HASH;
} }
//! insert an element in hash table. //! insert an element in hash table.
/*! /*!
If the element exists, this replaces the element. If the element exists, this replaces the element.
\return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted \return 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. If so, the element has been inserted at the last position of the array.
*/ */
inline GUINT _insert_hash_table_replace(GUINT hashkey, const T & value) inline GUINT _insert_hash_table_replace(GUINT hashkey, const T& value)
{ {
if(hashkey==GIM_INVALID_HASH) if (hashkey == GIM_INVALID_HASH)
{ {
//Insert anyway //Insert anyway
_insert_unsorted(hashkey,value); _insert_unsorted(hashkey, value);
return GIM_INVALID_HASH; return GIM_INVALID_HASH;
} }
GUINT cell_index = _assign_hash_table_cell(hashkey); GUINT cell_index = _assign_hash_table_cell(hashkey);
GUINT value_key = m_hash_table[cell_index]; GUINT value_key = m_hash_table[cell_index];
if(value_key!= GIM_INVALID_HASH) if (value_key != GIM_INVALID_HASH)
{//replaces the existing { //replaces the existing
m_nodes[value_key] = _node_type(hashkey,value); m_nodes[value_key] = _node_type(hashkey, value);
return value_key;// index of the replaced element return value_key; // index of the replaced element
} }
m_hash_table[cell_index] = m_nodes.size(); m_hash_table[cell_index] = m_nodes.size();
_insert_unsorted(hashkey,value); _insert_unsorted(hashkey, value);
return GIM_INVALID_HASH; return GIM_INVALID_HASH;
} }
///Sorted array data management. The hash table has the indices to the corresponding m_nodes array ///Sorted array data management. The hash table has the indices to the corresponding m_nodes array
inline bool _erase_sorted(GUINT index) inline bool _erase_sorted(GUINT index)
{ {
if(index>=(GUINT)m_nodes.size()) return false; if (index >= (GUINT)m_nodes.size()) return false;
m_nodes.erase_sorted(index); m_nodes.erase_sorted(index);
if(m_nodes.size()<2) m_sorted = false; if (m_nodes.size() < 2) m_sorted = false;
return true; return true;
} }
//! faster, but unsorted //! faster, but unsorted
inline bool _erase_unsorted(GUINT index) inline bool _erase_unsorted(GUINT index)
{ {
if(index>=m_nodes.size()) return false; if (index >= m_nodes.size()) return false;
GUINT lastindex = m_nodes.size()-1; GUINT lastindex = m_nodes.size() - 1;
if(index<lastindex && m_hash_table!=0) if (index < lastindex && m_hash_table != 0)
{ {
GUINT hashkey = m_nodes[lastindex].m_key; GUINT hashkey = m_nodes[lastindex].m_key;
if(hashkey!=GIM_INVALID_HASH) if (hashkey != GIM_INVALID_HASH)
{ {
//update the new position of the last element //update the new position of the last element
GUINT cell_index = _find_cell(hashkey); GUINT cell_index = _find_cell(hashkey);
btAssert(cell_index!=GIM_INVALID_HASH); btAssert(cell_index != GIM_INVALID_HASH);
//new position of the last element which will be swaped //new position of the last element which will be swaped
m_hash_table[cell_index] = index; m_hash_table[cell_index] = index;
} }
} }
m_nodes.erase(index); m_nodes.erase(index);
m_sorted = false; m_sorted = false;
return true; return true;
} }
//! Insert in position ordered //! 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 Also checks if it is needed to transform this container to a hash table, by calling check_for_switching_to_hashtable
*/ */
inline void _insert_in_pos(GUINT hashkey, const T & value, GUINT pos) inline void _insert_in_pos(GUINT hashkey, const T& value, GUINT pos)
{ {
m_nodes.insert(_node_type(hashkey,value),pos); m_nodes.insert(_node_type(hashkey, value), pos);
this->check_for_switching_to_hashtable(); this->check_for_switching_to_hashtable();
} }
//! Insert an element in an ordered array //! Insert an element in an ordered array
inline GUINT _insert_sorted(GUINT hashkey, const T & value) inline GUINT _insert_sorted(GUINT hashkey, const T& value)
{ {
if(hashkey==GIM_INVALID_HASH || size()==0) if (hashkey == GIM_INVALID_HASH || size() == 0)
{ {
m_nodes.push_back(_node_type(hashkey,value)); m_nodes.push_back(_node_type(hashkey, value));
return GIM_INVALID_HASH; return GIM_INVALID_HASH;
} }
//Insert at last position //Insert at last position
//Sort element //Sort element
GUINT result_ind=0; GUINT result_ind = 0;
GUINT last_index = m_nodes.size()-1; GUINT last_index = m_nodes.size() - 1;
_node_type * ptr = m_nodes.pointer(); _node_type* ptr = m_nodes.pointer();
bool found = gim_binary_search_ex( bool found = gim_binary_search_ex(
ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO()); ptr, 0, last_index, result_ind, hashkey, GIM_HASH_NODE_CMP_KEY_MACRO());
//Insert before found index //Insert before found index
if(found) if (found)
{ {
return result_ind; return result_ind;
} }
else else
{ {
_insert_in_pos(hashkey, value, result_ind); _insert_in_pos(hashkey, value, result_ind);
} }
return GIM_INVALID_HASH; return GIM_INVALID_HASH;
} }
inline GUINT _insert_sorted_replace(GUINT hashkey, const T & value) inline GUINT _insert_sorted_replace(GUINT hashkey, const T& value)
{ {
if(hashkey==GIM_INVALID_HASH || size()==0) if (hashkey == GIM_INVALID_HASH || size() == 0)
{ {
m_nodes.push_back(_node_type(hashkey,value)); m_nodes.push_back(_node_type(hashkey, value));
return GIM_INVALID_HASH; return GIM_INVALID_HASH;
} }
//Insert at last position //Insert at last position
//Sort element //Sort element
GUINT result_ind; GUINT result_ind;
GUINT last_index = m_nodes.size()-1; GUINT last_index = m_nodes.size() - 1;
_node_type * ptr = m_nodes.pointer(); _node_type* ptr = m_nodes.pointer();
bool found = gim_binary_search_ex( bool found = gim_binary_search_ex(
ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO()); ptr, 0, last_index, result_ind, hashkey, GIM_HASH_NODE_CMP_KEY_MACRO());
//Insert before found index //Insert before found index
if(found) if (found)
{ {
m_nodes[result_ind] = _node_type(hashkey,value); m_nodes[result_ind] = _node_type(hashkey, value);
} }
else else
{ {
_insert_in_pos(hashkey, value, result_ind); _insert_in_pos(hashkey, value, result_ind);
} }
return result_ind; return result_ind;
} }
//! Fast insertion in m_nodes array //! Fast insertion in m_nodes array
inline GUINT _insert_unsorted(GUINT hashkey, const T & value) inline GUINT _insert_unsorted(GUINT hashkey, const T& value)
{ {
m_nodes.push_back(_node_type(hashkey,value)); m_nodes.push_back(_node_type(hashkey, value));
m_sorted = false; m_sorted = false;
return GIM_INVALID_HASH; return GIM_INVALID_HASH;
} }
public: public:
/*! /*!
<li> if node_size = 0, then this container becomes a simple sorted array allocator. reserve_size is used for reserve memory in m_nodes. <li> 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. 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.
<li> If node_size != 0, then this container becomes a hash table for ever <li> If node_size != 0, then this container becomes a hash table for ever
</ul> </ul>
*/ */
gim_hash_table(GUINT reserve_size = GIM_DEFAULT_HASH_TABLE_SIZE, gim_hash_table(GUINT reserve_size = GIM_DEFAULT_HASH_TABLE_SIZE,
GUINT node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE, GUINT node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE,
GUINT min_hash_table_size = GIM_INVALID_HASH) GUINT min_hash_table_size = GIM_INVALID_HASH)
{ {
m_hash_table = NULL; m_hash_table = NULL;
m_table_size = 0; m_table_size = 0;
m_sorted = false; m_sorted = false;
m_node_size = node_size; m_node_size = node_size;
m_min_hash_table_size = min_hash_table_size; m_min_hash_table_size = min_hash_table_size;
if(m_node_size!=0) if (m_node_size != 0)
{ {
if(reserve_size!=0) if (reserve_size != 0)
{ {
m_nodes.reserve(reserve_size); m_nodes.reserve(reserve_size);
_reserve_table_memory(reserve_size); _reserve_table_memory(reserve_size);
_invalidate_keys(); _invalidate_keys();
} }
else else
{ {
m_nodes.reserve(GIM_DEFAULT_HASH_TABLE_SIZE); m_nodes.reserve(GIM_DEFAULT_HASH_TABLE_SIZE);
_reserve_table_memory(GIM_DEFAULT_HASH_TABLE_SIZE); _reserve_table_memory(GIM_DEFAULT_HASH_TABLE_SIZE);
_invalidate_keys(); _invalidate_keys();
} }
} }
else if(reserve_size!=0) else if (reserve_size != 0)
{ {
m_nodes.reserve(reserve_size); m_nodes.reserve(reserve_size);
} }
} }
~gim_hash_table() ~gim_hash_table()
{ {
_destroy(); _destroy();
} }
inline bool is_hash_table() inline bool is_hash_table()
{ {
if(m_hash_table) return true; if (m_hash_table) return true;
return false; return false;
} }
inline bool is_sorted() inline bool is_sorted()
{ {
if(size()<2) return true; if (size() < 2) return true;
return m_sorted; return m_sorted;
} }
bool sort() bool sort()
{ {
if(is_sorted()) return true; if (is_sorted()) return true;
if(m_nodes.size()<2) return false; if (m_nodes.size() < 2) return false;
_node_type * ptr = m_nodes.pointer(); _node_type* ptr = m_nodes.pointer();
GUINT siz = m_nodes.size(); GUINT siz = m_nodes.size();
gim_sort_hash_node_array(ptr,siz); gim_sort_hash_node_array(ptr, siz);
m_sorted=true; m_sorted = true;
if(m_hash_table) if (m_hash_table)
{ {
_rehash(); _rehash();
} }
return true; return true;
} }
bool switch_to_hashtable() bool switch_to_hashtable()
{ {
if(m_hash_table) return false; if (m_hash_table) return false;
if(m_node_size==0) m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE; if (m_node_size == 0) m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE;
if(m_nodes.size()<GIM_DEFAULT_HASH_TABLE_SIZE) if (m_nodes.size() < GIM_DEFAULT_HASH_TABLE_SIZE)
{ {
_resize_table(GIM_DEFAULT_HASH_TABLE_SIZE); _resize_table(GIM_DEFAULT_HASH_TABLE_SIZE);
} }
else else
{ {
_resize_table(m_nodes.size()+1); _resize_table(m_nodes.size() + 1);
} }
return true; return true;
} }
bool switch_to_sorted_array() bool switch_to_sorted_array()
{ {
if(m_hash_table==NULL) return true; if (m_hash_table == NULL) return true;
_clear_table_memory(); _clear_table_memory();
return sort(); return sort();
} }
//!If the container reaches the //!If the container reaches the
bool check_for_switching_to_hashtable() bool check_for_switching_to_hashtable()
{ {
if(this->m_hash_table) return true; if (this->m_hash_table) return true;
if(!(m_nodes.size()< m_min_hash_table_size)) if (!(m_nodes.size() < m_min_hash_table_size))
{ {
if(m_node_size == 0) if (m_node_size == 0)
{ {
m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE; m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE;
} }
_resize_table(m_nodes.size()+1); _resize_table(m_nodes.size() + 1);
return true; return true;
} }
return false; return false;
} }
inline void set_sorted(bool value) inline void set_sorted(bool value)
{ {
m_sorted = value; m_sorted = value;
} }
//! Retrieves the amount of keys. //! Retrieves the amount of keys.
inline GUINT size() const inline GUINT size() const
{ {
return m_nodes.size(); return m_nodes.size();
} }
//! Retrieves the hash key. //! Retrieves the hash key.
inline GUINT get_key(GUINT index) const inline GUINT get_key(GUINT index) const
{ {
return m_nodes[index].m_key; return m_nodes[index].m_key;
} }
//! Retrieves the value by index //! Retrieves the value by index
/*! /*!
*/ */
inline T * get_value_by_index(GUINT index) inline T* get_value_by_index(GUINT index)
{ {
return &m_nodes[index].m_data; return &m_nodes[index].m_data;
} }
inline const T& operator[](GUINT index) const inline const T& operator[](GUINT index) const
{ {
return m_nodes[index].m_data; return m_nodes[index].m_data;
} }
inline T& operator[](GUINT index) inline T& operator[](GUINT index)
{ {
return m_nodes[index].m_data; return m_nodes[index].m_data;
} }
//! Finds the index of the element with the key //! Finds the index of the element with the key
/*! /*!
\return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted \return 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. If so, the element has been inserted at the last position of the array.
*/ */
inline GUINT find(GUINT hashkey) inline GUINT find(GUINT hashkey)
{ {
if(m_hash_table) if (m_hash_table)
{ {
GUINT cell_index = _find_cell(hashkey); GUINT cell_index = _find_cell(hashkey);
if(cell_index==GIM_INVALID_HASH) return GIM_INVALID_HASH; if (cell_index == GIM_INVALID_HASH) return GIM_INVALID_HASH;
return m_hash_table[cell_index]; return m_hash_table[cell_index];
} }
GUINT last_index = m_nodes.size(); GUINT last_index = m_nodes.size();
if(last_index<2) if (last_index < 2)
{ {
if(last_index==0) return GIM_INVALID_HASH; if (last_index == 0) return GIM_INVALID_HASH;
if(m_nodes[0].m_key == hashkey) return 0; if (m_nodes[0].m_key == hashkey) return 0;
return GIM_INVALID_HASH; return GIM_INVALID_HASH;
} }
else if(m_sorted) else if (m_sorted)
{ {
//Binary search //Binary search
GUINT result_ind = 0; GUINT result_ind = 0;
last_index--; last_index--;
_node_type * ptr = m_nodes.pointer(); _node_type* ptr = m_nodes.pointer();
bool found = gim_binary_search_ex(ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO()); bool found = gim_binary_search_ex(ptr, 0, last_index, result_ind, hashkey, GIM_HASH_NODE_CMP_KEY_MACRO());
if(found) return result_ind; if (found) return result_ind;
} }
return GIM_INVALID_HASH; return GIM_INVALID_HASH;
} }
//! Retrieves the value associated with the index //! Retrieves the value associated with the index
/*! /*!
\return the found element, or null \return the found element, or null
*/ */
inline T * get_value(GUINT hashkey) inline T* get_value(GUINT hashkey)
{ {
GUINT index = find(hashkey); GUINT index = find(hashkey);
if(index == GIM_INVALID_HASH) return NULL; if (index == GIM_INVALID_HASH) return NULL;
return &m_nodes[index].m_data; return &m_nodes[index].m_data;
} }
/*! /*!
*/ */
inline bool erase_by_index(GUINT index) inline bool erase_by_index(GUINT index)
{ {
if(index > m_nodes.size()) return false; if (index > m_nodes.size()) return false;
if(m_hash_table == NULL) if (m_hash_table == NULL)
{ {
if(is_sorted()) if (is_sorted())
{ {
return this->_erase_sorted(index); return this->_erase_sorted(index);
} }
else else
{ {
return this->_erase_unsorted(index); return this->_erase_unsorted(index);
} }
} }
else else
{ {
return this->_erase_by_index_hash_table(index); return this->_erase_by_index_hash_table(index);
} }
return false; return false;
} }
inline bool erase_by_index_unsorted(GUINT index) inline bool erase_by_index_unsorted(GUINT index)
{ {
if(index > m_nodes.size()) return false; if (index > m_nodes.size()) return false;
if(m_hash_table == NULL) if (m_hash_table == NULL)
{ {
return this->_erase_unsorted(index); return this->_erase_unsorted(index);
} }
else else
{ {
return this->_erase_by_index_hash_table(index); return this->_erase_by_index_hash_table(index);
} }
return false; return false;
} }
/*! /*!
*/ */
inline bool erase_by_key(GUINT hashkey) inline bool erase_by_key(GUINT hashkey)
{ {
if(size()==0) return false; if (size() == 0) return false;
if(m_hash_table) if (m_hash_table)
{ {
return this->_erase_hash_table(hashkey); return this->_erase_hash_table(hashkey);
} }
//Binary search //Binary search
if(is_sorted()==false) return false; if (is_sorted() == false) return false;
GUINT result_ind = find(hashkey); GUINT result_ind = find(hashkey);
if(result_ind!= GIM_INVALID_HASH) if (result_ind != GIM_INVALID_HASH)
{ {
return this->_erase_sorted(result_ind); return this->_erase_sorted(result_ind);
} }
return false; return false;
} }
void clear() void clear()
{ {
m_nodes.clear(); m_nodes.clear();
if(m_hash_table==NULL) return; if (m_hash_table == NULL) return;
GUINT datasize = m_table_size*m_node_size; GUINT datasize = m_table_size * m_node_size;
//Initialize the hashkeys. //Initialize the hashkeys.
GUINT i; GUINT i;
for(i=0;i<datasize;i++) for (i = 0; i < datasize; i++)
{ {
m_hash_table[i] = GIM_INVALID_HASH;// invalidate keys m_hash_table[i] = GIM_INVALID_HASH; // invalidate keys
} }
m_sorted = false; m_sorted = false;
} }
//! Insert an element into the hash //! Insert an element into the hash
/*! /*!
\return If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position \return If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position
of the existing element. of the existing element.
*/ */
inline GUINT insert(GUINT hashkey, const T & element) inline GUINT insert(GUINT hashkey, const T& element)
{ {
if(m_hash_table) if (m_hash_table)
{ {
return this->_insert_hash_table(hashkey,element); return this->_insert_hash_table(hashkey, element);
} }
if(this->is_sorted()) if (this->is_sorted())
{ {
return this->_insert_sorted(hashkey,element); return this->_insert_sorted(hashkey, element);
} }
return this->_insert_unsorted(hashkey,element); return this->_insert_unsorted(hashkey, element);
} }
//! Insert an element into the hash, and could overrite an existing object with the same hash. //! Insert an element into the hash, and could overrite an existing object with the same hash.
/*! /*!
\return If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position \return If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position
of the replaced element. of the replaced element.
*/ */
inline GUINT insert_override(GUINT hashkey, const T & element) inline GUINT insert_override(GUINT hashkey, const T& element)
{ {
if(m_hash_table) if (m_hash_table)
{ {
return this->_insert_hash_table_replace(hashkey,element); return this->_insert_hash_table_replace(hashkey, element);
} }
if(this->is_sorted()) if (this->is_sorted())
{ {
return this->_insert_sorted_replace(hashkey,element); return this->_insert_sorted_replace(hashkey, element);
} }
this->_insert_unsorted(hashkey,element); this->_insert_unsorted(hashkey, element);
return m_nodes.size(); return m_nodes.size();
} }
//! Insert an element into the hash,But if this container is a sorted array, this inserts it unsorted //! Insert an element into the hash,But if this container is a sorted array, this inserts it unsorted
/*! /*!
*/ */
inline GUINT insert_unsorted(GUINT hashkey,const T & element) inline GUINT insert_unsorted(GUINT hashkey, const T& element)
{ {
if(m_hash_table) if (m_hash_table)
{ {
return this->_insert_hash_table(hashkey,element); return this->_insert_hash_table(hashkey, element);
} }
return this->_insert_unsorted(hashkey,element); return this->_insert_unsorted(hashkey, element);
} }
}; };
#endif // GIM_CONTAINERS_H_INCLUDED #endif // GIM_CONTAINERS_H_INCLUDED