"Fossies" - the Fresh Open Source Software Archive

Member "memcached-1.6.15/queue.h" (21 Feb 2022, 29387 Bytes) of package /linux/www/memcached-1.6.15.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "queue.h" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 1.6.12_vs_1.6.13.

    1 // grabbed from https://raw.githubusercontent.com/freebsd/freebsd-src/master/sys/sys/queue.h
    2 // on jan 17th, 2021.
    3 /*-
    4  * SPDX-License-Identifier: BSD-3-Clause
    5  *
    6  * Copyright (c) 1991, 1993
    7  *  The Regents of the University of California.  All rights reserved.
    8  *
    9  * Redistribution and use in source and binary forms, with or without
   10  * modification, are permitted provided that the following conditions
   11  * are met:
   12  * 1. Redistributions of source code must retain the above copyright
   13  *    notice, this list of conditions and the following disclaimer.
   14  * 2. Redistributions in binary form must reproduce the above copyright
   15  *    notice, this list of conditions and the following disclaimer in the
   16  *    documentation and/or other materials provided with the distribution.
   17  * 3. Neither the name of the University nor the names of its contributors
   18  *    may be used to endorse or promote products derived from this software
   19  *    without specific prior written permission.
   20  *
   21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   31  * SUCH DAMAGE.
   32  *
   33  *  @(#)queue.h 8.5 (Berkeley) 8/20/94
   34  * $FreeBSD$
   35  */
   36 
   37 #ifndef _SYS_QUEUE_H_
   38 #define _SYS_QUEUE_H_
   39 
   40 /*
   41  * This file defines four types of data structures: singly-linked lists,
   42  * singly-linked tail queues, lists and tail queues.
   43  *
   44  * A singly-linked list is headed by a single forward pointer. The elements
   45  * are singly linked for minimum space and pointer manipulation overhead at
   46  * the expense of O(n) removal for arbitrary elements. New elements can be
   47  * added to the list after an existing element or at the head of the list.
   48  * Elements being removed from the head of the list should use the explicit
   49  * macro for this purpose for optimum efficiency. A singly-linked list may
   50  * only be traversed in the forward direction.  Singly-linked lists are ideal
   51  * for applications with large datasets and few or no removals or for
   52  * implementing a LIFO queue.
   53  *
   54  * A singly-linked tail queue is headed by a pair of pointers, one to the
   55  * head of the list and the other to the tail of the list. The elements are
   56  * singly linked for minimum space and pointer manipulation overhead at the
   57  * expense of O(n) removal for arbitrary elements. New elements can be added
   58  * to the list after an existing element, at the head of the list, or at the
   59  * end of the list. Elements being removed from the head of the tail queue
   60  * should use the explicit macro for this purpose for optimum efficiency.
   61  * A singly-linked tail queue may only be traversed in the forward direction.
   62  * Singly-linked tail queues are ideal for applications with large datasets
   63  * and few or no removals or for implementing a FIFO queue.
   64  *
   65  * A list is headed by a single forward pointer (or an array of forward
   66  * pointers for a hash table header). The elements are doubly linked
   67  * so that an arbitrary element can be removed without a need to
   68  * traverse the list. New elements can be added to the list before
   69  * or after an existing element or at the head of the list. A list
   70  * may be traversed in either direction.
   71  *
   72  * A tail queue is headed by a pair of pointers, one to the head of the
   73  * list and the other to the tail of the list. The elements are doubly
   74  * linked so that an arbitrary element can be removed without a need to
   75  * traverse the list. New elements can be added to the list before or
   76  * after an existing element, at the head of the list, or at the end of
   77  * the list. A tail queue may be traversed in either direction.
   78  *
   79  * For details on the use of these macros, see the queue(3) manual page.
   80  *
   81  * Below is a summary of implemented functions where:
   82  *  +  means the macro is available
   83  *  -  means the macro is not available
   84  *  s  means the macro is available but is slow (runs in O(n) time)
   85  *
   86  *              SLIST   LIST    STAILQ  TAILQ
   87  * _HEAD            +   +   +   +
   88  * _CLASS_HEAD          +   +   +   +
   89  * _HEAD_INITIALIZER        +   +   +   +
   90  * _ENTRY           +   +   +   +
   91  * _CLASS_ENTRY         +   +   +   +
   92  * _INIT            +   +   +   +
   93  * _EMPTY           +   +   +   +
   94  * _FIRST           +   +   +   +
   95  * _NEXT            +   +   +   +
   96  * _PREV            -   +   -   +
   97  * _LAST            -   -   +   +
   98  * _LAST_FAST           -   -   -   +
   99  * _FOREACH         +   +   +   +
  100  * _FOREACH_FROM        +   +   +   +
  101  * _FOREACH_SAFE        +   +   +   +
  102  * _FOREACH_FROM_SAFE       +   +   +   +
  103  * _FOREACH_REVERSE     -   -   -   +
  104  * _FOREACH_REVERSE_FROM    -   -   -   +
  105  * _FOREACH_REVERSE_SAFE    -   -   -   +
  106  * _FOREACH_REVERSE_FROM_SAFE   -   -   -   +
  107  * _INSERT_HEAD         +   +   +   +
  108  * _INSERT_BEFORE       -   +   -   +
  109  * _INSERT_AFTER        +   +   +   +
  110  * _INSERT_TAIL         -   -   +   +
  111  * _CONCAT          s   s   +   +
  112  * _REMOVE_AFTER        +   -   +   -
  113  * _REMOVE_HEAD         +   -   +   -
  114  * _REMOVE          s   +   s   +
  115  * _SWAP            +   +   +   +
  116  *
  117  */
  118 #ifdef QUEUE_MACRO_DEBUG
  119 #warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH
  120 #define QUEUE_MACRO_DEBUG_TRACE
  121 #define QUEUE_MACRO_DEBUG_TRASH
  122 #endif
  123 
  124 #ifdef QUEUE_MACRO_DEBUG_TRACE
  125 /* Store the last 2 places the queue element or head was altered */
  126 struct qm_trace {
  127     unsigned long    lastline;
  128     unsigned long    prevline;
  129     const char  *lastfile;
  130     const char  *prevfile;
  131 };
  132 
  133 #define TRACEBUF    struct qm_trace trace;
  134 #define TRACEBUF_INITIALIZER    { __LINE__, 0, __FILE__, NULL } ,
  135 
  136 #define QMD_TRACE_HEAD(head) do {                   \
  137     (head)->trace.prevline = (head)->trace.lastline;        \
  138     (head)->trace.prevfile = (head)->trace.lastfile;        \
  139     (head)->trace.lastline = __LINE__;              \
  140     (head)->trace.lastfile = __FILE__;              \
  141 } while (0)
  142 
  143 #define QMD_TRACE_ELEM(elem) do {                   \
  144     (elem)->trace.prevline = (elem)->trace.lastline;        \
  145     (elem)->trace.prevfile = (elem)->trace.lastfile;        \
  146     (elem)->trace.lastline = __LINE__;              \
  147     (elem)->trace.lastfile = __FILE__;              \
  148 } while (0)
  149 
  150 #else   /* !QUEUE_MACRO_DEBUG_TRACE */
  151 #define QMD_TRACE_ELEM(elem)
  152 #define QMD_TRACE_HEAD(head)
  153 #define TRACEBUF
  154 #define TRACEBUF_INITIALIZER
  155 #endif  /* QUEUE_MACRO_DEBUG_TRACE */
  156 
  157 #ifdef QUEUE_MACRO_DEBUG_TRASH
  158 #define QMD_SAVELINK(name, link)    void **name = (void *)&(link)
  159 #define TRASHIT(x)      do {(x) = (void *)-1;} while (0)
  160 #define QMD_IS_TRASHED(x)   ((x) == (void *)(intptr_t)-1)
  161 #else   /* !QUEUE_MACRO_DEBUG_TRASH */
  162 #define QMD_SAVELINK(name, link)
  163 #define TRASHIT(x)
  164 #define QMD_IS_TRASHED(x)   0
  165 #endif  /* QUEUE_MACRO_DEBUG_TRASH */
  166 
  167 #ifdef __cplusplus
  168 /*
  169  * In C++ there can be structure lists and class lists:
  170  */
  171 #define QUEUE_TYPEOF(type) type
  172 #else
  173 #define QUEUE_TYPEOF(type) struct type
  174 #endif
  175 
  176 /*
  177  * Singly-linked List declarations.
  178  */
  179 #define SLIST_HEAD(name, type)                      \
  180 struct name {                               \
  181     struct type *slh_first; /* first element */         \
  182 }
  183 
  184 #define SLIST_CLASS_HEAD(name, type)                    \
  185 struct name {                               \
  186     class type *slh_first;  /* first element */         \
  187 }
  188 
  189 #define SLIST_HEAD_INITIALIZER(head)                    \
  190     { NULL }
  191 
  192 #define SLIST_ENTRY(type)                       \
  193 struct {                                \
  194     struct type *sle_next;  /* next element */          \
  195 }
  196 
  197 #define SLIST_CLASS_ENTRY(type)                     \
  198 struct {                                \
  199     class type *sle_next;       /* next element */      \
  200 }
  201 
  202 /*
  203  * Singly-linked List functions.
  204  */
  205 #if (defined(_KERNEL) && defined(INVARIANTS))
  206 #define QMD_SLIST_CHECK_PREVPTR(prevp, elm) do {            \
  207     if (*(prevp) != (elm))                      \
  208         panic("Bad prevptr *(%p) == %p != %p",          \
  209             (prevp), *(prevp), (elm));              \
  210 } while (0)
  211 #else
  212 #define QMD_SLIST_CHECK_PREVPTR(prevp, elm)
  213 #endif
  214 
  215 #define SLIST_CONCAT(head1, head2, type, field) do {            \
  216     QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1);        \
  217     if (curelm == NULL) {                       \
  218         if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL)  \
  219             SLIST_INIT(head2);              \
  220     } else if (SLIST_FIRST(head2) != NULL) {            \
  221         while (SLIST_NEXT(curelm, field) != NULL)       \
  222             curelm = SLIST_NEXT(curelm, field);     \
  223         SLIST_NEXT(curelm, field) = SLIST_FIRST(head2);     \
  224         SLIST_INIT(head2);                  \
  225     }                               \
  226 } while (0)
  227 
  228 #define SLIST_EMPTY(head)   ((head)->slh_first == NULL)
  229 
  230 #define SLIST_FIRST(head)   ((head)->slh_first)
  231 
  232 #define SLIST_FOREACH(var, head, field)                 \
  233     for ((var) = SLIST_FIRST((head));               \
  234         (var);                          \
  235         (var) = SLIST_NEXT((var), field))
  236 
  237 #define SLIST_FOREACH_FROM(var, head, field)                \
  238     for ((var) = ((var) ? (var) : SLIST_FIRST((head)));     \
  239         (var);                          \
  240         (var) = SLIST_NEXT((var), field))
  241 
  242 #define SLIST_FOREACH_SAFE(var, head, field, tvar)          \
  243     for ((var) = SLIST_FIRST((head));               \
  244         (var) && ((tvar) = SLIST_NEXT((var), field), 1);        \
  245         (var) = (tvar))
  246 
  247 #define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar)         \
  248     for ((var) = ((var) ? (var) : SLIST_FIRST((head)));     \
  249         (var) && ((tvar) = SLIST_NEXT((var), field), 1);        \
  250         (var) = (tvar))
  251 
  252 #define SLIST_FOREACH_PREVPTR(var, varp, head, field)           \
  253     for ((varp) = &SLIST_FIRST((head));             \
  254         ((var) = *(varp)) != NULL;                  \
  255         (varp) = &SLIST_NEXT((var), field))
  256 
  257 #define SLIST_INIT(head) do {                       \
  258     SLIST_FIRST((head)) = NULL;                 \
  259 } while (0)
  260 
  261 #define SLIST_INSERT_AFTER(slistelm, elm, field) do {           \
  262     SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);   \
  263     SLIST_NEXT((slistelm), field) = (elm);              \
  264 } while (0)
  265 
  266 #define SLIST_INSERT_HEAD(head, elm, field) do {            \
  267     SLIST_NEXT((elm), field) = SLIST_FIRST((head));         \
  268     SLIST_FIRST((head)) = (elm);                    \
  269 } while (0)
  270 
  271 #define SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
  272 
  273 #define SLIST_REMOVE(head, elm, type, field) do {           \
  274     QMD_SAVELINK(oldnext, (elm)->field.sle_next);           \
  275     if (SLIST_FIRST((head)) == (elm)) {             \
  276         SLIST_REMOVE_HEAD((head), field);           \
  277     }                               \
  278     else {                              \
  279         QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head);     \
  280         while (SLIST_NEXT(curelm, field) != (elm))      \
  281             curelm = SLIST_NEXT(curelm, field);     \
  282         SLIST_REMOVE_AFTER(curelm, field);          \
  283     }                               \
  284     TRASHIT(*oldnext);                      \
  285 } while (0)
  286 
  287 #define SLIST_REMOVE_AFTER(elm, field) do {             \
  288     SLIST_NEXT(elm, field) =                    \
  289         SLIST_NEXT(SLIST_NEXT(elm, field), field);          \
  290 } while (0)
  291 
  292 #define SLIST_REMOVE_HEAD(head, field) do {             \
  293     SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);   \
  294 } while (0)
  295 
  296 #define SLIST_REMOVE_PREVPTR(prevp, elm, field) do {            \
  297     QMD_SLIST_CHECK_PREVPTR(prevp, elm);                \
  298     *(prevp) = SLIST_NEXT(elm, field);              \
  299     TRASHIT((elm)->field.sle_next);                 \
  300 } while (0)
  301 
  302 #define SLIST_SWAP(head1, head2, type) do {             \
  303     QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1);        \
  304     SLIST_FIRST(head1) = SLIST_FIRST(head2);            \
  305     SLIST_FIRST(head2) = swap_first;                \
  306 } while (0)
  307 
  308 /*
  309  * Singly-linked Tail queue declarations.
  310  */
  311 #define STAILQ_HEAD(name, type)                     \
  312 struct name {                               \
  313     struct type *stqh_first;/* first element */         \
  314     struct type **stqh_last;/* addr of last next element */     \
  315 }
  316 
  317 #define STAILQ_CLASS_HEAD(name, type)                   \
  318 struct name {                               \
  319     class type *stqh_first; /* first element */         \
  320     class type **stqh_last; /* addr of last next element */     \
  321 }
  322 
  323 #define STAILQ_HEAD_INITIALIZER(head)                   \
  324     { NULL, &(head).stqh_first }
  325 
  326 #define STAILQ_ENTRY(type)                      \
  327 struct {                                \
  328     struct type *stqe_next; /* next element */          \
  329 }
  330 
  331 #define STAILQ_CLASS_ENTRY(type)                    \
  332 struct {                                \
  333     class type *stqe_next;  /* next element */          \
  334 }
  335 
  336 /*
  337  * Singly-linked Tail queue functions.
  338  */
  339 #define STAILQ_CONCAT(head1, head2) do {                \
  340     if (!STAILQ_EMPTY((head2))) {                   \
  341         *(head1)->stqh_last = (head2)->stqh_first;      \
  342         (head1)->stqh_last = (head2)->stqh_last;        \
  343         STAILQ_INIT((head2));                   \
  344     }                               \
  345 } while (0)
  346 
  347 #define STAILQ_EMPTY(head)  ((head)->stqh_first == NULL)
  348 
  349 #define STAILQ_FIRST(head)  ((head)->stqh_first)
  350 
  351 #define STAILQ_FOREACH(var, head, field)                \
  352     for((var) = STAILQ_FIRST((head));               \
  353        (var);                           \
  354        (var) = STAILQ_NEXT((var), field))
  355 
  356 #define STAILQ_FOREACH_FROM(var, head, field)               \
  357     for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));        \
  358        (var);                           \
  359        (var) = STAILQ_NEXT((var), field))
  360 
  361 #define STAILQ_FOREACH_SAFE(var, head, field, tvar)         \
  362     for ((var) = STAILQ_FIRST((head));              \
  363         (var) && ((tvar) = STAILQ_NEXT((var), field), 1);       \
  364         (var) = (tvar))
  365 
  366 #define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)        \
  367     for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));        \
  368         (var) && ((tvar) = STAILQ_NEXT((var), field), 1);       \
  369         (var) = (tvar))
  370 
  371 #define STAILQ_INIT(head) do {                      \
  372     STAILQ_FIRST((head)) = NULL;                    \
  373     (head)->stqh_last = &STAILQ_FIRST((head));          \
  374 } while (0)
  375 
  376 #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {       \
  377     if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
  378         (head)->stqh_last = &STAILQ_NEXT((elm), field);     \
  379     STAILQ_NEXT((tqelm), field) = (elm);                \
  380 } while (0)
  381 
  382 #define STAILQ_INSERT_HEAD(head, elm, field) do {           \
  383     if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
  384         (head)->stqh_last = &STAILQ_NEXT((elm), field);     \
  385     STAILQ_FIRST((head)) = (elm);                   \
  386 } while (0)
  387 
  388 #define STAILQ_INSERT_TAIL(head, elm, field) do {           \
  389     STAILQ_NEXT((elm), field) = NULL;               \
  390     *(head)->stqh_last = (elm);                 \
  391     (head)->stqh_last = &STAILQ_NEXT((elm), field);         \
  392 } while (0)
  393 
  394 #define STAILQ_LAST(head, type, field)              \
  395     (STAILQ_EMPTY((head)) ? NULL :              \
  396         __containerof((head)->stqh_last,            \
  397         QUEUE_TYPEOF(type), field.stqe_next))
  398 
  399 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
  400 
  401 #define STAILQ_REMOVE(head, elm, type, field) do {          \
  402     QMD_SAVELINK(oldnext, (elm)->field.stqe_next);          \
  403     if (STAILQ_FIRST((head)) == (elm)) {                \
  404         STAILQ_REMOVE_HEAD((head), field);          \
  405     }                               \
  406     else {                              \
  407         QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head);    \
  408         while (STAILQ_NEXT(curelm, field) != (elm))     \
  409             curelm = STAILQ_NEXT(curelm, field);        \
  410         STAILQ_REMOVE_AFTER(head, curelm, field);       \
  411     }                               \
  412     TRASHIT(*oldnext);                      \
  413 } while (0)
  414 
  415 #define STAILQ_REMOVE_AFTER(head, elm, field) do {          \
  416     if ((STAILQ_NEXT(elm, field) =                  \
  417          STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)  \
  418         (head)->stqh_last = &STAILQ_NEXT((elm), field);     \
  419 } while (0)
  420 
  421 #define STAILQ_REMOVE_HEAD(head, field) do {                \
  422     if ((STAILQ_FIRST((head)) =                 \
  423          STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)     \
  424         (head)->stqh_last = &STAILQ_FIRST((head));      \
  425 } while (0)
  426 
  427 #define STAILQ_SWAP(head1, head2, type) do {                \
  428     QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1);       \
  429     QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last;        \
  430     STAILQ_FIRST(head1) = STAILQ_FIRST(head2);          \
  431     (head1)->stqh_last = (head2)->stqh_last;            \
  432     STAILQ_FIRST(head2) = swap_first;               \
  433     (head2)->stqh_last = swap_last;                 \
  434     if (STAILQ_EMPTY(head1))                    \
  435         (head1)->stqh_last = &STAILQ_FIRST(head1);      \
  436     if (STAILQ_EMPTY(head2))                    \
  437         (head2)->stqh_last = &STAILQ_FIRST(head2);      \
  438 } while (0)
  439 
  440 /*
  441  * List declarations.
  442  */
  443 #define LIST_HEAD(name, type)                       \
  444 struct name {                               \
  445     struct type *lh_first;  /* first element */         \
  446 }
  447 
  448 #define LIST_CLASS_HEAD(name, type)                 \
  449 struct name {                               \
  450     class type *lh_first;   /* first element */         \
  451 }
  452 
  453 #define LIST_HEAD_INITIALIZER(head)                 \
  454     { NULL }
  455 
  456 #define LIST_ENTRY(type)                        \
  457 struct {                                \
  458     struct type *le_next;   /* next element */          \
  459     struct type **le_prev;  /* address of previous next element */  \
  460 }
  461 
  462 #define LIST_CLASS_ENTRY(type)                      \
  463 struct {                                \
  464     class type *le_next;    /* next element */          \
  465     class type **le_prev;   /* address of previous next element */  \
  466 }
  467 
  468 /*
  469  * List functions.
  470  */
  471 
  472 #if (defined(_KERNEL) && defined(INVARIANTS))
  473 /*
  474  * QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME)
  475  *
  476  * If the list is non-empty, validates that the first element of the list
  477  * points back at 'head.'
  478  */
  479 #define QMD_LIST_CHECK_HEAD(head, field) do {               \
  480     if (LIST_FIRST((head)) != NULL &&               \
  481         LIST_FIRST((head))->field.le_prev !=            \
  482          &LIST_FIRST((head)))                   \
  483         panic("Bad list head %p first->prev != head", (head));  \
  484 } while (0)
  485 
  486 /*
  487  * QMD_LIST_CHECK_NEXT(TYPE *elm, LIST_ENTRY NAME)
  488  *
  489  * If an element follows 'elm' in the list, validates that the next element
  490  * points back at 'elm.'
  491  */
  492 #define QMD_LIST_CHECK_NEXT(elm, field) do {                \
  493     if (LIST_NEXT((elm), field) != NULL &&              \
  494         LIST_NEXT((elm), field)->field.le_prev !=           \
  495          &((elm)->field.le_next))                   \
  496             panic("Bad link elm %p next->prev != elm", (elm));  \
  497 } while (0)
  498 
  499 /*
  500  * QMD_LIST_CHECK_PREV(TYPE *elm, LIST_ENTRY NAME)
  501  *
  502  * Validates that the previous element (or head of the list) points to 'elm.'
  503  */
  504 #define QMD_LIST_CHECK_PREV(elm, field) do {                \
  505     if (*(elm)->field.le_prev != (elm))             \
  506         panic("Bad link elm %p prev->next != elm", (elm));  \
  507 } while (0)
  508 #else
  509 #define QMD_LIST_CHECK_HEAD(head, field)
  510 #define QMD_LIST_CHECK_NEXT(elm, field)
  511 #define QMD_LIST_CHECK_PREV(elm, field)
  512 #endif /* (_KERNEL && INVARIANTS) */
  513 
  514 #define LIST_CONCAT(head1, head2, type, field) do {               \
  515     QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1);               \
  516     if (curelm == NULL) {                             \
  517         if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) {        \
  518             LIST_FIRST(head2)->field.le_prev =            \
  519                 &LIST_FIRST((head1));                 \
  520             LIST_INIT(head2);                     \
  521         }                                 \
  522     } else if (LIST_FIRST(head2) != NULL) {                   \
  523         while (LIST_NEXT(curelm, field) != NULL)              \
  524             curelm = LIST_NEXT(curelm, field);            \
  525         LIST_NEXT(curelm, field) = LIST_FIRST(head2);             \
  526         LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \
  527         LIST_INIT(head2);                         \
  528     }                                     \
  529 } while (0)
  530 
  531 #define LIST_EMPTY(head)    ((head)->lh_first == NULL)
  532 
  533 #define LIST_FIRST(head)    ((head)->lh_first)
  534 
  535 #define LIST_FOREACH(var, head, field)                  \
  536     for ((var) = LIST_FIRST((head));                \
  537         (var);                          \
  538         (var) = LIST_NEXT((var), field))
  539 
  540 #define LIST_FOREACH_FROM(var, head, field)             \
  541     for ((var) = ((var) ? (var) : LIST_FIRST((head)));      \
  542         (var);                          \
  543         (var) = LIST_NEXT((var), field))
  544 
  545 #define LIST_FOREACH_SAFE(var, head, field, tvar)           \
  546     for ((var) = LIST_FIRST((head));                \
  547         (var) && ((tvar) = LIST_NEXT((var), field), 1);     \
  548         (var) = (tvar))
  549 
  550 #define LIST_FOREACH_FROM_SAFE(var, head, field, tvar)          \
  551     for ((var) = ((var) ? (var) : LIST_FIRST((head)));      \
  552         (var) && ((tvar) = LIST_NEXT((var), field), 1);     \
  553         (var) = (tvar))
  554 
  555 #define LIST_INIT(head) do {                        \
  556     LIST_FIRST((head)) = NULL;                  \
  557 } while (0)
  558 
  559 #define LIST_INSERT_AFTER(listelm, elm, field) do {         \
  560     QMD_LIST_CHECK_NEXT(listelm, field);                \
  561     if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
  562         LIST_NEXT((listelm), field)->field.le_prev =        \
  563             &LIST_NEXT((elm), field);               \
  564     LIST_NEXT((listelm), field) = (elm);                \
  565     (elm)->field.le_prev = &LIST_NEXT((listelm), field);        \
  566 } while (0)
  567 
  568 #define LIST_INSERT_BEFORE(listelm, elm, field) do {            \
  569     QMD_LIST_CHECK_PREV(listelm, field);                \
  570     (elm)->field.le_prev = (listelm)->field.le_prev;        \
  571     LIST_NEXT((elm), field) = (listelm);                \
  572     *(listelm)->field.le_prev = (elm);              \
  573     (listelm)->field.le_prev = &LIST_NEXT((elm), field);        \
  574 } while (0)
  575 
  576 #define LIST_INSERT_HEAD(head, elm, field) do {             \
  577     QMD_LIST_CHECK_HEAD((head), field);             \
  578     if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
  579         LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
  580     LIST_FIRST((head)) = (elm);                 \
  581     (elm)->field.le_prev = &LIST_FIRST((head));         \
  582 } while (0)
  583 
  584 #define LIST_NEXT(elm, field)   ((elm)->field.le_next)
  585 
  586 #define LIST_PREV(elm, head, type, field)           \
  587     ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL :   \
  588         __containerof((elm)->field.le_prev,         \
  589         QUEUE_TYPEOF(type), field.le_next))
  590 
  591 #define LIST_REMOVE(elm, field) do {                    \
  592     QMD_SAVELINK(oldnext, (elm)->field.le_next);            \
  593     QMD_SAVELINK(oldprev, (elm)->field.le_prev);            \
  594     QMD_LIST_CHECK_NEXT(elm, field);                \
  595     QMD_LIST_CHECK_PREV(elm, field);                \
  596     if (LIST_NEXT((elm), field) != NULL)                \
  597         LIST_NEXT((elm), field)->field.le_prev =        \
  598             (elm)->field.le_prev;               \
  599     *(elm)->field.le_prev = LIST_NEXT((elm), field);        \
  600     TRASHIT(*oldnext);                      \
  601     TRASHIT(*oldprev);                      \
  602 } while (0)
  603 
  604 #define LIST_SWAP(head1, head2, type, field) do {           \
  605     QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1);       \
  606     LIST_FIRST((head1)) = LIST_FIRST((head2));          \
  607     LIST_FIRST((head2)) = swap_tmp;                 \
  608     if ((swap_tmp = LIST_FIRST((head1))) != NULL)           \
  609         swap_tmp->field.le_prev = &LIST_FIRST((head1));     \
  610     if ((swap_tmp = LIST_FIRST((head2))) != NULL)           \
  611         swap_tmp->field.le_prev = &LIST_FIRST((head2));     \
  612 } while (0)
  613 
  614 /*
  615  * Tail queue declarations.
  616  */
  617 #define TAILQ_HEAD(name, type)                      \
  618 struct name {                               \
  619     struct type *tqh_first; /* first element */         \
  620     struct type **tqh_last; /* addr of last next element */     \
  621     TRACEBUF                            \
  622 }
  623 
  624 #define TAILQ_CLASS_HEAD(name, type)                    \
  625 struct name {                               \
  626     class type *tqh_first;  /* first element */         \
  627     class type **tqh_last;  /* addr of last next element */     \
  628     TRACEBUF                            \
  629 }
  630 
  631 #define TAILQ_HEAD_INITIALIZER(head)                    \
  632     { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
  633 
  634 #define TAILQ_ENTRY(type)                       \
  635 struct {                                \
  636     struct type *tqe_next;  /* next element */          \
  637     struct type **tqe_prev; /* address of previous next element */  \
  638     TRACEBUF                            \
  639 }
  640 
  641 #define TAILQ_CLASS_ENTRY(type)                     \
  642 struct {                                \
  643     class type *tqe_next;   /* next element */          \
  644     class type **tqe_prev;  /* address of previous next element */  \
  645     TRACEBUF                            \
  646 }
  647 
  648 /*
  649  * Tail queue functions.
  650  */
  651 #if (defined(_KERNEL) && defined(INVARIANTS))
  652 /*
  653  * QMD_TAILQ_CHECK_HEAD(TAILQ_HEAD *head, TAILQ_ENTRY NAME)
  654  *
  655  * If the tailq is non-empty, validates that the first element of the tailq
  656  * points back at 'head.'
  657  */
  658 #define QMD_TAILQ_CHECK_HEAD(head, field) do {              \
  659     if (!TAILQ_EMPTY(head) &&                   \
  660         TAILQ_FIRST((head))->field.tqe_prev !=          \
  661          &TAILQ_FIRST((head)))                  \
  662         panic("Bad tailq head %p first->prev != head", (head)); \
  663 } while (0)
  664 
  665 /*
  666  * QMD_TAILQ_CHECK_TAIL(TAILQ_HEAD *head, TAILQ_ENTRY NAME)
  667  *
  668  * Validates that the tail of the tailq is a pointer to pointer to NULL.
  669  */
  670 #define QMD_TAILQ_CHECK_TAIL(head, field) do {              \
  671     if (*(head)->tqh_last != NULL)                  \
  672             panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head));  \
  673 } while (0)
  674 
  675 /*
  676  * QMD_TAILQ_CHECK_NEXT(TYPE *elm, TAILQ_ENTRY NAME)
  677  *
  678  * If an element follows 'elm' in the tailq, validates that the next element
  679  * points back at 'elm.'
  680  */
  681 #define QMD_TAILQ_CHECK_NEXT(elm, field) do {               \
  682     if (TAILQ_NEXT((elm), field) != NULL &&             \
  683         TAILQ_NEXT((elm), field)->field.tqe_prev !=         \
  684          &((elm)->field.tqe_next))                  \
  685         panic("Bad link elm %p next->prev != elm", (elm));  \
  686 } while (0)
  687 
  688 /*
  689  * QMD_TAILQ_CHECK_PREV(TYPE *elm, TAILQ_ENTRY NAME)
  690  *
  691  * Validates that the previous element (or head of the tailq) points to 'elm.'
  692  */
  693 #define QMD_TAILQ_CHECK_PREV(elm, field) do {               \
  694     if (*(elm)->field.tqe_prev != (elm))                \
  695         panic("Bad link elm %p prev->next != elm", (elm));  \
  696 } while (0)
  697 #else
  698 #define QMD_TAILQ_CHECK_HEAD(head, field)
  699 #define QMD_TAILQ_CHECK_TAIL(head, headname)
  700 #define QMD_TAILQ_CHECK_NEXT(elm, field)
  701 #define QMD_TAILQ_CHECK_PREV(elm, field)
  702 #endif /* (_KERNEL && INVARIANTS) */
  703 
  704 #define TAILQ_CONCAT(head1, head2, field) do {              \
  705     if (!TAILQ_EMPTY(head2)) {                  \
  706         *(head1)->tqh_last = (head2)->tqh_first;        \
  707         (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
  708         (head1)->tqh_last = (head2)->tqh_last;          \
  709         TAILQ_INIT((head2));                    \
  710         QMD_TRACE_HEAD(head1);                  \
  711         QMD_TRACE_HEAD(head2);                  \
  712     }                               \
  713 } while (0)
  714 
  715 #define TAILQ_EMPTY(head)   ((head)->tqh_first == NULL)
  716 
  717 #define TAILQ_FIRST(head)   ((head)->tqh_first)
  718 
  719 #define TAILQ_FOREACH(var, head, field)                 \
  720     for ((var) = TAILQ_FIRST((head));               \
  721         (var);                          \
  722         (var) = TAILQ_NEXT((var), field))
  723 
  724 #define TAILQ_FOREACH_FROM(var, head, field)                \
  725     for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));     \
  726         (var);                          \
  727         (var) = TAILQ_NEXT((var), field))
  728 
  729 #define TAILQ_FOREACH_SAFE(var, head, field, tvar)          \
  730     for ((var) = TAILQ_FIRST((head));               \
  731         (var) && ((tvar) = TAILQ_NEXT((var), field), 1);        \
  732         (var) = (tvar))
  733 
  734 #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)         \
  735     for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));     \
  736         (var) && ((tvar) = TAILQ_NEXT((var), field), 1);        \
  737         (var) = (tvar))
  738 
  739 #define TAILQ_FOREACH_REVERSE(var, head, headname, field)       \
  740     for ((var) = TAILQ_LAST((head), headname);          \
  741         (var);                          \
  742         (var) = TAILQ_PREV((var), headname, field))
  743 
  744 #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field)      \
  745     for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));    \
  746         (var);                          \
  747         (var) = TAILQ_PREV((var), headname, field))
  748 
  749 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)    \
  750     for ((var) = TAILQ_LAST((head), headname);          \
  751         (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);  \
  752         (var) = (tvar))
  753 
  754 #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
  755     for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));    \
  756         (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);  \
  757         (var) = (tvar))
  758 
  759 #define TAILQ_INIT(head) do {                       \
  760     TAILQ_FIRST((head)) = NULL;                 \
  761     (head)->tqh_last = &TAILQ_FIRST((head));            \
  762     QMD_TRACE_HEAD(head);                       \
  763 } while (0)
  764 
  765 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {      \
  766     QMD_TAILQ_CHECK_NEXT(listelm, field);               \
  767     if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
  768         TAILQ_NEXT((elm), field)->field.tqe_prev =      \
  769             &TAILQ_NEXT((elm), field);              \
  770     else {                              \
  771         (head)->tqh_last = &TAILQ_NEXT((elm), field);       \
  772         QMD_TRACE_HEAD(head);                   \
  773     }                               \
  774     TAILQ_NEXT((listelm), field) = (elm);               \
  775     (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);      \
  776     QMD_TRACE_ELEM(&(elm)->field);                  \
  777     QMD_TRACE_ELEM(&(listelm)->field);              \
  778 } while (0)
  779 
  780 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {           \
  781     QMD_TAILQ_CHECK_PREV(listelm, field);               \
  782     (elm)->field.tqe_prev = (listelm)->field.tqe_prev;      \
  783     TAILQ_NEXT((elm), field) = (listelm);               \
  784     *(listelm)->field.tqe_prev = (elm);             \
  785     (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);      \
  786     QMD_TRACE_ELEM(&(elm)->field);                  \
  787     QMD_TRACE_ELEM(&(listelm)->field);              \
  788 } while (0)
  789 
  790 #define TAILQ_INSERT_HEAD(head, elm, field) do {            \
  791     QMD_TAILQ_CHECK_HEAD(head, field);              \
  792     if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)   \
  793         TAILQ_FIRST((head))->field.tqe_prev =           \
  794             &TAILQ_NEXT((elm), field);              \
  795     else                                \
  796         (head)->tqh_last = &TAILQ_NEXT((elm), field);       \
  797     TAILQ_FIRST((head)) = (elm);                    \
  798     (elm)->field.tqe_prev = &TAILQ_FIRST((head));           \
  799     QMD_TRACE_HEAD(head);                       \
  800     QMD_TRACE_ELEM(&(elm)->field);                  \
  801 } while (0)
  802 
  803 #define TAILQ_INSERT_TAIL(head, elm, field) do {            \
  804     QMD_TAILQ_CHECK_TAIL(head, field);              \
  805     TAILQ_NEXT((elm), field) = NULL;                \
  806     (elm)->field.tqe_prev = (head)->tqh_last;           \
  807     *(head)->tqh_last = (elm);                  \
  808     (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
  809     QMD_TRACE_HEAD(head);                       \
  810     QMD_TRACE_ELEM(&(elm)->field);                  \
  811 } while (0)
  812 
  813 #define TAILQ_LAST(head, headname)                  \
  814     (*(((struct headname *)((head)->tqh_last))->tqh_last))
  815 
  816 /*
  817  * The FAST function is fast in that it causes no data access other
  818  * then the access to the head. The standard LAST function above
  819  * will cause a data access of both the element you want and
  820  * the previous element. FAST is very useful for instances when
  821  * you may want to prefetch the last data element.
  822  */
  823 #define TAILQ_LAST_FAST(head, type, field)          \
  824     (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, QUEUE_TYPEOF(type), field.tqe_next))
  825 
  826 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
  827 
  828 #define TAILQ_PREV(elm, headname, field)                \
  829     (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
  830 
  831 #define TAILQ_PREV_FAST(elm, head, type, field)             \
  832     ((elm)->field.tqe_prev == &(head)->tqh_first ? NULL :       \
  833      __containerof((elm)->field.tqe_prev, QUEUE_TYPEOF(type), field.tqe_next))
  834 
  835 #define TAILQ_REMOVE(head, elm, field) do {             \
  836     QMD_SAVELINK(oldnext, (elm)->field.tqe_next);           \
  837     QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);           \
  838     QMD_TAILQ_CHECK_NEXT(elm, field);               \
  839     QMD_TAILQ_CHECK_PREV(elm, field);               \
  840     if ((TAILQ_NEXT((elm), field)) != NULL)             \
  841         TAILQ_NEXT((elm), field)->field.tqe_prev =      \
  842             (elm)->field.tqe_prev;              \
  843     else {                              \
  844         (head)->tqh_last = (elm)->field.tqe_prev;       \
  845         QMD_TRACE_HEAD(head);                   \
  846     }                               \
  847     *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);      \
  848     TRASHIT(*oldnext);                      \
  849     TRASHIT(*oldprev);                      \
  850     QMD_TRACE_ELEM(&(elm)->field);                  \
  851 } while (0)
  852 
  853 #define TAILQ_SWAP(head1, head2, type, field) do {          \
  854     QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first;        \
  855     QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last;     \
  856     (head1)->tqh_first = (head2)->tqh_first;            \
  857     (head1)->tqh_last = (head2)->tqh_last;              \
  858     (head2)->tqh_first = swap_first;                \
  859     (head2)->tqh_last = swap_last;                  \
  860     if ((swap_first = (head1)->tqh_first) != NULL)          \
  861         swap_first->field.tqe_prev = &(head1)->tqh_first;   \
  862     else                                \
  863         (head1)->tqh_last = &(head1)->tqh_first;        \
  864     if ((swap_first = (head2)->tqh_first) != NULL)          \
  865         swap_first->field.tqe_prev = &(head2)->tqh_first;   \
  866     else                                \
  867         (head2)->tqh_last = &(head2)->tqh_first;        \
  868 } while (0)
  869 
  870 #endif /* !_SYS_QUEUE_H_ */