// license:GPL-2.0+ // copyright-holders:Couriersud #ifndef PTIMED_QUEUE_H_ #define PTIMED_QUEUE_H_ /// /// \file ptimed_queue.h /// #include "palloc.h" // FIXME: for aligned_vector #include "pchrono.h" #include "pmulti_threading.h" #include "ptypes.h" #include #include #include #include #include namespace plib { // ---------------------------------------------------------------------------------------- // timed queue // ---------------------------------------------------------------------------------------- // Note: Don't even try the following approach for element: // // template // struct pqentry_t : public std::pair // // This degrades performance significantly. template struct pqentry_t final { 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) { } pqentry_t(const pqentry_t &) = default; pqentry_t &operator=(const pqentry_t &) = default; pqentry_t(pqentry_t &&) noexcept = default; pqentry_t &operator=(pqentry_t &&) noexcept = default; ~pqentry_t() = default; constexpr bool operator ==(const pqentry_t &rhs) const noexcept { return m_object == rhs.m_object; } constexpr bool operator ==(const Element &rhs) const noexcept { return m_object == rhs; } constexpr bool operator <=(const pqentry_t &rhs) const noexcept { return (m_exec_time <= rhs.m_exec_time); } constexpr bool operator <(const pqentry_t &rhs) const noexcept { return (m_exec_time < rhs.m_exec_time); } static constexpr pqentry_t never() noexcept { return pqentry_t(Time::never(), nullptr); } constexpr const Time &exec_time() const noexcept { return m_exec_time; } constexpr const Element &object() const noexcept { return m_object; } private: Time m_exec_time; Element m_object; }; // Use TS = true for a threadsafe queue template class timed_queue_linear { public: explicit timed_queue_linear(const std::size_t list_size) : m_list(list_size) { clear(); } ~timed_queue_linear() = default; PCOPYASSIGNMOVE(timed_queue_linear, delete) std::size_t capacity() const noexcept { return m_list.capacity() - 1; } bool empty() const noexcept { return (m_end == &m_list[1]); } template void emplace(Args&&... args) noexcept { // Lock lock_guard_type lck(m_lock); T * i(m_end++); *i = T(std::forward(args)...); if (!KEEPSTAT) { for (; *(i-1) < *i; --i) { std::swap(*(i-1), *(i)); } } else { for (; *(i-1) < *i; --i) { std::swap(*(i-1), *(i)); m_prof_sortmove.inc(); } m_prof_call.inc(); } } template 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(); } void pop() noexcept { --m_end; } const T &top() const noexcept { return *(m_end-1); } template 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; } } //printf("Element not found in delete %s\n", elem->name().c_str()); } 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 narrow_cast(m_end - &m_list[1]); } const T & operator[](std::size_t index) const noexcept { return m_list[ 1 + index]; } private: using mutex_type = pspin_mutex; using lock_guard_type = std::lock_guard; mutex_type m_lock; T * m_end; aligned_vector m_list; public: // profiling // FIXME: Make those private pperfcount_t m_prof_sortmove; // NOLINT pperfcount_t m_prof_call; // NOLINT pperfcount_t m_prof_remove; // NOLINT }; template class timed_queue_heap { public: struct compare { constexpr bool operator()(const T &a, const T &b) const noexcept { return b <= a; } }; explicit timed_queue_heap(const std::size_t list_size) : m_list(list_size) { clear(); } ~timed_queue_heap() = default; PCOPYASSIGNMOVE(timed_queue_heap, delete) std::size_t capacity() const noexcept { return m_list.capacity(); } bool empty() const noexcept { return &m_list[0] == m_end; } template void emplace(Args&&... args) noexcept { // Lock lock_guard_type lck(m_lock); *m_end++ = T(std::forward(args)...); std::push_heap(&m_list[0], m_end, compare()); if (KEEPSTAT) m_prof_call.inc(); } template void push(T &&e) noexcept { // 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(); } void pop() noexcept { std::pop_heap(&m_list[0], m_end, compare()); m_end--; } const T &top() const noexcept { return m_list[0]; } template 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--) { if (*i == elem) { m_end--; *i = *m_end; 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; using lock_guard_type = std::lock_guard; mutex_type m_lock; T * m_end; aligned_vector m_list; public: // profiling pperfcount_t m_prof_sortmove; // NOLINT pperfcount_t m_prof_call; // NOLINT pperfcount_t m_prof_remove; // NOLINT }; } // namespace plib #endif // PTIMED_QUEUE_H_