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