summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/netlist/nl_lists.h
blob: 9e6cc335b5b55e21469a2d55221555db9d41fa3d (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// license:GPL-2.0+
// copyright-holders:Couriersud
/*
 * nllists.h
 *
 */

#pragma once

#ifndef NLLISTS_H_
#define NLLISTS_H_

#include <atomic>

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


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

namespace netlist
{
	template <class Element, class Time>
	class timed_queue
	{
		P_PREVENT_COPYING(timed_queue)
	public:

		struct entry_t
		{
			Time m_exec_time;
			Element m_object;
		};

		timed_queue(unsigned list_size)
		: m_list(list_size)
		{
	#if HAS_OPENMP && USE_OPENMP
			m_lock = 0;
	#endif
			clear();
		}

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

		void push(const Time t, Element o) NOEXCEPT
		{
	#if HAS_OPENMP && USE_OPENMP
			/* Lock */
			while (m_lock.exchange(1)) { }
	#endif
			entry_t * i = m_end;
			for (; t > (i - 1)->m_exec_time; --i)
			{
				*(i) = *(i-1);
				m_prof_sortmove.inc();
			}
			*i = { t, o };
			++m_end;
			m_prof_call.inc();
	#if HAS_OPENMP && USE_OPENMP
			m_lock = 0;
	#endif
		}

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

		void remove(const Element &elem) NOEXCEPT
		{
			/* Lock */
	#if HAS_OPENMP && USE_OPENMP
			while (m_lock.exchange(1)) { }
	#endif
			for (entry_t * i = m_end - 1; i > &m_list[0]; i--)
			{
				if (i->m_object == elem)
				{
					m_end--;
					while (i < m_end)
					{
						*i = *(i+1);
						++i;
					}
	#if HAS_OPENMP && USE_OPENMP
					m_lock = 0;
	#endif
					return;
				}
			}
	#if HAS_OPENMP && USE_OPENMP
			m_lock = 0;
	#endif
		}

		void retime(const Time t, const Element &elem) NOEXCEPT
		{
			remove(elem);
			push(t, elem);
		}

		void clear()
		{
			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

		 const entry_t *listptr() const { return &m_list[1]; }
		 std::size_t size() const { return m_end - &m_list[1]; }
		 const entry_t & operator[](const std::size_t index) const { return m_list[ 1 + index]; }

	private:

	#if HAS_OPENMP && USE_OPENMP
		volatile std::atomic<int> m_lock;
	#endif
		entry_t * m_end;
		std::vector<entry_t> m_list;

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

}

#endif /* NLLISTS_H_ */