X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=kernel%2Fhashlib.h;h=996bda38e560aeb496c826fb7410c345bf3e7972;hb=4d1db12133885d35f7ce6fe76db82e5878cee104;hp=7f2575d725a242763bf7cb695f5bab99d4365a54;hpb=12b05dfc040ccdcde193cd1ff81e97b3c5e2c974;p=yosys.git diff --git a/kernel/hashlib.h b/kernel/hashlib.h index 7f2575d72..996bda38e 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -1,5 +1,5 @@ // This is free and unencumbered software released into the public domain. -// +// // Anyone is free to copy, modify, publish, use, compile, sell, or // distribute this software, either in source code form or as a compiled // binary, for any purpose, commercial or non-commercial, and by any @@ -10,8 +10,10 @@ // ------------------------------------------------------- #ifndef HASHLIB_H +#define HASHLIB_H #include +#include #include #include @@ -29,7 +31,7 @@ inline unsigned int mkhash(unsigned int a, unsigned int b) { const unsigned int mkhash_init = 5381; // The ADD version of DJB2 -// (usunsigned int mkhashe this version for cache locality in b) +// (use this version for cache locality in b) inline unsigned int mkhash_add(unsigned int a, unsigned int b) { return ((a << 5) + a) + b; } @@ -49,30 +51,39 @@ inline unsigned int mkhash_xorshift(unsigned int a) { } template struct hash_ops { - bool cmp(const T &a, const T &b) const { + static inline bool cmp(const T &a, const T &b) { return a == b; } - unsigned int hash(const T &a) const { + static inline unsigned int hash(const T &a) { return a.hash(); } }; -template<> struct hash_ops { +struct hash_int_ops { template - bool cmp(T a, T b) const { + static inline bool cmp(T a, T b) { return a == b; } - template - unsigned int hash(T a) const { +}; + +template<> struct hash_ops : hash_int_ops +{ + static inline unsigned int hash(int32_t a) { return a; } }; +template<> struct hash_ops : hash_int_ops +{ + static inline unsigned int hash(int64_t a) { + return mkhash((unsigned int)(a), (unsigned int)(a >> 32)); + } +}; template<> struct hash_ops { - bool cmp(const std::string &a, const std::string &b) const { + static inline bool cmp(const std::string &a, const std::string &b) { return a == b; } - unsigned int hash(const std::string &a) const { + static inline unsigned int hash(const std::string &a) { unsigned int v = 0; for (auto c : a) v = mkhash(v, c); @@ -81,63 +92,80 @@ template<> struct hash_ops { }; template struct hash_ops> { - bool cmp(std::pair a, std::pair b) const { + static inline bool cmp(std::pair a, std::pair b) { return a == b; } - unsigned int hash(std::pair a) const { - hash_ops

