summaryrefslogtreecommitdiff
path: root/core/templates
diff options
context:
space:
mode:
Diffstat (limited to 'core/templates')
-rw-r--r--core/templates/bin_sorted_array.h4
-rw-r--r--core/templates/cowdata.h32
-rw-r--r--core/templates/hash_map.h779
-rw-r--r--core/templates/hash_set.h473
-rw-r--r--core/templates/hashfuncs.h197
-rw-r--r--core/templates/ordered_hash_map.h301
-rw-r--r--core/templates/paged_allocator.h8
-rw-r--r--core/templates/pair.h11
-rw-r--r--core/templates/rb_map.h (renamed from core/templates/map.h)36
-rw-r--r--core/templates/rb_set.h (renamed from core/templates/set.h)31
-rw-r--r--core/templates/rid_owner.h2
-rw-r--r--core/templates/vector.h2
12 files changed, 1143 insertions, 733 deletions
diff --git a/core/templates/bin_sorted_array.h b/core/templates/bin_sorted_array.h
index 59ac4cdaa1..d928bd7a82 100644
--- a/core/templates/bin_sorted_array.h
+++ b/core/templates/bin_sorted_array.h
@@ -61,7 +61,7 @@ public:
}
uint64_t move(uint64_t p_idx, uint64_t p_bin) {
- ERR_FAIL_COND_V(p_idx >= array.size(), -1);
+ ERR_FAIL_UNSIGNED_INDEX_V(p_idx, array.size(), -1);
uint64_t current_bin = bin_limits.size() - 1;
while (p_idx > bin_limits[current_bin]) {
@@ -113,7 +113,7 @@ public:
}
void remove_at(uint64_t p_idx) {
- ERR_FAIL_COND(p_idx >= array.size());
+ ERR_FAIL_UNSIGNED_INDEX(p_idx, array.size());
uint64_t new_idx = move(p_idx, 0);
uint64_t swap_idx = array.size() - 1;
diff --git a/core/templates/cowdata.h b/core/templates/cowdata.h
index f1ac32928f..e760fc2176 100644
--- a/core/templates/cowdata.h
+++ b/core/templates/cowdata.h
@@ -183,6 +183,8 @@ public:
}
int find(const T &p_val, int p_from = 0) const;
+ int rfind(const T &p_val, int p_from = -1) const;
+ int count(const T &p_val) const;
_FORCE_INLINE_ CowData() {}
_FORCE_INLINE_ ~CowData();
@@ -350,6 +352,36 @@ int CowData<T>::find(const T &p_val, int p_from) const {
}
template <class T>
+int CowData<T>::rfind(const T &p_val, int p_from) const {
+ const int s = size();
+
+ if (p_from < 0) {
+ p_from = s + p_from;
+ }
+ if (p_from < 0 || p_from >= s) {
+ p_from = s - 1;
+ }
+
+ for (int i = p_from; i >= 0; i--) {
+ if (get(i) == p_val) {
+ return i;
+ }
+ }
+ return -1;
+}
+
+template <class T>
+int CowData<T>::count(const T &p_val) const {
+ int amount = 0;
+ for (int i = 0; i < size(); i++) {
+ if (get(i) == p_val) {
+ amount++;
+ }
+ }
+ return amount;
+}
+
+template <class T>
void CowData<T>::_ref(const CowData *p_from) {
_ref(*p_from);
}
diff --git a/core/templates/hash_map.h b/core/templates/hash_map.h
index fa5677cc70..e5f73171a2 100644
--- a/core/templates/hash_map.h
+++ b/core/templates/hash_map.h
@@ -31,524 +31,557 @@
#ifndef HASH_MAP_H
#define HASH_MAP_H
-#include "core/error/error_macros.h"
#include "core/math/math_funcs.h"
#include "core/os/memory.h"
-#include "core/string/ustring.h"
#include "core/templates/hashfuncs.h"
-#include "core/templates/list.h"
+#include "core/templates/paged_allocator.h"
+#include "core/templates/pair.h"
/**
- * @class HashMap
+ * A HashMap implementation that uses open addressing with Robin Hood hashing.
+ * Robin Hood hashing swaps out entries that have a smaller probing distance
+ * than the to-be-inserted entry, that evens out the average probing distance
+ * and enables faster lookups. Backward shift deletion is employed to further
+ * improve the performance and to avoid infinite loops in rare cases.
*
- * Implementation of a standard Hashing HashMap, for quick lookups of Data associated with a Key.
- * The implementation provides hashers for the default types, if you need a special kind of hasher, provide
- * your own.
- * @param TKey Key, search is based on it, needs to be hasheable. It is unique in this container.
- * @param TData Data, data associated with the key
- * @param Hasher Hasher object, needs to provide a valid static hash function for TKey
- * @param Comparator comparator object, needs to be able to safely compare two TKey values.
- * It needs to ensure that x == x for any items inserted in the map. Bear in mind that nan != nan when implementing an equality check.
- * @param MIN_HASH_TABLE_POWER Miminum size of the hash table, as a power of two. You rarely need to change this parameter.
- * @param RELATIONSHIP Relationship at which the hash table is resized. if amount of elements is RELATIONSHIP
- * times bigger than the hash table, table is resized to solve this condition. if RELATIONSHIP is zero, table is always MIN_HASH_TABLE_POWER.
+ * Keys and values are stored in a double linked list by insertion order. This
+ * has a slight performance overhead on lookup, which can be mostly compensated
+ * using a paged allocator if required.
*
+ * The assignment operator copy the pairs from one map to the other.
*/
-template <class TKey, class TData, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<TKey>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8>
+template <class TKey, class TValue>
+struct HashMapElement {
+ HashMapElement *next = nullptr;
+ HashMapElement *prev = nullptr;
+ KeyValue<TKey, TValue> data;
+ HashMapElement() {}
+ HashMapElement(const TKey &p_key, const TValue &p_value) :
+ data(p_key, p_value) {}
+};
+
+template <class TKey, class TValue,
+ class Hasher = HashMapHasherDefault,
+ class Comparator = HashMapComparatorDefault<TKey>,
+ class Allocator = DefaultTypedAllocator<HashMapElement<TKey, TValue>>>
class HashMap {
public:
- struct Pair {
- TKey key;
- TData data;
+ const uint32_t MIN_CAPACITY_INDEX = 2; // Use a prime.
+ const float MAX_OCCUPANCY = 0.75;
+ const uint32_t EMPTY_HASH = 0;
- Pair(const TKey &p_key) :
- key(p_key),
- data() {}
- Pair(const TKey &p_key, const TData &p_data) :
- key(p_key),
- data(p_data) {
- }
- };
+private:
+ Allocator element_alloc;
+ HashMapElement<TKey, TValue> **elements = nullptr;
+ uint32_t *hashes = nullptr;
+ HashMapElement<TKey, TValue> *head_element = nullptr;
+ HashMapElement<TKey, TValue> *tail_element = nullptr;
- struct Element {
- private:
- friend class HashMap;
+ uint32_t capacity_index = 0;
+ uint32_t num_elements = 0;
- uint32_t hash = 0;
- Element *next = nullptr;
- Element() {}
- Pair pair;
+ _FORCE_INLINE_ uint32_t _hash(const TKey &p_key) const {
+ uint32_t hash = Hasher::hash(p_key);
- public:
- const TKey &key() const {
- return pair.key;
+ if (unlikely(hash == EMPTY_HASH)) {
+ hash = EMPTY_HASH + 1;
}
- TData &value() {
- return pair.data;
- }
+ return hash;
+ }
- const TData &value() const {
- return pair.value();
+ _FORCE_INLINE_ uint32_t _get_probe_length(uint32_t p_pos, uint32_t p_hash, uint32_t p_capacity) const {
+ uint32_t original_pos = p_hash % p_capacity;
+ return (p_pos - original_pos + p_capacity) % p_capacity;
+ }
+
+ bool _lookup_pos(const TKey &p_key, uint32_t &r_pos) const {
+ if (elements == nullptr) {
+ return false; // Failed lookups, no elements
}
- Element(const TKey &p_key) :
- pair(p_key) {}
- Element(const Element &p_other) :
- hash(p_other.hash),
- pair(p_other.pair.key, p_other.pair.data) {}
- };
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+ uint32_t hash = _hash(p_key);
+ uint32_t pos = hash % capacity;
+ uint32_t distance = 0;
-private:
- Element **hash_table = nullptr;
- uint8_t hash_table_power = 0;
- uint32_t elements = 0;
+ while (true) {
+ if (hashes[pos] == EMPTY_HASH) {
+ return false;
+ }
- void make_hash_table() {
- ERR_FAIL_COND(hash_table);
+ if (distance > _get_probe_length(pos, hashes[pos], capacity)) {
+ return false;
+ }
- hash_table = memnew_arr(Element *, (1 << MIN_HASH_TABLE_POWER));
+ if (hashes[pos] == hash && Comparator::compare(elements[pos]->data.key, p_key)) {
+ r_pos = pos;
+ return true;
+ }
- hash_table_power = MIN_HASH_TABLE_POWER;
- elements = 0;
- for (int i = 0; i < (1 << MIN_HASH_TABLE_POWER); i++) {
- hash_table[i] = nullptr;
+ pos = (pos + 1) % capacity;
+ distance++;
}
}
- void erase_hash_table() {
- ERR_FAIL_COND_MSG(elements, "Cannot erase hash table if there are still elements inside.");
-
- memdelete_arr(hash_table);
- hash_table = nullptr;
- hash_table_power = 0;
- elements = 0;
- }
+ void _insert_with_hash(uint32_t p_hash, HashMapElement<TKey, TValue> *p_value) {
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+ uint32_t hash = p_hash;
+ HashMapElement<TKey, TValue> *value = p_value;
+ uint32_t distance = 0;
+ uint32_t pos = hash % capacity;
- void check_hash_table() {
- int new_hash_table_power = -1;
+ while (true) {
+ if (hashes[pos] == EMPTY_HASH) {
+ elements[pos] = value;
+ hashes[pos] = hash;
- if ((int)elements > ((1 << hash_table_power) * RELATIONSHIP)) {
- /* rehash up */
- new_hash_table_power = hash_table_power + 1;
+ num_elements++;
- while ((int)elements > ((1 << new_hash_table_power) * RELATIONSHIP)) {
- new_hash_table_power++;
+ return;
}
- } else if ((hash_table_power > (int)MIN_HASH_TABLE_POWER) && ((int)elements < ((1 << (hash_table_power - 1)) * RELATIONSHIP))) {
- /* rehash down */
- new_hash_table_power = hash_table_power - 1;
-
- while ((int)elements < ((1 << (new_hash_table_power - 1)) * RELATIONSHIP)) {
- new_hash_table_power--;
+ // Not an empty slot, let's check the probing length of the existing one.
+ uint32_t existing_probe_len = _get_probe_length(pos, hashes[pos], capacity);
+ if (existing_probe_len < distance) {
+ SWAP(hash, hashes[pos]);
+ SWAP(value, elements[pos]);
+ distance = existing_probe_len;
}
- if (new_hash_table_power < (int)MIN_HASH_TABLE_POWER) {
- new_hash_table_power = MIN_HASH_TABLE_POWER;
- }
+ pos = (pos + 1) % capacity;
+ distance++;
}
+ }
- if (new_hash_table_power == -1) {
- return;
- }
+ void _resize_and_rehash(uint32_t p_new_capacity_index) {
+ uint32_t old_capacity = hash_table_size_primes[capacity_index];
- Element **new_hash_table = memnew_arr(Element *, ((uint64_t)1 << new_hash_table_power));
- ERR_FAIL_COND_MSG(!new_hash_table, "Out of memory.");
+ // Capacity can't be 0.
+ capacity_index = MAX((uint32_t)MIN_CAPACITY_INDEX, p_new_capacity_index);
- for (int i = 0; i < (1 << new_hash_table_power); i++) {
- new_hash_table[i] = nullptr;
- }
+ uint32_t capacity = hash_table_size_primes[capacity_index];
- if (hash_table) {
- for (int i = 0; i < (1 << hash_table_power); i++) {
- while (hash_table[i]) {
- Element *se = hash_table[i];
- hash_table[i] = se->next;
- int new_pos = se->hash & ((1 << new_hash_table_power) - 1);
- se->next = new_hash_table[new_pos];
- new_hash_table[new_pos] = se;
- }
- }
+ HashMapElement<TKey, TValue> **old_elements = elements;
+ uint32_t *old_hashes = hashes;
- memdelete_arr(hash_table);
- }
- hash_table = new_hash_table;
- hash_table_power = new_hash_table_power;
- }
+ num_elements = 0;
+ hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+ elements = reinterpret_cast<HashMapElement<TKey, TValue> **>(Memory::alloc_static(sizeof(HashMapElement<TKey, TValue> *) * capacity));
- /* I want to have only one function.. */
- _FORCE_INLINE_ const Element *get_element(const TKey &p_key) const {
- uint32_t hash = Hasher::hash(p_key);
- uint32_t index = hash & ((1 << hash_table_power) - 1);
+ for (uint32_t i = 0; i < capacity; i++) {
+ hashes[i] = 0;
+ elements[i] = nullptr;
+ }
- Element *e = hash_table[index];
+ if (old_capacity == 0) {
+ // Nothing to do.
+ return;
+ }
- while (e) {
- /* checking hash first avoids comparing key, which may take longer */
- if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) {
- /* the pair exists in this hashtable, so just update data */
- return e;
+ for (uint32_t i = 0; i < old_capacity; i++) {
+ if (old_hashes[i] == EMPTY_HASH) {
+ continue;
}
- e = e->next;
+ _insert_with_hash(old_hashes[i], old_elements[i]);
}
- return nullptr;
+ Memory::free_static(old_elements);
+ Memory::free_static(old_hashes);
}
- Element *create_element(const TKey &p_key) {
- /* if element doesn't exist, create it */
- Element *e = memnew(Element(p_key));
- ERR_FAIL_COND_V_MSG(!e, nullptr, "Out of memory.");
- uint32_t hash = Hasher::hash(p_key);
- uint32_t index = hash & ((1 << hash_table_power) - 1);
- e->next = hash_table[index];
- e->hash = hash;
-
- hash_table[index] = e;
- elements++;
+ _FORCE_INLINE_ HashMapElement<TKey, TValue> *_insert(const TKey &p_key, const TValue &p_value, bool p_front_insert = false) {
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+ if (unlikely(elements == nullptr)) {
+ // Allocate on demand to save memory.
- return e;
- }
+ hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+ elements = reinterpret_cast<HashMapElement<TKey, TValue> **>(Memory::alloc_static(sizeof(HashMapElement<TKey, TValue> *) * capacity));
- void copy_from(const HashMap &p_t) {
- if (&p_t == this) {
- return; /* much less bother with that */
- }
-
- clear();
-
- if (!p_t.hash_table || p_t.hash_table_power == 0) {
- return; /* not copying from empty table */
+ for (uint32_t i = 0; i < capacity; i++) {
+ hashes[i] = EMPTY_HASH;
+ elements[i] = nullptr;
+ }
}
- hash_table = memnew_arr(Element *, (uint64_t)1 << p_t.hash_table_power);
- hash_table_power = p_t.hash_table_power;
- elements = p_t.elements;
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
- for (int i = 0; i < (1 << p_t.hash_table_power); i++) {
- hash_table[i] = nullptr;
-
- const Element *e = p_t.hash_table[i];
-
- while (e) {
- Element *le = memnew(Element(*e)); /* local element */
+ if (exists) {
+ elements[pos]->data.value = p_value;
+ return elements[pos];
+ } else {
+ if (num_elements + 1 > MAX_OCCUPANCY * capacity) {
+ ERR_FAIL_COND_V_MSG(capacity_index + 1 == HASH_TABLE_SIZE_MAX, nullptr, "Hash table maximum capacity reached, aborting insertion.");
+ _resize_and_rehash(capacity_index + 1);
+ }
- /* add to list and reassign pointers */
- le->next = hash_table[i];
- hash_table[i] = le;
+ HashMapElement<TKey, TValue> *elem = element_alloc.new_allocation(HashMapElement<TKey, TValue>(p_key, p_value));
- e = e->next;
+ if (tail_element == nullptr) {
+ head_element = elem;
+ tail_element = elem;
+ } else if (p_front_insert) {
+ head_element->prev = elem;
+ elem->next = head_element;
+ head_element = elem;
+ } else {
+ tail_element->next = elem;
+ elem->prev = tail_element;
+ tail_element = elem;
}
+
+ uint32_t hash = _hash(p_key);
+ _insert_with_hash(hash, elem);
+ return elem;
}
}
public:
- Element *set(const TKey &p_key, const TData &p_data) {
- return set(Pair(p_key, p_data));
- }
+ _FORCE_INLINE_ uint32_t get_capacity() const { return hash_table_size_primes[capacity_index]; }
+ _FORCE_INLINE_ uint32_t size() const { return num_elements; }
- Element *set(const Pair &p_pair) {
- Element *e = nullptr;
- if (!hash_table) {
- make_hash_table(); // if no table, make one
- } else {
- e = const_cast<Element *>(get_element(p_pair.key));
- }
+ /* Standard Godot Container API */
- /* if we made it up to here, the pair doesn't exist, create and assign */
+ bool is_empty() const {
+ return num_elements == 0;
+ }
- if (!e) {
- e = create_element(p_pair.key);
- if (!e) {
- return nullptr;
- }
- check_hash_table(); // perform mantenience routine
+ void clear() {
+ if (elements == nullptr) {
+ return;
}
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+ for (uint32_t i = 0; i < capacity; i++) {
+ if (hashes[i] == EMPTY_HASH) {
+ continue;
+ }
- e->pair.data = p_pair.data;
- return e;
- }
+ hashes[i] = EMPTY_HASH;
+ element_alloc.delete_allocation(elements[i]);
+ elements[i] = nullptr;
+ }
- bool has(const TKey &p_key) const {
- return getptr(p_key) != nullptr;
+ tail_element = nullptr;
+ head_element = nullptr;
+ num_elements = 0;
}
- /**
- * Get a key from data, return a const reference.
- * WARNING: this doesn't check errors, use either getptr and check nullptr, or check
- * first with has(key)
- */
-
- const TData &get(const TKey &p_key) const {
- const TData *res = getptr(p_key);
- CRASH_COND_MSG(!res, "Map key not found.");
- return *res;
+ TValue &get(const TKey &p_key) {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
+ CRASH_COND_MSG(!exists, "HashMap key not found.");
+ return elements[pos]->data.value;
}
- TData &get(const TKey &p_key) {
- TData *res = getptr(p_key);
- CRASH_COND_MSG(!res, "Map key not found.");
- return *res;
+ const TValue &get(const TKey &p_key) const {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
+ CRASH_COND_MSG(!exists, "HashMap key not found.");
+ return elements[pos]->data.value;
}
- /**
- * Same as get, except it can return nullptr when item was not found.
- * This is mainly used for speed purposes.
- */
+ const TValue *getptr(const TKey &p_key) const {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
- _FORCE_INLINE_ TData *getptr(const TKey &p_key) {
- if (unlikely(!hash_table)) {
- return nullptr;
+ if (exists) {
+ return &elements[pos]->data.value;
}
+ return nullptr;
+ }
- Element *e = const_cast<Element *>(get_element(p_key));
+ TValue *getptr(const TKey &p_key) {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
- if (e) {
- return &e->pair.data;
+ if (exists) {
+ return &elements[pos]->data.value;
}
-
return nullptr;
}
- _FORCE_INLINE_ const TData *getptr(const TKey &p_key) const {
- if (unlikely(!hash_table)) {
- return nullptr;
- }
+ _FORCE_INLINE_ bool has(const TKey &p_key) const {
+ uint32_t _pos = 0;
+ return _lookup_pos(p_key, _pos);
+ }
- const Element *e = const_cast<Element *>(get_element(p_key));
+ bool erase(const TKey &p_key) {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
- if (e) {
- return &e->pair.data;
+ if (!exists) {
+ return false;
}
- return nullptr;
- }
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+ uint32_t next_pos = (pos + 1) % capacity;
+ while (hashes[next_pos] != EMPTY_HASH && _get_probe_length(next_pos, hashes[next_pos], capacity) != 0) {
+ SWAP(hashes[next_pos], hashes[pos]);
+ SWAP(elements[next_pos], elements[pos]);
+ pos = next_pos;
+ next_pos = (pos + 1) % capacity;
+ }
- /**
- * Same as get, except it can return nullptr when item was not found.
- * This version is custom, will take a hash and a custom key (that should support operator==()
- */
+ hashes[pos] = EMPTY_HASH;
- template <class C>
- _FORCE_INLINE_ TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) {
- if (unlikely(!hash_table)) {
- return nullptr;
+ if (head_element == elements[pos]) {
+ head_element = elements[pos]->next;
}
- uint32_t hash = p_custom_hash;
- uint32_t index = hash & ((1 << hash_table_power) - 1);
-
- Element *e = hash_table[index];
+ if (tail_element == elements[pos]) {
+ tail_element = elements[pos]->prev;
+ }
- while (e) {
- /* checking hash first avoids comparing key, which may take longer */
- if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) {
- /* the pair exists in this hashtable, so just update data */
- return &e->pair.data;
- }
+ if (elements[pos]->prev) {
+ elements[pos]->prev->next = elements[pos]->next;
+ }
- e = e->next;
+ if (elements[pos]->next) {
+ elements[pos]->next->prev = elements[pos]->prev;
}
- return nullptr;
+ element_alloc.delete_allocation(elements[pos]);
+ elements[pos] = nullptr;
+
+ num_elements--;
+ return true;
}
- template <class C>
- _FORCE_INLINE_ const TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) const {
- if (unlikely(!hash_table)) {
- return nullptr;
+ // Reserves space for a number of elements, useful to avoid many resizes and rehashes.
+ // If adding a known (possibly large) number of elements at once, must be larger than old capacity.
+ void reserve(uint32_t p_new_capacity) {
+ uint32_t new_index = capacity_index;
+
+ while (hash_table_size_primes[new_index] < p_new_capacity) {
+ ERR_FAIL_COND_MSG(new_index + 1 == (uint32_t)HASH_TABLE_SIZE_MAX, nullptr);
+ new_index++;
}
- uint32_t hash = p_custom_hash;
- uint32_t index = hash & ((1 << hash_table_power) - 1);
+ if (new_index == capacity_index) {
+ return;
+ }
- const Element *e = hash_table[index];
+ if (elements == nullptr) {
+ capacity_index = new_index;
+ return; // Unallocated yet.
+ }
+ _resize_and_rehash(new_index);
+ }
- while (e) {
- /* checking hash first avoids comparing key, which may take longer */
- if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) {
- /* the pair exists in this hashtable, so just update data */
- return &e->pair.data;
- }
+ /** Iterator API **/
- e = e->next;
+ struct ConstIterator {
+ _FORCE_INLINE_ const KeyValue<TKey, TValue> &operator*() const {
+ return E->data;
+ }
+ _FORCE_INLINE_ const KeyValue<TKey, TValue> *operator->() const { return &E->data; }
+ _FORCE_INLINE_ ConstIterator &operator++() {
+ if (E) {
+ E = E->next;
+ }
+ return *this;
+ }
+ _FORCE_INLINE_ ConstIterator &operator--() {
+ if (E) {
+ E = E->prev;
+ }
+ return *this;
}
- return nullptr;
- }
+ _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; }
+ _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; }
- /**
- * Erase an item, return true if erasing was successful
- */
+ _FORCE_INLINE_ explicit operator bool() const {
+ return E != nullptr;
+ }
- bool erase(const TKey &p_key) {
- if (unlikely(!hash_table)) {
- return false;
+ _FORCE_INLINE_ ConstIterator(const HashMapElement<TKey, TValue> *p_E) { E = p_E; }
+ _FORCE_INLINE_ ConstIterator() {}
+ _FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
+ _FORCE_INLINE_ void operator=(const ConstIterator &p_it) {
+ E = p_it.E;
}
- uint32_t hash = Hasher::hash(p_key);
- uint32_t index = hash & ((1 << hash_table_power) - 1);
-
- Element *e = hash_table[index];
- Element *p = nullptr;
- while (e) {
- /* checking hash first avoids comparing key, which may take longer */
- if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) {
- if (p) {
- p->next = e->next;
- } else {
- //begin of list
- hash_table[index] = e->next;
- }
-
- memdelete(e);
- elements--;
-
- if (elements == 0) {
- erase_hash_table();
- } else {
- check_hash_table();
- }
- return true;
+ private:
+ const HashMapElement<TKey, TValue> *E = nullptr;
+ };
+
+ struct Iterator {
+ _FORCE_INLINE_ KeyValue<TKey, TValue> &operator*() const {
+ return E->data;
+ }
+ _FORCE_INLINE_ KeyValue<TKey, TValue> *operator->() const { return &E->data; }
+ _FORCE_INLINE_ Iterator &operator++() {
+ if (E) {
+ E = E->next;
+ }
+ return *this;
+ }
+ _FORCE_INLINE_ Iterator &operator--() {
+ if (E) {
+ E = E->prev;
}
+ return *this;
+ }
- p = e;
- e = e->next;
+ _FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; }
+ _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
+
+ _FORCE_INLINE_ explicit operator bool() const {
+ return E != nullptr;
}
- return false;
- }
+ _FORCE_INLINE_ Iterator(HashMapElement<TKey, TValue> *p_E) { E = p_E; }
+ _FORCE_INLINE_ Iterator() {}
+ _FORCE_INLINE_ Iterator(const Iterator &p_it) { E = p_it.E; }
+ _FORCE_INLINE_ void operator=(const Iterator &p_it) {
+ E = p_it.E;
+ }
+
+ operator ConstIterator() const {
+ return ConstIterator(E);
+ }
- inline const TData &operator[](const TKey &p_key) const { //constref
+ private:
+ HashMapElement<TKey, TValue> *E = nullptr;
+ };
- return get(p_key);
+ _FORCE_INLINE_ Iterator begin() {
+ return Iterator(head_element);
+ }
+ _FORCE_INLINE_ Iterator end() {
+ return Iterator(nullptr);
+ }
+ _FORCE_INLINE_ Iterator last() {
+ return Iterator(tail_element);
}
- inline TData &operator[](const TKey &p_key) { //assignment
- Element *e = nullptr;
- if (!hash_table) {
- make_hash_table(); // if no table, make one
- } else {
- e = const_cast<Element *>(get_element(p_key));
+ _FORCE_INLINE_ Iterator find(const TKey &p_key) {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
+ if (!exists) {
+ return end();
}
+ return Iterator(elements[pos]);
+ }
- /* if we made it up to here, the pair doesn't exist, create */
- if (!e) {
- e = create_element(p_key);
- CRASH_COND(!e);
- check_hash_table(); // perform mantenience routine
+ _FORCE_INLINE_ void remove(const Iterator &p_iter) {
+ if (p_iter) {
+ erase(p_iter->key);
}
+ }
- return e->pair.data;
+ _FORCE_INLINE_ ConstIterator begin() const {
+ return ConstIterator(head_element);
+ }
+ _FORCE_INLINE_ ConstIterator end() const {
+ return ConstIterator(nullptr);
+ }
+ _FORCE_INLINE_ ConstIterator last() const {
+ return ConstIterator(tail_element);
}
- /**
- * Get the next key to p_key, and the first key if p_key is null.
- * Returns a pointer to the next key if found, nullptr otherwise.
- * Adding/Removing elements while iterating will, of course, have unexpected results, don't do it.
- *
- * Example:
- *
- * const TKey *k=nullptr;
- *
- * while( (k=table.next(k)) ) {
- *
- * print( *k );
- * }
- *
- */
- const TKey *next(const TKey *p_key) const {
- if (unlikely(!hash_table)) {
- return nullptr;
+ _FORCE_INLINE_ ConstIterator find(const TKey &p_key) const {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
+ if (!exists) {
+ return end();
}
+ return ConstIterator(elements[pos]);
+ }
- if (!p_key) { /* get the first key */
-
- for (int i = 0; i < (1 << hash_table_power); i++) {
- if (hash_table[i]) {
- return &hash_table[i]->pair.key;
- }
- }
-
- } else { /* get the next key */
+ /* Indexing */
- const Element *e = get_element(*p_key);
- ERR_FAIL_COND_V_MSG(!e, nullptr, "Invalid key supplied.");
- if (e->next) {
- /* if there is a "next" in the list, return that */
- return &e->next->pair.key;
- } else {
- /* go to next elements */
- uint32_t index = e->hash & ((1 << hash_table_power) - 1);
- index++;
- for (int i = index; i < (1 << hash_table_power); i++) {
- if (hash_table[i]) {
- return &hash_table[i]->pair.key;
- }
- }
- }
+ const TValue &operator[](const TKey &p_key) const {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
+ CRASH_COND(!exists);
+ return elements[pos]->data.value;
+ }
- /* nothing found, was at end */
+ TValue &operator[](const TKey &p_key) {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
+ if (!exists) {
+ return _insert(p_key, TValue())->data.value;
+ } else {
+ return elements[pos]->data.value;
}
-
- return nullptr; /* nothing found */
}
- inline unsigned int size() const {
- return elements;
- }
+ /* Insert */
- inline bool is_empty() const {
- return elements == 0;
+ Iterator insert(const TKey &p_key, const TValue &p_value, bool p_front_insert = false) {
+ return Iterator(_insert(p_key, p_value, p_front_insert));
}
- void clear() {
- /* clean up */
- if (hash_table) {
- for (int i = 0; i < (1 << hash_table_power); i++) {
- while (hash_table[i]) {
- Element *e = hash_table[i];
- hash_table[i] = e->next;
- memdelete(e);
- }
- }
+ /* Constructors */
- memdelete_arr(hash_table);
+ HashMap(const HashMap &p_other) {
+ reserve(hash_table_size_primes[p_other.capacity_index]);
+
+ if (p_other.num_elements == 0) {
+ return;
}
- hash_table = nullptr;
- hash_table_power = 0;
- elements = 0;
+ for (const KeyValue<TKey, TValue> &E : p_other) {
+ insert(E.key, E.value);
+ }
}
- void operator=(const HashMap &p_table) {
- copy_from(p_table);
- }
+ void operator=(const HashMap &p_other) {
+ if (this == &p_other) {
+ return; // Ignore self assignment.
+ }
+ if (num_elements != 0) {
+ clear();
+ }
- void get_key_list(List<TKey> *r_keys) const {
- if (unlikely(!hash_table)) {
- return;
+ reserve(hash_table_size_primes[p_other.capacity_index]);
+
+ if (p_other.elements == nullptr) {
+ return; // Nothing to copy.
}
- for (int i = 0; i < (1 << hash_table_power); i++) {
- Element *e = hash_table[i];
- while (e) {
- r_keys->push_back(e->pair.key);
- e = e->next;
- }
+
+ for (const KeyValue<TKey, TValue> &E : p_other) {
+ insert(E.key, E.value);
}
}
- HashMap() {}
+ HashMap(uint32_t p_initial_capacity) {
+ // Capacity can't be 0.
+ capacity_index = 0;
+ reserve(p_initial_capacity);
+ }
+ HashMap() {
+ capacity_index = MIN_CAPACITY_INDEX;
+ }
- HashMap(const HashMap &p_table) {
- copy_from(p_table);
+ uint32_t debug_get_hash(uint32_t p_index) {
+ if (num_elements == 0) {
+ return 0;
+ }
+ ERR_FAIL_INDEX_V(p_index, get_capacity(), 0);
+ return hashes[p_index];
+ }
+ Iterator debug_get_element(uint32_t p_index) {
+ if (num_elements == 0) {
+ return Iterator();
+ }
+ ERR_FAIL_INDEX_V(p_index, get_capacity(), Iterator());
+ return Iterator(elements[p_index]);
}
~HashMap() {
clear();
+
+ if (elements != nullptr) {
+ Memory::free_static(elements);
+ Memory::free_static(hashes);
+ }
}
};
diff --git a/core/templates/hash_set.h b/core/templates/hash_set.h
new file mode 100644
index 0000000000..2318067dcc
--- /dev/null
+++ b/core/templates/hash_set.h
@@ -0,0 +1,473 @@
+/*************************************************************************/
+/* hash_set.h */
+/*************************************************************************/
+/* This file is part of: */
+/* GODOT ENGINE */
+/* https://godotengine.org */
+/*************************************************************************/
+/* Copyright (c) 2007-2022 Juan Linietsky, Ariel Manzur. */
+/* Copyright (c) 2014-2022 Godot Engine contributors (cf. AUTHORS.md). */
+/* */
+/* Permission is hereby granted, free of charge, to any person obtaining */
+/* a copy of this software and associated documentation files (the */
+/* "Software"), to deal in the Software without restriction, including */
+/* without limitation the rights to use, copy, modify, merge, publish, */
+/* distribute, sublicense, and/or sell copies of the Software, and to */
+/* permit persons to whom the Software is furnished to do so, subject to */
+/* the following conditions: */
+/* */
+/* The above copyright notice and this permission notice shall be */
+/* included in all copies or substantial portions of the Software. */
+/* */
+/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
+/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
+/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
+/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
+/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
+/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
+/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
+/*************************************************************************/
+
+#ifndef HASH_SET_H
+#define HASH_SET_H
+
+#include "core/math/math_funcs.h"
+#include "core/os/memory.h"
+#include "core/templates/hash_map.h"
+#include "core/templates/hashfuncs.h"
+#include "core/templates/paged_allocator.h"
+
+/**
+ * Implementation of Set using a bidi indexed hash map.
+ * Use RBSet instead of this only if the following conditions are met:
+ *
+ * - You need to keep an iterator or const pointer to Key and you intend to add/remove elements in the meantime.
+ * - Iteration order does matter (via operator<)
+ *
+ */
+
+template <class TKey,
+ class Hasher = HashMapHasherDefault,
+ class Comparator = HashMapComparatorDefault<TKey>>
+class HashSet {
+public:
+ static constexpr uint32_t MIN_CAPACITY_INDEX = 2; // Use a prime.
+ static constexpr float MAX_OCCUPANCY = 0.75;
+ static constexpr uint32_t EMPTY_HASH = 0;
+
+private:
+ TKey *keys = nullptr;
+ uint32_t *hash_to_key = nullptr;
+ uint32_t *key_to_hash = nullptr;
+ uint32_t *hashes = nullptr;
+
+ uint32_t capacity_index = 0;
+ uint32_t num_elements = 0;
+
+ _FORCE_INLINE_ uint32_t _hash(const TKey &p_key) const {
+ uint32_t hash = Hasher::hash(p_key);
+
+ if (unlikely(hash == EMPTY_HASH)) {
+ hash = EMPTY_HASH + 1;
+ }
+
+ return hash;
+ }
+
+ _FORCE_INLINE_ uint32_t _get_probe_length(uint32_t p_pos, uint32_t p_hash, uint32_t p_capacity) const {
+ uint32_t original_pos = p_hash % p_capacity;
+ return (p_pos - original_pos + p_capacity) % p_capacity;
+ }
+
+ bool _lookup_pos(const TKey &p_key, uint32_t &r_pos) const {
+ if (keys == nullptr) {
+ return false; // Failed lookups, no elements
+ }
+
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+ uint32_t hash = _hash(p_key);
+ uint32_t pos = hash % capacity;
+ uint32_t distance = 0;
+
+ while (true) {
+ if (hashes[pos] == EMPTY_HASH) {
+ return false;
+ }
+
+ if (distance > _get_probe_length(pos, hashes[pos], capacity)) {
+ return false;
+ }
+
+ if (hashes[pos] == hash && Comparator::compare(keys[hash_to_key[pos]], p_key)) {
+ r_pos = hash_to_key[pos];
+ return true;
+ }
+
+ pos = (pos + 1) % capacity;
+ distance++;
+ }
+ }
+
+ uint32_t _insert_with_hash(uint32_t p_hash, uint32_t p_index) {
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+ uint32_t hash = p_hash;
+ uint32_t index = p_index;
+ uint32_t distance = 0;
+ uint32_t pos = hash % capacity;
+
+ while (true) {
+ if (hashes[pos] == EMPTY_HASH) {
+ hashes[pos] = hash;
+ key_to_hash[index] = pos;
+ hash_to_key[pos] = index;
+ return pos;
+ }
+
+ // Not an empty slot, let's check the probing length of the existing one.
+ uint32_t existing_probe_len = _get_probe_length(pos, hashes[pos], capacity);
+ if (existing_probe_len < distance) {
+ key_to_hash[index] = pos;
+ SWAP(hash, hashes[pos]);
+ SWAP(index, hash_to_key[pos]);
+ distance = existing_probe_len;
+ }
+
+ pos = (pos + 1) % capacity;
+ distance++;
+ }
+ }
+
+ void _resize_and_rehash(uint32_t p_new_capacity_index) {
+ // Capacity can't be 0.
+ capacity_index = MAX((uint32_t)MIN_CAPACITY_INDEX, p_new_capacity_index);
+
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+
+ uint32_t *old_hashes = hashes;
+ uint32_t *old_key_to_hash = key_to_hash;
+
+ hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+ keys = reinterpret_cast<TKey *>(Memory::realloc_static(keys, sizeof(TKey) * capacity));
+ key_to_hash = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+ hash_to_key = reinterpret_cast<uint32_t *>(Memory::realloc_static(hash_to_key, sizeof(uint32_t) * capacity));
+
+ for (uint32_t i = 0; i < capacity; i++) {
+ hashes[i] = EMPTY_HASH;
+ }
+
+ for (uint32_t i = 0; i < num_elements; i++) {
+ uint32_t h = old_hashes[old_key_to_hash[i]];
+ _insert_with_hash(h, i);
+ }
+
+ Memory::free_static(old_hashes);
+ Memory::free_static(old_key_to_hash);
+ }
+
+ _FORCE_INLINE_ int32_t _insert(const TKey &p_key) {
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+ if (unlikely(keys == nullptr)) {
+ // Allocate on demand to save memory.
+
+ hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+ keys = reinterpret_cast<TKey *>(Memory::alloc_static(sizeof(TKey) * capacity));
+ key_to_hash = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+ hash_to_key = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+
+ for (uint32_t i = 0; i < capacity; i++) {
+ hashes[i] = EMPTY_HASH;
+ }
+ }
+
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
+
+ if (exists) {
+ return pos;
+ } else {
+ if (num_elements + 1 > MAX_OCCUPANCY * capacity) {
+ ERR_FAIL_COND_V_MSG(capacity_index + 1 == HASH_TABLE_SIZE_MAX, -1, "Hash table maximum capacity reached, aborting insertion.");
+ _resize_and_rehash(capacity_index + 1);
+ }
+
+ uint32_t hash = _hash(p_key);
+ memnew_placement(&keys[num_elements], TKey(p_key));
+ _insert_with_hash(hash, num_elements);
+ num_elements++;
+ return num_elements - 1;
+ }
+ }
+
+ void _init_from(const HashSet &p_other) {
+ capacity_index = p_other.capacity_index;
+ num_elements = p_other.num_elements;
+
+ if (p_other.num_elements == 0) {
+ return;
+ }
+
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+
+ hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+ keys = reinterpret_cast<TKey *>(Memory::alloc_static(sizeof(TKey) * capacity));
+ key_to_hash = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+ hash_to_key = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+
+ for (uint32_t i = 0; i < num_elements; i++) {
+ memnew_placement(&keys[i], TKey(p_other.keys[i]));
+ key_to_hash[i] = p_other.key_to_hash[i];
+ }
+
+ for (uint32_t i = 0; i < capacity; i++) {
+ hashes[i] = p_other.hashes[i];
+ hash_to_key[i] = p_other.hash_to_key[i];
+ }
+ }
+
+public:
+ _FORCE_INLINE_ uint32_t get_capacity() const { return hash_table_size_primes[capacity_index]; }
+ _FORCE_INLINE_ uint32_t size() const { return num_elements; }
+
+ /* Standard Godot Container API */
+
+ bool is_empty() const {
+ return num_elements == 0;
+ }
+
+ void clear() {
+ if (keys == nullptr) {
+ return;
+ }
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+ for (uint32_t i = 0; i < capacity; i++) {
+ hashes[i] = EMPTY_HASH;
+ }
+ for (uint32_t i = 0; i < num_elements; i++) {
+ keys[i].~TKey();
+ }
+
+ num_elements = 0;
+ }
+
+ _FORCE_INLINE_ bool has(const TKey &p_key) const {
+ uint32_t _pos = 0;
+ return _lookup_pos(p_key, _pos);
+ }
+
+ bool erase(const TKey &p_key) {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
+
+ if (!exists) {
+ return false;
+ }
+
+ uint32_t key_pos = pos;
+ pos = key_to_hash[pos]; //make hash pos
+
+ uint32_t capacity = hash_table_size_primes[capacity_index];
+ uint32_t next_pos = (pos + 1) % capacity;
+ while (hashes[next_pos] != EMPTY_HASH && _get_probe_length(next_pos, hashes[next_pos], capacity) != 0) {
+ uint32_t kpos = hash_to_key[pos];
+ uint32_t kpos_next = hash_to_key[next_pos];
+ SWAP(key_to_hash[kpos], key_to_hash[kpos_next]);
+ SWAP(hashes[next_pos], hashes[pos]);
+ SWAP(hash_to_key[next_pos], hash_to_key[pos]);
+
+ pos = next_pos;
+ next_pos = (pos + 1) % capacity;
+ }
+
+ hashes[pos] = EMPTY_HASH;
+ keys[key_pos].~TKey();
+ num_elements--;
+ if (key_pos < num_elements) {
+ // Not the last key, move the last one here to keep keys lineal
+ memnew_placement(&keys[key_pos], TKey(keys[num_elements]));
+ keys[num_elements].~TKey();
+ key_to_hash[key_pos] = key_to_hash[num_elements];
+ hash_to_key[key_to_hash[num_elements]] = key_pos;
+ }
+
+ return true;
+ }
+
+ // Reserves space for a number of elements, useful to avoid many resizes and rehashes.
+ // If adding a known (possibly large) number of elements at once, must be larger than old capacity.
+ void reserve(uint32_t p_new_capacity) {
+ uint32_t new_index = capacity_index;
+
+ while (hash_table_size_primes[new_index] < p_new_capacity) {
+ ERR_FAIL_COND_MSG(new_index + 1 == (uint32_t)HASH_TABLE_SIZE_MAX, nullptr);
+ new_index++;
+ }
+
+ if (new_index == capacity_index) {
+ return;
+ }
+
+ if (keys == nullptr) {
+ capacity_index = new_index;
+ return; // Unallocated yet.
+ }
+ _resize_and_rehash(new_index);
+ }
+
+ /** Iterator API **/
+
+ struct Iterator {
+ _FORCE_INLINE_ const TKey &operator*() const {
+ return keys[index];
+ }
+ _FORCE_INLINE_ const TKey *operator->() const {
+ return &keys[index];
+ }
+ _FORCE_INLINE_ Iterator &operator++() {
+ index++;
+ if (index >= (int32_t)num_keys) {
+ index = -1;
+ keys = nullptr;
+ num_keys = 0;
+ }
+ return *this;
+ }
+ _FORCE_INLINE_ Iterator &operator--() {
+ index--;
+ if (index < 0) {
+ index = -1;
+ keys = nullptr;
+ num_keys = 0;
+ }
+ return *this;
+ }
+
+ _FORCE_INLINE_ bool operator==(const Iterator &b) const { return keys == b.keys && index == b.index; }
+ _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return keys != b.keys || index != b.index; }
+
+ _FORCE_INLINE_ explicit operator bool() const {
+ return keys != nullptr;
+ }
+
+ _FORCE_INLINE_ Iterator(const TKey *p_keys, uint32_t p_num_keys, int32_t p_index = -1) {
+ keys = p_keys;
+ num_keys = p_num_keys;
+ index = p_index;
+ }
+ _FORCE_INLINE_ Iterator() {}
+ _FORCE_INLINE_ Iterator(const Iterator &p_it) {
+ keys = p_it.keys;
+ num_keys = p_it.num_keys;
+ index = p_it.index;
+ }
+ _FORCE_INLINE_ void operator=(const Iterator &p_it) {
+ keys = p_it.keys;
+ num_keys = p_it.num_keys;
+ index = p_it.index;
+ }
+
+ private:
+ const TKey *keys = nullptr;
+ uint32_t num_keys = 0;
+ int32_t index = -1;
+ };
+
+ _FORCE_INLINE_ Iterator begin() const {
+ return num_elements ? Iterator(keys, num_elements, 0) : Iterator();
+ }
+ _FORCE_INLINE_ Iterator end() const {
+ return Iterator();
+ }
+ _FORCE_INLINE_ Iterator last() const {
+ if (num_elements == 0) {
+ return Iterator();
+ }
+ return Iterator(keys, num_elements, num_elements - 1);
+ }
+
+ _FORCE_INLINE_ Iterator find(const TKey &p_key) const {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
+ if (!exists) {
+ return end();
+ }
+ return Iterator(keys, num_elements, pos);
+ }
+
+ _FORCE_INLINE_ void remove(const Iterator &p_iter) {
+ if (p_iter) {
+ erase(*p_iter);
+ }
+ }
+
+ /* Insert */
+
+ Iterator insert(const TKey &p_key) {
+ uint32_t pos = _insert(p_key);
+ return Iterator(keys, num_elements, pos);
+ }
+
+ /* Constructors */
+
+ HashSet(const HashSet &p_other) {
+ _init_from(p_other);
+ }
+
+ void operator=(const HashSet &p_other) {
+ if (this == &p_other) {
+ return; // Ignore self assignment.
+ }
+
+ clear();
+
+ if (keys != nullptr) {
+ Memory::free_static(keys);
+ Memory::free_static(key_to_hash);
+ Memory::free_static(hash_to_key);
+ Memory::free_static(hashes);
+ keys = nullptr;
+ hashes = nullptr;
+ hash_to_key = nullptr;
+ key_to_hash = nullptr;
+ }
+
+ _init_from(p_other);
+ }
+
+ HashSet(uint32_t p_initial_capacity) {
+ // Capacity can't be 0.
+ capacity_index = 0;
+ reserve(p_initial_capacity);
+ }
+ HashSet() {
+ capacity_index = MIN_CAPACITY_INDEX;
+ }
+
+ void reset() {
+ clear();
+
+ if (keys != nullptr) {
+ Memory::free_static(keys);
+ Memory::free_static(key_to_hash);
+ Memory::free_static(hash_to_key);
+ Memory::free_static(hashes);
+ keys = nullptr;
+ hashes = nullptr;
+ hash_to_key = nullptr;
+ key_to_hash = nullptr;
+ }
+ capacity_index = MIN_CAPACITY_INDEX;
+ }
+
+ ~HashSet() {
+ clear();
+
+ if (keys != nullptr) {
+ Memory::free_static(keys);
+ Memory::free_static(key_to_hash);
+ Memory::free_static(hash_to_key);
+ Memory::free_static(hashes);
+ }
+ }
+};
+
+#endif // HASH_SET_H
diff --git a/core/templates/hashfuncs.h b/core/templates/hashfuncs.h
index 2a129f97d5..98ff7fa4ce 100644
--- a/core/templates/hashfuncs.h
+++ b/core/templates/hashfuncs.h
@@ -31,14 +31,22 @@
#ifndef HASHFUNCS_H
#define HASHFUNCS_H
+#include "core/math/aabb.h"
#include "core/math/math_defs.h"
#include "core/math/math_funcs.h"
+#include "core/math/rect2.h"
+#include "core/math/rect2i.h"
+#include "core/math/vector2.h"
+#include "core/math/vector2i.h"
+#include "core/math/vector3.h"
+#include "core/math/vector3i.h"
#include "core/object/object_id.h"
#include "core/string/node_path.h"
#include "core/string/string_name.h"
#include "core/string/ustring.h"
#include "core/templates/rid.h"
#include "core/typedefs.h"
+
/**
* Hashing functions
*/
@@ -48,7 +56,7 @@
* @param C String
* @return 32-bits hashcode
*/
-static inline uint32_t hash_djb2(const char *p_cstr) {
+static _FORCE_INLINE_ uint32_t hash_djb2(const char *p_cstr) {
const unsigned char *chr = (const unsigned char *)p_cstr;
uint32_t hash = 5381;
uint32_t c;
@@ -60,7 +68,7 @@ static inline uint32_t hash_djb2(const char *p_cstr) {
return hash;
}
-static inline uint32_t hash_djb2_buffer(const uint8_t *p_buff, int p_len, uint32_t p_prev = 5381) {
+static _FORCE_INLINE_ uint32_t hash_djb2_buffer(const uint8_t *p_buff, int p_len, uint32_t p_prev = 5381) {
uint32_t hash = p_prev;
for (int i = 0; i < p_len; i++) {
@@ -70,7 +78,7 @@ static inline uint32_t hash_djb2_buffer(const uint8_t *p_buff, int p_len, uint32
return hash;
}
-static inline uint32_t hash_djb2_one_32(uint32_t p_in, uint32_t p_prev = 5381) {
+static _FORCE_INLINE_ uint32_t hash_djb2_one_32(uint32_t p_in, uint32_t p_prev = 5381) {
return ((p_prev << 5) + p_prev) + p_in;
}
@@ -81,7 +89,7 @@ static inline uint32_t hash_djb2_one_32(uint32_t p_in, uint32_t p_prev = 5381) {
* @param p_int - 64-bit unsigned integer key to be hashed
* @return unsigned 32-bit value representing hashcode
*/
-static inline uint32_t hash_one_uint64(const uint64_t p_int) {
+static _FORCE_INLINE_ uint32_t hash_one_uint64(const uint64_t p_int) {
uint64_t v = p_int;
v = (~v) + (v << 18); // v = (v << 18) - v - 1;
v = v ^ (v >> 31);
@@ -92,7 +100,72 @@ static inline uint32_t hash_one_uint64(const uint64_t p_int) {
return uint32_t(v);
}
-static inline uint32_t hash_djb2_one_float(double p_in, uint32_t p_prev = 5381) {
+// Murmurhash3 32-bit version.
+// All MurmurHash versions are public domain software, and the author disclaims all copyright to their code.
+
+static _FORCE_INLINE_ uint32_t rotl32(uint32_t x, int8_t r) {
+ return (x << r) | (x >> (32 - r));
+}
+
+static _FORCE_INLINE_ uint32_t fmix32(uint32_t h) {
+ h ^= h >> 16;
+ h *= 0x85ebca6b;
+ h ^= h >> 13;
+ h *= 0xc2b2ae35;
+ h ^= h >> 16;
+
+ return h;
+}
+
+static _FORCE_INLINE_ uint32_t hash_murmur3_32(const void *key, int length, const uint32_t seed = 0x7F07C65) {
+ // Although not required, this is a random prime number.
+ const uint8_t *data = (const uint8_t *)key;
+ const int nblocks = length / 4;
+
+ uint32_t h1 = seed;
+
+ const uint32_t c1 = 0xcc9e2d51;
+ const uint32_t c2 = 0x1b873593;
+
+ const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
+
+ for (int i = -nblocks; i; i++) {
+ uint32_t k1 = blocks[i];
+
+ k1 *= c1;
+ k1 = rotl32(k1, 15);
+ k1 *= c2;
+
+ h1 ^= k1;
+ h1 = rotl32(h1, 13);
+ h1 = h1 * 5 + 0xe6546b64;
+ }
+
+ const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
+
+ uint32_t k1 = 0;
+
+ switch (length & 3) {
+ case 3:
+ k1 ^= tail[2] << 16;
+ [[fallthrough]];
+ case 2:
+ k1 ^= tail[1] << 8;
+ [[fallthrough]];
+ case 1:
+ k1 ^= tail[0];
+ k1 *= c1;
+ k1 = rotl32(k1, 15);
+ k1 *= c2;
+ h1 ^= k1;
+ };
+
+ // Finalize with additional bit mixing.
+ h1 ^= length;
+ return fmix32(h1);
+}
+
+static _FORCE_INLINE_ uint32_t hash_djb2_one_float(double p_in, uint32_t p_prev = 5381) {
union {
double d;
uint64_t i;
@@ -111,7 +184,7 @@ static inline uint32_t hash_djb2_one_float(double p_in, uint32_t p_prev = 5381)
}
template <class T>
-static inline uint32_t make_uint32_t(T p_in) {
+static _FORCE_INLINE_ uint32_t make_uint32_t(T p_in) {
union {
T t;
uint32_t _u32;
@@ -121,7 +194,7 @@ static inline uint32_t make_uint32_t(T p_in) {
return _u._u32;
}
-static inline uint64_t hash_djb2_one_float_64(double p_in, uint64_t p_prev = 5381) {
+static _FORCE_INLINE_ uint64_t hash_djb2_one_float_64(double p_in, uint64_t p_prev = 5381) {
union {
double d;
uint64_t i;
@@ -139,12 +212,12 @@ static inline uint64_t hash_djb2_one_float_64(double p_in, uint64_t p_prev = 538
return ((p_prev << 5) + p_prev) + u.i;
}
-static inline uint64_t hash_djb2_one_64(uint64_t p_in, uint64_t p_prev = 5381) {
+static _FORCE_INLINE_ uint64_t hash_djb2_one_64(uint64_t p_in, uint64_t p_prev = 5381) {
return ((p_prev << 5) + p_prev) + p_in;
}
template <class T>
-static inline uint64_t make_uint64_t(T p_in) {
+static _FORCE_INLINE_ uint64_t make_uint64_t(T p_in) {
union {
T t;
uint64_t _u64;
@@ -155,30 +228,44 @@ static inline uint64_t make_uint64_t(T p_in) {
return _u._u64;
}
+template <class T>
+class Ref;
+
struct HashMapHasherDefault {
+ // Generic hash function for any type.
+ template <class T>
+ static _FORCE_INLINE_ uint32_t hash(const T *p_pointer) { return hash_one_uint64((uint64_t)p_pointer); }
+
+ template <class T>
+ static _FORCE_INLINE_ uint32_t hash(const Ref<T> &p_ref) { return hash_one_uint64((uint64_t)p_ref.operator->()); }
+
static _FORCE_INLINE_ uint32_t hash(const String &p_string) { return p_string.hash(); }
static _FORCE_INLINE_ uint32_t hash(const char *p_cstr) { return hash_djb2(p_cstr); }
- static _FORCE_INLINE_ uint32_t hash(const uint64_t p_int) { return hash_one_uint64(p_int); }
- static _FORCE_INLINE_ uint32_t hash(const ObjectID &p_id) { return hash_one_uint64(p_id); }
-
- static _FORCE_INLINE_ uint32_t hash(const int64_t p_int) { return hash(uint64_t(p_int)); }
- static _FORCE_INLINE_ uint32_t hash(const float p_float) { return hash_djb2_one_float(p_float); }
- static _FORCE_INLINE_ uint32_t hash(const double p_double) { return hash_djb2_one_float(p_double); }
- static _FORCE_INLINE_ uint32_t hash(const uint32_t p_int) { return p_int; }
- static _FORCE_INLINE_ uint32_t hash(const int32_t p_int) { return (uint32_t)p_int; }
- static _FORCE_INLINE_ uint32_t hash(const uint16_t p_int) { return p_int; }
- static _FORCE_INLINE_ uint32_t hash(const int16_t p_int) { return (uint32_t)p_int; }
- static _FORCE_INLINE_ uint32_t hash(const uint8_t p_int) { return p_int; }
- static _FORCE_INLINE_ uint32_t hash(const int8_t p_int) { return (uint32_t)p_int; }
- static _FORCE_INLINE_ uint32_t hash(const wchar_t p_wchar) { return (uint32_t)p_wchar; }
- static _FORCE_INLINE_ uint32_t hash(const char16_t p_uchar) { return (uint32_t)p_uchar; }
- static _FORCE_INLINE_ uint32_t hash(const char32_t p_uchar) { return (uint32_t)p_uchar; }
+ static _FORCE_INLINE_ uint32_t hash(const wchar_t p_wchar) { return fmix32(p_wchar); }
+ static _FORCE_INLINE_ uint32_t hash(const char16_t p_uchar) { return fmix32(p_uchar); }
+ static _FORCE_INLINE_ uint32_t hash(const char32_t p_uchar) { return fmix32(p_uchar); }
static _FORCE_INLINE_ uint32_t hash(const RID &p_rid) { return hash_one_uint64(p_rid.get_id()); }
-
static _FORCE_INLINE_ uint32_t hash(const StringName &p_string_name) { return p_string_name.hash(); }
static _FORCE_INLINE_ uint32_t hash(const NodePath &p_path) { return p_path.hash(); }
+ static _FORCE_INLINE_ uint32_t hash(const ObjectID &p_id) { return hash_one_uint64(p_id); }
- //static _FORCE_INLINE_ uint32_t hash(const void* p_ptr) { return uint32_t(uint64_t(p_ptr))*(0x9e3779b1L); }
+ static _FORCE_INLINE_ uint32_t hash(const uint64_t p_int) { return hash_one_uint64(p_int); }
+ static _FORCE_INLINE_ uint32_t hash(const int64_t p_int) { return hash_one_uint64(p_int); }
+ static _FORCE_INLINE_ uint32_t hash(const float p_float) { return hash_djb2_one_float(p_float); }
+ static _FORCE_INLINE_ uint32_t hash(const double p_double) { return hash_djb2_one_float(p_double); }
+ static _FORCE_INLINE_ uint32_t hash(const uint32_t p_int) { return fmix32(p_int); }
+ static _FORCE_INLINE_ uint32_t hash(const int32_t p_int) { return fmix32(p_int); }
+ static _FORCE_INLINE_ uint32_t hash(const uint16_t p_int) { return fmix32(p_int); }
+ static _FORCE_INLINE_ uint32_t hash(const int16_t p_int) { return fmix32(p_int); }
+ static _FORCE_INLINE_ uint32_t hash(const uint8_t p_int) { return fmix32(p_int); }
+ static _FORCE_INLINE_ uint32_t hash(const int8_t p_int) { return fmix32(p_int); }
+ static _FORCE_INLINE_ uint32_t hash(const Vector2i &p_vec) { return hash_murmur3_32(&p_vec, sizeof(Vector2i)); }
+ static _FORCE_INLINE_ uint32_t hash(const Vector3i &p_vec) { return hash_murmur3_32(&p_vec, sizeof(Vector3i)); }
+ static _FORCE_INLINE_ uint32_t hash(const Vector2 &p_vec) { return hash_murmur3_32(&p_vec, sizeof(Vector2)); }
+ static _FORCE_INLINE_ uint32_t hash(const Vector3 &p_vec) { return hash_murmur3_32(&p_vec, sizeof(Vector3)); }
+ static _FORCE_INLINE_ uint32_t hash(const Rect2i &p_rect) { return hash_murmur3_32(&p_rect, sizeof(Rect2i)); }
+ static _FORCE_INLINE_ uint32_t hash(const Rect2 &p_rect) { return hash_murmur3_32(&p_rect, sizeof(Rect2)); }
+ static _FORCE_INLINE_ uint32_t hash(const AABB &p_aabb) { return hash_murmur3_32(&p_aabb, sizeof(AABB)); }
};
template <typename T>
@@ -186,14 +273,68 @@ struct HashMapComparatorDefault {
static bool compare(const T &p_lhs, const T &p_rhs) {
return p_lhs == p_rhs;
}
+};
- bool compare(const float &p_lhs, const float &p_rhs) {
+template <>
+struct HashMapComparatorDefault<float> {
+ static bool compare(const float &p_lhs, const float &p_rhs) {
return (p_lhs == p_rhs) || (Math::is_nan(p_lhs) && Math::is_nan(p_rhs));
}
+};
- bool compare(const double &p_lhs, const double &p_rhs) {
+template <>
+struct HashMapComparatorDefault<double> {
+ static bool compare(const double &p_lhs, const double &p_rhs) {
return (p_lhs == p_rhs) || (Math::is_nan(p_lhs) && Math::is_nan(p_rhs));
}
};
+template <>
+struct HashMapComparatorDefault<Vector2> {
+ static bool compare(const Vector2 &p_lhs, const Vector2 &p_rhs) {
+ return ((p_lhs.x == p_rhs.x) || (Math::is_nan(p_lhs.x) && Math::is_nan(p_rhs.x))) && ((p_lhs.y == p_rhs.y) || (Math::is_nan(p_lhs.y) && Math::is_nan(p_rhs.y)));
+ }
+};
+
+template <>
+struct HashMapComparatorDefault<Vector3> {
+ static bool compare(const Vector3 &p_lhs, const Vector3 &p_rhs) {
+ return ((p_lhs.x == p_rhs.x) || (Math::is_nan(p_lhs.x) && Math::is_nan(p_rhs.x))) && ((p_lhs.y == p_rhs.y) || (Math::is_nan(p_lhs.y) && Math::is_nan(p_rhs.y))) && ((p_lhs.z == p_rhs.z) || (Math::is_nan(p_lhs.z) && Math::is_nan(p_rhs.z)));
+ }
+};
+
+constexpr uint32_t HASH_TABLE_SIZE_MAX = 29;
+
+const uint32_t hash_table_size_primes[HASH_TABLE_SIZE_MAX] = {
+ 5,
+ 13,
+ 23,
+ 47,
+ 97,
+ 193,
+ 389,
+ 769,
+ 1543,
+ 3079,
+ 6151,
+ 12289,
+ 24593,
+ 49157,
+ 98317,
+ 196613,
+ 393241,
+ 786433,
+ 1572869,
+ 3145739,
+ 6291469,
+ 12582917,
+ 25165843,
+ 50331653,
+ 100663319,
+ 201326611,
+ 402653189,
+ 805306457,
+ 1610612741,
+};
+
#endif // HASHFUNCS_H
diff --git a/core/templates/ordered_hash_map.h b/core/templates/ordered_hash_map.h
deleted file mode 100644
index 3d1f3a08ec..0000000000
--- a/core/templates/ordered_hash_map.h
+++ /dev/null
@@ -1,301 +0,0 @@
-/*************************************************************************/
-/* ordered_hash_map.h */
-/*************************************************************************/
-/* This file is part of: */
-/* GODOT ENGINE */
-/* https://godotengine.org */
-/*************************************************************************/
-/* Copyright (c) 2007-2022 Juan Linietsky, Ariel Manzur. */
-/* Copyright (c) 2014-2022 Godot Engine contributors (cf. AUTHORS.md). */
-/* */
-/* Permission is hereby granted, free of charge, to any person obtaining */
-/* a copy of this software and associated documentation files (the */
-/* "Software"), to deal in the Software without restriction, including */
-/* without limitation the rights to use, copy, modify, merge, publish, */
-/* distribute, sublicense, and/or sell copies of the Software, and to */
-/* permit persons to whom the Software is furnished to do so, subject to */
-/* the following conditions: */
-/* */
-/* The above copyright notice and this permission notice shall be */
-/* included in all copies or substantial portions of the Software. */
-/* */
-/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
-/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
-/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
-/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
-/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
-/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
-/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
-/*************************************************************************/
-
-#ifndef ORDERED_HASH_MAP_H
-#define ORDERED_HASH_MAP_H
-
-#include "core/templates/hash_map.h"
-#include "core/templates/list.h"
-#include "core/templates/pair.h"
-
-/**
- * A hash map which allows to iterate elements in insertion order.
- * Insertion, lookup, deletion have O(1) complexity.
- * The API aims to be consistent with Map rather than HashMap, because the
- * former is more frequently used and is more coherent with the rest of the
- * codebase.
- * Deletion during iteration is safe and will preserve the order.
- */
-template <class K, class V, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<K>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8>
-class OrderedHashMap {
- typedef List<Pair<const K *, V>> InternalList;
- typedef HashMap<K, typename InternalList::Element *, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP> InternalMap;
-
- InternalList list;
- InternalMap map;
-
-public:
- class Element {
- friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>;
-
- typename InternalList::Element *list_element = nullptr;
- typename InternalList::Element *prev_element = nullptr;
- typename InternalList::Element *next_element = nullptr;
-
- Element(typename InternalList::Element *p_element) {
- list_element = p_element;
-
- if (list_element) {
- next_element = list_element->next();
- prev_element = list_element->prev();
- }
- }
-
- public:
- _FORCE_INLINE_ Element() {}
-
- Element next() const {
- return Element(next_element);
- }
-
- Element prev() const {
- return Element(prev_element);
- }
-
- Element(const Element &other) :
- list_element(other.list_element),
- prev_element(other.prev_element),
- next_element(other.next_element) {
- }
-
- void operator=(const Element &other) {
- list_element = other.list_element;
- next_element = other.next_element;
- prev_element = other.prev_element;
- }
-
- _FORCE_INLINE_ bool operator==(const Element &p_other) const {
- return this->list_element == p_other.list_element;
- }
- _FORCE_INLINE_ bool operator!=(const Element &p_other) const {
- return this->list_element != p_other.list_element;
- }
-
- operator bool() const {
- return (list_element != nullptr);
- }
-
- const K &key() const {
- CRASH_COND(!list_element);
- return *(list_element->get().first);
- }
-
- V &value() {
- CRASH_COND(!list_element);
- return list_element->get().second;
- }
-
- const V &value() const {
- CRASH_COND(!list_element);
- return list_element->get().second;
- }
-
- V &get() {
- CRASH_COND(!list_element);
- return list_element->get().second;
- }
-
- const V &get() const {
- CRASH_COND(!list_element);
- return list_element->get().second;
- }
- };
-
- class ConstElement {
- friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>;
-
- const typename InternalList::Element *list_element = nullptr;
-
- ConstElement(const typename InternalList::Element *p_element) :
- list_element(p_element) {
- }
-
- public:
- _FORCE_INLINE_ ConstElement() {}
-
- ConstElement(const ConstElement &other) :
- list_element(other.list_element) {
- }
-
- void operator=(const ConstElement &other) {
- list_element = other.list_element;
- }
-
- ConstElement next() const {
- return ConstElement(list_element ? list_element->next() : nullptr);
- }
-
- ConstElement prev() const {
- return ConstElement(list_element ? list_element->prev() : nullptr);
- }
-
- _FORCE_INLINE_ bool operator==(const ConstElement &p_other) const {
- return this->list_element == p_other.list_element;
- }
- _FORCE_INLINE_ bool operator!=(const ConstElement &p_other) const {
- return this->list_element != p_other.list_element;
- }
-
- operator bool() const {
- return (list_element != nullptr);
- }
-
- const K &key() const {
- CRASH_COND(!list_element);
- return *(list_element->get().first);
- }
-
- const V &value() const {
- CRASH_COND(!list_element);
- return list_element->get().second;
- }
-
- const V &get() const {
- CRASH_COND(!list_element);
- return list_element->get().second;
- }
- };
-
- ConstElement find(const K &p_key) const {
- typename InternalList::Element *const *list_element = map.getptr(p_key);
- if (list_element) {
- return ConstElement(*list_element);
- }
- return ConstElement(nullptr);
- }
-
- Element find(const K &p_key) {
- typename InternalList::Element **list_element = map.getptr(p_key);
- if (list_element) {
- return Element(*list_element);
- }
- return Element(nullptr);
- }
-
- Element insert(const K &p_key, const V &p_value) {
- typename InternalList::Element **list_element = map.getptr(p_key);
- if (list_element) {
- (*list_element)->get().second = p_value;
- return Element(*list_element);
- }
- // Incorrectly set the first value of the pair with a value that will
- // be invalid as soon as we leave this function...
- typename InternalList::Element *new_element = list.push_back(Pair<const K *, V>(&p_key, p_value));
- // ...this is needed here in case the hashmap recursively reference itself...
- typename InternalMap::Element *e = map.set(p_key, new_element);
- // ...now we can set the right value !
- new_element->get().first = &e->key();
-
- return Element(new_element);
- }
-
- void erase(Element &p_element) {
- map.erase(p_element.key());
- list.erase(p_element.list_element);
- p_element.list_element = nullptr;
- }
-
- bool erase(const K &p_key) {
- typename InternalList::Element **list_element = map.getptr(p_key);
- if (list_element) {
- list.erase(*list_element);
- map.erase(p_key);
- return true;
- }
- return false;
- }
-
- inline bool has(const K &p_key) const {
- return map.has(p_key);
- }
-
- const V &operator[](const K &p_key) const {
- ConstElement e = find(p_key);
- CRASH_COND(!e);
- return e.value();
- }
-
- V &operator[](const K &p_key) {
- Element e = find(p_key);
- if (!e) {
- // consistent with Map behaviour
- e = insert(p_key, V());
- }
- return e.value();
- }
-
- inline Element front() {
- return Element(list.front());
- }
-
- inline Element back() {
- return Element(list.back());
- }
-
- inline ConstElement front() const {
- return ConstElement(list.front());
- }
-
- inline ConstElement back() const {
- return ConstElement(list.back());
- }
-
- inline bool is_empty() const { return list.is_empty(); }
- inline int size() const { return list.size(); }
-
- const void *id() const {
- return list.id();
- }
-
- void clear() {
- map.clear();
- list.clear();
- }
-
-private:
- void _copy_from(const OrderedHashMap &p_map) {
- for (ConstElement E = p_map.front(); E; E = E.next()) {
- insert(E.key(), E.value());
- }
- }
-
-public:
- void operator=(const OrderedHashMap &p_map) {
- _copy_from(p_map);
- }
-
- OrderedHashMap(const OrderedHashMap &p_map) {
- _copy_from(p_map);
- }
-
- _FORCE_INLINE_ OrderedHashMap() {}
-};
-
-#endif // ORDERED_HASH_MAP_H
diff --git a/core/templates/paged_allocator.h b/core/templates/paged_allocator.h
index b9067e2edd..cf5911a847 100644
--- a/core/templates/paged_allocator.h
+++ b/core/templates/paged_allocator.h
@@ -50,6 +50,10 @@ class PagedAllocator {
SpinLock spin_lock;
public:
+ enum {
+ DEFAULT_PAGE_SIZE = 4096
+ };
+
template <class... Args>
T *alloc(const Args &&...p_args) {
if (thread_safe) {
@@ -121,7 +125,9 @@ public:
page_shift = get_shift_from_power_of_2(page_size);
}
- PagedAllocator(uint32_t p_page_size = 4096) { // power of 2 recommended because of alignment with OS page sizes. Even if element is bigger, its still a multiple and get rounded amount of pages
+ // Power of 2 recommended because of alignment with OS page sizes.
+ // Even if element is bigger, it's still a multiple and gets rounded to amount of pages.
+ PagedAllocator(uint32_t p_page_size = DEFAULT_PAGE_SIZE) {
configure(p_page_size);
}
diff --git a/core/templates/pair.h b/core/templates/pair.h
index eb86e21b03..6d33213fe3 100644
--- a/core/templates/pair.h
+++ b/core/templates/pair.h
@@ -31,8 +31,8 @@
#ifndef PAIR_H
#define PAIR_H
+#include "core/templates/hashfuncs.h"
#include "core/typedefs.h"
-
template <class F, class S>
struct Pair {
F first;
@@ -69,6 +69,15 @@ struct PairSort {
}
};
+template <class F, class S>
+struct PairHash {
+ static uint32_t hash(const Pair<F, S> &P) {
+ uint64_t h1 = HashMapHasherDefault::hash(P.first);
+ uint64_t h2 = HashMapHasherDefault::hash(P.second);
+ return hash_one_uint64((h1 << 32) | h2);
+ }
+};
+
template <class K, class V>
struct KeyValue {
const K key;
diff --git a/core/templates/map.h b/core/templates/rb_map.h
index c54da1dc03..c732ccd485 100644
--- a/core/templates/map.h
+++ b/core/templates/rb_map.h
@@ -1,5 +1,5 @@
/*************************************************************************/
-/* map.h */
+/* rb_map.h */
/*************************************************************************/
/* This file is part of: */
/* GODOT ENGINE */
@@ -28,8 +28,8 @@
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
/*************************************************************************/
-#ifndef MAP_H
-#define MAP_H
+#ifndef RB_MAP_H
+#define RB_MAP_H
#include "core/error/error_macros.h"
#include "core/os/memory.h"
@@ -39,7 +39,7 @@
// https://web.archive.org/web/20120507164830/https://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
template <class K, class V, class C = Comparator<K>, class A = DefaultAllocator>
-class Map {
+class RBMap {
enum Color {
RED,
BLACK
@@ -49,7 +49,7 @@ class Map {
public:
class Element {
private:
- friend class Map<K, V, C, A>;
+ friend class RBMap<K, V, C, A>;
int color = RED;
Element *right = nullptr;
Element *left = nullptr;
@@ -111,7 +111,9 @@ public:
_FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; }
_FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
-
+ explicit operator bool() const {
+ return E != nullptr;
+ }
Iterator(Element *p_E) { E = p_E; }
Iterator() {}
Iterator(const Iterator &p_it) { E = p_it.E; }
@@ -136,7 +138,9 @@ public:
_FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; }
_FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; }
-
+ explicit operator bool() const {
+ return E != nullptr;
+ }
ConstIterator(const Element *p_E) { E = p_E; }
ConstIterator() {}
ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
@@ -572,7 +576,7 @@ private:
memdelete_allocator<Element, A>(p_element);
}
- void _copy_from(const Map &p_map) {
+ void _copy_from(const RBMap &p_map) {
clear();
// not the fastest way, but safeset to write.
for (Element *I = p_map.front(); I; I = I->next()) {
@@ -710,8 +714,12 @@ public:
return e;
}
- inline bool is_empty() const { return _data.size_cache == 0; }
- inline int size() const { return _data.size_cache; }
+ inline bool is_empty() const {
+ return _data.size_cache == 0;
+ }
+ inline int size() const {
+ return _data.size_cache;
+ }
int calculate_depth() const {
// used for debug mostly
@@ -735,17 +743,17 @@ public:
_data._free_root();
}
- void operator=(const Map &p_map) {
+ void operator=(const RBMap &p_map) {
_copy_from(p_map);
}
- Map(const Map &p_map) {
+ RBMap(const RBMap &p_map) {
_copy_from(p_map);
}
- _FORCE_INLINE_ Map() {}
+ _FORCE_INLINE_ RBMap() {}
- ~Map() {
+ ~RBMap() {
clear();
}
};
diff --git a/core/templates/set.h b/core/templates/rb_set.h
index a8a0a77712..226ea979c9 100644
--- a/core/templates/set.h
+++ b/core/templates/rb_set.h
@@ -1,5 +1,5 @@
/*************************************************************************/
-/* set.h */
+/* rb_set.h */
/*************************************************************************/
/* This file is part of: */
/* GODOT ENGINE */
@@ -28,8 +28,8 @@
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
/*************************************************************************/
-#ifndef SET_H
-#define SET_H
+#ifndef RB_SET_H
+#define RB_SET_H
#include "core/os/memory.h"
#include "core/typedefs.h"
@@ -38,7 +38,7 @@
// https://web.archive.org/web/20120507164830/https://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
template <class T, class C = Comparator<T>, class A = DefaultAllocator>
-class Set {
+class RBSet {
enum Color {
RED,
BLACK
@@ -48,7 +48,7 @@ class Set {
public:
class Element {
private:
- friend class Set<T, C, A>;
+ friend class RBSet<T, C, A>;
int color = RED;
Element *right = nullptr;
Element *left = nullptr;
@@ -99,6 +99,7 @@ public:
_FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; }
_FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
+ explicit operator bool() const { return E != nullptr; }
Iterator(Element *p_E) { E = p_E; }
Iterator() {}
Iterator(const Iterator &p_it) { E = p_it.E; }
@@ -128,6 +129,8 @@ public:
_FORCE_INLINE_ ConstIterator() {}
_FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
+ explicit operator bool() const { return E != nullptr; }
+
private:
const Element *E = nullptr;
};
@@ -554,7 +557,7 @@ private:
memdelete_allocator<Element, A>(p_element);
}
- void _copy_from(const Set &p_set) {
+ void _copy_from(const RBSet &p_set) {
clear();
// not the fastest way, but safeset to write.
for (Element *I = p_set.front(); I; I = I->next()) {
@@ -661,8 +664,12 @@ public:
return e;
}
- inline bool is_empty() const { return _data.size_cache == 0; }
- inline int size() const { return _data.size_cache; }
+ inline bool is_empty() const {
+ return _data.size_cache == 0;
+ }
+ inline int size() const {
+ return _data.size_cache;
+ }
int calculate_depth() const {
// used for debug mostly
@@ -686,17 +693,17 @@ public:
_data._free_root();
}
- void operator=(const Set &p_set) {
+ void operator=(const RBSet &p_set) {
_copy_from(p_set);
}
- Set(const Set &p_set) {
+ RBSet(const RBSet &p_set) {
_copy_from(p_set);
}
- _FORCE_INLINE_ Set() {}
+ _FORCE_INLINE_ RBSet() {}
- ~Set() {
+ ~RBSet() {
clear();
}
};
diff --git a/core/templates/rid_owner.h b/core/templates/rid_owner.h
index 95632cdec2..9c74b41818 100644
--- a/core/templates/rid_owner.h
+++ b/core/templates/rid_owner.h
@@ -34,11 +34,11 @@
#include "core/os/memory.h"
#include "core/os/spin_lock.h"
#include "core/string/print_string.h"
+#include "core/templates/hash_set.h"
#include "core/templates/list.h"
#include "core/templates/oa_hash_map.h"
#include "core/templates/rid.h"
#include "core/templates/safe_refcount.h"
-#include "core/templates/set.h"
#include <stdio.h>
#include <typeinfo>
diff --git a/core/templates/vector.h b/core/templates/vector.h
index d87e76139b..2ac7c7630a 100644
--- a/core/templates/vector.h
+++ b/core/templates/vector.h
@@ -92,6 +92,8 @@ public:
_FORCE_INLINE_ const T &operator[](int p_index) const { return _cowdata.get(p_index); }
Error insert(int p_pos, T p_val) { return _cowdata.insert(p_pos, p_val); }
int find(const T &p_val, int p_from = 0) const { return _cowdata.find(p_val, p_from); }
+ int rfind(const T &p_val, int p_from = -1) const { return _cowdata.rfind(p_val, p_from); }
+ int count(const T &p_val) const { return _cowdata.count(p_val); }
void append_array(Vector<T> p_other);
generated by cgit v1.2.3 (git 2.25.1) at 2025-02-26 21:47:41 +0000