1/*
2 * Copyright 2013 Haiku, Inc. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 *
5 * Authors:
6 *		Paweł Dziepak, pdziepak@quarnos.org
7 */
8#ifndef RUN_QUEUE_H
9#define RUN_QUEUE_H
10
11
12#include <util/Heap.h>
13
14#include "scheduler_profiler.h"
15
16
17template<typename Element>
18struct RunQueueLink {
19					RunQueueLink();
20
21	unsigned int	fPriority;
22	Element*		fPrevious;
23	Element*		fNext;
24};
25
26template<typename Element>
27class RunQueueLinkImpl {
28public:
29	inline	RunQueueLink<Element>*	GetRunQueueLink();
30
31private:
32			RunQueueLink<Element>	fRunQueueLink;
33};
34
35template<typename Element>
36class RunQueueStandardGetLink {
37private:
38	typedef RunQueueLink<Element> Link;
39
40public:
41	inline	Link*		operator()(Element* element) const;
42};
43
44template<typename Element, RunQueueLink<Element> Element::*LinkMember>
45class RunQueueMemberGetLink {
46private:
47	typedef RunQueueLink<Element> Link;
48
49public:
50	inline	Link*		operator()(Element* element) const;
51};
52
53#define RUN_QUEUE_TEMPLATE_LIST	\
54	template<typename Element, unsigned int MaxPriority, typename GetLink>
55#define RUN_QUEUE_CLASS_NAME	RunQueue<Element, MaxPriority, GetLink>
56
57template<typename Element, unsigned int MaxPriority,
58	typename GetLink = RunQueueStandardGetLink<Element> >
59class RunQueue {
60public:
61	class ConstIterator {
62	public:
63								ConstIterator();
64								ConstIterator(const RunQueue<Element,
65										MaxPriority, GetLink>* list);
66
67		inline	ConstIterator&	operator=(const ConstIterator& other);
68
69				bool			HasNext() const;
70				Element*		Next();
71
72				void			Rewind();
73
74	private:
75		inline	void			_FindNextPriority();
76
77				const RUN_QUEUE_CLASS_NAME*	fList;
78				unsigned int	fPriority;
79				Element*		fNext;
80
81		static	GetLink			sGetLink;
82	};
83
84						RunQueue();
85
86	inline	status_t	GetInitStatus();
87
88	inline	Element*	PeekMaximum() const;
89
90	inline	void		PushFront(Element* element, unsigned int priority);
91	inline	void		PushBack(Element* elementt, unsigned int priority);
92
93	inline	void		Remove(Element* element);
94
95	inline	Element*	GetHead(unsigned int priority) const;
96
97	inline	ConstIterator	GetConstIterator() const;
98
99private:
100	struct PriorityEntry : public HeapLinkImpl<PriorityEntry, unsigned int>
101	{
102	};
103
104	typedef Heap<PriorityEntry, unsigned int, HeapGreaterCompare<unsigned int> >
105		PriorityHeap;
106
107			status_t	fInitStatus;
108
109			PriorityEntry	fPriorityEntries[MaxPriority + 1];
110			PriorityHeap	fPriorityHeap;
111
112			Element*	fHeads[MaxPriority + 1];
113			Element*	fTails[MaxPriority + 1];
114
115	static	GetLink		sGetLink;
116};
117
118
119template<typename Element>
120RunQueueLink<Element>::RunQueueLink()
121	:
122	fPrevious(NULL),
123	fNext(NULL)
124{
125}
126
127
128template<typename Element>
129RunQueueLink<Element>*
130RunQueueLinkImpl<Element>::GetRunQueueLink()
131{
132	return &fRunQueueLink;
133}
134
135
136template<typename Element>
137RunQueueLink<Element>*
138RunQueueStandardGetLink<Element>::operator()(Element* element) const
139{
140	return element->GetRunQueueLink();
141}
142
143
144template<typename Element, RunQueueLink<Element> Element::*LinkMember>
145RunQueueLink<Element>*
146RunQueueMemberGetLink<Element, LinkMember>::operator()(Element* element) const
147{
148	return &(element->*LinkMember);
149}
150
151
152RUN_QUEUE_TEMPLATE_LIST
153RUN_QUEUE_CLASS_NAME::ConstIterator::ConstIterator()
154	:
155	fList(NULL)
156{
157}
158
159
160RUN_QUEUE_TEMPLATE_LIST
161RUN_QUEUE_CLASS_NAME::ConstIterator::ConstIterator(const RunQueue<Element,
162		MaxPriority, GetLink>* list)
163	:
164	fList(list)
165{
166	Rewind();
167}
168
169
170RUN_QUEUE_TEMPLATE_LIST
171typename RUN_QUEUE_CLASS_NAME::ConstIterator&
172RUN_QUEUE_CLASS_NAME::ConstIterator::operator=(const ConstIterator& other)
173{
174	fList = other.fList;
175	fPriority = other.fPriority;
176	fNext = other.fNext;
177
178	return *this;
179}
180
181
182RUN_QUEUE_TEMPLATE_LIST
183bool
184RUN_QUEUE_CLASS_NAME::ConstIterator::HasNext() const
185{
186	return fNext != NULL;
187}
188
189
190RUN_QUEUE_TEMPLATE_LIST
191Element*
192RUN_QUEUE_CLASS_NAME::ConstIterator::Next()
193{
194	ASSERT(HasNext());
195
196	Element* current = fNext;
197	RunQueueLink<Element>* link = sGetLink(fNext);
198
199	fNext = link->fNext;
200	if (fNext == NULL)
201		_FindNextPriority();
202
203	return current;
204}
205
206
207RUN_QUEUE_TEMPLATE_LIST
208void
209RUN_QUEUE_CLASS_NAME::ConstIterator::Rewind()
210{
211	ASSERT(fList != NULL);
212
213	fPriority = MaxPriority;
214	fNext = fList->GetHead(fPriority);
215	if (fNext == NULL)
216		_FindNextPriority();
217}
218
219
220RUN_QUEUE_TEMPLATE_LIST
221void
222RUN_QUEUE_CLASS_NAME::ConstIterator::_FindNextPriority()
223{
224	ASSERT(fList != NULL);
225
226	while (fPriority-- > 0) {
227		fNext = fList->GetHead(fPriority);
228		if (fNext != NULL)
229			break;
230	}
231}
232
233
234RUN_QUEUE_TEMPLATE_LIST
235RUN_QUEUE_CLASS_NAME::RunQueue()
236	:
237	fInitStatus(B_OK),
238	fPriorityHeap(MaxPriority + 1)
239{
240	memset(fHeads, 0, sizeof(fHeads));
241	memset(fTails, 0, sizeof(fTails));
242}
243
244
245RUN_QUEUE_TEMPLATE_LIST
246status_t
247RUN_QUEUE_CLASS_NAME::GetInitStatus()
248{
249	return fInitStatus;
250}
251
252
253RUN_QUEUE_TEMPLATE_LIST
254Element*
255RUN_QUEUE_CLASS_NAME::PeekMaximum() const
256{
257	SCHEDULER_ENTER_FUNCTION();
258
259	PriorityEntry* maxPriority = fPriorityHeap.PeekRoot();
260	if (maxPriority == NULL)
261		return NULL;
262	unsigned int priority = PriorityHeap::GetKey(maxPriority);
263
264	ASSERT(priority <= MaxPriority);
265	ASSERT(fHeads[priority] != NULL);
266
267	Element* element = fHeads[priority];
268
269	ASSERT(sGetLink(element)->fPriority == priority);
270	ASSERT(fTails[priority] != NULL);
271	ASSERT(sGetLink(element)->fPrevious == NULL);
272
273	return element;
274}
275
276
277RUN_QUEUE_TEMPLATE_LIST
278void
279RUN_QUEUE_CLASS_NAME::PushFront(Element* element,
280	unsigned int priority)
281{
282	SCHEDULER_ENTER_FUNCTION();
283
284	ASSERT(priority <= MaxPriority);
285
286	RunQueueLink<Element>* elementLink = sGetLink(element);
287
288	ASSERT(elementLink->fPrevious == NULL);
289	ASSERT(elementLink->fNext == NULL);
290
291	ASSERT((fHeads[priority] == NULL && fTails[priority] == NULL)
292		|| (fHeads[priority] != NULL && fTails[priority] != NULL));
293
294	elementLink->fPriority = priority;
295	elementLink->fNext = fHeads[priority];
296	if (fHeads[priority] != NULL)
297		sGetLink(fHeads[priority])->fPrevious = element;
298	else {
299		fTails[priority] = element;
300		fPriorityHeap.Insert(&fPriorityEntries[priority], priority);
301	}
302	fHeads[priority] = element;
303}
304
305
306RUN_QUEUE_TEMPLATE_LIST
307void
308RUN_QUEUE_CLASS_NAME::PushBack(Element* element,
309	unsigned int priority)
310{
311	SCHEDULER_ENTER_FUNCTION();
312
313	ASSERT(priority <= MaxPriority);
314
315	RunQueueLink<Element>* elementLink = sGetLink(element);
316
317	ASSERT(elementLink->fPrevious == NULL);
318	ASSERT(elementLink->fNext == NULL);
319
320	ASSERT((fHeads[priority] == NULL && fTails[priority] == NULL)
321		|| (fHeads[priority] != NULL && fTails[priority] != NULL));
322
323	elementLink->fPriority = priority;
324	elementLink->fPrevious = fTails[priority];
325	if (fTails[priority] != NULL)
326		sGetLink(fTails[priority])->fNext = element;
327	else {
328		fHeads[priority] = element;
329		fPriorityHeap.Insert(&fPriorityEntries[priority], priority);
330	}
331	fTails[priority] = element;
332}
333
334
335RUN_QUEUE_TEMPLATE_LIST
336void
337RUN_QUEUE_CLASS_NAME::Remove(Element* element)
338{
339	SCHEDULER_ENTER_FUNCTION();
340
341	RunQueueLink<Element>* elementLink = sGetLink(element);
342	unsigned int priority = elementLink->fPriority;
343
344	ASSERT(elementLink->fPrevious != NULL || fHeads[priority] == element);
345	ASSERT(elementLink->fNext != NULL || fTails[priority] == element);
346
347	if (elementLink->fPrevious != NULL)
348		sGetLink(elementLink->fPrevious)->fNext = elementLink->fNext;
349	else
350		fHeads[priority] = elementLink->fNext;
351	if (elementLink->fNext != NULL)
352		sGetLink(elementLink->fNext)->fPrevious = elementLink->fPrevious;
353	else
354		fTails[priority] = elementLink->fPrevious;
355
356	ASSERT((fHeads[priority] == NULL && fTails[priority] == NULL)
357		|| (fHeads[priority] != NULL && fTails[priority] != NULL));
358
359	if (fHeads[priority] == NULL) {
360		fPriorityHeap.ModifyKey(&fPriorityEntries[priority], MaxPriority + 1);
361		ASSERT(fPriorityHeap.PeekRoot() == &fPriorityEntries[priority]);
362		fPriorityHeap.RemoveRoot();
363	}
364
365	elementLink->fPrevious = NULL;
366	elementLink->fNext = NULL;
367}
368
369
370RUN_QUEUE_TEMPLATE_LIST
371Element*
372RUN_QUEUE_CLASS_NAME::GetHead(unsigned int priority) const
373{
374	SCHEDULER_ENTER_FUNCTION();
375
376	ASSERT(priority <= MaxPriority);
377	return fHeads[priority];
378}
379
380
381RUN_QUEUE_TEMPLATE_LIST
382typename RUN_QUEUE_CLASS_NAME::ConstIterator
383RUN_QUEUE_CLASS_NAME::GetConstIterator() const
384{
385	return ConstIterator(this);
386}
387
388
389RUN_QUEUE_TEMPLATE_LIST
390GetLink RUN_QUEUE_CLASS_NAME::sGetLink;
391
392RUN_QUEUE_TEMPLATE_LIST
393GetLink RUN_QUEUE_CLASS_NAME::ConstIterator::sGetLink;
394
395
396#endif	// RUN_QUEUE_H
397
398