File:  [Qemu by Fabrice Bellard] / qemu / sys-queue.h
Revision 1.1.1.1 (vendor branch): download - view: text, annotated - select for diffs
Tue Apr 24 16:50:26 2018 UTC (3 years, 2 months ago) by root
Branches: qemu, MAIN
CVS tags: qemu0111, qemu0110, qemu0105, qemu0104, qemu0103, qemu0102, qemu0101, qemu0100, HEAD
qemu 0.10.0

    1: /*      $NetBSD: queue.h,v 1.45.14.1 2007/07/18 20:13:24 liamjfoy Exp $ */
    2: 
    3: /*
    4:  * Qemu version: Copy from netbsd, removed debug code, removed some of
    5:  * the implementations.  Left in lists, tail queues and circular queues.
    6:  */
    7: 
    8: /*
    9:  * Copyright (c) 1991, 1993
   10:  *      The Regents of the University of California.  All rights reserved.
   11:  *
   12:  * Redistribution and use in source and binary forms, with or without
   13:  * modification, are permitted provided that the following conditions
   14:  * are met:
   15:  * 1. Redistributions of source code must retain the above copyright
   16:  *    notice, this list of conditions and the following disclaimer.
   17:  * 2. Redistributions in binary form must reproduce the above copyright
   18:  *    notice, this list of conditions and the following disclaimer in the
   19:  *    documentation and/or other materials provided with the distribution.
   20:  * 3. Neither the name of the University nor the names of its contributors
   21:  *    may be used to endorse or promote products derived from this software
   22:  *    without specific prior written permission.
   23:  *
   24:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   25:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   26:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   27:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   28:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   29:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   30:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   31:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   32:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   33:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   34:  * SUCH DAMAGE.
   35:  *
   36:  *      @(#)queue.h     8.5 (Berkeley) 8/20/94
   37:  */
   38: 
   39: #ifndef _SYS_QUEUE_H_
   40: #define _SYS_QUEUE_H_
   41: 
   42: /*
   43:  * This file defines three types of data structures:
   44:  * lists, tail queues, and circular queues.
   45:  *
   46:  * A list is headed by a single forward pointer (or an array of forward
   47:  * pointers for a hash table header). The elements are doubly linked
   48:  * so that an arbitrary element can be removed without a need to
   49:  * traverse the list. New elements can be added to the list before
   50:  * or after an existing element or at the head of the list. A list
   51:  * may only be traversed in the forward direction.
   52:  *
   53:  * A tail queue is headed by a pair of pointers, one to the head of the
   54:  * list and the other to the tail of the list. The elements are doubly
   55:  * linked so that an arbitrary element can be removed without a need to
   56:  * traverse the list. New elements can be added to the list before or
   57:  * after an existing element, at the head of the list, or at the end of
   58:  * the list. A tail queue may be traversed in either direction.
   59:  *
   60:  * A circle queue is headed by a pair of pointers, one to the head of the
   61:  * list and the other to the tail of the list. The elements are doubly
   62:  * linked so that an arbitrary element can be removed without a need to
   63:  * traverse the list. New elements can be added to the list before or after
   64:  * an existing element, at the head of the list, or at the end of the list.
   65:  * A circle queue may be traversed in either direction, but has a more
   66:  * complex end of list detection.
   67:  *
   68:  * For details on the use of these macros, see the queue(3) manual page.
   69:  */
   70: 
   71: /*
   72:  * List definitions.
   73:  */
   74: #define LIST_HEAD(name, type)                                           \
   75: struct name {                                                           \
   76:         struct type *lh_first;  /* first element */                     \
   77: }
   78: 
   79: #define LIST_HEAD_INITIALIZER(head)                                     \
   80:         { NULL }
   81: 
   82: #define LIST_ENTRY(type)                                                \
   83: struct {                                                                \
   84:         struct type *le_next;   /* next element */                      \
   85:         struct type **le_prev;  /* address of previous next element */  \
   86: }
   87: 
   88: /*
   89:  * List functions.
   90:  */
   91: #define LIST_INIT(head) do {                                            \
   92:         (head)->lh_first = NULL;                                        \
   93: } while (/*CONSTCOND*/0)
   94: 
   95: #define LIST_INSERT_AFTER(listelm, elm, field) do {                     \
   96:         if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)  \
   97:                 (listelm)->field.le_next->field.le_prev =               \
   98:                     &(elm)->field.le_next;                              \
   99:         (listelm)->field.le_next = (elm);                               \
  100:         (elm)->field.le_prev = &(listelm)->field.le_next;               \
  101: } while (/*CONSTCOND*/0)
  102: 
  103: #define LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
  104:         (elm)->field.le_prev = (listelm)->field.le_prev;                \
  105:         (elm)->field.le_next = (listelm);                               \
  106:         *(listelm)->field.le_prev = (elm);                              \
  107:         (listelm)->field.le_prev = &(elm)->field.le_next;               \
  108: } while (/*CONSTCOND*/0)
  109: 
  110: #define LIST_INSERT_HEAD(head, elm, field) do {                         \
  111:         if (((elm)->field.le_next = (head)->lh_first) != NULL)          \
  112:                 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
  113:         (head)->lh_first = (elm);                                       \
  114:         (elm)->field.le_prev = &(head)->lh_first;                       \
  115: } while (/*CONSTCOND*/0)
  116: 
  117: #define LIST_REMOVE(elm, field) do {                                    \
  118:         if ((elm)->field.le_next != NULL)                               \
  119:                 (elm)->field.le_next->field.le_prev =                   \
  120:                     (elm)->field.le_prev;                               \
  121:         *(elm)->field.le_prev = (elm)->field.le_next;                   \
  122: } while (/*CONSTCOND*/0)
  123: 
  124: #define LIST_FOREACH(var, head, field)                                  \
  125:         for ((var) = ((head)->lh_first);                                \
  126:                 (var);                                                  \
  127:                 (var) = ((var)->field.le_next))
  128: 
  129: /*
  130:  * List access methods.
  131:  */
  132: #define LIST_EMPTY(head)                ((head)->lh_first == NULL)
  133: #define LIST_FIRST(head)                ((head)->lh_first)
  134: #define LIST_NEXT(elm, field)           ((elm)->field.le_next)
  135: 
  136: 
  137: /*
  138:  * Tail queue definitions.
  139:  */
  140: #define _TAILQ_HEAD(name, type, qual)                                   \
  141: struct name {                                                           \
  142:         qual type *tqh_first;           /* first element */             \
  143:         qual type *qual *tqh_last;      /* addr of last next element */ \
  144: }
  145: #define TAILQ_HEAD(name, type)  _TAILQ_HEAD(name, struct type,)
  146: 
  147: #define TAILQ_HEAD_INITIALIZER(head)                                    \
  148:         { NULL, &(head).tqh_first }
  149: 
  150: #define _TAILQ_ENTRY(type, qual)                                        \
  151: struct {                                                                \
  152:         qual type *tqe_next;            /* next element */              \
  153:         qual type *qual *tqe_prev;      /* address of previous next element */\
  154: }
  155: #define TAILQ_ENTRY(type)       _TAILQ_ENTRY(struct type,)
  156: 
  157: /*
  158:  * Tail queue functions.
  159:  */
  160: #define TAILQ_INIT(head) do {                                           \
  161:         (head)->tqh_first = NULL;                                       \
  162:         (head)->tqh_last = &(head)->tqh_first;                          \
  163: } while (/*CONSTCOND*/0)
  164: 
  165: #define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
  166:         if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
  167:                 (head)->tqh_first->field.tqe_prev =                     \
  168:                     &(elm)->field.tqe_next;                             \
  169:         else                                                            \
  170:                 (head)->tqh_last = &(elm)->field.tqe_next;              \
  171:         (head)->tqh_first = (elm);                                      \
  172:         (elm)->field.tqe_prev = &(head)->tqh_first;                     \
  173: } while (/*CONSTCOND*/0)
  174: 
  175: #define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
  176:         (elm)->field.tqe_next = NULL;                                   \
  177:         (elm)->field.tqe_prev = (head)->tqh_last;                       \
  178:         *(head)->tqh_last = (elm);                                      \
  179:         (head)->tqh_last = &(elm)->field.tqe_next;                      \
  180: } while (/*CONSTCOND*/0)
  181: 
  182: #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
  183:         if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
  184:                 (elm)->field.tqe_next->field.tqe_prev =                 \
  185:                     &(elm)->field.tqe_next;                             \
  186:         else                                                            \
  187:                 (head)->tqh_last = &(elm)->field.tqe_next;              \
  188:         (listelm)->field.tqe_next = (elm);                              \
  189:         (elm)->field.tqe_prev = &(listelm)->field.tqe_next;             \
  190: } while (/*CONSTCOND*/0)
  191: 
  192: #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
  193:         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
  194:         (elm)->field.tqe_next = (listelm);                              \
  195:         *(listelm)->field.tqe_prev = (elm);                             \
  196:         (listelm)->field.tqe_prev = &(elm)->field.tqe_next;             \
  197: } while (/*CONSTCOND*/0)
  198: 
  199: #define TAILQ_REMOVE(head, elm, field) do {                             \
  200:         if (((elm)->field.tqe_next) != NULL)                            \
  201:                 (elm)->field.tqe_next->field.tqe_prev =                 \
  202:                     (elm)->field.tqe_prev;                              \
  203:         else                                                            \
  204:                 (head)->tqh_last = (elm)->field.tqe_prev;               \
  205:         *(elm)->field.tqe_prev = (elm)->field.tqe_next;                 \
  206: } while (/*CONSTCOND*/0)
  207: 
  208: #define TAILQ_FOREACH(var, head, field)                                 \
  209:         for ((var) = ((head)->tqh_first);                               \
  210:                 (var);                                                  \
  211:                 (var) = ((var)->field.tqe_next))
  212: 
  213: #define TAILQ_FOREACH_SAFE(var, head, field, next_var)                  \
  214:         for ((var) = ((head)->tqh_first);                               \
  215:                 (var) && ((next_var) = ((var)->field.tqe_next), 1);     \
  216:                 (var) = (next_var))
  217: 
  218: #define TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
  219:         for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));    \
  220:                 (var);                                                  \
  221:                 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
  222: 
  223: /*
  224:  * Tail queue access methods.
  225:  */
  226: #define TAILQ_EMPTY(head)               ((head)->tqh_first == NULL)
  227: #define TAILQ_FIRST(head)               ((head)->tqh_first)
  228: #define TAILQ_NEXT(elm, field)          ((elm)->field.tqe_next)
  229: 
  230: #define TAILQ_LAST(head, headname) \
  231:         (*(((struct headname *)((head)->tqh_last))->tqh_last))
  232: #define TAILQ_PREV(elm, headname, field) \
  233:         (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
  234: 
  235: 
  236: /*
  237:  * Circular queue definitions.
  238:  */
  239: #define CIRCLEQ_HEAD(name, type)                                        \
  240: struct name {                                                           \
  241:         struct type *cqh_first;         /* first element */             \
  242:         struct type *cqh_last;          /* last element */              \
  243: }
  244: 
  245: #define CIRCLEQ_HEAD_INITIALIZER(head)                                  \
  246:         { (void *)&head, (void *)&head }
  247: 
  248: #define CIRCLEQ_ENTRY(type)                                             \
  249: struct {                                                                \
  250:         struct type *cqe_next;          /* next element */              \
  251:         struct type *cqe_prev;          /* previous element */          \
  252: }
  253: 
  254: /*
  255:  * Circular queue functions.
  256:  */
  257: #define CIRCLEQ_INIT(head) do {                                         \
  258:         (head)->cqh_first = (void *)(head);                             \
  259:         (head)->cqh_last = (void *)(head);                              \
  260: } while (/*CONSTCOND*/0)
  261: 
  262: #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
  263:         (elm)->field.cqe_next = (listelm)->field.cqe_next;              \
  264:         (elm)->field.cqe_prev = (listelm);                              \
  265:         if ((listelm)->field.cqe_next == (void *)(head))                \
  266:                 (head)->cqh_last = (elm);                               \
  267:         else                                                            \
  268:                 (listelm)->field.cqe_next->field.cqe_prev = (elm);      \
  269:         (listelm)->field.cqe_next = (elm);                              \
  270: } while (/*CONSTCOND*/0)
  271: 
  272: #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {           \
  273:         (elm)->field.cqe_next = (listelm);                              \
  274:         (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \
  275:         if ((listelm)->field.cqe_prev == (void *)(head))                \
  276:                 (head)->cqh_first = (elm);                              \
  277:         else                                                            \
  278:                 (listelm)->field.cqe_prev->field.cqe_next = (elm);      \
  279:         (listelm)->field.cqe_prev = (elm);                              \
  280: } while (/*CONSTCOND*/0)
  281: 
  282: #define CIRCLEQ_INSERT_HEAD(head, elm, field) do {                      \
  283:         (elm)->field.cqe_next = (head)->cqh_first;                      \
  284:         (elm)->field.cqe_prev = (void *)(head);                         \
  285:         if ((head)->cqh_last == (void *)(head))                         \
  286:                 (head)->cqh_last = (elm);                               \
  287:         else                                                            \
  288:                 (head)->cqh_first->field.cqe_prev = (elm);              \
  289:         (head)->cqh_first = (elm);                                      \
  290: } while (/*CONSTCOND*/0)
  291: 
  292: #define CIRCLEQ_INSERT_TAIL(head, elm, field) do {                      \
  293:         (elm)->field.cqe_next = (void *)(head);                         \
  294:         (elm)->field.cqe_prev = (head)->cqh_last;                       \
  295:         if ((head)->cqh_first == (void *)(head))                        \
  296:                 (head)->cqh_first = (elm);                              \
  297:         else                                                            \
  298:                 (head)->cqh_last->field.cqe_next = (elm);               \
  299:         (head)->cqh_last = (elm);                                       \
  300: } while (/*CONSTCOND*/0)
  301: 
  302: #define CIRCLEQ_REMOVE(head, elm, field) do {                           \
  303:         if ((elm)->field.cqe_next == (void *)(head))                    \
  304:                 (head)->cqh_last = (elm)->field.cqe_prev;               \
  305:         else                                                            \
  306:                 (elm)->field.cqe_next->field.cqe_prev =                 \
  307:                     (elm)->field.cqe_prev;                              \
  308:         if ((elm)->field.cqe_prev == (void *)(head))                    \
  309:                 (head)->cqh_first = (elm)->field.cqe_next;              \
  310:         else                                                            \
  311:                 (elm)->field.cqe_prev->field.cqe_next =                 \
  312:                     (elm)->field.cqe_next;                              \
  313: } while (/*CONSTCOND*/0)
  314: 
  315: #define CIRCLEQ_FOREACH(var, head, field)                               \
  316:         for ((var) = ((head)->cqh_first);                               \
  317:                 (var) != (const void *)(head);                          \
  318:                 (var) = ((var)->field.cqe_next))
  319: 
  320: #define CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \
  321:         for ((var) = ((head)->cqh_last);                                \
  322:                 (var) != (const void *)(head);                          \
  323:                 (var) = ((var)->field.cqe_prev))
  324: 
  325: /*
  326:  * Circular queue access methods.
  327:  */
  328: #define CIRCLEQ_EMPTY(head)             ((head)->cqh_first == (void *)(head))
  329: #define CIRCLEQ_FIRST(head)             ((head)->cqh_first)
  330: #define CIRCLEQ_LAST(head)              ((head)->cqh_last)
  331: #define CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)
  332: #define CIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)
  333: 
  334: #define CIRCLEQ_LOOP_NEXT(head, elm, field)                             \
  335:         (((elm)->field.cqe_next == (void *)(head))                      \
  336:             ? ((head)->cqh_first)                                       \
  337:             : (elm->field.cqe_next))
  338: #define CIRCLEQ_LOOP_PREV(head, elm, field)                             \
  339:         (((elm)->field.cqe_prev == (void *)(head))                      \
  340:             ? ((head)->cqh_last)                                        \
  341:             : (elm->field.cqe_prev))
  342: 
  343: #endif  /* !_SYS_QUEUE_H_ */

unix.superglobalmegacorp.com