Bullet Collision Detection & Physics Library
btHashMap.h
Go to the documentation of this file.
1 /*
2 Bullet Continuous Collision Detection and Physics Library
3 Copyright (c) 2003-2009 Erwin Coumans http://bulletphysics.org
4 
5 This software is provided 'as-is', without any express or implied warranty.
6 In no event will the authors be held liable for any damages arising from the use of this software.
7 Permission is granted to anyone to use this software for any purpose,
8 including commercial applications, and to alter it and redistribute it freely,
9 subject to the following restrictions:
10 
11 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.
12 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
13 3. This notice may not be removed or altered from any source distribution.
14 */
15 
16 
17 #ifndef BT_HASH_MAP_H
18 #define BT_HASH_MAP_H
19 
20 #include "btAlignedObjectArray.h"
21 
24 {
25  const char* m_string;
26  unsigned int m_hash;
27 
28  SIMD_FORCE_INLINE unsigned int getHash()const
29  {
30  return m_hash;
31  }
32 
33  btHashString(const char* name)
34  :m_string(name)
35  {
36  /* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
37  static const unsigned int InitialFNV = 2166136261u;
38  static const unsigned int FNVMultiple = 16777619u;
39 
40  /* Fowler / Noll / Vo (FNV) Hash */
41  unsigned int hash = InitialFNV;
42 
43  for(int i = 0; m_string[i]; i++)
44  {
45  hash = hash ^ (m_string[i]); /* xor the low 8 bits */
46  hash = hash * FNVMultiple; /* multiply by the magic number */
47  }
48  m_hash = hash;
49  }
50 
51  int portableStringCompare(const char* src, const char* dst) const
52  {
53  int ret = 0 ;
54 
55  while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
56  ++src, ++dst;
57 
58  if ( ret < 0 )
59  ret = -1 ;
60  else if ( ret > 0 )
61  ret = 1 ;
62 
63  return( ret );
64  }
65 
66  bool equals(const btHashString& other) const
67  {
68  return (m_string == other.m_string) ||
69  (0==portableStringCompare(m_string,other.m_string));
70 
71  }
72 
73 };
74 
75 const int BT_HASH_NULL=0xffffffff;
76 
77 
78 class btHashInt
79 {
80  int m_uid;
81 public:
82  btHashInt(int uid) :m_uid(uid)
83  {
84  }
85 
86  int getUid1() const
87  {
88  return m_uid;
89  }
90 
91  void setUid1(int uid)
92  {
93  m_uid = uid;
94  }
95 
96  bool equals(const btHashInt& other) const
97  {
98  return getUid1() == other.getUid1();
99  }
100  //to our success
101  SIMD_FORCE_INLINE unsigned int getHash()const
102  {
103  int key = m_uid;
104  // Thomas Wang's hash
105  key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
106  return key;
107  }
108 };
109 
110 
111 
113 {
114 
115  union
116  {
117  const void* m_pointer;
118  int m_hashValues[2];
119  };
120 
121 public:
122 
123  btHashPtr(const void* ptr)
124  :m_pointer(ptr)
125  {
126  }
127 
128  const void* getPointer() const
129  {
130  return m_pointer;
131  }
132 
133  bool equals(const btHashPtr& other) const
134  {
135  return getPointer() == other.getPointer();
136  }
137 
138  //to our success
139  SIMD_FORCE_INLINE unsigned int getHash()const
140  {
141  const bool VOID_IS_8 = ((sizeof(void*)==8));
142 
143  int key = VOID_IS_8? m_hashValues[0]+m_hashValues[1] : m_hashValues[0];
144 
145  // Thomas Wang's hash
146  key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
147  return key;
148  }
149 
150 
151 };
152 
153 
154 template <class Value>
156 {
157  int m_uid;
158 public:
159 
160  btHashKeyPtr(int uid) :m_uid(uid)
161  {
162  }
163 
164  int getUid1() const
165  {
166  return m_uid;
167  }
168 
169  bool equals(const btHashKeyPtr<Value>& other) const
170  {
171  return getUid1() == other.getUid1();
172  }
173 
174  //to our success
175  SIMD_FORCE_INLINE unsigned int getHash()const
176  {
177  int key = m_uid;
178  // Thomas Wang's hash
179  key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
180  return key;
181  }
182 
183 
184 };
185 
186 
187 template <class Value>
189 {
190  int m_uid;
191 public:
192 
193  btHashKey(int uid) :m_uid(uid)
194  {
195  }
196 
197  int getUid1() const
198  {
199  return m_uid;
200  }
201 
202  bool equals(const btHashKey<Value>& other) const
203  {
204  return getUid1() == other.getUid1();
205  }
206  //to our success
207  SIMD_FORCE_INLINE unsigned int getHash()const
208  {
209  int key = m_uid;
210  // Thomas Wang's hash
211  key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
212  return key;
213  }
214 };
215 
216 
219 template <class Key, class Value>
221 {
222 
223 protected:
226 
229 
230  void growTables(const Key& /*key*/)
231  {
232  int newCapacity = m_valueArray.capacity();
233 
234  if (m_hashTable.size() < newCapacity)
235  {
236  //grow hashtable and next table
237  int curHashtableSize = m_hashTable.size();
238 
239  m_hashTable.resize(newCapacity);
240  m_next.resize(newCapacity);
241 
242  int i;
243 
244  for (i= 0; i < newCapacity; ++i)
245  {
246  m_hashTable[i] = BT_HASH_NULL;
247  }
248  for (i = 0; i < newCapacity; ++i)
249  {
250  m_next[i] = BT_HASH_NULL;
251  }
252 
253  for(i=0;i<curHashtableSize;i++)
254  {
255  //const Value& value = m_valueArray[i];
256  //const Key& key = m_keyArray[i];
257 
258  int hashValue = m_keyArray[i].getHash() & (m_valueArray.capacity()-1); // New hash value with new mask
259  m_next[i] = m_hashTable[hashValue];
260  m_hashTable[hashValue] = i;
261  }
262 
263 
264  }
265  }
266 
267  public:
268 
269  void insert(const Key& key, const Value& value) {
270  int hash = key.getHash() & (m_valueArray.capacity()-1);
271 
272  //replace value if the key is already there
273  int index = findIndex(key);
274  if (index != BT_HASH_NULL)
275  {
276  m_valueArray[index]=value;
277  return;
278  }
279 
280  int count = m_valueArray.size();
281  int oldCapacity = m_valueArray.capacity();
282  m_valueArray.push_back(value);
283  m_keyArray.push_back(key);
284 
285  int newCapacity = m_valueArray.capacity();
286  if (oldCapacity < newCapacity)
287  {
288  growTables(key);
289  //hash with new capacity
290  hash = key.getHash() & (m_valueArray.capacity()-1);
291  }
292  m_next[count] = m_hashTable[hash];
293  m_hashTable[hash] = count;
294  }
295 
296  void remove(const Key& key) {
297 
298  int hash = key.getHash() & (m_valueArray.capacity()-1);
299 
300  int pairIndex = findIndex(key);
301 
302  if (pairIndex ==BT_HASH_NULL)
303  {
304  return;
305  }
306 
307  // Remove the pair from the hash table.
308  int index = m_hashTable[hash];
309  btAssert(index != BT_HASH_NULL);
310 
311  int previous = BT_HASH_NULL;
312  while (index != pairIndex)
313  {
314  previous = index;
315  index = m_next[index];
316  }
317 
318  if (previous != BT_HASH_NULL)
319  {
320  btAssert(m_next[previous] == pairIndex);
321  m_next[previous] = m_next[pairIndex];
322  }
323  else
324  {
325  m_hashTable[hash] = m_next[pairIndex];
326  }
327 
328  // We now move the last pair into spot of the
329  // pair being removed. We need to fix the hash
330  // table indices to support the move.
331 
332  int lastPairIndex = m_valueArray.size() - 1;
333 
334  // If the removed pair is the last pair, we are done.
335  if (lastPairIndex == pairIndex)
336  {
337  m_valueArray.pop_back();
338  m_keyArray.pop_back();
339  return;
340  }
341 
342  // Remove the last pair from the hash table.
343  int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity()-1);
344 
345  index = m_hashTable[lastHash];
346  btAssert(index != BT_HASH_NULL);
347 
348  previous = BT_HASH_NULL;
349  while (index != lastPairIndex)
350  {
351  previous = index;
352  index = m_next[index];
353  }
354 
355  if (previous != BT_HASH_NULL)
356  {
357  btAssert(m_next[previous] == lastPairIndex);
358  m_next[previous] = m_next[lastPairIndex];
359  }
360  else
361  {
362  m_hashTable[lastHash] = m_next[lastPairIndex];
363  }
364 
365  // Copy the last pair into the remove pair's spot.
366  m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
367  m_keyArray[pairIndex] = m_keyArray[lastPairIndex];
368 
369  // Insert the last pair into the hash table
370  m_next[pairIndex] = m_hashTable[lastHash];
371  m_hashTable[lastHash] = pairIndex;
372 
373  m_valueArray.pop_back();
374  m_keyArray.pop_back();
375 
376  }
377 
378 
379  int size() const
380  {
381  return m_valueArray.size();
382  }
383 
384  const Value* getAtIndex(int index) const
385  {
386  btAssert(index < m_valueArray.size());
387 
388  return &m_valueArray[index];
389  }
390 
391  Value* getAtIndex(int index)
392  {
393  btAssert(index < m_valueArray.size());
394 
395  return &m_valueArray[index];
396  }
397 
398  Value* operator[](const Key& key) {
399  return find(key);
400  }
401 
402  const Value* find(const Key& key) const
403  {
404  int index = findIndex(key);
405  if (index == BT_HASH_NULL)
406  {
407  return NULL;
408  }
409  return &m_valueArray[index];
410  }
411 
412  Value* find(const Key& key)
413  {
414  int index = findIndex(key);
415  if (index == BT_HASH_NULL)
416  {
417  return NULL;
418  }
419  return &m_valueArray[index];
420  }
421 
422 
423  int findIndex(const Key& key) const
424  {
425  unsigned int hash = key.getHash() & (m_valueArray.capacity()-1);
426 
427  if (hash >= (unsigned int)m_hashTable.size())
428  {
429  return BT_HASH_NULL;
430  }
431 
432  int index = m_hashTable[hash];
433  while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false)
434  {
435  index = m_next[index];
436  }
437  return index;
438  }
439 
440  void clear()
441  {
442  m_hashTable.clear();
443  m_next.clear();
444  m_valueArray.clear();
445  m_keyArray.clear();
446  }
447 
448 };
449 
450 #endif //BT_HASH_MAP_H
void clear()
Definition: btHashMap.h:440
bool equals(const btHashString &other) const
Definition: btHashMap.h:66
btAlignedObjectArray< int > m_hashTable
Definition: btHashMap.h:224
void push_back(const T &_Val)
int findIndex(const Key &key) const
Definition: btHashMap.h:423
btHashPtr(const void *ptr)
Definition: btHashMap.h:123
const int BT_HASH_NULL
Definition: btHashMap.h:75
int m_hashValues[2]
Definition: btHashMap.h:118
Value * find(const Key &key)
Definition: btHashMap.h:412
unsigned int getHash() const
Definition: btHashMap.h:175
btAlignedObjectArray< int > m_next
Definition: btHashMap.h:225
int size() const
Definition: btHashMap.h:379
unsigned int getHash() const
Definition: btHashMap.h:207
#define btAssert(x)
Definition: btScalar.h:113
bool equals(const btHashPtr &other) const
Definition: btHashMap.h:133
unsigned int m_hash
Definition: btHashMap.h:26
#define SIMD_FORCE_INLINE
Definition: btScalar.h:63
int getUid1() const
Definition: btHashMap.h:164
Value * operator[](const Key &key)
Definition: btHashMap.h:398
btAlignedObjectArray< Key > m_keyArray
Definition: btHashMap.h:228
bool equals(const btHashKey< Value > &other) const
Definition: btHashMap.h:202
btHashKey(int uid)
Definition: btHashMap.h:193
The btHashMap template class implements a generic and lightweight hashmap.
Definition: btHashMap.h:220
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
Definition: btHashMap.h:101
int portableStringCompare(const char *src, const char *dst) const
Definition: btHashMap.h:51
const char * m_string
Definition: btHashMap.h:25
int size() const
return the number of elements in the array
void growTables(const Key &)
Definition: btHashMap.h:230
const bool VOID_IS_8
Definition: bChunk.h:89
Value * getAtIndex(int index)
Definition: btHashMap.h:391
bool equals(const btHashKeyPtr< Value > &other) const
Definition: btHashMap.h:169
btHashString(const char *name)
Definition: btHashMap.h:33
int getUid1() const
Definition: btHashMap.h:86
int getUid1() const
Definition: btHashMap.h:197
void insert(const Key &key, const Value &value)
Definition: btHashMap.h:269
bool equals(const btHashInt &other) const
Definition: btHashMap.h:96
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
Definition: btHashMap.h:227
const Value * find(const Key &key) const
Definition: btHashMap.h:402
const Value * getAtIndex(int index) const
Definition: btHashMap.h:384
const void * m_pointer
Definition: btHashMap.h:117
very basic hashable string implementation, compatible with btHashMap
Definition: btHashMap.h:23
unsigned int getHash() const
Definition: btHashMap.h:139
void resize(int newsize, const T &fillData=T())
void setUid1(int uid)
Definition: btHashMap.h:91
int m_uid
Definition: btHashMap.h:190
unsigned int getHash() const
Definition: btHashMap.h:28
btHashKeyPtr(int uid)
Definition: btHashMap.h:160
int m_uid
Definition: btHashMap.h:80
const void * getPointer() const
Definition: btHashMap.h:128
btHashInt(int uid)
Definition: btHashMap.h:82