lib/libc_r/uthread/uthread_priority_queue.c

   1 /*
   2  * Copyright (c) 1998 Daniel Eischen <eischen@vigrid.com>.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by Daniel Eischen.
  16  * 4. Neither the name of the author nor the names of any co-contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY DANIEL EISCHEN AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  */
  33 #include <stdlib.h>
  34 #include <sys/queue.h>
  35 #include <string.h>
  36 #ifdef _THREAD_SAFE
  37 #include <pthread.h>
  38 #include "pthread_private.h"
  39
  40 /* Prototypes: */
  41 static void pq_insert_prio_list(pq_queue_t *pq, int prio);
  42
  43
  44 int
  45 _pq_init(pq_queue_t *pq, int minprio, int maxprio)
  46 {
  47         int i, ret = 0;
  48         int prioslots = maxprio - minprio + 1;
  49
  50         if (pq == NULL)
  51                 ret = -1;
  52
  53         /* Create the priority queue with (maxprio - minprio + 1) slots: */
  54         else if ((pq->pq_lists =
  55             (pq_list_t *) malloc(sizeof(pq_list_t) * prioslots)) == NULL)
  56                 ret = -1;
  57
  58         else {
  59                 /* Initialize the queue for each priority slot: */
  60                 for (i = 0; i < prioslots; i++) {
  61                         TAILQ_INIT(&pq->pq_lists[i].pl_head);
  62                         pq->pq_lists[i].pl_prio = i;
  63                         pq->pq_lists[i].pl_queued = 0;
  64                 }
  65
  66                 /* Initialize the priority queue: */
  67                 TAILQ_INIT(&pq->pq_queue);
  68
  69                 /* Remember the queue size: */
  70                 pq->pq_size = prioslots;
  71         }
  72         return (ret);
  73 }
  74
  75 void
  76 _pq_remove(pq_queue_t *pq, pthread_t pthread)
  77 {
  78         int prio = pthread->active_priority;
  79
  80         TAILQ_REMOVE(&pq->pq_lists[prio].pl_head, pthread, pqe);
  81 }
  82
  83
  84 void
  85 _pq_insert_head(pq_queue_t *pq, pthread_t pthread)
  86 {
  87         int prio = pthread->active_priority;
  88
  89         TAILQ_INSERT_HEAD(&pq->pq_lists[prio].pl_head, pthread, pqe);
  90         if (pq->pq_lists[prio].pl_queued == 0)
  91                 /* Insert the list into the priority queue: */
  92                 pq_insert_prio_list(pq, prio);
  93 }
  94
  95
  96 void
  97 _pq_insert_tail(pq_queue_t *pq, pthread_t pthread)
  98 {
  99         int prio = pthread->active_priority;
 100
 101         TAILQ_INSERT_TAIL(&pq->pq_lists[prio].pl_head, pthread, pqe);
 102         if (pq->pq_lists[prio].pl_queued == 0)
 103                 /* Insert the list into the priority queue: */
 104                 pq_insert_prio_list(pq, prio);
 105 }
 106
 107
 108 pthread_t
 109 _pq_first(pq_queue_t *pq)
 110 {
 111         pq_list_t *pql;
 112         pthread_t pthread = NULL;
 113
 114         while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) &&
 115             (pthread == NULL)) {
 116                 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
 117                         /*
 118                          * The priority list is empty; remove the list
 119                          * from the queue.
 120                          */
 121                         TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
 122
 123                         /* Mark the list as not being in the queue: */
 124                         pql->pl_queued = 0;
 125                 }
 126         }
 127         return (pthread);
 128 }
 129
 130
 131 static void
 132 pq_insert_prio_list(pq_queue_t *pq, int prio)
 133 {
 134         pq_list_t *pql;
 135
 136         /*
 137          * The priority queue is in descending priority order.  Start at
 138          * the beginning of the queue and find the list before which the
 139          * new list should to be inserted.
 140          */
 141         pql = TAILQ_FIRST(&pq->pq_queue);
 142         while ((pql != NULL) && (pql->pl_prio > prio))
 143                 pql = TAILQ_NEXT(pql, pl_link);
 144
 145         /* Insert the list: */
 146         if (pql == NULL)
 147                 TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link);
 148         else
 149                 TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link);
 150
 151         /* Mark this list as being in the queue: */
 152         pq->pq_lists[prio].pl_queued = 1;
 153 }
 154
 155 #endif