Added minor utility method for btHashMap, btHashString

1 files changed, 86 insertions, 19 deletions

diff --git a/src/LinearMath/btHashMap.h b/src/LinearMath/btHashMap.h
index f883e0e48..98f587c0b 100644
--- a/src/LinearMath/btHashMap.h
+++ b/src/LinearMath/btHashMap.h
@@ -3,6 +3,59 @@
 
 #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 = 2166136261;
+		static const unsigned int FNVMultiple = 16777619;
+
+		/* 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>
@@ -16,11 +69,15 @@ public:
 	{
 	}
 
-	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
 	{
@@ -35,10 +92,7 @@ public:
 		return key;
 	}
 
-	btHashKey	getKey(const Value& value) const
-	{
-		return btHashKey(value.getUid());
-	}
+	
 };
 
 
@@ -53,11 +107,16 @@ public:
 	{
 	}
 
-	int	getUid() const
+	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
 	{
@@ -72,10 +131,7 @@ public:
 		return key;
 	}
 
-	btHashKeyPtr	getKey(const Value& value) const
-	{
-		return btHashKeyPtr(value->getUid());
-	}
+	
 };
 
 ///The btHashMap template class implements a generic and lightweight hashmap.
@@ -86,9 +142,9 @@ class btHashMap
 
 	btAlignedObjectArray<int>		m_hashTable;
 	btAlignedObjectArray<int>		m_next;
+	
 	btAlignedObjectArray<Value>		m_valueArray;
-
-
+	btAlignedObjectArray<Key>		m_keyArray;
 
 	void	growTables(const Key& key)
 	{
@@ -116,8 +172,9 @@ class btHashMap
 			for(i=0;i<curHashtableSize;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 +187,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 +254,13 @@ 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 +284,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 +342,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 +362,7 @@ class btHashMap
 		m_hashTable.clear();
 		m_next.clear();
 		m_valueArray.clear();
+		m_keyArray.clear();
 	}
 
 };