Back to index

lightning-sunbird  0.9+nobinonly
queue.h
Go to the documentation of this file.
00001 /* 
00002  * Copyright (c) 1991, 1993
00003  *     The Regents of the University of California.  All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  * 1. Redistributions of source code must retain the above copyright
00009  *    notice, this list of conditions and the following disclaimer.
00010  * 2. Redistributions in binary form must reproduce the above copyright
00011  *    notice, this list of conditions and the following disclaimer in the
00012  *    documentation and/or other materials provided with the distribution.
00013  * 3. ***REMOVED*** - see 
00014  *    ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
00015  * 4. Neither the name of the University nor the names of its contributors
00016  *    may be used to endorse or promote products derived from this software
00017  *    without specific prior written permission.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00020  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00021  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00022  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00023  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00024  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00025  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00026  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00027  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00028  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00029  * SUCH DAMAGE.
00030  *
00031  *     @(#)queue.h   8.3 (Berkeley) 12/13/93
00032  */
00033 
00034 #ifndef       _QUEUE_H_
00035 #define       _QUEUE_H_
00036 
00037 /*
00038  * This file defines three types of data structures: lists, tail queues,
00039  * and circular queues.
00040  *
00041  * A list is headed by a single forward pointer (or an array of forward
00042  * pointers for a hash table header). The elements are doubly linked
00043  * so that an arbitrary element can be removed without a need to
00044  * traverse the list. New elements can be added to the list after
00045  * an existing element or at the head of the list. A list may only be
00046  * traversed in the forward direction.
00047  *
00048  * A tail queue is headed by a pair of pointers, one to the head of the
00049  * list and the other to the tail of the list. The elements are doubly
00050  * linked so that an arbitrary element can be removed without a need to
00051  * traverse the list. New elements can be added to the list after
00052  * an existing element, at the head of the list, or at the end of the
00053  * list. A tail queue may only be traversed in the forward direction.
00054  *
00055  * A circle queue is headed by a pair of pointers, one to the head of the
00056  * list and the other to the tail of the list. The elements are doubly
00057  * linked so that an arbitrary element can be removed without a need to
00058  * traverse the list. New elements can be added to the list before or after
00059  * an existing element, at the head of the list, or at the end of the list.
00060  * A circle queue may be traversed in either direction, but has a more
00061  * complex end of list detection.
00062  *
00063  * For details on the use of these macros, see the queue(3) manual page.
00064  */
00065 
00066 /*
00067  * List definitions.
00068  */
00069 #define LIST_HEAD(name, type)                                         \
00070 struct name {                                                  \
00071        struct type *lh_first;      /* first element */                \
00072 }
00073 
00074 #define LIST_ENTRY(type)                                       \
00075 struct {                                                       \
00076        struct type *le_next;       /* next element */                 \
00077        struct type **le_prev;      /* address of previous next element */    \
00078 }
00079 
00080 /*
00081  * List functions.
00082  */
00083 #define       LIST_INIT(head) {                                       \
00084        (head)->lh_first = NULL;                                \
00085 }
00086 
00087 #define LIST_INSERT_AFTER(listelm, elm, field) {               \
00088        if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
00089               (listelm)->field.le_next->field.le_prev =        \
00090                   &(elm)->field.le_next;                       \
00091        (listelm)->field.le_next = (elm);                       \
00092        (elm)->field.le_prev = &(listelm)->field.le_next;              \
00093 }
00094 
00095 #define LIST_INSERT_HEAD(head, elm, field) {                          \
00096        if (((elm)->field.le_next = (head)->lh_first) != NULL)         \
00097               (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
00098        (head)->lh_first = (elm);                               \
00099        (elm)->field.le_prev = &(head)->lh_first;               \
00100 }
00101 
00102 #define LIST_REMOVE(elm, field) {                              \
00103        if ((elm)->field.le_next != NULL)                       \
00104               (elm)->field.le_next->field.le_prev =                   \
00105                   (elm)->field.le_prev;                        \
00106        *(elm)->field.le_prev = (elm)->field.le_next;                  \
00107 }
00108 
00109 /*
00110  * Tail queue definitions.
00111  */
00112 #define TAILQ_HEAD(name, type)                                        \
00113 struct name {                                                  \
00114        struct type *tqh_first;     /* first element */                \
00115        struct type **tqh_last;     /* addr of last next element */           \
00116 }
00117 
00118 #define TAILQ_ENTRY(type)                                      \
00119 struct {                                                       \
00120        struct type *tqe_next;      /* next element */                 \
00121        struct type **tqe_prev;     /* address of previous next element */    \
00122 }
00123 
00124 /*
00125  * Tail queue functions.
00126  */
00127 #define       TAILQ_INIT(head) {                                      \
00128        (head)->tqh_first = NULL;                               \
00129        (head)->tqh_last = &(head)->tqh_first;                         \
00130 }
00131 
00132 #define TAILQ_INSERT_HEAD(head, elm, field) {                         \
00133        if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)       \
00134               (elm)->field.tqe_next->field.tqe_prev =                 \
00135                   &(elm)->field.tqe_next;                      \
00136        else                                                    \
00137               (head)->tqh_last = &(elm)->field.tqe_next;              \
00138        (head)->tqh_first = (elm);                              \
00139        (elm)->field.tqe_prev = &(head)->tqh_first;                    \
00140 }
00141 
00142 #define TAILQ_INSERT_TAIL(head, elm, field) {                         \
00143        (elm)->field.tqe_next = NULL;                                  \
00144        (elm)->field.tqe_prev = (head)->tqh_last;               \
00145        *(head)->tqh_last = (elm);                              \
00146        (head)->tqh_last = &(elm)->field.tqe_next;                     \
00147 }
00148 
00149 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) {               \
00150        if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
00151               (elm)->field.tqe_next->field.tqe_prev =          \
00152                   &(elm)->field.tqe_next;                      \
00153        else                                                    \
00154               (head)->tqh_last = &(elm)->field.tqe_next;              \
00155        (listelm)->field.tqe_next = (elm);                      \
00156        (elm)->field.tqe_prev = &(listelm)->field.tqe_next;            \
00157 }
00158 
00159 #define TAILQ_REMOVE(head, elm, field) {                       \
00160        if (((elm)->field.tqe_next) != NULL)                           \
00161               (elm)->field.tqe_next->field.tqe_prev =          \
00162                   (elm)->field.tqe_prev;                       \
00163        else                                                    \
00164               (head)->tqh_last = (elm)->field.tqe_prev;        \
00165        *(elm)->field.tqe_prev = (elm)->field.tqe_next;                \
00166 }
00167 
00168 /*
00169  * Circular queue definitions.
00170  */
00171 #define CIRCLEQ_HEAD(name, type)                               \
00172 struct name {                                                  \
00173        struct type *cqh_first;            /* first element */         \
00174        struct type *cqh_last;             /* last element */          \
00175 }
00176 
00177 #define CIRCLEQ_ENTRY(type)                                    \
00178 struct {                                                       \
00179        struct type *cqe_next;             /* next element */          \
00180        struct type *cqe_prev;             /* previous element */             \
00181 }
00182 
00183 /*
00184  * Circular queue functions.
00185  */
00186 #define       CIRCLEQ_INIT(head) {                                    \
00187        (head)->cqh_first = (void *)(head);                            \
00188        (head)->cqh_last = (void *)(head);                      \
00189 }
00190 
00191 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) {             \
00192        (elm)->field.cqe_next = (listelm)->field.cqe_next;             \
00193        (elm)->field.cqe_prev = (listelm);                      \
00194        if ((listelm)->field.cqe_next == (void *)(head))        \
00195               (head)->cqh_last = (elm);                        \
00196        else                                                    \
00197               (listelm)->field.cqe_next->field.cqe_prev = (elm);      \
00198        (listelm)->field.cqe_next = (elm);                      \
00199 }
00200 
00201 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) {            \
00202        (elm)->field.cqe_next = (listelm);                      \
00203        (elm)->field.cqe_prev = (listelm)->field.cqe_prev;             \
00204        if ((listelm)->field.cqe_prev == (void *)(head))        \
00205               (head)->cqh_first = (elm);                       \
00206        else                                                    \
00207               (listelm)->field.cqe_prev->field.cqe_next = (elm);      \
00208        (listelm)->field.cqe_prev = (elm);                      \
00209 }
00210 
00211 #define CIRCLEQ_INSERT_HEAD(head, elm, field) {                       \
00212        (elm)->field.cqe_next = (head)->cqh_first;                     \
00213        (elm)->field.cqe_prev = (void *)(head);                        \
00214        if ((head)->cqh_last == (void *)(head))                        \
00215               (head)->cqh_last = (elm);                        \
00216        else                                                    \
00217               (head)->cqh_first->field.cqe_prev = (elm);              \
00218        (head)->cqh_first = (elm);                              \
00219 }
00220 
00221 #define CIRCLEQ_INSERT_TAIL(head, elm, field) {                       \
00222        (elm)->field.cqe_next = (void *)(head);                        \
00223        (elm)->field.cqe_prev = (head)->cqh_last;               \
00224        if ((head)->cqh_first == (void *)(head))                \
00225               (head)->cqh_first = (elm);                       \
00226        else                                                    \
00227               (head)->cqh_last->field.cqe_next = (elm);        \
00228        (head)->cqh_last = (elm);                               \
00229 }
00230 
00231 #define       CIRCLEQ_REMOVE(head, elm, field) {                      \
00232        if ((elm)->field.cqe_next == (void *)(head))                   \
00233               (head)->cqh_last = (elm)->field.cqe_prev;        \
00234        else                                                    \
00235               (elm)->field.cqe_next->field.cqe_prev =                 \
00236                   (elm)->field.cqe_prev;                       \
00237        if ((elm)->field.cqe_prev == (void *)(head))                   \
00238               (head)->cqh_first = (elm)->field.cqe_next;              \
00239        else                                                    \
00240               (elm)->field.cqe_prev->field.cqe_next =                 \
00241                   (elm)->field.cqe_next;                       \
00242 }
00243 #endif /* !_QUEUE_H_ */