bullet: Update to current svn, r2636
[blender.git] / extern / bullet2 / 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