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!

9 files changed, 59 insertions, 56 deletions

diff --git a/servers/physics_2d/godot_area_2d.cpp b/servers/physics_2d/godot_area_2d.cpp
index 9937178550..11208f2d5b 100644
--- a/servers/physics_2d/godot_area_2d.cpp
+++ b/servers/physics_2d/godot_area_2d.cpp
@@ -225,22 +225,24 @@ void GodotArea2D::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 ? PhysicsServer2D::AREA_BODY_ADDED : PhysicsServer2D::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 ? PhysicsServer2D::AREA_BODY_ADDED : PhysicsServer2D::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;
@@ -261,22 +263,24 @@ void GodotArea2D::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 ? PhysicsServer2D::AREA_BODY_ADDED : PhysicsServer2D::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 ? PhysicsServer2D::AREA_BODY_ADDED : PhysicsServer2D::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_2d/godot_area_2d.h b/servers/physics_2d/godot_area_2d.h
index dadd9747b1..b825ea5cdb 100644
--- a/servers/physics_2d/godot_area_2d.h
+++ b/servers/physics_2d/godot_area_2d.h
@@ -68,16 +68,15 @@ class GodotArea2D : public GodotCollisionObject2D {
 		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() {}
@@ -91,10 +90,10 @@ class GodotArea2D : public GodotCollisionObject2D {
 		_FORCE_INLINE_ void dec() { state--; }
 	};
 
-	Map<BodyKey, BodyState> monitored_bodies;
-	Map<BodyKey, BodyState> monitored_areas;
+	HashMap<BodyKey, BodyState, BodyKey> monitored_bodies;
+	HashMap<BodyKey, BodyState, BodyKey> monitored_areas;
 
-	Set<GodotConstraint2D *> constraints;
+	RBSet<GodotConstraint2D *> constraints;
 
 	virtual void _shapes_changed() override;
 	void _queue_monitor_update();
@@ -143,7 +142,7 @@ public:
 
 	_FORCE_INLINE_ void add_constraint(GodotConstraint2D *p_constraint) { constraints.insert(p_constraint); }
 	_FORCE_INLINE_ void remove_constraint(GodotConstraint2D *p_constraint) { constraints.erase(p_constraint); }
-	_FORCE_INLINE_ const Set<GodotConstraint2D *> &get_constraints() const { return constraints; }
+	_FORCE_INLINE_ const RBSet<GodotConstraint2D *> &get_constraints() const { return constraints; }
 	_FORCE_INLINE_ void clear_constraints() { constraints.clear(); }
 
 	void set_monitorable(bool p_monitorable);
diff --git a/servers/physics_2d/godot_physics_server_2d.cpp b/servers/physics_2d/godot_physics_server_2d.cpp
index 650a95c914..f82f2533f3 100644
--- a/servers/physics_2d/godot_physics_server_2d.cpp
+++ b/servers/physics_2d/godot_physics_server_2d.cpp
@@ -1179,7 +1179,7 @@ void GodotPhysicsServer2D::free(RID p_rid) {
 		GodotShape2D *shape = shape_owner.get_or_null(p_rid);
 
 		while (shape->get_owners().size()) {
-			GodotShapeOwner2D *so = shape->get_owners().front()->key();
+			GodotShapeOwner2D *so = shape->get_owners().begin()->key;
 			so->remove_shape(shape);
 		}
 
@@ -1250,7 +1250,7 @@ void GodotPhysicsServer2D::step(real_t p_step) {
 	island_count = 0;
 	active_objects = 0;
 	collision_pairs = 0;
-	for (Set<const GodotSpace2D *>::Element *E = active_spaces.front(); E; E = E->next()) {
+	for (RBSet<const GodotSpace2D *>::Element *E = active_spaces.front(); E; E = E->next()) {
 		stepper->step(const_cast<GodotSpace2D *>(E->get()), p_step);
 		island_count += E->get()->get_island_count();
 		active_objects += E->get()->get_active_objects();
@@ -1271,7 +1271,7 @@ void GodotPhysicsServer2D::flush_queries() {
 
 	uint64_t time_beg = OS::get_singleton()->get_ticks_usec();
 
-	for (Set<const GodotSpace2D *>::Element *E = active_spaces.front(); E; E = E->next()) {
+	for (RBSet<const GodotSpace2D *>::Element *E = active_spaces.front(); E; E = E->next()) {
 		GodotSpace2D *space = const_cast<GodotSpace2D *>(E->get());
 		space->call_queries();
 	}
@@ -1292,7 +1292,7 @@ void GodotPhysicsServer2D::flush_queries() {
 			total_time[i] = 0;
 		}
 
-		for (Set<const GodotSpace2D *>::Element *E = active_spaces.front(); E; E = E->next()) {
+		for (RBSet<const GodotSpace2D *>::Element *E = active_spaces.front(); E; E = E->next()) {
 			for (int i = 0; i < GodotSpace2D::ELAPSED_TIME_MAX; i++) {
 				total_time[i] += E->get()->get_elapsed_time(GodotSpace2D::ElapsedTime(i));
 			}
diff --git a/servers/physics_2d/godot_physics_server_2d.h b/servers/physics_2d/godot_physics_server_2d.h
index 0a84caadc5..55a7b39b9e 100644
--- a/servers/physics_2d/godot_physics_server_2d.h
+++ b/servers/physics_2d/godot_physics_server_2d.h
@@ -56,7 +56,7 @@ class GodotPhysicsServer2D : public PhysicsServer2D {
 	bool flushing_queries = false;
 
 	GodotStep2D *stepper = nullptr;
-	Set<const GodotSpace2D *> active_spaces;
+	RBSet<const GodotSpace2D *> active_spaces;
 
 	mutable RID_PtrOwner<GodotShape2D, true> shape_owner;
 	mutable RID_PtrOwner<GodotSpace2D, true> space_owner;
diff --git a/servers/physics_2d/godot_shape_2d.cpp b/servers/physics_2d/godot_shape_2d.cpp
index 6c020f9e72..72ade3757b 100644
--- a/servers/physics_2d/godot_shape_2d.cpp
+++ b/servers/physics_2d/godot_shape_2d.cpp
@@ -50,20 +50,20 @@ Vector2 GodotShape2D::get_support(const Vector2 &p_normal) const {
 }
 
 void GodotShape2D::add_owner(GodotShapeOwner2D *p_owner) {
-	Map<GodotShapeOwner2D *, int>::Element *E = owners.find(p_owner);
+	HashMap<GodotShapeOwner2D *, int>::Iterator E = owners.find(p_owner);
 	if (E) {
-		E->get()++;
+		E->value++;
 	} else {
 		owners[p_owner] = 1;
 	}
 }
 
 void GodotShape2D::remove_owner(GodotShapeOwner2D *p_owner) {
-	Map<GodotShapeOwner2D *, int>::Element *E = owners.find(p_owner);
+	HashMap<GodotShapeOwner2D *, 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);
 	}
 }
 
@@ -71,7 +71,7 @@ bool GodotShape2D::is_owner(GodotShapeOwner2D *p_owner) const {
 	return owners.has(p_owner);
 }
 
-const Map<GodotShapeOwner2D *, int> &GodotShape2D::get_owners() const {
+const HashMap<GodotShapeOwner2D *, int> &GodotShape2D::get_owners() const {
 	return owners;
 }
 
@@ -841,7 +841,7 @@ void GodotConcavePolygonShape2D::set_data(const Variant &p_data) {
 
 		const Vector2 *arr = p2arr.ptr();
 
-		Map<Point2, int> pointmap;
+		HashMap<Point2, int> pointmap;
 		for (int i = 0; i < len; i += 2) {
 			Point2 p1 = arr[i];
 			Point2 p2 = arr[i + 1];
@@ -868,7 +868,7 @@ void GodotConcavePolygonShape2D::set_data(const Variant &p_data) {
 		}
 
 		points.resize(pointmap.size());
-		aabb.position = pointmap.front()->key();
+		aabb.position = pointmap.begin()->key;
 		for (const KeyValue<Point2, int> &E : pointmap) {
 			aabb.expand_to(E.key);
 			points.write[E.value] = E.key;
diff --git a/servers/physics_2d/godot_shape_2d.h b/servers/physics_2d/godot_shape_2d.h
index 9b3477cea8..cede01e18d 100644
--- a/servers/physics_2d/godot_shape_2d.h
+++ b/servers/physics_2d/godot_shape_2d.h
@@ -50,7 +50,7 @@ class GodotShape2D {
 	bool configured = false;
 	real_t custom_bias = 0.0;
 
-	Map<GodotShapeOwner2D *, int> owners;
+	HashMap<GodotShapeOwner2D *, int> owners;
 
 protected:
 	void configure(const Rect2 &p_aabb);
@@ -86,7 +86,7 @@ public:
 	void add_owner(GodotShapeOwner2D *p_owner);
 	void remove_owner(GodotShapeOwner2D *p_owner);
 	bool is_owner(GodotShapeOwner2D *p_owner) const;
-	const Map<GodotShapeOwner2D *, int> &get_owners() const;
+	const HashMap<GodotShapeOwner2D *, int> &get_owners() const;
 
 	_FORCE_INLINE_ void get_supports_transformed_cast(const Vector2 &p_cast, const Vector2 &p_normal, const Transform2D &p_xform, Vector2 *r_supports, int &r_amount) const {
 		get_supports(p_xform.basis_xform_inv(p_normal).normalized(), r_supports, r_amount);
diff --git a/servers/physics_2d/godot_space_2d.cpp b/servers/physics_2d/godot_space_2d.cpp
index 3ff7ab86bb..731eab2dfe 100644
--- a/servers/physics_2d/godot_space_2d.cpp
+++ b/servers/physics_2d/godot_space_2d.cpp
@@ -1073,7 +1073,7 @@ void GodotSpace2D::remove_object(GodotCollisionObject2D *p_object) {
 	objects.erase(p_object);
 }
 
-const Set<GodotCollisionObject2D *> &GodotSpace2D::get_objects() const {
+const RBSet<GodotCollisionObject2D *> &GodotSpace2D::get_objects() const {
 	return objects;
 }
 
diff --git a/servers/physics_2d/godot_space_2d.h b/servers/physics_2d/godot_space_2d.h
index 5d97721176..e8b05fa4f9 100644
--- a/servers/physics_2d/godot_space_2d.h
+++ b/servers/physics_2d/godot_space_2d.h
@@ -92,7 +92,7 @@ private:
 	static void *_broadphase_pair(GodotCollisionObject2D *A, int p_subindex_A, GodotCollisionObject2D *B, int p_subindex_B, void *p_self);
 	static void _broadphase_unpair(GodotCollisionObject2D *A, int p_subindex_A, GodotCollisionObject2D *B, int p_subindex_B, void *p_data, void *p_self);
 
-	Set<GodotCollisionObject2D *> objects;
+	RBSet<GodotCollisionObject2D *> objects;
 
 	GodotArea2D *area = nullptr;
 
@@ -156,7 +156,7 @@ public:
 
 	void add_object(GodotCollisionObject2D *p_object);
 	void remove_object(GodotCollisionObject2D *p_object);
-	const Set<GodotCollisionObject2D *> &get_objects() const;
+	const RBSet<GodotCollisionObject2D *> &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_2d/godot_step_2d.cpp b/servers/physics_2d/godot_step_2d.cpp
index fd72038be3..0df5c1aabc 100644
--- a/servers/physics_2d/godot_step_2d.cpp
+++ b/servers/physics_2d/godot_step_2d.cpp
@@ -168,7 +168,7 @@ void GodotStep2D::step(GodotSpace2D *p_space, real_t p_delta) {
 	const SelfList<GodotArea2D>::List &aml = p_space->get_moved_area_list();
 
 	while (aml.first()) {
-		for (const Set<GodotConstraint2D *>::Element *E = aml.first()->self()->get_constraints().front(); E; E = E->next()) {
+		for (const RBSet<GodotConstraint2D *>::Element *E = aml.first()->self()->get_constraints().front(); E; E = E->next()) {
 			GodotConstraint2D *constraint = E->get();
 			if (constraint->get_island_step() == _step) {
 				continue;