shqueue.h

Go to the documentation of this file.
00001 /*-
00002  * See the file LICENSE for redistribution information.
00003  *
00004  * Copyright (c) 1996, 1997, 1998, 1999, 2000
00005  *      Sleepycat Software.  All rights reserved.
00006  *
00007  * $Id: shqueue_8h-source.html,v 1.1 2008/06/08 10:22:10 sebdiaz Exp $
00008  */
00009 #ifndef _SYS_SHQUEUE_H_
00010 #define _SYS_SHQUEUE_H_
00011 
00012 /*
00013  * This file defines three types of data structures: lists, tail queues, and
00014  * circular queues, similarly to the include file <sys/queue.h>.
00015  *
00016  * The difference is that this set of macros can be used for structures that
00017  * reside in shared memory that may be mapped at different addresses in each
00018  * process.  In most cases, the macros for shared structures exactly mirror
00019  * the normal macros, although the macro calls require an additional type
00020  * parameter, only used by the HEAD and ENTRY macros of the standard macros.
00021  *
00022  * For details on the use of these macros, see the queue(3) manual page.
00023  */
00024 
00025 #if defined(__cplusplus)
00026 extern "C" {
00027 #endif
00028 
00029 /*
00030  * Shared list definitions.
00031  */
00032 #define SH_LIST_HEAD(name)                                              \
00033 struct name {                                                           \
00034         ssize_t slh_first;      /* first element */                     \
00035 }
00036 
00037 #define SH_LIST_ENTRY                                                   \
00038 struct {                                                                \
00039         ssize_t sle_next;       /* relative offset next element */      \
00040         ssize_t sle_prev;       /* relative offset of prev element */   \
00041 }
00042 
00043 /*
00044  * Shared list functions.  Since we use relative offsets for pointers,
00045  * 0 is a valid offset.  Therefore, we use -1 to indicate end of list.
00046  * The macros ending in "P" return pointers without checking for end
00047  * of list, the others check for end of list and evaluate to either a
00048  * pointer or NULL.
00049  */
00050 
00051 #define SH_LIST_FIRSTP(head, type)                                      \
00052         ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first))
00053 
00054 #define SH_LIST_FIRST(head, type)                                       \
00055         ((head)->slh_first == -1 ? NULL :                               \
00056         ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first)))
00057 
00058 #define SH_LIST_NEXTP(elm, field, type)                                 \
00059         ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next))
00060 
00061 #define SH_LIST_NEXT(elm, field, type)                                  \
00062         ((elm)->field.sle_next == -1 ? NULL :                           \
00063         ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next)))
00064 
00065 #define SH_LIST_PREV(elm, field)                                        \
00066         ((ssize_t *)(((u_int8_t *)(elm)) + (elm)->field.sle_prev))
00067 
00068 #define SH_PTR_TO_OFF(src, dest)                                        \
00069         ((ssize_t)(((u_int8_t *)(dest)) - ((u_int8_t *)(src))))
00070 
00071 #define SH_LIST_END(head)                       NULL
00072 
00073 /*
00074  * Take the element's next pointer and calculate what the corresponding
00075  * Prev pointer should be -- basically it is the negation plus the offset
00076  * of the next field in the structure.
00077  */
00078 #define SH_LIST_NEXT_TO_PREV(elm, field)                                \
00079         (-(elm)->field.sle_next + SH_PTR_TO_OFF(elm, &(elm)->field.sle_next))
00080 
00081 #define SH_LIST_INIT(head) (head)->slh_first = -1
00082 
00083 #define SH_LIST_INSERT_AFTER(listelm, elm, field, type) do {            \
00084         if ((listelm)->field.sle_next != -1) {                          \
00085                 (elm)->field.sle_next = SH_PTR_TO_OFF(elm,              \
00086                     SH_LIST_NEXTP(listelm, field, type));               \
00087                 SH_LIST_NEXTP(listelm, field, type)->field.sle_prev =   \
00088                         SH_LIST_NEXT_TO_PREV(elm, field);               \
00089         } else                                                          \
00090                 (elm)->field.sle_next = -1;                             \
00091         (listelm)->field.sle_next = SH_PTR_TO_OFF(listelm, elm);        \
00092         (elm)->field.sle_prev = SH_LIST_NEXT_TO_PREV(listelm, field);   \
00093 } while (0)
00094 
00095 #define SH_LIST_INSERT_HEAD(head, elm, field, type) do {                \
00096         if ((head)->slh_first != -1) {                                  \
00097                 (elm)->field.sle_next =                         \
00098                     (head)->slh_first - SH_PTR_TO_OFF(head, elm);       \
00099                 SH_LIST_FIRSTP(head, type)->field.sle_prev =            \
00100                         SH_LIST_NEXT_TO_PREV(elm, field);               \
00101         } else                                                          \
00102                 (elm)->field.sle_next = -1;                             \
00103         (head)->slh_first = SH_PTR_TO_OFF(head, elm);                   \
00104         (elm)->field.sle_prev = SH_PTR_TO_OFF(elm, &(head)->slh_first); \
00105 } while (0)
00106 
00107 #define SH_LIST_REMOVE(elm, field, type) do {                           \
00108         if ((elm)->field.sle_next != -1) {                              \
00109                 SH_LIST_NEXTP(elm, field, type)->field.sle_prev =       \
00110                         (elm)->field.sle_prev - (elm)->field.sle_next;  \
00111                 *SH_LIST_PREV(elm, field) += (elm)->field.sle_next;     \
00112         } else                                                          \
00113                 *SH_LIST_PREV(elm, field) = -1;                         \
00114 } while (0)
00115 
00116 /*
00117  * Shared tail queue definitions.
00118  */
00119 #define SH_TAILQ_HEAD(name)                                             \
00120 struct name {                                                           \
00121         ssize_t stqh_first;     /* relative offset of first element */  \
00122         ssize_t stqh_last;      /* relative offset of last's next */    \
00123 }
00124 
00125 #define SH_TAILQ_ENTRY                                                  \
00126 struct {                                                                \
00127         ssize_t stqe_next;      /* relative offset of next element */   \
00128         ssize_t stqe_prev;      /* relative offset of prev's next */    \
00129 }
00130 
00131 /*
00132  * Shared tail queue functions.
00133  */
00134 #define SH_TAILQ_FIRSTP(head, type)                                     \
00135         ((struct type *)((u_int8_t *)(head) + (head)->stqh_first))
00136 
00137 #define SH_TAILQ_FIRST(head, type)                                      \
00138         ((head)->stqh_first == -1 ? NULL : SH_TAILQ_FIRSTP(head, type))
00139 
00140 #define SH_TAILQ_NEXTP(elm, field, type)                                \
00141         ((struct type *)((u_int8_t *)(elm) + (elm)->field.stqe_next))
00142 
00143 #define SH_TAILQ_NEXT(elm, field, type)                                 \
00144         ((elm)->field.stqe_next == -1 ? NULL : SH_TAILQ_NEXTP(elm, field, type))
00145 
00146 #define SH_TAILQ_PREVP(elm, field)                                      \
00147         ((ssize_t *)((u_int8_t *)(elm) + (elm)->field.stqe_prev))
00148 
00149 #define SH_TAILQ_LAST(head)                                             \
00150         ((ssize_t *)(((u_int8_t *)(head)) + (head)->stqh_last))
00151 
00152 #define SH_TAILQ_NEXT_TO_PREV(elm, field)                               \
00153         (-(elm)->field.stqe_next + SH_PTR_TO_OFF(elm, &(elm)->field.stqe_next))
00154 
00155 #define SH_TAILQ_END(head)              NULL
00156 
00157 #define SH_TAILQ_INIT(head) {                                           \
00158         (head)->stqh_first = -1;                                        \
00159         (head)->stqh_last = SH_PTR_TO_OFF(head, &(head)->stqh_first);   \
00160 }
00161 
00162 #define SH_TAILQ_INSERT_HEAD(head, elm, field, type) do {               \
00163         if ((head)->stqh_first != -1) {                                 \
00164                 (elm)->field.stqe_next =                                \
00165                     (head)->stqh_first - SH_PTR_TO_OFF(head, elm);      \
00166                 SH_TAILQ_FIRSTP(head, type)->field.stqe_prev =          \
00167                         SH_TAILQ_NEXT_TO_PREV(elm, field);              \
00168         } else {                                                        \
00169                 (elm)->field.stqe_next = -1;                            \
00170                 (head)->stqh_last =                                     \
00171                     SH_PTR_TO_OFF(head, &(elm)->field.stqe_next);       \
00172         }                                                               \
00173         (head)->stqh_first = SH_PTR_TO_OFF(head, elm);                  \
00174         (elm)->field.stqe_prev =                                        \
00175             SH_PTR_TO_OFF(elm, &(head)->stqh_first);                    \
00176 } while (0)
00177 
00178 #define SH_TAILQ_INSERT_TAIL(head, elm, field) do {                     \
00179         (elm)->field.stqe_next = -1;                                    \
00180         (elm)->field.stqe_prev =                                        \
00181             -SH_PTR_TO_OFF(head, elm) + (head)->stqh_last;              \
00182         if ((head)->stqh_last ==                                        \
00183             SH_PTR_TO_OFF((head), &(head)->stqh_first))                 \
00184                 (head)->stqh_first = SH_PTR_TO_OFF(head, elm);          \
00185         else                                                            \
00186                 *SH_TAILQ_LAST(head) = -(head)->stqh_last +             \
00187                     SH_PTR_TO_OFF((elm), &(elm)->field.stqe_next) +     \
00188                     SH_PTR_TO_OFF(head, elm);                           \
00189         (head)->stqh_last =                                             \
00190             SH_PTR_TO_OFF(head, &((elm)->field.stqe_next));             \
00191 } while (0)
00192 
00193 #define SH_TAILQ_INSERT_AFTER(head, listelm, elm, field, type) do {     \
00194         if ((listelm)->field.stqe_next != -1) {                         \
00195                 (elm)->field.stqe_next = (listelm)->field.stqe_next -   \
00196                     SH_PTR_TO_OFF(listelm, elm);                        \
00197                 SH_TAILQ_NEXTP(listelm, field, type)->field.stqe_prev = \
00198                     SH_TAILQ_NEXT_TO_PREV(elm, field);                  \
00199         } else {                                                        \
00200                 (elm)->field.stqe_next = -1;                            \
00201                 (head)->stqh_last =                                     \
00202                     SH_PTR_TO_OFF(head, &elm->field.stqe_next);         \
00203         }                                                               \
00204         (listelm)->field.stqe_next = SH_PTR_TO_OFF(listelm, elm);       \
00205         (elm)->field.stqe_prev = SH_TAILQ_NEXT_TO_PREV(listelm, field); \
00206 } while (0)
00207 
00208 #define SH_TAILQ_REMOVE(head, elm, field, type) do {                    \
00209         if ((elm)->field.stqe_next != -1) {                             \
00210                 SH_TAILQ_NEXTP(elm, field, type)->field.stqe_prev =     \
00211                     (elm)->field.stqe_prev +                            \
00212                     SH_PTR_TO_OFF(SH_TAILQ_NEXTP(elm,                   \
00213                     field, type), elm);                                 \
00214                 *SH_TAILQ_PREVP(elm, field) += elm->field.stqe_next;    \
00215         } else {                                                        \
00216                 (head)->stqh_last = (elm)->field.stqe_prev +            \
00217                         SH_PTR_TO_OFF(head, elm);                       \
00218                 *SH_TAILQ_PREVP(elm, field) = -1;                       \
00219         }                                                               \
00220 } while (0)
00221 
00222 /*
00223  * Shared circular queue definitions.
00224  */
00225 #define SH_CIRCLEQ_HEAD(name)                                           \
00226 struct name {                                                           \
00227         ssize_t scqh_first;             /* first element */             \
00228         ssize_t scqh_last;              /* last element */              \
00229 }
00230 
00231 #define SH_CIRCLEQ_ENTRY                                                \
00232 struct {                                                                \
00233         ssize_t scqe_next;              /* next element */              \
00234         ssize_t scqe_prev;              /* previous element */          \
00235 }
00236 
00237 /*
00238  * Shared circular queue functions.
00239  */
00240 #define SH_CIRCLEQ_FIRSTP(head, type)                                   \
00241         ((struct type *)(((u_int8_t *)(head)) + (head)->scqh_first))
00242 
00243 #define SH_CIRCLEQ_FIRST(head, type)                                    \
00244         ((head)->scqh_first == -1 ?                                     \
00245         (void *)head : SH_CIRCLEQ_FIRSTP(head, type))
00246 
00247 #define SH_CIRCLEQ_LASTP(head, type)                                    \
00248         ((struct type *)(((u_int8_t *)(head)) + (head)->scqh_last))
00249 
00250 #define SH_CIRCLEQ_LAST(head, type)                                     \
00251         ((head)->scqh_last == -1 ? (void *)head : SH_CIRCLEQ_LASTP(head, type))
00252 
00253 #define SH_CIRCLEQ_NEXTP(elm, field, type)                              \
00254         ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.scqe_next))
00255 
00256 #define SH_CIRCLEQ_NEXT(head, elm, field, type)                         \
00257         ((elm)->field.scqe_next == SH_PTR_TO_OFF(elm, head) ?           \
00258             (void *)head : SH_CIRCLEQ_NEXTP(elm, field, type))
00259 
00260 #define SH_CIRCLEQ_PREVP(elm, field, type)                              \
00261         ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.scqe_prev))
00262 
00263 #define SH_CIRCLEQ_PREV(head, elm, field, type)                         \
00264         ((elm)->field.scqe_prev == SH_PTR_TO_OFF(elm, head) ?           \
00265             (void *)head : SH_CIRCLEQ_PREVP(elm, field, type))
00266 
00267 #define SH_CIRCLEQ_END(head)            ((void *)(head))
00268 
00269 #define SH_CIRCLEQ_INIT(head) {                                         \
00270         (head)->scqh_first = 0;                                         \
00271         (head)->scqh_last = 0;                                          \
00272 }
00273 
00274 #define SH_CIRCLEQ_INSERT_AFTER(head, listelm, elm, field, type) do {   \
00275         (elm)->field.scqe_prev = SH_PTR_TO_OFF(elm, listelm);           \
00276         (elm)->field.scqe_next = (listelm)->field.scqe_next +           \
00277             (elm)->field.scqe_prev;                                     \
00278         if (SH_CIRCLEQ_NEXTP(listelm, field, type) == (void *)head)     \
00279                 (head)->scqh_last = SH_PTR_TO_OFF(head, elm);           \
00280         else                                                            \
00281                 SH_CIRCLEQ_NEXTP(listelm,                               \
00282                     field, type)->field.scqe_prev =                     \
00283                     SH_PTR_TO_OFF(SH_CIRCLEQ_NEXTP(listelm,             \
00284                     field, type), elm);                                 \
00285         (listelm)->field.scqe_next = -(elm)->field.scqe_prev;           \
00286 } while (0)
00287 
00288 #define SH_CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field, type) do {  \
00289         (elm)->field.scqe_next = SH_PTR_TO_OFF(elm, listelm);           \
00290         (elm)->field.scqe_prev = (elm)->field.scqe_next -               \
00291                 SH_CIRCLEQ_PREVP(listelm, field, type)->field.scqe_next;\
00292         if (SH_CIRCLEQ_PREVP(listelm, field, type) == (void *)(head))   \
00293                 (head)->scqh_first = SH_PTR_TO_OFF(head, elm);          \
00294         else                                                            \
00295                 SH_CIRCLEQ_PREVP(listelm,                               \
00296                     field, type)->field.scqe_next =                     \
00297                     SH_PTR_TO_OFF(SH_CIRCLEQ_PREVP(listelm,             \
00298                     field, type), elm);                                 \
00299         (listelm)->field.scqe_prev = -(elm)->field.scqe_next;           \
00300 } while (0)
00301 
00302 #define SH_CIRCLEQ_INSERT_HEAD(head, elm, field, type) do {             \
00303         (elm)->field.scqe_prev = SH_PTR_TO_OFF(elm, head);              \
00304         (elm)->field.scqe_next = (head)->scqh_first +                   \
00305                 (elm)->field.scqe_prev;                                 \
00306         if ((head)->scqh_last == 0)                                     \
00307                 (head)->scqh_last = -(elm)->field.scqe_prev;            \
00308         else                                                            \
00309                 SH_CIRCLEQ_FIRSTP(head, type)->field.scqe_prev =        \
00310                     SH_PTR_TO_OFF(SH_CIRCLEQ_FIRSTP(head, type), elm);  \
00311         (head)->scqh_first = -(elm)->field.scqe_prev;                   \
00312 } while (0)
00313 
00314 #define SH_CIRCLEQ_INSERT_TAIL(head, elm, field, type) do {             \
00315         (elm)->field.scqe_next = SH_PTR_TO_OFF(elm, head);              \
00316         (elm)->field.scqe_prev = (head)->scqh_last +                    \
00317             (elm)->field.scqe_next;                                     \
00318         if ((head)->scqh_first == 0)                                    \
00319                 (head)->scqh_first = -(elm)->field.scqe_next;           \
00320         else                                                            \
00321                 SH_CIRCLEQ_LASTP(head, type)->field.scqe_next = \
00322                     SH_PTR_TO_OFF(SH_CIRCLEQ_LASTP(head, type), elm);   \
00323         (head)->scqh_last = -(elm)->field.scqe_next;                    \
00324 } while (0)
00325 
00326 #define SH_CIRCLEQ_REMOVE(head, elm, field, type) do {                  \
00327         if (SH_CIRCLEQ_NEXTP(elm, field, type) == (void *)(head))       \
00328                 (head)->scqh_last += (elm)->field.scqe_prev;            \
00329         else                                                            \
00330                 SH_CIRCLEQ_NEXTP(elm, field, type)->field.scqe_prev +=  \
00331                     (elm)->field.scqe_prev;                             \
00332         if (SH_CIRCLEQ_PREVP(elm, field, type) == (void *)(head))       \
00333                 (head)->scqh_first += (elm)->field.scqe_next;           \
00334         else                                                            \
00335                 SH_CIRCLEQ_PREVP(elm, field, type)->field.scqe_next +=  \
00336                     (elm)->field.scqe_next;                             \
00337 } while (0)
00338 
00339 #if defined(__cplusplus)
00340 }
00341 #endif
00342 
00343 #endif  /* !_SYS_SHQUEUE_H_ */

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