/*-
 * See the file LICENSE for redistribution information.
 *
 * Copyright (c) 1996, 1997
 *      Sleepycat Software.  All rights reserved.
 *
 *      @(#)shqueue.h   8.12 (Sleepycat) 9/10/97
 *      %W% (Sun) %G%
 */
/*
 * Copyright (c) 1998 by Sun Microsystems, Inc.
 * All rights reserved.
 */

#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>.
 *
 * 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
 * process.  In most cases, the macros for shared structures exactly mirror
 * the normal macros, although the macro calls require an additional type
 * parameter, only used by the HEAD and ENTRY macros of the standard macros.
 *
 * For details on the use of these macros, see the queue(3) manual page.
 */

/*
 * Shared list definitions.
 */
#define SH_LIST_HEAD(name)                                              \
struct name {                                                           \
        ssize_t slh_first;      /* first element */                     \
}

#define SH_LIST_ENTRY                                                   \
struct {                                                                \
        ssize_t sle_next;       /* relative offset 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.
 */

#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 :                               \
        ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first)))

#define SH_LIST_NEXTP(elm, field, type)                                 \
        ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next))

#define SH_LIST_NEXT(elm, field, type)                                  \
        ((elm)->field.sle_next == -1 ? NULL :                           \
        ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next)))

#define SH_LIST_PREV(elm, field)                                        \
        ((ssize_t *)(((u_int8_t *)(elm)) + (elm)->field.sle_prev))

#define SH_PTR_TO_OFF(src, dest)                                        \
        ((ssize_t)(((u_int8_t *)(dest)) - ((u_int8_t *)(src))))

#define SH_LIST_END(head)                       NULL

/*
 * 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))

#define SH_LIST_INIT(head) (head)->slh_first = -1

#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,              \
                    SH_LIST_NEXTP(listelm, field, type));               \
                SH_LIST_NEXTP(listelm, field, type)->field.sle_prev =   \
                        SH_LIST_NEXT_TO_PREV(elm, field);               \
        } else                                                          \
                (elm)->field.sle_next = -1;                             \
        (listelm)->field.sle_next = SH_PTR_TO_OFF(listelm, elm);        \
        (elm)->field.sle_prev = SH_LIST_NEXT_TO_PREV(listelm, field);   \
} while (0)

#define SH_LIST_INSERT_HEAD(head, elm, field, type) do {                \
        if ((head)->slh_first != -1) {                                  \
                (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);               \
        } else                                                          \
                (elm)->field.sle_next = -1;                             \
        (head)->slh_first = SH_PTR_TO_OFF(head, elm);                   \
        (elm)->field.sle_prev = SH_PTR_TO_OFF(elm, &(head)->slh_first); \
} while (0)

#define SH_LIST_REMOVE(elm, field, type) do {                           \
        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;     \
        } else                                                          \
                *SH_LIST_PREV(elm, field) = -1;                         \
} while (0)

/*
 * Shared tail queue definitions.
 */
#define SH_TAILQ_HEAD(name)                                             \
struct name {                                                           \
        ssize_t stqh_first;     /* relative offset of first element */  \
        ssize_t stqh_last;      /* relative offset of last's next */    \
}

#define SH_TAILQ_ENTRY                                                  \
struct {                                                                \
        ssize_t stqe_next;      /* relative offset of next element */   \
        ssize_t stqe_prev;      /* relative offset of prev's next */    \
}

/*
 * Shared tail queue functions.
 */
#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))

#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)                                             \
        ((ssize_t *)(((u_int8_t *)(head)) + (head)->stqh_last))

#define SH_TAILQ_NEXT_TO_PREV(elm, field)                               \
        (-(elm)->field.stqe_next + SH_PTR_TO_OFF(elm, &(elm)->field.stqe_next))

#define SH_TAILQ_END(head)              NULL

#define SH_TAILQ_INIT(head) {                                           \
        (head)->stqh_first = -1;                                        \
        (head)->stqh_last = SH_PTR_TO_OFF(head, &(head)->stqh_first);   \
}

#define SH_TAILQ_INSERT_HEAD(head, elm, field, type) do {               \
        if ((head)->stqh_first != -1) {                                 \
                (elm)->field.stqe_next =                                \
                    (head)->stqh_first - SH_PTR_TO_OFF(head, elm);      \
                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);       \
        }                                                               \
        (head)->stqh_first = SH_PTR_TO_OFF(head, elm);                  \
        (elm)->field.stqe_prev =                                        \
            SH_PTR_TO_OFF(elm, &(head)->stqh_first);                    \
} while (0)

#define SH_TAILQ_INSERT_TAIL(head, elm, field) do {                     \
        (elm)->field.stqe_next = -1;                                    \
        (elm)->field.stqe_prev =                                        \
            -SH_PTR_TO_OFF(head, elm) + (head)->stqh_last;              \
        if ((head)->stqh_last ==                                        \
            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_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_AFTER(head, listelm, elm, field, type) do {     \
        if ((listelm)->field.stqe_next != -1) {                         \
                (elm)->field.stqe_next = (listelm)->field.stqe_next -   \
                    SH_PTR_TO_OFF(listelm, elm);                        \
                SH_TAILQ_NEXTP(listelm, field, 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);         \
        }                                                               \
        (listelm)->field.stqe_next = SH_PTR_TO_OFF(listelm, elm);       \
        (elm)->field.stqe_prev = SH_TAILQ_NEXT_TO_PREV(listelm, field); \
} while (0)

#define SH_TAILQ_REMOVE(head, elm, field, type) do {                    \
        if ((elm)->field.stqe_next != -1) {                             \
                SH_TAILQ_NEXTP(elm, field, type)->field.stqe_prev =     \
                    (elm)->field.stqe_prev +                            \
                    SH_PTR_TO_OFF(SH_TAILQ_NEXTP(elm,                   \
                    field, type), elm);                                 \
                *SH_TAILQ_PREVP(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;                       \
        }                                                               \
} 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_END(head)            ((void *)(head))

#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)
#endif  /* !_SYS_SHQUEUE_H_ */