Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/trunk/src/external/bullet/LinearMath/btHashMap.h @ 11255

Last change on this file since 11255 was 8393, checked in by rgrieder, 14 years ago

Updated Bullet from v2.77 to v2.78.
(I'm not going to make a branch for that since the update from 2.74 to 2.77 hasn't been tested that much either).

You will HAVE to do a complete RECOMPILE! I tested with MSVC and MinGW and they both threw linker errors at me.

  • Property svn:eol-style set to native
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                        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
75const int BT_HASH_NULL=0xffffffff;
76
77
78class btHashInt
79{
80        int     m_uid;
81public:
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
112class btHashPtr
113{
114
115        union
116        {
117                const void*     m_pointer;
118                int     m_hashValues[2];
119        };
120
121public:
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
154template <class Value>
155class btHashKeyPtr
156{
157        int     m_uid;
158public:
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
187template <class Value>
188class btHashKey
189{
190        int     m_uid;
191public:
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
219template <class Key, class Value>
220class btHashMap
221{
222
223protected:
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
Note: See TracBrowser for help on using the repository browser.