diff options
Diffstat (limited to 'src/emu/netlist/plib/plists.h')
-rw-r--r-- | src/emu/netlist/plib/plists.h | 227 |
1 files changed, 227 insertions, 0 deletions
diff --git a/src/emu/netlist/plib/plists.h b/src/emu/netlist/plib/plists.h index e54c63f38e0..ab8ebf414c7 100644 --- a/src/emu/netlist/plib/plists.h +++ b/src/emu/netlist/plib/plists.h @@ -12,6 +12,7 @@ #include <cstring> #include <algorithm> +#include <cmath> #include "palloc.h" #include "pstring.h" @@ -66,6 +67,11 @@ public: ATTR_HOT std::size_t size() const { return m_capacity; } + void resize(const std::size_t new_size) + { + set_capacity(new_size); + } + protected: ATTR_COLD void set_capacity(const std::size_t new_capacity) { @@ -364,6 +370,14 @@ public: return _ListClass(NULL); } + int index_by_name(const pstring &name) const + { + for (std::size_t i=0; i < this->size(); i++) + if (get_name((*this)[i]) == name) + return (int) i; + return -1; + } + void remove_by_name(const pstring &name) { plist_t<_ListClass>::remove(find_by_name(name)); @@ -599,6 +613,219 @@ public: }; // ---------------------------------------------------------------------------------------- +// hashmap list +// ---------------------------------------------------------------------------------------- + + +template <class C> +struct phash_functor +{ + unsigned hash(const C &v) const { return (unsigned) v; } +}; + +template <> +struct phash_functor<pstring> +{ +#if 1 +#if 1 + unsigned hash(const pstring &v) const + { + const char *string = v.cstr(); + unsigned result = *string++; + for (UINT8 c = *string++; c != 0; c = *string++) + result = (result*33) ^ c; + return result; + } +#else + unsigned hash(const pstring &v) const + { + /* Fowler–Noll–Vo hash - FNV-1 */ + const char *string = v.cstr(); + unsigned result = 2166136261; + for (UINT8 c = *string++; c != 0; c = *string++) + result = (result * 16777619) ^ c; + // result = (result ^ c) * 16777619; FNV 1a + return result; + } +#endif +#else + unsigned hash(const pstring &v) const + { + /* jenkins one at a time algo */ + unsigned result = 0; + const char *string = v.cstr(); + while (*string) + { + result += *string; + string++; + result += (result << 10); + result ^= (result >> 6); + } + result += (result << 3); + result ^= (result >> 11); + result += (result << 15); + return result; + } +#endif +}; + +template <class K, class V, class H = phash_functor<K> > +class phashmap_t +{ +public: + phashmap_t() : m_hash(17) + { + for (unsigned i=0; i<m_hash.size(); i++) + m_hash[i] = -1; + } + + ~phashmap_t() + { + } + + struct element_t + { + element_t() { } + element_t(K key, unsigned hash, V value) + : m_key(key), m_hash(hash), m_value(value), m_next(-1) + {} + K m_key; + unsigned m_hash; + V m_value; + int m_next; + }; + + void clear() + { + if (0) + { + unsigned cnt = 0; + for (unsigned i=0; i<m_hash.size(); i++) + if (m_hash[i] >= 0) + cnt++; + const unsigned s = m_values.size(); + if (s>0) + printf("phashmap: %d elements %d hashsize, percent in overflow: %d\n", s, (unsigned) m_hash.size(), (s - cnt) * 100 / s); + else + printf("phashmap: No elements .. \n"); + } + m_values.clear(); + for (unsigned i=0; i<m_hash.size(); i++) + m_hash[i] = -1; + } + + bool contains(const K &key) const + { + return (get_idx(key) >= 0); + } + + int index_of(const K &key) const + { + return get_idx(key); + } + + unsigned size() const { return m_values.size(); } + + bool add(const K &key, const V &value) + { + /* + * we are using the Euler prime function here + * + * n * n + n + 41 | 40 >= n >=0 + * + * and accept that outside we will not have a prime + * + */ + if (m_values.size() > m_hash.size()) + { + unsigned n = std::sqrt( 2 * m_hash.size()); + n = n * n + n + 41; + m_hash.resize(n); + rebuild(); + } + const H h; + const unsigned hash=h.hash(key); + const unsigned pos = hash % m_hash.size(); + if (m_hash[pos] == -1) + { + unsigned vpos = m_values.size(); + m_values.add(element_t(key, hash, value)); + m_hash[pos] = vpos; + } + else + { + int ep = m_hash[pos]; + + for (; ep != -1; ep = m_values[ep].m_next) + { + if (m_values[ep].m_hash == hash && m_values[ep].m_key == key ) + return false; /* duplicate */ + } + unsigned vpos = m_values.size(); + m_values.add(element_t(key, hash, value)); + m_values[vpos].m_next = m_hash[pos]; + m_hash[pos] = vpos; + } + return true; + } + + V& operator[](const K &key) + { + int p = get_idx(key); + if (p == -1) + { + p = m_values.size(); + add(key, V()); + } + return m_values[p].m_value; + } + + const V& operator[](const K &key) const + { + int p = get_idx(key); + if (p == -1) + { + p = m_values.size(); + add(key, V()); + } + return m_values[p].m_value; + } + + V& value_at(const unsigned pos) { return m_values[pos].m_value; } + const V& value_at(const unsigned pos) const { return m_values[pos].m_value; } + + V& key_at(const unsigned pos) const { return m_values[pos].m_key; } +private: + + int get_idx(const K &key) const + { + H h; + const unsigned hash=h.hash(key); + const unsigned pos = hash % m_hash.size(); + + for (int ep = m_hash[pos]; ep != -1; ep = m_values[ep].m_next) + if (m_values[ep].m_hash == hash && m_values[ep].m_key == key ) + return ep; + return -1; + } + + void rebuild() + { + for (unsigned i=0; i<m_hash.size(); i++) + m_hash[i] = -1; + for (unsigned i=0; i<m_values.size(); i++) + { + unsigned pos = m_values[i].m_hash % m_hash.size(); + m_values[i].m_next = m_hash[pos]; + m_hash[pos] = i; + } + + } + plist_t<element_t> m_values; + parray_t<int> m_hash; +}; + +// ---------------------------------------------------------------------------------------- // sort a list ... slow, I am lazy // elements must support ">" operator. // ---------------------------------------------------------------------------------------- |