ice40: split out cells_map.v into ff_map.v

[yosys.git] / kernel / hashlib.h

diff --git a/kernel/hashlib.h b/kernel/hashlib.h
index f740fc50d6d93578e93ed6b9b2444b0cfc7c02c2..592d6e5775dd6f48b7ea5826dcb59d88f25a91b4 100644 (file)
--- a/kernel/hashlib.h
+++ b/kernel/hashlib.h
@@ -10,6 +10,7 @@
 // -------------------------------------------------------
 
 #ifndef HASHLIB_H
+#define HASHLIB_H
 
 #include <stdexcept>
 #include <algorithm>
@@ -74,7 +75,7 @@ template<> struct hash_ops<int32_t> : hash_int_ops
 template<> struct hash_ops<int64_t> : hash_int_ops
 {
        static inline unsigned int hash(int64_t a) {
-               return mkhash(a, a >> 32);
+               return mkhash((unsigned int)(a), (unsigned int)(a >> 32));
        }
 };
 
@@ -95,9 +96,7 @@ template<typename P, typename Q> struct hash_ops<std::pair<P, Q>> {
                return a == b;
        }
        static inline unsigned int hash(std::pair<P, Q> a) {
-               hash_ops<P> p_ops;
-               hash_ops<Q> q_ops;
-               return mkhash(p_ops.hash(a.first), q_ops.hash(a.second));
+               return mkhash(hash_ops<P>::hash(a.first), hash_ops<Q>::hash(a.second));
        }
 };
 
@@ -111,8 +110,8 @@ template<typename... T> struct hash_ops<std::tuple<T...>> {
        }
        template<size_t I = 0>
        static inline typename std::enable_if<I != sizeof...(T), unsigned int>::type hash(std::tuple<T...> a) {
-               hash_ops<typename std::tuple_element<I, std::tuple<T...>>::type> element_ops;
-               return mkhash(hash<I+1>(a), element_ops.hash(std::get<I>(a)));
+               typedef hash_ops<typename std::tuple_element<I, std::tuple<T...>>::type> element_ops_t;
+               return mkhash(hash<I+1>(a), element_ops_t::hash(std::get<I>(a)));
        }
 };
 
@@ -138,8 +137,8 @@ struct hash_cstr_ops {
        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;
        }
 };
 
@@ -148,7 +147,7 @@ struct hash_ptr_ops {
                return a == b;
        }
        static inline unsigned int hash(const void *a) {
-               return (unsigned long)a;
+               return (uintptr_t)a;
        }
 };
 
@@ -158,7 +157,7 @@ struct hash_obj_ops {
        }
        template<typename T>
        static inline unsigned int hash(const T *a) {
-               return a->hash();
+               return a ? a->hash() : 0;
        }
 };
 
@@ -315,11 +314,11 @@ class dict
        int do_insert(const K &key, int &hash)
        {
                if (hashtable.empty()) {
-                       entries.push_back(entry_t(std::pair<K, T>(key, T()), -1));
+                       entries.emplace_back(std::pair<K, T>(key, T()), -1);
                        do_rehash();
                        hash = do_hash(key);
                } else {
-                       entries.push_back(entry_t(std::pair<K, T>(key, T()), hashtable[hash]));
+                       entries.emplace_back(std::pair<K, T>(key, T()), hashtable[hash]);
                        hashtable[hash] = entries.size() - 1;
                }
                return entries.size() - 1;
@@ -328,11 +327,25 @@ class dict
        int do_insert(const std::pair<K, T> &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<K, T> &&rvalue, int &hash)
+       {
+               if (hashtable.empty()) {
+                       auto key = rvalue.first;
+                       entries.emplace_back(std::forward<std::pair<K, T>>(rvalue), -1);
+                       do_rehash();
+                       hash = do_hash(key);
+               } else {
+                       entries.emplace_back(std::forward<std::pair<K, T>>(rvalue), hashtable[hash]);
                        hashtable[hash] = entries.size() - 1;
                }
                return entries.size() - 1;
@@ -442,6 +455,56 @@ public:
                return std::pair<iterator, bool>(iterator(this, i), true);
        }
 
+       std::pair<iterator, bool> insert(std::pair<K, T> &&rvalue)
+       {
+               int hash = do_hash(rvalue.first);
+               int i = do_lookup(rvalue.first, hash);
+               if (i >= 0)
+                       return std::pair<iterator, bool>(iterator(this, i), false);
+               i = do_insert(std::forward<std::pair<K, T>>(rvalue), hash);
+               return std::pair<iterator, bool>(iterator(this, i), true);
+       }
+
+       std::pair<iterator, bool> 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, bool>(iterator(this, i), false);
+               i = do_insert(std::make_pair(key, value), hash);
+               return std::pair<iterator, bool>(iterator(this, i), true);
+       }
+
+       std::pair<iterator, bool> emplace(K const &key, T &&rvalue)
+       {
+               int hash = do_hash(key);
+               int i = do_lookup(key, hash);
+               if (i >= 0)
+                       return std::pair<iterator, bool>(iterator(this, i), false);
+               i = do_insert(std::make_pair(key, std::forward<T>(rvalue)), hash);
+               return std::pair<iterator, bool>(iterator(this, i), true);
+       }
+
+       std::pair<iterator, bool> emplace(K &&rkey, T const &value)
+       {
+               int hash = do_hash(rkey);
+               int i = do_lookup(rkey, hash);
+               if (i >= 0)
+                       return std::pair<iterator, bool>(iterator(this, i), false);
+               i = do_insert(std::make_pair(std::forward<K>(rkey), value), hash);
+               return std::pair<iterator, bool>(iterator(this, i), true);
+       }
+
+       std::pair<iterator, bool> emplace(K &&rkey, T &&rvalue)
+       {
+               int hash = do_hash(rkey);
+               int i = do_lookup(rkey, hash);
+               if (i >= 0)
+                       return std::pair<iterator, bool>(iterator(this, i), false);
+               i = do_insert(std::make_pair(std::forward<K>(rkey), std::forward<T>(rvalue)), hash);
+               return std::pair<iterator, bool>(iterator(this, i), true);
+       }
+
        int erase(const K &key)
        {
                int hash = do_hash(key);
@@ -506,7 +569,7 @@ public:
                return entries[i].udata.second;
        }
 
