dali-physics/third-party/bullet3/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 #ifndef BT_HASH_MAP_H
  17 #define BT_HASH_MAP_H
  18
  19 #include <string>
  20 #include "btAlignedObjectArray.h"
  21
  22 ///very basic hashable string implementation, compatible with btHashMap
  23 struct btHashString
  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
  33         btHashString()
  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:
  69         btHashInt()
  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
 107 class btHashPtr
 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>
 148 class btHashKeyPtr
 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>
 183 class btHashKey
 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
 216 ///The btHashMap template class implements a generic and lightweight hashmap.
 217 ///A basic sample of how to use btHashMap is located in Demos\BasicDemo\main.cpp
 218 template <class Key, class Value>
 219 class btHashMap
 220 {
 221 protected:
 222         btAlignedObjectArray<int> m_hashTable;
 223         btAlignedObjectArray<int> m_next;
 224
 225         btAlignedObjectArray<Value> m_valueArray;
 226         btAlignedObjectArray<Key> m_keyArray;
 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                         {
 244                                 m_hashTable[i] = BT_HASH_NULL;
 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                 }
 288                 m_next[count] = m_hashTable[hash];
 289                 m_hashTable[hash] = count;
 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                 {
 333                         m_valueArray.pop_back();
 334                         m_keyArray.pop_back();
 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
 369                 m_valueArray.pop_back();
 370                 m_keyArray.pop_back();
 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();
 465                 m_valueArray.clear();
 466                 m_keyArray.clear();
 467         }
 468 };
 469
 470 #endif  //BT_HASH_MAP_H