1/*- 2 * See the file LICENSE for redistribution information. 3 * 4 * Copyright (c) 1996,2008 Oracle. All rights reserved. 5 * 6 * $Id: shqueue.h,v 12.13 2008/01/08 20:58:18 bostic Exp $ 7 */ 8 9#ifndef _DB_SHQUEUE_H_ 10#define _DB_SHQUEUE_H_ 11 12/* 13 * This file defines three types of data structures: chains, lists and 14 * tail 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 * Since we use relative offsets of type ssize_t rather than pointers, 0 23 * (aka NULL) is a valid offset and cannot be used to indicate the end 24 * of a list. Therefore, we use -1 to indicate end of list. 25 * 26 * The macros ending in "P" return pointers without checking for end or 27 * beginning of lists, the others check for end of list and evaluate to 28 * either a pointer or NULL. 29 * 30 * For details on the use of these macros, see the queue(3) manual page. 31 */ 32 33#if defined(__cplusplus) 34extern "C" { 35#endif 36 37#define SH_PTR_TO_OFF(src, dest) \ 38 ((ssize_t)(((u_int8_t *)(dest)) - ((u_int8_t *)(src)))) 39 40/* 41 * Shared memory chain definitions. 42 */ 43#define SH_CHAIN_ENTRY \ 44struct { \ 45 ssize_t sce_next; /* relative offset to next element */ \ 46 ssize_t sce_prev; /* relative offset of prev element */ \ 47} 48 49#define SH_CHAIN_INIT(elm, field) \ 50 (elm)->field.sce_next = (elm)->field.sce_prev = -1 51 52#define SH_CHAIN_HASNEXT(elm, field) ((elm)->field.sce_next != -1) 53#define SH_CHAIN_NEXTP(elm, field, type) \ 54 ((struct type *)((u_int8_t *)(elm) + (elm)->field.sce_next)) 55#define SH_CHAIN_NEXT(elm, field, type) (SH_CHAIN_HASNEXT(elm, field) ? \ 56 SH_CHAIN_NEXTP(elm, field, type) : (struct type *)NULL) 57 58#define SH_CHAIN_HASPREV(elm, field) ((elm)->field.sce_prev != -1) 59#define SH_CHAIN_PREVP(elm, field, type) \ 60 ((struct type *)((u_int8_t *)(elm) + (elm)->field.sce_prev)) 61#define SH_CHAIN_PREV(elm, field, type) (SH_CHAIN_HASPREV(elm, field) ? \ 62 SH_CHAIN_PREVP(elm, field, type) : (struct type *)NULL) 63 64#define SH_CHAIN_SINGLETON(elm, field) \ 65 (!(SH_CHAIN_HASNEXT(elm, field) || SH_CHAIN_HASPREV(elm, field))) 66 67#define SH_CHAIN_INSERT_AFTER(listelm, elm, field, type) do { \ 68 struct type *__next = SH_CHAIN_NEXT(listelm, field, type); \ 69 if (__next != NULL) { \ 70 (elm)->field.sce_next = SH_PTR_TO_OFF(elm, __next); \ 71 __next->field.sce_prev = SH_PTR_TO_OFF(__next, elm); \ 72 } else \ 73 (elm)->field.sce_next = -1; \ 74 (elm)->field.sce_prev = SH_PTR_TO_OFF(elm, listelm); \ 75 (listelm)->field.sce_next = SH_PTR_TO_OFF(listelm, elm); \ 76} while (0) 77 78#define SH_CHAIN_INSERT_BEFORE(listelm, elm, field, type) do { \ 79 struct type *__prev = SH_CHAIN_PREV(listelm, field, type); \ 80 if (__prev != NULL) { \ 81 (elm)->field.sce_prev = SH_PTR_TO_OFF(elm, __prev); \ 82 __prev->field.sce_next = SH_PTR_TO_OFF(__prev, elm); \ 83 } else \ 84 (elm)->field.sce_prev = -1; \ 85 (elm)->field.sce_next = SH_PTR_TO_OFF(elm, listelm); \ 86 (listelm)->field.sce_prev = SH_PTR_TO_OFF(listelm, elm); \ 87} while (0) 88 89#define SH_CHAIN_REMOVE(elm, field, type) do { \ 90 struct type *__prev = SH_CHAIN_PREV(elm, field, type); \ 91 struct type *__next = SH_CHAIN_NEXT(elm, field, type); \ 92 if (__next != NULL) \ 93 __next->field.sce_prev = (__prev == NULL) ? -1 : \ 94 SH_PTR_TO_OFF(__next, __prev); \ 95 if (__prev != NULL) \ 96 __prev->field.sce_next = (__next == NULL) ? -1 : \ 97 SH_PTR_TO_OFF(__prev, __next); \ 98 SH_CHAIN_INIT(elm, field); \ 99} while (0) 100 101/* 102 * Shared memory list definitions. 103 */ 104#define SH_LIST_HEAD(name) \ 105struct name { \ 106 ssize_t slh_first; /* first element */ \ 107} 108 109#define SH_LIST_HEAD_INITIALIZER(head) \ 110 { -1 } 111 112#define SH_LIST_ENTRY \ 113struct { \ 114 ssize_t sle_next; /* relative offset to next element */ \ 115 ssize_t sle_prev; /* relative offset of prev element */ \ 116} 117 118/* 119 * Shared memory list functions. 120 */ 121#define SH_LIST_EMPTY(head) \ 122 ((head)->slh_first == -1) 123 124#define SH_LIST_FIRSTP(head, type) \ 125 ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first)) 126 127#define SH_LIST_FIRST(head, type) \ 128 (SH_LIST_EMPTY(head) ? NULL : \ 129 ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first))) 130 131#define SH_LIST_NEXTP(elm, field, type) \ 132 ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next)) 133 134#define SH_LIST_NEXT(elm, field, type) \ 135 ((elm)->field.sle_next == -1 ? NULL : \ 136 ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next))) 137 138 /* 139 *__SH_LIST_PREV_OFF is private API. It calculates the address of 140 * the elm->field.sle_next member of a SH_LIST structure. All offsets 141 * between elements are relative to that point in SH_LIST structures. 142 */ 143#define __SH_LIST_PREV_OFF(elm, field) \ 144 ((ssize_t *)(((u_int8_t *)(elm)) + (elm)->field.sle_prev)) 145 146#define SH_LIST_PREV(elm, field, type) \ 147 (struct type *)((ssize_t)(elm) - (*__SH_LIST_PREV_OFF(elm, field))) 148 149#define SH_LIST_FOREACH(var, head, field, type) \ 150 for ((var) = SH_LIST_FIRST((head), type); \ 151 (var) != NULL; \ 152 (var) = SH_LIST_NEXT((var), field, type)) 153 154/* 155 * Given correct A.next: B.prev = SH_LIST_NEXT_TO_PREV(A) 156 * in a list [A, B] 157 * The prev value is always the offset from an element to its preceding 158 * element's next location, not the beginning of the structure. To get 159 * to the beginning of an element structure in memory given an element 160 * do the following: 161 * A = B - (B.prev + (&B.next - B)) 162 * Take the element's next pointer and calculate what the corresponding 163 * Prev pointer should be -- basically it is the negation plus the offset 164 * of the next field in the structure. 165 */ 166#define SH_LIST_NEXT_TO_PREV(elm, field) \ 167 (((elm)->field.sle_next == -1 ? 0 : -(elm)->field.sle_next) + \ 168 SH_PTR_TO_OFF(elm, &(elm)->field.sle_next)) 169 170#define SH_LIST_INIT(head) (head)->slh_first = -1 171 172#define SH_LIST_INSERT_BEFORE(head, listelm, elm, field, type) do { \ 173 if (listelm == SH_LIST_FIRST(head, type)) { \ 174 SH_LIST_INSERT_HEAD(head, elm, field, type); \ 175 } else { \ 176 (elm)->field.sle_next = SH_PTR_TO_OFF(elm, listelm); \ 177 (elm)->field.sle_prev = SH_LIST_NEXT_TO_PREV( \ 178 SH_LIST_PREV((listelm), field, type), field) + \ 179 (elm)->field.sle_next; \ 180 (SH_LIST_PREV(listelm, field, type))->field.sle_next = \ 181 (SH_PTR_TO_OFF((SH_LIST_PREV(listelm, field, \ 182 type)), elm)); \ 183 (listelm)->field.sle_prev = SH_LIST_NEXT_TO_PREV(elm, field); \ 184 } \ 185} while (0) 186 187#define SH_LIST_INSERT_AFTER(listelm, elm, field, type) do { \ 188 if ((listelm)->field.sle_next != -1) { \ 189 (elm)->field.sle_next = SH_PTR_TO_OFF(elm, \ 190 SH_LIST_NEXTP(listelm, field, type)); \ 191 SH_LIST_NEXTP(listelm, field, type)->field.sle_prev = \ 192 SH_LIST_NEXT_TO_PREV(elm, field); \ 193 } else \ 194 (elm)->field.sle_next = -1; \ 195 (listelm)->field.sle_next = SH_PTR_TO_OFF(listelm, elm); \ 196 (elm)->field.sle_prev = SH_LIST_NEXT_TO_PREV(listelm, field); \ 197} while (0) 198 199#define SH_LIST_INSERT_HEAD(head, elm, field, type) do { \ 200 if ((head)->slh_first != -1) { \ 201 (elm)->field.sle_next = \ 202 (head)->slh_first - SH_PTR_TO_OFF(head, elm); \ 203 SH_LIST_FIRSTP(head, type)->field.sle_prev = \ 204 SH_LIST_NEXT_TO_PREV(elm, field); \ 205 } else \ 206 (elm)->field.sle_next = -1; \ 207 (head)->slh_first = SH_PTR_TO_OFF(head, elm); \ 208 (elm)->field.sle_prev = SH_PTR_TO_OFF(elm, &(head)->slh_first); \ 209} while (0) 210 211#define SH_LIST_REMOVE(elm, field, type) do { \ 212 if ((elm)->field.sle_next != -1) { \ 213 SH_LIST_NEXTP(elm, field, type)->field.sle_prev = \ 214 (elm)->field.sle_prev - (elm)->field.sle_next; \ 215 *__SH_LIST_PREV_OFF(elm, field) += (elm)->field.sle_next;\ 216 } else \ 217 *__SH_LIST_PREV_OFF(elm, field) = -1; \ 218} while (0) 219 220#define SH_LIST_REMOVE_HEAD(head, field, type) do { \ 221 if (!SH_LIST_EMPTY(head)) { \ 222 SH_LIST_REMOVE(SH_LIST_FIRSTP(head, type), field, type);\ 223 } \ 224} while (0) 225 226/* 227 * Shared memory tail queue definitions. 228 */ 229#define SH_TAILQ_HEAD(name) \ 230struct name { \ 231 ssize_t stqh_first; /* relative offset of first element */ \ 232 ssize_t stqh_last; /* relative offset of last's next */ \ 233} 234 235#define SH_TAILQ_HEAD_INITIALIZER(head) \ 236 { -1, 0 } 237 238#define SH_TAILQ_ENTRY \ 239struct { \ 240 ssize_t stqe_next; /* relative offset of next element */ \ 241 ssize_t stqe_prev; /* relative offset of prev's next */ \ 242} 243 244/* 245 * Shared memory tail queue functions. 246 */ 247 248#define SH_TAILQ_EMPTY(head) \ 249 ((head)->stqh_first == -1) 250 251#define SH_TAILQ_FIRSTP(head, type) \ 252 ((struct type *)((u_int8_t *)(head) + (head)->stqh_first)) 253 254#define SH_TAILQ_FIRST(head, type) \ 255 (SH_TAILQ_EMPTY(head) ? NULL : SH_TAILQ_FIRSTP(head, type)) 256 257#define SH_TAILQ_NEXTP(elm, field, type) \ 258 ((struct type *)((u_int8_t *)(elm) + (elm)->field.stqe_next)) 259 260#define SH_TAILQ_NEXT(elm, field, type) \ 261 ((elm)->field.stqe_next == -1 ? NULL : \ 262 ((struct type *)((u_int8_t *)(elm) + (elm)->field.stqe_next))) 263 264 /* 265 * __SH_TAILQ_PREV_OFF is private API. It calculates the address of 266 * the elm->field.stqe_next member of a SH_TAILQ structure. All 267 * offsets between elements are relative to that point in SH_TAILQ 268 * structures. 269 */ 270#define __SH_TAILQ_PREV_OFF(elm, field) \ 271 ((ssize_t *)(((u_int8_t *)(elm)) + (elm)->field.stqe_prev)) 272 273#define SH_TAILQ_PREVP(elm, field, type) \ 274 (struct type *)((ssize_t)elm - (*__SH_TAILQ_PREV_OFF(elm, field))) 275 276#define SH_TAILQ_PREV(head, elm, field, type) \ 277 (((elm) == SH_TAILQ_FIRST(head, type)) ? NULL : \ 278 (struct type *)((ssize_t)elm - (*__SH_TAILQ_PREV_OFF(elm, field)))) 279 280 /* 281 * __SH_TAILQ_LAST_OFF is private API. It calculates the address of 282 * the stqe_next member of a SH_TAILQ structure in the last element 283 * of this list. All offsets between elements are relative to that 284 * point in SH_TAILQ structures. 285 */ 286#define __SH_TAILQ_LAST_OFF(head) \ 287 ((ssize_t *)(((u_int8_t *)(head)) + (head)->stqh_last)) 288 289#define SH_TAILQ_LASTP(head, field, type) \ 290 ((struct type *)((ssize_t)(head) + \ 291 ((ssize_t)((head)->stqh_last) - \ 292 ((ssize_t)SH_PTR_TO_OFF(SH_TAILQ_FIRST(head, type), \ 293 &(SH_TAILQ_FIRSTP(head, type)->field.stqe_next)))))) 294 295#define SH_TAILQ_LAST(head, field, type) \ 296 (SH_TAILQ_EMPTY(head) ? NULL : SH_TAILQ_LASTP(head, field, type)) 297 298/* 299 * Given correct A.next: B.prev = SH_TAILQ_NEXT_TO_PREV(A) 300 * in a list [A, B] 301 * The prev value is always the offset from an element to its preceding 302 * element's next location, not the beginning of the structure. To get 303 * to the beginning of an element structure in memory given an element 304 * do the following: 305 * A = B - (B.prev + (&B.next - B)) 306 */ 307#define SH_TAILQ_NEXT_TO_PREV(elm, field) \ 308 (((elm)->field.stqe_next == -1 ? 0 : \ 309 (-(elm)->field.stqe_next) + \ 310 SH_PTR_TO_OFF(elm, &(elm)->field.stqe_next))) 311 312#define SH_TAILQ_FOREACH(var, head, field, type) \ 313 for ((var) = SH_TAILQ_FIRST((head), type); \ 314 (var) != NULL; \ 315 (var) = SH_TAILQ_NEXT((var), field, type)) 316 317#define SH_TAILQ_FOREACH_REVERSE(var, head, field, type) \ 318 for ((var) = SH_TAILQ_LAST((head), field, type); \ 319 (var) != NULL; \ 320 (var) = SH_TAILQ_PREV((head), (var), field, type)) 321 322#define SH_TAILQ_INIT(head) { \ 323 (head)->stqh_first = -1; \ 324 (head)->stqh_last = SH_PTR_TO_OFF(head, &(head)->stqh_first); \ 325} 326 327#define SH_TAILQ_INSERT_HEAD(head, elm, field, type) do { \ 328 if ((head)->stqh_first != -1) { \ 329 (elm)->field.stqe_next = \ 330 (head)->stqh_first - SH_PTR_TO_OFF(head, elm); \ 331 SH_TAILQ_FIRSTP(head, type)->field.stqe_prev = \ 332 SH_TAILQ_NEXT_TO_PREV(elm, field); \ 333 } else { \ 334 (head)->stqh_last = \ 335 SH_PTR_TO_OFF(head, &(elm)->field.stqe_next); \ 336 (elm)->field.stqe_next = -1; \ 337 } \ 338 (head)->stqh_first = SH_PTR_TO_OFF(head, elm); \ 339 (elm)->field.stqe_prev = \ 340 SH_PTR_TO_OFF(elm, &(head)->stqh_first); \ 341} while (0) 342 343#define SH_TAILQ_INSERT_TAIL(head, elm, field) do { \ 344 (elm)->field.stqe_next = -1; \ 345 (elm)->field.stqe_prev = \ 346 -SH_PTR_TO_OFF(head, elm) + (head)->stqh_last; \ 347 if ((head)->stqh_last == \ 348 SH_PTR_TO_OFF((head), &(head)->stqh_first)) \ 349 (head)->stqh_first = SH_PTR_TO_OFF(head, elm); \ 350 else \ 351 *__SH_TAILQ_LAST_OFF(head) = -(head)->stqh_last + \ 352 SH_PTR_TO_OFF((elm), &(elm)->field.stqe_next) + \ 353 SH_PTR_TO_OFF(head, elm); \ 354 (head)->stqh_last = \ 355 SH_PTR_TO_OFF(head, &((elm)->field.stqe_next)); \ 356} while (0) 357 358#define SH_TAILQ_INSERT_BEFORE(head, listelm, elm, field, type) do { \ 359 if (listelm == SH_TAILQ_FIRST(head, type)) { \ 360 SH_TAILQ_INSERT_HEAD(head, elm, field, type); \ 361 } else { \ 362 (elm)->field.stqe_next = SH_PTR_TO_OFF(elm, listelm); \ 363 (elm)->field.stqe_prev = SH_TAILQ_NEXT_TO_PREV( \ 364 SH_TAILQ_PREVP((listelm), field, type), field) + \ 365 (elm)->field.stqe_next; \ 366 (SH_TAILQ_PREVP(listelm, field, type))->field.stqe_next =\ 367 (SH_PTR_TO_OFF((SH_TAILQ_PREVP(listelm, field, type)), \ 368 elm)); \ 369 (listelm)->field.stqe_prev = \ 370 SH_TAILQ_NEXT_TO_PREV(elm, field); \ 371 } \ 372} while (0) 373 374#define SH_TAILQ_INSERT_AFTER(head, listelm, elm, field, type) do { \ 375 if ((listelm)->field.stqe_next != -1) { \ 376 (elm)->field.stqe_next = (listelm)->field.stqe_next - \ 377 SH_PTR_TO_OFF(listelm, elm); \ 378 SH_TAILQ_NEXTP(listelm, field, type)->field.stqe_prev = \ 379 SH_TAILQ_NEXT_TO_PREV(elm, field); \ 380 } else { \ 381 (elm)->field.stqe_next = -1; \ 382 (head)->stqh_last = \ 383 SH_PTR_TO_OFF(head, &(elm)->field.stqe_next); \ 384 } \ 385 (listelm)->field.stqe_next = SH_PTR_TO_OFF(listelm, elm); \ 386 (elm)->field.stqe_prev = SH_TAILQ_NEXT_TO_PREV(listelm, field); \ 387} while (0) 388 389#define SH_TAILQ_REMOVE(head, elm, field, type) do { \ 390 if ((elm)->field.stqe_next != -1) { \ 391 SH_TAILQ_NEXTP(elm, field, type)->field.stqe_prev = \ 392 (elm)->field.stqe_prev + \ 393 SH_PTR_TO_OFF(SH_TAILQ_NEXTP(elm, \ 394 field, type), elm); \ 395 *__SH_TAILQ_PREV_OFF(elm, field) += (elm)->field.stqe_next;\ 396 } else { \ 397 (head)->stqh_last = (elm)->field.stqe_prev + \ 398 SH_PTR_TO_OFF(head, elm); \ 399 *__SH_TAILQ_PREV_OFF(elm, field) = -1; \ 400 } \ 401} while (0) 402 403#if defined(__cplusplus) 404} 405#endif 406#endif /* !_DB_SHQUEUE_H_ */ 407