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

3 files changed, 46 insertions, 51 deletions

diff --git a/tests/core/object/test_class_db.h b/tests/core/object/test_class_db.h
index 5cf5403a50..2e316a7d95 100644
--- a/tests/core/object/test_class_db.h
+++ b/tests/core/object/test_class_db.h
@@ -173,7 +173,7 @@ struct NamesCache {
 	}
 };
 
-typedef OrderedHashMap<StringName, ExposedClass> ExposedClasses;
+typedef HashMap<StringName, ExposedClass> ExposedClasses;
 
 struct Context {
 	Vector<StringName> enum_types;
@@ -183,13 +183,13 @@ struct Context {
 	NamesCache names_cache;
 
 	const ExposedClass *find_exposed_class(const StringName &p_name) const {
-		ExposedClasses::ConstElement elem = exposed_classes.find(p_name);
-		return elem ? &elem.value() : nullptr;
+		ExposedClasses::ConstIterator elem = exposed_classes.find(p_name);
+		return elem ? &elem->value : nullptr;
 	}
 
 	const ExposedClass *find_exposed_class(const TypeReference &p_type_ref) const {
-		ExposedClasses::ConstElement elem = exposed_classes.find(p_type_ref.name);
-		return elem ? &elem.value() : nullptr;
+		ExposedClasses::ConstIterator elem = exposed_classes.find(p_type_ref.name);
+		return elem ? &elem->value : nullptr;
 	}
 
 	bool has_type(const TypeReference &p_type_ref) const {
@@ -676,12 +676,11 @@ void add_exposed_classes(Context &r_context) {
 		// Add signals
 
 		const HashMap<StringName, MethodInfo> &signal_map = class_info->signal_map;
-		const StringName *k = nullptr;
 
-		while ((k = signal_map.next(k))) {
+		for (const KeyValue<StringName, MethodInfo> &K : signal_map) {
 			SignalData signal;
 
-			const MethodInfo &method_info = signal_map.get(*k);
+			const MethodInfo &method_info = signal_map.get(K.key);
 
 			signal.name = method_info.name;
 
@@ -734,14 +733,12 @@ void add_exposed_classes(Context &r_context) {
 		ClassDB::get_integer_constant_list(class_name, &constants, true);
 
 		const HashMap<StringName, List<StringName>> &enum_map = class_info->enum_map;
-		k = nullptr;
 
-		while ((k = enum_map.next(k))) {
+		for (const KeyValue<StringName, List<StringName>> &K : enum_map) {
 			EnumData enum_;
-			enum_.name = *k;
+			enum_.name = K.key;
 
-			const List<StringName> &enum_constants = enum_map.get(*k);
-			for (const StringName &E : enum_constants) {
+			for (const StringName &E : K.value) {
 				const StringName &constant_name = E;
 				TEST_FAIL_COND(String(constant_name).find("::") != -1,
 						"Enum constant contains '::', check bindings to remove the scope: '",
@@ -760,7 +757,7 @@ void add_exposed_classes(Context &r_context) {
 
 			exposed_class.enums.push_back(enum_);
 
-			r_context.enum_types.push_back(String(class_name) + "." + String(*k));
+			r_context.enum_types.push_back(String(class_name) + "." + String(K.key));
 		}
 
 		for (const String &E : constants) {
@@ -850,8 +847,8 @@ TEST_SUITE("[ClassDB]") {
 			TEST_FAIL_COND(object_class->base != StringName(),
 					"Object class derives from another class: '", object_class->base, "'.");
 
-			for (ExposedClasses::Element E = context.exposed_classes.front(); E; E = E.next()) {
-				validate_class(context, E.value());
+			for (const KeyValue<StringName, ExposedClass> &E : context.exposed_classes) {
+				validate_class(context, E.value);
 			}
 		}
 	}
diff --git a/tests/core/templates/test_ordered_hash_map.h b/tests/core/templates/test_hash_map.h
index 08c5c9b72a..7a3d5f5d47 100644
--- a/tests/core/templates/test_ordered_hash_map.h
+++ b/tests/core/templates/test_hash_map.h
@@ -1,5 +1,5 @@
 /*************************************************************************/
-/*  test_ordered_hash_map.h                                              */
+/*  test_hash_map.h                                                      */
 /*************************************************************************/
 /*                       This file is part of:                           */
 /*                           GODOT ENGINE                                */
@@ -28,56 +28,53 @@
 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                */
 /*************************************************************************/
 
-#ifndef TEST_ORDERED_HASH_MAP_H
-#define TEST_ORDERED_HASH_MAP_H
+#ifndef TEST_HASH_MAP_H
+#define TEST_HASH_MAP_H
 
-#include "core/templates/ordered_hash_map.h"
+#include "core/templates/hash_map.h"
 
 #include "tests/test_macros.h"
 
-namespace TestOrderedHashMap {
+namespace TestHashMap {
 
-TEST_CASE("[OrderedHashMap] Insert element") {
-	OrderedHashMap<int, int> map;
-	OrderedHashMap<int, int>::Element e = map.insert(42, 84);
+TEST_CASE("[HashMap] Insert element") {
+	HashMap<int, int> map;
+	HashMap<int, int>::Iterator e = map.insert(42, 84);
 
 	CHECK(e);
-	CHECK(e.key() == 42);
-	CHECK(e.get() == 84);
-	CHECK(e.value() == 84);
+	CHECK(e->key == 42);
+	CHECK(e->value == 84);
 	CHECK(map[42] == 84);
 	CHECK(map.has(42));
 	CHECK(map.find(42));
 }
 
-TEST_CASE("[OrderedHashMap] Overwrite element") {
-	OrderedHashMap<int, int> map;
+TEST_CASE("[HashMap] Overwrite element") {
+	HashMap<int, int> map;
 	map.insert(42, 84);
 	map.insert(42, 1234);
 
 	CHECK(map[42] == 1234);
 }
 
-TEST_CASE("[OrderedHashMap] Erase via element") {
-	OrderedHashMap<int, int> map;
-	OrderedHashMap<int, int>::Element e = map.insert(42, 84);
-
-	map.erase(e);
-	CHECK(!e);
+TEST_CASE("[HashMap] Erase via element") {
+	HashMap<int, int> map;
+	HashMap<int, int>::Iterator e = map.insert(42, 84);
+	map.remove(e);
 	CHECK(!map.has(42));
 	CHECK(!map.find(42));
 }
 
-TEST_CASE("[OrderedHashMap] Erase via key") {
-	OrderedHashMap<int, int> map;
+TEST_CASE("[HashMap] Erase via key") {
+	HashMap<int, int> map;
 	map.insert(42, 84);
 	map.erase(42);
 	CHECK(!map.has(42));
 	CHECK(!map.find(42));
 }
 
-TEST_CASE("[OrderedHashMap] Size") {
-	OrderedHashMap<int, int> map;
+TEST_CASE("[HashMap] Size") {
+	HashMap<int, int> map;
 	map.insert(42, 84);
 	map.insert(123, 84);
 	map.insert(123, 84);
@@ -87,8 +84,8 @@ TEST_CASE("[OrderedHashMap] Size") {
 	CHECK(map.size() == 4);
 }
 
-TEST_CASE("[OrderedHashMap] Iteration") {
-	OrderedHashMap<int, int> map;
+TEST_CASE("[HashMap] Iteration") {
+	HashMap<int, int> map;
 	map.insert(42, 84);
 	map.insert(123, 12385);
 	map.insert(0, 12934);
@@ -102,34 +99,35 @@ TEST_CASE("[OrderedHashMap] Iteration") {
 	expected.push_back(Pair<int, int>(123485, 1238888));
 
 	int idx = 0;
-	for (OrderedHashMap<int, int>::Element E = map.front(); E; E = E.next()) {
-		CHECK(expected[idx] == Pair<int, int>(E.key(), E.value()));
+	for (const KeyValue<int, int> &E : map) {
+		CHECK(expected[idx] == Pair<int, int>(E.key, E.value));
 		++idx;
 	}
 }
 
-TEST_CASE("[OrderedHashMap] Const iteration") {
-	OrderedHashMap<int, int> map;
+TEST_CASE("[HashMap] Const iteration") {
+	HashMap<int, int> map;
 	map.insert(42, 84);
 	map.insert(123, 12385);
 	map.insert(0, 12934);
 	map.insert(123485, 1238888);
 	map.insert(123, 111111);
 
-	const OrderedHashMap<int, int> const_map = map;
+	const HashMap<int, int> const_map = map;
 
 	Vector<Pair<int, int>> expected;
 	expected.push_back(Pair<int, int>(42, 84));
 	expected.push_back(Pair<int, int>(123, 111111));
 	expected.push_back(Pair<int, int>(0, 12934));
 	expected.push_back(Pair<int, int>(123485, 1238888));
+	expected.push_back(Pair<int, int>(123, 111111));
 
 	int idx = 0;
-	for (OrderedHashMap<int, int>::ConstElement E = const_map.front(); E; E = E.next()) {
-		CHECK(expected[idx] == Pair<int, int>(E.key(), E.value()));
+	for (const KeyValue<int, int> &E : const_map) {
+		CHECK(expected[idx] == Pair<int, int>(E.key, E.value));
 		++idx;
 	}
 }
-} // namespace TestOrderedHashMap
+} // namespace TestHashMap
 
-#endif // TEST_ORDERED_HASH_MAP_H
+#endif // TEST_HASH_MAP_H
diff --git a/tests/test_main.cpp b/tests/test_main.cpp
index be51afd83c..4cdc5ea1fa 100644
--- a/tests/test_main.cpp
+++ b/tests/test_main.cpp
@@ -59,10 +59,10 @@
 #include "tests/core/string/test_string.h"
 #include "tests/core/string/test_translation.h"
 #include "tests/core/templates/test_command_queue.h"
+#include "tests/core/templates/test_hash_map.h"
 #include "tests/core/templates/test_list.h"
 #include "tests/core/templates/test_local_vector.h"
 #include "tests/core/templates/test_lru.h"
-#include "tests/core/templates/test_ordered_hash_map.h"
 #include "tests/core/templates/test_paged_array.h"
 #include "tests/core/templates/test_vector.h"
 #include "tests/core/test_crypto.h"