123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595 |
- #ifndef OA_HASH_MAP_H
- #define OA_HASH_MAP_H
- #include "hashfuncs.h"
- #include "math_funcs.h"
- #include "os/copymem.h"
- #include "os/memory.h"
- #define OA_HASH_MAP_INITIAL_LOCAL_STORAGE
- template <class TKey, class TData,
- uint16_t INITIAL_NUM_ELEMENTS = 64,
- class Hasher = HashMapHasherDefault,
- class Comparator = HashMapComparatorDefault<TKey> >
- class OAHashMap {
- private:
- #ifdef OA_HASH_MAP_INITIAL_LOCAL_STORAGE
- TData local_data[INITIAL_NUM_ELEMENTS];
- TKey local_keys[INITIAL_NUM_ELEMENTS];
- uint32_t local_hashes[INITIAL_NUM_ELEMENTS];
- uint8_t local_flags[INITIAL_NUM_ELEMENTS / 4 + (INITIAL_NUM_ELEMENTS % 4 != 0 ? 1 : 0)];
- #endif
- struct {
- TData *data;
- TKey *keys;
- uint32_t *hashes;
-
-
-
-
-
-
-
- uint8_t *flags;
- uint32_t capacity;
- } table, old_table;
- bool is_rehashing;
- uint32_t rehash_position;
- uint32_t rehash_amount;
- uint32_t elements;
-
-
- bool _raw_set_with_hash(uint32_t p_hash, const TKey &p_key, const TData &p_data) {
- for (int i = 0; i < table.capacity; i++) {
- int pos = (p_hash + i) % table.capacity;
- int flags_pos = pos / 4;
- int flags_pos_offset = pos % 4;
- bool is_filled_flag = table.flags[flags_pos] & (1 << (2 * flags_pos_offset));
- bool is_deleted_flag = table.flags[flags_pos] & (1 << (2 * flags_pos_offset + 1));
- if (is_filled_flag) {
- if (table.hashes[pos] == p_hash && Comparator::compare(table.keys[pos], p_key)) {
- table.data[pos] = p_data;
- return true;
- }
- continue;
- }
- table.keys[pos] = p_key;
- table.data[pos] = p_data;
- table.hashes[pos] = p_hash;
- table.flags[flags_pos] |= (1 << (2 * flags_pos_offset));
- table.flags[flags_pos] &= ~(1 << (2 * flags_pos_offset + 1));
- return false;
- }
- return false;
- }
- public:
- _FORCE_INLINE_ uint32_t get_capacity() const { return table.capacity; }
- _FORCE_INLINE_ uint32_t get_num_elements() const { return elements; }
- void set(const TKey &p_key, const TData &p_data) {
- uint32_t hash = Hasher::hash(p_key);
-
-
- if (is_rehashing) {
-
- for (int i = 0; i <= rehash_amount && rehash_position < old_table.capacity; rehash_position++) {
- int flags_pos = rehash_position / 4;
- int flags_pos_offset = rehash_position % 4;
- bool is_filled_flag = (old_table.flags[flags_pos] & (1 << (2 * flags_pos_offset))) > 0;
- bool is_deleted_flag = (old_table.flags[flags_pos] & (1 << (2 * flags_pos_offset + 1))) > 0;
- if (is_filled_flag) {
- _raw_set_with_hash(old_table.hashes[rehash_position], old_table.keys[rehash_position], old_table.data[rehash_position]);
- old_table.keys[rehash_position].~TKey();
- old_table.data[rehash_position].~TData();
- memnew_placement(&old_table.keys[rehash_position], TKey);
- memnew_placement(&old_table.data[rehash_position], TData);
- old_table.flags[flags_pos] &= ~(1 << (2 * flags_pos_offset));
- old_table.flags[flags_pos] |= (1 << (2 * flags_pos_offset + 1));
- }
- }
- if (rehash_position >= old_table.capacity) {
-
- is_rehashing = false;
- #ifdef OA_HASH_MAP_INITIAL_LOCAL_STORAGE
- if (old_table.data == local_data) {
-
- } else
- #endif
- {
- memdelete_arr(old_table.data);
- memdelete_arr(old_table.keys);
- memdelete_arr(old_table.hashes);
- memdelete_arr(old_table.flags);
- }
- }
- }
-
- if (elements >= table.capacity * 0.7) {
- old_table.capacity = table.capacity;
- old_table.data = table.data;
- old_table.flags = table.flags;
- old_table.hashes = table.hashes;
- old_table.keys = table.keys;
- table.capacity = old_table.capacity * 2;
- table.data = memnew_arr(TData, table.capacity);
- table.flags = memnew_arr(uint8_t, table.capacity / 4 + (table.capacity % 4 != 0 ? 1 : 0));
- table.hashes = memnew_arr(uint32_t, table.capacity);
- table.keys = memnew_arr(TKey, table.capacity);
- zeromem(table.flags, table.capacity / 4 + (table.capacity % 4 != 0 ? 1 : 0));
- is_rehashing = true;
- rehash_position = 0;
- rehash_amount = (elements * 2) / (table.capacity * 0.7 - old_table.capacity);
- }
- if (!_raw_set_with_hash(hash, p_key, p_data))
- elements++;
- }
-
- bool lookup(const TKey &p_key, TData *r_data) {
- uint32_t hash = Hasher::hash(p_key);
- bool check_old_table = is_rehashing;
- bool check_new_table = true;
-
-
-
-
-
-
- TData *value = NULL;
- for (int i = 0; i < table.capacity; i++) {
- if (!check_new_table && !check_old_table) {
- break;
- }
-
- if (check_old_table && i < old_table.capacity) {
- int pos = (hash + i) % old_table.capacity;
- int flags_pos = pos / 4;
- int flags_pos_offset = pos % 4;
- bool is_filled_flag = (old_table.flags[flags_pos] & (1 << (2 * flags_pos_offset))) > 0;
- bool is_deleted_flag = (old_table.flags[flags_pos] & (1 << (2 * flags_pos_offset + 1))) > 0;
- if (is_filled_flag) {
-
- if (old_table.hashes[pos] == hash && Comparator::compare(old_table.keys[pos], p_key)) {
- value = &old_table.data[pos];
- check_old_table = false;
- }
- } else if (!is_deleted_flag) {
-
-
-
- check_old_table = false;
- }
- }
- if (check_new_table) {
- int pos = (hash + i) % table.capacity;
- int flags_pos = pos / 4;
- int flags_pos_offset = pos % 4;
- bool is_filled_flag = (table.flags[flags_pos] & (1 << (2 * flags_pos_offset))) > 0;
- bool is_deleted_flag = (table.flags[flags_pos] & (1 << (2 * flags_pos_offset + 1))) > 0;
- if (is_filled_flag) {
-
- if (table.hashes[pos] == hash && Comparator::compare(table.keys[pos], p_key)) {
- if (r_data != NULL)
- *r_data = table.data[pos];
- return true;
- }
- continue;
- } else if (is_deleted_flag) {
- continue;
- } else if (value != NULL) {
-
- if (r_data != NULL)
- *r_data = *value;
- return true;
- } else {
- check_new_table = false;
- }
- }
- }
- if (value != NULL) {
- if (r_data != NULL)
- *r_data = *value;
- return true;
- }
- return false;
- }
- _FORCE_INLINE_ bool has(const TKey &p_key) {
- return lookup(p_key, NULL);
- }
- void remove(const TKey &p_key) {
- uint32_t hash = Hasher::hash(p_key);
- bool check_old_table = is_rehashing;
- bool check_new_table = true;
- for (int i = 0; i < table.capacity; i++) {
- if (!check_new_table && !check_old_table) {
- return;
- }
-
- if (check_old_table && i < old_table.capacity) {
- int pos = (hash + i) % old_table.capacity;
- int flags_pos = pos / 4;
- int flags_pos_offset = pos % 4;
- bool is_filled_flag = (old_table.flags[flags_pos] & (1 << (2 * flags_pos_offset))) > 0;
- bool is_deleted_flag = (old_table.flags[flags_pos] & (1 << (2 * flags_pos_offset + 1))) > 0;
- if (is_filled_flag) {
-
- if (old_table.hashes[pos] == hash && Comparator::compare(old_table.keys[pos], p_key)) {
- old_table.keys[pos].~TKey();
- old_table.data[pos].~TData();
- memnew_placement(&old_table.keys[pos], TKey);
- memnew_placement(&old_table.data[pos], TData);
- old_table.flags[flags_pos] &= ~(1 << (2 * flags_pos_offset));
- old_table.flags[flags_pos] |= (1 << (2 * flags_pos_offset + 1));
- elements--;
- return;
- }
- } else if (!is_deleted_flag) {
-
-
-
- check_old_table = false;
- }
- }
- if (check_new_table) {
- int pos = (hash + i) % table.capacity;
- int flags_pos = pos / 4;
- int flags_pos_offset = pos % 4;
- bool is_filled_flag = (table.flags[flags_pos] & (1 << (2 * flags_pos_offset))) > 0;
- bool is_deleted_flag = (table.flags[flags_pos] & (1 << (2 * flags_pos_offset + 1))) > 0;
- if (is_filled_flag) {
-
- if (table.hashes[pos] == hash && Comparator::compare(table.keys[pos], p_key)) {
- table.keys[pos].~TKey();
- table.data[pos].~TData();
- memnew_placement(&table.keys[pos], TKey);
- memnew_placement(&table.data[pos], TData);
- table.flags[flags_pos] &= ~(1 << (2 * flags_pos_offset));
- table.flags[flags_pos] |= (1 << (2 * flags_pos_offset + 1));
-
-
- elements--;
- return;
- }
- continue;
- } else if (is_deleted_flag) {
- continue;
- } else {
- check_new_table = false;
- }
- }
- }
- }
- struct Iterator {
- bool valid;
- uint32_t hash;
- const TKey *key;
- const TData *data;
- private:
- friend class OAHashMap;
- bool was_from_old_table;
- };
- Iterator iter() const {
- Iterator it;
- it.valid = false;
- it.was_from_old_table = false;
- bool check_old_table = is_rehashing;
- for (int i = 0; i < table.capacity; i++) {
-
- if (check_old_table && i < old_table.capacity) {
- int pos = i;
- int flags_pos = pos / 4;
- int flags_pos_offset = pos % 4;
- bool is_filled_flag = (old_table.flags[flags_pos] & (1 << (2 * flags_pos_offset))) > 0;
- if (is_filled_flag) {
- it.valid = true;
- it.hash = old_table.hashes[pos];
- it.data = &old_table.data[pos];
- it.key = &old_table.keys[pos];
- it.was_from_old_table = true;
- return it;
- }
- }
- {
- int pos = i;
- int flags_pos = pos / 4;
- int flags_pos_offset = pos % 4;
- bool is_filled_flag = (table.flags[flags_pos] & (1 << (2 * flags_pos_offset))) > 0;
- if (is_filled_flag) {
- it.valid = true;
- it.hash = table.hashes[pos];
- it.data = &table.data[pos];
- it.key = &table.keys[pos];
- return it;
- }
- }
- }
- return it;
- }
- Iterator next_iter(const Iterator &p_iter) const {
- if (!p_iter.valid) {
- return p_iter;
- }
- Iterator it;
- it.valid = false;
- it.was_from_old_table = false;
- bool check_old_table = is_rehashing;
-
- bool was_from_old_table = p_iter.was_from_old_table;
- int prev_index = (p_iter.data - (p_iter.was_from_old_table ? old_table.data : table.data));
- if (!was_from_old_table) {
- prev_index++;
- }
- for (int i = prev_index; i < table.capacity; i++) {
-
- if (check_old_table && i < old_table.capacity && !was_from_old_table) {
- int pos = i;
- int flags_pos = pos / 4;
- int flags_pos_offset = pos % 4;
- bool is_filled_flag = (old_table.flags[flags_pos] & (1 << (2 * flags_pos_offset))) > 0;
- if (is_filled_flag) {
- it.valid = true;
- it.hash = old_table.hashes[pos];
- it.data = &old_table.data[pos];
- it.key = &old_table.keys[pos];
- it.was_from_old_table = true;
- return it;
- }
- }
- was_from_old_table = false;
- {
- int pos = i;
- int flags_pos = pos / 4;
- int flags_pos_offset = pos % 4;
- bool is_filled_flag = (table.flags[flags_pos] & (1 << (2 * flags_pos_offset))) > 0;
- if (is_filled_flag) {
- it.valid = true;
- it.hash = table.hashes[pos];
- it.data = &table.data[pos];
- it.key = &table.keys[pos];
- return it;
- }
- }
- }
- return it;
- }
- OAHashMap(uint32_t p_initial_capacity = INITIAL_NUM_ELEMENTS) {
- #ifdef OA_HASH_MAP_INITIAL_LOCAL_STORAGE
- if (p_initial_capacity <= INITIAL_NUM_ELEMENTS) {
- table.data = local_data;
- table.keys = local_keys;
- table.hashes = local_hashes;
- table.flags = local_flags;
- zeromem(table.flags, INITIAL_NUM_ELEMENTS / 4 + (INITIAL_NUM_ELEMENTS % 4 != 0 ? 1 : 0));
- table.capacity = INITIAL_NUM_ELEMENTS;
- elements = 0;
- } else
- #endif
- {
- table.data = memnew_arr(TData, p_initial_capacity);
- table.keys = memnew_arr(TKey, p_initial_capacity);
- table.hashes = memnew_arr(uint32_t, p_initial_capacity);
- table.flags = memnew_arr(uint8_t, p_initial_capacity / 4 + (p_initial_capacity % 4 != 0 ? 1 : 0));
- zeromem(table.flags, p_initial_capacity / 4 + (p_initial_capacity % 4 != 0 ? 1 : 0));
- table.capacity = p_initial_capacity;
- elements = 0;
- }
- is_rehashing = false;
- rehash_position = 0;
- }
- ~OAHashMap() {
- #ifdef OA_HASH_MAP_INITIAL_LOCAL_STORAGE
- if (table.capacity <= INITIAL_NUM_ELEMENTS) {
- return;
- }
- #endif
- if (is_rehashing) {
- #ifdef OA_HASH_MAP_INITIAL_LOCAL_STORAGE
- if (old_table.data == local_data) {
-
- } else
- #endif
- {
- memdelete_arr(old_table.data);
- memdelete_arr(old_table.keys);
- memdelete_arr(old_table.hashes);
- memdelete_arr(old_table.flags);
- }
- }
- memdelete_arr(table.data);
- memdelete_arr(table.keys);
- memdelete_arr(table.hashes);
- memdelete_arr(table.flags);
- }
- };
- #endif
|