queue.h revision 25188
11556Srgrimes/* 21556Srgrimes * Copyright (c) 1991, 1993 31556Srgrimes * The Regents of the University of California. All rights reserved. 41556Srgrimes * 51556Srgrimes * Redistribution and use in source and binary forms, with or without 61556Srgrimes * modification, are permitted provided that the following conditions 71556Srgrimes * are met: 81556Srgrimes * 1. Redistributions of source code must retain the above copyright 91556Srgrimes * notice, this list of conditions and the following disclaimer. 101556Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111556Srgrimes * notice, this list of conditions and the following disclaimer in the 121556Srgrimes * documentation and/or other materials provided with the distribution. 131556Srgrimes * 3. All advertising materials mentioning features or use of this software 141556Srgrimes * must display the following acknowledgement: 151556Srgrimes * This product includes software developed by the University of 161556Srgrimes * California, Berkeley and its contributors. 171556Srgrimes * 4. Neither the name of the University nor the names of its contributors 181556Srgrimes * may be used to endorse or promote products derived from this software 191556Srgrimes * without specific prior written permission. 201556Srgrimes * 211556Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 221556Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 231556Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 241556Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 251556Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 261556Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 271556Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 281556Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 291556Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 301556Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3136152Scharnier * SUCH DAMAGE. 3236152Scharnier * 3336152Scharnier * @(#)queue.h 8.5 (Berkeley) 8/20/94 341556Srgrimes * $Id: queue.h,v 1.14 1997/04/14 18:22:02 phk Exp $ 3599110Sobrien */ 3699110Sobrien 371556Srgrimes#ifndef _SYS_QUEUE_H_ 381556Srgrimes#define _SYS_QUEUE_H_ 391556Srgrimes 401556Srgrimes/* 411556Srgrimes * This file defines five types of data structures: singly-linked lists, 421556Srgrimes * slingly-linked tail queues, lists, tail queues, and circular queues. 431556Srgrimes * 441556Srgrimes * A singly-linked list is headed by a single forward pointer. The elements 451556Srgrimes * are singly linked for minimum space and pointer manipulation overhead at 461556Srgrimes * the expense of O(n) removal for arbitrary elements. New elements can be 471556Srgrimes * added to the list after an existing element or at the head of the list. 481556Srgrimes * Elements being removed from the head of the list should use the explicit 4990111Simp * macro for this purpose for optimum efficiency. A singly-linked list may 5076810Skris * only be traversed in the forward direction. Singly-linked lists are ideal 511556Srgrimes * for applications with large datasets and few or no removals or for 521556Srgrimes * implementing a LIFO queue. 531556Srgrimes * 541556Srgrimes * A singly-linked tail queue is headed by a pair of pointers, one to the 551556Srgrimes * head of the list and the other to the tail of the list. The elements are 561556Srgrimes * singly linked for minimum space and pointer manipulation overhead at the 571556Srgrimes * expense of O(n) removal for arbitrary elements. New elements can be added 581556Srgrimes * to the list after an existing element, at the head of the list, or at the 591556Srgrimes * end of the list. Elements being removed from the head of the tail queue 601556Srgrimes * should use the explicit macro for this purpose for optimum efficiency. 611556Srgrimes * A singly-linked tail queue may only be traversed in the forward direction. 621556Srgrimes * Singly-linked tail queues are ideal for applications with large datasets 631556Srgrimes * and few or no removals or for implementing a FIFO queue. 641556Srgrimes * 6569321Sjkh * A list is headed by a single forward pointer (or an array of forward 661556Srgrimes * pointers for a hash table header). The elements are doubly linked 671556Srgrimes * so that an arbitrary element can be removed without a need to 681556Srgrimes * traverse the list. New elements can be added to the list before 691556Srgrimes * or after an existing element or at the head of the list. A list 701556Srgrimes * may only be traversed in the forward direction. 711556Srgrimes * 721556Srgrimes * A tail queue is headed by a pair of pointers, one to the head of the 731556Srgrimes * list and the other to the tail of the list. The elements are doubly 741556Srgrimes * linked so that an arbitrary element can be removed without a need to 751556Srgrimes * traverse the list. New elements can be added to the list before or 761556Srgrimes * after an existing element, at the head of the list, or at the end of 771556Srgrimes * the list. A tail queue may only be traversed in the forward direction. 7876810Skris * 791556Srgrimes * A circle queue is headed by a pair of pointers, one to the head of the 801556Srgrimes * list and the other to the tail of the list. The elements are doubly 811556Srgrimes * linked so that an arbitrary element can be removed without a need to 821556Srgrimes * traverse the list. New elements can be added to the list before or after 831556Srgrimes * an existing element, at the head of the list, or at the end of the list. 841556Srgrimes * A circle queue may be traversed in either direction, but has a more 8576810Skris * complex end of list detection. 861556Srgrimes * 871556Srgrimes * For details on the use of these macros, see the queue(3) manual page. 881556Srgrimes * 8990111Simp * 901556Srgrimes * SLIST LIST STAILQ TAILQ CIRCLEQ 911556Srgrimes * _HEAD + + + + + 9276810Skris * _ENTRY + + + + + 931556Srgrimes * _INIT + + + + + 941556Srgrimes * _EMPTY + + + + + 951556Srgrimes * _FIRST + + - + + 9690111Simp * _NEXT + + - + + 971556Srgrimes * _PREV - - - + + 981556Srgrimes * _LAST - - - + + 991556Srgrimes * _FOREACH - + - + - 1001556Srgrimes * _INSERT_HEAD + + + + + 1018855Srgrimes * _INSERT_BEFORE - + - + + 1021556Srgrimes * _INSERT_AFTER + + + + + 1031556Srgrimes * _INSERT_TAIL - - + + + 1041556Srgrimes * _REMOVE_HEAD + - + - - 1051556Srgrimes * _REMOVE + + + + + 1061556Srgrimes * 1078148Sache */ 1088148Sache 1091556Srgrimes/* 1101556Srgrimes * Singly-linked List definitions. 1111556Srgrimes */ 1121556Srgrimes#define SLIST_HEAD(name, type) \ 1131556Srgrimesstruct name { \ 1141556Srgrimes struct type *slh_first; /* first element */ \ 1151556Srgrimes} 1161556Srgrimes 1171556Srgrimes#define SLIST_ENTRY(type) \ 1181556Srgrimesstruct { \ 1191556Srgrimes struct type *sle_next; /* next element */ \ 1201556Srgrimes} 1211556Srgrimes 1221556Srgrimes/* 1231556Srgrimes * Singly-linked List functions. 1241556Srgrimes */ 1251556Srgrimes#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 1261556Srgrimes 1271556Srgrimes#define SLIST_FIRST(head) ((head)->slh_first) 1281556Srgrimes 1291556Srgrimes#define SLIST_INIT(head) { \ 1301556Srgrimes (head)->slh_first = NULL; \ 1311556Srgrimes} 1321556Srgrimes 1331556Srgrimes#define SLIST_INSERT_AFTER(slistelm, elm, field) { \ 1341556Srgrimes (elm)->field.sle_next = (slistelm)->field.sle_next; \ 1351556Srgrimes (slistelm)->field.sle_next = (elm); \ 1361556Srgrimes} 1371556Srgrimes 1381556Srgrimes#define SLIST_INSERT_HEAD(head, elm, field) { \ 1391556Srgrimes (elm)->field.sle_next = (head)->slh_first; \ 1401556Srgrimes (head)->slh_first = (elm); \ 141} 142 143#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 144 145#define SLIST_REMOVE_HEAD(head, field) { \ 146 (head)->slh_first = (head)->slh_first->field.sle_next; \ 147} 148 149#define SLIST_REMOVE(head, elm, type, field) { \ 150 if ((head)->slh_first == (elm)) { \ 151 SLIST_REMOVE_HEAD((head), field); \ 152 } \ 153 else { \ 154 struct type *curelm = (head)->slh_first; \ 155 while( curelm->field.sle_next != (elm) ) \ 156 curelm = curelm->field.sle_next; \ 157 curelm->field.sle_next = \ 158 curelm->field.sle_next->field.sle_next; \ 159 } \ 160} 161 162/* 163 * Singly-linked Tail queue definitions. 164 */ 165#define STAILQ_HEAD(name, type) \ 166struct name { \ 167 struct type *stqh_first;/* first element */ \ 168 struct type **stqh_last;/* addr of last next element */ \ 169} 170 171#define STAILQ_ENTRY(type) \ 172struct { \ 173 struct type *stqe_next; /* next element */ \ 174} 175 176/* 177 * Singly-linked Tail queue functions. 178 */ 179#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 180 181#define STAILQ_INIT(head) { \ 182 (head)->stqh_first = NULL; \ 183 (head)->stqh_last = &(head)->stqh_first; \ 184} 185 186#define STAILQ_INSERT_HEAD(head, elm, field) { \ 187 if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \ 188 (head)->stqh_last = &(elm)->field.stqe_next; \ 189 (head)->stqh_first = (elm); \ 190} 191 192#define STAILQ_INSERT_TAIL(head, elm, field) { \ 193 (elm)->field.stqe_next = NULL; \ 194 *(head)->stqh_last = (elm); \ 195 (head)->stqh_last = &(elm)->field.stqe_next; \ 196} 197 198#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) { \ 199 if (((elm)->field.stqe_next = (tqelm)->field.stqe_next) == NULL)\ 200 (head)->stqh_last = &(elm)->field.stqe_next; \ 201 (tqelm)->field.stqe_next = (elm); \ 202} 203 204#define STAILQ_REMOVE_HEAD(head, field) { \ 205 if (((head)->stqh_first = \ 206 (head)->stqh_first->field.stqe_next) == NULL) \ 207 (head)->stqh_last = &(head)->stqh_first; \ 208} 209 210#define STAILQ_REMOVE(head, elm, type, field) { \ 211 if ((head)->stqh_first == (elm)) { \ 212 STAILQ_REMOVE_HEAD(head, field); \ 213 } \ 214 else { \ 215 struct type *curelm = (head)->stqh_first; \ 216 while( curelm->field.stqe_next != (elm) ) \ 217 curelm = curelm->field.stqe_next; \ 218 if((curelm->field.stqe_next = \ 219 curelm->field.stqe_next->field.stqe_next) == NULL) \ 220 (head)->stqh_last = &(curelm)->field.stqe_next; \ 221 } \ 222} 223 224/* 225 * List definitions. 226 */ 227#define LIST_HEAD(name, type) \ 228struct name { \ 229 struct type *lh_first; /* first element */ \ 230} 231 232#define LIST_ENTRY(type) \ 233struct { \ 234 struct type *le_next; /* next element */ \ 235 struct type **le_prev; /* address of previous next element */ \ 236} 237 238/* 239 * List functions. 240 */ 241 242#define LIST_EMPTY(head) ((head)->lh_first == NULL) 243 244#define LIST_FIRST(head) ((head)->lh_first) 245 246#define LIST_FOREACH(var, head, field) \ 247 for((var) = (head)->lh_first; (var); (var) = (var)->field.le_next) 248 249#define LIST_INIT(head) { \ 250 (head)->lh_first = NULL; \ 251} 252 253#define LIST_INSERT_AFTER(listelm, elm, field) { \ 254 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 255 (listelm)->field.le_next->field.le_prev = \ 256 &(elm)->field.le_next; \ 257 (listelm)->field.le_next = (elm); \ 258 (elm)->field.le_prev = &(listelm)->field.le_next; \ 259} 260 261#define LIST_INSERT_BEFORE(listelm, elm, field) { \ 262 (elm)->field.le_prev = (listelm)->field.le_prev; \ 263 (elm)->field.le_next = (listelm); \ 264 *(listelm)->field.le_prev = (elm); \ 265 (listelm)->field.le_prev = &(elm)->field.le_next; \ 266} 267 268#define LIST_INSERT_HEAD(head, elm, field) { \ 269 if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 270 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 271 (head)->lh_first = (elm); \ 272 (elm)->field.le_prev = &(head)->lh_first; \ 273} 274 275#define LIST_NEXT(elm, field) ((elm)->field.le_next) 276 277#define LIST_REMOVE(elm, field) { \ 278 if ((elm)->field.le_next != NULL) \ 279 (elm)->field.le_next->field.le_prev = \ 280 (elm)->field.le_prev; \ 281 *(elm)->field.le_prev = (elm)->field.le_next; \ 282} 283 284/* 285 * Tail queue definitions. 286 */ 287#define TAILQ_HEAD(name, type) \ 288struct name { \ 289 struct type *tqh_first; /* first element */ \ 290 struct type **tqh_last; /* addr of last next element */ \ 291} 292 293#define TAILQ_ENTRY(type) \ 294struct { \ 295 struct type *tqe_next; /* next element */ \ 296 struct type **tqe_prev; /* address of previous next element */ \ 297} 298 299/* 300 * Tail queue functions. 301 */ 302#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 303 304#define TAILQ_FOREACH(var, head, field) \ 305 for (var = TAILQ_FIRST(head); var; var = TAILQ_NEXT(var, field)) 306 307#define TAILQ_FIRST(head) ((head)->tqh_first) 308 309#define TAILQ_LAST(head) ((head)->tqh_last) 310 311#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 312 313#define TAILQ_PREV(elm, field) ((elm)->field.tqe_prev) 314 315#define TAILQ_INIT(head) { \ 316 (head)->tqh_first = NULL; \ 317 (head)->tqh_last = &(head)->tqh_first; \ 318} 319 320#define TAILQ_INSERT_HEAD(head, elm, field) { \ 321 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 322 (head)->tqh_first->field.tqe_prev = \ 323 &(elm)->field.tqe_next; \ 324 else \ 325 (head)->tqh_last = &(elm)->field.tqe_next; \ 326 (head)->tqh_first = (elm); \ 327 (elm)->field.tqe_prev = &(head)->tqh_first; \ 328} 329 330#define TAILQ_INSERT_TAIL(head, elm, field) { \ 331 (elm)->field.tqe_next = NULL; \ 332 (elm)->field.tqe_prev = (head)->tqh_last; \ 333 *(head)->tqh_last = (elm); \ 334 (head)->tqh_last = &(elm)->field.tqe_next; \ 335} 336 337#define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \ 338 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 339 (elm)->field.tqe_next->field.tqe_prev = \ 340 &(elm)->field.tqe_next; \ 341 else \ 342 (head)->tqh_last = &(elm)->field.tqe_next; \ 343 (listelm)->field.tqe_next = (elm); \ 344 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 345} 346 347#define TAILQ_INSERT_BEFORE(listelm, elm, field) { \ 348 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 349 (elm)->field.tqe_next = (listelm); \ 350 *(listelm)->field.tqe_prev = (elm); \ 351 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 352} 353 354#define TAILQ_REMOVE(head, elm, field) { \ 355 if (((elm)->field.tqe_next) != NULL) \ 356 (elm)->field.tqe_next->field.tqe_prev = \ 357 (elm)->field.tqe_prev; \ 358 else \ 359 (head)->tqh_last = (elm)->field.tqe_prev; \ 360 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 361} 362 363/* 364 * Circular queue definitions. 365 */ 366#define CIRCLEQ_HEAD(name, type) \ 367struct name { \ 368 struct type *cqh_first; /* first element */ \ 369 struct type *cqh_last; /* last element */ \ 370} 371 372#define CIRCLEQ_ENTRY(type) \ 373struct { \ 374 struct type *cqe_next; /* next element */ \ 375 struct type *cqe_prev; /* previous element */ \ 376} 377 378/* 379 * Circular queue functions. 380 */ 381#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (head)->cqh_last) 382 383#define CIRCLEQ_FIRST(head) ((head)->cqh_first) 384 385#define CIRCLEQ_FOREACH(var, head, field) \ 386 for((var) = (head)->cqh_first; (var); (var) = (var)->field.cqe_next) 387 388#define CIRCLEQ_INIT(head) { \ 389 (head)->cqh_first = (void *)(head); \ 390 (head)->cqh_last = (void *)(head); \ 391} 392 393#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \ 394 (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 395 (elm)->field.cqe_prev = (listelm); \ 396 if ((listelm)->field.cqe_next == (void *)(head)) \ 397 (head)->cqh_last = (elm); \ 398 else \ 399 (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 400 (listelm)->field.cqe_next = (elm); \ 401} 402 403#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \ 404 (elm)->field.cqe_next = (listelm); \ 405 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 406 if ((listelm)->field.cqe_prev == (void *)(head)) \ 407 (head)->cqh_first = (elm); \ 408 else \ 409 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 410 (listelm)->field.cqe_prev = (elm); \ 411} 412 413#define CIRCLEQ_INSERT_HEAD(head, elm, field) { \ 414 (elm)->field.cqe_next = (head)->cqh_first; \ 415 (elm)->field.cqe_prev = (void *)(head); \ 416 if ((head)->cqh_last == (void *)(head)) \ 417 (head)->cqh_last = (elm); \ 418 else \ 419 (head)->cqh_first->field.cqe_prev = (elm); \ 420 (head)->cqh_first = (elm); \ 421} 422 423#define CIRCLEQ_INSERT_TAIL(head, elm, field) { \ 424 (elm)->field.cqe_next = (void *)(head); \ 425 (elm)->field.cqe_prev = (head)->cqh_last; \ 426 if ((head)->cqh_first == (void *)(head)) \ 427 (head)->cqh_first = (elm); \ 428 else \ 429 (head)->cqh_last->field.cqe_next = (elm); \ 430 (head)->cqh_last = (elm); \ 431} 432 433#define CIRCLEQ_LAST(head) ((head)->cqh_last) 434 435#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next) 436 437#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev) 438 439#define CIRCLEQ_REMOVE(head, elm, field) { \ 440 if ((elm)->field.cqe_next == (void *)(head)) \ 441 (head)->cqh_last = (elm)->field.cqe_prev; \ 442 else \ 443 (elm)->field.cqe_next->field.cqe_prev = \ 444 (elm)->field.cqe_prev; \ 445 if ((elm)->field.cqe_prev == (void *)(head)) \ 446 (head)->cqh_first = (elm)->field.cqe_next; \ 447 else \ 448 (elm)->field.cqe_prev->field.cqe_next = \ 449 (elm)->field.cqe_next; \ 450} 451 452#ifdef KERNEL 453 454/* 455 * XXX insque() and remque() are an old way of handling certain queues. 456 * They bogusly assumes that all queue heads look alike. 457 */ 458 459struct quehead { 460 struct quehead *qh_link; 461 struct quehead *qh_rlink; 462}; 463 464#ifdef __GNUC__ 465 466static __inline void 467insque(void *a, void *b) 468{ 469 struct quehead *element = a, *head = b; 470 471 element->qh_link = head->qh_link; 472 element->qh_rlink = head; 473 head->qh_link = element; 474 element->qh_link->qh_rlink = element; 475} 476 477static __inline void 478remque(void *a) 479{ 480 struct quehead *element = a; 481 482 element->qh_link->qh_rlink = element->qh_rlink; 483 element->qh_rlink->qh_link = element->qh_link; 484 element->qh_rlink = 0; 485} 486 487#else /* !__GNUC__ */ 488 489void insque __P((void *a, void *b)); 490void remque __P((void *a)); 491 492#endif /* __GNUC__ */ 493 494#endif /* KERNEL */ 495 496#endif /* !_SYS_QUEUE_H_ */ 497