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