Blender  V3.3
btHashMap.h
Go to the documentation of this file.
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 #ifndef BT_HASH_MAP_H
17 #define BT_HASH_MAP_H
18 
19 #include <string>
20 #include "btAlignedObjectArray.h"
21 
24 {
25  std::string m_string1;
26  unsigned int m_hash;
27 
28  SIMD_FORCE_INLINE unsigned int getHash() const
29  {
30  return m_hash;
31  }
32 
34  {
35  m_string1 = "";
36  m_hash = 0;
37  }
38  btHashString(const char* name)
39  : m_string1(name)
40  {
41  /* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
42  static const unsigned int InitialFNV = 2166136261u;
43  static const unsigned int FNVMultiple = 16777619u;
44 
45  /* Fowler / Noll / Vo (FNV) Hash */
46  unsigned int hash = InitialFNV;
47 
48  for (int i = 0; m_string1.c_str()[i]; i++)
49  {
50  hash = hash ^ (m_string1.c_str()[i]); /* xor the low 8 bits */
51  hash = hash * FNVMultiple; /* multiply by the magic number */
52  }
53  m_hash = hash;
54  }
55 
56  bool equals(const btHashString& other) const
57  {
58  return (m_string1 == other.m_string1);
59  }
60 };
61 
62 const int BT_HASH_NULL = 0xffffffff;
63 
64 class btHashInt
65 {
66  int m_uid;
67 
68 public:
70  {
71  }
72 
73  btHashInt(int uid) : m_uid(uid)
74  {
75  }
76 
77  int getUid1() const
78  {
79  return m_uid;
80  }
81 
82  void setUid1(int uid)
83  {
84  m_uid = uid;
85  }
86 
87  bool equals(const btHashInt& other) const
88  {
89  return getUid1() == other.getUid1();
90  }
91  //to our success
92  SIMD_FORCE_INLINE unsigned int getHash() const
93  {
94  unsigned int key = m_uid;
95  // Thomas Wang's hash
96  key += ~(key << 15);
97  key ^= (key >> 10);
98  key += (key << 3);
99  key ^= (key >> 6);
100  key += ~(key << 11);
101  key ^= (key >> 16);
102 
103  return key;
104  }
105 };
106 
108 {
109  union {
110  const void* m_pointer;
111  unsigned int m_hashValues[2];
112  };
113 
114 public:
115  btHashPtr(const void* ptr)
116  : m_pointer(ptr)
117  {
118  }
119 
120  const void* getPointer() const
121  {
122  return m_pointer;
123  }
124 
125  bool equals(const btHashPtr& other) const
126  {
127  return getPointer() == other.getPointer();
128  }
129 
130  //to our success
131  SIMD_FORCE_INLINE unsigned int getHash() const
132  {
133  const bool VOID_IS_8 = ((sizeof(void*) == 8));
134 
135  unsigned int key = VOID_IS_8 ? m_hashValues[0] + m_hashValues[1] : m_hashValues[0];
136  // Thomas Wang's hash
137  key += ~(key << 15);
138  key ^= (key >> 10);
139  key += (key << 3);
140  key ^= (key >> 6);
141  key += ~(key << 11);
142  key ^= (key >> 16);
143  return key;
144  }
145 };
146 
147 template <class Value>
149 {
150  int m_uid;
151 
152 public:
153  btHashKeyPtr(int uid) : m_uid(uid)
154  {
155  }
156 
157  int getUid1() const
158  {
159  return m_uid;
160  }
161 
162  bool equals(const btHashKeyPtr<Value>& other) const
163  {
164  return getUid1() == other.getUid1();
165  }
166 
167  //to our success
168  SIMD_FORCE_INLINE unsigned int getHash() const
169  {
170  unsigned int key = m_uid;
171  // Thomas Wang's hash
172  key += ~(key << 15);
173  key ^= (key >> 10);
174  key += (key << 3);
175  key ^= (key >> 6);
176  key += ~(key << 11);
177  key ^= (key >> 16);
178  return key;
179  }
180 };
181 
182 template <class Value>
184 {
185  int m_uid;
186 
187 public:
188  btHashKey(int uid) : m_uid(uid)
189  {
190  }
191 
192  int getUid1() const
193  {
194  return m_uid;
195  }
196 
197  bool equals(const btHashKey<Value>& other) const
198  {
199  return getUid1() == other.getUid1();
200  }
201  //to our success
202  SIMD_FORCE_INLINE unsigned int getHash() const
203  {
204  unsigned int key = m_uid;
205  // Thomas Wang's hash
206  key += ~(key << 15);
207  key ^= (key >> 10);
208  key += (key << 3);
209  key ^= (key >> 6);
210  key += ~(key << 11);
211  key ^= (key >> 16);
212  return key;
213  }
214 };
215 
218 template <class Key, class Value>
220 {
221 protected:
224 
227 
228  void growTables(const Key& /*key*/)
229  {
230  int newCapacity = m_valueArray.capacity();
231 
232  if (m_hashTable.size() < newCapacity)
233  {
234  //grow hashtable and next table
235  int curHashtableSize = m_hashTable.size();
236 
237  m_hashTable.resize(newCapacity);
238  m_next.resize(newCapacity);
239 
240  int i;
241 
242  for (i = 0; i < newCapacity; ++i)
243  {
245  }
246  for (i = 0; i < newCapacity; ++i)
247  {
248  m_next[i] = BT_HASH_NULL;
249  }
250 
251  for (i = 0; i < curHashtableSize; i++)
252  {
253  //const Value& value = m_valueArray[i];
254  //const Key& key = m_keyArray[i];
255 
256  int hashValue = m_keyArray[i].getHash() & (m_valueArray.capacity() - 1); // New hash value with new mask
257  m_next[i] = m_hashTable[hashValue];
258  m_hashTable[hashValue] = i;
259  }
260  }
261  }
262 
263 public:
264  void insert(const Key& key, const Value& value)
265  {
266  int hash = key.getHash() & (m_valueArray.capacity() - 1);
267 
268  //replace value if the key is already there
269  int index = findIndex(key);
270  if (index != BT_HASH_NULL)
271  {
272  m_valueArray[index] = value;
273  return;
274  }
275 
276  int count = m_valueArray.size();
277  int oldCapacity = m_valueArray.capacity();
278  m_valueArray.push_back(value);
279  m_keyArray.push_back(key);
280 
281  int newCapacity = m_valueArray.capacity();
282  if (oldCapacity < newCapacity)
283  {
284  growTables(key);
285  //hash with new capacity
286  hash = key.getHash() & (m_valueArray.capacity() - 1);
287  }
290  }
291 
292  void remove(const Key& key)
293  {
294  int hash = key.getHash() & (m_valueArray.capacity() - 1);
295 
296  int pairIndex = findIndex(key);
297 
298  if (pairIndex == BT_HASH_NULL)
299  {
300  return;
301  }
302 
303  // Remove the pair from the hash table.
304  int index = m_hashTable[hash];
305  btAssert(index != BT_HASH_NULL);
306 
307  int previous = BT_HASH_NULL;
308  while (index != pairIndex)
309  {
310  previous = index;
311  index = m_next[index];
312  }
313 
314  if (previous != BT_HASH_NULL)
315  {
316  btAssert(m_next[previous] == pairIndex);
317  m_next[previous] = m_next[pairIndex];
318  }
319  else
320  {
321  m_hashTable[hash] = m_next[pairIndex];
322  }
323 
324  // We now move the last pair into spot of the
325  // pair being removed. We need to fix the hash
326  // table indices to support the move.
327 
328  int lastPairIndex = m_valueArray.size() - 1;
329 
330  // If the removed pair is the last pair, we are done.
331  if (lastPairIndex == pairIndex)
332  {
335  return;
336  }
337 
338  // Remove the last pair from the hash table.
339  int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity() - 1);
340 
341  index = m_hashTable[lastHash];
342  btAssert(index != BT_HASH_NULL);
343 
344  previous = BT_HASH_NULL;
345  while (index != lastPairIndex)
346  {
347  previous = index;
348  index = m_next[index];
349  }
350 
351  if (previous != BT_HASH_NULL)
352  {
353  btAssert(m_next[previous] == lastPairIndex);
354  m_next[previous] = m_next[lastPairIndex];
355  }
356  else
357  {
358  m_hashTable[lastHash] = m_next[lastPairIndex];
359  }
360 
361  // Copy the last pair into the remove pair's spot.
362  m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
363  m_keyArray[pairIndex] = m_keyArray[lastPairIndex];
364 
365  // Insert the last pair into the hash table
366  m_next[pairIndex] = m_hashTable[lastHash];
367  m_hashTable[lastHash] = pairIndex;
368 
371  }
372 
373  int size() const
374  {
375  return m_valueArray.size();
376  }
377 
378  const Value* getAtIndex(int index) const
379  {
380  btAssert(index < m_valueArray.size());
381  btAssert(index >= 0);
382  if (index >= 0 && index < m_valueArray.size())
383  {
384  return &m_valueArray[index];
385  }
386  return 0;
387  }
388 
389  Value* getAtIndex(int index)
390  {
391  btAssert(index < m_valueArray.size());
392  btAssert(index >= 0);
393  if (index >= 0 && index < m_valueArray.size())
394  {
395  return &m_valueArray[index];
396  }
397  return 0;
398  }
399 
400  Key getKeyAtIndex(int index)
401  {
402  btAssert(index < m_keyArray.size());
403  btAssert(index >= 0);
404  return m_keyArray[index];
405  }
406 
407  const Key getKeyAtIndex(int index) const
408  {
409  btAssert(index < m_keyArray.size());
410  btAssert(index >= 0);
411  return m_keyArray[index];
412  }
413 
414  Value* operator[](const Key& key)
415  {
416  return find(key);
417  }
418 
419  const Value* operator[](const Key& key) const
420  {
421  return find(key);
422  }
423 
424  const Value* find(const Key& key) const
425  {
426  int index = findIndex(key);
427  if (index == BT_HASH_NULL)
428  {
429  return NULL;
430  }
431  return &m_valueArray[index];
432  }
433 
434  Value* find(const Key& key)
435  {
436  int index = findIndex(key);
437  if (index == BT_HASH_NULL)
438  {
439  return NULL;
440  }
441  return &m_valueArray[index];
442  }
443 
444  int findIndex(const Key& key) const
445  {
446  unsigned int hash = key.getHash() & (m_valueArray.capacity() - 1);
447 
448  if (hash >= (unsigned int)m_hashTable.size())
449  {
450  return BT_HASH_NULL;
451  }
452 
453  int index = m_hashTable[hash];
454  while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false)
455  {
456  index = m_next[index];
457  }
458  return index;
459  }
460 
461  void clear()
462  {
463  m_hashTable.clear();
464  m_next.clear();
466  m_keyArray.clear();
467  }
468 };
469 
470 #endif //BT_HASH_MAP_H
Group Output data from inside of a node group A color picker Mix two input colors RGB to Convert a color s luminance to a grayscale value Generate a normal vector and a dot product Bright Control the brightness and contrast of the input color Vector Map an input vectors to used to fine tune the interpolation of the input Camera Retrieve information about the camera and how it relates to the current shading point s position Clamp a value between a minimum and a maximum Vector Perform vector math operation Invert a producing a negative Combine Generate a color from its and blue Hue Saturation Value
const int BT_HASH_NULL
Definition: btHashMap.h:62
#define SIMD_FORCE_INLINE
Definition: btScalar.h:280
#define btAssert(x)
Definition: btScalar.h:295
SIMD_FORCE_INLINE void clear()
clear the array, deallocated memory. Generally it is better to use array.resize(0),...
SIMD_FORCE_INLINE int capacity() const
return the pre-allocated (reserved) elements, this is at least as large as the total number of elemen...
SIMD_FORCE_INLINE int size() const
return the number of elements in the array
SIMD_FORCE_INLINE void pop_back()
SIMD_FORCE_INLINE void resize(int newsize, const T &fillData=T())
SIMD_FORCE_INLINE void push_back(const T &_Val)
void setUid1(int uid)
Definition: btHashMap.h:82
btHashInt()
Definition: btHashMap.h:69
btHashInt(int uid)
Definition: btHashMap.h:73
int getUid1() const
Definition: btHashMap.h:77
SIMD_FORCE_INLINE unsigned int getHash() const
Definition: btHashMap.h:92
bool equals(const btHashInt &other) const
Definition: btHashMap.h:87
SIMD_FORCE_INLINE unsigned int getHash() const
Definition: btHashMap.h:168
btHashKeyPtr(int uid)
Definition: btHashMap.h:153
bool equals(const btHashKeyPtr< Value > &other) const
Definition: btHashMap.h:162
int getUid1() const
Definition: btHashMap.h:157
SIMD_FORCE_INLINE unsigned int getHash() const
Definition: btHashMap.h:202
btHashKey(int uid)
Definition: btHashMap.h:188
bool equals(const btHashKey< Value > &other) const
Definition: btHashMap.h:197
int getUid1() const
Definition: btHashMap.h:192
void insert(const Key &key, const Value &value)
Definition: btHashMap.h:264
Key getKeyAtIndex(int index)
Definition: btHashMap.h:400
void clear()
Definition: btHashMap.h:461
int size() const
Definition: btHashMap.h:373
const Value * find(const Key &key) const
Definition: btHashMap.h:424
void growTables(const Key &)
Definition: btHashMap.h:228
Value * getAtIndex(int index)
Definition: btHashMap.h:389
int findIndex(const Key &key) const
Definition: btHashMap.h:444
const Key getKeyAtIndex(int index) const
Definition: btHashMap.h:407
void remove(const Key &key)
Definition: btHashMap.h:292
const Value * operator[](const Key &key) const
Definition: btHashMap.h:419
btAlignedObjectArray< int > m_hashTable
Definition: btHashMap.h:222
btAlignedObjectArray< int > m_next
Definition: btHashMap.h:223
const Value * getAtIndex(int index) const
Definition: btHashMap.h:378
btAlignedObjectArray< Key > m_keyArray
Definition: btHashMap.h:226
btAlignedObjectArray< Value > m_valueArray
Definition: btHashMap.h:225
Value * operator[](const Key &key)
Definition: btHashMap.h:414
Value * find(const Key &key)
Definition: btHashMap.h:434
btHashPtr(const void *ptr)
Definition: btHashMap.h:115
const void * m_pointer
Definition: btHashMap.h:110
SIMD_FORCE_INLINE unsigned int getHash() const
Definition: btHashMap.h:131
bool equals(const btHashPtr &other) const
Definition: btHashMap.h:125
const void * getPointer() const
Definition: btHashMap.h:120
unsigned int m_hashValues[2]
Definition: btHashMap.h:111
int count
#define hash
Definition: noise.c:153
very basic hashable string implementation, compatible with btHashMap
Definition: btHashMap.h:24
bool equals(const btHashString &other) const
Definition: btHashMap.h:56
std::string m_string1
Definition: btHashMap.h:25
btHashString(const char *name)
Definition: btHashMap.h:38
unsigned int m_hash
Definition: btHashMap.h:26
SIMD_FORCE_INLINE unsigned int getHash() const
Definition: btHashMap.h:28
PointerRNA * ptr
Definition: wm_files.c:3480