1 // license:GPL-2.0+ 2 // copyright-holders:Couriersud 3 4 #ifndef PTIMED_QUEUE_H_ 5 #define PTIMED_QUEUE_H_ 6 7 /// 8 /// \file ptimed_queue.h 9 /// 10 11 #include "palloc.h" // FIXME: for aligned_vector 12 #include "pchrono.h" 13 #include "pmulti_threading.h" 14 #include "ptypes.h" 15 16 #include <algorithm> 17 #include <mutex> 18 #include <type_traits> 19 #include <utility> 20 #include <vector> 21 22 namespace plib { 23 24 // ---------------------------------------------------------------------------------------- 25 // timed queue 26 // ---------------------------------------------------------------------------------------- 27 28 // Note: Don't even try the following approach for element: 29 // 30 // template <typename Time, typename Element> 31 // struct pqentry_t : public std::pair<Time, Element> 32 // 33 // This degrades performance significantly. 34 35 template <typename Time, typename Element> 36 struct pqentry_t final 37 { pqentry_tfinal38 constexpr pqentry_t() noexcept : m_exec_time(), m_object(nullptr) { } pqentry_tfinal39 constexpr pqentry_t(const Time &t, const Element &o) noexcept : m_exec_time(t), m_object(o) { } 40 41 pqentry_t(const pqentry_t &) = default; 42 pqentry_t &operator=(const pqentry_t &) = default; 43 pqentry_t(pqentry_t &&) noexcept = default; 44 pqentry_t &operator=(pqentry_t &&) noexcept = default; 45 46 ~pqentry_t() = default; 47 48 constexpr bool operator ==(const pqentry_t &rhs) const noexcept 49 { 50 return m_object == rhs.m_object; 51 } 52 53 constexpr bool operator ==(const Element &rhs) const noexcept 54 { 55 return m_object == rhs; 56 } 57 58 constexpr bool operator <=(const pqentry_t &rhs) const noexcept 59 { 60 return (m_exec_time <= rhs.m_exec_time); 61 } 62 63 constexpr bool operator <(const pqentry_t &rhs) const noexcept 64 { 65 return (m_exec_time < rhs.m_exec_time); 66 } 67 neverfinal68 static constexpr pqentry_t never() noexcept { return pqentry_t(Time::never(), nullptr); } 69 exec_timefinal70 constexpr const Time &exec_time() const noexcept { return m_exec_time; } objectfinal71 constexpr const Element &object() const noexcept { return m_object; } 72 private: 73 Time m_exec_time; 74 Element m_object; 75 }; 76 77 // Use TS = true for a threadsafe queue 78 template <class T, bool TS> 79 class timed_queue_linear 80 { 81 public: 82 timed_queue_linear(const std::size_t list_size)83 explicit timed_queue_linear(const std::size_t list_size) 84 : m_list(list_size) 85 { 86 clear(); 87 } 88 ~timed_queue_linear() = default; 89 PCOPYASSIGNMOVE(timed_queue_linear,delete)90 PCOPYASSIGNMOVE(timed_queue_linear, delete) 91 92 std::size_t capacity() const noexcept { return m_list.capacity() - 1; } empty()93 bool empty() const noexcept { return (m_end == &m_list[1]); } 94 95 template<bool KEEPSTAT, typename... Args> emplace(Args &&...args)96 void emplace(Args&&... args) noexcept 97 { 98 // Lock 99 lock_guard_type lck(m_lock); 100 T * i(m_end++); 101 *i = T(std::forward<Args>(args)...); 102 103 if (!KEEPSTAT) 104 { 105 for (; *(i-1) < *i; --i) 106 { 107 std::swap(*(i-1), *(i)); 108 } 109 } 110 else 111 { 112 for (; *(i-1) < *i; --i) 113 { 114 std::swap(*(i-1), *(i)); 115 m_prof_sortmove.inc(); 116 } 117 m_prof_call.inc(); 118 } 119 } 120 121 template<bool KEEPSTAT> push(T && e)122 void push(T && e) noexcept 123 { 124 #if 0 125 // Lock 126 lock_guard_type lck(m_lock); 127 T * i(m_end-1); 128 for (; *i < e; --i) 129 { 130 *(i+1) = *(i); 131 if (KEEPSTAT) 132 m_prof_sortmove.inc(); 133 } 134 *(i+1) = std::move(e); 135 ++m_end; 136 #else 137 // Lock 138 lock_guard_type lck(m_lock); 139 T * i(m_end++); 140 *i = std::move(e); 141 for (; *(i-1) < *i; --i) 142 { 143 std::swap(*(i-1), *(i)); 144 if (KEEPSTAT) 145 m_prof_sortmove.inc(); 146 } 147 #endif 148 if (KEEPSTAT) 149 m_prof_call.inc(); 150 } 151 pop()152 void pop() noexcept { --m_end; } 153 top()154 const T &top() const noexcept { return *(m_end-1); } 155 156 template <bool KEEPSTAT, class R> remove(const R & elem)157 void remove(const R &elem) noexcept 158 { 159 // Lock 160 lock_guard_type lck(m_lock); 161 if (KEEPSTAT) 162 m_prof_remove.inc(); 163 for (T * i = m_end - 1; i > &m_list[0]; --i) 164 { 165 // == operator ignores time! 166 if (*i == elem) 167 { 168 std::copy(i+1, m_end--, i); 169 return; 170 } 171 } 172 //printf("Element not found in delete %s\n", elem->name().c_str()); 173 } 174 clear()175 void clear() noexcept 176 { 177 lock_guard_type lck(m_lock); 178 m_end = &m_list[0]; 179 // put an empty element with maximum time into the queue. 180 // the insert algo above will run into this element and doesn't 181 // need a comparison with queue start. 182 // 183 m_list[0] = T::never(); 184 m_end++; 185 } 186 187 // save state support & mame disasm 188 listptr()189 const T *listptr() const noexcept { return &m_list[1]; } size()190 std::size_t size() const noexcept { return narrow_cast<std::size_t>(m_end - &m_list[1]); } 191 const T & operator[](std::size_t index) const noexcept { return m_list[ 1 + index]; } 192 private: 193 using mutex_type = pspin_mutex<TS>; 194 using lock_guard_type = std::lock_guard<mutex_type>; 195 196 mutex_type m_lock; 197 T * m_end; 198 aligned_vector<T> m_list; 199 200 public: 201 // profiling 202 // FIXME: Make those private 203 pperfcount_t<true> m_prof_sortmove; // NOLINT 204 pperfcount_t<true> m_prof_call; // NOLINT 205 pperfcount_t<true> m_prof_remove; // NOLINT 206 }; 207 208 template <class T, bool TS> 209 class timed_queue_heap 210 { 211 public: 212 213 struct compare 214 { operatorcompare215 constexpr bool operator()(const T &a, const T &b) const noexcept { return b <= a; } 216 }; 217 timed_queue_heap(const std::size_t list_size)218 explicit timed_queue_heap(const std::size_t list_size) 219 : m_list(list_size) 220 { 221 clear(); 222 } 223 ~timed_queue_heap() = default; 224 PCOPYASSIGNMOVE(timed_queue_heap,delete)225 PCOPYASSIGNMOVE(timed_queue_heap, delete) 226 227 std::size_t capacity() const noexcept { return m_list.capacity(); } empty()228 bool empty() const noexcept { return &m_list[0] == m_end; } 229 230 template<bool KEEPSTAT, typename... Args> emplace(Args &&...args)231 void emplace(Args&&... args) noexcept 232 { 233 // Lock 234 lock_guard_type lck(m_lock); 235 *m_end++ = T(std::forward<Args>(args)...); 236 std::push_heap(&m_list[0], m_end, compare()); 237 if (KEEPSTAT) 238 m_prof_call.inc(); 239 } 240 241 template <bool KEEPSTAT> push(T && e)242 void push(T &&e) noexcept 243 { 244 // Lock 245 lock_guard_type lck(m_lock); 246 *m_end++ = e; 247 std::push_heap(&m_list[0], m_end, compare()); 248 if (KEEPSTAT) 249 m_prof_call.inc(); 250 } 251 pop()252 void pop() noexcept 253 { 254 std::pop_heap(&m_list[0], m_end, compare()); 255 m_end--; 256 } 257 top()258 const T &top() const noexcept { return m_list[0]; } 259 260 template <bool KEEPSTAT, class R> remove(const R & elem)261 void remove(const R &elem) noexcept 262 { 263 // Lock 264 lock_guard_type lck(m_lock); 265 if (KEEPSTAT) 266 m_prof_remove.inc(); 267 for (T * i = m_end - 1; i >= &m_list[0]; i--) 268 { 269 if (*i == elem) 270 { 271 m_end--; 272 *i = *m_end; 273 std::make_heap(&m_list[0], m_end, compare()); 274 return; 275 } 276 } 277 } 278 clear()279 void clear() 280 { 281 lock_guard_type lck(m_lock); 282 m_list.clear(); 283 m_end = &m_list[0]; 284 } 285 286 // save state support & mame disasm 287 listptr()288 constexpr const T *listptr() const { return &m_list[0]; } size()289 constexpr std::size_t size() const noexcept { return m_list.size(); } 290 constexpr const T & operator[](const std::size_t index) const { return m_list[ 0 + index]; } 291 private: 292 using mutex_type = pspin_mutex<TS>; 293 using lock_guard_type = std::lock_guard<mutex_type>; 294 295 mutex_type m_lock; 296 T * m_end; 297 aligned_vector<T> m_list; 298 299 public: 300 // profiling 301 pperfcount_t<true> m_prof_sortmove; // NOLINT 302 pperfcount_t<true> m_prof_call; // NOLINT 303 pperfcount_t<true> m_prof_remove; // NOLINT 304 }; 305 306 } // namespace plib 307 308 #endif // PTIMED_QUEUE_H_ 309