From 8b7c7f5a753b43cec10f72b274bb1d70c253652b Mon Sep 17 00:00:00 2001 From: reduz Date: Sun, 8 May 2022 10:09:19 +0200 Subject: Add a new HashMap implementation Adds a new, cleaned up, HashMap implementation. * Uses Robin Hood Hashing (https://en.wikipedia.org/wiki/Hash_table#Robin_Hood_hashing). * Keeps elements in a double linked list for simpler, ordered, iteration. * Allows keeping iterators for later use in removal (Unlike Map<>, it does not do much for performance vs keeping the key, but helps replace old code). * Uses a more modern C++ iterator API, deprecates the old one. * Supports custom allocator (in case there is a wish to use a paged one). This class aims to unify all the associative template usage and replace it by this one: * Map<> (whereas key order does not matter, which is 99% of cases) * HashMap<> * OrderedHashMap<> * OAHashMap<> --- core/variant/dictionary.cpp | 85 ++++++++++++++++++++++++--------------------- 1 file changed, 46 insertions(+), 39 deletions(-) (limited to 'core/variant/dictionary.cpp') diff --git a/core/variant/dictionary.cpp b/core/variant/dictionary.cpp index 0f2f8fc8ed..46543da2c2 100644 --- a/core/variant/dictionary.cpp +++ b/core/variant/dictionary.cpp @@ -30,7 +30,7 @@ #include "dictionary.h" -#include "core/templates/ordered_hash_map.h" +#include "core/templates/hash_map.h" #include "core/templates/safe_refcount.h" #include "core/variant/variant.h" // required in this order by VariantInternal, do not remove this comment. @@ -41,7 +41,7 @@ struct DictionaryPrivate { SafeRefCount refcount; - OrderedHashMap variant_map; + HashMap variant_map; }; void Dictionary::get_key_list(List *p_keys) const { @@ -49,16 +49,16 @@ void Dictionary::get_key_list(List *p_keys) const { return; } - for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { - p_keys->push_back(E.key()); + for (const KeyValue &E : _p->variant_map) { + p_keys->push_back(E.key); } } Variant Dictionary::get_key_at_index(int p_index) const { int index = 0; - for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { + for (const KeyValue &E : _p->variant_map) { if (index == p_index) { - return E.key(); + return E.key; } index++; } @@ -68,9 +68,9 @@ Variant Dictionary::get_key_at_index(int p_index) const { Variant Dictionary::get_value_at_index(int p_index) const { int index = 0; - for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { + for (const KeyValue &E : _p->variant_map) { if (index == p_index) { - return E.value(); + return E.value; } index++; } @@ -97,50 +97,50 @@ const Variant &Dictionary::operator[](const Variant &p_key) const { } const Variant *Dictionary::getptr(const Variant &p_key) const { - OrderedHashMap::ConstElement E; + HashMap::ConstIterator E; if (p_key.get_type() == Variant::STRING_NAME) { const StringName *sn = VariantInternal::get_string_name(&p_key); - E = ((const OrderedHashMap *)&_p->variant_map)->find(sn->operator String()); + E = ((const HashMap *)&_p->variant_map)->find(sn->operator String()); } else { - E = ((const OrderedHashMap *)&_p->variant_map)->find(p_key); + E = ((const HashMap *)&_p->variant_map)->find(p_key); } if (!E) { return nullptr; } - return &E.get(); + return &E->value; } Variant *Dictionary::getptr(const Variant &p_key) { - OrderedHashMap::Element E; + HashMap::Iterator E; if (p_key.get_type() == Variant::STRING_NAME) { const StringName *sn = VariantInternal::get_string_name(&p_key); - E = ((OrderedHashMap *)&_p->variant_map)->find(sn->operator String()); + E = ((HashMap *)&_p->variant_map)->find(sn->operator String()); } else { - E = ((OrderedHashMap *)&_p->variant_map)->find(p_key); + E = ((HashMap *)&_p->variant_map)->find(p_key); } if (!E) { return nullptr; } - return &E.get(); + return &E->value; } Variant Dictionary::get_valid(const Variant &p_key) const { - OrderedHashMap::ConstElement E; + HashMap::ConstIterator E; if (p_key.get_type() == Variant::STRING_NAME) { const StringName *sn = VariantInternal::get_string_name(&p_key); - E = ((const OrderedHashMap *)&_p->variant_map)->find(sn->operator String()); + E = ((const HashMap *)&_p->variant_map)->find(sn->operator String()); } else { - E = ((const OrderedHashMap *)&_p->variant_map)->find(p_key); + E = ((const HashMap *)&_p->variant_map)->find(p_key); } if (!E) { return Variant(); } - return E.get(); + return E->value; } Variant Dictionary::get(const Variant &p_key, const Variant &p_default) const { @@ -210,9 +210,9 @@ bool Dictionary::recursive_equal(const Dictionary &p_dictionary, int recursion_c return true; } recursion_count++; - for (OrderedHashMap::ConstElement this_E = ((const OrderedHashMap *)&_p->variant_map)->front(); this_E; this_E = this_E.next()) { - OrderedHashMap::ConstElement other_E = ((const OrderedHashMap *)&p_dictionary._p->variant_map)->find(this_E.key()); - if (!other_E || !this_E.value().hash_compare(other_E.value(), recursion_count)) { + for (const KeyValue &this_E : _p->variant_map) { + HashMap::ConstIterator other_E = ((const HashMap *)&p_dictionary._p->variant_map)->find(this_E.key); + if (!other_E || !this_E.value.hash_compare(other_E->value, recursion_count)) { return false; } } @@ -261,9 +261,9 @@ uint32_t Dictionary::recursive_hash(int recursion_count) const { uint32_t h = hash_djb2_one_32(Variant::DICTIONARY); recursion_count++; - for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { - h = hash_djb2_one_32(E.key().recursive_hash(recursion_count), h); - h = hash_djb2_one_32(E.value().recursive_hash(recursion_count), h); + for (const KeyValue &E : _p->variant_map) { + h = hash_djb2_one_32(E.key.recursive_hash(recursion_count), h); + h = hash_djb2_one_32(E.value.recursive_hash(recursion_count), h); } return h; @@ -278,8 +278,8 @@ Array Dictionary::keys() const { varr.resize(size()); int i = 0; - for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { - varr[i] = E.key(); + for (const KeyValue &E : _p->variant_map) { + varr[i] = E.key; i++; } @@ -295,8 +295,8 @@ Array Dictionary::values() const { varr.resize(size()); int i = 0; - for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { - varr[i] = E.get(); + for (const KeyValue &E : _p->variant_map) { + varr[i] = E.value; i++; } @@ -306,16 +306,23 @@ Array Dictionary::values() const { const Variant *Dictionary::next(const Variant *p_key) const { if (p_key == nullptr) { // caller wants to get the first element - if (_p->variant_map.front()) { - return &_p->variant_map.front().key(); + if (_p->variant_map.begin()) { + return &_p->variant_map.begin()->key; } return nullptr; } - OrderedHashMap::Element E = _p->variant_map.find(*p_key); + HashMap::Iterator E = _p->variant_map.find(*p_key); - if (E && E.next()) { - return &E.next().key(); + if (!E) { + return nullptr; + } + + ++E; + + if (E) { + return &E->key; } + return nullptr; } @@ -333,12 +340,12 @@ Dictionary Dictionary::recursive_duplicate(bool p_deep, int recursion_count) con if (p_deep) { recursion_count++; - for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { - n[E.key().recursive_duplicate(true, recursion_count)] = E.value().recursive_duplicate(true, recursion_count); + for (const KeyValue &E : _p->variant_map) { + n[E.key.recursive_duplicate(true, recursion_count)] = E.value.recursive_duplicate(true, recursion_count); } } else { - for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { - n[E.key()] = E.value(); + for (const KeyValue &E : _p->variant_map) { + n[E.key] = E.value; } } -- cgit v1.2.3