1: /*
    2:  * Copyright (c) 1991, 1993
    3:  *      The Regents of the University of California.  All rights reserved.
    4:  *
    5:  * Redistribution and use in source and binary forms, with or without
    6:  * modification, are permitted provided that the following conditions
    7:  * are met:
    8:  * 1. Redistributions of source code must retain the above copyright
    9:  *    notice, this list of conditions and the following disclaimer.
   10:  * 2. Redistributions in binary form must reproduce the above copyright
   11:  *    notice, this list of conditions and the following disclaimer in the
   12:  *    documentation and/or other materials provided with the distribution.
   13:  * 4. Neither the name of the University nor the names of its contributors
   14:  *    may be used to endorse or promote products derived from this software
   15:  *    without specific prior written permission.
   16:  *
   17:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   18:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   19:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   20:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   21:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   22:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   23:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   24:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   25:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   26:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   27:  * SUCH DAMAGE.
   28:  *
   29:  *      @(#)queue.h  8.3 (Berkeley) 12/13/93
   30:  */
   31: 
   32: #ifndef _SYS_QUEUE_H
   33: #define _SYS_QUEUE_H 1
   34: 
   35: /*
   36:  * This file defines three types of data structures: lists, tail queues,
   37:  * and circular queues.
   38:  *
   39:  * A list is headed by a single forward pointer (or an array of forward
   40:  * pointers for a hash table header). The elements are doubly linked
   41:  * so that an arbitrary element can be removed without a need to
   42:  * traverse the list. New elements can be added to the list after
   43:  * an existing element or at the head of the list. A list may only be
   44:  * traversed in the forward direction.
   45:  *
   46:  * A tail queue is headed by a pair of pointers, one to the head of the
   47:  * list and the other to the tail of the list. The elements are doubly
   48:  * linked so that an arbitrary element can be removed without a need to
   49:  * traverse the list. New elements can be added to the list after
   50:  * an existing element, at the head of the list, or at the end of the
   51:  * list. A tail queue may only be traversed in the forward direction.
   52:  *
   53:  * A circle 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 after
   57:  * an existing element, at the head of the list, or at the end of the list.
   58:  * A circle queue may be traversed in either direction, but has a more
   59:  * complex end of list detection.
   60:  *
   61:  * For details on the use of these macros, see the queue(3) manual page.
   62:  */
   63: 
   64: /*
   65:  * List definitions.
   66:  */
   67: #define LIST_HEAD(name, type)                                           \
   68: struct name {                                                           \
   69:         struct type *lh_first; /* first element */                     \
   70: }
   71: 
   72: #define LIST_ENTRY(type)                                                \
   73: struct {                                                                \
   74:         struct type *le_next;  /* next element */                       \
   75:         struct type **le_prev; /* address of previous next element */  \
   76: }
   77: 
   78: /*
   79:  * List functions.
   80:  */
   81: #define LIST_INIT(head) {                                               \
   82:         (head)->lh_first = NULL;                                       \
   83: }
   84: 
   85: #define LIST_INSERT_AFTER(listelm, elm, field) {                        \
   86:         if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
   87:                 (listelm)->field.le_next->field.le_prev =             \
   88:                     &(elm)->field.le_next;                            \
   89:         (listelm)->field.le_next = (elm);                              \
   90:         (elm)->field.le_prev = &(listelm)->field.le_next;              \
   91: }
   92: 
   93: #define LIST_INSERT_HEAD(head, elm, field) {                            \
   94:         if (((elm)->field.le_next = (head)->lh_first) != NULL)         \
   95:                 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
   96:         (head)->lh_first = (elm);                                      \
   97:         (elm)->field.le_prev = &(head)->lh_first;                      \
   98: }
   99: 
  100: #define LIST_REMOVE(elm, field) {                                       \
  101:         if ((elm)->field.le_next != NULL)                              \
  102:                 (elm)->field.le_next->field.le_prev =                         \
  103:                     (elm)->field.le_prev;                             \
  104:         *(elm)->field.le_prev = (elm)->field.le_next;                  \
  105: }
  106: 
  107: /*
  108:  * Tail queue definitions.
  109:  */
  110: #define TAILQ_HEAD(name, type)                                          \
  111: struct name {                                                           \
  112:         struct type *tqh_first;        /* first element */                    \
  113:         struct type **tqh_last;        /* addr of last next element */                \
  114: }
  115: 
  116: #define TAILQ_ENTRY(type)                                               \
  117: struct {                                                                \
  118:         struct type *tqe_next; /* next element */                      \
  119:         struct type **tqe_prev;        /* address of previous next element */ \
  120: }
  121: 
  122: /*
  123:  * Tail queue functions.
  124:  */
  125: #define TAILQ_INIT(head) {                                              \
  126:         (head)->tqh_first = NULL;                                      \
  127:         (head)->tqh_last = &(head)->tqh_first;                         \
  128: }
  129: 
  130: #define TAILQ_INSERT_HEAD(head, elm, field) {                           \
  131:         if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)       \
  132:                 (elm)->field.tqe_next->field.tqe_prev =                       \
  133:                     &(elm)->field.tqe_next;                           \
  134:         else                                                           \
  135:                 (head)->tqh_last = &(elm)->field.tqe_next;            \
  136:         (head)->tqh_first = (elm);                                     \
  137:         (elm)->field.tqe_prev = &(head)->tqh_first;                    \
  138: }
  139: 
  140: #define TAILQ_INSERT_TAIL(head, elm, field) {                           \
  141:         (elm)->field.tqe_next = NULL;                                  \
  142:         (elm)->field.tqe_prev = (head)->tqh_last;                      \
  143:         *(head)->tqh_last = (elm);                                     \
  144:         (head)->tqh_last = &(elm)->field.tqe_next;                     \
  145: }
  146: 
  147: #define TAILQ_INSERT_AFTER(head, listelm, elm, field) {                 \
  148:         if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
  149:                 (elm)->field.tqe_next->field.tqe_prev =               \
  150:                     &(elm)->field.tqe_next;                           \
  151:         else                                                           \
  152:                 (head)->tqh_last = &(elm)->field.tqe_next;            \
  153:         (listelm)->field.tqe_next = (elm);                             \
  154:         (elm)->field.tqe_prev = &(listelm)->field.tqe_next;            \
  155: }
  156: 
  157: #define TAILQ_REMOVE(head, elm, field) {                                \
  158:         if (((elm)->field.tqe_next) != NULL)                           \
  159:                 (elm)->field.tqe_next->field.tqe_prev =               \
  160:                     (elm)->field.tqe_prev;                            \
  161:         else                                                           \
  162:                 (head)->tqh_last = (elm)->field.tqe_prev;             \
  163:         *(elm)->field.tqe_prev = (elm)->field.tqe_next;                        \
  164: }
  165: 
  166: /*
  167:  * Circular queue definitions.
  168:  */
  169: #define CIRCLEQ_HEAD(name, type)                                        \
  170: struct name {                                                           \
  171:         struct type *cqh_first;                /* first element */           \
  172:         struct type *cqh_last;         /* last element */             \
  173: }
  174: 
  175: #define CIRCLEQ_ENTRY(type)                                             \
  176: struct {                                                                \
  177:         struct type *cqe_next;         /* next element */             \
  178:         struct type *cqe_prev;         /* previous element */         \
  179: }
  180: 
  181: /*
  182:  * Circular queue functions.
  183:  */
  184: #define CIRCLEQ_INIT(head) {                                            \
  185:         (head)->cqh_first = (void *)(head);                            \
  186:         (head)->cqh_last = (void *)(head);                             \
  187: }
  188: 
  189: #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) {               \
  190:         (elm)->field.cqe_next = (listelm)->field.cqe_next;             \
  191:         (elm)->field.cqe_prev = (listelm);                             \
  192:         if ((listelm)->field.cqe_next == (void *)(head))               \
  193:                 (head)->cqh_last = (elm);                             \
  194:         else                                                           \
  195:                 (listelm)->field.cqe_next->field.cqe_prev = (elm);    \
  196:         (listelm)->field.cqe_next = (elm);                             \
  197: }
  198: 
  199: #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) {              \
  200:         (elm)->field.cqe_next = (listelm);                             \
  201:         (elm)->field.cqe_prev = (listelm)->field.cqe_prev;             \
  202:         if ((listelm)->field.cqe_prev == (void *)(head))               \
  203:                 (head)->cqh_first = (elm);                            \
  204:         else                                                           \
  205:                 (listelm)->field.cqe_prev->field.cqe_next = (elm);    \
  206:         (listelm)->field.cqe_prev = (elm);                             \
  207: }
  208: 
  209: #define CIRCLEQ_INSERT_HEAD(head, elm, field) {                         \
  210:         (elm)->field.cqe_next = (head)->cqh_first;                     \
  211:         (elm)->field.cqe_prev = (void *)(head);                                \
  212:         if ((head)->cqh_last == (void *)(head))                                \
  213:                 (head)->cqh_last = (elm);                             \
  214:         else                                                           \
  215:                 (head)->cqh_first->field.cqe_prev = (elm);            \
  216:         (head)->cqh_first = (elm);                                     \
  217: }
  218: 
  219: #define CIRCLEQ_INSERT_TAIL(head, elm, field) {                         \
  220:         (elm)->field.cqe_next = (void *)(head);                                \
  221:         (elm)->field.cqe_prev = (head)->cqh_last;                      \
  222:         if ((head)->cqh_first == (void *)(head))                       \
  223:                 (head)->cqh_first = (elm);                            \
  224:         else                                                           \
  225:                 (head)->cqh_last->field.cqe_next = (elm);             \
  226:         (head)->cqh_last = (elm);                                      \
  227: }
  228: 
  229: #define CIRCLEQ_REMOVE(head, elm, field) {                              \
  230:         if ((elm)->field.cqe_next == (void *)(head))                   \
  231:                 (head)->cqh_last = (elm)->field.cqe_prev;             \
  232:         else                                                           \
  233:                 (elm)->field.cqe_next->field.cqe_prev =                       \
  234:                     (elm)->field.cqe_prev;                            \
  235:         if ((elm)->field.cqe_prev == (void *)(head))                   \
  236:                 (head)->cqh_first = (elm)->field.cqe_next;            \
  237:         else                                                           \
  238:                 (elm)->field.cqe_prev->field.cqe_next =                       \
  239:                     (elm)->field.cqe_next;                            \
  240: }
  241: #endif  /* sys/queue.h */