lib/libmthread/queue.c

   1 #include <minix/mthread.h>
   2 #include "global.h"
   3 #include "proto.h"
   4
   5 /*===========================================================================*
   6  *                              mthread_queue_add                            *
   7  *===========================================================================*/
   8 void mthread_queue_add(queue, thread)
   9 mthread_queue_t *queue;         /* Queue we want thread to append to */
  10 mthread_thread_t thread;
  11 {
  12 /* Append a thread to the tail of the queue. As a process can be present on
  13  * only one queue at the same time, we can use the threads array's 'next'
  14  * pointer to point to the next thread on the queue.
  15  */
  16   mthread_tcb_t *last;
  17
  18   if (!isokthreadid(thread))
  19         mthread_panic("Can't append invalid thread ID to a queue");
  20
  21   last = mthread_find_tcb(thread);
  22
  23   if (mthread_queue_isempty(queue)) {
  24         queue->mq_head = queue->mq_tail = last;
  25   } else  {
  26         queue->mq_tail->m_next = last;
  27         queue->mq_tail = last;  /* 'last' is the new last in line */
  28   }
  29 }
  30
  31
  32 /*===========================================================================*
  33  *                              mthread_queue_init                           *
  34  *===========================================================================*/
  35 void mthread_queue_init(queue)
  36 mthread_queue_t *queue;         /* Queue that has to be initialized */
  37 {
  38 /* Initialize queue to a known state */
  39
  40   queue->mq_head = queue->mq_tail = NULL;
  41 }
  42
  43
  44 /*===========================================================================*
  45  *                              mthread_queue_isempty                        *
  46  *===========================================================================*/
  47 int mthread_queue_isempty(queue)
  48 mthread_queue_t *queue;
  49 {
  50   return(queue->mq_head == NULL);
  51 }
  52
  53
  54 /*===========================================================================*
  55  *                              mthread_dump_queue                           *
  56  *===========================================================================*/
  57 #ifdef MDEBUG
  58 void mthread_dump_queue(queue)
  59 mthread_queue_t *queue;
  60 {
  61   int threshold, count = 0;
  62   mthread_tcb_t *t;
  63   mthread_thread_t tid;
  64   threshold = no_threads;
  65   printf("Dumping queue: ");
  66
  67   if(queue->mq_head != NULL) {
  68         t = queue->mq_head;
  69         if (t == &mainthread) tid = MAIN_THREAD;
  70         else tid = t->m_tid;
  71         printf("%d ", tid);
  72         count++;
  73         t = t->m_next;
  74         while (t != NULL) {
  75                 if (t == &mainthread) tid = MAIN_THREAD;
  76                 else tid = t->m_tid;
  77                 printf("%d ", tid);
  78                 t = t->m_next;
  79                 count++;
  80                 if (count > threshold) break;
  81         }
  82   } else {
  83         printf("[empty]");
  84   }
  85
  86   printf("\n");
  87 }
  88 #endif
  89
  90 /*===========================================================================*
  91  *                              mthread_queue_remove                         *
  92  *===========================================================================*/
  93 mthread_thread_t mthread_queue_remove(queue)
  94 mthread_queue_t *queue;         /* Queue we want a thread from */
  95 {
  96 /* Get the first thread in this queue, if there is one. */
  97   mthread_thread_t thread;
  98   mthread_tcb_t *tcb, *random_tcb, *prev;
  99   int count = 0, offset_id = 0, picked_random = 0;
 100
 101   tcb = queue->mq_head;
 102
 103   if (MTHREAD_RND_SCHED) {
 104         /* Count items on queue */
 105         random_tcb = queue->mq_head;
 106         if (random_tcb != NULL) {
 107                 do {
 108                         count++;
 109                         random_tcb = random_tcb->m_next;
 110                 } while (random_tcb != NULL);
 111         }
 112
 113         if (count > 1) {
 114                 picked_random = 1;
 115
 116                 /* Get random offset */
 117                 offset_id = random() % count;
 118
 119                 /* Find offset in queue */
 120                 random_tcb = queue->mq_head;
 121                 prev = random_tcb;
 122                 while (--offset_id > 0) {
 123                         prev = random_tcb;
 124                         random_tcb = random_tcb->m_next;
 125                 }
 126
 127                 /* Stitch head and tail together */
 128                 prev->m_next = random_tcb->m_next;
 129
 130                 /* Fix head and tail */
 131                 if (queue->mq_head == random_tcb)
 132                         queue->mq_head = random_tcb->m_next;
 133                 if (queue->mq_tail == random_tcb)
 134                         queue->mq_tail = prev;
 135
 136                 tcb = random_tcb;
 137         }
 138   }
 139
 140   /* Retrieve thread id from tcb */
 141   if (tcb == NULL) thread = NO_THREAD;
 142   else if (tcb == &mainthread) thread = MAIN_THREAD;
 143   else thread = (tcb->m_tid);
 144
 145   /* If we didn't pick a random thread and queue is not empty... */
 146   if (!picked_random && thread != NO_THREAD) {
 147         tcb = queue->mq_head;
 148         if (queue->mq_head == queue->mq_tail) {
 149                 /* Queue holds only one thread */
 150                 queue->mq_head = queue->mq_tail = NULL; /* So mark thread empty */
 151         } else {
 152                 /* Second thread in line is the new first */
 153                 queue->mq_head = queue->mq_head->m_next;
 154         }
 155   }
 156
 157   if (tcb != NULL)
 158         tcb->m_next = NULL; /* This thread is no longer part of a queue */
 159
 160   return(thread);
 161 }
 162