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

5 files changed, 15 insertions, 17 deletions

diff --git a/servers/rendering/renderer_rd/storage_rd/material_storage.cpp b/servers/rendering/renderer_rd/storage_rd/material_storage.cpp
index 4d2ee738a4..550fc7d788 100644
--- a/servers/rendering/renderer_rd/storage_rd/material_storage.cpp
+++ b/servers/rendering/renderer_rd/storage_rd/material_storage.cpp
@@ -1959,10 +1959,9 @@ Vector<StringName> MaterialStorage::global_variable_get_list() const {
 		ERR_FAIL_V_MSG(Vector<StringName>(), "This function should never be used outside the editor, it can severely damage performance.");
 	}
 
-	const StringName *K = nullptr;
 	Vector<StringName> names;
-	while ((K = global_variables.variables.next(K))) {
-		names.push_back(*K);
+	for (const KeyValue<StringName, GlobalVariables::Variable> &E : global_variables.variables) {
+		names.push_back(E.key);
 	}
 	names.sort_custom<StringName::AlphCompare>();
 	return names;
diff --git a/servers/rendering/renderer_rd/storage_rd/texture_storage.cpp b/servers/rendering/renderer_rd/storage_rd/texture_storage.cpp
index 15d40b8a1f..7d4808f936 100644
--- a/servers/rendering/renderer_rd/storage_rd/texture_storage.cpp
+++ b/servers/rendering/renderer_rd/storage_rd/texture_storage.cpp
@@ -1831,13 +1831,13 @@ void TextureStorage::update_decal_atlas() {
 		Vector<DecalAtlas::SortItem> itemsv;
 		itemsv.resize(decal_atlas.textures.size());
 		int base_size = 8;
-		const RID *K = nullptr;
 
 		int idx = 0;
-		while ((K = decal_atlas.textures.next(K))) {
+
+		for (const KeyValue<RID, DecalAtlas::Texture> &E : decal_atlas.textures) {
 			DecalAtlas::SortItem &si = itemsv.write[idx];
 
-			Texture *src_tex = get_texture(*K);
+			Texture *src_tex = get_texture(E.key);
 
 			si.size.width = (src_tex->width / border) + 1;
 			si.size.height = (src_tex->height / border) + 1;
@@ -1847,7 +1847,7 @@ void TextureStorage::update_decal_atlas() {
 				base_size = nearest_power_of_2_templated(si.size.width);
 			}
 
-			si.texture = *K;
+			si.texture = E.key;
 			idx++;
 		}
 
@@ -1983,10 +1983,9 @@ void TextureStorage::update_decal_atlas() {
 
 				RD::DrawListID draw_list = RD::get_singleton()->draw_list_begin(mm.fb, RD::INITIAL_ACTION_CLEAR, RD::FINAL_ACTION_READ, RD::INITIAL_ACTION_DROP, RD::FINAL_ACTION_DISCARD, cc);
 
-				const RID *K = nullptr;
-				while ((K = decal_atlas.textures.next(K))) {
-					DecalAtlas::Texture *t = decal_atlas.textures.getptr(*K);
-					Texture *src_tex = get_texture(*K);
+				for (const KeyValue<RID, DecalAtlas::Texture> &E : decal_atlas.textures) {
+					DecalAtlas::Texture *t = decal_atlas.textures.getptr(E.key);
+					Texture *src_tex = get_texture(E.key);
 					copy_effects->copy_to_atlas_fb(src_tex->rd_texture, mm.fb, t->uv_rect, draw_list, false, t->panorama_to_dp_users > 0);
 				}
 
diff --git a/servers/rendering/rendering_server_default.cpp b/servers/rendering/rendering_server_default.cpp
index 000b253e8a..c8345d8eef 100644
--- a/servers/rendering/rendering_server_default.cpp
+++ b/servers/rendering/rendering_server_default.cpp
@@ -179,10 +179,10 @@ void RenderingServerDefault::_draw(bool p_swap_buffers, double frame_step) {
 			print_line("GPU PROFILE (total " + rtos(total_time) + "ms): ");
 
 			float print_threshold = 0.01;
-			for (OrderedHashMap<String, float>::Element E = print_gpu_profile_task_time.front(); E; E = E.next()) {
-				double time = E.value() / double(print_frame_profile_frame_count);
+			for (const KeyValue<String, float> &E : print_gpu_profile_task_time) {
+				double time = E.value / double(print_frame_profile_frame_count);
 				if (time > print_threshold) {
-					print_line("\t-" + E.key() + ": " + rtos(time) + "ms");
+					print_line("\t-" + E.key + ": " + rtos(time) + "ms");
 				}
 			}
 			print_gpu_profile_task_time.clear();
diff --git a/servers/rendering/rendering_server_default.h b/servers/rendering/rendering_server_default.h
index de4f8d9194..daf2f86a4c 100644
--- a/servers/rendering/rendering_server_default.h
+++ b/servers/rendering/rendering_server_default.h
@@ -33,7 +33,7 @@
 
 #include "core/math/octree.h"
 #include "core/templates/command_queue_mt.h"
-#include "core/templates/ordered_hash_map.h"
+#include "core/templates/hash_map.h"
 #include "renderer_canvas_cull.h"
 #include "renderer_scene_cull.h"
 #include "renderer_viewport.h"
@@ -69,7 +69,7 @@ class RenderingServerDefault : public RenderingServer {
 
 	//for printing
 	bool print_gpu_profile = false;
-	OrderedHashMap<String, float> print_gpu_profile_task_time;
+	HashMap<String, float> print_gpu_profile_task_time;
 	uint64_t print_frame_profile_ticks_from = 0;
 	uint32_t print_frame_profile_frame_count = 0;
 
diff --git a/servers/rendering/shader_types.h b/servers/rendering/shader_types.h
index 385083b670..6ba05a3b43 100644
--- a/servers/rendering/shader_types.h
+++ b/servers/rendering/shader_types.h
@@ -31,7 +31,7 @@
 #ifndef SHADERTYPES_H
 #define SHADERTYPES_H
 
-#include "core/templates/ordered_hash_map.h"
+#include "core/templates/map.h"
 #include "servers/rendering_server.h"
 #include "shader_language.h"