src/system/kernel/scheduler/RunQueue.h

   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