Add a new HashSet template

* Intended to replace RBSet in most cases.
* Optimized for iteration speed

5 files changed, 20 insertions, 17 deletions

diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp
index 29aa959e54..efa970c681 100644
--- a/core/math/a_star.cpp
+++ b/core/math/a_star.cpp
@@ -151,15 +151,15 @@ void AStar3D::connect_points(int p_id, int p_with_id, bool bidirectional) {
 		s.direction = Segment::BIDIRECTIONAL;
 	}
 
-	RBSet<Segment>::Element *element = segments.find(s);
-	if (element != nullptr) {
-		s.direction |= element->get().direction;
+	HashSet<Segment, Segment>::Iterator element = segments.find(s);
+	if (element) {
+		s.direction |= element->direction;
 		if (s.direction == Segment::BIDIRECTIONAL) {
 			// Both are neighbours of each other now
 			a->unlinked_neighbours.remove(b->id);
 			b->unlinked_neighbours.remove(a->id);
 		}
-		segments.erase(element);
+		segments.remove(element);
 	}
 
 	segments.insert(s);
@@ -177,16 +177,16 @@ void AStar3D::disconnect_points(int p_id, int p_with_id, bool bidirectional) {
 	Segment s(p_id, p_with_id);
 	int remove_direction = bidirectional ? (int)Segment::BIDIRECTIONAL : s.direction;
 
-	RBSet<Segment>::Element *element = segments.find(s);
-	if (element != nullptr) {
+	HashSet<Segment, Segment>::Iterator element = segments.find(s);
+	if (element) {
 		// s is the new segment
 		// Erase the directions to be removed
-		s.direction = (element->get().direction & ~remove_direction);
+		s.direction = (element->direction & ~remove_direction);
 
 		a->neighbours.remove(b->id);
 		if (bidirectional) {
 			b->neighbours.remove(a->id);
-			if (element->get().direction != Segment::BIDIRECTIONAL) {
+			if (element->direction != Segment::BIDIRECTIONAL) {
 				a->unlinked_neighbours.remove(b->id);
 				b->unlinked_neighbours.remove(a->id);
 			}
@@ -198,7 +198,7 @@ void AStar3D::disconnect_points(int p_id, int p_with_id, bool bidirectional) {
 			}
 		}
 
-		segments.erase(element);
+		segments.remove(element);
 		if (s.direction != Segment::NONE) {
 			segments.insert(s);
 		}
@@ -235,10 +235,10 @@ Vector<int> AStar3D::get_point_connections(int p_id) {
 
 bool AStar3D::are_points_connected(int p_id, int p_with_id, bool bidirectional) const {
 	Segment s(p_id, p_with_id);
-	const RBSet<Segment>::Element *element = segments.find(s);
+	const HashSet<Segment, Segment>::Iterator element = segments.find(s);
 
-	return element != nullptr &&
-			(bidirectional || (element->get().direction & s.direction) == s.direction);
+	return element &&
+			(bidirectional || (element->direction & s.direction) == s.direction);
 }
 
 void AStar3D::clear() {
diff --git a/core/math/a_star.h b/core/math/a_star.h
index 086be839b5..e2f75ad18c 100644
--- a/core/math/a_star.h
+++ b/core/math/a_star.h
@@ -92,7 +92,10 @@ class AStar3D : public RefCounted {
 		};
 		unsigned char direction = NONE;
 
-		bool operator<(const Segment &p_s) const { return key < p_s.key; }
+		static uint32_t hash(const Segment &p_seg) {
+			return hash_one_uint64(p_seg.key);
+		}
+		bool operator==(const Segment &p_s) const { return key == p_s.key; }
 
 		Segment() {}
 		Segment(int p_from, int p_to) {
@@ -112,7 +115,7 @@ class AStar3D : public RefCounted {
 	uint64_t pass = 1;
 
 	OAHashMap<int, Point *> points;
-	RBSet<Segment> segments;
+	HashSet<Segment, Segment> segments;
 
 	bool _solve(Point *begin_point, Point *end_point);
 
diff --git a/core/math/quick_hull.cpp b/core/math/quick_hull.cpp
index 43744deeb0..c7727a44a1 100644
--- a/core/math/quick_hull.cpp
+++ b/core/math/quick_hull.cpp
@@ -52,7 +52,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_
 
 	Vector<bool> valid_points;
 	valid_points.resize(p_points.size());
-	RBSet<Vector3> valid_cache;
+	HashSet<Vector3> valid_cache;
 
 	for (int i = 0; i < p_points.size(); i++) {
 		Vector3 sp = p_points[i].snapped(Vector3(0.0001, 0.0001, 0.0001));
diff --git a/core/math/quick_hull.h b/core/math/quick_hull.h
index 1c354880b4..6783743fc2 100644
--- a/core/math/quick_hull.h
+++ b/core/math/quick_hull.h
@@ -33,8 +33,8 @@
 
 #include "core/math/aabb.h"
 #include "core/math/geometry_3d.h"
+#include "core/templates/hash_set.h"
 #include "core/templates/list.h"
-#include "core/templates/rb_set.h"
 
 class QuickHull {
 public:
diff --git a/core/math/static_raycaster.h b/core/math/static_raycaster.h
index adc81906d7..bc6511c073 100644
--- a/core/math/static_raycaster.h
+++ b/core/math/static_raycaster.h
@@ -102,7 +102,7 @@ public:
 	virtual void add_mesh(const PackedVector3Array &p_vertices, const PackedInt32Array &p_indices, unsigned int p_id) = 0;
 	virtual void commit() = 0;
 
-	virtual void set_mesh_filter(const RBSet<int> &p_mesh_ids) = 0;
+	virtual void set_mesh_filter(const HashSet<int> &p_mesh_ids) = 0;
 	virtual void clear_mesh_filter() = 0;
 
 	static Ref<StaticRaycaster> create();