p_ops; - hash_ops q_ops; - return mkhash(p_ops.hash(a.first), q_ops.hash(a.second)); + static inline unsigned int hash(std::pair a) { + return mkhash(hash_ops

::hash(a.first), hash_ops::hash(a.second)); + } +}; + +template struct hash_ops> { + static inline bool cmp(std::tuple a, std::tuple b) { + return a == b; + } + template + static inline typename std::enable_if::type hash(std::tuple) { + return mkhash_init; + } + template + static inline typename std::enable_if::type hash(std::tuple a) { + typedef hash_ops>::type> element_ops_t; + return mkhash(hash(a), element_ops_t::hash(std::get(a))); } }; template struct hash_ops> { - bool cmp(std::vector a, std::vector b) const { + static inline bool cmp(std::vector a, std::vector b) { return a == b; } - unsigned int hash(std::vector a) const { - hash_ops t_ops; + static inline unsigned int hash(std::vector a) { unsigned int h = mkhash_init; for (auto k : a) - h = mkhash(h, t_ops.hash(k)); + h = mkhash(h, hash_ops::hash(k)); return h; } }; struct hash_cstr_ops { - bool cmp(const char *a, const char *b) const { + static inline bool cmp(const char *a, const char *b) { 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 { + static inline unsigned int hash(const char *a) { unsigned int hash = mkhash_init; while (*a) - hash = mkhash(hash, *(a++)); - return hash; + hash = mkhash(hash, *(a++)); + return hash; } }; struct hash_ptr_ops { - bool cmp(const void *a, const void *b) const { + static inline bool cmp(const void *a, const void *b) { return a == b; } - unsigned int hash(const void *a) const { - return (unsigned long)a; + static inline unsigned int hash(const void *a) { + return (uintptr_t)a; } }; struct hash_obj_ops { - bool cmp(const void *a, const void *b) const { + static inline bool cmp(const void *a, const void *b) { return a == b; } template - unsigned int hash(const T *a) const { - return a->hash(); + static inline unsigned int hash(const T *a) { + return a ? a->hash() : 0; } }; +template +inline unsigned int mkhash(const T &v) { + return hash_ops().hash(v); +} + inline int hashtable_size(int min_size) { static std::vector zero_and_some_primes = { @@ -163,7 +191,12 @@ inline int hashtable_size(int min_size) throw std::length_error("hash table exceeded maximum size."); } -template> +template> class dict; +template> class idict; +template> class pool; +template> class mfp; + +template class dict { struct entry_t @@ -173,18 +206,19 @@ 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) { } }; std::vector hashtable; std::vector entries; OPS ops; -#if 0 +#ifdef NDEBUG + static inline void do_assert(bool) { } +#else static inline void do_assert(bool cond) { if (!cond) throw std::runtime_error("dict<> assert failed."); } -#else - static inline void do_assert(bool) { } #endif int do_hash(const K &key) const @@ -198,7 +232,7 @@ class dict void do_rehash() { hashtable.clear(); - hashtable.resize(hashtable_size(entries.size() * hashtable_size_factor), -1); + hashtable.resize(hashtable_size(entries.capacity() * hashtable_size_factor), -1); for (int i = 0; i < int(entries.size()); i++) { do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size())); @@ -215,6 +249,8 @@ class dict return 0; int k = hashtable[hash]; + do_assert(0 <= k && k < int(entries.size())); + if (k == index) { hashtable[hash] = entries[index].next; } else { @@ -232,6 +268,8 @@ class dict int back_hash = do_hash(entries[back_idx].udata.first); k = hashtable[back_hash]; + do_assert(0 <= k && k < int(entries.size())); + if (k == back_idx) { hashtable[back_hash] = index; } else { @@ -273,52 +311,82 @@ class dict return index; } + int do_insert(const K &key, int &hash) + { + if (hashtable.empty()) { + entries.emplace_back(std::pair(key, T()), -1); + do_rehash(); + hash = do_hash(key); + } else { + entries.emplace_back(std::pair(key, T()), hashtable[hash]); + hashtable[hash] = entries.size() - 1; + } + return entries.size() - 1; + } + int do_insert(const std::pair &value, int &hash) { if (hashtable.empty()) { - entries.push_back(entry_t(value, -1)); + entries.emplace_back(value, -1); do_rehash(); hash = do_hash(value.first); } else { - entries.push_back(entry_t(value, hashtable[hash])); + entries.emplace_back(value, hashtable[hash]); + hashtable[hash] = entries.size() - 1; + } + return entries.size() - 1; + } + + int do_insert(std::pair &&rvalue, int &hash) + { + if (hashtable.empty()) { + auto key = rvalue.first; + entries.emplace_back(std::forward>(rvalue), -1); + do_rehash(); + hash = do_hash(key); + } else { + entries.emplace_back(std::forward>(rvalue), hashtable[hash]); hashtable[hash] = entries.size() - 1; } return entries.size() - 1; } public: - class iterator + class const_iterator : public std::iterator> { friend class dict; protected: - dict *ptr; + const dict *ptr; int index; + const_iterator(const dict *ptr, int index) : ptr(ptr), index(index) { } public: - iterator() { } - iterator(dict *ptr, int index) : ptr(ptr), index(index) { } - iterator operator++() { index--; return *this; } - bool operator==(const iterator &other) const { return index == other.index; } - bool operator!=(const iterator &other) const { return index != other.index; } - std::pair &operator*() { return ptr->entries[index].udata; } - std::pair *operator->() { return &ptr->entries[index].udata; } + const_iterator() { } + const_iterator operator++() { index--; return *this; } + bool operator<(const const_iterator &other) const { return index > other.index; } + 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 &operator*() const { return ptr->entries[index].udata; } const std::pair *operator->() const { return &ptr->entries[index].udata; } }; - class const_iterator + class iterator : public std::iterator> { friend class dict; protected: - const dict *ptr; + dict *ptr; int index; + iterator(dict *ptr, int index) : ptr(ptr), index(index) { } public: - const_iterator() { } - const_iterator(const dict *ptr, int index) : ptr(ptr), index(index) { } - const_iterator operator++() { index--; return *this; } - bool operator==(const const_iterator &other) const { return index == other.index; } - bool operator!=(const const_iterator &other) const { return index != other.index; } + iterator() { } + iterator operator++() { index--; return *this; } + bool operator<(const iterator &other) const { return index > other.index; } + bool operator==(const iterator &other) const { return index == other.index; } + bool operator!=(const iterator &other) const { return index != other.index; } + std::pair &operator*() { return ptr->entries[index].udata; } + std::pair *operator->() { return &ptr->entries[index].udata; } const std::pair &operator*() const { return ptr->entries[index].udata; } const std::pair *operator->() const { return &ptr->entries[index].udata; } + operator const_iterator() const { return const_iterator(ptr, index); } }; dict() @@ -367,6 +435,16 @@ public: insert(*first); } + std::pair insert(const K &key) + { + int hash = do_hash(key); + int i = do_lookup(key, hash); + if (i >= 0) + return std::pair(iterator(this, i), false); + i = do_insert(key, hash); + return std::pair(iterator(this, i), true); + } + std::pair insert(const std::pair &value) { int hash = do_hash(value.first); @@ -377,6 +455,56 @@ public: return std::pair(iterator(this, i), true); } + std::pair insert(std::pair &&rvalue) + { + int hash = do_hash(rvalue.first); + int i = do_lookup(rvalue.first, hash); + if (i >= 0) + return std::pair(iterator(this, i), false); + i = do_insert(std::forward>(rvalue), hash); + return std::pair(iterator(this, i), true); + } + + std::pair emplace(K const &key, T const &value) + { + int hash = do_hash(key); + int i = do_lookup(key, hash); + if (i >= 0) + return std::pair(iterator(this, i), false); + i = do_insert(std::make_pair(key, value), hash); + return std::pair(iterator(this, i), true); + } + + std::pair emplace(K const &key, T &&rvalue) + { + int hash = do_hash(key); + int i = do_lookup(key, hash); + if (i >= 0) + return std::pair(iterator(this, i), false); + i = do_insert(std::make_pair(key, std::forward(rvalue)), hash); + return std::pair(iterator(this, i), true); + } + + std::pair emplace(K &&rkey, T const &value) + { + int hash = do_hash(rkey); + int i = do_lookup(rkey, hash); + if (i >= 0) + return std::pair(iterator(this, i), false); + i = do_insert(std::make_pair(std::forward(rkey), value), hash); + return std::pair(iterator(this, i), true); + } + + std::pair emplace(K &&rkey, T &&rvalue) + { + int hash = do_hash(rkey); + int i = do_lookup(rkey, hash); + if (i >= 0) + return std::pair(iterator(this, i), false); + i = do_insert(std::make_pair(std::forward(rkey), std::forward(rvalue)), hash); + return std::pair(iterator(this, i), true); + } + int erase(const K &key) { int hash = do_hash(key); @@ -398,6 +526,13 @@ public: return i < 0 ? 0 : 1; } + int count(const K &key, const_iterator it) const + { + int hash = do_hash(key); + int i = do_lookup(key, hash); + return i < 0 || i > it.index ? 0 : 1; + } + iterator find(const K &key) { int hash = do_hash(key); @@ -434,6 +569,15 @@ public: return entries[i].udata.second; } + T at(const K &key, const T &defval) const + { + int hash = do_hash(key); + int i = do_lookup(key, hash); + if (i < 0) + return defval; + return entries[i].udata.second; + } + T& operator[](const K &key) { int hash = do_hash(key); @@ -443,6 +587,13 @@ public: return entries[i].udata.second; } + template> + void sort(Compare comp = Compare()) + { + std::sort(entries.begin(), entries.end(), [comp](const entry_t &a, const entry_t &b){ return comp(b.udata.first, a.udata.first); }); + do_rehash(); + } + void swap(dict &other) { hashtable.swap(other.hashtable); @@ -454,37 +605,36 @@ public: return false; for (auto &it : entries) { auto oit = other.find(it.udata.first); - if (oit == other.end() || oit->second != it.udata.second) + if (oit == other.end() || !(oit->second == it.udata.second)) return false; } return true; } bool operator!=(const dict &other) const { - return !(*this == other); + return !operator==(other); } + void reserve(size_t n) { entries.reserve(n); } size_t size() const { return entries.size(); } bool empty() const { return entries.empty(); } void clear() { hashtable.clear(); entries.clear(); } iterator begin() { return iterator(this, int(entries.size())-1); } + iterator element(int n) { return iterator(this, int(entries.size())-1-n); } iterator end() { return iterator(nullptr, -1); } const_iterator begin() const { return const_iterator(this, int(entries.size())-1); } + const_iterator element(int n) const { return const_iterator(this, int(entries.size())-1-n); } const_iterator end() const { return const_iterator(nullptr, -1); } }; -// ******************************************************************************** -// ******************************************************************************** -// ******************************************************************************** -// ******************************************************************************** -// ******************************************************************************** - - -template> +template class pool { + template friend class idict; + +protected: struct entry_t { K udata; @@ -498,12 +648,12 @@ class pool std::vector entries; OPS ops; -#if 0 +#ifdef NDEBUG + static inline void do_assert(bool) { } +#else static inline void do_assert(bool cond) { if (!cond) throw std::runtime_error("pool<> assert failed."); } -#else - static inline void do_assert(bool) { } #endif int do_hash(const K &key) const @@ -517,7 +667,7 @@ class pool void do_rehash() { hashtable.clear(); - hashtable.resize(hashtable_size(entries.size() * hashtable_size_factor), -1); + hashtable.resize(hashtable_size(entries.capacity() * hashtable_size_factor), -1); for (int i = 0; i < int(entries.size()); i++) { do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size())); @@ -606,36 +756,39 @@ class pool } public: - class iterator + class const_iterator : public std::iterator { friend class pool; protected: - pool *ptr; + const pool *ptr; int index; + const_iterator(const pool *ptr, int index) : ptr(ptr), index(index) { } public: - iterator() { } - iterator(pool *ptr, int index) : ptr(ptr), index(index) { } - iterator operator++() { index--; return *this; } - bool operator==(const iterator &other) const { return index == other.index; } - bool operator!=(const iterator &other) const { return index != other.index; } + const_iterator() { } + const_iterator operator++() { index--; 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 K &operator*() const { return ptr->entries[index].udata; } const K *operator->() const { return &ptr->entries[index].udata; } }; - class const_iterator + class iterator : public std::iterator { friend class pool; protected: - const pool *ptr; + pool *ptr; int index; + iterator(pool *ptr, int index) : ptr(ptr), index(index) { } public: - const_iterator() { } - const_iterator(const pool *ptr, int index) : ptr(ptr), index(index) { } - const_iterator operator++() { index--; return *this; } - bool operator==(const const_iterator &other) const { return index == other.index; } - bool operator!=(const const_iterator &other) const { return index != other.index; } + iterator() { } + iterator operator++() { index--; return *this; } + bool operator==(const iterator &other) const { return index == other.index; } + bool operator!=(const iterator &other) const { return index != other.index; } + K &operator*() { return ptr->entries[index].udata; } + K *operator->() { return &ptr->entries[index].udata; } const K &operator*() const { return ptr->entries[index].udata; } const K *operator->() const { return &ptr->entries[index].udata; } + operator const_iterator() const { return const_iterator(ptr, index); } }; pool() @@ -703,7 +856,7 @@ public: iterator erase(iterator it) { - int hash = do_hash(it->first); + int hash = do_hash(*it); do_erase(it.index, hash); return ++it; } @@ -715,6 +868,13 @@ public: return i < 0 ? 0 : 1; } + int count(const K &key, const_iterator it) const + { + int hash = do_hash(key); + int i = do_lookup(key, hash); + return i < 0 || i > it.index ? 0 : 1; + } + iterator find(const K &key) { int hash = do_hash(key); @@ -740,6 +900,21 @@ public: return i >= 0; } + template> + void sort(Compare comp = Compare()) + { + std::sort(entries.begin(), entries.end(), [comp](const entry_t &a, const entry_t &b){ return comp(b.udata, a.udata); }); + do_rehash(); + } + + K pop() + { + iterator it = begin(); + K ret = *it; + erase(it); + return ret; + } + void swap(pool &other) { hashtable.swap(other.hashtable); @@ -756,20 +931,199 @@ public: } bool operator!=(const pool &other) const { - return !(*this == other); + return !operator==(other); + } + + bool hash() const { + unsigned int hashval = mkhash_init; + for (auto &it : entries) + hashval ^= ops.hash(it.udata); + return hashval; } + void reserve(size_t n) { entries.reserve(n); } size_t size() const { return entries.size(); } bool empty() const { return entries.empty(); } void clear() { hashtable.clear(); entries.clear(); } iterator begin() { return iterator(this, int(entries.size())-1); } + iterator element(int n) { return iterator(this, int(entries.size())-1-n); } iterator end() { return iterator(nullptr, -1); } const_iterator begin() const { return const_iterator(this, int(entries.size())-1); } + const_iterator element(int n) const { return const_iterator(this, int(entries.size())-1-n); } const_iterator end() const { return const_iterator(nullptr, -1); } }; +template +class idict +{ + pool database; + +public: + typedef typename pool::const_iterator const_iterator; + + int operator()(const K &key) + { + int hash = database.do_hash(key); + int i = database.do_lookup(key, hash); + if (i < 0) + i = database.do_insert(key, hash); + return i + offset; + } + + int at(const K &key) const + { + int hash = database.do_hash(key); + int i = database.do_lookup(key, hash); + if (i < 0) + throw std::out_of_range("idict::at()"); + return i + offset; + } + + int at(const K &key, int defval) const + { + int hash = database.do_hash(key); + int i = database.do_lookup(key, hash); + if (i < 0) + return defval; + return i + offset; + } + + int count(const K &key) const + { + int hash = database.do_hash(key); + int i = database.do_lookup(key, hash); + return i < 0 ? 0 : 1; + } + + void expect(const K &key, int i) + { + int j = (*this)(key); + if (i != j) + throw std::out_of_range("idict::expect()"); + } + + const K &operator[](int index) const + { + return database.entries.at(index - offset).udata; + } + + void swap(idict &other) + { + database.swap(other.database); + } + + void reserve(size_t n) { database.reserve(n); } + 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 element(int n) const { return database.element(n); } + const_iterator end() const { return database.end(); } +}; + +template +class mfp +{ + mutable idict database; + mutable std::vector parents; + +public: + typedef typename idict::const_iterator const_iterator; + + 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; + } + + int lookup(const K &a) const + { + return ifind((*this)(a)); + } + + const K &find(const K &a) const + { + int i = database.at(a, -1); + if (i < 0) + return a; + return (*this)[ifind(i)]; + } + + void merge(const K &a, const K &b) + { + imerge((*this)(a), (*this)(b)); + } + + void promote(const K &a) + { + int i = database.at(a, -1); + if (i >= 0) + ipromote(i); + } + + void swap(mfp &other) + { + database.swap(other.database); + parents.swap(other.parents); + } + + void reserve(size_t n) { database.reserve(n); } + size_t size() const { return database.size(); } + bool empty() const { return database.empty(); } + void clear() { database.clear(); parents.clear(); } + + const_iterator begin() const { return database.begin(); } + const_iterator element(int n) const { return database.element(n); } + const_iterator end() const { return database.end(); } +}; + } /* namespace hashlib */ #endif