summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/netlist/plib/plists.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/netlist/plib/plists.h')
-rw-r--r--src/lib/netlist/plib/plists.h488
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;
};