summaryrefslogtreecommitdiffstatshomepage
path: root/src/emu/netlist/plib/plists.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/emu/netlist/plib/plists.h')
-rw-r--r--src/emu/netlist/plib/plists.h227
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.
// ----------------------------------------------------------------------------------------