The Design and Implementation of the FreeBSD Operating System, Second Edition
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 

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

Cache object: bfe1947dd36c117793a0781e3b450216


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.