db2/include/shqueue.h

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996, 1997, 1998
   5  *      Sleepycat Software.  All rights reserved.
   6  *
   7  *      @(#)shqueue.h   8.13 (Sleepycat) 4/10/98
   8  */
   9 #ifndef _SYS_SHQUEUE_H_
  10 #define _SYS_SHQUEUE_H_
  11
  12 /*
  13  * This file defines three types of data structures: lists, tail queues, and
  14  * circular queues, similarly to the include file <sys/queue.h>.
  15  *
  16  * The difference is that this set of macros can be used for structures that
  17  * reside in shared memory that may be mapped at different addresses in each
  18  * process.  In most cases, the macros for shared structures exactly mirror
  19  * the normal macros, although the macro calls require an additional type
  20  * parameter, only used by the HEAD and ENTRY macros of the standard macros.
  21  *
  22  * For details on the use of these macros, see the queue(3) manual page.
  23  */
  24
  25 /*
  26  * Shared list definitions.
  27  */
  28 #define SH_LIST_HEAD(name)                                              \
  29 struct name {                                                           \
  30         ssize_t slh_first;      /* first element */                     \
  31 }
  32
  33 #define SH_LIST_ENTRY                                                   \
  34 struct {                                                                \
  35         ssize_t sle_next;       /* relative offset next element */      \
  36         ssize_t sle_prev;       /* relative offset of prev element */   \
  37 }
  38
  39 /*
  40  * Shared list functions.  Since we use relative offsets for pointers,
  41  * 0 is a valid offset.  Therefore, we use -1 to indicate end of list.
  42  * The macros ending in "P" return pointers without checking for end
  43  * of list, the others check for end of list and evaluate to either a
  44  * pointer or NULL.
  45  */
  46
  47 #define SH_LIST_FIRSTP(head, type)                                      \
  48         ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first))
  49
  50 #define SH_LIST_FIRST(head, type)                                       \
  51         ((head)->slh_first == -1 ? NULL :                               \
  52         ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first)))
  53
  54 #define SH_LIST_NEXTP(elm, field, type)                                 \
  55         ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next))
  56
  57 #define SH_LIST_NEXT(elm, field, type)                                  \
  58         ((elm)->field.sle_next == -1 ? NULL :                           \
  59         ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next)))
  60
  61 #define SH_LIST_PREV(elm, field)                                        \
  62         ((ssize_t *)(((u_int8_t *)(elm)) + (elm)->field.sle_prev))
  63
  64 #define SH_PTR_TO_OFF(src, dest)                                        \
  65         ((ssize_t)(((u_int8_t *)(dest)) - ((u_int8_t *)(src))))
  66
  67 #define SH_LIST_END(head)                       NULL
  68
  69 /*
  70  * Take the element's next pointer and calculate what the corresponding
  71  * Prev pointer should be -- basically it is the negation plus the offset
  72  * of the next field in the structure.
  73  */
  74 #define SH_LIST_NEXT_TO_PREV(elm, field)                                \
  75         (-(elm)->field.sle_next + SH_PTR_TO_OFF(elm, &(elm)->field.sle_next))
  76
  77 #define SH_LIST_INIT(head) (head)->slh_first = -1
  78
  79 #define SH_LIST_INSERT_AFTER(listelm, elm, field, type) do {            \
  80         if ((listelm)->field.sle_next != -1) {                          \
  81                 (elm)->field.sle_next = SH_PTR_TO_OFF(elm,              \
  82                     SH_LIST_NEXTP(listelm, field, type));               \
  83                 SH_LIST_NEXTP(listelm, field, type)->field.sle_prev =   \
  84                         SH_LIST_NEXT_TO_PREV(elm, field);               \
  85         } else                                                          \
  86                 (elm)->field.sle_next = -1;                             \
  87         (listelm)->field.sle_next = SH_PTR_TO_OFF(listelm, elm);        \
  88         (elm)->field.sle_prev = SH_LIST_NEXT_TO_PREV(listelm, field);   \
  89 } while (0)
  90
  91 #define SH_LIST_INSERT_HEAD(head, elm, field, type) do {                \
  92         if ((head)->slh_first != -1) {                                  \
  93                 (elm)->field.sle_next =                                 \
  94                     (head)->slh_first - SH_PTR_TO_OFF(head, elm);       \
  95                 SH_LIST_FIRSTP(head, type)->field.sle_prev =            \
  96                         SH_LIST_NEXT_TO_PREV(elm, field);               \
  97         } else                                                          \
  98                 (elm)->field.sle_next = -1;                             \
  99         (head)->slh_first = SH_PTR_TO_OFF(head, elm);                   \
 100         (elm)->field.sle_prev = SH_PTR_TO_OFF(elm, &(head)->slh_first); \
 101 } while (0)
 102
 103 #define SH_LIST_REMOVE(elm, field, type) do {                           \
 104         if ((elm)->field.sle_next != -1) {                              \
 105                 SH_LIST_NEXTP(elm, field, type)->field.sle_prev =       \
 106                         (elm)->field.sle_prev - (elm)->field.sle_next;  \
 107                 *SH_LIST_PREV(elm, field) += (elm)->field.sle_next;     \
 108         } else                                                          \
 109                 *SH_LIST_PREV(elm, field) = -1;                         \
 110 } while (0)
 111
 112 /*
 113  * Shared tail queue definitions.
 114  */
 115 #define SH_TAILQ_HEAD(name)                                             \
 116 struct name {                                                           \
 117         ssize_t stqh_first;     /* relative offset of first element */  \
 118         ssize_t stqh_last;      /* relative offset of last's next */    \
 119 }
 120
 121 #define SH_TAILQ_ENTRY                                                  \
 122 struct {                                                                \
 123         ssize_t stqe_next;      /* relative offset of next element */   \
 124         ssize_t stqe_prev;      /* relative offset of prev's next */    \
 125 }
 126
 127 /*
 128  * Shared tail queue functions.
 129  */
 130 #define SH_TAILQ_FIRSTP(head, type)                                     \
 131         ((struct type *)((u_int8_t *)(head) + (head)->stqh_first))
 132
 133 #define SH_TAILQ_FIRST(head, type)                                      \
 134         ((head)->stqh_first == -1 ? NULL : SH_TAILQ_FIRSTP(head, type))
 135
 136 #define SH_TAILQ_NEXTP(elm, field, type)                                \
 137         ((struct type *)((u_int8_t *)(elm) + (elm)->field.stqe_next))
 138
 139 #define SH_TAILQ_NEXT(elm, field, type)                                 \
 140         ((elm)->field.stqe_next == -1 ? NULL : SH_TAILQ_NEXTP(elm, field, type))
 141
 142 #define SH_TAILQ_PREVP(elm, field)                                      \
 143         ((ssize_t *)((u_int8_t *)(elm) + (elm)->field.stqe_prev))
 144
 145 #define SH_TAILQ_LAST(head)                                             \
 146         ((ssize_t *)(((u_int8_t *)(head)) + (head)->stqh_last))
 147
 148 #define SH_TAILQ_NEXT_TO_PREV(elm, field)                               \
 149         (-(elm)->field.stqe_next + SH_PTR_TO_OFF(elm, &(elm)->field.stqe_next))
 150
 151 #define SH_TAILQ_END(head)              NULL
 152
 153 #define SH_TAILQ_INIT(head) {                                           \
 154         (head)->stqh_first = -1;                                        \
 155         (head)->stqh_last = SH_PTR_TO_OFF(head, &(head)->stqh_first);   \
 156 }
 157
 158 #define SH_TAILQ_INSERT_HEAD(head, elm, field, type) do {               \
 159         if ((head)->stqh_first != -1) {                                 \
 160                 (elm)->field.stqe_next =                                \
 161                     (head)->stqh_first - SH_PTR_TO_OFF(head, elm);      \
 162                 SH_TAILQ_FIRSTP(head, type)->field.stqe_prev =          \
 163                         SH_TAILQ_NEXT_TO_PREV(elm, field);              \
 164         } else {                                                        \
 165                 (elm)->field.stqe_next = -1;                            \
 166                 (head)->stqh_last =                                     \
 167                     SH_PTR_TO_OFF(head, &(elm)->field.stqe_next);       \
 168         }                                                               \
 169         (head)->stqh_first = SH_PTR_TO_OFF(head, elm);                  \
 170         (elm)->field.stqe_prev =                                        \
 171             SH_PTR_TO_OFF(elm, &(head)->stqh_first);                    \
 172 } while (0)
 173
 174 #define SH_TAILQ_INSERT_TAIL(head, elm, field) do {                     \
 175         (elm)->field.stqe_next = -1;                                    \
 176         (elm)->field.stqe_prev =                                        \
 177             -SH_PTR_TO_OFF(head, elm) + (head)->stqh_last;              \
 178         if ((head)->stqh_last ==                                        \
 179             SH_PTR_TO_OFF((head), &(head)->stqh_first))                 \
 180                 (head)->stqh_first = SH_PTR_TO_OFF(head, elm);          \
 181         else                                                            \
 182                 *SH_TAILQ_LAST(head) = -(head)->stqh_last +             \
 183                     SH_PTR_TO_OFF((elm), &(elm)->field.stqe_next) +     \
 184                     SH_PTR_TO_OFF(head, elm);                           \
 185         (head)->stqh_last =                                             \
 186             SH_PTR_TO_OFF(head, &((elm)->field.stqe_next));             \
 187 } while (0)
 188
 189 #define SH_TAILQ_INSERT_AFTER(head, listelm, elm, field, type) do {     \
 190         if ((listelm)->field.stqe_next != -1) {                         \
 191                 (elm)->field.stqe_next = (listelm)->field.stqe_next -   \
 192                     SH_PTR_TO_OFF(listelm, elm);                        \
 193                 SH_TAILQ_NEXTP(listelm, field, type)->field.stqe_prev = \
 194                     SH_TAILQ_NEXT_TO_PREV(elm, field);                  \
 195         } else {                                                        \
 196                 (elm)->field.stqe_next = -1;                            \
 197                 (head)->stqh_last =                                     \
 198                     SH_PTR_TO_OFF(head, &elm->field.stqe_next);         \
 199         }                                                               \
 200         (listelm)->field.stqe_next = SH_PTR_TO_OFF(listelm, elm);       \
 201         (elm)->field.stqe_prev = SH_TAILQ_NEXT_TO_PREV(listelm, field); \
 202 } while (0)
 203
 204 #define SH_TAILQ_REMOVE(head, elm, field, type) do {                    \
 205         if ((elm)->field.stqe_next != -1) {                             \
 206                 SH_TAILQ_NEXTP(elm, field, type)->field.stqe_prev =     \
 207                     (elm)->field.stqe_prev +                            \
 208                     SH_PTR_TO_OFF(SH_TAILQ_NEXTP(elm,                   \
 209                     field, type), elm);                                 \
 210                 *SH_TAILQ_PREVP(elm, field) += elm->field.stqe_next;    \
 211         } else {                                                        \
 212                 (head)->stqh_last = (elm)->field.stqe_prev +            \
 213                         SH_PTR_TO_OFF(head, elm);                       \
 214                 *SH_TAILQ_PREVP(elm, field) = -1;                       \
 215         }                                                               \
 216 } while (0)
 217
 218 /*
 219  * Shared circular queue definitions.
 220  */
 221 #define SH_CIRCLEQ_HEAD(name)                                           \
 222 struct name {                                                           \
 223         ssize_t scqh_first;             /* first element */             \
 224         ssize_t scqh_last;              /* last element */              \
 225 }
 226
 227 #define SH_CIRCLEQ_ENTRY                                                \
 228 struct {                                                                \
 229         ssize_t scqe_next;              /* next element */              \
 230         ssize_t scqe_prev;              /* previous element */          \
 231 }
 232
 233 /*
 234  * Shared circular queue functions.
 235  */
 236 #define SH_CIRCLEQ_FIRSTP(head, type)                                   \
 237         ((struct type *)(((u_int8_t *)(head)) + (head)->scqh_first))
 238
 239 #define SH_CIRCLEQ_FIRST(head, type)                                    \
 240         ((head)->scqh_first == -1 ?                                     \
 241         (void *)head : SH_CIRCLEQ_FIRSTP(head, type))
 242
 243 #define SH_CIRCLEQ_LASTP(head, type)                                    \
 244         ((struct type *)(((u_int8_t *)(head)) + (head)->scqh_last))
 245
 246 #define SH_CIRCLEQ_LAST(head, type)                                     \
 247         ((head)->scqh_last == -1 ? (void *)head : SH_CIRCLEQ_LASTP(head, type))
 248
 249 #define SH_CIRCLEQ_NEXTP(elm, field, type)                              \
 250         ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.scqe_next))
 251
 252 #define SH_CIRCLEQ_NEXT(head, elm, field, type)                         \
 253         ((elm)->field.scqe_next == SH_PTR_TO_OFF(elm, head) ?           \
 254             (void *)head : SH_CIRCLEQ_NEXTP(elm, field, type))
 255
 256 #define SH_CIRCLEQ_PREVP(elm, field, type)                              \
 257         ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.scqe_prev))
 258
 259 #define SH_CIRCLEQ_PREV(head, elm, field, type)                         \
 260         ((elm)->field.scqe_prev == SH_PTR_TO_OFF(elm, head) ?           \
 261             (void *)head : SH_CIRCLEQ_PREVP(elm, field, type))
 262
 263 #define SH_CIRCLEQ_END(head)            ((void *)(head))
 264
 265 #define SH_CIRCLEQ_INIT(head) {                                         \
 266         (head)->scqh_first = 0;                                         \
 267         (head)->scqh_last = 0;                                          \
 268 }
 269
 270 #define SH_CIRCLEQ_INSERT_AFTER(head, listelm, elm, field, type) do {   \
 271         (elm)->field.scqe_prev = SH_PTR_TO_OFF(elm, listelm);           \
 272         (elm)->field.scqe_next = (listelm)->field.scqe_next +           \
 273             (elm)->field.scqe_prev;                                     \
 274         if (SH_CIRCLEQ_NEXTP(listelm, field, type) == (void *)head)     \
 275                 (head)->scqh_last = SH_PTR_TO_OFF(head, elm);           \
 276         else                                                            \
 277                 SH_CIRCLEQ_NEXTP(listelm,                               \
 278                     field, type)->field.scqe_prev =                     \
 279                     SH_PTR_TO_OFF(SH_CIRCLEQ_NEXTP(listelm,             \
 280                     field, type), elm);                                 \
 281         (listelm)->field.scqe_next = -(elm)->field.scqe_prev;           \
 282 } while (0)
 283
 284 #define SH_CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field, type) do {  \
 285         (elm)->field.scqe_next = SH_PTR_TO_OFF(elm, listelm);           \
 286         (elm)->field.scqe_prev = (elm)->field.scqe_next -               \
 287                 SH_CIRCLEQ_PREVP(listelm, field, type)->field.scqe_next;\
 288         if (SH_CIRCLEQ_PREVP(listelm, field, type) == (void *)(head))   \
 289                 (head)->scqh_first = SH_PTR_TO_OFF(head, elm);          \
 290         else                                                            \
 291                 SH_CIRCLEQ_PREVP(listelm,                               \
 292                     field, type)->field.scqe_next =                     \
 293                     SH_PTR_TO_OFF(SH_CIRCLEQ_PREVP(listelm,             \
 294                     field, type), elm);                                 \
 295         (listelm)->field.scqe_prev = -(elm)->field.scqe_next;           \
 296 } while (0)
 297
 298 #define SH_CIRCLEQ_INSERT_HEAD(head, elm, field, type) do {             \
 299         (elm)->field.scqe_prev = SH_PTR_TO_OFF(elm, head);              \
 300         (elm)->field.scqe_next = (head)->scqh_first +                   \
 301                 (elm)->field.scqe_prev;                                 \
 302         if ((head)->scqh_last == 0)                                     \
 303                 (head)->scqh_last = -(elm)->field.scqe_prev;            \
 304         else                                                            \
 305                 SH_CIRCLEQ_FIRSTP(head, type)->field.scqe_prev =        \
 306                     SH_PTR_TO_OFF(SH_CIRCLEQ_FIRSTP(head, type), elm);  \
 307         (head)->scqh_first = -(elm)->field.scqe_prev;                   \
 308 } while (0)
 309
 310 #define SH_CIRCLEQ_INSERT_TAIL(head, elm, field, type) do {             \
 311         (elm)->field.scqe_next = SH_PTR_TO_OFF(elm, head);              \
 312         (elm)->field.scqe_prev = (head)->scqh_last +                    \
 313             (elm)->field.scqe_next;                                     \
 314         if ((head)->scqh_first == 0)                                    \
 315                 (head)->scqh_first = -(elm)->field.scqe_next;           \
 316         else                                                            \
 317                 SH_CIRCLEQ_LASTP(head, type)->field.scqe_next =         \
 318                     SH_PTR_TO_OFF(SH_CIRCLEQ_LASTP(head, type), elm);   \
 319         (head)->scqh_last = -(elm)->field.scqe_next;                    \
 320 } while (0)
 321
 322 #define SH_CIRCLEQ_REMOVE(head, elm, field, type) do {                  \
 323         if (SH_CIRCLEQ_NEXTP(elm, field, type) == (void *)(head))       \
 324                 (head)->scqh_last += (elm)->field.scqe_prev;            \
 325         else                                                            \
 326                 SH_CIRCLEQ_NEXTP(elm, field, type)->field.scqe_prev +=  \
 327                     (elm)->field.scqe_prev;                             \
 328         if (SH_CIRCLEQ_PREVP(elm, field, type) == (void *)(head))       \
 329                 (head)->scqh_first += (elm)->field.scqe_next;           \
 330         else                                                            \
 331                 SH_CIRCLEQ_PREVP(elm, field, type)->field.scqe_next +=  \
 332                     (elm)->field.scqe_next;                             \
 333 } while (0)
 334 #endif  /* !_SYS_SHQUEUE_H_ */