From e3119e7d059d527d458ac6d2aef1e194beb746b4 Mon Sep 17 00:00:00 2001 From: bruvzg <7645683+bruvzg@users.noreply.github.com> Date: Mon, 6 Jun 2022 12:18:07 +0300 Subject: Sync containers with new HashMap/HashSet, sync API headers. --- include/godot_cpp/core/memory.hpp | 8 + include/godot_cpp/templates/hash_map.hpp | 780 ++++++++++++++++-------------- include/godot_cpp/templates/hash_set.hpp | 477 ++++++++++++++++++ include/godot_cpp/templates/hashfuncs.hpp | 131 ++++- include/godot_cpp/templates/map.hpp | 757 ----------------------------- include/godot_cpp/templates/rb_map.hpp | 765 +++++++++++++++++++++++++++++ include/godot_cpp/templates/rb_set.hpp | 714 +++++++++++++++++++++++++++ include/godot_cpp/templates/set.hpp | 707 --------------------------- include/godot_cpp/variant/variant.hpp | 20 +- 9 files changed, 2514 insertions(+), 1845 deletions(-) create mode 100644 include/godot_cpp/templates/hash_set.hpp delete mode 100644 include/godot_cpp/templates/map.hpp create mode 100644 include/godot_cpp/templates/rb_map.hpp create mode 100644 include/godot_cpp/templates/rb_set.hpp delete mode 100644 include/godot_cpp/templates/set.hpp (limited to 'include/godot_cpp') diff --git a/include/godot_cpp/core/memory.hpp b/include/godot_cpp/core/memory.hpp index 5848fbd..35b551c 100644 --- a/include/godot_cpp/core/memory.hpp +++ b/include/godot_cpp/core/memory.hpp @@ -98,6 +98,14 @@ public: _ALWAYS_INLINE_ static void free(void *p_ptr) { Memory::free_static(p_ptr); } }; +template +class DefaultTypedAllocator { +public: + template + _ALWAYS_INLINE_ T *new_allocation(const Args &&...p_args) { return memnew(T(p_args...)); } + _ALWAYS_INLINE_ void delete_allocation(T *p_allocation) { memdelete(p_allocation); } +}; + template void memdelete(T *p_class, typename std::enable_if>::type * = 0) { if (!__has_trivial_destructor(T)) { diff --git a/include/godot_cpp/templates/hash_map.hpp b/include/godot_cpp/templates/hash_map.hpp index 8243cb5..1e66b7d 100644 --- a/include/godot_cpp/templates/hash_map.hpp +++ b/include/godot_cpp/templates/hash_map.hpp @@ -34,524 +34,558 @@ #include #include #include -#include +#include + +namespace godot { /** - * @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. */ -namespace godot { +template +struct HashMapElement { + HashMapElement *next = nullptr; + HashMapElement *prev = nullptr; + KeyValue data; + HashMapElement() {} + HashMapElement(const TKey &p_key, const TValue &p_value) : + data(p_key, p_value) {} +}; -template , uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8> +template , + class Allocator = DefaultTypedAllocator>> 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 **elements = nullptr; + uint32_t *hashes = nullptr; + HashMapElement *head_element = nullptr; + HashMapElement *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 *p_value) { + uint32_t capacity = hash_table_size_primes[capacity_index]; + uint32_t hash = p_hash; + HashMapElement *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 **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(Memory::alloc_static(sizeof(uint32_t) * capacity)); + elements = reinterpret_cast **>(Memory::alloc_static(sizeof(HashMapElement *) * 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; - } - - 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++; - - return e; + Memory::free_static(old_elements); + Memory::free_static(old_hashes); } - void copy_from(const HashMap &p_t) { - if (&p_t == this) { - return; /* much less bother with that */ - } + _FORCE_INLINE_ HashMapElement *_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. - clear(); + hashes = reinterpret_cast(Memory::alloc_static(sizeof(uint32_t) * capacity)); + elements = reinterpret_cast **>(Memory::alloc_static(sizeof(HashMapElement *) * capacity)); - 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; - - for (int i = 0; i < (1 << p_t.hash_table_power); i++) { - hash_table[i] = nullptr; - - const Element *e = p_t.hash_table[i]; + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); - 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 *elem = element_alloc.new_allocation(HashMapElement(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(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(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(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 - _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 - _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; + } + + if (elements == nullptr) { + capacity_index = new_index; + return; // Unallocated yet. + } + _resize_and_rehash(new_index); + } - const Element *e = hash_table[index]; + /** Iterator API **/ - 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; + struct ConstIterator { + _FORCE_INLINE_ const KeyValue &operator*() const { + return E->data; + } + _FORCE_INLINE_ const KeyValue *operator->() const { return &E->data; } + _FORCE_INLINE_ ConstIterator &operator++() { + if (E) { + E = E->next; } - - 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 *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 *E = nullptr; + }; + + struct Iterator { + _FORCE_INLINE_ KeyValue &operator*() const { + return E->data; + } + _FORCE_INLINE_ KeyValue *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; + } + + _FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; } + _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; } - p = e; - e = e->next; + _FORCE_INLINE_ explicit operator bool() const { + return E != nullptr; } - return false; - } + _FORCE_INLINE_ Iterator(HashMapElement *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; + } - inline const TData &operator[](const TKey &p_key) const { // constref + operator ConstIterator() const { + return ConstIterator(E); + } - return get(p_key); + private: + HashMapElement *E = nullptr; + }; + + _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(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 &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 *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 &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); + } } }; } // namespace godot -#endif // ! HASH_MAP_HPP +#endif // HASH_MAP_HPP diff --git a/include/godot_cpp/templates/hash_set.hpp b/include/godot_cpp/templates/hash_set.hpp new file mode 100644 index 0000000..dc83a2a --- /dev/null +++ b/include/godot_cpp/templates/hash_set.hpp @@ -0,0 +1,477 @@ +/*************************************************************************/ +/* hash_set.hpp */ +/*************************************************************************/ +/* 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_HPP +#define HASH_SET_HPP + +#include +#include +#include +#include +#include + +namespace godot { + +/** + * 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 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(Memory::alloc_static(sizeof(uint32_t) * capacity)); + keys = reinterpret_cast(Memory::realloc_static(keys, sizeof(TKey) * capacity)); + key_to_hash = reinterpret_cast(Memory::alloc_static(sizeof(uint32_t) * capacity)); + hash_to_key = reinterpret_cast(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(Memory::alloc_static(sizeof(uint32_t) * capacity)); + keys = reinterpret_cast(Memory::alloc_static(sizeof(TKey) * capacity)); + key_to_hash = reinterpret_cast(Memory::alloc_static(sizeof(uint32_t) * capacity)); + hash_to_key = reinterpret_cast(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(Memory::alloc_static(sizeof(uint32_t) * capacity)); + keys = reinterpret_cast(Memory::alloc_static(sizeof(TKey) * capacity)); + key_to_hash = reinterpret_cast(Memory::alloc_static(sizeof(uint32_t) * capacity)); + hash_to_key = reinterpret_cast(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); + } + } +}; + +} // namespace godot + +#endif // HASH_SET_HPP diff --git a/include/godot_cpp/templates/hashfuncs.hpp b/include/godot_cpp/templates/hashfuncs.hpp index 885e4ba..a308d0a 100644 --- a/include/godot_cpp/templates/hashfuncs.hpp +++ b/include/godot_cpp/templates/hashfuncs.hpp @@ -32,7 +32,19 @@ #define HASHFUNCS_HPP #include +#include +#include +#include +#include +#include #include +#include +#include +#include +#include +#include +#include +#include /** * Hashing functions @@ -152,9 +164,14 @@ static inline uint64_t make_uint64_t(T p_in) { return _u._u64; } +template +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); } 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); } @@ -169,6 +186,60 @@ struct HashMapHasherDefault { 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 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(); } + + template + static _FORCE_INLINE_ uint32_t hash(const T *p_pointer) { return hash_one_uint64((uint64_t)p_pointer); } + + template + static _FORCE_INLINE_ uint32_t hash(const Ref &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); } }; template @@ -176,16 +247,70 @@ 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 { + static bool compare(const float &p_lhs, const float &p_rhs) { return (p_lhs == p_rhs) || (std::isnan(p_lhs) && std::isnan(p_rhs)); } +}; - bool compare(const double &p_lhs, const double &p_rhs) { +template <> +struct HashMapComparatorDefault { + static bool compare(const double &p_lhs, const double &p_rhs) { return (p_lhs == p_rhs) || (std::isnan(p_lhs) && std::isnan(p_rhs)); } }; +template <> +struct HashMapComparatorDefault { + static bool compare(const Vector2 &p_lhs, const Vector2 &p_rhs) { + return ((p_lhs.x == p_rhs.x) || (std::isnan(p_lhs.x) && std::isnan(p_rhs.x))) && ((p_lhs.y == p_rhs.y) || (std::isnan(p_lhs.y) && std::isnan(p_rhs.y))); + } +}; + +template <> +struct HashMapComparatorDefault { + static bool compare(const Vector3 &p_lhs, const Vector3 &p_rhs) { + return ((p_lhs.x == p_rhs.x) || (std::isnan(p_lhs.x) && std::isnan(p_rhs.x))) && ((p_lhs.y == p_rhs.y) || (std::isnan(p_lhs.y) && std::isnan(p_rhs.y))) && ((p_lhs.z == p_rhs.z) || (std::isnan(p_lhs.z) && std::isnan(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, +}; + } // namespace godot -#endif // ! HASHFUNCS_HPP +#endif // HASHFUNCS_HPP diff --git a/include/godot_cpp/templates/map.hpp b/include/godot_cpp/templates/map.hpp deleted file mode 100644 index 21b8899..0000000 --- a/include/godot_cpp/templates/map.hpp +++ /dev/null @@ -1,757 +0,0 @@ -/*************************************************************************/ -/* map.hpp */ -/*************************************************************************/ -/* 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 MAP_HPP -#define MAP_HPP - -#include -#include -#include - -namespace godot { - -// based on the very nice implementation of rb-trees by: -// https://web.archive.org/web/20120507164830/https://web.mit.edu/~emin/www/source_code/red_black_tree/index.html - -template , class A = DefaultAllocator> -class Map { - enum Color { - RED, - BLACK - }; - struct _Data; - -public: - class Element { - private: - friend class Map; - int color = RED; - Element *right = nullptr; - Element *left = nullptr; - Element *parent = nullptr; - Element *_next = nullptr; - Element *_prev = nullptr; - KeyValue _data; - - public: - KeyValue &key_value() { return _data; } - const KeyValue &key_value() const { return _data; } - - const Element *next() const { - return _next; - } - Element *next() { - return _next; - } - const Element *prev() const { - return _prev; - } - Element *prev() { - return _prev; - } - const K &key() const { - return _data.key; - } - V &value() { - return _data.value; - } - const V &value() const { - return _data.value; - } - V &get() { - return _data.value; - } - const V &get() const { - return _data.value; - } - Element(const KeyValue &p_data) : - _data(p_data) {} - }; - - typedef KeyValue ValueType; - - struct Iterator { - _FORCE_INLINE_ KeyValue &operator*() const { - return E->key_value(); - } - _FORCE_INLINE_ KeyValue *operator->() const { return &E->key_value(); } - _FORCE_INLINE_ Iterator &operator++() { - E = E->next(); - return *this; - } - _FORCE_INLINE_ Iterator &operator--() { - E = E->prev(); - return *this; - } - - _FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; } - _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; } - - Iterator(Element *p_E) { E = p_E; } - Iterator() {} - Iterator(const Iterator &p_it) { E = p_it.E; } - - private: - Element *E = nullptr; - }; - - struct ConstIterator { - _FORCE_INLINE_ const KeyValue &operator*() const { - return E->key_value(); - } - _FORCE_INLINE_ const KeyValue *operator->() const { return &E->key_value(); } - _FORCE_INLINE_ ConstIterator &operator++() { - E = E->next(); - return *this; - } - _FORCE_INLINE_ ConstIterator &operator--() { - E = E->prev(); - return *this; - } - - _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; } - _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; } - - ConstIterator(const Element *p_E) { E = p_E; } - ConstIterator() {} - ConstIterator(const ConstIterator &p_it) { E = p_it.E; } - - private: - const Element *E = nullptr; - }; - - _FORCE_INLINE_ Iterator begin() { - return Iterator(front()); - } - _FORCE_INLINE_ Iterator end() { - return Iterator(nullptr); - } - -#if 0 - //to use when replacing find() - _FORCE_INLINE_ Iterator find(const K &p_key) { - return Iterator(find(p_key)); - } -#endif - _FORCE_INLINE_ void remove(const Iterator &p_iter) { - return erase(p_iter.E); - } - - _FORCE_INLINE_ ConstIterator begin() const { - return ConstIterator(front()); - } - _FORCE_INLINE_ ConstIterator end() const { - return ConstIterator(nullptr); - } - -#if 0 - //to use when replacing find() - _FORCE_INLINE_ ConstIterator find(const K &p_key) const { - return ConstIterator(find(p_key)); - } -#endif -private: - struct _Data { - Element *_root = nullptr; - Element *_nil; - int size_cache = 0; - - _FORCE_INLINE_ _Data() { -#ifdef GLOBALNIL_DISABLED - _nil = memnew_allocator(Element, A); - _nil->parent = _nil->left = _nil->right = _nil; - _nil->color = BLACK; -#else - _nil = (Element *)&_GlobalNilClass::_nil; -#endif - } - - void _create_root() { - _root = memnew_allocator(Element(KeyValue(K(), V())), A); - _root->parent = _root->left = _root->right = _nil; - _root->color = BLACK; - } - - void _free_root() { - if (_root) { - memdelete_allocator(_root); - _root = nullptr; - } - } - - ~_Data() { - _free_root(); - -#ifdef GLOBALNIL_DISABLED - memdelete_allocator(_nil); -#endif - } - }; - - _Data _data; - - inline void _set_color(Element *p_node, int p_color) { - ERR_FAIL_COND(p_node == _data._nil && p_color == RED); - p_node->color = p_color; - } - - inline void _rotate_left(Element *p_node) { - Element *r = p_node->right; - p_node->right = r->left; - if (r->left != _data._nil) { - r->left->parent = p_node; - } - r->parent = p_node->parent; - if (p_node == p_node->parent->left) { - p_node->parent->left = r; - } else { - p_node->parent->right = r; - } - - r->left = p_node; - p_node->parent = r; - } - - inline void _rotate_right(Element *p_node) { - Element *l = p_node->left; - p_node->left = l->right; - if (l->right != _data._nil) { - l->right->parent = p_node; - } - l->parent = p_node->parent; - if (p_node == p_node->parent->right) { - p_node->parent->right = l; - } else { - p_node->parent->left = l; - } - - l->right = p_node; - p_node->parent = l; - } - - inline Element *_successor(Element *p_node) const { - Element *node = p_node; - - if (node->right != _data._nil) { - node = node->right; - while (node->left != _data._nil) { /* returns the minimum of the right subtree of node */ - node = node->left; - } - return node; - } else { - while (node == node->parent->right) { - node = node->parent; - } - - if (node->parent == _data._root) { - return nullptr; // No successor, as p_node = last node - } - return node->parent; - } - } - - inline Element *_predecessor(Element *p_node) const { - Element *node = p_node; - - if (node->left != _data._nil) { - node = node->left; - while (node->right != _data._nil) { /* returns the minimum of the left subtree of node */ - node = node->right; - } - return node; - } else { - while (node == node->parent->left) { - node = node->parent; - } - - if (node == _data._root) { - return nullptr; // No predecessor, as p_node = first node - } - return node->parent; - } - } - - Element *_find(const K &p_key) const { - Element *node = _data._root->left; - C less; - - while (node != _data._nil) { - if (less(p_key, node->_data.key)) { - node = node->left; - } else if (less(node->_data.key, p_key)) { - node = node->right; - } else { - return node; // found - } - } - - return nullptr; - } - - Element *_find_closest(const K &p_key) const { - Element *node = _data._root->left; - Element *prev = nullptr; - C less; - - while (node != _data._nil) { - prev = node; - - if (less(p_key, node->_data.key)) { - node = node->left; - } else if (less(node->_data.key, p_key)) { - node = node->right; - } else { - return node; // found - } - } - - if (prev == nullptr) { - return nullptr; // tree empty - } - - if (less(p_key, prev->_data.key)) { - prev = prev->_prev; - } - - return prev; - } - - void _insert_rb_fix(Element *p_new_node) { - Element *node = p_new_node; - Element *nparent = node->parent; - Element *ngrand_parent; - - while (nparent->color == RED) { - ngrand_parent = nparent->parent; - - if (nparent == ngrand_parent->left) { - if (ngrand_parent->right->color == RED) { - _set_color(nparent, BLACK); - _set_color(ngrand_parent->right, BLACK); - _set_color(ngrand_parent, RED); - node = ngrand_parent; - nparent = node->parent; - } else { - if (node == nparent->right) { - _rotate_left(nparent); - node = nparent; - nparent = node->parent; - } - _set_color(nparent, BLACK); - _set_color(ngrand_parent, RED); - _rotate_right(ngrand_parent); - } - } else { - if (ngrand_parent->left->color == RED) { - _set_color(nparent, BLACK); - _set_color(ngrand_parent->left, BLACK); - _set_color(ngrand_parent, RED); - node = ngrand_parent; - nparent = node->parent; - } else { - if (node == nparent->left) { - _rotate_right(nparent); - node = nparent; - nparent = node->parent; - } - _set_color(nparent, BLACK); - _set_color(ngrand_parent, RED); - _rotate_left(ngrand_parent); - } - } - } - - _set_color(_data._root->left, BLACK); - } - - Element *_insert(const K &p_key, const V &p_value) { - Element *new_parent = _data._root; - Element *node = _data._root->left; - C less; - - while (node != _data._nil) { - new_parent = node; - - if (less(p_key, node->_data.key)) { - node = node->left; - } else if (less(node->_data.key, p_key)) { - node = node->right; - } else { - node->_data.value = p_value; - return node; // Return existing node with new value - } - } - - typedef KeyValue KV; - Element *new_node = memnew_allocator(Element(KV(p_key, p_value)), A); - new_node->parent = new_parent; - new_node->right = _data._nil; - new_node->left = _data._nil; - - // new_node->data=_data; - - if (new_parent == _data._root || less(p_key, new_parent->_data.key)) { - new_parent->left = new_node; - } else { - new_parent->right = new_node; - } - - new_node->_next = _successor(new_node); - new_node->_prev = _predecessor(new_node); - if (new_node->_next) { - new_node->_next->_prev = new_node; - } - if (new_node->_prev) { - new_node->_prev->_next = new_node; - } - - _data.size_cache++; - _insert_rb_fix(new_node); - return new_node; - } - - void _erase_fix_rb(Element *p_node) { - Element *root = _data._root->left; - Element *node = _data._nil; - Element *sibling = p_node; - Element *parent = sibling->parent; - - while (node != root) { // If red node found, will exit at a break - if (sibling->color == RED) { - _set_color(sibling, BLACK); - _set_color(parent, RED); - if (sibling == parent->right) { - sibling = sibling->left; - _rotate_left(parent); - } else { - sibling = sibling->right; - _rotate_right(parent); - } - } - if ((sibling->left->color == BLACK) && (sibling->right->color == BLACK)) { - _set_color(sibling, RED); - if (parent->color == RED) { - _set_color(parent, BLACK); - break; - } else { // loop: haven't found any red nodes yet - node = parent; - parent = node->parent; - sibling = (node == parent->left) ? parent->right : parent->left; - } - } else { - if (sibling == parent->right) { - if (sibling->right->color == BLACK) { - _set_color(sibling->left, BLACK); - _set_color(sibling, RED); - _rotate_right(sibling); - sibling = sibling->parent; - } - _set_color(sibling, parent->color); - _set_color(parent, BLACK); - _set_color(sibling->right, BLACK); - _rotate_left(parent); - break; - } else { - if (sibling->left->color == BLACK) { - _set_color(sibling->right, BLACK); - _set_color(sibling, RED); - _rotate_left(sibling); - sibling = sibling->parent; - } - - _set_color(sibling, parent->color); - _set_color(parent, BLACK); - _set_color(sibling->left, BLACK); - _rotate_right(parent); - break; - } - } - } - - ERR_FAIL_COND(_data._nil->color != BLACK); - } - - void _erase(Element *p_node) { - 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; - if (rp == rp->parent->left) { - rp->parent->left = node; - sibling = rp->parent->right; - } else { - rp->parent->right = node; - sibling = rp->parent->left; - } - - if (node->color == RED) { - node->parent = rp->parent; - _set_color(node, BLACK); - } else if (rp->color == BLACK && rp->parent != _data._root) { - _erase_fix_rb(sibling); - } - - if (rp != p_node) { - ERR_FAIL_COND(rp == _data._nil); - - rp->left = p_node->left; - rp->right = p_node->right; - rp->parent = p_node->parent; - rp->color = p_node->color; - if (p_node->left != _data._nil) { - p_node->left->parent = rp; - } - if (p_node->right != _data._nil) { - p_node->right->parent = rp; - } - - if (p_node == p_node->parent->left) { - p_node->parent->left = rp; - } else { - p_node->parent->right = rp; - } - } - - if (p_node->_next) { - p_node->_next->_prev = p_node->_prev; - } - if (p_node->_prev) { - p_node->_prev->_next = p_node->_next; - } - - memdelete_allocator(p_node); - _data.size_cache--; - ERR_FAIL_COND(_data._nil->color == RED); - } - - void _calculate_depth(Element *p_element, int &max_d, int d) const { - if (p_element == _data._nil) { - return; - } - - _calculate_depth(p_element->left, max_d, d + 1); - _calculate_depth(p_element->right, max_d, d + 1); - - if (d > max_d) { - max_d = d; - } - } - - void _cleanup_tree(Element *p_element) { - if (p_element == _data._nil) { - return; - } - - _cleanup_tree(p_element->left); - _cleanup_tree(p_element->right); - memdelete_allocator(p_element); - } - - void _copy_from(const Map &p_map) { - clear(); - // not the fastest way, but safeset to write. - for (Element *I = p_map.front(); I; I = I->next()) { - insert(I->key(), I->value()); - } - } - -public: - const Element *find(const K &p_key) const { - if (!_data._root) { - return nullptr; - } - - const Element *res = _find(p_key); - return res; - } - - Element *find(const K &p_key) { - if (!_data._root) { - return nullptr; - } - - Element *res = _find(p_key); - return res; - } - - const Element *find_closest(const K &p_key) const { - if (!_data._root) { - return nullptr; - } - - const Element *res = _find_closest(p_key); - return res; - } - - Element *find_closest(const K &p_key) { - if (!_data._root) { - return nullptr; - } - - Element *res = _find_closest(p_key); - return res; - } - - bool has(const K &p_key) const { - return find(p_key) != nullptr; - } - - Element *insert(const K &p_key, const V &p_value) { - if (!_data._root) { - _data._create_root(); - } - return _insert(p_key, p_value); - } - - void erase(Element *p_element) { - if (!_data._root || !p_element) { - return; - } - - _erase(p_element); - if (_data.size_cache == 0 && _data._root) { - _data._free_root(); - } - } - - bool erase(const K &p_key) { - if (!_data._root) { - return false; - } - - Element *e = find(p_key); - if (!e) { - return false; - } - - _erase(e); - if (_data.size_cache == 0 && _data._root) { - _data._free_root(); - } - return true; - } - - const V &operator[](const K &p_key) const { - CRASH_COND(!_data._root); - const Element *e = find(p_key); - CRASH_COND(!e); - return e->_data.value; - } - - V &operator[](const K &p_key) { - if (!_data._root) { - _data._create_root(); - } - - Element *e = find(p_key); - if (!e) { - e = insert(p_key, V()); - } - - return e->_data.value; - } - - Element *front() const { - if (!_data._root) { - return nullptr; - } - - Element *e = _data._root->left; - if (e == _data._nil) { - return nullptr; - } - - while (e->left != _data._nil) { - e = e->left; - } - - return e; - } - - Element *back() const { - if (!_data._root) { - return nullptr; - } - - Element *e = _data._root->left; - if (e == _data._nil) { - return nullptr; - } - - while (e->right != _data._nil) { - e = e->right; - } - - return e; - } - - 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 - if (!_data._root) { - return 0; - } - - int max_d = 0; - _calculate_depth(_data._root->left, max_d, 0); - return max_d; - } - - void clear() { - if (!_data._root) { - return; - } - - _cleanup_tree(_data._root->left); - _data._root->left = _data._nil; - _data.size_cache = 0; - _data._free_root(); - } - - void operator=(const Map &p_map) { - _copy_from(p_map); - } - - Map(const Map &p_map) { - _copy_from(p_map); - } - - _FORCE_INLINE_ Map() {} - - ~Map() { - clear(); - } -}; - -} // namespace godot - -#endif // ! MAP_HPP diff --git a/include/godot_cpp/templates/rb_map.hpp b/include/godot_cpp/templates/rb_map.hpp new file mode 100644 index 0000000..38631e4 --- /dev/null +++ b/include/godot_cpp/templates/rb_map.hpp @@ -0,0 +1,765 @@ +/*************************************************************************/ +/* rb_map.hpp */ +/*************************************************************************/ +/* 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 RB_MAP_HPP +#define RB_MAP_HPP + +#include +#include +#include + +namespace godot { + +// based on the very nice implementation of rb-trees by: +// https://web.archive.org/web/20120507164830/https://web.mit.edu/~emin/www/source_code/red_black_tree/index.html + +template , class A = DefaultAllocator> +class RBMap { + enum Color { + RED, + BLACK + }; + struct _Data; + +public: + class Element { + private: + friend class RBMap; + int color = RED; + Element *right = nullptr; + Element *left = nullptr; + Element *parent = nullptr; + Element *_next = nullptr; + Element *_prev = nullptr; + KeyValue _data; + + public: + KeyValue &key_value() { return _data; } + const KeyValue &key_value() const { return _data; } + + const Element *next() const { + return _next; + } + Element *next() { + return _next; + } + const Element *prev() const { + return _prev; + } + Element *prev() { + return _prev; + } + const K &key() const { + return _data.key; + } + V &value() { + return _data.value; + } + const V &value() const { + return _data.value; + } + V &get() { + return _data.value; + } + const V &get() const { + return _data.value; + } + Element(const KeyValue &p_data) : + _data(p_data) {} + }; + + typedef KeyValue ValueType; + + struct Iterator { + _FORCE_INLINE_ KeyValue &operator*() const { + return E->key_value(); + } + _FORCE_INLINE_ KeyValue *operator->() const { return &E->key_value(); } + _FORCE_INLINE_ Iterator &operator++() { + E = E->next(); + return *this; + } + _FORCE_INLINE_ Iterator &operator--() { + E = E->prev(); + return *this; + } + + _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; } + + private: + Element *E = nullptr; + }; + + struct ConstIterator { + _FORCE_INLINE_ const KeyValue &operator*() const { + return E->key_value(); + } + _FORCE_INLINE_ const KeyValue *operator->() const { return &E->key_value(); } + _FORCE_INLINE_ ConstIterator &operator++() { + E = E->next(); + return *this; + } + _FORCE_INLINE_ ConstIterator &operator--() { + E = E->prev(); + return *this; + } + + _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; } + + private: + const Element *E = nullptr; + }; + + _FORCE_INLINE_ Iterator begin() { + return Iterator(front()); + } + _FORCE_INLINE_ Iterator end() { + return Iterator(nullptr); + } + +#if 0 + //to use when replacing find() + _FORCE_INLINE_ Iterator find(const K &p_key) { + return Iterator(find(p_key)); + } +#endif + _FORCE_INLINE_ void remove(const Iterator &p_iter) { + return erase(p_iter.E); + } + + _FORCE_INLINE_ ConstIterator begin() const { + return ConstIterator(front()); + } + _FORCE_INLINE_ ConstIterator end() const { + return ConstIterator(nullptr); + } + +#if 0 + //to use when replacing find() + _FORCE_INLINE_ ConstIterator find(const K &p_key) const { + return ConstIterator(find(p_key)); + } +#endif +private: + struct _Data { + Element *_root = nullptr; + Element *_nil = nullptr; + int size_cache = 0; + + _FORCE_INLINE_ _Data() { +#ifdef GLOBALNIL_DISABLED + _nil = memnew_allocator(Element, A); + _nil->parent = _nil->left = _nil->right = _nil; + _nil->color = BLACK; +#else + _nil = (Element *)&_GlobalNilClass::_nil; +#endif + } + + void _create_root() { + _root = memnew_allocator(Element(KeyValue(K(), V())), A); + _root->parent = _root->left = _root->right = _nil; + _root->color = BLACK; + } + + void _free_root() { + if (_root) { + memdelete_allocator(_root); + _root = nullptr; + } + } + + ~_Data() { + _free_root(); + +#ifdef GLOBALNIL_DISABLED + memdelete_allocator(_nil); +#endif + } + }; + + _Data _data; + + inline void _set_color(Element *p_node, int p_color) { + ERR_FAIL_COND(p_node == _data._nil && p_color == RED); + p_node->color = p_color; + } + + inline void _rotate_left(Element *p_node) { + Element *r = p_node->right; + p_node->right = r->left; + if (r->left != _data._nil) { + r->left->parent = p_node; + } + r->parent = p_node->parent; + if (p_node == p_node->parent->left) { + p_node->parent->left = r; + } else { + p_node->parent->right = r; + } + + r->left = p_node; + p_node->parent = r; + } + + inline void _rotate_right(Element *p_node) { + Element *l = p_node->left; + p_node->left = l->right; + if (l->right != _data._nil) { + l->right->parent = p_node; + } + l->parent = p_node->parent; + if (p_node == p_node->parent->right) { + p_node->parent->right = l; + } else { + p_node->parent->left = l; + } + + l->right = p_node; + p_node->parent = l; + } + + inline Element *_successor(Element *p_node) const { + Element *node = p_node; + + if (node->right != _data._nil) { + node = node->right; + while (node->left != _data._nil) { /* returns the minimum of the right subtree of node */ + node = node->left; + } + return node; + } else { + while (node == node->parent->right) { + node = node->parent; + } + + if (node->parent == _data._root) { + return nullptr; // No successor, as p_node = last node + } + return node->parent; + } + } + + inline Element *_predecessor(Element *p_node) const { + Element *node = p_node; + + if (node->left != _data._nil) { + node = node->left; + while (node->right != _data._nil) { /* returns the minimum of the left subtree of node */ + node = node->right; + } + return node; + } else { + while (node == node->parent->left) { + node = node->parent; + } + + if (node == _data._root) { + return nullptr; // No predecessor, as p_node = first node + } + return node->parent; + } + } + + Element *_find(const K &p_key) const { + Element *node = _data._root->left; + C less; + + while (node != _data._nil) { + if (less(p_key, node->_data.key)) { + node = node->left; + } else if (less(node->_data.key, p_key)) { + node = node->right; + } else { + return node; // found + } + } + + return nullptr; + } + + Element *_find_closest(const K &p_key) const { + Element *node = _data._root->left; + Element *prev = nullptr; + C less; + + while (node != _data._nil) { + prev = node; + + if (less(p_key, node->_data.key)) { + node = node->left; + } else if (less(node->_data.key, p_key)) { + node = node->right; + } else { + return node; // found + } + } + + if (prev == nullptr) { + return nullptr; // tree empty + } + + if (less(p_key, prev->_data.key)) { + prev = prev->_prev; + } + + return prev; + } + + void _insert_rb_fix(Element *p_new_node) { + Element *node = p_new_node; + Element *nparent = node->parent; + Element *ngrand_parent = nullptr; + + while (nparent->color == RED) { + ngrand_parent = nparent->parent; + + if (nparent == ngrand_parent->left) { + if (ngrand_parent->right->color == RED) { + _set_color(nparent, BLACK); + _set_color(ngrand_parent->right, BLACK); + _set_color(ngrand_parent, RED); + node = ngrand_parent; + nparent = node->parent; + } else { + if (node == nparent->right) { + _rotate_left(nparent); + node = nparent; + nparent = node->parent; + } + _set_color(nparent, BLACK); + _set_color(ngrand_parent, RED); + _rotate_right(ngrand_parent); + } + } else { + if (ngrand_parent->left->color == RED) { + _set_color(nparent, BLACK); + _set_color(ngrand_parent->left, BLACK); + _set_color(ngrand_parent, RED); + node = ngrand_parent; + nparent = node->parent; + } else { + if (node == nparent->left) { + _rotate_right(nparent); + node = nparent; + nparent = node->parent; + } + _set_color(nparent, BLACK); + _set_color(ngrand_parent, RED); + _rotate_left(ngrand_parent); + } + } + } + + _set_color(_data._root->left, BLACK); + } + + Element *_insert(const K &p_key, const V &p_value) { + Element *new_parent = _data._root; + Element *node = _data._root->left; + C less; + + while (node != _data._nil) { + new_parent = node; + + if (less(p_key, node->_data.key)) { + node = node->left; + } else if (less(node->_data.key, p_key)) { + node = node->right; + } else { + node->_data.value = p_value; + return node; // Return existing node with new value + } + } + + typedef KeyValue KV; + Element *new_node = memnew_allocator(Element(KV(p_key, p_value)), A); + new_node->parent = new_parent; + new_node->right = _data._nil; + new_node->left = _data._nil; + + // new_node->data=_data; + + if (new_parent == _data._root || less(p_key, new_parent->_data.key)) { + new_parent->left = new_node; + } else { + new_parent->right = new_node; + } + + new_node->_next = _successor(new_node); + new_node->_prev = _predecessor(new_node); + if (new_node->_next) { + new_node->_next->_prev = new_node; + } + if (new_node->_prev) { + new_node->_prev->_next = new_node; + } + + _data.size_cache++; + _insert_rb_fix(new_node); + return new_node; + } + + void _erase_fix_rb(Element *p_node) { + Element *root = _data._root->left; + Element *node = _data._nil; + Element *sibling = p_node; + Element *parent = sibling->parent; + + while (node != root) { // If red node found, will exit at a break + if (sibling->color == RED) { + _set_color(sibling, BLACK); + _set_color(parent, RED); + if (sibling == parent->right) { + sibling = sibling->left; + _rotate_left(parent); + } else { + sibling = sibling->right; + _rotate_right(parent); + } + } + if ((sibling->left->color == BLACK) && (sibling->right->color == BLACK)) { + _set_color(sibling, RED); + if (parent->color == RED) { + _set_color(parent, BLACK); + break; + } else { // loop: haven't found any red nodes yet + node = parent; + parent = node->parent; + sibling = (node == parent->left) ? parent->right : parent->left; + } + } else { + if (sibling == parent->right) { + if (sibling->right->color == BLACK) { + _set_color(sibling->left, BLACK); + _set_color(sibling, RED); + _rotate_right(sibling); + sibling = sibling->parent; + } + _set_color(sibling, parent->color); + _set_color(parent, BLACK); + _set_color(sibling->right, BLACK); + _rotate_left(parent); + break; + } else { + if (sibling->left->color == BLACK) { + _set_color(sibling->right, BLACK); + _set_color(sibling, RED); + _rotate_left(sibling); + sibling = sibling->parent; + } + + _set_color(sibling, parent->color); + _set_color(parent, BLACK); + _set_color(sibling->left, BLACK); + _rotate_right(parent); + break; + } + } + } + + ERR_FAIL_COND(_data._nil->color != BLACK); + } + + void _erase(Element *p_node) { + 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 = nullptr; + if (rp == rp->parent->left) { + rp->parent->left = node; + sibling = rp->parent->right; + } else { + rp->parent->right = node; + sibling = rp->parent->left; + } + + if (node->color == RED) { + node->parent = rp->parent; + _set_color(node, BLACK); + } else if (rp->color == BLACK && rp->parent != _data._root) { + _erase_fix_rb(sibling); + } + + if (rp != p_node) { + ERR_FAIL_COND(rp == _data._nil); + + rp->left = p_node->left; + rp->right = p_node->right; + rp->parent = p_node->parent; + rp->color = p_node->color; + if (p_node->left != _data._nil) { + p_node->left->parent = rp; + } + if (p_node->right != _data._nil) { + p_node->right->parent = rp; + } + + if (p_node == p_node->parent->left) { + p_node->parent->left = rp; + } else { + p_node->parent->right = rp; + } + } + + if (p_node->_next) { + p_node->_next->_prev = p_node->_prev; + } + if (p_node->_prev) { + p_node->_prev->_next = p_node->_next; + } + + memdelete_allocator(p_node); + _data.size_cache--; + ERR_FAIL_COND(_data._nil->color == RED); + } + + void _calculate_depth(Element *p_element, int &max_d, int d) const { + if (p_element == _data._nil) { + return; + } + + _calculate_depth(p_element->left, max_d, d + 1); + _calculate_depth(p_element->right, max_d, d + 1); + + if (d > max_d) { + max_d = d; + } + } + + void _cleanup_tree(Element *p_element) { + if (p_element == _data._nil) { + return; + } + + _cleanup_tree(p_element->left); + _cleanup_tree(p_element->right); + memdelete_allocator(p_element); + } + + 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()) { + insert(I->key(), I->value()); + } + } + +public: + const Element *find(const K &p_key) const { + if (!_data._root) { + return nullptr; + } + + const Element *res = _find(p_key); + return res; + } + + Element *find(const K &p_key) { + if (!_data._root) { + return nullptr; + } + + Element *res = _find(p_key); + return res; + } + + const Element *find_closest(const K &p_key) const { + if (!_data._root) { + return nullptr; + } + + const Element *res = _find_closest(p_key); + return res; + } + + Element *find_closest(const K &p_key) { + if (!_data._root) { + return nullptr; + } + + Element *res = _find_closest(p_key); + return res; + } + + bool has(const K &p_key) const { + return find(p_key) != nullptr; + } + + Element *insert(const K &p_key, const V &p_value) { + if (!_data._root) { + _data._create_root(); + } + return _insert(p_key, p_value); + } + + void erase(Element *p_element) { + if (!_data._root || !p_element) { + return; + } + + _erase(p_element); + if (_data.size_cache == 0 && _data._root) { + _data._free_root(); + } + } + + bool erase(const K &p_key) { + if (!_data._root) { + return false; + } + + Element *e = find(p_key); + if (!e) { + return false; + } + + _erase(e); + if (_data.size_cache == 0 && _data._root) { + _data._free_root(); + } + return true; + } + + const V &operator[](const K &p_key) const { + CRASH_COND(!_data._root); + const Element *e = find(p_key); + CRASH_COND(!e); + return e->_data.value; + } + + V &operator[](const K &p_key) { + if (!_data._root) { + _data._create_root(); + } + + Element *e = find(p_key); + if (!e) { + e = insert(p_key, V()); + } + + return e->_data.value; + } + + Element *front() const { + if (!_data._root) { + return nullptr; + } + + Element *e = _data._root->left; + if (e == _data._nil) { + return nullptr; + } + + while (e->left != _data._nil) { + e = e->left; + } + + return e; + } + + Element *back() const { + if (!_data._root) { + return nullptr; + } + + Element *e = _data._root->left; + if (e == _data._nil) { + return nullptr; + } + + while (e->right != _data._nil) { + e = e->right; + } + + return e; + } + + 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 + if (!_data._root) { + return 0; + } + + int max_d = 0; + _calculate_depth(_data._root->left, max_d, 0); + return max_d; + } + + void clear() { + if (!_data._root) { + return; + } + + _cleanup_tree(_data._root->left); + _data._root->left = _data._nil; + _data.size_cache = 0; + _data._free_root(); + } + + void operator=(const RBMap &p_map) { + _copy_from(p_map); + } + + RBMap(const RBMap &p_map) { + _copy_from(p_map); + } + + _FORCE_INLINE_ RBMap() {} + + ~RBMap() { + clear(); + } +}; + +} // namespace godot + +#endif // MAP_HPP diff --git a/include/godot_cpp/templates/rb_set.hpp b/include/godot_cpp/templates/rb_set.hpp new file mode 100644 index 0000000..122ce5b --- /dev/null +++ b/include/godot_cpp/templates/rb_set.hpp @@ -0,0 +1,714 @@ +/*************************************************************************/ +/* rb_set.hpp */ +/*************************************************************************/ +/* 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 RB_SET_HPP +#define RB_SET_HPP + +#include + +// based on the very nice implementation of rb-trees by: +// https://web.archive.org/web/20120507164830/https://web.mit.edu/~emin/www/source_code/red_black_tree/index.html + +namespace godot { + +template , class A = DefaultAllocator> +class RBSet { + enum Color { + RED, + BLACK + }; + struct _Data; + +public: + class Element { + private: + friend class RBSet; + int color = RED; + Element *right = nullptr; + Element *left = nullptr; + Element *parent = nullptr; + Element *_next = nullptr; + Element *_prev = nullptr; + T value; + //_Data *data; + + public: + const Element *next() const { + return _next; + } + Element *next() { + return _next; + } + const Element *prev() const { + return _prev; + } + Element *prev() { + return _prev; + } + T &get() { + return value; + } + const T &get() const { + return value; + }; + Element() {} + }; + + typedef T ValueType; + + struct Iterator { + _FORCE_INLINE_ T &operator*() const { + return E->get(); + } + _FORCE_INLINE_ T *operator->() const { return &E->get(); } + _FORCE_INLINE_ Iterator &operator++() { + E = E->next(); + return *this; + } + _FORCE_INLINE_ Iterator &operator--() { + E = E->prev(); + return *this; + } + + _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; } + + private: + Element *E = nullptr; + }; + + struct ConstIterator { + _FORCE_INLINE_ const T &operator*() const { + return E->get(); + } + _FORCE_INLINE_ const T *operator->() const { return &E->get(); } + _FORCE_INLINE_ ConstIterator &operator++() { + E = E->next(); + return *this; + } + _FORCE_INLINE_ ConstIterator &operator--() { + E = E->prev(); + return *this; + } + + _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; } + _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; } + + _FORCE_INLINE_ ConstIterator(const Element *p_E) { E = p_E; } + _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; + }; + + _FORCE_INLINE_ Iterator begin() { + return Iterator(front()); + } + _FORCE_INLINE_ Iterator end() { + return Iterator(nullptr); + } + +#if 0 + //to use when replacing find() + _FORCE_INLINE_ Iterator find(const K &p_key) { + return Iterator(find(p_key)); + } +#endif + + _FORCE_INLINE_ ConstIterator begin() const { + return ConstIterator(front()); + } + _FORCE_INLINE_ ConstIterator end() const { + return ConstIterator(nullptr); + } + +#if 0 + //to use when replacing find() + _FORCE_INLINE_ ConstIterator find(const K &p_key) const { + return ConstIterator(find(p_key)); + } +#endif +private: + struct _Data { + Element *_root = nullptr; + Element *_nil = nullptr; + int size_cache = 0; + + _FORCE_INLINE_ _Data() { +#ifdef GLOBALNIL_DISABLED + _nil = memnew_allocator(Element, A); + _nil->parent = _nil->left = _nil->right = _nil; + _nil->color = BLACK; +#else + _nil = (Element *)&_GlobalNilClass::_nil; +#endif + } + + void _create_root() { + _root = memnew_allocator(Element, A); + _root->parent = _root->left = _root->right = _nil; + _root->color = BLACK; + } + + void _free_root() { + if (_root) { + memdelete_allocator(_root); + _root = nullptr; + } + } + + ~_Data() { + _free_root(); + +#ifdef GLOBALNIL_DISABLED + memdelete_allocator(_nil); +#endif + } + }; + + _Data _data; + + inline void _set_color(Element *p_node, int p_color) { + ERR_FAIL_COND(p_node == _data._nil && p_color == RED); + p_node->color = p_color; + } + + inline void _rotate_left(Element *p_node) { + Element *r = p_node->right; + p_node->right = r->left; + if (r->left != _data._nil) { + r->left->parent = p_node; + } + r->parent = p_node->parent; + if (p_node == p_node->parent->left) { + p_node->parent->left = r; + } else { + p_node->parent->right = r; + } + + r->left = p_node; + p_node->parent = r; + } + + inline void _rotate_right(Element *p_node) { + Element *l = p_node->left; + p_node->left = l->right; + if (l->right != _data._nil) { + l->right->parent = p_node; + } + l->parent = p_node->parent; + if (p_node == p_node->parent->right) { + p_node->parent->right = l; + } else { + p_node->parent->left = l; + } + + l->right = p_node; + p_node->parent = l; + } + + inline Element *_successor(Element *p_node) const { + Element *node = p_node; + + if (node->right != _data._nil) { + node = node->right; + while (node->left != _data._nil) { /* returns the minimum of the right subtree of node */ + node = node->left; + } + return node; + } else { + while (node == node->parent->right) { + node = node->parent; + } + + if (node->parent == _data._root) { + return nullptr; // No successor, as p_node = last node + } + return node->parent; + } + } + + inline Element *_predecessor(Element *p_node) const { + Element *node = p_node; + + if (node->left != _data._nil) { + node = node->left; + while (node->right != _data._nil) { /* returns the minimum of the left subtree of node */ + node = node->right; + } + return node; + } else { + while (node == node->parent->left) { + node = node->parent; + } + + if (node == _data._root) { + return nullptr; // No predecessor, as p_node = first node. + } + return node->parent; + } + } + + Element *_find(const T &p_value) const { + Element *node = _data._root->left; + C less; + + while (node != _data._nil) { + if (less(p_value, node->value)) { + node = node->left; + } else if (less(node->value, p_value)) { + node = node->right; + } else { + return node; // found + } + } + + return nullptr; + } + + Element *_lower_bound(const T &p_value) const { + Element *node = _data._root->left; + Element *prev = nullptr; + C less; + + while (node != _data._nil) { + prev = node; + + if (less(p_value, node->value)) { + node = node->left; + } else if (less(node->value, p_value)) { + node = node->right; + } else { + return node; // found + } + } + + if (prev == nullptr) { + return nullptr; // tree empty + } + + if (less(prev->value, p_value)) { + prev = prev->_next; + } + + return prev; + } + + void _insert_rb_fix(Element *p_new_node) { + Element *node = p_new_node; + Element *nparent = node->parent; + Element *ngrand_parent = nullptr; + + while (nparent->color == RED) { + ngrand_parent = nparent->parent; + + if (nparent == ngrand_parent->left) { + if (ngrand_parent->right->color == RED) { + _set_color(nparent, BLACK); + _set_color(ngrand_parent->right, BLACK); + _set_color(ngrand_parent, RED); + node = ngrand_parent; + nparent = node->parent; + } else { + if (node == nparent->right) { + _rotate_left(nparent); + node = nparent; + nparent = node->parent; + } + _set_color(nparent, BLACK); + _set_color(ngrand_parent, RED); + _rotate_right(ngrand_parent); + } + } else { + if (ngrand_parent->left->color == RED) { + _set_color(nparent, BLACK); + _set_color(ngrand_parent->left, BLACK); + _set_color(ngrand_parent, RED); + node = ngrand_parent; + nparent = node->parent; + } else { + if (node == nparent->left) { + _rotate_right(nparent); + node = nparent; + nparent = node->parent; + } + _set_color(nparent, BLACK); + _set_color(ngrand_parent, RED); + _rotate_left(ngrand_parent); + } + } + } + + _set_color(_data._root->left, BLACK); + } + + Element *_insert(const T &p_value) { + Element *new_parent = _data._root; + Element *node = _data._root->left; + C less; + + while (node != _data._nil) { + new_parent = node; + + if (less(p_value, node->value)) { + node = node->left; + } else if (less(node->value, p_value)) { + node = node->right; + } else { + return node; // Return existing node + } + } + + Element *new_node = memnew_allocator(Element, A); + new_node->parent = new_parent; + new_node->right = _data._nil; + new_node->left = _data._nil; + new_node->value = p_value; + // new_node->data=_data; + + if (new_parent == _data._root || less(p_value, new_parent->value)) { + new_parent->left = new_node; + } else { + new_parent->right = new_node; + } + + new_node->_next = _successor(new_node); + new_node->_prev = _predecessor(new_node); + if (new_node->_next) { + new_node->_next->_prev = new_node; + } + if (new_node->_prev) { + new_node->_prev->_next = new_node; + } + + _data.size_cache++; + _insert_rb_fix(new_node); + return new_node; + } + + void _erase_fix_rb(Element *p_node) { + Element *root = _data._root->left; + Element *node = _data._nil; + Element *sibling = p_node; + Element *parent = sibling->parent; + + while (node != root) { // If red node found, will exit at a break + if (sibling->color == RED) { + _set_color(sibling, BLACK); + _set_color(parent, RED); + if (sibling == parent->right) { + sibling = sibling->left; + _rotate_left(parent); + } else { + sibling = sibling->right; + _rotate_right(parent); + } + } + if ((sibling->left->color == BLACK) && (sibling->right->color == BLACK)) { + _set_color(sibling, RED); + if (parent->color == RED) { + _set_color(parent, BLACK); + break; + } else { // loop: haven't found any red nodes yet + node = parent; + parent = node->parent; + sibling = (node == parent->left) ? parent->right : parent->left; + } + } else { + if (sibling == parent->right) { + if (sibling->right->color == BLACK) { + _set_color(sibling->left, BLACK); + _set_color(sibling, RED); + _rotate_right(sibling); + sibling = sibling->parent; + } + _set_color(sibling, parent->color); + _set_color(parent, BLACK); + _set_color(sibling->right, BLACK); + _rotate_left(parent); + break; + } else { + if (sibling->left->color == BLACK) { + _set_color(sibling->right, BLACK); + _set_color(sibling, RED); + _rotate_left(sibling); + sibling = sibling->parent; + } + + _set_color(sibling, parent->color); + _set_color(parent, BLACK); + _set_color(sibling->left, BLACK); + _rotate_right(parent); + break; + } + } + } + + ERR_FAIL_COND(_data._nil->color != BLACK); + } + + void _erase(Element *p_node) { + 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 = nullptr; + if (rp == rp->parent->left) { + rp->parent->left = node; + sibling = rp->parent->right; + } else { + rp->parent->right = node; + sibling = rp->parent->left; + } + + if (node->color == RED) { + node->parent = rp->parent; + _set_color(node, BLACK); + } else if (rp->color == BLACK && rp->parent != _data._root) { + _erase_fix_rb(sibling); + } + + if (rp != p_node) { + ERR_FAIL_COND(rp == _data._nil); + + rp->left = p_node->left; + rp->right = p_node->right; + rp->parent = p_node->parent; + rp->color = p_node->color; + if (p_node->left != _data._nil) { + p_node->left->parent = rp; + } + if (p_node->right != _data._nil) { + p_node->right->parent = rp; + } + + if (p_node == p_node->parent->left) { + p_node->parent->left = rp; + } else { + p_node->parent->right = rp; + } + } + + if (p_node->_next) { + p_node->_next->_prev = p_node->_prev; + } + if (p_node->_prev) { + p_node->_prev->_next = p_node->_next; + } + + memdelete_allocator(p_node); + _data.size_cache--; + ERR_FAIL_COND(_data._nil->color == RED); + } + + void _calculate_depth(Element *p_element, int &max_d, int d) const { + if (p_element == _data._nil) { + return; + } + + _calculate_depth(p_element->left, max_d, d + 1); + _calculate_depth(p_element->right, max_d, d + 1); + + if (d > max_d) { + max_d = d; + } + } + + void _cleanup_tree(Element *p_element) { + if (p_element == _data._nil) { + return; + } + + _cleanup_tree(p_element->left); + _cleanup_tree(p_element->right); + memdelete_allocator(p_element); + } + + 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()) { + insert(I->get()); + } + } + +public: + const Element *find(const T &p_value) const { + if (!_data._root) { + return nullptr; + } + + const Element *res = _find(p_value); + return res; + } + + Element *find(const T &p_value) { + if (!_data._root) { + return nullptr; + } + + Element *res = _find(p_value); + return res; + } + + Element *lower_bound(const T &p_value) const { + if (!_data._root) { + return nullptr; + } + return _lower_bound(p_value); + } + + bool has(const T &p_value) const { + return find(p_value) != nullptr; + } + + Element *insert(const T &p_value) { + if (!_data._root) { + _data._create_root(); + } + return _insert(p_value); + } + + void erase(Element *p_element) { + if (!_data._root || !p_element) { + return; + } + + _erase(p_element); + if (_data.size_cache == 0 && _data._root) { + _data._free_root(); + } + } + + bool erase(const T &p_value) { + if (!_data._root) { + return false; + } + + Element *e = find(p_value); + if (!e) { + return false; + } + + _erase(e); + if (_data.size_cache == 0 && _data._root) { + _data._free_root(); + } + return true; + } + + Element *front() const { + if (!_data._root) { + return nullptr; + } + + Element *e = _data._root->left; + if (e == _data._nil) { + return nullptr; + } + + while (e->left != _data._nil) { + e = e->left; + } + + return e; + } + + Element *back() const { + if (!_data._root) { + return nullptr; + } + + Element *e = _data._root->left; + if (e == _data._nil) { + return nullptr; + } + + while (e->right != _data._nil) { + e = e->right; + } + + return e; + } + + 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 + if (!_data._root) { + return 0; + } + + int max_d = 0; + _calculate_depth(_data._root->left, max_d, 0); + return max_d; + } + + void clear() { + if (!_data._root) { + return; + } + + _cleanup_tree(_data._root->left); + _data._root->left = _data._nil; + _data.size_cache = 0; + _data._free_root(); + } + + void operator=(const RBSet &p_set) { + _copy_from(p_set); + } + + RBSet(const RBSet &p_set) { + _copy_from(p_set); + } + + _FORCE_INLINE_ RBSet() {} + + ~RBSet() { + clear(); + } +}; + +} // namespace godot + +#endif // SET_HPP diff --git a/include/godot_cpp/templates/set.hpp b/include/godot_cpp/templates/set.hpp deleted file mode 100644 index 38a071d..0000000 --- a/include/godot_cpp/templates/set.hpp +++ /dev/null @@ -1,707 +0,0 @@ -/*************************************************************************/ -/* set.hpp */ -/*************************************************************************/ -/* 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 SET_HPP -#define SET_HPP - -#include - -// based on the very nice implementation of rb-trees by: -// https://web.archive.org/web/20120507164830/https://web.mit.edu/~emin/www/source_code/red_black_tree/index.html - -namespace godot { - -template , class A = DefaultAllocator> -class Set { - enum Color { - RED, - BLACK - }; - struct _Data; - -public: - class Element { - private: - friend class Set; - int color = RED; - Element *right = nullptr; - Element *left = nullptr; - Element *parent = nullptr; - Element *_next = nullptr; - Element *_prev = nullptr; - T value; - //_Data *data; - - public: - const Element *next() const { - return _next; - } - Element *next() { - return _next; - } - const Element *prev() const { - return _prev; - } - Element *prev() { - return _prev; - } - T &get() { - return value; - } - const T &get() const { - return value; - }; - Element() {} - }; - - typedef T ValueType; - - struct Iterator { - _FORCE_INLINE_ T &operator*() const { - return E->get(); - } - _FORCE_INLINE_ T *operator->() const { return &E->get(); } - _FORCE_INLINE_ Iterator &operator++() { - E = E->next(); - return *this; - } - _FORCE_INLINE_ Iterator &operator--() { - E = E->prev(); - return *this; - } - - _FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; } - _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; } - - Iterator(Element *p_E) { E = p_E; } - Iterator() {} - Iterator(const Iterator &p_it) { E = p_it.E; } - - private: - Element *E = nullptr; - }; - - struct ConstIterator { - _FORCE_INLINE_ const T &operator*() const { - return E->get(); - } - _FORCE_INLINE_ const T *operator->() const { return &E->get(); } - _FORCE_INLINE_ ConstIterator &operator++() { - E = E->next(); - return *this; - } - _FORCE_INLINE_ ConstIterator &operator--() { - E = E->prev(); - return *this; - } - - _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; } - _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; } - - _FORCE_INLINE_ ConstIterator(const Element *p_E) { E = p_E; } - _FORCE_INLINE_ ConstIterator() {} - _FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; } - - private: - const Element *E = nullptr; - }; - - _FORCE_INLINE_ Iterator begin() { - return Iterator(front()); - } - _FORCE_INLINE_ Iterator end() { - return Iterator(nullptr); - } - -#if 0 - //to use when replacing find() - _FORCE_INLINE_ Iterator find(const K &p_key) { - return Iterator(find(p_key)); - } -#endif - - _FORCE_INLINE_ ConstIterator begin() const { - return ConstIterator(front()); - } - _FORCE_INLINE_ ConstIterator end() const { - return ConstIterator(nullptr); - } - -#if 0 - //to use when replacing find() - _FORCE_INLINE_ ConstIterator find(const K &p_key) const { - return ConstIterator(find(p_key)); - } -#endif -private: - struct _Data { - Element *_root = nullptr; - Element *_nil = nullptr; - int size_cache = 0; - - _FORCE_INLINE_ _Data() { -#ifdef GLOBALNIL_DISABLED - _nil = memnew_allocator(Element, A); - _nil->parent = _nil->left = _nil->right = _nil; - _nil->color = BLACK; -#else - _nil = (Element *)&_GlobalNilClass::_nil; -#endif - } - - void _create_root() { - _root = memnew_allocator(Element, A); - _root->parent = _root->left = _root->right = _nil; - _root->color = BLACK; - } - - void _free_root() { - if (_root) { - memdelete_allocator(_root); - _root = nullptr; - } - } - - ~_Data() { - _free_root(); - -#ifdef GLOBALNIL_DISABLED - memdelete_allocator(_nil); -#endif - } - }; - - _Data _data; - - inline void _set_color(Element *p_node, int p_color) { - ERR_FAIL_COND(p_node == _data._nil && p_color == RED); - p_node->color = p_color; - } - - inline void _rotate_left(Element *p_node) { - Element *r = p_node->right; - p_node->right = r->left; - if (r->left != _data._nil) { - r->left->parent = p_node; - } - r->parent = p_node->parent; - if (p_node == p_node->parent->left) { - p_node->parent->left = r; - } else { - p_node->parent->right = r; - } - - r->left = p_node; - p_node->parent = r; - } - - inline void _rotate_right(Element *p_node) { - Element *l = p_node->left; - p_node->left = l->right; - if (l->right != _data._nil) { - l->right->parent = p_node; - } - l->parent = p_node->parent; - if (p_node == p_node->parent->right) { - p_node->parent->right = l; - } else { - p_node->parent->left = l; - } - - l->right = p_node; - p_node->parent = l; - } - - inline Element *_successor(Element *p_node) const { - Element *node = p_node; - - if (node->right != _data._nil) { - node = node->right; - while (node->left != _data._nil) { /* returns the minimum of the right subtree of node */ - node = node->left; - } - return node; - } else { - while (node == node->parent->right) { - node = node->parent; - } - - if (node->parent == _data._root) { - return nullptr; // No successor, as p_node = last node - } - return node->parent; - } - } - - inline Element *_predecessor(Element *p_node) const { - Element *node = p_node; - - if (node->left != _data._nil) { - node = node->left; - while (node->right != _data._nil) { /* returns the minimum of the left subtree of node */ - node = node->right; - } - return node; - } else { - while (node == node->parent->left) { - node = node->parent; - } - - if (node == _data._root) { - return nullptr; // No predecessor, as p_node = first node. - } - return node->parent; - } - } - - Element *_find(const T &p_value) const { - Element *node = _data._root->left; - C less; - - while (node != _data._nil) { - if (less(p_value, node->value)) { - node = node->left; - } else if (less(node->value, p_value)) { - node = node->right; - } else { - return node; // found - } - } - - return nullptr; - } - - Element *_lower_bound(const T &p_value) const { - Element *node = _data._root->left; - Element *prev = nullptr; - C less; - - while (node != _data._nil) { - prev = node; - - if (less(p_value, node->value)) { - node = node->left; - } else if (less(node->value, p_value)) { - node = node->right; - } else { - return node; // found - } - } - - if (prev == nullptr) { - return nullptr; // tree empty - } - - if (less(prev->value, p_value)) { - prev = prev->_next; - } - - return prev; - } - - void _insert_rb_fix(Element *p_new_node) { - Element *node = p_new_node; - Element *nparent = node->parent; - Element *ngrand_parent; - - while (nparent->color == RED) { - ngrand_parent = nparent->parent; - - if (nparent == ngrand_parent->left) { - if (ngrand_parent->right->color == RED) { - _set_color(nparent, BLACK); - _set_color(ngrand_parent->right, BLACK); - _set_color(ngrand_parent, RED); - node = ngrand_parent; - nparent = node->parent; - } else { - if (node == nparent->right) { - _rotate_left(nparent); - node = nparent; - nparent = node->parent; - } - _set_color(nparent, BLACK); - _set_color(ngrand_parent, RED); - _rotate_right(ngrand_parent); - } - } else { - if (ngrand_parent->left->color == RED) { - _set_color(nparent, BLACK); - _set_color(ngrand_parent->left, BLACK); - _set_color(ngrand_parent, RED); - node = ngrand_parent; - nparent = node->parent; - } else { - if (node == nparent->left) { - _rotate_right(nparent); - node = nparent; - nparent = node->parent; - } - _set_color(nparent, BLACK); - _set_color(ngrand_parent, RED); - _rotate_left(ngrand_parent); - } - } - } - - _set_color(_data._root->left, BLACK); - } - - Element *_insert(const T &p_value) { - Element *new_parent = _data._root; - Element *node = _data._root->left; - C less; - - while (node != _data._nil) { - new_parent = node; - - if (less(p_value, node->value)) { - node = node->left; - } else if (less(node->value, p_value)) { - node = node->right; - } else { - return node; // Return existing node - } - } - - Element *new_node = memnew_allocator(Element, A); - new_node->parent = new_parent; - new_node->right = _data._nil; - new_node->left = _data._nil; - new_node->value = p_value; - // new_node->data=_data; - - if (new_parent == _data._root || less(p_value, new_parent->value)) { - new_parent->left = new_node; - } else { - new_parent->right = new_node; - } - - new_node->_next = _successor(new_node); - new_node->_prev = _predecessor(new_node); - if (new_node->_next) { - new_node->_next->_prev = new_node; - } - if (new_node->_prev) { - new_node->_prev->_next = new_node; - } - - _data.size_cache++; - _insert_rb_fix(new_node); - return new_node; - } - - void _erase_fix_rb(Element *p_node) { - Element *root = _data._root->left; - Element *node = _data._nil; - Element *sibling = p_node; - Element *parent = sibling->parent; - - while (node != root) { // If red node found, will exit at a break - if (sibling->color == RED) { - _set_color(sibling, BLACK); - _set_color(parent, RED); - if (sibling == parent->right) { - sibling = sibling->left; - _rotate_left(parent); - } else { - sibling = sibling->right; - _rotate_right(parent); - } - } - if ((sibling->left->color == BLACK) && (sibling->right->color == BLACK)) { - _set_color(sibling, RED); - if (parent->color == RED) { - _set_color(parent, BLACK); - break; - } else { // loop: haven't found any red nodes yet - node = parent; - parent = node->parent; - sibling = (node == parent->left) ? parent->right : parent->left; - } - } else { - if (sibling == parent->right) { - if (sibling->right->color == BLACK) { - _set_color(sibling->left, BLACK); - _set_color(sibling, RED); - _rotate_right(sibling); - sibling = sibling->parent; - } - _set_color(sibling, parent->color); - _set_color(parent, BLACK); - _set_color(sibling->right, BLACK); - _rotate_left(parent); - break; - } else { - if (sibling->left->color == BLACK) { - _set_color(sibling->right, BLACK); - _set_color(sibling, RED); - _rotate_left(sibling); - sibling = sibling->parent; - } - - _set_color(sibling, parent->color); - _set_color(parent, BLACK); - _set_color(sibling->left, BLACK); - _rotate_right(parent); - break; - } - } - } - - ERR_FAIL_COND(_data._nil->color != BLACK); - } - - void _erase(Element *p_node) { - 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; - if (rp == rp->parent->left) { - rp->parent->left = node; - sibling = rp->parent->right; - } else { - rp->parent->right = node; - sibling = rp->parent->left; - } - - if (node->color == RED) { - node->parent = rp->parent; - _set_color(node, BLACK); - } else if (rp->color == BLACK && rp->parent != _data._root) { - _erase_fix_rb(sibling); - } - - if (rp != p_node) { - ERR_FAIL_COND(rp == _data._nil); - - rp->left = p_node->left; - rp->right = p_node->right; - rp->parent = p_node->parent; - rp->color = p_node->color; - if (p_node->left != _data._nil) { - p_node->left->parent = rp; - } - if (p_node->right != _data._nil) { - p_node->right->parent = rp; - } - - if (p_node == p_node->parent->left) { - p_node->parent->left = rp; - } else { - p_node->parent->right = rp; - } - } - - if (p_node->_next) { - p_node->_next->_prev = p_node->_prev; - } - if (p_node->_prev) { - p_node->_prev->_next = p_node->_next; - } - - memdelete_allocator(p_node); - _data.size_cache--; - ERR_FAIL_COND(_data._nil->color == RED); - } - - void _calculate_depth(Element *p_element, int &max_d, int d) const { - if (p_element == _data._nil) { - return; - } - - _calculate_depth(p_element->left, max_d, d + 1); - _calculate_depth(p_element->right, max_d, d + 1); - - if (d > max_d) { - max_d = d; - } - } - - void _cleanup_tree(Element *p_element) { - if (p_element == _data._nil) { - return; - } - - _cleanup_tree(p_element->left); - _cleanup_tree(p_element->right); - memdelete_allocator(p_element); - } - - void _copy_from(const Set &p_set) { - clear(); - // not the fastest way, but safeset to write. - for (Element *I = p_set.front(); I; I = I->next()) { - insert(I->get()); - } - } - -public: - const Element *find(const T &p_value) const { - if (!_data._root) { - return nullptr; - } - - const Element *res = _find(p_value); - return res; - } - - Element *find(const T &p_value) { - if (!_data._root) { - return nullptr; - } - - Element *res = _find(p_value); - return res; - } - - Element *lower_bound(const T &p_value) const { - if (!_data._root) { - return nullptr; - } - return _lower_bound(p_value); - } - - bool has(const T &p_value) const { - return find(p_value) != nullptr; - } - - Element *insert(const T &p_value) { - if (!_data._root) { - _data._create_root(); - } - return _insert(p_value); - } - - void erase(Element *p_element) { - if (!_data._root || !p_element) { - return; - } - - _erase(p_element); - if (_data.size_cache == 0 && _data._root) { - _data._free_root(); - } - } - - bool erase(const T &p_value) { - if (!_data._root) { - return false; - } - - Element *e = find(p_value); - if (!e) { - return false; - } - - _erase(e); - if (_data.size_cache == 0 && _data._root) { - _data._free_root(); - } - return true; - } - - Element *front() const { - if (!_data._root) { - return nullptr; - } - - Element *e = _data._root->left; - if (e == _data._nil) { - return nullptr; - } - - while (e->left != _data._nil) { - e = e->left; - } - - return e; - } - - Element *back() const { - if (!_data._root) { - return nullptr; - } - - Element *e = _data._root->left; - if (e == _data._nil) { - return nullptr; - } - - while (e->right != _data._nil) { - e = e->right; - } - - return e; - } - - 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 - if (!_data._root) { - return 0; - } - - int max_d = 0; - _calculate_depth(_data._root->left, max_d, 0); - return max_d; - } - - void clear() { - if (!_data._root) { - return; - } - - _cleanup_tree(_data._root->left); - _data._root->left = _data._nil; - _data.size_cache = 0; - _data._free_root(); - } - - void operator=(const Set &p_set) { - _copy_from(p_set); - } - - Set(const Set &p_set) { - _copy_from(p_set); - } - - _FORCE_INLINE_ Set() {} - - ~Set() { - clear(); - } -}; - -} // namespace godot - -#endif // ! SET_HPP diff --git a/include/godot_cpp/variant/variant.hpp b/include/godot_cpp/variant/variant.hpp index 1e87d6b..34811aa 100644 --- a/include/godot_cpp/variant/variant.hpp +++ b/include/godot_cpp/variant/variant.hpp @@ -102,14 +102,14 @@ public: }; enum Operator { - //comparison + // comparison OP_EQUAL, OP_NOT_EQUAL, OP_LESS, OP_LESS_EQUAL, OP_GREATER, OP_GREATER_EQUAL, - //mathematic + // mathematic OP_ADD, OP_SUBTRACT, OP_MULTIPLY, @@ -117,19 +117,19 @@ public: OP_NEGATE, OP_POSITIVE, OP_MODULE, - //bitwise + // bitwise OP_SHIFT_LEFT, OP_SHIFT_RIGHT, OP_BIT_AND, OP_BIT_OR, OP_BIT_XOR, OP_BIT_NEGATE, - //logic + // logic OP_AND, OP_OR, OP_XOR, OP_NOT, - //containment + // containment OP_IN, OP_MAX }; @@ -285,6 +285,8 @@ public: bool has_key(const Variant &key, bool *r_valid = nullptr) const; static bool has_member(Variant::Type type, const StringName &member); + uint32_t hash() const; + uint32_t recursive_hash(int recursion_count) const; bool hash_compare(const Variant &variant) const; bool booleanize() const; String stringify() const; @@ -299,6 +301,14 @@ public: void clear(); }; +struct VariantHasher { + static _FORCE_INLINE_ uint32_t hash(const Variant &p_variant) { return p_variant.hash(); } +}; + +struct VariantComparator { + static _FORCE_INLINE_ bool compare(const Variant &p_lhs, const Variant &p_rhs) { return p_lhs.hash_compare(p_rhs); } +}; + } // namespace godot #endif // ! GODOT_CPP_VARIANT_HPP -- cgit v1.2.3