diff options
Diffstat (limited to 'extern/bullet2/src/BulletCollision/Gimpact/gim_hash_table.h')
| -rw-r--r-- | extern/bullet2/src/BulletCollision/Gimpact/gim_hash_table.h | 1385 |
1 files changed, 670 insertions, 715 deletions
diff --git a/extern/bullet2/src/BulletCollision/Gimpact/gim_hash_table.h b/extern/bullet2/src/BulletCollision/Gimpact/gim_hash_table.h index e4237c2c570..abf88d3108d 100644 --- a/extern/bullet2/src/BulletCollision/Gimpact/gim_hash_table.h +++ b/extern/bullet2/src/BulletCollision/Gimpact/gim_hash_table.h @@ -34,53 +34,52 @@ email: projectileman@yahoo.com #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_NODE_SIZE 4 #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 { - GUINT m_key; - T m_data; - GIM_HASH_TABLE_NODE() - { - } - - GIM_HASH_TABLE_NODE(const GIM_HASH_TABLE_NODE & value) - { - m_key = value.m_key; - m_data = value.m_data; - } - - GIM_HASH_TABLE_NODE(GUINT key, const T & data) - { - m_key = key; - m_data = data; - } - - bool operator <(const GIM_HASH_TABLE_NODE<T> & other) const + GUINT m_key; + T m_data; + GIM_HASH_TABLE_NODE() + { + } + + GIM_HASH_TABLE_NODE(const GIM_HASH_TABLE_NODE& value) + { + m_key = value.m_key; + m_data = value.m_data; + } + + GIM_HASH_TABLE_NODE(GUINT key, const T& data) + { + m_key = key; + m_data = data; + } + + bool operator<(const GIM_HASH_TABLE_NODE<T>& other) const { ///inverse order, further objects are first - if(m_key < other.m_key) return true; + if (m_key < other.m_key) return true; 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 - if(m_key > other.m_key) return true; + if (m_key > other.m_key) return true; 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 - if(m_key == other.m_key) return true; + if (m_key == other.m_key) return true; return false; } }; @@ -89,21 +88,19 @@ struct GIM_HASH_TABLE_NODE class GIM_HASH_NODE_GET_KEY { public: - template<class T> - inline GUINT operator()( const T& a) + template <class T> + inline GUINT operator()(const T& a) { return a.m_key; } }; - - ///Macro for comparing the key and the element class GIM_HASH_NODE_CMP_KEY_MACRO { public: - template<class T> - inline int operator() ( const T& a, GUINT key) + template <class T> + inline int operator()(const T& a, GUINT key) { return ((int)(a.m_key - key)); } @@ -113,65 +110,53 @@ public: class GIM_HASH_NODE_CMP_MACRO { public: - template<class T> - inline int operator() ( const T& a, const T& b ) + template <class T> + inline int operator()(const T& a, const T& b) { return ((int)(a.m_key - b.m_key)); } }; - - - - //! Sorting for hash table /*! switch automatically between quicksort and radixsort */ -template<typename T> -void gim_sort_hash_node_array(T * array, GUINT array_count) +template <typename T> +void gim_sort_hash_node_array(T* array, GUINT array_count) { - if(array_count<GIM_MIN_RADIX_SORT_SIZE) - { - gim_heap_sort(array,array_count,GIM_HASH_NODE_CMP_MACRO()); - } - else - { - memcopy_elements_func cmpfunc; - gim_radix_sort(array,array_count,GIM_HASH_NODE_GET_KEY(),cmpfunc); - } + if (array_count < GIM_MIN_RADIX_SORT_SIZE) + { + gim_heap_sort(array, array_count, GIM_HASH_NODE_CMP_MACRO()); + } + else + { + memcopy_elements_func cmpfunc; + gim_radix_sort(array, array_count, GIM_HASH_NODE_GET_KEY(), cmpfunc); + } } - - - - - // Note: assumes long is at least 32 bits. #define GIM_NUM_PRIME 28 static const GUINT gim_prime_list[GIM_NUM_PRIME] = -{ - 53ul, 97ul, 193ul, 389ul, 769ul, - 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, - 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, - 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, - 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, - 1610612741ul, 3221225473ul, 4294967291ul -}; + { + 53ul, 97ul, 193ul, 389ul, 769ul, + 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, + 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, + 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, + 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, + 1610612741ul, 3221225473ul, 4294967291ul}; inline GUINT gim_next_prime(GUINT number) { - //Find nearest upper prime - GUINT result_ind = 0; - gim_binary_search(gim_prime_list,0,(GIM_NUM_PRIME-2),number,result_ind); + //Find nearest upper prime + GUINT result_ind = 0; + gim_binary_search(gim_prime_list, 0, (GIM_NUM_PRIME - 2), number, result_ind); - // inv: result_ind < 28 - return gim_prime_list[result_ind]; + // inv: result_ind < 28 + return gim_prime_list[result_ind]; } - - //! A compact hash table implementation /*! A memory aligned compact hash table that coud be treated as an array. @@ -187,129 +172,124 @@ When the array size reaches the size equivalent to 'min_hash_table_size', then i </ul> */ -template<class T> +template <class T> class gim_hash_table { protected: - typedef GIM_HASH_TABLE_NODE<T> _node_type; - - //!The nodes - //array< _node_type, SuperAllocator<_node_type> > m_nodes; - gim_array< _node_type > m_nodes; - //SuperBufferedArray< _node_type > m_nodes; - bool m_sorted; - - ///Hash table data management. The hash table has the indices to the corresponding m_nodes array - GUINT * m_hash_table;//!< - GUINT m_table_size;//!< - GUINT m_node_size;//!< - GUINT m_min_hash_table_size; - - - - //! Returns the cell index - inline GUINT _find_cell(GUINT hashkey) - { - _node_type * nodesptr = m_nodes.pointer(); - GUINT start_index = (hashkey%m_table_size)*m_node_size; - GUINT end_index = start_index + m_node_size; - - while(start_index<end_index) - { - GUINT value = m_hash_table[start_index]; - if(value != GIM_INVALID_HASH) - { - if(nodesptr[value].m_key == hashkey) return start_index; - } - start_index++; - } - return GIM_INVALID_HASH; - } - - //! 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) - { - _node_type * nodesptr = m_nodes.pointer(); - GUINT avaliable_index = GIM_INVALID_HASH; - GUINT start_index = (hashkey%m_table_size)*m_node_size; - GUINT end_index = start_index + m_node_size; - - while(start_index<end_index) - { - GUINT value = m_hash_table[start_index]; - if(value == GIM_INVALID_HASH) - { - if(avaliable_index==GIM_INVALID_HASH) - { - avaliable_index = start_index; - } - } - else if(nodesptr[value].m_key == hashkey) - { - return start_index; - } - start_index++; - } - return avaliable_index; - } - - - - //! reserves the memory for the hash table. - /*! + typedef GIM_HASH_TABLE_NODE<T> _node_type; + + //!The nodes + //array< _node_type, SuperAllocator<_node_type> > m_nodes; + gim_array<_node_type> m_nodes; + //SuperBufferedArray< _node_type > m_nodes; + bool m_sorted; + + ///Hash table data management. The hash table has the indices to the corresponding m_nodes array + GUINT* m_hash_table; //!< + GUINT m_table_size; //!< + GUINT m_node_size; //!< + GUINT m_min_hash_table_size; + + //! Returns the cell index + inline GUINT _find_cell(GUINT hashkey) + { + _node_type* nodesptr = m_nodes.pointer(); + GUINT start_index = (hashkey % m_table_size) * m_node_size; + GUINT end_index = start_index + m_node_size; + + while (start_index < end_index) + { + GUINT value = m_hash_table[start_index]; + if (value != GIM_INVALID_HASH) + { + if (nodesptr[value].m_key == hashkey) return start_index; + } + start_index++; + } + return GIM_INVALID_HASH; + } + + //! 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) + { + _node_type* nodesptr = m_nodes.pointer(); + GUINT avaliable_index = GIM_INVALID_HASH; + GUINT start_index = (hashkey % m_table_size) * m_node_size; + GUINT end_index = start_index + m_node_size; + + while (start_index < end_index) + { + GUINT value = m_hash_table[start_index]; + if (value == GIM_INVALID_HASH) + { + if (avaliable_index == GIM_INVALID_HASH) + { + avaliable_index = start_index; + } + } + else if (nodesptr[value].m_key == hashkey) + { + return start_index; + } + start_index++; + } + return avaliable_index; + } + + //! reserves the memory for the hash table. + /*! \pre hash table must be empty \post reserves the memory for the hash table, an initializes all elements to GIM_INVALID_HASH. */ - inline void _reserve_table_memory(GUINT newtablesize) - { - if(newtablesize==0) return; - if(m_node_size==0) return; - - //Get a Prime size - - m_table_size = gim_next_prime(newtablesize); - - GUINT datasize = m_table_size*m_node_size; - //Alloc the data buffer - m_hash_table = (GUINT *)gim_alloc(datasize*sizeof(GUINT)); - } - - inline void _invalidate_keys() - { - GUINT datasize = m_table_size*m_node_size; - for(GUINT i=0;i<datasize;i++) - { - m_hash_table[i] = GIM_INVALID_HASH;// invalidate keys - } - } - - //! Clear all memory for the hash table - inline void _clear_table_memory() - { - if(m_hash_table==NULL) return; - gim_free(m_hash_table); - m_hash_table = NULL; - m_table_size = 0; - } - - //! Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys - inline void _rehash() - { - _invalidate_keys(); - - _node_type * nodesptr = m_nodes.pointer(); - for(GUINT i=0;i<(GUINT)m_nodes.size();i++) - { - GUINT nodekey = nodesptr[i].m_key; - if(nodekey != GIM_INVALID_HASH) - { - //Search for the avaliable cell in buffer - GUINT index = _find_avaliable_cell(nodekey); - - - if(m_hash_table[index]!=GIM_INVALID_HASH) - {//The new index is alreade used... discard this new incomming object, repeated key - btAssert(m_hash_table[index]==nodekey); + inline void _reserve_table_memory(GUINT newtablesize) + { + if (newtablesize == 0) return; + if (m_node_size == 0) return; + + //Get a Prime size + + m_table_size = gim_next_prime(newtablesize); + + GUINT datasize = m_table_size * m_node_size; + //Alloc the data buffer + m_hash_table = (GUINT*)gim_alloc(datasize * sizeof(GUINT)); + } + + inline void _invalidate_keys() + { + GUINT datasize = m_table_size * m_node_size; + for (GUINT i = 0; i < datasize; i++) + { + m_hash_table[i] = GIM_INVALID_HASH; // invalidate keys + } + } + + //! Clear all memory for the hash table + inline void _clear_table_memory() + { + if (m_hash_table == NULL) return; + gim_free(m_hash_table); + m_hash_table = NULL; + m_table_size = 0; + } + + //! Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys + inline void _rehash() + { + _invalidate_keys(); + + _node_type* nodesptr = m_nodes.pointer(); + for (GUINT i = 0; i < (GUINT)m_nodes.size(); i++) + { + GUINT nodekey = nodesptr[i].m_key; + if (nodekey != GIM_INVALID_HASH) + { + //Search for the avaliable cell in buffer + GUINT index = _find_avaliable_cell(nodekey); + + if (m_hash_table[index] != GIM_INVALID_HASH) + { //The new index is alreade used... discard this new incomming object, repeated key + btAssert(m_hash_table[index] == nodekey); nodesptr[i].m_key = GIM_INVALID_HASH; } else @@ -318,585 +298,560 @@ protected: //Assign the value for alloc m_hash_table[index] = i; } - } - } - } - - //! Resize hash table indices - inline void _resize_table(GUINT newsize) - { - //Clear memory - _clear_table_memory(); - //Alloc the data - _reserve_table_memory(newsize); - //Invalidate keys and rehash - _rehash(); - } - - //! Destroy hash table memory - inline void _destroy() - { - if(m_hash_table==NULL) return; - _clear_table_memory(); - } - - //! Finds an avaliable hash table cell, and resizes the table if there isn't space - inline GUINT _assign_hash_table_cell(GUINT hashkey) - { - GUINT cell_index = _find_avaliable_cell(hashkey); - - if(cell_index==GIM_INVALID_HASH) - { - //rehashing - _resize_table(m_table_size+1); - GUINT cell_index = _find_avaliable_cell(hashkey); - btAssert(cell_index!=GIM_INVALID_HASH); - } - return cell_index; - } - - //! erase by index in hash table - inline bool _erase_by_index_hash_table(GUINT index) - { - if(index >= m_nodes.size()) return false; - if(m_nodes[index].m_key != GIM_INVALID_HASH) - { - //Search for the avaliable cell in buffer - GUINT cell_index = _find_cell(m_nodes[index].m_key); - - btAssert(cell_index!=GIM_INVALID_HASH); - btAssert(m_hash_table[cell_index]==index); - - m_hash_table[cell_index] = GIM_INVALID_HASH; - } - - return this->_erase_unsorted(index); - } - - //! erase by key in hash table - inline bool _erase_hash_table(GUINT hashkey) - { - if(hashkey == GIM_INVALID_HASH) return false; - - //Search for the avaliable cell in buffer - GUINT cell_index = _find_cell(hashkey); - if(cell_index ==GIM_INVALID_HASH) return false; - - GUINT index = m_hash_table[cell_index]; - m_hash_table[cell_index] = GIM_INVALID_HASH; - - return this->_erase_unsorted(index); - } - - - - //! insert an element in hash table - /*! + } + } + } + + //! Resize hash table indices + inline void _resize_table(GUINT newsize) + { + //Clear memory + _clear_table_memory(); + //Alloc the data + _reserve_table_memory(newsize); + //Invalidate keys and rehash + _rehash(); + } + + //! Destroy hash table memory + inline void _destroy() + { + if (m_hash_table == NULL) return; + _clear_table_memory(); + } + + //! Finds an avaliable hash table cell, and resizes the table if there isn't space + inline GUINT _assign_hash_table_cell(GUINT hashkey) + { + GUINT cell_index = _find_avaliable_cell(hashkey); + + if (cell_index == GIM_INVALID_HASH) + { + //rehashing + _resize_table(m_table_size + 1); + GUINT cell_index = _find_avaliable_cell(hashkey); + btAssert(cell_index != GIM_INVALID_HASH); + } + return cell_index; + } + + //! erase by index in hash table + inline bool _erase_by_index_hash_table(GUINT index) + { + if (index >= m_nodes.size()) return false; + if (m_nodes[index].m_key != GIM_INVALID_HASH) + { + //Search for the avaliable cell in buffer + GUINT cell_index = _find_cell(m_nodes[index].m_key); + + btAssert(cell_index != GIM_INVALID_HASH); + btAssert(m_hash_table[cell_index] == index); + + m_hash_table[cell_index] = GIM_INVALID_HASH; + } + + return this->_erase_unsorted(index); + } + + //! erase by key in hash table + inline bool _erase_hash_table(GUINT hashkey) + { + if (hashkey == GIM_INVALID_HASH) return false; + + //Search for the avaliable cell in buffer + GUINT cell_index = _find_cell(hashkey); + if (cell_index == GIM_INVALID_HASH) return false; + + GUINT index = m_hash_table[cell_index]; + m_hash_table[cell_index] = GIM_INVALID_HASH; + + return this->_erase_unsorted(index); + } + + //! insert an element in hash table + /*! 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 If so, the element has been inserted at the last position of the array. */ - inline GUINT _insert_hash_table(GUINT hashkey, const T & value) - { - if(hashkey==GIM_INVALID_HASH) - { - //Insert anyway - _insert_unsorted(hashkey,value); - return GIM_INVALID_HASH; - } + inline GUINT _insert_hash_table(GUINT hashkey, const T& value) + { + if (hashkey == GIM_INVALID_HASH) + { + //Insert anyway + _insert_unsorted(hashkey, value); + 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); - return GIM_INVALID_HASH; - } + _insert_unsorted(hashkey, value); + return GIM_INVALID_HASH; + } - //! insert an element in hash table. - /*! + //! insert an element in hash table. + /*! 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 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) - { - if(hashkey==GIM_INVALID_HASH) - { - //Insert anyway - _insert_unsorted(hashkey,value); - return GIM_INVALID_HASH; - } - - GUINT cell_index = _assign_hash_table_cell(hashkey); - - GUINT value_key = m_hash_table[cell_index]; - - if(value_key!= GIM_INVALID_HASH) - {//replaces the existing - m_nodes[value_key] = _node_type(hashkey,value); - return value_key;// index of the replaced element - } - - m_hash_table[cell_index] = m_nodes.size(); - - _insert_unsorted(hashkey,value); - return GIM_INVALID_HASH; - - } - - - ///Sorted array data management. The hash table has the indices to the corresponding m_nodes array - inline bool _erase_sorted(GUINT index) - { - if(index>=(GUINT)m_nodes.size()) return false; - m_nodes.erase_sorted(index); - if(m_nodes.size()<2) m_sorted = false; - return true; - } - - //! faster, but unsorted - inline bool _erase_unsorted(GUINT index) - { - if(index>=m_nodes.size()) return false; - - GUINT lastindex = m_nodes.size()-1; - if(index<lastindex && m_hash_table!=0) - { - GUINT hashkey = m_nodes[lastindex].m_key; - if(hashkey!=GIM_INVALID_HASH) + inline GUINT _insert_hash_table_replace(GUINT hashkey, const T& value) + { + if (hashkey == GIM_INVALID_HASH) + { + //Insert anyway + _insert_unsorted(hashkey, value); + return GIM_INVALID_HASH; + } + + GUINT cell_index = _assign_hash_table_cell(hashkey); + + GUINT value_key = m_hash_table[cell_index]; + + if (value_key != GIM_INVALID_HASH) + { //replaces the existing + m_nodes[value_key] = _node_type(hashkey, value); + return value_key; // index of the replaced element + } + + m_hash_table[cell_index] = m_nodes.size(); + + _insert_unsorted(hashkey, value); + return GIM_INVALID_HASH; + } + + ///Sorted array data management. The hash table has the indices to the corresponding m_nodes array + inline bool _erase_sorted(GUINT index) + { + if (index >= (GUINT)m_nodes.size()) return false; + m_nodes.erase_sorted(index); + if (m_nodes.size() < 2) m_sorted = false; + return true; + } + + //! faster, but unsorted + inline bool _erase_unsorted(GUINT index) + { + if (index >= m_nodes.size()) return false; + + GUINT lastindex = m_nodes.size() - 1; + if (index < lastindex && m_hash_table != 0) + { + GUINT hashkey = m_nodes[lastindex].m_key; + if (hashkey != GIM_INVALID_HASH) { //update the new position of the last element 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 m_hash_table[cell_index] = index; } - } - m_nodes.erase(index); - m_sorted = false; - return true; - } - - //! Insert in position ordered - /*! + } + m_nodes.erase(index); + m_sorted = false; + return true; + } + + //! 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 */ - inline void _insert_in_pos(GUINT hashkey, const T & value, GUINT pos) - { - m_nodes.insert(_node_type(hashkey,value),pos); - this->check_for_switching_to_hashtable(); - } - - //! Insert an element in an ordered array - inline GUINT _insert_sorted(GUINT hashkey, const T & value) - { - if(hashkey==GIM_INVALID_HASH || size()==0) - { - m_nodes.push_back(_node_type(hashkey,value)); - return GIM_INVALID_HASH; - } - //Insert at last position - //Sort element - - - GUINT result_ind=0; - GUINT last_index = m_nodes.size()-1; - _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()); - - - //Insert before found index - if(found) - { - return result_ind; - } - else - { - _insert_in_pos(hashkey, value, result_ind); - } - return GIM_INVALID_HASH; - } - - inline GUINT _insert_sorted_replace(GUINT hashkey, const T & value) - { - if(hashkey==GIM_INVALID_HASH || size()==0) - { - m_nodes.push_back(_node_type(hashkey,value)); - return GIM_INVALID_HASH; - } - //Insert at last position - //Sort element - GUINT result_ind; - GUINT last_index = m_nodes.size()-1; - _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()); - - //Insert before found index - if(found) - { - m_nodes[result_ind] = _node_type(hashkey,value); - } - else - { - _insert_in_pos(hashkey, value, result_ind); - } - return result_ind; - } - - //! Fast insertion in m_nodes array - inline GUINT _insert_unsorted(GUINT hashkey, const T & value) - { - m_nodes.push_back(_node_type(hashkey,value)); - m_sorted = false; - return GIM_INVALID_HASH; - } - - + inline void _insert_in_pos(GUINT hashkey, const T& value, GUINT pos) + { + m_nodes.insert(_node_type(hashkey, value), pos); + this->check_for_switching_to_hashtable(); + } -public: + //! Insert an element in an ordered array + inline GUINT _insert_sorted(GUINT hashkey, const T& value) + { + if (hashkey == GIM_INVALID_HASH || size() == 0) + { + m_nodes.push_back(_node_type(hashkey, value)); + return GIM_INVALID_HASH; + } + //Insert at last position + //Sort element + + GUINT result_ind = 0; + GUINT last_index = m_nodes.size() - 1; + _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()); + + //Insert before found index + if (found) + { + return result_ind; + } + else + { + _insert_in_pos(hashkey, value, result_ind); + } + return GIM_INVALID_HASH; + } - /*! + inline GUINT _insert_sorted_replace(GUINT hashkey, const T& value) + { + if (hashkey == GIM_INVALID_HASH || size() == 0) + { + m_nodes.push_back(_node_type(hashkey, value)); + return GIM_INVALID_HASH; + } + //Insert at last position + //Sort element + GUINT result_ind; + GUINT last_index = m_nodes.size() - 1; + _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()); + + //Insert before found index + if (found) + { + m_nodes[result_ind] = _node_type(hashkey, value); + } + else + { + _insert_in_pos(hashkey, value, result_ind); + } + return result_ind; + } + + //! Fast insertion in m_nodes array + inline GUINT _insert_unsorted(GUINT hashkey, const T& value) + { + m_nodes.push_back(_node_type(hashkey, value)); + m_sorted = false; + return GIM_INVALID_HASH; + } + +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. 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 </ul> */ - 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) - { - m_hash_table = NULL; - m_table_size = 0; - m_sorted = false; - m_node_size = node_size; - m_min_hash_table_size = min_hash_table_size; - - if(m_node_size!=0) - { - if(reserve_size!=0) - { - m_nodes.reserve(reserve_size); - _reserve_table_memory(reserve_size); - _invalidate_keys(); - } - else - { - m_nodes.reserve(GIM_DEFAULT_HASH_TABLE_SIZE); - _reserve_table_memory(GIM_DEFAULT_HASH_TABLE_SIZE); - _invalidate_keys(); - } - } - else if(reserve_size!=0) - { - m_nodes.reserve(reserve_size); - } - - } - - ~gim_hash_table() - { - _destroy(); - } - - inline bool is_hash_table() - { - if(m_hash_table) return true; - return false; - } - - inline bool is_sorted() - { - if(size()<2) return true; - return m_sorted; - } - - bool sort() - { - if(is_sorted()) return true; - if(m_nodes.size()<2) return false; - - - _node_type * ptr = m_nodes.pointer(); - GUINT siz = m_nodes.size(); - gim_sort_hash_node_array(ptr,siz); - m_sorted=true; - - - - if(m_hash_table) - { - _rehash(); - } - return true; - } - - bool switch_to_hashtable() - { - if(m_hash_table) return false; - if(m_node_size==0) m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE; - if(m_nodes.size()<GIM_DEFAULT_HASH_TABLE_SIZE) - { - _resize_table(GIM_DEFAULT_HASH_TABLE_SIZE); - } - else - { - _resize_table(m_nodes.size()+1); - } - - return true; - } - - bool switch_to_sorted_array() - { - if(m_hash_table==NULL) return true; - _clear_table_memory(); - return sort(); - } - - //!If the container reaches the - bool check_for_switching_to_hashtable() - { - if(this->m_hash_table) return true; - - if(!(m_nodes.size()< m_min_hash_table_size)) - { - if(m_node_size == 0) - { - m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE; - } - - _resize_table(m_nodes.size()+1); - return true; - } - return false; - } - - inline void set_sorted(bool value) - { - m_sorted = value; - } - - //! Retrieves the amount of keys. - inline GUINT size() const - { - return m_nodes.size(); - } - - //! Retrieves the hash key. - inline GUINT get_key(GUINT index) const - { - return m_nodes[index].m_key; - } - - //! 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) + { + m_hash_table = NULL; + m_table_size = 0; + m_sorted = false; + m_node_size = node_size; + m_min_hash_table_size = min_hash_table_size; + + if (m_node_size != 0) + { + if (reserve_size != 0) + { + m_nodes.reserve(reserve_size); + _reserve_table_memory(reserve_size); + _invalidate_keys(); + } + else + { + m_nodes.reserve(GIM_DEFAULT_HASH_TABLE_SIZE); + _reserve_table_memory(GIM_DEFAULT_HASH_TABLE_SIZE); + _invalidate_keys(); + } + } + else if (reserve_size != 0) + { + m_nodes.reserve(reserve_size); + } + } + + ~gim_hash_table() + { + _destroy(); + } + + inline bool is_hash_table() + { + if (m_hash_table) return true; + return false; + } + + inline bool is_sorted() + { + if (size() < 2) return true; + return m_sorted; + } + + bool sort() + { + if (is_sorted()) return true; + if (m_nodes.size() < 2) return false; + + _node_type* ptr = m_nodes.pointer(); + GUINT siz = m_nodes.size(); + gim_sort_hash_node_array(ptr, siz); + m_sorted = true; + + if (m_hash_table) + { + _rehash(); + } + return true; + } + + bool switch_to_hashtable() + { + if (m_hash_table) return false; + if (m_node_size == 0) m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE; + if (m_nodes.size() < GIM_DEFAULT_HASH_TABLE_SIZE) + { + _resize_table(GIM_DEFAULT_HASH_TABLE_SIZE); + } + else + { + _resize_table(m_nodes.size() + 1); + } + + return true; + } + + bool switch_to_sorted_array() + { + if (m_hash_table == NULL) return true; + _clear_table_memory(); + return sort(); + } + + //!If the container reaches the + bool check_for_switching_to_hashtable() + { + if (this->m_hash_table) return true; + + if (!(m_nodes.size() < m_min_hash_table_size)) + { + if (m_node_size == 0) + { + m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE; + } + + _resize_table(m_nodes.size() + 1); + return true; + } + return false; + } + + inline void set_sorted(bool value) + { + m_sorted = value; + } + + //! Retrieves the amount of keys. + inline GUINT size() const + { + return m_nodes.size(); + } + + //! Retrieves the hash key. + inline GUINT get_key(GUINT index) const + { + return m_nodes[index].m_key; + } + + //! Retrieves the value by index + /*! */ - inline T * get_value_by_index(GUINT index) - { - return &m_nodes[index].m_data; - } - - inline const T& operator[](GUINT index) const - { - return m_nodes[index].m_data; - } - - inline T& operator[](GUINT index) - { - return m_nodes[index].m_data; - } - - //! Finds the index of the element with the key - /*! + inline T* get_value_by_index(GUINT index) + { + return &m_nodes[index].m_data; + } + + inline const T& operator[](GUINT index) const + { + return m_nodes[index].m_data; + } + + inline T& operator[](GUINT index) + { + return m_nodes[index].m_data; + } + + //! 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 If so, the element has been inserted at the last position of the array. */ - inline GUINT find(GUINT hashkey) - { - if(m_hash_table) - { - GUINT cell_index = _find_cell(hashkey); - if(cell_index==GIM_INVALID_HASH) return GIM_INVALID_HASH; - return m_hash_table[cell_index]; - } + inline GUINT find(GUINT hashkey) + { + if (m_hash_table) + { + GUINT cell_index = _find_cell(hashkey); + if (cell_index == GIM_INVALID_HASH) return GIM_INVALID_HASH; + return m_hash_table[cell_index]; + } GUINT last_index = m_nodes.size(); - if(last_index<2) - { - if(last_index==0) return GIM_INVALID_HASH; - if(m_nodes[0].m_key == hashkey) return 0; - return GIM_INVALID_HASH; - } - else if(m_sorted) - { - //Binary search - GUINT result_ind = 0; + if (last_index < 2) + { + if (last_index == 0) return GIM_INVALID_HASH; + if (m_nodes[0].m_key == hashkey) return 0; + return GIM_INVALID_HASH; + } + else if (m_sorted) + { + //Binary search + GUINT result_ind = 0; 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; + } + return GIM_INVALID_HASH; + } - if(found) return result_ind; - } - return GIM_INVALID_HASH; - } - - //! Retrieves the value associated with the index - /*! + //! Retrieves the value associated with the index + /*! \return the found element, or null */ - inline T * get_value(GUINT hashkey) - { - GUINT index = find(hashkey); - if(index == GIM_INVALID_HASH) return NULL; - return &m_nodes[index].m_data; - } - + inline T* get_value(GUINT hashkey) + { + GUINT index = find(hashkey); + if (index == GIM_INVALID_HASH) return NULL; + return &m_nodes[index].m_data; + } - /*! + /*! */ - inline bool erase_by_index(GUINT index) - { - if(index > m_nodes.size()) return false; - - if(m_hash_table == NULL) - { - if(is_sorted()) - { - return this->_erase_sorted(index); - } - else - { - return this->_erase_unsorted(index); - } - } - else - { - return this->_erase_by_index_hash_table(index); - } - return false; - } - - - - inline bool erase_by_index_unsorted(GUINT index) - { - if(index > m_nodes.size()) return false; - - if(m_hash_table == NULL) - { - return this->_erase_unsorted(index); - } - else - { - return this->_erase_by_index_hash_table(index); - } - return false; - } - - - - /*! + inline bool erase_by_index(GUINT index) + { + if (index > m_nodes.size()) return false; + + if (m_hash_table == NULL) + { + if (is_sorted()) + { + return this->_erase_sorted(index); + } + else + { + return this->_erase_unsorted(index); + } + } + else + { + return this->_erase_by_index_hash_table(index); + } + return false; + } + + inline bool erase_by_index_unsorted(GUINT index) + { + if (index > m_nodes.size()) return false; + + if (m_hash_table == NULL) + { + return this->_erase_unsorted(index); + } + else + { + return this->_erase_by_index_hash_table(index); + } + return false; + } + + /*! */ - inline bool erase_by_key(GUINT hashkey) - { - if(size()==0) return false; - - if(m_hash_table) - { - return this->_erase_hash_table(hashkey); - } - //Binary search - - if(is_sorted()==false) return false; - - GUINT result_ind = find(hashkey); - if(result_ind!= GIM_INVALID_HASH) - { - return this->_erase_sorted(result_ind); - } - return false; - } - - void clear() - { - m_nodes.clear(); - - if(m_hash_table==NULL) return; - GUINT datasize = m_table_size*m_node_size; - //Initialize the hashkeys. - GUINT i; - for(i=0;i<datasize;i++) - { - m_hash_table[i] = GIM_INVALID_HASH;// invalidate keys - } + inline bool erase_by_key(GUINT hashkey) + { + if (size() == 0) return false; + + if (m_hash_table) + { + return this->_erase_hash_table(hashkey); + } + //Binary search + + if (is_sorted() == false) return false; + + GUINT result_ind = find(hashkey); + if (result_ind != GIM_INVALID_HASH) + { + return this->_erase_sorted(result_ind); + } + return false; + } + + void clear() + { + m_nodes.clear(); + + if (m_hash_table == NULL) return; + GUINT datasize = m_table_size * m_node_size; + //Initialize the hashkeys. + GUINT i; + for (i = 0; i < datasize; i++) + { + m_hash_table[i] = GIM_INVALID_HASH; // invalidate keys + } 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 of the existing element. */ - inline GUINT insert(GUINT hashkey, const T & element) - { - if(m_hash_table) - { - return this->_insert_hash_table(hashkey,element); - } - if(this->is_sorted()) - { - return this->_insert_sorted(hashkey,element); - } - return this->_insert_unsorted(hashkey,element); - } - - //! Insert an element into the hash, and could overrite an existing object with the same hash. - /*! + inline GUINT insert(GUINT hashkey, const T& element) + { + if (m_hash_table) + { + return this->_insert_hash_table(hashkey, element); + } + if (this->is_sorted()) + { + return this->_insert_sorted(hashkey, element); + } + return this->_insert_unsorted(hashkey, element); + } + + //! 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 of the replaced element. */ - inline GUINT insert_override(GUINT hashkey, const T & element) - { - if(m_hash_table) - { - return this->_insert_hash_table_replace(hashkey,element); - } - if(this->is_sorted()) - { - return this->_insert_sorted_replace(hashkey,element); - } - this->_insert_unsorted(hashkey,element); - return m_nodes.size(); - } - - - - //! 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) - { - if(m_hash_table) - { - return this->_insert_hash_table(hashkey,element); - } - return this->_insert_unsorted(hashkey,element); - } - + inline GUINT insert_override(GUINT hashkey, const T& element) + { + if (m_hash_table) + { + return this->_insert_hash_table_replace(hashkey, element); + } + if (this->is_sorted()) + { + return this->_insert_sorted_replace(hashkey, element); + } + this->_insert_unsorted(hashkey, element); + return m_nodes.size(); + } + //! 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) + { + if (m_hash_table) + { + return this->_insert_hash_table(hashkey, element); + } + return this->_insert_unsorted(hashkey, element); + } }; - - -#endif // GIM_CONTAINERS_H_INCLUDED +#endif // GIM_CONTAINERS_H_INCLUDED |