← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to tests/bullet/src/LinearMath/btHashMap.h

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

Lines of Context:
tests/bullet/src/LinearMath/btHashMap.h
 
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
 
 
22
///very basic hashable string implementation, compatible with btHashMap
 
23
struct btHashString
 
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
 
 
112
class btHashPtr
 
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>
 
155
class btHashKeyPtr
 
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>
 
188
class btHashKey
 
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
 
 
217
///The btHashMap template class implements a generic and lightweight hashmap.
 
218
///A basic sample of how to use btHashMap is located in Demos\BasicDemo\main.cpp
 
219
template <class Key, class Value>
 
220
class btHashMap
 
221
{
 
222
 
 
223
protected:
 
224
        btAlignedObjectArray<int>               m_hashTable;
 
225
        btAlignedObjectArray<int>               m_next;
 
226
        
 
227
        btAlignedObjectArray<Value>             m_valueArray;
 
228
        btAlignedObjectArray<Key>               m_keyArray;
 
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