diff options
Diffstat (limited to 'src/lib/netlist/plib/plists.h')
-rw-r--r-- | src/lib/netlist/plib/plists.h | 852 |
1 files changed, 852 insertions, 0 deletions
diff --git a/src/lib/netlist/plib/plists.h b/src/lib/netlist/plib/plists.h new file mode 100644 index 00000000000..dd26cfb963b --- /dev/null +++ b/src/lib/netlist/plib/plists.h @@ -0,0 +1,852 @@ +// license:GPL-2.0+ +// copyright-holders:Couriersud +/* + * plists.h + * + */ + +#pragma once + +#ifndef PLISTS_H_ +#define PLISTS_H_ + +#include <cstring> +#include <algorithm> +#include <cmath> + +#include "palloc.h" +#include "pstring.h" + +// ---------------------------------------------------------------------------------------- +// parray_t: dynamic array +// ---------------------------------------------------------------------------------------- + +template <class _ListClass> +class parray_t +{ +public: + + ATTR_COLD parray_t(std::size_t numElements) + : m_list(0), m_capacity(0) + { + set_capacity(numElements); + } + + ATTR_COLD parray_t(const parray_t &rhs) + : m_list(0), m_capacity(0) + { + set_capacity(rhs.size()); + for (std::size_t i=0; i<m_capacity; i++) + m_list[i] = rhs[i]; + } + + ATTR_COLD parray_t &operator=(const parray_t &rhs) + { + set_capacity(rhs.size()); + for (std::size_t i=0; i<m_capacity; i++) + m_list[i] = rhs[i]; + return *this; + } + + ~parray_t() + { + if (m_list != NULL) + pfree_array(m_list); + m_list = NULL; + } + + /* using the [] operator will not allow gcc to vectorize code because + * basically a pointer is returned. + * array works around this. + */ + + ATTR_HOT _ListClass *data() { return m_list; } + + 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 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) + { + if (m_list != NULL) + pfree_array(m_list); + if (new_capacity > 0) + m_list = palloc_array(_ListClass, new_capacity); + else + m_list = NULL; + m_capacity = new_capacity; + } + +private: + + _ListClass * m_list; + int m_capacity; +}; + +// ---------------------------------------------------------------------------------------- +// plist_t: a simple list +// ---------------------------------------------------------------------------------------- +#if 0 +#include <vector> +//#define plist_t std::vector +template <typename _ListClass> +class plist_t : public std::vector<_ListClass> +{ +public: + plist_t() : std::vector<_ListClass>() {} + plist_t(const int numElements) : std::vector<_ListClass>(numElements) {} + + void add(const _ListClass &elem) { this->push_back(elem); } + void clear_and_free() + { + for (_ListClass *i = this->data(); i < this->data() + this->size(); i++) + { + pfree(*i); + } + this->clear(); + } + bool contains(const _ListClass &elem) const + { + for (const _ListClass *i = this->data(); i < this->data() + this->size(); i++) + { + if (*i == elem) + return true; + } + return false; + } + + void remove(const _ListClass &elem) + { + for (int i = 0; i < this->size(); i++) + { + if (this->at(i) == elem) + { + this->erase(this->begin() + i); + return; + } + } + } + void remove_at(const int pos) + { + this->erase(this->begin() + pos); + } + + int indexof(const _ListClass &elem) const + { + for (int i = 0; i < this->size(); i++) + { + if (this->at(i) == elem) + return i; + } + return -1; + } + + ATTR_HOT void swap(const int pos1, const int pos2) + { + //nl_assert((pos1>=0) && (pos1<m_count)); + //nl_assert((pos2>=0) && (pos2<m_count)); + _ListClass tmp = (*this)[pos1]; + (*this)[pos1] = (*this)[pos2]; + (*this)[pos2] =tmp; + } + +}; + +#else +template <typename _ListClass> +class plist_t +{ +public: + + ATTR_COLD plist_t(const std::size_t numElements = 0) + { + m_capacity = numElements; + if (m_capacity == 0) + m_list = NULL; + else + m_list = this->alloc(m_capacity); + m_count = 0; + } + + ATTR_COLD plist_t(const plist_t &rhs) + { + m_capacity = rhs.capacity(); + if (m_capacity == 0) + m_list = NULL; + else + m_list = this->alloc(m_capacity); + m_count = 0; + for (std::size_t i=0; i<rhs.size(); i++) + { + this->add(rhs[i]); + } + } + + ATTR_COLD plist_t &operator=(const plist_t &rhs) + { + this->clear(); + for (std::size_t i=0; i<rhs.size(); i++) + { + this->add(rhs[i]); + } + return *this; + } + + + ~plist_t() + { + if (m_list != NULL) + this->dealloc(m_list); + m_list = NULL; + } + + ATTR_HOT _ListClass *data() { return m_list; } + + 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 void add(const _ListClass &elem) + { + if (m_count >= m_capacity){ + std::size_t new_size = m_capacity * 2; + if (new_size < 32) + new_size = 32; + set_capacity(new_size); + } + + m_list[m_count++] = 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++) + { + if (m_list[i] == elem) + { + m_count --; + while (i < m_count) + { + m_list[i] = m_list[i+1]; + i++; + } + return; + } + } + } + + ATTR_HOT void remove_at(const std::size_t pos) + { + //nl_assert((pos>=0) && (pos<m_count)); + m_count--; + for (std::size_t i = pos; i < m_count; i++) + { + m_list[i] = m_list[i+1]; + } + } + + 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)); + _ListClass tmp = m_list[pos1]; + m_list[pos1] = m_list[pos2]; + m_list[pos2] =tmp; + } + + ATTR_HOT bool contains(const _ListClass &elem) const + { + for (_ListClass *i = m_list; i < m_list + m_count; i++) + { + if (*i == elem) + return true; + } + return false; + } + + ATTR_HOT int indexof(const _ListClass &elem) const + { + for (std::size_t i = 0; i < m_count; i++) + { + if (m_list[i] == elem) + return i; + } + return -1; + } + + 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() + { + for (_ListClass *i = m_list; i < m_list + m_count; i++) + { + pfree(*i); + } + clear(); + } + +private: + ATTR_COLD void set_capacity(const std::size_t new_capacity) + { + std::size_t cnt = size(); + if (new_capacity > 0) + { + _ListClass *m_new = this->alloc(new_capacity); + _ListClass *pd = m_new; + + if (cnt > new_capacity) + cnt = new_capacity; + 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; + } + else + { + if (m_list != NULL) + this->dealloc(m_list); + m_list = NULL; + m_count = 0; + } + m_capacity = new_capacity; + } + + _ListClass *alloc(const std::size_t n) + { + return palloc_array(_ListClass, n); + } + + void dealloc(_ListClass *p) + { + pfree_array(p); + } + + std::size_t m_count; + _ListClass * m_list; + std::size_t m_capacity; +}; +#endif + +// ---------------------------------------------------------------------------------------- +// pnamedlist_t: a simple list of elements which have a name() interface +// ---------------------------------------------------------------------------------------- + +template <class _ListClass> +class pnamedlist_t : public plist_t<_ListClass> +{ +public: + _ListClass find_by_name(const pstring &name) const + { + for (std::size_t i=0; i < this->size(); i++) + if (get_name((*this)[i]) == name) + return (*this)[i]; + 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)); + } + + bool add(_ListClass dev, bool allow_duplicate) + { + if (allow_duplicate) + plist_t<_ListClass>::add(dev); + else + { + if (!(this->find_by_name(get_name(dev)) == _ListClass(NULL))) + return false; + plist_t<_ListClass>::add(dev); + } + return true; + } + +private: + 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(); } + +}; + + +// ---------------------------------------------------------------------------------------- +// pstack_t: a simple stack +// ---------------------------------------------------------------------------------------- + +template <class _StackClass> +class pstack_t +{ +public: + + ATTR_COLD pstack_t(const int numElements = 128) + : m_list(numElements) + { + } + + ATTR_COLD pstack_t(const pstack_t &rhs) + : m_list(rhs.m_list) + { + } + + ATTR_COLD pstack_t &operator=(const pstack_t &rhs) + { + m_list = rhs.m_list; + return *this; + } + + + ~pstack_t() + { + } + + ATTR_HOT void push(const _StackClass &elem) + { + m_list.add(elem); + } + + ATTR_HOT _StackClass peek() const + { + return m_list[m_list.size() - 1]; + } + + ATTR_HOT _StackClass pop() + { + _StackClass ret = peek(); + m_list.remove_at(m_list.size() - 1); + return ret; + } + + 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; +}; + +template <class _ListClass> +struct plinkedlist_element_t +{ + plinkedlist_element_t() : m_next(NULL) {} + _ListClass * m_next; + +}; + +// ---------------------------------------------------------------------------------------- +// plinkedlist_t: a simple linked list +// ---------------------------------------------------------------------------------------- + +template <class _ListClass> +class plinkedlist_t +{ +public: + + plinkedlist_t() : m_head(NULL) {} + + ATTR_HOT void insert(const _ListClass &before, _ListClass &elem) + { + if (m_head == &before) + { + elem.m_next = m_head; + m_head = elem; + } + else + { + _ListClass *p = m_head; + while (p != NULL) + { + if (p->m_next == &before) + { + elem->m_next = &before; + p->m_next = &elem; + return; + } + p = p->m_next; + } + throw pexception("element not found"); + } + } + + ATTR_HOT void insert(_ListClass &elem) + { + elem.m_next = m_head; + m_head = &elem; + } + + ATTR_HOT void add(_ListClass &elem) + { + _ListClass **p = &m_head; + while (*p != NULL) + { + p = &((*p)->m_next); + } + *p = &elem; + elem.m_next = NULL; + } + + ATTR_HOT void remove(const _ListClass &elem) + { + _ListClass **p = &m_head; + while (*p != &elem) + { + //nl_assert(*p != NULL); + p = &((*p)->m_next); + } + (*p) = elem.m_next; + } + + + 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; +}; + +// ---------------------------------------------------------------------------------------- +// string list +// ---------------------------------------------------------------------------------------- + +class pstring_list_t : public plist_t<pstring> +{ +public: + pstring_list_t() : plist_t<pstring>() { } + + pstring_list_t(const pstring &str, const pstring &onstr, bool ignore_empty = false) + : plist_t<pstring>() + { + int p = 0; + int pn; + + pn = str.find(onstr, p); + while (pn>=0) + { + pstring t = str.substr(p, pn - p); + if (!ignore_empty || t.len() != 0) + this->add(t); + p = pn + onstr.len(); + pn = str.find(onstr, p); + } + if (p < (int) str.len()) + { + pstring t = str.substr(p); + if (!ignore_empty || t.len() != 0) + this->add(t); + } + } + + static pstring_list_t splitexpr(const pstring &str, const pstring_list_t &onstrl) + { + pstring_list_t temp; + pstring col = ""; + + unsigned i = 0; + while (i<str.blen()) + { + int p = -1; + for (std::size_t j=0; j < onstrl.size(); j++) + { + if (std::memcmp(onstrl[j].cstr(), &(str.cstr()[i]), onstrl[j].blen())==0) + { + p = j; + break; + } + } + if (p>=0) + { + if (col != "") + temp.add(col); + + col = ""; + temp.add(onstrl[p]); + i += onstrl[p].blen(); + } + else + { + pstring::traits::code_t c = pstring::traits::code(str.cstr() + i); + col += c; + i+=pstring::traits::codelen(c); + } + } + if (col != "") + temp.add(col); + return temp; + } +}; + +// ---------------------------------------------------------------------------------------- +// hashmap list +// ---------------------------------------------------------------------------------------- + + +template <class C> +struct phash_functor +{ + phash_functor() + {} + phash_functor(const C &v) + { + m_hash = v; + } + friend unsigned operator%(const phash_functor &lhs, const unsigned &rhs) { return lhs.m_hash % rhs; } + bool operator==(const phash_functor &lhs) const { return (m_hash == lhs.m_hash); } +private: + unsigned m_hash; +}; + +template <> +struct phash_functor<pstring> +{ + phash_functor() + {} + phash_functor(const pstring &v) + { + /* modified djb2 */ + const pstring::mem_t *string = v.cstr(); + unsigned result = 5381; + for (pstring::mem_t c = *string; c != 0; c = *string++) + result = ((result << 5) + result ) ^ (result >> (32 - 5)) ^ c; + //result = (result*33) ^ c; + m_hash = result; + } + friend unsigned operator%(const phash_functor<pstring> &lhs, const unsigned &rhs) { return lhs.m_hash % rhs; } + bool operator==(const phash_functor<pstring> &lhs) const { return (m_hash == lhs.m_hash); } +private: + unsigned m_hash; +}; + +#if 0 +#if 0 + 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; + } +#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 +#endif + +template <class K, class V, class H = phash_functor<K> > +class phashmap_t +{ +public: + phashmap_t() : m_hash(37) + { + for (unsigned i=0; i<m_hash.size(); i++) + m_hash[i] = -1; + } + + ~phashmap_t() + { + } + + struct element_t + { + element_t() { } + element_t(const K &key, const H &hash, const V &value) + : m_key(key), m_hash(hash), m_value(value), m_next(-1) + {} + K m_key; + H m_hash; + V m_value; + int m_next; + }; + + void clear() + { +#if 0 + 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"); + } +#endif + 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() * 3 / 2 > m_hash.size()) + { + unsigned n = std::sqrt( 2 * m_hash.size()); + n = n * n + n + 41; + m_hash.resize(n); + rebuild(); + } + const 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; + } + + 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) { return m_values[pos].m_key; } +private: + + int get_idx(const K &key) const + { + 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_ */ |