1 /* 2 * This is a copy of NetBSD's sys/queue.h, edited to use a different symbol for 3 * multiple inclusion protection and to suppress the include of <sys/null.h>. 4 */ 5 6 /* $NetBSD: queue.h,v 1.53 2011/11/19 22:51:31 tls Exp $ */ 7 8 /* 9 * Copyright (c) 1991, 1993 10 * The Regents of the University of California. All rights reserved. 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions 14 * are met: 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 3. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * @(#)queue.h 8.5 (Berkeley) 8/20/94 37 */ 38 39 #ifndef K5_QUEUE_H 40 #define K5_QUEUE_H 41 42 /* #include <sys/null.h> */ 43 44 /* 45 * This file defines five types of data structures: singly-linked lists, 46 * lists, simple queues, tail queues, and circular queues. 47 * 48 * A singly-linked list is headed by a single forward pointer. The 49 * elements are singly linked for minimum space and pointer manipulation 50 * overhead at the expense of O(n) removal for arbitrary elements. New 51 * elements can be added to the list after an existing element or at the 52 * head of the list. Elements being removed from the head of the list 53 * should use the explicit macro for this purpose for optimum 54 * efficiency. A singly-linked list may only be traversed in the forward 55 * direction. Singly-linked lists are ideal for applications with large 56 * datasets and few or no removals or for implementing a LIFO queue. 57 * 58 * A list is headed by a single forward pointer (or an array of forward 59 * pointers for a hash table header). The elements are doubly linked 60 * so that an arbitrary element can be removed without a need to 61 * traverse the list. New elements can be added to the list before 62 * or after an existing element or at the head of the list. A list 63 * may only be traversed in the forward direction. 64 * 65 * A simple queue is headed by a pair of pointers, one the head of the 66 * list and the other to the tail of the list. The elements are singly 67 * linked to save space, so elements can only be removed from the 68 * head of the list. New elements can be added to the list after 69 * an existing element, at the head of the list, or at the end of the 70 * list. A simple queue may only be traversed in the forward direction. 71 * 72 * A tail 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 76 * after an existing element, at the head of the list, or at the end of 77 * the list. A tail queue may be traversed in either direction. 78 * 79 * A circle queue is headed by a pair of pointers, one to the head of the 80 * list and the other to the tail of the list. The elements are doubly 81 * linked so that an arbitrary element can be removed without a need to 82 * traverse the list. New elements can be added to the list before or after 83 * an existing element, at the head of the list, or at the end of the list. 84 * A circle queue may be traversed in either direction, but has a more 85 * complex end of list detection. 86 * 87 * For details on the use of these macros, see the queue(3) manual page. 88 */ 89 90 /* 91 * List definitions. 92 */ 93 #define K5_LIST_HEAD(name, type) \ 94 struct name { \ 95 struct type *lh_first; /* first element */ \ 96 } 97 98 #define K5_LIST_HEAD_INITIALIZER(head) \ 99 { NULL } 100 101 #define K5_LIST_ENTRY(type) \ 102 struct { \ 103 struct type *le_next; /* next element */ \ 104 struct type **le_prev; /* address of previous next element */ \ 105 } 106 107 /* 108 * List functions. 109 */ 110 #define K5_LIST_INIT(head) do { \ 111 (head)->lh_first = NULL; \ 112 } while (/*CONSTCOND*/0) 113 114 #define K5_LIST_INSERT_AFTER(listelm, elm, field) do { \ 115 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 116 (listelm)->field.le_next->field.le_prev = \ 117 &(elm)->field.le_next; \ 118 (listelm)->field.le_next = (elm); \ 119 (elm)->field.le_prev = &(listelm)->field.le_next; \ 120 } while (/*CONSTCOND*/0) 121 122 #define K5_LIST_INSERT_BEFORE(listelm, elm, field) do { \ 123 (elm)->field.le_prev = (listelm)->field.le_prev; \ 124 (elm)->field.le_next = (listelm); \ 125 *(listelm)->field.le_prev = (elm); \ 126 (listelm)->field.le_prev = &(elm)->field.le_next; \ 127 } while (/*CONSTCOND*/0) 128 129 #define K5_LIST_INSERT_HEAD(head, elm, field) do { \ 130 if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 131 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 132 (head)->lh_first = (elm); \ 133 (elm)->field.le_prev = &(head)->lh_first; \ 134 } while (/*CONSTCOND*/0) 135 136 #define K5_LIST_REMOVE(elm, field) do { \ 137 if ((elm)->field.le_next != NULL) \ 138 (elm)->field.le_next->field.le_prev = \ 139 (elm)->field.le_prev; \ 140 *(elm)->field.le_prev = (elm)->field.le_next; \ 141 } while (/*CONSTCOND*/0) 142 143 #define K5_LIST_FOREACH(var, head, field) \ 144 for ((var) = ((head)->lh_first); \ 145 (var); \ 146 (var) = ((var)->field.le_next)) 147 148 #define K5_LIST_FOREACH_SAFE(var, head, field, tvar) \ 149 for ((var) = K5_LIST_FIRST((head)); \ 150 (var) && ((tvar) = K5_LIST_NEXT((var), field), 1); \ 151 (var) = (tvar)) 152 /* 153 * List access methods. 154 */ 155 #define K5_LIST_EMPTY(head) ((head)->lh_first == NULL) 156 #define K5_LIST_FIRST(head) ((head)->lh_first) 157 #define K5_LIST_NEXT(elm, field) ((elm)->field.le_next) 158 159 160 /* 161 * Singly-linked List definitions. 162 */ 163 #define K5_SLIST_HEAD(name, type) \ 164 struct name { \ 165 struct type *slh_first; /* first element */ \ 166 } 167 168 #define K5_SLIST_HEAD_INITIALIZER(head) \ 169 { NULL } 170 171 #define K5_SLIST_ENTRY(type) \ 172 struct { \ 173 struct type *sle_next; /* next element */ \ 174 } 175 176 /* 177 * Singly-linked List functions. 178 */ 179 #define K5_SLIST_INIT(head) do { \ 180 (head)->slh_first = NULL; \ 181 } while (/*CONSTCOND*/0) 182 183 #define K5_SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 184 (elm)->field.sle_next = (slistelm)->field.sle_next; \ 185 (slistelm)->field.sle_next = (elm); \ 186 } while (/*CONSTCOND*/0) 187 188 #define K5_SLIST_INSERT_HEAD(head, elm, field) do { \ 189 (elm)->field.sle_next = (head)->slh_first; \ 190 (head)->slh_first = (elm); \ 191 } while (/*CONSTCOND*/0) 192 193 #define K5_SLIST_REMOVE_HEAD(head, field) do { \ 194 (head)->slh_first = (head)->slh_first->field.sle_next; \ 195 } while (/*CONSTCOND*/0) 196 197 #define K5_SLIST_REMOVE(head, elm, type, field) do { \ 198 if ((head)->slh_first == (elm)) { \ 199 K5_SLIST_REMOVE_HEAD((head), field); \ 200 } \ 201 else { \ 202 struct type *curelm = (head)->slh_first; \ 203 while(curelm->field.sle_next != (elm)) \ 204 curelm = curelm->field.sle_next; \ 205 curelm->field.sle_next = \ 206 curelm->field.sle_next->field.sle_next; \ 207 } \ 208 } while (/*CONSTCOND*/0) 209 210 #define K5_SLIST_REMOVE_AFTER(slistelm, field) do { \ 211 (slistelm)->field.sle_next = \ 212 K5_SLIST_NEXT(K5_SLIST_NEXT((slistelm), field), field); \ 213 } while (/*CONSTCOND*/0) 214 215 #define K5_SLIST_FOREACH(var, head, field) \ 216 for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next) 217 218 #define K5_SLIST_FOREACH_SAFE(var, head, field, tvar) \ 219 for ((var) = K5_SLIST_FIRST((head)); \ 220 (var) && ((tvar) = K5_SLIST_NEXT((var), field), 1); \ 221 (var) = (tvar)) 222 223 /* 224 * Singly-linked List access methods. 225 */ 226 #define K5_SLIST_EMPTY(head) ((head)->slh_first == NULL) 227 #define K5_SLIST_FIRST(head) ((head)->slh_first) 228 #define K5_SLIST_NEXT(elm, field) ((elm)->field.sle_next) 229 230 231 /* 232 * Singly-linked Tail queue declarations. 233 */ 234 #define K5_STAILQ_HEAD(name, type) \ 235 struct name { \ 236 struct type *stqh_first; /* first element */ \ 237 struct type **stqh_last; /* addr of last next element */ \ 238 } 239 240 #define K5_STAILQ_HEAD_INITIALIZER(head) \ 241 { NULL, &(head).stqh_first } 242 243 #define K5_STAILQ_ENTRY(type) \ 244 struct { \ 245 struct type *stqe_next; /* next element */ \ 246 } 247 248 /* 249 * Singly-linked Tail queue functions. 250 */ 251 #define K5_STAILQ_INIT(head) do { \ 252 (head)->stqh_first = NULL; \ 253 (head)->stqh_last = &(head)->stqh_first; \ 254 } while (/*CONSTCOND*/0) 255 256 #define K5_STAILQ_INSERT_HEAD(head, elm, field) do { \ 257 if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \ 258 (head)->stqh_last = &(elm)->field.stqe_next; \ 259 (head)->stqh_first = (elm); \ 260 } while (/*CONSTCOND*/0) 261 262 #define K5_STAILQ_INSERT_TAIL(head, elm, field) do { \ 263 (elm)->field.stqe_next = NULL; \ 264 *(head)->stqh_last = (elm); \ 265 (head)->stqh_last = &(elm)->field.stqe_next; \ 266 } while (/*CONSTCOND*/0) 267 268 #define K5_STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 269 if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\ 270 (head)->stqh_last = &(elm)->field.stqe_next; \ 271 (listelm)->field.stqe_next = (elm); \ 272 } while (/*CONSTCOND*/0) 273 274 #define K5_STAILQ_REMOVE_HEAD(head, field) do { \ 275 if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \ 276 (head)->stqh_last = &(head)->stqh_first; \ 277 } while (/*CONSTCOND*/0) 278 279 #define K5_STAILQ_REMOVE(head, elm, type, field) do { \ 280 if ((head)->stqh_first == (elm)) { \ 281 K5_STAILQ_REMOVE_HEAD((head), field); \ 282 } else { \ 283 struct type *curelm = (head)->stqh_first; \ 284 while (curelm->field.stqe_next != (elm)) \ 285 curelm = curelm->field.stqe_next; \ 286 if ((curelm->field.stqe_next = \ 287 curelm->field.stqe_next->field.stqe_next) == NULL) \ 288 (head)->stqh_last = &(curelm)->field.stqe_next; \ 289 } \ 290 } while (/*CONSTCOND*/0) 291 292 #define K5_STAILQ_FOREACH(var, head, field) \ 293 for ((var) = ((head)->stqh_first); \ 294 (var); \ 295 (var) = ((var)->field.stqe_next)) 296 297 #define K5_STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 298 for ((var) = K5_STAILQ_FIRST((head)); \ 299 (var) && ((tvar) = K5_STAILQ_NEXT((var), field), 1); \ 300 (var) = (tvar)) 301 302 #define K5_STAILQ_CONCAT(head1, head2) do { \ 303 if (!K5_STAILQ_EMPTY((head2))) { \ 304 *(head1)->stqh_last = (head2)->stqh_first; \ 305 (head1)->stqh_last = (head2)->stqh_last; \ 306 K5_STAILQ_INIT((head2)); \ 307 } \ 308 } while (/*CONSTCOND*/0) 309 310 #define K5_STAILQ_LAST(head, type, field) \ 311 (K5_STAILQ_EMPTY((head)) ? \ 312 NULL : \ 313 ((struct type *)(void *) \ 314 ((char *)((head)->stqh_last) - offsetof(struct type, field)))) 315 316 /* 317 * Singly-linked Tail queue access methods. 318 */ 319 #define K5_STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 320 #define K5_STAILQ_FIRST(head) ((head)->stqh_first) 321 #define K5_STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 322 323 324 /* 325 * Simple queue definitions. 326 */ 327 #define K5_SIMPLEQ_HEAD(name, type) \ 328 struct name { \ 329 struct type *sqh_first; /* first element */ \ 330 struct type **sqh_last; /* addr of last next element */ \ 331 } 332 333 #define K5_SIMPLEQ_HEAD_INITIALIZER(head) \ 334 { NULL, &(head).sqh_first } 335 336 #define K5_SIMPLEQ_ENTRY(type) \ 337 struct { \ 338 struct type *sqe_next; /* next element */ \ 339 } 340 341 /* 342 * Simple queue functions. 343 */ 344 #define K5_SIMPLEQ_INIT(head) do { \ 345 (head)->sqh_first = NULL; \ 346 (head)->sqh_last = &(head)->sqh_first; \ 347 } while (/*CONSTCOND*/0) 348 349 #define K5_SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ 350 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ 351 (head)->sqh_last = &(elm)->field.sqe_next; \ 352 (head)->sqh_first = (elm); \ 353 } while (/*CONSTCOND*/0) 354 355 #define K5_SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ 356 (elm)->field.sqe_next = NULL; \ 357 *(head)->sqh_last = (elm); \ 358 (head)->sqh_last = &(elm)->field.sqe_next; \ 359 } while (/*CONSTCOND*/0) 360 361 #define K5_SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 362 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ 363 (head)->sqh_last = &(elm)->field.sqe_next; \ 364 (listelm)->field.sqe_next = (elm); \ 365 } while (/*CONSTCOND*/0) 366 367 #define K5_SIMPLEQ_REMOVE_HEAD(head, field) do { \ 368 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ 369 (head)->sqh_last = &(head)->sqh_first; \ 370 } while (/*CONSTCOND*/0) 371 372 #define K5_SIMPLEQ_REMOVE(head, elm, type, field) do { \ 373 if ((head)->sqh_first == (elm)) { \ 374 K5_SIMPLEQ_REMOVE_HEAD((head), field); \ 375 } else { \ 376 struct type *curelm = (head)->sqh_first; \ 377 while (curelm->field.sqe_next != (elm)) \ 378 curelm = curelm->field.sqe_next; \ 379 if ((curelm->field.sqe_next = \ 380 curelm->field.sqe_next->field.sqe_next) == NULL) \ 381 (head)->sqh_last = &(curelm)->field.sqe_next; \ 382 } \ 383 } while (/*CONSTCOND*/0) 384 385 #define K5_SIMPLEQ_FOREACH(var, head, field) \ 386 for ((var) = ((head)->sqh_first); \ 387 (var); \ 388 (var) = ((var)->field.sqe_next)) 389 390 #define K5_SIMPLEQ_FOREACH_SAFE(var, head, field, next) \ 391 for ((var) = ((head)->sqh_first); \ 392 (var) && ((next = ((var)->field.sqe_next)), 1); \ 393 (var) = (next)) 394 395 #define K5_SIMPLEQ_CONCAT(head1, head2) do { \ 396 if (!K5_SIMPLEQ_EMPTY((head2))) { \ 397 *(head1)->sqh_last = (head2)->sqh_first; \ 398 (head1)->sqh_last = (head2)->sqh_last; \ 399 K5_SIMPLEQ_INIT((head2)); \ 400 } \ 401 } while (/*CONSTCOND*/0) 402 403 #define K5_SIMPLEQ_LAST(head, type, field) \ 404 (K5_SIMPLEQ_EMPTY((head)) ? \ 405 NULL : \ 406 ((struct type *)(void *) \ 407 ((char *)((head)->sqh_last) - offsetof(struct type, field)))) 408 409 /* 410 * Simple queue access methods. 411 */ 412 #define K5_SIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL) 413 #define K5_SIMPLEQ_FIRST(head) ((head)->sqh_first) 414 #define K5_SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) 415 416 417 /* 418 * Tail queue definitions. 419 */ 420 #define _K5_TAILQ_HEAD(name, type, qual) \ 421 struct name { \ 422 qual type *tqh_first; /* first element */ \ 423 qual type *qual *tqh_last; /* addr of last next element */ \ 424 } 425 #define K5_TAILQ_HEAD(name, type) _K5_TAILQ_HEAD(name, struct type,) 426 427 #define K5_TAILQ_HEAD_INITIALIZER(head) \ 428 { NULL, &(head).tqh_first } 429 430 #define _K5_TAILQ_ENTRY(type, qual) \ 431 struct { \ 432 qual type *tqe_next; /* next element */ \ 433 qual type *qual *tqe_prev; /* address of previous next element */\ 434 } 435 #define K5_TAILQ_ENTRY(type) _K5_TAILQ_ENTRY(struct type,) 436 437 /* 438 * Tail queue functions. 439 */ 440 #define K5_TAILQ_INIT(head) do { \ 441 (head)->tqh_first = NULL; \ 442 (head)->tqh_last = &(head)->tqh_first; \ 443 } while (/*CONSTCOND*/0) 444 445 #define K5_TAILQ_INSERT_HEAD(head, elm, field) do { \ 446 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 447 (head)->tqh_first->field.tqe_prev = \ 448 &(elm)->field.tqe_next; \ 449 else \ 450 (head)->tqh_last = &(elm)->field.tqe_next; \ 451 (head)->tqh_first = (elm); \ 452 (elm)->field.tqe_prev = &(head)->tqh_first; \ 453 } while (/*CONSTCOND*/0) 454 455 #define K5_TAILQ_INSERT_TAIL(head, elm, field) do { \ 456 (elm)->field.tqe_next = NULL; \ 457 (elm)->field.tqe_prev = (head)->tqh_last; \ 458 *(head)->tqh_last = (elm); \ 459 (head)->tqh_last = &(elm)->field.tqe_next; \ 460 } while (/*CONSTCOND*/0) 461 462 #define K5_TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 463 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 464 (elm)->field.tqe_next->field.tqe_prev = \ 465 &(elm)->field.tqe_next; \ 466 else \ 467 (head)->tqh_last = &(elm)->field.tqe_next; \ 468 (listelm)->field.tqe_next = (elm); \ 469 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 470 } while (/*CONSTCOND*/0) 471 472 #define K5_TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 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 K5_TAILQ_REMOVE(head, elm, field) do { \ 480 if (((elm)->field.tqe_next) != NULL) \ 481 (elm)->field.tqe_next->field.tqe_prev = \ 482 (elm)->field.tqe_prev; \ 483 else \ 484 (head)->tqh_last = (elm)->field.tqe_prev; \ 485 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 486 } while (/*CONSTCOND*/0) 487 488 #define K5_TAILQ_FOREACH(var, head, field) \ 489 for ((var) = ((head)->tqh_first); \ 490 (var); \ 491 (var) = ((var)->field.tqe_next)) 492 493 #define K5_TAILQ_FOREACH_SAFE(var, head, field, next) \ 494 for ((var) = ((head)->tqh_first); \ 495 (var) != NULL && ((next) = K5_TAILQ_NEXT(var, field), 1); \ 496 (var) = (next)) 497 498 #define K5_TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 499 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \ 500 (var); \ 501 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last))) 502 503 #define K5_TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev) \ 504 for ((var) = K5_TAILQ_LAST((head), headname); \ 505 (var) && ((prev) = K5_TAILQ_PREV((var), headname, field), 1);\ 506 (var) = (prev)) 507 508 #define K5_TAILQ_CONCAT(head1, head2, field) do { \ 509 if (!K5_TAILQ_EMPTY(head2)) { \ 510 *(head1)->tqh_last = (head2)->tqh_first; \ 511 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 512 (head1)->tqh_last = (head2)->tqh_last; \ 513 K5_TAILQ_INIT((head2)); \ 514 } \ 515 } while (/*CONSTCOND*/0) 516 517 /* 518 * Tail queue access methods. 519 */ 520 #define K5_TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 521 #define K5_TAILQ_FIRST(head) ((head)->tqh_first) 522 #define K5_TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 523 524 #define K5_TAILQ_LAST(head, headname) \ 525 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 526 #define K5_TAILQ_PREV(elm, headname, field) \ 527 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 528 529 530 /* 531 * Circular queue definitions. 532 */ 533 #define K5_CIRCLEQ_HEAD(name, type) \ 534 struct name { \ 535 struct type *cqh_first; /* first element */ \ 536 struct type *cqh_last; /* last element */ \ 537 } 538 539 #define K5_CIRCLEQ_HEAD_INITIALIZER(head) \ 540 { (void *)&head, (void *)&head } 541 542 #define K5_CIRCLEQ_ENTRY(type) \ 543 struct { \ 544 struct type *cqe_next; /* next element */ \ 545 struct type *cqe_prev; /* previous element */ \ 546 } 547 548 /* 549 * Circular queue functions. 550 */ 551 #define K5_CIRCLEQ_INIT(head) do { \ 552 (head)->cqh_first = (void *)(head); \ 553 (head)->cqh_last = (void *)(head); \ 554 } while (/*CONSTCOND*/0) 555 556 #define K5_CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 557 (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 558 (elm)->field.cqe_prev = (listelm); \ 559 if ((listelm)->field.cqe_next == (void *)(head)) \ 560 (head)->cqh_last = (elm); \ 561 else \ 562 (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 563 (listelm)->field.cqe_next = (elm); \ 564 } while (/*CONSTCOND*/0) 565 566 #define K5_CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ 567 (elm)->field.cqe_next = (listelm); \ 568 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 569 if ((listelm)->field.cqe_prev == (void *)(head)) \ 570 (head)->cqh_first = (elm); \ 571 else \ 572 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 573 (listelm)->field.cqe_prev = (elm); \ 574 } while (/*CONSTCOND*/0) 575 576 #define K5_CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ 577 (elm)->field.cqe_next = (head)->cqh_first; \ 578 (elm)->field.cqe_prev = (void *)(head); \ 579 if ((head)->cqh_last == (void *)(head)) \ 580 (head)->cqh_last = (elm); \ 581 else \ 582 (head)->cqh_first->field.cqe_prev = (elm); \ 583 (head)->cqh_first = (elm); \ 584 } while (/*CONSTCOND*/0) 585 586 #define K5_CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ 587 (elm)->field.cqe_next = (void *)(head); \ 588 (elm)->field.cqe_prev = (head)->cqh_last; \ 589 if ((head)->cqh_first == (void *)(head)) \ 590 (head)->cqh_first = (elm); \ 591 else \ 592 (head)->cqh_last->field.cqe_next = (elm); \ 593 (head)->cqh_last = (elm); \ 594 } while (/*CONSTCOND*/0) 595 596 #define K5_CIRCLEQ_REMOVE(head, elm, field) do { \ 597 if ((elm)->field.cqe_next == (void *)(head)) \ 598 (head)->cqh_last = (elm)->field.cqe_prev; \ 599 else \ 600 (elm)->field.cqe_next->field.cqe_prev = \ 601 (elm)->field.cqe_prev; \ 602 if ((elm)->field.cqe_prev == (void *)(head)) \ 603 (head)->cqh_first = (elm)->field.cqe_next; \ 604 else \ 605 (elm)->field.cqe_prev->field.cqe_next = \ 606 (elm)->field.cqe_next; \ 607 } while (/*CONSTCOND*/0) 608 609 #define K5_CIRCLEQ_FOREACH(var, head, field) \ 610 for ((var) = ((head)->cqh_first); \ 611 (var) != (const void *)(head); \ 612 (var) = ((var)->field.cqe_next)) 613 614 #define K5_CIRCLEQ_FOREACH_REVERSE(var, head, field) \ 615 for ((var) = ((head)->cqh_last); \ 616 (var) != (const void *)(head); \ 617 (var) = ((var)->field.cqe_prev)) 618 619 /* 620 * Circular queue access methods. 621 */ 622 #define K5_CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head)) 623 #define K5_CIRCLEQ_FIRST(head) ((head)->cqh_first) 624 #define K5_CIRCLEQ_LAST(head) ((head)->cqh_last) 625 #define K5_CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) 626 #define K5_CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) 627 628 #define K5_CIRCLEQ_LOOP_NEXT(head, elm, field) \ 629 (((elm)->field.cqe_next == (void *)(head)) \ 630 ? ((head)->cqh_first) \ 631 : (elm->field.cqe_next)) 632 #define K5_CIRCLEQ_LOOP_PREV(head, elm, field) \ 633 (((elm)->field.cqe_prev == (void *)(head)) \ 634 ? ((head)->cqh_last) \ 635 : (elm->field.cqe_prev)) 636 637 #endif /* !K5_QUEUE_H */ 638