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 = *(const unsigned char *)src - *(const 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) ||
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 
84  {
85  }
86 
87  btHashInt(int uid) :m_uid(uid)
88  {
89  }
90 
91  int getUid1() const
92  {
93  return m_uid;
94  }
95 
96  void setUid1(int uid)
97  {
98  m_uid = uid;
99  }
100 
101  bool equals(const btHashInt& other) const
102  {
103  return getUid1() == other.getUid1();
104  }
105  //to our success
106  SIMD_FORCE_INLINE unsigned int getHash()const
107  {
108  unsigned int key = m_uid;
109  // Thomas Wang's hash
110  key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
111 
112  return key;
113  }
114 };
115 
116 
117 
119 {
120 
121  union
122  {
123  const void* m_pointer;
124  unsigned int m_hashValues[2];
125  };
126 
127 public:
128 
129  btHashPtr(const void* ptr)
130  :m_pointer(ptr)
131  {
132  }
133 
134  const void* getPointer() const
135  {
136  return m_pointer;
137  }
138 
139  bool equals(const btHashPtr& other) const
140  {
141  return getPointer() == other.getPointer();
142  }
143 
144  //to our success
145  SIMD_FORCE_INLINE unsigned int getHash()const
146  {
147  const bool VOID_IS_8 = ((sizeof(void*)==8));
148 
149  unsigned int key = VOID_IS_8? m_hashValues[0]+m_hashValues[1] : m_hashValues[0];
150  // Thomas Wang's hash
151  key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
152  return key;
153  }
154 
155 
156 };
157 
158 
159 template <class Value>
161 {
162  int m_uid;
163 public:
164 
165  btHashKeyPtr(int uid) :m_uid(uid)
166  {
167  }
168 
169  int getUid1() const
170  {
171  return m_uid;
172  }
173 
174  bool equals(const btHashKeyPtr<Value>& other) const
175  {
176  return getUid1() == other.getUid1();
177  }
178 
179  //to our success
180  SIMD_FORCE_INLINE unsigned int getHash()const
181  {
182  unsigned int key = m_uid;
183  // Thomas Wang's hash
184  key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
185  return key;
186  }
187 
188 
189 };
190 
191 
192 template <class Value>
194 {
195  int m_uid;
196 public:
197 
198  btHashKey(int uid) :m_uid(uid)
199  {
200  }
201 
202  int getUid1() const
203  {
204  return m_uid;
205  }
206 
207  bool equals(const btHashKey<Value>& other) const
208  {
209  return getUid1() == other.getUid1();
210  }
211  //to our success
212  SIMD_FORCE_INLINE unsigned int getHash()const
213  {
214  unsigned int key = m_uid;
215  // Thomas Wang's hash
216  key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16);
217  return key;
218  }
219 };
220 
221 
224 template <class Key, class Value>
226 {
227 
228 protected:
231 
234 
235  void growTables(const Key& /*key*/)
236  {
237  int newCapacity = m_valueArray.capacity();
238 
239  if (m_hashTable.size() < newCapacity)
240  {
241  //grow hashtable and next table
242  int curHashtableSize = m_hashTable.size();
243 
244  m_hashTable.resize(newCapacity);
245  m_next.resize(newCapacity);
246 
247  int i;
248 
249  for (i= 0; i < newCapacity; ++i)
250  {
252  }
253  for (i = 0; i < newCapacity; ++i)
254  {
255  m_next[i] = BT_HASH_NULL;
256  }
257 
258  for(i=0;i<curHashtableSize;i++)
259  {
260  //const Value& value = m_valueArray[i];
261  //const Key& key = m_keyArray[i];
262 
263  int hashValue = m_keyArray[i].getHash() & (m_valueArray.capacity()-1); // New hash value with new mask
264  m_next[i] = m_hashTable[hashValue];
265  m_hashTable[hashValue] = i;
266  }
267 
268 
269  }
270  }
271 
272  public:
273 
274  void insert(const Key& key, const Value& value) {
275  int hash = key.getHash() & (m_valueArray.capacity()-1);
276 
277  //replace value if the key is already there
278  int index = findIndex(key);
279  if (index != BT_HASH_NULL)
280  {
281  m_valueArray[index]=value;
282  return;
283  }
284 
285  int count = m_valueArray.size();
286  int oldCapacity = m_valueArray.capacity();
287  m_valueArray.push_back(value);
288  m_keyArray.push_back(key);
289 
290  int newCapacity = m_valueArray.capacity();
291  if (oldCapacity < newCapacity)
292  {
293  growTables(key);
294  //hash with new capacity
295  hash = key.getHash() & (m_valueArray.capacity()-1);
296  }
297  m_next[count] = m_hashTable[hash];
298  m_hashTable[hash] = count;
299  }
300 
301  void remove(const Key& key) {
302 
303  int hash = key.getHash() & (m_valueArray.capacity()-1);
304 
305  int pairIndex = findIndex(key);
306 
307  if (pairIndex ==BT_HASH_NULL)
308  {
309  return;
310  }
311 
312  // Remove the pair from the hash table.
313  int index = m_hashTable[hash];
314  btAssert(index != BT_HASH_NULL);
315 
316  int previous = BT_HASH_NULL;
317  while (index != pairIndex)
318  {
319  previous = index;
320  index = m_next[index];
321  }
322 
323  if (previous != BT_HASH_NULL)
324  {
325  btAssert(m_next[previous] == pairIndex);
326  m_next[previous] = m_next[pairIndex];
327  }
328  else
329  {
330  m_hashTable[hash] = m_next[pairIndex];
331  }
332 
333  // We now move the last pair into spot of the
334  // pair being removed. We need to fix the hash
335  // table indices to support the move.
336 
337  int lastPairIndex = m_valueArray.size() - 1;
338 
339  // If the removed pair is the last pair, we are done.
340  if (lastPairIndex == pairIndex)
341  {
344  return;
345  }
346 
347  // Remove the last pair from the hash table.
348  int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity()-1);
349 
350  index = m_hashTable[lastHash];
351  btAssert(index != BT_HASH_NULL);
352 
353  previous = BT_HASH_NULL;
354  while (index != lastPairIndex)
355  {
356  previous = index;
357  index = m_next[index];
358  }
359 
360  if (previous != BT_HASH_NULL)
361  {
362  btAssert(m_next[previous] == lastPairIndex);
363  m_next[previous] = m_next[lastPairIndex];
364  }
365  else
366  {
367  m_hashTable[lastHash] = m_next[lastPairIndex];
368  }
369 
370  // Copy the last pair into the remove pair's spot.
371  m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
372  m_keyArray[pairIndex] = m_keyArray[lastPairIndex];
373 
374  // Insert the last pair into the hash table
375  m_next[pairIndex] = m_hashTable[lastHash];
376  m_hashTable[lastHash] = pairIndex;
377 
380 
381  }
382 
383 
384  int size() const
385  {
386  return m_valueArray.size();
387  }
388 
389  const Value* getAtIndex(int index) const
390  {
391  btAssert(index < m_valueArray.size());
392  btAssert(index>=0);
393  if (index>=0 && index < m_valueArray.size())
394  {
395  return &m_valueArray[index];
396  }
397  return 0;
398  }
399 
400  Value* getAtIndex(int index)
401  {
402  btAssert(index < m_valueArray.size());
403  btAssert(index>=0);
404  if (index>=0 && index < m_valueArray.size())
405  {
406  return &m_valueArray[index];
407  }
408  return 0;
409  }
410 
411  Key getKeyAtIndex(int index)
412  {
413  btAssert(index < m_keyArray.size());
414  btAssert(index>=0);
415  return m_keyArray[index];
416  }
417 
418  const Key getKeyAtIndex(int index) const
419  {
420  btAssert(index < m_keyArray.size());
421  btAssert(index>=0);
422  return m_keyArray[index];
423  }
424 
425 
426  Value* operator[](const Key& key) {
427  return find(key);
428  }
429 
430  const Value* operator[](const Key& key) const {
431  return find(key);
432  }
433 
434  const Value* find(const Key& key) const
435  {
436  int index = findIndex(key);
437  if (index == BT_HASH_NULL)
438  {
439  return NULL;
440  }
441  return &m_valueArray[index];
442  }
443 
444  Value* find(const Key& key)
445  {
446  int index = findIndex(key);
447  if (index == BT_HASH_NULL)
448  {
449  return NULL;
450  }
451  return &m_valueArray[index];
452  }
453 
454 
455  int findIndex(const Key& key) const
456  {
457  unsigned int hash = key.getHash() & (m_valueArray.capacity()-1);
458 
459  if (hash >= (unsigned int)m_hashTable.size())
460  {
461  return BT_HASH_NULL;
462  }
463 
464  int index = m_hashTable[hash];
465  while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false)
466  {
467  index = m_next[index];
468  }
469  return index;
470  }
471 
472  void clear()
473  {
474  m_hashTable.clear();
475  m_next.clear();
477  m_keyArray.clear();
478  }
479 
480 };
481 
482 #endif //BT_HASH_MAP_H
void clear()
Definition: btHashMap.h:472
const void * getPointer() const
Definition: btHashMap.h:134
btAlignedObjectArray< int > m_hashTable
Definition: btHashMap.h:229
void push_back(const T &_Val)
unsigned int m_hashValues[2]
Definition: btHashMap.h:124
bool equals(const btHashInt &other) const
Definition: btHashMap.h:101
btHashPtr(const void *ptr)
Definition: btHashMap.h:129
const int BT_HASH_NULL
Definition: btHashMap.h:75
bool equals(const btHashKey< Value > &other) const
Definition: btHashMap.h:207
Value * find(const Key &key)
Definition: btHashMap.h:444
int findIndex(const Key &key) const
Definition: btHashMap.h:455
const Value * find(const Key &key) const
Definition: btHashMap.h:434
bool equals(const btHashPtr &other) const
Definition: btHashMap.h:139
unsigned int getHash() const
Definition: btHashMap.h:180
btAlignedObjectArray< int > m_next
Definition: btHashMap.h:230
#define btAssert(x)
Definition: btScalar.h:131
unsigned int m_hash
Definition: btHashMap.h:26
#define SIMD_FORCE_INLINE
Definition: btScalar.h:81
int getUid1() const
Definition: btHashMap.h:169
Value * operator[](const Key &key)
Definition: btHashMap.h:426
const Value * operator[](const Key &key) const
Definition: btHashMap.h:430
btAlignedObjectArray< Key > m_keyArray
Definition: btHashMap.h:233
btHashKey(int uid)
Definition: btHashMap.h:198
The btHashMap template class implements a generic and lightweight hashmap.
Definition: btHashMap.h:225
const Value * getAtIndex(int index) const
Definition: btHashMap.h:389
int size() const
Definition: btHashMap.h:384
unsigned int getHash() const
Definition: btHashMap.h:28
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.
btHashInt()
Definition: btHashMap.h:83
const char * m_string
Definition: btHashMap.h:25
void growTables(const Key &)
Definition: btHashMap.h:235
const bool VOID_IS_8
Definition: bChunk.h:89
Value * getAtIndex(int index)
Definition: btHashMap.h:400
Key getKeyAtIndex(int index)
Definition: btHashMap.h:411
btHashString(const char *name)
Definition: btHashMap.h:33
int capacity() const
return the pre-allocated (reserved) elements, this is at least as large as the total number of elemen...
void insert(const Key &key, const Value &value)
Definition: btHashMap.h:274
btAlignedObjectArray< Value > m_valueArray
Definition: btHashMap.h:232
int size() const
return the number of elements in the array
const void * m_pointer
Definition: btHashMap.h:123
very basic hashable string implementation, compatible with btHashMap
Definition: btHashMap.h:23
int getUid1() const
Definition: btHashMap.h:91
void resize(int newsize, const T &fillData=T())
unsigned int getHash() const
Definition: btHashMap.h:106
unsigned int getHash() const
Definition: btHashMap.h:212
void setUid1(int uid)
Definition: btHashMap.h:96
bool equals(const btHashString &other) const
Definition: btHashMap.h:66
int getUid1() const
Definition: btHashMap.h:202
int m_uid
Definition: btHashMap.h:195
unsigned int getHash() const
Definition: btHashMap.h:145
btHashKeyPtr(int uid)
Definition: btHashMap.h:165
int m_uid
Definition: btHashMap.h:80
bool equals(const btHashKeyPtr< Value > &other) const
Definition: btHashMap.h:174
int portableStringCompare(const char *src, const char *dst) const
Definition: btHashMap.h:51
btHashInt(int uid)
Definition: btHashMap.h:87
const Key getKeyAtIndex(int index) const
Definition: btHashMap.h:418