diff --git a/src/network/network_content.cpp b/src/network/network_content.cpp
--- a/src/network/network_content.cpp
+++ b/src/network/network_content.cpp
@@ -68,7 +68,11 @@ bool ClientNetworkContentSocketHandler::
 
 	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::
 	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::
  * @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::
  */
 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::
 
 	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
--- 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;