diff options
Diffstat (limited to 'src/lib/netlist/plib/plists.h')
-rw-r--r-- | src/lib/netlist/plib/plists.h | 488 |
1 files changed, 126 insertions, 362 deletions
diff --git a/src/lib/netlist/plib/plists.h b/src/lib/netlist/plib/plists.h index dd26cfb963b..d63d4fbe898 100644 --- a/src/lib/netlist/plib/plists.h +++ b/src/lib/netlist/plib/plists.h @@ -13,6 +13,8 @@ #include <cstring> #include <algorithm> #include <cmath> +#include <stack> +#include <vector> #include "palloc.h" #include "pstring.h" @@ -55,15 +57,8 @@ public: 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 _ListClass& operator[](const std::size_t index) { return m_list[index]; } + ATTR_HOT const _ListClass& operator[](const std::size_t index) const { return m_list[index]; } ATTR_HOT std::size_t size() const { return m_capacity; } @@ -93,385 +88,78 @@ private: // ---------------------------------------------------------------------------------------- // 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 +class pvector_t : public std::vector<_ListClass> { public: + pvector_t() : std::vector<_ListClass>() {} - 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) + void clear_and_free() { - 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++) + for (_ListClass i : *this) { - this->add(rhs[i]); + pfree(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() + bool contains(const _ListClass &elem) const { - if (m_list != NULL) - this->dealloc(m_list); - m_list = NULL; + return (std::find(this->begin(), this->end(), elem) != this->end()); } - 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) + void remove(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; + this->erase(std::remove(this->begin(), this->end(), elem), this->end()); } - ATTR_HOT void insert_at(const _ListClass &elem, const std::size_t index) + ATTR_HOT void insert_at(const std::size_t index, 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); - } - 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; - } - } + this->insert(this->begin() + index, elem); } 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; + this->erase(this->begin() + pos); } - ATTR_HOT int indexof(const _ListClass &elem) const + int indexof(const _ListClass &elem) const { - for (std::size_t i = 0; i < m_count; i++) + for (int i = 0; i < this->size(); i++) { - if (m_list[i] == elem) + if (this->at(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 +// plinkedlist_t: a simple linked list +// the list allows insertions / deletions if used properly // ---------------------------------------------------------------------------------------- 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)); - } +class plinkedlist_t; - 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(); } +#if 1 -}; - - -// ---------------------------------------------------------------------------------------- -// pstack_t: a simple stack -// ---------------------------------------------------------------------------------------- - -template <class _StackClass> -class pstack_t +template <class _ListClass> +struct plinkedlist_element_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) - { - } + friend class plinkedlist_t<_ListClass>; - 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(); } + plinkedlist_element_t() : m_next(NULL) {} + _ListClass *next() const { return m_next; } 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 { @@ -499,7 +187,7 @@ public: } p = p->m_next; } - throw pexception("element not found"); + //throw pexception("element not found"); } } @@ -522,18 +210,14 @@ public: ATTR_HOT void remove(const _ListClass &elem) { - _ListClass **p = &m_head; - while (*p != &elem) + _ListClass **p; + for (p = &m_head; *p != &elem; p = &((*p)->m_next)) { //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); } @@ -541,18 +225,99 @@ public: private: _ListClass *m_head; }; +#else + +template <class _ListClass> +struct plinkedlist_element_t +{ +public: + + friend class plinkedlist_t<_ListClass>; + + plinkedlist_element_t() : m_next(NULL), m_prev(NULL) {} + + _ListClass *next() const { return m_next; } +private: + _ListClass * m_next; + _ListClass * m_prev; +}; + +template <class _ListClass> +class plinkedlist_t +{ +public: + + plinkedlist_t() : m_head(NULL), m_tail(NULL) {} + + ATTR_HOT void insert(_ListClass &elem) + { + if (m_head != NULL) + m_head->m_prev = &elem; + elem.m_next = m_head; + elem.m_prev = NULL; + m_head = &elem; + if (m_tail == NULL) + m_tail = &elem; + } + + ATTR_HOT void add(_ListClass &elem) + { + if (m_tail != NULL) + m_tail->m_next = &elem; + elem.m_prev = m_tail; + m_tail = &elem; + elem.m_next = NULL; + if (m_head == NULL) + m_head = &elem; + } + + ATTR_HOT void remove(const _ListClass &elem) + { + if (prev(elem) == NULL) + { + m_head = next(elem); + if (m_tail == &elem) + m_tail = NULL; + } + else + prev(elem)->m_next = next(elem); + + if (next(elem) == NULL) + { + m_tail = prev(elem); + if (m_head == &elem) + m_head = NULL; + } + else + next(elem)->m_prev = prev(elem); + } + + + ATTR_HOT static _ListClass *next(const _ListClass &elem) { return static_cast<_ListClass *>(elem.m_next); } + ATTR_HOT static _ListClass *next(const _ListClass *elem) { return static_cast<_ListClass *>(elem->m_next); } + ATTR_HOT static _ListClass *prev(const _ListClass &elem) { return static_cast<_ListClass *>(elem.m_prev); } + ATTR_HOT static _ListClass *prev(const _ListClass *elem) { return static_cast<_ListClass *>(elem->m_prev); } + ATTR_HOT _ListClass *first() const { return m_head; } + ATTR_HOT void clear() { m_head = m_tail = NULL; } + ATTR_HOT bool is_empty() const { return (m_head == NULL); } + +private: + _ListClass *m_head; + _ListClass *m_tail; +}; +#endif // ---------------------------------------------------------------------------------------- // string list // ---------------------------------------------------------------------------------------- -class pstring_list_t : public plist_t<pstring> +class pstring_vector_t : public pvector_t<pstring> { public: - pstring_list_t() : plist_t<pstring>() { } + pstring_vector_t() : pvector_t<pstring>() { } - pstring_list_t(const pstring &str, const pstring &onstr, bool ignore_empty = false) - : plist_t<pstring>() + pstring_vector_t(const pstring &str, const pstring &onstr, bool ignore_empty = false) + : pvector_t<pstring>() { int p = 0; int pn; @@ -562,7 +327,7 @@ public: { pstring t = str.substr(p, pn - p); if (!ignore_empty || t.len() != 0) - this->add(t); + this->push_back(t); p = pn + onstr.len(); pn = str.find(onstr, p); } @@ -570,13 +335,13 @@ public: { pstring t = str.substr(p); if (!ignore_empty || t.len() != 0) - this->add(t); + this->push_back(t); } } - static pstring_list_t splitexpr(const pstring &str, const pstring_list_t &onstrl) + pstring_vector_t(const pstring &str, const pstring_vector_t &onstrl) + : pvector_t<pstring>() { - pstring_list_t temp; pstring col = ""; unsigned i = 0; @@ -594,10 +359,10 @@ public: if (p>=0) { if (col != "") - temp.add(col); + this->push_back(col); col = ""; - temp.add(onstrl[p]); + this->push_back(onstrl[p]); i += onstrl[p].blen(); } else @@ -608,8 +373,7 @@ public: } } if (col != "") - temp.add(col); - return temp; + this->push_back(col); } }; @@ -768,7 +532,7 @@ public: if (m_hash[pos] == -1) { unsigned vpos = m_values.size(); - m_values.add(element_t(key, hash, value)); + m_values.push_back(element_t(key, hash, value)); m_hash[pos] = vpos; } else @@ -781,7 +545,7 @@ public: return false; /* duplicate */ } unsigned vpos = m_values.size(); - m_values.add(element_t(key, hash, value)); + m_values.push_back(element_t(key, hash, value)); m_values[vpos].m_next = m_hash[pos]; m_hash[pos] = vpos; } @@ -828,7 +592,7 @@ private: } } - plist_t<element_t> m_values; + pvector_t<element_t> m_values; parray_t<int> m_hash; }; |