summaryrefslogtreecommitdiff
path: root/core/templates
diff options
context:
space:
mode:
Diffstat (limited to 'core/templates')
-rw-r--r--core/templates/command_queue_mt.h10
-rw-r--r--core/templates/cowdata.h57
-rw-r--r--core/templates/hash_map.h779
-rw-r--r--core/templates/hashfuncs.h118
-rw-r--r--core/templates/oa_hash_map.h20
-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)42
-rw-r--r--core/templates/rb_set.h (renamed from core/templates/set.h)32
-rw-r--r--core/templates/rid_owner.h2
-rw-r--r--core/templates/safe_list.h38
-rw-r--r--core/templates/self_list.h2
-rw-r--r--core/templates/thread_work_pool.h4
-rw-r--r--core/templates/vector.h2
15 files changed, 675 insertions, 751 deletions
diff --git a/core/templates/command_queue_mt.h b/core/templates/command_queue_mt.h
index 1ecb81c2a2..7d3e31b5bc 100644
--- a/core/templates/command_queue_mt.h
+++ b/core/templates/command_queue_mt.h
@@ -215,7 +215,7 @@
T *instance; \
M method; \
SEMIC_SEP_LIST(PARAM_DECL, N); \
- virtual void call() { \
+ virtual void call() override { \
(instance->*method)(COMMA_SEP_LIST(ARG, N)); \
} \
};
@@ -227,7 +227,7 @@
T *instance; \
M method; \
SEMIC_SEP_LIST(PARAM_DECL, N); \
- virtual void call() { \
+ virtual void call() override { \
*ret = (instance->*method)(COMMA_SEP_LIST(ARG, N)); \
} \
};
@@ -238,7 +238,7 @@
T *instance; \
M method; \
SEMIC_SEP_LIST(PARAM_DECL, N); \
- virtual void call() { \
+ virtual void call() override { \
(instance->*method)(COMMA_SEP_LIST(ARG, N)); \
} \
};
@@ -311,9 +311,9 @@ class CommandQueueMT {
};
struct SyncCommand : public CommandBase {
- SyncSemaphore *sync_sem;
+ SyncSemaphore *sync_sem = nullptr;
- virtual void post() {
+ virtual void post() override {
sync_sem->sem.post();
}
};
diff --git a/core/templates/cowdata.h b/core/templates/cowdata.h
index 326616b607..e760fc2176 100644
--- a/core/templates/cowdata.h
+++ b/core/templates/cowdata.h
@@ -86,13 +86,6 @@ private:
return reinterpret_cast<uint32_t *>(_ptr) - 1;
}
- _FORCE_INLINE_ T *_get_data() const {
- if (!_ptr) {
- return nullptr;
- }
- return reinterpret_cast<T *>(_ptr);
- }
-
_FORCE_INLINE_ size_t _get_alloc_size(size_t p_elements) const {
return next_power_of_2(p_elements * sizeof(T));
}
@@ -128,11 +121,11 @@ public:
_FORCE_INLINE_ T *ptrw() {
_copy_on_write();
- return (T *)_get_data();
+ return _ptr;
}
_FORCE_INLINE_ const T *ptr() const {
- return _get_data();
+ return _ptr;
}
_FORCE_INLINE_ int size() const {
@@ -150,19 +143,19 @@ public:
_FORCE_INLINE_ void set(int p_index, const T &p_elem) {
ERR_FAIL_INDEX(p_index, size());
_copy_on_write();
- _get_data()[p_index] = p_elem;
+ _ptr[p_index] = p_elem;
}
_FORCE_INLINE_ T &get_m(int p_index) {
CRASH_BAD_INDEX(p_index, size());
_copy_on_write();
- return _get_data()[p_index];
+ return _ptr[p_index];
}
_FORCE_INLINE_ const T &get(int p_index) const {
CRASH_BAD_INDEX(p_index, size());
- return _get_data()[p_index];
+ return _ptr[p_index];
}
Error resize(int p_size);
@@ -190,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();
@@ -249,7 +244,7 @@ uint32_t CowData<T>::_copy_on_write() {
} else {
for (uint32_t i = 0; i < current_size; i++) {
- memnew_placement(&_data[i], T(_get_data()[i]));
+ memnew_placement(&_data[i], T(_ptr[i]));
}
}
@@ -308,10 +303,8 @@ Error CowData<T>::resize(int p_size) {
// construct the newly created elements
if (!__has_trivial_constructor(T)) {
- T *elems = _get_data();
-
for (int i = *_get_size(); i < p_size; i++) {
- memnew_placement(&elems[i], T);
+ memnew_placement(&_ptr[i], T);
}
}
@@ -321,7 +314,7 @@ Error CowData<T>::resize(int p_size) {
if (!__has_trivial_destructor(T)) {
// deinitialize no longer needed elements
for (uint32_t i = p_size; i < *_get_size(); i++) {
- T *t = &_get_data()[i];
+ T *t = &_ptr[i];
t->~T();
}
}
@@ -359,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/hashfuncs.h b/core/templates/hashfuncs.h
index 2a129f97d5..1330d55270 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
*/
@@ -155,6 +163,9 @@ static inline uint64_t make_uint64_t(T p_in) {
return _u._u64;
}
+template <class T>
+class Ref;
+
struct HashMapHasherDefault {
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); }
@@ -178,6 +189,55 @@ struct HashMapHasherDefault {
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(); }
+ 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 Vector2i &p_vec) {
+ uint32_t h = hash_djb2_one_32(p_vec.x);
+ return hash_djb2_one_32(p_vec.y, h);
+ }
+ static _FORCE_INLINE_ uint32_t hash(const Vector3i &p_vec) {
+ uint32_t h = hash_djb2_one_32(p_vec.x);
+ h = hash_djb2_one_32(p_vec.y, h);
+ return hash_djb2_one_32(p_vec.z, h);
+ }
+
+ static _FORCE_INLINE_ uint32_t hash(const Vector2 &p_vec) {
+ uint32_t h = hash_djb2_one_float(p_vec.x);
+ return hash_djb2_one_float(p_vec.y, h);
+ }
+ static _FORCE_INLINE_ uint32_t hash(const Vector3 &p_vec) {
+ uint32_t h = hash_djb2_one_float(p_vec.x);
+ h = hash_djb2_one_float(p_vec.y, h);
+ return hash_djb2_one_float(p_vec.z, h);
+ }
+
+ static _FORCE_INLINE_ uint32_t hash(const Rect2i &p_rect) {
+ uint32_t h = hash_djb2_one_32(p_rect.position.x);
+ h = hash_djb2_one_32(p_rect.position.y, h);
+ h = hash_djb2_one_32(p_rect.size.x, h);
+ return hash_djb2_one_32(p_rect.size.y, h);
+ }
+
+ static _FORCE_INLINE_ uint32_t hash(const Rect2 &p_rect) {
+ uint32_t h = hash_djb2_one_float(p_rect.position.x);
+ h = hash_djb2_one_float(p_rect.position.y, h);
+ h = hash_djb2_one_float(p_rect.size.x, h);
+ return hash_djb2_one_float(p_rect.size.y, h);
+ }
+
+ static _FORCE_INLINE_ uint32_t hash(const AABB &p_aabb) {
+ uint32_t h = hash_djb2_one_float(p_aabb.position.x);
+ h = hash_djb2_one_float(p_aabb.position.y, h);
+ h = hash_djb2_one_float(p_aabb.position.z, h);
+ h = hash_djb2_one_float(p_aabb.size.x, h);
+ h = hash_djb2_one_float(p_aabb.size.y, h);
+ return hash_djb2_one_float(p_aabb.size.z, h);
+ }
+
//static _FORCE_INLINE_ uint32_t hash(const void* p_ptr) { return uint32_t(uint64_t(p_ptr))*(0x9e3779b1L); }
};
@@ -186,14 +246,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/oa_hash_map.h b/core/templates/oa_hash_map.h
index 4e712fccf2..25c21d1802 100644
--- a/core/templates/oa_hash_map.h
+++ b/core/templates/oa_hash_map.h
@@ -246,13 +246,17 @@ public:
return false;
}
- /**
- * returns true if the value was found, false otherwise.
- *
- * if r_data is not nullptr then the value will be written to the object
- * it points to.
- */
- TValue *lookup_ptr(const TKey &p_key) const {
+ const TValue *lookup_ptr(const TKey &p_key) const {
+ uint32_t pos = 0;
+ bool exists = _lookup_pos(p_key, pos);
+
+ if (exists) {
+ return &values[pos];
+ }
+ return nullptr;
+ }
+
+ TValue *lookup_ptr(const TKey &p_key) {
uint32_t pos = 0;
bool exists = _lookup_pos(p_key, pos);
@@ -306,7 +310,7 @@ public:
bool valid;
const TKey *key;
- TValue *value;
+ TValue *value = nullptr;
private:
uint32_t pos;
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 f228640a1e..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; }
@@ -178,7 +182,7 @@ public:
private:
struct _Data {
Element *_root = nullptr;
- Element *_nil;
+ Element *_nil = nullptr;
int size_cache = 0;
_FORCE_INLINE_ _Data() {
@@ -344,7 +348,7 @@ private:
void _insert_rb_fix(Element *p_new_node) {
Element *node = p_new_node;
Element *nparent = node->parent;
- Element *ngrand_parent;
+ Element *ngrand_parent = nullptr;
while (nparent->color == RED) {
ngrand_parent = nparent->parent;
@@ -500,7 +504,7 @@ private:
Element *rp = ((p_node->left == _data._nil) || (p_node->right == _data._nil)) ? p_node : p_node->_next;
Element *node = (rp->left == _data._nil) ? rp->right : rp->left;
- Element *sibling;
+ Element *sibling = nullptr;
if (rp == rp->parent->left) {
rp->parent->left = node;
sibling = rp->parent->right;
@@ -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 cdc6e8447d..2de816769c 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;
@@ -328,7 +328,7 @@ private:
void _insert_rb_fix(Element *p_new_node) {
Element *node = p_new_node;
Element *nparent = node->parent;
- Element *ngrand_parent;
+ Element *ngrand_parent = nullptr;
while (nparent->color == RED) {
ngrand_parent = nparent->parent;
@@ -482,7 +482,7 @@ private:
Element *rp = ((p_node->left == _data._nil) || (p_node->right == _data._nil)) ? p_node : p_node->_next;
Element *node = (rp->left == _data._nil) ? rp->right : rp->left;
- Element *sibling;
+ Element *sibling = nullptr;
if (rp == rp->parent->left) {
rp->parent->left = node;
sibling = rp->parent->right;
@@ -554,7 +554,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 +661,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 +690,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..d26977380e 100644
--- a/core/templates/rid_owner.h
+++ b/core/templates/rid_owner.h
@@ -36,9 +36,9 @@
#include "core/string/print_string.h"
#include "core/templates/list.h"
#include "core/templates/oa_hash_map.h"
+#include "core/templates/rb_set.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/safe_list.h b/core/templates/safe_list.h
index 53fc3fe5f9..e850f3bd5e 100644
--- a/core/templates/safe_list.h
+++ b/core/templates/safe_list.h
@@ -75,8 +75,8 @@ public:
class Iterator {
friend class SafeList;
- SafeListNode *cursor;
- SafeList *list;
+ SafeListNode *cursor = nullptr;
+ SafeList *list = nullptr;
Iterator(SafeListNode *p_cursor, SafeList *p_list) :
cursor(p_cursor), list(p_list) {
@@ -203,7 +203,7 @@ public:
}
// Calling this will cause zero to many deallocations.
- void maybe_cleanup() {
+ bool maybe_cleanup() {
SafeListNode *cursor = nullptr;
SafeListNode *new_graveyard_head = nullptr;
do {
@@ -212,7 +212,7 @@ public:
if (active_iterator_count.load() != 0) {
// It's not safe to clean up with an active iterator, because that iterator
// could be pointing to an element that we want to delete.
- return;
+ return false;
}
// Any iterator created after this point will never point to a deleted node.
// Swap it out with the current graveyard head.
@@ -225,6 +225,17 @@ public:
tmp->deletion_fn(tmp->val);
memdelete_allocator<SafeListNode, A>(tmp);
}
+ return true;
+ }
+
+ ~SafeList() {
+#ifdef DEBUG_ENABLED
+ if (!maybe_cleanup()) {
+ ERR_PRINT("There are still iterators around when destructing a SafeList. Memory will be leaked. This is a bug.");
+ }
+#else
+ maybe_cleanup();
+#endif
}
};
@@ -253,8 +264,8 @@ public:
class Iterator {
friend class SafeList;
- SafeListNode *cursor;
- SafeList *list;
+ SafeListNode *cursor = nullptr;
+ SafeList *list = nullptr;
public:
Iterator(SafeListNode *p_cursor, SafeList *p_list) :
@@ -353,11 +364,11 @@ public:
}
// Calling this will cause zero to many deallocations.
- void maybe_cleanup() {
+ bool maybe_cleanup() {
SafeListNode *cursor = graveyard_head;
if (active_iterator_count != 0) {
// It's not safe to clean up with an active iterator, because that iterator could be pointing to an element that we want to delete.
- return;
+ return false;
}
graveyard_head = nullptr;
// Our graveyard list is now unreachable by any active iterators, detached from the main graveyard head and ready for deletion.
@@ -367,6 +378,17 @@ public:
tmp->deletion_fn(tmp->val);
memdelete_allocator<SafeListNode, A>(tmp);
}
+ return true;
+ }
+
+ ~SafeList() {
+#ifdef DEBUG_ENABLED
+ if (!maybe_cleanup()) {
+ ERR_PRINT("There are still iterators around when destructing a SafeList. Memory will be leaked. This is a bug.");
+ }
+#else
+ maybe_cleanup();
+#endif
}
};
diff --git a/core/templates/self_list.h b/core/templates/self_list.h
index 7f2236fa3a..719b5f2e63 100644
--- a/core/templates/self_list.h
+++ b/core/templates/self_list.h
@@ -108,7 +108,7 @@ public:
private:
List *_root = nullptr;
- T *_self;
+ T *_self = nullptr;
SelfList<T> *_next = nullptr;
SelfList<T> *_prev = nullptr;
diff --git a/core/templates/thread_work_pool.h b/core/templates/thread_work_pool.h
index 957af44f48..b0cebf04f1 100644
--- a/core/templates/thread_work_pool.h
+++ b/core/templates/thread_work_pool.h
@@ -52,7 +52,7 @@ class ThreadWorkPool {
C *instance;
M method;
U userdata;
- virtual void work() {
+ virtual void work() override {
while (true) {
uint32_t work_index = index->fetch_add(1, std::memory_order_relaxed);
if (work_index >= max_elements) {
@@ -68,7 +68,7 @@ class ThreadWorkPool {
Semaphore start;
Semaphore completed;
std::atomic<bool> exit;
- BaseWork *work;
+ BaseWork *work = nullptr;
};
ThreadData *threads = nullptr;
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-03-21 22:01:46 +0000