thr_priority_queue.c revision 55194
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 * $FreeBSD: head/lib/libkse/thread/thr_priority_queue.c 55194 1999-12-28 18:13:04Z deischen $ 33 */ 34#include <stdlib.h> 35#include <sys/queue.h> 36#include <string.h> 37#ifdef _THREAD_SAFE 38#include <pthread.h> 39#include "pthread_private.h" 40 41/* Prototypes: */ 42static void pq_insert_prio_list(pq_queue_t *pq, int prio); 43 44#if defined(_PTHREADS_INVARIANTS) 45 46static int _pq_active = 0; 47 48#define _PQ_IN_SCHEDQ (PTHREAD_FLAGS_IN_PRIOQ | PTHREAD_FLAGS_IN_WAITQ | PTHREAD_FLAGS_IN_WORKQ) 49 50#define _PQ_SET_ACTIVE() _pq_active = 1 51#define _PQ_CLEAR_ACTIVE() _pq_active = 0 52#define _PQ_ASSERT_ACTIVE(msg) do { \ 53 if (_pq_active == 0) \ 54 PANIC(msg); \ 55} while (0) 56#define _PQ_ASSERT_INACTIVE(msg) do { \ 57 if (_pq_active != 0) \ 58 PANIC(msg); \ 59} while (0) 60#define _PQ_ASSERT_IN_WAITQ(thrd, msg) do { \ 61 if (((thrd)->flags & PTHREAD_FLAGS_IN_WAITQ) == 0) \ 62 PANIC(msg); \ 63} while (0) 64#define _PQ_ASSERT_IN_PRIOQ(thrd, msg) do { \ 65 if (((thrd)->flags & PTHREAD_FLAGS_IN_PRIOQ) == 0) \ 66 PANIC(msg); \ 67} while (0) 68#define _PQ_ASSERT_NOT_QUEUED(thrd, msg) do { \ 69 if ((thrd)->flags & _PQ_IN_SCHEDQ) \ 70 PANIC(msg); \ 71} while (0) 72 73#else 74 75#define _PQ_SET_ACTIVE() 76#define _PQ_CLEAR_ACTIVE() 77#define _PQ_ASSERT_ACTIVE(msg) 78#define _PQ_ASSERT_INACTIVE(msg) 79#define _PQ_ASSERT_IN_WAITQ(thrd, msg) 80#define _PQ_ASSERT_IN_PRIOQ(thrd, msg) 81#define _PQ_ASSERT_NOT_QUEUED(thrd, msg) 82#define _PQ_CHECK_PRIO() 83 84#endif 85 86 87int 88_pq_alloc(pq_queue_t *pq, int minprio, int maxprio) 89{ 90 int ret = 0; 91 int prioslots = maxprio - minprio + 1; 92 93 if (pq == NULL) 94 ret = -1; 95 96 /* Create the priority queue with (maxprio - minprio + 1) slots: */ 97 else if ((pq->pq_lists = 98 (pq_list_t *) malloc(sizeof(pq_list_t) * prioslots)) == NULL) 99 ret = -1; 100 101 else { 102 /* Remember the queue size: */ 103 pq->pq_size = prioslots; 104 105 ret = _pq_init(pq); 106 107 } 108 return (ret); 109} 110 111int 112_pq_init(pq_queue_t *pq) 113{ 114 int i, ret = 0; 115 116 if ((pq == NULL) || (pq->pq_lists == NULL)) 117 ret = -1; 118 119 else { 120 /* Initialize the queue for each priority slot: */ 121 for (i = 0; i < pq->pq_size; i++) { 122 TAILQ_INIT(&pq->pq_lists[i].pl_head); 123 pq->pq_lists[i].pl_prio = i; 124 pq->pq_lists[i].pl_queued = 0; 125 } 126 127 /* Initialize the priority queue: */ 128 TAILQ_INIT(&pq->pq_queue); 129 _PQ_CLEAR_ACTIVE(); 130 } 131 return (ret); 132} 133 134void 135_pq_remove(pq_queue_t *pq, pthread_t pthread) 136{ 137 int prio = pthread->active_priority; 138 139 /* 140 * Make some assertions when debugging is enabled: 141 */ 142 _PQ_ASSERT_INACTIVE("_pq_remove: pq_active"); 143 _PQ_SET_ACTIVE(); 144 _PQ_ASSERT_IN_PRIOQ(pthread, "_pq_remove: Not in priority queue"); 145 146 /* 147 * Remove this thread from priority list. Note that if 148 * the priority list becomes empty, it is not removed 149 * from the priority queue because another thread may be 150 * added to the priority list (resulting in a needless 151 * removal/insertion). Priority lists are only removed 152 * from the priority queue when _pq_first is called. 153 */ 154 TAILQ_REMOVE(&pq->pq_lists[prio].pl_head, pthread, pqe); 155 156 /* This thread is now longer in the priority queue. */ 157 pthread->flags &= ~PTHREAD_FLAGS_IN_PRIOQ; 158 159 _PQ_CLEAR_ACTIVE(); 160} 161 162 163void 164_pq_insert_head(pq_queue_t *pq, pthread_t pthread) 165{ 166 int prio = pthread->active_priority; 167 168 /* 169 * Make some assertions when debugging is enabled: 170 */ 171 _PQ_ASSERT_INACTIVE("_pq_insert_head: pq_active"); 172 _PQ_SET_ACTIVE(); 173 _PQ_ASSERT_NOT_QUEUED(pthread, 174 "_pq_insert_head: Already in priority queue"); 175 176 TAILQ_INSERT_HEAD(&pq->pq_lists[prio].pl_head, pthread, pqe); 177 if (pq->pq_lists[prio].pl_queued == 0) 178 /* Insert the list into the priority queue: */ 179 pq_insert_prio_list(pq, prio); 180 181 /* Mark this thread as being in the priority queue. */ 182 pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ; 183 184 _PQ_CLEAR_ACTIVE(); 185} 186 187 188void 189_pq_insert_tail(pq_queue_t *pq, pthread_t pthread) 190{ 191 int prio = pthread->active_priority; 192 193 /* 194 * Make some assertions when debugging is enabled: 195 */ 196 _PQ_ASSERT_INACTIVE("_pq_insert_tail: pq_active"); 197 _PQ_SET_ACTIVE(); 198 _PQ_ASSERT_NOT_QUEUED(pthread, 199 "_pq_insert_tail: Already in priority queue"); 200 201 TAILQ_INSERT_TAIL(&pq->pq_lists[prio].pl_head, pthread, pqe); 202 if (pq->pq_lists[prio].pl_queued == 0) 203 /* Insert the list into the priority queue: */ 204 pq_insert_prio_list(pq, prio); 205 206 /* Mark this thread as being in the priority queue. */ 207 pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ; 208 209 _PQ_CLEAR_ACTIVE(); 210} 211 212 213pthread_t 214_pq_first(pq_queue_t *pq) 215{ 216 pq_list_t *pql; 217 pthread_t pthread = NULL; 218 219 /* 220 * Make some assertions when debugging is enabled: 221 */ 222 _PQ_ASSERT_INACTIVE("_pq_first: pq_active"); 223 _PQ_SET_ACTIVE(); 224 225 while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) && 226 (pthread == NULL)) { 227 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) { 228 /* 229 * The priority list is empty; remove the list 230 * from the queue. 231 */ 232 TAILQ_REMOVE(&pq->pq_queue, pql, pl_link); 233 234 /* Mark the list as not being in the queue: */ 235 pql->pl_queued = 0; 236 } 237 } 238 239 _PQ_CLEAR_ACTIVE(); 240 return (pthread); 241} 242 243 244static void 245pq_insert_prio_list(pq_queue_t *pq, int prio) 246{ 247 pq_list_t *pql; 248 249 /* 250 * Make some assertions when debugging is enabled: 251 */ 252 _PQ_ASSERT_ACTIVE("pq_insert_prio_list: pq_active"); 253 254 /* 255 * The priority queue is in descending priority order. Start at 256 * the beginning of the queue and find the list before which the 257 * new list should be inserted. 258 */ 259 pql = TAILQ_FIRST(&pq->pq_queue); 260 while ((pql != NULL) && (pql->pl_prio > prio)) 261 pql = TAILQ_NEXT(pql, pl_link); 262 263 /* Insert the list: */ 264 if (pql == NULL) 265 TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link); 266 else 267 TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link); 268 269 /* Mark this list as being in the queue: */ 270 pq->pq_lists[prio].pl_queued = 1; 271} 272 273#if defined(_PTHREADS_INVARIANTS) 274void 275_waitq_insert(pthread_t pthread) 276{ 277 pthread_t tid; 278 279 /* 280 * Make some assertions when debugging is enabled: 281 */ 282 _PQ_ASSERT_INACTIVE("_waitq_insert: pq_active"); 283 _PQ_SET_ACTIVE(); 284 _PQ_ASSERT_NOT_QUEUED(pthread, "_waitq_insert: Already in queue"); 285 286 if (pthread->wakeup_time.tv_sec == -1) 287 TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe); 288 else { 289 tid = TAILQ_FIRST(&_waitingq); 290 while ((tid != NULL) && (tid->wakeup_time.tv_sec != -1) && 291 ((tid->wakeup_time.tv_sec < pthread->wakeup_time.tv_sec) || 292 ((tid->wakeup_time.tv_sec == pthread->wakeup_time.tv_sec) && 293 (tid->wakeup_time.tv_nsec <= pthread->wakeup_time.tv_nsec)))) 294 tid = TAILQ_NEXT(tid, pqe); 295 if (tid == NULL) 296 TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe); 297 else 298 TAILQ_INSERT_BEFORE(tid, pthread, pqe); 299 } 300 pthread->flags |= PTHREAD_FLAGS_IN_WAITQ; 301 302 _PQ_CLEAR_ACTIVE(); 303} 304 305void 306_waitq_remove(pthread_t pthread) 307{ 308 /* 309 * Make some assertions when debugging is enabled: 310 */ 311 _PQ_ASSERT_INACTIVE("_waitq_remove: pq_active"); 312 _PQ_SET_ACTIVE(); 313 _PQ_ASSERT_IN_WAITQ(pthread, "_waitq_remove: Not in queue"); 314 315 TAILQ_REMOVE(&_waitingq, pthread, pqe); 316 pthread->flags &= ~PTHREAD_FLAGS_IN_WAITQ; 317 318 _PQ_CLEAR_ACTIVE(); 319} 320 321void 322_waitq_setactive(void) 323{ 324 _PQ_ASSERT_INACTIVE("_waitq_setactive: pq_active"); 325 _PQ_SET_ACTIVE(); 326} 327 328void 329_waitq_clearactive(void) 330{ 331 _PQ_ASSERT_ACTIVE("_waitq_clearactive: ! pq_active"); 332 _PQ_CLEAR_ACTIVE(); 333} 334#endif 335#endif 336