Add a new HashSet template

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

6 files changed, 40 insertions, 33 deletions

diff --git a/scene/gui/base_button.h b/scene/gui/base_button.h
index 0b70d285ee..ba3852ec98 100644
--- a/scene/gui/base_button.h
+++ b/scene/gui/base_button.h
@@ -143,7 +143,7 @@ VARIANT_ENUM_CAST(BaseButton::ActionMode)
 class ButtonGroup : public Resource {
 	GDCLASS(ButtonGroup, Resource);
 	friend class BaseButton;
-	RBSet<BaseButton *> buttons;
+	HashSet<BaseButton *> buttons;
 
 protected:
 	static void _bind_methods();
diff --git a/scene/gui/code_edit.h b/scene/gui/code_edit.h
index 0b00735f46..ccf046c612 100644
--- a/scene/gui/code_edit.h
+++ b/scene/gui/code_edit.h
@@ -58,7 +58,7 @@ private:
 	String indent_text = "\t";
 
 	bool auto_indent = false;
-	RBSet<char32_t> auto_indent_prefixes;
+	HashSet<char32_t> auto_indent_prefixes;
 
 	bool indent_using_spaces = false;
 	int _calculate_spaces_till_next_left_indent(int p_column) const;
@@ -214,7 +214,7 @@ private:
 	int code_completion_longest_line = 0;
 	Rect2i code_completion_rect;
 
-	RBSet<char32_t> code_completion_prefixes;
+	HashSet<char32_t> code_completion_prefixes;
 	List<ScriptLanguage::CodeCompletionOption> code_completion_option_submitted;
 	List<ScriptLanguage::CodeCompletionOption> code_completion_option_sources;
 	String code_completion_base;
diff --git a/scene/gui/graph_edit.cpp b/scene/gui/graph_edit.cpp
index ccf7e2828a..fdff6a88a9 100644
--- a/scene/gui/graph_edit.cpp
+++ b/scene/gui/graph_edit.cpp
@@ -1696,7 +1696,7 @@ void GraphEdit::set_warped_panning(bool p_warped) {
 	warped_panning = p_warped;
 }
 
-int GraphEdit::_set_operations(SET_OPERATIONS p_operation, RBSet<StringName> &r_u, const RBSet<StringName> &r_v) {
+int GraphEdit::_set_operations(SET_OPERATIONS p_operation, HashSet<StringName> &r_u, const HashSet<StringName> &r_v) {
 	switch (p_operation) {
 		case GraphEdit::IS_EQUAL: {
 			for (const StringName &E : r_u) {
@@ -1718,10 +1718,13 @@ int GraphEdit::_set_operations(SET_OPERATIONS p_operation, RBSet<StringName> &r_
 			return 1;
 		} break;
 		case GraphEdit::DIFFERENCE: {
-			for (RBSet<StringName>::Element *E = r_u.front(); E; E = E->next()) {
-				if (r_v.has(E->get())) {
-					r_u.erase(E->get());
+			for (HashSet<StringName>::Iterator E = r_u.begin(); E;) {
+				HashSet<StringName>::Iterator N = E;
+				++N;
+				if (r_v.has(*E)) {
+					r_u.remove(E);
 				}
+				E = N;
 			}
 			return r_u.size();
 		} break;
@@ -1739,17 +1742,17 @@ int GraphEdit::_set_operations(SET_OPERATIONS p_operation, RBSet<StringName> &r_
 	return -1;
 }
 
-HashMap<int, Vector<StringName>> GraphEdit::_layering(const RBSet<StringName> &r_selected_nodes, const HashMap<StringName, RBSet<StringName>> &r_upper_neighbours) {
+HashMap<int, Vector<StringName>> GraphEdit::_layering(const HashSet<StringName> &r_selected_nodes, const HashMap<StringName, HashSet<StringName>> &r_upper_neighbours) {
 	HashMap<int, Vector<StringName>> l;
 
-	RBSet<StringName> p = r_selected_nodes, q = r_selected_nodes, u, z;
+	HashSet<StringName> p = r_selected_nodes, q = r_selected_nodes, u, z;
 	int current_layer = 0;
 	bool selected = false;
 
 	while (!_set_operations(GraphEdit::IS_EQUAL, q, u)) {
 		_set_operations(GraphEdit::DIFFERENCE, p, u);
 		for (const StringName &E : p) {
-			RBSet<StringName> n = r_upper_neighbours[E];
+			HashSet<StringName> n = r_upper_neighbours[E];
 			if (_set_operations(GraphEdit::IS_SUBSET, n, z)) {
 				Vector<StringName> t;
 				t.push_back(E);
@@ -1759,7 +1762,7 @@ HashMap<int, Vector<StringName>> GraphEdit::_layering(const RBSet<StringName> &r
 				selected = true;
 				t.append_array(l[current_layer]);
 				l.insert(current_layer, t);
-				RBSet<StringName> V;
+				HashSet<StringName> V;
 				V.insert(E);
 				_set_operations(GraphEdit::UNION, u, V);
 			}
@@ -1801,7 +1804,7 @@ Vector<StringName> GraphEdit::_split(const Vector<StringName> &r_layer, const Ha
 	return left;
 }
 
-void GraphEdit::_horizontal_alignment(Dictionary &r_root, Dictionary &r_align, const HashMap<int, Vector<StringName>> &r_layers, const HashMap<StringName, RBSet<StringName>> &r_upper_neighbours, const RBSet<StringName> &r_selected_nodes) {
+void GraphEdit::_horizontal_alignment(Dictionary &r_root, Dictionary &r_align, const HashMap<int, Vector<StringName>> &r_layers, const HashMap<StringName, HashSet<StringName>> &r_upper_neighbours, const HashSet<StringName> &r_selected_nodes) {
 	for (const StringName &E : r_selected_nodes) {
 		r_root[E] = E;
 		r_align[E] = E;
@@ -1841,7 +1844,7 @@ void GraphEdit::_horizontal_alignment(Dictionary &r_root, Dictionary &r_align, c
 	}
 }
 
-void GraphEdit::_crossing_minimisation(HashMap<int, Vector<StringName>> &r_layers, const HashMap<StringName, RBSet<StringName>> &r_upper_neighbours) {
+void GraphEdit::_crossing_minimisation(HashMap<int, Vector<StringName>> &r_layers, const HashMap<StringName, HashSet<StringName>> &r_upper_neighbours) {
 	if (r_layers.size() == 1) {
 		return;
 	}
@@ -1879,7 +1882,7 @@ void GraphEdit::_crossing_minimisation(HashMap<int, Vector<StringName>> &r_layer
 	}
 }
 
-void GraphEdit::_calculate_inner_shifts(Dictionary &r_inner_shifts, const Dictionary &r_root, const Dictionary &r_node_names, const Dictionary &r_align, const RBSet<StringName> &r_block_heads, const HashMap<StringName, Pair<int, int>> &r_port_info) {
+void GraphEdit::_calculate_inner_shifts(Dictionary &r_inner_shifts, const Dictionary &r_root, const Dictionary &r_node_names, const Dictionary &r_align, const HashSet<StringName> &r_block_heads, const HashMap<StringName, Pair<int, int>> &r_port_info) {
 	for (const StringName &E : r_block_heads) {
 		real_t left = 0;
 		StringName u = E;
@@ -2052,7 +2055,7 @@ void GraphEdit::arrange_nodes() {
 	}
 
 	Dictionary node_names;
-	RBSet<StringName> selected_nodes;
+	HashSet<StringName> selected_nodes;
 
 	for (int i = get_child_count() - 1; i >= 0; i--) {
 		GraphNode *gn = Object::cast_to<GraphNode>(get_child(i));
@@ -2063,7 +2066,7 @@ void GraphEdit::arrange_nodes() {
 		node_names[gn->get_name()] = gn;
 	}
 
-	HashMap<StringName, RBSet<StringName>> upper_neighbours;
+	HashMap<StringName, HashSet<StringName>> upper_neighbours;
 	HashMap<StringName, Pair<int, int>> port_info;
 	Vector2 origin(FLT_MAX, FLT_MAX);
 
@@ -2078,7 +2081,7 @@ void GraphEdit::arrange_nodes() {
 
 		if (gn->is_selected()) {
 			selected_nodes.insert(gn->get_name());
-			RBSet<StringName> s;
+			HashSet<StringName> s;
 			for (List<Connection>::Element *E = connections.front(); E; E = E->next()) {
 				GraphNode *p_from = Object::cast_to<GraphNode>(node_names[E->get().from]);
 				if (E->get().to == gn->get_name() && p_from->is_selected()) {
@@ -2115,7 +2118,7 @@ void GraphEdit::arrange_nodes() {
 	HashMap<StringName, Vector2> new_positions;
 	Vector2 default_position(FLT_MAX, FLT_MAX);
 	Dictionary inner_shift;
-	RBSet<StringName> block_heads;
+	HashSet<StringName> block_heads;
 
 	for (const StringName &E : selected_nodes) {
 		inner_shift[E] = 0.0f;
diff --git a/scene/gui/graph_edit.h b/scene/gui/graph_edit.h
index 9e34d5528f..5484a2317c 100644
--- a/scene/gui/graph_edit.h
+++ b/scene/gui/graph_edit.h
@@ -218,8 +218,11 @@ private:
 			uint64_t key = 0;
 		};
 
-		bool operator<(const ConnType &p_type) const {
-			return key < p_type.key;
+		static uint32_t hash(const ConnType &p_conn) {
+			return hash_one_uint64(p_conn.key);
+		}
+		bool operator==(const ConnType &p_type) const {
+			return key == p_type.key;
 		}
 
 		ConnType(uint32_t a = 0, uint32_t b = 0) {
@@ -228,9 +231,9 @@ private:
 		}
 	};
 
-	RBSet<ConnType> valid_connection_types;
-	RBSet<int> valid_left_disconnect_types;
-	RBSet<int> valid_right_disconnect_types;
+	HashSet<ConnType, ConnType> valid_connection_types;
+	HashSet<int> valid_left_disconnect_types;
+	HashSet<int> valid_right_disconnect_types;
 
 	HashMap<StringName, Vector<GraphNode *>> comment_enclosed_nodes;
 	void _update_comment_enclosed_nodes_list(GraphNode *p_node, HashMap<StringName, Vector<GraphNode *>> &p_comment_enclosed_nodes);
@@ -258,12 +261,12 @@ private:
 		UNION,
 	};
 
-	int _set_operations(SET_OPERATIONS p_operation, RBSet<StringName> &r_u, const RBSet<StringName> &r_v);
-	HashMap<int, Vector<StringName>> _layering(const RBSet<StringName> &r_selected_nodes, const HashMap<StringName, RBSet<StringName>> &r_upper_neighbours);
+	int _set_operations(SET_OPERATIONS p_operation, HashSet<StringName> &r_u, const HashSet<StringName> &r_v);
+	HashMap<int, Vector<StringName>> _layering(const HashSet<StringName> &r_selected_nodes, const HashMap<StringName, HashSet<StringName>> &r_upper_neighbours);
 	Vector<StringName> _split(const Vector<StringName> &r_layer, const HashMap<StringName, Dictionary> &r_crossings);
-	void _horizontal_alignment(Dictionary &r_root, Dictionary &r_align, const HashMap<int, Vector<StringName>> &r_layers, const HashMap<StringName, RBSet<StringName>> &r_upper_neighbours, const RBSet<StringName> &r_selected_nodes);
-	void _crossing_minimisation(HashMap<int, Vector<StringName>> &r_layers, const HashMap<StringName, RBSet<StringName>> &r_upper_neighbours);
-	void _calculate_inner_shifts(Dictionary &r_inner_shifts, const Dictionary &r_root, const Dictionary &r_node_names, const Dictionary &r_align, const RBSet<StringName> &r_block_heads, const HashMap<StringName, Pair<int, int>> &r_port_info);
+	void _horizontal_alignment(Dictionary &r_root, Dictionary &r_align, const HashMap<int, Vector<StringName>> &r_layers, const HashMap<StringName, HashSet<StringName>> &r_upper_neighbours, const HashSet<StringName> &r_selected_nodes);
+	void _crossing_minimisation(HashMap<int, Vector<StringName>> &r_layers, const HashMap<StringName, HashSet<StringName>> &r_upper_neighbours);
+	void _calculate_inner_shifts(Dictionary &r_inner_shifts, const Dictionary &r_root, const Dictionary &r_node_names, const Dictionary &r_align, const HashSet<StringName> &r_block_heads, const HashMap<StringName, Pair<int, int>> &r_port_info);
 	float _calculate_threshold(StringName p_v, StringName p_w, const Dictionary &r_node_names, const HashMap<int, Vector<StringName>> &r_layers, const Dictionary &r_root, const Dictionary &r_align, const Dictionary &r_inner_shift, real_t p_current_threshold, const HashMap<StringName, Vector2> &r_node_positions);
 	void _place_block(StringName p_v, float p_delta, const HashMap<int, Vector<StringName>> &r_layers, const Dictionary &r_root, const Dictionary &r_align, const Dictionary &r_node_name, const Dictionary &r_inner_shift, Dictionary &r_sink, Dictionary &r_shift, HashMap<StringName, Vector2> &r_node_positions);
 
diff --git a/scene/gui/grid_container.cpp b/scene/gui/grid_container.cpp
index 5d9484806b..6f8518a7b0 100644
--- a/scene/gui/grid_container.cpp
+++ b/scene/gui/grid_container.cpp
@@ -29,12 +29,13 @@
 /*************************************************************************/
 
 #include "grid_container.h"
+#include "core/templates/rb_set.h"
 
 void GridContainer::_notification(int p_what) {
 	switch (p_what) {
 		case NOTIFICATION_SORT_CHILDREN: {
-			HashMap<int, int> col_minw; // Max of min_width of all controls in each col (indexed by col).
-			HashMap<int, int> row_minh; // Max of min_height of all controls in each row (indexed by row).
+			RBMap<int, int> col_minw; // Max of min_width of all controls in each col (indexed by col).
+			RBMap<int, int> row_minh; // Max of min_height of all controls in each row (indexed by row).
 			RBSet<int> col_expanded; // Columns which have the SIZE_EXPAND flag set.
 			RBSet<int> row_expanded; // Rows which have the SIZE_EXPAND flag set.
 
@@ -261,8 +262,8 @@ void GridContainer::_bind_methods() {
 }
 
 Size2 GridContainer::get_minimum_size() const {
-	HashMap<int, int> col_minw;
-	HashMap<int, int> row_minh;
+	RBMap<int, int> col_minw;
+	RBMap<int, int> row_minh;
 
 	int hsep = get_theme_constant(SNAME("h_separation"));
 	int vsep = get_theme_constant(SNAME("v_separation"));
diff --git a/scene/gui/range.h b/scene/gui/range.h
index a59bfa9677..1274821bd1 100644
--- a/scene/gui/range.h
+++ b/scene/gui/range.h
@@ -45,7 +45,7 @@ class Range : public Control {
 		bool exp_ratio = false;
 		bool allow_greater = false;
 		bool allow_lesser = false;
-		RBSet<Range *> owners;
+		HashSet<Range *> owners;
 		void emit_value_changed();
 		void emit_changed(const char *p_what = "");
 	};