diff options
Diffstat (limited to 'db/dbinc/shqueue.h')
| -rw-r--r-- | db/dbinc/shqueue.h | 300 |
1 files changed, 154 insertions, 146 deletions
diff --git a/db/dbinc/shqueue.h b/db/dbinc/shqueue.h index e0b81d537..20a5234c7 100644 --- a/db/dbinc/shqueue.h +++ b/db/dbinc/shqueue.h @@ -1,18 +1,18 @@ /*- * See the file LICENSE for redistribution information. * - * Copyright (c) 1996-2002 + * Copyright (c) 1996-2003 * Sleepycat Software. All rights reserved. * - * Id: shqueue.h,v 11.9 2002/01/11 15:52:30 bostic Exp + * $Id: shqueue.h,v 11.13 2003/04/24 15:41:02 bostic Exp $ */ #ifndef _SYS_SHQUEUE_H_ #define _SYS_SHQUEUE_H_ /* - * This file defines three types of data structures: lists, tail queues, and - * circular queues, similarly to the include file <sys/queue.h>. + * This file defines two types of data structures: lists and tail queues + * similarly to the include file <sys/queue.h>. * * The difference is that this set of macros can be used for structures that * reside in shared memory that may be mapped at different addresses in each @@ -20,6 +20,14 @@ * the normal macros, although the macro calls require an additional type * parameter, only used by the HEAD and ENTRY macros of the standard macros. * + * Since we use relative offsets of type ssize_t rather than pointers, 0 + * (aka NULL) is a valid offset and cannot be used to indicate the end + * of a list. Therefore, we use -1 to indicate end of list. + * + * The macros ending in "P" return pointers without checking for end or + * beginning of lists, the others check for end of list and evaluate to + * either a pointer or NULL. + * * For details on the use of these macros, see the queue(3) manual page. */ @@ -28,32 +36,34 @@ extern "C" { #endif /* - * Shared list definitions. + * Shared memory list definitions. */ #define SH_LIST_HEAD(name) \ struct name { \ ssize_t slh_first; /* first element */ \ } +#define SH_LIST_HEAD_INITIALIZER(head) \ + { -1 } + #define SH_LIST_ENTRY \ struct { \ - ssize_t sle_next; /* relative offset next element */ \ + ssize_t sle_next; /* relative offset to next element */ \ ssize_t sle_prev; /* relative offset of prev element */ \ } /* - * Shared list functions. Since we use relative offsets for pointers, - * 0 is a valid offset. Therefore, we use -1 to indicate end of list. - * The macros ending in "P" return pointers without checking for end - * of list, the others check for end of list and evaluate to either a - * pointer or NULL. + * Shared memory list functions. */ +#define SH_LIST_EMPTY(head) \ + ((head)->slh_first == -1) + #define SH_LIST_FIRSTP(head, type) \ ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first)) #define SH_LIST_FIRST(head, type) \ - ((head)->slh_first == -1 ? NULL : \ + (SH_LIST_EMPTY(head) ? NULL : \ ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first))) #define SH_LIST_NEXTP(elm, field, type) \ @@ -63,22 +73,58 @@ struct { \ ((elm)->field.sle_next == -1 ? NULL : \ ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next))) -#define SH_LIST_PREV(elm, field) \ + /* + *__SH_LIST_PREV_OFF is private API. It calculates the address of + * the elm->field.sle_next member of a SH_LIST structure. All offsets + * between elements are relative to that point in SH_LIST structures. + */ +#define __SH_LIST_PREV_OFF(elm, field) \ ((ssize_t *)(((u_int8_t *)(elm)) + (elm)->field.sle_prev)) +#define SH_LIST_PREV(elm, field, type) \ + (struct type *)((ssize_t)elm - (*__SH_LIST_PREV_OFF(elm, field))) + +#define SH_LIST_FOREACH(var, head, field, type) \ + for ((var) = SH_LIST_FIRST((head), type); \ + (var); \ + (var) = SH_LIST_NEXT((var), field, type)) + #define SH_PTR_TO_OFF(src, dest) \ ((ssize_t)(((u_int8_t *)(dest)) - ((u_int8_t *)(src)))) /* + * Given correct A.next: B.prev = SH_LIST_NEXT_TO_PREV(A) + * in a list [A, B] + * The prev value is always the offset from an element to its preceeding + * element's next location, not the beginning of the structure. To get + * to the beginning of an element structure in memory given an element + * do the following: + * A = B - (B.prev + (&B.next - B)) * Take the element's next pointer and calculate what the corresponding * Prev pointer should be -- basically it is the negation plus the offset * of the next field in the structure. */ #define SH_LIST_NEXT_TO_PREV(elm, field) \ - (-(elm)->field.sle_next + SH_PTR_TO_OFF(elm, &(elm)->field.sle_next)) + (((elm)->field.sle_next == -1 ? 0 : -(elm)->field.sle_next) + \ + SH_PTR_TO_OFF(elm, &(elm)->field.sle_next)) #define SH_LIST_INIT(head) (head)->slh_first = -1 +#define SH_LIST_INSERT_BEFORE(head, listelm, elm, field, type) do { \ + if (listelm == SH_LIST_FIRST(head, type)) { \ + SH_LIST_INSERT_HEAD(head, elm, field, type); \ + } else { \ + (elm)->field.sle_next = SH_PTR_TO_OFF(elm, listelm); \ + (elm)->field.sle_prev = SH_LIST_NEXT_TO_PREV( \ + SH_LIST_PREV((listelm), field, type), field) + \ + (elm)->field.sle_next; \ + (SH_LIST_PREV(listelm, field, type))->field.sle_next = \ + (SH_PTR_TO_OFF((SH_LIST_PREV(listelm, field, \ + type)), elm)); \ + (listelm)->field.sle_prev = SH_LIST_NEXT_TO_PREV(elm, field); \ + } \ +} while (0) + #define SH_LIST_INSERT_AFTER(listelm, elm, field, type) do { \ if ((listelm)->field.sle_next != -1) { \ (elm)->field.sle_next = SH_PTR_TO_OFF(elm, \ @@ -93,7 +139,7 @@ struct { \ #define SH_LIST_INSERT_HEAD(head, elm, field, type) do { \ if ((head)->slh_first != -1) { \ - (elm)->field.sle_next = \ + (elm)->field.sle_next = \ (head)->slh_first - SH_PTR_TO_OFF(head, elm); \ SH_LIST_FIRSTP(head, type)->field.sle_prev = \ SH_LIST_NEXT_TO_PREV(elm, field); \ @@ -107,13 +153,19 @@ struct { \ if ((elm)->field.sle_next != -1) { \ SH_LIST_NEXTP(elm, field, type)->field.sle_prev = \ (elm)->field.sle_prev - (elm)->field.sle_next; \ - *SH_LIST_PREV(elm, field) += (elm)->field.sle_next; \ + *__SH_LIST_PREV_OFF(elm, field) += (elm)->field.sle_next;\ } else \ - *SH_LIST_PREV(elm, field) = -1; \ + *__SH_LIST_PREV_OFF(elm, field) = -1; \ +} while (0) + +#define SH_LIST_REMOVE_HEAD(head, field, type) do { \ + if (!SH_LIST_EMPTY(head)) { \ + SH_LIST_REMOVE(SH_LIST_FIRSTP(head, type), field, type);\ + } \ } while (0) /* - * Shared tail queue definitions. + * Shared memory tail queue definitions. */ #define SH_TAILQ_HEAD(name) \ struct name { \ @@ -121,6 +173,9 @@ struct name { \ ssize_t stqh_last; /* relative offset of last's next */ \ } +#define SH_TAILQ_HEAD_INITIALIZER(head) \ + { -1, 0 } + #define SH_TAILQ_ENTRY \ struct { \ ssize_t stqe_next; /* relative offset of next element */ \ @@ -128,28 +183,80 @@ struct { \ } /* - * Shared tail queue functions. + * Shared memory tail queue functions. */ + +#define SH_TAILQ_EMPTY(head) \ + ((head)->stqh_first == -1) + #define SH_TAILQ_FIRSTP(head, type) \ ((struct type *)((u_int8_t *)(head) + (head)->stqh_first)) #define SH_TAILQ_FIRST(head, type) \ - ((head)->stqh_first == -1 ? NULL : SH_TAILQ_FIRSTP(head, type)) + (SH_TAILQ_EMPTY(head) ? NULL : SH_TAILQ_FIRSTP(head, type)) #define SH_TAILQ_NEXTP(elm, field, type) \ ((struct type *)((u_int8_t *)(elm) + (elm)->field.stqe_next)) #define SH_TAILQ_NEXT(elm, field, type) \ - ((elm)->field.stqe_next == -1 ? NULL : SH_TAILQ_NEXTP(elm, field, type)) - -#define SH_TAILQ_PREVP(elm, field) \ - ((ssize_t *)((u_int8_t *)(elm) + (elm)->field.stqe_prev)) - -#define SH_TAILQ_LAST(head) \ + ((elm)->field.stqe_next == -1 ? NULL : \ + ((struct type *)((u_int8_t *)(elm) + (elm)->field.stqe_next))) + + /* + * __SH_TAILQ_PREV_OFF is private API. It calculates the address of + * the elm->field.stqe_next member of a SH_TAILQ structure. All + * offsets between elements are relative to that point in SH_TAILQ + * structures. + */ +#define __SH_TAILQ_PREV_OFF(elm, field) \ + ((ssize_t *)(((u_int8_t *)(elm)) + (elm)->field.stqe_prev)) + +#define SH_TAILQ_PREVP(elm, field, type) \ + (struct type *)((ssize_t)elm - (*__SH_TAILQ_PREV_OFF(elm, field))) + +#define SH_TAILQ_PREV(head, elm, field, type) \ + (((elm) == SH_TAILQ_FIRST(head, type)) ? NULL : \ + (struct type *)((ssize_t)elm - (*__SH_TAILQ_PREV_OFF(elm, field)))) + + /* + * __SH_TAILQ_LAST_OFF is private API. It calculates the address of + * the stqe_next member of a SH_TAILQ structure in the last element + * of this list. All offsets between elements are relative to that + * point in SH_TAILQ structures. + */ +#define __SH_TAILQ_LAST_OFF(head) \ ((ssize_t *)(((u_int8_t *)(head)) + (head)->stqh_last)) +#define SH_TAILQ_LAST(head, field, type) \ + (SH_TAILQ_EMPTY(head) ? NULL : \ + (struct type *)((ssize_t)(head) + \ + ((ssize_t)((head)->stqh_last) - \ + ((ssize_t)SH_PTR_TO_OFF(SH_TAILQ_FIRST(head, type), \ + &(SH_TAILQ_FIRST(head, type)->field.stqe_next)))))) + +/* + * Given correct A.next: B.prev = SH_TAILQ_NEXT_TO_PREV(A) + * in a list [A, B] + * The prev value is always the offset from an element to its preceeding + * element's next location, not the beginning of the structure. To get + * to the beginning of an element structure in memory given an element + * do the following: + * A = B - (B.prev + (&B.next - B)) + */ #define SH_TAILQ_NEXT_TO_PREV(elm, field) \ - (-(elm)->field.stqe_next + SH_PTR_TO_OFF(elm, &(elm)->field.stqe_next)) + (((elm)->field.stqe_next == -1 ? 0 : \ + (-(elm)->field.stqe_next) + \ + SH_PTR_TO_OFF(elm, &(elm)->field.stqe_next))) + +#define SH_TAILQ_FOREACH(var, head, field, type) \ + for ((var) = SH_TAILQ_FIRST((head), type); \ + (var); \ + (var) = SH_TAILQ_NEXT((var), field, type)) + +#define SH_TAILQ_FOREACH_REVERSE(var, head, field, type) \ + for ((var) = SH_TAILQ_LAST((head), field, type); \ + (var); \ + (var) = SH_TAILQ_PREV((head), (var), field, type)) #define SH_TAILQ_INIT(head) { \ (head)->stqh_first = -1; \ @@ -163,9 +270,9 @@ struct { \ SH_TAILQ_FIRSTP(head, type)->field.stqe_prev = \ SH_TAILQ_NEXT_TO_PREV(elm, field); \ } else { \ - (elm)->field.stqe_next = -1; \ (head)->stqh_last = \ SH_PTR_TO_OFF(head, &(elm)->field.stqe_next); \ + (elm)->field.stqe_next = -1; \ } \ (head)->stqh_first = SH_PTR_TO_OFF(head, elm); \ (elm)->field.stqe_prev = \ @@ -180,13 +287,29 @@ struct { \ SH_PTR_TO_OFF((head), &(head)->stqh_first)) \ (head)->stqh_first = SH_PTR_TO_OFF(head, elm); \ else \ - *SH_TAILQ_LAST(head) = -(head)->stqh_last + \ + *__SH_TAILQ_LAST_OFF(head) = -(head)->stqh_last + \ SH_PTR_TO_OFF((elm), &(elm)->field.stqe_next) + \ SH_PTR_TO_OFF(head, elm); \ (head)->stqh_last = \ SH_PTR_TO_OFF(head, &((elm)->field.stqe_next)); \ } while (0) +#define SH_TAILQ_INSERT_BEFORE(head, listelm, elm, field, type) do { \ + if (listelm == SH_TAILQ_FIRST(head, type)) { \ + SH_TAILQ_INSERT_HEAD(head, elm, field, type); \ + } else { \ + (elm)->field.stqe_next = SH_PTR_TO_OFF(elm, listelm); \ + (elm)->field.stqe_prev = SH_TAILQ_NEXT_TO_PREV( \ + SH_TAILQ_PREVP((listelm), field, type), field) + \ + (elm)->field.stqe_next; \ + (SH_TAILQ_PREVP(listelm, field, type))->field.stqe_next =\ + (SH_PTR_TO_OFF((SH_TAILQ_PREVP(listelm, field, type)), \ + elm)); \ + (listelm)->field.stqe_prev = \ + SH_TAILQ_NEXT_TO_PREV(elm, field); \ + } \ +} while (0) + #define SH_TAILQ_INSERT_AFTER(head, listelm, elm, field, type) do { \ if ((listelm)->field.stqe_next != -1) { \ (elm)->field.stqe_next = (listelm)->field.stqe_next - \ @@ -208,129 +331,14 @@ struct { \ (elm)->field.stqe_prev + \ SH_PTR_TO_OFF(SH_TAILQ_NEXTP(elm, \ field, type), elm); \ - *SH_TAILQ_PREVP(elm, field) += elm->field.stqe_next; \ + *__SH_TAILQ_PREV_OFF(elm, field) += elm->field.stqe_next;\ } else { \ (head)->stqh_last = (elm)->field.stqe_prev + \ SH_PTR_TO_OFF(head, elm); \ - *SH_TAILQ_PREVP(elm, field) = -1; \ + *__SH_TAILQ_PREV_OFF(elm, field) = -1; \ } \ } while (0) -/* - * Shared circular queue definitions. - */ -#define SH_CIRCLEQ_HEAD(name) \ -struct name { \ - ssize_t scqh_first; /* first element */ \ - ssize_t scqh_last; /* last element */ \ -} - -#define SH_CIRCLEQ_ENTRY \ -struct { \ - ssize_t scqe_next; /* next element */ \ - ssize_t scqe_prev; /* previous element */ \ -} - -/* - * Shared circular queue functions. - */ -#define SH_CIRCLEQ_FIRSTP(head, type) \ - ((struct type *)(((u_int8_t *)(head)) + (head)->scqh_first)) - -#define SH_CIRCLEQ_FIRST(head, type) \ - ((head)->scqh_first == -1 ? \ - (void *)head : SH_CIRCLEQ_FIRSTP(head, type)) - -#define SH_CIRCLEQ_LASTP(head, type) \ - ((struct type *)(((u_int8_t *)(head)) + (head)->scqh_last)) - -#define SH_CIRCLEQ_LAST(head, type) \ - ((head)->scqh_last == -1 ? (void *)head : SH_CIRCLEQ_LASTP(head, type)) - -#define SH_CIRCLEQ_NEXTP(elm, field, type) \ - ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.scqe_next)) - -#define SH_CIRCLEQ_NEXT(head, elm, field, type) \ - ((elm)->field.scqe_next == SH_PTR_TO_OFF(elm, head) ? \ - (void *)head : SH_CIRCLEQ_NEXTP(elm, field, type)) - -#define SH_CIRCLEQ_PREVP(elm, field, type) \ - ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.scqe_prev)) - -#define SH_CIRCLEQ_PREV(head, elm, field, type) \ - ((elm)->field.scqe_prev == SH_PTR_TO_OFF(elm, head) ? \ - (void *)head : SH_CIRCLEQ_PREVP(elm, field, type)) - -#define SH_CIRCLEQ_INIT(head) { \ - (head)->scqh_first = 0; \ - (head)->scqh_last = 0; \ -} - -#define SH_CIRCLEQ_INSERT_AFTER(head, listelm, elm, field, type) do { \ - (elm)->field.scqe_prev = SH_PTR_TO_OFF(elm, listelm); \ - (elm)->field.scqe_next = (listelm)->field.scqe_next + \ - (elm)->field.scqe_prev; \ - if (SH_CIRCLEQ_NEXTP(listelm, field, type) == (void *)head) \ - (head)->scqh_last = SH_PTR_TO_OFF(head, elm); \ - else \ - SH_CIRCLEQ_NEXTP(listelm, \ - field, type)->field.scqe_prev = \ - SH_PTR_TO_OFF(SH_CIRCLEQ_NEXTP(listelm, \ - field, type), elm); \ - (listelm)->field.scqe_next = -(elm)->field.scqe_prev; \ -} while (0) - -#define SH_CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field, type) do { \ - (elm)->field.scqe_next = SH_PTR_TO_OFF(elm, listelm); \ - (elm)->field.scqe_prev = (elm)->field.scqe_next - \ - SH_CIRCLEQ_PREVP(listelm, field, type)->field.scqe_next;\ - if (SH_CIRCLEQ_PREVP(listelm, field, type) == (void *)(head)) \ - (head)->scqh_first = SH_PTR_TO_OFF(head, elm); \ - else \ - SH_CIRCLEQ_PREVP(listelm, \ - field, type)->field.scqe_next = \ - SH_PTR_TO_OFF(SH_CIRCLEQ_PREVP(listelm, \ - field, type), elm); \ - (listelm)->field.scqe_prev = -(elm)->field.scqe_next; \ -} while (0) - -#define SH_CIRCLEQ_INSERT_HEAD(head, elm, field, type) do { \ - (elm)->field.scqe_prev = SH_PTR_TO_OFF(elm, head); \ - (elm)->field.scqe_next = (head)->scqh_first + \ - (elm)->field.scqe_prev; \ - if ((head)->scqh_last == 0) \ - (head)->scqh_last = -(elm)->field.scqe_prev; \ - else \ - SH_CIRCLEQ_FIRSTP(head, type)->field.scqe_prev = \ - SH_PTR_TO_OFF(SH_CIRCLEQ_FIRSTP(head, type), elm); \ - (head)->scqh_first = -(elm)->field.scqe_prev; \ -} while (0) - -#define SH_CIRCLEQ_INSERT_TAIL(head, elm, field, type) do { \ - (elm)->field.scqe_next = SH_PTR_TO_OFF(elm, head); \ - (elm)->field.scqe_prev = (head)->scqh_last + \ - (elm)->field.scqe_next; \ - if ((head)->scqh_first == 0) \ - (head)->scqh_first = -(elm)->field.scqe_next; \ - else \ - SH_CIRCLEQ_LASTP(head, type)->field.scqe_next = \ - SH_PTR_TO_OFF(SH_CIRCLEQ_LASTP(head, type), elm); \ - (head)->scqh_last = -(elm)->field.scqe_next; \ -} while (0) - -#define SH_CIRCLEQ_REMOVE(head, elm, field, type) do { \ - if (SH_CIRCLEQ_NEXTP(elm, field, type) == (void *)(head)) \ - (head)->scqh_last += (elm)->field.scqe_prev; \ - else \ - SH_CIRCLEQ_NEXTP(elm, field, type)->field.scqe_prev += \ - (elm)->field.scqe_prev; \ - if (SH_CIRCLEQ_PREVP(elm, field, type) == (void *)(head)) \ - (head)->scqh_first += (elm)->field.scqe_next; \ - else \ - SH_CIRCLEQ_PREVP(elm, field, type)->field.scqe_next += \ - (elm)->field.scqe_next; \ -} while (0) - #if defined(__cplusplus) } #endif |