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> 120 RunQueueLink<Element>::RunQueueLink() 121 : 122 fPrevious(NULL), 123 fNext(NULL) 124 { 125 } 126 127 128 template<typename Element> 129 RunQueueLink<Element>* 130 RunQueueLinkImpl<Element>::GetRunQueueLink() 131 { 132 return &fRunQueueLink; 133 } 134 135 136 template<typename Element> 137 RunQueueLink<Element>* 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>* 146 RunQueueMemberGetLink<Element, LinkMember>::operator()(Element* element) const 147 { 148 return &(element->*LinkMember); 149 } 150 151 152 RUN_QUEUE_TEMPLATE_LIST 153 RUN_QUEUE_CLASS_NAME::ConstIterator::ConstIterator() 154 : 155 fList(NULL) 156 { 157 } 158 159 160 RUN_QUEUE_TEMPLATE_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 184 RUN_QUEUE_CLASS_NAME::ConstIterator::HasNext() const 185 { 186 return fNext != NULL; 187 } 188 189 190 RUN_QUEUE_TEMPLATE_LIST 191 Element* 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 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 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 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 247 RUN_QUEUE_CLASS_NAME::GetInitStatus() 248 { 249 return fInitStatus; 250 } 251 252 253 RUN_QUEUE_TEMPLATE_LIST 254 Element* 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 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 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 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* 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 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