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<>

2 files changed, 18 insertions, 26 deletions

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<String, GDMonoAssembly *> &domain_assemblies = assemblies[domain_id];
 
-	const String *k = nullptr;
-	while ((k = domain_assemblies.next(k))) {
-		GDMonoAssembly *assembly = domain_assemblies.get(*k);
+	for (const KeyValue<String, GDMonoAssembly *> &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<String, GDMonoAssembly *> &domain_assemblies = assemblies[domain_id];
 
-	const String *k = nullptr;
-	while ((k = domain_assemblies.next(k))) {
-		GDMonoAssembly *assembly = domain_assemblies.get(*k);
+	for (const KeyValue<String, GDMonoAssembly *> &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<String, GDMonoAssembly *> &domain_assemblies = assemblies[p_domain_id];
 
-	const String *k = nullptr;
-	while ((k = domain_assemblies.next(k))) {
-		memdelete(domain_assemblies.get(*k));
+	for (const KeyValue<String, GDMonoAssembly *> &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<String, GDMonoAssembly *> &domain_assemblies = assemblies.get(*k);
+		for (const KeyValue<int32_t, HashMap<String, GDMonoAssembly *>> &E : assemblies) {
+			const HashMap<String, GDMonoAssembly *> &domain_assemblies = E.value;
 
-			const String *kk = nullptr;
-			while ((kk = domain_assemblies.next(kk))) {
-				memdelete(domain_assemblies.get(*kk));
+			for (const KeyValue<String, GDMonoAssembly *> &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<MethodKey, GDMonoMethod *> &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<GDMonoMethod *> deleted_methods;
 		deleted_methods.resize(methods.size());
 
-		const MethodKey *k = nullptr;
-		while ((k = methods.next(k))) {
-			GDMonoMethod *method = methods.get(*k);
+		for (const KeyValue<MethodKey, GDMonoMethod *> &E : methods) {
+			GDMonoMethod *method = E.value;
 
 			if (method) {
 				for (int i = 0; i < offset; i++) {