| #ifndef BT_HASH_MAP_H | |
| #define BT_HASH_MAP_H | |
| #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 ); | |
| } | |
| const 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 | |
| { | |
| int m_uid; | |
| public: | |
| btHashKey(int uid) | |
| :m_uid(uid) | |
| { | |
| } | |
| 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 | |
| { | |
| unsigned 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 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 | |
| { | |
| unsigned 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; | |
| } | |
| }; | |
| ///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; | |
| btAlignedObjectArray<Key> m_keyArray; | |
| 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]; | |
| //const Key& key = m_keyArray[i]; | |
| 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; | |
| } | |
| } | |
| } | |
| public: | |
| void insert(const Key& key, const Value& value) { | |
| int hash = key.getHash() & (m_valueArray.capacity()-1); | |
| //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) | |
| { | |
| 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(); | |
| m_keyArray.pop_back(); | |
| return; | |
| } | |
| // Remove the last pair from the hash table. | |
| int lastHash = m_keyArray[lastPairIndex].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]; | |
| 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(); | |
| } | |
| 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 | |
| { | |
| unsigned int hash = key.getHash() & (m_valueArray.capacity()-1); | |
| if (hash >= (unsigned int)m_hashTable.size()) | |
| { | |
| return BT_HASH_NULL; | |
| } | |
| int index = m_hashTable[hash]; | |
| while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false) | |
| { | |
| index = m_next[index]; | |
| } | |
| return index; | |
| } | |
| void clear() | |
| { | |
| m_hashTable.clear(); | |
| m_next.clear(); | |
| m_valueArray.clear(); | |
| m_keyArray.clear(); | |
| } | |
| }; | |
| #endif //BT_HASH_MAP_H |