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<> --- modules/mono/mono_gd/gd_mono.cpp | 25 ++++++++++--------------- modules/mono/mono_gd/gd_mono_class.cpp | 19 ++++++++----------- 2 files changed, 18 insertions(+), 26 deletions(-) (limited to 'modules/mono/mono_gd') diff --git a/modules/mono/mono_gd/gd_mono.cpp b/modules/mono/mono_gd/gd_mono.cpp index e98ce8f6c1..39a8ef22b7 100644 --- a/modules/mono/mono_gd/gd_mono.cpp +++ b/modules/mono/mono_gd/gd_mono.cpp @@ -1167,9 +1167,8 @@ GDMonoClass *GDMono::get_class(MonoClass *p_raw_class) { int32_t domain_id = mono_domain_get_id(mono_domain_get()); HashMap &domain_assemblies = assemblies[domain_id]; - const String *k = nullptr; - while ((k = domain_assemblies.next(k))) { - GDMonoAssembly *assembly = domain_assemblies.get(*k); + for (const KeyValue &E : domain_assemblies) { + GDMonoAssembly *assembly = E.value; if (assembly->get_image() == image) { GDMonoClass *klass = assembly->get_class(p_raw_class); if (klass) { @@ -1190,9 +1189,8 @@ GDMonoClass *GDMono::get_class(const StringName &p_namespace, const StringName & int32_t domain_id = mono_domain_get_id(mono_domain_get()); HashMap &domain_assemblies = assemblies[domain_id]; - const String *k = nullptr; - while ((k = domain_assemblies.next(k))) { - GDMonoAssembly *assembly = domain_assemblies.get(*k); + for (const KeyValue &E : domain_assemblies) { + GDMonoAssembly *assembly = E.value; klass = assembly->get_class(p_namespace, p_name); if (klass) { return klass; @@ -1205,9 +1203,8 @@ GDMonoClass *GDMono::get_class(const StringName &p_namespace, const StringName & void GDMono::_domain_assemblies_cleanup(int32_t p_domain_id) { HashMap &domain_assemblies = assemblies[p_domain_id]; - const String *k = nullptr; - while ((k = domain_assemblies.next(k))) { - memdelete(domain_assemblies.get(*k)); + for (const KeyValue &E : domain_assemblies) { + memdelete(E.value); } assemblies.erase(p_domain_id); @@ -1298,13 +1295,11 @@ GDMono::~GDMono() { // Leave the rest to 'mono_jit_cleanup' #endif - const int32_t *k = nullptr; - while ((k = assemblies.next(k))) { - HashMap &domain_assemblies = assemblies.get(*k); + for (const KeyValue> &E : assemblies) { + const HashMap &domain_assemblies = E.value; - const String *kk = nullptr; - while ((kk = domain_assemblies.next(kk))) { - memdelete(domain_assemblies.get(*kk)); + for (const KeyValue &F : domain_assemblies) { + memdelete(F.value); } } assemblies.clear(); diff --git a/modules/mono/mono_gd/gd_mono_class.cpp b/modules/mono/mono_gd/gd_mono_class.cpp index 3fc0f16e05..daf70443e9 100644 --- a/modules/mono/mono_gd/gd_mono_class.cpp +++ b/modules/mono/mono_gd/gd_mono_class.cpp @@ -247,7 +247,7 @@ void GDMonoClass::fetch_methods_with_godot_api_checks(GDMonoClass *p_native_base if (existing_method) { memdelete(*existing_method); // Must delete old one } - methods.set(key, method); + methods.insert(key, method); break; } @@ -266,11 +266,9 @@ void GDMonoClass::fetch_methods_with_godot_api_checks(GDMonoClass *p_native_base GDMonoMethod *GDMonoClass::get_fetched_method_unknown_params(const StringName &p_name) { ERR_FAIL_COND_V(!methods_fetched, nullptr); - const MethodKey *k = nullptr; - - while ((k = methods.next(k))) { - if (k->name == p_name) { - return methods.get(*k); + for (const KeyValue &E : methods) { + if (E.key.name == p_name) { + return E.value; } } @@ -307,7 +305,7 @@ GDMonoMethod *GDMonoClass::get_method(const StringName &p_name, uint16_t p_param if (raw_method) { GDMonoMethod *method = memnew(GDMonoMethod(p_name, raw_method)); - methods.set(key, method); + methods.insert(key, method); return method; } @@ -342,7 +340,7 @@ GDMonoMethod *GDMonoClass::get_method(MonoMethod *p_raw_method, const StringName } GDMonoMethod *method = memnew(GDMonoMethod(p_name, p_raw_method)); - methods.set(key, method); + methods.insert(key, method); return method; } @@ -549,9 +547,8 @@ GDMonoClass::~GDMonoClass() { Vector deleted_methods; deleted_methods.resize(methods.size()); - const MethodKey *k = nullptr; - while ((k = methods.next(k))) { - GDMonoMethod *method = methods.get(*k); + for (const KeyValue &E : methods) { + GDMonoMethod *method = E.value; if (method) { for (int i = 0; i < offset; i++) { -- cgit v1.2.3