kernel/fiasco/src/kern/prio_list.cpp

   1 INTERFACE:
   2
   3 #include <cassert>
   4 #include <dlist>
   5 #include <hlist>
   6 #include "member_offs.h"
   7 #include "spin_lock.h"
   8 #include "types.h"
   9
  10 /**
  11  * Priority sorted list with insert complexity O(n) n = number of available
  12  * priorities (256 in Fiasco).
  13  */
  14
  15
  16 class Prio_list_elem;
  17
  18 /**
  19  * Priority sorted list.
  20  *
  21  * The list is organized in a way that the highest priority member can be
  22  * found with O(1). Ever dequeue operation is also O(1).
  23  *
  24  * There is a forward iteratable list with at most one element per priority.
  25  * Elements with the same priority are handled in a double-linked circular
  26  * list for each priority. This double-linked list implements FIFO policy for
  27  * finding the next element.
  28  */
  29 class Prio_list : private cxx::H_list<Prio_list_elem>
  30 {
  31   MEMBER_OFFSET();
  32   friend class Jdb_sender_list;
  33 public:
  34   typedef cxx::H_list<Prio_list_elem> P_list;
  35   typedef cxx::D_list_cyclic<Prio_list_elem> S_list;
  36
  37   using P_list::front;
  38   using P_list::empty;
  39
  40   Prio_list_elem *first() const { return front(); }
  41 };
  42
  43 class Iteratable_prio_list : public Prio_list
  44 {
  45 public:
  46   Spin_lock<> *lock() { return &_lock; }
  47
  48 private:
  49   Prio_list_elem *_cursor;
  50   Spin_lock<> _lock;
  51 };
  52
  53 typedef Iteratable_prio_list Locked_prio_list;
  54
  55
  56 /**
  57  * Single element of a priority sorted list.
  58  */
  59 class Prio_list_elem : public cxx::H_list_item, public cxx::D_list_item
  60 {
  61   MEMBER_OFFSET();
  62 private:
  63   friend class Prio_list;
  64   friend class Jdb_sender_list;
  65   typedef cxx::D_list_cyclic<Prio_list_elem> S_list;
  66
  67   /**
  68    * Priority, the higher the better.
  69    */
  70   unsigned short _prio;
  71 };
  72
  73
  74
  75 IMPLEMENTATION:
  76
  77 /**
  78  * Setup pointers for enqueue.
  79  */
  80 PRIVATE inline
  81 void
  82 Prio_list_elem::init(unsigned short p)
  83 {
  84   _prio = p;
  85 }
  86
  87 /**
  88  * Get the priority.
  89  */
  90 PUBLIC inline
  91 unsigned short
  92 Prio_list_elem::prio() const
  93 { return _prio; }
  94
  95 PUBLIC inline
  96 Prio_list_elem *
  97 Prio_list::next(Prio_list_elem *e) const
  98 {
  99   S_list::Iterator i = ++S_list::iter(e);
 100   if (P_list::in_list(*i))
 101     return *++P_list::iter(*i);
 102   return *i;
 103 }
 104
 105 /**
 106  * Insert a new element into the priority list.
 107  * @param e the element to insert
 108  * @param prio the priority for the element
 109  */
 110 PUBLIC inline NEEDS[Prio_list_elem::init]
 111 void
 112 Prio_list::insert(Prio_list_elem *e, unsigned short prio)
 113 {
 114   assert (e);
 115   e->init(prio);
 116
 117   Iterator pos = begin();
 118
 119   while (pos != end() && pos->prio() > prio)
 120     ++pos;
 121
 122   if (pos != end() && pos->prio() == prio)
 123     S_list::insert_before(e, S_list::iter(*pos));
 124   else
 125     {
 126       S_list::self_insert(e);
 127       insert_before(e, pos);
 128     }
 129 }
 130
 131 /**
 132  * Is the element actually enqueued?
 133  * @return true if the element is actaully enqueued in a list.
 134  */
 135 PUBLIC inline
 136 bool Prio_list_elem::in_list() const { return S_list::in_list(this); }
 137
 138 /**
 139  * Dequeue a given element from the list.
 140  * @param e the element to dequeue
 141  */
 142 PUBLIC inline
 143 void
 144 Prio_list::dequeue(Prio_list_elem *e, Prio_list_elem **next = 0)
 145 {
 146   if (P_list::in_list(e))
 147     {
 148       assert (S_list::in_list(e));
 149       // yes we are the head of our priority
 150       if (S_list::has_sibling(e))
 151         {
 152           P_list::replace(e, *++S_list::iter(e));
 153           if (next) *next = *++S_list::iter(e);
 154         }
 155       else
 156         {
 157           if (next) *next = *++P_list::iter(e);
 158           P_list::remove(e);
 159         }
 160     }
 161   else
 162     {
 163       if (next)
 164         {
 165           if (P_list::in_list(*++S_list::iter(e))) // actually we are the last on our priority
 166             *next = *++P_list::iter(e);
 167           else
 168             *next = *++S_list::iter(e);
 169         }
 170     }
 171   S_list::remove(e);
 172 }
 173
 174 PUBLIC inline
 175 Iteratable_prio_list::Iteratable_prio_list() : _cursor(0), _lock(Spin_lock<>::Unlocked) {}
 176
 177 /**
 178  * Dequeue a given element from the list.
 179  * @param e the element to dequeue
 180  */
 181 PUBLIC inline NEEDS[Prio_list::dequeue]
 182 void
 183 Iteratable_prio_list::dequeue(Prio_list_elem *e)
 184 {
 185   Prio_list_elem **c = 0;
 186   if (EXPECT_FALSE(_cursor != 0) && EXPECT_FALSE(_cursor == e))
 187     c = &_cursor;
 188
 189   Prio_list::dequeue(e, c);
 190 }
 191
 192 PUBLIC inline
 193 void
 194 Iteratable_prio_list::cursor(Prio_list_elem *e)
 195 { _cursor = e; }
 196
 197 PUBLIC inline
 198 Prio_list_elem *
 199 Iteratable_prio_list::cursor() const
 200 { return _cursor; }
 201