From 45af29da8095af16729955117a165d23e77cd740 Mon Sep 17 00:00:00 2001 From: reduz Date: Thu, 19 May 2022 17:00:06 +0200 Subject: Add a new HashSet template * Intended to replace RBSet in most cases. * Optimized for iteration speed --- core/config/project_settings.h | 2 +- core/debugger/local_debugger.cpp | 6 +- core/debugger/script_debugger.cpp | 2 +- core/debugger/script_debugger.h | 6 +- core/input/input.h | 1 + core/io/file_access_pack.h | 4 +- core/io/json.cpp | 4 +- core/io/json.h | 2 +- core/io/logger.cpp | 8 +- core/io/resource.h | 2 +- core/io/resource_format_binary.cpp | 2 +- core/io/resource_format_binary.h | 2 +- core/io/resource_importer.cpp | 4 +- core/io/resource_loader.h | 2 +- core/math/a_star.cpp | 24 +- core/math/a_star.h | 7 +- core/math/quick_hull.cpp | 2 +- core/math/quick_hull.h | 2 +- core/math/static_raycaster.h | 2 +- core/multiplayer/multiplayer_api.h | 4 +- core/object/class_db.cpp | 2 +- core/object/class_db.h | 5 +- core/object/object.h | 6 +- core/object/script_language.cpp | 2 +- core/object/script_language.h | 4 +- core/object/script_language_extension.h | 4 +- core/string/translation.h | 4 +- core/templates/hash_set.h | 473 +++++++++++++++++++++ core/templates/rb_set.h | 3 + core/templates/rid_owner.h | 2 +- doc/classes/CodeEdit.xml | 2 +- drivers/gles3/storage/config.h | 4 +- drivers/gles3/storage/material_storage.cpp | 2 +- drivers/gles3/storage/material_storage.h | 4 +- drivers/gles3/storage/mesh_storage.h | 2 +- drivers/vulkan/rendering_device_vulkan.cpp | 14 +- drivers/vulkan/rendering_device_vulkan.h | 8 +- editor/animation_bezier_editor.cpp | 20 +- editor/animation_bezier_editor.h | 5 +- editor/animation_track_editor.cpp | 2 +- editor/create_dialog.h | 2 +- editor/debugger/editor_debugger_inspector.cpp | 2 +- editor/debugger/editor_debugger_inspector.h | 2 +- editor/debugger/editor_debugger_node.h | 2 +- editor/debugger/editor_debugger_tree.h | 2 +- editor/debugger/editor_performance_profiler.cpp | 2 +- editor/debugger/editor_profiler.cpp | 2 +- editor/debugger/editor_profiler.h | 2 +- editor/doc_tools.cpp | 2 +- editor/editor_asset_installer.cpp | 2 +- editor/editor_data.cpp | 4 +- editor/editor_data.h | 2 +- editor/editor_dir_dialog.h | 2 +- editor/editor_export.cpp | 22 +- editor/editor_export.h | 22 +- editor/editor_feature_profile.cpp | 4 +- editor/editor_feature_profile.h | 8 +- editor/editor_file_system.cpp | 10 +- editor/editor_file_system.h | 16 +- editor/editor_folding.cpp | 12 +- editor/editor_folding.h | 6 +- editor/editor_help.cpp | 2 +- editor/editor_inspector.cpp | 8 +- editor/editor_inspector.h | 4 +- editor/editor_node.cpp | 8 +- editor/editor_node.h | 10 +- editor/editor_resource_picker.cpp | 25 +- editor/editor_resource_picker.h | 4 +- editor/editor_settings.h | 3 +- editor/editor_themes.cpp | 4 +- editor/editor_translation_parser.cpp | 4 +- editor/export_template_manager.cpp | 3 +- editor/fileserver/editor_file_server.cpp | 2 +- editor/fileserver/editor_file_server.h | 2 +- editor/filesystem_dock.cpp | 2 +- editor/filesystem_dock.h | 2 +- editor/find_in_files.cpp | 6 +- editor/find_in_files.h | 6 +- editor/import/collada.cpp | 10 +- editor/import/collada.h | 2 +- editor/import/dynamic_font_import_settings.h | 1 + editor/import/editor_import_collada.cpp | 12 +- editor/import/resource_importer_scene.cpp | 4 +- editor/import/resource_importer_scene.h | 2 +- editor/import/scene_import_settings.h | 4 +- editor/import_dock.cpp | 4 +- editor/inspector_dock.cpp | 2 +- .../plugins/animation_blend_tree_editor_plugin.cpp | 13 +- editor/plugins/animation_state_machine_editor.cpp | 8 +- editor/plugins/animation_state_machine_editor.h | 4 +- editor/plugins/editor_preview_plugins.cpp | 4 +- editor/plugins/gdextension_export_plugin.h | 4 +- editor/plugins/mesh_instance_3d_editor_plugin.cpp | 15 +- editor/plugins/node_3d_editor_gizmos.cpp | 2 +- editor/plugins/node_3d_editor_plugin.cpp | 43 +- .../packed_scene_translation_parser_plugin.h | 2 +- editor/plugins/root_motion_editor_plugin.cpp | 2 +- editor/plugins/script_editor_plugin.cpp | 8 +- editor/plugins/script_editor_plugin.h | 4 +- editor/plugins/script_text_editor.cpp | 6 +- editor/plugins/script_text_editor.h | 2 +- editor/plugins/sprite_frames_editor_plugin.h | 4 +- editor/plugins/visual_shader_editor_plugin.cpp | 16 +- editor/plugins/visual_shader_editor_plugin.h | 6 +- editor/pot_generator.cpp | 2 +- editor/pot_generator.h | 4 +- editor/project_export.cpp | 9 +- editor/project_manager.cpp | 22 +- editor/project_settings_editor.cpp | 2 +- editor/property_editor.cpp | 4 +- editor/reparent_dialog.cpp | 2 +- editor/reparent_dialog.h | 2 +- editor/scene_tree_dock.cpp | 18 +- editor/scene_tree_dock.h | 2 +- editor/scene_tree_editor.cpp | 4 +- editor/scene_tree_editor.h | 4 +- editor/shader_create_dialog.cpp | 2 +- main/main.cpp | 2 +- .../editor/gdscript_translation_parser_plugin.h | 8 +- modules/gdscript/gdscript.cpp | 8 +- modules/gdscript/gdscript.h | 13 +- modules/gdscript/gdscript_analyzer.cpp | 6 +- modules/gdscript/gdscript_analyzer.h | 2 +- modules/gdscript/gdscript_cache.cpp | 6 +- modules/gdscript/gdscript_cache.h | 4 +- modules/gdscript/gdscript_compiler.h | 6 +- modules/gdscript/gdscript_editor.cpp | 4 +- modules/gdscript/gdscript_parser.h | 8 +- modules/gdscript/gdscript_tokenizer.h | 2 +- .../language_server/gdscript_workspace.cpp | 2 +- modules/gdscript/register_types.cpp | 2 +- modules/gltf/gltf_document.h | 10 +- modules/gltf/gltf_skeleton.h | 2 +- modules/gltf/gltf_state.h | 4 +- modules/gridmap/grid_map.h | 2 +- modules/mono/csharp_script.cpp | 18 +- modules/mono/csharp_script.h | 12 +- modules/raycast/lightmap_raycaster.cpp | 2 +- modules/raycast/lightmap_raycaster.h | 4 +- modules/raycast/raycast_occlusion_cull.h | 16 +- modules/raycast/static_raycaster.cpp | 2 +- modules/raycast/static_raycaster.h | 4 +- modules/text_server_adv/text_server_adv.cpp | 2 +- modules/text_server_adv/text_server_adv.h | 4 +- modules/visual_script/visual_script.cpp | 2 +- modules/visual_script/visual_script.h | 3 +- platform/android/export/export_plugin.cpp | 2 +- platform/android/export/export_plugin.h | 2 +- platform/iphone/export/export_plugin.cpp | 6 +- platform/iphone/export/export_plugin.h | 2 +- platform/javascript/export/export_plugin.h | 2 +- platform/linuxbsd/display_server_x11.cpp | 2 +- platform/linuxbsd/display_server_x11.h | 2 +- platform/osx/display_server_osx.h | 2 +- platform/osx/export/export_plugin.h | 2 +- platform/osx/godot_window_delegate.mm | 2 +- platform/uwp/export/app_packager.h | 2 +- platform/uwp/export/export_plugin.cpp | 2 +- platform/uwp/export/export_plugin.h | 2 +- platform/windows/display_server_windows.cpp | 2 +- platform/windows/display_server_windows.h | 2 +- scene/2d/audio_stream_player_2d.cpp | 2 +- scene/2d/ray_cast_2d.h | 2 +- scene/2d/shape_cast_2d.h | 2 +- scene/2d/visible_on_screen_notifier_2d.h | 2 +- scene/3d/audio_stream_player_3d.cpp | 2 +- scene/3d/collision_object_3d.h | 2 +- scene/3d/lightmapper.h | 2 +- scene/3d/ray_cast_3d.h | 2 +- scene/3d/skeleton_3d.h | 2 +- scene/3d/spring_arm_3d.h | 2 +- scene/3d/vehicle_body_3d.h | 2 +- scene/animation/animation_player.h | 2 +- scene/animation/animation_tree.h | 2 +- scene/debugger/scene_debugger.cpp | 65 +-- scene/debugger/scene_debugger.h | 2 +- scene/gui/base_button.h | 2 +- scene/gui/code_edit.h | 4 +- scene/gui/graph_edit.cpp | 33 +- scene/gui/graph_edit.h | 23 +- scene/gui/grid_container.cpp | 9 +- scene/gui/range.h | 2 +- scene/main/node.cpp | 6 +- scene/main/node.h | 4 +- scene/main/resource_preloader.cpp | 2 +- scene/main/scene_tree.h | 2 +- scene/main/viewport.h | 8 +- scene/main/window.h | 2 +- scene/multiplayer/multiplayer_spawner.h | 2 +- scene/multiplayer/scene_replication_interface.cpp | 2 +- scene/multiplayer/scene_replication_state.cpp | 4 +- scene/multiplayer/scene_replication_state.h | 16 +- scene/resources/bit_map.cpp | 4 +- scene/resources/concave_polygon_shape_3d.cpp | 2 +- scene/resources/concave_polygon_shape_3d.h | 12 +- scene/resources/packed_scene.cpp | 2 +- scene/resources/polygon_path_finder.cpp | 2 +- scene/resources/polygon_path_finder.h | 22 +- scene/resources/resource_format_text.cpp | 4 +- scene/resources/resource_format_text.h | 2 +- scene/resources/theme.cpp | 2 +- scene/resources/tile_set.cpp | 2 +- scene/resources/tile_set.h | 1 + scene/resources/visual_shader.cpp | 16 +- scene/resources/visual_shader.h | 4 +- scene/resources/world_2d.h | 4 +- scene/resources/world_3d.h | 4 +- servers/audio/audio_stream.h | 4 +- servers/extensions/physics_server_3d_extension.cpp | 6 +- servers/extensions/physics_server_3d_extension.h | 6 +- servers/physics_2d/godot_area_2d.h | 4 +- servers/physics_2d/godot_physics_server_2d.cpp | 2 +- servers/physics_2d/godot_physics_server_2d.h | 2 +- servers/physics_2d/godot_space_2d.cpp | 2 +- servers/physics_2d/godot_space_2d.h | 4 +- servers/physics_3d/godot_area_3d.h | 4 +- servers/physics_3d/godot_physics_server_3d.cpp | 2 +- servers/physics_3d/godot_physics_server_3d.h | 2 +- servers/physics_3d/godot_soft_body_3d.h | 6 +- servers/physics_3d/godot_space_3d.cpp | 2 +- servers/physics_3d/godot_space_3d.h | 4 +- servers/physics_server_2d.h | 10 +- servers/physics_server_3d.h | 10 +- servers/rendering/renderer_canvas_cull.cpp | 8 +- servers/rendering/renderer_canvas_cull.h | 10 +- .../scene_shader_forward_clustered.h | 2 +- .../renderer_rd/renderer_scene_render_rd.h | 2 +- .../renderer_rd/storage_rd/material_storage.cpp | 2 +- .../renderer_rd/storage_rd/material_storage.h | 4 +- .../renderer_rd/storage_rd/mesh_storage.h | 2 +- .../renderer_rd/storage_rd/particles_storage.h | 2 +- .../renderer_rd/storage_rd/texture_storage.h | 2 +- servers/rendering/renderer_scene_cull.cpp | 12 +- servers/rendering/renderer_scene_cull.h | 30 +- servers/rendering/renderer_storage.h | 2 +- servers/rendering/shader_compiler.cpp | 4 +- servers/rendering/shader_compiler.h | 14 +- servers/rendering/shader_language.cpp | 20 +- servers/rendering/shader_language.h | 10 +- servers/rendering/shader_types.cpp | 2 +- servers/rendering/shader_types.h | 4 +- tests/core/templates/test_hash_set.h | 228 ++++++++++ tests/test_main.cpp | 1 + 243 files changed, 1400 insertions(+), 662 deletions(-) create mode 100644 core/templates/hash_set.h create mode 100644 tests/core/templates/test_hash_set.h diff --git a/core/config/project_settings.h b/core/config/project_settings.h index bacc8adc54..d9b1a9b81b 100644 --- a/core/config/project_settings.h +++ b/core/config/project_settings.h @@ -91,7 +91,7 @@ protected: bool using_datapack = false; List input_presets; - RBSet custom_features; + HashSet custom_features; HashMap feature_overrides; HashMap autoloads; diff --git a/core/debugger/local_debugger.cpp b/core/debugger/local_debugger.cpp index f378ba94c3..06e08081e9 100644 --- a/core/debugger/local_debugger.cpp +++ b/core/debugger/local_debugger.cpp @@ -241,15 +241,15 @@ void LocalDebugger::debug(bool p_can_continue, bool p_is_error_breakpoint) { } else if (line.begins_with("br") || line.begins_with("break")) { if (line.get_slice_count(" ") <= 1) { - const HashMap> &breakpoints = script_debugger->get_breakpoints(); + const HashMap> &breakpoints = script_debugger->get_breakpoints(); if (breakpoints.size() == 0) { print_line("No Breakpoints."); continue; } print_line("Breakpoint(s): " + itos(breakpoints.size())); - for (const KeyValue> &E : breakpoints) { - print_line("\t" + String(E.value.front()->get()) + ":" + itos(E.key)); + for (const KeyValue> &E : breakpoints) { + print_line("\t" + String(*E.value.begin()) + ":" + itos(E.key)); } } else { diff --git a/core/debugger/script_debugger.cpp b/core/debugger/script_debugger.cpp index 1efa7f7690..e30f3e7886 100644 --- a/core/debugger/script_debugger.cpp +++ b/core/debugger/script_debugger.cpp @@ -50,7 +50,7 @@ int ScriptDebugger::get_depth() const { void ScriptDebugger::insert_breakpoint(int p_line, const StringName &p_source) { if (!breakpoints.has(p_line)) { - breakpoints[p_line] = RBSet(); + breakpoints[p_line] = HashSet(); } breakpoints[p_line].insert(p_source); } diff --git a/core/debugger/script_debugger.h b/core/debugger/script_debugger.h index a5a72d7c54..5124b357a5 100644 --- a/core/debugger/script_debugger.h +++ b/core/debugger/script_debugger.h @@ -33,8 +33,8 @@ #include "core/object/script_language.h" #include "core/string/string_name.h" +#include "core/templates/hash_set.h" #include "core/templates/rb_map.h" -#include "core/templates/rb_set.h" #include "core/templates/vector.h" class ScriptDebugger { @@ -44,7 +44,7 @@ class ScriptDebugger { int depth = -1; bool skip_breakpoints = false; - HashMap> breakpoints; + HashMap> breakpoints; ScriptLanguage *break_lang = nullptr; Vector error_stack_info; @@ -66,7 +66,7 @@ public: bool is_breakpoint(int p_line, const StringName &p_source) const; bool is_breakpoint_line(int p_line) const; void clear_breakpoints(); - const HashMap> &get_breakpoints() const { return breakpoints; } + const HashMap> &get_breakpoints() const { return breakpoints; } void debug(ScriptLanguage *p_lang, bool p_can_continue = true, bool p_is_error_breakpoint = false); ScriptLanguage *get_break_language() const; diff --git a/core/input/input.h b/core/input/input.h index 7bb7889a43..9a5b8e6e06 100644 --- a/core/input/input.h +++ b/core/input/input.h @@ -35,6 +35,7 @@ #include "core/object/object.h" #include "core/os/keyboard.h" #include "core/os/thread_safe.h" +#include "core/templates/rb_set.h" class Input : public Object { GDCLASS(Input, Object); diff --git a/core/io/file_access_pack.h b/core/io/file_access_pack.h index 404ad38c96..19a0cce796 100644 --- a/core/io/file_access_pack.h +++ b/core/io/file_access_pack.h @@ -34,9 +34,9 @@ #include "core/io/dir_access.h" #include "core/io/file_access.h" #include "core/string/print_string.h" +#include "core/templates/hash_set.h" #include "core/templates/list.h" #include "core/templates/rb_map.h" -#include "core/templates/rb_set.h" // Godot's packed file magic header ("GDPC" in ASCII). #define PACK_HEADER_MAGIC 0x43504447 @@ -73,7 +73,7 @@ private: PackedDir *parent = nullptr; String name; HashMap subdirs; - RBSet files; + HashSet files; }; struct PathMD5 { diff --git a/core/io/json.cpp b/core/io/json.cpp index b3a9762e75..4c4d91f851 100644 --- a/core/io/json.cpp +++ b/core/io/json.cpp @@ -55,7 +55,7 @@ String JSON::_make_indent(const String &p_indent, int p_size) { return indent_text; } -String JSON::_stringify(const Variant &p_var, const String &p_indent, int p_cur_indent, bool p_sort_keys, RBSet &p_markers, bool p_full_precision) { +String JSON::_stringify(const Variant &p_var, const String &p_indent, int p_cur_indent, bool p_sort_keys, HashSet &p_markers, bool p_full_precision) { String colon = ":"; String end_statement = ""; @@ -529,7 +529,7 @@ Error JSON::_parse_string(const String &p_json, Variant &r_ret, String &r_err_st } String JSON::stringify(const Variant &p_var, const String &p_indent, bool p_sort_keys, bool p_full_precision) { - RBSet markers; + HashSet markers; return _stringify(p_var, p_indent, 0, p_sort_keys, markers, p_full_precision); } diff --git a/core/io/json.h b/core/io/json.h index f883d3963a..6ba0a8c76b 100644 --- a/core/io/json.h +++ b/core/io/json.h @@ -70,7 +70,7 @@ class JSON : public RefCounted { static const char *tk_name[]; static String _make_indent(const String &p_indent, int p_size); - static String _stringify(const Variant &p_var, const String &p_indent, int p_cur_indent, bool p_sort_keys, RBSet &p_markers, bool p_full_precision = false); + static String _stringify(const Variant &p_var, const String &p_indent, int p_cur_indent, bool p_sort_keys, HashSet &p_markers, bool p_full_precision = false); static Error _get_token(const char32_t *p_str, int &index, int p_len, Token &r_token, int &line, String &r_err_str); static Error _parse_value(Variant &value, Token &token, const char32_t *p_str, int &index, int p_len, int &line, String &r_err_str); static Error _parse_array(Array &array, const char32_t *p_str, int &index, int p_len, int &line, String &r_err_str); diff --git a/core/io/logger.cpp b/core/io/logger.cpp index 925bfdbd02..0418825009 100644 --- a/core/io/logger.cpp +++ b/core/io/logger.cpp @@ -128,7 +128,7 @@ void RotatedFileLogger::clear_old_backups() { da->list_dir_begin(); String f = da->get_next(); - RBSet backups; + HashSet backups; while (!f.is_empty()) { if (!da->current_is_dir() && f.begins_with(basename) && f.get_extension() == extension && f != base_path.get_file()) { backups.insert(f); @@ -137,12 +137,12 @@ void RotatedFileLogger::clear_old_backups() { } da->list_dir_end(); - if (backups.size() > max_backups) { + if (backups.size() > (uint32_t)max_backups) { // since backups are appended with timestamp and Set iterates them in sorted order, // first backups are the oldest int to_delete = backups.size() - max_backups; - for (RBSet::Element *E = backups.front(); E && to_delete > 0; E = E->next(), --to_delete) { - da->remove(E->get()); + for (HashSet::Iterator E = backups.begin(); E && to_delete > 0; ++E, --to_delete) { + da->remove(*E); } } } diff --git a/core/io/resource.h b/core/io/resource.h index 53c828f9cd..a45bc6e1e4 100644 --- a/core/io/resource.h +++ b/core/io/resource.h @@ -54,7 +54,7 @@ public: virtual String get_base_extension() const { return "res"; } private: - RBSet owners; + HashSet owners; friend class ResBase; friend class ResourceCache; diff --git a/core/io/resource_format_binary.cpp b/core/io/resource_format_binary.cpp index cf87869a32..cb634632c8 100644 --- a/core/io/resource_format_binary.cpp +++ b/core/io/resource_format_binary.cpp @@ -2022,7 +2022,7 @@ Error ResourceFormatSaverBinaryInstance::save(const String &p_path, const Refstore_32(saved_resources.size()); //amount of internal resources Vector ofs_pos; - RBSet used_unique_ids; + HashSet used_unique_ids; for (Ref &r : saved_resources) { if (r->is_built_in()) { diff --git a/core/io/resource_format_binary.h b/core/io/resource_format_binary.h index db29909dd5..5da880ddb8 100644 --- a/core/io/resource_format_binary.h +++ b/core/io/resource_format_binary.h @@ -127,7 +127,7 @@ class ResourceFormatSaverBinaryInstance { bool big_endian; bool takeover_paths; String magic; - RBSet> resource_set; + HashSet> resource_set; struct NonPersistentKey { //for resource properties generated on the fly Ref base; diff --git a/core/io/resource_importer.cpp b/core/io/resource_importer.cpp index 5deee9721b..934cb780e6 100644 --- a/core/io/resource_importer.cpp +++ b/core/io/resource_importer.cpp @@ -139,7 +139,7 @@ Ref ResourceFormatImporter::load(const String &p_path, const String &p } void ResourceFormatImporter::get_recognized_extensions(List *p_extensions) const { - RBSet found; + HashSet found; for (int i = 0; i < importers.size(); i++) { List local_exts; @@ -159,7 +159,7 @@ void ResourceFormatImporter::get_recognized_extensions_for_type(const String &p_ return; } - RBSet found; + HashSet found; for (int i = 0; i < importers.size(); i++) { String res_type = importers[i]->get_resource_type(); diff --git a/core/io/resource_loader.h b/core/io/resource_loader.h index e189ad1dff..815dd1dd72 100644 --- a/core/io/resource_loader.h +++ b/core/io/resource_loader.h @@ -145,7 +145,7 @@ private: bool start_next = true; int requests = 0; int poll_requests = 0; - RBSet sub_tasks; + HashSet sub_tasks; }; static void _thread_load_function(void *p_userdata); 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::Element *element = segments.find(s); - if (element != nullptr) { - s.direction |= element->get().direction; + HashSet::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::Element *element = segments.find(s); - if (element != nullptr) { + HashSet::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 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::Element *element = segments.find(s); + const HashSet::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 points; - RBSet segments; + HashSet 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 &p_points, Geometry3D::MeshData &r_ Vector valid_points; valid_points.resize(p_points.size()); - RBSet valid_cache; + HashSet 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 &p_mesh_ids) = 0; + virtual void set_mesh_filter(const HashSet &p_mesh_ids) = 0; virtual void clear_mesh_filter() = 0; static Ref create(); diff --git a/core/multiplayer/multiplayer_api.h b/core/multiplayer/multiplayer_api.h index b93f2acbd3..cc7743ccf8 100644 --- a/core/multiplayer/multiplayer_api.h +++ b/core/multiplayer/multiplayer_api.h @@ -113,7 +113,7 @@ public: private: Ref multiplayer_peer; - RBSet connected_peers; + HashSet connected_peers; int remote_sender_id = 0; int remote_sender_override = 0; @@ -172,7 +172,7 @@ public: bool has_multiplayer_peer() const { return multiplayer_peer.is_valid(); } Vector get_peer_ids() const; - const RBSet get_connected_peers() const { return connected_peers; } + const HashSet get_connected_peers() const { return connected_peers; } int get_remote_sender_id() const { return remote_sender_override ? remote_sender_override : remote_sender_id; } void set_remote_sender_override(int p_id) { remote_sender_override = p_id; } int get_unique_id() const; diff --git a/core/object/class_db.cpp b/core/object/class_db.cpp index d19cbf2642..f61bd24efd 100644 --- a/core/object/class_db.cpp +++ b/core/object/class_db.cpp @@ -1390,7 +1390,7 @@ void ClassDB::get_extensions_for_type(const StringName &p_class, List *p } HashMap> ClassDB::default_values; -RBSet ClassDB::default_values_cached; +HashSet ClassDB::default_values_cached; Variant ClassDB::class_get_default_property_value(const StringName &p_class, const StringName &p_property, bool *r_valid) { if (!default_values_cached.has(p_class)) { diff --git a/core/object/class_db.h b/core/object/class_db.h index 67b71ab058..2448a86e33 100644 --- a/core/object/class_db.h +++ b/core/object/class_db.h @@ -38,6 +38,7 @@ // Makes callable_mp readily available in all classes connecting signals. // Needs to come after method_bind and object have been included. #include "core/object/callable_method_pointer.h" +#include "core/templates/hash_set.h" #define DEFVAL(m_defval) (m_defval) @@ -110,7 +111,7 @@ public: #ifdef DEBUG_METHODS_ENABLED List constant_order; List method_order; - RBSet methods_in_properties; + HashSet methods_in_properties; List virtual_methods; HashMap virtual_methods_map; HashMap> method_error_values; @@ -149,7 +150,7 @@ public: static void _add_class2(const StringName &p_class, const StringName &p_inherits); static HashMap> default_values; - static RBSet default_values_cached; + static HashSet default_values_cached; // Native structs, used by binder struct NativeStruct { diff --git a/core/object/object.h b/core/object/object.h index ca7b9965f1..988d261d77 100644 --- a/core/object/object.h +++ b/core/object/object.h @@ -37,9 +37,9 @@ #include "core/os/rw_lock.h" #include "core/os/spin_lock.h" #include "core/templates/hash_map.h" +#include "core/templates/hash_set.h" #include "core/templates/list.h" #include "core/templates/rb_map.h" -#include "core/templates/rb_set.h" #include "core/templates/safe_refcount.h" #include "core/templates/vmap.h" #include "core/variant/callable_bind.h" @@ -510,7 +510,7 @@ private: #ifdef TOOLS_ENABLED bool _edited = false; uint32_t _edited_version = 0; - RBSet editor_section_folding; + HashSet editor_section_folding; #endif ScriptInstance *script_instance = nullptr; Variant script; // Reference does not exist yet, store it in a Variant. @@ -815,7 +815,7 @@ public: #ifdef TOOLS_ENABLED void editor_set_section_unfold(const String &p_section, bool p_unfolded); bool editor_is_section_unfolded(const String &p_section); - const RBSet &editor_get_section_folding() const { return editor_section_folding; } + const HashSet &editor_get_section_folding() const { return editor_section_folding; } void editor_clear_section_folding() { editor_section_folding.clear(); } #endif diff --git a/core/object/script_language.cpp b/core/object/script_language.cpp index 1546d52fd2..66c9a80193 100644 --- a/core/object/script_language.cpp +++ b/core/object/script_language.cpp @@ -475,7 +475,7 @@ bool PlaceHolderScriptInstance::has_method(const StringName &p_method) const { } void PlaceHolderScriptInstance::update(const List &p_properties, const HashMap &p_values) { - RBSet new_values; + HashSet new_values; for (const PropertyInfo &E : p_properties) { StringName n = E.name; new_values.insert(n); diff --git a/core/object/script_language.h b/core/object/script_language.h index b1481a372e..0a8e79a24e 100644 --- a/core/object/script_language.h +++ b/core/object/script_language.h @@ -155,7 +155,7 @@ public: virtual int get_member_line(const StringName &p_member) const { return -1; } virtual void get_constants(HashMap *p_constants) {} - virtual void get_members(RBSet *p_constants) {} + virtual void get_members(HashSet *p_constants) {} virtual bool is_placeholder_fallback_enabled() const { return false; } @@ -283,7 +283,7 @@ public: virtual Ref