From 82fa3560372bd89ad0985644a76cdd14f6701ec2 Mon Sep 17 00:00:00 2001
From: Clifford Wolf <clifford@clifford.at>
Date: Wed, 23 Jul 2014 23:58:03 +0200
Subject: [PATCH] Added hashing to RTLIL::SigSpec relational and equal
 operators

---
 kernel/rtlil.cc | 79 +++++++++++++++++++++++++++++++++++++++----------
 kernel/rtlil.h  |  9 ++++--
 2 files changed, 71 insertions(+), 17 deletions(-)

diff --git a/kernel/rtlil.cc b/kernel/rtlil.cc
index b0958bd0d..87c9cd04c 100644
--- a/kernel/rtlil.cc
+++ b/kernel/rtlil.cc
@@ -1411,12 +1411,14 @@ bool RTLIL::SigChunk::operator !=(const RTLIL::SigChunk &other) const
 RTLIL::SigSpec::SigSpec()
 {
 	width_ = 0;
+	hash_ = 0;
 }
 
 RTLIL::SigSpec::SigSpec(const RTLIL::Const &value)
 {
 	chunks_.push_back(RTLIL::SigChunk(value));
 	width_ = chunks_.back().width;
+	hash_ = 0;
 	check();
 }
 
@@ -1424,6 +1426,7 @@ RTLIL::SigSpec::SigSpec(const RTLIL::SigChunk &chunk)
 {
 	chunks_.push_back(chunk);
 	width_ = chunks_.back().width;
+	hash_ = 0;
 	check();
 }
 
@@ -1431,6 +1434,7 @@ RTLIL::SigSpec::SigSpec(RTLIL::Wire *wire)
 {
 	chunks_.push_back(RTLIL::SigChunk(wire));
 	width_ = chunks_.back().width;
+	hash_ = 0;
 	check();
 }
 
@@ -1438,6 +1442,7 @@ RTLIL::SigSpec::SigSpec(RTLIL::Wire *wire, int offset, int width)
 {
 	chunks_.push_back(RTLIL::SigChunk(wire, offset, width));
 	width_ = chunks_.back().width;
+	hash_ = 0;
 	check();
 }
 
@@ -1445,6 +1450,7 @@ RTLIL::SigSpec::SigSpec(const std::string &str)
 {
 	chunks_.push_back(RTLIL::SigChunk(str));
 	width_ = chunks_.back().width;
+	hash_ = 0;
 	check();
 }
 
@@ -1452,6 +1458,7 @@ RTLIL::SigSpec::SigSpec(int val, int width)
 {
 	chunks_.push_back(RTLIL::SigChunk(val, width));
 	width_ = width;
+	hash_ = 0;
 	check();
 }
 
@@ -1459,6 +1466,7 @@ RTLIL::SigSpec::SigSpec(RTLIL::State bit, int width)
 {
 	chunks_.push_back(RTLIL::SigChunk(bit, width));
 	width_ = width;
+	hash_ = 0;
 	check();
 }
 
@@ -1470,12 +1478,14 @@ RTLIL::SigSpec::SigSpec(RTLIL::SigBit bit, int width)
 		for (int i = 0; i < width; i++)
 			chunks_.push_back(bit);
 	width_ = width;
