From 46cef1955db894fe47a8745b9a69933145e3c9f8 Mon Sep 17 00:00:00 2001
From: Takashi Sawanaka <sdottaka@users.sourceforge.net>
Date: Sat, 25 Jan 2020 12:50:53 +0900
Subject: [PATCH] xdiff_genudiff_compat.cpp: Improve the comparison speed when
 choosing patience or histogram for the diff algorithm and enabling moved
 block detection

---
 Src/xdiff_gnudiff_compat.cpp | 37 ++++++++++++++++++++++++++++---------
 1 file changed, 28 insertions(+), 9 deletions(-)

diff --git a/Src/xdiff_gnudiff_compat.cpp b/Src/xdiff_gnudiff_compat.cpp
index 15a68a4fe..9f275f47f 100644
--- a/Src/xdiff_gnudiff_compat.cpp
+++ b/Src/xdiff_gnudiff_compat.cpp
@@ -68,24 +68,43 @@ static int hunk_func(long start_a, long count_a, long start_b, long count_b, voi
 
 static void append_equivs(const xdfile_t& xdf, struct file_data& filevec, std::vector<xrecord_t *>& equivs, unsigned xdl_flags)
 {
+	std::unordered_map<unsigned long, std::vector<int>> equivs_map;
+	for (int i = 0; i < equivs.size(); ++i)
+	{
+		unsigned long ha = equivs[i]->ha;
+		if (equivs_map.find(ha) != equivs_map.end())
+			equivs_map[ha].push_back(i);
+		else
+			equivs_map.emplace(ha, std::vector<int>{i});
+	}
+
 	for (int i = 0; i < xdf.nrec; ++i)
 	{
-		int j;
-		for (j = 0; j < static_cast<int>(equivs.size()); j++)
+		unsigned long ha = xdf.recs[i]->ha;
+		if (equivs_map.find(ha) != equivs_map.end())
 		{
-			if (equivs[j]->ha == xdf.recs[i]->ha &&
-				xdl_recmatch(equivs[j]->ptr, equivs[j]->size, xdf.recs[i]->ptr, xdf.recs[i]->size, xdl_flags))
+			bool found = false;
+			for (auto j: equivs_map[ha])
 			{
-				break;
+				if (xdl_recmatch(equivs[j]->ptr, equivs[j]->size, xdf.recs[i]->ptr, xdf.recs[i]->size, xdl_flags))
+				{
+					found = true;
+					filevec.equivs[i] = j;
+					equivs_map.emplace(ha, std::vector<int>{j});
+					break;
+				}
+			}
+			if (!found)
+			{
+				filevec.equivs[i] = static_cast<int>(equivs.size());
+				equivs_map[ha].push_back(filevec.equivs[i]);
+				equivs.push_back(xdf.recs[i]);
 			}
-		}
-		if (j < static_cast<int>(equivs.size()))
-		{
-			filevec.equivs[i] = j;
 		}
 		else
 		{
 			filevec.equivs[i] = static_cast<int>(equivs.size());
+			equivs_map.emplace(ha, std::vector<int>{filevec.equivs[i]});
 			equivs.push_back(xdf.recs[i]);
 		}
 	}
-- 
2.11.0