summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJonathan G Rennison <j.g.rennison@gmail.com>2021-09-09 17:06:00 +0100
committerGitHub <noreply@github.com>2021-09-09 18:06:00 +0200
commit6e3d023e693638d68bfb74b2103c26c6e90a6985 (patch)
treef6ac0c9b2d7253e43275e584671e7c23babfba1f
parent7469f00c5b8d0dc5cc2034eb9dc91c6e8721ac03 (diff)
downloadopenttd-6e3d023e693638d68bfb74b2103c26c6e90a6985.tar.xz
Fix #9535: Maintain a reverse dependency map of network content (#9538)
Fixes performance issues with dependency lookup when retrieving content list from the content server.
-rw-r--r--src/network/network_content.cpp26
-rw-r--r--src/network/network_content.h4
2 files changed, 17 insertions, 13 deletions
diff --git a/src/network/network_content.cpp b/src/network/network_content.cpp
index 13172f9ea..f130ffbb0 100644
--- a/src/network/network_content.cpp
+++ b/src/network/network_content.cpp
@@ -68,7 +68,11 @@ bool ClientNetworkContentSocketHandler::Receive_SERVER_INFO(Packet *p)
uint dependency_count = p->Recv_uint8();
ci->dependencies.reserve(dependency_count);
- for (uint i = 0; i < dependency_count; i++) ci->dependencies.push_back((ContentID)p->Recv_uint32());
+ for (uint i = 0; i < dependency_count; i++) {
+ ContentID dependency_cid = (ContentID)p->Recv_uint32();
+ ci->dependencies.push_back(dependency_cid);
+ this->reverse_dependency_map.insert({ dependency_cid, ci->id });
+ }
uint tag_count = p->Recv_uint8();
ci->tags.reserve(tag_count);
@@ -168,8 +172,10 @@ bool ClientNetworkContentSocketHandler::Receive_SERVER_INFO(Packet *p)
this->infos.push_back(ci);
/* Incoming data means that we might need to reconsider dependencies */
- for (ContentInfo *ici : this->infos) {
- this->CheckDependencyState(ici);
+ ConstContentVector parents;
+ this->ReverseLookupTreeDependency(parents, ci);
+ for (const ContentInfo *ici : parents) {
+ this->CheckDependencyState(const_cast<ContentInfo *>(ici));
}
this->OnReceiveContentInfo(ci);
@@ -833,7 +839,7 @@ void ClientNetworkContentSocketHandler::DownloadContentInfo(ContentID cid)
* @param cid the ContentID to search for
* @return the ContentInfo or nullptr if not found
*/
-ContentInfo *ClientNetworkContentSocketHandler::GetContent(ContentID cid)
+ContentInfo *ClientNetworkContentSocketHandler::GetContent(ContentID cid) const
{
for (ContentInfo *ci : this->infos) {
if (ci->id == cid) return ci;
@@ -923,15 +929,10 @@ void ClientNetworkContentSocketHandler::ToggleSelectedState(const ContentInfo *c
*/
void ClientNetworkContentSocketHandler::ReverseLookupDependency(ConstContentVector &parents, const ContentInfo *child) const
{
- for (const ContentInfo *ci : this->infos) {
- if (ci == child) continue;
+ auto range = this->reverse_dependency_map.equal_range(child->id);
- for (auto &dependency : ci->dependencies) {
- if (dependency == child->id) {
- parents.push_back(ci);
- break;
- }
- }
+ for (auto iter = range.first; iter != range.second; ++iter) {
+ parents.push_back(GetContent(iter->second));
}
}
@@ -1056,6 +1057,7 @@ void ClientNetworkContentSocketHandler::Clear()
this->infos.clear();
this->requested.clear();
+ this->reverse_dependency_map.clear();
}
/*** CALLBACK ***/
diff --git a/src/network/network_content.h b/src/network/network_content.h
index b74308a10..cf60681a2 100644
--- a/src/network/network_content.h
+++ b/src/network/network_content.h
@@ -12,6 +12,7 @@
#include "core/tcp_content.h"
#include "core/tcp_http.h"
+#include <unordered_map>
/** Vector with content info */
typedef std::vector<ContentInfo *> ContentVector;
@@ -68,6 +69,7 @@ protected:
std::vector<ContentCallback *> callbacks; ///< Callbacks to notify "the world"
ContentIDList requested; ///< ContentIDs we already requested (so we don't do it again)
ContentVector infos; ///< All content info we received
+ std::unordered_multimap<ContentID, ContentID> reverse_dependency_map; ///< Content reverse dependency map
std::vector<char> http_response; ///< The HTTP response to the requests we've been doing
int http_response_index; ///< Where we are, in the response, with handling it
@@ -81,7 +83,7 @@ protected:
bool Receive_SERVER_INFO(Packet *p) override;
bool Receive_SERVER_CONTENT(Packet *p) override;
- ContentInfo *GetContent(ContentID cid);
+ ContentInfo *GetContent(ContentID cid) const;
void DownloadContentInfo(ContentID cid);
void OnConnect(bool success) override;