From 2fb4931e5be2c2a0c80ffbca73ad74ebb8c9032f Mon Sep 17 00:00:00 2001 From: Alberto Gonzalez Date: Tue, 14 Apr 2020 18:09:05 +0000 Subject: Add specialized `hash()` for type `dict` and use a `dict` instead of a `std::map` for `techmap_cache` and `techmap_do_cache`. --- kernel/hashlib.h | 25 ++++++++++++++++++++----- 1 file changed, 20 insertions(+), 5 deletions(-) (limited to 'kernel/hashlib.h') diff --git a/kernel/hashlib.h b/kernel/hashlib.h index 592d6e577..cdbad87c4 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -19,6 +19,12 @@ namespace hashlib { +template struct hash_ops; +template> class dict; +template> class idict; +template> class pool; +template> class mfp; + const int hashtable_size_trigger = 2; const int hashtable_size_factor = 3; @@ -100,6 +106,20 @@ template struct hash_ops> { } }; +template struct hash_ops> { + static inline bool cmp(dict a, dict b) { + return a == b; + } + static inline unsigned int hash(dict a) { + unsigned int h = mkhash_init; + for (auto &it : a) { + h = mkhash(h, hash_ops

::hash(it.first)); + h = mkhash(h, hash_ops::hash(it.second)); + } + return h; + } +}; + template struct hash_ops> { static inline bool cmp(std::tuple a, std::tuple b) { return a == b; @@ -191,11 +211,6 @@ inline int hashtable_size(int min_size) throw std::length_error("hash table exceeded maximum size."); } -template> class dict; -template> class idict; -template> class pool; -template> class mfp; - template class dict { -- cgit v1.2.3 From 35b94d1f664928dcf8476a9a6f35e2bb7f647ee1 Mon Sep 17 00:00:00 2001 From: Alberto Gonzalez Date: Wed, 22 Apr 2020 22:04:22 +0000 Subject: kernel: Re-implement `dict` hash code as a `dict` member function instead of a specialized template for `hash_ops`. --- kernel/hashlib.h | 34 ++++++++++++++-------------------- 1 file changed, 14 insertions(+), 20 deletions(-) (limited to 'kernel/hashlib.h') diff --git a/kernel/hashlib.h b/kernel/hashlib.h index cdbad87c4..18114b6ad 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -19,12 +19,6 @@ namespace hashlib { -template struct hash_ops; -template> class dict; -template> class idict; -template> class pool; -template> class mfp; - const int hashtable_size_trigger = 2; const int hashtable_size_factor = 3; @@ -106,20 +100,6 @@ template struct hash_ops> { } }; -template struct hash_ops> { - static inline bool cmp(dict a, dict b) { - return a == b; - } - static inline unsigned int hash(dict a) { - unsigned int h = mkhash_init; - for (auto &it : a) { - h = mkhash(h, hash_ops

::hash(it.first)); - h = mkhash(h, hash_ops::hash(it.second)); - } - return h; - } -}; - template struct hash_ops> { static inline bool cmp(std::tuple a, std::tuple b) { return a == b; @@ -211,6 +191,11 @@ inline int hashtable_size(int min_size) throw std::length_error("hash table exceeded maximum size."); } +template> class dict; +template> class idict; +template> class pool; +template> class mfp; + template class dict { @@ -630,6 +615,15 @@ public: return !operator==(other); } + unsigned int hash() const { + unsigned int h = mkhash_init; + for (auto &it : entries) { + h = mkhash(h, hash_ops::hash(it.udata.first)); + h = mkhash(h, hash_ops::hash(it.udata.second)); + } + return h; + } + void reserve(size_t n) { entries.reserve(n); } size_t size() const { return entries.size(); } bool empty() const { return entries.empty(); } -- cgit v1.2.3 From 976edb7597692ac04111b3c51b13e18105c14f42 Mon Sep 17 00:00:00 2001 From: Alberto Gonzalez Date: Fri, 24 Apr 2020 08:37:16 +0000 Subject: kernel: Ensure `dict` always hashes to the same value given the same contents. --- kernel/hashlib.h | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) (limited to 'kernel/hashlib.h') diff --git a/kernel/hashlib.h b/kernel/hashlib.h index 18114b6ad..1284f3f8d 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -207,6 +207,7 @@ class dict entry_t() { } entry_t(const std::pair &udata, int next) : udata(udata), next(next) { } entry_t(std::pair &&udata, int next) : udata(std::move(udata)), next(next) { } + bool operator<(const entry_t &other) const { return udata.first < other.udata.first; } }; std::vector hashtable; @@ -616,10 +617,12 @@ public: } unsigned int hash() const { + std::vector entries_(entries); //make a copy to preserve const-ness + std::sort(entries_.begin(), entries_.end()); unsigned int h = mkhash_init; - for (auto &it : entries) { - h = mkhash(h, hash_ops::hash(it.udata.first)); - h = mkhash(h, hash_ops::hash(it.udata.second)); + for (unsigned int i = 0; i < entries_.size(); ++i) { + h = mkhash(h, hash_ops::hash(entries_[i].udata.first)); + h = mkhash(h, hash_ops::hash(entries_[i].udata.second)); } return h; } -- cgit v1.2.3 From 6eea4b3d79590f874caa3ec740785781f3926666 Mon Sep 17 00:00:00 2001 From: Alberto Gonzalez Date: Mon, 18 May 2020 17:10:01 +0000 Subject: kernel: Try an order-independent approach to hashing `dict`. Co-Authored-By: David Shah Co-Authored-By: Eddie Hung --- kernel/hashlib.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'kernel/hashlib.h') diff --git a/kernel/hashlib.h b/kernel/hashlib.h index 1284f3f8d..5c87b55f5 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -617,12 +617,10 @@ public: } unsigned int hash() const { - std::vector entries_(entries); //make a copy to preserve const-ness - std::sort(entries_.begin(), entries_.end()); unsigned int h = mkhash_init; - for (unsigned int i = 0; i < entries_.size(); ++i) { - h = mkhash(h, hash_ops::hash(entries_[i].udata.first)); - h = mkhash(h, hash_ops::hash(entries_[i].udata.second)); + for (auto &entry : entries) { + h ^= hash_ops::hash(entry.udata.first); + h ^= hash_ops::hash(entry.udata.second); } return h; } -- cgit v1.2.3