diff options
| 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 /core | |
| parent | 396def9b66c476f7834604adb7136ca903ed01be (diff) | |
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!
Diffstat (limited to 'core')
71 files changed, 414 insertions, 357 deletions
diff --git a/core/config/engine.cpp b/core/config/engine.cpp index ff8a8d283f..782d369ae6 100644 --- a/core/config/engine.cpp +++ b/core/config/engine.cpp @@ -208,9 +208,9 @@ void Engine::add_singleton(const Singleton &p_singleton) { } Object *Engine::get_singleton_object(const StringName &p_name) const { - const Map<StringName, Object *>::Element *E = singleton_ptrs.find(p_name); + HashMap<StringName, Object *>::ConstIterator E = singleton_ptrs.find(p_name); ERR_FAIL_COND_V_MSG(!E, nullptr, "Failed to retrieve non-existent singleton '" + String(p_name) + "'."); - return E->get(); + return E->value; } bool Engine::is_singleton_user_created(const StringName &p_name) const { diff --git a/core/config/engine.h b/core/config/engine.h index eac96852b3..82e3ee5487 100644 --- a/core/config/engine.h +++ b/core/config/engine.h @@ -69,7 +69,7 @@ private: bool _in_physics = false; List<Singleton> singletons; - Map<StringName, Object *> singleton_ptrs; + HashMap<StringName, Object *> singleton_ptrs; bool editor_hint = false; bool project_manager_hint = false; diff --git a/core/config/project_settings.cpp b/core/config/project_settings.cpp index ba108d75da..3ef9a69d06 100644 --- a/core/config/project_settings.cpp +++ b/core/config/project_settings.cpp @@ -331,7 +331,7 @@ struct _VCSort { void ProjectSettings::_get_property_list(List<PropertyInfo> *p_list) const { _THREAD_SAFE_METHOD_ - Set<_VCSort> vclist; + RBSet<_VCSort> vclist; for (const KeyValue<StringName, VariantContainer> &E : props) { const VariantContainer *v = &E.value; @@ -360,7 +360,7 @@ void ProjectSettings::_get_property_list(List<PropertyInfo> *p_list) const { vclist.insert(vc); } - for (Set<_VCSort>::Element *E = vclist.front(); E; E = E->next()) { + for (RBSet<_VCSort>::Element *E = vclist.front(); E; E = E->next()) { String prop_info_name = E->get().name; int dot = prop_info_name.find("."); if (dot != -1 && !custom_prop_info.has(prop_info_name)) { @@ -764,7 +764,7 @@ Error ProjectSettings::save() { return error; } -Error ProjectSettings::_save_settings_binary(const String &p_file, const Map<String, List<String>> &props, const CustomMap &p_custom, const String &p_custom_features) { +Error ProjectSettings::_save_settings_binary(const String &p_file, const HashMap<String, List<String>> &props, const CustomMap &p_custom, const String &p_custom_features) { Error err; Ref<FileAccess> file = FileAccess::open(p_file, FileAccess::WRITE, &err); ERR_FAIL_COND_V_MSG(err != OK, err, "Couldn't save project.binary at " + p_file + "."); @@ -800,19 +800,20 @@ Error ProjectSettings::_save_settings_binary(const String &p_file, const Map<Str file->store_32(count); //store how many properties are saved } - for (Map<String, List<String>>::Element *E = props.front(); E; E = E->next()) { - for (String &key : E->get()) { - if (!E->key().is_empty()) { - key = E->key() + "/" + key; + for (const KeyValue<String, List<String>> &E : props) { + for (const String &key : E.value) { + String k = key; + if (!E.key.is_empty()) { + k = E.key + "/" + k; } Variant value; - if (p_custom.has(key)) { - value = p_custom[key]; + if (p_custom.has(k)) { + value = p_custom[k]; } else { - value = get(key); + value = get(k); } - file->store_pascal_string(key); + file->store_pascal_string(k); int len; err = encode_variant(value, nullptr, len, true); @@ -831,7 +832,7 @@ Error ProjectSettings::_save_settings_binary(const String &p_file, const Map<Str return OK; } -Error ProjectSettings::_save_settings_text(const String &p_file, const Map<String, List<String>> &props, const CustomMap &p_custom, const String &p_custom_features) { +Error ProjectSettings::_save_settings_text(const String &p_file, const HashMap<String, List<String>> &props, const CustomMap &p_custom, const String &p_custom_features) { Error err; Ref<FileAccess> file = FileAccess::open(p_file, FileAccess::WRITE, &err); @@ -852,18 +853,18 @@ Error ProjectSettings::_save_settings_text(const String &p_file, const Map<Strin } file->store_string("\n"); - for (const Map<String, List<String>>::Element *E = props.front(); E; E = E->next()) { - if (E != props.front()) { + for (const KeyValue<String, List<String>> &E : props) { + if (E.key != props.begin()->key) { file->store_string("\n"); } - if (!E->key().is_empty()) { - file->store_string("[" + E->key() + "]\n\n"); + if (!E.key.is_empty()) { + file->store_string("[" + E.key + "]\n\n"); } - for (const String &F : E->get()) { + for (const String &F : E.value) { String key = F; - if (!E->key().is_empty()) { - key = E->key() + "/" + key; + if (!E.key.is_empty()) { + key = E.key + "/" + key; } Variant value; if (p_custom.has(key)) { @@ -917,7 +918,7 @@ Error ProjectSettings::save_custom(const String &p_path, const CustomMap &p_cust project_features = _trim_to_supported_features(project_features); set_setting("application/config/features", project_features); - Set<_VCSort> vclist; + RBSet<_VCSort> vclist; if (p_merge_with_current) { for (const KeyValue<StringName, VariantContainer> &G : props) { @@ -946,19 +947,19 @@ Error ProjectSettings::save_custom(const String &p_path, const CustomMap &p_cust for (const KeyValue<String, Variant> &E : p_custom) { // Lookup global prop to store in the same order - Map<StringName, VariantContainer>::Element *global_prop = props.find(E.key); + HashMap<StringName, VariantContainer>::Iterator global_prop = props.find(E.key); _VCSort vc; vc.name = E.key; - vc.order = global_prop ? global_prop->get().order : 0xFFFFFFF; + vc.order = global_prop ? global_prop->value.order : 0xFFFFFFF; vc.type = E.value.get_type(); vc.flags = PROPERTY_USAGE_STORAGE; vclist.insert(vc); } - Map<String, List<String>> props; + HashMap<String, List<String>> props; - for (Set<_VCSort>::Element *E = vclist.front(); E; E = E->next()) { + for (RBSet<_VCSort>::Element *E = vclist.front(); E; E = E->next()) { String category = E->get().name; String name = E->get().name; @@ -1051,7 +1052,7 @@ void ProjectSettings::set_custom_property_info(const String &p_prop, const Prope custom_prop_info[p_prop].name = p_prop; } -const Map<StringName, PropertyInfo> &ProjectSettings::get_custom_property_info() const { +const HashMap<StringName, PropertyInfo> &ProjectSettings::get_custom_property_info() const { return custom_prop_info; } diff --git a/core/config/project_settings.h b/core/config/project_settings.h index 8655526edd..f8dc618cb8 100644 --- a/core/config/project_settings.h +++ b/core/config/project_settings.h @@ -34,14 +34,14 @@ #include "core/object/class_db.h" #include "core/os/thread_safe.h" #include "core/templates/hash_map.h" -#include "core/templates/set.h" +#include "core/templates/rb_set.h" class ProjectSettings : public Object { GDCLASS(ProjectSettings, Object); _THREAD_SAFE_CLASS_ public: - typedef Map<String, Variant> CustomMap; + typedef HashMap<String, Variant> CustomMap; static const String PROJECT_DATA_DIR_NAME_SUFFIX; enum { @@ -84,15 +84,15 @@ protected: int last_builtin_order = 0; uint64_t last_save_time = 0; - Map<StringName, VariantContainer> props; + HashMap<StringName, VariantContainer> props; String resource_path; - Map<StringName, PropertyInfo> custom_prop_info; + HashMap<StringName, PropertyInfo> custom_prop_info; bool disable_feature_overrides = false; bool using_datapack = false; List<String> input_presets; - Set<String> custom_features; - Map<StringName, StringName> feature_overrides; + RBSet<String> custom_features; + HashMap<StringName, StringName> feature_overrides; HashMap<StringName, AutoloadInfo> autoloads; @@ -108,8 +108,8 @@ protected: Error _load_settings_binary(const String &p_path); Error _load_settings_text_or_binary(const String &p_text_path, const String &p_bin_path); - Error _save_settings_text(const String &p_file, const Map<String, List<String>> &props, const CustomMap &p_custom = CustomMap(), const String &p_custom_features = String()); - Error _save_settings_binary(const String &p_file, const Map<String, List<String>> &props, const CustomMap &p_custom = CustomMap(), const String &p_custom_features = String()); + Error _save_settings_text(const String &p_file, const HashMap<String, List<String>> &props, const CustomMap &p_custom = CustomMap(), const String &p_custom_features = String()); + Error _save_settings_binary(const String &p_file, const HashMap<String, List<String>> &props, const CustomMap &p_custom = CustomMap(), const String &p_custom_features = String()); Error _save_custom_bnd(const String &p_file); @@ -168,7 +168,7 @@ public: Error save_custom(const String &p_path = "", const CustomMap &p_custom = CustomMap(), const Vector<String> &p_custom_features = Vector<String>(), bool p_merge_with_current = true); Error save(); void set_custom_property_info(const String &p_prop, const PropertyInfo &p_info); - const Map<StringName, PropertyInfo> &get_custom_property_info() const; + const HashMap<StringName, PropertyInfo> &get_custom_property_info() const; uint64_t get_last_saved_time() { return last_save_time; } Vector<String> get_optimizer_presets() const; diff --git a/core/core_bind.cpp b/core/core_bind.cpp index 7c3cbfe48d..194c7fdefd 100644 --- a/core/core_bind.cpp +++ b/core/core_bind.cpp @@ -439,7 +439,7 @@ void OS::print_resources_by_type(const Vector<String> &p_types) { print_line(vformat("Resources currently in use for the following types: %s", p_types)); - Map<String, int> type_count; + RBMap<String, int> type_count; List<Ref<Resource>> resources; ResourceCache::get_cached_resources(&resources); diff --git a/core/core_bind.h b/core/core_bind.h index 76313dc1a8..e4d15d5c9d 100644 --- a/core/core_bind.h +++ b/core/core_bind.h @@ -680,8 +680,8 @@ public: class EngineDebugger : public Object { GDCLASS(EngineDebugger, Object); - Map<StringName, Callable> captures; - Map<StringName, Ref<EngineProfiler>> profilers; + HashMap<StringName, Callable> captures; + HashMap<StringName, Ref<EngineProfiler>> profilers; protected: static void _bind_methods(); diff --git a/core/debugger/engine_debugger.cpp b/core/debugger/engine_debugger.cpp index 54760d8d65..263c75760b 100644 --- a/core/debugger/engine_debugger.cpp +++ b/core/debugger/engine_debugger.cpp @@ -39,9 +39,9 @@ EngineDebugger *EngineDebugger::singleton = nullptr; ScriptDebugger *EngineDebugger::script_debugger = nullptr; -Map<StringName, EngineDebugger::Profiler> EngineDebugger::profilers; -Map<StringName, EngineDebugger::Capture> EngineDebugger::captures; -Map<String, EngineDebugger::CreatePeerFunc> EngineDebugger::protocols; +HashMap<StringName, EngineDebugger::Profiler> EngineDebugger::profilers; +HashMap<StringName, EngineDebugger::Capture> EngineDebugger::captures; +HashMap<String, EngineDebugger::CreatePeerFunc> EngineDebugger::protocols; void EngineDebugger::register_profiler(const StringName &p_name, const Profiler &p_func) { ERR_FAIL_COND_MSG(profilers.has(p_name), "Profiler already registered: " + p_name); diff --git a/core/debugger/engine_debugger.h b/core/debugger/engine_debugger.h index fdfa41c9cc..a8a791f9b0 100644 --- a/core/debugger/engine_debugger.h +++ b/core/debugger/engine_debugger.h @@ -33,7 +33,7 @@ #include "core/string/string_name.h" #include "core/string/ustring.h" -#include "core/templates/map.h" +#include "core/templates/hash_map.h" #include "core/templates/vector.h" #include "core/variant/array.h" #include "core/variant/variant.h" @@ -96,9 +96,9 @@ protected: static EngineDebugger *singleton; static ScriptDebugger *script_debugger; - static Map<StringName, Profiler> profilers; - static Map<StringName, Capture> captures; - static Map<String, CreatePeerFunc> protocols; + static HashMap<StringName, Profiler> profilers; + static HashMap<StringName, Capture> captures; + static HashMap<String, CreatePeerFunc> protocols; public: _FORCE_INLINE_ static EngineDebugger *get_singleton() { return singleton; } diff --git a/core/debugger/local_debugger.cpp b/core/debugger/local_debugger.cpp index 4ed4c97c64..f378ba94c3 100644 --- a/core/debugger/local_debugger.cpp +++ b/core/debugger/local_debugger.cpp @@ -241,14 +241,14 @@ 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 Map<int, Set<StringName>> &breakpoints = script_debugger->get_breakpoints(); + const HashMap<int, RBSet<StringName>> &breakpoints = script_debugger->get_breakpoints(); if (breakpoints.size() == 0) { print_line("No Breakpoints."); continue; } print_line("Breakpoint(s): " + itos(breakpoints.size())); - for (const KeyValue<int, Set<StringName>> &E : breakpoints) { + for (const KeyValue<int, RBSet<StringName>> &E : breakpoints) { print_line("\t" + String(E.value.front()->get()) + ":" + itos(E.key)); } diff --git a/core/debugger/local_debugger.h b/core/debugger/local_debugger.h index ecd805a6cb..c687214c65 100644 --- a/core/debugger/local_debugger.h +++ b/core/debugger/local_debugger.h @@ -42,7 +42,7 @@ private: ScriptsProfiler *scripts_profiler = nullptr; String target_function; - Map<String, String> options; + HashMap<String, String> options; Pair<String, int> to_breakpoint(const String &p_line); void print_variables(const List<String> &names, const List<Variant> &values, const String &variable_prefix); diff --git a/core/debugger/script_debugger.cpp b/core/debugger/script_debugger.cpp index 4dd93249ef..1efa7f7690 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] = Set<StringName>(); + breakpoints[p_line] = RBSet<StringName>(); } breakpoints[p_line].insert(p_source); } diff --git a/core/debugger/script_debugger.h b/core/debugger/script_debugger.h index feb6702b54..a5a72d7c54 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/map.h" -#include "core/templates/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; - Map<int, Set<StringName>> breakpoints; + HashMap<int, RBSet<StringName>> breakpoints; ScriptLanguage *break_lang = nullptr; Vector<StackInfo> 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 Map<int, Set<StringName>> &get_breakpoints() const { return breakpoints; } + const HashMap<int, RBSet<StringName>> &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/doc_data.h b/core/doc_data.h index 194a39a729..af20b717d7 100644 --- a/core/doc_data.h +++ b/core/doc_data.h @@ -32,7 +32,7 @@ #define DOC_DATA_H #include "core/io/xml_parser.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" #include "core/variant/variant.h" struct ScriptMemberInfo { @@ -161,7 +161,7 @@ public: Vector<MethodDoc> operators; Vector<MethodDoc> signals; Vector<ConstantDoc> constants; - Map<String, String> enums; + HashMap<String, String> enums; Vector<PropertyDoc> properties; Vector<ThemeItemDoc> theme_properties; bool is_script_doc = false; diff --git a/core/extension/extension_api_dump.cpp b/core/extension/extension_api_dump.cpp index 4d5dc7958c..9e8addf8aa 100644 --- a/core/extension/extension_api_dump.cpp +++ b/core/extension/extension_api_dump.cpp @@ -334,7 +334,7 @@ Dictionary NativeExtensionAPIDump::generate_extension_api() { { // Global enums and constants. Array constants; - Map<String, List<Pair<String, int>>> enum_list; + HashMap<String, List<Pair<String, int>>> enum_list; for (int i = 0; i < CoreConstants::get_global_constant_count(); i++) { int value = CoreConstants::get_global_constant_value(i); diff --git a/core/extension/native_extension.h b/core/extension/native_extension.h index af5a474e79..8f106f753d 100644 --- a/core/extension/native_extension.h +++ b/core/extension/native_extension.h @@ -45,7 +45,7 @@ class NativeExtension : public Resource { ObjectNativeExtension native_extension; }; - Map<StringName, Extension> extension_classes; + HashMap<StringName, Extension> extension_classes; static void _register_extension_class(const GDNativeExtensionClassLibraryPtr p_library, const char *p_class_name, const char *p_parent_class_name, const GDNativeExtensionClassCreationInfo *p_extension_funcs); static void _register_extension_class_method(const GDNativeExtensionClassLibraryPtr p_library, const char *p_class_name, const GDNativeExtensionClassMethodInfo *p_method_info); diff --git a/core/extension/native_extension_manager.cpp b/core/extension/native_extension_manager.cpp index 5436f7d51e..186fcc44f6 100644 --- a/core/extension/native_extension_manager.cpp +++ b/core/extension/native_extension_manager.cpp @@ -90,9 +90,9 @@ Vector<String> NativeExtensionManager::get_loaded_extensions() const { return ret; } Ref<NativeExtension> NativeExtensionManager::get_extension(const String &p_path) { - Map<String, Ref<NativeExtension>>::Element *E = native_extension_map.find(p_path); + HashMap<String, Ref<NativeExtension>>::Iterator E = native_extension_map.find(p_path); ERR_FAIL_COND_V(!E, Ref<NativeExtension>()); - return E->get(); + return E->value; } void NativeExtensionManager::initialize_extensions(NativeExtension::InitializationLevel p_level) { diff --git a/core/extension/native_extension_manager.h b/core/extension/native_extension_manager.h index b8339e4817..5594f6c0de 100644 --- a/core/extension/native_extension_manager.h +++ b/core/extension/native_extension_manager.h @@ -37,7 +37,7 @@ class NativeExtensionManager : public Object { GDCLASS(NativeExtensionManager, Object); int32_t level = -1; - Map<String, Ref<NativeExtension>> native_extension_map; + HashMap<String, Ref<NativeExtension>> native_extension_map; static void _bind_methods(); diff --git a/core/input/input.cpp b/core/input/input.cpp index 3a2e50a674..4befdfac58 100644 --- a/core/input/input.cpp +++ b/core/input/input.cpp @@ -227,8 +227,8 @@ Input::VelocityTrack::VelocityTrack() { bool Input::is_anything_pressed() const { _THREAD_SAFE_METHOD_ - for (Map<StringName, Input::Action>::Element *E = action_state.front(); E; E = E->next()) { - if (E->get().pressed) { + for (const KeyValue<StringName, Input::Action> &E : action_state) { + if (E.value.pressed) { return true; } } @@ -272,65 +272,65 @@ bool Input::is_action_pressed(const StringName &p_action, bool p_exact) const { bool Input::is_action_just_pressed(const StringName &p_action, bool p_exact) const { ERR_FAIL_COND_V_MSG(!InputMap::get_singleton()->has_action(p_action), false, InputMap::get_singleton()->suggest_actions(p_action)); - const Map<StringName, Action>::Element *E = action_state.find(p_action); + HashMap<StringName, Action>::ConstIterator E = action_state.find(p_action); if (!E) { return false; } - if (p_exact && E->get().exact == false) { + if (p_exact && E->value.exact == false) { return false; } if (Engine::get_singleton()->is_in_physics_frame()) { - return E->get().pressed && E->get().physics_frame == Engine::get_singleton()->get_physics_frames(); + return E->value.pressed && E->value.physics_frame == Engine::get_singleton()->get_physics_frames(); } else { - return E->get().pressed && E->get().process_frame == Engine::get_singleton()->get_process_frames(); + return E->value.pressed && E->value.process_frame == Engine::get_singleton()->get_process_frames(); } } bool Input::is_action_just_released(const StringName &p_action, bool p_exact) const { ERR_FAIL_COND_V_MSG(!InputMap::get_singleton()->has_action(p_action), false, InputMap::get_singleton()->suggest_actions(p_action)); - const Map<StringName, Action>::Element *E = action_state.find(p_action); + HashMap<StringName, Action>::ConstIterator E = action_state.find(p_action); if (!E) { return false; } - if (p_exact && E->get().exact == false) { + if (p_exact && E->value.exact == false) { return false; } if (Engine::get_singleton()->is_in_physics_frame()) { - return !E->get().pressed && E->get().physics_frame == Engine::get_singleton()->get_physics_frames(); + return !E->value.pressed && E->value.physics_frame == Engine::get_singleton()->get_physics_frames(); } else { - return !E->get().pressed && E->get().process_frame == Engine::get_singleton()->get_process_frames(); + return !E->value.pressed && E->value.process_frame == Engine::get_singleton()->get_process_frames(); } } float Input::get_action_strength(const StringName &p_action, bool p_exact) const { ERR_FAIL_COND_V_MSG(!InputMap::get_singleton()->has_action(p_action), 0.0, InputMap::get_singleton()->suggest_actions(p_action)); - const Map<StringName, Action>::Element *E = action_state.find(p_action); + HashMap<StringName, Action>::ConstIterator E = action_state.find(p_action); if (!E) { return 0.0f; } - if (p_exact && E->get().exact == false) { + if (p_exact && E->value.exact == false) { return 0.0f; } - return E->get().strength; + return E->value.strength; } float Input::get_action_raw_strength(const StringName &p_action, bool p_exact) const { - const Map<StringName, Action>::Element *E = action_state.find(p_action); + HashMap<StringName, Action>::ConstIterator E = action_state.find(p_action); if (!E) { return 0.0f; } - if (p_exact && E->get().exact == false) { + if (p_exact && E->value.exact == false) { return 0.0f; } - return E->get().raw_strength; + return E->value.raw_strength; } float Input::get_axis(const StringName &p_negative_action, const StringName &p_positive_action) const { @@ -1403,12 +1403,12 @@ String Input::get_joy_guid(int p_device) const { Array Input::get_connected_joypads() { Array ret; - Map<int, Joypad>::Element *elem = joy_names.front(); + HashMap<int, Joypad>::Iterator elem = joy_names.begin(); while (elem) { - if (elem->get().connected) { - ret.push_back(elem->key()); + if (elem->value.connected) { + ret.push_back(elem->key); } - elem = elem->next(); + ++elem; } return ret; } diff --git a/core/input/input.h b/core/input/input.h index 5a7cb84ece..7bb7889a43 100644 --- a/core/input/input.h +++ b/core/input/input.h @@ -82,11 +82,11 @@ public: private: MouseButton mouse_button_mask = MouseButton::NONE; - Set<Key> physical_keys_pressed; - Set<Key> keys_pressed; - Set<JoyButton> joy_buttons_pressed; - Map<JoyAxis, float> _joy_axis; - //Map<StringName,int> custom_action_press; + RBSet<Key> physical_keys_pressed; + RBSet<Key> keys_pressed; + RBSet<JoyButton> joy_buttons_pressed; + RBMap<JoyAxis, float> _joy_axis; + //RBMap<StringName,int> custom_action_press; Vector3 gravity; Vector3 accelerometer; Vector3 magnetometer; @@ -103,7 +103,7 @@ private: float raw_strength; }; - Map<StringName, Action> action_state; + HashMap<StringName, Action> action_state; bool emulate_touch_from_mouse = false; bool emulate_mouse_from_touch = false; @@ -137,8 +137,8 @@ private: }; VelocityTrack mouse_velocity_track; - Map<int, VelocityTrack> touch_velocity_track; - Map<int, Joypad> joy_names; + HashMap<int, VelocityTrack> touch_velocity_track; + HashMap<int, Joypad> joy_names; int fallback_mapping = -1; CursorShape default_shape = CURSOR_ARROW; @@ -231,7 +231,7 @@ protected: uint64_t timestamp; }; - Map<int, VibrationInfo> joy_vibration; + HashMap<int, VibrationInfo> joy_vibration; static void _bind_methods(); diff --git a/core/input/input_map.cpp b/core/input/input_map.cpp index 51c1cf9608..942c5248df 100644 --- a/core/input/input_map.cpp +++ b/core/input/input_map.cpp @@ -691,12 +691,12 @@ const HashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with_featur return default_builtin_with_overrides_cache; } - HashMap<String, List<Ref<InputEvent>>> builtins = get_builtins(); + const HashMap<String, List<Ref<InputEvent>>> &builtins = get_builtins(); // Get a list of all built in inputs which are valid overrides for the OS // Key = builtin name (e.g. ui_accept) // Value = override/feature names (e.g. macos, if it was defined as "ui_accept.macos" and the platform supports that feature) - Map<String, Vector<String>> builtins_with_overrides; + HashMap<String, Vector<String>> builtins_with_overrides; for (const KeyValue<String, List<Ref<InputEvent>>> &E : builtins) { String fullname = E.key; diff --git a/core/io/file_access_memory.cpp b/core/io/file_access_memory.cpp index 943dc72307..499d001234 100644 --- a/core/io/file_access_memory.cpp +++ b/core/io/file_access_memory.cpp @@ -32,13 +32,13 @@ #include "core/config/project_settings.h" #include "core/io/dir_access.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" -static Map<String, Vector<uint8_t>> *files = nullptr; +static HashMap<String, Vector<uint8_t>> *files = nullptr; void FileAccessMemory::register_file(String p_name, Vector<uint8_t> p_data) { if (!files) { - files = memnew((Map<String, Vector<uint8_t>>)); + files = memnew((HashMap<String, Vector<uint8_t>>)); } String name; @@ -84,11 +84,11 @@ Error FileAccessMemory::_open(const String &p_path, int p_mode_flags) { String name = fix_path(p_path); //name = DirAccess::normalize_path(name); - Map<String, Vector<uint8_t>>::Element *E = files->find(name); + HashMap<String, Vector<uint8_t>>::Iterator E = files->find(name); ERR_FAIL_COND_V_MSG(!E, ERR_FILE_NOT_FOUND, "Can't find file '" + p_path + "'."); - data = E->get().ptrw(); - length = E->get().size(); + data = E->value.ptrw(); + length = E->value.size(); pos = 0; return OK; diff --git a/core/io/file_access_network.h b/core/io/file_access_network.h index 214d391c95..c7431752c0 100644 --- a/core/io/file_access_network.h +++ b/core/io/file_access_network.h @@ -52,7 +52,7 @@ class FileAccessNetworkClient { bool quit = false; Mutex mutex; Mutex blockrequest_mutex; - Map<int, FileAccessNetwork *> accesses; + HashMap<int, FileAccessNetwork *> accesses; Ref<StreamPeerTCP> client; int32_t last_id = 0; int32_t lockcount = 0; diff --git a/core/io/file_access_pack.cpp b/core/io/file_access_pack.cpp index ba120de68b..89efdc4938 100644 --- a/core/io/file_access_pack.cpp +++ b/core/io/file_access_pack.cpp @@ -406,7 +406,7 @@ Error DirAccessPack::list_dir_begin() { list_dirs.push_back(E.key); } - for (Set<String>::Element *E = current->files.front(); E; E = E->next()) { + for (RBSet<String>::Element *E = current->files.front(); E; E = E->next()) { list_files.push_back(E->get()); } diff --git a/core/io/file_access_pack.h b/core/io/file_access_pack.h index 17e87c835a..404ad38c96 100644 --- a/core/io/file_access_pack.h +++ b/core/io/file_access_pack.h @@ -35,8 +35,8 @@ #include "core/io/file_access.h" #include "core/string/print_string.h" #include "core/templates/list.h" -#include "core/templates/map.h" -#include "core/templates/set.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 @@ -72,23 +72,20 @@ private: struct PackedDir { PackedDir *parent = nullptr; String name; - Map<String, PackedDir *> subdirs; - Set<String> files; + HashMap<String, PackedDir *> subdirs; + RBSet<String> files; }; struct PathMD5 { uint64_t a = 0; uint64_t b = 0; - bool operator<(const PathMD5 &p_md5) const { - if (p_md5.a == a) { - return b < p_md5.b; - } else { - return a < p_md5.a; - } - } - bool operator==(const PathMD5 &p_md5) const { - return a == p_md5.a && b == p_md5.b; + bool operator==(const PathMD5 &p_val) const { + return (a == p_val.a) && (b == p_val.b); + } + static uint32_t hash(const PathMD5 &p_val) { + uint32_t h = hash_djb2_one_32(p_val.a); + return hash_djb2_one_32(p_val.b, h); } PathMD5() {} @@ -99,7 +96,7 @@ private: } }; - Map<PathMD5, PackedFile> files; + HashMap<PathMD5, PackedFile, PathMD5> files; Vector<PackSource *> sources; @@ -186,15 +183,15 @@ public: Ref<FileAccess> PackedData::try_open_path(const String &p_path) { PathMD5 pmd5(p_path.md5_buffer()); - Map<PathMD5, PackedFile>::Element *E = files.find(pmd5); + HashMap<PathMD5, PackedFile, PathMD5>::Iterator E = files.find(pmd5); if (!E) { return nullptr; //not found } - if (E->get().offset == 0) { + if (E->value.offset == 0) { return nullptr; //was erased } - return E->get().src->get_file(p_path, &E->get()); + return E->value.src->get_file(p_path, &E->value); } bool PackedData::has_path(const String &p_path) { diff --git a/core/io/file_access_zip.h b/core/io/file_access_zip.h index ae58d99a66..6ea603546a 100644 --- a/core/io/file_access_zip.h +++ b/core/io/file_access_zip.h @@ -34,7 +34,7 @@ #ifdef MINIZIP_ENABLED #include "core/io/file_access_pack.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" #include "thirdparty/minizip/unzip.h" @@ -55,7 +55,7 @@ private: }; Vector<Package> packages; - Map<String, File> files; + HashMap<String, File> files; static ZipArchive *instance; diff --git a/core/io/ip.cpp b/core/io/ip.cpp index 5156a5cb99..25e3bef5fc 100644 --- a/core/io/ip.cpp +++ b/core/io/ip.cpp @@ -267,7 +267,7 @@ Array IP::_get_local_addresses() const { Array IP::_get_local_interfaces() const { Array results; - Map<String, Interface_Info> interfaces; + HashMap<String, Interface_Info> interfaces; get_local_interfaces(&interfaces); for (KeyValue<String, Interface_Info> &E : interfaces) { Interface_Info &c = E.value; @@ -289,7 +289,7 @@ Array IP::_get_local_interfaces() const { } void IP::get_local_addresses(List<IPAddress> *r_addresses) const { - Map<String, Interface_Info> interfaces; + HashMap<String, Interface_Info> interfaces; get_local_interfaces(&interfaces); for (const KeyValue<String, Interface_Info> &E : interfaces) { for (const IPAddress &F : E.value.ip_addresses) { diff --git a/core/io/ip.h b/core/io/ip.h index 06ff8a4d70..4d83515e2b 100644 --- a/core/io/ip.h +++ b/core/io/ip.h @@ -92,7 +92,7 @@ public: virtual void _resolve_hostname(List<IPAddress> &r_addresses, const String &p_hostname, Type p_type = TYPE_ANY) const = 0; Array get_resolve_item_addresses(ResolverID p_id) const; - virtual void get_local_interfaces(Map<String, Interface_Info> *r_interfaces) const = 0; + virtual void get_local_interfaces(HashMap<String, Interface_Info> *r_interfaces) const = 0; void erase_resolve_item(ResolverID p_id); void clear_cache(const String &p_hostname = ""); diff --git a/core/io/json.cpp b/core/io/json.cpp index 4b745dff44..b3a9762e75 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, Set<const void *> &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, RBSet<const void *> &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) { - Set<const void *> markers; + RBSet<const void *> 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 ed251938ec..f883d3963a 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, Set<const void *> &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, RBSet<const void *> &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 c19fc2820b..925bfdbd02 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(); - Set<String> backups; + RBSet<String> 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); @@ -141,7 +141,7 @@ void RotatedFileLogger::clear_old_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 (Set<String>::Element *E = backups.front(); E && to_delete > 0; E = E->next(), --to_delete) { + for (RBSet<String>::Element *E = backups.front(); E && to_delete > 0; E = E->next(), --to_delete) { da->remove(E->get()); } } diff --git a/core/io/packed_data_container.cpp b/core/io/packed_data_container.cpp index 027fdd51aa..a456318148 100644 --- a/core/io/packed_data_container.cpp +++ b/core/io/packed_data_container.cpp @@ -210,7 +210,7 @@ Variant PackedDataContainer::_key_at_ofs(uint32_t p_ofs, const Variant &p_key, b } } -uint32_t PackedDataContainer::_pack(const Variant &p_data, Vector<uint8_t> &tmpdata, Map<String, uint32_t> &string_cache) { +uint32_t PackedDataContainer::_pack(const Variant &p_data, Vector<uint8_t> &tmpdata, HashMap<String, uint32_t> &string_cache) { switch (p_data.get_type()) { case Variant::STRING: { String s = p_data; @@ -321,7 +321,7 @@ uint32_t PackedDataContainer::_pack(const Variant &p_data, Vector<uint8_t> &tmpd Error PackedDataContainer::pack(const Variant &p_data) { Vector<uint8_t> tmpdata; - Map<String, uint32_t> string_cache; + HashMap<String, uint32_t> string_cache; _pack(p_data, tmpdata, string_cache); datalen = tmpdata.size(); data.resize(tmpdata.size()); diff --git a/core/io/packed_data_container.h b/core/io/packed_data_container.h index f042b364ee..73c215aed8 100644 --- a/core/io/packed_data_container.h +++ b/core/io/packed_data_container.h @@ -50,7 +50,7 @@ class PackedDataContainer : public Resource { Vector<uint8_t> data; int datalen = 0; - uint32_t _pack(const Variant &p_data, Vector<uint8_t> &tmpdata, Map<String, uint32_t> &string_cache); + uint32_t _pack(const Variant &p_data, Vector<uint8_t> &tmpdata, HashMap<String, uint32_t> &string_cache); Variant _iter_init_ofs(const Array &p_iter, uint32_t p_offset); Variant _iter_next_ofs(const Array &p_iter, uint32_t p_offset); diff --git a/core/io/resource.cpp b/core/io/resource.cpp index e81382b72e..4a94c17132 100644 --- a/core/io/resource.cpp +++ b/core/io/resource.cpp @@ -193,7 +193,7 @@ void Resource::reload_from_file() { copy_from(s); } -Ref<Resource> Resource::duplicate_for_local_scene(Node *p_for_scene, Map<Ref<Resource>, Ref<Resource>> &remap_cache) { +Ref<Resource> Resource::duplicate_for_local_scene(Node *p_for_scene, HashMap<Ref<Resource>, Ref<Resource>> &remap_cache) { List<PropertyInfo> plist; get_property_list(&plist); @@ -228,7 +228,7 @@ Ref<Resource> Resource::duplicate_for_local_scene(Node *p_for_scene, Map<Ref<Res return r; } -void Resource::configure_for_local_scene(Node *p_for_scene, Map<Ref<Resource>, Ref<Resource>> &remap_cache) { +void Resource::configure_for_local_scene(Node *p_for_scene, HashMap<Ref<Resource>, Ref<Resource>> &remap_cache) { List<PropertyInfo> plist; get_property_list(&plist); @@ -317,7 +317,7 @@ void Resource::unregister_owner(Object *p_owner) { } void Resource::notify_change_to_owners() { - for (Set<ObjectID>::Element *E = owners.front(); E; E = E->next()) { + for (RBSet<ObjectID>::Element *E = owners.front(); E; E = E->next()) { Object *obj = ObjectDB::get_instance(E->get()); ERR_CONTINUE_MSG(!obj, "Object was deleted, while still owning a resource."); //wtf //TODO store string @@ -532,7 +532,7 @@ void ResourceCache::dump(const char *p_file, bool p_short) { #ifdef DEBUG_ENABLED lock.read_lock(); - Map<String, int> type_count; + HashMap<String, int> type_count; Ref<FileAccess> f; if (p_file) { diff --git a/core/io/resource.h b/core/io/resource.h index 43ae104da5..53c828f9cd 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: - Set<ObjectID> owners; + RBSet<ObjectID> owners; friend class ResBase; friend class ResourceCache; @@ -111,8 +111,8 @@ public: String get_scene_unique_id() const; virtual Ref<Resource> duplicate(bool p_subresources = false) const; - Ref<Resource> duplicate_for_local_scene(Node *p_for_scene, Map<Ref<Resource>, Ref<Resource>> &remap_cache); - void configure_for_local_scene(Node *p_for_scene, Map<Ref<Resource>, Ref<Resource>> &remap_cache); + Ref<Resource> duplicate_for_local_scene(Node *p_for_scene, HashMap<Ref<Resource>, Ref<Resource>> &remap_cache); + void configure_for_local_scene(Node *p_for_scene, HashMap<Ref<Resource>, Ref<Resource>> &remap_cache); void set_local_to_scene(bool p_enable); bool is_local_to_scene() const; diff --git a/core/io/resource_format_binary.cpp b/core/io/resource_format_binary.cpp index 3c854bbbe5..cf87869a32 100644 --- a/core/io/resource_format_binary.cpp +++ b/core/io/resource_format_binary.cpp @@ -1130,7 +1130,7 @@ void ResourceFormatLoaderBinary::get_dependencies(const String &p_path, List<Str loader.get_dependencies(f, p_dependencies, p_add_types); } -Error ResourceFormatLoaderBinary::rename_dependencies(const String &p_path, const Map<String, String> &p_map) { +Error ResourceFormatLoaderBinary::rename_dependencies(const String &p_path, const HashMap<String, String> &p_map) { Ref<FileAccess> f = FileAccess::open(p_path, FileAccess::READ); ERR_FAIL_COND_V_MSG(f.is_null(), ERR_CANT_OPEN, "Cannot open file '" + p_path + "'."); @@ -1384,7 +1384,7 @@ void ResourceFormatSaverBinaryInstance::_pad_buffer(Ref<FileAccess> f, int p_byt } } -void ResourceFormatSaverBinaryInstance::write_variant(Ref<FileAccess> f, const Variant &p_property, Map<Ref<Resource>, int> &resource_map, Map<Ref<Resource>, int> &external_resources, Map<StringName, int> &string_map, const PropertyInfo &p_hint) { +void ResourceFormatSaverBinaryInstance::write_variant(Ref<FileAccess> f, const Variant &p_property, HashMap<Ref<Resource>, int> &resource_map, HashMap<Ref<Resource>, int> &external_resources, HashMap<StringName, int> &string_map, const PropertyInfo &p_hint) { switch (p_property.get_type()) { case Variant::NIL: { f->store_32(VARIANT_NIL); @@ -2022,7 +2022,7 @@ Error ResourceFormatSaverBinaryInstance::save(const String &p_path, const Ref<Re // save internal resource table f->store_32(saved_resources.size()); //amount of internal resources Vector<uint64_t> ofs_pos; - Set<String> used_unique_ids; + RBSet<String> used_unique_ids; for (Ref<Resource> &r : saved_resources) { if (r->is_built_in()) { @@ -2036,7 +2036,7 @@ Error ResourceFormatSaverBinaryInstance::save(const String &p_path, const Ref<Re } } - Map<Ref<Resource>, int> resource_map; + HashMap<Ref<Resource>, int> resource_map; int res_index = 0; for (Ref<Resource> &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 92d4e4eeaa..db29909dd5 100644 --- a/core/io/resource_format_binary.h +++ b/core/io/resource_format_binary.h @@ -75,12 +75,12 @@ class ResourceLoaderBinary { }; Vector<IntResource> internal_resources; - Map<String, Ref<Resource>> internal_index_cache; + HashMap<String, Ref<Resource>> internal_index_cache; String get_unicode_string(); void _advance_padding(uint32_t p_len); - Map<String, String> remaps; + HashMap<String, String> remaps; Error error = OK; ResourceFormatLoader::CacheMode cache_mode = ResourceFormatLoader::CACHE_MODE_REUSE; @@ -89,7 +89,7 @@ class ResourceLoaderBinary { Error parse_variant(Variant &r_v); - Map<String, Ref<Resource>> dependency_cache; + HashMap<String, Ref<Resource>> dependency_cache; public: void set_local_path(const String &p_local_path); @@ -97,7 +97,7 @@ public: Error load(); void set_translation_remapped(bool p_remapped); - void set_remaps(const Map<String, String> &p_remaps) { remaps = p_remaps; } + void set_remaps(const HashMap<String, String> &p_remaps) { remaps = p_remaps; } void open(Ref<FileAccess> p_f, bool p_no_resources = false, bool p_keep_uuid_paths = false); String recognize(Ref<FileAccess> p_f); void get_dependencies(Ref<FileAccess> p_f, List<String> *p_dependencies, bool p_add_types); @@ -114,7 +114,7 @@ public: virtual String get_resource_type(const String &p_path) const; virtual ResourceUID::ID get_resource_uid(const String &p_path) const; virtual void get_dependencies(const String &p_path, List<String> *p_dependencies, bool p_add_types = false); - virtual Error rename_dependencies(const String &p_path, const Map<String, String> &p_map); + virtual Error rename_dependencies(const String &p_path, const HashMap<String, String> &p_map); }; class ResourceFormatSaverBinaryInstance { @@ -127,7 +127,7 @@ class ResourceFormatSaverBinaryInstance { bool big_endian; bool takeover_paths; String magic; - Set<Ref<Resource>> resource_set; + RBSet<Ref<Resource>> resource_set; struct NonPersistentKey { //for resource properties generated on the fly Ref<Resource> base; @@ -135,11 +135,11 @@ class ResourceFormatSaverBinaryInstance { bool operator<(const NonPersistentKey &p_key) const { return base == p_key.base ? property < p_key.property : base < p_key.base; } }; - Map<NonPersistentKey, Ref<Resource>> non_persistent_map; - Map<StringName, int> string_map; + RBMap<NonPersistentKey, Ref<Resource>> non_persistent_map; + HashMap<StringName, int> string_map; Vector<StringName> strings; - Map<Ref<Resource>, int> external_resources; + HashMap<Ref<Resource>, int> external_resources; List<Ref<Resource>> saved_resources; struct Property { @@ -168,7 +168,7 @@ public: RESERVED_FIELDS = 11 }; Error save(const String &p_path, const Ref<Resource> &p_resource, uint32_t p_flags = 0); - static void write_variant(Ref<FileAccess> f, const Variant &p_property, Map<Ref<Resource>, int> &resource_map, Map<Ref<Resource>, int> &external_resources, Map<StringName, int> &string_map, const PropertyInfo &p_hint = PropertyInfo()); + static void write_variant(Ref<FileAccess> f, const Variant &p_property, HashMap<Ref<Resource>, int> &resource_map, HashMap<Ref<Resource>, int> &external_resources, HashMap<StringName, int> &string_map, const PropertyInfo &p_hint = PropertyInfo()); }; class ResourceFormatSaverBinary : public ResourceFormatSaver { diff --git a/core/io/resource_importer.cpp b/core/io/resource_importer.cpp index 984cf06d2b..5deee9721b 100644 --- a/core/io/resource_importer.cpp +++ b/core/io/resource_importer.cpp @@ -139,7 +139,7 @@ Ref<Resource> ResourceFormatImporter::load(const String &p_path, const String &p } void ResourceFormatImporter::get_recognized_extensions(List<String> *p_extensions) const { - Set<String> found; + RBSet<String> found; for (int i = 0; i < importers.size(); i++) { List<String> local_exts; @@ -159,7 +159,7 @@ void ResourceFormatImporter::get_recognized_extensions_for_type(const String &p_ return; } - Set<String> found; + RBSet<String> found; for (int i = 0; i < importers.size(); i++) { String res_type = importers[i]->get_resource_type(); diff --git a/core/io/resource_importer.h b/core/io/resource_importer.h index b3d777847b..0c7909df06 100644 --- a/core/io/resource_importer.h +++ b/core/io/resource_importer.h @@ -134,15 +134,15 @@ public: virtual String get_preset_name(int p_idx) const { return String(); } virtual void get_import_options(const String &p_path, List<ImportOption> *r_options, int p_preset = 0) const = 0; - virtual bool get_option_visibility(const String &p_path, const String &p_option, const Map<StringName, Variant> &p_options) const = 0; + virtual bool get_option_visibility(const String &p_path, const String &p_option, const HashMap<StringName, Variant> &p_options) const = 0; virtual String get_option_group_file() const { return String(); } - virtual Error import(const String &p_source_file, const String &p_save_path, const Map<StringName, Variant> &p_options, List<String> *r_platform_variants, List<String> *r_gen_files = nullptr, Variant *r_metadata = nullptr) = 0; + virtual Error import(const String &p_source_file, const String &p_save_path, const HashMap<StringName, Variant> &p_options, List<String> *r_platform_variants, List<String> *r_gen_files = nullptr, Variant *r_metadata = nullptr) = 0; virtual bool can_import_threaded() const { return true; } virtual void import_threaded_begin() {} virtual void import_threaded_end() {} - virtual Error import_group_file(const String &p_group_file, const Map<String, Map<StringName, Variant>> &p_source_file_options, const Map<String, String> &p_base_paths) { return ERR_UNAVAILABLE; } + virtual Error import_group_file(const String &p_group_file, const HashMap<String, HashMap<StringName, Variant>> &p_source_file_options, const HashMap<String, String> &p_base_paths) { return ERR_UNAVAILABLE; } virtual bool are_import_settings_valid(const String &p_path) const { return true; } virtual String get_import_settings_string() const { return String(); } }; diff --git a/core/io/resource_loader.cpp b/core/io/resource_loader.cpp index d125dd4e91..9e6330f34b 100644 --- a/core/io/resource_loader.cpp +++ b/core/io/resource_loader.cpp @@ -154,7 +154,7 @@ void ResourceFormatLoader::get_dependencies(const String &p_path, List<String> * } } -Error ResourceFormatLoader::rename_dependencies(const String &p_path, const Map<String, String> &p_map) { +Error ResourceFormatLoader::rename_dependencies(const String &p_path, const HashMap<String, String> &p_map) { Dictionary deps_dict; for (KeyValue<String, String> E : p_map) { deps_dict[E.key] = E.value; @@ -391,7 +391,7 @@ float ResourceLoader::_dependency_get_progress(const String &p_path) { int dep_count = load_task.sub_tasks.size(); if (dep_count > 0) { float dep_progress = 0; - for (Set<String>::Element *E = load_task.sub_tasks.front(); E; E = E->next()) { + for (RBSet<String>::Element *E = load_task.sub_tasks.front(); E; E = E->next()) { dep_progress += _dependency_get_progress(E->get()); } dep_progress /= float(dep_count); @@ -733,7 +733,7 @@ void ResourceLoader::get_dependencies(const String &p_path, List<String> *p_depe } } -Error ResourceLoader::rename_dependencies(const String &p_path, const Map<String, String> &p_map) { +Error ResourceLoader::rename_dependencies(const String &p_path, const HashMap<String, String> &p_map) { String local_path = _path_remap(_validate_local_path(p_path)); for (int i = 0; i < loader_count; i++) { diff --git a/core/io/resource_loader.h b/core/io/resource_loader.h index ea18ac23fd..e189ad1dff 100644 --- a/core/io/resource_loader.h +++ b/core/io/resource_loader.h @@ -70,7 +70,7 @@ public: virtual String get_resource_type(const String &p_path) const; virtual ResourceUID::ID get_resource_uid(const String &p_path) const; virtual void get_dependencies(const String &p_path, List<String> *p_dependencies, bool p_add_types = false); - virtual Error rename_dependencies(const String &p_path, const Map<String, String> &p_map); + virtual Error rename_dependencies(const String &p_path, const HashMap<String, String> &p_map); virtual bool is_import_valid(const String &p_path) const { return true; } virtual bool is_imported(const String &p_path) const { return false; } virtual int get_import_order(const String &p_path) const { return 0; } @@ -145,7 +145,7 @@ private: bool start_next = true; int requests = 0; int poll_requests = 0; - Set<String> sub_tasks; + RBSet<String> sub_tasks; }; static void _thread_load_function(void *p_userdata); @@ -173,7 +173,7 @@ public: static String get_resource_type(const String &p_path); static ResourceUID::ID get_resource_uid(const String &p_path); static void get_dependencies(const String &p_path, List<String> *p_dependencies, bool p_add_types = false); - static Error rename_dependencies(const String &p_path, const Map<String, String> &p_map); + static Error rename_dependencies(const String &p_path, const HashMap<String, String> &p_map); static bool is_import_valid(const String &p_path); static String get_import_group_file(const String &p_path); static bool is_imported(const String &p_path); diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp index 284b4294ea..a3ee259030 100644 --- a/core/math/a_star.cpp +++ b/core/math/a_star.cpp @@ -151,7 +151,7 @@ void AStar3D::connect_points(int p_id, int p_with_id, bool bidirectional) { s.direction = Segment::BIDIRECTIONAL; } - Set<Segment>::Element *element = segments.find(s); + RBSet<Segment>::Element *element = segments.find(s); if (element != nullptr) { s.direction |= element->get().direction; if (s.direction == Segment::BIDIRECTIONAL) { @@ -177,7 +177,7 @@ 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; - Set<Segment>::Element *element = segments.find(s); + RBSet<Segment>::Element *element = segments.find(s); if (element != nullptr) { // s is the new segment // Erase the directions to be removed @@ -235,7 +235,7 @@ 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 Set<Segment>::Element *element = segments.find(s); + const RBSet<Segment>::Element *element = segments.find(s); return element != nullptr && (bidirectional || (element->get().direction & s.direction) == s.direction); @@ -293,7 +293,7 @@ Vector3 AStar3D::get_closest_position_in_segment(const Vector3 &p_point) const { real_t closest_dist = 1e20; Vector3 closest_point; - for (const Set<Segment>::Element *E = segments.front(); E; E = E->next()) { + for (const RBSet<Segment>::Element *E = segments.front(); E; E = E->next()) { Point *from_point = nullptr, *to_point = nullptr; points.lookup(E->get().u, from_point); points.lookup(E->get().v, to_point); diff --git a/core/math/a_star.h b/core/math/a_star.h index bb7112fb09..086be839b5 100644 --- a/core/math/a_star.h +++ b/core/math/a_star.h @@ -112,7 +112,7 @@ class AStar3D : public RefCounted { uint64_t pass = 1; OAHashMap<int, Point *> points; - Set<Segment> segments; + RBSet<Segment> segments; bool _solve(Point *begin_point, Point *end_point); diff --git a/core/math/color.cpp b/core/math/color.cpp index e32f9147d9..74552a2894 100644 --- a/core/math/color.cpp +++ b/core/math/color.cpp @@ -33,7 +33,7 @@ #include "color_names.inc" #include "core/math/math_funcs.h" #include "core/string/print_string.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" uint32_t Color::to_argb32() const { uint32_t c = (uint8_t)Math::round(a * 255); diff --git a/core/math/disjoint_set.h b/core/math/disjoint_set.h index 8657dc068e..d07c08e45e 100644 --- a/core/math/disjoint_set.h +++ b/core/math/disjoint_set.h @@ -31,11 +31,11 @@ #ifndef DISJOINT_SET_H #define DISJOINT_SET_H -#include "core/templates/map.h" +#include "core/templates/rb_map.h" #include "core/templates/vector.h" /* This DisjointSet class uses Find with path compression and Union by rank */ -template <typename T, class C = Comparator<T>, class AL = DefaultAllocator> +template <typename T, class H = HashMapHasherDefault, class C = HashMapComparatorDefault<T>, class AL = DefaultAllocator> class DisjointSet { struct Element { T object; @@ -43,7 +43,7 @@ class DisjointSet { int rank = 0; }; - typedef Map<T, Element *, C, AL> MapT; + typedef HashMap<T, Element *, H, C> MapT; MapT elements; @@ -65,15 +65,15 @@ public: /* FUNCTIONS */ -template <typename T, class C, class AL> -DisjointSet<T, C, AL>::~DisjointSet() { - for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) { - memdelete_allocator<Element, AL>(itr->value()); +template <typename T, class H, class C, class AL> +DisjointSet<T, H, C, AL>::~DisjointSet() { + for (KeyValue<T, Element *> &E : elements) { + memdelete_allocator<Element, AL>(E.value); } } -template <typename T, class C, class AL> -typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::get_parent(Element *element) { +template <typename T, class H, class C, class AL> +typename DisjointSet<T, H, C, AL>::Element *DisjointSet<T, H, C, AL>::get_parent(Element *element) { if (element->parent != element) { element->parent = get_parent(element->parent); } @@ -81,11 +81,11 @@ typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::get_parent(Eleme return element->parent; } -template <typename T, class C, class AL> -typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::insert_or_get(T object) { - typename MapT::Element *itr = elements.find(object); +template <typename T, class H, class C, class AL> +typename DisjointSet<T, H, C, AL>::Element *DisjointSet<T, H, C, AL>::insert_or_get(T object) { + typename MapT::Iterator itr = elements.find(object); if (itr != nullptr) { - return itr->value(); + return itr->value; } Element *new_element = memnew_allocator(Element, AL); @@ -96,8 +96,8 @@ typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::insert_or_get(T return new_element; } -template <typename T, class C, class AL> -void DisjointSet<T, C, AL>::create_union(T a, T b) { +template <typename T, class H, class C, class AL> +void DisjointSet<T, H, C, AL>::create_union(T a, T b) { Element *x = insert_or_get(a); Element *y = insert_or_get(b); @@ -121,28 +121,28 @@ void DisjointSet<T, C, AL>::create_union(T a, T b) { } } -template <typename T, class C, class AL> -void DisjointSet<T, C, AL>::get_representatives(Vector<T> &out_representatives) { - for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) { - Element *element = itr->value(); +template <typename T, class H, class C, class AL> +void DisjointSet<T, H, C, AL>::get_representatives(Vector<T> &out_representatives) { + for (KeyValue<T, Element *> &E : elements) { + Element *element = E.value; if (element->parent == element) { out_representatives.push_back(element->object); } } } -template <typename T, class C, class AL> -void DisjointSet<T, C, AL>::get_members(Vector<T> &out_members, T representative) { - typename MapT::Element *rep_itr = elements.find(representative); +template <typename T, class H, class C, class AL> +void DisjointSet<T, H, C, AL>::get_members(Vector<T> &out_members, T representative) { + typename MapT::Iterator rep_itr = elements.find(representative); ERR_FAIL_COND(rep_itr == nullptr); - Element *rep_element = rep_itr->value(); + Element *rep_element = rep_itr->value; ERR_FAIL_COND(rep_element->parent != rep_element); - for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) { - Element *parent = get_parent(itr->value()); + for (KeyValue<T, Element *> &E : elements) { + Element *parent = get_parent(E.value); if (parent == rep_element) { - out_members.push_back(itr->key()); + out_members.push_back(E.key); } } } diff --git a/core/math/geometry_3d.cpp b/core/math/geometry_3d.cpp index f76de079e4..ec96753c79 100644 --- a/core/math/geometry_3d.cpp +++ b/core/math/geometry_3d.cpp @@ -36,7 +36,7 @@ #include "thirdparty/misc/polypartition.h" void Geometry3D::MeshData::optimize_vertices() { - Map<int, int> vtx_remap; + HashMap<int, int> vtx_remap; for (int i = 0; i < faces.size(); i++) { for (int j = 0; j < faces[i].indices.size(); j++) { diff --git a/core/math/octree.h b/core/math/octree.h index 65ab9e2292..8dd103f109 100644 --- a/core/math/octree.h +++ b/core/math/octree.h @@ -36,7 +36,7 @@ #include "core/math/vector3.h" #include "core/string/print_string.h" #include "core/templates/list.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" #include "core/variant/variant.h" typedef uint32_t OctreeElementID; @@ -151,8 +151,8 @@ private: typename List<PairData *, AL>::Element *eA, *eB; }; - typedef Map<OctreeElementID, Element, Comparator<OctreeElementID>, AL> ElementMap; - typedef Map<PairKey, PairData, Comparator<PairKey>, AL> PairMap; + typedef HashMap<OctreeElementID, Element, Comparator<OctreeElementID>, AL> ElementMap; + typedef HashMap<PairKey, PairData, Comparator<PairKey>, AL> PairMap; ElementMap element_map; PairMap pair_map; diff --git a/core/math/quick_hull.cpp b/core/math/quick_hull.cpp index 3614bfadf8..43744deeb0 100644 --- a/core/math/quick_hull.cpp +++ b/core/math/quick_hull.cpp @@ -30,7 +30,7 @@ #include "quick_hull.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" uint32_t QuickHull::debug_stop_after = 0xFFFFFFFF; @@ -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()); - Set<Vector3> valid_cache; + RBSet<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)); @@ -237,7 +237,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ //find lit faces and lit edges List<List<Face>::Element *> lit_faces; //lit face is a death sentence - Map<Edge, FaceConnect> lit_edges; //create this on the flight, should not be that bad for performance and simplifies code a lot + HashMap<Edge, FaceConnect, Edge> lit_edges; //create this on the flight, should not be that bad for performance and simplifies code a lot for (List<Face>::Element *E = faces.front(); E; E = E->next()) { if (E->get().plane.distance_to(v) > 0) { @@ -248,15 +248,15 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ uint32_t b = E->get().vertices[(i + 1) % 3]; Edge e(a, b); - Map<Edge, FaceConnect>::Element *F = lit_edges.find(e); + HashMap<Edge, FaceConnect, Edge>::Iterator F = lit_edges.find(e); if (!F) { F = lit_edges.insert(e, FaceConnect()); } if (e.vertices[0] == a) { //left - F->get().left = E; + F->value.left = E; } else { - F->get().right = E; + F->value.right = E; } } } @@ -333,7 +333,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ /* CREATE MESHDATA */ //make a map of edges again - Map<Edge, RetFaceConnect> ret_edges; + HashMap<Edge, RetFaceConnect, Edge> ret_edges; List<Geometry3D::MeshData::Face> ret_faces; for (const Face &E : faces) { @@ -351,15 +351,15 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ uint32_t b = E.vertices[(i + 1) % 3]; Edge e(a, b); - Map<Edge, RetFaceConnect>::Element *G = ret_edges.find(e); + HashMap<Edge, RetFaceConnect, Edge>::Iterator G = ret_edges.find(e); if (!G) { G = ret_edges.insert(e, RetFaceConnect()); } if (e.vertices[0] == a) { //left - G->get().left = F; + G->value.left = F; } else { - G->get().right = F; + G->value.right = F; } } } @@ -374,10 +374,10 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ int b = E->get().indices[(i + 1) % f.indices.size()]; Edge e(a, b); - Map<Edge, RetFaceConnect>::Element *F = ret_edges.find(e); + HashMap<Edge, RetFaceConnect, Edge>::Iterator F = ret_edges.find(e); ERR_CONTINUE(!F); - List<Geometry3D::MeshData::Face>::Element *O = F->get().left == E ? F->get().right : F->get().left; + List<Geometry3D::MeshData::Face>::Element *O = F->value.left == E ? F->value.right : F->value.left; ERR_CONTINUE(O == E); ERR_CONTINUE(O == nullptr); @@ -401,13 +401,13 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ } Edge e2(idx, idxn); - Map<Edge, RetFaceConnect>::Element *F2 = ret_edges.find(e2); + HashMap<Edge, RetFaceConnect, Edge>::Iterator F2 = ret_edges.find(e2); ERR_CONTINUE(!F2); //change faceconnect, point to this face instead - if (F2->get().left == O) { - F2->get().left = E; - } else if (F2->get().right == O) { - F2->get().right = E; + if (F2->value.left == O) { + F2->value.left = E; + } else if (F2->value.right == O) { + F2->value.right = E; } } @@ -426,7 +426,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ } } - ret_edges.erase(F); //remove the edge + ret_edges.remove(F); //remove the edge ret_faces.erase(O); //remove the face } } diff --git a/core/math/quick_hull.h b/core/math/quick_hull.h index b8d813c979..1c354880b4 100644 --- a/core/math/quick_hull.h +++ b/core/math/quick_hull.h @@ -34,7 +34,7 @@ #include "core/math/aabb.h" #include "core/math/geometry_3d.h" #include "core/templates/list.h" -#include "core/templates/set.h" +#include "core/templates/rb_set.h" class QuickHull { public: @@ -44,9 +44,16 @@ public: uint64_t id = 0; }; + static uint32_t hash(const Edge &p_edge) { + return hash_one_uint64(p_edge.id); + } + bool operator<(const Edge &p_edge) const { return id < p_edge.id; } + bool operator==(const Edge &p_edge) const { + return id == p_edge.id; + } Edge(int p_vtx_a = 0, int p_vtx_b = 0) { if (p_vtx_a > p_vtx_b) { diff --git a/core/math/static_raycaster.h b/core/math/static_raycaster.h index 33254399c7..adc81906d7 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 Set<int> &p_mesh_ids) = 0; + virtual void set_mesh_filter(const RBSet<int> &p_mesh_ids) = 0; virtual void clear_mesh_filter() = 0; static Ref<StaticRaycaster> create(); diff --git a/core/math/triangle_mesh.cpp b/core/math/triangle_mesh.cpp index e146c4a4e3..54461bf70f 100644 --- a/core/math/triangle_mesh.cpp +++ b/core/math/triangle_mesh.cpp @@ -122,7 +122,7 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) { const Vector3 *r = p_faces.ptr(); Triangle *w = triangles.ptrw(); - Map<Vector3, int> db; + HashMap<Vector3, int> db; for (int i = 0; i < fc; i++) { Triangle &f = w[i]; @@ -131,9 +131,9 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) { for (int j = 0; j < 3; j++) { int vidx = -1; Vector3 vs = v[j].snapped(Vector3(0.0001, 0.0001, 0.0001)); - Map<Vector3, int>::Element *E = db.find(vs); + HashMap<Vector3, int>::Iterator E = db.find(vs); if (E) { - vidx = E->get(); + vidx = E->value; } else { vidx = db.size(); db[vs] = vidx; diff --git a/core/multiplayer/multiplayer_api.cpp b/core/multiplayer/multiplayer_api.cpp index 3533acd103..e18c3dd2e4 100644 --- a/core/multiplayer/multiplayer_api.cpp +++ b/core/multiplayer/multiplayer_api.cpp @@ -494,7 +494,7 @@ Vector<int> MultiplayerAPI::get_peer_ids() const { ERR_FAIL_COND_V_MSG(!multiplayer_peer.is_valid(), Vector<int>(), "No multiplayer peer is assigned. Assume no peers are connected."); Vector<int> ret; - for (Set<int>::Element *E = connected_peers.front(); E; E = E->next()) { + for (RBSet<int>::Element *E = connected_peers.front(); E; E = E->next()) { ret.push_back(E->get()); } diff --git a/core/multiplayer/multiplayer_api.h b/core/multiplayer/multiplayer_api.h index 9fe67615e3..b93f2acbd3 100644 --- a/core/multiplayer/multiplayer_api.h +++ b/core/multiplayer/multiplayer_api.h @@ -113,7 +113,7 @@ public: private: Ref<MultiplayerPeer> multiplayer_peer; - Set<int> connected_peers; + RBSet<int> 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<int> get_peer_ids() const; - const Set<int> get_connected_peers() const { return connected_peers; } + const RBSet<int> 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 d0fcde832b..d19cbf2642 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<String> *p } HashMap<StringName, HashMap<StringName, Variant>> ClassDB::default_values; -Set<StringName> ClassDB::default_values_cached; +RBSet<StringName> 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)) { @@ -1492,7 +1492,7 @@ void ClassDB::unregister_extension_class(const StringName &p_class) { classes.erase(p_class); } -Map<StringName, ClassDB::NativeStruct> ClassDB::native_structs; +HashMap<StringName, ClassDB::NativeStruct> ClassDB::native_structs; void ClassDB::register_native_struct(const StringName &p_name, const String &p_code, uint64_t p_current_size) { NativeStruct ns; ns.ccode = p_code; diff --git a/core/object/class_db.h b/core/object/class_db.h index d4e1fc4e76..67b71ab058 100644 --- a/core/object/class_db.h +++ b/core/object/class_db.h @@ -110,10 +110,10 @@ public: #ifdef DEBUG_METHODS_ENABLED List<StringName> constant_order; List<StringName> method_order; - Set<StringName> methods_in_properties; + RBSet<StringName> methods_in_properties; List<MethodInfo> virtual_methods; - Map<StringName, MethodInfo> virtual_methods_map; - Map<StringName, Vector<Error>> method_error_values; + HashMap<StringName, MethodInfo> virtual_methods_map; + HashMap<StringName, Vector<Error>> method_error_values; #endif HashMap<StringName, PropertySetGet> property_setget; @@ -149,14 +149,14 @@ public: static void _add_class2(const StringName &p_class, const StringName &p_inherits); static HashMap<StringName, HashMap<StringName, Variant>> default_values; - static Set<StringName> default_values_cached; + static RBSet<StringName> default_values_cached; // Native structs, used by binder struct NativeStruct { String ccode; // C code to create the native struct, fields separated by ; Arrays accepted (even containing other structs), also function pointers. All types must be Godot types. uint64_t struct_size; // local size of struct, for comparison }; - static Map<StringName, NativeStruct> native_structs; + static HashMap<StringName, NativeStruct> native_structs; private: // Non-locking variants of get_parent_class and is_parent_class. diff --git a/core/object/message_queue.cpp b/core/object/message_queue.cpp index 79c36ac81f..fa1945cf79 100644 --- a/core/object/message_queue.cpp +++ b/core/object/message_queue.cpp @@ -142,9 +142,9 @@ Error MessageQueue::push_callablep(const Callable &p_callable, const Variant **p } void MessageQueue::statistics() { - Map<StringName, int> set_count; - Map<int, int> notify_count; - Map<Callable, int> call_count; + HashMap<StringName, int> set_count; + HashMap<int, int> notify_count; + HashMap<Callable, int> call_count; int null_count = 0; uint32_t read_pos = 0; diff --git a/core/object/object.cpp b/core/object/object.cpp index 797eecd312..0912ea55f0 100644 --- a/core/object/object.cpp +++ b/core/object/object.cpp @@ -1382,8 +1382,6 @@ bool Object::is_connected(const StringName &p_signal, const Callable &p_callable Callable target = p_callable; return s->slot_map.has(*target.get_base_comparator()); - //const Map<Signal::Target,Signal::Slot>::Element *E = s->slot_map.find(target); - //return (E!=nullptr ); } void Object::disconnect(const StringName &p_signal, const Callable &p_callable) { diff --git a/core/object/object.h b/core/object/object.h index 00cb73593b..ca7b9965f1 100644 --- a/core/object/object.h +++ b/core/object/object.h @@ -38,9 +38,9 @@ #include "core/os/spin_lock.h" #include "core/templates/hash_map.h" #include "core/templates/list.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" +#include "core/templates/rb_set.h" #include "core/templates/safe_refcount.h" -#include "core/templates/set.h" #include "core/templates/vmap.h" #include "core/variant/callable_bind.h" #include "core/variant/variant.h" @@ -510,7 +510,7 @@ private: #ifdef TOOLS_ENABLED bool _edited = false; uint32_t _edited_version = 0; - Set<String> editor_section_folding; + RBSet<String> 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 Set<String> &editor_get_section_folding() const { return editor_section_folding; } + const RBSet<String> &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 c1036e3413..1546d52fd2 100644 --- a/core/object/script_language.cpp +++ b/core/object/script_language.cpp @@ -93,7 +93,7 @@ Array Script::_get_script_signal_list() { Dictionary Script::_get_script_constant_map() { Dictionary ret; - Map<StringName, Variant> map; + HashMap<StringName, Variant> map; get_constants(&map); for (const KeyValue<StringName, Variant> &E : map) { ret[E.key] = E.value; @@ -474,8 +474,8 @@ bool PlaceHolderScriptInstance::has_method(const StringName &p_method) const { return false; } -void PlaceHolderScriptInstance::update(const List<PropertyInfo> &p_properties, const Map<StringName, Variant> &p_values) { - Set<StringName> new_values; +void PlaceHolderScriptInstance::update(const List<PropertyInfo> &p_properties, const HashMap<StringName, Variant> &p_values) { + RBSet<StringName> new_values; for (const PropertyInfo &E : p_properties) { StringName n = E.name; new_values.insert(n); @@ -490,16 +490,16 @@ void PlaceHolderScriptInstance::update(const List<PropertyInfo> &p_properties, c properties = p_properties; List<StringName> to_remove; - for (Map<StringName, Variant>::Element *E = values.front(); E; E = E->next()) { - if (!new_values.has(E->key())) { - to_remove.push_back(E->key()); + for (KeyValue<StringName, Variant> &E : values) { + if (!new_values.has(E.key)) { + to_remove.push_back(E.key); } Variant defval; - if (script->get_property_default_value(E->key(), defval)) { + if (script->get_property_default_value(E.key, defval)) { //remove because it's the same as the default value - if (defval == E->get()) { - to_remove.push_back(E->key()); + if (defval == E.value) { + to_remove.push_back(E.key); } } } @@ -520,10 +520,10 @@ void PlaceHolderScriptInstance::update(const List<PropertyInfo> &p_properties, c void PlaceHolderScriptInstance::property_set_fallback(const StringName &p_name, const Variant &p_value, bool *r_valid) { if (script->is_placeholder_fallback_enabled()) { - Map<StringName, Variant>::Element *E = values.find(p_name); + HashMap<StringName, Variant>::Iterator E = values.find(p_name); if (E) { - E->value() = p_value; + E->value = p_value; } else { values.insert(p_name, p_value); } @@ -547,13 +547,13 @@ void PlaceHolderScriptInstance::property_set_fallback(const StringName &p_name, Variant PlaceHolderScriptInstance::property_get_fallback(const StringName &p_name, bool *r_valid) { if (script->is_placeholder_fallback_enabled()) { - const Map<StringName, Variant>::Element *E = values.find(p_name); + HashMap<StringName, Variant>::ConstIterator E = values.find(p_name); if (E) { if (r_valid) { *r_valid = true; } - return E->value(); + return E->value; } E = constants.find(p_name); @@ -561,7 +561,7 @@ Variant PlaceHolderScriptInstance::property_get_fallback(const StringName &p_nam if (r_valid) { *r_valid = true; } - return E->value(); + return E->value; } } diff --git a/core/object/script_language.h b/core/object/script_language.h index bd87427eaf..b1481a372e 100644 --- a/core/object/script_language.h +++ b/core/object/script_language.h @@ -34,8 +34,8 @@ #include "core/doc_data.h" #include "core/io/resource.h" #include "core/multiplayer/multiplayer.h" -#include "core/templates/map.h" #include "core/templates/pair.h" +#include "core/templates/rb_map.h" class ScriptLanguage; @@ -154,8 +154,8 @@ public: virtual int get_member_line(const StringName &p_member) const { return -1; } - virtual void get_constants(Map<StringName, Variant> *p_constants) {} - virtual void get_members(Set<StringName> *p_constants) {} + virtual void get_constants(HashMap<StringName, Variant> *p_constants) {} + virtual void get_members(RBSet<StringName> *p_constants) {} virtual bool is_placeholder_fallback_enabled() const { return false; } @@ -283,7 +283,7 @@ public: virtual Ref<Script> make_template(const String &p_template, const String &p_class_name, const String &p_base_class_name) const { return Ref<Script>(); } virtual Vector<ScriptTemplate> get_built_in_templates(StringName p_object) { return Vector<ScriptTemplate>(); } virtual bool is_using_templates() { return false; } - virtual bool validate(const String &p_script, const String &p_path = "", List<String> *r_functions = nullptr, List<ScriptError> *r_errors = nullptr, List<Warning> *r_warnings = nullptr, Set<int> *r_safe_lines = nullptr) const = 0; + virtual bool validate(const String &p_script, const String &p_path = "", List<String> *r_functions = nullptr, List<ScriptError> *r_errors = nullptr, List<Warning> *r_warnings = nullptr, RBSet<int> *r_safe_lines = nullptr) const = 0; virtual String validate_path(const String &p_path) const { return ""; } virtual Script *create_script() const = 0; virtual bool has_named_classes() const = 0; @@ -433,8 +433,8 @@ extern uint8_t script_encryption_key[32]; class PlaceHolderScriptInstance : public ScriptInstance { Object *owner = nullptr; List<PropertyInfo> properties; - Map<StringName, Variant> values; - Map<StringName, Variant> constants; + HashMap<StringName, Variant> values; + HashMap<StringName, Variant> constants; ScriptLanguage *language = nullptr; Ref<Script> script; @@ -459,7 +459,7 @@ public: Object *get_owner() override { return owner; } - void update(const List<PropertyInfo> &p_properties, const Map<StringName, Variant> &p_values); //likely changed in editor + void update(const List<PropertyInfo> &p_properties, const HashMap<StringName, Variant> &p_values); //likely changed in editor virtual bool is_placeholder() const override { return true; } diff --git a/core/object/script_language_extension.h b/core/object/script_language_extension.h index 40f18ab30d..5ffa6c5a70 100644 --- a/core/object/script_language_extension.h +++ b/core/object/script_language_extension.h @@ -153,7 +153,7 @@ public: GDVIRTUAL0RC(Dictionary, _get_constants) - virtual void get_constants(Map<StringName, Variant> *p_constants) override { + virtual void get_constants(HashMap<StringName, Variant> *p_constants) override { Dictionary constants; GDVIRTUAL_REQUIRED_CALL(_get_constants, constants); List<Variant> keys; @@ -163,7 +163,7 @@ public: } } GDVIRTUAL0RC(TypedArray<StringName>, _get_members) - virtual void get_members(Set<StringName> *p_members) override { + virtual void get_members(RBSet<StringName> *p_members) override { TypedArray<StringName> members; GDVIRTUAL_REQUIRED_CALL(_get_members, members); for (int i = 0; i < members.size(); i++) { @@ -282,7 +282,7 @@ public: EXBIND0R(bool, is_using_templates) GDVIRTUAL6RC(Dictionary, _validate, const String &, const String &, bool, bool, bool, bool) - virtual bool validate(const String &p_script, const String &p_path = "", List<String> *r_functions = nullptr, List<ScriptError> *r_errors = nullptr, List<Warning> *r_warnings = nullptr, Set<int> *r_safe_lines = nullptr) const override { + virtual bool validate(const String &p_script, const String &p_path = "", List<String> *r_functions = nullptr, List<ScriptError> *r_errors = nullptr, List<Warning> *r_warnings = nullptr, RBSet<int> *r_safe_lines = nullptr) const override { Dictionary ret; GDVIRTUAL_REQUIRED_CALL(_validate, p_script, p_path, r_functions != nullptr, r_errors != nullptr, r_warnings != nullptr, r_safe_lines != nullptr, ret); if (!ret.has("valid")) { diff --git a/core/string/optimized_translation.cpp b/core/string/optimized_translation.cpp index 93429744fc..07302cc8c3 100644 --- a/core/string/optimized_translation.cpp +++ b/core/string/optimized_translation.cpp @@ -53,7 +53,7 @@ void OptimizedTranslation::generate(const Ref<Translation> &p_from) { int size = Math::larger_prime(keys.size()); Vector<Vector<Pair<int, CharString>>> buckets; - Vector<Map<uint32_t, int>> table; + Vector<HashMap<uint32_t, int>> table; Vector<uint32_t> hfunc_table; Vector<CompressedString> compressed; @@ -108,7 +108,7 @@ void OptimizedTranslation::generate(const Ref<Translation> &p_from) { for (int i = 0; i < size; i++) { const Vector<Pair<int, CharString>> &b = buckets[i]; - Map<uint32_t, int> &t = table.write[i]; + HashMap<uint32_t, int> &t = table.write[i]; if (b.size() == 0) { continue; @@ -147,7 +147,7 @@ void OptimizedTranslation::generate(const Ref<Translation> &p_from) { int btindex = 0; for (int i = 0; i < size; i++) { - const Map<uint32_t, int> &t = table[i]; + const HashMap<uint32_t, int> &t = table[i]; if (t.size() == 0) { htw[i] = 0xFFFFFFFF; //nothing continue; diff --git a/core/string/translation.cpp b/core/string/translation.cpp index d6d361b5f1..c64f815563 100644 --- a/core/string/translation.cpp +++ b/core/string/translation.cpp @@ -95,12 +95,12 @@ StringName Translation::get_message(const StringName &p_src_text, const StringNa WARN_PRINT("Translation class doesn't handle context. Using context in get_message() on a Translation instance is probably a mistake. \nUse a derived Translation class that handles context, such as TranslationPO class"); } - const Map<StringName, StringName>::Element *E = translation_map.find(p_src_text); + HashMap<StringName, StringName>::ConstIterator E = translation_map.find(p_src_text); if (!E) { return StringName(); } - return E->get(); + return E->value; } StringName Translation::get_plural_message(const StringName &p_src_text, const StringName &p_plural_text, int p_n, const StringName &p_context) const { @@ -215,12 +215,12 @@ static _character_accent_pair _character_to_accented[] = { Vector<TranslationServer::LocaleScriptInfo> TranslationServer::locale_script_info; -Map<String, String> TranslationServer::language_map; -Map<String, String> TranslationServer::script_map; -Map<String, String> TranslationServer::locale_rename_map; -Map<String, String> TranslationServer::country_name_map; -Map<String, String> TranslationServer::variant_map; -Map<String, String> TranslationServer::country_rename_map; +HashMap<String, String> TranslationServer::language_map; +HashMap<String, String> TranslationServer::script_map; +HashMap<String, String> TranslationServer::locale_rename_map; +HashMap<String, String> TranslationServer::country_name_map; +HashMap<String, String> TranslationServer::variant_map; +HashMap<String, String> TranslationServer::country_rename_map; void TranslationServer::init_locale_info() { // Init locale info. @@ -452,8 +452,8 @@ String TranslationServer::get_locale_name(const String &p_locale) const { Vector<String> TranslationServer::get_all_languages() const { Vector<String> languages; - for (const Map<String, String>::Element *E = language_map.front(); E; E = E->next()) { - languages.push_back(E->key()); + for (const KeyValue<String, String> &E : language_map) { + languages.push_back(E.key); } return languages; @@ -466,8 +466,8 @@ String TranslationServer::get_language_name(const String &p_language) const { Vector<String> TranslationServer::get_all_scripts() const { Vector<String> scripts; - for (const Map<String, String>::Element *E = script_map.front(); E; E = E->next()) { - scripts.push_back(E->key()); + for (const KeyValue<String, String> &E : script_map) { + scripts.push_back(E.key); } return scripts; @@ -480,8 +480,8 @@ String TranslationServer::get_script_name(const String &p_script) const { Vector<String> TranslationServer::get_all_countries() const { Vector<String> countries; - for (const Map<String, String>::Element *E = country_name_map.front(); E; E = E->next()) { - countries.push_back(E->key()); + for (const KeyValue<String, String> &E : country_name_map) { + countries.push_back(E.key); } return countries; @@ -507,7 +507,7 @@ String TranslationServer::get_locale() const { Array TranslationServer::get_loaded_locales() const { Array locales; - for (const Set<Ref<Translation>>::Element *E = translations.front(); E; E = E->next()) { + for (const RBSet<Ref<Translation>>::Element *E = translations.front(); E; E = E->next()) { const Ref<Translation> &t = E->get(); ERR_FAIL_COND_V(t.is_null(), Array()); String l = t->get_locale(); @@ -530,7 +530,7 @@ Ref<Translation> TranslationServer::get_translation_object(const String &p_local Ref<Translation> res; int best_score = 0; - for (const Set<Ref<Translation>>::Element *E = translations.front(); E; E = E->next()) { + for (const RBSet<Ref<Translation>>::Element *E = translations.front(); E; E = E->next()) { const Ref<Translation> &t = E->get(); ERR_FAIL_COND_V(t.is_null(), nullptr); String l = t->get_locale(); @@ -599,7 +599,7 @@ StringName TranslationServer::_get_message_from_translations(const StringName &p StringName res; int best_score = 0; - for (const Set<Ref<Translation>>::Element *E = translations.front(); E; E = E->next()) { + for (const RBSet<Ref<Translation>>::Element *E = translations.front(); E; E = E->next()) { const Ref<Translation> &t = E->get(); ERR_FAIL_COND_V(t.is_null(), p_message); String l = t->get_locale(); diff --git a/core/string/translation.h b/core/string/translation.h index ded6ed5925..f58f6f91a2 100644 --- a/core/string/translation.h +++ b/core/string/translation.h @@ -41,7 +41,7 @@ class Translation : public Resource { RES_BASE_EXTENSION("translation"); String locale = "en"; - Map<StringName, StringName> translation_map; + HashMap<StringName, StringName> translation_map; virtual Vector<String> _get_message_list() const; virtual Dictionary _get_messages() const; @@ -74,7 +74,7 @@ class TranslationServer : public Object { String locale = "en"; String fallback; - Set<Ref<Translation>> translations; + RBSet<Ref<Translation>> translations; Ref<Translation> tool_translation; Ref<Translation> doc_translation; @@ -111,16 +111,16 @@ class TranslationServer : public Object { String name; String script; String default_country; - Set<String> supported_countries; + RBSet<String> supported_countries; }; static Vector<LocaleScriptInfo> locale_script_info; - static Map<String, String> language_map; - static Map<String, String> script_map; - static Map<String, String> locale_rename_map; - static Map<String, String> country_name_map; - static Map<String, String> country_rename_map; - static Map<String, String> variant_map; + static HashMap<String, String> language_map; + static HashMap<String, String> script_map; + static HashMap<String, String> locale_rename_map; + static HashMap<String, String> country_name_map; + static HashMap<String, String> country_rename_map; + static HashMap<String, String> variant_map; void init_locale_info(); diff --git a/core/templates/hash_map.h b/core/templates/hash_map.h index 55292d3eb5..e5f73171a2 100644 --- a/core/templates/hash_map.h +++ b/core/templates/hash_map.h @@ -373,76 +373,80 @@ public: /** Iterator API **/ - struct Iterator { - _FORCE_INLINE_ KeyValue<TKey, TValue> &operator*() const { + struct ConstIterator { + _FORCE_INLINE_ const KeyValue<TKey, TValue> &operator*() const { return E->data; } - _FORCE_INLINE_ KeyValue<TKey, TValue> *operator->() const { return &E->data; } - _FORCE_INLINE_ Iterator &operator++() { + _FORCE_INLINE_ const KeyValue<TKey, TValue> *operator->() const { return &E->data; } + _FORCE_INLINE_ ConstIterator &operator++() { if (E) { E = E->next; } return *this; } - _FORCE_INLINE_ Iterator &operator--() { + _FORCE_INLINE_ ConstIterator &operator--() { if (E) { E = E->prev; } return *this; } - _FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; } - _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; } + _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; } + _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; } - _FORCE_INLINE_ operator bool() const { + _FORCE_INLINE_ explicit operator bool() const { return E != nullptr; } - _FORCE_INLINE_ Iterator(HashMapElement<TKey, TValue> *p_E) { E = p_E; } - _FORCE_INLINE_ Iterator() {} - _FORCE_INLINE_ Iterator(const Iterator &p_it) { E = p_it.E; } - _FORCE_INLINE_ void operator=(const Iterator &p_it) { + _FORCE_INLINE_ ConstIterator(const HashMapElement<TKey, TValue> *p_E) { E = p_E; } + _FORCE_INLINE_ ConstIterator() {} + _FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; } + _FORCE_INLINE_ void operator=(const ConstIterator &p_it) { E = p_it.E; } private: - HashMapElement<TKey, TValue> *E = nullptr; + const HashMapElement<TKey, TValue> *E = nullptr; }; - struct ConstIterator { - _FORCE_INLINE_ const KeyValue<TKey, TValue> &operator*() const { + struct Iterator { + _FORCE_INLINE_ KeyValue<TKey, TValue> &operator*() const { return E->data; } - _FORCE_INLINE_ const KeyValue<TKey, TValue> *operator->() const { return &E->data; } - _FORCE_INLINE_ ConstIterator &operator++() { + _FORCE_INLINE_ KeyValue<TKey, TValue> *operator->() const { return &E->data; } + _FORCE_INLINE_ Iterator &operator++() { if (E) { E = E->next; } return *this; } - _FORCE_INLINE_ ConstIterator &operator--() { + _FORCE_INLINE_ Iterator &operator--() { if (E) { E = E->prev; } return *this; } - _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; } - _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; } + _FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; } + _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; } - _FORCE_INLINE_ operator bool() const { + _FORCE_INLINE_ explicit operator bool() const { return E != nullptr; } - _FORCE_INLINE_ ConstIterator(const HashMapElement<TKey, TValue> *p_E) { E = p_E; } - _FORCE_INLINE_ ConstIterator() {} - _FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; } - _FORCE_INLINE_ void operator=(const ConstIterator &p_it) { + _FORCE_INLINE_ Iterator(HashMapElement<TKey, TValue> *p_E) { E = p_E; } + _FORCE_INLINE_ Iterator() {} + _FORCE_INLINE_ Iterator(const Iterator &p_it) { E = p_it.E; } + _FORCE_INLINE_ void operator=(const Iterator &p_it) { E = p_it.E; } + operator ConstIterator() const { + return ConstIterator(E); + } + private: - const HashMapElement<TKey, TValue> *E = nullptr; + HashMapElement<TKey, TValue> *E = nullptr; }; _FORCE_INLINE_ Iterator begin() { diff --git a/core/templates/hashfuncs.h b/core/templates/hashfuncs.h index eb73ff4ede..1330d55270 100644 --- a/core/templates/hashfuncs.h +++ b/core/templates/hashfuncs.h @@ -163,6 +163,9 @@ static inline uint64_t make_uint64_t(T p_in) { return _u._u64; } +template <class T> +class Ref; + struct HashMapHasherDefault { static _FORCE_INLINE_ uint32_t hash(const String &p_string) { return p_string.hash(); } static _FORCE_INLINE_ uint32_t hash(const char *p_cstr) { return hash_djb2(p_cstr); } @@ -186,6 +189,12 @@ struct HashMapHasherDefault { static _FORCE_INLINE_ uint32_t hash(const StringName &p_string_name) { return p_string_name.hash(); } static _FORCE_INLINE_ uint32_t hash(const NodePath &p_path) { return p_path.hash(); } + template <class T> + static _FORCE_INLINE_ uint32_t hash(const T *p_pointer) { return hash_one_uint64((uint64_t)p_pointer); } + + template <class T> + static _FORCE_INLINE_ uint32_t hash(const Ref<T> &p_ref) { return hash_one_uint64((uint64_t)p_ref.operator->()); } + static _FORCE_INLINE_ uint32_t hash(const Vector2i &p_vec) { uint32_t h = hash_djb2_one_32(p_vec.x); return hash_djb2_one_32(p_vec.y, h); @@ -237,16 +246,36 @@ struct HashMapComparatorDefault { static bool compare(const T &p_lhs, const T &p_rhs) { return p_lhs == p_rhs; } +}; - bool compare(const float &p_lhs, const float &p_rhs) { +template <> +struct HashMapComparatorDefault<float> { + static bool compare(const float &p_lhs, const float &p_rhs) { return (p_lhs == p_rhs) || (Math::is_nan(p_lhs) && Math::is_nan(p_rhs)); } +}; - bool compare(const double &p_lhs, const double &p_rhs) { +template <> +struct HashMapComparatorDefault<double> { + static bool compare(const double &p_lhs, const double &p_rhs) { return (p_lhs == p_rhs) || (Math::is_nan(p_lhs) && Math::is_nan(p_rhs)); } }; +template <> +struct HashMapComparatorDefault<Vector2> { + static bool compare(const Vector2 &p_lhs, const Vector2 &p_rhs) { + return ((p_lhs.x == p_rhs.x) || (Math::is_nan(p_lhs.x) && Math::is_nan(p_rhs.x))) && ((p_lhs.y == p_rhs.y) || (Math::is_nan(p_lhs.y) && Math::is_nan(p_rhs.y))); + } +}; + +template <> +struct HashMapComparatorDefault<Vector3> { + static bool compare(const Vector3 &p_lhs, const Vector3 &p_rhs) { + return ((p_lhs.x == p_rhs.x) || (Math::is_nan(p_lhs.x) && Math::is_nan(p_rhs.x))) && ((p_lhs.y == p_rhs.y) || (Math::is_nan(p_lhs.y) && Math::is_nan(p_rhs.y))) && ((p_lhs.z == p_rhs.z) || (Math::is_nan(p_lhs.z) && Math::is_nan(p_rhs.z))); + } +}; + constexpr uint32_t HASH_TABLE_SIZE_MAX = 29; const uint32_t hash_table_size_primes[HASH_TABLE_SIZE_MAX] = { diff --git a/core/templates/pair.h b/core/templates/pair.h index eb86e21b03..6d33213fe3 100644 --- a/core/templates/pair.h +++ b/core/templates/pair.h @@ -31,8 +31,8 @@ #ifndef PAIR_H #define PAIR_H +#include "core/templates/hashfuncs.h" #include "core/typedefs.h" - template <class F, class S> struct Pair { F first; @@ -69,6 +69,15 @@ struct PairSort { } }; +template <class F, class S> +struct PairHash { + static uint32_t hash(const Pair<F, S> &P) { + uint64_t h1 = HashMapHasherDefault::hash(P.first); + uint64_t h2 = HashMapHasherDefault::hash(P.second); + return hash_one_uint64((h1 << 32) | h2); + } +}; + template <class K, class V> struct KeyValue { const K key; diff --git a/core/templates/map.h b/core/templates/rb_map.h index c54da1dc03..c732ccd485 100644 --- a/core/templates/map.h +++ b/core/templates/rb_map.h @@ -1,5 +1,5 @@ /*************************************************************************/ -/* map.h */ +/* rb_map.h */ /*************************************************************************/ /* This file is part of: */ /* GODOT ENGINE */ @@ -28,8 +28,8 @@ /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ /*************************************************************************/ -#ifndef MAP_H -#define MAP_H +#ifndef RB_MAP_H +#define RB_MAP_H #include "core/error/error_macros.h" #include "core/os/memory.h" @@ -39,7 +39,7 @@ // https://web.archive.org/web/20120507164830/https://web.mit.edu/~emin/www/source_code/red_black_tree/index.html template <class K, class V, class C = Comparator<K>, class A = DefaultAllocator> -class Map { +class RBMap { enum Color { RED, BLACK @@ -49,7 +49,7 @@ class Map { public: class Element { private: - friend class Map<K, V, C, A>; + friend class RBMap<K, V, C, A>; int color = RED; Element *right = nullptr; Element *left = nullptr; @@ -111,7 +111,9 @@ public: _FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; } _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; } - + explicit operator bool() const { + return E != nullptr; + } Iterator(Element *p_E) { E = p_E; } Iterator() {} Iterator(const Iterator &p_it) { E = p_it.E; } @@ -136,7 +138,9 @@ public: _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; } _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; } - + explicit operator bool() const { + return E != nullptr; + } ConstIterator(const Element *p_E) { E = p_E; } ConstIterator() {} ConstIterator(const ConstIterator &p_it) { E = p_it.E; } @@ -572,7 +576,7 @@ private: memdelete_allocator<Element, A>(p_element); } - void _copy_from(const Map &p_map) { + void _copy_from(const RBMap &p_map) { clear(); // not the fastest way, but safeset to write. for (Element *I = p_map.front(); I; I = I->next()) { @@ -710,8 +714,12 @@ public: return e; } - inline bool is_empty() const { return _data.size_cache == 0; } - inline int size() const { return _data.size_cache; } + inline bool is_empty() const { + return _data.size_cache == 0; + } + inline int size() const { + return _data.size_cache; + } int calculate_depth() const { // used for debug mostly @@ -735,17 +743,17 @@ public: _data._free_root(); } - void operator=(const Map &p_map) { + void operator=(const RBMap &p_map) { _copy_from(p_map); } - Map(const Map &p_map) { + RBMap(const RBMap &p_map) { _copy_from(p_map); } - _FORCE_INLINE_ Map() {} + _FORCE_INLINE_ RBMap() {} - ~Map() { + ~RBMap() { clear(); } }; diff --git a/core/templates/set.h b/core/templates/rb_set.h index a8a0a77712..2de816769c 100644 --- a/core/templates/set.h +++ b/core/templates/rb_set.h @@ -1,5 +1,5 @@ /*************************************************************************/ -/* set.h */ +/* rb_set.h */ /*************************************************************************/ /* This file is part of: */ /* GODOT ENGINE */ @@ -28,8 +28,8 @@ /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ /*************************************************************************/ -#ifndef SET_H -#define SET_H +#ifndef RB_SET_H +#define RB_SET_H #include "core/os/memory.h" #include "core/typedefs.h" @@ -38,7 +38,7 @@ // https://web.archive.org/web/20120507164830/https://web.mit.edu/~emin/www/source_code/red_black_tree/index.html template <class T, class C = Comparator<T>, class A = DefaultAllocator> -class Set { +class RBSet { enum Color { RED, BLACK @@ -48,7 +48,7 @@ class Set { public: class Element { private: - friend class Set<T, C, A>; + friend class RBSet<T, C, A>; int color = RED; Element *right = nullptr; Element *left = nullptr; @@ -554,7 +554,7 @@ private: memdelete_allocator<Element, A>(p_element); } - void _copy_from(const Set &p_set) { + void _copy_from(const RBSet &p_set) { clear(); // not the fastest way, but safeset to write. for (Element *I = p_set.front(); I; I = I->next()) { @@ -661,8 +661,12 @@ public: return e; } - inline bool is_empty() const { return _data.size_cache == 0; } - inline int size() const { return _data.size_cache; } + inline bool is_empty() const { + return _data.size_cache == 0; + } + inline int size() const { + return _data.size_cache; + } int calculate_depth() const { // used for debug mostly @@ -686,17 +690,17 @@ public: _data._free_root(); } - void operator=(const Set &p_set) { + void operator=(const RBSet &p_set) { _copy_from(p_set); } - Set(const Set &p_set) { + RBSet(const RBSet &p_set) { _copy_from(p_set); } - _FORCE_INLINE_ Set() {} + _FORCE_INLINE_ RBSet() {} - ~Set() { + ~RBSet() { clear(); } }; diff --git a/core/templates/rid_owner.h b/core/templates/rid_owner.h index 95632cdec2..d26977380e 100644 --- a/core/templates/rid_owner.h +++ b/core/templates/rid_owner.h @@ -36,9 +36,9 @@ #include "core/string/print_string.h" #include "core/templates/list.h" #include "core/templates/oa_hash_map.h" +#include "core/templates/rb_set.h" #include "core/templates/rid.h" #include "core/templates/safe_refcount.h" -#include "core/templates/set.h" #include <stdio.h> #include <typeinfo> diff --git a/core/variant/variant_call.cpp b/core/variant/variant_call.cpp index 882a89b8ba..a3568a8d6a 100644 --- a/core/variant/variant_call.cpp +++ b/core/variant/variant_call.cpp @@ -919,11 +919,11 @@ struct _VariantCall { } struct ConstantData { - Map<StringName, int> value; + HashMap<StringName, int> value; #ifdef DEBUG_ENABLED List<StringName> value_ordered; #endif - Map<StringName, Variant> variant_value; + HashMap<StringName, Variant> variant_value; #ifdef DEBUG_ENABLED List<StringName> variant_value_ordered; #endif @@ -1281,14 +1281,14 @@ Variant Variant::get_constant_value(Variant::Type p_type, const StringName &p_va ERR_FAIL_INDEX_V(p_type, Variant::VARIANT_MAX, 0); _VariantCall::ConstantData &cd = _VariantCall::constant_data[p_type]; - Map<StringName, int>::Element *E = cd.value.find(p_value); + HashMap<StringName, int>::Iterator E = cd.value.find(p_value); if (!E) { - Map<StringName, Variant>::Element *F = cd.variant_value.find(p_value); + HashMap<StringName, Variant>::Iterator F = cd.variant_value.find(p_value); if (F) { if (r_valid) { *r_valid = true; } - return F->get(); + return F->value; } else { return -1; } @@ -1297,7 +1297,7 @@ Variant Variant::get_constant_value(Variant::Type p_type, const StringName &p_va *r_valid = true; } - return E->get(); + return E->value; } #ifdef DEBUG_METHODS_ENABLED diff --git a/core/variant/variant_parser.h b/core/variant/variant_parser.h index 70ca8d8cb5..56b484c8bc 100644 --- a/core/variant/variant_parser.h +++ b/core/variant/variant_parser.h @@ -113,7 +113,7 @@ public: struct Tag { String name; - Map<String, Variant> fields; + HashMap<String, Variant> fields; }; private: |