1/**************************************************************************/
2/* oa_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 OA_HASH_MAP_H
32#define OA_HASH_MAP_H
33
34#include "core/math/math_funcs.h"
35#include "core/os/memory.h"
36#include "core/templates/hashfuncs.h"
37
38/**
39 * A HashMap implementation that uses open addressing with Robin Hood hashing.
40 * Robin Hood hashing swaps out entries that have a smaller probing distance
41 * than the to-be-inserted entry, that evens out the average probing distance
42 * and enables faster lookups. Backward shift deletion is employed to further
43 * improve the performance and to avoid infinite loops in rare cases.
44 *
45 * The entries are stored inplace, so huge keys or values might fill cache lines
46 * a lot faster.
47 *
48 * Only used keys and values are constructed. For free positions there's space
49 * in the arrays for each, but that memory is kept uninitialized.
50 *
51 * The assignment operator copy the pairs from one map to the other.
52 */
53template <class TKey, class TValue,
54 class Hasher = HashMapHasherDefault,
55 class Comparator = HashMapComparatorDefault<TKey>>
56class OAHashMap {
57private:
58 TValue *values = nullptr;
59 TKey *keys = nullptr;
60 uint32_t *hashes = nullptr;
61
62 uint32_t capacity = 0;
63
64 uint32_t num_elements = 0;
65
66 static const uint32_t EMPTY_HASH = 0;
67
68 _FORCE_INLINE_ uint32_t _hash(const TKey &p_key) const {
69 uint32_t hash = Hasher::hash(p_key);
70
71 if (hash == EMPTY_HASH) {
72 hash = EMPTY_HASH + 1;
73 }
74
75 return hash;
76 }
77
78 _FORCE_INLINE_ uint32_t _get_probe_length(uint32_t p_pos, uint32_t p_hash) const {
79 uint32_t original_pos = p_hash % capacity;
80 return (p_pos - original_pos + capacity) % capacity;
81 }
82
83 _FORCE_INLINE_ void _construct(uint32_t p_pos, uint32_t p_hash, const TKey &p_key, const TValue &p_value) {
84 memnew_placement(&keys[p_pos], TKey(p_key));
85 memnew_placement(&values[p_pos], TValue(p_value));
86 hashes[p_pos] = p_hash;
87
88 num_elements++;
89 }
90
91 bool _lookup_pos(const TKey &p_key, uint32_t &r_pos) const {
92 uint32_t hash = _hash(p_key);
93 uint32_t pos = hash % capacity;
94 uint32_t distance = 0;
95
96 while (true) {
97 if (hashes[pos] == EMPTY_HASH) {
98 return false;
99 }
100
101 if (distance > _get_probe_length(pos, hashes[pos])) {
102 return false;
103 }
104
105 if (hashes[pos] == hash && Comparator::compare(keys[pos], p_key)) {
106 r_pos = pos;
107 return true;
108 }
109
110 pos = (pos + 1) % capacity;
111 distance++;
112 }
113 }
114
115 void _insert_with_hash(uint32_t p_hash, const TKey &p_key, const TValue &p_value) {
116 uint32_t hash = p_hash;
117 uint32_t distance = 0;
118 uint32_t pos = hash % capacity;
119
120 TKey key = p_key;
121 TValue value = p_value;
122
123 while (true) {
124 if (hashes[pos] == EMPTY_HASH) {
125 _construct(pos, hash, key, value);
126
127 return;
128 }
129
130 // not an empty slot, let's check the probing length of the existing one
131 uint32_t existing_probe_len = _get_probe_length(pos, hashes[pos]);
132 if (existing_probe_len < distance) {
133 SWAP(hash, hashes[pos]);
134 SWAP(key, keys[pos]);
135 SWAP(value, values[pos]);
136 distance = existing_probe_len;
137 }
138
139 pos = (pos + 1) % capacity;
140 distance++;
141 }
142 }
143
144 void _resize_and_rehash(uint32_t p_new_capacity) {
145 uint32_t old_capacity = capacity;
146
147 // Capacity can't be 0.
148 capacity = MAX(1u, p_new_capacity);
149
150 TKey *old_keys = keys;
151 TValue *old_values = values;
152 uint32_t *old_hashes = hashes;
153
154 num_elements = 0;
155 keys = static_cast<TKey *>(Memory::alloc_static(sizeof(TKey) * capacity));
156 values = static_cast<TValue *>(Memory::alloc_static(sizeof(TValue) * capacity));
157 hashes = static_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
158
159 for (uint32_t i = 0; i < capacity; i++) {
160 hashes[i] = 0;
161 }
162
163 if (old_capacity == 0) {
164 // Nothing to do.
165 return;
166 }
167
168 for (uint32_t i = 0; i < old_capacity; i++) {
169 if (old_hashes[i] == EMPTY_HASH) {
170 continue;
171 }
172
173 _insert_with_hash(old_hashes[i], old_keys[i], old_values[i]);
174
175 old_keys[i].~TKey();
176 old_values[i].~TValue();
177 }
178
179 Memory::free_static(old_keys);
180 Memory::free_static(old_values);
181 Memory::free_static(old_hashes);
182 }
183
184 void _resize_and_rehash() {
185 _resize_and_rehash(capacity * 2);
186 }
187
188public:
189 _FORCE_INLINE_ uint32_t get_capacity() const { return capacity; }
190 _FORCE_INLINE_ uint32_t get_num_elements() const { return num_elements; }
191
192 bool is_empty() const {
193 return num_elements == 0;
194 }
195
196 void clear() {
197 for (uint32_t i = 0; i < capacity; i++) {
198 if (hashes[i] == EMPTY_HASH) {
199 continue;
200 }
201
202 hashes[i] = EMPTY_HASH;
203 values[i].~TValue();
204 keys[i].~TKey();
205 }
206
207 num_elements = 0;
208 }
209
210 void insert(const TKey &p_key, const TValue &p_value) {
211 if (num_elements + 1 > 0.9 * capacity) {
212 _resize_and_rehash();
213 }
214
215 uint32_t hash = _hash(p_key);
216
217 _insert_with_hash(hash, p_key, p_value);
218 }
219
220 void set(const TKey &p_key, const TValue &p_data) {
221 uint32_t pos = 0;
222 bool exists = _lookup_pos(p_key, pos);
223
224 if (exists) {
225 values[pos] = p_data;
226 } else {
227 insert(p_key, p_data);
228 }
229 }
230
231 /**
232 * returns true if the value was found, false otherwise.
233 *
234 * if r_data is not nullptr then the value will be written to the object
235 * it points to.
236 */
237 bool lookup(const TKey &p_key, TValue &r_data) const {
238 uint32_t pos = 0;
239 bool exists = _lookup_pos(p_key, pos);
240
241 if (exists) {
242 r_data = values[pos];
243 return true;
244 }
245
246 return false;
247 }
248
249 const TValue *lookup_ptr(const TKey &p_key) const {
250 uint32_t pos = 0;
251 bool exists = _lookup_pos(p_key, pos);
252
253 if (exists) {
254 return &values[pos];
255 }
256 return nullptr;
257 }
258
259 TValue *lookup_ptr(const TKey &p_key) {
260 uint32_t pos = 0;
261 bool exists = _lookup_pos(p_key, pos);
262
263 if (exists) {
264 return &values[pos];
265 }
266 return nullptr;
267 }
268
269 _FORCE_INLINE_ bool has(const TKey &p_key) const {
270 uint32_t _pos = 0;
271 return _lookup_pos(p_key, _pos);
272 }
273
274 void remove(const TKey &p_key) {
275 uint32_t pos = 0;
276 bool exists = _lookup_pos(p_key, pos);
277
278 if (!exists) {
279 return;
280 }
281
282 uint32_t next_pos = (pos + 1) % capacity;
283 while (hashes[next_pos] != EMPTY_HASH &&
284 _get_probe_length(next_pos, hashes[next_pos]) != 0) {
285 SWAP(hashes[next_pos], hashes[pos]);
286 SWAP(keys[next_pos], keys[pos]);
287 SWAP(values[next_pos], values[pos]);
288 pos = next_pos;
289 next_pos = (pos + 1) % capacity;
290 }
291
292 hashes[pos] = EMPTY_HASH;
293 values[pos].~TValue();
294 keys[pos].~TKey();
295
296 num_elements--;
297 }
298
299 /**
300 * reserves space for a number of elements, useful to avoid many resizes and rehashes
301 * if adding a known (possibly large) number of elements at once, must be larger than old
302 * capacity.
303 **/
304 void reserve(uint32_t p_new_capacity) {
305 ERR_FAIL_COND(p_new_capacity < capacity);
306 _resize_and_rehash(p_new_capacity);
307 }
308
309 struct Iterator {
310 bool valid;
311
312 const TKey *key;
313 TValue *value = nullptr;
314
315 private:
316 uint32_t pos;
317 friend class OAHashMap;
318 };
319
320 Iterator iter() const {
321 Iterator it;
322
323 it.valid = true;
324 it.pos = 0;
325
326 return next_iter(it);
327 }
328
329 Iterator next_iter(const Iterator &p_iter) const {
330 if (!p_iter.valid) {
331 return p_iter;
332 }
333
334 Iterator it;
335 it.valid = false;
336 it.pos = p_iter.pos;
337 it.key = nullptr;
338 it.value = nullptr;
339
340 for (uint32_t i = it.pos; i < capacity; i++) {
341 it.pos = i + 1;
342
343 if (hashes[i] == EMPTY_HASH) {
344 continue;
345 }
346
347 it.valid = true;
348 it.key = &keys[i];
349 it.value = &values[i];
350 return it;
351 }
352
353 return it;
354 }
355
356 OAHashMap(const OAHashMap &p_other) {
357 (*this) = p_other;
358 }
359
360 void operator=(const OAHashMap &p_other) {
361 if (capacity != 0) {
362 clear();
363 }
364
365 _resize_and_rehash(p_other.capacity);
366
367 for (Iterator it = p_other.iter(); it.valid; it = p_other.next_iter(it)) {
368 set(*it.key, *it.value);
369 }
370 }
371
372 OAHashMap(uint32_t p_initial_capacity = 64) {
373 // Capacity can't be 0.
374 capacity = MAX(1u, p_initial_capacity);
375
376 keys = static_cast<TKey *>(Memory::alloc_static(sizeof(TKey) * capacity));
377 values = static_cast<TValue *>(Memory::alloc_static(sizeof(TValue) * capacity));
378 hashes = static_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
379
380 for (uint32_t i = 0; i < capacity; i++) {
381 hashes[i] = EMPTY_HASH;
382 }
383 }
384
385 ~OAHashMap() {
386 for (uint32_t i = 0; i < capacity; i++) {
387 if (hashes[i] == EMPTY_HASH) {
388 continue;
389 }
390
391 values[i].~TValue();
392 keys[i].~TKey();
393 }
394
395 Memory::free_static(keys);
396 Memory::free_static(values);
397 Memory::free_static(hashes);
398 }
399};
400
401#endif // OA_HASH_MAP_H
402