pth_pqueue.c

   1 /*
   2 **  GNU Pth - The GNU Portable Threads
   3 **  Copyright (c) 1999-2006 Ralf S. Engelschall <rse@engelschall.com>
   4 **
   5 **  This file is part of GNU Pth, a non-preemptive thread scheduling
   6 **  library which can be found at http://www.gnu.org/software/pth/.
   7 **
   8 **  This library is free software; you can redistribute it and/or
   9 **  modify it under the terms of the GNU Lesser General Public
  10 **  License as published by the Free Software Foundation; either
  11 **  version 2.1 of the License, or (at your option) any later version.
  12 **
  13 **  This library is distributed in the hope that it will be useful,
  14 **  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 **  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16 **  Lesser General Public License for more details.
  17 **
  18 **  You should have received a copy of the GNU Lesser General Public
  19 **  License along with this library; if not, write to the Free Software
  20 **  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  21 **  USA, or contact Ralf S. Engelschall <rse@engelschall.com>.
  22 **
  23 **  pth_pqueue.c: Pth thread priority queues
  24 */
  25                              /* ``Real hackers can write assembly
  26                                   code in any language''
  27                                                    -- Unknown */
  28 #include "pth_p.h"
  29
  30 #if cpp
  31
  32 /* thread priority queue */
  33 struct pth_pqueue_st {
  34     pth_t q_head;
  35     int   q_num;
  36 };
  37 typedef struct pth_pqueue_st pth_pqueue_t;
  38
  39 #endif /* cpp */
  40
  41 /* initialize a priority queue; O(1) */
  42 intern void pth_pqueue_init(pth_pqueue_t *q)
  43 {
  44     if (q != NULL) {
  45         q->q_head = NULL;
  46         q->q_num  = 0;
  47     }
  48     return;
  49 }
  50
  51 /* insert thread into priority queue; O(n) */
  52 intern void pth_pqueue_insert(pth_pqueue_t *q, int prio, pth_t t)
  53 {
  54     pth_t c;
  55     int p;
  56
  57     if (q == NULL)
  58         return;
  59     if (q->q_head == NULL || q->q_num == 0) {
  60         /* add as first element */
  61         t->q_prev = t;
  62         t->q_next = t;
  63         t->q_prio = prio;
  64         q->q_head = t;
  65     }
  66     else if (q->q_head->q_prio < prio) {
  67         /* add as new head of queue */
  68         t->q_prev = q->q_head->q_prev;
  69         t->q_next = q->q_head;
  70         t->q_prev->q_next = t;
  71         t->q_next->q_prev = t;
  72         t->q_prio = prio;
  73         t->q_next->q_prio = prio - t->q_next->q_prio;
  74         q->q_head = t;
  75     }
  76     else {
  77         /* insert after elements with greater or equal priority */
  78         c = q->q_head;
  79         p = c->q_prio;
  80         while ((p - c->q_next->q_prio) >= prio && c->q_next != q->q_head) {
  81             c = c->q_next;
  82             p -= c->q_prio;
  83         }
  84         t->q_prev = c;
  85         t->q_next = c->q_next;
  86         t->q_prev->q_next = t;
  87         t->q_next->q_prev = t;
  88         t->q_prio = p - prio;
  89         if (t->q_next != q->q_head)
  90             t->q_next->q_prio -= t->q_prio;
  91     }
  92     q->q_num++;
  93     return;
  94 }
  95
  96 /* remove thread with maximum priority from priority queue; O(1) */
  97 intern pth_t pth_pqueue_delmax(pth_pqueue_t *q)
  98 {
  99     pth_t t;
 100
 101     if (q == NULL)
 102         return NULL;
 103     if (q->q_head == NULL)
 104         t = NULL;
 105     else if (q->q_head->q_next == q->q_head) {
 106         /* remove the last element and make queue empty */
 107         t = q->q_head;
 108         t->q_next = NULL;
 109         t->q_prev = NULL;
 110         t->q_prio = 0;
 111         q->q_head = NULL;
 112         q->q_num  = 0;
 113     }
 114     else {
 115         /* remove head of queue */
 116         t = q->q_head;
 117         t->q_prev->q_next = t->q_next;
 118         t->q_next->q_prev = t->q_prev;
 119         t->q_next->q_prio = t->q_prio - t->q_next->q_prio;
 120         t->q_prio = 0;
 121         q->q_head = t->q_next;
 122         q->q_num--;
 123     }
 124     return t;
 125 }
 126
 127 /* remove thread from priority queue; O(n) */
 128 intern void pth_pqueue_delete(pth_pqueue_t *q, pth_t t)
 129 {
 130     if (q == NULL)
 131         return;
 132     if (q->q_head == NULL)
 133         return;
 134     else if (q->q_head == t) {
 135         if (t->q_next == t) {
 136             /* remove the last element and make queue empty */
 137             t->q_next = NULL;
 138             t->q_prev = NULL;
 139             t->q_prio = 0;
 140             q->q_head = NULL;
 141             q->q_num  = 0;
 142         }
 143         else {
 144             /* remove head of queue */
 145             t->q_prev->q_next = t->q_next;
 146             t->q_next->q_prev = t->q_prev;
 147             t->q_next->q_prio = t->q_prio - t->q_next->q_prio;
 148             t->q_prio = 0;
 149             q->q_head = t->q_next;
 150             q->q_num--;
 151         }
 152     }
 153     else {
 154         t->q_prev->q_next = t->q_next;
 155         t->q_next->q_prev = t->q_prev;
 156         if (t->q_next != q->q_head)
 157             t->q_next->q_prio += t->q_prio;
 158         t->q_prio = 0;
 159         q->q_num--;
 160     }
 161     return;
 162 }
 163
 164 /* determine priority required to favorite a thread; O(1) */
 165 #if cpp
 166 #define pth_pqueue_favorite_prio(q) \
 167     ((q)->q_head != NULL ? (q)->q_head->q_prio + 1 : PTH_PRIO_MAX)
 168 #endif
 169
 170 /* move a thread inside queue to the top; O(n) */
 171 intern int pth_pqueue_favorite(pth_pqueue_t *q, pth_t t)
 172 {
 173     if (q == NULL)
 174         return FALSE;
 175     if (q->q_head == NULL || q->q_num == 0)
 176         return FALSE;
 177     /* element is already at top */
 178     if (q->q_num == 1)
 179         return TRUE;
 180     /* move to top */
 181     pth_pqueue_delete(q, t);
 182     pth_pqueue_insert(q, pth_pqueue_favorite_prio(q), t);
 183     return TRUE;
 184 }
 185
 186 /* increase priority of all(!) threads in queue; O(1) */
 187 intern void pth_pqueue_increase(pth_pqueue_t *q)
 188 {
 189     if (q == NULL)
 190         return;
 191     if (q->q_head == NULL)
 192         return;
 193     /* <grin> yes, that's all ;-) */
 194     q->q_head->q_prio += 1;
 195     return;
 196 }
 197
 198 /* return number of elements in priority queue: O(1) */
 199 #if cpp
 200 #define pth_pqueue_elements(q) \
 201     ((q) == NULL ? (-1) : (q)->q_num)
 202 #endif
 203
 204 /* walk to first thread in queue; O(1) */
 205 #if cpp
 206 #define pth_pqueue_head(q) \
 207     ((q) == NULL ? NULL : (q)->q_head)
 208 #endif
 209
 210 /* walk to last thread in queue */
 211 intern pth_t pth_pqueue_tail(pth_pqueue_t *q)
 212 {
 213     if (q == NULL)
 214         return NULL;
 215     if (q->q_head == NULL)
 216         return NULL;
 217     return q->q_head->q_prev;
 218 }
 219
 220 /* walk to next or previous thread in queue; O(1) */
 221 intern pth_t pth_pqueue_walk(pth_pqueue_t *q, pth_t t, int direction)
 222 {
 223     pth_t tn;
 224
 225     if (q == NULL || t == NULL)
 226         return NULL;
 227     tn = NULL;
 228     if (direction == PTH_WALK_PREV) {
 229         if (t != q->q_head)
 230             tn = t->q_prev;
 231     }
 232     else if (direction == PTH_WALK_NEXT) {
 233         tn = t->q_next;
 234         if (tn == q->q_head)
 235             tn = NULL;
 236     }
 237     return tn;
 238 }
 239
 240 /* check whether a thread is in a queue; O(n) */
 241 intern int pth_pqueue_contains(pth_pqueue_t *q, pth_t t)
 242 {
 243     pth_t tc;
 244     int found;
 245
 246     found = FALSE;
 247     for (tc = pth_pqueue_head(q); tc != NULL;
 248          tc = pth_pqueue_walk(q, tc, PTH_WALK_NEXT)) {
 249         if (tc == t) {
 250             found = TRUE;
 251             break;
 252         }
 253     }
 254     return found;
 255 }
 256