1/**************************************************************************/
2/* hash_set.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_SET_H
32#define HASH_SET_H
33
34#include "core/math/math_funcs.h"
35#include "core/os/memory.h"
36#include "core/templates/hash_map.h"
37#include "core/templates/hashfuncs.h"
38#include "core/templates/paged_allocator.h"
39
40/**
41 * Implementation of Set using a bidi indexed hash map.
42 * Use RBSet instead of this only if the following conditions are met:
43 *
44 * - You need to keep an iterator or const pointer to Key and you intend to add/remove elements in the meantime.
45 * - Iteration order does matter (via operator<)
46 *
47 */
48
49template <class TKey,
50 class Hasher = HashMapHasherDefault,
51 class Comparator = HashMapComparatorDefault<TKey>>
52class HashSet {
53public:
54 static constexpr uint32_t MIN_CAPACITY_INDEX = 2; // Use a prime.
55 static constexpr float MAX_OCCUPANCY = 0.75;
56 static constexpr uint32_t EMPTY_HASH = 0;
57
58private:
59 TKey *keys = nullptr;
60 uint32_t *hash_to_key = nullptr;
61 uint32_t *key_to_hash = nullptr;
62 uint32_t *hashes = nullptr;
63
64 uint32_t capacity_index = 0;
65 uint32_t num_elements = 0;
66
67 _FORCE_INLINE_ uint32_t _hash(const TKey &p_key) const {
68 uint32_t hash = Hasher::hash(p_key);
69
70 if (unlikely(hash == EMPTY_HASH)) {
71 hash = EMPTY_HASH + 1;
72 }
73
74 return hash;
75 }
76
77 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) {
78 const uint32_t original_pos = fastmod(p_hash, p_capacity_inv, p_capacity);
79 return fastmod(p_pos - original_pos + p_capacity, p_capacity_inv, p_capacity);
80 }
81
82 bool _lookup_pos(const TKey &p_key, uint32_t &r_pos) const {
83 if (keys == nullptr || num_elements == 0) {
84 return false; // Failed lookups, no elements
85 }
86
87 const uint32_t capacity = hash_table_size_primes[capacity_index];
88 const uint64_t capacity_inv = hash_table_size_primes_inv[capacity_index];
89 uint32_t hash = _hash(p_key);
90 uint32_t pos = fastmod(hash, capacity_inv, capacity);
91 uint32_t distance = 0;
92
93 while (true) {
94 if (hashes[pos] == EMPTY_HASH) {
95 return false;
96 }
97
98 if (distance > _get_probe_length(pos, hashes[pos], capacity, capacity_inv)) {
99 return false;
100 }
101
102 if (hashes[pos] == hash && Comparator::compare(keys[hash_to_key[pos]], p_key)) {
103 r_pos = hash_to_key[pos];
104 return true;
105 }
106
107 pos = fastmod(pos + 1, capacity_inv, capacity);
108 distance++;
109 }
110 }
111
112 uint32_t _insert_with_hash(uint32_t p_hash, uint32_t p_index) {
113 const uint32_t capacity = hash_table_size_primes[capacity_index];
114 const uint64_t capacity_inv = hash_table_size_primes_inv[capacity_index];
115 uint32_t hash = p_hash;
116 uint32_t index = p_index;
117 uint32_t distance = 0;
118 uint32_t pos = fastmod(hash, capacity_inv, capacity);
119
120 while (true) {
121 if (hashes[pos] == EMPTY_HASH) {
122 hashes[pos] = hash;
123 key_to_hash[index] = pos;
124 hash_to_key[pos] = index;
125 return pos;
126 }
127
128 // Not an empty slot, let's check the probing length of the existing one.
129 uint32_t existing_probe_len = _get_probe_length(pos, hashes[pos], capacity, capacity_inv);
130 if (existing_probe_len < distance) {
131 key_to_hash[index] = pos;
132 SWAP(hash, hashes[pos]);
133 SWAP(index, hash_to_key[pos]);
134 distance = existing_probe_len;
135 }
136
137 pos = fastmod(pos + 1, capacity_inv, capacity);
138 distance++;
139 }
140 }
141
142 void _resize_and_rehash(uint32_t p_new_capacity_index) {
143 // Capacity can't be 0.
144 capacity_index = MAX((uint32_t)MIN_CAPACITY_INDEX, p_new_capacity_index);
145
146 uint32_t capacity = hash_table_size_primes[capacity_index];
147
148 uint32_t *old_hashes = hashes;
149 uint32_t *old_key_to_hash = key_to_hash;
150
151 hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
152 keys = reinterpret_cast<TKey *>(Memory::realloc_static(keys, sizeof(TKey) * capacity));
153 key_to_hash = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
154 hash_to_key = reinterpret_cast<uint32_t *>(Memory::realloc_static(hash_to_key, sizeof(uint32_t) * capacity));
155
156 for (uint32_t i = 0; i < capacity; i++) {
157 hashes[i] = EMPTY_HASH;
158 }
159
160 for (uint32_t i = 0; i < num_elements; i++) {
161 uint32_t h = old_hashes[old_key_to_hash[i]];
162 _insert_with_hash(h, i);
163 }
164
165 Memory::free_static(old_hashes);
166 Memory::free_static(old_key_to_hash);
167 }
168
169 _FORCE_INLINE_ int32_t _insert(const TKey &p_key) {
170 uint32_t capacity = hash_table_size_primes[capacity_index];
171 if (unlikely(keys == nullptr)) {
172 // Allocate on demand to save memory.
173
174 hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
175 keys = reinterpret_cast<TKey *>(Memory::alloc_static(sizeof(TKey) * capacity));
176 key_to_hash = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
177 hash_to_key = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
178
179 for (uint32_t i = 0; i < capacity; i++) {
180 hashes[i] = EMPTY_HASH;
181 }
182 }
183
184 uint32_t pos = 0;
185 bool exists = _lookup_pos(p_key, pos);
186
187 if (exists) {
188 return pos;
189 } else {
190 if (num_elements + 1 > MAX_OCCUPANCY * capacity) {
191 ERR_FAIL_COND_V_MSG(capacity_index + 1 == HASH_TABLE_SIZE_MAX, -1, "Hash table maximum capacity reached, aborting insertion.");
192 _resize_and_rehash(capacity_index + 1);
193 }
194
195 uint32_t hash = _hash(p_key);
196 memnew_placement(&keys[num_elements], TKey(p_key));
197 _insert_with_hash(hash, num_elements);
198 num_elements++;
199 return num_elements - 1;
200 }
201 }
202
203 void _init_from(const HashSet &p_other) {
204 capacity_index = p_other.capacity_index;
205 num_elements = p_other.num_elements;
206
207 if (p_other.num_elements == 0) {
208 return;
209 }
210
211 uint32_t capacity = hash_table_size_primes[capacity_index];
212
213 hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
214 keys = reinterpret_cast<TKey *>(Memory::alloc_static(sizeof(TKey) * capacity));
215 key_to_hash = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
216 hash_to_key = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
217
218 for (uint32_t i = 0; i < num_elements; i++) {
219 memnew_placement(&keys[i], TKey(p_other.keys[i]));
220 key_to_hash[i] = p_other.key_to_hash[i];
221 }
222
223 for (uint32_t i = 0; i < capacity; i++) {
224 hashes[i] = p_other.hashes[i];
225 hash_to_key[i] = p_other.hash_to_key[i];
226 }
227 }
228
229public:
230 _FORCE_INLINE_ uint32_t get_capacity() const { return hash_table_size_primes[capacity_index]; }
231 _FORCE_INLINE_ uint32_t size() const { return num_elements; }
232
233 /* Standard Godot Container API */
234
235 bool is_empty() const {
236 return num_elements == 0;
237 }
238
239 void clear() {
240 if (keys == nullptr || num_elements == 0) {
241 return;
242 }
243 uint32_t capacity = hash_table_size_primes[capacity_index];
244 for (uint32_t i = 0; i < capacity; i++) {
245 hashes[i] = EMPTY_HASH;
246 }
247 for (uint32_t i = 0; i < num_elements; i++) {
248 keys[i].~TKey();
249 }
250
251 num_elements = 0;
252 }
253
254 _FORCE_INLINE_ bool has(const TKey &p_key) const {
255 uint32_t _pos = 0;
256 return _lookup_pos(p_key, _pos);
257 }
258
259 bool erase(const TKey &p_key) {
260 uint32_t pos = 0;
261 bool exists = _lookup_pos(p_key, pos);
262
263 if (!exists) {
264 return false;
265 }
266
267 uint32_t key_pos = pos;
268 pos = key_to_hash[pos]; //make hash pos
269
270 const uint32_t capacity = hash_table_size_primes[capacity_index];
271 const uint64_t capacity_inv = hash_table_size_primes_inv[capacity_index];
272 uint32_t next_pos = fastmod(pos + 1, capacity_inv, capacity);
273 while (hashes[next_pos] != EMPTY_HASH && _get_probe_length(next_pos, hashes[next_pos], capacity, capacity_inv) != 0) {
274 uint32_t kpos = hash_to_key[pos];
275 uint32_t kpos_next = hash_to_key[next_pos];
276 SWAP(key_to_hash[kpos], key_to_hash[kpos_next]);
277 SWAP(hashes[next_pos], hashes[pos]);
278 SWAP(hash_to_key[next_pos], hash_to_key[pos]);
279
280 pos = next_pos;
281 next_pos = fastmod(pos + 1, capacity_inv, capacity);
282 }
283
284 hashes[pos] = EMPTY_HASH;
285 keys[key_pos].~TKey();
286 num_elements--;
287 if (key_pos < num_elements) {
288 // Not the last key, move the last one here to keep keys lineal
289 memnew_placement(&keys[key_pos], TKey(keys[num_elements]));
290 keys[num_elements].~TKey();
291 key_to_hash[key_pos] = key_to_hash[num_elements];
292 hash_to_key[key_to_hash[num_elements]] = key_pos;
293 }
294
295 return true;
296 }
297
298 // Reserves space for a number of elements, useful to avoid many resizes and rehashes.
299 // If adding a known (possibly large) number of elements at once, must be larger than old capacity.
300 void reserve(uint32_t p_new_capacity) {
301 uint32_t new_index = capacity_index;
302
303 while (hash_table_size_primes[new_index] < p_new_capacity) {
304 ERR_FAIL_COND_MSG(new_index + 1 == (uint32_t)HASH_TABLE_SIZE_MAX, nullptr);
305 new_index++;
306 }
307
308 if (new_index == capacity_index) {
309 return;
310 }
311
312 if (keys == nullptr) {
313 capacity_index = new_index;
314 return; // Unallocated yet.
315 }
316 _resize_and_rehash(new_index);
317 }
318
319 /** Iterator API **/
320
321 struct Iterator {
322 _FORCE_INLINE_ const TKey &operator*() const {
323 return keys[index];
324 }
325 _FORCE_INLINE_ const TKey *operator->() const {
326 return &keys[index];
327 }
328 _FORCE_INLINE_ Iterator &operator++() {
329 index++;
330 if (index >= (int32_t)num_keys) {
331 index = -1;
332 keys = nullptr;
333 num_keys = 0;
334 }
335 return *this;
336 }
337 _FORCE_INLINE_ Iterator &operator--() {
338 index--;
339 if (index < 0) {
340 index = -1;
341 keys = nullptr;
342 num_keys = 0;
343 }
344 return *this;
345 }
346
347 _FORCE_INLINE_ bool operator==(const Iterator &b) const { return keys == b.keys && index == b.index; }
348 _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return keys != b.keys || index != b.index; }
349
350 _FORCE_INLINE_ explicit operator bool() const {
351 return keys != nullptr;
352 }
353
354 _FORCE_INLINE_ Iterator(const TKey *p_keys, uint32_t p_num_keys, int32_t p_index = -1) {
355 keys = p_keys;
356 num_keys = p_num_keys;
357 index = p_index;
358 }
359 _FORCE_INLINE_ Iterator() {}
360 _FORCE_INLINE_ Iterator(const Iterator &p_it) {
361 keys = p_it.keys;
362 num_keys = p_it.num_keys;
363 index = p_it.index;
364 }
365 _FORCE_INLINE_ void operator=(const Iterator &p_it) {
366 keys = p_it.keys;
367 num_keys = p_it.num_keys;
368 index = p_it.index;
369 }
370
371 private:
372 const TKey *keys = nullptr;
373 uint32_t num_keys = 0;
374 int32_t index = -1;
375 };
376
377 _FORCE_INLINE_ Iterator begin() const {
378 return num_elements ? Iterator(keys, num_elements, 0) : Iterator();
379 }
380 _FORCE_INLINE_ Iterator end() const {
381 return Iterator();
382 }
383 _FORCE_INLINE_ Iterator last() const {
384 if (num_elements == 0) {
385 return Iterator();
386 }
387 return Iterator(keys, num_elements, num_elements - 1);
388 }
389
390 _FORCE_INLINE_ Iterator find(const TKey &p_key) const {
391 uint32_t pos = 0;
392 bool exists = _lookup_pos(p_key, pos);
393 if (!exists) {
394 return end();
395 }
396 return Iterator(keys, num_elements, pos);
397 }
398
399 _FORCE_INLINE_ void remove(const Iterator &p_iter) {
400 if (p_iter) {
401 erase(*p_iter);
402 }
403 }
404
405 /* Insert */
406
407 Iterator insert(const TKey &p_key) {
408 uint32_t pos = _insert(p_key);
409 return Iterator(keys, num_elements, pos);
410 }
411
412 /* Constructors */
413
414 HashSet(const HashSet &p_other) {
415 _init_from(p_other);
416 }
417
418 void operator=(const HashSet &p_other) {
419 if (this == &p_other) {
420 return; // Ignore self assignment.
421 }
422
423 clear();
424
425 if (keys != nullptr) {
426 Memory::free_static(keys);
427 Memory::free_static(key_to_hash);
428 Memory::free_static(hash_to_key);
429 Memory::free_static(hashes);
430 keys = nullptr;
431 hashes = nullptr;
432 hash_to_key = nullptr;
433 key_to_hash = nullptr;
434 }
435
436 _init_from(p_other);
437 }
438
439 HashSet(uint32_t p_initial_capacity) {
440 // Capacity can't be 0.
441 capacity_index = 0;
442 reserve(p_initial_capacity);
443 }
444 HashSet() {
445 capacity_index = MIN_CAPACITY_INDEX;
446 }
447
448 void reset() {
449 clear();
450
451 if (keys != nullptr) {
452 Memory::free_static(keys);
453 Memory::free_static(key_to_hash);
454 Memory::free_static(hash_to_key);
455 Memory::free_static(hashes);
456 keys = nullptr;
457 hashes = nullptr;
458 hash_to_key = nullptr;
459 key_to_hash = nullptr;
460 }
461 capacity_index = MIN_CAPACITY_INDEX;
462 }
463
464 ~HashSet() {
465 clear();
466
467 if (keys != nullptr) {
468 Memory::free_static(keys);
469 Memory::free_static(key_to_hash);
470 Memory::free_static(hash_to_key);
471 Memory::free_static(hashes);
472 }
473 }
474};
475
476#endif // HASH_SET_H
477