diff options
Diffstat (limited to 'extern/bullet2/BulletCollision/Gimpact/gim_hash_table.h')
| -rw-r--r-- | extern/bullet2/BulletCollision/Gimpact/gim_hash_table.h | 902 |
1 files changed, 902 insertions, 0 deletions
diff --git a/extern/bullet2/BulletCollision/Gimpact/gim_hash_table.h b/extern/bullet2/BulletCollision/Gimpact/gim_hash_table.h new file mode 100644 index 00000000000..93c66f81823 --- /dev/null +++ b/extern/bullet2/BulletCollision/Gimpact/gim_hash_table.h @@ -0,0 +1,902 @@ +#ifndef GIM_HASH_TABLE_H_INCLUDED +#define GIM_HASH_TABLE_H_INCLUDED +/*! \file gim_trimesh_data.h +\author Francisco Len Nßjera +*/ +/* +----------------------------------------------------------------------------- +This source file is part of GIMPACT Library. + +For the latest info, see http://gimpact.sourceforge.net/ + +Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371. +email: projectileman@yahoo.com + + This library is free software; you can redistribute it and/or + modify it under the terms of EITHER: + (1) The GNU Lesser General Public License as published by the Free + Software Foundation; either version 2.1 of the License, or (at + your option) any later version. The text of the GNU Lesser + General Public License is included with this library in the + file GIMPACT-LICENSE-LGPL.TXT. + (2) The BSD-style license that is included with this library in + the file GIMPACT-LICENSE-BSD.TXT. + (3) The zlib/libpng license that is included with this library in + the file GIMPACT-LICENSE-ZLIB.TXT. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + 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. + +----------------------------------------------------------------------------- +*/ + +#include "gim_radixsort.h" + + +#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 + +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 + { + ///inverse order, further objects are first + if(m_key < other.m_key) return true; + return false; + } + + bool operator >(const GIM_HASH_TABLE_NODE<T> & other) const + { + ///inverse order, further objects are first + if(m_key > other.m_key) return true; + return false; + } + + bool operator ==(const GIM_HASH_TABLE_NODE<T> & other) const + { + ///inverse order, further objects are first + if(m_key == other.m_key) return true; + return false; + } +}; + +///Macro for getting the key +class GIM_HASH_NODE_GET_KEY +{ +public: + 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) + { + return ((int)(a.m_key - key)); + } +}; + +///Macro for comparing Hash nodes +class GIM_HASH_NODE_CMP_MACRO +{ +public: + 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) +{ + 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 +}; + +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); + + // 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. +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. +</br> + +<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. +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> + +*/ +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. + /*! + \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); + nodesptr[i].m_key = GIM_INVALID_HASH; + } + else + { + //; + //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 + /*! + 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; + } + + GUINT cell_index = _assign_hash_table_cell(hashkey); + + GUINT value_key = m_hash_table[cell_index]; + + if(value_key!= GIM_INVALID_HASH) return value_key;// Not overrited + + m_hash_table[cell_index] = m_nodes.size(); + + _insert_unsorted(hashkey,value); + return GIM_INVALID_HASH; + } + + //! 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) + { + //update the new position of the last element + GUINT cell_index = _find_cell(hashkey); + 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 + /*! + 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; + } + + + +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 + /*! + */ + 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]; + } + 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; + last_index--; + _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()); + + + if(found) return result_ind; + } + return GIM_INVALID_HASH; + } + + //! 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 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 + } + m_sorted = false; + } + + //! 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. + /*! + \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); + } + + +}; + + + +#endif // GIM_CONTAINERS_H_INCLUDED |