diff options
Diffstat (limited to 'src/lib/netlist/plib/plists.h')
-rw-r--r-- | src/lib/netlist/plib/plists.h | 635 |
1 files changed, 429 insertions, 206 deletions
diff --git a/src/lib/netlist/plib/plists.h b/src/lib/netlist/plib/plists.h index 727dad5d936..d6c37eaf5ca 100644 --- a/src/lib/netlist/plib/plists.h +++ b/src/lib/netlist/plib/plists.h @@ -10,283 +10,506 @@ #ifndef PLISTS_H_ #define PLISTS_H_ +#include "palloc.h" +#include "pchrono.h" #include "pstring.h" +#include <algorithm> #include <array> +#include <atomic> +#include <mutex> #include <type_traits> +#include <utility> #include <vector> namespace plib { -/* ---------------------------------------------------------------------------------------- - * uninitialised_array_t: - * fixed size array allowing to override constructor and initialize - * members by placement new. - * - * Use with care. This template is provided to improve locality of storage - * in high frequency applications. It should not be used for anything else. - * ---------------------------------------------------------------------------------------- */ - -template <class C, std::size_t N> -class uninitialised_array_t -{ -public: - using iterator = C *; - using const_iterator = const C *; - - //uninitialised_array_t() noexcept = default; - uninitialised_array_t() noexcept - : m_initialized(0) + /**! fixed size array allowing to override constructor and initialize members by placement new. + * + * Use with care. This template is provided to improve locality of storage + * in high frequency applications. It should not be used for anything else. + * + */ + template <class C, std::size_t N> + class uninitialised_array_t { - } + public: - COPYASSIGNMOVE(uninitialised_array_t, delete) - ~uninitialised_array_t() noexcept - { - if (m_initialized>=N) - for (std::size_t i=0; i<N; i++) - (*this)[i].~C(); - } + using iterator = C *; + using const_iterator = const C *; - size_t size() const { return N; } + //uninitialised_array_t() noexcept = default; + uninitialised_array_t() noexcept + : m_initialized(0) + { + } - C& operator[](const std::size_t &index) noexcept - { - return *reinterpret_cast<C *>(&m_buf[index]); - } + COPYASSIGNMOVE(uninitialised_array_t, delete) + ~uninitialised_array_t() noexcept + { + if (m_initialized>=N) + for (std::size_t i=0; i<N; i++) + (*this)[i].~C(); + } - const C& operator[](const std::size_t &index) const noexcept - { - return *reinterpret_cast<const C *>(&m_buf[index]); - } + size_t size() const { return N; } - template<typename... Args> - void emplace(const std::size_t index, Args&&... args) - { - m_initialized++; - // allocate on buffer - new (&m_buf[index]) C(std::forward<Args>(args)...); - } + C& operator[](const std::size_t &index) noexcept + { + return *reinterpret_cast<C *>(&m_buf[index]); + } - iterator begin() const noexcept { return reinterpret_cast<iterator>(&m_buf[0]); } - iterator end() const noexcept { return reinterpret_cast<iterator>(&m_buf[N]); } + const C& operator[](const std::size_t &index) const noexcept + { + return *reinterpret_cast<const C *>(&m_buf[index]); + } - iterator begin() noexcept { return reinterpret_cast<iterator>(&m_buf[0]); } - iterator end() noexcept { return reinterpret_cast<iterator>(&m_buf[N]); } + template<typename... Args> + void emplace(const std::size_t index, Args&&... args) + { + m_initialized++; + // allocate on buffer + new (&m_buf[index]) C(std::forward<Args>(args)...); + } - const_iterator cbegin() const noexcept { return reinterpret_cast<const_iterator>(&m_buf[0]); } - const_iterator cend() const noexcept { return reinterpret_cast<const_iterator>(&m_buf[N]); } + iterator begin() const noexcept { return reinterpret_cast<iterator>(&m_buf[0]); } + iterator end() const noexcept { return reinterpret_cast<iterator>(&m_buf[N]); } -protected: + iterator begin() noexcept { return reinterpret_cast<iterator>(&m_buf[0]); } + iterator end() noexcept { return reinterpret_cast<iterator>(&m_buf[N]); } -private: + const_iterator cbegin() const noexcept { return reinterpret_cast<const_iterator>(&m_buf[0]); } + const_iterator cend() const noexcept { return reinterpret_cast<const_iterator>(&m_buf[N]); } - /* ensure proper alignment */ - PALIGNAS_VECTOROPT() - std::array<typename std::aligned_storage<sizeof(C), alignof(C)>::type, N> m_buf; - unsigned m_initialized; -}; + protected: -// ---------------------------------------------------------------------------------------- -// plinkedlist_t: a simple linked list -// the list allows insertions / deletions if used properly -// ---------------------------------------------------------------------------------------- + private: -#if 0 -template <class LC> -class linkedlist_t -{ -public: + /* ensure proper alignment */ + PALIGNAS_VECTOROPT() + std::array<typename std::aligned_storage<sizeof(C), alignof(C)>::type, N> m_buf; + unsigned m_initialized; + }; - struct element_t + /**! a simple linked list. + * + * the list allows insertions deletions whilst being processed. + */ + template <class LC> + class linkedlist_t { public: - friend class linkedlist_t<LC>; + struct element_t + { + public: + friend class linkedlist_t<LC>; + + constexpr element_t() : m_next(nullptr), m_prev(nullptr) {} + ~element_t() noexcept = default; - constexpr element_t() : m_next(nullptr) {} - constexpr element_t(const element_t &rhs) = delete; - constexpr element_t(element_t &&rhs) = delete; + COPYASSIGNMOVE(element_t, delete) - constexpr LC *next() const noexcept { return m_next; } + constexpr LC *next() const noexcept { return m_next; } + constexpr LC *prev() const noexcept { return m_prev; } + private: + LC * m_next; + LC * m_prev; + }; + + struct iter_t final : public std::iterator<std::forward_iterator_tag, LC> + { + private: + LC* p; + public: + explicit constexpr iter_t(LC* x) noexcept : p(x) { } + constexpr iter_t(iter_t &rhs) noexcept : p(rhs.p) { } + iter_t(iter_t &&rhs) noexcept { std::swap(*this, rhs); } + iter_t& operator=(const iter_t &rhs) noexcept { if (this != &rhs) p = rhs.p; return *this; } + iter_t& operator=(iter_t &&rhs) noexcept { std::swap(*this, rhs); return *this; } + ~iter_t() = default; + + iter_t& operator++() noexcept { p = p->next();return *this; } + // NOLINTNEXTLINE(cert-dcl21-cpp) + iter_t operator++(int) & noexcept { const iter_t tmp(*this); operator++(); return tmp; } + + constexpr bool operator==(const iter_t& rhs) const noexcept { return p == rhs.p; } + constexpr bool operator!=(const iter_t& rhs) const noexcept { return p != rhs.p; } + C14CONSTEXPR LC& operator*() noexcept { return *p; } + C14CONSTEXPR LC* operator->() noexcept { return p; } + + C14CONSTEXPR LC& operator*() const noexcept { return *p; } + C14CONSTEXPR LC* operator->() const noexcept { return p; } + }; + + constexpr linkedlist_t() : m_head(nullptr) {} + + constexpr iter_t begin() const noexcept { return iter_t(m_head); } + constexpr iter_t end() const noexcept { return iter_t(nullptr); } + + void push_front(LC *elem) noexcept + { + elem->m_next = m_head; + elem->m_prev = nullptr; + if (m_head) + m_head->m_prev = elem; + m_head = elem; + } + + void push_back(LC *elem) noexcept + { + LC ** p(&m_head); + LC * prev(nullptr); + while (*p != nullptr) + { + prev = *p; + p = &((*p)->m_next); + } + *p = elem; + elem->m_prev = prev; + elem->m_next = nullptr; + } + + void remove(const LC *elem) noexcept + { + if (elem->m_prev) + elem->m_prev->m_next = elem->m_next; + else + m_head = elem->m_next; + if (elem->m_next) + elem->m_next->m_prev = elem->m_prev; + else + { + /* update tail */ + } + } + + LC *front() const noexcept { return m_head; } + constexpr bool empty() const noexcept { return (m_head == nullptr); } + void clear() noexcept + { + LC *p(m_head); + while (p != nullptr) + { + LC *n(p->m_next); + p->m_next = nullptr; + p->m_prev = nullptr; + p = n; + } + m_head = nullptr; + } - protected: - ~element_t() = default; private: - LC * m_next; + LC *m_head; }; - struct iter_t final : public std::iterator<std::forward_iterator_tag, LC> + // ---------------------------------------------------------------------------------------- + // FIXME: Move elsewhere + // ---------------------------------------------------------------------------------------- + + template<bool enabled_ = true> + class pspin_mutex { - private: - LC* p; public: - explicit constexpr iter_t(LC* x) noexcept : p(x) { } - explicit constexpr iter_t(const iter_t &rhs) noexcept : p(rhs.p) { } - iter_t(iter_t &&rhs) noexcept { std::swap(*this, rhs); } - iter_t& operator=(const iter_t &rhs) { iter_t t(rhs); std::swap(*this, t); return *this; } - iter_t& operator=(iter_t &&rhs) { std::swap(*this, rhs); return *this; } - iter_t& operator++() noexcept {p = p->next();return *this;} - iter_t operator++(int) noexcept {iter_t tmp(*this); operator++(); return tmp;} - constexpr bool operator==(const iter_t& rhs) const noexcept {return p == rhs.p;} - constexpr bool operator!=(const iter_t& rhs) const noexcept {return p != rhs.p;} - /* constexpr */ LC& operator*() noexcept {return *p;} - /* constexpr */ LC* operator->() noexcept {return p;} - - constexpr LC& operator*() const noexcept {return *p;} - constexpr LC* operator->() const noexcept {return p;} + pspin_mutex() noexcept = default; + void lock() noexcept{ while (m_lock.test_and_set(std::memory_order_acquire)) { } } + void unlock() noexcept { m_lock.clear(std::memory_order_release); } + private: + PALIGNAS_CACHELINE() + std::atomic_flag m_lock = ATOMIC_FLAG_INIT; }; - constexpr linkedlist_t() : m_head(nullptr) {} + template<> + class pspin_mutex<false> + { + public: + void lock() const noexcept { } + void unlock() const noexcept { } + }; - constexpr iter_t begin() const noexcept { return iter_t(m_head); } - constexpr iter_t end() const noexcept { return iter_t(nullptr); } + // ---------------------------------------------------------------------------------------- + // timed queue + // ---------------------------------------------------------------------------------------- - void push_front(LC *elem) noexcept + template <class Element, class Time> + struct pqentry_t final { - elem->m_next = m_head; - m_head = elem; - } + constexpr pqentry_t() noexcept : m_exec_time(), m_object(nullptr) { } + constexpr pqentry_t(const Time t, const Element o) noexcept : m_exec_time(t), m_object(o) { } +#if 0 + ~pqentry_t() = default; + constexpr pqentry_t(const pqentry_t &e) noexcept = default; + constexpr pqentry_t(pqentry_t &&e) noexcept = default; + pqentry_t& operator=(pqentry_t && other) noexcept = default; + pqentry_t& operator=(const pqentry_t &other) noexcept = default; - void push_back(LC *elem) noexcept - { - LC **p = &m_head; - while (*p != nullptr) + void swap(pqentry_t &other) noexcept { - p = &((*p)->m_next); + std::swap(m_exec_time, other.m_exec_time); + std::swap(m_object, other.m_object); + } +#endif + inline bool operator ==(const pqentry_t &rhs) const noexcept + { + return m_object == rhs.m_object; } - *p = elem; - elem->m_next = nullptr; - } - void remove(const LC *elem) noexcept - { - auto p = &m_head; - while(*p != elem) + inline bool operator ==(const Element &rhs) const noexcept + { + return m_object == rhs; + } + + inline bool operator <=(const pqentry_t &rhs) const noexcept { - //nl_assert(*p != nullptr); - p = &((*p)->m_next); + return (m_exec_time <= rhs.m_exec_time); } - (*p) = elem->m_next; - } - LC *front() const noexcept { return m_head; } - void clear() noexcept { m_head = nullptr; } - constexpr bool empty() const noexcept { return (m_head == nullptr); } + inline bool operator <(const pqentry_t &rhs) const noexcept + { + return (m_exec_time < rhs.m_exec_time); + } -private: - LC *m_head; -}; -#else -template <class LC> -class linkedlist_t -{ -public: + inline static constexpr pqentry_t never() noexcept { return pqentry_t(Time::never(), nullptr); } - struct element_t + Time m_exec_time; + Element m_object; + }; + + /* Use TS = true for a threadsafe queue */ + template <class T, bool TS> + class timed_queue_linear : nocopyassignmove { public: - friend class linkedlist_t<LC>; + explicit timed_queue_linear(const std::size_t list_size) + : m_list(list_size) + { + clear(); + } + + std::size_t capacity() const noexcept { return m_list.capacity() - 1; } + bool empty() const noexcept { return (m_end == &m_list[1]); } + + template<bool KEEPSTAT> + void push(T && e) noexcept + { +#if 0 + /* Lock */ + lock_guard_type lck(m_lock); + T * i(m_end-1); + for (; *i < e; --i) + { + *(i+1) = *(i); + if (KEEPSTAT) + m_prof_sortmove.inc(); + } + *(i+1) = std::move(e); + ++m_end; +#else + /* Lock */ + lock_guard_type lck(m_lock); + T * i(m_end++); + *i = std::move(e); + for (; *(i-1) < *i; --i) + { + std::swap(*(i-1), *(i)); + if (KEEPSTAT) + m_prof_sortmove.inc(); + } +#endif + if (KEEPSTAT) + m_prof_call.inc(); + } + + T pop() noexcept { return *(--m_end); } + const T &top() const noexcept { return *(m_end-1); } - constexpr element_t() : m_next(nullptr), m_prev(nullptr) {} - ~element_t() noexcept = default; + template <bool KEEPSTAT, class R> + void remove(const R &elem) noexcept + { + /* Lock */ + lock_guard_type lck(m_lock); + if (KEEPSTAT) + m_prof_remove.inc(); + for (T * i = m_end - 1; i > &m_list[0]; --i) + { + // == operator ignores time! + if (*i == elem) + { + std::copy(i+1, m_end--, i); + return; + } + } + } - COPYASSIGNMOVE(element_t, delete) + template <bool KEEPSTAT, class R> + void retime(R && elem) noexcept + { + /* Lock */ + lock_guard_type lck(m_lock); + if (KEEPSTAT) + m_prof_retime.inc(); + + for (R * i = m_end - 1; i > &m_list[0]; --i) + { + if (*i == elem) // partial equal! + { + *i = std::forward<R>(elem); + while (*(i-1) < *i) + { + std::swap(*(i-1), *i); + --i; + } + while (i < m_end && *i < *(i+1)) + { + std::swap(*(i+1), *i); + ++i; + } + return; + } + } + } - constexpr LC *next() const noexcept { return m_next; } - constexpr LC *prev() const noexcept { return m_prev; } + void clear() noexcept + { + lock_guard_type lck(m_lock); + m_end = &m_list[0]; + /* put an empty element with maximum time into the queue. + * the insert algo above will run into this element and doesn't + * need a comparison with queue start. + */ + m_list[0] = T::never(); + m_end++; + } + + // save state support & mame disasm + + const T *listptr() const noexcept { return &m_list[1]; } + std::size_t size() const noexcept { return static_cast<std::size_t>(m_end - &m_list[1]); } + const T & operator[](const std::size_t index) const noexcept { return m_list[ 1 + index]; } private: - LC * m_next; - LC * m_prev; + using mutex_type = pspin_mutex<TS>; + using lock_guard_type = std::lock_guard<mutex_type>; + + mutex_type m_lock; + PALIGNAS_CACHELINE() + T * m_end; + aligned_vector<T> m_list; + + public: + // profiling + pperfcount_t<true> m_prof_sortmove; + pperfcount_t<true> m_prof_call; + pperfcount_t<true> m_prof_remove; + pperfcount_t<true> m_prof_retime; }; - struct iter_t final : public std::iterator<std::forward_iterator_tag, LC> + template <class T, bool TS> + class timed_queue_heap : nocopyassignmove { - private: - LC* p; public: - explicit constexpr iter_t(LC* x) noexcept : p(x) { } - constexpr iter_t(iter_t &rhs) noexcept : p(rhs.p) { } - iter_t(iter_t &&rhs) noexcept { std::swap(*this, rhs); } - iter_t& operator=(const iter_t &rhs) noexcept { p = rhs.p; return *this; } - iter_t& operator=(iter_t &&rhs) noexcept { std::swap(*this, rhs); return *this; } - iter_t& operator++() noexcept {p = p->next();return *this;} - // NOLINTNEXTLINE(cert-dcl21-cpp) - iter_t operator++(int) & noexcept {const iter_t tmp(*this); operator++(); return tmp;} - - ~iter_t() = default; - - constexpr bool operator==(const iter_t& rhs) const noexcept {return p == rhs.p;} - constexpr bool operator!=(const iter_t& rhs) const noexcept {return p != rhs.p;} - constexpr LC& operator*() noexcept {return *p;} - constexpr LC* operator->() noexcept {return p;} - - constexpr LC& operator*() const noexcept {return *p;} - constexpr LC* operator->() const noexcept {return p;} - }; - constexpr linkedlist_t() : m_head(nullptr) {} + struct compare + { + constexpr bool operator()(const T &a, const T &b) const { return b <= a; } + }; - constexpr iter_t begin() const noexcept { return iter_t(m_head); } - constexpr iter_t end() const noexcept { return iter_t(nullptr); } + explicit timed_queue_heap(const std::size_t list_size) + : m_list(list_size) + { + clear(); + } - void push_front(LC *elem) noexcept - { - if (m_head) - m_head->m_prev = elem; - elem->m_next = m_head; - elem->m_prev = nullptr; - m_head = elem; - } - - void push_back(LC *elem) noexcept - { - LC ** p(&m_head); - LC * prev(nullptr); - while (*p != nullptr) + std::size_t capacity() const noexcept { return m_list.capacity(); } + bool empty() const noexcept { return &m_list[0] == m_end; } + + template <bool KEEPSTAT> + void push(T &&e) noexcept { - prev = *p; - p = &((*p)->m_next); + /* Lock */ + lock_guard_type lck(m_lock); + *m_end++ = e; + std::push_heap(&m_list[0], m_end, compare()); + if (KEEPSTAT) + m_prof_call.inc(); } - *p = elem; - elem->m_prev = prev; - elem->m_next = nullptr; - } - void remove(const LC *elem) noexcept - { - if (elem->m_prev) - elem->m_prev->m_next = elem->m_next; - else - m_head = elem->m_next; - if (elem->m_next) - elem->m_next->m_prev = elem->m_prev; - else + T pop() noexcept { - /* update tail */ + T ret(m_list[0]); + std::pop_heap(&m_list[0], m_end, compare()); + m_end--; + return ret; } - } - LC *front() const noexcept { return m_head; } - constexpr bool empty() const noexcept { return (m_head == nullptr); } - void clear() noexcept - { - LC *p(m_head); - while (p != nullptr) + const T &top() const noexcept { return m_list[0]; } + + template <bool KEEPSTAT, class R> + void remove(const R &elem) noexcept { - LC *n(p->m_next); - p->m_next = nullptr; - p->m_prev = nullptr; - p = n; + /* Lock */ + lock_guard_type lck(m_lock); + if (KEEPSTAT) + m_prof_remove.inc(); + for (T * i = m_end - 1; i >= &m_list[0]; i--) + { + if (*i == elem) + { + m_end--; + for (;i < m_end; i++) + *i = std::move(*(i+1)); + std::make_heap(&m_list[0], m_end, compare()); + return; + } + } } - m_head = nullptr; - } -private: - LC *m_head; -}; -#endif + template <bool KEEPSTAT> + void retime(const T &elem) noexcept + { + /* Lock */ + lock_guard_type lck(m_lock); + if (KEEPSTAT) + m_prof_retime.inc(); + for (T * i = m_end - 1; i >= &m_list[0]; i--) + { + if (*i == elem) // partial equal! + { + *i = elem; + std::make_heap(&m_list[0], m_end, compare()); + return; + } + } + } + + void clear() + { + lock_guard_type lck(m_lock); + m_list.clear(); + m_end = &m_list[0]; + } + + // save state support & mame disasm + + constexpr const T *listptr() const { return &m_list[0]; } + constexpr std::size_t size() const noexcept { return m_list.size(); } + constexpr const T & operator[](const std::size_t index) const { return m_list[ 0 + index]; } + private: + using mutex_type = pspin_mutex<TS>; + using lock_guard_type = std::lock_guard<mutex_type>; + + mutex_type m_lock; + std::vector<T> m_list; + T *m_end; + + public: + // profiling + pperfcount_t<true> m_prof_sortmove; + pperfcount_t<true> m_prof_call; + pperfcount_t<true> m_prof_remove; + pperfcount_t<true> m_prof_retime; + }; + } // namespace plib #endif /* PLISTS_H_ */ |