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, 35 insertions, 35 deletions

diff --git a/core/input/input.cpp b/core/input/input.cpp
index 40cea2cd80..3a2e50a674 100644
--- a/core/input/input.cpp
+++ b/core/input/input.cpp
@@ -636,21 +636,21 @@ void Input::_parse_input_event_impl(const Ref<InputEvent> &p_event, bool p_is_em
 		}
 	}
 
-	for (OrderedHashMap<StringName, InputMap::Action>::ConstElement E = InputMap::get_singleton()->get_action_map().front(); E; E = E.next()) {
-		if (InputMap::get_singleton()->event_is_action(p_event, E.key())) {
+	for (const KeyValue<StringName, InputMap::Action> &E : InputMap::get_singleton()->get_action_map()) {
+		if (InputMap::get_singleton()->event_is_action(p_event, E.key)) {
 			// If not echo and action pressed state has changed
-			if (!p_event->is_echo() && is_action_pressed(E.key(), false) != p_event->is_action_pressed(E.key())) {
+			if (!p_event->is_echo() && is_action_pressed(E.key, false) != p_event->is_action_pressed(E.key)) {
 				Action action;
 				action.physics_frame = Engine::get_singleton()->get_physics_frames();
 				action.process_frame = Engine::get_singleton()->get_process_frames();
-				action.pressed = p_event->is_action_pressed(E.key());
+				action.pressed = p_event->is_action_pressed(E.key);
 				action.strength = 0.0f;
 				action.raw_strength = 0.0f;
-				action.exact = InputMap::get_singleton()->event_is_action(p_event, E.key(), true);
-				action_state[E.key()] = action;
+				action.exact = InputMap::get_singleton()->event_is_action(p_event, E.key, true);
+				action_state[E.key] = action;
 			}
-			action_state[E.key()].strength = p_event->get_action_strength(E.key());
-			action_state[E.key()].raw_strength = p_event->get_action_raw_strength(E.key());
+			action_state[E.key].strength = p_event->get_action_strength(E.key);
+			action_state[E.key].raw_strength = p_event->get_action_raw_strength(E.key);
 		}
 	}
 
diff --git a/core/input/input_map.cpp b/core/input/input_map.cpp
index ab94c00999..51c1cf9608 100644
--- a/core/input/input_map.cpp
+++ b/core/input/input_map.cpp
@@ -119,8 +119,8 @@ List<StringName> InputMap::get_actions() const {
 		return actions;
 	}
 
-	for (OrderedHashMap<StringName, Action>::Element E = input_map.front(); E; E = E.next()) {
-		actions.push_back(E.key());
+	for (const KeyValue<StringName, Action> &E : input_map) {
+		actions.push_back(E.key);
 	}
 
 	return actions;
@@ -203,12 +203,12 @@ Array InputMap::_action_get_events(const StringName &p_action) {
 }
 
 const List<Ref<InputEvent>> *InputMap::action_get_events(const StringName &p_action) {
-	const OrderedHashMap<StringName, Action>::Element E = input_map.find(p_action);
+	HashMap<StringName, Action>::Iterator E = input_map.find(p_action);
 	if (!E) {
 		return nullptr;
 	}
 
-	return &E.get().inputs;
+	return &E->value.inputs;
 }
 
 bool InputMap::event_is_action(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match) const {
@@ -216,7 +216,7 @@ bool InputMap::event_is_action(const Ref<InputEvent> &p_event, const StringName
 }
 
 bool InputMap::event_get_action_status(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match, bool *r_pressed, float *r_strength, float *r_raw_strength) const {
-	OrderedHashMap<StringName, Action>::Element E = input_map.find(p_action);
+	HashMap<StringName, Action>::Iterator E = input_map.find(p_action);
 	ERR_FAIL_COND_V_MSG(!E, false, suggest_actions(p_action));
 
 	Ref<InputEventAction> input_event_action = p_event;
@@ -235,11 +235,11 @@ bool InputMap::event_get_action_status(const Ref<InputEvent> &p_event, const Str
 		return input_event_action->get_action() == p_action;
 	}
 
-	List<Ref<InputEvent>>::Element *event = _find_event(E.get(), p_event, p_exact_match, r_pressed, r_strength, r_raw_strength);
+	List<Ref<InputEvent>>::Element *event = _find_event(E->value, p_event, p_exact_match, r_pressed, r_strength, r_raw_strength);
 	return event != nullptr;
 }
 
-const OrderedHashMap<StringName, InputMap::Action> &InputMap::get_action_map() const {
+const HashMap<StringName, InputMap::Action> &InputMap::get_action_map() const {
 	return input_map;
 }
 
@@ -360,7 +360,7 @@ String InputMap::get_builtin_display_name(const String &p_name) const {
 	return p_name;
 }
 
-const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins() {
+const HashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins() {
 	// Return cache if it has already been built.
 	if (default_builtin_cache.size()) {
 		return default_builtin_cache;
@@ -686,19 +686,19 @@ const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins() {
 	return default_builtin_cache;
 }
 
-const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with_feature_overrides_applied() {
+const HashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with_feature_overrides_applied() {
 	if (default_builtin_with_overrides_cache.size() > 0) {
 		return default_builtin_with_overrides_cache;
 	}
 
-	OrderedHashMap<String, List<Ref<InputEvent>>> builtins = get_builtins();
+	HashMap<String, List<Ref<InputEvent>>> builtins = get_builtins();
 
 	// Get a list of all built in inputs which are valid overrides for the OS
 	// Key = builtin name (e.g. ui_accept)
 	// Value = override/feature names (e.g. macos, if it was defined as "ui_accept.macos" and the platform supports that feature)
 	Map<String, Vector<String>> builtins_with_overrides;
-	for (OrderedHashMap<String, List<Ref<InputEvent>>>::Element E = builtins.front(); E; E = E.next()) {
-		String fullname = E.key();
+	for (const KeyValue<String, List<Ref<InputEvent>>> &E : builtins) {
+		String fullname = E.key;
 
 		Vector<String> split = fullname.split(".");
 		String name = split[0];
@@ -709,8 +709,8 @@ const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with
 		}
 	}
 
-	for (OrderedHashMap<String, List<Ref<InputEvent>>>::Element E = builtins.front(); E; E = E.next()) {
-		String fullname = E.key();
+	for (const KeyValue<String, List<Ref<InputEvent>>> &E : builtins) {
+		String fullname = E.key;
 
 		Vector<String> split = fullname.split(".");
 		String name = split[0];
@@ -726,22 +726,22 @@ const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with
 			continue;
 		}
 
-		default_builtin_with_overrides_cache.insert(name, E.value());
+		default_builtin_with_overrides_cache.insert(name, E.value);
 	}
 
 	return default_builtin_with_overrides_cache;
 }
 
 void InputMap::load_default() {
-	OrderedHashMap<String, List<Ref<InputEvent>>> builtins = get_builtins_with_feature_overrides_applied();
+	HashMap<String, List<Ref<InputEvent>>> builtins = get_builtins_with_feature_overrides_applied();
 
-	for (OrderedHashMap<String, List<Ref<InputEvent>>>::Element E = builtins.front(); E; E = E.next()) {
-		String name = E.key();
+	for (const KeyValue<String, List<Ref<InputEvent>>> &E : builtins) {
+		String name = E.key;
 
 		add_action(name);
 
-		List<Ref<InputEvent>> inputs = E.get();
-		for (List<Ref<InputEvent>>::Element *I = inputs.front(); I; I = I->next()) {
+		const List<Ref<InputEvent>> &inputs = E.value;
+		for (const List<Ref<InputEvent>>::Element *I = inputs.front(); I; I = I->next()) {
 			Ref<InputEventKey> iek = I->get();
 
 			// For the editor, only add keyboard actions.
diff --git a/core/input/input_map.h b/core/input/input_map.h
index 79b4d1038f..2400a4a3f7 100644
--- a/core/input/input_map.h
+++ b/core/input/input_map.h
@@ -34,7 +34,7 @@
 #include "core/input/input_event.h"
 #include "core/object/class_db.h"
 #include "core/object/object.h"
-#include "core/templates/ordered_hash_map.h"
+#include "core/templates/hash_map.h"
 
 class InputMap : public Object {
 	GDCLASS(InputMap, Object);
@@ -54,9 +54,9 @@ public:
 private:
 	static InputMap *singleton;
 
-	mutable OrderedHashMap<StringName, Action> input_map;
-	OrderedHashMap<String, List<Ref<InputEvent>>> default_builtin_cache;
-	OrderedHashMap<String, List<Ref<InputEvent>>> default_builtin_with_overrides_cache;
+	mutable HashMap<StringName, Action> input_map;
+	HashMap<String, List<Ref<InputEvent>>> default_builtin_cache;
+	HashMap<String, List<Ref<InputEvent>>> default_builtin_with_overrides_cache;
 
 	List<Ref<InputEvent>>::Element *_find_event(Action &p_action, const Ref<InputEvent> &p_event, bool p_exact_match = false, bool *r_pressed = nullptr, float *r_strength = nullptr, float *r_raw_strength = nullptr) const;
 
@@ -85,7 +85,7 @@ public:
 	bool event_is_action(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match = false) const;
 	bool event_get_action_status(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match = false, bool *r_pressed = nullptr, float *r_strength = nullptr, float *r_raw_strength = nullptr) const;
 
-	const OrderedHashMap<StringName, Action> &get_action_map() const;
+	const HashMap<StringName, Action> &get_action_map() const;
 	void load_from_project_settings();
 	void load_default();
 
@@ -93,8 +93,8 @@ public:
 
 	String get_builtin_display_name(const String &p_name) const;
 	// Use an Ordered Map so insertion order is preserved. We want the elements to be 'grouped' somewhat.
-	const OrderedHashMap<String, List<Ref<InputEvent>>> &get_builtins();
-	const OrderedHashMap<String, List<Ref<InputEvent>>> &get_builtins_with_feature_overrides_applied();
+	const HashMap<String, List<Ref<InputEvent>>> &get_builtins();
+	const HashMap<String, List<Ref<InputEvent>>> &get_builtins_with_feature_overrides_applied();
 
 	InputMap();
 	~InputMap();