diff options
Diffstat (limited to 'kernel/hashlib.h')
| -rw-r--r-- | kernel/hashlib.h | 140 |
1 files changed, 134 insertions, 6 deletions
diff --git a/kernel/hashlib.h b/kernel/hashlib.h index f94945eca..f015bf4dd 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -63,18 +63,21 @@ struct hash_int_ops { static inline bool cmp(T a, T b) { return a == b; } +}; + +template<> struct hash_ops<int32_t> : hash_int_ops +{ static inline unsigned int hash(int32_t a) { return a; } +}; +template<> struct hash_ops<int64_t> : hash_int_ops +{ static inline unsigned int hash(int64_t a) { return mkhash(a, a >> 32); } }; -template<> struct hash_ops<int> : hash_int_ops {}; -template<> struct hash_ops<long> : hash_int_ops {}; -template<> struct hash_ops<long long> : hash_int_ops {}; - template<> struct hash_ops<std::string> { static inline bool cmp(const std::string &a, const std::string &b) { return a == b; @@ -118,10 +121,9 @@ template<typename T> struct hash_ops<std::vector<T>> { return a == b; } static inline unsigned int hash(std::vector<T> a) { - hash_ops<T> t_ops; unsigned int h = mkhash_init; for (auto k : a) - h = mkhash(h, t_ops.hash(k)); + h = mkhash(h, hash_ops<T>::hash(k)); return h; } }; @@ -160,6 +162,11 @@ struct hash_obj_ops { } }; +template<typename T> +inline unsigned int mkhash(const T &v) { + return hash_ops<T>().hash(v); +} + inline int hashtable_size(int min_size) { static std::vector<int> zero_and_some_primes = { @@ -188,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 @@ -498,6 +506,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); @@ -888,6 +905,15 @@ public: 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); @@ -907,6 +933,108 @@ 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: + typedef typename idict<K, 0, OPS>::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 + { + 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(); } + const_iterator begin() const { return database.begin(); } const_iterator end() const { return database.end(); } }; |