summaryrefslogblamecommitdiffstatshomepage
path: root/src/lib/netlist/nl_lists.h
blob: 8417d1231dc447642b236c33bb4460c762232a31 (plain) (tree)
1
2
3
4
5
6
7
8
9






                               

            



                      
                          
                        
                         
                        
 


                 
                    
 



                                                                                           
                           
 
                 
 

                                             
                         

               


                                                                                                  




                                                           
                                

               

                                                

          
             
                                            
                                                  

               
 
                                    
                 



                                                                                                                           
                                             
 
                                                                     
                         
                                            


                                             












                                                                          

                                         

                  
                                                        

                                   

                                
 
                                                                                                 
                                                                                       
 
                                               
                 
                                  
                                           
                                            
                                                                         
                         
                                              
                                                      
                         
                                          
                                
                                          
                 
 

                                                                          
 
                                                         
                 
                                  
                                           
                                                                          
                         
                                                        
                                 
                                                
                                                             
                                                                       
                                               
                                 
                         
                 
 
                                                                       
                 



















                                                                                                

                 
                            
                 
                                           




                                                                                       
                                                                  




                                                   


                                                                                                                    
                





                                                        
 
                               
                                


                                            
                            

                                             











































                                                                                                                           
                                   
                 



                                                                                             
                                                                                     




                                               

                                                                     

                                          
 


                                             

                                                                    








                                                                         
                                                                           


                                                        




                                                                                     





                                                                       










                                                                                     





                                           
                                           
















                                                                                                                  
                               






                                             
 
 
                       
// license:GPL-2.0+
// copyright-holders:Couriersud
/*
 * nllists.h
 *
 */

#pragma once

#ifndef NLLISTS_H_
#define NLLISTS_H_

#include "nl_config.h"
#include "netlist_types.h"
#include "plib/plists.h"
#include "plib/pchrono.h"
#include "plib/ptypes.h"

#include <atomic>
#include <thread>
#include <mutex>
#include <algorithm>

// ----------------------------------------------------------------------------------------
// timed queue
// ----------------------------------------------------------------------------------------

#define USE_HEAP	(0)

namespace netlist
{
	//FIXME: move to an appropriate place
	template<bool enabled_ = true>
	class pspin_mutex
	{
	public:
		pspin_mutex() noexcept { }
		void lock() noexcept{ while (m_lock.test_and_set(std::memory_order_acquire)) { } }
		void unlock() noexcept { m_lock.clear(std::memory_order_release); }
	private:
		std::atomic_flag m_lock = ATOMIC_FLAG_INIT;
	};

	template<>
	class pspin_mutex<false>
	{
	public:
		void lock() const noexcept { }
		void unlock() const noexcept { }
	};

#if !USE_HEAP
	template <class Element, class Time>
	class timed_queue : plib::nocopyassignmove
	{
	public:

		struct entry_t final
		{
			constexpr entry_t() noexcept : m_exec_time(), m_object(nullptr) { }
			constexpr entry_t(const Time &t, const Element &o) noexcept : m_exec_time(t), m_object(o) { }
			constexpr entry_t(const entry_t &e) noexcept : m_exec_time(e.m_exec_time), m_object(e.m_object) { }
			entry_t(entry_t &&e) noexcept { swap(e); }
			~entry_t() = default;

			entry_t& operator=(entry_t && other) noexcept
			{
				swap(other);
				return *this;
			}

			entry_t& operator=(const entry_t &other) noexcept
			{
				entry_t t(other);
				swap(t);
				return *this;
			}

			void swap(entry_t &other) noexcept
			{
				std::swap(m_exec_time, other.m_exec_time);
				std::swap(m_object, other.m_object);
			}

			Time m_exec_time;
			Element m_object;
		};

		timed_queue(const std::size_t list_size)
		: m_list(list_size)
		{
			clear();
		}

		constexpr std::size_t capacity() const noexcept { return m_list.capacity() - 1; }
		constexpr bool empty() const noexcept { return (m_end == &m_list[1]); }

		void push(entry_t &&e) noexcept
		{
			/* Lock */
			tqlock lck(m_lock);
			entry_t * i = m_end;
			for (; e.m_exec_time > (i - 1)->m_exec_time; --i)
			{
				*(i) = *(i-1);
				m_prof_sortmove.inc();
			}
			*i = std::move(e);
			++m_end;
			m_prof_call.inc();
		}

		entry_t pop() noexcept              { return *(--m_end); }
		const entry_t &top() const noexcept { return *(m_end-1); }

		void remove(const Element &elem) noexcept
		{
			/* Lock */
			tqlock lck(m_lock);
			for (entry_t * i = m_end - 1; i > &m_list[0]; i--)
			{
				if (i->m_object == elem)
				{
					m_end--;
					for (;i < m_end; i++)
						*i = std::move(*(i+1));
					return;
				}
			}
		}

