Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/sys/queue.h
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
1 /* $NetBSD: queue.h,v 1.49.6.1 2008/11/20 03:22:38 snj 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 #include <sys/null.h> 38 39 /* 40 * This file defines five types of data structures: singly-linked lists, 41 * lists, simple queues, tail queues, and circular queues. 42 * 43 * A singly-linked list is headed by a single forward pointer. The 44 * elements are singly linked for minimum space and pointer manipulation 45 * overhead at the expense of O(n) removal for arbitrary elements. New 46 * elements can be added to the list after an existing element or at the 47 * head of the list. Elements being removed from the head of the list 48 * should use the explicit macro for this purpose for optimum 49 * efficiency. A singly-linked list may only be traversed in the forward 50 * direction. Singly-linked lists are ideal for applications with large 51 * datasets and few or no removals or for implementing a LIFO queue. 52 * 53 * A list is headed by a single forward pointer (or an array of forward 54 * pointers for a hash table header). The elements are doubly linked 55 * so that an arbitrary element can be removed without a need to 56 * traverse the list. New elements can be added to the list before 57 * or after an existing element or at the head of the list. A list 58 * may only be traversed in the forward direction. 59 * 60 * A simple queue is headed by a pair of pointers, one the head of the 61 * list and the other to the tail of the list. The elements are singly 62 * linked to save space, so elements can only be removed from the 63 * head of the list. New elements can be added to the list after 64 * an existing element, at the head of the list, or at the end of the 65 * list. A simple queue may only be traversed in the forward direction. 66 * 67 * A tail queue is headed by a pair of pointers, one to the head of the 68 * list and the other to the tail of the list. The elements are doubly 69 * linked so that an arbitrary element can be removed without a need to 70 * traverse the list. New elements can be added to the list before or 71 * after an existing element, at the head of the list, or at the end of 72 * the list. A tail queue may be traversed in either direction. 73 * 74 * A circle queue is headed by a pair of pointers, one to the head of the 75 * list and the other to the tail of the list. The elements are doubly 76 * linked so that an arbitrary element can be removed without a need to 77 * traverse the list. New elements can be added to the list before or after 78 * an existing element, at the head of the list, or at the end of the list. 79 * A circle queue may be traversed in either direction, but has a more 80 * complex end of list detection. 81 * 82 * For details on the use of these macros, see the queue(3) manual page. 83 */ 84 85 /* 86 * List definitions. 87 */ 88 #define LIST_HEAD(name, type) \ 89 struct name { \ 90 struct type *lh_first; /* first element */ \ 91 } 92 93 #define LIST_HEAD_INITIALIZER(head) \ 94 { NULL } 95 96 #define LIST_ENTRY(type) \ 97 struct { \ 98 struct type *le_next; /* next element */ \ 99 struct type **le_prev; /* address of previous next element */ \ 100 } 101 102 /* 103 * List functions. 104 */ 105 #if defined(_KERNEL) && defined(QUEUEDEBUG) 106 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) \ 107 if ((head)->lh_first && \ 108 (head)->lh_first->field.le_prev != &(head)->lh_first) \ 109 panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__); 110 #define QUEUEDEBUG_LIST_OP(elm, field) \ 111 if ((elm)->field.le_next && \ 112 (elm)->field.le_next->field.le_prev != \ 113 &(elm)->field.le_next) \ 114 panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\ 115 if (*(elm)->field.le_prev != (elm)) \ 116 panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__); 117 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) \ 118 (elm)->field.le_next = (void *)1L; \ 119 (elm)->field.le_prev = (void *)1L; 120 #else 121 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) 122 #define QUEUEDEBUG_LIST_OP(elm, field) 123 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) 124 #endif 125 126 #define LIST_INIT(head) do { \ 127 (head)->lh_first = NULL; \ 128 } while (/*CONSTCOND*/0) 129 130 #define LIST_INSERT_AFTER(listelm, elm, field) do { \ 131 QUEUEDEBUG_LIST_OP((listelm), field) \ 132 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 133 (listelm)->field.le_next->field.le_prev = \ 134 &(elm)->field.le_next; \ 135 (listelm)->field.le_next = (elm); \ 136 (elm)->field.le_prev = &(listelm)->field.le_next; \ 137 } while (/*CONSTCOND*/0) 138 139 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 140 QUEUEDEBUG_LIST_OP((listelm), field) \ 141 (elm)->field.le_prev = (listelm)->field.le_prev; \ 142 (elm)->field.le_next = (listelm); \ 143 *(listelm)->field.le_prev = (elm); \ 144 (listelm)->field.le_prev = &(elm)->field.le_next; \ 145 } while (/*CONSTCOND*/0) 146 147 #define LIST_INSERT_HEAD(head, elm, field) do { \ 148 QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field) \ 149 if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 150 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 151 (head)->lh_first = (elm); \ 152 (elm)->field.le_prev = &(head)->lh_first; \ 153 } while (/*CONSTCOND*/0) 154 155 #define LIST_REMOVE(elm, field) do { \ 156 QUEUEDEBUG_LIST_OP((elm), field) \ 157 if ((elm)->field.le_next != NULL) \ 158 (elm)->field.le_next->field.le_prev = \ 159 (elm)->field.le_prev; \ 160 *(elm)->field.le_prev = (elm)->field.le_next; \ 161 QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \ 162 } while (/*CONSTCOND*/0) 163 164 #define LIST_FOREACH(var, head, field) \ 165 for ((var) = ((head)->lh_first); \ 166 (var); \ 167 (var) = ((var)->field.le_next)) 168 169 /* 170 * List access methods. 171 */ 172 #define LIST_EMPTY(head) ((head)->lh_first == NULL) 173 #define LIST_FIRST(head) ((head)->lh_first) 174 #define LIST_NEXT(elm, field) ((elm)->field.le_next) 175 176 177 /* 178 * Singly-linked List definitions. 179 */ 180 #define SLIST_HEAD(name, type) \ 181 struct name { \ 182 struct type *slh_first; /* first element */ \ 183 } 184 185 #define SLIST_HEAD_INITIALIZER(head) \ 186 { NULL } 187 188 #define SLIST_ENTRY(type) \ 189 struct { \ 190 struct type *sle_next; /* next element */ \ 191 } 192 193 /* 194 * Singly-linked List functions. 195 */ 196 #define SLIST_INIT(head) do { \ 197 (head)->slh_first = NULL; \ 198 } while (/*CONSTCOND*/0) 199 200 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 201 (elm)->field.sle_next = (slistelm)->field.sle_next; \ 202 (slistelm)->field.sle_next = (elm); \ 203 } while (/*CONSTCOND*/0) 204 205 #define SLIST_INSERT_HEAD(head, elm, field) do { \ 206 (elm)->field.sle_next = (head)->slh_first; \ 207 (head)->slh_first = (elm); \ 208 } while (/*CONSTCOND*/0) 209 210 #define SLIST_REMOVE_HEAD(head, field) do { \ 211 (head)->slh_first = (head)->slh_first->field.sle_next; \ 212 } while (/*CONSTCOND*/0) 213 214 #define SLIST_REMOVE(head, elm, type, field) do { \ 215 if ((head)->slh_first == (elm)) { \ 216 SLIST_REMOVE_HEAD((head), field); \ 217 } \ 218 else { \ 219 struct type *curelm = (head)->slh_first; \ 220 while(curelm->field.sle_next != (elm)) \ 221 curelm = curelm->field.sle_next; \ 222 curelm->field.sle_next = \ 223 curelm->field.sle_next->field.sle_next; \ 224 } \ 225 } while (/*CONSTCOND*/0) 226 227 #define SLIST_REMOVE_AFTER(slistelm, field) do { \ 228 (slistelm)->field.sle_next = \ 229 SLIST_NEXT(SLIST_NEXT((slistelm), field), field); \ 230 } while (/*CONSTCOND*/0) 231 232 #define SLIST_FOREACH(var, head, field) \ 233 for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next) 234 235 /* 236 * Singly-linked List access methods. 237 */ 238 #define SLIST_EMPTY(head) ((head)->slh_first == NULL) 239 #define SLIST_FIRST(head) ((head)->slh_first) 240 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 241 242 243 /* 244 * Singly-linked Tail queue declarations. 245 */ 246 #define STAILQ_HEAD(name, type) \ 247 struct name { \ 248 struct type *stqh_first; /* first element */ \ 249 struct type **stqh_last; /* addr of last next element */ \ 250 } 251 252 #define STAILQ_HEAD_INITIALIZER(head) \ 253 { NULL, &(head).stqh_first } 254 255 #define STAILQ_ENTRY(type) \ 256 struct { \ 257 struct type *stqe_next; /* next element */ \ 258 } 259 260 /* 261 * Singly-linked Tail queue functions. 262 */ 263 #define STAILQ_INIT(head) do { \ 264 (head)->stqh_first = NULL; \ 265 (head)->stqh_last = &(head)->stqh_first; \ 266 } while (/*CONSTCOND*/0) 267 268 #define STAILQ_INSERT_HEAD(head, elm, field) do { \ 269 if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \ 270 (head)->stqh_last = &(elm)->field.stqe_next; \ 271 (head)->stqh_first = (elm); \ 272 } while (/*CONSTCOND*/0) 273 274 #define STAILQ_INSERT_TAIL(head, elm, field) do { \ 275 (elm)->field.stqe_next = NULL; \ 276 *(head)->stqh_last = (elm); \ 277 (head)->stqh_last = &(elm)->field.stqe_next; \ 278 } while (/*CONSTCOND*/0) 279 280 #define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 281 if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\ 282 (head)->stqh_last = &(elm)->field.stqe_next; \ 283 (listelm)->field.stqe_next = (elm); \ 284 } while (/*CONSTCOND*/0) 285 286 #define STAILQ_REMOVE_HEAD(head, field) do { \ 287 if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \ 288 (head)->stqh_last = &(head)->stqh_first; \ 289 } while (/*CONSTCOND*/0) 290 291 #define STAILQ_REMOVE(head, elm, type, field) do { \ 292 if ((head)->stqh_first == (elm)) { \ 293 STAILQ_REMOVE_HEAD((head), field); \ 294 } else { \ 295 struct type *curelm = (head)->stqh_first; \ 296 while (curelm->field.stqe_next != (elm)) \ 297 curelm = curelm->field.stqe_next; \ 298 if ((curelm->field.stqe_next = \ 299 curelm->field.stqe_next->field.stqe_next) == NULL) \ 300 (head)->stqh_last = &(curelm)->field.stqe_next; \ 301 } \ 302 } while (/*CONSTCOND*/0) 303 304 #define STAILQ_FOREACH(var, head, field) \ 305 for ((var) = ((head)->stqh_first); \ 306 (var); \ 307 (var) = ((var)->field.stqe_next)) 308 309 #define STAILQ_CONCAT(head1, head2) do { \ 310 if (!STAILQ_EMPTY((head2))) { \ 311 *(head1)->stqh_last = (head2)->stqh_first; \ 312 (head1)->stqh_last = (head2)->stqh_last; \ 313 STAILQ_INIT((head2)); \ 314 } \ 315 } while (/*CONSTCOND*/0) 316 317 /* 318 * Singly-linked Tail queue access methods. 319 */ 320 #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 321 #define STAILQ_FIRST(head) ((head)->stqh_first) 322 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 323 324 325 /* 326 * Simple queue definitions. 327 */ 328 #define SIMPLEQ_HEAD(name, type) \ 329 struct name { \ 330 struct type *sqh_first; /* first element */ \ 331 struct type **sqh_last; /* addr of last next element */ \ 332 } 333 334 #define SIMPLEQ_HEAD_INITIALIZER(head) \ 335 { NULL, &(head).sqh_first } 336 337 #define SIMPLEQ_ENTRY(type) \ 338 struct { \ 339 struct type *sqe_next; /* next element */ \ 340 } 341 342 /* 343 * Simple queue functions. 344 */ 345 #define SIMPLEQ_INIT(head) do { \ 346 (head)->sqh_first = NULL; \ 347 (head)->sqh_last = &(head)->sqh_first; \ 348 } while (/*CONSTCOND*/0) 349 350 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ 351 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ 352 (head)->sqh_last = &(elm)->field.sqe_next; \ 353 (head)->sqh_first = (elm); \ 354 } while (/*CONSTCOND*/0) 355 356 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ 357 (elm)->field.sqe_next = NULL; \ 358 *(head)->sqh_last = (elm); \ 359 (head)->sqh_last = &(elm)->field.sqe_next; \ 360 } while (/*CONSTCOND*/0) 361 362 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 363 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ 364 (head)->sqh_last = &(elm)->field.sqe_next; \ 365 (listelm)->field.sqe_next = (elm); \ 366 } while (/*CONSTCOND*/0) 367 368 #define SIMPLEQ_REMOVE_HEAD(head, field) do { \ 369 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ 370 (head)->sqh_last = &(head)->sqh_first; \ 371 } while (/*CONSTCOND*/0) 372 373 #define SIMPLEQ_REMOVE(head, elm, type, field) do { \ 374 if ((head)->sqh_first == (elm)) { \ 375 SIMPLEQ_REMOVE_HEAD((head), field); \ 376 } else { \ 377 struct type *curelm = (head)->sqh_first; \ 378 while (curelm->field.sqe_next != (elm)) \ 379 curelm = curelm->field.sqe_next; \ 380 if ((curelm->field.sqe_next = \ 381 curelm->field.sqe_next->field.sqe_next) == NULL) \ 382 (head)->sqh_last = &(curelm)->field.sqe_next; \ 383 } \ 384 } while (/*CONSTCOND*/0) 385 386 #define SIMPLEQ_FOREACH(var, head, field) \ 387 for ((var) = ((head)->sqh_first); \ 388 (var); \ 389 (var) = ((var)->field.sqe_next)) 390 391 /* 392 * Simple queue access methods. 393 */ 394 #define SIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL) 395 #define SIMPLEQ_FIRST(head) ((head)->sqh_first) 396 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) 397 398 399 /* 400 * Tail queue definitions. 401 */ 402 #define _TAILQ_HEAD(name, type, qual) \ 403 struct name { \ 404 qual type *tqh_first; /* first element */ \ 405 qual type *qual *tqh_last; /* addr of last next element */ \ 406 } 407 #define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,) 408 409 #define TAILQ_HEAD_INITIALIZER(head) \ 410 { NULL, &(head).tqh_first } 411 412 #define _TAILQ_ENTRY(type, qual) \ 413 struct { \ 414 qual type *tqe_next; /* next element */ \ 415 qual type *qual *tqe_prev; /* address of previous next element */\ 416 } 417 #define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,) 418 419 /* 420 * Tail queue functions. 421 */ 422 #if defined(_KERNEL) && defined(QUEUEDEBUG) 423 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) \ 424 if ((head)->tqh_first && \ 425 (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \ 426 panic("TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__); 427 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) \ 428 if (*(head)->tqh_last != NULL) \ 429 panic("TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__); 430 #define QUEUEDEBUG_TAILQ_OP(elm, field) \ 431 if ((elm)->field.tqe_next && \ 432 (elm)->field.tqe_next->field.tqe_prev != \ 433 &(elm)->field.tqe_next) \ 434 panic("TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\ 435 if (*(elm)->field.tqe_prev != (elm)) \ 436 panic("TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__); 437 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) \ 438 if ((elm)->field.tqe_next == NULL && \ 439 (head)->tqh_last != &(elm)->field.tqe_next) \ 440 panic("TAILQ_PREREMOVE head %p elm %p %s:%d", \ 441 (head), (elm), __FILE__, __LINE__); 442 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) \ 443 (elm)->field.tqe_next = (void *)1L; \ 444 (elm)->field.tqe_prev = (void *)1L; 445 #else 446 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) 447 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) 448 #define QUEUEDEBUG_TAILQ_OP(elm, field) 449 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) 450 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) 451 #endif 452 453 #define TAILQ_INIT(head) do { \ 454 (head)->tqh_first = NULL; \ 455 (head)->tqh_last = &(head)->tqh_first; \ 456 } while (/*CONSTCOND*/0) 457 458 #define TAILQ_INSERT_HEAD(head, elm, field) do { \ 459 QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field) \ 460 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 461 (head)->tqh_first->field.tqe_prev = \ 462 &(elm)->field.tqe_next; \ 463 else \ 464 (head)->tqh_last = &(elm)->field.tqe_next; \ 465 (head)->tqh_first = (elm); \ 466 (elm)->field.tqe_prev = &(head)->tqh_first; \ 467 } while (/*CONSTCOND*/0) 468 469 #define TAILQ_INSERT_TAIL(head, elm, field) do { \ 470 QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field) \ 471 (elm)->field.tqe_next = NULL; \ 472 (elm)->field.tqe_prev = (head)->tqh_last; \ 473 *(head)->tqh_last = (elm); \ 474 (head)->tqh_last = &(elm)->field.tqe_next; \ 475 } while (/*CONSTCOND*/0) 476 477 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 478 QUEUEDEBUG_TAILQ_OP((listelm), field) \ 479 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 480 (elm)->field.tqe_next->field.tqe_prev = \ 481 &(elm)->field.tqe_next; \ 482 else \ 483 (head)->tqh_last = &(elm)->field.tqe_next; \ 484 (listelm)->field.tqe_next = (elm); \ 485 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 486 } while (/*CONSTCOND*/0) 487 488 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 489 QUEUEDEBUG_TAILQ_OP((listelm), field) \ 490 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 491 (elm)->field.tqe_next = (listelm); \ 492 *(listelm)->field.tqe_prev = (elm); \ 493 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 494 } while (/*CONSTCOND*/0) 495 496 #define TAILQ_REMOVE(head, elm, field) do { \ 497 QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field) \ 498 QUEUEDEBUG_TAILQ_OP((elm), field) \ 499 if (((elm)->field.tqe_next) != NULL) \ 500 (elm)->field.tqe_next->field.tqe_prev = \ 501 (elm)->field.tqe_prev; \ 502 else \ 503 (head)->tqh_last = (elm)->field.tqe_prev; \ 504 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 505 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \ 506 } while (/*CONSTCOND*/0) 507 508 #define TAILQ_FOREACH(var, head, field) \ 509 for ((var) = ((head)->tqh_first); \ 510 (var); \ 511 (var) = ((var)->field.tqe_next)) 512 513 #define TAILQ_FOREACH_SAFE(var, head, field, next) \ 514 for ((var) = ((head)->tqh_first); \ 515 (var) != NULL && ((next) = TAILQ_NEXT(var, field), 1); \ 516 (var) = (next)) 517 518 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 519 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \ 520 (var); \ 521 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last))) 522 523 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev) \ 524 for ((var) = TAILQ_LAST((head), headname); \ 525 (var) && ((prev) = TAILQ_PREV((var), headname, field), 1);\ 526 (var) = (prev)) 527 528 #define TAILQ_CONCAT(head1, head2, field) do { \ 529 if (!TAILQ_EMPTY(head2)) { \ 530 *(head1)->tqh_last = (head2)->tqh_first; \ 531 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 532 (head1)->tqh_last = (head2)->tqh_last; \ 533 TAILQ_INIT((head2)); \ 534 } \ 535 } while (/*CONSTCOND*/0) 536 537 /* 538 * Tail queue access methods. 539 */ 540 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 541 #define TAILQ_FIRST(head) ((head)->tqh_first) 542 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 543 544 #define TAILQ_LAST(head, headname) \ 545 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 546 #define TAILQ_PREV(elm, headname, field) \ 547 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 548 549 550 /* 551 * Circular queue definitions. 552 */ 553 #if defined(_KERNEL) && defined(QUEUEDEBUG) 554 #define QUEUEDEBUG_CIRCLEQ_HEAD(head, field) \ 555 if ((head)->cqh_first != (void *)(head) && \ 556 (head)->cqh_first->field.cqe_prev != (void *)(head)) \ 557 panic("CIRCLEQ head forw %p %s:%d", (head), \ 558 __FILE__, __LINE__); \ 559 if ((head)->cqh_last != (void *)(head) && \ 560 (head)->cqh_last->field.cqe_next != (void *)(head)) \ 561 panic("CIRCLEQ head back %p %s:%d", (head), \ 562 __FILE__, __LINE__); 563 #define QUEUEDEBUG_CIRCLEQ_ELM(head, elm, field) \ 564 if ((elm)->field.cqe_next == (void *)(head)) { \ 565 if ((head)->cqh_last != (elm)) \ 566 panic("CIRCLEQ elm last %p %s:%d", (elm), \ 567 __FILE__, __LINE__); \ 568 } else { \ 569 if ((elm)->field.cqe_next->field.cqe_prev != (elm)) \ 570 panic("CIRCLEQ elm forw %p %s:%d", (elm), \ 571 __FILE__, __LINE__); \ 572 } \ 573 if ((elm)->field.cqe_prev == (void *)(head)) { \ 574 if ((head)->cqh_first != (elm)) \ 575 panic("CIRCLEQ elm first %p %s:%d", (elm), \ 576 __FILE__, __LINE__); \ 577 } else { \ 578 if ((elm)->field.cqe_prev->field.cqe_next != (elm)) \ 579 panic("CIRCLEQ elm prev %p %s:%d", (elm), \ 580 __FILE__, __LINE__); \ 581 } 582 #define QUEUEDEBUG_CIRCLEQ_POSTREMOVE(elm, field) \ 583 (elm)->field.cqe_next = (void *)1L; \ 584 (elm)->field.cqe_prev = (void *)1L; 585 #else 586 #define QUEUEDEBUG_CIRCLEQ_HEAD(head, field) 587 #define QUEUEDEBUG_CIRCLEQ_ELM(head, elm, field) 588 #define QUEUEDEBUG_CIRCLEQ_POSTREMOVE(elm, field) 589 #endif 590 591 #define CIRCLEQ_HEAD(name, type) \ 592 struct name { \ 593 struct type *cqh_first; /* first element */ \ 594 struct type *cqh_last; /* last element */ \ 595 } 596 597 #define CIRCLEQ_HEAD_INITIALIZER(head) \ 598 { (void *)&head, (void *)&head } 599 600 #define CIRCLEQ_ENTRY(type) \ 601 struct { \ 602 struct type *cqe_next; /* next element */ \ 603 struct type *cqe_prev; /* previous element */ \ 604 } 605 606 /* 607 * Circular queue functions. 608 */ 609 #define CIRCLEQ_INIT(head) do { \ 610 (head)->cqh_first = (void *)(head); \ 611 (head)->cqh_last = (void *)(head); \ 612 } while (/*CONSTCOND*/0) 613 614 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 615 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \ 616 QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field) \ 617 (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 618 (elm)->field.cqe_prev = (listelm); \ 619 if ((listelm)->field.cqe_next == (void *)(head)) \ 620 (head)->cqh_last = (elm); \ 621 else \ 622 (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 623 (listelm)->field.cqe_next = (elm); \ 624 } while (/*CONSTCOND*/0) 625 626 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ 627 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \ 628 QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field) \ 629 (elm)->field.cqe_next = (listelm); \ 630 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 631 if ((listelm)->field.cqe_prev == (void *)(head)) \ 632 (head)->cqh_first = (elm); \ 633 else \ 634 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 635 (listelm)->field.cqe_prev = (elm); \ 636 } while (/*CONSTCOND*/0) 637 638 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ 639 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \ 640 (elm)->field.cqe_next = (head)->cqh_first; \ 641 (elm)->field.cqe_prev = (void *)(head); \ 642 if ((head)->cqh_last == (void *)(head)) \ 643 (head)->cqh_last = (elm); \ 644 else \ 645 (head)->cqh_first->field.cqe_prev = (elm); \ 646 (head)->cqh_first = (elm); \ 647 } while (/*CONSTCOND*/0) 648 649 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ 650 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \ 651 (elm)->field.cqe_next = (void *)(head); \ 652 (elm)->field.cqe_prev = (head)->cqh_last; \ 653 if ((head)->cqh_first == (void *)(head)) \ 654 (head)->cqh_first = (elm); \ 655 else \ 656 (head)->cqh_last->field.cqe_next = (elm); \ 657 (head)->cqh_last = (elm); \ 658 } while (/*CONSTCOND*/0) 659 660 #define CIRCLEQ_REMOVE(head, elm, field) do { \ 661 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \ 662 QUEUEDEBUG_CIRCLEQ_ELM((head), (elm), field) \ 663 if ((elm)->field.cqe_next == (void *)(head)) \ 664 (head)->cqh_last = (elm)->field.cqe_prev; \ 665 else \ 666 (elm)->field.cqe_next->field.cqe_prev = \ 667 (elm)->field.cqe_prev; \ 668 if ((elm)->field.cqe_prev == (void *)(head)) \ 669 (head)->cqh_first = (elm)->field.cqe_next; \ 670 else \ 671 (elm)->field.cqe_prev->field.cqe_next = \ 672 (elm)->field.cqe_next; \ 673 QUEUEDEBUG_CIRCLEQ_POSTREMOVE((elm), field) \ 674 } while (/*CONSTCOND*/0) 675 676 #define CIRCLEQ_FOREACH(var, head, field) \ 677 for ((var) = ((head)->cqh_first); \ 678 (var) != (const void *)(head); \ 679 (var) = ((var)->field.cqe_next)) 680 681 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ 682 for ((var) = ((head)->cqh_last); \ 683 (var) != (const void *)(head); \ 684 (var) = ((var)->field.cqe_prev)) 685 686 /* 687 * Circular queue access methods. 688 */ 689 #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head)) 690 #define CIRCLEQ_FIRST(head) ((head)->cqh_first) 691 #define CIRCLEQ_LAST(head) ((head)->cqh_last) 692 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) 693 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) 694 695 #define CIRCLEQ_LOOP_NEXT(head, elm, field) \ 696 (((elm)->field.cqe_next == (void *)(head)) \ 697 ? ((head)->cqh_first) \ 698 : (elm->field.cqe_next)) 699 #define CIRCLEQ_LOOP_PREV(head, elm, field) \ 700 (((elm)->field.cqe_prev == (void *)(head)) \ 701 ? ((head)->cqh_last) \ 702 : (elm->field.cqe_prev)) 703 704 #endif /* !_SYS_QUEUE_H_ */
Cache object: 2192213a556cf42495ec47c59ad5f320
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]