Bullet Collision Detection & Physics Library
btHashMap.h
Go to the documentation of this file.
1/*
2Bullet Continuous Collision Detection and Physics Library
3Copyright (c) 2003-2009 Erwin Coumans http://bulletphysics.org
4
5This software is provided 'as-is', without any express or implied warranty.
6In no event will the authors be held liable for any damages arising from the use of this software.
7Permission is granted to anyone to use this software for any purpose,
8including commercial applications, and to alter it and redistribute it freely,
9subject to the following restrictions:
10
111. 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.
122. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
133. 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
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
75const int BT_HASH_NULL=0xffffffff;
76
77
79{
80 int m_uid;
81public:
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
127public:
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
159template <class Value>
161{
162 int m_uid;
163public:
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
192template <class Value>
194{
195 int m_uid;
196public:
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
224template <class Key, class Value>
226{
227
228protected:
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 {
342 m_valueArray.pop_back();
343 m_keyArray.pop_back();
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
378 m_valueArray.pop_back();
379 m_keyArray.pop_back();
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();
476 m_valueArray.clear();
477 m_keyArray.clear();
478 }
479
480};
481
482#endif //BT_HASH_MAP_H
const int BT_HASH_NULL
Definition: btHashMap.h:75
#define SIMD_FORCE_INLINE
Definition: btScalar.h:81
#define btAssert(x)
Definition: btScalar.h:131
The btAlignedObjectArray template class uses a subset of the stl::vector interface for its methods It...
void setUid1(int uid)
Definition: btHashMap.h:96
btHashInt()
Definition: btHashMap.h:83
unsigned int getHash() const
Definition: btHashMap.h:106
btHashInt(int uid)
Definition: btHashMap.h:87
int m_uid
Definition: btHashMap.h:80
int getUid1() const
Definition: btHashMap.h:91
bool equals(const btHashInt &other) const
Definition: btHashMap.h:101
btHashKeyPtr(int uid)
Definition: btHashMap.h:165
bool equals(const btHashKeyPtr< Value > &other) const
Definition: btHashMap.h:174
int getUid1() const
Definition: btHashMap.h:169
unsigned int getHash() const
Definition: btHashMap.h:180
unsigned int getHash() const
Definition: btHashMap.h:212
btHashKey(int uid)
Definition: btHashMap.h:198
bool equals(const btHashKey< Value > &other) const
Definition: btHashMap.h:207
int m_uid
Definition: btHashMap.h:195
int getUid1() const
Definition: btHashMap.h:202
The btHashMap template class implements a generic and lightweight hashmap.
Definition: btHashMap.h:226
void insert(const Key &key, const Value &value)
Definition: btHashMap.h:274
Key getKeyAtIndex(int index)
Definition: btHashMap.h:411
void clear()
Definition: btHashMap.h:472
int size() const
Definition: btHashMap.h:384
void growTables(const Key &)
Definition: btHashMap.h:235
Value * operator[](const Key &key)
Definition: btHashMap.h:426
int findIndex(const Key &key) const
Definition: btHashMap.h:455
const Key getKeyAtIndex(int index) const
Definition: btHashMap.h:418
Value * find(const Key &key)
Definition: btHashMap.h:444
void remove(const Key &key)
Definition: btHashMap.h:301
btAlignedObjectArray< int > m_hashTable
Definition: btHashMap.h:229
btAlignedObjectArray< int > m_next
Definition: btHashMap.h:230
const Value * getAtIndex(int index) const
Definition: btHashMap.h:389
btAlignedObjectArray< Key > m_keyArray
Definition: btHashMap.h:233
btAlignedObjectArray< Value > m_valueArray
Definition: btHashMap.h:232
const Value * find(const Key &key) const
Definition: btHashMap.h:434
Value * getAtIndex(int index)
Definition: btHashMap.h:400
const Value * operator[](const Key &key) const
Definition: btHashMap.h:430
const void * getPointer() const
Definition: btHashMap.h:134
btHashPtr(const void *ptr)
Definition: btHashMap.h:129
const void * m_pointer
Definition: btHashMap.h:123
bool equals(const btHashPtr &other) const
Definition: btHashMap.h:139
unsigned int getHash() const
Definition: btHashMap.h:145
unsigned int m_hashValues[2]
Definition: btHashMap.h:124
const bool VOID_IS_8
Definition: bChunk.h:89
very basic hashable string implementation, compatible with btHashMap
Definition: btHashMap.h:24
bool equals(const btHashString &other) const
Definition: btHashMap.h:66
int portableStringCompare(const char *src, const char *dst) const
Definition: btHashMap.h:51
unsigned int getHash() const
Definition: btHashMap.h:28
btHashString(const char *name)
Definition: btHashMap.h:33
unsigned int m_hash
Definition: btHashMap.h:26
const char * m_string
Definition: btHashMap.h:25