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

diff --git a/editor/plugins/node_3d_editor_gizmos.h b/editor/plugins/node_3d_editor_gizmos.h
index f859ceda3b..4df329a2c5 100644
--- a/editor/plugins/node_3d_editor_gizmos.h
+++ b/editor/plugins/node_3d_editor_gizmos.h
@@ -31,8 +31,8 @@
 #ifndef NODE_3D_EDITOR_GIZMOS_H
 #define NODE_3D_EDITOR_GIZMOS_H
 
+#include "core/templates/hash_map.h"
 #include "core/templates/local_vector.h"
-#include "core/templates/ordered_hash_map.h"
 #include "scene/3d/camera_3d.h"
 #include "scene/3d/node_3d.h"
 #include "scene/3d/skeleton_3d.h"
diff --git a/editor/plugins/script_editor_plugin.cpp b/editor/plugins/script_editor_plugin.cpp
index 5240fdf836..8d29e04eec 100644
--- a/editor/plugins/script_editor_plugin.cpp
+++ b/editor/plugins/script_editor_plugin.cpp
@@ -119,9 +119,9 @@ void EditorStandardSyntaxHighlighter::_update_cache() {
 	}
 
 	/* Autoloads. */
-	OrderedHashMap<StringName, ProjectSettings::AutoloadInfo> autoloads = ProjectSettings::get_singleton()->get_autoload_list();
-	for (OrderedHashMap<StringName, ProjectSettings::AutoloadInfo>::Element E = autoloads.front(); E; E = E.next()) {
-		const ProjectSettings::AutoloadInfo &info = E.value();
+	HashMap<StringName, ProjectSettings::AutoloadInfo> autoloads = ProjectSettings::get_singleton()->get_autoload_list();
+	for (const KeyValue<StringName, ProjectSettings::AutoloadInfo> &E : autoloads) {
+		const ProjectSettings::AutoloadInfo &info = E.value;
 		if (info.is_singleton) {
 			highlighter->add_keyword_color(info.name, usertype_color);
 		}
diff --git a/editor/plugins/theme_editor_plugin.cpp b/editor/plugins/theme_editor_plugin.cpp
index 87f8c4b165..41a599e933 100644
--- a/editor/plugins/theme_editor_plugin.cpp
+++ b/editor/plugins/theme_editor_plugin.cpp
@@ -2339,8 +2339,8 @@ void ThemeTypeEditor::_update_type_list_debounced() {
 	update_debounce_timer->start();
 }
 
-OrderedHashMap<StringName, bool> ThemeTypeEditor::_get_type_items(String p_type_name, void (Theme::*get_list_func)(StringName, List<StringName> *) const, bool include_default) {
-	OrderedHashMap<StringName, bool> items;
+HashMap<StringName, bool> ThemeTypeEditor::_get_type_items(String p_type_name, void (Theme::*get_list_func)(StringName, List<StringName> *) const, bool include_default) {
+	HashMap<StringName, bool> items;
 	List<StringName> names;
 
 	if (include_default) {
@@ -2367,12 +2367,12 @@ OrderedHashMap<StringName, bool> ThemeTypeEditor::_get_type_items(String p_type_
 	}
 
 	List<StringName> keys;
-	for (OrderedHashMap<StringName, bool>::Element E = items.front(); E; E = E.next()) {
-		keys.push_back(E.key());
+	for (const KeyValue<StringName, bool> &E : items) {
+		keys.push_back(E.key);
 	}
 	keys.sort_custom<StringName::AlphCompare>();
 
-	OrderedHashMap<StringName, bool> ordered_items;
+	HashMap<StringName, bool> ordered_items;
 	for (const StringName &E : keys) {
 		ordered_items[E] = items[E];
 	}
@@ -2464,18 +2464,18 @@ void ThemeTypeEditor::_update_type_items() {
 			color_items_list->remove_child(node);
 		}
 
-		OrderedHashMap<StringName, bool> color_items = _get_type_items(edited_type, &Theme::get_color_list, show_default);
-		for (OrderedHashMap<StringName, bool>::Element E = color_items.front(); E; E = E.next()) {
-			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_COLOR, E.key(), E.get());
+		HashMap<StringName, bool> color_items = _get_type_items(edited_type, &Theme::get_color_list, show_default);
+		for (const KeyValue<StringName, bool> &E : color_items) {
+			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_COLOR, E.key, E.value);
 			ColorPickerButton *item_editor = memnew(ColorPickerButton);
 			item_editor->set_h_size_flags(SIZE_EXPAND_FILL);
 			item_control->add_child(item_editor);
 
-			if (E.get()) {
-				item_editor->set_pick_color(edited_theme->get_color(E.key(), edited_type));
-				item_editor->connect("color_changed", callable_mp(this, &ThemeTypeEditor::_color_item_changed), varray(E.key()));
+			if (E.value) {
+				item_editor->set_pick_color(edited_theme->get_color(E.key, edited_type));
+				item_editor->connect("color_changed", callable_mp(this, &ThemeTypeEditor::_color_item_changed), varray(E.key));
 			} else {
-				item_editor->set_pick_color(Theme::get_default()->get_color(E.key(), edited_type));
+				item_editor->set_pick_color(Theme::get_default()->get_color(E.key, edited_type));
 				item_editor->set_disabled(true);
 			}
 
@@ -2492,9 +2492,9 @@ void ThemeTypeEditor::_update_type_items() {
 			constant_items_list->remove_child(node);
 		}
 
-		OrderedHashMap<StringName, bool> constant_items = _get_type_items(edited_type, &Theme::get_constant_list, show_default);
-		for (OrderedHashMap<StringName, bool>::Element E = constant_items.front(); E; E = E.next()) {
-			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_CONSTANT, E.key(), E.get());
+		HashMap<StringName, bool> constant_items = _get_type_items(edited_type, &Theme::get_constant_list, show_default);
+		for (const KeyValue<StringName, bool> &E : constant_items) {
+			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_CONSTANT, E.key, E.value);
 			SpinBox *item_editor = memnew(SpinBox);
 			item_editor->set_h_size_flags(SIZE_EXPAND_FILL);
 			item_editor->set_min(-100000);
@@ -2504,11 +2504,11 @@ void ThemeTypeEditor::_update_type_items() {
 			item_editor->set_allow_greater(true);
 			item_control->add_child(item_editor);
 
-			if (E.get()) {
-				item_editor->set_value(edited_theme->get_constant(E.key(), edited_type));
-				item_editor->connect("value_changed", callable_mp(this, &ThemeTypeEditor::_constant_item_changed), varray(E.key()));
+			if (E.value) {
+				item_editor->set_value(edited_theme->get_constant(E.key, edited_type));
+				item_editor->connect("value_changed", callable_mp(this, &ThemeTypeEditor::_constant_item_changed), varray(E.key));
 			} else {
-				item_editor->set_value(Theme::get_default()->get_constant(E.key(), edited_type));
+				item_editor->set_value(Theme::get_default()->get_constant(E.key, edited_type));
 				item_editor->set_editable(false);
 			}
 
@@ -2525,25 +2525,25 @@ void ThemeTypeEditor::_update_type_items() {
 			font_items_list->remove_child(node);
 		}
 
-		OrderedHashMap<StringName, bool> font_items = _get_type_items(edited_type, &Theme::get_font_list, show_default);
-		for (OrderedHashMap<StringName, bool>::Element E = font_items.front(); E; E = E.next()) {
-			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_FONT, E.key(), E.get());
+		HashMap<StringName, bool> font_items = _get_type_items(edited_type, &Theme::get_font_list, show_default);
+		for (const KeyValue<StringName, bool> &E : font_items) {
+			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_FONT, E.key, E.value);
 			EditorResourcePicker *item_editor = memnew(EditorResourcePicker);
 			item_editor->set_h_size_flags(SIZE_EXPAND_FILL);
 			item_editor->set_base_type("Font");
 			item_control->add_child(item_editor);
 
-			if (E.get()) {
-				if (edited_theme->has_font(E.key(), edited_type)) {
-					item_editor->set_edited_resource(edited_theme->get_font(E.key(), edited_type));
+			if (E.value) {
+				if (edited_theme->has_font(E.key, edited_type)) {
+					item_editor->set_edited_resource(edited_theme->get_font(E.key, edited_type));
 				} else {
 					item_editor->set_edited_resource(Ref<Resource>());
 				}
 				item_editor->connect("resource_selected", callable_mp(this, &ThemeTypeEditor::_edit_resource_item));
-				item_editor->connect("resource_changed", callable_mp(this, &ThemeTypeEditor::_font_item_changed), varray(E.key()));
+				item_editor->connect("resource_changed", callable_mp(this, &ThemeTypeEditor::_font_item_changed), varray(E.key));
 			} else {
-				if (Theme::get_default()->has_font(E.key(), edited_type)) {
-					item_editor->set_edited_resource(Theme::get_default()->get_font(E.key(), edited_type));
+				if (Theme::get_default()->has_font(E.key, edited_type)) {
+					item_editor->set_edited_resource(Theme::get_default()->get_font(E.key, edited_type));
 				} else {
 					item_editor->set_edited_resource(Ref<Resource>());
 				}
@@ -2563,9 +2563,9 @@ void ThemeTypeEditor::_update_type_items() {
 			font_size_items_list->remove_child(node);
 		}
 
-		OrderedHashMap<StringName, bool> font_size_items = _get_type_items(edited_type, &Theme::get_font_size_list, show_default);
-		for (OrderedHashMap<StringName, bool>::Element E = font_size_items.front(); E; E = E.next()) {
-			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_FONT_SIZE, E.key(), E.get());
+		HashMap<StringName, bool> font_size_items = _get_type_items(edited_type, &Theme::get_font_size_list, show_default);
+		for (const KeyValue<StringName, bool> &E : font_size_items) {
+			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_FONT_SIZE, E.key, E.value);
 			SpinBox *item_editor = memnew(SpinBox);
 			item_editor->set_h_size_flags(SIZE_EXPAND_FILL);
 			item_editor->set_min(-100000);
@@ -2575,11 +2575,11 @@ void ThemeTypeEditor::_update_type_items() {
 			item_editor->set_allow_greater(true);
 			item_control->add_child(item_editor);
 
-			if (E.get()) {
-				item_editor->set_value(edited_theme->get_font_size(E.key(), edited_type));
-				item_editor->connect("value_changed", callable_mp(this, &ThemeTypeEditor::_font_size_item_changed), varray(E.key()));
+			if (E.value) {
+				item_editor->set_value(edited_theme->get_font_size(E.key, edited_type));
+				item_editor->connect("value_changed", callable_mp(this, &ThemeTypeEditor::_font_size_item_changed), varray(E.key));
 			} else {
-				item_editor->set_value(Theme::get_default()->get_font_size(E.key(), edited_type));
+				item_editor->set_value(Theme::get_default()->get_font_size(E.key, edited_type));
 				item_editor->set_editable(false);
 			}
 
@@ -2596,25 +2596,25 @@ void ThemeTypeEditor::_update_type_items() {
 			icon_items_list->remove_child(node);
 		}
 
-		OrderedHashMap<StringName, bool> icon_items = _get_type_items(edited_type, &Theme::get_icon_list, show_default);
-		for (OrderedHashMap<StringName, bool>::Element E = icon_items.front(); E; E = E.next()) {
-			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_ICON, E.key(), E.get());
+		HashMap<StringName, bool> icon_items = _get_type_items(edited_type, &Theme::get_icon_list, show_default);
+		for (const KeyValue<StringName, bool> &E : icon_items) {
+			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_ICON, E.key, E.value);
 			EditorResourcePicker *item_editor = memnew(EditorResourcePicker);
 			item_editor->set_h_size_flags(SIZE_EXPAND_FILL);
 			item_editor->set_base_type("Texture2D");
 			item_control->add_child(item_editor);
 
-			if (E.get()) {
-				if (edited_theme->has_icon(E.key(), edited_type)) {
-					item_editor->set_edited_resource(edited_theme->get_icon(E.key(), edited_type));
+			if (E.value) {
+				if (edited_theme->has_icon(E.key, edited_type)) {
+					item_editor->set_edited_resource(edited_theme->get_icon(E.key, edited_type));
 				} else {
 					item_editor->set_edited_resource(Ref<Resource>());
 				}
 				item_editor->connect("resource_selected", callable_mp(this, &ThemeTypeEditor::_edit_resource_item));
-				item_editor->connect("resource_changed", callable_mp(this, &ThemeTypeEditor::_icon_item_changed), varray(E.key()));
+				item_editor->connect("resource_changed", callable_mp(this, &ThemeTypeEditor::_icon_item_changed), varray(E.key));
 			} else {
-				if (Theme::get_default()->has_icon(E.key(), edited_type)) {
-					item_editor->set_edited_resource(Theme::get_default()->get_icon(E.key(), edited_type));
+				if (Theme::get_default()->has_icon(E.key, edited_type)) {
+					item_editor->set_edited_resource(Theme::get_default()->get_icon(E.key, edited_type));
 				} else {
 					item_editor->set_edited_resource(Ref<Resource>());
 				}
@@ -2664,26 +2664,26 @@ void ThemeTypeEditor::_update_type_items() {
 			stylebox_items_list->add_child(memnew(HSeparator));
 		}
 
-		OrderedHashMap<StringName, bool> stylebox_items = _get_type_items(edited_type, &Theme::get_stylebox_list, show_default);
-		for (OrderedHashMap<StringName, bool>::Element E = stylebox_items.front(); E; E = E.next()) {
-			if (leading_stylebox.pinned && leading_stylebox.item_name == E.key()) {
+		HashMap<StringName, bool> stylebox_items = _get_type_items(edited_type, &Theme::get_stylebox_list, show_default);
+		for (const KeyValue<StringName, bool> &E : stylebox_items) {
+			if (leading_stylebox.pinned && leading_stylebox.item_name == E.key) {
 				continue;
 			}
 
-			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_STYLEBOX, E.key(), E.get());
+			HBoxContainer *item_control = _create_property_control(Theme::DATA_TYPE_STYLEBOX, E.key, E.value);
 			EditorResourcePicker *item_editor = memnew(EditorResourcePicker);
 			item_editor->set_h_size_flags(SIZE_EXPAND_FILL);
 			item_editor->set_stretch_ratio(1.5);
 			item_editor->set_base_type("StyleBox");
 
-			if (E.get()) {
-				if (edited_theme->has_stylebox(E.key(), edited_type)) {
-					item_editor->set_edited_resource(edited_theme->get_stylebox(E.key(), edited_type));
+			if (E.value) {
+				if (edited_theme->has_stylebox(E.key, edited_type)) {
+					item_editor->set_edited_resource(edited_theme->get_stylebox(E.key, edited_type));
 				} else {
 					item_editor->set_edited_resource(Ref<Resource>());
 				}
 				item_editor->connect("resource_selected", callable_mp(this, &ThemeTypeEditor::_edit_resource_item));
-				item_editor->connect("resource_changed", callable_mp(this, &ThemeTypeEditor::_stylebox_item_changed), varray(E.key()));
+				item_editor->connect("resource_changed", callable_mp(this, &ThemeTypeEditor::_stylebox_item_changed), varray(E.key));
 
 				Button *pin_leader_button = memnew(Button);
 				pin_leader_button->set_flat(true);
@@ -2691,10 +2691,10 @@ void ThemeTypeEditor::_update_type_items() {
 				pin_leader_button->set_icon(get_theme_icon(SNAME("Pin"), SNAME("EditorIcons")));
 				pin_leader_button->set_tooltip(TTR("Pin this StyleBox as a main style. Editing its properties will update the same properties in all other StyleBoxes of this type."));
 				item_control->add_child(pin_leader_button);
-				pin_leader_button->connect("pressed", callable_mp(this, &ThemeTypeEditor::_on_pin_leader_button_pressed), varray(item_editor, E.key()));
+				pin_leader_button->connect("pressed", callable_mp(this, &ThemeTypeEditor::_on_pin_leader_button_pressed), varray(item_editor, E.key));
 			} else {
-				if (Theme::get_default()->has_stylebox(E.key(), edited_type)) {
-					item_editor->set_edited_resource(Theme::get_default()->get_stylebox(E.key(), edited_type));
+				if (Theme::get_default()->has_stylebox(E.key, edited_type)) {
+					item_editor->set_edited_resource(Theme::get_default()->get_stylebox(E.key, edited_type));
 				} else {
 					item_editor->set_edited_resource(Ref<Resource>());
 				}
diff --git a/editor/plugins/theme_editor_plugin.h b/editor/plugins/theme_editor_plugin.h
index 3894ca31e5..6debf00e90 100644
--- a/editor/plugins/theme_editor_plugin.h
+++ b/editor/plugins/theme_editor_plugin.h
@@ -363,7 +363,7 @@ class ThemeTypeEditor : public MarginContainer {
 	VBoxContainer *_create_item_list(Theme::DataType p_data_type);
 	void _update_type_list();
 	void _update_type_list_debounced();
-	OrderedHashMap<StringName, bool> _get_type_items(String p_type_name, void (Theme::*get_list_func)(StringName, List<StringName> *) const, bool include_default);
+	HashMap<StringName, bool> _get_type_items(String p_type_name, void (Theme::*get_list_func)(StringName, List<StringName> *) const, bool include_default);
 	HBoxContainer *_create_property_control(Theme::DataType p_data_type, String p_item_name, bool p_editable);
 	void _add_focusable(Control *p_control);
 	void _update_type_items();