diff options
Diffstat (limited to 'src/lib/netlist/plib/plists.h')
-rw-r--r-- | src/lib/netlist/plib/plists.h | 461 |
1 files changed, 115 insertions, 346 deletions
diff --git a/src/lib/netlist/plib/plists.h b/src/lib/netlist/plib/plists.h index dd26cfb963b..4e2026cb084 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 -{ -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++) + 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)); - } - - 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(); } - -}; - +class plinkedlist_t; -// ---------------------------------------------------------------------------------------- -// pstack_t: a simple stack -// ---------------------------------------------------------------------------------------- +#if 1 -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) - { - } + friend class plinkedlist_t<_ListClass>; - 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(); } + 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"); } } @@ -541,6 +229,87 @@ 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 @@ -562,7 +331,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,7 +339,7 @@ public: { pstring t = str.substr(p); if (!ignore_empty || t.len() != 0) - this->add(t); + this->push_back(t); } } @@ -594,10 +363,10 @@ public: if (p>=0) { if (col != "") - temp.add(col); + temp.push_back(col); col = ""; - temp.add(onstrl[p]); + temp.push_back(onstrl[p]); i += onstrl[p].blen(); } else @@ -608,7 +377,7 @@ public: } } if (col != "") - temp.add(col); + temp.push_back(col); return temp; } }; @@ -768,7 +537,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 +550,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; } |