Replaced std::unordered_map as implementation for Yosys::dict

7 files changed, 262 insertions, 47 deletions

diff --git a/kernel/cost.h b/kernel/cost.h
index 1b4166e0..c6c631e0 100644
--- a/kernel/cost.h
+++ b/kernel/cost.h
@@ -24,10 +24,10 @@
 
 YOSYS_NAMESPACE_BEGIN
 
-int get_cell_cost(RTLIL::Cell *cell, dict<RTLIL::Module*, int> *mod_cost_cache = nullptr);
+int get_cell_cost(RTLIL::Cell *cell, dict<RTLIL::IdString, int> *mod_cost_cache = nullptr);
 
 int get_cell_cost(RTLIL::IdString type, const dict<RTLIL::IdString, RTLIL::Const> &parameters = dict<RTLIL::IdString, RTLIL::Const>(),
-		RTLIL::Design *design = nullptr, dict<RTLIL::Module*, int> *mod_cost_cache = nullptr)
+		RTLIL::Design *design = nullptr, dict<RTLIL::IdString, int> *mod_cost_cache = nullptr)
 {
 	static dict<RTLIL::IdString, int> gate_cost = {
 		{ "$_BUF_",   1 },
@@ -55,18 +55,18 @@ int get_cell_cost(RTLIL::IdString type, const dict<RTLIL::IdString, RTLIL::Const
 		if (mod->attributes.count("\\cost"))
 			return mod->attributes.at("\\cost").as_int();
 
-		dict<RTLIL::Module*, int> local_mod_cost_cache;
+		dict<RTLIL::IdString, int> local_mod_cost_cache;
 		if (mod_cost_cache == nullptr)
 			mod_cost_cache = &local_mod_cost_cache;
 
-		if (mod_cost_cache->count(mod))
-			return mod_cost_cache->at(mod);
+		if (mod_cost_cache->count(mod->name))
+			return mod_cost_cache->at(mod->name);
 
 		int module_cost = 1;
 		for (auto c : mod->cells())
 			module_cost += get_cell_cost(c, mod_cost_cache);
 
-		(*mod_cost_cache)[mod] = module_cost;
+		(*mod_cost_cache)[mod->name] = module_cost;
 		return module_cost;
 	}
 
@@ -74,7 +74,7 @@ int get_cell_cost(RTLIL::IdString type, const dict<RTLIL::IdString, RTLIL::Const
 	return 1;
 }
 
-int get_cell_cost(RTLIL::Cell *cell, dict<RTLIL::Module*, int> *mod_cost_cache)
+int get_cell_cost(RTLIL::Cell *cell, dict<RTLIL::IdString, int> *mod_cost_cache)
 {
 	return get_cell_cost(cell->type, cell->parameters, cell->module->design, mod_cost_cache);
 }
diff --git a/kernel/hashmap.h b/kernel/hashmap.h
index bd4fc4d2..d5f8c4e9 100644
--- a/kernel/hashmap.h
+++ b/kernel/hashmap.h
@@ -19,6 +19,7 @@
 
 #ifndef YOSYS_HASHMAP_H
 
+#include <stdexcept>
 #include <string>
 #include <vector>
 
@@ -27,28 +28,28 @@ inline unsigned int mkhash(unsigned int a, unsigned int b) {
 }
 
 template<typename T> struct hash_ops {
-	bool cmp(const T &a, const T &b) {
+	bool cmp(const T &a, const T &b) const {
 		return a == b;
 	}
-	unsigned int hash(const T &a) {
+	unsigned int hash(const T &a) const {
 		return a.hash();
 	}
 };
 
 template<> struct hash_ops<int> {
-	bool cmp(int a, int b) {
+	bool cmp(int a, int b) const {
 		return a == b;
 	}
-	unsigned int hash(int a) {
+	unsigned int hash(int a) const {
 		return a;
 	}
 };
 
 template<> struct hash_ops<std::string> {
-	bool cmp(const std::string &a, const std::string &b) {
+	bool cmp(const std::string &a, const std::string &b) const {
 		return a == b;
 	}
-	unsigned int hash(const std::string &a) {
+	unsigned int hash(const std::string &a) const {
 		unsigned int v = 0;
 		for (auto c : a)
 			v = mkhash(v, c);
@@ -56,14 +57,25 @@ template<> struct hash_ops<std::string> {
 	}
 };
 
+struct hash_ptr_ops {
+	bool cmp(const void *a, const void *b) const {
+		return a == b;
+	}
+	unsigned int hash(const void *a) const {
+		return (unsigned long)a;
+	}
+};
+
 template<typename K, typename T, typename OPS = hash_ops<K>>
-class new_dict
+class dict
 {
 	struct entry_t
 	{
 		int link;
 		std::pair<K, T> udata;
+
 		entry_t() : link(-1) { }
+		entry_t(const std::pair<K, T> &udata) : link(1), udata(udata) { }
 
 		bool is_free() const { return link < 0; }
 		int get_next() const { return (link > 0 ? link : -link) - 2; }
@@ -79,17 +91,61 @@ class new_dict
 
 	void init()
 	{
+		free_list = -1;
 		counter = 0;
-		entries.resize(61);
+	}
+
+	void init_from(const dict<K, T, OPS> &other)
+	{
+		hashtable.clear();
+		entries.clear();
+
+		counter = other.size();
+		int new_size = grow_size(counter);
+		entries.reserve(new_size);
+
+		for (auto &it : other)
+			entries.push_back(entry_t(it));
+		entries.resize(new_size);
 		rehash();
 	}
 
-	int mkhash(const K &key)
+	size_t grow_size(size_t old_size)
 	{
-		return ops.hash(key) % int(hashtable.size());
+		if (old_size <         53) return         53;
+		if (old_size <        113) return        113;
+		if (old_size <        251) return        251;
+		if (old_size <        503) return        503;
+		if (old_size <       1130) return       1130;
+		if (old_size <       2510) return       2510;
+		if (old_size <       5030) return       5030;
+		if (old_size <      11300) return      11300;
+		if (old_size <      25100) return      25100;
+		if (old_size <      50300) return      50300;
+		if (old_size <     113000) return     113000;
+		if (old_size <     251000) return     251000;
+		if (old_size <     503000) return     503000;
+		if (old_size <    1130000) return    1130000;
+		if (old_size <    2510000) return    2510000;
+		if (old_size <    5030000) return    5030000;
+		if (old_size <   11300000) return   11300000;
+		if (old_size <   25100000) return   25100000;
+		if (old_size <   50300000) return   50300000;
+		if (old_size <  113000000) return  113000000;
+		if (old_size <  251000000) return  251000000;
+		if (old_size <  503000000) return  503000000;
+		if (old_size < 1130000000) return 1130000000;
+		throw std::length_error("maximum size for dict reached");
+	}
+
+	int mkhash(const K &key) const
+	{
+		unsigned int hash = 0;
+		if (!hashtable.empty())
+			hash = ops.hash(key) % (unsigned int)(hashtable.size());
+		return hash;
 	}
 
-public:
 	void rehash()
 	{
 		free_list = -1;
@@ -112,7 +168,7 @@ public:
 	void do_erase(const K &key, int hash)
 	{
 		int last_index = -1;
-		int index = hashtable[hash];
+		int index = hashtable.empty() ? -1 : hashtable[hash];
 		while (1) {
 			if (index < 0)
 				return;
@@ -124,7 +180,8 @@ public:
 				entries[index].udata = std::pair<K, T>();
 				entries[index].set_next_free(free_list);
 				free_list = index;
-				counter--;
+				if (--counter == 0)
+					init();
 				return;
 			}
 			last_index = index;
@@ -132,9 +189,9 @@ public:
 		}
 	}
 
-	int lookup_index(const K &key, int hash)
+	int lookup_index(const K &key, int hash) const
 	{
-		int index = hashtable[hash];
+		int index = hashtable.empty() ? -1 : hashtable[hash];
 		while (1) {
 			if (index < 0)
 				return -1;
@@ -149,7 +206,7 @@ public:
 		if (free_list < 0)
 		{
 			int i = entries.size();
-			entries.resize(2*entries.size());
+			entries.resize(grow_size(i));
 			entries[i].udata = value;
 			entries[i].set_next_used(0);
 			counter++;
@@ -169,24 +226,74 @@ public:
 public:
 	class iterator
 	{
-		new_dict<K, T, OPS> *ptr;
+		dict<K, T, OPS> *ptr;
 		int index;
 	public:
-		iterator(new_dict<K, T, OPS> *ptr, int index) : ptr(ptr), index(index) { }
+		iterator() { }
+		iterator(dict<K, T, OPS> *ptr, int index) : ptr(ptr), index(index) { }
 		iterator operator++() { do index++; while (index != int(ptr->entries.size()) && ptr->entries[index].is_free()); return *this; }
 		iterator operator--() { do index--; while (index != 0 && ptr->entries[index].is_free()); return *this; }
 		bool operator==(const iterator &other) const { return index == other.index; }
 		bool operator!=(const iterator &other) const { return index != other.index; }
 		std::pair<K, T> &operator*() { return ptr->entries[index].udata; }
+		std::pair<K, T> *operator->() { return &ptr->entries[index].udata; }
+		const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
+		const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
 	};
 
-	new_dict()
+	class const_iterator
+	{
+		const dict<K, T, OPS> *ptr;
+		int index;
+	public:
+		const_iterator() { }
+		const_iterator(const dict<K, T, OPS> *ptr, int index) : ptr(ptr), index(index) { }
+		const_iterator operator++() { do index++; while (index != int(ptr->entries.size()) && ptr->entries[index].is_free()); return *this; }
+		const_iterator operator--() { do index--; while (index != 0 && ptr->entries[index].is_free()); return *this; }
+		bool operator==(const const_iterator &other) const { return index == other.index; }
+		bool operator!=(const const_iterator &other) const { return index != other.index; }
+		const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
+		const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
+	};
+
+	dict()
 	{
 		init();
 	}
 
+	dict(const dict<K, T, OPS> &other)
+	{
+		init_from(other);
+	}
+
+	dict(dict<K, T, OPS> &&other)
+	{
+		free_list = -1;
+		counter = 0;
+		swap(other);
+	}
+
+	dict<K, T, OPS> &operator=(const dict<K, T, OPS> &other) {
+		clear();
+		init_from(other);
+		return *this;
+	}
+
+	dict<K, T, OPS> &operator=(dict<K, T, OPS> &&other) {
+		clear();
+		swap(other);
+		return *this;
+	}
+
+	dict(const std::initializer_list<std::pair<K, T>> &list)
+	{
+		init();
+		for (auto &it : list)
+			insert(it);
+	}
+
 	template<class InputIterator>
-	new_dict(InputIterator first, InputIterator last)
+	dict(InputIterator first, InputIterator last)
 	{
 		init();
 		insert(first, last);
@@ -215,13 +322,55 @@ public:
 		do_erase(key, hash);
 	}
 
-	int count(const K &key)
+	void erase(const iterator it)
+	{
+		int hash = mkhash(it->first);
+		do_erase(it->first, hash);
+	}
+
+	int count(const K &key) const
 	{
 		int hash = mkhash(key);
 		int i = lookup_index(key, hash);
 		return i < 0 ? 0 : 1;
 	}
 
+	iterator find(const K &key)
+	{
+		int hash = mkhash(key);
+		int i = lookup_index(key, hash);
+		if (i < 0)
+			return end();
+		return iterator(this, i);
+	}
+
+	const_iterator find(const K &key) const
+	{
+		int hash = mkhash(key);
+		int i = lookup_index(key, hash);
+		if (i < 0)
+			return end();
+		return const_iterator(this, i);
+	}
+
+	T& at(const K &key)
+	{
+		int hash = mkhash(key);
+		int i = lookup_index(key, hash);
+		if (i < 0)
+			throw std::out_of_range("dict::at()");
+		return entries[i].udata.second;
+	}
+
+	const T& at(const K &key) const
+	{
+		int hash = mkhash(key);
+		int i = lookup_index(key, hash);
+		if (i < 0)
+			throw std::out_of_range("dict::at()");
+		return entries[i].udata.second;
+	}
+
 	T& operator[](const K &key)
 	{
 		int hash = mkhash(key);
@@ -231,8 +380,47 @@ public:
 		return entries[i].udata.second;
 	}
 
+	void swap(dict<K, T, OPS> &other)
+	{
+		hashtable.swap(other.hashtable);
+		entries.swap(other.entries);
+		std::swap(free_list, other.free_list);
+		std::swap(counter, other.counter);
+	}
+
+	bool operator==(const dict<K, T, OPS> &other) const {
+		if (counter != other.counter)
+			return false;
+		if (counter == 0)
+			return true;
+		if (entries.size() < other.entries.size())
+			for (auto &it : *this) {
+				auto oit = other.find(it.first);
+				if (oit == other.end() || oit->second != it.second)
+					return false;
+			}
+		else
+			for (auto &oit : other) {
+				auto it = find(oit.first);
+				if (it == end() || it->second != oit.second)
+					return false;
+			}
+		return true;
+	}
+
+	bool operator!=(const dict<K, T, OPS> &other) const {
+		return !(*this == other);
+	}
+
+	size_t size() const { return counter; }
+	bool empty() const { return counter == 0; }
+	void clear() { hashtable.clear(); entries.clear(); init(); }
+
 	iterator begin() { int index = 0; while (index != int(entries.size()) && entries[index].is_free()) index++; return iterator(this, index); }
 	iterator end() { return iterator(this, entries.size()); }
+
+	const_iterator begin() const { int index = 0; while (index != int(entries.size()) && entries[index].is_free()) index++; return const_iterator(this, index); }
+	const_iterator end() const { return const_iterator(this, entries.size()); }
 };
 
 #endif
diff --git a/kernel/log.cc b/kernel/log.cc
index 677884c9..5b18e3d6 100644
--- a/kernel/log.cc
+++ b/kernel/log.cc
@@ -301,7 +301,7 @@ void log_cell(RTLIL::Cell *cell, std::string indent)
 // ---------------------------------------------------
 #ifdef YOSYS_ENABLE_COVER
 
-new_dict<std::string, std::pair<std::string, int>> extra_coverage_data;
+dict<std::string, std::pair<std::string, int>> extra_coverage_data;
 
 void cover_extra(std::string parent, std::string id, bool increment) {
 	if (extra_coverage_data.count(id) == 0) {
@@ -314,9 +314,9 @@ void cover_extra(std::string parent, std::string id, bool increment) {
 		extra_coverage_data[id].second++;
 }
 
-new_dict<std::string, std::pair<std::string, int>> get_coverage_data()
+dict<std::string, std::pair<std::string, int>> get_coverage_data()
 {
-	new_dict<std::string, std::pair<std::string, int>> coverage_data;
+	dict<std::string, std::pair<std::string, int>> coverage_data;
 
 	for (auto &it : pass_register) {
 		std::string key = stringf("passes.%s", it.first.c_str());
diff --git a/kernel/log.h b/kernel/log.h
index eec07199..9bb2b362 100644
--- a/kernel/log.h
+++ b/kernel/log.h
@@ -106,10 +106,10 @@ struct CoverData {
 extern "C" struct CoverData __start_yosys_cover_list[];
 extern "C" struct CoverData __stop_yosys_cover_list[];
 
-extern new_dict<std::string, std::pair<std::string, int>> extra_coverage_data;
+extern dict<std::string, std::pair<std::string, int>> extra_coverage_data;
 
 void cover_extra(std::string parent, std::string id, bool increment = true);
-new_dict<std::string, std::pair<std::string, int>> get_coverage_data();
+dict<std::string, std::pair<std::string, int>> get_coverage_data();
 
 #define cover_list(_id, ...) do { cover(_id); \
 	std::string r = cover_list_worker(_id, __VA_ARGS__); \
diff --git a/kernel/rtlil.cc b/kernel/rtlil.cc
index 28fdeecd..05160b86 100644
--- a/kernel/rtlil.cc
+++ b/kernel/rtlil.cc
@@ -30,7 +30,7 @@ YOSYS_NAMESPACE_BEGIN
 RTLIL::IdString::destruct_guard_t RTLIL::IdString::destruct_guard;
 std::vector<int> RTLIL::IdString::global_refcount_storage_;
 std::vector<char*> RTLIL::IdString::global_id_storage_;
-dict<char*, int, RTLIL::IdString::char_ptr_hash, RTLIL::IdString::char_ptr_eq> RTLIL::IdString::global_id_index_;
+dict<char*, int, RTLIL::IdString::char_ptr_ops> RTLIL::IdString::global_id_index_;
 std::vector<int> RTLIL::IdString::global_free_idx_list_;
 
 RTLIL::Const::Const()
@@ -242,7 +242,7 @@ RTLIL::Design::Design()
 
 RTLIL::Design::~Design()
 {
-	for (auto it = modules_.begin(); it != modules_.end(); it++)
+	for (auto it = modules_.begin(); it != modules_.end(); ++it)
 		delete it->second;
 }
 
@@ -454,13 +454,13 @@ RTLIL::Module::Module()
 
 RTLIL::Module::~Module()
 {
-	for (auto it = wires_.begin(); it != wires_.end(); it++)
+	for (auto it = wires_.begin(); it != wires_.end(); ++it)
 		delete it->second;
-	for (auto it = memories.begin(); it != memories.end(); it++)
+	for (auto it = memories.begin(); it != memories.end(); ++it)
 		delete it->second;
-	for (auto it = cells_.begin(); it != cells_.end(); it++)
+	for (auto it = cells_.begin(); it != cells_.end(); ++it)
 		delete it->second;
-	for (auto it = processes.begin(); it != processes.end(); it++)
+	for (auto it = processes.begin(); it != processes.end(); ++it)
 		delete it->second;
 }
 
@@ -2258,7 +2258,7 @@ void RTLIL::SigSpec::unpack() const
 
 #define DJB2(_hash, _value) (_hash) = (((_hash) << 5) + (_hash)) + (_value)
 
-void RTLIL::SigSpec::hash() const
+void RTLIL::SigSpec::updhash() const
 {
 	RTLIL::SigSpec *that = (RTLIL::SigSpec*)this;
 
@@ -2721,8 +2721,8 @@ bool RTLIL::SigSpec::operator <(const RTLIL::SigSpec &other) const
 	if (chunks_.size() != other.chunks_.size())
 		return chunks_.size() < other.chunks_.size();
 
-	hash();
-	other.hash();
+	updhash();
+	other.updhash();
 
 	if (hash_ != other.hash_)
 		return hash_ < other.hash_;
@@ -2753,8 +2753,8 @@ bool RTLIL::SigSpec::operator ==(const RTLIL::SigSpec &other) const
 	if (chunks_.size() != chunks_.size())
 		return false;
 
-	hash();
-	other.hash();
+	updhash();
+	other.updhash();
 
 	if (hash_ != other.hash_)
 		return false;
diff --git a/kernel/rtlil.h b/kernel/rtlil.h
index e684ba4a..756cca71 100644
--- a/kernel/rtlil.h
+++ b/kernel/rtlil.h
@@ -124,6 +124,21 @@ namespace RTLIL
 			}
 		};
 
+		struct char_ptr_ops {
+			bool cmp(const char *a, const char *b) const {
+				for (int i = 0; a[i] || b[i]; i++)
+					if (a[i] != b[i])
+						return false;
+				return true;
+			}
+			unsigned int hash(const char *a) const {
+				size_t hash = 5381;
+				while (*a)
+					hash = mkhash(hash, *(a++));
+				return hash;
+			}
+		};
+
 		static struct destruct_guard_t {
 			bool ok; // POD, will be initialized to zero
 			destruct_guard_t() { ok = true; }
@@ -132,7 +147,7 @@ namespace RTLIL
 
 		static std::vector<int> global_refcount_storage_;
 		static std::vector<char*> global_id_storage_;
-		static dict<char*, int, char_ptr_hash, char_ptr_eq> global_id_index_;
+		static dict<char*, int, char_ptr_ops> global_id_index_;
 		static std::vector<int> global_free_idx_list_;
 
 		static inline int get_reference(int idx)
@@ -263,6 +278,10 @@ namespace RTLIL
 			*this = IdString();
 		}
 
+		unsigned int hash() const {
+			return index_;
+		}
+
 		// The following is a helper key_compare class. Instead of for example nodict<Cell*>
 		// use nodict<Cell*, IdString::compare_ptr_by_name<Cell>> if the order of cells in the
 		// set has an influence on the algorithm.
@@ -538,6 +557,7 @@ struct RTLIL::SigBit
 	bool operator <(const RTLIL::SigBit &other) const;
 	bool operator ==(const RTLIL::SigBit &other) const;
 	bool operator !=(const RTLIL::SigBit &other) const;
+	unsigned int hash() const;
 };
 
 struct RTLIL::SigSpecIterator : public std::iterator<std::input_iterator_tag, RTLIL::SigSpec>
@@ -572,7 +592,7 @@ private:
 
 	void pack() const;
 	void unpack() const;
-	void hash() const;
+	void updhash() const;
 
 	inline bool packed() const {
 		return bits_.empty();
@@ -710,6 +730,8 @@ public:
 	operator std::vector<RTLIL::SigChunk>() const { return chunks(); }
 	operator std::vector<RTLIL::SigBit>() const { return bits(); }
 
+	unsigned int hash() const { if (!hash_) updhash(); return hash_; };
+
 #ifndef NDEBUG
 	void check() const;
 #else
@@ -1213,6 +1235,12 @@ inline bool RTLIL::SigBit::operator!=(const RTLIL::SigBit &other) const {
 	return (wire != other.wire) || (wire ? (offset != other.offset) : (data != other.data));
 }
 
+inline unsigned int RTLIL::SigBit::hash() const {
+	if (wire)
+		return wire->name.hash() * 33 + offset;
+	return data;
+}
+
 inline RTLIL::SigBit &RTLIL::SigSpecIterator::operator*() const {
 	return (*sig_p)[index];
 }
diff --git a/kernel/yosys.h b/kernel/yosys.h
index b14852ea..9b76d28c 100644
--- a/kernel/yosys.h
+++ b/kernel/yosys.h
@@ -124,7 +124,6 @@
 
 YOSYS_NAMESPACE_BEGIN
 
-#define dict std::unordered_map
 #define nodict std::unordered_set
 #include "kernel/hashmap.h"
 using std::vector;