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