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

4 files changed, 75 insertions, 114 deletions

diff --git a/core/object/class_db.cpp b/core/object/class_db.cpp
index 593f27b7cf..d0fcde832b 100644
--- a/core/object/class_db.cpp
+++ b/core/object/class_db.cpp
@@ -90,10 +90,8 @@ bool ClassDB::is_parent_class(const StringName &p_class, const StringName &p_inh
 void ClassDB::get_class_list(List<StringName> *p_classes) {
 	OBJTYPE_RLOCK;
 
-	const StringName *k = nullptr;
-
-	while ((k = classes.next(k))) {
-		p_classes->push_back(*k);
+	for (const KeyValue<StringName, ClassInfo> &E : classes) {
+		p_classes->push_back(E.key);
 	}
 
 	p_classes->sort();
@@ -102,11 +100,9 @@ void ClassDB::get_class_list(List<StringName> *p_classes) {
 void ClassDB::get_inheriters_from_class(const StringName &p_class, List<StringName> *p_classes) {
 	OBJTYPE_RLOCK;
 
-	const StringName *k = nullptr;
-
-	while ((k = classes.next(k))) {
-		if (*k != p_class && _is_parent_class(*k, p_class)) {
-			p_classes->push_back(*k);
+	for (const KeyValue<StringName, ClassInfo> &E : classes) {
+		if (E.key != p_class && _is_parent_class(E.key, p_class)) {
+			p_classes->push_back(E.key);
 		}
 	}
 }
@@ -114,11 +110,9 @@ void ClassDB::get_inheriters_from_class(const StringName &p_class, List<StringNa
 void ClassDB::get_direct_inheriters_from_class(const StringName &p_class, List<StringName> *p_classes) {
 	OBJTYPE_RLOCK;
 
-	const StringName *k = nullptr;
-
-	while ((k = classes.next(k))) {
-		if (*k != p_class && _get_parent_class(*k) == p_class) {
-			p_classes->push_back(*k);
+	for (const KeyValue<StringName, ClassInfo> &E : classes) {
+		if (E.key != p_class && _get_parent_class(E.key) == p_class) {
+			p_classes->push_back(E.key);
 		}
 	}
 }
@@ -172,17 +166,12 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 
 	uint64_t hash = hash_djb2_one_64(HashMapHasherDefault::hash(VERSION_FULL_CONFIG));
 
-	List<StringName> names;
-
-	const StringName *k = nullptr;
+	List<StringName> class_list;
+	ClassDB::get_class_list(&class_list);
+	// Must be alphabetically sorted for hash to compute.
+	class_list.sort_custom<StringName::AlphCompare>();
 
-	while ((k = classes.next(k))) {
-		names.push_back(*k);
-	}
-	//must be alphabetically sorted for hash to compute
-	names.sort_custom<StringName::AlphCompare>();
-
-	for (const StringName &E : names) {
+	for (const StringName &E : class_list) {
 		ClassInfo *t = classes.getptr(E);
 		ERR_FAIL_COND_V_MSG(!t, 0, "Cannot get class '" + String(E) + "'.");
 		if (t->api != p_api || !t->exposed) {
@@ -195,10 +184,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 
 			List<StringName> snames;
 
-			k = nullptr;
-
-			while ((k = t->method_map.next(k))) {
-				String name = k->operator String();
+			for (const KeyValue<StringName, MethodBind *> &F : t->method_map) {
+				String name = F.key.operator String();
 
 				ERR_CONTINUE(name.is_empty());
 
@@ -206,7 +193,7 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 					continue; // Ignore non-virtual methods that start with an underscore
 				}
 
-				snames.push_back(*k);
+				snames.push_back(F.key);
 			}
 
 			snames.sort_custom<StringName::AlphCompare>();
@@ -241,10 +228,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 
 			List<StringName> snames;
 
-			k = nullptr;
-
-			while ((k = t->constant_map.next(k))) {
-				snames.push_back(*k);
+			for (const KeyValue<StringName, int> &F : t->constant_map) {
+				snames.push_back(F.key);
 			}
 
 			snames.sort_custom<StringName::AlphCompare>();
@@ -259,10 +244,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 
 			List<StringName> snames;
 
-			k = nullptr;
-
-			while ((k = t->signal_map.next(k))) {
-				snames.push_back(*k);
+			for (const KeyValue<StringName, MethodInfo> &F : t->signal_map) {
+				snames.push_back(F.key);
 			}
 
 			snames.sort_custom<StringName::AlphCompare>();
@@ -280,10 +263,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 
 			List<StringName> snames;
 
-			k = nullptr;
-
-			while ((k = t->property_setget.next(k))) {
-				snames.push_back(*k);
+			for (const KeyValue<StringName, PropertySetGet> &F : t->property_setget) {
+				snames.push_back(F.key);
 			}
 
 			snames.sort_custom<StringName::AlphCompare>();
@@ -474,10 +455,8 @@ void ClassDB::get_method_list(const StringName &p_class, List<MethodInfo> *p_met
 
 #else
 
-		const StringName *K = nullptr;
-
-		while ((K = type->method_map.next(K))) {
-			MethodBind *m = type->method_map[*K];
+		for (KeyValue<StringName, MethodBind *> &E : type->method_map) {
+			MethodBind *m = E.value;
 			MethodInfo minfo = info_from_bind(m);
 			p_methods->push_back(minfo);
 		}
@@ -603,10 +582,9 @@ void ClassDB::get_integer_constant_list(const StringName &p_class, List<String>
 			p_constants->push_back(E);
 		}
 #else
-		const StringName *K = nullptr;
 
-		while ((K = type->constant_map.next(K))) {
-			p_constants->push_back(*K);
+		for (const KeyValue<StringName, int> &E : type->constant_map) {
+			p_constants->push_back(E.key);
 		}
 
 #endif
@@ -667,12 +645,11 @@ StringName ClassDB::get_integer_constant_enum(const StringName &p_class, const S
 	ClassInfo *type = classes.getptr(p_class);
 
 	while (type) {
-		const StringName *k = nullptr;
-		while ((k = type->enum_map.next(k))) {
-			List<StringName> &constants_list = type->enum_map.get(*k);
+		for (KeyValue<StringName, List<StringName>> &E : type->enum_map) {
+			List<StringName> &constants_list = E.value;
 			const List<StringName>::Element *found = constants_list.find(p_name);
 			if (found) {
-				return *k;
+				return E.key;
 			}
 		}
 
@@ -692,9 +669,8 @@ void ClassDB::get_enum_list(const StringName &p_class, List<StringName> *p_enums
 	ClassInfo *type = classes.getptr(p_class);
 
 	while (type) {
-		const StringName *k = nullptr;
-		while ((k = type->enum_map.next(k))) {
-			p_enums->push_back(*k);
+		for (KeyValue<StringName, List<StringName>> &E : type->enum_map) {
+			p_enums->push_back(E.key);
 		}
 
 		if (p_no_inheritance) {
@@ -800,9 +776,8 @@ void ClassDB::get_signal_list(const StringName &p_class, List<MethodInfo> *p_sig
 	ClassInfo *check = type;
 
 	while (check) {
-		const StringName *S = nullptr;
-		while ((S = check->signal_map.next(S))) {
-			p_signals->push_back(check->signal_map[*S]);
+		for (KeyValue<StringName, MethodInfo> &E : check->signal_map) {
+			p_signals->push_back(E.value);
 		}
 
 		if (p_no_inheritance) {
@@ -1397,10 +1372,8 @@ void ClassDB::add_resource_base_extension(const StringName &p_extension, const S
 }
 
 void ClassDB::get_resource_base_extensions(List<String> *p_extensions) {
-	const StringName *K = nullptr;
-
-	while ((K = resource_base_extensions.next(K))) {
-		p_extensions->push_back(*K);
+	for (const KeyValue<StringName, StringName> &E : resource_base_extensions) {
+		p_extensions->push_back(E.key);
 	}
 }
 
@@ -1409,12 +1382,9 @@ bool ClassDB::is_resource_extension(const StringName &p_extension) {
 }
 
 void ClassDB::get_extensions_for_type(const StringName &p_class, List<String> *p_extensions) {
-	const StringName *K = nullptr;
-
-	while ((K = resource_base_extensions.next(K))) {
-		StringName cmp = resource_base_extensions[*K];
-		if (is_parent_class(p_class, cmp) || is_parent_class(cmp, p_class)) {
-			p_extensions->push_back(*K);
+	for (const KeyValue<StringName, StringName> &E : resource_base_extensions) {
+		if (is_parent_class(p_class, E.value) || is_parent_class(E.value, p_class)) {
+			p_extensions->push_back(E.key);
 		}
 	}
 }
@@ -1556,14 +1526,11 @@ void ClassDB::cleanup_defaults() {
 void ClassDB::cleanup() {
 	//OBJTYPE_LOCK; hah not here
 
-	const StringName *k = nullptr;
-
-	while ((k = classes.next(k))) {
-		ClassInfo &ti = classes[*k];
+	for (KeyValue<StringName, ClassInfo> &E : classes) {
+		ClassInfo &ti = E.value;
 
-		const StringName *m = nullptr;
-		while ((m = ti.method_map.next(m))) {
-			memdelete(ti.method_map[*m]);
+		for (KeyValue<StringName, MethodBind *> &F : ti.method_map) {
+			memdelete(F.value);
 		}
 	}
 	classes.clear();
diff --git a/core/object/object.cpp b/core/object/object.cpp
index 2b62041533..797eecd312 100644
--- a/core/object/object.cpp
+++ b/core/object/object.cpp
@@ -417,9 +417,9 @@ void Object::set(const StringName &p_name, const Variant &p_value, bool *r_valid
 		return;
 
 	} else {
-		OrderedHashMap<StringName, Variant>::Element *E = metadata_properties.getptr(p_name);
-		if (E) {
-			E->get() = p_value;
+		Variant **V = metadata_properties.getptr(p_name);
+		if (V) {
+			**V = p_value;
 			if (r_valid) {
 				*r_valid = true;
 			}
@@ -508,10 +508,10 @@ Variant Object::get(const StringName &p_name, bool *r_valid) const {
 		return ret;
 	}
 
-	const OrderedHashMap<StringName, Variant>::Element *E = metadata_properties.getptr(p_name);
+	const Variant *const *V = metadata_properties.getptr(p_name);
 
-	if (E) {
-		ret = E->get();
+	if (V) {
+		ret = **V;
 		if (r_valid) {
 			*r_valid = true;
 		}
@@ -666,9 +666,9 @@ void Object::get_property_list(List<PropertyInfo> *p_list, bool p_reversed) cons
 		script_instance->get_property_list(p_list);
 	}
 
-	for (OrderedHashMap<StringName, Variant>::ConstElement K = metadata.front(); K; K = K.next()) {
-		PropertyInfo pi = PropertyInfo(K.value().get_type(), "metadata/" + K.key().operator String());
-		if (K.value().get_type() == Variant::OBJECT) {
+	for (const KeyValue<StringName, Variant> &K : metadata) {
+		PropertyInfo pi = PropertyInfo(K.value.get_type(), "metadata/" + K.key.operator String());
+		if (K.value.get_type() == Variant::OBJECT) {
 			pi.hint = PROPERTY_HINT_RESOURCE_TYPE;
 			pi.hint_string = "Resource";
 		}
@@ -944,13 +944,13 @@ void Object::set_meta(const StringName &p_name, const Variant &p_value) {
 		return;
 	}
 
-	OrderedHashMap<StringName, Variant>::Element E = metadata.find(p_name);
+	HashMap<StringName, Variant>::Iterator E = metadata.find(p_name);
 	if (E) {
-		E.value() = p_value;
+		E->value = p_value;
 	} else {
 		ERR_FAIL_COND(!p_name.operator String().is_valid_identifier());
-		E = metadata.insert(p_name, p_value);
-		metadata_properties["metadata/" + p_name.operator String()] = E;
+		Variant *V = &metadata.insert(p_name, p_value)->value;
+		metadata_properties["metadata/" + p_name.operator String()] = V;
 		notify_property_list_changed();
 	}
 }
@@ -993,16 +993,16 @@ Array Object::_get_method_list_bind() const {
 Vector<StringName> Object::_get_meta_list_bind() const {
 	Vector<StringName> _metaret;
 
-	for (OrderedHashMap<StringName, Variant>::ConstElement K = metadata.front(); K; K = K.next()) {
-		_metaret.push_back(K.key());
+	for (const KeyValue<StringName, Variant> &K : metadata) {
+		_metaret.push_back(K.key);
 	}
 
 	return _metaret;
 }
 
 void Object::get_meta_list(List<StringName> *p_list) const {
-	for (OrderedHashMap<StringName, Variant>::ConstElement K = metadata.front(); K; K = K.next()) {
-		p_list->push_back(K.key());
+	for (const KeyValue<StringName, Variant> &K : metadata) {
+		p_list->push_back(K.key);
 	}
 }
 
@@ -1250,21 +1250,18 @@ void Object::get_signal_list(List<MethodInfo> *p_signals) const {
 
 	ClassDB::get_signal_list(get_class_name(), p_signals);
 	//find maybe usersignals?
-	const StringName *S = nullptr;
 
-	while ((S = signal_map.next(S))) {
-		if (!signal_map[*S].user.name.is_empty()) {
+	for (const KeyValue<StringName, SignalData> &E : signal_map) {
+		if (!E.value.user.name.is_empty()) {
 			//user signal
-			p_signals->push_back(signal_map[*S].user);
+			p_signals->push_back(E.value.user);
 		}
 	}
 }
 
 void Object::get_all_signal_connections(List<Connection> *p_connections) const {
-	const StringName *S = nullptr;
-
-	while ((S = signal_map.next(S))) {
-		const SignalData *s = &signal_map[*S];
+	for (const KeyValue<StringName, SignalData> &E : signal_map) {
+		const SignalData *s = &E.value;
 
 		for (int i = 0; i < s->slot_map.size(); i++) {
 			p_connections->push_back(s->slot_map.getv(i).conn);
@@ -1285,10 +1282,9 @@ void Object::get_signal_connection_list(const StringName &p_signal, List<Connect
 
 int Object::get_persistent_signal_connection_count() const {
 	int count = 0;
-	const StringName *S = nullptr;
 
-	while ((S = signal_map.next(S))) {
-		const SignalData *s = &signal_map[*S];
+	for (const KeyValue<StringName, SignalData> &E : signal_map) {
+		const SignalData *s = &E.value;
 
 		for (int i = 0; i < s->slot_map.size(); i++) {
 			if (s->slot_map.getv(i).conn.flags & CONNECT_PERSIST) {
@@ -1866,15 +1862,15 @@ Object::~Object() {
 		_extension_instance = nullptr;
 	}
 
-	const StringName *S = nullptr;
-
 	if (_emitting) {
 		//@todo this may need to actually reach the debugger prioritarily somehow because it may crash before
 		ERR_PRINT("Object " + to_string() + " was freed or unreferenced while a signal is being emitted from it. Try connecting to the signal using 'CONNECT_DEFERRED' flag, or use queue_free() to free the object (if this object is a Node) to avoid this error and potential crashes.");
 	}
 
-	while ((S = signal_map.next(nullptr))) {
-		SignalData *s = &signal_map[*S];
+	while (signal_map.size()) {
+		// Avoid regular iteration so erasing is safe.
+		KeyValue<StringName, SignalData> &E = *signal_map.begin();
+		SignalData *s = &E.value;
 
 		//brute force disconnect for performance
 		int slot_count = s->slot_map.size();
@@ -1884,7 +1880,7 @@ Object::~Object() {
 			slot_list[i].value.conn.callable.get_object()->connections.erase(slot_list[i].value.cE);
 		}
 
-		signal_map.erase(*S);
+		signal_map.erase(E.key);
 	}
 
 	//signals from nodes that connect to this node
diff --git a/core/object/object.h b/core/object/object.h
index c3e3c68b59..00cb73593b 100644
--- a/core/object/object.h
+++ b/core/object/object.h
@@ -39,7 +39,6 @@
 #include "core/templates/hash_map.h"
 #include "core/templates/list.h"
 #include "core/templates/map.h"
-#include "core/templates/ordered_hash_map.h"
 #include "core/templates/safe_refcount.h"
 #include "core/templates/set.h"
 #include "core/templates/vmap.h"
@@ -515,8 +514,8 @@ private:
 #endif
 	ScriptInstance *script_instance = nullptr;
 	Variant script; // Reference does not exist yet, store it in a Variant.
-	OrderedHashMap<StringName, Variant> metadata;
-	HashMap<StringName, OrderedHashMap<StringName, Variant>::Element> metadata_properties;
+	HashMap<StringName, Variant> metadata;
+	HashMap<StringName, Variant *> metadata_properties;
 	mutable StringName _class_name;
 	mutable const StringName *_class_ptr = nullptr;
 
diff --git a/core/object/script_language.cpp b/core/object/script_language.cpp
index a5d25bf533..c1036e3413 100644
--- a/core/object/script_language.cpp
+++ b/core/object/script_language.cpp
@@ -253,10 +253,9 @@ StringName ScriptServer::get_global_class_native_base(const String &p_class) {
 }
 
 void ScriptServer::get_global_class_list(List<StringName> *r_global_classes) {
-	const StringName *K = nullptr;
 	List<StringName> classes;
-	while ((K = global_classes.next(K))) {
-		classes.push_back(*K);
+	for (const KeyValue<StringName, GlobalScriptClass> &E : global_classes) {
+		classes.push_back(E.key);
 	}
 	classes.sort_custom<StringName::AlphCompare>();
 	for (const StringName &E : classes) {