added another missing file, btHashMap
authorErwin Coumans <blender@erwincoumans.com>
Wed, 17 Sep 2008 20:02:20 +0000 (20:02 +0000)
committerErwin Coumans <blender@erwincoumans.com>
Wed, 17 Sep 2008 20:02:20 +0000 (20:02 +0000)
extern/bullet2/src/LinearMath/btHashMap.h [new file with mode: 0644]

diff --git a/extern/bullet2/src/LinearMath/btHashMap.h b/extern/bullet2/src/LinearMath/btHashMap.h
new file mode 100644 (file)
index 0000000..f883e0e
--- /dev/null
@@ -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