diff options
Diffstat (limited to 'src/emu/netlist/plib/plists.h')
-rw-r--r-- | src/emu/netlist/plib/plists.h | 350 |
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_ */ |