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