Differential D8762 Diff 28333 extern/bullet2/src/LinearMath/btHashMap.h

Changeset View

Standalone View

extern/bullet2/src/LinearMath/btHashMap.h

/*		/*
Bullet Continuous Collision Detection and Physics Library		Bullet Continuous Collision Detection and Physics Library
Copyright (c) 2003-2009 Erwin Coumans http://bulletphysics.org		Copyright (c) 2003-2009 Erwin Coumans http://bulletphysics.org

This software is provided 'as-is', without any express or implied warranty.		This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.		In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,		Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,		including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:		subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.		1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.		2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.		3. This notice may not be removed or altered from any source distribution.
*/		*/


#ifndef BT_HASH_MAP_H		#ifndef BT_HASH_MAP_H
#define BT_HASH_MAP_H		#define BT_HASH_MAP_H

		#include <string>
#include "btAlignedObjectArray.h"		#include "btAlignedObjectArray.h"

///very basic hashable string implementation, compatible with btHashMap		///very basic hashable string implementation, compatible with btHashMap
struct btHashString		struct btHashString
{		{
const char* m_string;		std::string m_string1;
unsigned int m_hash;		unsigned int m_hash;

SIMD_FORCE_INLINE unsigned int getHash()const		SIMD_FORCE_INLINE unsigned int getHash() const
{		{
return m_hash;		return m_hash;
}		}

		btHashString()
		{
		m_string1 = "";
		m_hash = 0;
		}
btHashString(const char* name)		btHashString(const char* name)
:m_string(name)		: m_string1(name)
{		{
/* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */		/* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
static const unsigned int InitialFNV = 2166136261u;		static const unsigned int InitialFNV = 2166136261u;
static const unsigned int FNVMultiple = 16777619u;		static const unsigned int FNVMultiple = 16777619u;

/* Fowler / Noll / Vo (FNV) Hash */		/* Fowler / Noll / Vo (FNV) Hash */
unsigned int hash = InitialFNV;		unsigned int hash = InitialFNV;

for(int i = 0; m_string[i]; i++)		for (int i = 0; m_string1.c_str()[i]; i++)
{		{
hash = hash ^ (m_string[i]); /* xor the low 8 bits */		hash = hash ^ (m_string1.c_str()[i]); /* xor the low 8 bits */
hash = hash * FNVMultiple; /* multiply by the magic number */		hash = hash * FNVMultiple; /* multiply by the magic number */
}		}
m_hash = hash;		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		bool equals(const btHashString& other) const
{		{
return (m_string == other.m_string) \|\|		return (m_string1 == other.m_string1);
(0==portableStringCompare(m_string,other.m_string));

}		}

};		};

const int BT_HASH_NULL=0xffffffff;		const int BT_HASH_NULL = 0xffffffff;


class btHashInt		class btHashInt
{		{
int m_uid;		int m_uid;

public:		public:
		btHashInt()
		{
		}

btHashInt(int uid) :m_uid(uid)		btHashInt(int uid) : m_uid(uid)
{		{
}		}

int getUid1() const		int getUid1() const
{		{
return m_uid;		return m_uid;
}		}

void setUid1(int uid)		void setUid1(int uid)
{		{
m_uid = uid;		m_uid = uid;
}		}

bool equals(const btHashInt& other) const		bool equals(const btHashInt& other) const
{		{
return getUid1() == other.getUid1();		return getUid1() == other.getUid1();
}		}
//to our success		//to our success
SIMD_FORCE_INLINE unsigned int getHash()const		SIMD_FORCE_INLINE unsigned int getHash() const
{		{
int key = m_uid;		unsigned int key = m_uid;
// Thomas Wang's hash		// 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;		return key;
}		}
};		};



class btHashPtr		class btHashPtr
{		{
		union {
union
{
const void* m_pointer;		const void* m_pointer;
int m_hashValues[2];		unsigned int m_hashValues[2];
};		};

public:		public:

btHashPtr(const void* ptr)		btHashPtr(const void* ptr)
:m_pointer(ptr)		: m_pointer(ptr)
{		{
}		}

const void* getPointer() const		const void* getPointer() const
{		{
return m_pointer;		return m_pointer;
}		}

bool equals(const btHashPtr& other) const		bool equals(const btHashPtr& other) const
{		{
return getPointer() == other.getPointer();		return getPointer() == other.getPointer();
}		}

//to our success		//to our success
SIMD_FORCE_INLINE unsigned int getHash()const		SIMD_FORCE_INLINE unsigned int getHash() const
{		{
const bool VOID_IS_8 = ((sizeof(void*)==8));		const bool VOID_IS_8 = ((sizeof(void*) == 8));

int key = VOID_IS_8? m_hashValues[0]+m_hashValues[1] : m_hashValues[0];		unsigned int key = VOID_IS_8 ? m_hashValues[0] + m_hashValues[1] : m_hashValues[0];

// Thomas Wang's hash		// 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;		return key;
}		}


};		};


template <class Value>		template <class Value>
class btHashKeyPtr		class btHashKeyPtr
{		{
int m_uid;		int m_uid;
public:

		public:
btHashKeyPtr(int uid) :m_uid(uid)		btHashKeyPtr(int uid) : m_uid(uid)
{		{
}		}

int getUid1() const		int getUid1() const
{		{
return m_uid;		return m_uid;
}		}

bool equals(const btHashKeyPtr<Value>& other) const		bool equals(const btHashKeyPtr<Value>& other) const
{		{
return getUid1() == other.getUid1();		return getUid1() == other.getUid1();
}		}

//to our success		//to our success
SIMD_FORCE_INLINE unsigned int getHash()const		SIMD_FORCE_INLINE unsigned int getHash() const
{		{
int key = m_uid;		unsigned int key = m_uid;
// Thomas Wang's hash		// 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;		return key;
}		}


};		};


template <class Value>		template <class Value>
class btHashKey		class btHashKey
{		{
int m_uid;		int m_uid;
public:

		public:
btHashKey(int uid) :m_uid(uid)		btHashKey(int uid) : m_uid(uid)
{		{
}		}

int getUid1() const		int getUid1() const
{		{
return m_uid;		return m_uid;
}		}

bool equals(const btHashKey<Value>& other) const		bool equals(const btHashKey<Value>& other) const
{		{
return getUid1() == other.getUid1();		return getUid1() == other.getUid1();
}		}
//to our success		//to our success
SIMD_FORCE_INLINE unsigned int getHash()const		SIMD_FORCE_INLINE unsigned int getHash() const
{		{
int key = m_uid;		unsigned int key = m_uid;
// Thomas Wang's hash		// 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;		return key;
}		}
};		};


///The btHashMap template class implements a generic and lightweight hashmap.		///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		///A basic sample of how to use btHashMap is located in Demos\BasicDemo\main.cpp
template <class Key, class Value>		template <class Key, class Value>
class btHashMap		class btHashMap
{		{

protected:		protected:
btAlignedObjectArray<int> m_hashTable;		btAlignedObjectArray<int> m_hashTable;
btAlignedObjectArray<int> m_next;		btAlignedObjectArray<int> m_next;

btAlignedObjectArray<Value> m_valueArray;		btAlignedObjectArray<Value> m_valueArray;
btAlignedObjectArray<Key> m_keyArray;		btAlignedObjectArray<Key> m_keyArray;

void growTables(const Key& /key/)		void growTables(const Key& /key/)
{		{
int newCapacity = m_valueArray.capacity();		int newCapacity = m_valueArray.capacity();

if (m_hashTable.size() < newCapacity)		if (m_hashTable.size() < newCapacity)
{		{
//grow hashtable and next table		//grow hashtable and next table
int curHashtableSize = m_hashTable.size();		int curHashtableSize = m_hashTable.size();

m_hashTable.resize(newCapacity);		m_hashTable.resize(newCapacity);
m_next.resize(newCapacity);		m_next.resize(newCapacity);

int i;		int i;

for (i= 0; i < newCapacity; ++i)		for (i = 0; i < newCapacity; ++i)
{		{
m_hashTable[i] = BT_HASH_NULL;		m_hashTable[i] = BT_HASH_NULL;
}		}
for (i = 0; i < newCapacity; ++i)		for (i = 0; i < newCapacity; ++i)
{		{
m_next[i] = BT_HASH_NULL;		m_next[i] = BT_HASH_NULL;
}		}

for(i=0;i<curHashtableSize;i++)		for (i = 0; i < curHashtableSize; i++)
{		{
//const Value& value = m_valueArray[i];		//const Value& value = m_valueArray[i];
//const Key& key = m_keyArray[i];		//const Key& key = m_keyArray[i];

int hashValue = m_keyArray[i].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_next[i] = m_hashTable[hashValue];
m_hashTable[hashValue] = i;		m_hashTable[hashValue] = i;
}		}


}		}
}		}

public:		public:
		void insert(const Key& key, const Value& value)
void insert(const Key& key, const Value& value) {		{
int hash = key.getHash() & (m_valueArray.capacity()-1);		int hash = key.getHash() & (m_valueArray.capacity() - 1);

//replace value if the key is already there		//replace value if the key is already there
int index = findIndex(key);		int index = findIndex(key);
if (index != BT_HASH_NULL)		if (index != BT_HASH_NULL)
{		{
m_valueArray[index]=value;		m_valueArray[index] = value;
return;		return;
}		}

int count = m_valueArray.size();		int count = m_valueArray.size();
int oldCapacity = m_valueArray.capacity();		int oldCapacity = m_valueArray.capacity();
m_valueArray.push_back(value);		m_valueArray.push_back(value);
m_keyArray.push_back(key);		m_keyArray.push_back(key);

int newCapacity = m_valueArray.capacity();		int newCapacity = m_valueArray.capacity();
if (oldCapacity < newCapacity)		if (oldCapacity < newCapacity)
{		{
growTables(key);		growTables(key);
//hash with new capacity		//hash with new capacity
hash = key.getHash() & (m_valueArray.capacity()-1);		hash = key.getHash() & (m_valueArray.capacity() - 1);
}		}
m_next[count] = m_hashTable[hash];		m_next[count] = m_hashTable[hash];
m_hashTable[hash] = count;		m_hashTable[hash] = count;
}		}

void remove(const Key& key) {		void remove(const Key& key)
		{
int hash = key.getHash() & (m_valueArray.capacity()-1);		int hash = key.getHash() & (m_valueArray.capacity() - 1);

int pairIndex = findIndex(key);		int pairIndex = findIndex(key);

if (pairIndex ==BT_HASH_NULL)		if (pairIndex == BT_HASH_NULL)
{		{
return;		return;
}		}

// Remove the pair from the hash table.		// Remove the pair from the hash table.
int index = m_hashTable[hash];		int index = m_hashTable[hash];
btAssert(index != BT_HASH_NULL);		btAssert(index != BT_HASH_NULL);

Show All 24 Lines	void remove(const Key& key)
if (lastPairIndex == pairIndex)		if (lastPairIndex == pairIndex)
{		{
m_valueArray.pop_back();		m_valueArray.pop_back();
m_keyArray.pop_back();		m_keyArray.pop_back();
return;		return;
}		}

// Remove the last pair from the hash table.		// Remove the last pair from the hash table.
int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity()-1);		int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity() - 1);

index = m_hashTable[lastHash];		index = m_hashTable[lastHash];
btAssert(index != BT_HASH_NULL);		btAssert(index != BT_HASH_NULL);

previous = BT_HASH_NULL;		previous = BT_HASH_NULL;
while (index != lastPairIndex)		while (index != lastPairIndex)
{		{
previous = index;		previous = index;
Show All 15 Lines	void remove(const Key& key)
m_keyArray[pairIndex] = m_keyArray[lastPairIndex];		m_keyArray[pairIndex] = m_keyArray[lastPairIndex];

// Insert the last pair into the hash table		// Insert the last pair into the hash table
m_next[pairIndex] = m_hashTable[lastHash];		m_next[pairIndex] = m_hashTable[lastHash];
m_hashTable[lastHash] = pairIndex;		m_hashTable[lastHash] = pairIndex;

m_valueArray.pop_back();		m_valueArray.pop_back();
m_keyArray.pop_back();		m_keyArray.pop_back();

}		}


int size() const		int size() const
{		{
return m_valueArray.size();		return m_valueArray.size();
}		}

const Value* getAtIndex(int index) const		const Value* getAtIndex(int index) const
{		{
btAssert(index < m_valueArray.size());		btAssert(index < m_valueArray.size());
		btAssert(index >= 0);
		if (index >= 0 && index < m_valueArray.size())
		{
return &m_valueArray[index];		return &m_valueArray[index];
}		}
		return 0;
		}

Value* getAtIndex(int index)		Value* getAtIndex(int index)
{		{
btAssert(index < m_valueArray.size());		btAssert(index < m_valueArray.size());
		btAssert(index >= 0);
		if (index >= 0 && index < m_valueArray.size())
		{
return &m_valueArray[index];		return &m_valueArray[index];
}		}
		return 0;
		}

		Key getKeyAtIndex(int index)
		{
		btAssert(index < m_keyArray.size());
		btAssert(index >= 0);
		return m_keyArray[index];
		}

Value* operator[](const Key& key) {		const Key getKeyAtIndex(int index) const
		{
		btAssert(index < m_keyArray.size());
		btAssert(index >= 0);
		return m_keyArray[index];
		}

		Value* operator[](const Key& key)
		{
return find(key);		return find(key);
}		}

const Value* operator[](const Key& key) const {		const Value* operator[](const Key& key) const
		{
return find(key);		return find(key);
}		}

const Value* find(const Key& key) const		const Value* find(const Key& key) const
{		{
int index = findIndex(key);		int index = findIndex(key);
if (index == BT_HASH_NULL)		if (index == BT_HASH_NULL)
{		{
return NULL;		return NULL;
}		}
return &m_valueArray[index];		return &m_valueArray[index];
}		}

Value* find(const Key& key)		Value* find(const Key& key)
{		{
int index = findIndex(key);		int index = findIndex(key);
if (index == BT_HASH_NULL)		if (index == BT_HASH_NULL)
{		{
return NULL;		return NULL;
}		}
return &m_valueArray[index];		return &m_valueArray[index];
}		}


int findIndex(const Key& key) const		int findIndex(const Key& key) const
{		{
unsigned int hash = key.getHash() & (m_valueArray.capacity()-1);		unsigned int hash = key.getHash() & (m_valueArray.capacity() - 1);

if (hash >= (unsigned int)m_hashTable.size())		if (hash >= (unsigned int)m_hashTable.size())
{		{
return BT_HASH_NULL;		return BT_HASH_NULL;
}		}

int index = m_hashTable[hash];		int index = m_hashTable[hash];
while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false)		while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false)
{		{
index = m_next[index];		index = m_next[index];
}		}
return index;		return index;
}		}

void clear()		void clear()
{		{
m_hashTable.clear();		m_hashTable.clear();
m_next.clear();		m_next.clear();
m_valueArray.clear();		m_valueArray.clear();
m_keyArray.clear();		m_keyArray.clear();
}		}

};		};

#endif //BT_HASH_MAP_H		#endif //BT_HASH_MAP_H