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<> --- modules/gdscript/editor/gdscript_highlighter.cpp | 5 ++-- modules/gdscript/gdscript_analyzer.cpp | 8 ++---- modules/gdscript/gdscript_byte_codegen.cpp | 6 ++-- modules/gdscript/gdscript_compiler.cpp | 2 +- modules/gdscript/gdscript_editor.cpp | 28 ++++++++----------- modules/gdscript/gdscript_parser.cpp | 26 ++++++++---------- modules/gdscript/gdscript_parser.h | 2 +- .../language_server/gdscript_extend_parser.cpp | 32 ++++++++-------------- .../language_server/gdscript_language_protocol.cpp | 32 ++++++++++++---------- .../language_server/gdscript_text_document.cpp | 18 ++++-------- .../language_server/gdscript_workspace.cpp | 18 ++++-------- modules/gdscript/tests/gdscript_test_runner.cpp | 10 +++---- 12 files changed, 78 insertions(+), 109 deletions(-) (limited to 'modules/gdscript') diff --git a/modules/gdscript/editor/gdscript_highlighter.cpp b/modules/gdscript/editor/gdscript_highlighter.cpp index e3f0ddfc35..191568661d 100644 --- a/modules/gdscript/editor/gdscript_highlighter.cpp +++ b/modules/gdscript/editor/gdscript_highlighter.cpp @@ -510,9 +510,8 @@ void GDScriptSyntaxHighlighter::_update_cache() { } /* Autoloads. */ - OrderedHashMap autoloads = ProjectSettings::get_singleton()->get_autoload_list(); - for (OrderedHashMap::Element E = autoloads.front(); E; E = E.next()) { - const ProjectSettings::AutoloadInfo &info = E.value(); + for (const KeyValue &E : ProjectSettings::get_singleton()->get_autoload_list()) { + const ProjectSettings::AutoloadInfo &info = E.value; if (info.is_singleton) { keywords[info.name] = usertype_color; } diff --git a/modules/gdscript/gdscript_analyzer.cpp b/modules/gdscript/gdscript_analyzer.cpp index d346264933..85ad08ea4f 100644 --- a/modules/gdscript/gdscript_analyzer.cpp +++ b/modules/gdscript/gdscript_analyzer.cpp @@ -4218,13 +4218,11 @@ Error GDScriptAnalyzer::resolve_program() { resolve_class_interface(parser->head); resolve_class_body(parser->head); - List parser_keys; - depended_parsers.get_key_list(&parser_keys); - for (const String &E : parser_keys) { - if (depended_parsers[E].is_null()) { + for (KeyValue> &K : depended_parsers) { + if (K.value.is_null()) { return ERR_PARSE_ERROR; } - depended_parsers[E]->raise_status(GDScriptParserRef::FULLY_SOLVED); + K.value->raise_status(GDScriptParserRef::FULLY_SOLVED); } return parser->errors.is_empty() ? OK : ERR_PARSE_ERROR; } diff --git a/modules/gdscript/gdscript_byte_codegen.cpp b/modules/gdscript/gdscript_byte_codegen.cpp index e72069bcd5..3d5a39bf38 100644 --- a/modules/gdscript/gdscript_byte_codegen.cpp +++ b/modules/gdscript/gdscript_byte_codegen.cpp @@ -196,10 +196,8 @@ GDScriptFunction *GDScriptByteCodeGenerator::write_end() { function->_constant_count = constant_map.size(); function->constants.resize(constant_map.size()); function->_constants_ptr = function->constants.ptrw(); - const Variant *K = nullptr; - while ((K = constant_map.next(K))) { - int idx = constant_map[*K]; - function->constants.write[idx] = *K; + for (const KeyValue &K : constant_map) { + function->constants.write[K.value] = K.key; } } else { function->_constants_ptr = nullptr; diff --git a/modules/gdscript/gdscript_compiler.cpp b/modules/gdscript/gdscript_compiler.cpp index 37a988ee4c..c194fbf9b8 100644 --- a/modules/gdscript/gdscript_compiler.cpp +++ b/modules/gdscript/gdscript_compiler.cpp @@ -336,7 +336,7 @@ GDScriptCodeGenerator::Address GDScriptCompiler::_parse_expression(CodeGen &code if (GDScriptLanguage::get_singleton()->get_global_map().has(identifier)) { // If it's an autoload singleton, we postpone to load it at runtime. // This is so one autoload doesn't try to load another before it's compiled. - OrderedHashMap autoloads = ProjectSettings::get_singleton()->get_autoload_list(); + HashMap autoloads = ProjectSettings::get_singleton()->get_autoload_list(); if (autoloads.has(identifier) && autoloads[identifier].is_singleton) { GDScriptCodeGenerator::Address global = codegen.add_temporary(_gdtype_from_datatype(in->get_datatype())); int idx = GDScriptLanguage::get_singleton()->get_global_map()[identifier]; diff --git a/modules/gdscript/gdscript_editor.cpp b/modules/gdscript/gdscript_editor.cpp index 0197bf9ea3..7021f0aa1e 100644 --- a/modules/gdscript/gdscript_editor.cpp +++ b/modules/gdscript/gdscript_editor.cpp @@ -851,9 +851,10 @@ static void _list_available_types(bool p_inherit_only, GDScriptParser::Completio } // Autoload singletons - OrderedHashMap autoloads = ProjectSettings::get_singleton()->get_autoload_list(); - for (OrderedHashMap::Element E = autoloads.front(); E; E = E.next()) { - const ProjectSettings::AutoloadInfo &info = E.get(); + HashMap autoloads = ProjectSettings::get_singleton()->get_autoload_list(); + + for (const KeyValue &E : autoloads) { + const ProjectSettings::AutoloadInfo &info = E.value; if (!info.is_singleton || info.path.get_extension().to_lower() != "gd") { continue; } @@ -1219,12 +1220,11 @@ static void _find_identifiers(const GDScriptParser::CompletionContext &p_context r_result.insert(option.display, option); } - OrderedHashMap autoloads = ProjectSettings::get_singleton()->get_autoload_list(); - for (OrderedHashMap::Element E = autoloads.front(); E; E = E.next()) { - if (!E.value().is_singleton) { + for (const KeyValue &E : ProjectSettings::get_singleton()->get_autoload_list()) { + if (!E.value.is_singleton) { continue; } - ScriptLanguage::CodeCompletionOption option(E.key(), ScriptLanguage::CODE_COMPLETION_KIND_CONSTANT); + ScriptLanguage::CodeCompletionOption option(E.key, ScriptLanguage::CODE_COMPLETION_KIND_CONSTANT); r_result.insert(option.display, option); } @@ -1517,12 +1517,10 @@ static bool _guess_expression_type(GDScriptParser::CompletionContext &p_context, r_type = _type_from_variant(GDScriptLanguage::get_singleton()->get_named_globals_map()[which]); found = true; } else { - OrderedHashMap autoloads = ProjectSettings::get_singleton()->get_autoload_list(); - - for (OrderedHashMap::Element E = autoloads.front(); E; E = E.next()) { - String name = E.key(); + for (const KeyValue &E : ProjectSettings::get_singleton()->get_autoload_list()) { + String name = E.key; if (name == which) { - String script = E.value().path; + String script = E.value.path; if (!script.begins_with("res://")) { script = "res://" + script; @@ -2882,10 +2880,8 @@ static void _find_call_arguments(GDScriptParser::CompletionContext &p_context, c } // Get autoloads. - OrderedHashMap autoloads = ProjectSettings::get_singleton()->get_autoload_list(); - - for (OrderedHashMap::Element E = autoloads.front(); E; E = E.next()) { - String path = "/root/" + E.key(); + for (const KeyValue &E : ProjectSettings::get_singleton()->get_autoload_list()) { + String path = "/root/" + E.key; ScriptLanguage::CodeCompletionOption option(path.quote(quote_style), ScriptLanguage::CODE_COMPLETION_KIND_NODE_PATH); options.insert(option.display, option); } diff --git a/modules/gdscript/gdscript_parser.cpp b/modules/gdscript/gdscript_parser.cpp index a2dc9bb8a8..b6bf523a67 100644 --- a/modules/gdscript/gdscript_parser.cpp +++ b/modules/gdscript/gdscript_parser.cpp @@ -100,10 +100,8 @@ void GDScriptParser::cleanup() { } void GDScriptParser::get_annotation_list(List *r_annotations) const { - List keys; - valid_annotations.get_key_list(&keys); - for (const StringName &E : keys) { - r_annotations->push_back(valid_annotations[E].info); + for (const KeyValue &E : valid_annotations) { + r_annotations->push_back(E.value.info); } } @@ -1894,11 +1892,8 @@ GDScriptParser::MatchBranchNode *GDScriptParser::parse_match_branch() { SuiteNode *suite = alloc_node(); if (branch->patterns.size() > 0) { - List binds; - branch->patterns[0]->binds.get_key_list(&binds); - - for (const StringName &E : binds) { - SuiteNode::Local local(branch->patterns[0]->binds[E], current_function); + for (const KeyValue &E : branch->patterns[0]->binds) { + SuiteNode::Local local(E.value, current_function); local.type = SuiteNode::Local::PATTERN_BIND; suite->add_local(local); } @@ -3566,14 +3561,15 @@ bool GDScriptParser::export_annotations(const AnnotationNode *p_annotation, Node variable->export_info.hint = PROPERTY_HINT_ENUM; String enum_hint_string; - for (OrderedHashMap::Element E = export_type.enum_values.front(); E; E = E.next()) { - enum_hint_string += E.key().operator String().capitalize().xml_escape(); - enum_hint_string += ":"; - enum_hint_string += String::num_int64(E.value()).xml_escape(); - - if (E.next()) { + bool first = true; + for (const KeyValue &E : export_type.enum_values) { + if (!first) { enum_hint_string += ","; + first = false; } + enum_hint_string += E.key.operator String().capitalize().xml_escape(); + enum_hint_string += ":"; + enum_hint_string += String::num_int64(E.value).xml_escape(); } variable->export_info.hint_string = enum_hint_string; diff --git a/modules/gdscript/gdscript_parser.h b/modules/gdscript/gdscript_parser.h index ab05ac5f51..857e06440c 100644 --- a/modules/gdscript/gdscript_parser.h +++ b/modules/gdscript/gdscript_parser.h @@ -132,7 +132,7 @@ public: ClassNode *class_type = nullptr; MethodInfo method_info; // For callable/signals. - OrderedHashMap enum_values; // For enums. + HashMap enum_values; // For enums. _FORCE_INLINE_ bool is_set() const { return kind != UNRESOLVED; } _FORCE_INLINE_ bool has_no_type() const { return type_source == UNDETECTED; } diff --git a/modules/gdscript/language_server/gdscript_extend_parser.cpp b/modules/gdscript/language_server/gdscript_extend_parser.cpp index 5516f59fe9..bc1f001d86 100644 --- a/modules/gdscript/language_server/gdscript_extend_parser.cpp +++ b/modules/gdscript/language_server/gdscript_extend_parser.cpp @@ -89,16 +89,16 @@ void ExtendGDScriptParser::update_symbols() { for (int i = 0; i < class_symbol.children.size(); i++) { const lsp::DocumentSymbol &symbol = class_symbol.children[i]; - members.set(symbol.name, &symbol); + members.insert(symbol.name, &symbol); // cache level one inner classes if (symbol.kind == lsp::SymbolKind::Class) { ClassMembers inner_class; for (int j = 0; j < symbol.children.size(); j++) { const lsp::DocumentSymbol &s = symbol.children[j]; - inner_class.set(s.name, &s); + inner_class.insert(s.name, &s); } - inner_classes.set(symbol.name, inner_class); + inner_classes.insert(symbol.name, inner_class); } } } @@ -661,30 +661,22 @@ const List &ExtendGDScriptParser::get_document_links() const const Array &ExtendGDScriptParser::get_member_completions() { if (member_completions.is_empty()) { - const String *name = members.next(nullptr); - while (name) { - const lsp::DocumentSymbol *symbol = members.get(*name); + for (const KeyValue &E : members) { + const lsp::DocumentSymbol *symbol = E.value; lsp::CompletionItem item = symbol->make_completion_item(); - item.data = JOIN_SYMBOLS(path, *name); + item.data = JOIN_SYMBOLS(path, E.key); member_completions.push_back(item.to_json()); - - name = members.next(name); } - const String *_class = inner_classes.next(nullptr); - while (_class) { - const ClassMembers *inner_class = inner_classes.getptr(*_class); - const String *member_name = inner_class->next(nullptr); - while (member_name) { - const lsp::DocumentSymbol *symbol = inner_class->get(*member_name); + for (const KeyValue &E : inner_classes) { + const ClassMembers *inner_class = &E.value; + + for (const KeyValue &F : *inner_class) { + const lsp::DocumentSymbol *symbol = F.value; lsp::CompletionItem item = symbol->make_completion_item(); - item.data = JOIN_SYMBOLS(path, JOIN_SYMBOLS(*_class, *member_name)); + item.data = JOIN_SYMBOLS(path, JOIN_SYMBOLS(E.key, F.key)); member_completions.push_back(item.to_json()); - - member_name = inner_class->next(member_name); } - - _class = inner_classes.next(_class); } } diff --git a/modules/gdscript/language_server/gdscript_language_protocol.cpp b/modules/gdscript/language_server/gdscript_language_protocol.cpp index cdddab319d..7460f8edff 100644 --- a/modules/gdscript/language_server/gdscript_language_protocol.cpp +++ b/modules/gdscript/language_server/gdscript_language_protocol.cpp @@ -126,7 +126,7 @@ Error GDScriptLanguageProtocol::on_client_connected() { ERR_FAIL_COND_V_MSG(clients.size() >= LSP_MAX_CLIENTS, FAILED, "Max client limits reached"); Ref peer = memnew(LSPeer); peer->connection = tcp_peer; - clients.set(next_client_id, peer); + clients.insert(next_client_id, peer); next_client_id++; EditorNode::get_log()->add_message("[LSP] Connection Taken", EditorLog::MSG_TYPE_EDITOR); return OK; @@ -229,28 +229,33 @@ void GDScriptLanguageProtocol::poll() { if (server->is_connection_available()) { on_client_connected(); } - const int *id = nullptr; - while ((id = clients.next(id))) { - Ref peer = clients.get(*id); + + HashMap>::Iterator E = clients.begin(); + while (E != clients.end()) { + Ref peer = E->value; StreamPeerTCP::Status status = peer->connection->get_status(); if (status == StreamPeerTCP::STATUS_NONE || status == StreamPeerTCP::STATUS_ERROR) { - on_client_disconnected(*id); - id = nullptr; + on_client_disconnected(E->key); + E = clients.begin(); + continue; } else { if (peer->connection->get_available_bytes() > 0) { - latest_client_id = *id; + latest_client_id = E->key; Error err = peer->handle_data(); if (err != OK && err != ERR_BUSY) { - on_client_disconnected(*id); - id = nullptr; + on_client_disconnected(E->key); + E = clients.begin(); + continue; } } Error err = peer->send_data(); if (err != OK && err != ERR_BUSY) { - on_client_disconnected(*id); - id = nullptr; + on_client_disconnected(E->key); + E = clients.begin(); + continue; } } + ++E; } } @@ -259,9 +264,8 @@ Error GDScriptLanguageProtocol::start(int p_port, const IPAddress &p_bind_ip) { } void GDScriptLanguageProtocol::stop() { - const int *id = nullptr; - while ((id = clients.next(id))) { - Ref peer = clients.get(*id); + for (const KeyValue> &E : clients) { + Ref peer = clients.get(E.key); peer->connection->disconnect_from_host(); } diff --git a/modules/gdscript/language_server/gdscript_text_document.cpp b/modules/gdscript/language_server/gdscript_text_document.cpp index c42bd58aeb..1f02943480 100644 --- a/modules/gdscript/language_server/gdscript_text_document.cpp +++ b/modules/gdscript/language_server/gdscript_text_document.cpp @@ -109,23 +109,15 @@ void GDScriptTextDocument::notify_client_show_symbol(const lsp::DocumentSymbol * void GDScriptTextDocument::initialize() { if (GDScriptLanguageProtocol::get_singleton()->is_smart_resolve_enabled()) { - const HashMap &native_members = GDScriptLanguageProtocol::get_singleton()->get_workspace()->native_members; + for (const KeyValue &E : GDScriptLanguageProtocol::get_singleton()->get_workspace()->native_members) { + const ClassMembers &members = E.value; - const StringName *class_ptr = native_members.next(nullptr); - while (class_ptr) { - const ClassMembers &members = native_members.get(*class_ptr); - - const String *name = members.next(nullptr); - while (name) { - const lsp::DocumentSymbol *symbol = members.get(*name); + for (const KeyValue &F : members) { + const lsp::DocumentSymbol *symbol = members.get(F.key); lsp::CompletionItem item = symbol->make_completion_item(); - item.data = JOIN_SYMBOLS(String(*class_ptr), *name); + item.data = JOIN_SYMBOLS(String(E.key), F.key); native_member_completions.push_back(item.to_json()); - - name = members.next(name); } - - class_ptr = native_members.next(class_ptr); } } } diff --git a/modules/gdscript/language_server/gdscript_workspace.cpp b/modules/gdscript/language_server/gdscript_workspace.cpp index 89ee6b35e5..378dc6d04b 100644 --- a/modules/gdscript/language_server/gdscript_workspace.cpp +++ b/modules/gdscript/language_server/gdscript_workspace.cpp @@ -404,9 +404,9 @@ Error GDScriptWorkspace::initialize() { const lsp::DocumentSymbol &class_symbol = E.value; for (int i = 0; i < class_symbol.children.size(); i++) { const lsp::DocumentSymbol &symbol = class_symbol.children[i]; - members.set(symbol.name, &symbol); + members.insert(symbol.name, &symbol); } - native_members.set(E.key, members); + native_members.insert(E.key, members); } // cache member completions @@ -682,13 +682,11 @@ void GDScriptWorkspace::resolve_related_symbols(const lsp::TextDocumentPositionP Vector2i offset; symbol_identifier = parser->get_identifier_under_position(p_doc_pos.position, offset); - const StringName *class_ptr = native_members.next(nullptr); - while (class_ptr) { - const ClassMembers &members = native_members.get(*class_ptr); + for (const KeyValue &E : native_members) { + const ClassMembers &members = native_members.get(E.key); if (const lsp::DocumentSymbol *const *symbol = members.getptr(symbol_identifier)) { r_list.push_back(*symbol); } - class_ptr = native_members.next(class_ptr); } for (const KeyValue &E : scripts) { @@ -698,15 +696,11 @@ void GDScriptWorkspace::resolve_related_symbols(const lsp::TextDocumentPositionP r_list.push_back(*symbol); } - const HashMap &inner_classes = script->get_inner_classes(); - const String *_class = inner_classes.next(nullptr); - while (_class) { - const ClassMembers *inner_class = inner_classes.getptr(*_class); + for (const KeyValue &F : script->get_inner_classes()) { + const ClassMembers *inner_class = &F.value; if (const lsp::DocumentSymbol *const *symbol = inner_class->getptr(symbol_identifier)) { r_list.push_back(*symbol); } - - _class = inner_classes.next(_class); } } } diff --git a/modules/gdscript/tests/gdscript_test_runner.cpp b/modules/gdscript/tests/gdscript_test_runner.cpp index ea51990237..71dc5de7e4 100644 --- a/modules/gdscript/tests/gdscript_test_runner.cpp +++ b/modules/gdscript/tests/gdscript_test_runner.cpp @@ -48,11 +48,11 @@ namespace GDScriptTests { void init_autoloads() { - OrderedHashMap autoloads = ProjectSettings::get_singleton()->get_autoload_list(); + HashMap autoloads = ProjectSettings::get_singleton()->get_autoload_list(); // First pass, add the constants so they exist before any script is loaded. - for (OrderedHashMap::Element E = autoloads.front(); E; E = E.next()) { - const ProjectSettings::AutoloadInfo &info = E.get(); + for (const KeyValue &E : ProjectSettings::get_singleton()->get_autoload_list()) { + const ProjectSettings::AutoloadInfo &info = E.value; if (info.is_singleton) { for (int i = 0; i < ScriptServer::get_language_count(); i++) { @@ -62,8 +62,8 @@ void init_autoloads() { } // Second pass, load into global constants. - for (OrderedHashMap::Element E = autoloads.front(); E; E = E.next()) { - const ProjectSettings::AutoloadInfo &info = E.get(); + for (const KeyValue &E : ProjectSettings::get_singleton()->get_autoload_list()) { + const ProjectSettings::AutoloadInfo &info = E.value; if (!info.is_singleton) { // Skip non-singletons since we don't have a scene tree here anyway. -- cgit v1.2.3