43 static const unsigned int InitialFNV = 2166136261u;
44 static const unsigned int FNVMultiple = 16777619u;
47 unsigned int hash = InitialFNV;
49 for(
int i = 0; m_string1.c_str()[i]; i++)
51 hash = hash ^ (m_string1.c_str()[i]);
52 hash = hash * FNVMultiple;
91 return getUid1() == other.
getUid1();
96 unsigned int key = m_uid;
98 key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
112 unsigned int m_hashValues[2];
135 const bool VOID_IS_8 = ((
sizeof(
void*)==8));
137 unsigned int key = VOID_IS_8? m_hashValues[0]+m_hashValues[1] : m_hashValues[0];
139 key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
147 template <
class Value>
164 return getUid1() == other.
getUid1();
170 unsigned int key = m_uid;
172 key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
180 template <
class Value>
197 return getUid1() == other.
getUid1();
202 unsigned int key = m_uid;
204 key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
212 template <
class Key,
class Value>
225 int newCapacity = m_valueArray.
capacity();
227 if (m_hashTable.
size() < newCapacity)
230 int curHashtableSize = m_hashTable.
size();
232 m_hashTable.
resize(newCapacity);
233 m_next.
resize(newCapacity);
237 for (i= 0; i < newCapacity; ++i)
241 for (i = 0; i < newCapacity; ++i)
246 for(i=0;i<curHashtableSize;i++)
251 int hashValue = m_keyArray[i].getHash() & (m_valueArray.
capacity()-1);
252 m_next[i] = m_hashTable[hashValue];
253 m_hashTable[hashValue] = i;
262 void insert(
const Key& key,
const Value& value) {
263 int hash = key.getHash() & (m_valueArray.
capacity()-1);
266 int index = findIndex(key);
269 m_valueArray[index]=value;
273 int count = m_valueArray.
size();
274 int oldCapacity = m_valueArray.
capacity();
278 int newCapacity = m_valueArray.
capacity();
279 if (oldCapacity < newCapacity)
283 hash = key.getHash() & (m_valueArray.
capacity()-1);
285 m_next[count] = m_hashTable[hash];
286 m_hashTable[hash] = count;
289 void remove(
const Key& key) {
291 int hash = key.getHash() & (m_valueArray.
capacity()-1);
293 int pairIndex = findIndex(key);
301 int index = m_hashTable[hash];
305 while (index != pairIndex)
308 index = m_next[index];
313 btAssert(m_next[previous] == pairIndex);
314 m_next[previous] = m_next[pairIndex];
318 m_hashTable[hash] = m_next[pairIndex];
325 int lastPairIndex = m_valueArray.
size() - 1;
328 if (lastPairIndex == pairIndex)
336 int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.
capacity()-1);
338 index = m_hashTable[lastHash];
342 while (index != lastPairIndex)
345 index = m_next[index];
350 btAssert(m_next[previous] == lastPairIndex);
351 m_next[previous] = m_next[lastPairIndex];
355 m_hashTable[lastHash] = m_next[lastPairIndex];
359 m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
360 m_keyArray[pairIndex] = m_keyArray[lastPairIndex];
363 m_next[pairIndex] = m_hashTable[lastHash];
364 m_hashTable[lastHash] = pairIndex;
374 return m_valueArray.
size();
381 if (index>=0 && index < m_valueArray.
size())
383 return &m_valueArray[index];
392 if (index>=0 && index < m_valueArray.
size())
394 return &m_valueArray[index];
403 return m_keyArray[index];
410 return m_keyArray[index];
422 const Value*
find(
const Key& key)
const 424 int index = findIndex(key);
429 return &m_valueArray[index];
434 int index = findIndex(key);
439 return &m_valueArray[index];
445 unsigned int hash = key.getHash() & (m_valueArray.
capacity()-1);
447 if (hash >= (
unsigned int)m_hashTable.
size())
452 int index = m_hashTable[hash];
453 while ((index !=
BT_HASH_NULL) && key.equals(m_keyArray[index]) ==
false)
455 index = m_next[index];
464 m_valueArray.
clear();
470 #endif //BT_HASH_MAP_H
bool equals(const btHashString &other) const
btAlignedObjectArray< int > m_hashTable
void push_back(const T &_Val)
int findIndex(const Key &key) const
btHashPtr(const void *ptr)
Value * find(const Key &key)
unsigned int getHash() const
btAlignedObjectArray< int > m_next
unsigned int getHash() const
bool equals(const btHashPtr &other) const
#define SIMD_FORCE_INLINE
Value * operator[](const Key &key)
btAlignedObjectArray< Key > m_keyArray
bool equals(const btHashKey< Value > &other) const
The btHashMap template class implements a generic and lightweight hashmap.
void clear()
clear the array, deallocated memory. Generally it is better to use array.resize(0), to reduce performance overhead of run-time memory (de)allocations.
unsigned int getHash() const
int size() const
return the number of elements in the array
void growTables(const Key &)
Value * getAtIndex(int index)
bool equals(const btHashKeyPtr< Value > &other) const
Key getKeyAtIndex(int index)
btHashString(const char *name)
void insert(const Key &key, const Value &value)
bool equals(const btHashInt &other) const
int capacity() const
return the pre-allocated (reserved) elements, this is at least as large as the total number of elemen...
btAlignedObjectArray< Value > m_valueArray
const Value * find(const Key &key) const
const Value * getAtIndex(int index) const
const Key getKeyAtIndex(int index) const
very basic hashable string implementation, compatible with btHashMap
unsigned int getHash() const
void resize(int newsize, const T &fillData=T())
unsigned int getHash() const
const void * getPointer() const
const Value * operator[](const Key &key) const