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<> --- tests/core/object/test_class_db.h | 29 +++--- tests/core/templates/test_hash_map.h | 133 ++++++++++++++++++++++++++ tests/core/templates/test_ordered_hash_map.h | 135 --------------------------- 3 files changed, 146 insertions(+), 151 deletions(-) create mode 100644 tests/core/templates/test_hash_map.h delete mode 100644 tests/core/templates/test_ordered_hash_map.h (limited to 'tests/core') diff --git a/tests/core/object/test_class_db.h b/tests/core/object/test_class_db.h index 5cf5403a50..2e316a7d95 100644 --- a/tests/core/object/test_class_db.h +++ b/tests/core/object/test_class_db.h @@ -173,7 +173,7 @@ struct NamesCache { } }; -typedef OrderedHashMap ExposedClasses; +typedef HashMap ExposedClasses; struct Context { Vector enum_types; @@ -183,13 +183,13 @@ struct Context { NamesCache names_cache; const ExposedClass *find_exposed_class(const StringName &p_name) const { - ExposedClasses::ConstElement elem = exposed_classes.find(p_name); - return elem ? &elem.value() : nullptr; + ExposedClasses::ConstIterator elem = exposed_classes.find(p_name); + return elem ? &elem->value : nullptr; } const ExposedClass *find_exposed_class(const TypeReference &p_type_ref) const { - ExposedClasses::ConstElement elem = exposed_classes.find(p_type_ref.name); - return elem ? &elem.value() : nullptr; + ExposedClasses::ConstIterator elem = exposed_classes.find(p_type_ref.name); + return elem ? &elem->value : nullptr; } bool has_type(const TypeReference &p_type_ref) const { @@ -676,12 +676,11 @@ void add_exposed_classes(Context &r_context) { // Add signals const HashMap &signal_map = class_info->signal_map; - const StringName *k = nullptr; - while ((k = signal_map.next(k))) { + for (const KeyValue &K : signal_map) { SignalData signal; - const MethodInfo &method_info = signal_map.get(*k); + const MethodInfo &method_info = signal_map.get(K.key); signal.name = method_info.name; @@ -734,14 +733,12 @@ void add_exposed_classes(Context &r_context) { ClassDB::get_integer_constant_list(class_name, &constants, true); const HashMap> &enum_map = class_info->enum_map; - k = nullptr; - while ((k = enum_map.next(k))) { + for (const KeyValue> &K : enum_map) { EnumData enum_; - enum_.name = *k; + enum_.name = K.key; - const List &enum_constants = enum_map.get(*k); - for (const StringName &E : enum_constants) { + for (const StringName &E : K.value) { const StringName &constant_name = E; TEST_FAIL_COND(String(constant_name).find("::") != -1, "Enum constant contains '::', check bindings to remove the scope: '", @@ -760,7 +757,7 @@ void add_exposed_classes(Context &r_context) { exposed_class.enums.push_back(enum_); - r_context.enum_types.push_back(String(class_name) + "." + String(*k)); + r_context.enum_types.push_back(String(class_name) + "." + String(K.key)); } for (const String &E : constants) { @@ -850,8 +847,8 @@ TEST_SUITE("[ClassDB]") { TEST_FAIL_COND(object_class->base != StringName(), "Object class derives from another class: '", object_class->base, "'."); - for (ExposedClasses::Element E = context.exposed_classes.front(); E; E = E.next()) { - validate_class(context, E.value()); + for (const KeyValue &E : context.exposed_classes) { + validate_class(context, E.value); } } } diff --git a/tests/core/templates/test_hash_map.h b/tests/core/templates/test_hash_map.h new file mode 100644 index 0000000000..7a3d5f5d47 --- /dev/null +++ b/tests/core/templates/test_hash_map.h @@ -0,0 +1,133 @@ +/*************************************************************************/ +/* test_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 TEST_HASH_MAP_H +#define TEST_HASH_MAP_H + +#include "core/templates/hash_map.h" + +#include "tests/test_macros.h" + +namespace TestHashMap { + +TEST_CASE("[HashMap] Insert element") { + HashMap map; + HashMap::Iterator e = map.insert(42, 84); + + CHECK(e); + CHECK(e->key == 42); + CHECK(e->value == 84); + CHECK(map[42] == 84); + CHECK(map.has(42)); + CHECK(map.find(42)); +} + +TEST_CASE("[HashMap] Overwrite element") { + HashMap map; + map.insert(42, 84); + map.insert(42, 1234); + + CHECK(map[42] == 1234); +} + +TEST_CASE("[HashMap] Erase via element") { + HashMap map; + HashMap::Iterator e = map.insert(42, 84); + map.remove(e); + CHECK(!map.has(42)); + CHECK(!map.find(42)); +} + +TEST_CASE("[HashMap] Erase via key") { + HashMap map; + map.insert(42, 84); + map.erase(42); + CHECK(!map.has(42)); + CHECK(!map.find(42)); +} + +TEST_CASE("[HashMap] Size") { + HashMap map; + map.insert(42, 84); + map.insert(123, 84); + map.insert(123, 84); + map.insert(0, 84); + map.insert(123485, 84); + + CHECK(map.size() == 4); +} + +TEST_CASE("[HashMap] Iteration") { + HashMap map; + map.insert(42, 84); + map.insert(123, 12385); + map.insert(0, 12934); + map.insert(123485, 1238888); + map.insert(123, 111111); + + Vector> expected; + expected.push_back(Pair(42, 84)); + expected.push_back(Pair(123, 111111)); + expected.push_back(Pair(0, 12934)); + expected.push_back(Pair(123485, 1238888)); + + int idx = 0; + for (const KeyValue &E : map) { + CHECK(expected[idx] == Pair(E.key, E.value)); + ++idx; + } +} + +TEST_CASE("[HashMap] Const iteration") { + HashMap map; + map.insert(42, 84); + map.insert(123, 12385); + map.insert(0, 12934); + map.insert(123485, 1238888); + map.insert(123, 111111); + + const HashMap const_map = map; + + Vector> expected; + expected.push_back(Pair(42, 84)); + expected.push_back(Pair(123, 111111)); + expected.push_back(Pair(0, 12934)); + expected.push_back(Pair(123485, 1238888)); + expected.push_back(Pair(123, 111111)); + + int idx = 0; + for (const KeyValue &E : const_map) { + CHECK(expected[idx] == Pair(E.key, E.value)); + ++idx; + } +} +} // namespace TestHashMap + +#endif // TEST_HASH_MAP_H diff --git a/tests/core/templates/test_ordered_hash_map.h b/tests/core/templates/test_ordered_hash_map.h deleted file mode 100644 index 08c5c9b72a..0000000000 --- a/tests/core/templates/test_ordered_hash_map.h +++ /dev/null @@ -1,135 +0,0 @@ -/*************************************************************************/ -/* test_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 TEST_ORDERED_HASH_MAP_H -#define TEST_ORDERED_HASH_MAP_H - -#include "core/templates/ordered_hash_map.h" - -#include "tests/test_macros.h" - -namespace TestOrderedHashMap { - -TEST_CASE("[OrderedHashMap] Insert element") { - OrderedHashMap map; - OrderedHashMap::Element e = map.insert(42, 84); - - CHECK(e); - CHECK(e.key() == 42); - CHECK(e.get() == 84); - CHECK(e.value() == 84); - CHECK(map[42] == 84); - CHECK(map.has(42)); - CHECK(map.find(42)); -} - -TEST_CASE("[OrderedHashMap] Overwrite element") { - OrderedHashMap map; - map.insert(42, 84); - map.insert(42, 1234); - - CHECK(map[42] == 1234); -} - -TEST_CASE("[OrderedHashMap] Erase via element") { - OrderedHashMap map; - OrderedHashMap::Element e = map.insert(42, 84); - - map.erase(e); - CHECK(!e); - CHECK(!map.has(42)); - CHECK(!map.find(42)); -} - -TEST_CASE("[OrderedHashMap] Erase via key") { - OrderedHashMap map; - map.insert(42, 84); - map.erase(42); - CHECK(!map.has(42)); - CHECK(!map.find(42)); -} - -TEST_CASE("[OrderedHashMap] Size") { - OrderedHashMap map; - map.insert(42, 84); - map.insert(123, 84); - map.insert(123, 84); - map.insert(0, 84); - map.insert(123485, 84); - - CHECK(map.size() == 4); -} - -TEST_CASE("[OrderedHashMap] Iteration") { - OrderedHashMap map; - map.insert(42, 84); - map.insert(123, 12385); - map.insert(0, 12934); - map.insert(123485, 1238888); - map.insert(123, 111111); - - Vector> expected; - expected.push_back(Pair(42, 84)); - expected.push_back(Pair(123, 111111)); - expected.push_back(Pair(0, 12934)); - expected.push_back(Pair(123485, 1238888)); - - int idx = 0; - for (OrderedHashMap::Element E = map.front(); E; E = E.next()) { - CHECK(expected[idx] == Pair(E.key(), E.value())); - ++idx; - } -} - -TEST_CASE("[OrderedHashMap] Const iteration") { - OrderedHashMap map; - map.insert(42, 84); - map.insert(123, 12385); - map.insert(0, 12934); - map.insert(123485, 1238888); - map.insert(123, 111111); - - const OrderedHashMap const_map = map; - - Vector> expected; - expected.push_back(Pair(42, 84)); - expected.push_back(Pair(123, 111111)); - expected.push_back(Pair(0, 12934)); - expected.push_back(Pair(123485, 1238888)); - - int idx = 0; - for (OrderedHashMap::ConstElement E = const_map.front(); E; E = E.next()) { - CHECK(expected[idx] == Pair(E.key(), E.value())); - ++idx; - } -} -} // namespace TestOrderedHashMap - -#endif // TEST_ORDERED_HASH_MAP_H -- cgit v1.2.3