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<>

4 files changed, 41 insertions, 59 deletions

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<lsp::DocumentLink> &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<String, const lsp::DocumentSymbol *> &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<String, ClassMembers> &E : inner_classes) {
+			const ClassMembers *inner_class = &E.value;
+
+			for (const KeyValue<String, const lsp::DocumentSymbol *> &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<LSPeer> 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<LSPeer> peer = clients.get(*id);
+
+	HashMap<int, Ref<LSPeer>>::Iterator E = clients.begin();
+	while (E != clients.end()) {
+		Ref<LSPeer> 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<LSPeer> peer = clients.get(*id);
+	for (const KeyValue<int, Ref<LSPeer>> &E : clients) {
+		Ref<LSPeer> 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<StringName, ClassMembers> &native_members = GDScriptLanguageProtocol::get_singleton()->get_workspace()->native_members;
+		for (const KeyValue<StringName, ClassMembers> &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<String, const lsp::DocumentSymbol *> &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<StringName, ClassMembers> &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<String, ExtendGDScriptParser *> &E : scripts) {
@@ -698,15 +696,11 @@ void GDScriptWorkspace::resolve_related_symbols(const lsp::TextDocumentPositionP
 				r_list.push_back(*symbol);
 			}
 
-			const HashMap<String, ClassMembers> &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<String, ClassMembers> &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);
 			}
 		}
 	}