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