1 /*************************************************************************/ 2 /* hash_map.h */ 3 /*************************************************************************/ 4 /* This file is part of: */ 5 /* GODOT ENGINE */ 6 /* https://godotengine.org */ 7 /*************************************************************************/ 8 /* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ 9 /* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ 10 /* */ 11 /* Permission is hereby granted, free of charge, to any person obtaining */ 12 /* a copy of this software and associated documentation files (the */ 13 /* "Software"), to deal in the Software without restriction, including */ 14 /* without limitation the rights to use, copy, modify, merge, publish, */ 15 /* distribute, sublicense, and/or sell copies of the Software, and to */ 16 /* permit persons to whom the Software is furnished to do so, subject to */ 17 /* the following conditions: */ 18 /* */ 19 /* The above copyright notice and this permission notice shall be */ 20 /* included in all copies or substantial portions of the Software. */ 21 /* */ 22 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ 23 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ 24 /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ 25 /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ 26 /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ 27 /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ 28 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ 29 /*************************************************************************/ 30 #ifndef HASH_MAP_H 31 #define HASH_MAP_H 32 33 #include "hashfuncs.h" 34 #include "list.h" 35 #include "math_funcs.h" 36 #include "os/memory.h" 37 #include "ustring.h" 38 39 struct HashMapHasherDefault { hashHashMapHasherDefault40 static _FORCE_INLINE_ uint32_t hash(const String &p_string) { return p_string.hash(); } hashHashMapHasherDefault41 static _FORCE_INLINE_ uint32_t hash(const char *p_cstr) { return hash_djb2(p_cstr); } hashHashMapHasherDefault42 static _FORCE_INLINE_ uint32_t hash(const uint64_t p_int) { return hash_one_uint64(p_int); } 43 hashHashMapHasherDefault44 static _FORCE_INLINE_ uint32_t hash(const int64_t p_int) { return hash(uint64_t(p_int)); } hashHashMapHasherDefault45 static _FORCE_INLINE_ uint32_t hash(const float p_float) { return hash_djb2_one_float(p_float); } hashHashMapHasherDefault46 static _FORCE_INLINE_ uint32_t hash(const double p_double) { return hash_djb2_one_float(p_double); } hashHashMapHasherDefault47 static _FORCE_INLINE_ uint32_t hash(const uint32_t p_int) { return p_int; } hashHashMapHasherDefault48 static _FORCE_INLINE_ uint32_t hash(const int32_t p_int) { return (uint32_t)p_int; } hashHashMapHasherDefault49 static _FORCE_INLINE_ uint32_t hash(const uint16_t p_int) { return p_int; } hashHashMapHasherDefault50 static _FORCE_INLINE_ uint32_t hash(const int16_t p_int) { return (uint32_t)p_int; } hashHashMapHasherDefault51 static _FORCE_INLINE_ uint32_t hash(const uint8_t p_int) { return p_int; } hashHashMapHasherDefault52 static _FORCE_INLINE_ uint32_t hash(const int8_t p_int) { return (uint32_t)p_int; } hashHashMapHasherDefault53 static _FORCE_INLINE_ uint32_t hash(const wchar_t p_wchar) { return (uint32_t)p_wchar; } 54 //static _FORCE_INLINE_ uint32_t hash(const void* p_ptr) { return uint32_t(uint64_t(p_ptr))*(0x9e3779b1L); } 55 }; 56 57 template <typename T> 58 struct HashMapComparatorDefault { compareHashMapComparatorDefault59 static bool compare(const T &p_lhs, const T &p_rhs) { 60 return p_lhs == p_rhs; 61 } 62 compareHashMapComparatorDefault63 bool compare(const float &p_lhs, const float &p_rhs) { 64 return (p_lhs == p_rhs) || (Math::is_nan(p_lhs) && Math::is_nan(p_rhs)); 65 } 66 compareHashMapComparatorDefault67 bool compare(const double &p_lhs, const double &p_rhs) { 68 return (p_lhs == p_rhs) || (Math::is_nan(p_lhs) && Math::is_nan(p_rhs)); 69 } 70 }; 71 72 /** 73 * @class HashMap 74 * @author Juan Linietsky <reduzio@gmail.com> 75 * 76 * Implementation of a standard Hashing HashMap, for quick lookups of Data associated with a Key. 77 * The implementation provides hashers for the default types, if you need a special kind of hasher, provide 78 * your own. 79 * @param TKey Key, search is based on it, needs to be hasheable. It is unique in this container. 80 * @param TData Data, data associated with the key 81 * @param Hasher Hasher object, needs to provide a valid static hash function for TKey 82 * @param Comparator comparator object, needs to be able to safely compare two TKey values. It needs to ensure that x == x for any items inserted in the map. Bear in mind that nan != nan when implementing an equality check. 83 * @param MIN_HASH_TABLE_POWER Miminum size of the hash table, as a power of two. You rarely need to change this parameter. 84 * @param RELATIONSHIP Relationship at which the hash table is resized. if amount of elements is RELATIONSHIP 85 * times bigger than the hash table, table is resized to solve this condition. if RELATIONSHIP is zero, table is always MIN_HASH_TABLE_POWER. 86 * 87 */ 88 89 template <class TKey, class TData, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<TKey>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8> 90 class HashMap { 91 public: 92 struct Pair { 93 94 TKey key; 95 TData data; 96 PairPair97 Pair() {} PairPair98 Pair(const TKey &p_key, const TData &p_data) { 99 key = p_key; 100 data = p_data; 101 } 102 }; 103 104 private: 105 struct Entry { 106 107 uint32_t hash; 108 Entry *next; 109 Pair pair; 110 EntryEntry111 Entry() { next = 0; } 112 }; 113 114 Entry **hash_table; 115 uint8_t hash_table_power; 116 uint32_t elements; 117 make_hash_table()118 void make_hash_table() { 119 120 ERR_FAIL_COND(hash_table); 121 122 hash_table = memnew_arr(Entry *, (1 << MIN_HASH_TABLE_POWER)); 123 124 hash_table_power = MIN_HASH_TABLE_POWER; 125 elements = 0; 126 for (int i = 0; i < (1 << MIN_HASH_TABLE_POWER); i++) 127 hash_table[i] = 0; 128 } 129 erase_hash_table()130 void erase_hash_table() { 131 132 ERR_FAIL_COND(elements); 133 134 memdelete_arr(hash_table); 135 hash_table = 0; 136 hash_table_power = 0; 137 elements = 0; 138 } 139 check_hash_table()140 void check_hash_table() { 141 142 int new_hash_table_power = -1; 143 144 if ((int)elements > ((1 << hash_table_power) * RELATIONSHIP)) { 145 /* rehash up */ 146 new_hash_table_power = hash_table_power + 1; 147 148 while ((int)elements > ((1 << new_hash_table_power) * RELATIONSHIP)) { 149 150 new_hash_table_power++; 151 } 152 153 } else if ((hash_table_power > (int)MIN_HASH_TABLE_POWER) && ((int)elements < ((1 << (hash_table_power - 1)) * RELATIONSHIP))) { 154 155 /* rehash down */ 156 new_hash_table_power = hash_table_power - 1; 157 158 while ((int)elements < ((1 << (new_hash_table_power - 1)) * RELATIONSHIP)) { 159 160 new_hash_table_power--; 161 } 162 163 if (new_hash_table_power < (int)MIN_HASH_TABLE_POWER) 164 new_hash_table_power = MIN_HASH_TABLE_POWER; 165 } 166 167 if (new_hash_table_power == -1) 168 return; 169 170 Entry **new_hash_table = memnew_arr(Entry *, (1 << new_hash_table_power)); 171 if (!new_hash_table) { 172 173 ERR_PRINT("Out of Memory"); 174 return; 175 } 176 177 for (int i = 0; i < (1 << new_hash_table_power); i++) { 178 179 new_hash_table[i] = 0; 180 } 181 182 for (int i = 0; i < (1 << hash_table_power); i++) { 183 184 while (hash_table[i]) { 185 186 Entry *se = hash_table[i]; 187 hash_table[i] = se->next; 188 int new_pos = se->hash & ((1 << new_hash_table_power) - 1); 189 se->next = new_hash_table[new_pos]; 190 new_hash_table[new_pos] = se; 191 } 192 } 193 194 if (hash_table) 195 memdelete_arr(hash_table); 196 hash_table = new_hash_table; 197 hash_table_power = new_hash_table_power; 198 } 199 200 /* I want to have only one function.. */ get_entry(const TKey & p_key)201 _FORCE_INLINE_ const Entry *get_entry(const TKey &p_key) const { 202 203 uint32_t hash = Hasher::hash(p_key); 204 uint32_t index = hash & ((1 << hash_table_power) - 1); 205 206 Entry *e = hash_table[index]; 207 208 while (e) { 209 210 /* checking hash first avoids comparing key, which may take longer */ 211 if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) { 212 213 /* the pair exists in this hashtable, so just update data */ 214 return e; 215 } 216 217 e = e->next; 218 } 219 220 return NULL; 221 } 222 create_entry(const TKey & p_key)223 Entry *create_entry(const TKey &p_key) { 224 225 /* if entry doesn't exist, create it */ 226 Entry *e = memnew(Entry); 227 ERR_FAIL_COND_V(!e, NULL); /* out of memory */ 228 uint32_t hash = Hasher::hash(p_key); 229 uint32_t index = hash & ((1 << hash_table_power) - 1); 230 e->next = hash_table[index]; 231 e->hash = hash; 232 e->pair.key = p_key; 233 234 hash_table[index] = e; 235 elements++; 236 237 return e; 238 } 239 copy_from(const HashMap & p_t)240 void copy_from(const HashMap &p_t) { 241 242 if (&p_t == this) 243 return; /* much less bother with that */ 244 245 clear(); 246 247 if (!p_t.hash_table || p_t.hash_table_power == 0) 248 return; /* not copying from empty table */ 249 250 hash_table = memnew_arr(Entry *, 1 << p_t.hash_table_power); 251 hash_table_power = p_t.hash_table_power; 252 elements = p_t.elements; 253 254 for (int i = 0; i < (1 << p_t.hash_table_power); i++) { 255 256 hash_table[i] = NULL; 257 /* elements will be in the reverse order, but it doesn't matter */ 258 259 const Entry *e = p_t.hash_table[i]; 260 261 while (e) { 262 263 Entry *le = memnew(Entry); /* local entry */ 264 265 *le = *e; /* copy data */ 266 267 /* add to list and reassign pointers */ 268 le->next = hash_table[i]; 269 hash_table[i] = le; 270 271 e = e->next; 272 } 273 } 274 } 275 276 public: set(const TKey & p_key,const TData & p_data)277 void set(const TKey &p_key, const TData &p_data) { 278 279 set(Pair(p_key, p_data)); 280 } 281 set(const Pair & p_pair)282 void set(const Pair &p_pair) { 283 284 Entry *e = NULL; 285 if (!hash_table) 286 make_hash_table(); // if no table, make one 287 else 288 e = const_cast<Entry *>(get_entry(p_pair.key)); 289 290 /* if we made it up to here, the pair doesn't exist, create and assign */ 291 292 if (!e) { 293 294 e = create_entry(p_pair.key); 295 if (!e) 296 return; 297 check_hash_table(); // perform mantenience routine 298 } 299 300 e->pair.data = p_pair.data; 301 } 302 has(const TKey & p_key)303 bool has(const TKey &p_key) const { 304 305 return getptr(p_key) != NULL; 306 } 307 308 /** 309 * Get a key from data, return a const reference. 310 * WARNING: this doesn't check errors, use either getptr and check NULL, or check 311 * first with has(key) 312 */ 313 get(const TKey & p_key)314 const TData &get(const TKey &p_key) const { 315 316 const TData *res = getptr(p_key); 317 ERR_FAIL_COND_V(!res, *res); 318 return *res; 319 } 320 get(const TKey & p_key)321 TData &get(const TKey &p_key) { 322 323 TData *res = getptr(p_key); 324 ERR_FAIL_COND_V(!res, *res); 325 return *res; 326 } 327 328 /** 329 * Same as get, except it can return NULL when item was not found. 330 * This is mainly used for speed purposes. 331 */ 332 getptr(const TKey & p_key)333 _FORCE_INLINE_ TData *getptr(const TKey &p_key) { 334 335 if (!hash_table) 336 return NULL; 337 338 Entry *e = const_cast<Entry *>(get_entry(p_key)); 339 340 if (e) 341 return &e->pair.data; 342 343 return NULL; 344 } 345 getptr(const TKey & p_key)346 _FORCE_INLINE_ const TData *getptr(const TKey &p_key) const { 347 348 if (!hash_table) 349 return NULL; 350 351 const Entry *e = const_cast<Entry *>(get_entry(p_key)); 352 353 if (e) 354 return &e->pair.data; 355 356 return NULL; 357 } 358 359 /** 360 * Same as get, except it can return NULL when item was not found. 361 * This version is custom, will take a hash and a custom key (that should support operator==() 362 */ 363 364 template <class C> custom_getptr(C p_custom_key,uint32_t p_custom_hash)365 _FORCE_INLINE_ TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) { 366 367 if (!hash_table) 368 return NULL; 369 370 uint32_t hash = p_custom_hash; 371 uint32_t index = hash & ((1 << hash_table_power) - 1); 372 373 Entry *e = hash_table[index]; 374 375 while (e) { 376 377 /* checking hash first avoids comparing key, which may take longer */ 378 if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) { 379 380 /* the pair exists in this hashtable, so just update data */ 381 return &e->pair.data; 382 } 383 384 e = e->next; 385 } 386 387 return NULL; 388 } 389 390 template <class C> custom_getptr(C p_custom_key,uint32_t p_custom_hash)391 _FORCE_INLINE_ const TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) const { 392 393 if (!hash_table) 394 return NULL; 395 396 uint32_t hash = p_custom_hash; 397 uint32_t index = hash & ((1 << hash_table_power) - 1); 398 399 const Entry *e = hash_table[index]; 400 401 while (e) { 402 403 /* checking hash first avoids comparing key, which may take longer */ 404 if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) { 405 406 /* the pair exists in this hashtable, so just update data */ 407 return &e->pair.data; 408 } 409 410 e = e->next; 411 } 412 413 return NULL; 414 } 415 416 /** 417 * Erase an item, return true if erasing was succesful 418 */ 419 erase(const TKey & p_key)420 bool erase(const TKey &p_key) { 421 422 if (!hash_table) 423 return false; 424 425 uint32_t hash = Hasher::hash(p_key); 426 uint32_t index = hash & ((1 << hash_table_power) - 1); 427 428 Entry *e = hash_table[index]; 429 Entry *p = NULL; 430 while (e) { 431 432 /* checking hash first avoids comparing key, which may take longer */ 433 if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) { 434 435 if (p) { 436 437 p->next = e->next; 438 } else { 439 //begin of list 440 hash_table[index] = e->next; 441 } 442 443 memdelete(e); 444 elements--; 445 446 if (elements == 0) 447 erase_hash_table(); 448 else 449 check_hash_table(); 450 return true; 451 } 452 453 p = e; 454 e = e->next; 455 } 456 457 return false; 458 } 459 460 inline const TData &operator[](const TKey &p_key) const { //constref 461 462 return get(p_key); 463 } 464 inline TData &operator[](const TKey &p_key) { //assignment 465 466 Entry *e = NULL; 467 if (!hash_table) 468 make_hash_table(); // if no table, make one 469 else 470 e = const_cast<Entry *>(get_entry(p_key)); 471 472 /* if we made it up to here, the pair doesn't exist, create */ 473 if (!e) { 474 475 e = create_entry(p_key); 476 PRAY_COND(!e, TData); 477 check_hash_table(); // perform mantenience routine 478 } 479 480 return e->pair.data; 481 } 482 483 /** 484 * Get the next key to p_key, and the first key if p_key is null. 485 * Returns a pointer to the next key if found, NULL otherwise. 486 * Adding/Removing elements while iterating will, of course, have unexpected results, don't do it. 487 * 488 * Example: 489 * 490 * const TKey *k=NULL; 491 * 492 * while( (k=table.next(k)) ) { 493 * 494 * print( *k ); 495 * } 496 * 497 */ next(const TKey * p_key)498 const TKey *next(const TKey *p_key) const { 499 500 if (!hash_table) return NULL; 501 502 if (!p_key) { /* get the first key */ 503 504 for (int i = 0; i < (1 << hash_table_power); i++) { 505 506 if (hash_table[i]) { 507 return &hash_table[i]->pair.key; 508 } 509 } 510 511 } else { /* get the next key */ 512 513 const Entry *e = get_entry(*p_key); 514 ERR_FAIL_COND_V(!e, NULL); /* invalid key supplied */ 515 516 if (e->next) { 517 /* if there is a "next" in the list, return that */ 518 return &e->next->pair.key; 519 } else { 520 /* go to next entries */ 521 uint32_t index = e->hash & ((1 << hash_table_power) - 1); 522 index++; 523 for (int i = index; i < (1 << hash_table_power); i++) { 524 525 if (hash_table[i]) { 526 return &hash_table[i]->pair.key; 527 } 528 } 529 } 530 531 /* nothing found, was at end */ 532 } 533 534 return NULL; /* nothing found */ 535 } 536 size()537 inline unsigned int size() const { 538 539 return elements; 540 } 541 empty()542 inline bool empty() const { 543 544 return elements == 0; 545 } 546 clear()547 void clear() { 548 549 /* clean up */ 550 if (hash_table) { 551 for (int i = 0; i < (1 << hash_table_power); i++) { 552 553 while (hash_table[i]) { 554 555 Entry *e = hash_table[i]; 556 hash_table[i] = e->next; 557 memdelete(e); 558 } 559 } 560 561 memdelete_arr(hash_table); 562 } 563 564 hash_table = 0; 565 hash_table_power = 0; 566 elements = 0; 567 } 568 569 void operator=(const HashMap &p_table) { 570 571 copy_from(p_table); 572 } 573 HashMap()574 HashMap() { 575 hash_table = NULL; 576 elements = 0; 577 hash_table_power = 0; 578 } 579 get_key_list(List<TKey> * p_keys)580 void get_key_list(List<TKey> *p_keys) const { 581 if (!hash_table) 582 return; 583 for (int i = 0; i < (1 << hash_table_power); i++) { 584 585 Entry *e = hash_table[i]; 586 while (e) { 587 p_keys->push_back(e->pair.key); 588 e = e->next; 589 } 590 } 591 } 592 HashMap(const HashMap & p_table)593 HashMap(const HashMap &p_table) { 594 595 hash_table = NULL; 596 elements = 0; 597 hash_table_power = 0; 598 599 copy_from(p_table); 600 } 601 ~HashMap()602 ~HashMap() { 603 604 clear(); 605 } 606 }; 607 608 #endif 609