From 746dddc0673d7261f19b1e056e90e6e3a49ef33a Mon Sep 17 00:00:00 2001
From: reduz <reduzio@gmail.com>
Date: Fri, 13 May 2022 15:04:37 +0200
Subject: Replace most uses of Map by HashMap

* Map is unnecessary and inefficient in almost every case.
* Replaced by the new HashMap.
* Renamed Map to RBMap and Set to RBSet for cases that still make sense
  (order matters) but use is discouraged.

There were very few cases where replacing by HashMap was undesired because
keeping the key order was intended.
I tried to keep those (as RBMap) as much as possible, but might have missed
some. Review appreciated!
---
 modules/gridmap/grid_map.cpp | 21 +++++++++++----------
 modules/gridmap/grid_map.h   | 21 +++++++++++++++------
 2 files changed, 26 insertions(+), 16 deletions(-)

(limited to 'modules/gridmap')

diff --git a/modules/gridmap/grid_map.cpp b/modules/gridmap/grid_map.cpp
index 3c7bd5eb70..9da137f9d5 100644
--- a/modules/gridmap/grid_map.cpp
+++ b/modules/gridmap/grid_map.cpp
@@ -103,9 +103,10 @@ bool GridMap::_get(const StringName &p_name, Variant &r_ret) const {
 		{
 			int *w = cells.ptrw();
 			int i = 0;
-			for (Map<IndexKey, Cell>::Element *E = cell_map.front(); E; E = E->next(), i++) {
-				encode_uint64(E->key().key, (uint8_t *)&w[i * 3]);
-				encode_uint32(E->get().cell, (uint8_t *)&w[i * 3 + 2]);
+			for (const KeyValue<IndexKey, Cell> &E : cell_map) {
+				encode_uint64(E.key.key, (uint8_t *)&w[i * 3]);
+				encode_uint32(E.value.cell, (uint8_t *)&w[i * 3 + 2]);
+				i++;
 			}
 		}
 
@@ -480,9 +481,9 @@ bool GridMap::_octant_update(const OctantKey &p_key) {
 	 * and set said multimesh bounding box to one containing all cells which have this item
 	 */
 
-	Map<int, List<Pair<Transform3D, IndexKey>>> multimesh_items;
+	HashMap<int, List<Pair<Transform3D, IndexKey>>> multimesh_items;
 
-	for (Set<IndexKey>::Element *E = g.cells.front(); E; E = E->next()) {
+	for (RBSet<IndexKey>::Element *E = g.cells.front(); E; E = E->next()) {
 		ERR_CONTINUE(!cell_map.has(E->get()));
 		const Cell &c = cell_map[E->get()];
 
@@ -770,7 +771,7 @@ void GridMap::_queue_octants_dirty() {
 
 void GridMap::_recreate_octant_data() {
 	recreating_octants = true;
-	Map<IndexKey, Cell> cell_copy = cell_map;
+	HashMap<IndexKey, Cell, IndexKey> cell_copy = cell_map;
 	_clear_internal();
 	for (const KeyValue<IndexKey, Cell> &E : cell_copy) {
 		set_cell_item(Vector3i(E.key), E.value.item, E.value.rot);
@@ -998,7 +999,7 @@ void GridMap::make_baked_meshes(bool p_gen_lightmap_uv, float p_lightmap_uv_texe
 	}
 
 	//generate
-	Map<OctantKey, Map<Ref<Material>, Ref<SurfaceTool>>> surface_map;
+	HashMap<OctantKey, HashMap<Ref<Material>, Ref<SurfaceTool>>, OctantKey> surface_map;
 
 	for (KeyValue<IndexKey, Cell> &E : cell_map) {
 		IndexKey key = E.key;
@@ -1028,10 +1029,10 @@ void GridMap::make_baked_meshes(bool p_gen_lightmap_uv, float p_lightmap_uv_texe
 		ok.z = key.z / octant_size;
 
 		if (!surface_map.has(ok)) {
-			surface_map[ok] = Map<Ref<Material>, Ref<SurfaceTool>>();
+			surface_map[ok] = HashMap<Ref<Material>, Ref<SurfaceTool>>();
 		}
 
-		Map<Ref<Material>, Ref<SurfaceTool>> &mat_map = surface_map[ok];
+		HashMap<Ref<Material>, Ref<SurfaceTool>> &mat_map = surface_map[ok];
 
 		for (int i = 0; i < mesh->get_surface_count(); i++) {
 			if (mesh->surface_get_primitive_type(i) != Mesh::PRIMITIVE_TRIANGLES) {
@@ -1051,7 +1052,7 @@ void GridMap::make_baked_meshes(bool p_gen_lightmap_uv, float p_lightmap_uv_texe
 		}
 	}
 
-	for (KeyValue<OctantKey, Map<Ref<Material>, Ref<SurfaceTool>>> &E : surface_map) {
+	for (KeyValue<OctantKey, HashMap<Ref<Material>, Ref<SurfaceTool>>> &E : surface_map) {
 		Ref<ArrayMesh> mesh;
 		mesh.instantiate();
 		for (KeyValue<Ref<Material>, Ref<SurfaceTool>> &F : E.value) {
diff --git a/modules/gridmap/grid_map.h b/modules/gridmap/grid_map.h
index 5e367e149d..88e16bce82 100644
--- a/modules/gridmap/grid_map.h
+++ b/modules/gridmap/grid_map.h
@@ -56,9 +56,15 @@ class GridMap : public Node3D {
 		};
 		uint64_t key = 0;
 
+		static uint32_t hash(const IndexKey &p_key) {
+			return hash_one_uint64(p_key.key);
+		}
 		_FORCE_INLINE_ bool operator<(const IndexKey &p_key) const {
 			return key < p_key.key;
 		}
+		_FORCE_INLINE_ bool operator==(const IndexKey &p_key) const {
+			return key == p_key.key;
+		}
 
 		_FORCE_INLINE_ operator Vector3i() const {
 			return Vector3i(x, y, z);
@@ -107,13 +113,13 @@ class GridMap : public Node3D {
 		};
 
 		Vector<MultimeshInstance> multimesh_instances;
-		Set<IndexKey> cells;
+		RBSet<IndexKey> cells;
 		RID collision_debug;
 		RID collision_debug_instance;
 
 		bool dirty = false;
 		RID static_body;
-		Map<IndexKey, NavMesh> navmesh_ids;
+		HashMap<IndexKey, NavMesh> navmesh_ids;
 	};
 
 	union OctantKey {
@@ -126,8 +132,11 @@ class GridMap : public Node3D {
 
 		uint64_t key = 0;
 
-		_FORCE_INLINE_ bool operator<(const OctantKey &p_key) const {
-			return key < p_key.key;
+		static uint32_t hash(const OctantKey &p_key) {
+			return hash_one_uint64(p_key.key);
+		}
+		_FORCE_INLINE_ bool operator==(const OctantKey &p_key) const {
+			return key == p_key.key;
 		}
 
 		//OctantKey(const IndexKey& p_k, int p_item) { indexkey=p_k.key; item=p_item; }
@@ -154,8 +163,8 @@ class GridMap : public Node3D {
 
 	Ref<MeshLibrary> mesh_library;
 
-	Map<OctantKey, Octant *> octant_map;
-	Map<IndexKey, Cell> cell_map;
+	HashMap<OctantKey, Octant *, OctantKey> octant_map;
+	HashMap<IndexKey, Cell, IndexKey> cell_map;
 
 	void _recreate_octant_data();
 
-- 
cgit v1.2.3