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. Neither the name of the University nor the names of its contributors
00014  *    may be used to endorse or promote products derived from this software
00015  *    without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00018  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00019  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00020  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00021  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00022  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00023  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00024  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00025  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00026  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00027  * SUCH DAMAGE.
00028  *
00029  *      @(#)queue.h     8.5 (Berkeley) 8/20/94
00030  */
00031 
00032 #ifndef _SYS_QUEUE_H_
00033 #define _SYS_QUEUE_H_
00034 
00035 /*
00036  * This file defines three types of data structures: lists, tail queues,
00037  * and circular queues.
00038  *
00039  * A list is headed by a single forward pointer (or an array of forward
00040  * pointers for a hash table header). The elements are doubly linked
00041  * so that an arbitrary element can be removed without a need to
00042  * traverse the list. New elements can be added to the list before
00043  * or after an existing element or at the head of the list. A list
00044  * may only be traversed in the forward direction.
00045  *
00046  * A tail queue is headed by a pair of pointers, one to the head of the
00047  * list and the other to the tail of the list. The elements are doubly
00048  * linked so that an arbitrary element can be removed without a need to
00049  * traverse the list. New elements can be added to the list before or
00050  * after an existing element, at the head of the list, or at the end of
00051  * the list. A tail queue may only be traversed in the forward direction.
00052  *
00053  * A circle queue is headed by a pair of pointers, one to the head of the
00054  * list and the other to the tail of the list. The elements are doubly
00055  * linked so that an arbitrary element can be removed without a need to
00056  * traverse the list. New elements can be added to the list before or after
00057  * an existing element, at the head of the list, or at the end of the list.
00058  * A circle queue may be traversed in either direction, but has a more
00059  * complex end of list detection.
00060  *
00061  * For details on the use of these macros, see the queue(3) manual page.
00062  */
00063 
00064 #if defined(__cplusplus)
00065 extern "C" {
00066 #endif
00067 
00068 /*
00069  * List definitions.
00070  */
00071 #define LIST_HEAD(name, type)                                           \
00072 struct name {                                                           \
00073         struct type *lh_first;  /* first element */                     \
00074 }
00075 
00076 #define LIST_ENTRY(type)                                                \
00077 struct {                                                                \
00078         struct type *le_next;   /* next element */                      \
00079         struct type **le_prev;  /* address of previous next element */  \
00080 }
00081 
00082 #define LIST_FIRST(head)                ((head)->lh_first)
00083 #define LIST_NEXT(elm, field)           ((elm)->field.le_next)
00084 #define LIST_END(head)                  NULL
00085 
00086 /*
00087  * List functions.
00088  */
00089 #define LIST_INIT(head) {                                               \
00090         (head)->lh_first = NULL;                                        \
00091 }
00092 
00093 #define LIST_INSERT_AFTER(listelm, elm, field) do {                     \
00094         if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)  \
00095                 (listelm)->field.le_next->field.le_prev =               \
00096                     &(elm)->field.le_next;                              \
00097         (listelm)->field.le_next = (elm);                               \
00098         (elm)->field.le_prev = &(listelm)->field.le_next;               \
00099 } while (0)
00100 
00101 #define LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
00102         (elm)->field.le_prev = (listelm)->field.le_prev;                \
00103         (elm)->field.le_next = (listelm);                               \
00104         *(listelm)->field.le_prev = (elm);                              \
00105         (listelm)->field.le_prev = &(elm)->field.le_next;               \
00106 } while (0)
00107 
00108 #define LIST_INSERT_HEAD(head, elm, field) do {                         \
00109         if (((elm)->field.le_next = (head)->lh_first) != NULL)          \
00110                 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
00111         (head)->lh_first = (elm);                                       \
00112         (elm)->field.le_prev = &(head)->lh_first;                       \
00113 } while (0)
00114 
00115 #define LIST_REMOVE(elm, field) do {                                    \
00116         if ((elm)->field.le_next != NULL)                               \
00117                 (elm)->field.le_next->field.le_prev =                   \
00118                     (elm)->field.le_prev;                               \
00119         *(elm)->field.le_prev = (elm)->field.le_next;                   \
00120 } while (0)
00121 
00122 /*
00123  * Tail queue definitions.
00124  */
00125 #define TAILQ_HEAD(name, type)                                          \
00126 struct name {                                                           \
00127         struct type *tqh_first; /* first element */                     \
00128         struct type **tqh_last; /* addr of last next element */         \
00129 }
00130 
00131 #define TAILQ_ENTRY(type)                                               \
00132 struct {                                                                \
00133         struct type *tqe_next;  /* next element */                      \
00134         struct type **tqe_prev; /* address of previous next element */  \
00135 }
00136 
00137 #define TAILQ_FIRST(head)               ((head)->tqh_first)
00138 #define TAILQ_NEXT(elm, field)          ((elm)->field.tqe_next)
00139 #define TAILQ_END(head)                 NULL
00140 
00141 /*
00142  * Tail queue functions.
00143  */
00144 #define TAILQ_INIT(head) do {                                           \
00145         (head)->tqh_first = NULL;                                       \
00146         (head)->tqh_last = &(head)->tqh_first;                          \
00147 } while (0)
00148 
00149 #define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
00150         if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
00151                 (head)->tqh_first->field.tqe_prev =                     \
00152                     &(elm)->field.tqe_next;                             \
00153         else                                                            \
00154                 (head)->tqh_last = &(elm)->field.tqe_next;              \
00155         (head)->tqh_first = (elm);                                      \
00156         (elm)->field.tqe_prev = &(head)->tqh_first;                     \
00157 } while (0)
00158 
00159 #define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
00160         (elm)->field.tqe_next = NULL;                                   \
00161         (elm)->field.tqe_prev = (head)->tqh_last;                       \
00162         *(head)->tqh_last = (elm);                                      \
00163         (head)->tqh_last = &(elm)->field.tqe_next;                      \
00164 } while (0)
00165 
00166 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
00167         if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
00168                 (elm)->field.tqe_next->field.tqe_prev =         \
00169                     &(elm)->field.tqe_next;                             \
00170         else                                                            \
00171                 (head)->tqh_last = &(elm)->field.tqe_next;              \
00172         (listelm)->field.tqe_next = (elm);                              \
00173         (elm)->field.tqe_prev = &(listelm)->field.tqe_next;             \
00174 } while (0)
00175 
00176 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
00177         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
00178         (elm)->field.tqe_next = (listelm);                              \
00179         *(listelm)->field.tqe_prev = (elm);                             \
00180         (listelm)->field.tqe_prev = &(elm)->field.tqe_next;             \
00181 } while (0)
00182 
00183 #define TAILQ_REMOVE(head, elm, field) do {                             \
00184         if (((elm)->field.tqe_next) != NULL)                            \
00185                 (elm)->field.tqe_next->field.tqe_prev =         \
00186                     (elm)->field.tqe_prev;                              \
00187         else                                                            \
00188                 (head)->tqh_last = (elm)->field.tqe_prev;               \
00189         *(elm)->field.tqe_prev = (elm)->field.tqe_next;                 \
00190 } while (0)
00191 
00192 /*
00193  * Circular queue definitions.
00194  */
00195 #define CIRCLEQ_HEAD(name, type)                                        \
00196 struct name {                                                           \
00197         struct type *cqh_first;         /* first element */             \
00198         struct type *cqh_last;          /* last element */              \
00199 }
00200 
00201 #define CIRCLEQ_ENTRY(type)                                             \
00202 struct {                                                                \
00203         struct type *cqe_next;          /* next element */              \
00204         struct type *cqe_prev;          /* previous element */          \
00205 }
00206 
00207 #define CIRCLEQ_FIRST(head)             ((head)->cqh_first)
00208 #define CIRCLEQ_LAST(head)              ((head)->cqh_last)
00209 #define CIRCLEQ_END(head)               ((void *)(head))
00210 #define CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)
00211 #define CIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)
00212 
00213 /*
00214  * Circular queue functions.
00215  */
00216 #define CIRCLEQ_INIT(head) do {                                         \
00217         (head)->cqh_first = (void *)(head);                             \
00218         (head)->cqh_last = (void *)(head);                              \
00219 } while (0)
00220 
00221 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
00222         (elm)->field.cqe_next = (listelm)->field.cqe_next;              \
00223         (elm)->field.cqe_prev = (listelm);                              \
00224         if ((listelm)->field.cqe_next == (void *)(head))                \
00225                 (head)->cqh_last = (elm);                               \
00226         else                                                            \
00227                 (listelm)->field.cqe_next->field.cqe_prev = (elm);      \
00228         (listelm)->field.cqe_next = (elm);                              \
00229 } while (0)
00230 
00231 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {           \
00232         (elm)->field.cqe_next = (listelm);                              \
00233         (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \
00234         if ((listelm)->field.cqe_prev == (void *)(head))                \
00235                 (head)->cqh_first = (elm);                              \
00236         else                                                            \
00237                 (listelm)->field.cqe_prev->field.cqe_next = (elm);      \
00238         (listelm)->field.cqe_prev = (elm);                              \
00239 } while (0)
00240 
00241 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do {                      \
00242         (elm)->field.cqe_next = (head)->cqh_first;                      \
00243         (elm)->field.cqe_prev = (void *)(head);                         \
00244         if ((head)->cqh_last == (void *)(head))                         \
00245                 (head)->cqh_last = (elm);                               \
00246         else                                                            \
00247                 (head)->cqh_first->field.cqe_prev = (elm);              \
00248         (head)->cqh_first = (elm);                                      \
00249 } while (0)
00250 
00251 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do {                      \
00252         (elm)->field.cqe_next = (void *)(head);                         \
00253         (elm)->field.cqe_prev = (head)->cqh_last;                       \
00254         if ((head)->cqh_first == (void *)(head))                        \
00255                 (head)->cqh_first = (elm);                              \
00256         else                                                            \
00257                 (head)->cqh_last->field.cqe_next = (elm);               \
00258         (head)->cqh_last = (elm);                                       \
00259 } while (0)
00260 
00261 #define CIRCLEQ_REMOVE(head, elm, field) do {                           \
00262         if ((elm)->field.cqe_next == (void *)(head))                    \
00263                 (head)->cqh_last = (elm)->field.cqe_prev;               \
00264         else                                                            \
00265                 (elm)->field.cqe_next->field.cqe_prev =                 \
00266                     (elm)->field.cqe_prev;                              \
00267         if ((elm)->field.cqe_prev == (void *)(head))                    \
00268                 (head)->cqh_first = (elm)->field.cqe_next;              \
00269         else                                                            \
00270                 (elm)->field.cqe_prev->field.cqe_next =                 \
00271                     (elm)->field.cqe_next;                              \
00272 } while (0)
00273 
00274 #if defined(__cplusplus)
00275 }
00276 #endif
00277 
00278 #endif  /* !_SYS_QUEUE_H_ */

Generated on Sun Jun 8 10:56:39 2008 for GNUmifluz by  doxygen 1.5.5