1/**************************************************************************/
2/* hash_map.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
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/math/math_funcs.h"
35#include "core/os/memory.h"
36#include "core/templates/hashfuncs.h"
37#include "core/templates/paged_allocator.h"
38#include "core/templates/pair.h"
39
40/**
41 * A HashMap implementation that uses open addressing with Robin Hood hashing.
42 * Robin Hood hashing swaps out entries that have a smaller probing distance
43 * than the to-be-inserted entry, that evens out the average probing distance
44 * and enables faster lookups. Backward shift deletion is employed to further
45 * improve the performance and to avoid infinite loops in rare cases.
46 *
47 * Keys and values are stored in a double linked list by insertion order. This
48 * has a slight performance overhead on lookup, which can be mostly compensated
49 * using a paged allocator if required.
50 *
51 * The assignment operator copy the pairs from one map to the other.
52 */
53
54template <class TKey, class TValue>
55struct HashMapElement {
56 HashMapElement *next = nullptr;
57 HashMapElement *prev = nullptr;
58 KeyValue<TKey, TValue> data;
59 HashMapElement() {}
60 HashMapElement(const TKey &p_key, const TValue &p_value) :
61 data(p_key, p_value) {}
62};
63
64template <class TKey, class TValue,
65 class Hasher = HashMapHasherDefault,
66 class Comparator = HashMapComparatorDefault<TKey>,
67 class Allocator = DefaultTypedAllocator<HashMapElement<TKey, TValue>>>
68class HashMap {
69public:
70 static constexpr uint32_t MIN_CAPACITY_INDEX = 2; // Use a prime.
71 static constexpr float MAX_OCCUPANCY = 0.75;
72 static constexpr uint32_t EMPTY_HASH = 0;
73
74private:
75 Allocator element_alloc;
76 HashMapElement<TKey, TValue> **elements = nullptr;
77 uint32_t *hashes = nullptr;
78 HashMapElement<TKey, TValue> *head_element = nullptr;
79 HashMapElement<TKey, TValue> *tail_element = nullptr;
80
81 uint32_t capacity_index = 0;
82 uint32_t num_elements = 0;
83
84 _FORCE_INLINE_ uint32_t _hash(const TKey &p_key) const {
85 uint32_t hash = Hasher::hash(p_key);
86
87 if (unlikely(hash == EMPTY_HASH)) {
88 hash = EMPTY_HASH + 1;
89 }
90
91 return hash;
92 }
93
94 static _FORCE_INLINE_ uint32_t _get_probe_length(const uint32_t p_pos, const uint32_t p_hash, const uint32_t p_capacity, const uint64_t p_capacity_inv) {
95 const uint32_t original_pos = fastmod(p_hash, p_capacity_inv, p_capacity);
96 return fastmod(p_pos - original_pos + p_capacity, p_capacity_inv, p_capacity);
97 }
98
99 bool _lookup_pos(const TKey &p_key, uint32_t &r_pos) const {
100 if (elements == nullptr || num_elements == 0) {
101 return false; // Failed lookups, no elements
102 }
103
104 const uint32_t capacity = hash_table_size_primes[capacity_index];
105 const uint64_t capacity_inv = hash_table_size_primes_inv[capacity_index];
106 uint32_t hash = _hash(p_key);
107 uint32_t pos = fastmod(hash, capacity_inv, capacity);
108 uint32_t distance = 0;
109
110 while (true) {
111 if (hashes[pos] == EMPTY_HASH) {
112 return false;
113 }
114
115 if (distance > _get_probe_length(pos, hashes[pos], capacity, capacity_inv)) {
116 return false;
117 }
118
119 if (hashes[pos] == hash && Comparator::compare(elements[pos]->data.key, p_key)) {
120 r_pos = pos;
121 return true;
122 }
123
124 pos = fastmod((pos + 1), capacity_inv, capacity);
125 distance++;
126 }
127 }
128
129 void _insert_with_hash(uint32_t p_hash, HashMapElement<TKey, TValue> *p_value) {
130 const uint32_t capacity = hash_table_size_primes[capacity_index];
131 const uint64_t capacity_inv = hash_table_size_primes_inv[capacity_index];
132 uint32_t hash = p_hash;
133 HashMapElement<TKey, TValue> *value = p_value;
134 uint32_t distance = 0;
135 uint32_t pos = fastmod(hash, capacity_inv, capacity);
136
137 while (true) {
138 if (hashes[pos] == EMPTY_HASH) {
139 elements[pos] = value;
140 hashes[pos] = hash;
141
142 num_elements++;
143
144 return;
145 }
146
147 // Not an empty slot, let's check the probing length of the existing one.
148 uint32_t existing_probe_len = _get_probe_length(pos, hashes[pos], capacity, capacity_inv);
149 if (existing_probe_len < distance) {
150 SWAP(hash, hashes[pos]);
151 SWAP(value, elements[pos]);
152 distance = existing_probe_len;
153 }
154
155 pos = fastmod((pos + 1), capacity_inv, capacity);
156 distance++;
157 }
158 }
159
160 void _resize_and_rehash(uint32_t p_new_capacity_index) {
161 uint32_t old_capacity = hash_table_size_primes[capacity_index];
162
163 // Capacity can't be 0.
164 capacity_index = MAX((uint32_t)MIN_CAPACITY_INDEX, p_new_capacity_index);
165
166 uint32_t capacity = hash_table_size_primes[capacity_index];
167
168 HashMapElement<TKey, TValue> **old_elements = elements;
169 uint32_t *old_hashes = hashes;
170
171 num_elements = 0;
172 hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
173 elements = reinterpret_cast<HashMapElement<TKey, TValue> **>(Memory::alloc_static(sizeof(HashMapElement<TKey, TValue> *) * capacity));
174
175 for (uint32_t i = 0; i < capacity; i++) {
176 hashes[i] = 0;
177 elements[i] = nullptr;
178 }
179
180 if (old_capacity == 0) {
181 // Nothing to do.
182 return;
183 }
184
185 for (uint32_t i = 0; i < old_capacity; i++) {
186 if (old_hashes[i] == EMPTY_HASH) {
187 continue;
188 }
189
190 _insert_with_hash(old_hashes[i], old_elements[i]);
191 }
192
193 Memory::free_static(old_elements);
194 Memory::free_static(old_hashes);
195 }
196
197 _FORCE_INLINE_ HashMapElement<TKey, TValue> *_insert(const TKey &p_key, const TValue &p_value, bool p_front_insert = false) {
198 uint32_t capacity = hash_table_size_primes[capacity_index];
199 if (unlikely(elements == nullptr)) {
200 // Allocate on demand to save memory.
201
202 hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
203 elements = reinterpret_cast<HashMapElement<TKey, TValue> **>(Memory::alloc_static(sizeof(HashMapElement<TKey, TValue> *) * capacity));
204
205 for (uint32_t i = 0; i < capacity; i++) {
206 hashes[i] = EMPTY_HASH;
207 elements[i] = nullptr;
208 }
209 }
210
211 uint32_t pos = 0;
212 bool exists = _lookup_pos(p_key, pos);
213
214 if (exists) {
215 elements[pos]->data.value = p_value;
216 return elements[pos];
217 } else {
218 if (num_elements + 1 > MAX_OCCUPANCY * capacity) {
219 ERR_FAIL_COND_V_MSG(capacity_index + 1 == HASH_TABLE_SIZE_MAX, nullptr, "Hash table maximum capacity reached, aborting insertion.");
220 _resize_and_rehash(capacity_index + 1);
221 }
222
223 HashMapElement<TKey, TValue> *elem = element_alloc.new_allocation(HashMapElement<TKey, TValue>(p_key, p_value));
224
225 if (tail_element == nullptr) {
226 head_element = elem;
227 tail_element = elem;
228 } else if (p_front_insert) {
229 head_element->prev = elem;
230 elem->next = head_element;
231 head_element = elem;
232 } else {
233 tail_element->next = elem;
234 elem->prev = tail_element;
235 tail_element = elem;
236 }
237
238 uint32_t hash = _hash(p_key);
239 _insert_with_hash(hash, elem);
240 return elem;
241 }
242 }
243
244public:
245 _FORCE_INLINE_ uint32_t get_capacity() const { return hash_table_size_primes[capacity_index]; }
246 _FORCE_INLINE_ uint32_t size() const { return num_elements; }
247
248 /* Standard Godot Container API */
249
250 bool is_empty() const {
251 return num_elements == 0;
252 }
253
254 void clear() {
255 if (elements == nullptr || num_elements == 0) {
256 return;
257 }
258 uint32_t capacity = hash_table_size_primes[capacity_index];
259 for (uint32_t i = 0; i < capacity; i++) {
260 if (hashes[i] == EMPTY_HASH) {
261 continue;
262 }
263
264 hashes[i] = EMPTY_HASH;
265 element_alloc.delete_allocation(elements[i]);
266 elements[i] = nullptr;
267 }
268
269 tail_element = nullptr;
270 head_element = nullptr;
271 num_elements = 0;
272 }
273
274 TValue &get(const TKey &p_key) {
275 uint32_t pos = 0;
276 bool exists = _lookup_pos(p_key, pos);
277 CRASH_COND_MSG(!exists, "HashMap key not found.");
278 return elements[pos]->data.value;
279 }
280
281 const TValue &get(const TKey &p_key) const {
282 uint32_t pos = 0;
283 bool exists = _lookup_pos(p_key, pos);
284 CRASH_COND_MSG(!exists, "HashMap key not found.");
285 return elements[pos]->data.value;
286 }
287
288 const TValue *getptr(const TKey &p_key) const {
289 uint32_t pos = 0;
290 bool exists = _lookup_pos(p_key, pos);
291
292 if (exists) {
293 return &elements[pos]->data.value;
294 }
295 return nullptr;
296 }
297
298 TValue *getptr(const TKey &p_key) {
299 uint32_t pos = 0;
300 bool exists = _lookup_pos(p_key, pos);
301
302 if (exists) {
303 return &elements[pos]->data.value;
304 }
305 return nullptr;
306 }
307
308 _FORCE_INLINE_ bool has(const TKey &p_key) const {
309 uint32_t _pos = 0;
310 return _lookup_pos(p_key, _pos);
311 }
312
313 bool erase(const TKey &p_key) {
314 uint32_t pos = 0;
315 bool exists = _lookup_pos(p_key, pos);
316
317 if (!exists) {
318 return false;
319 }
320
321 const uint32_t capacity = hash_table_size_primes[capacity_index];
322 const uint64_t capacity_inv = hash_table_size_primes_inv[capacity_index];
323 uint32_t next_pos = fastmod((pos + 1), capacity_inv, capacity);
324 while (hashes[next_pos] != EMPTY_HASH && _get_probe_length(next_pos, hashes[next_pos], capacity, capacity_inv) != 0) {
325 SWAP(hashes[next_pos], hashes[pos]);
326 SWAP(elements[next_pos], elements[pos]);
327 pos = next_pos;
328 next_pos = fastmod((pos + 1), capacity_inv, capacity);
329 }
330
331 hashes[pos] = EMPTY_HASH;
332
333 if (head_element == elements[pos]) {
334 head_element = elements[pos]->next;
335 }
336
337 if (tail_element == elements[pos]) {
338 tail_element = elements[pos]->prev;
339 }
340
341 if (elements[pos]->prev) {
342 elements[pos]->prev->next = elements[pos]->next;
343 }
344
345 if (elements[pos]->next) {
346 elements[pos]->next->prev = elements[pos]->prev;
347 }
348
349 element_alloc.delete_allocation(elements[pos]);
350 elements[pos] = nullptr;
351
352 num_elements--;
353 return true;
354 }
355
356 // Replace the key of an entry in-place, without invalidating iterators or changing the entries position during iteration.
357 // p_old_key must exist in the map and p_new_key must not, unless it is equal to p_old_key.
358 bool replace_key(const TKey &p_old_key, const TKey &p_new_key) {
359 if (p_old_key == p_new_key) {
360 return true;
361 }
362 uint32_t pos = 0;
363 ERR_FAIL_COND_V(_lookup_pos(p_new_key, pos), false);
364 ERR_FAIL_COND_V(!_lookup_pos(p_old_key, pos), false);
365 HashMapElement<TKey, TValue> *element = elements[pos];
366
367 // Delete the old entries in hashes and elements.
368 const uint32_t capacity = hash_table_size_primes[capacity_index];
369 const uint64_t capacity_inv = hash_table_size_primes_inv[capacity_index];
370 uint32_t next_pos = fastmod((pos + 1), capacity_inv, capacity);
371 while (hashes[next_pos] != EMPTY_HASH && _get_probe_length(next_pos, hashes[next_pos], capacity, capacity_inv) != 0) {
372 SWAP(hashes[next_pos], hashes[pos]);
373 SWAP(elements[next_pos], elements[pos]);
374 pos = next_pos;
375 next_pos = fastmod((pos + 1), capacity_inv, capacity);
376 }
377 hashes[pos] = EMPTY_HASH;
378 elements[pos] = nullptr;
379 // _insert_with_hash will increment this again.
380 num_elements--;
381
382 // Update the HashMapElement with the new key and reinsert it.
383 const_cast<TKey &>(element->data.key) = p_new_key;
384 uint32_t hash = _hash(p_new_key);
385 _insert_with_hash(hash, element);
386
387 return true;
388 }
389
390 // Reserves space for a number of elements, useful to avoid many resizes and rehashes.
391 // If adding a known (possibly large) number of elements at once, must be larger than old capacity.
392 void reserve(uint32_t p_new_capacity) {
393 uint32_t new_index = capacity_index;
394
395 while (hash_table_size_primes[new_index] < p_new_capacity) {
396 ERR_FAIL_COND_MSG(new_index + 1 == (uint32_t)HASH_TABLE_SIZE_MAX, nullptr);
397 new_index++;
398 }
399
400 if (new_index == capacity_index) {
401 return;
402 }
403
404 if (elements == nullptr) {
405 capacity_index = new_index;
406 return; // Unallocated yet.
407 }
408 _resize_and_rehash(new_index);
409 }
410
411 /** Iterator API **/
412
413 struct ConstIterator {
414 _FORCE_INLINE_ const KeyValue<TKey, TValue> &operator*() const {
415 return E->data;
416 }
417 _FORCE_INLINE_ const KeyValue<TKey, TValue> *operator->() const { return &E->data; }
418 _FORCE_INLINE_ ConstIterator &operator++() {
419 if (E) {
420 E = E->next;
421 }
422 return *this;
423 }
424 _FORCE_INLINE_ ConstIterator &operator--() {
425 if (E) {
426 E = E->prev;
427 }
428 return *this;
429 }
430
431 _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; }
432 _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; }
433
434 _FORCE_INLINE_ explicit operator bool() const {
435 return E != nullptr;
436 }
437
438 _FORCE_INLINE_ ConstIterator(const HashMapElement<TKey, TValue> *p_E) { E = p_E; }
439 _FORCE_INLINE_ ConstIterator() {}
440 _FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
441 _FORCE_INLINE_ void operator=(const ConstIterator &p_it) {
442 E = p_it.E;
443 }
444
445 private:
446 const HashMapElement<TKey, TValue> *E = nullptr;
447 };
448
449 struct Iterator {
450 _FORCE_INLINE_ KeyValue<TKey, TValue> &operator*() const {
451 return E->data;
452 }
453 _FORCE_INLINE_ KeyValue<TKey, TValue> *operator->() const { return &E->data; }
454 _FORCE_INLINE_ Iterator &operator++() {
455 if (E) {
456 E = E->next;
457 }
458 return *this;
459 }
460 _FORCE_INLINE_ Iterator &operator--() {
461 if (E) {
462 E = E->prev;
463 }
464 return *this;
465 }
466
467 _FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; }
468 _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
469
470 _FORCE_INLINE_ explicit operator bool() const {
471 return E != nullptr;
472 }
473
474 _FORCE_INLINE_ Iterator(HashMapElement<TKey, TValue> *p_E) { E = p_E; }
475 _FORCE_INLINE_ Iterator() {}
476 _FORCE_INLINE_ Iterator(const Iterator &p_it) { E = p_it.E; }
477 _FORCE_INLINE_ void operator=(const Iterator &p_it) {
478 E = p_it.E;
479 }
480
481 operator ConstIterator() const {
482 return ConstIterator(E);
483 }
484
485 private:
486 HashMapElement<TKey, TValue> *E = nullptr;
487 };
488
489 _FORCE_INLINE_ Iterator begin() {
490 return Iterator(head_element);
491 }
492 _FORCE_INLINE_ Iterator end() {
493 return Iterator(nullptr);
494 }
495 _FORCE_INLINE_ Iterator last() {
496 return Iterator(tail_element);
497 }
498
499 _FORCE_INLINE_ Iterator find(const TKey &p_key) {
500 uint32_t pos = 0;
501 bool exists = _lookup_pos(p_key, pos);
502 if (!exists) {
503 return end();
504 }
505 return Iterator(elements[pos]);
506 }
507
508 _FORCE_INLINE_ void remove(const Iterator &p_iter) {
509 if (p_iter) {
510 erase(p_iter->key);
511 }
512 }
513
514 _FORCE_INLINE_ ConstIterator begin() const {
515 return ConstIterator(head_element);
516 }
517 _FORCE_INLINE_ ConstIterator end() const {
518 return ConstIterator(nullptr);
519 }
520 _FORCE_INLINE_ ConstIterator last() const {
521 return ConstIterator(tail_element);
522 }
523
524 _FORCE_INLINE_ ConstIterator find(const TKey &p_key) const {
525 uint32_t pos = 0;
526 bool exists = _lookup_pos(p_key, pos);
527 if (!exists) {
528 return end();
529 }
530 return ConstIterator(elements[pos]);
531 }
532
533 /* Indexing */
534
535 const TValue &operator[](const TKey &p_key) const {
536 uint32_t pos = 0;
537 bool exists = _lookup_pos(p_key, pos);
538 CRASH_COND(!exists);
539 return elements[pos]->data.value;
540 }
541
542 TValue &operator[](const TKey &p_key) {
543 uint32_t pos = 0;
544 bool exists = _lookup_pos(p_key, pos);
545 if (!exists) {
546 return _insert(p_key, TValue())->data.value;
547 } else {
548 return elements[pos]->data.value;
549 }
550 }
551
552 /* Insert */
553
554 Iterator insert(const TKey &p_key, const TValue &p_value, bool p_front_insert = false) {
555 return Iterator(_insert(p_key, p_value, p_front_insert));
556 }
557
558 /* Constructors */
559
560 HashMap(const HashMap &p_other) {
561 reserve(hash_table_size_primes[p_other.capacity_index]);
562
563 if (p_other.num_elements == 0) {
564 return;
565 }
566
567 for (const KeyValue<TKey, TValue> &E : p_other) {
568 insert(E.key, E.value);
569 }
570 }
571
572 void operator=(const HashMap &p_other) {
573 if (this == &p_other) {
574 return; // Ignore self assignment.
575 }
576 if (num_elements != 0) {
577 clear();
578 }
579
580 reserve(hash_table_size_primes[p_other.capacity_index]);
581
582 if (p_other.elements == nullptr) {
583 return; // Nothing to copy.
584 }
585
586 for (const KeyValue<TKey, TValue> &E : p_other) {
587 insert(E.key, E.value);
588 }
589 }
590
591 HashMap(uint32_t p_initial_capacity) {
592 // Capacity can't be 0.
593 capacity_index = 0;
594 reserve(p_initial_capacity);
595 }
596 HashMap() {
597 capacity_index = MIN_CAPACITY_INDEX;
598 }
599
600 uint32_t debug_get_hash(uint32_t p_index) {
601 if (num_elements == 0) {
602 return 0;
603 }
604 ERR_FAIL_INDEX_V(p_index, get_capacity(), 0);
605 return hashes[p_index];
606 }
607 Iterator debug_get_element(uint32_t p_index) {
608 if (num_elements == 0) {
609 return Iterator();
610 }
611 ERR_FAIL_INDEX_V(p_index, get_capacity(), Iterator());
612 return Iterator(elements[p_index]);
613 }
614
615 ~HashMap() {
616 clear();
617
618 if (elements != nullptr) {
619 Memory::free_static(elements);
620 Memory::free_static(hashes);
621 }
622 }
623};
624
625#endif // HASH_MAP_H
626