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.h350
1 files changed, 305 insertions, 45 deletions
diff --git a/src/emu/netlist/plib/plists.h b/src/emu/netlist/plib/plists.h
index 032f123aab1..ab8ebf414c7 100644
--- a/src/emu/netlist/plib/plists.h
+++ b/src/emu/netlist/plib/plists.h
@@ -11,6 +11,8 @@
#define PLISTS_H_
#include <cstring>
+#include <algorithm>
+#include <cmath>
#include "palloc.h"
#include "pstring.h"
@@ -58,12 +60,17 @@ public:
* array works around this.
*/
- ATTR_HOT /* inline */ _ListClass *data() { return m_list; }
+ ATTR_HOT _ListClass *data() { return m_list; }
- ATTR_HOT /* inline */ _ListClass& operator[](std::size_t index) { return m_list[index]; }
- ATTR_HOT /* inline */ const _ListClass& operator[](std::size_t index) const { return m_list[index]; }
+ ATTR_HOT _ListClass& operator[](std::size_t index) { return m_list[index]; }
+ ATTR_HOT const _ListClass& operator[](std::size_t index) const { return m_list[index]; }
- ATTR_HOT /* inline */ std::size_t size() const { return m_capacity; }
+ 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)
@@ -96,7 +103,7 @@ public:
plist_t() : std::vector<_ListClass>() {}
plist_t(const int numElements) : std::vector<_ListClass>(numElements) {}
- /* inline */ void add(const _ListClass &elem) { this->push_back(elem); }
+ void add(const _ListClass &elem) { this->push_back(elem); }
void clear_and_free()
{
for (_ListClass *i = this->data(); i < this->data() + this->size(); i++)
@@ -105,7 +112,7 @@ public:
}
this->clear();
}
- /* inline */ bool contains(const _ListClass &elem) const
+ bool contains(const _ListClass &elem) const
{
for (const _ListClass *i = this->data(); i < this->data() + this->size(); i++)
{
@@ -115,7 +122,7 @@ public:
return false;
}
- /* inline */ void remove(const _ListClass &elem)
+ void remove(const _ListClass &elem)
{
for (int i = 0; i < this->size(); i++)
{
@@ -126,12 +133,12 @@ public:
}
}
}
- /* inline */ void remove_at(const int pos)
+ void remove_at(const int pos)
{
this->erase(this->begin() + pos);
}
- /* inline */ int indexof(const _ListClass &elem) const
+ int indexof(const _ListClass &elem) const
{
for (int i = 0; i < this->size(); i++)
{
@@ -141,7 +148,7 @@ public:
return -1;
}
- ATTR_HOT /* inline */ void swap(const int pos1, const int pos2)
+ ATTR_HOT void swap(const int pos1, const int pos2)
{
//nl_assert((pos1>=0) && (pos1<m_count));
//nl_assert((pos2>=0) && (pos2<m_count));
@@ -200,12 +207,12 @@ public:
m_list = NULL;
}
- ATTR_HOT /* inline */ _ListClass *data() { return m_list; }
+ ATTR_HOT _ListClass *data() { return m_list; }
- ATTR_HOT /* inline */ _ListClass& operator[](std::size_t index) { return *(m_list + index); }
- ATTR_HOT /* inline */ const _ListClass& operator[](std::size_t index) const { return *(m_list + index); }
+ ATTR_HOT _ListClass& operator[](std::size_t index) { return *(m_list + index); }
+ ATTR_HOT const _ListClass& operator[](std::size_t index) const { return *(m_list + index); }
- ATTR_HOT /* inline */ void add(const _ListClass &elem)
+ ATTR_HOT void add(const _ListClass &elem)
{
if (m_count >= m_capacity){
std::size_t new_size = m_capacity * 2;
@@ -217,7 +224,21 @@ public:
m_list[m_count++] = elem;
}
- ATTR_HOT /* inline */ void remove(const _ListClass &elem)
+ ATTR_HOT void insert_at(const _ListClass &elem, const std::size_t index)
+ {
+ if (m_count >= m_capacity){
+ std::size_t new_size = m_capacity * 2;
+ if (new_size < 32)
+ new_size = 32;
+ set_capacity(new_size);
+ }
+ for (std::size_t i = m_count; i>index; i--)
+ m_list[i] = m_list[i-1];
+ m_list[index] = elem;
+ m_count++;
+ }
+
+ ATTR_HOT void remove(const _ListClass &elem)
{
for (std::size_t i = 0; i < m_count; i++)
{
@@ -234,7 +255,7 @@ public:
}
}
- ATTR_HOT /* inline */ void remove_at(const std::size_t pos)
+ ATTR_HOT void remove_at(const std::size_t pos)
{
//nl_assert((pos>=0) && (pos<m_count));
m_count--;
@@ -244,7 +265,7 @@ public:
}
}
- ATTR_HOT /* inline */ void swap(const std::size_t pos1, const std::size_t pos2)
+ ATTR_HOT void swap(const std::size_t pos1, const std::size_t pos2)
{
//nl_assert((pos1>=0) && (pos1<m_count));
//nl_assert((pos2>=0) && (pos2<m_count));
@@ -253,7 +274,7 @@ public:
m_list[pos2] =tmp;
}
- ATTR_HOT /* inline */ bool contains(const _ListClass &elem) const
+ ATTR_HOT bool contains(const _ListClass &elem) const
{
for (_ListClass *i = m_list; i < m_list + m_count; i++)
{
@@ -263,7 +284,7 @@ public:
return false;
}
- ATTR_HOT /* inline */ int indexof(const _ListClass &elem) const
+ ATTR_HOT int indexof(const _ListClass &elem) const
{
for (std::size_t i = 0; i < m_count; i++)
{
@@ -273,10 +294,10 @@ public:
return -1;
}
- ATTR_HOT /* inline */ std::size_t size() const { return m_count; }
- ATTR_HOT /* inline */ bool is_empty() const { return (m_count == 0); }
- ATTR_HOT /* inline */ void clear() { m_count = 0; }
- ATTR_HOT /* inline */ std::size_t capacity() const { return m_capacity; }
+ ATTR_HOT std::size_t size() const { return m_count; }
+ ATTR_HOT bool is_empty() const { return (m_count == 0); }
+ ATTR_HOT void clear() { m_count = 0; }
+ ATTR_HOT std::size_t capacity() const { return m_capacity; }
ATTR_COLD void clear_and_free()
{
@@ -298,10 +319,12 @@ private:
if (cnt > new_capacity)
cnt = new_capacity;
- for (_ListClass *ps = m_list; ps < m_list + cnt; ps++, pd++)
- *pd = *ps;
if (m_list != NULL)
+ {
+ for (_ListClass *ps = m_list; ps < m_list + cnt; ps++, pd++)
+ *pd = *ps;
this->dealloc(m_list);
+ }
m_list = m_new;
m_count = cnt;
}
@@ -347,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));
@@ -366,9 +397,9 @@ public:
}
private:
- template <typename T> static const pstring get_name(const T *elem) { return elem->name(); }
- template <typename T> static const pstring get_name(T *elem) { return elem->name(); }
- template <typename T> static const pstring get_name(const T &elem) { return elem.name(); }
+ template <typename T> const pstring &get_name(const T *elem) const { return elem->name(); }
+ template <typename T> const pstring &get_name(T *elem) const { return elem->name(); }
+ template <typename T> const pstring &get_name(const T &elem) const { return elem.name(); }
};
@@ -403,27 +434,27 @@ public:
{
}
- ATTR_HOT /* inline */ void push(const _StackClass &elem)
+ ATTR_HOT void push(const _StackClass &elem)
{
m_list.add(elem);
}
- ATTR_HOT /* inline */ _StackClass peek() const
+ ATTR_HOT _StackClass peek() const
{
return m_list[m_list.size() - 1];
}
- ATTR_HOT /* inline */ _StackClass pop()
+ ATTR_HOT _StackClass pop()
{
_StackClass ret = peek();
m_list.remove_at(m_list.size() - 1);
return ret;
}
- ATTR_HOT /* inline */ int count() const { return m_list.size(); }
- ATTR_HOT /* inline */ bool empty() const { return (m_list.size() == 0); }
- ATTR_HOT /* inline */ void reset() { m_list.reset(); }
- ATTR_HOT /* inline */ int capacity() const { return m_list.capacity(); }
+ ATTR_HOT int count() const { return m_list.size(); }
+ ATTR_HOT bool empty() const { return (m_list.size() == 0); }
+ ATTR_HOT void reset() { m_list.reset(); }
+ ATTR_HOT int capacity() const { return m_list.capacity(); }
private:
plist_t<_StackClass> m_list;
@@ -448,7 +479,7 @@ public:
plinkedlist_t() : m_head(NULL) {}
- ATTR_HOT /* inline */ void insert(const _ListClass &before, _ListClass &elem)
+ ATTR_HOT void insert(const _ListClass &before, _ListClass &elem)
{
if (m_head == &before)
{
@@ -473,13 +504,13 @@ public:
}
}
- ATTR_HOT /* inline */ void insert(_ListClass &elem)
+ ATTR_HOT void insert(_ListClass &elem)
{
elem.m_next = m_head;
m_head = &elem;
}
- ATTR_HOT /* inline */ void add(_ListClass &elem)
+ ATTR_HOT void add(_ListClass &elem)
{
_ListClass **p = &m_head;
while (*p != NULL)
@@ -490,7 +521,7 @@ public:
elem.m_next = NULL;
}
- ATTR_HOT /* inline */ void remove(const _ListClass &elem)
+ ATTR_HOT void remove(const _ListClass &elem)
{
_ListClass **p = &m_head;
while (*p != &elem)
@@ -502,11 +533,11 @@ public:
}
- ATTR_HOT static /* inline */ _ListClass *next(const _ListClass &elem) { return elem.m_next; }
- ATTR_HOT static /* inline */ _ListClass *next(const _ListClass *elem) { return elem->m_next; }
- ATTR_HOT /* inline */ _ListClass *first() const { return m_head; }
- ATTR_HOT /* inline */ void clear() { m_head = NULL; }
- ATTR_HOT /* inline */ bool is_empty() const { return (m_head == NULL); }
+ ATTR_HOT static _ListClass *next(const _ListClass &elem) { return elem.m_next; }
+ ATTR_HOT static _ListClass *next(const _ListClass *elem) { return elem->m_next; }
+ ATTR_HOT _ListClass *first() const { return m_head; }
+ ATTR_HOT void clear() { m_head = NULL; }
+ ATTR_HOT bool is_empty() const { return (m_head == NULL); }
private:
_ListClass *m_head;
@@ -524,7 +555,6 @@ public:
pstring_list_t(const pstring &str, const pstring &onstr, bool ignore_empty = false)
: plist_t<pstring>()
{
-
int p = 0;
int pn;
@@ -582,4 +612,234 @@ 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.
+// ----------------------------------------------------------------------------------------
+
+template<typename Class>
+static inline void psort_list(Class &sl)
+{
+ for(unsigned i = 0; i < sl.size(); i++)
+ {
+ for(unsigned j = i + 1; j < sl.size(); j++)
+ if(sl[i] > sl[j])
+ std::swap(sl[i], sl[j]);
+
+ }
+}
+
#endif /* PLISTS_H_ */