Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/gui/src/bullet/LinearMath/btHashMap.h @ 3003

Last change on this file since 3003 was 2662, checked in by rgrieder, 16 years ago

Merged presentation branch back to trunk.

  • Property svn:eol-style set to native
File size: 5.5 KB
Line 
1#ifndef BT_HASH_MAP_H
2#define BT_HASH_MAP_H
3
4#include "btAlignedObjectArray.h"
5
6const int BT_HASH_NULL=0xffffffff;
7
8template <class Value>
9class btHashKey
10{
11        int     m_uid;
12public:
13
14        btHashKey(int uid)
15                :m_uid(uid)
16        {
17        }
18
19        int     getUid() const
20        {
21                return m_uid;
22        }
23
24        //to our success
25        SIMD_FORCE_INLINE       unsigned int getHash()const
26        {
27                int key = m_uid;
28                // Thomas Wang's hash
29                key += ~(key << 15);
30                key ^=  (key >> 10);
31                key +=  (key << 3);
32                key ^=  (key >> 6);
33                key += ~(key << 11);
34                key ^=  (key >> 16);
35                return key;
36        }
37
38        btHashKey       getKey(const Value& value) const
39        {
40                return btHashKey(value.getUid());
41        }
42};
43
44
45template <class Value>
46class btHashKeyPtr
47{
48        int     m_uid;
49public:
50
51        btHashKeyPtr(int uid)
52                :m_uid(uid)
53        {
54        }
55
56        int     getUid() const
57        {
58                return m_uid;
59        }
60
61        //to our success
62        SIMD_FORCE_INLINE       unsigned int getHash()const
63        {
64                int key = m_uid;
65                // Thomas Wang's hash
66                key += ~(key << 15);
67                key ^=  (key >> 10);
68                key +=  (key << 3);
69                key ^=  (key >> 6);
70                key += ~(key << 11);
71                key ^=  (key >> 16);
72                return key;
73        }
74
75        btHashKeyPtr    getKey(const Value& value) const
76        {
77                return btHashKeyPtr(value->getUid());
78        }
79};
80
81///The btHashMap template class implements a generic and lightweight hashmap.
82///A basic sample of how to use btHashMap is located in Demos\BasicDemo\main.cpp
83template <class Key, class Value>
84class btHashMap
85{
86
87        btAlignedObjectArray<int>               m_hashTable;
88        btAlignedObjectArray<int>               m_next;
89        btAlignedObjectArray<Value>             m_valueArray;
90
91
92
93        void    growTables(const Key& key)
94        {
95                int newCapacity = m_valueArray.capacity();
96
97                if (m_hashTable.size() < newCapacity)
98                {
99                        //grow hashtable and next table
100                        int curHashtableSize = m_hashTable.size();
101
102                        m_hashTable.resize(newCapacity);
103                        m_next.resize(newCapacity);
104
105                        int i;
106
107                        for (i= 0; i < newCapacity; ++i)
108                        {
109                                m_hashTable[i] = BT_HASH_NULL;
110                        }
111                        for (i = 0; i < newCapacity; ++i)
112                        {
113                                m_next[i] = BT_HASH_NULL;
114                        }
115
116                        for(i=0;i<curHashtableSize;i++)
117                        {
118                                const Value& value = m_valueArray[i];
119
120                                int     hashValue = key.getKey(value).getHash() & (m_valueArray.capacity()-1);  // New hash value with new mask
121                                m_next[i] = m_hashTable[hashValue];
122                                m_hashTable[hashValue] = i;
123                        }
124
125
126                }
127        }
128
129        public:
130
131        void insert(const Key& key, const Value& value) {
132                int hash = key.getHash() & (m_valueArray.capacity()-1);
133                //don't add it if it is already there
134                if (find(key))
135                {
136                        return;
137                }
138                int count = m_valueArray.size();
139                int oldCapacity = m_valueArray.capacity();
140                m_valueArray.push_back(value);
141                int newCapacity = m_valueArray.capacity();
142                if (oldCapacity < newCapacity)
143                {
144                        growTables(key);
145                        //hash with new capacity
146                        hash = key.getHash() & (m_valueArray.capacity()-1);
147                }
148                m_next[count] = m_hashTable[hash];
149                m_hashTable[hash] = count;
150        }
151
152        void remove(const Key& key) {
153
154                int hash = key.getHash() & (m_valueArray.capacity()-1);
155
156                int pairIndex = findIndex(key);
157               
158                if (pairIndex ==BT_HASH_NULL)
159                {
160                        return;
161                }
162
163                // Remove the pair from the hash table.
164                int index = m_hashTable[hash];
165                btAssert(index != BT_HASH_NULL);
166
167                int previous = BT_HASH_NULL;
168                while (index != pairIndex)
169                {
170                        previous = index;
171                        index = m_next[index];
172                }
173
174                if (previous != BT_HASH_NULL)
175                {
176                        btAssert(m_next[previous] == pairIndex);
177                        m_next[previous] = m_next[pairIndex];
178                }
179                else
180                {
181                        m_hashTable[hash] = m_next[pairIndex];
182                }
183
184                // We now move the last pair into spot of the
185                // pair being removed. We need to fix the hash
186                // table indices to support the move.
187
188                int lastPairIndex = m_valueArray.size() - 1;
189
190                // If the removed pair is the last pair, we are done.
191                if (lastPairIndex == pairIndex)
192                {
193                        m_valueArray.pop_back();
194                        return;
195                }
196
197                // Remove the last pair from the hash table.
198                const Value* lastValue = &m_valueArray[lastPairIndex];
199                int lastHash = key.getKey(*lastValue).getHash() & (m_valueArray.capacity()-1);
200
201                index = m_hashTable[lastHash];
202                btAssert(index != BT_HASH_NULL);
203
204                previous = BT_HASH_NULL;
205                while (index != lastPairIndex)
206                {
207                        previous = index;
208                        index = m_next[index];
209                }
210
211                if (previous != BT_HASH_NULL)
212                {
213                        btAssert(m_next[previous] == lastPairIndex);
214                        m_next[previous] = m_next[lastPairIndex];
215                }
216                else
217                {
218                        m_hashTable[lastHash] = m_next[lastPairIndex];
219                }
220
221                // Copy the last pair into the remove pair's spot.
222                m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
223
224                // Insert the last pair into the hash table
225                m_next[pairIndex] = m_hashTable[lastHash];
226                m_hashTable[lastHash] = pairIndex;
227
228                m_valueArray.pop_back();
229
230        }
231
232
233        int size() const
234        {
235                return m_valueArray.size();
236        }
237
238        const Value* getAtIndex(int index) const
239        {
240                btAssert(index < m_valueArray.size());
241
242                return &m_valueArray[index];
243        }
244
245        Value* getAtIndex(int index)
246        {
247                btAssert(index < m_valueArray.size());
248
249                return &m_valueArray[index];
250        }
251
252        Value* operator[](const Key& key) {
253                return find(key);
254        }
255
256        const Value*    find(const Key& key) const
257        {
258                int index = findIndex(key);
259                if (index == BT_HASH_NULL)
260                {
261                        return NULL;
262                }
263                return &m_valueArray[index];
264        }
265
266        Value*  find(const Key& key)
267        {
268                int index = findIndex(key);
269                if (index == BT_HASH_NULL)
270                {
271                        return NULL;
272                }
273                return &m_valueArray[index];
274        }
275
276
277        int     findIndex(const Key& key) const
278        {
279                int hash = key.getHash() & (m_valueArray.capacity()-1);
280
281                if (hash >= m_hashTable.size())
282                {
283                        return BT_HASH_NULL;
284                }
285
286                int index = m_hashTable[hash];
287                while ((index != BT_HASH_NULL) && (key.getUid() == key.getKey(m_valueArray[index]).getUid()) == false)
288                {
289                        index = m_next[index];
290                }
291                return index;
292        }
293
294        void    clear()
295        {
296                m_hashTable.clear();
297                m_next.clear();
298                m_valueArray.clear();
299        }
300
301};
302
303#endif //BT_HASH_MAP_H
Note: See TracBrowser for help on using the repository browser.