		void retime(const Element &elem, const Time t) noexcept
		{
			/* Lock */
			tqlock lck(m_lock);
			for (entry_t * i = m_end - 1; i > &m_list[0]; i--)
			{
				if (i->m_object == elem)
				{
					i->m_exec_time = t;
					while ((i-1)->m_exec_time < i->m_exec_time)
					{
						std::swap(*(i-1), *i);
						i--;
					}
					while (i < m_end && (i+1)->m_exec_time > i->m_exec_time)
					{
						std::swap(*(i+1), *i);
						i++;
					}
					return;
				}
			}
		}

		void clear()
		{
			tqlock 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] = { Time::never(), Element(0) };
			m_end++;
		}

		// save state support & mame disasm

		constexpr const entry_t *listptr() const { return &m_list[1]; }
		constexpr std::size_t size() const noexcept { return static_cast<std::size_t>(m_end - &m_list[1]); }
		constexpr const entry_t & operator[](const std::size_t index) const { return m_list[ 1 + index]; }
	private:
	#if HAS_OPENMP && USE_OPENMP
		using tqmutex = pspin_mutex<true>;
	#else
		using tqmutex = pspin_mutex<false>;
	#endif
		using tqlock = std::lock_guard<tqmutex>;

		tqmutex m_lock;
		entry_t * m_end;
		std::vector<entry_t> m_list;

	public:
		// profiling
		nperfcount_t m_prof_sortmove;
		nperfcount_t m_prof_call;
	};
#else
	template <class Element, class Time>
	class timed_queue : plib::nocopyassignmove
	{
	public:

		struct entry_t final
		{
			constexpr entry_t() noexcept : m_exec_time(), m_object(nullptr) { }
			constexpr entry_t(const Time &t, const Element &o) noexcept : m_exec_time(t), m_object(o) { }
			constexpr entry_t(const entry_t &e) noexcept : m_exec_time(e.m_exec_time), m_object(e.m_object) { }
			entry_t(entry_t &&e) noexcept { swap(e); }
			~entry_t() = default;

			entry_t& operator=(entry_t && other) noexcept
			{
				swap(other);
				return *this;
			}

			entry_t& operator=(const entry_t &other) noexcept
			{
				entry_t t(other);
				swap(t);
				return *this;
			}

			void swap(entry_t &other) noexcept
			{
				std::swap(m_exec_time, other.m_exec_time);
				std::swap(m_object, other.m_object);
			}

			Time m_exec_time;
			Element m_object;
		};

		struct compare
		{
			bool operator()(const entry_t &a, const entry_t &b) { return a.m_exec_time > b.m_exec_time; }
		};

		timed_queue(const std::size_t list_size)
		: m_list(list_size)
		{
			clear();
		}

		constexpr std::size_t capacity() const noexcept { return m_list.capacity(); }
		constexpr bool empty() const noexcept { return &m_list[0] == m_end; }

		void push(entry_t &&e) noexcept
		{
			/* Lock */
			tqlock lck(m_lock);
			*m_end++ = e;
			std::push_heap(&m_list[0], m_end, compare());
			m_prof_call.inc();
		}

		entry_t pop() noexcept
		{
			entry_t t(m_list[0]);
			std::pop_heap(&m_list[0], m_end, compare());
			m_end--;
			return t;
		}

		const entry_t &top() const noexcept { return m_list[0]; }

		void remove(const Element &elem) noexcept
		{
			/* Lock */
			tqlock lck(m_lock);
			for (entry_t * i = m_end - 1; i >= &m_list[0]; i--)
			{
				if (i->m_object == elem)
				{
					m_end--;
					for (;i < m_end; i++)
						*i = std::move(*(i+1));
					std::make_heap(&m_list[0], m_end, compare());
					return;
				}
			}
		}

		void retime(const Element &elem, const Time t) noexcept
		{
			/* Lock */
			tqlock lck(m_lock);
			for (entry_t * i = m_end - 1; i >= &m_list[0]; i--)
			{
				if (i->m_object == elem)
				{
					i->m_exec_time = t;
					std::make_heap(&m_list[0], m_end, compare());
					return;
				}
			}
		}

		void clear()
		{
			tqlock lck(m_lock);
			m_list.clear();
			m_end = &m_list[0];
		}

		// save state support & mame disasm

		constexpr const entry_t *listptr() const { return &m_list[0]; }
		constexpr std::size_t size() const noexcept { return m_list.size(); }
		constexpr const entry_t & operator[](const std::size_t index) const { return m_list[ 0 + index]; }
	private:
	#if HAS_OPENMP && USE_OPENMP
		using tqmutex = pspin_mutex<true>;
	#else
		using tqmutex = pspin_mutex<false>;
	#endif
		using tqlock = std::lock_guard<tqmutex>;

		tqmutex m_lock;
		std::vector<entry_t> m_list;
		entry_t *m_end;

	public:
		// profiling
		nperfcount_t m_prof_sortmove;
		nperfcount_t m_prof_call;
	};
#endif
}

#endif /* NLLISTS_H_ */