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

2 files changed, 9 insertions, 11 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);
 				}