include/sys/queue.h

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