dali-physics/third-party/bullet3/src/Bullet3Common/b3HashMap.h

   1 /*
   2 Bullet Continuous Collision Detection and Physics Library
   3 Copyright (c) 2003-2013 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 B3_HASH_MAP_H
  17 #define B3_HASH_MAP_H
  18
  19 #include "b3AlignedObjectArray.h"
  20
  21 #include <string>
  22
  23 ///very basic hashable string implementation, compatible with b3HashMap
  24 struct b3HashString
  25 {
  26         std::string m_string;
  27         unsigned int m_hash;
  28
  29         B3_FORCE_INLINE unsigned int getHash() const
  30         {
  31                 return m_hash;
  32         }
  33
  34         b3HashString(const char* name)
  35                 : m_string(name)
  36         {
  37                 /* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
  38                 static const unsigned int InitialFNV = 2166136261u;
  39                 static const unsigned int FNVMultiple = 16777619u;
  40
  41                 /* Fowler / Noll / Vo (FNV) Hash */
  42                 unsigned int hash = InitialFNV;
  43                 int len = m_string.length();
  44                 for (int i = 0; i < len; i++)
  45                 {
  46                         hash = hash ^ (m_string[i]); /* xor  the low 8 bits */
  47                         hash = hash * FNVMultiple;   /* multiply by the magic number */
  48                 }
  49                 m_hash = hash;
  50         }
  51
  52         int portableStringCompare(const char* src, const char* dst) const
  53         {
  54                 int ret = 0;
  55
  56                 while (!(ret = *(unsigned char*)src - *(unsigned char*)dst) && *dst)
  57                         ++src, ++dst;
  58
  59                 if (ret < 0)
  60                         ret = -1;
  61                 else if (ret > 0)
  62                         ret = 1;
  63
  64                 return (ret);
  65         }
  66
  67         bool equals(const b3HashString& other) const
  68         {
  69                 return (m_string == other.m_string);
  70         }
  71 };
  72
  73 const int B3_HASH_NULL = 0xffffffff;
  74
  75 class b3HashInt
  76 {
  77         int m_uid;
  78
  79 public:
  80         b3HashInt(int uid) : m_uid(uid)
  81         {
  82         }
  83
  84         int getUid1() const
  85         {
  86                 return m_uid;
  87         }
  88
  89         void setUid1(int uid)
  90         {
  91                 m_uid = uid;
  92         }
  93
  94         bool equals(const b3HashInt& other) const
  95         {
  96                 return getUid1() == other.getUid1();
  97         }
  98         //to our success
  99         B3_FORCE_INLINE unsigned int getHash() const
 100         {
 101                 int key = m_uid;
 102                 // Thomas Wang's hash
 103                 key += ~(key << 15);
 104                 key ^= (key >> 10);
 105                 key += (key << 3);
 106                 key ^= (key >> 6);
 107                 key += ~(key << 11);
 108                 key ^= (key >> 16);
 109                 return key;
 110         }
 111 };
 112
 113 class b3HashPtr
 114 {
 115         union {
 116                 const void* m_pointer;
 117                 int m_hashValues[2];
 118         };
 119
 120 public:
 121         b3HashPtr(const void* ptr)
 122                 : m_pointer(ptr)
 123         {
 124         }
 125
 126         const void* getPointer() const
 127         {
 128                 return m_pointer;
 129         }
 130
 131         bool equals(const b3HashPtr& other) const
 132         {
 133                 return getPointer() == other.getPointer();
 134         }
 135
 136         //to our success
 137         B3_FORCE_INLINE unsigned int getHash() const
 138         {
 139                 const bool VOID_IS_8 = ((sizeof(void*) == 8));
 140
 141                 int key = VOID_IS_8 ? m_hashValues[0] + m_hashValues[1] : m_hashValues[0];
 142
 143                 // Thomas Wang's hash
 144                 key += ~(key << 15);
 145                 key ^= (key >> 10);
 146                 key += (key << 3);
 147                 key ^= (key >> 6);
 148                 key += ~(key << 11);
 149                 key ^= (key >> 16);
 150                 return key;
 151         }
 152 };
 153
 154 template <class Value>
 155 class b3HashKeyPtr
 156 {
 157         int m_uid;
 158
 159 public:
 160         b3HashKeyPtr(int uid) : m_uid(uid)
 161         {
 162         }
 163
 164         int getUid1() const
 165         {
 166                 return m_uid;
 167         }
 168
 169         bool equals(const b3HashKeyPtr<Value>& other) const
 170         {
 171                 return getUid1() == other.getUid1();
 172         }
 173
 174         //to our success
 175         B3_FORCE_INLINE unsigned int getHash() const
 176         {
 177                 int key = m_uid;
 178                 // Thomas Wang's hash
 179                 key += ~(key << 15);
 180                 key ^= (key >> 10);
 181                 key += (key << 3);
 182                 key ^= (key >> 6);
 183                 key += ~(key << 11);
 184                 key ^= (key >> 16);
 185                 return key;
 186         }
 187 };
 188
 189 template <class Value>
 190 class b3HashKey
 191 {
 192         int m_uid;
 193
 194 public:
 195         b3HashKey(int uid) : m_uid(uid)
 196         {
 197         }
 198
 199         int getUid1() const
 200         {
 201                 return m_uid;
 202         }
 203
 204         bool equals(const b3HashKey<Value>& other) const
 205         {
 206                 return getUid1() == other.getUid1();
 207         }
 208         //to our success
 209         B3_FORCE_INLINE unsigned int getHash() const
 210         {
 211                 int key = m_uid;
 212                 // Thomas Wang's hash
 213                 key += ~(key << 15);
 214                 key ^= (key >> 10);
 215                 key += (key << 3);
 216                 key ^= (key >> 6);
 217                 key += ~(key << 11);
 218                 key ^= (key >> 16);
 219                 return key;
 220         }
 221 };
 222
 223 ///The b3HashMap template class implements a generic and lightweight hashmap.
 224 ///A basic sample of how to use b3HashMap is located in Demos\BasicDemo\main.cpp
 225 template <class Key, class Value>
 226 class b3HashMap
 227 {
 228 protected:
 229         b3AlignedObjectArray<int> m_hashTable;
 230         b3AlignedObjectArray<int> m_next;
 231
 232         b3AlignedObjectArray<Value> m_valueArray;
 233         b3AlignedObjectArray<Key> m_keyArray;
 234
 235         void growTables(const Key& /*key*/)
 236         {
 237                 int newCapacity = m_valueArray.capacity();
 238
 239                 if (m_hashTable.size() < newCapacity)
 240                 {
 241                         //grow hashtable and next table
 242                         int curHashtableSize = m_hashTable.size();
 243
 244                         m_hashTable.resize(newCapacity);
 245                         m_next.resize(newCapacity);
 246
 247                         int i;
 248
 249                         for (i = 0; i < newCapacity; ++i)
 250                         {
 251                                 m_hashTable[i] = B3_HASH_NULL;
 252                         }
 253                         for (i = 0; i < newCapacity; ++i)
 254                         {
 255                                 m_next[i] = B3_HASH_NULL;
 256                         }
 257
 258                         for (i = 0; i < curHashtableSize; i++)
 259                         {
 260                                 //const Value& value = m_valueArray[i];
 261                                 //const Key& key = m_keyArray[i];
 262
 263                                 int hashValue = m_keyArray[i].getHash() & (m_valueArray.capacity() - 1);  // New hash value with new mask
 264                                 m_next[i] = m_hashTable[hashValue];
 265                                 m_hashTable[hashValue] = i;
 266                         }
 267                 }
 268         }
 269
 270 public:
 271         void insert(const Key& key, const Value& value)
 272         {
 273                 int hash = key.getHash() & (m_valueArray.capacity() - 1);
 274
 275                 //replace value if the key is already there
 276                 int index = findIndex(key);
 277                 if (index != B3_HASH_NULL)
 278                 {
 279                         m_valueArray[index] = value;
 280                         return;
 281                 }
 282
 283                 int count = m_valueArray.size();
 284                 int oldCapacity = m_valueArray.capacity();
 285                 m_valueArray.push_back(value);
 286                 m_keyArray.push_back(key);
 287
 288                 int newCapacity = m_valueArray.capacity();
 289                 if (oldCapacity < newCapacity)
 290                 {
 291                         growTables(key);
 292                         //hash with new capacity
 293                         hash = key.getHash() & (m_valueArray.capacity() - 1);
 294                 }
 295                 m_next[count] = m_hashTable[hash];
 296                 m_hashTable[hash] = count;
 297         }
 298
 299         void remove(const Key& key)
 300         {
 301                 int hash = key.getHash() & (m_valueArray.capacity() - 1);
 302
 303                 int pairIndex = findIndex(key);
 304
 305                 if (pairIndex == B3_HASH_NULL)
 306                 {
 307                         return;
 308                 }
 309
 310                 // Remove the pair from the hash table.
 311                 int index = m_hashTable[hash];
 312                 b3Assert(index != B3_HASH_NULL);
 313
 314                 int previous = B3_HASH_NULL;
 315                 while (index != pairIndex)
 316                 {
 317                         previous = index;
 318                         index = m_next[index];
 319                 }
 320
 321                 if (previous != B3_HASH_NULL)
 322                 {
 323                         b3Assert(m_next[previous] == pairIndex);
 324                         m_next[previous] = m_next[pairIndex];
 325                 }
 326                 else
 327                 {
 328                         m_hashTable[hash] = m_next[pairIndex];
 329                 }
 330
 331                 // We now move the last pair into spot of the
 332                 // pair being removed. We need to fix the hash
 333                 // table indices to support the move.
 334
 335                 int lastPairIndex = m_valueArray.size() - 1;
 336
 337                 // If the removed pair is the last pair, we are done.
 338                 if (lastPairIndex == pairIndex)
 339                 {
 340                         m_valueArray.pop_back();
 341                         m_keyArray.pop_back();
 342                         return;
 343                 }
 344
 345                 // Remove the last pair from the hash table.
 346                 int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity() - 1);
 347
 348                 index = m_hashTable[lastHash];
 349                 b3Assert(index != B3_HASH_NULL);
 350
 351                 previous = B3_HASH_NULL;
 352                 while (index != lastPairIndex)
 353                 {
 354                         previous = index;
 355                         index = m_next[index];
 356                 }
 357
 358                 if (previous != B3_HASH_NULL)
 359                 {
 360                         b3Assert(m_next[previous] == lastPairIndex);
 361                         m_next[previous] = m_next[lastPairIndex];
 362                 }
 363                 else
 364                 {
 365                         m_hashTable[lastHash] = m_next[lastPairIndex];
 366                 }
 367
 368                 // Copy the last pair into the remove pair's spot.
 369                 m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
 370                 m_keyArray[pairIndex] = m_keyArray[lastPairIndex];
 371
 372                 // Insert the last pair into the hash table
 373                 m_next[pairIndex] = m_hashTable[lastHash];
 374                 m_hashTable[lastHash] = pairIndex;
 375
 376                 m_valueArray.pop_back();
 377                 m_keyArray.pop_back();
 378         }
 379
 380         int size() const
 381         {
 382                 return m_valueArray.size();
 383         }
 384
 385         const Value* getAtIndex(int index) const
 386         {
 387                 b3Assert(index < m_valueArray.size());
 388
 389                 return &m_valueArray[index];
 390         }
 391
 392         Value* getAtIndex(int index)
 393         {
 394                 b3Assert(index < m_valueArray.size());
 395
 396                 return &m_valueArray[index];
 397         }
 398
 399         Key getKeyAtIndex(int index)
 400         {
 401                 b3Assert(index < m_keyArray.size());
 402                 return m_keyArray[index];
 403         }
 404
 405         const Key getKeyAtIndex(int index) const
 406         {
 407                 b3Assert(index < m_keyArray.size());
 408                 return m_keyArray[index];
 409         }
 410
 411         Value* operator[](const Key& key)
 412         {
 413                 return find(key);
 414         }
 415
 416         const Value* find(const Key& key) const
 417         {
 418                 int index = findIndex(key);
 419                 if (index == B3_HASH_NULL)
 420                 {
 421                         return NULL;
 422                 }
 423                 return &m_valueArray[index];
 424         }
 425
 426         Value* find(const Key& key)
 427         {
 428                 int index = findIndex(key);
 429                 if (index == B3_HASH_NULL)
 430                 {
 431                         return NULL;
 432                 }
 433                 return &m_valueArray[index];
 434         }
 435
 436         int findIndex(const Key& key) const
 437         {
 438                 unsigned int hash = key.getHash() & (m_valueArray.capacity() - 1);
 439
 440                 if (hash >= (unsigned int)m_hashTable.size())
 441                 {
 442                         return B3_HASH_NULL;
 443                 }
 444
 445                 int index = m_hashTable[hash];
 446                 while ((index != B3_HASH_NULL) && key.equals(m_keyArray[index]) == false)
 447                 {
 448                         index = m_next[index];
 449                 }
 450                 return index;
 451         }
 452
 453         void clear()
 454         {
 455                 m_hashTable.clear();
 456                 m_next.clear();
 457                 m_valueArray.clear();
 458                 m_keyArray.clear();
 459         }
 460 };
 461
 462 #endif  //B3_HASH_MAP_H