From 09b4050f2e6e02fd6252f8650bc206b401b7a683 Mon Sep 17 00:00:00 2001
From: Clifford Wolf <clifford@clifford.at>
Date: Tue, 27 Oct 2015 15:04:47 +0100
Subject: [PATCH] Added hashlib::mfp and new SigMap

---
 kernel/hashlib.h  | 93 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sigtools.h | 91 ++++++++++++++++++++++++++++++++++++++++++++++
 kernel/yosys.h    |  1 +
 3 files changed, 185 insertions(+)

diff --git a/kernel/hashlib.h b/kernel/hashlib.h
index 4f5a353c5..83c112f3c 100644
--- a/kernel/hashlib.h
+++ b/kernel/hashlib.h
@@ -195,6 +195,7 @@ inline int hashtable_size(int min_size)
 template<typename K, typename T, typename OPS = hash_ops<K>> class dict;
 template<typename K, int offset = 0, typename OPS = hash_ops<K>> class idict;
 template<typename K, typename OPS = hash_ops<K>> class pool;
+template<typename K, typename OPS = hash_ops<K>> class mfp;
 
 template<typename K, typename T, typename OPS>
 class dict
@@ -914,10 +915,102 @@ public:
 		return database.entries.at(index - offset).udata;
 	}
 
+	void swap(idict &other)
+	{
+		database.swap(other.database);
+	}
+
+	size_t size() const { return database.size(); }
+	bool empty() const { return database.empty(); }
+	void clear() { database.clear(); }
+
 	const_iterator begin() const { return database.begin(); }
 	const_iterator end() const { return database.end(); }
 };
 
+template<typename K, typename OPS>
+class mfp
+{
+	mutable idict<K, 0, OPS> database;
+	mutable std::vector<int> parents;
+
+public:
+	int operator()(const K &key) const
+	{
+		int i = database(key);
+		parents.resize(database.size(), -1);
+		return i;
+	}
+
+	const K &operator[](int index) const
+	{
+		return database[index];
+	}
+
+	int ifind(int i) const
+	{
+		int p = i, k = i;
+
+		while (parents[p] != -1)
+			p = parents[p];
+
+		while (k != p) {
+			int next_k = parents[k];
+			parents[k] = p;
+			k = next_k;
+		}
+
+		return p;
+	}
+
+	void imerge(int i, int j)
+	{
+		i = ifind(i);
+		j = ifind(j);
+
+		if (i != j)
+			parents[i] = j;
+	}
+
+	void ipromote(int i)
+	{
+		int k = i;
+
+		while (k != -1) {
+			int next_k = parents[k];
+			parents[k] = i;
+			k = next_k;
+		}
+
+		parents[i] = -1;
+	}
+
+	const K &find(const K &a) const
+	{
+		return (*this)[ifind((*this)(a))];
+	}
+
+	void merge(const K &a, const K &b)
+	{
+		imerge((*this)(a), (*this)(b));
+	}
+
+	void promote(const K &a)
+	{
+		ipromote((*this)(a));
+	}
+
+	void swap(mfp &other)
+	{
+		database.swap(other.database);
+		parents.swap(other.parents);
+	}
+
+	size_t size() const { return database.size(); }
+	bool empty() const { return database.empty(); }
+	void clear() { database.clear(); parents.clear(); }
+};
+
 } /* namespace hashlib */
 
 #endif
diff --git a/kernel/sigtools.h b/kernel/sigtools.h
index a9419f876..b382cdeb2 100644
--- a/kernel/sigtools.h
+++ b/kernel/sigtools.h
@@ -220,6 +220,96 @@ struct SigSet
 	}
 };
 
+#if 1
+struct SigMap
+{
+	mfp<SigBit> database;
+
+	SigMap(RTLIL::Module *module = NULL)
+	{
+		if (module != NULL)
+			set(module);
+	}
+
+	// SigMap(const SigMap &other)
+	// {
+	// 	copy(other);
+	// }
+
+	// const SigMap &operator=(const SigMap &other)
+	// {
+	// 	copy(other);
+	// 	return *this;
+	// }
+
+	void swap(SigMap &other)
+	{
+		database.swap(other.database);
+	}
+
+	void clear()
+	{
+		database.clear();
+	}
+
+	void set(RTLIL::Module *module)
+	{
+		clear();
+		for (auto &it : module->connections())
+			add(it.first, it.second);
+	}
+
+	void add(RTLIL::SigSpec from, RTLIL::SigSpec to)
+	{
+		log_assert(GetSize(from) == GetSize(to));
+
+		for (int i = 0; i < GetSize(from); i++)
+		{
+			RTLIL::SigBit &bf = from[i];
+			RTLIL::SigBit &bt = to[i];
+
+			if (bf.wire != nullptr)
+				database.merge(bf, bt);
+		}
+	}
+
+	void add(RTLIL::SigSpec sig)
+	{
+		for (auto &bit : sig)
+			database.promote(bit);
+	}
+
+	void apply(RTLIL::SigBit &bit) const
+	{
+		bit = database.find(bit);
+	}
+
+	void apply(RTLIL::SigSpec &sig) const
+	{
+		for (auto &bit : sig)
+			apply(bit);
+	}
+
+	RTLIL::SigBit operator()(RTLIL::SigBit bit) const
+	{
+		apply(bit);
+		return bit;
+	}
+
+	RTLIL::SigSpec operator()(RTLIL::SigSpec sig) const
+	{
+		apply(sig);
+		return sig;
+	}
+
+	RTLIL::SigSpec operator()(RTLIL::Wire *wire) const
+	{
+		SigSpec sig(wire);
+		apply(sig);
+		return sig;
+	}
+};
+#else
 struct SigMap
 {
 	struct bitDef_t : public std::pair<RTLIL::Wire*, int> {
@@ -430,6 +520,7 @@ struct SigMap
 		return sig;
 	}
 };
+#endif
 
 YOSYS_NAMESPACE_END
 
diff --git a/kernel/yosys.h b/kernel/yosys.h
index 89a4f6084..92fa6ac19 100644
--- a/kernel/yosys.h
+++ b/kernel/yosys.h
@@ -171,6 +171,7 @@ using hashlib::hash_obj_ops;
 using hashlib::dict;
 using hashlib::idict;
 using hashlib::pool;
+using hashlib::mfp;
 
 namespace RTLIL {
 	struct IdString;
-- 
2.30.2