From 8b7c7f5a753b43cec10f72b274bb1d70c253652b Mon Sep 17 00:00:00 2001 From: reduz Date: Sun, 8 May 2022 10:09:19 +0200 Subject: Add a new HashMap implementation Adds a new, cleaned up, HashMap implementation. * Uses Robin Hood Hashing (https://en.wikipedia.org/wiki/Hash_table#Robin_Hood_hashing). * Keeps elements in a double linked list for simpler, ordered, iteration. * Allows keeping iterators for later use in removal (Unlike Map<>, it does not do much for performance vs keeping the key, but helps replace old code). * Uses a more modern C++ iterator API, deprecates the old one. * Supports custom allocator (in case there is a wish to use a paged one). This class aims to unify all the associative template usage and replace it by this one: * Map<> (whereas key order does not matter, which is 99% of cases) * HashMap<> * OrderedHashMap<> * OAHashMap<> --- core/input/input_map.cpp | 40 ++++++++++++++++++++-------------------- 1 file changed, 20 insertions(+), 20 deletions(-) (limited to 'core/input/input_map.cpp') diff --git a/core/input/input_map.cpp b/core/input/input_map.cpp index ab94c00999..51c1cf9608 100644 --- a/core/input/input_map.cpp +++ b/core/input/input_map.cpp @@ -119,8 +119,8 @@ List InputMap::get_actions() const { return actions; } - for (OrderedHashMap::Element E = input_map.front(); E; E = E.next()) { - actions.push_back(E.key()); + for (const KeyValue &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> *InputMap::action_get_events(const StringName &p_action) { - const OrderedHashMap::Element E = input_map.find(p_action); + HashMap::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 &p_event, const StringName &p_action, bool p_exact_match) const { @@ -216,7 +216,7 @@ bool InputMap::event_is_action(const Ref &p_event, const StringName } bool InputMap::event_get_action_status(const Ref &p_event, const StringName &p_action, bool p_exact_match, bool *r_pressed, float *r_strength, float *r_raw_strength) const { - OrderedHashMap::Element E = input_map.find(p_action); + HashMap::Iterator E = input_map.find(p_action); ERR_FAIL_COND_V_MSG(!E, false, suggest_actions(p_action)); Ref input_event_action = p_event; @@ -235,11 +235,11 @@ bool InputMap::event_get_action_status(const Ref &p_event, const Str return input_event_action->get_action() == p_action; } - List>::Element *event = _find_event(E.get(), p_event, p_exact_match, r_pressed, r_strength, r_raw_strength); + List>::Element *event = _find_event(E->value, p_event, p_exact_match, r_pressed, r_strength, r_raw_strength); return event != nullptr; } -const OrderedHashMap &InputMap::get_action_map() const { +const HashMap &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>> &InputMap::get_builtins() { +const HashMap>> &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>> &InputMap::get_builtins() { return default_builtin_cache; } -const OrderedHashMap>> &InputMap::get_builtins_with_feature_overrides_applied() { +const HashMap>> &InputMap::get_builtins_with_feature_overrides_applied() { if (default_builtin_with_overrides_cache.size() > 0) { return default_builtin_with_overrides_cache; } - OrderedHashMap>> builtins = get_builtins(); + HashMap>> 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> builtins_with_overrides; - for (OrderedHashMap>>::Element E = builtins.front(); E; E = E.next()) { - String fullname = E.key(); + for (const KeyValue>> &E : builtins) { + String fullname = E.key; Vector split = fullname.split("."); String name = split[0]; @@ -709,8 +709,8 @@ const OrderedHashMap>> &InputMap::get_builtins_with } } - for (OrderedHashMap>>::Element E = builtins.front(); E; E = E.next()) { - String fullname = E.key(); + for (const KeyValue>> &E : builtins) { + String fullname = E.key; Vector split = fullname.split("."); String name = split[0]; @@ -726,22 +726,22 @@ const OrderedHashMap>> &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>> builtins = get_builtins_with_feature_overrides_applied(); + HashMap>> builtins = get_builtins_with_feature_overrides_applied(); - for (OrderedHashMap>>::Element E = builtins.front(); E; E = E.next()) { - String name = E.key(); + for (const KeyValue>> &E : builtins) { + String name = E.key; add_action(name); - List> inputs = E.get(); - for (List>::Element *I = inputs.front(); I; I = I->next()) { + const List> &inputs = E.value; + for (const List>::Element *I = inputs.front(); I; I = I->next()) { Ref iek = I->get(); // For the editor, only add keyboard actions. -- cgit v1.2.3