2 * Copyright (c) 1998 Daniel Eischen <eischen@vigrid.com>.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
34 #include <sys/queue.h>
38 #include "pthread_private.h"
41 static void pq_insert_prio_list(pq_queue_t *pq, int prio);
45 _pq_init(pq_queue_t *pq, int minprio, int maxprio)
48 int prioslots = maxprio - minprio + 1;
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)
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;
66 /* Initialize the priority queue: */
67 TAILQ_INIT(&pq->pq_queue);
69 /* Remember the queue size: */
70 pq->pq_size = prioslots;
76 _pq_remove(pq_queue_t *pq, pthread_t pthread)
78 int prio = pthread->active_priority;
80 TAILQ_REMOVE(&pq->pq_lists[prio].pl_head, pthread, pqe);
85 _pq_insert_head(pq_queue_t *pq, pthread_t pthread)
87 int prio = pthread->active_priority;
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);
97 _pq_insert_tail(pq_queue_t *pq, pthread_t pthread)
99 int prio = pthread->active_priority;
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);
109 _pq_first(pq_queue_t *pq)
112 pthread_t pthread = NULL;
114 while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) &&
116 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
118 * The priority list is empty; remove the list
121 TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
123 /* Mark the list as not being in the queue: */
132 pq_insert_prio_list(pq_queue_t *pq, int prio)
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.
141 pql = TAILQ_FIRST(&pq->pq_queue);
142 while ((pql != NULL) && (pql->pl_prio > prio))
143 pql = TAILQ_NEXT(pql, pl_link);
145 /* Insert the list: */
147 TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link);
149 TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link);
151 /* Mark this list as being in the queue: */
152 pq->pq_lists[prio].pl_queued = 1;