diff options
Diffstat (limited to 'extern/bullet2/src/LinearMath/btHashMap.h')
| -rw-r--r-- | extern/bullet2/src/LinearMath/btHashMap.h | 211 |
1 files changed, 171 insertions, 40 deletions
diff --git a/extern/bullet2/src/LinearMath/btHashMap.h b/extern/bullet2/src/LinearMath/btHashMap.h index f883e0e489a..e3302b5e9ff 100644 --- a/extern/bullet2/src/LinearMath/btHashMap.h +++ b/extern/bullet2/src/LinearMath/btHashMap.h @@ -3,94 +3,215 @@ #include "btAlignedObjectArray.h" +///very basic hashable string implementation, compatible with btHashMap +struct btHashString +{ + const char* m_string; + unsigned int m_hash; + + SIMD_FORCE_INLINE unsigned int getHash()const + { + return m_hash; + } + + btHashString(const char* name) + :m_string(name) + { + /* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */ + static const unsigned int InitialFNV = 2166136261u; + static const unsigned int FNVMultiple = 16777619u; + + /* Fowler / Noll / Vo (FNV) Hash */ + unsigned int hash = InitialFNV; + + for(int i = 0; m_string[i]; i++) + { + hash = hash ^ (m_string[i]); /* xor the low 8 bits */ + hash = hash * FNVMultiple; /* multiply by the magic number */ + } + m_hash = hash; + } + + int portableStringCompare(const char* src, const char* dst) const + { + int ret = 0 ; + + while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst) + ++src, ++dst; + + if ( ret < 0 ) + ret = -1 ; + else if ( ret > 0 ) + ret = 1 ; + + return( ret ); + } + + bool equals(const btHashString& other) const + { + return (m_string == other.m_string) || + (0==portableStringCompare(m_string,other.m_string)); + + } + +}; + const int BT_HASH_NULL=0xffffffff; -template <class Value> -class btHashKey + +class btHashInt { int m_uid; public: - - btHashKey(int uid) - :m_uid(uid) + btHashInt(int uid) :m_uid(uid) { } - int getUid() const + int getUid1() const { return m_uid; } + void setUid1(int uid) + { + m_uid = uid; + } + + bool equals(const btHashInt& other) const + { + return getUid1() == other.getUid1(); + } //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); + 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 + + +class btHashPtr +{ + + union { - return btHashKey(value.getUid()); + const void* m_pointer; + int m_hashValues[2]; + }; + +public: + + btHashPtr(const void* ptr) + :m_pointer(ptr) + { + } + + const void* getPointer() const + { + return m_pointer; + } + + bool equals(const btHashPtr& other) const + { + return getPointer() == other.getPointer(); + } + + //to our success + SIMD_FORCE_INLINE unsigned int getHash()const + { + const bool VOID_IS_8 = ((sizeof(void*)==8)); + + int key = VOID_IS_8? m_hashValues[0]+m_hashValues[1] : m_hashValues[0]; + + // Thomas Wang's hash + key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16); + return key; } + + }; template <class Value> class btHashKeyPtr { + int m_uid; +public: + + btHashKeyPtr(int uid) :m_uid(uid) + { + } + + int getUid1() const + { + return m_uid; + } + + bool equals(const btHashKeyPtr<Value>& other) const + { + return getUid1() == other.getUid1(); + } + + //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; + } + + +}; + + +template <class Value> +class btHashKey +{ int m_uid; public: - btHashKeyPtr(int uid) - :m_uid(uid) + btHashKey(int uid) :m_uid(uid) { } - int getUid() const + int getUid1() const { return m_uid; } + bool equals(const btHashKey<Value>& other) const + { + return getUid1() == other.getUid1(); + } //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); + 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 { +protected: btAlignedObjectArray<int> m_hashTable; btAlignedObjectArray<int> m_next; + btAlignedObjectArray<Value> m_valueArray; + btAlignedObjectArray<Key> m_keyArray; - - - void growTables(const Key& key) + void growTables(const Key& /*key*/) { int newCapacity = m_valueArray.capacity(); @@ -115,9 +236,10 @@ class btHashMap for(i=0;i<curHashtableSize;i++) { - const Value& value = m_valueArray[i]; + //const Value& value = m_valueArray[i]; + //const Key& key = m_keyArray[i]; - int hashValue = key.getKey(value).getHash() & (m_valueArray.capacity()-1); // New hash value with new mask + int hashValue = m_keyArray[i].getHash() & (m_valueArray.capacity()-1); // New hash value with new mask m_next[i] = m_hashTable[hashValue]; m_hashTable[hashValue] = i; } @@ -130,14 +252,20 @@ class btHashMap 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)) + + //replace value if the key is already there + int index = findIndex(key); + if (index != BT_HASH_NULL) { + m_valueArray[index]=value; return; } + int count = m_valueArray.size(); int oldCapacity = m_valueArray.capacity(); m_valueArray.push_back(value); + m_keyArray.push_back(key); + int newCapacity = m_valueArray.capacity(); if (oldCapacity < newCapacity) { @@ -191,12 +319,12 @@ class btHashMap if (lastPairIndex == pairIndex) { m_valueArray.pop_back(); + m_keyArray.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); + int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity()-1); index = m_hashTable[lastHash]; btAssert(index != BT_HASH_NULL); @@ -220,12 +348,14 @@ class btHashMap // Copy the last pair into the remove pair's spot. m_valueArray[pairIndex] = m_valueArray[lastPairIndex]; + m_keyArray[pairIndex] = m_keyArray[lastPairIndex]; // Insert the last pair into the hash table m_next[pairIndex] = m_hashTable[lastHash]; m_hashTable[lastHash] = pairIndex; m_valueArray.pop_back(); + m_keyArray.pop_back(); } @@ -276,15 +406,15 @@ class btHashMap int findIndex(const Key& key) const { - int hash = key.getHash() & (m_valueArray.capacity()-1); + unsigned int hash = key.getHash() & (m_valueArray.capacity()-1); - if (hash >= m_hashTable.size()) + if (hash >= (unsigned int)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) + while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false) { index = m_next[index]; } @@ -296,6 +426,7 @@ class btHashMap m_hashTable.clear(); m_next.clear(); m_valueArray.clear(); + m_keyArray.clear(); } }; |