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!
author: reduz <reduzio@gmail.com> 2022-05-13 15:04:37 +0200
committer: Rémi Verschelde <rverschelde@gmail.com> 2022-05-16 10:37:48 +0200
commit: 746dddc0673d7261f19b1e056e90e6e3a49ef33a (patch)
tree: 434b526eb286850ebccc6d2c998a7d90fdb8b5e2 /scene/2d
parent: 396def9b66c476f7834604adb7136ca903ed01be (diff)
download: redot-engine-746dddc0673d7261f19b1e056e90e6e3a49ef33a.tar.gz
12 files changed, 204 insertions, 202 deletions
diff --git a/scene/2d/area_2d.cpp b/scene/2d/area_2d.cpp
index 70b9b769cd..9699f784a2 100644
--- a/scene/2d/area_2d.cpp
+++ b/scene/2d/area_2d.cpp
@@ -137,14 +137,14 @@ void Area2D::_body_enter_tree(ObjectID p_id) {
 	Node *node = Object::cast_to<Node>(obj);
 	ERR_FAIL_COND(!node);
 
-	Map<ObjectID, BodyState>::Element *E = body_map.find(p_id);
+	HashMap<ObjectID, BodyState>::Iterator E = body_map.find(p_id);
 	ERR_FAIL_COND(!E);
-	ERR_FAIL_COND(E->get().in_tree);
+	ERR_FAIL_COND(E->value.in_tree);
 
-	E->get().in_tree = true;
+	E->value.in_tree = true;
 	emit_signal(SceneStringNames::get_singleton()->body_entered, node);
-	for (int i = 0; i < E->get().shapes.size(); i++) {
-		emit_signal(SceneStringNames::get_singleton()->body_shape_entered, E->get().rid, node, E->get().shapes[i].body_shape, E->get().shapes[i].area_shape);
+	for (int i = 0; i < E->value.shapes.size(); i++) {
+		emit_signal(SceneStringNames::get_singleton()->body_shape_entered, E->value.rid, node, E->value.shapes[i].body_shape, E->value.shapes[i].area_shape);
 	}
 }
 
@@ -152,13 +152,13 @@ void Area2D::_body_exit_tree(ObjectID p_id) {
 	Object *obj = ObjectDB::get_instance(p_id);
 	Node *node = Object::cast_to<Node>(obj);
 	ERR_FAIL_COND(!node);
-	Map<ObjectID, BodyState>::Element *E = body_map.find(p_id);
+	HashMap<ObjectID, BodyState>::Iterator E = body_map.find(p_id);
 	ERR_FAIL_COND(!E);
-	ERR_FAIL_COND(!E->get().in_tree);
-	E->get().in_tree = false;
+	ERR_FAIL_COND(!E->value.in_tree);
+	E->value.in_tree = false;
 	emit_signal(SceneStringNames::get_singleton()->body_exited, node);
-	for (int i = 0; i < E->get().shapes.size(); i++) {
-		emit_signal(SceneStringNames::get_singleton()->body_shape_exited, E->get().rid, node, E->get().shapes[i].body_shape, E->get().shapes[i].area_shape);
+	for (int i = 0; i < E->value.shapes.size(); i++) {
+		emit_signal(SceneStringNames::get_singleton()->body_shape_exited, E->value.rid, node, E->value.shapes[i].body_shape, E->value.shapes[i].area_shape);
 	}
 }
 
@@ -169,7 +169,7 @@ void Area2D::_body_inout(int p_status, const RID &p_body, ObjectID p_instance, i
 	Object *obj = ObjectDB::get_instance(objid);
 	Node *node = Object::cast_to<Node>(obj);
 
-	Map<ObjectID, BodyState>::Element *E = body_map.find(objid);
+	HashMap<ObjectID, BodyState>::Iterator E = body_map.find(objid);
 
 	if (!body_in && !E) {
 		return; //does not exist because it was likely removed from the tree
@@ -180,36 +180,36 @@ void Area2D::_body_inout(int p_status, const RID &p_body, ObjectID p_instance, i
 	if (body_in) {
 		if (!E) {
 			E = body_map.insert(objid, BodyState());
-			E->get().rid = p_body;
-			E->get().rc = 0;
-			E->get().in_tree = node && node->is_inside_tree();
+			E->value.rid = p_body;
+			E->value.rc = 0;
+			E->value.in_tree = node && node->is_inside_tree();
 			if (node) {
 				node->connect(SceneStringNames::get_singleton()->tree_entered, callable_mp(this, &Area2D::_body_enter_tree), make_binds(objid));
 				node->connect(SceneStringNames::get_singleton()->tree_exiting, callable_mp(this, &Area2D::_body_exit_tree), make_binds(objid));
-				if (E->get().in_tree) {
+				if (E->value.in_tree) {
 					emit_signal(SceneStringNames::get_singleton()->body_entered, node);
 				}
 			}
 		}
-		E->get().rc++;
+		E->value.rc++;
 		if (node) {
-			E->get().shapes.insert(ShapePair(p_body_shape, p_area_shape));
+			E->value.shapes.insert(ShapePair(p_body_shape, p_area_shape));
 		}
 
-		if (!node || E->get().in_tree) {
+		if (!node || E->value.in_tree) {
 			emit_signal(SceneStringNames::get_singleton()->body_shape_entered, p_body, node, p_body_shape, p_area_shape);
 		}
 
 	} else {
-		E->get().rc--;
+		E->value.rc--;
 
 		if (node) {
-			E->get().shapes.erase(ShapePair(p_body_shape, p_area_shape));
+			E->value.shapes.erase(ShapePair(p_body_shape, p_area_shape));
 		}
 
-		bool in_tree = E->get().in_tree;
-		if (E->get().rc == 0) {
-			body_map.erase(E);
+		bool in_tree = E->value.in_tree;
+		if (E->value.rc == 0) {
+			body_map.remove(E);
 			if (node) {
 				node->disconnect(SceneStringNames::get_singleton()->tree_entered, callable_mp(this, &Area2D::_body_enter_tree));
 				node->disconnect(SceneStringNames::get_singleton()->tree_exiting, callable_mp(this, &Area2D::_body_exit_tree));
@@ -231,14 +231,14 @@ void Area2D::_area_enter_tree(ObjectID p_id) {
 	Node *node = Object::cast_to<Node>(obj);
 	ERR_FAIL_COND(!node);
 
-	Map<ObjectID, AreaState>::Element *E = area_map.find(p_id);
+	HashMap<ObjectID, AreaState>::Iterator E = area_map.find(p_id);
 	ERR_FAIL_COND(!E);
-	ERR_FAIL_COND(E->get().in_tree);
+	ERR_FAIL_COND(E->value.in_tree);
 
-	E->get().in_tree = true;
+	E->value.in_tree = true;
 	emit_signal(SceneStringNames::get_singleton()->area_entered, node);
-	for (int i = 0; i < E->get().shapes.size(); i++) {
-		emit_signal(SceneStringNames::get_singleton()->area_shape_entered, E->get().rid, node, E->get().shapes[i].area_shape, E->get().shapes[i].self_shape);
+	for (int i = 0; i < E->value.shapes.size(); i++) {
+		emit_signal(SceneStringNames::get_singleton()->area_shape_entered, E->value.rid, node, E->value.shapes[i].area_shape, E->value.shapes[i].self_shape);
 	}
 }
 
@@ -246,13 +246,13 @@ void Area2D::_area_exit_tree(ObjectID p_id) {
 	Object *obj = ObjectDB::get_instance(p_id);
 	Node *node = Object::cast_to<Node>(obj);
 	ERR_FAIL_COND(!node);
-	Map<ObjectID, AreaState>::Element *E = area_map.find(p_id);
+	HashMap<ObjectID, AreaState>::Iterator E = area_map.find(p_id);
 	ERR_FAIL_COND(!E);
-	ERR_FAIL_COND(!E->get().in_tree);
-	E->get().in_tree = false;
+	ERR_FAIL_COND(!E->value.in_tree);
+	E->value.in_tree = false;
 	emit_signal(SceneStringNames::get_singleton()->area_exited, node);
-	for (int i = 0; i < E->get().shapes.size(); i++) {
-		emit_signal(SceneStringNames::get_singleton()->area_shape_exited, E->get().rid, node, E->get().shapes[i].area_shape, E->get().shapes[i].self_shape);
+	for (int i = 0; i < E->value.shapes.size(); i++) {
+		emit_signal(SceneStringNames::get_singleton()->area_shape_exited, E->value.rid, node, E->value.shapes[i].area_shape, E->value.shapes[i].self_shape);
 	}
 }
 
@@ -263,7 +263,7 @@ void Area2D::_area_inout(int p_status, const RID &p_area, ObjectID p_instance, i
 	Object *obj = ObjectDB::get_instance(objid);
 	Node *node = Object::cast_to<Node>(obj);
 
-	Map<ObjectID, AreaState>::Element *E = area_map.find(objid);
+	HashMap<ObjectID, AreaState>::Iterator E = area_map.find(objid);
 
 	if (!area_in && !E) {
 		return; //likely removed from the tree
@@ -273,36 +273,36 @@ void Area2D::_area_inout(int p_status, const RID &p_area, ObjectID p_instance, i
 	if (area_in) {
 		if (!E) {
 			E = area_map.insert(objid, AreaState());
-			E->get().rid = p_area;
-			E->get().rc = 0;
-			E->get().in_tree = node && node->is_inside_tree();
+			E->value.rid = p_area;
+			E->value.rc = 0;
+			E->value.in_tree = node && node->is_inside_tree();
 			if (node) {
 				node->connect(SceneStringNames::get_singleton()->tree_entered, callable_mp(this, &Area2D::_area_enter_tree), make_binds(objid));
 				node->connect(SceneStringNames::get_singleton()->tree_exiting, callable_mp(this, &Area2D::_area_exit_tree), make_binds(objid));
-				if (E->get().in_tree) {
+				if (E->value.in_tree) {
 					emit_signal(SceneStringNames::get_singleton()->area_entered, node);
 				}
 			}
 		}
-		E->get().rc++;
+		E->value.rc++;
 		if (node) {
-			E->get().shapes.insert(AreaShapePair(p_area_shape, p_self_shape));
+			E->value.shapes.insert(AreaShapePair(p_area_shape, p_self_shape));
 		}
 
-		if (!node || E->get().in_tree) {
+		if (!node || E->value.in_tree) {
 			emit_signal(SceneStringNames::get_singleton()->area_shape_entered, p_area, node, p_area_shape, p_self_shape);
 		}
 
 	} else {
-		E->get().rc--;
+		E->value.rc--;
 
 		if (node) {
-			E->get().shapes.erase(AreaShapePair(p_area_shape, p_self_shape));
+			E->value.shapes.erase(AreaShapePair(p_area_shape, p_self_shape));
 		}
 
-		bool in_tree = E->get().in_tree;
-		if (E->get().rc == 0) {
-			area_map.erase(E);
+		bool in_tree = E->value.in_tree;
+		if (E->value.rc == 0) {
+			area_map.remove(E);
 			if (node) {
 				node->disconnect(SceneStringNames::get_singleton()->tree_entered, callable_mp(this, &Area2D::_area_enter_tree));
 				node->disconnect(SceneStringNames::get_singleton()->tree_exiting, callable_mp(this, &Area2D::_area_exit_tree));
@@ -323,7 +323,7 @@ void Area2D::_clear_monitoring() {
 	ERR_FAIL_COND_MSG(locked, "This function can't be used during the in/out signal.");
 
 	{
-		Map<ObjectID, BodyState> bmcopy = body_map;
+		HashMap<ObjectID, BodyState> bmcopy = body_map;
 		body_map.clear();
 		//disconnect all monitored stuff
 
@@ -351,7 +351,7 @@ void Area2D::_clear_monitoring() {
 	}
 
 	{
-		Map<ObjectID, AreaState> bmcopy = area_map;
+		HashMap<ObjectID, AreaState> bmcopy = area_map;
 		area_map.clear();
 		//disconnect all monitored stuff
 
@@ -461,20 +461,20 @@ TypedArray<Area2D> Area2D::get_overlapping_areas() const {
 
 bool Area2D::overlaps_area(Node *p_area) const {
 	ERR_FAIL_NULL_V(p_area, false);
-	const Map<ObjectID, AreaState>::Element *E = area_map.find(p_area->get_instance_id());
+	HashMap<ObjectID, AreaState>::ConstIterator E = area_map.find(p_area->get_instance_id());
 	if (!E) {
 		return false;
 	}
-	return E->get().in_tree;
+	return E->value.in_tree;
 }
 
 bool Area2D::overlaps_body(Node *p_body) const {
 	ERR_FAIL_NULL_V(p_body, false);
-	const Map<ObjectID, BodyState>::Element *E = body_map.find(p_body->get_instance_id());
+	HashMap<ObjectID, BodyState>::ConstIterator E = body_map.find(p_body->get_instance_id());
 	if (!E) {
 		return false;
 	}
-	return E->get().in_tree;
+	return E->value.in_tree;
 }
 
 void Area2D::set_audio_bus_override(bool p_override) {
diff --git a/scene/2d/area_2d.h b/scene/2d/area_2d.h
index a42e7722b0..a584420ced 100644
--- a/scene/2d/area_2d.h
+++ b/scene/2d/area_2d.h
@@ -94,7 +94,7 @@ private:
 		VSet<ShapePair> shapes;
 	};
 
-	Map<ObjectID, BodyState> body_map;
+	HashMap<ObjectID, BodyState> body_map;
 
 	void _area_inout(int p_status, const RID &p_area, ObjectID p_instance, int p_area_shape, int p_self_shape);
 
@@ -126,7 +126,7 @@ private:
 		VSet<AreaShapePair> shapes;
 	};
 
-	Map<ObjectID, AreaState> area_map;
+	HashMap<ObjectID, AreaState> area_map;
 	void _clear_monitoring();
 
 	bool audio_bus_override = false;
diff --git a/scene/2d/audio_stream_player_2d.cpp b/scene/2d/audio_stream_player_2d.cpp
index c1328badfb..624ef70468 100644
--- a/scene/2d/audio_stream_player_2d.cpp
+++ b/scene/2d/audio_stream_player_2d.cpp
@@ -148,7 +148,7 @@ void AudioStreamPlayer2D::_update_panning() {
 
 	Vector2 global_pos = get_global_position();
 
-	Set<Viewport *> viewports = world_2d->get_viewports();
+	RBSet<Viewport *> viewports = world_2d->get_viewports();
 	viewports.insert(get_viewport()); // TODO: This is a mediocre workaround for #50958. Remove when that bug is fixed!
 
 	volume_vector.resize(4);
diff --git a/scene/2d/collision_object_2d.h b/scene/2d/collision_object_2d.h
index f2b7eecc7b..997afee6c4 100644
--- a/scene/2d/collision_object_2d.h
+++ b/scene/2d/collision_object_2d.h
@@ -75,7 +75,7 @@ private:
 
 	int total_subshapes = 0;
 
-	Map<uint32_t, ShapeData> shapes;
+	RBMap<uint32_t, ShapeData> shapes;
 	bool only_update_transform_changes = false; // This is used for sync to physics.
 
 	void _apply_disabled();
diff --git a/scene/2d/navigation_region_2d.cpp b/scene/2d/navigation_region_2d.cpp
index 3cc9f3f2c4..f46453283c 100644
--- a/scene/2d/navigation_region_2d.cpp
+++ b/scene/2d/navigation_region_2d.cpp
@@ -302,19 +302,19 @@ void NavigationPolygon::make_polygons_from_outlines() {
 	polygons.clear();
 	vertices.clear();
 
-	Map<Vector2, int> points;
+	HashMap<Vector2, int> points;
 	for (List<TPPLPoly>::Element *I = out_poly.front(); I; I = I->next()) {
 		TPPLPoly &tp = I->get();
 
 		struct Polygon p;
 
 		for (int64_t i = 0; i < tp.GetNumPoints(); i++) {
-			Map<Vector2, int>::Element *E = points.find(tp[i]);
+			HashMap<Vector2, int>::Iterator E = points.find(tp[i]);
 			if (!E) {
 				E = points.insert(tp[i], vertices.size());
 				vertices.push_back(tp[i]);
 			}
-			p.indices.push_back(E->get());
+			p.indices.push_back(E->value);
 		}
 
 		polygons.push_back(p);
diff --git a/scene/2d/physics_body_2d.cpp b/scene/2d/physics_body_2d.cpp
index 88f68e4142..f345d8c3c9 100644
--- a/scene/2d/physics_body_2d.cpp
+++ b/scene/2d/physics_body_2d.cpp
@@ -339,17 +339,17 @@ void RigidDynamicBody2D::_body_enter_tree(ObjectID p_id) {
 	ERR_FAIL_COND(!node);
 
 	ERR_FAIL_COND(!contact_monitor);
-	Map<ObjectID, BodyState>::Element *E = contact_monitor->body_map.find(p_id);
+	HashMap<ObjectID, BodyState>::Iterator E = contact_monitor->body_map.find(p_id);
 	ERR_FAIL_COND(!E);
-	ERR_FAIL_COND(E->get().in_scene);
+	ERR_FAIL_COND(E->value.in_scene);
 
 	contact_monitor->locked = true;
 
-	E->get().in_scene = true;
+	E->value.in_scene = true;
 	emit_signal(SceneStringNames::get_singleton()->body_entered, node);
 
-	for (int i = 0; i < E->get().shapes.size(); i++) {
-		emit_signal(SceneStringNames::get_singleton()->body_shape_entered, E->get().rid, node, E->get().shapes[i].body_shape, E->get().shapes[i].local_shape);
+	for (int i = 0; i < E->value.shapes.size(); i++) {
+		emit_signal(SceneStringNames::get_singleton()->body_shape_entered, E->value.rid, node, E->value.shapes[i].body_shape, E->value.shapes[i].local_shape);
 	}
 
 	contact_monitor->locked = false;
@@ -360,17 +360,17 @@ void RigidDynamicBody2D::_body_exit_tree(ObjectID p_id) {
 	Node *node = Object::cast_to<Node>(obj);
 	ERR_FAIL_COND(!node);
 	ERR_FAIL_COND(!contact_monitor);
-	Map<ObjectID, BodyState>::Element *E = contact_monitor->body_map.find(p_id);
+	HashMap<ObjectID, BodyState>::Iterator E = contact_monitor->body_map.find(p_id);
 	ERR_FAIL_COND(!E);
-	ERR_FAIL_COND(!E->get().in_scene);
-	E->get().in_scene = false;
+	ERR_FAIL_COND(!E->value.in_scene);
+	E->value.in_scene = false;
 
 	contact_monitor->locked = true;
 
 	emit_signal(SceneStringNames::get_singleton()->body_exited, node);
 
-	for (int i = 0; i < E->get().shapes.size(); i++) {
-		emit_signal(SceneStringNames::get_singleton()->body_shape_exited, E->get().rid, node, E->get().shapes[i].body_shape, E->get().shapes[i].local_shape);
+	for (int i = 0; i < E->value.shapes.size(); i++) {
+		emit_signal(SceneStringNames::get_singleton()->body_shape_exited, E->value.rid, node, E->value.shapes[i].body_shape, E->value.shapes[i].local_shape);
 	}
 
 	contact_monitor->locked = false;
@@ -384,45 +384,45 @@ void RigidDynamicBody2D::_body_inout(int p_status, const RID &p_body, ObjectID p
 	Node *node = Object::cast_to<Node>(obj);
 
 	ERR_FAIL_COND(!contact_monitor);
-	Map<ObjectID, BodyState>::Element *E = contact_monitor->body_map.find(objid);
+	HashMap<ObjectID, BodyState>::Iterator E = contact_monitor->body_map.find(objid);
 
 	ERR_FAIL_COND(!body_in && !E);
 
 	if (body_in) {
 		if (!E) {
 			E = contact_monitor->body_map.insert(objid, BodyState());
-			E->get().rid = p_body;
-			//E->get().rc=0;
-			E->get().in_scene = node && node->is_inside_tree();
+			E->value.rid = p_body;
+			//E->value.rc=0;
+			E->value.in_scene = node && node->is_inside_tree();
 			if (node) {
 				node->connect(SceneStringNames::get_singleton()->tree_entered, callable_mp(this, &RigidDynamicBody2D::_body_enter_tree), make_binds(objid));
 				node->connect(SceneStringNames::get_singleton()->tree_exiting, callable_mp(this, &RigidDynamicBody2D::_body_exit_tree), make_binds(objid));
-				if (E->get().in_scene) {
+				if (E->value.in_scene) {
 					emit_signal(SceneStringNames::get_singleton()->body_entered, node);
 				}
 			}
 
-			//E->get().rc++;
+			//E->value.rc++;
 		}
 
 		if (node) {
-			E->get().shapes.insert(ShapePair(p_body_shape, p_local_shape));
+			E->value.shapes.insert(ShapePair(p_body_shape, p_local_shape));
 		}
 
-		if (E->get().in_scene) {
+		if (E->value.in_scene) {
 			emit_signal(SceneStringNames::get_singleton()->body_shape_entered, p_body, node, p_body_shape, p_local_shape);
 		}
 
 	} else {
-		//E->get().rc--;
+		//E->value.rc--;
 
 		if (node) {
-			E->get().shapes.erase(ShapePair(p_body_shape, p_local_shape));
+			E->value.shapes.erase(ShapePair(p_body_shape, p_local_shape));
 		}
 
-		bool in_scene = E->get().in_scene;
+		bool in_scene = E->value.in_scene;
 
-		if (E->get().shapes.is_empty()) {
+		if (E->value.shapes.is_empty()) {
 			if (node) {
 				node->disconnect(SceneStringNames::get_singleton()->tree_entered, callable_mp(this, &RigidDynamicBody2D::_body_enter_tree));
 				node->disconnect(SceneStringNames::get_singleton()->tree_exiting, callable_mp(this, &RigidDynamicBody2D::_body_exit_tree));
@@ -431,7 +431,7 @@ void RigidDynamicBody2D::_body_inout(int p_status, const RID &p_body, ObjectID p
 				}
 			}
 
-			contact_monitor->body_map.erase(E);
+			contact_monitor->body_map.remove(E);
 		}
 		if (node && in_scene) {
 			emit_signal(SceneStringNames::get_singleton()->body_shape_exited, p_body, node, p_body_shape, p_local_shape);
@@ -494,7 +494,7 @@ void RigidDynamicBody2D::_body_state_changed(PhysicsDirectBodyState2D *p_state)
 			int local_shape = p_state->get_contact_local_shape(i);
 			int shape = p_state->get_contact_collider_shape(i);
 
-			Map<ObjectID, BodyState>::Element *E = contact_monitor->body_map.find(obj);
+			HashMap<ObjectID, BodyState>::Iterator E = contact_monitor->body_map.find(obj);
 			if (!E) {
 				toadd[toadd_count].rid = rid;
 				toadd[toadd_count].local_shape = local_shape;
@@ -505,7 +505,7 @@ void RigidDynamicBody2D::_body_state_changed(PhysicsDirectBodyState2D *p_state)
 			}
 
 			ShapePair sp(shape, local_shape);
-			int idx = E->get().shapes.find(sp);
+			int idx = E->value.shapes.find(sp);
 			if (idx == -1) {
 				toadd[toadd_count].rid = rid;
 				toadd[toadd_count].local_shape = local_shape;
@@ -515,7 +515,7 @@ void RigidDynamicBody2D::_body_state_changed(PhysicsDirectBodyState2D *p_state)
 				continue;
 			}
 
-			E->get().shapes[idx].tagged = true;
+			E->value.shapes[idx].tagged = true;
 		}
 
 		//put the ones to remove
diff --git a/scene/2d/physics_body_2d.h b/scene/2d/physics_body_2d.h
index 1e4483b4d0..7401fc7578 100644
--- a/scene/2d/physics_body_2d.h
+++ b/scene/2d/physics_body_2d.h
@@ -200,7 +200,7 @@ private:
 
 	struct ContactMonitor {
 		bool locked = false;
-		Map<ObjectID, BodyState> body_map;
+		HashMap<ObjectID, BodyState> body_map;
 	};
 
 	ContactMonitor *contact_monitor = nullptr;
diff --git a/scene/2d/ray_cast_2d.h b/scene/2d/ray_cast_2d.h
index 2c6f2d5c00..b809bc4b8e 100644
--- a/scene/2d/ray_cast_2d.h
+++ b/scene/2d/ray_cast_2d.h
@@ -44,7 +44,7 @@ class RayCast2D : public Node2D {
 	int against_shape = 0;
 	Vector2 collision_point;
 	Vector2 collision_normal;
-	Set<RID> exclude;
+	RBSet<RID> exclude;
 	uint32_t collision_mask = 1;
 	bool exclude_parent_body = true;
 
diff --git a/scene/2d/shape_cast_2d.h b/scene/2d/shape_cast_2d.h
index 15436d6e3d..78125b08bd 100644
--- a/scene/2d/shape_cast_2d.h
+++ b/scene/2d/shape_cast_2d.h
@@ -46,7 +46,7 @@ class ShapeCast2D : public Node2D {
 	RID shape_rid;
 	Vector2 target_position = Vector2(0, 50);
 
-	Set<RID> exclude;
+	RBSet<RID> exclude;
 	real_t margin = 0.0;
 	uint32_t collision_mask = 1;
 	bool exclude_parent_body = true;
diff --git a/scene/2d/tile_map.cpp b/scene/2d/tile_map.cpp
index cab57146b1..19c341c1e1 100644
--- a/scene/2d/tile_map.cpp
+++ b/scene/2d/tile_map.cpp
@@ -34,8 +34,8 @@
 #include "scene/resources/world_2d.h"
 #include "servers/navigation_server_2d.h"
 
-Map<Vector2i, TileSet::CellNeighbor> TileMap::TerrainConstraint::get_overlapping_coords_and_peering_bits() const {
-	Map<Vector2i, TileSet::CellNeighbor> output;
+HashMap<Vector2i, TileSet::CellNeighbor> TileMap::TerrainConstraint::get_overlapping_coords_and_peering_bits() const {
+	HashMap<Vector2i, TileSet::CellNeighbor> output;
 	Ref<TileSet> tile_set = tile_map->get_tileset();
 	ERR_FAIL_COND_V(!tile_set.is_valid(), output);
 
@@ -742,7 +742,7 @@ Vector2i TileMap::_coords_to_quadrant_coords(int p_layer, const Vector2i &p_coor
 			p_coords.y > 0 ? p_coords.y / quadrant_size : (p_coords.y - (quadrant_size - 1)) / quadrant_size);
 }
 
-Map<Vector2i, TileMapQuadrant>::Element *TileMap::_create_quadrant(int p_layer, const Vector2i &p_qk) {
+HashMap<Vector2i, TileMapQuadrant>::Iterator TileMap::_create_quadrant(int p_layer, const Vector2i &p_qk) {
 	ERR_FAIL_INDEX_V(p_layer, (int)layers.size(), nullptr);
 
 	TileMapQuadrant q;
@@ -765,9 +765,9 @@ Map<Vector2i, TileMapQuadrant>::Element *TileMap::_create_quadrant(int p_layer,
 	return layers[p_layer].quadrant_map.insert(p_qk, q);
 }
 
-void TileMap::_make_quadrant_dirty(Map<Vector2i, TileMapQuadrant>::Element *Q) {
+void TileMap::_make_quadrant_dirty(HashMap<Vector2i, TileMapQuadrant>::Iterator Q) {
 	// Make the given quadrant dirty, then trigger an update later.
-	TileMapQuadrant &q = Q->get();
+	TileMapQuadrant &q = Q->value;
 	if (!q.dirty_list_element.in_list()) {
 		layers[q.layer].dirty_quadrant_list.add(&q.dirty_list_element);
 	}
@@ -810,7 +810,7 @@ void TileMap::_update_dirty_quadrants() {
 		for (SelfList<TileMapQuadrant> *q = dirty_quadrant_list.first(); q; q = q->next()) {
 			q->self()->map_to_world.clear();
 			q->self()->world_to_map.clear();
-			for (Set<Vector2i>::Element *E = q->self()->cells.front(); E; E = E->next()) {
+			for (RBSet<Vector2i>::Element *E = q->self()->cells.front(); E; E = E->next()) {
 				Vector2i pk = E->get();
 				Vector2i pk_world_coords = map_to_world(pk);
 				q->self()->map_to_world[pk] = pk_world_coords;
@@ -871,18 +871,18 @@ void TileMap::_recreate_layer_internals(int p_layer) {
 	_rendering_update_layer(p_layer);
 
 	// Recreate the quadrants.
-	const Map<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
+	const HashMap<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
 	for (const KeyValue<Vector2i, TileMapCell> &E : tile_map) {
 		Vector2i qk = _coords_to_quadrant_coords(p_layer, Vector2i(E.key.x, E.key.y));
 
-		Map<Vector2i, TileMapQuadrant>::Element *Q = layers[p_layer].quadrant_map.find(qk);
+		HashMap<Vector2i, TileMapQuadrant>::Iterator Q = layers[p_layer].quadrant_map.find(qk);
 		if (!Q) {
 			Q = _create_quadrant(p_layer, qk);
-			layers[p_layer].dirty_quadrant_list.add(&Q->get().dirty_list_element);
+			layers[p_layer].dirty_quadrant_list.add(&Q->value.dirty_list_element);
 		}
 
 		Vector2i pk = E.key;
-		Q->get().cells.insert(pk);
+		Q->value.cells.insert(pk);
 
 		_make_quadrant_dirty(Q);
 	}
@@ -896,9 +896,9 @@ void TileMap::_recreate_internals() {
 	}
 }
 
-void TileMap::_erase_quadrant(Map<Vector2i, TileMapQuadrant>::Element *Q) {
+void TileMap::_erase_quadrant(HashMap<Vector2i, TileMapQuadrant>::Iterator Q) {
 	// Remove a quadrant.
-	TileMapQuadrant *q = &(Q->get());
+	TileMapQuadrant *q = &(Q->value);
 
 	// Call the cleanup_quadrant method on plugins.
 	if (tile_set.is_valid()) {
@@ -917,7 +917,7 @@ void TileMap::_erase_quadrant(Map<Vector2i, TileMapQuadrant>::Element *Q) {
 	RenderingServer *rs = RenderingServer::get_singleton();
 	rs->free(q->debug_canvas_item);
 
-	layers[q->layer].quadrant_map.erase(Q);
+	layers[q->layer].quadrant_map.remove(Q);
 	rect_cache_dirty = true;
 }
 
@@ -926,7 +926,7 @@ void TileMap::_clear_layer_internals(int p_layer) {
 
 	// Clear quadrants.
 	while (layers[p_layer].quadrant_map.size()) {
-		_erase_quadrant(layers[p_layer].quadrant_map.front());
+		_erase_quadrant(layers[p_layer].quadrant_map.begin());
 	}
 
 	// Clear the layers internals.
@@ -954,15 +954,17 @@ void TileMap::_recompute_rect_cache() {
 	}
 
 	Rect2 r_total;
+	bool first = true;
 	for (unsigned int layer = 0; layer < layers.size(); layer++) {
-		for (const Map<Vector2i, TileMapQuadrant>::Element *E = layers[layer].quadrant_map.front(); E; E = E->next()) {
+		for (const KeyValue<Vector2i, TileMapQuadrant> &E : layers[layer].quadrant_map) {
 			Rect2 r;
-			r.position = map_to_world(E->key() * get_effective_quadrant_size(layer));
-			r.expand_to(map_to_world((E->key() + Vector2i(1, 0)) * get_effective_quadrant_size(layer)));
-			r.expand_to(map_to_world((E->key() + Vector2i(1, 1)) * get_effective_quadrant_size(layer)));
-			r.expand_to(map_to_world((E->key() + Vector2i(0, 1)) * get_effective_quadrant_size(layer)));
-			if (E == layers[layer].quadrant_map.front()) {
+			r.position = map_to_world(E.key * get_effective_quadrant_size(layer));
+			r.expand_to(map_to_world((E.key + Vector2i(1, 0)) * get_effective_quadrant_size(layer)));
+			r.expand_to(map_to_world((E.key + Vector2i(1, 1)) * get_effective_quadrant_size(layer)));
+			r.expand_to(map_to_world((E.key + Vector2i(0, 1)) * get_effective_quadrant_size(layer)));
+			if (first) {
 				r_total = r;
+				first = false;
 			} else {
 				r_total = r_total.merge(r);
 			}
@@ -1201,7 +1203,7 @@ void TileMap::_rendering_update_dirty_quadrants(SelfList<TileMapQuadrant>::List
 
 		for (int layer = 0; layer < (int)layers.size(); layer++) {
 			// Sort the quadrants coords per world coordinates
-			Map<Vector2i, Vector2i, TileMapQuadrant::CoordsWorldComparator> world_to_map;
+			RBMap<Vector2i, Vector2i, TileMapQuadrant::CoordsWorldComparator> world_to_map;
 			for (const KeyValue<Vector2i, TileMapQuadrant> &E : layers[layer].quadrant_map) {
 				world_to_map[map_to_world(E.key)] = E.key;
 			}
@@ -1248,7 +1250,7 @@ void TileMap::_rendering_draw_quadrant_debug(TileMapQuadrant *p_quadrant) {
 	// Draw a placeholder for scenes needing one.
 	RenderingServer *rs = RenderingServer::get_singleton();
 	Vector2 quadrant_pos = map_to_world(p_quadrant->coords * get_effective_quadrant_size(p_quadrant->layer));
-	for (Set<Vector2i>::Element *E_cell = p_quadrant->cells.front(); E_cell; E_cell = E_cell->next()) {
+	for (RBSet<Vector2i>::Element *E_cell = p_quadrant->cells.front(); E_cell; E_cell = E_cell->next()) {
 		const TileMapCell &c = get_cell(p_quadrant->layer, E_cell->get(), true);
 
 		TileSetSource *source;
@@ -1462,7 +1464,7 @@ void TileMap::_physics_update_dirty_quadrants(SelfList<TileMapQuadrant>::List &r
 		q.bodies.clear();
 
 		// Recreate bodies and shapes.
-		for (Set<Vector2i>::Element *E_cell = q.cells.front(); E_cell; E_cell = E_cell->next()) {
+		for (RBSet<Vector2i>::Element *E_cell = q.cells.front(); E_cell; E_cell = E_cell->next()) {
 			TileMapCell c = get_cell(q.layer, E_cell->get(), true);
 
 			TileSetSource *source;
@@ -1659,7 +1661,7 @@ void TileMap::_navigation_update_dirty_quadrants(SelfList<TileMapQuadrant>::List
 		q.navigation_regions.clear();
 
 		// Get the navigation polygons and create regions.
-		for (Set<Vector2i>::Element *E_cell = q.cells.front(); E_cell; E_cell = E_cell->next()) {
+		for (RBSet<Vector2i>::Element *E_cell = q.cells.front(); E_cell; E_cell = E_cell->next()) {
 			TileMapCell c = get_cell(q.layer, E_cell->get(), true);
 
 			TileSetSource *source;
@@ -1748,7 +1750,7 @@ void TileMap::_navigation_draw_quadrant_debug(TileMapQuadrant *p_quadrant) {
 
 	Vector2 quadrant_pos = map_to_world(p_quadrant->coords * get_effective_quadrant_size(p_quadrant->layer));
 
-	for (Set<Vector2i>::Element *E_cell = p_quadrant->cells.front(); E_cell; E_cell = E_cell->next()) {
+	for (RBSet<Vector2i>::Element *E_cell = p_quadrant->cells.front(); E_cell; E_cell = E_cell->next()) {
 		TileMapCell c = get_cell(p_quadrant->layer, E_cell->get(), true);
 
 		TileSetSource *source;
@@ -1823,7 +1825,7 @@ void TileMap::_scenes_update_dirty_quadrants(SelfList<TileMapQuadrant>::List &r_
 		q.scenes.clear();
 
 		// Recreate the scenes.
-		for (Set<Vector2i>::Element *E_cell = q.cells.front(); E_cell; E_cell = E_cell->next()) {
+		for (RBSet<Vector2i>::Element *E_cell = q.cells.front(); E_cell; E_cell = E_cell->next()) {
 			const TileMapCell &c = get_cell(q.layer, E_cell->get(), true);
 
 			TileSetSource *source;
@@ -1881,7 +1883,7 @@ void TileMap::_scenes_draw_quadrant_debug(TileMapQuadrant *p_quadrant) {
 	// Draw a placeholder for scenes needing one.
 	RenderingServer *rs = RenderingServer::get_singleton();
 	Vector2 quadrant_pos = map_to_world(p_quadrant->coords * get_effective_quadrant_size(p_quadrant->layer));
-	for (Set<Vector2i>::Element *E_cell = p_quadrant->cells.front(); E_cell; E_cell = E_cell->next()) {
+	for (RBSet<Vector2i>::Element *E_cell = p_quadrant->cells.front(); E_cell; E_cell = E_cell->next()) {
 		const TileMapCell &c = get_cell(p_quadrant->layer, E_cell->get(), true);
 
 		TileSetSource *source;
@@ -1923,9 +1925,9 @@ void TileMap::set_cell(int p_layer, const Vector2i &p_coords, int p_source_id, c
 	ERR_FAIL_INDEX(p_layer, (int)layers.size());
 
 	// Set the current cell tile (using integer position).
-	Map<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
+	HashMap<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
 	Vector2i pk(p_coords);
-	Map<Vector2i, TileMapCell>::Element *E = tile_map.find(pk);
+	HashMap<Vector2i, TileMapCell>::Iterator E = tile_map.find(pk);
 
 	int source_id = p_source_id;
 	Vector2i atlas_coords = p_atlas_coords;
@@ -1946,7 +1948,7 @@ void TileMap::set_cell(int p_layer, const Vector2i &p_coords, int p_source_id, c
 	// Get the quadrant
 	Vector2i qk = _coords_to_quadrant_coords(p_layer, pk);
 
-	Map<Vector2i, TileMapQuadrant>::Element *Q = layers[p_layer].quadrant_map.find(qk);
+	HashMap<Vector2i, TileMapQuadrant>::Iterator Q = layers[p_layer].quadrant_map.find(qk);
 
 	if (source_id == TileSet::INVALID_SOURCE) {
 		// Erase existing cell in the tile map.
@@ -1954,7 +1956,7 @@ void TileMap::set_cell(int p_layer, const Vector2i &p_coords, int p_source_id, c
 
 		// Erase existing cell in the quadrant.
 		ERR_FAIL_COND(!Q);
-		TileMapQuadrant &q = Q->get();
+		TileMapQuadrant &q = Q->value;
 
 		q.cells.erase(pk);
 
@@ -1975,18 +1977,18 @@ void TileMap::set_cell(int p_layer, const Vector2i &p_coords, int p_source_id, c
 			if (!Q) {
 				Q = _create_quadrant(p_layer, qk);
 			}
-			TileMapQuadrant &q = Q->get();
+			TileMapQuadrant &q = Q->value;
 			q.cells.insert(pk);
 
 		} else {
 			ERR_FAIL_COND(!Q); // TileMapQuadrant should exist...
 
-			if (E->get().source_id == source_id && E->get().get_atlas_coords() == atlas_coords && E->get().alternative_tile == alternative_tile) {
+			if (E->value.source_id == source_id && E->value.get_atlas_coords() == atlas_coords && E->value.alternative_tile == alternative_tile) {
 				return; // Nothing changed.
 			}
 		}
 
-		TileMapCell &c = E->get();
+		TileMapCell &c = E->value;
 
 		c.source_id = source_id;
 		c.set_atlas_coords(atlas_coords);
@@ -2005,57 +2007,57 @@ int TileMap::get_cell_source_id(int p_layer, const Vector2i &p_coords, bool p_us
 	ERR_FAIL_INDEX_V(p_layer, (int)layers.size(), TileSet::INVALID_SOURCE);
 
 	// Get a cell source id from position
-	const Map<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
-	const Map<Vector2i, TileMapCell>::Element *E = tile_map.find(p_coords);
+	const HashMap<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
+	HashMap<Vector2i, TileMapCell>::ConstIterator E = tile_map.find(p_coords);
 
 	if (!E) {
 		return TileSet::INVALID_SOURCE;
 	}
 
 	if (p_use_proxies && tile_set.is_valid()) {
-		Array proxyed = tile_set->map_tile_proxy(E->get().source_id, E->get().get_atlas_coords(), E->get().alternative_tile);
+		Array proxyed = tile_set->map_tile_proxy(E->value.source_id, E->value.get_atlas_coords(), E->value.alternative_tile);
 		return proxyed[0];
 	}
 
-	return E->get().source_id;
+	return E->value.source_id;
 }
 
 Vector2i TileMap::get_cell_atlas_coords(int p_layer, const Vector2i &p_coords, bool p_use_proxies) const {
 	ERR_FAIL_INDEX_V(p_layer, (int)layers.size(), TileSetSource::INVALID_ATLAS_COORDS);
 
 	// Get a cell source id from position
-	const Map<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
-	const Map<Vector2i, TileMapCell>::Element *E = tile_map.find(p_coords);
+	const HashMap<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
+	HashMap<Vector2i, TileMapCell>::ConstIterator E = tile_map.find(p_coords);
 
 	if (!E) {
 		return TileSetSource::INVALID_ATLAS_COORDS;
 	}
 
 	if (p_use_proxies && tile_set.is_valid()) {
-		Array proxyed = tile_set->map_tile_proxy(E->get().source_id, E->get().get_atlas_coords(), E->get().alternative_tile);
+		Array proxyed = tile_set->map_tile_proxy(E->value.source_id, E->value.get_atlas_coords(), E->value.alternative_tile);
 		return proxyed[1];
 	}
 
-	return E->get().get_atlas_coords();
+	return E->value.get_atlas_coords();
 }
 
 int TileMap::get_cell_alternative_tile(int p_layer, const Vector2i &p_coords, bool p_use_proxies) const {
 	ERR_FAIL_INDEX_V(p_layer, (int)layers.size(), TileSetSource::INVALID_TILE_ALTERNATIVE);
 
 	// Get a cell source id from position
-	const Map<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
-	const Map<Vector2i, TileMapCell>::Element *E = tile_map.find(p_coords);
+	const HashMap<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
+	HashMap<Vector2i, TileMapCell>::ConstIterator E = tile_map.find(p_coords);
 
 	if (!E) {
 		return TileSetSource::INVALID_TILE_ALTERNATIVE;
 	}
 
 	if (p_use_proxies && tile_set.is_valid()) {
-		Array proxyed = tile_set->map_tile_proxy(E->get().source_id, E->get().get_atlas_coords(), E->get().alternative_tile);
+		Array proxyed = tile_set->map_tile_proxy(E->value.source_id, E->value.get_atlas_coords(), E->value.alternative_tile);
 		return proxyed[2];
 	}
 
-	return E->get().alternative_tile;
+	return E->value.alternative_tile;
 }
 
 Ref<TileMapPattern> TileMap::get_pattern(int p_layer, TypedArray<Vector2i> p_coords_array) {
@@ -2147,13 +2149,13 @@ void TileMap::set_pattern(int p_layer, Vector2i p_position, const Ref<TileMapPat
 	}
 }
 
-Set<TileSet::TerrainsPattern> TileMap::_get_valid_terrains_patterns_for_constraints(int p_terrain_set, const Vector2i &p_position, Set<TerrainConstraint> p_constraints) {
+RBSet<TileSet::TerrainsPattern> TileMap::_get_valid_terrains_patterns_for_constraints(int p_terrain_set, const Vector2i &p_position, RBSet<TerrainConstraint> p_constraints) {
 	if (!tile_set.is_valid()) {
-		return Set<TileSet::TerrainsPattern>();
+		return RBSet<TileSet::TerrainsPattern>();
 	}
 
 	// Returns all tiles compatible with the given constraints.
-	Set<TileSet::TerrainsPattern> compatible_terrain_tile_patterns;
+	RBSet<TileSet::TerrainsPattern> compatible_terrain_tile_patterns;
 	for (TileSet::TerrainsPattern &terrain_pattern : tile_set->get_terrains_pattern_set(p_terrain_set)) {
 		int valid = true;
 		for (int i = 0; i < TileSet::CELL_NEIGHBOR_MAX; i++) {
@@ -2161,7 +2163,7 @@ Set<TileSet::TerrainsPattern> TileMap::_get_valid_terrains_patterns_for_constrai
 			if (tile_set->is_valid_peering_bit_terrain(p_terrain_set, bit)) {
 				// Check if the bit is compatible with the constraints.
 				TerrainConstraint terrain_bit_constraint = TerrainConstraint(this, p_position, bit, terrain_pattern.get_terrain(bit));
-				Set<TerrainConstraint>::Element *in_set_constraint_element = p_constraints.find(terrain_bit_constraint);
+				RBSet<TerrainConstraint>::Element *in_set_constraint_element = p_constraints.find(terrain_bit_constraint);
 				if (in_set_constraint_element && in_set_constraint_element->get().get_terrain() != terrain_bit_constraint.get_terrain()) {
 					valid = false;
 					break;
@@ -2177,17 +2179,17 @@ Set<TileSet::TerrainsPattern> TileMap::_get_valid_terrains_patterns_for_constrai
 	return compatible_terrain_tile_patterns;
 }
 
-Set<TileMap::TerrainConstraint> TileMap::get_terrain_constraints_from_removed_cells_list(int p_layer, const Set<Vector2i> &p_to_replace, int p_terrain_set, bool p_ignore_empty_terrains) const {
+RBSet<TileMap::TerrainConstraint> TileMap::get_terrain_constraints_from_removed_cells_list(int p_layer, const RBSet<Vector2i> &p_to_replace, int p_terrain_set, bool p_ignore_empty_terrains) const {
 	if (!tile_set.is_valid()) {
-		return Set<TerrainConstraint>();
+		return RBSet<TerrainConstraint>();
 	}
 
-	ERR_FAIL_INDEX_V(p_terrain_set, tile_set->get_terrain_sets_count(), Set<TerrainConstraint>());
-	ERR_FAIL_INDEX_V(p_layer, (int)layers.size(), Set<TerrainConstraint>());
+	ERR_FAIL_INDEX_V(p_terrain_set, tile_set->get_terrain_sets_count(), RBSet<TerrainConstraint>());
+	ERR_FAIL_INDEX_V(p_layer, (int)layers.size(), RBSet<TerrainConstraint>());
 
 	// Build a set of dummy constraints get the constrained points.
-	Set<TerrainConstraint> dummy_constraints;
-	for (Set<Vector2i>::Element *E = p_to_replace.front(); E; E = E->next()) {
+	RBSet<TerrainConstraint> dummy_constraints;
+	for (RBSet<Vector2i>::Element *E = p_to_replace.front(); E; E = E->next()) {
 		for (int i = 0; i < TileSet::CELL_NEIGHBOR_MAX; i++) { // Iterates over sides.
 			TileSet::CellNeighbor bit = TileSet::CellNeighbor(i);
 			if (tile_set->is_valid_peering_bit_terrain(p_terrain_set, bit)) {
@@ -2197,14 +2199,14 @@ Set<TileMap::TerrainConstraint> TileMap::get_terrain_constraints_from_removed_ce
 	}
 
 	// For each constrained point, we get all overlapping tiles, and select the most adequate terrain for it.
-	Set<TerrainConstraint> constraints;
-	for (Set<TerrainConstraint>::Element *E = dummy_constraints.front(); E; E = E->next()) {
+	RBSet<TerrainConstraint> constraints;
+	for (RBSet<TerrainConstraint>::Element *E = dummy_constraints.front(); E; E = E->next()) {
 		TerrainConstraint c = E->get();
 
-		Map<int, int> terrain_count;
+		HashMap<int, int> terrain_count;
 
 		// Count the number of occurrences per terrain.
-		Map<Vector2i, TileSet::CellNeighbor> overlapping_terrain_bits = c.get_overlapping_coords_and_peering_bits();
+		HashMap<Vector2i, TileSet::CellNeighbor> overlapping_terrain_bits = c.get_overlapping_coords_and_peering_bits();
 		for (const KeyValue<Vector2i, TileSet::CellNeighbor> &E_overlapping : overlapping_terrain_bits) {
 			if (!p_to_replace.has(E_overlapping.key)) {
 				TileData *neighbor_tile_data = nullptr;
@@ -2250,13 +2252,13 @@ Set<TileMap::TerrainConstraint> TileMap::get_terrain_constraints_from_removed_ce
 	return constraints;
 }
 
-Set<TileMap::TerrainConstraint> TileMap::get_terrain_constraints_from_added_tile(Vector2i p_position, int p_terrain_set, TileSet::TerrainsPattern p_terrains_pattern) const {
+RBSet<TileMap::TerrainConstraint> TileMap::get_terrain_constraints_from_added_tile(Vector2i p_position, int p_terrain_set, TileSet::TerrainsPattern p_terrains_pattern) const {
 	if (!tile_set.is_valid()) {
-		return Set<TerrainConstraint>();
+		return RBSet<TerrainConstraint>();
 	}
 
 	// Compute the constraints needed from the surrounding tiles.
-	Set<TerrainConstraint> output;
+	RBSet<TerrainConstraint> output;
 	for (uint32_t i = 0; i < TileSet::CELL_NEIGHBOR_MAX; i++) {
 		TileSet::CellNeighbor side = TileSet::CellNeighbor(i);
 		if (tile_set->is_valid_peering_bit_terrain(p_terrain_set, side)) {
@@ -2268,35 +2270,35 @@ Set<TileMap::TerrainConstraint> TileMap::get_terrain_constraints_from_added_tile
 	return output;
 }
 
-Map<Vector2i, TileSet::TerrainsPattern> TileMap::terrain_wave_function_collapse(const Set<Vector2i> &p_to_replace, int p_terrain_set, const Set<TerrainConstraint> p_constraints) {
+HashMap<Vector2i, TileSet::TerrainsPattern> TileMap::terrain_wave_function_collapse(const RBSet<Vector2i> &p_to_replace, int p_terrain_set, const RBSet<TerrainConstraint> p_constraints) {
 	if (!tile_set.is_valid()) {
-		return Map<Vector2i, TileSet::TerrainsPattern>();
+		return HashMap<Vector2i, TileSet::TerrainsPattern>();
 	}
 
 	// Copy the constraints set.
-	Set<TerrainConstraint> constraints = p_constraints;
+	RBSet<TerrainConstraint> constraints = p_constraints;
 
 	// Compute all acceptable patterns for each cell.
-	Map<Vector2i, Set<TileSet::TerrainsPattern>> per_cell_acceptable_tiles;
+	HashMap<Vector2i, RBSet<TileSet::TerrainsPattern>> per_cell_acceptable_tiles;
 	for (Vector2i cell : p_to_replace) {
 		per_cell_acceptable_tiles[cell] = _get_valid_terrains_patterns_for_constraints(p_terrain_set, cell, constraints);
 	}
 
 	// Output map.
-	Map<Vector2i, TileSet::TerrainsPattern> output;
+	HashMap<Vector2i, TileSet::TerrainsPattern> output;
 
 	// Add all positions to a set.
-	Set<Vector2i> to_replace = Set<Vector2i>(p_to_replace);
+	RBSet<Vector2i> to_replace = RBSet<Vector2i>(p_to_replace);
 	while (!to_replace.is_empty()) {
 		// Compute the minimum number of tile possibilities for each cell.
 		int min_nb_possibilities = 100000000;
-		for (const KeyValue<Vector2i, Set<TileSet::TerrainsPattern>> &E : per_cell_acceptable_tiles) {
+		for (const KeyValue<Vector2i, RBSet<TileSet::TerrainsPattern>> &E : per_cell_acceptable_tiles) {
 			min_nb_possibilities = MIN(min_nb_possibilities, E.value.size());
 		}
 
 		// Get the set of possible cells to fill, out of the most constrained ones.
 		LocalVector<Vector2i> to_choose_from;
-		for (const KeyValue<Vector2i, Set<TileSet::TerrainsPattern>> &E : per_cell_acceptable_tiles) {
+		for (const KeyValue<Vector2i, RBSet<TileSet::TerrainsPattern>> &E : per_cell_acceptable_tiles) {
 			if (E.value.size() == min_nb_possibilities) {
 				to_choose_from.push_back(E.key);
 			}
@@ -2306,7 +2308,7 @@ Map<Vector2i, TileSet::TerrainsPattern> TileMap::terrain_wave_function_collapse(
 		Vector2i selected_cell_to_replace = to_choose_from[Math::random(0, to_choose_from.size() - 1)];
 
 		// Get the list of acceptable patterns for the given cell.
-		Set<TileSet::TerrainsPattern> valid_tiles = per_cell_acceptable_tiles[selected_cell_to_replace];
+		RBSet<TileSet::TerrainsPattern> valid_tiles = per_cell_acceptable_tiles[selected_cell_to_replace];
 		if (valid_tiles.is_empty()) {
 			break; // No possibilities :/
 		}
@@ -2317,7 +2319,7 @@ Map<Vector2i, TileSet::TerrainsPattern> TileMap::terrain_wave_function_collapse(
 		LocalVector<int> terrains_counts;
 		int pattern_index = 0;
 		for (const TileSet::TerrainsPattern &pattern : valid_tiles) {
-			Set<int> terrains;
+			RBSet<int> terrains;
 			for (int i = 0; i < TileSet::CELL_NEIGHBOR_MAX; i++) {
 				TileSet::CellNeighbor side = TileSet::CellNeighbor(i);
 				if (tile_set->is_valid_peering_bit_terrain(p_terrain_set, side)) {
@@ -2345,8 +2347,8 @@ Map<Vector2i, TileSet::TerrainsPattern> TileMap::terrain_wave_function_collapse(
 		per_cell_acceptable_tiles.erase(selected_cell_to_replace);
 
 		// Add the new constraints from the added tiles.
-		Set<TerrainConstraint> new_constraints = get_terrain_constraints_from_added_tile(selected_cell_to_replace, p_terrain_set, selected_terrain_tile_pattern);
-		for (Set<TerrainConstraint>::Element *E_constraint = new_constraints.front(); E_constraint; E_constraint = E_constraint->next()) {
+		RBSet<TerrainConstraint> new_constraints = get_terrain_constraints_from_added_tile(selected_cell_to_replace, p_terrain_set, selected_terrain_tile_pattern);
+		for (RBSet<TerrainConstraint>::Element *E_constraint = new_constraints.front(); E_constraint; E_constraint = E_constraint->next()) {
 			constraints.insert(E_constraint->get());
 		}
 
@@ -2369,14 +2371,14 @@ void TileMap::set_cells_from_surrounding_terrains(int p_layer, TypedArray<Vector
 	ERR_FAIL_INDEX(p_layer, (int)layers.size());
 	ERR_FAIL_INDEX(p_terrain_set, tile_set->get_terrain_sets_count());
 
-	Set<Vector2i> coords_set;
+	RBSet<Vector2i> coords_set;
 	for (int i = 0; i < p_coords_array.size(); i++) {
 		coords_set.insert(p_coords_array[i]);
 	}
 
-	Set<TileMap::TerrainConstraint> constraints = get_terrain_constraints_from_removed_cells_list(p_layer, coords_set, p_terrain_set, p_ignore_empty_terrains);
+	RBSet<TileMap::TerrainConstraint> constraints = get_terrain_constraints_from_removed_cells_list(p_layer, coords_set, p_terrain_set, p_ignore_empty_terrains);
 
-	Map<Vector2i, TileSet::TerrainsPattern> wfc_output = terrain_wave_function_collapse(coords_set, p_terrain_set, constraints);
+	HashMap<Vector2i, TileSet::TerrainsPattern> wfc_output = terrain_wave_function_collapse(coords_set, p_terrain_set, constraints);
 	for (const KeyValue<Vector2i, TileSet::TerrainsPattern> &kv : wfc_output) {
 		TileMapCell cell = tile_set->get_random_tile_from_terrains_pattern(p_terrain_set, kv.value);
 		set_cell(p_layer, kv.key, cell.source_id, cell.get_atlas_coords(), cell.alternative_tile);
@@ -2385,11 +2387,11 @@ void TileMap::set_cells_from_surrounding_terrains(int p_layer, TypedArray<Vector
 
 TileMapCell TileMap::get_cell(int p_layer, const Vector2i &p_coords, bool p_use_proxies) const {
 	ERR_FAIL_INDEX_V(p_layer, (int)layers.size(), TileMapCell());
-	const Map<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
+	const HashMap<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
 	if (!tile_map.has(p_coords)) {
 		return TileMapCell();
 	} else {
-		TileMapCell c = tile_map.find(p_coords)->get();
+		TileMapCell c = tile_map.find(p_coords)->value;
 		if (p_use_proxies && tile_set.is_valid()) {
 			Array proxyed = tile_set->map_tile_proxy(c.source_id, c.get_atlas_coords(), c.alternative_tile);
 			c.source_id = proxyed[0];
@@ -2400,7 +2402,7 @@ TileMapCell TileMap::get_cell(int p_layer, const Vector2i &p_coords, bool p_use_
 	}
 }
 
-Map<Vector2i, TileMapQuadrant> *TileMap::get_quadrant_map(int p_layer) {
+HashMap<Vector2i, TileMapQuadrant> *TileMap::get_quadrant_map(int p_layer) {
 	ERR_FAIL_INDEX_V(p_layer, (int)layers.size(), nullptr);
 
 	return &layers[p_layer].quadrant_map;
@@ -2415,15 +2417,15 @@ void TileMap::fix_invalid_tiles() {
 	ERR_FAIL_COND_MSG(tile_set.is_null(), "Cannot fix invalid tiles if Tileset is not open.");
 
 	for (unsigned int i = 0; i < layers.size(); i++) {
-		const Map<Vector2i, TileMapCell> &tile_map = layers[i].tile_map;
-		Set<Vector2i> coords;
+		const HashMap<Vector2i, TileMapCell> &tile_map = layers[i].tile_map;
+		RBSet<Vector2i> coords;
 		for (const KeyValue<Vector2i, TileMapCell> &E : tile_map) {
 			TileSetSource *source = *tile_set->get_source(E.value.source_id);
 			if (!source || !source->has_tile(E.value.get_atlas_coords()) || !source->has_alternative_tile(E.value.get_atlas_coords(), E.value.alternative_tile)) {
 				coords.insert(E.key);
 			}
 		}
-		for (Set<Vector2i>::Element *E = coords.front(); E; E = E->next()) {
+		for (RBSet<Vector2i>::Element *E = coords.front(); E; E = E->next()) {
 			set_cell(i, E->get(), TileSet::INVALID_SOURCE, TileSetSource::INVALID_ATLAS_COORDS, TileSetSource::INVALID_TILE_ALTERNATIVE);
 		}
 	}
@@ -2546,7 +2548,7 @@ Vector<int> TileMap::_get_tile_data(int p_layer) const {
 	ERR_FAIL_INDEX_V(p_layer, (int)layers.size(), Vector<int>());
 
 	// Export tile data to raw format
-	const Map<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
+	const HashMap<Vector2i, TileMapCell> &tile_map = layers[p_layer].tile_map;
 	Vector<int> data;
 	data.resize(tile_map.size() * 3);
 	int *w = data.ptrw();
@@ -3375,10 +3377,10 @@ Rect2 TileMap::get_used_rect() { // Not const because of cache
 		used_rect_cache = Rect2i();
 
 		for (unsigned int i = 0; i < layers.size(); i++) {
-			const Map<Vector2i, TileMapCell> &tile_map = layers[i].tile_map;
+			const HashMap<Vector2i, TileMapCell> &tile_map = layers[i].tile_map;
 			if (tile_map.size() > 0) {
 				if (first) {
-					used_rect_cache = Rect2i(tile_map.front()->key().x, tile_map.front()->key().y, 0, 0);
+					used_rect_cache = Rect2i(tile_map.begin()->key.x, tile_map.begin()->key.y, 0, 0);
 					first = false;
 				}
 
@@ -3448,8 +3450,8 @@ void TileMap::set_texture_filter(TextureFilter p_texture_filter) {
 	// Set a default texture filter for the whole tilemap
 	CanvasItem::set_texture_filter(p_texture_filter);
 	for (unsigned int layer = 0; layer < layers.size(); layer++) {
-		for (Map<Vector2i, TileMapQuadrant>::Element *F = layers[layer].quadrant_map.front(); F; F = F->next()) {
-			TileMapQuadrant &q = F->get();
+		for (HashMap<Vector2i, TileMapQuadrant>::Iterator F = layers[layer].quadrant_map.begin(); F; ++F) {
+			TileMapQuadrant &q = F->value;
 			for (const RID &ci : q.canvas_items) {
 				RenderingServer::get_singleton()->canvas_item_set_default_texture_filter(ci, RS::CanvasItemTextureFilter(p_texture_filter));
 				_make_quadrant_dirty(F);
@@ -3463,8 +3465,8 @@ void TileMap::set_texture_repeat(CanvasItem::TextureRepeat p_texture_repeat) {
 	// Set a default texture repeat for the whole tilemap
 	CanvasItem::set_texture_repeat(p_texture_repeat);
 	for (unsigned int layer = 0; layer < layers.size(); layer++) {
-		for (Map<Vector2i, TileMapQuadrant>::Element *F = layers[layer].quadrant_map.front(); F; F = F->next()) {
-			TileMapQuadrant &q = F->get();
+		for (HashMap<Vector2i, TileMapQuadrant>::Iterator F = layers[layer].quadrant_map.begin(); F; ++F) {
+			TileMapQuadrant &q = F->value;
 			for (const RID &ci : q.canvas_items) {
 				RenderingServer::get_singleton()->canvas_item_set_default_texture_repeat(ci, RS::CanvasItemTextureRepeat(p_texture_repeat));
 				_make_quadrant_dirty(F);
@@ -3512,7 +3514,7 @@ TypedArray<Vector2i> TileMap::get_surrounding_tiles(Vector2i coords) {
 	return around;
 }
 
-void TileMap::draw_cells_outline(Control *p_control, Set<Vector2i> p_cells, Color p_color, Transform2D p_transform) {
+void TileMap::draw_cells_outline(Control *p_control, RBSet<Vector2i> p_cells, Color p_color, Transform2D p_transform) {
 	if (!tile_set.is_valid()) {
 		return;
 	}
@@ -3522,7 +3524,7 @@ void TileMap::draw_cells_outline(Control *p_control, Set<Vector2i> p_cells, Colo
 	Vector<Vector2> polygon = tile_set->get_tile_shape_polygon();
 	TileSet::TileShape shape = tile_set->get_tile_shape();
 
-	for (Set<Vector2i>::Element *E = p_cells.front(); E; E = E->next()) {
+	for (RBSet<Vector2i>::Element *E = p_cells.front(); E; E = E->next()) {
 		Vector2 center = map_to_world(E->get());
 
 #define DRAW_SIDE_IF_NEEDED(side, polygon_index_from, polygon_index_to)                     \
@@ -3576,7 +3578,7 @@ TypedArray<String> TileMap::get_configuration_warnings() const {
 	TypedArray<String> warnings = Node::get_configuration_warnings();
 
 	// Retrieve the set of Z index values with a Y-sorted layer.
-	Set<int> y_sorted_z_index;
+	RBSet<int> y_sorted_z_index;
 	for (int layer = 0; layer < (int)layers.size(); layer++) {
 		if (layers[layer].y_sort_enabled) {
 			y_sorted_z_index.insert(layers[layer].z_index);
diff --git a/scene/2d/tile_map.h b/scene/2d/tile_map.h
index a0655dea2a..02a2b3a1c6 100644
--- a/scene/2d/tile_map.h
+++ b/scene/2d/tile_map.h
@@ -57,11 +57,11 @@ struct TileMapQuadrant {
 	Vector2i coords;
 
 	// TileMapCells
-	Set<Vector2i> cells;
+	RBSet<Vector2i> cells;
 	// We need those two maps to sort by world position for rendering
 	// This is kind of workaround, it would be better to sort the cells directly in the "cells" set instead.
-	Map<Vector2i, Vector2i> map_to_world;
-	Map<Vector2i, Vector2i, CoordsWorldComparator> world_to_map;
+	RBMap<Vector2i, Vector2i> map_to_world;
+	RBMap<Vector2i, Vector2i, CoordsWorldComparator> world_to_map;
 
 	// Debug.
 	RID debug_canvas_item;
@@ -74,13 +74,13 @@ struct TileMapQuadrant {
 	List<RID> bodies;
 
 	// Navigation.
-	Map<Vector2i, Vector<RID>> navigation_regions;
+	HashMap<Vector2i, Vector<RID>> navigation_regions;
 
 	// Scenes.
-	Map<Vector2i, String> scenes;
+	HashMap<Vector2i, String> scenes;
 
 	// Runtime TileData cache.
-	Map<Vector2i, TileData *> runtime_tile_data_cache;
+	HashMap<Vector2i, TileData *> runtime_tile_data_cache;
 
 	void operator=(const TileMapQuadrant &q) {
 		layer = q.layer;
@@ -135,7 +135,7 @@ public:
 			return base_cell_coords;
 		}
 
-		Map<Vector2i, TileSet::CellNeighbor> get_overlapping_coords_and_peering_bits() const;
+		HashMap<Vector2i, TileSet::CellNeighbor> get_overlapping_coords_and_peering_bits() const;
 
 		void set_terrain(int p_terrain) {
 			terrain = p_terrain;
@@ -193,22 +193,22 @@ private:
 		int y_sort_origin = 0;
 		int z_index = 0;
 		RID canvas_item;
-		Map<Vector2i, TileMapCell> tile_map;
-		Map<Vector2i, TileMapQuadrant> quadrant_map;
+		HashMap<Vector2i, TileMapCell> tile_map;
+		HashMap<Vector2i, TileMapQuadrant> quadrant_map;
 		SelfList<TileMapQuadrant>::List dirty_quadrant_list;
 	};
 	LocalVector<TileMapLayer> layers;
 	int selected_layer = -1;
 
 	// Mapping for RID to coords.
-	Map<RID, Vector2i> bodies_coords;
+	HashMap<RID, Vector2i> bodies_coords;
 
 	// Quadrants and internals management.
 	Vector2i _coords_to_quadrant_coords(int p_layer, const Vector2i &p_coords) const;
 
-	Map<Vector2i, TileMapQuadrant>::Element *_create_quadrant(int p_layer, const Vector2i &p_qk);
+	HashMap<Vector2i, TileMapQuadrant>::Iterator _create_quadrant(int p_layer, const Vector2i &p_qk);
 
-	void _make_quadrant_dirty(Map<Vector2i, TileMapQuadrant>::Element *Q);
+	void _make_quadrant_dirty(HashMap<Vector2i, TileMapQuadrant>::Iterator Q);
 	void _make_all_quadrants_dirty();
 	void _queue_update_dirty_quadrants();
 
@@ -217,7 +217,7 @@ private:
 	void _recreate_layer_internals(int p_layer);
 	void _recreate_internals();
 
-	void _erase_quadrant(Map<Vector2i, TileMapQuadrant>::Element *Q);
+	void _erase_quadrant(HashMap<Vector2i, TileMapQuadrant>::Iterator Q);
 	void _clear_layer_internals(int p_layer);
 	void _clear_internals();
 
@@ -251,7 +251,7 @@ private:
 	void _scenes_draw_quadrant_debug(TileMapQuadrant *p_quadrant);
 
 	// Terrains.
-	Set<TileSet::TerrainsPattern> _get_valid_terrains_patterns_for_constraints(int p_terrain_set, const Vector2i &p_position, Set<TerrainConstraint> p_constraints);
+	RBSet<TileSet::TerrainsPattern> _get_valid_terrains_patterns_for_constraints(int p_terrain_set, const Vector2i &p_position, RBSet<TerrainConstraint> p_constraints);
 
 	// Set and get tiles from data arrays.
 	void _set_tile_data(int p_layer, const Vector<int> &p_data);
@@ -333,14 +333,14 @@ public:
 	void set_pattern(int p_layer, Vector2i p_position, const Ref<TileMapPattern> p_pattern);
 
 	// Terrains.
-	Set<TerrainConstraint> get_terrain_constraints_from_removed_cells_list(int p_layer, const Set<Vector2i> &p_to_replace, int p_terrain_set, bool p_ignore_empty_terrains = true) const; // Not exposed.
-	Set<TerrainConstraint> get_terrain_constraints_from_added_tile(Vector2i p_position, int p_terrain_set, TileSet::TerrainsPattern p_terrains_pattern) const; // Not exposed.
-	Map<Vector2i, TileSet::TerrainsPattern> terrain_wave_function_collapse(const Set<Vector2i> &p_to_replace, int p_terrain_set, const Set<TerrainConstraint> p_constraints); // Not exposed.
+	RBSet<TerrainConstraint> get_terrain_constraints_from_removed_cells_list(int p_layer, const RBSet<Vector2i> &p_to_replace, int p_terrain_set, bool p_ignore_empty_terrains = true) const; // Not exposed.
+	RBSet<TerrainConstraint> get_terrain_constraints_from_added_tile(Vector2i p_position, int p_terrain_set, TileSet::TerrainsPattern p_terrains_pattern) const; // Not exposed.
+	HashMap<Vector2i, TileSet::TerrainsPattern> terrain_wave_function_collapse(const RBSet<Vector2i> &p_to_replace, int p_terrain_set, const RBSet<TerrainConstraint> p_constraints); // Not exposed.
 	void set_cells_from_surrounding_terrains(int p_layer, TypedArray<Vector2i> p_coords_array, int p_terrain_set, bool p_ignore_empty_terrains = true);
 
 	// Not exposed to users
 	TileMapCell get_cell(int p_layer, const Vector2i &p_coords, bool p_use_proxies = false) const;
-	Map<Vector2i, TileMapQuadrant> *get_quadrant_map(int p_layer);
+	HashMap<Vector2i, TileMapQuadrant> *get_quadrant_map(int p_layer);
 	int get_effective_quadrant_size(int p_layer) const;
 	//---
 
@@ -377,7 +377,7 @@ public:
 
 	// Helpers?
 	TypedArray<Vector2i> get_surrounding_tiles(Vector2i coords);
-	void draw_cells_outline(Control *p_control, Set<Vector2i> p_cells, Color p_color, Transform2D p_transform = Transform2D());
+	void draw_cells_outline(Control *p_control, RBSet<Vector2i> p_cells, Color p_color, Transform2D p_transform = Transform2D());
 
 	// Virtual function to modify the TileData at runtime
 	GDVIRTUAL2R(bool, _use_tile_data_runtime_update, int, Vector2i);
diff --git a/scene/2d/visible_on_screen_notifier_2d.h b/scene/2d/visible_on_screen_notifier_2d.h
index e0d580f174..3165eb92df 100644
--- a/scene/2d/visible_on_screen_notifier_2d.h
+++ b/scene/2d/visible_on_screen_notifier_2d.h
@@ -37,7 +37,7 @@ class Viewport;
 class VisibleOnScreenNotifier2D : public Node2D {
 	GDCLASS(VisibleOnScreenNotifier2D, Node2D);
 
-	Set<Viewport *> viewports;
+	RBSet<Viewport *> viewports;
 
 	Rect2 rect;
author	reduz <reduzio@gmail.com>	2022-05-13 15:04:37 +0200
committer	Rémi Verschelde <rverschelde@gmail.com>	2022-05-16 10:37:48 +0200
commit	746dddc0673d7261f19b1e056e90e6e3a49ef33a (patch)
tree	434b526eb286850ebccc6d2c998a7d90fdb8b5e2 /scene/2d
parent	396def9b66c476f7834604adb7136ca903ed01be (diff)
download	redot-engine-746dddc0673d7261f19b1e056e90e6e3a49ef33a.tar.gz