diff options
author | Erwin Coumans <blender@erwincoumans.com> | 2008-09-18 00:02:20 +0400 |
---|---|---|
committer | Erwin Coumans <blender@erwincoumans.com> | 2008-09-18 00:02:20 +0400 |
commit | 80f22a9e602c40eca5c7f8a9a7b5b8b291b51bff (patch) | |
tree | e6d9b67c9ae0d413af9f94845dd70e3c344eef98 /extern/bullet2/src/LinearMath | |
parent | 8b73f35141c2572c123791029b58c438d6d5fb9f (diff) |
added another missing file, btHashMap
Diffstat (limited to 'extern/bullet2/src/LinearMath')
-rw-r--r-- | extern/bullet2/src/LinearMath/btHashMap.h | 303 |
1 files changed, 303 insertions, 0 deletions
diff --git a/extern/bullet2/src/LinearMath/btHashMap.h b/extern/bullet2/src/LinearMath/btHashMap.h new file mode 100644 index 00000000000..f883e0e489a --- /dev/null +++ b/extern/bullet2/src/LinearMath/btHashMap.h @@ -0,0 +1,303 @@ +#ifndef BT_HASH_MAP_H +#define BT_HASH_MAP_H + +#include "btAlignedObjectArray.h" + +const int BT_HASH_NULL=0xffffffff; + +template <class Value> +class btHashKey +{ + int m_uid; +public: + + btHashKey(int uid) + :m_uid(uid) + { + } + + int getUid() const + { + return m_uid; + } + + //to our success + SIMD_FORCE_INLINE unsigned int getHash()const + { + int key = m_uid; + // Thomas Wang's hash + key += ~(key << 15); + key ^= (key >> 10); + key += (key << 3); + key ^= (key >> 6); + key += ~(key << 11); + key ^= (key >> 16); + return key; + } + + btHashKey getKey(const Value& value) const + { + return btHashKey(value.getUid()); + } +}; + + +template <class Value> +class btHashKeyPtr +{ + int m_uid; +public: + + btHashKeyPtr(int uid) + :m_uid(uid) + { + } + + int getUid() const + { + return m_uid; + } + + //to our success + SIMD_FORCE_INLINE unsigned int getHash()const + { + int key = m_uid; + // Thomas Wang's hash + key += ~(key << 15); + key ^= (key >> 10); + key += (key << 3); + key ^= (key >> 6); + key += ~(key << 11); + key ^= (key >> 16); + return key; + } + + btHashKeyPtr getKey(const Value& value) const + { + return btHashKeyPtr(value->getUid()); + } +}; + +///The btHashMap template class implements a generic and lightweight hashmap. +///A basic sample of how to use btHashMap is located in Demos\BasicDemo\main.cpp +template <class Key, class Value> +class btHashMap +{ + + btAlignedObjectArray<int> m_hashTable; + btAlignedObjectArray<int> m_next; + btAlignedObjectArray<Value> m_valueArray; + + + + void growTables(const Key& key) + { + int newCapacity = m_valueArray.capacity(); + + if (m_hashTable.size() < newCapacity) + { + //grow hashtable and next table + int curHashtableSize = m_hashTable.size(); + + m_hashTable.resize(newCapacity); + m_next.resize(newCapacity); + + int i; + + for (i= 0; i < newCapacity; ++i) + { + m_hashTable[i] = BT_HASH_NULL; + } + for (i = 0; i < newCapacity; ++i) + { + m_next[i] = BT_HASH_NULL; + } + + for(i=0;i<curHashtableSize;i++) + { + const Value& value = m_valueArray[i]; + + int hashValue = key.getKey(value).getHash() & (m_valueArray.capacity()-1); // New hash value with new mask + m_next[i] = m_hashTable[hashValue]; + m_hashTable[hashValue] = i; + } + + + } + } + + public: + + void insert(const Key& key, const Value& value) { + int hash = key.getHash() & (m_valueArray.capacity()-1); + //don't add it if it is already there + if (find(key)) + { + return; + } + int count = m_valueArray.size(); + int oldCapacity = m_valueArray.capacity(); + m_valueArray.push_back(value); + int newCapacity = m_valueArray.capacity(); + if (oldCapacity < newCapacity) + { + growTables(key); + //hash with new capacity + hash = key.getHash() & (m_valueArray.capacity()-1); + } + m_next[count] = m_hashTable[hash]; + m_hashTable[hash] = count; + } + + void remove(const Key& key) { + + int hash = key.getHash() & (m_valueArray.capacity()-1); + + int pairIndex = findIndex(key); + + if (pairIndex ==BT_HASH_NULL) + { + return; + } + + // Remove the pair from the hash table. + int index = m_hashTable[hash]; + btAssert(index != BT_HASH_NULL); + + int previous = BT_HASH_NULL; + while (index != pairIndex) + { + previous = index; + index = m_next[index]; + } + + if (previous != BT_HASH_NULL) + { + btAssert(m_next[previous] == pairIndex); + m_next[previous] = m_next[pairIndex]; + } + else + { + m_hashTable[hash] = m_next[pairIndex]; + } + + // We now move the last pair into spot of the + // pair being removed. We need to fix the hash + // table indices to support the move. + + int lastPairIndex = m_valueArray.size() - 1; + + // If the removed pair is the last pair, we are done. + if (lastPairIndex == pairIndex) + { + m_valueArray.pop_back(); + return; + } + + // Remove the last pair from the hash table. + const Value* lastValue = &m_valueArray[lastPairIndex]; + int lastHash = key.getKey(*lastValue).getHash() & (m_valueArray.capacity()-1); + + index = m_hashTable[lastHash]; + btAssert(index != BT_HASH_NULL); + + previous = BT_HASH_NULL; + while (index != lastPairIndex) + { + previous = index; + index = m_next[index]; + } + + if (previous != BT_HASH_NULL) + { + btAssert(m_next[previous] == lastPairIndex); + m_next[previous] = m_next[lastPairIndex]; + } + else + { + m_hashTable[lastHash] = m_next[lastPairIndex]; + } + + // Copy the last pair into the remove pair's spot. + m_valueArray[pairIndex] = m_valueArray[lastPairIndex]; + + // Insert the last pair into the hash table + m_next[pairIndex] = m_hashTable[lastHash]; + m_hashTable[lastHash] = pairIndex; + + m_valueArray.pop_back(); + + } + + + int size() const + { + return m_valueArray.size(); + } + + const Value* getAtIndex(int index) const + { + btAssert(index < m_valueArray.size()); + + return &m_valueArray[index]; + } + + Value* getAtIndex(int index) + { + btAssert(index < m_valueArray.size()); + + return &m_valueArray[index]; + } + + Value* operator[](const Key& key) { + return find(key); + } + + const Value* find(const Key& key) const + { + int index = findIndex(key); + if (index == BT_HASH_NULL) + { + return NULL; + } + return &m_valueArray[index]; + } + + Value* find(const Key& key) + { + int index = findIndex(key); + if (index == BT_HASH_NULL) + { + return NULL; + } + return &m_valueArray[index]; + } + + + int findIndex(const Key& key) const + { + int hash = key.getHash() & (m_valueArray.capacity()-1); + + if (hash >= m_hashTable.size()) + { + return BT_HASH_NULL; + } + + int index = m_hashTable[hash]; + while ((index != BT_HASH_NULL) && (key.getUid() == key.getKey(m_valueArray[index]).getUid()) == false) + { + index = m_next[index]; + } + return index; + } + + void clear() + { + m_hashTable.clear(); + m_next.clear(); + m_valueArray.clear(); + } + +}; + +#endif //BT_HASH_MAP_H |