1 /*************************************************************************/ 2 /* hash_map.h */ 3 /*************************************************************************/ 4 /* This file is part of: */ 5 /* GODOT ENGINE */ 6 /* https://godotengine.org */ 7 /*************************************************************************/ 8 /* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ 9 /* Copyright (c) 2014-2020 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 31 #ifndef HASH_MAP_H 32 #define HASH_MAP_H 33 34 #include "core/error_macros.h" 35 #include "core/hashfuncs.h" 36 #include "core/list.h" 37 #include "core/math/math_funcs.h" 38 #include "core/os/memory.h" 39 #include "core/ustring.h" 40 41 /** 42 * @class HashMap 43 * @author Juan Linietsky <reduzio@gmail.com> 44 * 45 * Implementation of a standard Hashing HashMap, for quick lookups of Data associated with a Key. 46 * The implementation provides hashers for the default types, if you need a special kind of hasher, provide 47 * your own. 48 * @param TKey Key, search is based on it, needs to be hasheable. It is unique in this container. 49 * @param TData Data, data associated with the key 50 * @param Hasher Hasher object, needs to provide a valid static hash function for TKey 51 * @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. 52 * @param MIN_HASH_TABLE_POWER Miminum size of the hash table, as a power of two. You rarely need to change this parameter. 53 * @param RELATIONSHIP Relationship at which the hash table is resized. if amount of elements is RELATIONSHIP 54 * times bigger than the hash table, table is resized to solve this condition. if RELATIONSHIP is zero, table is always MIN_HASH_TABLE_POWER. 55 * 56 */ 57 58 template <class TKey, class TData, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<TKey>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8> 59 class HashMap { 60 public: 61 struct Pair { 62 63 TKey key; 64 TData data; 65 PairPair66 Pair() {} PairPair67 Pair(const TKey &p_key, const TData &p_data) : 68 key(p_key), 69 data(p_data) { 70 } 71 }; 72 73 struct Element { 74 private: 75 friend class HashMap; 76 77 uint32_t hash; 78 Element *next; ElementElement79 Element() { next = 0; } 80 Pair pair; 81 82 public: keyElement83 const TKey &key() const { 84 return pair.key; 85 } 86 valueElement87 TData &value() { 88 return pair.data; 89 } 90 valueElement91 const TData &value() const { 92 return pair.value(); 93 } 94 }; 95 96 private: 97 Element **hash_table; 98 uint8_t hash_table_power; 99 uint32_t elements; 100 make_hash_table()101 void make_hash_table() { 102 103 ERR_FAIL_COND(hash_table); 104 105 hash_table = memnew_arr(Element *, (1 << MIN_HASH_TABLE_POWER)); 106 107 hash_table_power = MIN_HASH_TABLE_POWER; 108 elements = 0; 109 for (int i = 0; i < (1 << MIN_HASH_TABLE_POWER); i++) 110 hash_table[i] = 0; 111 } 112 erase_hash_table()113 void erase_hash_table() { 114 115 ERR_FAIL_COND_MSG(elements, "Cannot erase hash table if there are still elements inside."); 116 117 memdelete_arr(hash_table); 118 hash_table = 0; 119 hash_table_power = 0; 120 elements = 0; 121 } 122 check_hash_table()123 void check_hash_table() { 124 125 int new_hash_table_power = -1; 126 127 if ((int)elements > ((1 << hash_table_power) * RELATIONSHIP)) { 128 /* rehash up */ 129 new_hash_table_power = hash_table_power + 1; 130 131 while ((int)elements > ((1 << new_hash_table_power) * RELATIONSHIP)) { 132 133 new_hash_table_power++; 134 } 135 136 } else if ((hash_table_power > (int)MIN_HASH_TABLE_POWER) && ((int)elements < ((1 << (hash_table_power - 1)) * RELATIONSHIP))) { 137 138 /* rehash down */ 139 new_hash_table_power = hash_table_power - 1; 140 141 while ((int)elements < ((1 << (new_hash_table_power - 1)) * RELATIONSHIP)) { 142 143 new_hash_table_power--; 144 } 145 146 if (new_hash_table_power < (int)MIN_HASH_TABLE_POWER) 147 new_hash_table_power = MIN_HASH_TABLE_POWER; 148 } 149 150 if (new_hash_table_power == -1) 151 return; 152 153 Element **new_hash_table = memnew_arr(Element *, ((uint64_t)1 << new_hash_table_power)); 154 ERR_FAIL_COND_MSG(!new_hash_table, "Out of memory."); 155 156 for (int i = 0; i < (1 << new_hash_table_power); i++) { 157 158 new_hash_table[i] = 0; 159 } 160 161 if (hash_table) { 162 for (int i = 0; i < (1 << hash_table_power); i++) { 163 164 while (hash_table[i]) { 165 166 Element *se = hash_table[i]; 167 hash_table[i] = se->next; 168 int new_pos = se->hash & ((1 << new_hash_table_power) - 1); 169 se->next = new_hash_table[new_pos]; 170 new_hash_table[new_pos] = se; 171 } 172 } 173 174 memdelete_arr(hash_table); 175 } 176 hash_table = new_hash_table; 177 hash_table_power = new_hash_table_power; 178 } 179 180 /* I want to have only one function.. */ get_element(const TKey & p_key)181 _FORCE_INLINE_ const Element *get_element(const TKey &p_key) const { 182 183 uint32_t hash = Hasher::hash(p_key); 184 uint32_t index = hash & ((1 << hash_table_power) - 1); 185 186 Element *e = hash_table[index]; 187 188 while (e) { 189 190 /* checking hash first avoids comparing key, which may take longer */ 191 if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) { 192 193 /* the pair exists in this hashtable, so just update data */ 194 return e; 195 } 196 197 e = e->next; 198 } 199 200 return NULL; 201 } 202 create_element(const TKey & p_key)203 Element *create_element(const TKey &p_key) { 204 205 /* if element doesn't exist, create it */ 206 Element *e = memnew(Element); 207 ERR_FAIL_COND_V_MSG(!e, NULL, "Out of memory."); 208 uint32_t hash = Hasher::hash(p_key); 209 uint32_t index = hash & ((1 << hash_table_power) - 1); 210 e->next = hash_table[index]; 211 e->hash = hash; 212 e->pair.key = p_key; 213 e->pair.data = TData(); 214 215 hash_table[index] = e; 216 elements++; 217 218 return e; 219 } 220 copy_from(const HashMap & p_t)221 void copy_from(const HashMap &p_t) { 222 223 if (&p_t == this) 224 return; /* much less bother with that */ 225 226 clear(); 227 228 if (!p_t.hash_table || p_t.hash_table_power == 0) 229 return; /* not copying from empty table */ 230 231 hash_table = memnew_arr(Element *, (uint64_t)1 << p_t.hash_table_power); 232 hash_table_power = p_t.hash_table_power; 233 elements = p_t.elements; 234 235 for (int i = 0; i < (1 << p_t.hash_table_power); i++) { 236 237 hash_table[i] = NULL; 238 239 const Element *e = p_t.hash_table[i]; 240 241 while (e) { 242 243 Element *le = memnew(Element); /* local element */ 244 245 *le = *e; /* copy data */ 246 247 /* add to list and reassign pointers */ 248 le->next = hash_table[i]; 249 hash_table[i] = le; 250 251 e = e->next; 252 } 253 } 254 } 255 256 public: set(const TKey & p_key,const TData & p_data)257 Element *set(const TKey &p_key, const TData &p_data) { 258 return set(Pair(p_key, p_data)); 259 } 260 set(const Pair & p_pair)261 Element *set(const Pair &p_pair) { 262 263 Element *e = NULL; 264 if (!hash_table) 265 make_hash_table(); // if no table, make one 266 else 267 e = const_cast<Element *>(get_element(p_pair.key)); 268 269 /* if we made it up to here, the pair doesn't exist, create and assign */ 270 271 if (!e) { 272 273 e = create_element(p_pair.key); 274 if (!e) 275 return NULL; 276 check_hash_table(); // perform mantenience routine 277 } 278 279 e->pair.data = p_pair.data; 280 return e; 281 } 282 has(const TKey & p_key)283 bool has(const TKey &p_key) const { 284 285 return getptr(p_key) != NULL; 286 } 287 288 /** 289 * Get a key from data, return a const reference. 290 * WARNING: this doesn't check errors, use either getptr and check NULL, or check 291 * first with has(key) 292 */ 293 get(const TKey & p_key)294 const TData &get(const TKey &p_key) const { 295 296 const TData *res = getptr(p_key); 297 CRASH_COND_MSG(!res, "Map key not found."); 298 return *res; 299 } 300 get(const TKey & p_key)301 TData &get(const TKey &p_key) { 302 303 TData *res = getptr(p_key); 304 CRASH_COND_MSG(!res, "Map key not found."); 305 return *res; 306 } 307 308 /** 309 * Same as get, except it can return NULL when item was not found. 310 * This is mainly used for speed purposes. 311 */ 312 getptr(const TKey & p_key)313 _FORCE_INLINE_ TData *getptr(const TKey &p_key) { 314 315 if (unlikely(!hash_table)) 316 return NULL; 317 318 Element *e = const_cast<Element *>(get_element(p_key)); 319 320 if (e) 321 return &e->pair.data; 322 323 return NULL; 324 } 325 getptr(const TKey & p_key)326 _FORCE_INLINE_ const TData *getptr(const TKey &p_key) const { 327 328 if (unlikely(!hash_table)) 329 return NULL; 330 331 const Element *e = const_cast<Element *>(get_element(p_key)); 332 333 if (e) 334 return &e->pair.data; 335 336 return NULL; 337 } 338 339 /** 340 * Same as get, except it can return NULL when item was not found. 341 * This version is custom, will take a hash and a custom key (that should support operator==() 342 */ 343 344 template <class C> custom_getptr(C p_custom_key,uint32_t p_custom_hash)345 _FORCE_INLINE_ TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) { 346 347 if (unlikely(!hash_table)) 348 return NULL; 349 350 uint32_t hash = p_custom_hash; 351 uint32_t index = hash & ((1 << hash_table_power) - 1); 352 353 Element *e = hash_table[index]; 354 355 while (e) { 356 357 /* checking hash first avoids comparing key, which may take longer */ 358 if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) { 359 360 /* the pair exists in this hashtable, so just update data */ 361 return &e->pair.data; 362 } 363 364 e = e->next; 365 } 366 367 return NULL; 368 } 369 370 template <class C> custom_getptr(C p_custom_key,uint32_t p_custom_hash)371 _FORCE_INLINE_ const TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) const { 372 373 if (unlikely(!hash_table)) 374 return NULL; 375 376 uint32_t hash = p_custom_hash; 377 uint32_t index = hash & ((1 << hash_table_power) - 1); 378 379 const Element *e = hash_table[index]; 380 381 while (e) { 382 383 /* checking hash first avoids comparing key, which may take longer */ 384 if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) { 385 386 /* the pair exists in this hashtable, so just update data */ 387 return &e->pair.data; 388 } 389 390 e = e->next; 391 } 392 393 return NULL; 394 } 395 396 /** 397 * Erase an item, return true if erasing was successful 398 */ 399 erase(const TKey & p_key)400 bool erase(const TKey &p_key) { 401 402 if (unlikely(!hash_table)) 403 return false; 404 405 uint32_t hash = Hasher::hash(p_key); 406 uint32_t index = hash & ((1 << hash_table_power) - 1); 407 408 Element *e = hash_table[index]; 409 Element *p = NULL; 410 while (e) { 411 412 /* checking hash first avoids comparing key, which may take longer */ 413 if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) { 414 415 if (p) { 416 417 p->next = e->next; 418 } else { 419 //begin of list 420 hash_table[index] = e->next; 421 } 422 423 memdelete(e); 424 elements--; 425 426 if (elements == 0) 427 erase_hash_table(); 428 else 429 check_hash_table(); 430 return true; 431 } 432 433 p = e; 434 e = e->next; 435 } 436 437 return false; 438 } 439 440 inline const TData &operator[](const TKey &p_key) const { //constref 441 442 return get(p_key); 443 } 444 inline TData &operator[](const TKey &p_key) { //assignment 445 446 Element *e = NULL; 447 if (!hash_table) 448 make_hash_table(); // if no table, make one 449 else 450 e = const_cast<Element *>(get_element(p_key)); 451 452 /* if we made it up to here, the pair doesn't exist, create */ 453 if (!e) { 454 455 e = create_element(p_key); 456 CRASH_COND(!e); 457 check_hash_table(); // perform mantenience routine 458 } 459 460 return e->pair.data; 461 } 462 463 /** 464 * Get the next key to p_key, and the first key if p_key is null. 465 * Returns a pointer to the next key if found, NULL otherwise. 466 * Adding/Removing elements while iterating will, of course, have unexpected results, don't do it. 467 * 468 * Example: 469 * 470 * const TKey *k=NULL; 471 * 472 * while( (k=table.next(k)) ) { 473 * 474 * print( *k ); 475 * } 476 * 477 */ next(const TKey * p_key)478 const TKey *next(const TKey *p_key) const { 479 480 if (unlikely(!hash_table)) 481 return NULL; 482 483 if (!p_key) { /* get the first key */ 484 485 for (int i = 0; i < (1 << hash_table_power); i++) { 486 487 if (hash_table[i]) { 488 return &hash_table[i]->pair.key; 489 } 490 } 491 492 } else { /* get the next key */ 493 494 const Element *e = get_element(*p_key); 495 ERR_FAIL_COND_V_MSG(!e, NULL, "Invalid key supplied."); 496 if (e->next) { 497 /* if there is a "next" in the list, return that */ 498 return &e->next->pair.key; 499 } else { 500 /* go to next elements */ 501 uint32_t index = e->hash & ((1 << hash_table_power) - 1); 502 index++; 503 for (int i = index; i < (1 << hash_table_power); i++) { 504 505 if (hash_table[i]) { 506 return &hash_table[i]->pair.key; 507 } 508 } 509 } 510 511 /* nothing found, was at end */ 512 } 513 514 return NULL; /* nothing found */ 515 } 516 size()517 inline unsigned int size() const { 518 519 return elements; 520 } 521 empty()522 inline bool empty() const { 523 524 return elements == 0; 525 } 526 clear()527 void clear() { 528 529 /* clean up */ 530 if (hash_table) { 531 for (int i = 0; i < (1 << hash_table_power); i++) { 532 533 while (hash_table[i]) { 534 535 Element *e = hash_table[i]; 536 hash_table[i] = e->next; 537 memdelete(e); 538 } 539 } 540 541 memdelete_arr(hash_table); 542 } 543 544 hash_table = 0; 545 hash_table_power = 0; 546 elements = 0; 547 } 548 549 void operator=(const HashMap &p_table) { 550 551 copy_from(p_table); 552 } 553 HashMap()554 HashMap() { 555 hash_table = NULL; 556 elements = 0; 557 hash_table_power = 0; 558 } 559 get_key_value_ptr_array(const Pair ** p_pairs)560 void get_key_value_ptr_array(const Pair **p_pairs) const { 561 if (unlikely(!hash_table)) 562 return; 563 for (int i = 0; i < (1 << hash_table_power); i++) { 564 565 Element *e = hash_table[i]; 566 while (e) { 567 *p_pairs = &e->pair; 568 p_pairs++; 569 e = e->next; 570 } 571 } 572 } 573 get_key_list(List<TKey> * p_keys)574 void get_key_list(List<TKey> *p_keys) const { 575 if (unlikely(!hash_table)) 576 return; 577 for (int i = 0; i < (1 << hash_table_power); i++) { 578 579 Element *e = hash_table[i]; 580 while (e) { 581 p_keys->push_back(e->pair.key); 582 e = e->next; 583 } 584 } 585 } 586 HashMap(const HashMap & p_table)587 HashMap(const HashMap &p_table) { 588 589 hash_table = NULL; 590 elements = 0; 591 hash_table_power = 0; 592 593 copy_from(p_table); 594 } 595 ~HashMap()596 ~HashMap() { 597 598 clear(); 599 } 600 }; 601 602 #endif 603