source: trunk/src/bullet/LinearMath/btHashMap.h @ 1640

Last change on this file since 1640 was 1640, checked in by sam, 9 years ago

core: fix shitloads of compiler warnings in the Bullet source code.

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