1 /* $NetBSD: queue.h,v 1.39 2004/04/18 14:25:34 lukem Exp $ */ 2 3 /* 4 * Copyright (c) 1991, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. Neither the name of the University nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 * 31 * @(#)queue.h 8.5 (Berkeley) 8/20/94 32 */ 33 34 #ifndef _SYS_QUEUE_H_ 35 #define _SYS_QUEUE_H_ 36 37 /* 38 * This file defines five types of data structures: singly-linked lists, 39 * lists, simple queues, tail queues, and circular queues. 40 * 41 * A singly-linked list is headed by a single forward pointer. The 42 * elements are singly linked for minimum space and pointer manipulation 43 * overhead at the expense of O(n) removal for arbitrary elements. New 44 * elements can be added to the list after an existing element or at the 45 * head of the list. Elements being removed from the head of the list 46 * should use the explicit macro for this purpose for optimum 47 * efficiency. A singly-linked list may only be traversed in the forward 48 * direction. Singly-linked lists are ideal for applications with large 49 * datasets and few or no removals or for implementing a LIFO queue. 50 * 51 * A list is headed by a single forward pointer (or an array of forward 52 * pointers for a hash table header). The elements are doubly linked 53 * so that an arbitrary element can be removed without a need to 54 * traverse the list. New elements can be added to the list before 55 * or after an existing element or at the head of the list. A list 56 * may only be traversed in the forward direction. 57 * 58 * A simple queue is headed by a pair of pointers, one the head of the 59 * list and the other to the tail of the list. The elements are singly 60 * linked to save space, so only elements can only be removed from the 61 * head of the list. New elements can be added to the list after 62 * an existing element, at the head of the list, or at the end of the 63 * list. A simple queue may only be traversed in the forward direction. 64 * 65 * A tail queue is headed by a pair of pointers, one to the head of the 66 * list and the other to the tail of the list. The elements are doubly 67 * linked so that an arbitrary element can be removed without a need to 68 * traverse the list. New elements can be added to the list before or 69 * after an existing element, at the head of the list, or at the end of 70 * the list. A tail queue may be traversed in either direction. 71 * 72 * A circle queue is headed by a pair of pointers, one to the head of the 73 * list and the other to the tail of the list. The elements are doubly 74 * linked so that an arbitrary element can be removed without a need to 75 * traverse the list. New elements can be added to the list before or after 76 * an existing element, at the head of the list, or at the end of the list. 77 * A circle queue may be traversed in either direction, but has a more 78 * complex end of list detection. 79 * 80 * For details on the use of these macros, see the queue(3) manual page. 81 */ 82 83 /* 84 * List definitions. 85 */ 86 #define LIST_HEAD(name, type) \ 87 struct name { \ 88 struct type *lh_first; /* first element */ \ 89 } 90 91 #define LIST_HEAD_INITIALIZER(head) \ 92 { NULL } 93 94 #define LIST_ENTRY(type) \ 95 struct { \ 96 struct type *le_next; /* next element */ \ 97 struct type **le_prev; /* address of previous next element */ \ 98 } 99 100 /* 101 * List functions. 102 */ 103 #if defined(_KERNEL) && defined(QUEUEDEBUG) 104 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) \ 105 if ((head)->lh_first && \ 106 (head)->lh_first->field.le_prev != &(head)->lh_first) \ 107 panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__); 108 #define QUEUEDEBUG_LIST_OP(elm, field) \ 109 if ((elm)->field.le_next && \ 110 (elm)->field.le_next->field.le_prev != \ 111 &(elm)->field.le_next) \ 112 panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\ 113 if (*(elm)->field.le_prev != (elm)) \ 114 panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__); 115 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) \ 116 (elm)->field.le_next = (void *)1L; \ 117 (elm)->field.le_prev = (void *)1L; 118 #else 119 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) 120 #define QUEUEDEBUG_LIST_OP(elm, field) 121 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) 122 #endif 123 124 #define LIST_INIT(head) do { \ 125 (head)->lh_first = NULL; \ 126 } while (/*CONSTCOND*/0) 127 128 #define LIST_INSERT_AFTER(listelm, elm, field) do { \ 129 QUEUEDEBUG_LIST_OP((listelm), field) \ 130 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 131 (listelm)->field.le_next->field.le_prev = \ 132 &(elm)->field.le_next; \ 133 (listelm)->field.le_next = (elm); \ 134 (elm)->field.le_prev = &(listelm)->field.le_next; \ 135 } while (/*CONSTCOND*/0) 136 137 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 138 QUEUEDEBUG_LIST_OP((listelm), field) \ 139 (elm)->field.le_prev = (listelm)->field.le_prev; \ 140 (elm)->field.le_next = (listelm); \ 141 *(listelm)->field.le_prev = (elm); \ 142 (listelm)->field.le_prev = &(elm)->field.le_next; \ 143 } while (/*CONSTCOND*/0) 144 145 #define LIST_INSERT_HEAD(head, elm, field) do { \ 146 QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field) \ 147 if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 148 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 149 (head)->lh_first = (elm); \ 150 (elm)->field.le_prev = &(head)->lh_first; \ 151 } while (/*CONSTCOND*/0) 152 153 #define LIST_REMOVE(elm, field) do { \ 154 QUEUEDEBUG_LIST_OP((elm), field) \ 155 if ((elm)->field.le_next != NULL) \ 156 (elm)->field.le_next->field.le_prev = \ 157 (elm)->field.le_prev; \ 158 *(elm)->field.le_prev = (elm)->field.le_next; \ 159 QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \ 160 } while (/*CONSTCOND*/0) 161 162 #define LIST_FOREACH(var, head, field) \ 163 for ((var) = ((head)->lh_first); \ 164 (var); \ 165 (var) = ((var)->field.le_next)) 166 167 /* 168 * List access methods. 169 */ 170 #define LIST_EMPTY(head) ((head)->lh_first == NULL) 171 #define LIST_FIRST(head) ((head)->lh_first) 172 #define LIST_NEXT(elm, field) ((elm)->field.le_next) 173 174 175 /* 176 * Singly-linked List definitions. 177 */ 178 #define SLIST_HEAD(name, type) \ 179 struct name { \ 180 struct type *slh_first; /* first element */ \ 181 } 182 183 #define SLIST_HEAD_INITIALIZER(head) \ 184 { NULL } 185 186 #define SLIST_ENTRY(type) \ 187 struct { \ 188 struct type *sle_next; /* next element */ \ 189 } 190 191 /* 192 * Singly-linked List functions. 193 */ 194 #define SLIST_INIT(head) do { \ 195 (head)->slh_first = NULL; \ 196 } while (/*CONSTCOND*/0) 197 198 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 199 (elm)->field.sle_next = (slistelm)->field.sle_next; \ 200 (slistelm)->field.sle_next = (elm); \ 201 } while (/*CONSTCOND*/0) 202 203 #define SLIST_INSERT_HEAD(head, elm, field) do { \ 204 (elm)->field.sle_next = (head)->slh_first; \ 205 (head)->slh_first = (elm); \ 206 } while (/*CONSTCOND*/0) 207 208 #define SLIST_REMOVE_HEAD(head, field) do { \ 209 (head)->slh_first = (head)->slh_first->field.sle_next; \ 210 } while (/*CONSTCOND*/0) 211 212 #define SLIST_REMOVE(head, elm, type, field) do { \ 213 if ((head)->slh_first == (elm)) { \ 214 SLIST_REMOVE_HEAD((head), field); \ 215 } \ 216 else { \ 217 struct type *curelm = (head)->slh_first; \ 218 while(curelm->field.sle_next != (elm)) \ 219 curelm = curelm->field.sle_next; \ 220 curelm->field.sle_next = \ 221 curelm->field.sle_next->field.sle_next; \ 222 } \ 223 } while (/*CONSTCOND*/0) 224 225 #define SLIST_FOREACH(var, head, field) \ 226 for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next) 227 228 /* 229 * Singly-linked List access methods. 230 */ 231 #define SLIST_EMPTY(head) ((head)->slh_first == NULL) 232 #define SLIST_FIRST(head) ((head)->slh_first) 233 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 234 235 236 /* 237 * Singly-linked Tail queue declarations. 238 */ 239 #define STAILQ_HEAD(name, type) \ 240 struct name { \ 241 struct type *stqh_first; /* first element */ \ 242 struct type **stqh_last; /* addr of last next element */ \ 243 } 244 245 #define STAILQ_HEAD_INITIALIZER(head) \ 246 { NULL, &(head).stqh_first } 247 248 #define STAILQ_ENTRY(type) \ 249 struct { \ 250 struct type *stqe_next; /* next element */ \ 251 } 252 253 /* 254 * Singly-linked Tail queue functions. 255 */ 256 #define STAILQ_INIT(head) do { \ 257 (head)->stqh_first = NULL; \ 258 (head)->stqh_last = &(head)->stqh_first; \ 259 } while (/*CONSTCOND*/0) 260 261 #define STAILQ_INSERT_HEAD(head, elm, field) do { \ 262 if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \ 263 (head)->stqh_last = &(elm)->field.stqe_next; \ 264 (head)->stqh_first = (elm); \ 265 } while (/*CONSTCOND*/0) 266 267 #define STAILQ_INSERT_TAIL(head, elm, field) do { \ 268 (elm)->field.stqe_next = NULL; \ 269 *(head)->stqh_last = (elm); \ 270 (head)->stqh_last = &(elm)->field.stqe_next; \ 271 } while (/*CONSTCOND*/0) 272 273 #define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 274 if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\ 275 (head)->stqh_last = &(elm)->field.stqe_next; \ 276 (listelm)->field.stqe_next = (elm); \ 277 } while (/*CONSTCOND*/0) 278 279 #define STAILQ_REMOVE_HEAD(head, field) do { \ 280 if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \ 281 (head)->stqh_last = &(head)->stqh_first; \ 282 } while (/*CONSTCOND*/0) 283 284 #define STAILQ_REMOVE(head, elm, type, field) do { \ 285 if ((head)->stqh_first == (elm)) { \ 286 STAILQ_REMOVE_HEAD((head), field); \ 287 } else { \ 288 struct type *curelm = (head)->stqh_first; \ 289 while (curelm->field.stqe_next != (elm)) \ 290 curelm = curelm->field.stqe_next; \ 291 if ((curelm->field.stqe_next = \ 292 curelm->field.stqe_next->field.stqe_next) == NULL) \ 293 (head)->stqh_last = &(curelm)->field.stqe_next; \ 294 } \ 295 } while (/*CONSTCOND*/0) 296 297 #define STAILQ_FOREACH(var, head, field) \ 298 for ((var) = ((head)->stqh_first); \ 299 (var); \ 300 (var) = ((var)->field.stqe_next)) 301 302 /* 303 * Singly-linked Tail queue access methods. 304 */ 305 #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 306 #define STAILQ_FIRST(head) ((head)->stqh_first) 307 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 308 309 310 /* 311 * Simple queue definitions. 312 */ 313 #define SIMPLEQ_HEAD(name, type) \ 314 struct name { \ 315 struct type *sqh_first; /* first element */ \ 316 struct type **sqh_last; /* addr of last next element */ \ 317 } 318 319 #define SIMPLEQ_HEAD_INITIALIZER(head) \ 320 { NULL, &(head).sqh_first } 321 322 #define SIMPLEQ_ENTRY(type) \ 323 struct { \ 324 struct type *sqe_next; /* next element */ \ 325 } 326 327 /* 328 * Simple queue functions. 329 */ 330 #define SIMPLEQ_INIT(head) do { \ 331 (head)->sqh_first = NULL; \ 332 (head)->sqh_last = &(head)->sqh_first; \ 333 } while (/*CONSTCOND*/0) 334 335 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ 336 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ 337 (head)->sqh_last = &(elm)->field.sqe_next; \ 338 (head)->sqh_first = (elm); \ 339 } while (/*CONSTCOND*/0) 340 341 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ 342 (elm)->field.sqe_next = NULL; \ 343 *(head)->sqh_last = (elm); \ 344 (head)->sqh_last = &(elm)->field.sqe_next; \ 345 } while (/*CONSTCOND*/0) 346 347 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 348 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ 349 (head)->sqh_last = &(elm)->field.sqe_next; \ 350 (listelm)->field.sqe_next = (elm); \ 351 } while (/*CONSTCOND*/0) 352 353 #define SIMPLEQ_REMOVE_HEAD(head, field) do { \ 354 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ 355 (head)->sqh_last = &(head)->sqh_first; \ 356 } while (/*CONSTCOND*/0) 357 358 #define SIMPLEQ_REMOVE(head, elm, type, field) do { \ 359 if ((head)->sqh_first == (elm)) { \ 360 SIMPLEQ_REMOVE_HEAD((head), field); \ 361 } else { \ 362 struct type *curelm = (head)->sqh_first; \ 363 while (curelm->field.sqe_next != (elm)) \ 364 curelm = curelm->field.sqe_next; \ 365 if ((curelm->field.sqe_next = \ 366 curelm->field.sqe_next->field.sqe_next) == NULL) \ 367 (head)->sqh_last = &(curelm)->field.sqe_next; \ 368 } \ 369 } while (/*CONSTCOND*/0) 370 371 #define SIMPLEQ_FOREACH(var, head, field) \ 372 for ((var) = ((head)->sqh_first); \ 373 (var); \ 374 (var) = ((var)->field.sqe_next)) 375 376 /* 377 * Simple queue access methods. 378 */ 379 #define SIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL) 380 #define SIMPLEQ_FIRST(head) ((head)->sqh_first) 381 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) 382 383 384 /* 385 * Tail queue definitions. 386 */ 387 #define TAILQ_HEAD(name, type) \ 388 struct name { \ 389 struct type *tqh_first; /* first element */ \ 390 struct type **tqh_last; /* addr of last next element */ \ 391 } 392 393 #define TAILQ_HEAD_INITIALIZER(head) \ 394 { NULL, &(head).tqh_first } 395 396 #define TAILQ_ENTRY(type) \ 397 struct { \ 398 struct type *tqe_next; /* next element */ \ 399 struct type **tqe_prev; /* address of previous next element */ \ 400 } 401 402 /* 403 * Tail queue functions. 404 */ 405 #if defined(_KERNEL) && defined(QUEUEDEBUG) 406 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) \ 407 if ((head)->tqh_first && \ 408 (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \ 409 panic("TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__); 410 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) \ 411 if (*(head)->tqh_last != NULL) \ 412 panic("TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__); 413 #define QUEUEDEBUG_TAILQ_OP(elm, field) \ 414 if ((elm)->field.tqe_next && \ 415 (elm)->field.tqe_next->field.tqe_prev != \ 416 &(elm)->field.tqe_next) \ 417 panic("TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\ 418 if (*(elm)->field.tqe_prev != (elm)) \ 419 panic("TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__); 420 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) \ 421 if ((elm)->field.tqe_next == NULL && \ 422 (head)->tqh_last != &(elm)->field.tqe_next) \ 423 panic("TAILQ_PREREMOVE head %p elm %p %s:%d", \ 424 (head), (elm), __FILE__, __LINE__); 425 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) \ 426 (elm)->field.tqe_next = (void *)1L; \ 427 (elm)->field.tqe_prev = (void *)1L; 428 #else 429 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) 430 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) 431 #define QUEUEDEBUG_TAILQ_OP(elm, field) 432 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) 433 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) 434 #endif 435 436 #define TAILQ_INIT(head) do { \ 437 (head)->tqh_first = NULL; \ 438 (head)->tqh_last = &(head)->tqh_first; \ 439 } while (/*CONSTCOND*/0) 440 441 #define TAILQ_INSERT_HEAD(head, elm, field) do { \ 442 QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field) \ 443 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 444 (head)->tqh_first->field.tqe_prev = \ 445 &(elm)->field.tqe_next; \ 446 else \ 447 (head)->tqh_last = &(elm)->field.tqe_next; \ 448 (head)->tqh_first = (elm); \ 449 (elm)->field.tqe_prev = &(head)->tqh_first; \ 450 } while (/*CONSTCOND*/0) 451 452 #define TAILQ_INSERT_TAIL(head, elm, field) do { \ 453 QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field) \ 454 (elm)->field.tqe_next = NULL; \ 455 (elm)->field.tqe_prev = (head)->tqh_last; \ 456 *(head)->tqh_last = (elm); \ 457 (head)->tqh_last = &(elm)->field.tqe_next; \ 458 } while (/*CONSTCOND*/0) 459 460 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 461 QUEUEDEBUG_TAILQ_OP((listelm), field) \ 462 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 463 (elm)->field.tqe_next->field.tqe_prev = \ 464 &(elm)->field.tqe_next; \ 465 else \ 466 (head)->tqh_last = &(elm)->field.tqe_next; \ 467 (listelm)->field.tqe_next = (elm); \ 468 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 469 } while (/*CONSTCOND*/0) 470 471 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 472 QUEUEDEBUG_TAILQ_OP((listelm), field) \ 473 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 474 (elm)->field.tqe_next = (listelm); \ 475 *(listelm)->field.tqe_prev = (elm); \ 476 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 477 } while (/*CONSTCOND*/0) 478 479 #define TAILQ_REMOVE(head, elm, field) do { \ 480 QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field) \ 481 QUEUEDEBUG_TAILQ_OP((elm), field) \ 482 if (((elm)->field.tqe_next) != NULL) \ 483 (elm)->field.tqe_next->field.tqe_prev = \ 484 (elm)->field.tqe_prev; \ 485 else \ 486 (head)->tqh_last = (elm)->field.tqe_prev; \ 487 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 488 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \ 489 } while (/*CONSTCOND*/0) 490 491 #define TAILQ_FOREACH(var, head, field) \ 492 for ((var) = ((head)->tqh_first); \ 493 (var); \ 494 (var) = ((var)->field.tqe_next)) 495 496 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 497 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \ 498 (var); \ 499 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last))) 500 501 /* 502 * Tail queue access methods. 503 */ 504 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 505 #define TAILQ_FIRST(head) ((head)->tqh_first) 506 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 507 508 #define TAILQ_LAST(head, headname) \ 509 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 510 #define TAILQ_PREV(elm, headname, field) \ 511 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 512 513 514 /* 515 * Circular queue definitions. 516 */ 517 #define CIRCLEQ_HEAD(name, type) \ 518 struct name { \ 519 struct type *cqh_first; /* first element */ \ 520 struct type *cqh_last; /* last element */ \ 521 } 522 523 #define CIRCLEQ_HEAD_INITIALIZER(head) \ 524 { (void *)&head, (void *)&head } 525 526 #define CIRCLEQ_ENTRY(type) \ 527 struct { \ 528 struct type *cqe_next; /* next element */ \ 529 struct type *cqe_prev; /* previous element */ \ 530 } 531 532 /* 533 * Circular queue functions. 534 */ 535 #define CIRCLEQ_INIT(head) do { \ 536 (head)->cqh_first = (void *)(head); \ 537 (head)->cqh_last = (void *)(head); \ 538 } while (/*CONSTCOND*/0) 539 540 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 541 (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 542 (elm)->field.cqe_prev = (listelm); \ 543 if ((listelm)->field.cqe_next == (void *)(head)) \ 544 (head)->cqh_last = (elm); \ 545 else \ 546 (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 547 (listelm)->field.cqe_next = (elm); \ 548 } while (/*CONSTCOND*/0) 549 550 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ 551 (elm)->field.cqe_next = (listelm); \ 552 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 553 if ((listelm)->field.cqe_prev == (void *)(head)) \ 554 (head)->cqh_first = (elm); \ 555 else \ 556 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 557 (listelm)->field.cqe_prev = (elm); \ 558 } while (/*CONSTCOND*/0) 559 560 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ 561 (elm)->field.cqe_next = (head)->cqh_first; \ 562 (elm)->field.cqe_prev = (void *)(head); \ 563 if ((head)->cqh_last == (void *)(head)) \ 564 (head)->cqh_last = (elm); \ 565 else \ 566 (head)->cqh_first->field.cqe_prev = (elm); \ 567 (head)->cqh_first = (elm); \ 568 } while (/*CONSTCOND*/0) 569 570 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ 571 (elm)->field.cqe_next = (void *)(head); \ 572 (elm)->field.cqe_prev = (head)->cqh_last; \ 573 if ((head)->cqh_first == (void *)(head)) \ 574 (head)->cqh_first = (elm); \ 575 else \ 576 (head)->cqh_last->field.cqe_next = (elm); \ 577 (head)->cqh_last = (elm); \ 578 } while (/*CONSTCOND*/0) 579 580 #define CIRCLEQ_REMOVE(head, elm, field) do { \ 581 if ((elm)->field.cqe_next == (void *)(head)) \ 582 (head)->cqh_last = (elm)->field.cqe_prev; \ 583 else \ 584 (elm)->field.cqe_next->field.cqe_prev = \ 585 (elm)->field.cqe_prev; \ 586 if ((elm)->field.cqe_prev == (void *)(head)) \ 587 (head)->cqh_first = (elm)->field.cqe_next; \ 588 else \ 589 (elm)->field.cqe_prev->field.cqe_next = \ 590 (elm)->field.cqe_next; \ 591 } while (/*CONSTCOND*/0) 592 593 #define CIRCLEQ_FOREACH(var, head, field) \ 594 for ((var) = ((head)->cqh_first); \ 595 (var) != (void *)(head); \ 596 (var) = ((var)->field.cqe_next)) 597 598 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ 599 for ((var) = ((head)->cqh_last); \ 600 (var) != (void *)(head); \ 601 (var) = ((var)->field.cqe_prev)) 602 603 /* 604 * Circular queue access methods. 605 */ 606 #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head)) 607 #define CIRCLEQ_FIRST(head) ((head)->cqh_first) 608 #define CIRCLEQ_LAST(head) ((head)->cqh_last) 609 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) 610 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) 611 612 #endif /* !_SYS_QUEUE_H_ */ 613