diff options
Diffstat (limited to 'core')
97 files changed, 1280 insertions, 1323 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 79fa6a0895..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; } @@ -1091,7 +1092,7 @@ bool ProjectSettings::has_custom_feature(const String &p_feature) const { return custom_features.has(p_feature); } -OrderedHashMap<StringName, ProjectSettings::AutoloadInfo> ProjectSettings::get_autoload_list() const { +const HashMap<StringName, ProjectSettings::AutoloadInfo> &ProjectSettings::get_autoload_list() const { return autoloads; } @@ -1135,13 +1136,13 @@ void ProjectSettings::_bind_methods() { void ProjectSettings::_add_builtin_input_map() { if (InputMap::get_singleton()) { - OrderedHashMap<String, List<Ref<InputEvent>>> builtins = InputMap::get_singleton()->get_builtins(); + HashMap<String, List<Ref<InputEvent>>> builtins = InputMap::get_singleton()->get_builtins(); - for (OrderedHashMap<String, List<Ref<InputEvent>>>::Element E = builtins.front(); E; E = E.next()) { + for (KeyValue<String, List<Ref<InputEvent>>> &E : builtins) { Array events; // Convert list of input events into array - for (List<Ref<InputEvent>>::Element *I = E.get().front(); I; I = I->next()) { + for (List<Ref<InputEvent>>::Element *I = E.value.front(); I; I = I->next()) { events.push_back(I->get()); } @@ -1149,7 +1150,7 @@ void ProjectSettings::_add_builtin_input_map() { action["deadzone"] = Variant(0.5f); action["events"] = events; - String action_name = "input/" + E.key(); + String action_name = "input/" + E.key; GLOBAL_DEF(action_name, action); input_presets.push_back(action_name); } @@ -1175,6 +1176,22 @@ ProjectSettings::ProjectSettings() { GLOBAL_DEF("application/config/use_custom_user_dir", false); GLOBAL_DEF("application/config/custom_user_dir_name", ""); GLOBAL_DEF("application/config/project_settings_override", ""); + + GLOBAL_DEF_BASIC("display/window/size/viewport_width", 1024); + custom_prop_info["display/window/size/viewport_width"] = PropertyInfo(Variant::INT, "display/window/size/viewport_width", PROPERTY_HINT_RANGE, "0,7680,1,or_greater"); // 8K resolution + + GLOBAL_DEF_BASIC("display/window/size/viewport_height", 600); + custom_prop_info["display/window/size/viewport_height"] = PropertyInfo(Variant::INT, "display/window/size/viewport_height", PROPERTY_HINT_RANGE, "0,4320,1,or_greater"); // 8K resolution + + GLOBAL_DEF_BASIC("display/window/size/resizable", true); + GLOBAL_DEF_BASIC("display/window/size/borderless", false); + GLOBAL_DEF_BASIC("display/window/size/fullscreen", false); + GLOBAL_DEF("display/window/size/always_on_top", false); + GLOBAL_DEF("display/window/size/window_width_override", 0); + custom_prop_info["display/window/size/window_width_override"] = PropertyInfo(Variant::INT, "display/window/size/window_width_override", PROPERTY_HINT_RANGE, "0,7680,1,or_greater"); // 8K resolution + GLOBAL_DEF("display/window/size/window_height_override", 0); + custom_prop_info["display/window/size/window_height_override"] = PropertyInfo(Variant::INT, "display/window/size/window_height_override", PROPERTY_HINT_RANGE, "0,4320,1,or_greater"); // 8K resolution + GLOBAL_DEF_BASIC("audio/buses/default_bus_layout", "res://default_bus_layout.tres"); custom_prop_info["audio/buses/default_bus_layout"] = PropertyInfo(Variant::STRING, "audio/buses/default_bus_layout", PROPERTY_HINT_FILE, "*.tres"); diff --git a/core/config/project_settings.h b/core/config/project_settings.h index 614a11f726..f8dc618cb8 100644 --- a/core/config/project_settings.h +++ b/core/config/project_settings.h @@ -33,15 +33,15 @@ #include "core/object/class_db.h" #include "core/os/thread_safe.h" -#include "core/templates/ordered_hash_map.h" -#include "core/templates/set.h" +#include "core/templates/hash_map.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,17 +84,17 @@ 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; - OrderedHashMap<StringName, AutoloadInfo> autoloads; + HashMap<StringName, AutoloadInfo> autoloads; String project_data_dir_name; @@ -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; @@ -181,7 +181,7 @@ public: bool has_custom_feature(const String &p_feature) const; - OrderedHashMap<StringName, AutoloadInfo> get_autoload_list() const; + const HashMap<StringName, AutoloadInfo> &get_autoload_list() const; void add_autoload(const AutoloadInfo &p_autoload); void remove_autoload(const StringName &p_autoload); bool has_autoload(const StringName &p_autoload) 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/core_constants.cpp b/core/core_constants.cpp index 2a514b68d8..a53929a3af 100644 --- a/core/core_constants.cpp +++ b/core/core_constants.cpp @@ -703,6 +703,7 @@ void register_global_constants() { BIND_CORE_ENUM_CONSTANT_CUSTOM("OP_NEGATE", Variant::OP_NEGATE); BIND_CORE_ENUM_CONSTANT_CUSTOM("OP_POSITIVE", Variant::OP_POSITIVE); BIND_CORE_ENUM_CONSTANT_CUSTOM("OP_MODULE", Variant::OP_MODULE); + BIND_CORE_ENUM_CONSTANT_CUSTOM("OP_POWER", Variant::OP_POWER); //bitwise BIND_CORE_ENUM_CONSTANT_CUSTOM("OP_SHIFT_LEFT", Variant::OP_SHIFT_LEFT); BIND_CORE_ENUM_CONSTANT_CUSTOM("OP_SHIFT_RIGHT", Variant::OP_SHIFT_RIGHT); 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/gdnative_interface.h b/core/extension/gdnative_interface.h index 36d51ff2b9..98976b29f6 100644 --- a/core/extension/gdnative_interface.h +++ b/core/extension/gdnative_interface.h @@ -114,6 +114,7 @@ typedef enum { GDNATIVE_VARIANT_OP_NEGATE, GDNATIVE_VARIANT_OP_POSITIVE, GDNATIVE_VARIANT_OP_MODULE, + GDNATIVE_VARIANT_OP_POWER, /* bitwise */ GDNATIVE_VARIANT_OP_SHIFT_LEFT, GDNATIVE_VARIANT_OP_SHIFT_RIGHT, 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 40cea2cd80..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 { @@ -636,21 +636,21 @@ void Input::_parse_input_event_impl(const Ref<InputEvent> &p_event, bool p_is_em } } - for (OrderedHashMap<StringName, InputMap::Action>::ConstElement E = InputMap::get_singleton()->get_action_map().front(); E; E = E.next()) { - if (InputMap::get_singleton()->event_is_action(p_event, E.key())) { + for (const KeyValue<StringName, InputMap::Action> &E : InputMap::get_singleton()->get_action_map()) { + if (InputMap::get_singleton()->event_is_action(p_event, E.key)) { // If not echo and action pressed state has changed - if (!p_event->is_echo() && is_action_pressed(E.key(), false) != p_event->is_action_pressed(E.key())) { + if (!p_event->is_echo() && is_action_pressed(E.key, false) != p_event->is_action_pressed(E.key)) { Action action; action.physics_frame = Engine::get_singleton()->get_physics_frames(); action.process_frame = Engine::get_singleton()->get_process_frames(); - action.pressed = p_event->is_action_pressed(E.key()); + action.pressed = p_event->is_action_pressed(E.key); action.strength = 0.0f; action.raw_strength = 0.0f; - action.exact = InputMap::get_singleton()->event_is_action(p_event, E.key(), true); - action_state[E.key()] = action; + action.exact = InputMap::get_singleton()->event_is_action(p_event, E.key, true); + action_state[E.key] = action; } - action_state[E.key()].strength = p_event->get_action_strength(E.key()); - action_state[E.key()].raw_strength = p_event->get_action_raw_strength(E.key()); + action_state[E.key].strength = p_event->get_action_strength(E.key); + action_state[E.key].raw_strength = p_event->get_action_raw_strength(E.key); } } @@ -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 ab94c00999..942c5248df 100644 --- a/core/input/input_map.cpp +++ b/core/input/input_map.cpp @@ -119,8 +119,8 @@ List<StringName> InputMap::get_actions() const { return actions; } - for (OrderedHashMap<StringName, Action>::Element E = input_map.front(); E; E = E.next()) { - actions.push_back(E.key()); + for (const KeyValue<StringName, Action> &E : input_map) { + actions.push_back(E.key); } return actions; @@ -203,12 +203,12 @@ Array InputMap::_action_get_events(const StringName &p_action) { } const List<Ref<InputEvent>> *InputMap::action_get_events(const StringName &p_action) { - const OrderedHashMap<StringName, Action>::Element E = input_map.find(p_action); + HashMap<StringName, Action>::Iterator E = input_map.find(p_action); if (!E) { return nullptr; } - return &E.get().inputs; + return &E->value.inputs; } bool InputMap::event_is_action(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match) const { @@ -216,7 +216,7 @@ bool InputMap::event_is_action(const Ref<InputEvent> &p_event, const StringName } bool InputMap::event_get_action_status(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match, bool *r_pressed, float *r_strength, float *r_raw_strength) const { - OrderedHashMap<StringName, Action>::Element E = input_map.find(p_action); + HashMap<StringName, Action>::Iterator E = input_map.find(p_action); ERR_FAIL_COND_V_MSG(!E, false, suggest_actions(p_action)); Ref<InputEventAction> input_event_action = p_event; @@ -235,11 +235,11 @@ bool InputMap::event_get_action_status(const Ref<InputEvent> &p_event, const Str return input_event_action->get_action() == p_action; } - List<Ref<InputEvent>>::Element *event = _find_event(E.get(), p_event, p_exact_match, r_pressed, r_strength, r_raw_strength); + List<Ref<InputEvent>>::Element *event = _find_event(E->value, p_event, p_exact_match, r_pressed, r_strength, r_raw_strength); return event != nullptr; } -const OrderedHashMap<StringName, InputMap::Action> &InputMap::get_action_map() const { +const HashMap<StringName, InputMap::Action> &InputMap::get_action_map() const { return input_map; } @@ -360,7 +360,7 @@ String InputMap::get_builtin_display_name(const String &p_name) const { return p_name; } -const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins() { +const HashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins() { // Return cache if it has already been built. if (default_builtin_cache.size()) { return default_builtin_cache; @@ -686,19 +686,19 @@ const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins() { return default_builtin_cache; } -const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with_feature_overrides_applied() { +const HashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with_feature_overrides_applied() { if (default_builtin_with_overrides_cache.size() > 0) { return default_builtin_with_overrides_cache; } - OrderedHashMap<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; - for (OrderedHashMap<String, List<Ref<InputEvent>>>::Element E = builtins.front(); E; E = E.next()) { - String fullname = E.key(); + HashMap<String, Vector<String>> builtins_with_overrides; + for (const KeyValue<String, List<Ref<InputEvent>>> &E : builtins) { + String fullname = E.key; Vector<String> split = fullname.split("."); String name = split[0]; @@ -709,8 +709,8 @@ const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with } } - for (OrderedHashMap<String, List<Ref<InputEvent>>>::Element E = builtins.front(); E; E = E.next()) { - String fullname = E.key(); + for (const KeyValue<String, List<Ref<InputEvent>>> &E : builtins) { + String fullname = E.key; Vector<String> split = fullname.split("."); String name = split[0]; @@ -726,22 +726,22 @@ const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with continue; } - default_builtin_with_overrides_cache.insert(name, E.value()); + default_builtin_with_overrides_cache.insert(name, E.value); } return default_builtin_with_overrides_cache; } void InputMap::load_default() { - OrderedHashMap<String, List<Ref<InputEvent>>> builtins = get_builtins_with_feature_overrides_applied(); + HashMap<String, List<Ref<InputEvent>>> builtins = get_builtins_with_feature_overrides_applied(); - for (OrderedHashMap<String, List<Ref<InputEvent>>>::Element E = builtins.front(); E; E = E.next()) { - String name = E.key(); + for (const KeyValue<String, List<Ref<InputEvent>>> &E : builtins) { + String name = E.key; add_action(name); - List<Ref<InputEvent>> inputs = E.get(); - for (List<Ref<InputEvent>>::Element *I = inputs.front(); I; I = I->next()) { + const List<Ref<InputEvent>> &inputs = E.value; + for (const List<Ref<InputEvent>>::Element *I = inputs.front(); I; I = I->next()) { Ref<InputEventKey> iek = I->get(); // For the editor, only add keyboard actions. diff --git a/core/input/input_map.h b/core/input/input_map.h index 79b4d1038f..2400a4a3f7 100644 --- a/core/input/input_map.h +++ b/core/input/input_map.h @@ -34,7 +34,7 @@ #include "core/input/input_event.h" #include "core/object/class_db.h" #include "core/object/object.h" -#include "core/templates/ordered_hash_map.h" +#include "core/templates/hash_map.h" class InputMap : public Object { GDCLASS(InputMap, Object); @@ -54,9 +54,9 @@ public: private: static InputMap *singleton; - mutable OrderedHashMap<StringName, Action> input_map; - OrderedHashMap<String, List<Ref<InputEvent>>> default_builtin_cache; - OrderedHashMap<String, List<Ref<InputEvent>>> default_builtin_with_overrides_cache; + mutable HashMap<StringName, Action> input_map; + HashMap<String, List<Ref<InputEvent>>> default_builtin_cache; + HashMap<String, List<Ref<InputEvent>>> default_builtin_with_overrides_cache; List<Ref<InputEvent>>::Element *_find_event(Action &p_action, const Ref<InputEvent> &p_event, bool p_exact_match = false, bool *r_pressed = nullptr, float *r_strength = nullptr, float *r_raw_strength = nullptr) const; @@ -85,7 +85,7 @@ public: bool event_is_action(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match = false) const; bool event_get_action_status(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match = false, bool *r_pressed = nullptr, float *r_strength = nullptr, float *r_raw_strength = nullptr) const; - const OrderedHashMap<StringName, Action> &get_action_map() const; + const HashMap<StringName, Action> &get_action_map() const; void load_from_project_settings(); void load_default(); @@ -93,8 +93,8 @@ public: String get_builtin_display_name(const String &p_name) const; // Use an Ordered Map so insertion order is preserved. We want the elements to be 'grouped' somewhat. - const OrderedHashMap<String, List<Ref<InputEvent>>> &get_builtins(); - const OrderedHashMap<String, List<Ref<InputEvent>>> &get_builtins_with_feature_overrides_applied(); + const HashMap<String, List<Ref<InputEvent>>> &get_builtins(); + const HashMap<String, List<Ref<InputEvent>>> &get_builtins_with_feature_overrides_applied(); InputMap(); ~InputMap(); diff --git a/core/io/config_file.cpp b/core/io/config_file.cpp index bc24cac955..dd0191f43f 100644 --- a/core/io/config_file.cpp +++ b/core/io/config_file.cpp @@ -73,7 +73,7 @@ void ConfigFile::set_value(const String &p_section, const String &p_key, const V } else { if (!values.has(p_section)) { - values[p_section] = OrderedHashMap<String, Variant>(); + values[p_section] = HashMap<String, Variant>(); } values[p_section][p_key] = p_value; @@ -102,16 +102,16 @@ bool ConfigFile::has_section_key(const String &p_section, const String &p_key) c } void ConfigFile::get_sections(List<String> *r_sections) const { - for (OrderedHashMap<String, OrderedHashMap<String, Variant>>::ConstElement E = values.front(); E; E = E.next()) { - r_sections->push_back(E.key()); + for (const KeyValue<String, HashMap<String, Variant>> &E : values) { + r_sections->push_back(E.key); } } void ConfigFile::get_section_keys(const String &p_section, List<String> *r_keys) const { ERR_FAIL_COND_MSG(!values.has(p_section), vformat("Cannot get keys from nonexistent section \"%s\".", p_section)); - for (OrderedHashMap<String, Variant>::ConstElement E = values[p_section].front(); E; E = E.next()) { - r_keys->push_back(E.key()); + for (const KeyValue<String, Variant> &E : values[p_section]) { + r_keys->push_back(E.key); } } @@ -174,18 +174,21 @@ Error ConfigFile::save_encrypted_pass(const String &p_path, const String &p_pass } Error ConfigFile::_internal_save(Ref<FileAccess> file) { - for (OrderedHashMap<String, OrderedHashMap<String, Variant>>::Element E = values.front(); E; E = E.next()) { - if (E != values.front()) { + bool first = true; + for (const KeyValue<String, HashMap<String, Variant>> &E : values) { + if (first) { + first = false; + } else { 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 (OrderedHashMap<String, Variant>::Element F = E.get().front(); F; F = F.next()) { + for (const KeyValue<String, Variant> &F : E.value) { String vstr; - VariantWriter::write_to_string(F.get(), vstr); - file->store_string(F.key().property_name_encode() + "=" + vstr + "\n"); + VariantWriter::write_to_string(F.value, vstr); + file->store_string(F.key.property_name_encode() + "=" + vstr + "\n"); } } diff --git a/core/io/config_file.h b/core/io/config_file.h index 7a52b0e16a..3b07ec52f5 100644 --- a/core/io/config_file.h +++ b/core/io/config_file.h @@ -33,13 +33,13 @@ #include "core/io/file_access.h" #include "core/object/ref_counted.h" -#include "core/templates/ordered_hash_map.h" +#include "core/templates/hash_map.h" #include "core/variant/variant_parser.h" class ConfigFile : public RefCounted { GDCLASS(ConfigFile, RefCounted); - OrderedHashMap<String, OrderedHashMap<String, Variant>> values; + HashMap<String, HashMap<String, Variant>> values; PackedStringArray _get_sections() const; PackedStringArray _get_section_keys(const String &p_section) const; 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/image.cpp b/core/io/image.cpp index 661a9f7177..671a000e2c 100644 --- a/core/io/image.cpp +++ b/core/io/image.cpp @@ -436,7 +436,7 @@ static void _convert(int p_width, int p_height, const uint8_t *p_src, uint8_t *p const uint8_t *rofs = &p_src[((y * p_width) + x) * (read_bytes + (read_alpha ? 1 : 0))]; uint8_t *wofs = &p_dst[((y * p_width) + x) * (write_bytes + (write_alpha ? 1 : 0))]; - uint8_t rgba[4]; + uint8_t rgba[4] = { 0, 0, 0, 255 }; if (read_gray) { rgba[0] = rofs[0]; @@ -454,7 +454,7 @@ static void _convert(int p_width, int p_height, const uint8_t *p_src, uint8_t *p if (write_gray) { //TODO: not correct grayscale, should use fixed point version of actual weights - wofs[0] = uint8_t((uint16_t(rofs[0]) + uint16_t(rofs[1]) + uint16_t(rofs[2])) / 3); + wofs[0] = uint8_t((uint16_t(rgba[0]) + uint16_t(rgba[1]) + uint16_t(rgba[2])) / 3); } else { for (uint32_t i = 0; i < write_bytes; i++) { wofs[i] = rgba[i]; 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/missing_resource.cpp b/core/io/missing_resource.cpp index 7aae6c6f0a..29814cdeb3 100644 --- a/core/io/missing_resource.cpp +++ b/core/io/missing_resource.cpp @@ -53,8 +53,8 @@ bool MissingResource::_get(const StringName &p_name, Variant &r_ret) const { } void MissingResource::_get_property_list(List<PropertyInfo> *p_list) const { - for (OrderedHashMap<StringName, Variant>::ConstElement E = properties.front(); E; E = E.next()) { - p_list->push_back(PropertyInfo(E.value().get_type(), E.key())); + for (const KeyValue<StringName, Variant> &E : properties) { + p_list->push_back(PropertyInfo(E.value.get_type(), E.key)); } } diff --git a/core/io/missing_resource.h b/core/io/missing_resource.h index e87efe1a98..6536a4119b 100644 --- a/core/io/missing_resource.h +++ b/core/io/missing_resource.h @@ -38,7 +38,7 @@ class MissingResource : public Resource { GDCLASS(MissingResource, Resource) - OrderedHashMap<StringName, Variant> properties; + HashMap<StringName, Variant> properties; String original_class; bool recording_properties = false; 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 e6535c67a4..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 @@ -478,10 +478,8 @@ void ResourceCache::clear() { if (resources.size()) { ERR_PRINT("Resources still in use at exit (run with --verbose for details)."); if (OS::get_singleton()->is_stdout_verbose()) { - const String *K = nullptr; - while ((K = resources.next(K))) { - Resource *r = resources[*K]; - print_line(vformat("Resource still in use: %s (%s)", *K, r->get_class())); + for (const KeyValue<String, Resource *> &E : resources) { + print_line(vformat("Resource still in use: %s (%s)", E.key, E.value->get_class())); } } } @@ -516,10 +514,8 @@ Resource *ResourceCache::get(const String &p_path) { void ResourceCache::get_cached_resources(List<Ref<Resource>> *p_resources) { lock.read_lock(); - const String *K = nullptr; - while ((K = resources.next(K))) { - Resource *r = resources[*K]; - p_resources->push_back(Ref<Resource>(r)); + for (KeyValue<String, Resource *> &E : resources) { + p_resources->push_back(Ref<Resource>(E.value)); } lock.read_unlock(); } @@ -536,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) { @@ -544,9 +540,8 @@ void ResourceCache::dump(const char *p_file, bool p_short) { ERR_FAIL_COND_MSG(f.is_null(), "Cannot create file at path '" + String::utf8(p_file) + "'."); } - const String *K = nullptr; - while ((K = resources.next(K))) { - Resource *r = resources[*K]; + for (KeyValue<String, Resource *> &E : resources) { + Resource *r = E.value; if (!type_count.has(r->get_class())) { type_count[r->get_class()] = 0; 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/io/resource_uid.cpp b/core/io/resource_uid.cpp index 515b7c710e..fc324a26da 100644 --- a/core/io/resource_uid.cpp +++ b/core/io/resource_uid.cpp @@ -149,12 +149,12 @@ Error ResourceUID::save_to_cache() { cache_entries = 0; - for (OrderedHashMap<ID, Cache>::Element E = unique_ids.front(); E; E = E.next()) { - f->store_64(E.key()); - uint32_t s = E.get().cs.length(); + for (KeyValue<ID, Cache> &E : unique_ids) { + f->store_64(E.key); + uint32_t s = E.value.cs.length(); f->store_32(s); - f->store_buffer((const uint8_t *)E.get().cs.ptr(), s); - E.get().saved_to_cache = true; + f->store_buffer((const uint8_t *)E.value.cs.ptr(), s); + E.value.saved_to_cache = true; cache_entries++; } @@ -202,8 +202,8 @@ Error ResourceUID::update_cache() { MutexLock l(mutex); Ref<FileAccess> f; - for (OrderedHashMap<ID, Cache>::Element E = unique_ids.front(); E; E = E.next()) { - if (!E.get().saved_to_cache) { + for (KeyValue<ID, Cache> &E : unique_ids) { + if (!E.value.saved_to_cache) { if (f.is_null()) { f = FileAccess::open(get_cache_file(), FileAccess::READ_WRITE); //append if (f.is_null()) { @@ -211,11 +211,11 @@ Error ResourceUID::update_cache() { } f->seek_end(); } - f->store_64(E.key()); - uint32_t s = E.get().cs.length(); + f->store_64(E.key); + uint32_t s = E.value.cs.length(); f->store_32(s); - f->store_buffer((const uint8_t *)E.get().cs.ptr(), s); - E.get().saved_to_cache = true; + f->store_buffer((const uint8_t *)E.value.cs.ptr(), s); + E.value.saved_to_cache = true; cache_entries++; } } diff --git a/core/io/resource_uid.h b/core/io/resource_uid.h index 0b7ffdf6d0..da42553cf5 100644 --- a/core/io/resource_uid.h +++ b/core/io/resource_uid.h @@ -33,7 +33,7 @@ #include "core/object/ref_counted.h" #include "core/string/string_name.h" -#include "core/templates/ordered_hash_map.h" +#include "core/templates/hash_map.h" class ResourceUID : public Object { GDCLASS(ResourceUID, Object) @@ -53,7 +53,7 @@ private: bool saved_to_cache = false; }; - OrderedHashMap<ID, Cache> unique_ids; //unique IDs and utf8 paths (less memory used) + HashMap<ID, Cache> unique_ids; //unique IDs and utf8 paths (less memory used) static ResourceUID *singleton; uint32_t cache_entries = 0; diff --git a/core/io/zip_io.cpp b/core/io/zip_io.cpp index 2cc844b628..e573e8de19 100644 --- a/core/io/zip_io.cpp +++ b/core/io/zip_io.cpp @@ -31,18 +31,19 @@ #include "zip_io.h" void *zipio_open(voidpf opaque, const char *p_fname, int mode) { - ZipIOData *zd = (ZipIOData *)opaque; + Ref<FileAccess> *fa = reinterpret_cast<Ref<FileAccess> *>(opaque); + ERR_FAIL_COND_V(fa == nullptr, nullptr); String fname; fname.parse_utf8(p_fname); if (mode & ZLIB_FILEFUNC_MODE_WRITE) { - zd->f = FileAccess::open(fname, FileAccess::WRITE); + (*fa) = FileAccess::open(fname, FileAccess::WRITE); } else { - zd->f = FileAccess::open(fname, FileAccess::READ); + (*fa) = FileAccess::open(fname, FileAccess::READ); } - if (zd->f.is_null()) { + if (fa->is_null()) { return nullptr; } @@ -50,49 +51,66 @@ void *zipio_open(voidpf opaque, const char *p_fname, int mode) { } uLong zipio_read(voidpf opaque, voidpf stream, void *buf, uLong size) { - ZipIOData *zd = (ZipIOData *)opaque; - return zd->f->get_buffer((uint8_t *)buf, size); + Ref<FileAccess> *fa = reinterpret_cast<Ref<FileAccess> *>(opaque); + ERR_FAIL_COND_V(fa == nullptr, 0); + ERR_FAIL_COND_V(fa->is_null(), 0); + + return (*fa)->get_buffer((uint8_t *)buf, size); } uLong zipio_write(voidpf opaque, voidpf stream, const void *buf, uLong size) { - ZipIOData *zd = (ZipIOData *)opaque; - zd->f->store_buffer((uint8_t *)buf, size); + Ref<FileAccess> *fa = reinterpret_cast<Ref<FileAccess> *>(opaque); + ERR_FAIL_COND_V(fa == nullptr, 0); + ERR_FAIL_COND_V(fa->is_null(), 0); + + (*fa)->store_buffer((uint8_t *)buf, size); return size; } long zipio_tell(voidpf opaque, voidpf stream) { - ZipIOData *zd = (ZipIOData *)opaque; - return zd->f->get_position(); + Ref<FileAccess> *fa = reinterpret_cast<Ref<FileAccess> *>(opaque); + ERR_FAIL_COND_V(fa == nullptr, 0); + ERR_FAIL_COND_V(fa->is_null(), 0); + + return (*fa)->get_position(); } long zipio_seek(voidpf opaque, voidpf stream, uLong offset, int origin) { - ZipIOData *zd = (ZipIOData *)opaque; + Ref<FileAccess> *fa = reinterpret_cast<Ref<FileAccess> *>(opaque); + ERR_FAIL_COND_V(fa == nullptr, 0); + ERR_FAIL_COND_V(fa->is_null(), 0); uint64_t pos = offset; switch (origin) { case ZLIB_FILEFUNC_SEEK_CUR: - pos = zd->f->get_position() + offset; + pos = (*fa)->get_position() + offset; break; case ZLIB_FILEFUNC_SEEK_END: - pos = zd->f->get_length() + offset; + pos = (*fa)->get_length() + offset; break; default: break; } - zd->f->seek(pos); + (*fa)->seek(pos); return 0; } int zipio_close(voidpf opaque, voidpf stream) { - ZipIOData *zd = (ZipIOData *)opaque; - memdelete(zd); + Ref<FileAccess> *fa = reinterpret_cast<Ref<FileAccess> *>(opaque); + ERR_FAIL_COND_V(fa == nullptr, 0); + ERR_FAIL_COND_V(fa->is_null(), 0); + + fa->unref(); return 0; } int zipio_testerror(voidpf opaque, voidpf stream) { - ZipIOData *zd = (ZipIOData *)opaque; - return (zd->f.is_valid() && zd->f->get_error() != OK) ? 1 : 0; + Ref<FileAccess> *fa = reinterpret_cast<Ref<FileAccess> *>(opaque); + ERR_FAIL_COND_V(fa == nullptr, 1); + ERR_FAIL_COND_V(fa->is_null(), 0); + + return (fa->is_valid() && (*fa)->get_error() != OK) ? 1 : 0; } voidpf zipio_alloc(voidpf opaque, uInt items, uInt size) { @@ -105,9 +123,9 @@ void zipio_free(voidpf opaque, voidpf address) { memfree(address); } -zlib_filefunc_def zipio_create_io() { +zlib_filefunc_def zipio_create_io(Ref<FileAccess> *p_data) { zlib_filefunc_def io; - io.opaque = (void *)memnew(ZipIOData); + io.opaque = (void *)p_data; io.zopen_file = zipio_open; io.zread_file = zipio_read; io.zwrite_file = zipio_write; diff --git a/core/io/zip_io.h b/core/io/zip_io.h index 3bcd1f830d..f137bd2bbf 100644 --- a/core/io/zip_io.h +++ b/core/io/zip_io.h @@ -39,10 +39,6 @@ #include "thirdparty/minizip/unzip.h" #include "thirdparty/minizip/zip.h" -struct ZipIOData { - Ref<FileAccess> f; -}; - void *zipio_open(voidpf opaque, const char *p_fname, int mode); uLong zipio_read(voidpf opaque, voidpf stream, void *buf, uLong size); uLong zipio_write(voidpf opaque, voidpf stream, const void *buf, uLong size); @@ -57,6 +53,6 @@ int zipio_testerror(voidpf opaque, voidpf stream); voidpf zipio_alloc(voidpf opaque, uInt items, uInt size); void zipio_free(voidpf opaque, voidpf address); -zlib_filefunc_def zipio_create_io(); +zlib_filefunc_def zipio_create_io(Ref<FileAccess> *p_data); #endif // ZIP_IO_H 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/expression.cpp b/core/math/expression.cpp index 9dd1257474..97dc175d94 100644 --- a/core/math/expression.cpp +++ b/core/math/expression.cpp @@ -155,7 +155,12 @@ Error Expression::_get_token(Token &r_token) { return OK; } case '*': { - r_token.type = TK_OP_MUL; + if (expression[str_ofs] == '*') { + r_token.type = TK_OP_POW; + str_ofs++; + } else { + r_token.type = TK_OP_MUL; + } return OK; } case '%': { @@ -542,6 +547,7 @@ const char *Expression::token_name[TK_MAX] = { "OP MUL", "OP DIV", "OP MOD", + "OP POW", "OP SHIFT LEFT", "OP SHIFT RIGHT", "OP BIT AND", @@ -1013,6 +1019,9 @@ Expression::ENode *Expression::_parse_expression() { case TK_OP_MOD: op = Variant::OP_MODULE; break; + case TK_OP_POW: + op = Variant::OP_POWER; + break; case TK_OP_SHIFT_LEFT: op = Variant::OP_SHIFT_LEFT; break; @@ -1066,35 +1075,38 @@ Expression::ENode *Expression::_parse_expression() { bool unary = false; switch (expression[i].op) { - case Variant::OP_BIT_NEGATE: + case Variant::OP_POWER: priority = 0; + break; + case Variant::OP_BIT_NEGATE: + priority = 1; unary = true; break; case Variant::OP_NEGATE: - priority = 1; + priority = 2; unary = true; break; case Variant::OP_MULTIPLY: case Variant::OP_DIVIDE: case Variant::OP_MODULE: - priority = 2; + priority = 3; break; case Variant::OP_ADD: case Variant::OP_SUBTRACT: - priority = 3; + priority = 4; break; case Variant::OP_SHIFT_LEFT: case Variant::OP_SHIFT_RIGHT: - priority = 4; + priority = 5; break; case Variant::OP_BIT_AND: - priority = 5; + priority = 6; break; case Variant::OP_BIT_XOR: - priority = 6; + priority = 7; break; case Variant::OP_BIT_OR: - priority = 7; + priority = 8; break; case Variant::OP_LESS: case Variant::OP_LESS_EQUAL: @@ -1102,20 +1114,20 @@ Expression::ENode *Expression::_parse_expression() { case Variant::OP_GREATER_EQUAL: case Variant::OP_EQUAL: case Variant::OP_NOT_EQUAL: - priority = 8; + priority = 9; break; case Variant::OP_IN: - priority = 10; + priority = 11; break; case Variant::OP_NOT: - priority = 11; + priority = 12; unary = true; break; case Variant::OP_AND: - priority = 12; + priority = 13; break; case Variant::OP_OR: - priority = 13; + priority = 14; break; default: { _set_error("Parser bug, invalid operator in expression: " + itos(expression[i].op)); diff --git a/core/math/expression.h b/core/math/expression.h index d43cc4091a..6ea3c1611f 100644 --- a/core/math/expression.h +++ b/core/math/expression.h @@ -85,6 +85,7 @@ private: TK_OP_MUL, TK_OP_DIV, TK_OP_MOD, + TK_OP_POW, TK_OP_SHIFT_LEFT, TK_OP_SHIFT_RIGHT, TK_OP_BIT_AND, 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 593f27b7cf..d19cbf2642 100644 --- a/core/object/class_db.cpp +++ b/core/object/class_db.cpp @@ -90,10 +90,8 @@ bool ClassDB::is_parent_class(const StringName &p_class, const StringName &p_inh void ClassDB::get_class_list(List<StringName> *p_classes) { OBJTYPE_RLOCK; - const StringName *k = nullptr; - - while ((k = classes.next(k))) { - p_classes->push_back(*k); + for (const KeyValue<StringName, ClassInfo> &E : classes) { + p_classes->push_back(E.key); } p_classes->sort(); @@ -102,11 +100,9 @@ void ClassDB::get_class_list(List<StringName> *p_classes) { void ClassDB::get_inheriters_from_class(const StringName &p_class, List<StringName> *p_classes) { OBJTYPE_RLOCK; - const StringName *k = nullptr; - - while ((k = classes.next(k))) { - if (*k != p_class && _is_parent_class(*k, p_class)) { - p_classes->push_back(*k); + for (const KeyValue<StringName, ClassInfo> &E : classes) { + if (E.key != p_class && _is_parent_class(E.key, p_class)) { + p_classes->push_back(E.key); } } } @@ -114,11 +110,9 @@ void ClassDB::get_inheriters_from_class(const StringName &p_class, List<StringNa void ClassDB::get_direct_inheriters_from_class(const StringName &p_class, List<StringName> *p_classes) { OBJTYPE_RLOCK; - const StringName *k = nullptr; - - while ((k = classes.next(k))) { - if (*k != p_class && _get_parent_class(*k) == p_class) { - p_classes->push_back(*k); + for (const KeyValue<StringName, ClassInfo> &E : classes) { + if (E.key != p_class && _get_parent_class(E.key) == p_class) { + p_classes->push_back(E.key); } } } @@ -172,17 +166,12 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { uint64_t hash = hash_djb2_one_64(HashMapHasherDefault::hash(VERSION_FULL_CONFIG)); - List<StringName> names; - - const StringName *k = nullptr; + List<StringName> class_list; + ClassDB::get_class_list(&class_list); + // Must be alphabetically sorted for hash to compute. + class_list.sort_custom<StringName::AlphCompare>(); - while ((k = classes.next(k))) { - names.push_back(*k); - } - //must be alphabetically sorted for hash to compute - names.sort_custom<StringName::AlphCompare>(); - - for (const StringName &E : names) { + for (const StringName &E : class_list) { ClassInfo *t = classes.getptr(E); ERR_FAIL_COND_V_MSG(!t, 0, "Cannot get class '" + String(E) + "'."); if (t->api != p_api || !t->exposed) { @@ -195,10 +184,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { List<StringName> snames; - k = nullptr; - - while ((k = t->method_map.next(k))) { - String name = k->operator String(); + for (const KeyValue<StringName, MethodBind *> &F : t->method_map) { + String name = F.key.operator String(); ERR_CONTINUE(name.is_empty()); @@ -206,7 +193,7 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { continue; // Ignore non-virtual methods that start with an underscore } - snames.push_back(*k); + snames.push_back(F.key); } snames.sort_custom<StringName::AlphCompare>(); @@ -241,10 +228,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { List<StringName> snames; - k = nullptr; - - while ((k = t->constant_map.next(k))) { - snames.push_back(*k); + for (const KeyValue<StringName, int> &F : t->constant_map) { + snames.push_back(F.key); } snames.sort_custom<StringName::AlphCompare>(); @@ -259,10 +244,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { List<StringName> snames; - k = nullptr; - - while ((k = t->signal_map.next(k))) { - snames.push_back(*k); + for (const KeyValue<StringName, MethodInfo> &F : t->signal_map) { + snames.push_back(F.key); } snames.sort_custom<StringName::AlphCompare>(); @@ -280,10 +263,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) { List<StringName> snames; - k = nullptr; - - while ((k = t->property_setget.next(k))) { - snames.push_back(*k); + for (const KeyValue<StringName, PropertySetGet> &F : t->property_setget) { + snames.push_back(F.key); } snames.sort_custom<StringName::AlphCompare>(); @@ -474,10 +455,8 @@ void ClassDB::get_method_list(const StringName &p_class, List<MethodInfo> *p_met #else - const StringName *K = nullptr; - - while ((K = type->method_map.next(K))) { - MethodBind *m = type->method_map[*K]; + for (KeyValue<StringName, MethodBind *> &E : type->method_map) { + MethodBind *m = E.value; MethodInfo minfo = info_from_bind(m); p_methods->push_back(minfo); } @@ -603,10 +582,9 @@ void ClassDB::get_integer_constant_list(const StringName &p_class, List<String> p_constants->push_back(E); } #else - const StringName *K = nullptr; - while ((K = type->constant_map.next(K))) { - p_constants->push_back(*K); + for (const KeyValue<StringName, int> &E : type->constant_map) { + p_constants->push_back(E.key); } #endif @@ -667,12 +645,11 @@ StringName ClassDB::get_integer_constant_enum(const StringName &p_class, const S ClassInfo *type = classes.getptr(p_class); while (type) { - const StringName *k = nullptr; - while ((k = type->enum_map.next(k))) { - List<StringName> &constants_list = type->enum_map.get(*k); + for (KeyValue<StringName, List<StringName>> &E : type->enum_map) { + List<StringName> &constants_list = E.value; const List<StringName>::Element *found = constants_list.find(p_name); if (found) { - return *k; + return E.key; } } @@ -692,9 +669,8 @@ void ClassDB::get_enum_list(const StringName &p_class, List<StringName> *p_enums ClassInfo *type = classes.getptr(p_class); while (type) { - const StringName *k = nullptr; - while ((k = type->enum_map.next(k))) { - p_enums->push_back(*k); + for (KeyValue<StringName, List<StringName>> &E : type->enum_map) { + p_enums->push_back(E.key); } if (p_no_inheritance) { @@ -800,9 +776,8 @@ void ClassDB::get_signal_list(const StringName &p_class, List<MethodInfo> *p_sig ClassInfo *check = type; while (check) { - const StringName *S = nullptr; - while ((S = check->signal_map.next(S))) { - p_signals->push_back(check->signal_map[*S]); + for (KeyValue<StringName, MethodInfo> &E : check->signal_map) { + p_signals->push_back(E.value); } if (p_no_inheritance) { @@ -1397,10 +1372,8 @@ void ClassDB::add_resource_base_extension(const StringName &p_extension, const S } void ClassDB::get_resource_base_extensions(List<String> *p_extensions) { - const StringName *K = nullptr; - - while ((K = resource_base_extensions.next(K))) { - p_extensions->push_back(*K); + for (const KeyValue<StringName, StringName> &E : resource_base_extensions) { + p_extensions->push_back(E.key); } } @@ -1409,18 +1382,15 @@ bool ClassDB::is_resource_extension(const StringName &p_extension) { } void ClassDB::get_extensions_for_type(const StringName &p_class, List<String> *p_extensions) { - const StringName *K = nullptr; - - while ((K = resource_base_extensions.next(K))) { - StringName cmp = resource_base_extensions[*K]; - if (is_parent_class(p_class, cmp) || is_parent_class(cmp, p_class)) { - p_extensions->push_back(*K); + for (const KeyValue<StringName, StringName> &E : resource_base_extensions) { + if (is_parent_class(p_class, E.value) || is_parent_class(E.value, p_class)) { + p_extensions->push_back(E.key); } } } 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)) { @@ -1522,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; @@ -1556,14 +1526,11 @@ void ClassDB::cleanup_defaults() { void ClassDB::cleanup() { //OBJTYPE_LOCK; hah not here - const StringName *k = nullptr; - - while ((k = classes.next(k))) { - ClassInfo &ti = classes[*k]; + for (KeyValue<StringName, ClassInfo> &E : classes) { + ClassInfo &ti = E.value; - const StringName *m = nullptr; - while ((m = ti.method_map.next(m))) { - memdelete(ti.method_map[*m]); + for (KeyValue<StringName, MethodBind *> &F : ti.method_map) { + memdelete(F.value); } } classes.clear(); 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 2b62041533..0912ea55f0 100644 --- a/core/object/object.cpp +++ b/core/object/object.cpp @@ -417,9 +417,9 @@ void Object::set(const StringName &p_name, const Variant &p_value, bool *r_valid return; } else { - OrderedHashMap<StringName, Variant>::Element *E = metadata_properties.getptr(p_name); - if (E) { - E->get() = p_value; + Variant **V = metadata_properties.getptr(p_name); + if (V) { + **V = p_value; if (r_valid) { *r_valid = true; } @@ -508,10 +508,10 @@ Variant Object::get(const StringName &p_name, bool *r_valid) const { return ret; } - const OrderedHashMap<StringName, Variant>::Element *E = metadata_properties.getptr(p_name); + const Variant *const *V = metadata_properties.getptr(p_name); - if (E) { - ret = E->get(); + if (V) { + ret = **V; if (r_valid) { *r_valid = true; } @@ -666,9 +666,9 @@ void Object::get_property_list(List<PropertyInfo> *p_list, bool p_reversed) cons script_instance->get_property_list(p_list); } - for (OrderedHashMap<StringName, Variant>::ConstElement K = metadata.front(); K; K = K.next()) { - PropertyInfo pi = PropertyInfo(K.value().get_type(), "metadata/" + K.key().operator String()); - if (K.value().get_type() == Variant::OBJECT) { + for (const KeyValue<StringName, Variant> &K : metadata) { + PropertyInfo pi = PropertyInfo(K.value.get_type(), "metadata/" + K.key.operator String()); + if (K.value.get_type() == Variant::OBJECT) { pi.hint = PROPERTY_HINT_RESOURCE_TYPE; pi.hint_string = "Resource"; } @@ -944,13 +944,13 @@ void Object::set_meta(const StringName &p_name, const Variant &p_value) { return; } - OrderedHashMap<StringName, Variant>::Element E = metadata.find(p_name); + HashMap<StringName, Variant>::Iterator E = metadata.find(p_name); if (E) { - E.value() = p_value; + E->value = p_value; } else { ERR_FAIL_COND(!p_name.operator String().is_valid_identifier()); - E = metadata.insert(p_name, p_value); - metadata_properties["metadata/" + p_name.operator String()] = E; + Variant *V = &metadata.insert(p_name, p_value)->value; + metadata_properties["metadata/" + p_name.operator String()] = V; notify_property_list_changed(); } } @@ -993,16 +993,16 @@ Array Object::_get_method_list_bind() const { Vector<StringName> Object::_get_meta_list_bind() const { Vector<StringName> _metaret; - for (OrderedHashMap<StringName, Variant>::ConstElement K = metadata.front(); K; K = K.next()) { - _metaret.push_back(K.key()); + for (const KeyValue<StringName, Variant> &K : metadata) { + _metaret.push_back(K.key); } return _metaret; } void Object::get_meta_list(List<StringName> *p_list) const { - for (OrderedHashMap<StringName, Variant>::ConstElement K = metadata.front(); K; K = K.next()) { - p_list->push_back(K.key()); + for (const KeyValue<StringName, Variant> &K : metadata) { + p_list->push_back(K.key); } } @@ -1250,21 +1250,18 @@ void Object::get_signal_list(List<MethodInfo> *p_signals) const { ClassDB::get_signal_list(get_class_name(), p_signals); //find maybe usersignals? - const StringName *S = nullptr; - while ((S = signal_map.next(S))) { - if (!signal_map[*S].user.name.is_empty()) { + for (const KeyValue<StringName, SignalData> &E : signal_map) { + if (!E.value.user.name.is_empty()) { //user signal - p_signals->push_back(signal_map[*S].user); + p_signals->push_back(E.value.user); } } } void Object::get_all_signal_connections(List<Connection> *p_connections) const { - const StringName *S = nullptr; - - while ((S = signal_map.next(S))) { - const SignalData *s = &signal_map[*S]; + for (const KeyValue<StringName, SignalData> &E : signal_map) { + const SignalData *s = &E.value; for (int i = 0; i < s->slot_map.size(); i++) { p_connections->push_back(s->slot_map.getv(i).conn); @@ -1285,10 +1282,9 @@ void Object::get_signal_connection_list(const StringName &p_signal, List<Connect int Object::get_persistent_signal_connection_count() const { int count = 0; - const StringName *S = nullptr; - while ((S = signal_map.next(S))) { - const SignalData *s = &signal_map[*S]; + for (const KeyValue<StringName, SignalData> &E : signal_map) { + const SignalData *s = &E.value; for (int i = 0; i < s->slot_map.size(); i++) { if (s->slot_map.getv(i).conn.flags & CONNECT_PERSIST) { @@ -1386,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) { @@ -1866,15 +1860,15 @@ Object::~Object() { _extension_instance = nullptr; } - const StringName *S = nullptr; - if (_emitting) { //@todo this may need to actually reach the debugger prioritarily somehow because it may crash before ERR_PRINT("Object " + to_string() + " was freed or unreferenced while a signal is being emitted from it. Try connecting to the signal using 'CONNECT_DEFERRED' flag, or use queue_free() to free the object (if this object is a Node) to avoid this error and potential crashes."); } - while ((S = signal_map.next(nullptr))) { - SignalData *s = &signal_map[*S]; + while (signal_map.size()) { + // Avoid regular iteration so erasing is safe. + KeyValue<StringName, SignalData> &E = *signal_map.begin(); + SignalData *s = &E.value; //brute force disconnect for performance int slot_count = s->slot_map.size(); @@ -1884,7 +1878,7 @@ Object::~Object() { slot_list[i].value.conn.callable.get_object()->connections.erase(slot_list[i].value.cE); } - signal_map.erase(*S); + signal_map.erase(E.key); } //signals from nodes that connect to this node diff --git a/core/object/object.h b/core/object/object.h index c3e3c68b59..ca7b9965f1 100644 --- a/core/object/object.h +++ b/core/object/object.h @@ -38,10 +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/ordered_hash_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" @@ -511,12 +510,12 @@ 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. - OrderedHashMap<StringName, Variant> metadata; - HashMap<StringName, OrderedHashMap<StringName, Variant>::Element> metadata_properties; + HashMap<StringName, Variant> metadata; + HashMap<StringName, Variant *> metadata_properties; mutable StringName _class_name; mutable const StringName *_class_ptr = nullptr; @@ -816,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 a5d25bf533..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; @@ -253,10 +253,9 @@ StringName ScriptServer::get_global_class_native_base(const String &p_class) { } void ScriptServer::get_global_class_list(List<StringName> *r_global_classes) { - const StringName *K = nullptr; List<StringName> classes; - while ((K = global_classes.next(K))) { - classes.push_back(*K); + for (const KeyValue<StringName, GlobalScriptClass> &E : global_classes) { + classes.push_back(E.key); } classes.sort_custom<StringName::AlphCompare>(); for (const StringName &E : classes) { @@ -475,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); @@ -491,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); } } } @@ -521,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); } @@ -548,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); @@ -562,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 f58ef45743..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; @@ -346,6 +346,7 @@ public: LOOKUP_RESULT_CLASS_CONSTANT, LOOKUP_RESULT_CLASS_PROPERTY, LOOKUP_RESULT_CLASS_METHOD, + LOOKUP_RESULT_CLASS_SIGNAL, LOOKUP_RESULT_CLASS_ENUM, LOOKUP_RESULT_CLASS_TBD_GLOBALSCOPE, LOOKUP_RESULT_MAX @@ -432,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; @@ -458,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.cpp b/core/object/script_language_extension.cpp index 21d7685674..5af79bbea3 100644 --- a/core/object/script_language_extension.cpp +++ b/core/object/script_language_extension.cpp @@ -157,6 +157,7 @@ void ScriptLanguageExtension::_bind_methods() { BIND_ENUM_CONSTANT(LOOKUP_RESULT_CLASS_CONSTANT); BIND_ENUM_CONSTANT(LOOKUP_RESULT_CLASS_PROPERTY); BIND_ENUM_CONSTANT(LOOKUP_RESULT_CLASS_METHOD); + BIND_ENUM_CONSTANT(LOOKUP_RESULT_CLASS_SIGNAL); BIND_ENUM_CONSTANT(LOOKUP_RESULT_CLASS_ENUM); BIND_ENUM_CONSTANT(LOOKUP_RESULT_CLASS_TBD_GLOBALSCOPE); BIND_ENUM_CONSTANT(LOOKUP_RESULT_MAX); 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/os/memory.h b/core/os/memory.h index baa96ef3e9..42ba9634e2 100644 --- a/core/os/memory.h +++ b/core/os/memory.h @@ -197,4 +197,12 @@ struct _GlobalNilClass { static _GlobalNil _nil; }; +template <class T> +class DefaultTypedAllocator { +public: + template <class... Args> + _FORCE_INLINE_ T *new_allocation(const Args &&...p_args) { return memnew(T(p_args...)); } + _FORCE_INLINE_ void delete_allocation(T *p_allocation) { memdelete(p_allocation); } +}; + #endif // MEMORY_H diff --git a/core/os/os.h b/core/os/os.h index 5eac77d634..157b8ab992 100644 --- a/core/os/os.h +++ b/core/os/os.h @@ -82,11 +82,6 @@ public: RENDER_SEPARATE_THREAD }; - enum RenderMainThreadMode { - RENDER_MAIN_THREAD_ONLY, - RENDER_ANY_THREAD, - }; - protected: friend class Main; // Needed by tests to setup command-line args. @@ -94,7 +89,6 @@ protected: HasServerFeatureCallback has_server_feature_callback = nullptr; RenderThreadMode _render_thread_mode = RENDER_THREAD_SAFE; - RenderMainThreadMode _render_main_thread_mode = RENDER_ANY_THREAD; // Functions used by Main to initialize/deinitialize the OS. void add_logger(Logger *p_logger); @@ -258,8 +252,6 @@ public: virtual uint64_t get_free_static_memory() const; RenderThreadMode get_render_thread_mode() const { return _render_thread_mode; } - RenderMainThreadMode get_render_main_thread_mode() const { return _render_main_thread_mode; } - void set_render_main_thread_mode(RenderMainThreadMode p_thread_mode) { _render_main_thread_mode = p_thread_mode; } virtual String get_locale() const; String get_locale_language() const; 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/string/translation_po.cpp b/core/string/translation_po.cpp index 3f94e064ec..fa656b634d 100644 --- a/core/string/translation_po.cpp +++ b/core/string/translation_po.cpp @@ -70,21 +70,14 @@ Dictionary TranslationPO::_get_messages() const { Dictionary d; - List<StringName> context_l; - translation_map.get_key_list(&context_l); - for (const StringName &ctx : context_l) { - const HashMap<StringName, Vector<StringName>> &id_str_map = translation_map[ctx]; - + for (const KeyValue<StringName, HashMap<StringName, Vector<StringName>>> &E : translation_map) { Dictionary d2; - List<StringName> id_l; - id_str_map.get_key_list(&id_l); - // Save list of id and strs associated with a context in a temporary dictionary. - for (List<StringName>::Element *E2 = id_l.front(); E2; E2 = E2->next()) { - StringName id = E2->get(); - d2[id] = id_str_map[id]; + + for (const KeyValue<StringName, Vector<StringName>> &E2 : E.value) { + d2[E2.key] = E2.value; } - d[ctx] = d2; + d[E.key] = d2; } return d; @@ -274,31 +267,24 @@ void TranslationPO::get_message_list(List<StringName> *r_messages) const { // OptimizedTranslation uses this function to get the list of msgid. // Return all the keys of translation_map under "" context. - List<StringName> context_l; - translation_map.get_key_list(&context_l); - - for (const StringName &E : context_l) { - if (String(E) != "") { + for (const KeyValue<StringName, HashMap<StringName, Vector<StringName>>> &E : translation_map) { + if (E.key != StringName()) { continue; } - List<StringName> msgid_l; - translation_map[E].get_key_list(&msgid_l); - - for (List<StringName>::Element *E2 = msgid_l.front(); E2; E2 = E2->next()) { - r_messages->push_back(E2->get()); + for (const KeyValue<StringName, Vector<StringName>> &E2 : E.value) { + r_messages->push_back(E2.key); } } } int TranslationPO::get_message_count() const { - List<StringName> context_l; - translation_map.get_key_list(&context_l); - int count = 0; - for (const StringName &E : context_l) { - count += translation_map[E].size(); + + for (const KeyValue<StringName, HashMap<StringName, Vector<StringName>>> &E : translation_map) { + count += E.value.size(); } + return count; } diff --git a/core/string/ustring.cpp b/core/string/ustring.cpp index 5d998d22d4..015dfbc651 100644 --- a/core/string/ustring.cpp +++ b/core/string/ustring.cpp @@ -4779,6 +4779,17 @@ Vector<uint8_t> String::to_utf32_buffer() const { } #ifdef TOOLS_ENABLED +/** + * "Tools TRanslate". Performs string replacement for internationalization + * within the editor. A translation context can optionally be specified to + * disambiguate between identical source strings in translations. When + * placeholders are desired, use `vformat(TTR("Example: %s"), some_string)`. + * If a string mentions a quantity (and may therefore need a dynamic plural form), + * use `TTRN()` instead of `TTR()`. + * + * NOTE: Only use `TTR()` in editor-only code (typically within the `editor/` folder). + * For translations that can be supplied by exported projects, use `RTR()` instead. + */ String TTR(const String &p_text, const String &p_context) { if (TranslationServer::get_singleton()) { return TranslationServer::get_singleton()->tool_translate(p_text, p_context); @@ -4787,6 +4798,18 @@ String TTR(const String &p_text, const String &p_context) { return p_text; } +/** + * "Tools TRanslate for N items". Performs string replacement for + * internationalization within the editor. A translation context can optionally + * be specified to disambiguate between identical source strings in + * translations. Use `TTR()` if the string doesn't need dynamic plural form. + * When placeholders are desired, use + * `vformat(TTRN("%d item", "%d items", some_integer), some_integer)`. + * The placeholder must be present in both strings to avoid run-time warnings in `vformat()`. + * + * NOTE: Only use `TTRN()` in editor-only code (typically within the `editor/` folder). + * For translations that can be supplied by exported projects, use `RTRN()` instead. + */ String TTRN(const String &p_text, const String &p_text_plural, int p_n, const String &p_context) { if (TranslationServer::get_singleton()) { return TranslationServer::get_singleton()->tool_translate_plural(p_text, p_text_plural, p_n, p_context); @@ -4799,9 +4822,10 @@ String TTRN(const String &p_text, const String &p_text_plural, int p_n, const St return p_text_plural; } -/* DTR and DTRN are used for the documentation, handling descriptions extracted - * from the XML. - * They also replace `$DOCS_URL` with the actual URL to the documentation's branch, +/** + * "Docs TRanslate". Used for the editor class reference documentation, + * handling descriptions extracted from the XML. + * It also replaces `$DOCS_URL` with the actual URL to the documentation's branch, * to allow dehardcoding it in the XML and doing proper substitutions everywhere. */ String DTR(const String &p_text, const String &p_context) { @@ -4815,6 +4839,12 @@ String DTR(const String &p_text, const String &p_context) { return text.replace("$DOCS_URL", VERSION_DOCS_URL); } +/** + * "Docs TRanslate for N items". Used for the editor class reference documentation + * (with support for plurals), handling descriptions extracted from the XML. + * It also replaces `$DOCS_URL` with the actual URL to the documentation's branch, + * to allow dehardcoding it in the XML and doing proper substitutions everywhere. + */ String DTRN(const String &p_text, const String &p_text_plural, int p_n, const String &p_context) { const String text = p_text.dedent().strip_edges(); const String text_plural = p_text_plural.dedent().strip_edges(); @@ -4831,6 +4861,19 @@ String DTRN(const String &p_text, const String &p_text_plural, int p_n, const St } #endif +/** + * "Run-time TRanslate". Performs string replacement for internationalization + * within a running project. The translation string must be supplied by the + * project, as Godot does not provide built-in translations for `RTR()` strings + * to keep binary size low. A translation context can optionally be specified to + * disambiguate between identical source strings in translations. When + * placeholders are desired, use `vformat(RTR("Example: %s"), some_string)`. + * If a string mentions a quantity (and may therefore need a dynamic plural form), + * use `RTRN()` instead of `RTR()`. + * + * NOTE: Do not use `RTR()` in editor-only code (typically within the `editor/` + * folder). For editor translations, use `TTR()` instead. + */ String RTR(const String &p_text, const String &p_context) { if (TranslationServer::get_singleton()) { String rtr = TranslationServer::get_singleton()->tool_translate(p_text, p_context); @@ -4844,6 +4887,20 @@ String RTR(const String &p_text, const String &p_context) { return p_text; } +/** + * "Run-time TRanslate for N items". Performs string replacement for + * internationalization within a running project. The translation string must be + * supplied by the project, as Godot does not provide built-in translations for + * `RTRN()` strings to keep binary size low. A translation context can + * optionally be specified to disambiguate between identical source strings in + * translations. Use `RTR()` if the string doesn't need dynamic plural form. + * When placeholders are desired, use + * `vformat(RTRN("%d item", "%d items", some_integer), some_integer)`. + * The placeholder must be present in both strings to avoid run-time warnings in `vformat()`. + * + * NOTE: Do not use `RTRN()` in editor-only code (typically within the `editor/` + * folder). For editor translations, use `TTRN()` instead. + */ String RTRN(const String &p_text, const String &p_text_plural, int p_n, const String &p_context) { if (TranslationServer::get_singleton()) { String rtr = TranslationServer::get_singleton()->tool_translate_plural(p_text, p_text_plural, p_n, p_context); diff --git a/core/templates/hash_map.h b/core/templates/hash_map.h index fa5677cc70..e5f73171a2 100644 --- a/core/templates/hash_map.h +++ b/core/templates/hash_map.h @@ -31,524 +31,557 @@ #ifndef HASH_MAP_H #define HASH_MAP_H -#include "core/error/error_macros.h" #include "core/math/math_funcs.h" #include "core/os/memory.h" -#include "core/string/ustring.h" #include "core/templates/hashfuncs.h" -#include "core/templates/list.h" +#include "core/templates/paged_allocator.h" +#include "core/templates/pair.h" /** - * @class HashMap + * A HashMap implementation that uses open addressing with Robin Hood hashing. + * Robin Hood hashing swaps out entries that have a smaller probing distance + * than the to-be-inserted entry, that evens out the average probing distance + * and enables faster lookups. Backward shift deletion is employed to further + * improve the performance and to avoid infinite loops in rare cases. * - * Implementation of a standard Hashing HashMap, for quick lookups of Data associated with a Key. - * The implementation provides hashers for the default types, if you need a special kind of hasher, provide - * your own. - * @param TKey Key, search is based on it, needs to be hasheable. It is unique in this container. - * @param TData Data, data associated with the key - * @param Hasher Hasher object, needs to provide a valid static hash function for TKey - * @param Comparator comparator object, needs to be able to safely compare two TKey values. - * It needs to ensure that x == x for any items inserted in the map. Bear in mind that nan != nan when implementing an equality check. - * @param MIN_HASH_TABLE_POWER Miminum size of the hash table, as a power of two. You rarely need to change this parameter. - * @param RELATIONSHIP Relationship at which the hash table is resized. if amount of elements is RELATIONSHIP - * times bigger than the hash table, table is resized to solve this condition. if RELATIONSHIP is zero, table is always MIN_HASH_TABLE_POWER. + * Keys and values are stored in a double linked list by insertion order. This + * has a slight performance overhead on lookup, which can be mostly compensated + * using a paged allocator if required. * + * The assignment operator copy the pairs from one map to the other. */ -template <class TKey, class TData, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<TKey>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8> +template <class TKey, class TValue> +struct HashMapElement { + HashMapElement *next = nullptr; + HashMapElement *prev = nullptr; + KeyValue<TKey, TValue> data; + HashMapElement() {} + HashMapElement(const TKey &p_key, const TValue &p_value) : + data(p_key, p_value) {} +}; + +template <class TKey, class TValue, + class Hasher = HashMapHasherDefault, + class Comparator = HashMapComparatorDefault<TKey>, + class Allocator = DefaultTypedAllocator<HashMapElement<TKey, TValue>>> class HashMap { public: - struct Pair { - TKey key; - TData data; + const uint32_t MIN_CAPACITY_INDEX = 2; // Use a prime. + const float MAX_OCCUPANCY = 0.75; + const uint32_t EMPTY_HASH = 0; - Pair(const TKey &p_key) : - key(p_key), - data() {} - Pair(const TKey &p_key, const TData &p_data) : - key(p_key), - data(p_data) { - } - }; +private: + Allocator element_alloc; + HashMapElement<TKey, TValue> **elements = nullptr; + uint32_t *hashes = nullptr; + HashMapElement<TKey, TValue> *head_element = nullptr; + HashMapElement<TKey, TValue> *tail_element = nullptr; - struct Element { - private: - friend class HashMap; + uint32_t capacity_index = 0; + uint32_t num_elements = 0; - uint32_t hash = 0; - Element *next = nullptr; - Element() {} - Pair pair; + _FORCE_INLINE_ uint32_t _hash(const TKey &p_key) const { + uint32_t hash = Hasher::hash(p_key); - public: - const TKey &key() const { - return pair.key; + if (unlikely(hash == EMPTY_HASH)) { + hash = EMPTY_HASH + 1; } - TData &value() { - return pair.data; - } + return hash; + } - const TData &value() const { - return pair.value(); + _FORCE_INLINE_ uint32_t _get_probe_length(uint32_t p_pos, uint32_t p_hash, uint32_t p_capacity) const { + uint32_t original_pos = p_hash % p_capacity; + return (p_pos - original_pos + p_capacity) % p_capacity; + } + + bool _lookup_pos(const TKey &p_key, uint32_t &r_pos) const { + if (elements == nullptr) { + return false; // Failed lookups, no elements } - Element(const TKey &p_key) : - pair(p_key) {} - Element(const Element &p_other) : - hash(p_other.hash), - pair(p_other.pair.key, p_other.pair.data) {} - }; + uint32_t capacity = hash_table_size_primes[capacity_index]; + uint32_t hash = _hash(p_key); + uint32_t pos = hash % capacity; + uint32_t distance = 0; -private: - Element **hash_table = nullptr; - uint8_t hash_table_power = 0; - uint32_t elements = 0; + while (true) { + if (hashes[pos] == EMPTY_HASH) { + return false; + } - void make_hash_table() { - ERR_FAIL_COND(hash_table); + if (distance > _get_probe_length(pos, hashes[pos], capacity)) { + return false; + } - hash_table = memnew_arr(Element *, (1 << MIN_HASH_TABLE_POWER)); + if (hashes[pos] == hash && Comparator::compare(elements[pos]->data.key, p_key)) { + r_pos = pos; + return true; + } - hash_table_power = MIN_HASH_TABLE_POWER; - elements = 0; - for (int i = 0; i < (1 << MIN_HASH_TABLE_POWER); i++) { - hash_table[i] = nullptr; + pos = (pos + 1) % capacity; + distance++; } } - void erase_hash_table() { - ERR_FAIL_COND_MSG(elements, "Cannot erase hash table if there are still elements inside."); - - memdelete_arr(hash_table); - hash_table = nullptr; - hash_table_power = 0; - elements = 0; - } + void _insert_with_hash(uint32_t p_hash, HashMapElement<TKey, TValue> *p_value) { + uint32_t capacity = hash_table_size_primes[capacity_index]; + uint32_t hash = p_hash; + HashMapElement<TKey, TValue> *value = p_value; + uint32_t distance = 0; + uint32_t pos = hash % capacity; - void check_hash_table() { - int new_hash_table_power = -1; + while (true) { + if (hashes[pos] == EMPTY_HASH) { + elements[pos] = value; + hashes[pos] = hash; - if ((int)elements > ((1 << hash_table_power) * RELATIONSHIP)) { - /* rehash up */ - new_hash_table_power = hash_table_power + 1; + num_elements++; - while ((int)elements > ((1 << new_hash_table_power) * RELATIONSHIP)) { - new_hash_table_power++; + return; } - } else if ((hash_table_power > (int)MIN_HASH_TABLE_POWER) && ((int)elements < ((1 << (hash_table_power - 1)) * RELATIONSHIP))) { - /* rehash down */ - new_hash_table_power = hash_table_power - 1; - - while ((int)elements < ((1 << (new_hash_table_power - 1)) * RELATIONSHIP)) { - new_hash_table_power--; + // Not an empty slot, let's check the probing length of the existing one. + uint32_t existing_probe_len = _get_probe_length(pos, hashes[pos], capacity); + if (existing_probe_len < distance) { + SWAP(hash, hashes[pos]); + SWAP(value, elements[pos]); + distance = existing_probe_len; } - if (new_hash_table_power < (int)MIN_HASH_TABLE_POWER) { - new_hash_table_power = MIN_HASH_TABLE_POWER; - } + pos = (pos + 1) % capacity; + distance++; } + } - if (new_hash_table_power == -1) { - return; - } + void _resize_and_rehash(uint32_t p_new_capacity_index) { + uint32_t old_capacity = hash_table_size_primes[capacity_index]; - Element **new_hash_table = memnew_arr(Element *, ((uint64_t)1 << new_hash_table_power)); - ERR_FAIL_COND_MSG(!new_hash_table, "Out of memory."); + // Capacity can't be 0. + capacity_index = MAX((uint32_t)MIN_CAPACITY_INDEX, p_new_capacity_index); - for (int i = 0; i < (1 << new_hash_table_power); i++) { - new_hash_table[i] = nullptr; - } + uint32_t capacity = hash_table_size_primes[capacity_index]; - if (hash_table) { - for (int i = 0; i < (1 << hash_table_power); i++) { - while (hash_table[i]) { - Element *se = hash_table[i]; - hash_table[i] = se->next; - int new_pos = se->hash & ((1 << new_hash_table_power) - 1); - se->next = new_hash_table[new_pos]; - new_hash_table[new_pos] = se; - } - } + HashMapElement<TKey, TValue> **old_elements = elements; + uint32_t *old_hashes = hashes; - memdelete_arr(hash_table); - } - hash_table = new_hash_table; - hash_table_power = new_hash_table_power; - } + num_elements = 0; + hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity)); + elements = reinterpret_cast<HashMapElement<TKey, TValue> **>(Memory::alloc_static(sizeof(HashMapElement<TKey, TValue> *) * capacity)); - /* I want to have only one function.. */ - _FORCE_INLINE_ const Element *get_element(const TKey &p_key) const { - uint32_t hash = Hasher::hash(p_key); - uint32_t index = hash & ((1 << hash_table_power) - 1); + for (uint32_t i = 0; i < capacity; i++) { + hashes[i] = 0; + elements[i] = nullptr; + } - Element *e = hash_table[index]; + if (old_capacity == 0) { + // Nothing to do. + return; + } - while (e) { - /* checking hash first avoids comparing key, which may take longer */ - if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) { - /* the pair exists in this hashtable, so just update data */ - return e; + for (uint32_t i = 0; i < old_capacity; i++) { + if (old_hashes[i] == EMPTY_HASH) { + continue; } - e = e->next; + _insert_with_hash(old_hashes[i], old_elements[i]); } - return nullptr; + Memory::free_static(old_elements); + Memory::free_static(old_hashes); } - Element *create_element(const TKey &p_key) { - /* if element doesn't exist, create it */ - Element *e = memnew(Element(p_key)); - ERR_FAIL_COND_V_MSG(!e, nullptr, "Out of memory."); - uint32_t hash = Hasher::hash(p_key); - uint32_t index = hash & ((1 << hash_table_power) - 1); - e->next = hash_table[index]; - e->hash = hash; - - hash_table[index] = e; - elements++; + _FORCE_INLINE_ HashMapElement<TKey, TValue> *_insert(const TKey &p_key, const TValue &p_value, bool p_front_insert = false) { + uint32_t capacity = hash_table_size_primes[capacity_index]; + if (unlikely(elements == nullptr)) { + // Allocate on demand to save memory. - return e; - } + hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity)); + elements = reinterpret_cast<HashMapElement<TKey, TValue> **>(Memory::alloc_static(sizeof(HashMapElement<TKey, TValue> *) * capacity)); - void copy_from(const HashMap &p_t) { - if (&p_t == this) { - return; /* much less bother with that */ - } - - clear(); - - if (!p_t.hash_table || p_t.hash_table_power == 0) { - return; /* not copying from empty table */ + for (uint32_t i = 0; i < capacity; i++) { + hashes[i] = EMPTY_HASH; + elements[i] = nullptr; + } } - hash_table = memnew_arr(Element *, (uint64_t)1 << p_t.hash_table_power); - hash_table_power = p_t.hash_table_power; - elements = p_t.elements; + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); - for (int i = 0; i < (1 << p_t.hash_table_power); i++) { - hash_table[i] = nullptr; - - const Element *e = p_t.hash_table[i]; - - while (e) { - Element *le = memnew(Element(*e)); /* local element */ + if (exists) { + elements[pos]->data.value = p_value; + return elements[pos]; + } else { + if (num_elements + 1 > MAX_OCCUPANCY * capacity) { + ERR_FAIL_COND_V_MSG(capacity_index + 1 == HASH_TABLE_SIZE_MAX, nullptr, "Hash table maximum capacity reached, aborting insertion."); + _resize_and_rehash(capacity_index + 1); + } - /* add to list and reassign pointers */ - le->next = hash_table[i]; - hash_table[i] = le; + HashMapElement<TKey, TValue> *elem = element_alloc.new_allocation(HashMapElement<TKey, TValue>(p_key, p_value)); - e = e->next; + if (tail_element == nullptr) { + head_element = elem; + tail_element = elem; + } else if (p_front_insert) { + head_element->prev = elem; + elem->next = head_element; + head_element = elem; + } else { + tail_element->next = elem; + elem->prev = tail_element; + tail_element = elem; } + + uint32_t hash = _hash(p_key); + _insert_with_hash(hash, elem); + return elem; } } public: - Element *set(const TKey &p_key, const TData &p_data) { - return set(Pair(p_key, p_data)); - } + _FORCE_INLINE_ uint32_t get_capacity() const { return hash_table_size_primes[capacity_index]; } + _FORCE_INLINE_ uint32_t size() const { return num_elements; } - Element *set(const Pair &p_pair) { - Element *e = nullptr; - if (!hash_table) { - make_hash_table(); // if no table, make one - } else { - e = const_cast<Element *>(get_element(p_pair.key)); - } + /* Standard Godot Container API */ - /* if we made it up to here, the pair doesn't exist, create and assign */ + bool is_empty() const { + return num_elements == 0; + } - if (!e) { - e = create_element(p_pair.key); - if (!e) { - return nullptr; - } - check_hash_table(); // perform mantenience routine + void clear() { + if (elements == nullptr) { + return; } + uint32_t capacity = hash_table_size_primes[capacity_index]; + for (uint32_t i = 0; i < capacity; i++) { + if (hashes[i] == EMPTY_HASH) { + continue; + } - e->pair.data = p_pair.data; - return e; - } + hashes[i] = EMPTY_HASH; + element_alloc.delete_allocation(elements[i]); + elements[i] = nullptr; + } - bool has(const TKey &p_key) const { - return getptr(p_key) != nullptr; + tail_element = nullptr; + head_element = nullptr; + num_elements = 0; } - /** - * Get a key from data, return a const reference. - * WARNING: this doesn't check errors, use either getptr and check nullptr, or check - * first with has(key) - */ - - const TData &get(const TKey &p_key) const { - const TData *res = getptr(p_key); - CRASH_COND_MSG(!res, "Map key not found."); - return *res; + TValue &get(const TKey &p_key) { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); + CRASH_COND_MSG(!exists, "HashMap key not found."); + return elements[pos]->data.value; } - TData &get(const TKey &p_key) { - TData *res = getptr(p_key); - CRASH_COND_MSG(!res, "Map key not found."); - return *res; + const TValue &get(const TKey &p_key) const { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); + CRASH_COND_MSG(!exists, "HashMap key not found."); + return elements[pos]->data.value; } - /** - * Same as get, except it can return nullptr when item was not found. - * This is mainly used for speed purposes. - */ + const TValue *getptr(const TKey &p_key) const { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); - _FORCE_INLINE_ TData *getptr(const TKey &p_key) { - if (unlikely(!hash_table)) { - return nullptr; + if (exists) { + return &elements[pos]->data.value; } + return nullptr; + } - Element *e = const_cast<Element *>(get_element(p_key)); + TValue *getptr(const TKey &p_key) { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); - if (e) { - return &e->pair.data; + if (exists) { + return &elements[pos]->data.value; } - return nullptr; } - _FORCE_INLINE_ const TData *getptr(const TKey &p_key) const { - if (unlikely(!hash_table)) { - return nullptr; - } + _FORCE_INLINE_ bool has(const TKey &p_key) const { + uint32_t _pos = 0; + return _lookup_pos(p_key, _pos); + } - const Element *e = const_cast<Element *>(get_element(p_key)); + bool erase(const TKey &p_key) { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); - if (e) { - return &e->pair.data; + if (!exists) { + return false; } - return nullptr; - } + uint32_t capacity = hash_table_size_primes[capacity_index]; + uint32_t next_pos = (pos + 1) % capacity; + while (hashes[next_pos] != EMPTY_HASH && _get_probe_length(next_pos, hashes[next_pos], capacity) != 0) { + SWAP(hashes[next_pos], hashes[pos]); + SWAP(elements[next_pos], elements[pos]); + pos = next_pos; + next_pos = (pos + 1) % capacity; + } - /** - * Same as get, except it can return nullptr when item was not found. - * This version is custom, will take a hash and a custom key (that should support operator==() - */ + hashes[pos] = EMPTY_HASH; - template <class C> - _FORCE_INLINE_ TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) { - if (unlikely(!hash_table)) { - return nullptr; + if (head_element == elements[pos]) { + head_element = elements[pos]->next; } - uint32_t hash = p_custom_hash; - uint32_t index = hash & ((1 << hash_table_power) - 1); - - Element *e = hash_table[index]; + if (tail_element == elements[pos]) { + tail_element = elements[pos]->prev; + } - while (e) { - /* checking hash first avoids comparing key, which may take longer */ - if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) { - /* the pair exists in this hashtable, so just update data */ - return &e->pair.data; - } + if (elements[pos]->prev) { + elements[pos]->prev->next = elements[pos]->next; + } - e = e->next; + if (elements[pos]->next) { + elements[pos]->next->prev = elements[pos]->prev; } - return nullptr; + element_alloc.delete_allocation(elements[pos]); + elements[pos] = nullptr; + + num_elements--; + return true; } - template <class C> - _FORCE_INLINE_ const TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) const { - if (unlikely(!hash_table)) { - return nullptr; + // Reserves space for a number of elements, useful to avoid many resizes and rehashes. + // If adding a known (possibly large) number of elements at once, must be larger than old capacity. + void reserve(uint32_t p_new_capacity) { + uint32_t new_index = capacity_index; + + while (hash_table_size_primes[new_index] < p_new_capacity) { + ERR_FAIL_COND_MSG(new_index + 1 == (uint32_t)HASH_TABLE_SIZE_MAX, nullptr); + new_index++; } - uint32_t hash = p_custom_hash; - uint32_t index = hash & ((1 << hash_table_power) - 1); + if (new_index == capacity_index) { + return; + } - const Element *e = hash_table[index]; + if (elements == nullptr) { + capacity_index = new_index; + return; // Unallocated yet. + } + _resize_and_rehash(new_index); + } - while (e) { - /* checking hash first avoids comparing key, which may take longer */ - if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) { - /* the pair exists in this hashtable, so just update data */ - return &e->pair.data; - } + /** Iterator API **/ - e = e->next; + struct ConstIterator { + _FORCE_INLINE_ const KeyValue<TKey, TValue> &operator*() const { + return E->data; + } + _FORCE_INLINE_ const KeyValue<TKey, TValue> *operator->() const { return &E->data; } + _FORCE_INLINE_ ConstIterator &operator++() { + if (E) { + E = E->next; + } + return *this; + } + _FORCE_INLINE_ ConstIterator &operator--() { + if (E) { + E = E->prev; + } + return *this; } - return nullptr; - } + _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; } + _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; } - /** - * Erase an item, return true if erasing was successful - */ + _FORCE_INLINE_ explicit operator bool() const { + return E != nullptr; + } - bool erase(const TKey &p_key) { - if (unlikely(!hash_table)) { - return false; + _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; } - uint32_t hash = Hasher::hash(p_key); - uint32_t index = hash & ((1 << hash_table_power) - 1); - - Element *e = hash_table[index]; - Element *p = nullptr; - while (e) { - /* checking hash first avoids comparing key, which may take longer */ - if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) { - if (p) { - p->next = e->next; - } else { - //begin of list - hash_table[index] = e->next; - } - - memdelete(e); - elements--; - - if (elements == 0) { - erase_hash_table(); - } else { - check_hash_table(); - } - return true; + private: + const HashMapElement<TKey, TValue> *E = nullptr; + }; + + struct Iterator { + _FORCE_INLINE_ KeyValue<TKey, TValue> &operator*() const { + return E->data; + } + _FORCE_INLINE_ KeyValue<TKey, TValue> *operator->() const { return &E->data; } + _FORCE_INLINE_ Iterator &operator++() { + if (E) { + E = E->next; + } + return *this; + } + _FORCE_INLINE_ Iterator &operator--() { + if (E) { + E = E->prev; } + return *this; + } - p = e; - e = e->next; + _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_ explicit operator bool() const { + return E != nullptr; } - return false; - } + _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); + } - inline const TData &operator[](const TKey &p_key) const { //constref + private: + HashMapElement<TKey, TValue> *E = nullptr; + }; - return get(p_key); + _FORCE_INLINE_ Iterator begin() { + return Iterator(head_element); + } + _FORCE_INLINE_ Iterator end() { + return Iterator(nullptr); + } + _FORCE_INLINE_ Iterator last() { + return Iterator(tail_element); } - inline TData &operator[](const TKey &p_key) { //assignment - Element *e = nullptr; - if (!hash_table) { - make_hash_table(); // if no table, make one - } else { - e = const_cast<Element *>(get_element(p_key)); + _FORCE_INLINE_ Iterator find(const TKey &p_key) { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); + if (!exists) { + return end(); } + return Iterator(elements[pos]); + } - /* if we made it up to here, the pair doesn't exist, create */ - if (!e) { - e = create_element(p_key); - CRASH_COND(!e); - check_hash_table(); // perform mantenience routine + _FORCE_INLINE_ void remove(const Iterator &p_iter) { + if (p_iter) { + erase(p_iter->key); } + } - return e->pair.data; + _FORCE_INLINE_ ConstIterator begin() const { + return ConstIterator(head_element); + } + _FORCE_INLINE_ ConstIterator end() const { + return ConstIterator(nullptr); + } + _FORCE_INLINE_ ConstIterator last() const { + return ConstIterator(tail_element); } - /** - * Get the next key to p_key, and the first key if p_key is null. - * Returns a pointer to the next key if found, nullptr otherwise. - * Adding/Removing elements while iterating will, of course, have unexpected results, don't do it. - * - * Example: - * - * const TKey *k=nullptr; - * - * while( (k=table.next(k)) ) { - * - * print( *k ); - * } - * - */ - const TKey *next(const TKey *p_key) const { - if (unlikely(!hash_table)) { - return nullptr; + _FORCE_INLINE_ ConstIterator find(const TKey &p_key) const { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); + if (!exists) { + return end(); } + return ConstIterator(elements[pos]); + } - if (!p_key) { /* get the first key */ - - for (int i = 0; i < (1 << hash_table_power); i++) { - if (hash_table[i]) { - return &hash_table[i]->pair.key; - } - } - - } else { /* get the next key */ + /* Indexing */ - const Element *e = get_element(*p_key); - ERR_FAIL_COND_V_MSG(!e, nullptr, "Invalid key supplied."); - if (e->next) { - /* if there is a "next" in the list, return that */ - return &e->next->pair.key; - } else { - /* go to next elements */ - uint32_t index = e->hash & ((1 << hash_table_power) - 1); - index++; - for (int i = index; i < (1 << hash_table_power); i++) { - if (hash_table[i]) { - return &hash_table[i]->pair.key; - } - } - } + const TValue &operator[](const TKey &p_key) const { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); + CRASH_COND(!exists); + return elements[pos]->data.value; + } - /* nothing found, was at end */ + TValue &operator[](const TKey &p_key) { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); + if (!exists) { + return _insert(p_key, TValue())->data.value; + } else { + return elements[pos]->data.value; } - - return nullptr; /* nothing found */ } - inline unsigned int size() const { - return elements; - } + /* Insert */ - inline bool is_empty() const { - return elements == 0; + Iterator insert(const TKey &p_key, const TValue &p_value, bool p_front_insert = false) { + return Iterator(_insert(p_key, p_value, p_front_insert)); } - void clear() { - /* clean up */ - if (hash_table) { - for (int i = 0; i < (1 << hash_table_power); i++) { - while (hash_table[i]) { - Element *e = hash_table[i]; - hash_table[i] = e->next; - memdelete(e); - } - } + /* Constructors */ - memdelete_arr(hash_table); + HashMap(const HashMap &p_other) { + reserve(hash_table_size_primes[p_other.capacity_index]); + + if (p_other.num_elements == 0) { + return; } - hash_table = nullptr; - hash_table_power = 0; - elements = 0; + for (const KeyValue<TKey, TValue> &E : p_other) { + insert(E.key, E.value); + } } - void operator=(const HashMap &p_table) { - copy_from(p_table); - } + void operator=(const HashMap &p_other) { + if (this == &p_other) { + return; // Ignore self assignment. + } + if (num_elements != 0) { + clear(); + } - void get_key_list(List<TKey> *r_keys) const { - if (unlikely(!hash_table)) { - return; + reserve(hash_table_size_primes[p_other.capacity_index]); + + if (p_other.elements == nullptr) { + return; // Nothing to copy. } - for (int i = 0; i < (1 << hash_table_power); i++) { - Element *e = hash_table[i]; - while (e) { - r_keys->push_back(e->pair.key); - e = e->next; - } + + for (const KeyValue<TKey, TValue> &E : p_other) { + insert(E.key, E.value); } } - HashMap() {} + HashMap(uint32_t p_initial_capacity) { + // Capacity can't be 0. + capacity_index = 0; + reserve(p_initial_capacity); + } + HashMap() { + capacity_index = MIN_CAPACITY_INDEX; + } - HashMap(const HashMap &p_table) { - copy_from(p_table); + uint32_t debug_get_hash(uint32_t p_index) { + if (num_elements == 0) { + return 0; + } + ERR_FAIL_INDEX_V(p_index, get_capacity(), 0); + return hashes[p_index]; + } + Iterator debug_get_element(uint32_t p_index) { + if (num_elements == 0) { + return Iterator(); + } + ERR_FAIL_INDEX_V(p_index, get_capacity(), Iterator()); + return Iterator(elements[p_index]); } ~HashMap() { clear(); + + if (elements != nullptr) { + Memory::free_static(elements); + Memory::free_static(hashes); + } } }; diff --git a/core/templates/hashfuncs.h b/core/templates/hashfuncs.h index 2a129f97d5..1330d55270 100644 --- a/core/templates/hashfuncs.h +++ b/core/templates/hashfuncs.h @@ -31,14 +31,22 @@ #ifndef HASHFUNCS_H #define HASHFUNCS_H +#include "core/math/aabb.h" #include "core/math/math_defs.h" #include "core/math/math_funcs.h" +#include "core/math/rect2.h" +#include "core/math/rect2i.h" +#include "core/math/vector2.h" +#include "core/math/vector2i.h" +#include "core/math/vector3.h" +#include "core/math/vector3i.h" #include "core/object/object_id.h" #include "core/string/node_path.h" #include "core/string/string_name.h" #include "core/string/ustring.h" #include "core/templates/rid.h" #include "core/typedefs.h" + /** * Hashing functions */ @@ -155,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); } @@ -178,6 +189,55 @@ 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); + } + static _FORCE_INLINE_ uint32_t hash(const Vector3i &p_vec) { + uint32_t h = hash_djb2_one_32(p_vec.x); + h = hash_djb2_one_32(p_vec.y, h); + return hash_djb2_one_32(p_vec.z, h); + } + + static _FORCE_INLINE_ uint32_t hash(const Vector2 &p_vec) { + uint32_t h = hash_djb2_one_float(p_vec.x); + return hash_djb2_one_float(p_vec.y, h); + } + static _FORCE_INLINE_ uint32_t hash(const Vector3 &p_vec) { + uint32_t h = hash_djb2_one_float(p_vec.x); + h = hash_djb2_one_float(p_vec.y, h); + return hash_djb2_one_float(p_vec.z, h); + } + + static _FORCE_INLINE_ uint32_t hash(const Rect2i &p_rect) { + uint32_t h = hash_djb2_one_32(p_rect.position.x); + h = hash_djb2_one_32(p_rect.position.y, h); + h = hash_djb2_one_32(p_rect.size.x, h); + return hash_djb2_one_32(p_rect.size.y, h); + } + + static _FORCE_INLINE_ uint32_t hash(const Rect2 &p_rect) { + uint32_t h = hash_djb2_one_float(p_rect.position.x); + h = hash_djb2_one_float(p_rect.position.y, h); + h = hash_djb2_one_float(p_rect.size.x, h); + return hash_djb2_one_float(p_rect.size.y, h); + } + + static _FORCE_INLINE_ uint32_t hash(const AABB &p_aabb) { + uint32_t h = hash_djb2_one_float(p_aabb.position.x); + h = hash_djb2_one_float(p_aabb.position.y, h); + h = hash_djb2_one_float(p_aabb.position.z, h); + h = hash_djb2_one_float(p_aabb.size.x, h); + h = hash_djb2_one_float(p_aabb.size.y, h); + return hash_djb2_one_float(p_aabb.size.z, h); + } + //static _FORCE_INLINE_ uint32_t hash(const void* p_ptr) { return uint32_t(uint64_t(p_ptr))*(0x9e3779b1L); } }; @@ -186,14 +246,68 @@ 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] = { + 5, + 13, + 23, + 47, + 97, + 193, + 389, + 769, + 1543, + 3079, + 6151, + 12289, + 24593, + 49157, + 98317, + 196613, + 393241, + 786433, + 1572869, + 3145739, + 6291469, + 12582917, + 25165843, + 50331653, + 100663319, + 201326611, + 402653189, + 805306457, + 1610612741, +}; + #endif // HASHFUNCS_H diff --git a/core/templates/ordered_hash_map.h b/core/templates/ordered_hash_map.h deleted file mode 100644 index 3d1f3a08ec..0000000000 --- a/core/templates/ordered_hash_map.h +++ /dev/null @@ -1,301 +0,0 @@ -/*************************************************************************/ -/* ordered_hash_map.h */ -/*************************************************************************/ -/* This file is part of: */ -/* GODOT ENGINE */ -/* https://godotengine.org */ -/*************************************************************************/ -/* Copyright (c) 2007-2022 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2022 Godot Engine contributors (cf. AUTHORS.md). */ -/* */ -/* Permission is hereby granted, free of charge, to any person obtaining */ -/* a copy of this software and associated documentation files (the */ -/* "Software"), to deal in the Software without restriction, including */ -/* without limitation the rights to use, copy, modify, merge, publish, */ -/* distribute, sublicense, and/or sell copies of the Software, and to */ -/* permit persons to whom the Software is furnished to do so, subject to */ -/* the following conditions: */ -/* */ -/* The above copyright notice and this permission notice shall be */ -/* included in all copies or substantial portions of the Software. */ -/* */ -/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ -/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ -/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ -/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ -/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ -/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ -/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ -/*************************************************************************/ - -#ifndef ORDERED_HASH_MAP_H -#define ORDERED_HASH_MAP_H - -#include "core/templates/hash_map.h" -#include "core/templates/list.h" -#include "core/templates/pair.h" - -/** - * A hash map which allows to iterate elements in insertion order. - * Insertion, lookup, deletion have O(1) complexity. - * The API aims to be consistent with Map rather than HashMap, because the - * former is more frequently used and is more coherent with the rest of the - * codebase. - * Deletion during iteration is safe and will preserve the order. - */ -template <class K, class V, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<K>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8> -class OrderedHashMap { - typedef List<Pair<const K *, V>> InternalList; - typedef HashMap<K, typename InternalList::Element *, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP> InternalMap; - - InternalList list; - InternalMap map; - -public: - class Element { - friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>; - - typename InternalList::Element *list_element = nullptr; - typename InternalList::Element *prev_element = nullptr; - typename InternalList::Element *next_element = nullptr; - - Element(typename InternalList::Element *p_element) { - list_element = p_element; - - if (list_element) { - next_element = list_element->next(); - prev_element = list_element->prev(); - } - } - - public: - _FORCE_INLINE_ Element() {} - - Element next() const { - return Element(next_element); - } - - Element prev() const { - return Element(prev_element); - } - - Element(const Element &other) : - list_element(other.list_element), - prev_element(other.prev_element), - next_element(other.next_element) { - } - - void operator=(const Element &other) { - list_element = other.list_element; - next_element = other.next_element; - prev_element = other.prev_element; - } - - _FORCE_INLINE_ bool operator==(const Element &p_other) const { - return this->list_element == p_other.list_element; - } - _FORCE_INLINE_ bool operator!=(const Element &p_other) const { - return this->list_element != p_other.list_element; - } - - operator bool() const { - return (list_element != nullptr); - } - - const K &key() const { - CRASH_COND(!list_element); - return *(list_element->get().first); - } - - V &value() { - CRASH_COND(!list_element); - return list_element->get().second; - } - - const V &value() const { - CRASH_COND(!list_element); - return list_element->get().second; - } - - V &get() { - CRASH_COND(!list_element); - return list_element->get().second; - } - - const V &get() const { - CRASH_COND(!list_element); - return list_element->get().second; - } - }; - - class ConstElement { - friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>; - - const typename InternalList::Element *list_element = nullptr; - - ConstElement(const typename InternalList::Element *p_element) : - list_element(p_element) { - } - - public: - _FORCE_INLINE_ ConstElement() {} - - ConstElement(const ConstElement &other) : - list_element(other.list_element) { - } - - void operator=(const ConstElement &other) { - list_element = other.list_element; - } - - ConstElement next() const { - return ConstElement(list_element ? list_element->next() : nullptr); - } - - ConstElement prev() const { - return ConstElement(list_element ? list_element->prev() : nullptr); - } - - _FORCE_INLINE_ bool operator==(const ConstElement &p_other) const { - return this->list_element == p_other.list_element; - } - _FORCE_INLINE_ bool operator!=(const ConstElement &p_other) const { - return this->list_element != p_other.list_element; - } - - operator bool() const { - return (list_element != nullptr); - } - - const K &key() const { - CRASH_COND(!list_element); - return *(list_element->get().first); - } - - const V &value() const { - CRASH_COND(!list_element); - return list_element->get().second; - } - - const V &get() const { - CRASH_COND(!list_element); - return list_element->get().second; - } - }; - - ConstElement find(const K &p_key) const { - typename InternalList::Element *const *list_element = map.getptr(p_key); - if (list_element) { - return ConstElement(*list_element); - } - return ConstElement(nullptr); - } - - Element find(const K &p_key) { - typename InternalList::Element **list_element = map.getptr(p_key); - if (list_element) { - return Element(*list_element); - } - return Element(nullptr); - } - - Element insert(const K &p_key, const V &p_value) { - typename InternalList::Element **list_element = map.getptr(p_key); - if (list_element) { - (*list_element)->get().second = p_value; - return Element(*list_element); - } - // Incorrectly set the first value of the pair with a value that will - // be invalid as soon as we leave this function... - typename InternalList::Element *new_element = list.push_back(Pair<const K *, V>(&p_key, p_value)); - // ...this is needed here in case the hashmap recursively reference itself... - typename InternalMap::Element *e = map.set(p_key, new_element); - // ...now we can set the right value ! - new_element->get().first = &e->key(); - - return Element(new_element); - } - - void erase(Element &p_element) { - map.erase(p_element.key()); - list.erase(p_element.list_element); - p_element.list_element = nullptr; - } - - bool erase(const K &p_key) { - typename InternalList::Element **list_element = map.getptr(p_key); - if (list_element) { - list.erase(*list_element); - map.erase(p_key); - return true; - } - return false; - } - - inline bool has(const K &p_key) const { - return map.has(p_key); - } - - const V &operator[](const K &p_key) const { - ConstElement e = find(p_key); - CRASH_COND(!e); - return e.value(); - } - - V &operator[](const K &p_key) { - Element e = find(p_key); - if (!e) { - // consistent with Map behaviour - e = insert(p_key, V()); - } - return e.value(); - } - - inline Element front() { - return Element(list.front()); - } - - inline Element back() { - return Element(list.back()); - } - - inline ConstElement front() const { - return ConstElement(list.front()); - } - - inline ConstElement back() const { - return ConstElement(list.back()); - } - - inline bool is_empty() const { return list.is_empty(); } - inline int size() const { return list.size(); } - - const void *id() const { - return list.id(); - } - - void clear() { - map.clear(); - list.clear(); - } - -private: - void _copy_from(const OrderedHashMap &p_map) { - for (ConstElement E = p_map.front(); E; E = E.next()) { - insert(E.key(), E.value()); - } - } - -public: - void operator=(const OrderedHashMap &p_map) { - _copy_from(p_map); - } - - OrderedHashMap(const OrderedHashMap &p_map) { - _copy_from(p_map); - } - - _FORCE_INLINE_ OrderedHashMap() {} -}; - -#endif // ORDERED_HASH_MAP_H diff --git a/core/templates/paged_allocator.h b/core/templates/paged_allocator.h index b9067e2edd..cf5911a847 100644 --- a/core/templates/paged_allocator.h +++ b/core/templates/paged_allocator.h @@ -50,6 +50,10 @@ class PagedAllocator { SpinLock spin_lock; public: + enum { + DEFAULT_PAGE_SIZE = 4096 + }; + template <class... Args> T *alloc(const Args &&...p_args) { if (thread_safe) { @@ -121,7 +125,9 @@ public: page_shift = get_shift_from_power_of_2(page_size); } - PagedAllocator(uint32_t p_page_size = 4096) { // power of 2 recommended because of alignment with OS page sizes. Even if element is bigger, its still a multiple and get rounded amount of pages + // Power of 2 recommended because of alignment with OS page sizes. + // Even if element is bigger, it's still a multiple and gets rounded to amount of pages. + PagedAllocator(uint32_t p_page_size = DEFAULT_PAGE_SIZE) { configure(p_page_size); } 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/dictionary.cpp b/core/variant/dictionary.cpp index 0f2f8fc8ed..46543da2c2 100644 --- a/core/variant/dictionary.cpp +++ b/core/variant/dictionary.cpp @@ -30,7 +30,7 @@ #include "dictionary.h" -#include "core/templates/ordered_hash_map.h" +#include "core/templates/hash_map.h" #include "core/templates/safe_refcount.h" #include "core/variant/variant.h" // required in this order by VariantInternal, do not remove this comment. @@ -41,7 +41,7 @@ struct DictionaryPrivate { SafeRefCount refcount; - OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> variant_map; + HashMap<Variant, Variant, VariantHasher, VariantComparator> variant_map; }; void Dictionary::get_key_list(List<Variant> *p_keys) const { @@ -49,16 +49,16 @@ void Dictionary::get_key_list(List<Variant> *p_keys) const { return; } - for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) { - p_keys->push_back(E.key()); + for (const KeyValue<Variant, Variant> &E : _p->variant_map) { + p_keys->push_back(E.key); } } Variant Dictionary::get_key_at_index(int p_index) const { int index = 0; - for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) { + for (const KeyValue<Variant, Variant> &E : _p->variant_map) { if (index == p_index) { - return E.key(); + return E.key; } index++; } @@ -68,9 +68,9 @@ Variant Dictionary::get_key_at_index(int p_index) const { Variant Dictionary::get_value_at_index(int p_index) const { int index = 0; - for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) { + for (const KeyValue<Variant, Variant> &E : _p->variant_map) { if (index == p_index) { - return E.value(); + return E.value; } index++; } @@ -97,50 +97,50 @@ const Variant &Dictionary::operator[](const Variant &p_key) const { } const Variant *Dictionary::getptr(const Variant &p_key) const { - OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstElement E; + HashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstIterator E; if (p_key.get_type() == Variant::STRING_NAME) { const StringName *sn = VariantInternal::get_string_name(&p_key); - E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String()); + E = ((const HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String()); } else { - E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key); + E = ((const HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key); } if (!E) { return nullptr; } - return &E.get(); + return &E->value; } Variant *Dictionary::getptr(const Variant &p_key) { - OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E; + HashMap<Variant, Variant, VariantHasher, VariantComparator>::Iterator E; if (p_key.get_type() == Variant::STRING_NAME) { const StringName *sn = VariantInternal::get_string_name(&p_key); - E = ((OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String()); + E = ((HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String()); } else { - E = ((OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key); + E = ((HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key); } if (!E) { return nullptr; } - return &E.get(); + return &E->value; } Variant Dictionary::get_valid(const Variant &p_key) const { - OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstElement E; + HashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstIterator E; if (p_key.get_type() == Variant::STRING_NAME) { const StringName *sn = VariantInternal::get_string_name(&p_key); - E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String()); + E = ((const HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String()); } else { - E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key); + E = ((const HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key); } if (!E) { return Variant(); } - return E.get(); + return E->value; } Variant Dictionary::get(const Variant &p_key, const Variant &p_default) const { @@ -210,9 +210,9 @@ bool Dictionary::recursive_equal(const Dictionary &p_dictionary, int recursion_c return true; } recursion_count++; - for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstElement this_E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->front(); this_E; this_E = this_E.next()) { - OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstElement other_E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&p_dictionary._p->variant_map)->find(this_E.key()); - if (!other_E || !this_E.value().hash_compare(other_E.value(), recursion_count)) { + for (const KeyValue<Variant, Variant> &this_E : _p->variant_map) { + HashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstIterator other_E = ((const HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&p_dictionary._p->variant_map)->find(this_E.key); + if (!other_E || !this_E.value.hash_compare(other_E->value, recursion_count)) { return false; } } @@ -261,9 +261,9 @@ uint32_t Dictionary::recursive_hash(int recursion_count) const { uint32_t h = hash_djb2_one_32(Variant::DICTIONARY); recursion_count++; - for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) { - h = hash_djb2_one_32(E.key().recursive_hash(recursion_count), h); - h = hash_djb2_one_32(E.value().recursive_hash(recursion_count), h); + for (const KeyValue<Variant, Variant> &E : _p->variant_map) { + h = hash_djb2_one_32(E.key.recursive_hash(recursion_count), h); + h = hash_djb2_one_32(E.value.recursive_hash(recursion_count), h); } return h; @@ -278,8 +278,8 @@ Array Dictionary::keys() const { varr.resize(size()); int i = 0; - for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) { - varr[i] = E.key(); + for (const KeyValue<Variant, Variant> &E : _p->variant_map) { + varr[i] = E.key; i++; } @@ -295,8 +295,8 @@ Array Dictionary::values() const { varr.resize(size()); int i = 0; - for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) { - varr[i] = E.get(); + for (const KeyValue<Variant, Variant> &E : _p->variant_map) { + varr[i] = E.value; i++; } @@ -306,16 +306,23 @@ Array Dictionary::values() const { const Variant *Dictionary::next(const Variant *p_key) const { if (p_key == nullptr) { // caller wants to get the first element - if (_p->variant_map.front()) { - return &_p->variant_map.front().key(); + if (_p->variant_map.begin()) { + return &_p->variant_map.begin()->key; } return nullptr; } - OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.find(*p_key); + HashMap<Variant, Variant, VariantHasher, VariantComparator>::Iterator E = _p->variant_map.find(*p_key); - if (E && E.next()) { - return &E.next().key(); + if (!E) { + return nullptr; + } + + ++E; + + if (E) { + return &E->key; } + return nullptr; } @@ -333,12 +340,12 @@ Dictionary Dictionary::recursive_duplicate(bool p_deep, int recursion_count) con if (p_deep) { recursion_count++; - for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) { - n[E.key().recursive_duplicate(true, recursion_count)] = E.value().recursive_duplicate(true, recursion_count); + for (const KeyValue<Variant, Variant> &E : _p->variant_map) { + n[E.key.recursive_duplicate(true, recursion_count)] = E.value.recursive_duplicate(true, recursion_count); } } else { - for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) { - n[E.key()] = E.value(); + for (const KeyValue<Variant, Variant> &E : _p->variant_map) { + n[E.key] = E.value; } } diff --git a/core/variant/variant.h b/core/variant/variant.h index 475bf7158d..726ba120b5 100644 --- a/core/variant/variant.h +++ b/core/variant/variant.h @@ -473,6 +473,7 @@ public: OP_NEGATE, OP_POSITIVE, OP_MODULE, + OP_POWER, //bitwise OP_SHIFT_LEFT, OP_SHIFT_RIGHT, 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_construct.h b/core/variant/variant_construct.h index ce2e9af04f..638c0136f3 100644 --- a/core/variant/variant_construct.h +++ b/core/variant/variant_construct.h @@ -344,7 +344,7 @@ public: return; } - VariantTypeChanger<Array>::change(&r_ret); + r_ret = Array(); Array &dst_arr = *VariantGetInternalPtr<Array>::get_ptr(&r_ret); const T &src_arr = *VariantGetInternalPtr<T>::get_ptr(p_args[0]); @@ -356,7 +356,7 @@ public: } static inline void validated_construct(Variant *r_ret, const Variant **p_args) { - VariantTypeChanger<Array>::change(r_ret); + *r_ret = Array(); Array &dst_arr = *VariantGetInternalPtr<Array>::get_ptr(r_ret); const T &src_arr = *VariantGetInternalPtr<T>::get_ptr(p_args[0]); diff --git a/core/variant/variant_op.cpp b/core/variant/variant_op.cpp index 35e0319aa3..adace2b534 100644 --- a/core/variant/variant_op.cpp +++ b/core/variant/variant_op.cpp @@ -361,6 +361,11 @@ void Variant::_register_variant_operators() { register_op<OperatorEvaluatorStringModT<PackedVector3Array>>(Variant::OP_MODULE, Variant::STRING, Variant::PACKED_VECTOR3_ARRAY); register_op<OperatorEvaluatorStringModT<PackedColorArray>>(Variant::OP_MODULE, Variant::STRING, Variant::PACKED_COLOR_ARRAY); + register_op<OperatorEvaluatorPow<int64_t, int64_t, int64_t>>(Variant::OP_POWER, Variant::INT, Variant::INT); + register_op<OperatorEvaluatorPow<double, int64_t, double>>(Variant::OP_POWER, Variant::INT, Variant::FLOAT); + register_op<OperatorEvaluatorPow<double, double, double>>(Variant::OP_POWER, Variant::FLOAT, Variant::FLOAT); + register_op<OperatorEvaluatorPow<double, double, int64_t>>(Variant::OP_POWER, Variant::FLOAT, Variant::INT); + register_op<OperatorEvaluatorNeg<int64_t, int64_t>>(Variant::OP_NEGATE, Variant::INT, Variant::NIL); register_op<OperatorEvaluatorNeg<double, double>>(Variant::OP_NEGATE, Variant::FLOAT, Variant::NIL); register_op<OperatorEvaluatorNeg<Vector2, Vector2>>(Variant::OP_NEGATE, Variant::VECTOR2, Variant::NIL); @@ -929,6 +934,7 @@ static const char *_op_names[Variant::OP_MAX] = { "unary-", "unary+", "%", + "**", "<<", ">>", "&", diff --git a/core/variant/variant_op.h b/core/variant/variant_op.h index f72a92d31a..3e9bae1078 100644 --- a/core/variant/variant_op.h +++ b/core/variant/variant_op.h @@ -92,6 +92,24 @@ public: }; template <class R, class A, class B> +class OperatorEvaluatorPow { +public: + static void evaluate(const Variant &p_left, const Variant &p_right, Variant *r_ret, bool &r_valid) { + const A &a = *VariantGetInternalPtr<A>::get_ptr(&p_left); + const B &b = *VariantGetInternalPtr<B>::get_ptr(&p_right); + *r_ret = R(Math::pow((double)a, (double)b)); + r_valid = true; + } + static inline void validated_evaluate(const Variant *left, const Variant *right, Variant *r_ret) { + *VariantGetInternalPtr<R>::get_ptr(r_ret) = R(Math::pow((double)*VariantGetInternalPtr<A>::get_ptr(left), (double)*VariantGetInternalPtr<B>::get_ptr(right))); + } + static void ptr_evaluate(const void *left, const void *right, void *r_ret) { + PtrToArg<R>::encode(R(Math::pow((double)PtrToArg<A>::convert(left), (double)PtrToArg<B>::convert(right))), r_ret); + } + static Variant::Type get_return_type() { return GetTypeInfo<R>::VARIANT_TYPE; } +}; + +template <class R, class A, class B> class OperatorEvaluatorXForm { public: static void evaluate(const Variant &p_left, const Variant &p_right, Variant *r_ret, bool &r_valid) { 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: |