-       T at(const K &key, const T &defval) const
+       const T& at(const K &key, const T &defval) const
        {
                int hash = do_hash(key);
                int i = do_lookup(key, hash);
@@ -558,9 +621,11 @@ public:
        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); }
 };
 
@@ -577,6 +642,7 @@ protected:
 
                entry_t() { }
                entry_t(const K &udata, int next) : udata(udata), next(next) { }
+               entry_t(K &&udata, int next) : udata(std::move(udata)), next(next) { }
        };
 
        std::vector<int> hashtable;
@@ -680,11 +746,24 @@ protected:
        int do_insert(const K &value, int &hash)
        {
                if (hashtable.empty()) {
-                       entries.push_back(entry_t(value, -1));
+                       entries.emplace_back(value, -1);
                        do_rehash();
                        hash = do_hash(value);
                } 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(K &&rvalue, int &hash)
+       {
+               if (hashtable.empty()) {
+                       entries.emplace_back(std::forward<K>(rvalue), -1);
+                       do_rehash();
+                       hash = do_hash(rvalue);
+               } else {
+                       entries.emplace_back(std::forward<K>(rvalue), hashtable[hash]);
                        hashtable[hash] = entries.size() - 1;
                }
                return entries.size() - 1;
@@ -782,6 +861,22 @@ public:
                return std::pair<iterator, bool>(iterator(this, i), true);
        }
 
+       std::pair<iterator, bool> insert(K &&rvalue)
+       {
+               int hash = do_hash(rvalue);
+               int i = do_lookup(rvalue, hash);
+               if (i >= 0)
+                       return std::pair<iterator, bool>(iterator(this, i), false);
+               i = do_insert(std::forward<K>(rvalue), hash);
+               return std::pair<iterator, bool>(iterator(this, i), true);
+       }
+
+       template<typename... Args>
+       std::pair<iterator, bool> emplace(Args&&... args)
+       {
+               return insert(K(std::forward<Args>(args)...));
+       }
+
        int erase(const K &key)
        {
                int hash = do_hash(key);
@@ -869,15 +964,24 @@ public:
                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); }
 };
 
@@ -887,7 +991,21 @@ class idict
        pool<K, OPS> database;
 
 public:
-       typedef typename pool<K, OPS>::const_iterator const_iterator;
+       class const_iterator : public std::iterator<std::forward_iterator_tag, K>
+       {
+               friend class idict;
+       protected:
+               const idict &container;
+               int index;
+               const_iterator(const idict &container, int index) : container(container), index(index) { }
+       public:
+               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 container[index]; }
+               const K *operator->() const { return &container[index]; }
+       };
 
        int operator()(const K &key)
        {
@@ -945,8 +1063,9 @@ public:
        bool empty() const { return database.empty(); }
        void clear() { database.clear(); }
 
-       const_iterator begin() const { return database.begin(); }
-       const_iterator end() const { return database.end(); }
+       const_iterator begin() const { return const_iterator(*this, offset); }
+       const_iterator element(int n) const { return const_iterator(*this, n); }
+       const_iterator end() const { return const_iterator(*this, offset + size()); }
 };
 
 template<typename K, typename OPS>
@@ -1015,7 +1134,10 @@ public:
 
        const K &find(const K &a) const
        {
-               return (*this)[ifind((*this)(a))];
+               int i = database.at(a, -1);
+               if (i < 0)
+                       return a;
+               return (*this)[ifind(i)];
        }
 
        void merge(const K &a, const K &b)
@@ -1025,7 +1147,9 @@ public:
 
        void promote(const K &a)
        {
-               ipromote((*this)(a));
+               int i = database.at(a, -1);
+               if (i >= 0)
+                       ipromote(i);
        }
 
        void swap(mfp &other)
@@ -1040,6 +1164,7 @@ public:
        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(); }
 };