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