From 1e32e4bdae2e3fb3d1bf68314e146052a3c65561 Mon Sep 17 00:00:00 2001
From: Clifford Wolf <clifford@clifford.at>
Date: Wed, 28 Oct 2015 11:21:55 +0100
Subject: [PATCH] Improved SigMap performance

---
 CodingReadme      |  3 +++
 kernel/hashlib.h  |  5 +++++
 kernel/sigtools.h | 13 ++++++++-----
 3 files changed, 16 insertions(+), 5 deletions(-)

diff --git a/CodingReadme b/CodingReadme
index a385a99dc..5d5d9b32c 100644
--- a/CodingReadme
+++ b/CodingReadme
@@ -93,6 +93,9 @@ creates a bijective map from K to the integers. For example:
 
 It is not possible to remove elements from an idict.
 
+Finally mfp<K> implements a merge-find set data structure (aka. disjoint-set or
+union–find) over the type K ("mfp" = merge-find-promote).
+
   2. Standard STL data types
 
 In Yosys we use std::vector<T> and std::string whenever applicable. When
diff --git a/kernel/hashlib.h b/kernel/hashlib.h
index 83c112f3c..1f022e473 100644
--- a/kernel/hashlib.h
+++ b/kernel/hashlib.h
@@ -985,6 +985,11 @@ public:
 		parents[i] = -1;
 	}
 
+	int lookup(const K &a) const
+	{
+		return ifind((*this)(a));
+	}
+
 	const K &find(const K &a) const
 	{
 		return (*this)[ifind((*this)(a))];
diff --git a/kernel/sigtools.h b/kernel/sigtools.h
index 3ef87199e..d73c5623d 100644
--- a/kernel/sigtools.h
+++ b/kernel/sigtools.h
@@ -253,18 +253,21 @@ struct SigMap
 
 		for (int i = 0; i < GetSize(from); i++)
 		{
-			RTLIL::SigBit bf = database.find(from[i]);
-			RTLIL::SigBit bt = database.find(to[i]);
+			int bfi = database.lookup(from[i]);
+			int bti = database.lookup(to[i]);
+
+			const RTLIL::SigBit &bf = database[bfi];
+			const RTLIL::SigBit &bt = database[bti];
 
 			if (bf.wire || bt.wire)
 			{
-				database.merge(bf, bt);
+				database.imerge(bfi, bti);
 
 				if (bf.wire == nullptr)
-					database.promote(bf);
+					database.ipromote(bfi);
 
 				if (bt.wire == nullptr)
-					database.promote(bt);
+					database.ipromote(bti);
 			}
 		}
 	}
-- 
2.30.2