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!

12 files changed, 68 insertions, 65 deletions

diff --git a/servers/physics_3d/godot_area_3d.cpp b/servers/physics_3d/godot_area_3d.cpp
index e7df23d0d8..e2ad765d62 100644
--- a/servers/physics_3d/godot_area_3d.cpp
+++ b/servers/physics_3d/godot_area_3d.cpp
@@ -254,22 +254,24 @@ void GodotArea3D::call_queries() {
 				resptr[i] = &res[i];
 			}
 
-			for (Map<BodyKey, BodyState>::Element *E = monitored_bodies.front(); E;) {
-				if (E->get().state == 0) { // Nothing happened
-					Map<BodyKey, BodyState>::Element *next = E->next();
-					monitored_bodies.erase(E);
+			for (HashMap<BodyKey, BodyState, BodyKey>::Iterator E = monitored_bodies.begin(); E;) {
+				if (E->value.state == 0) { // Nothing happened
+					HashMap<BodyKey, BodyState, BodyKey>::Iterator next = E;
+					++next;
+					monitored_bodies.remove(E);
 					E = next;
 					continue;
 				}
 
-				res[0] = E->get().state > 0 ? PhysicsServer3D::AREA_BODY_ADDED : PhysicsServer3D::AREA_BODY_REMOVED;
-				res[1] = E->key().rid;
-				res[2] = E->key().instance_id;
-				res[3] = E->key().body_shape;
-				res[4] = E->key().area_shape;
+				res[0] = E->value.state > 0 ? PhysicsServer3D::AREA_BODY_ADDED : PhysicsServer3D::AREA_BODY_REMOVED;
+				res[1] = E->key.rid;
+				res[2] = E->key.instance_id;
+				res[3] = E->key.body_shape;
+				res[4] = E->key.area_shape;
 
-				Map<BodyKey, BodyState>::Element *next = E->next();
-				monitored_bodies.erase(E);
+				HashMap<BodyKey, BodyState, BodyKey>::Iterator next = E;
+				++next;
+				monitored_bodies.remove(E);
 				E = next;
 
 				Callable::CallError ce;
@@ -290,22 +292,24 @@ void GodotArea3D::call_queries() {
 				resptr[i] = &res[i];
 			}
 
-			for (Map<BodyKey, BodyState>::Element *E = monitored_areas.front(); E;) {
-				if (E->get().state == 0) { // Nothing happened
-					Map<BodyKey, BodyState>::Element *next = E->next();
-					monitored_areas.erase(E);
+			for (HashMap<BodyKey, BodyState, BodyKey>::Iterator E = monitored_areas.begin(); E;) {
+				if (E->value.state == 0) { // Nothing happened
+					HashMap<BodyKey, BodyState, BodyKey>::Iterator next = E;
+					++next;
+					monitored_areas.remove(E);
 					E = next;
 					continue;
 				}
 
-				res[0] = E->get().state > 0 ? PhysicsServer3D::AREA_BODY_ADDED : PhysicsServer3D::AREA_BODY_REMOVED;
-				res[1] = E->key().rid;
-				res[2] = E->key().instance_id;
-				res[3] = E->key().body_shape;
-				res[4] = E->key().area_shape;
+				res[0] = E->value.state > 0 ? PhysicsServer3D::AREA_BODY_ADDED : PhysicsServer3D::AREA_BODY_REMOVED;
+				res[1] = E->key.rid;
+				res[2] = E->key.instance_id;
+				res[3] = E->key.body_shape;
+				res[4] = E->key.area_shape;
 
-				Map<BodyKey, BodyState>::Element *next = E->next();
-				monitored_areas.erase(E);
+				HashMap<BodyKey, BodyState, BodyKey>::Iterator next = E;
+				++next;
+				monitored_areas.remove(E);
 				E = next;
 
 				Callable::CallError ce;
diff --git a/servers/physics_3d/godot_area_3d.h b/servers/physics_3d/godot_area_3d.h
index d15f8ec0a6..2a5e5a537a 100644
--- a/servers/physics_3d/godot_area_3d.h
+++ b/servers/physics_3d/godot_area_3d.h
@@ -72,16 +72,15 @@ class GodotArea3D : public GodotCollisionObject3D {
 		uint32_t body_shape = 0;
 		uint32_t area_shape = 0;
 
-		_FORCE_INLINE_ bool operator<(const BodyKey &p_key) const {
-			if (rid == p_key.rid) {
-				if (body_shape == p_key.body_shape) {
-					return area_shape < p_key.area_shape;
-				} else {
-					return body_shape < p_key.body_shape;
-				}
-			} else {
-				return rid < p_key.rid;
-			}
+		static uint32_t hash(const BodyKey &p_key) {
+			uint32_t h = hash_one_uint64(p_key.rid.get_id());
+			h = hash_djb2_one_64(p_key.instance_id, h);
+			h = hash_djb2_one_32(p_key.area_shape, h);
+			return hash_djb2_one_32(p_key.body_shape, h);
+		}
+
+		_FORCE_INLINE_ bool operator==(const BodyKey &p_key) const {
+			return rid == p_key.rid && instance_id == p_key.instance_id && body_shape == p_key.body_shape && area_shape == p_key.area_shape;
 		}
 
 		_FORCE_INLINE_ BodyKey() {}
@@ -96,11 +95,11 @@ class GodotArea3D : public GodotCollisionObject3D {
 		_FORCE_INLINE_ void dec() { state--; }
 	};
 
-	Map<BodyKey, BodyState> monitored_soft_bodies;
-	Map<BodyKey, BodyState> monitored_bodies;
-	Map<BodyKey, BodyState> monitored_areas;
+	HashMap<BodyKey, BodyState, BodyKey> monitored_soft_bodies;
+	HashMap<BodyKey, BodyState, BodyKey> monitored_bodies;
+	HashMap<BodyKey, BodyState, BodyKey> monitored_areas;
 
-	Set<GodotConstraint3D *> constraints;
+	RBSet<GodotConstraint3D *> constraints;
 
 	virtual void _shapes_changed() override;
 	void _queue_monitor_update();
@@ -164,7 +163,7 @@ public:
 
 	_FORCE_INLINE_ void add_constraint(GodotConstraint3D *p_constraint) { constraints.insert(p_constraint); }
 	_FORCE_INLINE_ void remove_constraint(GodotConstraint3D *p_constraint) { constraints.erase(p_constraint); }
-	_FORCE_INLINE_ const Set<GodotConstraint3D *> &get_constraints() const { return constraints; }
+	_FORCE_INLINE_ const RBSet<GodotConstraint3D *> &get_constraints() const { return constraints; }
 	_FORCE_INLINE_ void clear_constraints() { constraints.clear(); }
 
 	void set_monitorable(bool p_monitorable);
diff --git a/servers/physics_3d/godot_body_3d.h b/servers/physics_3d/godot_body_3d.h
index c0c847d920..93bd5a0071 100644
--- a/servers/physics_3d/godot_body_3d.h
+++ b/servers/physics_3d/godot_body_3d.h
@@ -112,7 +112,7 @@ class GodotBody3D : public GodotCollisionObject3D {
 	virtual void _shapes_changed() override;
 	Transform3D new_transform;
 
-	Map<GodotConstraint3D *, int> constraint_map;
+	HashMap<GodotConstraint3D *, int> constraint_map;
 
 	Vector<AreaCMP> areas;
 
@@ -196,7 +196,7 @@ public:
 
 	_FORCE_INLINE_ void add_constraint(GodotConstraint3D *p_constraint, int p_pos) { constraint_map[p_constraint] = p_pos; }
 	_FORCE_INLINE_ void remove_constraint(GodotConstraint3D *p_constraint) { constraint_map.erase(p_constraint); }
-	const Map<GodotConstraint3D *, int> &get_constraint_map() const { return constraint_map; }
+	const HashMap<GodotConstraint3D *, int> &get_constraint_map() const { return constraint_map; }
 	_FORCE_INLINE_ void clear_constraint_map() { constraint_map.clear(); }
 
 	_FORCE_INLINE_ void set_omit_force_integration(bool p_omit_force_integration) { omit_force_integration = p_omit_force_integration; }
diff --git a/servers/physics_3d/godot_physics_server_3d.cpp b/servers/physics_3d/godot_physics_server_3d.cpp
index e5107be74b..cb4988757c 100644
--- a/servers/physics_3d/godot_physics_server_3d.cpp
+++ b/servers/physics_3d/godot_physics_server_3d.cpp
@@ -1531,7 +1531,7 @@ void GodotPhysicsServer3D::free(RID p_rid) {
 		GodotShape3D *shape = shape_owner.get_or_null(p_rid);
 
 		while (shape->get_owners().size()) {
-			GodotShapeOwner3D *so = shape->get_owners().front()->key();
+			GodotShapeOwner3D *so = shape->get_owners().begin()->key;
 			so->remove_shape(shape);
 		}
 
@@ -1611,7 +1611,7 @@ void GodotPhysicsServer3D::step(real_t p_step) {
 	island_count = 0;
 	active_objects = 0;
 	collision_pairs = 0;
-	for (Set<const GodotSpace3D *>::Element *E = active_spaces.front(); E; E = E->next()) {
+	for (RBSet<const GodotSpace3D *>::Element *E = active_spaces.front(); E; E = E->next()) {
 		stepper->step(const_cast<GodotSpace3D *>(E->get()), p_step);
 		island_count += E->get()->get_island_count();
 		active_objects += E->get()->get_active_objects();
@@ -1635,7 +1635,7 @@ void GodotPhysicsServer3D::flush_queries() {
 
 	uint64_t time_beg = OS::get_singleton()->get_ticks_usec();
 
-	for (Set<const GodotSpace3D *>::Element *E = active_spaces.front(); E; E = E->next()) {
+	for (RBSet<const GodotSpace3D *>::Element *E = active_spaces.front(); E; E = E->next()) {
 		GodotSpace3D *space = const_cast<GodotSpace3D *>(E->get());
 		space->call_queries();
 	}
@@ -1656,7 +1656,7 @@ void GodotPhysicsServer3D::flush_queries() {
 			total_time[i] = 0;
 		}
 
-		for (Set<const GodotSpace3D *>::Element *E = active_spaces.front(); E; E = E->next()) {
+		for (RBSet<const GodotSpace3D *>::Element *E = active_spaces.front(); E; E = E->next()) {
 			for (int i = 0; i < GodotSpace3D::ELAPSED_TIME_MAX; i++) {
 				total_time[i] += E->get()->get_elapsed_time(GodotSpace3D::ElapsedTime(i));
 			}
diff --git a/servers/physics_3d/godot_physics_server_3d.h b/servers/physics_3d/godot_physics_server_3d.h
index d2078a912c..65c53084ac 100644
--- a/servers/physics_3d/godot_physics_server_3d.h
+++ b/servers/physics_3d/godot_physics_server_3d.h
@@ -54,7 +54,7 @@ class GodotPhysicsServer3D : public PhysicsServer3D {
 	bool flushing_queries = false;
 
 	GodotStep3D *stepper = nullptr;
-	Set<const GodotSpace3D *> active_spaces;
+	RBSet<const GodotSpace3D *> active_spaces;
 
 	mutable RID_PtrOwner<GodotShape3D, true> shape_owner;
 	mutable RID_PtrOwner<GodotSpace3D, true> space_owner;
diff --git a/servers/physics_3d/godot_shape_3d.cpp b/servers/physics_3d/godot_shape_3d.cpp
index 2efc11a4c0..5e310670a5 100644
--- a/servers/physics_3d/godot_shape_3d.cpp
+++ b/servers/physics_3d/godot_shape_3d.cpp
@@ -76,20 +76,20 @@ Vector3 GodotShape3D::get_support(const Vector3 &p_normal) const {
 }
 
 void GodotShape3D::add_owner(GodotShapeOwner3D *p_owner) {
-	Map<GodotShapeOwner3D *, int>::Element *E = owners.find(p_owner);
+	HashMap<GodotShapeOwner3D *, int>::Iterator E = owners.find(p_owner);
 	if (E) {
-		E->get()++;
+		E->value++;
 	} else {
 		owners[p_owner] = 1;
 	}
 }
 
 void GodotShape3D::remove_owner(GodotShapeOwner3D *p_owner) {
-	Map<GodotShapeOwner3D *, int>::Element *E = owners.find(p_owner);
+	HashMap<GodotShapeOwner3D *, int>::Iterator E = owners.find(p_owner);
 	ERR_FAIL_COND(!E);
-	E->get()--;
-	if (E->get() == 0) {
-		owners.erase(E);
+	E->value--;
+	if (E->value == 0) {
+		owners.remove(E);
 	}
 }
 
@@ -97,7 +97,7 @@ bool GodotShape3D::is_owner(GodotShapeOwner3D *p_owner) const {
 	return owners.has(p_owner);
 }
 
-const Map<GodotShapeOwner3D *, int> &GodotShape3D::get_owners() const {
+const HashMap<GodotShapeOwner3D *, int> &GodotShape3D::get_owners() const {
 	return owners;
 }
 
diff --git a/servers/physics_3d/godot_shape_3d.h b/servers/physics_3d/godot_shape_3d.h
index 9d171c3928..1fc8f7c711 100644
--- a/servers/physics_3d/godot_shape_3d.h
+++ b/servers/physics_3d/godot_shape_3d.h
@@ -51,7 +51,7 @@ class GodotShape3D {
 	bool configured = false;
 	real_t custom_bias = 0.0;
 
-	Map<GodotShapeOwner3D *, int> owners;
+	HashMap<GodotShapeOwner3D *, int> owners;
 
 protected:
 	void configure(const AABB &p_aabb);
@@ -93,7 +93,7 @@ public:
 	void add_owner(GodotShapeOwner3D *p_owner);
 	void remove_owner(GodotShapeOwner3D *p_owner);
 	bool is_owner(GodotShapeOwner3D *p_owner) const;
-	const Map<GodotShapeOwner3D *, int> &get_owners() const;
+	const HashMap<GodotShapeOwner3D *, int> &get_owners() const;
 
 	GodotShape3D() {}
 	virtual ~GodotShape3D();
diff --git a/servers/physics_3d/godot_soft_body_3d.cpp b/servers/physics_3d/godot_soft_body_3d.cpp
index be4b41292d..9cc7912a5a 100644
--- a/servers/physics_3d/godot_soft_body_3d.cpp
+++ b/servers/physics_3d/godot_soft_body_3d.cpp
@@ -33,7 +33,7 @@
 #include "godot_space_3d.h"
 
 #include "core/math/geometry_3d.h"
-#include "core/templates/map.h"
+#include "core/templates/rb_map.h"
 #include "servers/rendering_server.h"
 
 // Based on Bullet soft body.
@@ -494,7 +494,7 @@ bool GodotSoftBody3D::create_from_trimesh(const Vector<int> &p_indices, const Ve
 		// Process vertices.
 		{
 			uint32_t vertex_count = 0;
-			Map<Vector3, uint32_t> unique_vertices;
+			HashMap<Vector3, uint32_t> unique_vertices;
 
 			vertices.resize(visual_vertex_count);
 			map_visual_to_physics.resize(visual_vertex_count);
@@ -502,11 +502,11 @@ bool GodotSoftBody3D::create_from_trimesh(const Vector<int> &p_indices, const Ve
 			for (int visual_vertex_index = 0; visual_vertex_index < visual_vertex_count; ++visual_vertex_index) {
 				const Vector3 &vertex = p_vertices[visual_vertex_index];
 
-				Map<Vector3, uint32_t>::Element *e = unique_vertices.find(vertex);
+				HashMap<Vector3, uint32_t>::Iterator e = unique_vertices.find(vertex);
 				uint32_t vertex_id;
 				if (e) {
 					// Already existing.
-					vertex_id = e->value();
+					vertex_id = e->value;
 				} else {
 					// Create new one.
 					vertex_id = vertex_count++;
diff --git a/servers/physics_3d/godot_soft_body_3d.h b/servers/physics_3d/godot_soft_body_3d.h
index 96f63e5819..094ab39c47 100644
--- a/servers/physics_3d/godot_soft_body_3d.h
+++ b/servers/physics_3d/godot_soft_body_3d.h
@@ -38,7 +38,7 @@
 #include "core/math/dynamic_bvh.h"
 #include "core/math/vector3.h"
 #include "core/templates/local_vector.h"
-#include "core/templates/set.h"
+#include "core/templates/rb_set.h"
 #include "core/templates/vset.h"
 
 class GodotConstraint3D;
@@ -103,7 +103,7 @@ class GodotSoftBody3D : public GodotCollisionObject3D {
 
 	SelfList<GodotSoftBody3D> active_list;
 
-	Set<GodotConstraint3D *> constraints;
+	RBSet<GodotConstraint3D *> constraints;
 
 	Vector<AreaCMP> areas;
 
@@ -123,7 +123,7 @@ public:
 
 	_FORCE_INLINE_ void add_constraint(GodotConstraint3D *p_constraint) { constraints.insert(p_constraint); }
 	_FORCE_INLINE_ void remove_constraint(GodotConstraint3D *p_constraint) { constraints.erase(p_constraint); }
-	_FORCE_INLINE_ const Set<GodotConstraint3D *> &get_constraints() const { return constraints; }
+	_FORCE_INLINE_ const RBSet<GodotConstraint3D *> &get_constraints() const { return constraints; }
 	_FORCE_INLINE_ void clear_constraints() { constraints.clear(); }
 
 	_FORCE_INLINE_ void add_exception(const RID &p_exception) { exceptions.insert(p_exception); }
diff --git a/servers/physics_3d/godot_space_3d.cpp b/servers/physics_3d/godot_space_3d.cpp
index 0b84520c39..9c051b23f6 100644
--- a/servers/physics_3d/godot_space_3d.cpp
+++ b/servers/physics_3d/godot_space_3d.cpp
@@ -1096,7 +1096,7 @@ void GodotSpace3D::remove_object(GodotCollisionObject3D *p_object) {
 	objects.erase(p_object);
 }
 
-const Set<GodotCollisionObject3D *> &GodotSpace3D::get_objects() const {
+const RBSet<GodotCollisionObject3D *> &GodotSpace3D::get_objects() const {
 	return objects;
 }
 
diff --git a/servers/physics_3d/godot_space_3d.h b/servers/physics_3d/godot_space_3d.h
index 6308ede9a9..67dde30fb5 100644
--- a/servers/physics_3d/godot_space_3d.h
+++ b/servers/physics_3d/godot_space_3d.h
@@ -89,7 +89,7 @@ private:
 	static void *_broadphase_pair(GodotCollisionObject3D *A, int p_subindex_A, GodotCollisionObject3D *B, int p_subindex_B, void *p_self);
 	static void _broadphase_unpair(GodotCollisionObject3D *A, int p_subindex_A, GodotCollisionObject3D *B, int p_subindex_B, void *p_data, void *p_self);
 
-	Set<GodotCollisionObject3D *> objects;
+	RBSet<GodotCollisionObject3D *> objects;
 
 	GodotArea3D *area = nullptr;
 
@@ -158,7 +158,7 @@ public:
 
 	void add_object(GodotCollisionObject3D *p_object);
 	void remove_object(GodotCollisionObject3D *p_object);
-	const Set<GodotCollisionObject3D *> &get_objects() const;
+	const RBSet<GodotCollisionObject3D *> &get_objects() const;
 
 	_FORCE_INLINE_ int get_solver_iterations() const { return solver_iterations; }
 	_FORCE_INLINE_ real_t get_contact_recycle_radius() const { return contact_recycle_radius; }
diff --git a/servers/physics_3d/godot_step_3d.cpp b/servers/physics_3d/godot_step_3d.cpp
index 204adae450..b46436ba39 100644
--- a/servers/physics_3d/godot_step_3d.cpp
+++ b/servers/physics_3d/godot_step_3d.cpp
@@ -87,7 +87,7 @@ void GodotStep3D::_populate_island(GodotBody3D *p_body, LocalVector<GodotBody3D
 void GodotStep3D::_populate_island_soft_body(GodotSoftBody3D *p_soft_body, LocalVector<GodotBody3D *> &p_body_island, LocalVector<GodotConstraint3D *> &p_constraint_island) {
 	p_soft_body->set_island_step(_step);
 
-	for (Set<GodotConstraint3D *>::Element *E = p_soft_body->get_constraints().front(); E; E = E->next()) {
+	for (RBSet<GodotConstraint3D *>::Element *E = p_soft_body->get_constraints().front(); E; E = E->next()) {
 		GodotConstraint3D *constraint = const_cast<GodotConstraint3D *>(E->get());
 		if (constraint->get_island_step() == _step) {
 			continue; // Already processed.
@@ -236,7 +236,7 @@ void GodotStep3D::step(GodotSpace3D *p_space, real_t p_delta) {
 	const SelfList<GodotArea3D>::List &aml = p_space->get_moved_area_list();
 
 	while (aml.first()) {
-		for (const Set<GodotConstraint3D *>::Element *E = aml.first()->self()->get_constraints().front(); E; E = E->next()) {
+		for (const RBSet<GodotConstraint3D *>::Element *E = aml.first()->self()->get_constraints().front(); E; E = E->next()) {
 			GodotConstraint3D *constraint = E->get();
 			if (constraint->get_island_step() == _step) {
 				continue;