+	hash_ = 0;
 	check();
 }
 
 RTLIL::SigSpec::SigSpec(std::vector<RTLIL::SigChunk> chunks)
 {
 	width_ = 0;
+	hash_ = 0;
 	for (auto &c : chunks)
 		append(c);
 	check();
@@ -1484,6 +1494,7 @@ RTLIL::SigSpec::SigSpec(std::vector<RTLIL::SigChunk> chunks)
 RTLIL::SigSpec::SigSpec(std::vector<RTLIL::SigBit> bits)
 {
 	width_ = 0;
+	hash_ = 0;
 	for (auto &bit : bits)
 		append_bit(bit);
 	check();
@@ -1492,6 +1503,7 @@ RTLIL::SigSpec::SigSpec(std::vector<RTLIL::SigBit> bits)
 RTLIL::SigSpec::SigSpec(std::set<RTLIL::SigBit> bits)
 {
 	width_ = 0;
+	hash_ = 0;
 	for (auto &bit : bits)
 		append_bit(bit);
 	check();
@@ -1529,11 +1541,34 @@ void RTLIL::SigSpec::unpack() const
 			that->bits_.push_back(RTLIL::SigBit(c, i));
 
 	that->chunks_.clear();
+	that->hash_ = 0;
 }
 
-bool RTLIL::SigSpec::packed() const
+#define DJB2(_hash, _value) do { (_hash) = (((_hash) << 5) + (_hash)) + (_value); } while (0)
+
+void RTLIL::SigSpec::hash() const
 {
-	return bits_.empty();
+	RTLIL::SigSpec *that = (RTLIL::SigSpec*)this;
+
+	if (that->hash_ != 0)
+		return;
+
+	that->pack();
+	that->hash_ = 5381;
+
+	for (auto &c : that->chunks_)
+		if (c.wire == NULL) {
+			for (auto &v : c.data.bits)
+				DJB2(that->hash_, v);
+		} else {
+			for (auto &v : c.wire->name)
+				DJB2(that->hash_, v);
+			DJB2(that->hash_, c.offset);
+			DJB2(that->hash_, c.width);
+		}
+
+	if (that->hash_ == 0)
+		that->hash_ = 1;
 }
 
 void RTLIL::SigSpec::sort()
@@ -1842,39 +1877,53 @@ void RTLIL::SigSpec::check() const
 
 bool RTLIL::SigSpec::operator <(const RTLIL::SigSpec &other) const
 {
-	pack();
-	other.pack();
+	if (this == &other)
+		return false;
 
 	if (width_ != other.width_)
 		return width_ < other.width_;
 
-	RTLIL::SigSpec a = *this, b = other;
+	pack();
+	other.pack();
+
+	if (chunks_.size() != other.chunks_.size())
+		return chunks_.size() < other.chunks_.size();
+
+	hash();
+	other.hash();
 
-	if (a.chunks_.size() != b.chunks_.size())
-		return a.chunks_.size() < b.chunks_.size();
+	if (hash_ != other.hash_)
+		return hash_ < other.hash_;
 
-	for (size_t i = 0; i < a.chunks_.size(); i++)
-		if (a.chunks_[i] != b.chunks_[i])
-			return a.chunks_[i] < b.chunks_[i];
+	for (size_t i = 0; i < chunks_.size(); i++)
+		if (chunks_[i] != other.chunks_[i])
+			return chunks_[i] < other.chunks_[i];
 
 	return false;
 }
 
 bool RTLIL::SigSpec::operator ==(const RTLIL::SigSpec &other) const
 {
+	if (this == &other)
+		return true;
+
+	if (width_ != other.width_)
+		return false;
+
 	pack();
 	other.pack();
 
-	if (width_ != other.width_)
+	if (chunks_.size() != chunks_.size())
 		return false;
 
-	RTLIL::SigSpec a = *this, b = other;
+	hash();
+	other.hash();
 
-	if (a.chunks_.size() != b.chunks_.size())
+	if (hash_ != other.hash_)
 		return false;
 
-	for (size_t i = 0; i < a.chunks_.size(); i++)
-		if (a.chunks_[i] != b.chunks_[i])
+	for (size_t i = 0; i < chunks_.size(); i++)
+		if (chunks_[i] != other.chunks_[i])
 			return false;
 
 	return true;
diff --git a/kernel/rtlil.h b/kernel/rtlil.h
index 95de5f8c6..c25f71855 100644
--- a/kernel/rtlil.h
+++ b/kernel/rtlil.h
@@ -505,13 +505,18 @@ struct RTLIL::SigSpecIterator {
 
 struct RTLIL::SigSpec {
 private:
+	int width_;
+	unsigned long hash_;
 	std::vector<RTLIL::SigChunk> chunks_; // LSB at index 0
 	std::vector<RTLIL::SigBit> bits_; // LSB at index 0
-	int width_;
 
 	void pack() const;
 	void unpack() const;
-	bool packed() const;
+	void hash() const;
+
+	inline bool packed() const {
+		return bits_.empty();
+	}
 
 	inline void inline_unpack() const {
 		if (!chunks_.empty())
-- 
2.30.2