diff options
Diffstat (limited to 'thirdparty/bullet/BulletCollision/Gimpact/gim_hash_table.h')
| -rw-r--r-- | thirdparty/bullet/BulletCollision/Gimpact/gim_hash_table.h | 857 |
1 files changed, 0 insertions, 857 deletions
diff --git a/thirdparty/bullet/BulletCollision/Gimpact/gim_hash_table.h b/thirdparty/bullet/BulletCollision/Gimpact/gim_hash_table.h deleted file mode 100644 index abf88d3108..0000000000 --- a/thirdparty/bullet/BulletCollision/Gimpact/gim_hash_table.h +++ /dev/null @@ -1,857 +0,0 @@ -#ifndef GIM_HASH_TABLE_H_INCLUDED -#define GIM_HASH_TABLE_H_INCLUDED -/*! \file gim_trimesh_data.h -\author Francisco Leon Najera -*/ -/* ------------------------------------------------------------------------------ -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 |