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
17 template<typename Element>
18 struct RunQueueLink {
19 RunQueueLink();
20
21 unsigned int fPriority;
22 Element* fPrevious;
23 Element* fNext;
24 };
25
26 template<typename Element>
27 class RunQueueLinkImpl {
28 public:
29 inline RunQueueLink<Element>* GetRunQueueLink();
30
31 private:
32 RunQueueLink<Element> fRunQueueLink;
33 };
34
35 template<typename Element>
36 class RunQueueStandardGetLink {
37 private:
38 typedef RunQueueLink<Element> Link;
39
40 public:
41 inline Link* operator()(Element* element) const;
42 };
43
44 template<typename Element, RunQueueLink<Element> Element::*LinkMember>
45 class RunQueueMemberGetLink {
46 private:
47 typedef RunQueueLink<Element> Link;
48
49 public:
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
57 template<typename Element, unsigned int MaxPriority,
58 typename GetLink = RunQueueStandardGetLink<Element> >
59 class RunQueue {
60 public:
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
99 private:
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
119 template<typename Element>
RunQueueLink()120 RunQueueLink<Element>::RunQueueLink()
121 :
122 fPrevious(NULL),
123 fNext(NULL)
124 {
125 }
126
127
128 template<typename Element>
129 RunQueueLink<Element>*
GetRunQueueLink()130 RunQueueLinkImpl<Element>::GetRunQueueLink()
131 {
132 return &fRunQueueLink;
133 }
134
135
136 template<typename Element>
137 RunQueueLink<Element>*
operator()138 RunQueueStandardGetLink<Element>::operator()(Element* element) const
139 {
140 return element->GetRunQueueLink();
141 }
142
143
144 template<typename Element, RunQueueLink<Element> Element::*LinkMember>
145 RunQueueLink<Element>*
operator()146 RunQueueMemberGetLink<Element, LinkMember>::operator()(Element* element) const
147 {
148 return &(element->*LinkMember);
149 }
150
151
152 RUN_QUEUE_TEMPLATE_LIST
ConstIterator()153 RUN_QUEUE_CLASS_NAME::ConstIterator::ConstIterator()
154 :
155 fList(NULL)
156 {
157 }
158
159
160 RUN_QUEUE_TEMPLATE_LIST
ConstIterator(const RunQueue<Element,MaxPriority,GetLink> * list)161 RUN_QUEUE_CLASS_NAME::ConstIterator::ConstIterator(const RunQueue<Element,
162 MaxPriority, GetLink>* list)
163 :
164 fList(list)
165 {
166 Rewind();
167 }
168
169
170 RUN_QUEUE_TEMPLATE_LIST
171 typename RUN_QUEUE_CLASS_NAME::ConstIterator&
172 RUN_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
182 RUN_QUEUE_TEMPLATE_LIST
183 bool
HasNext()184 RUN_QUEUE_CLASS_NAME::ConstIterator::HasNext() const
185 {
186 return fNext != NULL;
187 }
188
189
190 RUN_QUEUE_TEMPLATE_LIST
191 Element*
Next()192 RUN_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
207 RUN_QUEUE_TEMPLATE_LIST
208 void
Rewind()209 RUN_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
220 RUN_QUEUE_TEMPLATE_LIST
221 void
_FindNextPriority()222 RUN_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
234 RUN_QUEUE_TEMPLATE_LIST
RunQueue()235 RUN_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
245 RUN_QUEUE_TEMPLATE_LIST
246 status_t
GetInitStatus()247 RUN_QUEUE_CLASS_NAME::GetInitStatus()
248 {
249 return fInitStatus;
250 }
251
252
253 RUN_QUEUE_TEMPLATE_LIST
254 Element*
PeekMaximum()255 RUN_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
277 RUN_QUEUE_TEMPLATE_LIST
278 void
PushFront(Element * element,unsigned int priority)279 RUN_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
306 RUN_QUEUE_TEMPLATE_LIST
307 void
PushBack(Element * element,unsigned int priority)308 RUN_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
335 RUN_QUEUE_TEMPLATE_LIST
336 void
Remove(Element * element)337 RUN_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
370 RUN_QUEUE_TEMPLATE_LIST
371 Element*
GetHead(unsigned int priority)372 RUN_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
381 RUN_QUEUE_TEMPLATE_LIST
382 typename RUN_QUEUE_CLASS_NAME::ConstIterator
GetConstIterator()383 RUN_QUEUE_CLASS_NAME::GetConstIterator() const
384 {
385 return ConstIterator(this);
386 }
387
388
389 RUN_QUEUE_TEMPLATE_LIST
390 GetLink RUN_QUEUE_CLASS_NAME::sGetLink;
391
392 RUN_QUEUE_TEMPLATE_LIST
393 GetLink RUN_QUEUE_CLASS_NAME::ConstIterator::sGetLink;
394
395
396 #endif // RUN_QUEUE_H
397
398