Date: Sun, 10 Nov 2002 09:32:35 -0800 From: Kirk McKusick <mckusick@beastie.mckusick.com> To: arch@freebsd.org Cc: bostic@sleepycat.com (Keith Bostic) Subject: Shared-memory version of <sys/queue.h> macros Message-ID: <200211101732.gAAHWZ59035339@beastie.mckusick.com>
next in thread | raw e-mail | index | archive | help
I am proposing to add a new version of the <sys/queue.h> macros that
are designed to work in shared memory. The man page and actual macros
are included below. Search for NEW to find the additions to the existing
macros. Since these are not needed by the kernel, I propose to create
a new file /usr/include/queue.h which will contain the new shared memory
version of the queue macros and also include <sys/queue.h> to pull in
the existing set of queue macros. The include of <sys/queue.h> is to
avoid duplication and possible divergence of the original macro
set. Note that these shared memory macros are being contributed by
the folks that produce Berkeley DB and have been heavily tested in a
shared memory application, so they are known to work.
Kirk McKusick
=-=-=-=-=
# This is a shell archive. Save it in a file, remove anything before
# this line, and then unpack it by entering "sh file". Note, it may
# create directories; files and directories will be owned by you and
# have default permissions.
#
# This archive contains:
#
# queue.3.txt
# shqueue.h
#
echo x - queue.3.txt
sed 's/^X//' >queue.3.txt << 'END-of-queue.3.txt'
XQUEUE(3) System Library Functions Manual QUEUE(3)
X
XNAME
X SLIST_EMPTY, SLIST_ENTRY, SLIST_FIRST, SLIST_FOREACH, SLIST_HEAD,
X SLIST_HEAD_INITIALIZER, SLIST_INIT, SLIST_INSERT_AFTER,
X SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE_HEAD, SLIST_REMOVE,
X STAILQ_CONCAT, STAILQ_EMPTY, STAILQ_ENTRY, STAILQ_FIRST, STAILQ_FOREACH,
X STAILQ_HEAD, STAILQ_HEAD_INITIALIZER, STAILQ_INIT, STAILQ_INSERT_AFTER,
X STAILQ_INSERT_HEAD, STAILQ_INSERT_TAIL, STAILQ_LAST, STAILQ_NEXT,
X STAILQ_REMOVE_HEAD, STAILQ_REMOVE, LIST_EMPTY, LIST_ENTRY, LIST_FIRST,
X LIST_FOREACH, LIST_HEAD, LIST_HEAD_INITIALIZER, LIST_INIT,
X LIST_INSERT_AFTER, LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_NEXT,
X LIST_REMOVE, TAILQ_CONCAT, TAILQ_EMPTY, TAILQ_ENTRY, TAILQ_FIRST,
X TAILQ_FOREACH, TAILQ_FOREACH_REVERSE, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER,
X TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD,
X TAILQ_INSERT_TAIL, TAILQ_LAST, TAILQ_NEXT, TAILQ_PREV, TAILQ_REMOVE -
X implementations of singly-linked lists, singly-linked tail queues, lists
X and tail queues
X[NEW]
X SH_LIST_EMPTY, SH_LIST_ENTRY, SH_LIST_FIRST, SH_LIST_FIRST_P,
X SH_LIST_FOREACH, SH_LIST_HEAD, SH_LIST_HEAD_INITIALIZER, SH_LIST_INIT,
X SH_LIST_INSERT_AFTER, SH_LIST_INSERT_BEFORE, SH_LIST_INSERT_HEAD,
X SH_LIST_NEXT, SH_LIST_NEXTP, SH_LIST_REMOVE, SH_TAILQ_EMPTY,
X SH_TAILQ_ENTRY, SH_TAILQ_FIRST, SH_TAILQ_FIRSTP, SH_TAILQ_FOREACH,
X SH_TAILQ_FOREACH_REVERSE, SH_TAILQ_HEAD, SH_TAILQ_HEAD_INITIALIZER,
X SH_TAILQ_INIT, SH_TAILQ_INSERT_AFTER, SH_TAILQ_INSERT_BEFORE,
X SH_TAILQ_INSERT_HEAD, SH_TAILQ_INSERT_TAIL, SH_TAILQ_LAST,
X SH_TAILQ_NEXT, SH_TAILQ_PREV, SH_TAILQ_PREVP, SH_TAILQ_REMOVE -
X implementations of singly-linked lists, singly-linked tail queues, lists
X and tail queues for use in shared memory situations
X
XSYNOPSIS
X #include <sys/queue.h>
X
X SLIST_EMPTY(SLIST_HEAD *head);
X
X SLIST_ENTRY(TYPE);
X
X SLIST_FIRST(SLIST_HEAD *head);
X
X SLIST_FOREACH(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);
X
X SLIST_HEAD(HEADNAME, TYPE);
X
X SLIST_HEAD_INITIALIZER(SLIST_HEAD head);
X
X SLIST_INIT(SLIST_HEAD *head);
X
X SLIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, SLIST_ENTRY NAME);
X
X SLIST_INSERT_HEAD(SLIST_HEAD *head, TYPE *elm, SLIST_ENTRY NAME);
X
X SLIST_NEXT(TYPE *elm, SLIST_ENTRY NAME);
X
X SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME);
X
X SLIST_REMOVE(SLIST_HEAD *head, TYPE *elm, TYPE, SLIST_ENTRY NAME);
X
X STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2);
X
X STAILQ_EMPTY(STAILQ_HEAD *head);
X
X STAILQ_ENTRY(TYPE);
X
X STAILQ_FIRST(STAILQ_HEAD *head);
X
X STAILQ_FOREACH(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
X
X STAILQ_HEAD(HEADNAME, TYPE);
X
X STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);
X
X STAILQ_INIT(STAILQ_HEAD *head);
X
X STAILQ_INSERT_AFTER(STAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
X STAILQ_ENTRY NAME);
X
X STAILQ_INSERT_HEAD(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
X
X STAILQ_INSERT_TAIL(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
X
X STAILQ_LAST(STAILQ_HEAD *head, TYPE, STAILQ_ENTRY NAME);
X
X STAILQ_NEXT(TYPE *elm, STAILQ_ENTRY NAME);
X
X STAILQ_REMOVE_HEAD(STAILQ_HEAD *head, STAILQ_ENTRY NAME);
X
X STAILQ_REMOVE(STAILQ_HEAD *head, TYPE *elm, TYPE, STAILQ_ENTRY NAME);
X
X LIST_EMPTY(LIST_HEAD *head);
X
X LIST_ENTRY(TYPE);
X
X LIST_FIRST(LIST_HEAD *head);
X
X LIST_FOREACH(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);
X
X LIST_HEAD(HEADNAME, TYPE);
X
X LIST_HEAD_INITIALIZER(LIST_HEAD head);
X
X LIST_INIT(LIST_HEAD *head);
X
X LIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);
X
X LIST_INSERT_BEFORE(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);
X
X LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME);
X
X LIST_NEXT(TYPE *elm, LIST_ENTRY NAME);
X
X LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);
X
X TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TAILQ_ENTRY NAME);
X
X TAILQ_EMPTY(TAILQ_HEAD *head);
X
X TAILQ_ENTRY(TYPE);
X
X TAILQ_FIRST(TAILQ_HEAD *head);
X
X TAILQ_FOREACH(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME);
X
X TAILQ_FOREACH_REVERSE(TYPE *var, TAILQ_HEAD *head, HEADNAME,
X TAILQ_ENTRY NAME);
X
X TAILQ_HEAD(HEADNAME, TYPE);
X
X TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);
X
X TAILQ_INIT(TAILQ_HEAD *head);
X
X TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
X TAILQ_ENTRY NAME);
X
X TAILQ_INSERT_BEFORE(TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME);
X
X TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
X
X TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
X
X TAILQ_LAST(TAILQ_HEAD *head, HEADNAME);
X
X TAILQ_NEXT(TYPE *elm, TAILQ_ENTRY NAME);
X
X TAILQ_PREV(TYPE *elm, HEADNAME, TAILQ_ENTRY NAME);
X
X TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
X
X[NEW]
X SH_LIST_EMPTY(LIST_HEAD *head);
X
X SH_LIST_ENTRY;
X
X SH_LIST_FIRST(SH_LIST_HEAD *head, TYPE);
X
X SH_LIST_FIRSTP(SH_LIST_HEAD *head, TYPE);
X
X SH_LIST_FOREACH(TYPE *var, SH_LIST_HEAD *head, SH_LIST_ENTRY NAME, TYPE);
X
X SH_LIST_HEAD(HEADNAME);
X
X SH_LIST_HEAD_INITIALIZER(SH_LIST_HEAD head);
X
X SH_LIST_INIT(SH_LIST_HEAD *head);
X
X SH_LIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, SH_LIST_ENTRY NAME, TYPE);
X
X SH_LIST_INSERT_BEFORE(TYPE *listelm, TYPE *elm, SH_LIST_ENTRY NAME, TYPE);
X
X SH_LIST_INSERT_HEAD(SH_LIST_HEAD *head, TYPE *elm, SH_LIST_ENTRY NAME,
X TYPE);
X
X SH_LIST_NEXT(TYPE *elm, SH_LIST_ENTRY NAME, TYPE);
X
X SH_LIST_NEXTP(TYPE *elm, SH_LIST_ENTRY NAME, TYPE);
X
X SH_LIST_REMOVE(TYPE *elm, SH_LIST_ENTRY NAME, TYPE);
X
X SH_TAILQ_EMPTY(SH_TAILQ_HEAD *head);
X
X SH_TAILQ_ENTRY;
X
X SH_TAILQ_FIRST(SH_TAILQ_HEAD *head, TYPE);
X
X SH_TAILQ_FIRSTP(SH_TAILQ_HEAD *head, TYPE);
X
X SH_TAILQ_FOREACH(TYPE *var, SH_TAILQ_HEAD *head, SH_TAILQ_ENTRY NAME,
X TYPE);
X
X SH_TAILQ_FOREACH_REVERSE(TYPE *var, SH_TAILQ_HEAD *head, HEADNAME,
X SH_TAILQ_ENTRY NAME, TYPE);
X
X SH_TAILQ_HEAD(HEADNAME);
X
X SH_TAILQ_HEAD_INITIALIZER(SH_TAILQ_HEAD head);
X
X SH_TAILQ_INIT(SH_TAILQ_HEAD *head);
X
X SH_TAILQ_INSERT_AFTER(SH_TAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
X SH_TAILQ_ENTRY NAME, TYPE);
X
X SH_TAILQ_INSERT_BEFORE(TYPE *listelm, TYPE *elm, SH_TAILQ_ENTRY NAME,
X TYPE);
X
X SH_TAILQ_INSERT_HEAD(SH_TAILQ_HEAD *head, TYPE *elm, SH_TAILQ_ENTRY NAME,
X TYPE);
X
X SH_TAILQ_INSERT_TAIL(SH_TAILQ_HEAD *head, TYPE *elm, SH_TAILQ_ENTRY NAME,
X TYPE);
X
X SH_TAILQ_LAST(SH_TAILQ_HEAD *head, HEADNAME, TYPE);
X
X SH_TAILQ_NEXT(TYPE *elm, SH_TAILQ_ENTRY NAME, TYPE);
X
X SH_TAILQ_NEXTP(TYPE *elm, SH_TAILQ_ENTRY NAME, TYPE);
X
X SH_TAILQ_PREV(TYPE *elm, HEADNAME, SH_TAILQ_ENTRY NAME, TYPE);
X
X SH_TAILQ_REMOVE(SH_TAILQ_HEAD *head, TYPE *elm, SH_TAILQ_ENTRY NAME,
X TYPE);
X
XDESCRIPTION
X These macros define and operate on four types of data structures: singly-
X linked lists, singly-linked tail queues, lists, and tail queues. All
X four structures support the following functionality:
X 1. Insertion of a new entry at the head of the list.
X 2. Insertion of a new entry after any element in the list.
X 3. O(1) removal of an entry from the head of the list.
X 4. O(n) removal of any entry in the list.
X 5. Forward traversal through the list.
X
X Singly-linked lists are the simplest of the five data structures and sup-
X port only the above functionality. Singly-linked lists are ideal for
X applications with large datasets and few or no removals, or for imple-
X menting a LIFO queue.
X
X Singly-linked tail queues add the following functionality:
X 1. Entries can be added at the end of a list.
X 2. They may be concatenated.
X However:
X 1. All list insertions must specify the head of the list.
X 2. Each head entry requires two pointers rather than one.
X 3. Code size is about 15% greater and operations run about 20%
X slower than singly-linked lists.
X
X Singly-linked tailqs are ideal for applications with large datasets and
X few or no removals, or for implementing a FIFO queue.
X
X All doubly linked types of data structures (lists and tail queues) addi-
X tionally allow:
X 1. Insertion of a new entry before any element in the list.
X 2. O(1) removal of any entry in the list.
X However:
X 1. Each elements requires two pointers rather than one.
X 2. Code size and execution time of operations (except for
X removal) is about twice that of the singly-linked data-struc-
X tures.
X
X Linked lists are the simplest of the doubly linked data structures and
X support only the above functionality over singly-linked lists.
X
X Tail queues add the following functionality:
X 1. Entries can be added at the end of a list.
X 2. They may be traversed backwards, from tail to head.
X 3. They may be concatenated.
X However:
X 1. All list insertions and removals must specify the head of the
X list.
X 2. Each head entry requires two pointers rather than one.
X 3. Code size is about 15% greater and operations run about 20%
X slower than singly-linked lists.
X
X In the macro definitions, TYPE is the name of a user defined structure,
X that must contain a field of type SLIST_ENTRY, STAILQ_ENTRY, LIST_ENTRY,
X or TAILQ_ENTRY, named NAME. The argument HEADNAME is the name of a user
X defined structure that must be declared using the macros SLIST_HEAD,
X STAILQ_HEAD, LIST_HEAD, or TAILQ_HEAD. See the examples below for fur-
X ther explanation of how these macros are used.
X
X[NEW]
X Shared memory lists and tail queues are for use in memory shared
X by multiple processes. Macros designed for this case begin with the
X prefix 'SH_' and store offset information rather than pointers.
X Addresses of elements are calculated at time of access by the macros
X provided and are relative to the callers address space. This allows
X a processes to use shared memory functions to map lists or tail
X queues into memory at locations that may not be consistent with the
X other processes doing the same.
X
X All the rules regarding the access patterns of offset based
X lists and tail queues are identical to the pointer based macros.
X
X The API is largely identical to the non-shared memory lists and
X tail queues, with the exception that in some cases an additional
X TYPE argument is needed.
X
XSINGLY-LINKED LISTS
X A singly-linked list is headed by a structure defined by the SLIST_HEAD
X macro. This structure contains a single pointer to the first element on
X the list. The elements are singly linked for minimum space and pointer
X manipulation overhead at the expense of O(n) removal for arbitrary ele-
X ments. New elements can be added to the list after an existing element
X or at the head of the list. An SLIST_HEAD structure is declared as fol-
X lows:
X
X SLIST_HEAD(HEADNAME, TYPE) head;
X
X where HEADNAME is the name of the structure to be defined, and TYPE is
X the type of the elements to be linked into the list. A pointer to the
X head of the list can later be declared as:
X
X struct HEADNAME *headp;
X
X (The names head and headp are user selectable.)
X
X The macro SLIST_HEAD_INITIALIZER evaluates to an initializer for the list
X head.
X
X The macro SLIST_EMPTY evaluates to true if there are no elements in the
X list.
X
X The macro SLIST_ENTRY declares a structure that connects the elements in
X the list.
X
X The macro SLIST_FIRST returns the first element in the list or NULL if
X the list is empty.
X
X The macro SLIST_FOREACH traverses the list referenced by head in the for-
X ward direction, assigning each element in turn to var.
X
X The macro SLIST_INIT initializes the list referenced by head.
X
X The macro SLIST_INSERT_HEAD inserts the new element elm at the head of
X the list.
X
X The macro SLIST_INSERT_AFTER inserts the new element elm after the ele-
X ment listelm.
X
X The macro SLIST_NEXT returns the next element in the list.
X
X The macro SLIST_REMOVE_HEAD removes the element elm from the head of the
X list. For optimum efficiency, elements being removed from the head of
X the list should explicitly use this macro instead of the generic
X SLIST_REMOVE macro.
X
X The macro SLIST_REMOVE removes the element elm from the list.
X
XSINGLY-LINKED LIST EXAMPLE
X SLIST_HEAD(slisthead, entry) head =
X SLIST_HEAD_INITIALIZER(head);
X struct slisthead *headp; /* Singly-linked List head. */
X struct entry {
X ...
X SLIST_ENTRY(entry) entries; /* Singly-linked List. */
X ...
X } *n1, *n2, *n3, *np;
X SLIST_INIT(&head); /* Initialize the list. */
X n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
X SLIST_INSERT_HEAD(&head, n1, entries);
X n2 = malloc(sizeof(struct entry)); /* Insert after. */
X SLIST_INSERT_AFTER(n1, n2, entries);
X SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
X free(n2);
X n3 = SLIST_FIRST(&head);
X SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
X free(n3);
X /* Forward traversal. */
X SLIST_FOREACH(np, &head, entries)
X np-> ...
X while (!SLIST_EMPTY(&head)) { /* List Deletion. */
X n1 = SLIST_FIRST(&head);
X SLIST_REMOVE_HEAD(&head, entries);
X free(n1);
X }
X
XSINGLY-LINKED TAIL QUEUES
X A singly-linked tail queue is headed by a structure defined by the
X STAILQ_HEAD macro. This structure contains a pair of pointers, one to
X the first element in the tail queue and the other to the last element in
X the tail queue. The elements are singly linked for minimum space and
X pointer manipulation overhead at the expense of O(n) removal for arbi-
X trary elements. New elements can be added to the tail queue after an
X existing element, at the head of the tail queue, or at the end of the
X tail queue. A STAILQ_HEAD structure is declared as follows:
X
X STAILQ_HEAD(HEADNAME, TYPE) head;
X
X where HEADNAME is the name of the structure to be defined, and TYPE is
X the type of the elements to be linked into the tail queue. A pointer to
X the head of the tail queue can later be declared as:
X
X struct HEADNAME *headp;
X
X (The names head and headp are user selectable.)
X
X The macro STAILQ_HEAD_INITIALIZER evaluates to an initializer for the
X tail queue head.
X
X The macro STAILQ_CONCAT concatenates the tail queue headed by head2 onto
X the end of the one headed by head1 removing all entries from the former.
X
X The macro STAILQ_EMPTY evaluates to true if there are no items on the
X tail queue.
X
X The macro STAILQ_ENTRY declares a structure that connects the elements in
X the tail queue.
X
X The macro STAILQ_FIRST returns the first item on the tail queue or NULL
X if the tail queue is empty.
X
X The macro STAILQ_FOREACH traverses the tail queue referenced by head in
X the forward direction, assigning each element in turn to var.
X
X The macro STAILQ_INIT initializes the tail queue referenced by head.
X
X The macro STAILQ_INSERT_HEAD inserts the new element elm at the head of
X the tail queue.
X
X The macro STAILQ_INSERT_TAIL inserts the new element elm at the end of
X the tail queue.
X
X The macro STAILQ_INSERT_AFTER inserts the new element elm after the ele-
X ment listelm.
X
X The macro STAILQ_LAST returns the last item on the tail queue. If the
X tail queue is empty the return value is undefined.
X
X The macro STAILQ_NEXT returns the next item on the tail queue, or NULL
X this item is the last.
X
X The macro STAILQ_REMOVE_HEAD removes the element at the head of the tail
X queue. For optimum efficiency, elements being removed from the head of
X the tail queue should use this macro explicitly rather than the generic
X STAILQ_REMOVE macro.
X
X The macro STAILQ_REMOVE removes the element elm from the tail queue.
X
XSINGLY-LINKED TAIL QUEUE EXAMPLE
X STAILQ_HEAD(stailhead, entry) head =
X STAILQ_HEAD_INITIALIZER(head);
X struct stailhead *headp; /* Singly-linked tail queue head. */
X struct entry {
X ...
X STAILQ_ENTRY(entry) entries; /* Tail queue. */
X ...
X } *n1, *n2, *n3, *np;
X STAILQ_INIT(&head); /* Initialize the queue. */
X n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
X STAILQ_INSERT_HEAD(&head, n1, entries);
X n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
X STAILQ_INSERT_TAIL(&head, n1, entries);
X n2 = malloc(sizeof(struct entry)); /* Insert after. */
X STAILQ_INSERT_AFTER(&head, n1, n2, entries);
X /* Deletion. */
X STAILQ_REMOVE(&head, n2, entry, entries);
X free(n2);
X /* Deletion from the head. */
X n3 = STAILQ_FIRST(&head);
X STAILQ_REMOVE_HEAD(&head, entries);
X free(n3);
X /* Forward traversal. */
X STAILQ_FOREACH(np, &head, entries)
X np-> ...
X /* TailQ Deletion. */
X while (!STAILQ_EMPTY(&head)) {
X n1 = STAILQ_FIRST(&head);
X STAILQ_REMOVE_HEAD(&head, entries);
X free(n1);
X }
X /* Faster TailQ Deletion. */
X n1 = STAILQ_FIRST(&head);
X while (n1 != NULL) {
X n2 = STAILQ_NEXT(n1, entries);
X free(n1);
X n1 = n2;
X }
X STAILQ_INIT(&head);
X
XLISTS
X A list is headed by a structure defined by the LIST_HEAD macro. This
X structure contains a single pointer to the first element on the list.
X The elements are doubly linked so that an arbitrary element can be
X removed without traversing the list. New elements can be added to the
X list after an existing element, before an existing element, or at the
X head of the list. A LIST_HEAD structure is declared as follows:
X
X LIST_HEAD(HEADNAME, TYPE) head;
X
X where HEADNAME is the name of the structure to be defined, and TYPE is
X the type of the elements to be linked into the list. A pointer to the
X head of the list can later be declared as:
X
X struct HEADNAME *headp;
X
X (The names head and headp are user selectable.)
X
X The macro LIST_HEAD_INITIALIZER evaluates to an initializer for the list
X head.
X
X The macro LIST_EMPTY evaluates to true if their are no elements in the
X list.
X
X The macro LIST_ENTRY declares a structure that connects the elements in
X the list.
X
X The macro LIST_FIRST returns the first element in the list or NULL if the
X list is empty.
X
X The macro LIST_FOREACH traverses the list referenced by head in the for-
X ward direction, assigning each element in turn to var.
X
X The macro LIST_INIT initializes the list referenced by head.
X
X The macro LIST_INSERT_HEAD inserts the new element elm at the head of the
X list.
X
X The macro LIST_INSERT_AFTER inserts the new element elm after the element
X listelm.
X
X The macro LIST_INSERT_BEFORE inserts the new element elm before the ele-
X ment listelm.
X
X The macro LIST_NEXT returns the next element in the list, or NULL if this
X is the last.
X
X The macro LIST_REMOVE removes the element elm from the list.
X
XLIST EXAMPLE
X LIST_HEAD(listhead, entry) head =
X LIST_HEAD_INITIALIZER(head);
X struct listhead *headp; /* List head. */
X struct entry {
X ...
X LIST_ENTRY(entry) entries; /* List. */
X ...
X } *n1, *n2, *n3, *np;
X LIST_INIT(&head); /* Initialize the list. */
X n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
X LIST_INSERT_HEAD(&head, n1, entries);
X n2 = malloc(sizeof(struct entry)); /* Insert after. */
X LIST_INSERT_AFTER(n1, n2, entries);
X n3 = malloc(sizeof(struct entry)); /* Insert before. */
X LIST_INSERT_BEFORE(n2, n3, entries);
X LIST_REMOVE(n2, entries); /* Deletion. */
X free(n2);
X /* Forward traversal. */
X LIST_FOREACH(np, &head, entries)
X np-> ...
X while (!LIST_EMPTY(&head)) { /* List Deletion. */
X n1 = LIST_FIRST(&head);
X LIST_REMOVE(n1, entries);
X free(n1);
X }
X n1 = LIST_FIRST(&head); /* Faster List Deletion. */
X while (n1 != NULL) {
X n2 = LIST_NEXT(n1, entries);
X free(n1);
X n1 = n2;
X }
X LIST_INIT(&head);
X
X[NEW]
XSHARED MEMORY LISTS
X A shared memory list is headed by a structure defined by the
X SH_LIST_HEAD macro. This structure contains a single offset to
X the first element on the list stored as a ssize_t representing the
X distance in bytes from the location of the head structure in memory
X to the first element in memory.
X
X As with the implementation of list, the elements are doubly linked
X so that an arbitrary element can be removed without traversing the
X list. New elements can be added to the list after an existing
X element, before an existing element, or at the head of the list.
X All elements store offsets, just as the list head does, rather than
X addresses of neighboring elements. All operations on these
X elements use the address of a element supplied by a caller to then
X calculate the relative address of effected elements. As type
X information is not stored within the head and each of the elements
X items must be cast as appropriate when accessed. To accomplish
X this some macros require an additional TYPE argument. A
X SH_LIST_HEAD structure is declared as follows:
X
X SH_LIST_HEAD(HEADNAME) head;
X
X where HEADNAME is the name of the structure to be defined. A pointer
X to the head of the list can later be declared as:
X
X struct HEADNAME *headp;
X
X (The names head and headp are user selectable.)
X
X The macro SH_LIST_HEAD_INITIALIZER evaluates to an initializer for the
X list head.
X
X The macro SH_LIST_EMPTY evaluates to true if their are no elements in
X the list.
X
X The macro SH_LIST_ENTRY declares a structure that connects the elements
X in the list. SH_LIST_ENTRY is a bit different than LIST_ENTRY in that
X it takes no arguments and is used to insert the list next and prev
X structures. This can be declared as:
X
X struct list_element {
X ...
X SH_LIST_ENTRY list_entries;
X ...
X };
X
X (The names list_element and list_entries are user selectable.)
X
X The macro SH_LIST_FIRST returns the first element in the list or NULL
X if the list is empty.
X
X The macro SH_LIST_FIRSTP is much like SH_LIST_FIRST except that it
X does not first check for an empty list and may evaluate to an address
X of no merit if the list is in fact empty. Use this macro only when
X the list is not empty perhapes in conjunction with SH_LIST_EMPTY.
X
X The macro SH_LIST_FOREACH traverses the list referenced by head in
X the forward direction, assigning each element in turn to var.
X
X The macro SH_LIST_INIT initializes the list referenced by head.
X
X The macro SH_LIST_INSERT_HEAD inserts the new element elm at the
X head of the list.
X
X The macro SH_LIST_INSERT_AFTER inserts the new element elm after
X the element listelm.
X
X The macro SH_LIST_INSERT_BEFORE inserts the new element elm before
X the element listelm.
X
X The macro SH_LIST_NEXT returns the next element in the list, or NULL
X if this is the last.
X
X The macro SH_LIST_NEXTP is much like SH_LIST_NEXT except that it
X does not first check for the end of the list and may evaluate to an
X address of no merit if listelm is last element.
X
X The macro SH_LIST_REMOVE removes the element elm from the list.
X
X The macro SH_LIST_REMOVE_HEAD removes the first element elm from
X the list.
X
X
XSHARED MEMORY SINGLY-LINKED LIST EXAMPLE
X SH_LIST_HEAD(listhead) head =
X SH_LIST_HEAD_INITIALIZER(head);
X struct listhead *headp; /* List head. */
X struct entry {
X ...
X SH_LIST_ENTRY entries; /* List. */
X ...
X } *n1, *n2, *n3, *np;
X SH_LIST_INIT(&head); /* Initialize the list. */
X n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
X SH_LIST_INSERT_HEAD(&head, n1, entries, entry);
X n2 = malloc(sizeof(struct entry)); /* Insert after. */
X SH_LIST_INSERT_AFTER(n1, n2, entries, entry);
X n3 = malloc(sizeof(struct entry)); /* Insert before. */
X SH_LIST_INSERT_BEFORE(n2, n3, entries, entry);
X SH_LIST_REMOVE(n2, entries, entry); /* Deletion. */
X free(n2);
X /* Forward traversal. */
X SH_LIST_FOREACH(np, &head, entries, entry)
X np-> ...
X while (!SH_LIST_EMPTY(&head)) { /* List Deletion. */
X n1 = SH_LIST_FIRST(&head, entry);
X SH_LIST_REMOVE(n1, entries, entry);
X free(n1);
X }
X n1 = SH_LIST_FIRST(&head, entry); /* Faster List Deletion. */
X while (n1 != NULL) {
X n2 = SH_LIST_NEXT(n1, entries, entry);
X free(n1);
X n1 = n2;
X }
X SH_LIST_INIT(&head);
X
X
XTAIL QUEUES
X A tail queue is headed by a structure defined by the TAILQ_HEAD macro.
X This structure contains a pair of pointers, one to the first element in
X the tail queue and the other to the last element in the tail queue. The
X elements are doubly linked so that an arbitrary element can be removed
X without traversing the tail queue. New elements can be added to the tail
X queue after an existing element, before an existing element, at the head
X of the tail queue, or at the end of the tail queue. A TAILQ_HEAD struc-
X ture is declared as follows:
X
X TAILQ_HEAD(HEADNAME, TYPE) head;
X
X where HEADNAME is the name of the structure to be defined, and TYPE is
X the type of the elements to be linked into the tail queue. A pointer to
X the head of the tail queue can later be declared as:
X
X struct HEADNAME *headp;
X
X (The names head and headp are user selectable.)
X
X The macro TAILQ_HEAD_INITIALIZER evaluates to an initializer for the tail
X queue head.
X
X The macro TAILQ_CONCAT concatenates the tail queue headed by head2 onto
X the end of the one headed by head1 removing all entries from the former.
X
X The macro TAILQ_EMPTY evaluates to true if there are no items on the tail
X queue.
X
X The macro TAILQ_ENTRY declares a structure that connects the elements in
X the tail queue.
X
X The macro TAILQ_FIRST returns the first item on the tail queue or NULL if
X the tail queue is empty.
X
X The macro TAILQ_FOREACH traverses the tail queue referenced by head in
X the forward direction, assigning each element in turn to var. var is set
X to NULL if the loop completes normally, or if there were no elements.
X
X The macro TAILQ_FOREACH_REVERSE traverses the tail queue referenced by
X head in the reverse direction, assigning each element in turn to var.
X
X The macro TAILQ_INIT initializes the tail queue referenced by head.
X
X The macro TAILQ_INSERT_HEAD inserts the new element elm at the head of
X the tail queue.
X
X The macro TAILQ_INSERT_TAIL inserts the new element elm at the end of the
X tail queue.
X
X The macro TAILQ_INSERT_AFTER inserts the new element elm after the ele-
X ment listelm.
X
X The macro TAILQ_INSERT_BEFORE inserts the new element elm before the ele-
X ment listelm.
X
X The macro TAILQ_LAST returns the last item on the tail queue. If the
X tail queue is empty the return value is undefined.
X
X The macro TAILQ_NEXT returns the next item on the tail queue, or NULL if
X this item is the last.
X
X The macro TAILQ_PREV returns the previous item on the tail queue, or NULL
X if this item is the first.
X
X The macro TAILQ_REMOVE removes the element elm from the tail queue.
X
XTAIL QUEUE EXAMPLE
X TAILQ_HEAD(tailhead, entry) head =
X TAILQ_HEAD_INITIALIZER(head);
X struct tailhead *headp; /* Tail queue head. */
X struct entry {
X ...
X TAILQ_ENTRY(entry) entries; /* Tail queue. */
X ...
X } *n1, *n2, *n3, *np;
X TAILQ_INIT(&head); /* Initialize the queue. */
X n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
X TAILQ_INSERT_HEAD(&head, n1, entries);
X n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
X TAILQ_INSERT_TAIL(&head, n1, entries);
X n2 = malloc(sizeof(struct entry)); /* Insert after. */
X TAILQ_INSERT_AFTER(&head, n1, n2, entries);
X n3 = malloc(sizeof(struct entry)); /* Insert before. */
X TAILQ_INSERT_BEFORE(n2, n3, entries);
X TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
X free(n2);
X /* Forward traversal. */
X TAILQ_FOREACH(np, &head, entries)
X np-> ...
X /* Reverse traversal. */
X TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
X np-> ...
X /* TailQ Deletion. */
X while (!TAILQ_EMPTY(&head)) {
X n1 = TAILQ_FIRST(&head);
X TAILQ_REMOVE(&head, n1, entries);
X free(n1);
X }
X /* Faster TailQ Deletion. */
X n1 = TAILQ_FIRST(&head);
X while (n1 != NULL) {
X n2 = TAILQ_NEXT(n1, entries);
X free(n1);
X n1 = n2;
X }
X TAILQ_INIT(&head);
X
X[NEW]
XSHARED MEMORY TAIL QUEUES
X A shared memory tail queue is headed by a structure defined by the
X SH_TAILQ_HEAD macro. This structure containst a pair of offsets,
X one to the first element in the tail queue and the other to the last
X element in the tail queue.
X
X The elements are doubly linked so that an arbitrary element can be
X removed without traversing the tail queue. New elements can be
X added to the tail queue after an existing element, before an
X existing element, at the head or the end of the tail queue. All
X elements store offsets, rather than addresses of neighboring
X elements. All operations on these elements use the address of a
X element supplied by a caller to then calculate the relative address
X of effected elements. As type information is not stored within
X the head and each of the elements items must be cast as appropreate
X when accessed. To accomplish this some macros require an
X additional TYPE argument. A SH_TAILQ_HEAD structure is declared
X as follows:
X
X SH_TAILQ_HEAD(HEADNAME) head;
X
X where HEADNAME is the name of the structure to be defined. A pointer
X to the head of the tail queue can later be declared as:
X
X struct HEADNAME *headp;
X
X (The names head and headp are user selectable.)
X
X The macro SH_TAILQ_HEAD_INITIALIZER evaluates to an initializer for the
X tail queue head.
X
X The macro SH_TAILQ_EMPTY evaluates to true if their are no elements in
X the tail queue.
X
X The macro SH_TAILQ_ENTRY declares a structure that connects the elements
X in the tail queue. SH_TAILQ_ENTRY is a bit different than TAILQ_ENTRY in
X that it takes no arguments and is used to insert the tail queue next and
X prev structures. This can be declared as:
X
X struct list_element {
X ...
X SH_TAILQ_ENTRY list_entries;
X ...
X };
X
X (The names list_element and list_entries are user selectable.)
X
X The macro SH_TAILQ_FIRST returns the first element in the tail queue or
X NULL if the tailq is empty.
X
X The macro SH_TAILQ_FIRSTP is much like SH_TAILQ_FIRST except that it
X does not first check for an empty tailq and may evaluate to an address
X of no merit if the tailq is in fact empty. Use this macro only when
X the tailq is not empty perhapes in conjunction with SH_TAILQ_EMPTY.
X
X The macro SH_TAILQ_FOREACH traverses the tailq referenced by head in
X the forward direction, assigning each element in turn to var.
X
X The macro SH_TAILQ_FOREACH_REVERSE traverses the tailq referenced by
X head in the reverse direction, assigning each element in turn to var.
X
X The macro SH_TAILQ_INIT initializes the tail queue referenced by head.
X
X The macro SH_TAILQ_INSERT_HEAD inserts the new element elm at the
X head of the tail queue.
X
X The macro SH_TAILQ_INSERT_AFTER inserts the new element elm after
X the element listelm.
X
X The macro SH_TAILQ_INSERT_BEFORE inserts the new element elm before
X the element listelm.
X
X The macro SH_TAILQ_NEXT returns the next element in the tail queue,
X or NULL if this is the last.
X
X The macro SH_TAILQ_NEXTP is much like SH_TAILQ_NEXT except that it
X does not first check for the end of the tail queue and may evaluate to
X an address of no merit if listelm is last element.
X
X The macro SH_TAILQ_LAST returns the last element in the tail queue, or
X NULL if this is the last.
X
X The macro SH_TAILQ_PREV returns the previous element in the tail queue,
X or NULL if this is the last.
X
X The macro SH_TAILQ_REMOVE removes the element elm from the tailq.
X
X The macro SH_TAILQ_REMOVE_HEAD removes the first element elm from
X the tailq.
X
X
XSHARED MEMORY SINGLY-LINKED TAILQ EXAMPLE
X SH_TAILQ_HEAD(listhead) head =
X SH_TAILQ_HEAD_INITIALIZER(head);
X struct listhead *headp; /* Tailq head. */
X struct entry {
X ...
X SH_TAILQ_ENTRY entries; /* Tailq. */
X ...
X } *n1, *n2, *n3, *np;
X SH_TAILQ_INIT(&head); /* Initialize the tailq. */
X n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
X SH_TAILQ_INSERT_HEAD(&head, n1, entries, entry);
X n2 = malloc(sizeof(struct entry)); /* Insert after. */
X SH_TAILQ_INSERT_AFTER(n1, n2, entries, entry);
X n3 = malloc(sizeof(struct entry)); /* Insert before. */
X SH_TAILQ_INSERT_BEFORE(n2, n3, entries, entry);
X SH_TAILQ_REMOVE(n2, entries, entry); /* Deletion. */
X free(n2);
X /* Forward traversal. */
X SH_TAILQ_FOREACH(np, &head, entries, entry)
X np-> ...
X while (!SH_TAILQ_EMPTY(&head)) { /* Tailq Deletion. */
X n1 = SH_TAILQ_FIRST(&head, entry);
X SH_TAILQ_REMOVE(n1, entries, entry);
X free(n1);
X }
X n1 = SH_TAILQ_FIRST(&head, entry); /* Faster Tailq Deletion. */
X while (n1 != NULL) {
X n2 = SH_TAILQ_NEXT(n1, entries, entry);
X free(n1);
X n1 = n2;
X }
X SH_TAILQ_INIT(&head);
X
X
XHISTORY
X The queue functions first appeared in 4.4BSD.
X
XBSD January 24, 1994 BSD
END-of-queue.3.txt
echo x - shqueue.h
sed 's/^X//' >shqueue.h << 'END-of-shqueue.h'
X/*-
X * Copyright (c) 1996-2002
X * Sleepycat Software. All rights reserved.
X *
X * $Id: shqueue.h,v 11.11 2002/10/17 15:05:04 gburd Exp $
X */
X
X#ifndef _SYS_SHQUEUE_H_
X#define _SYS_SHQUEUE_H_
X
X/*
X * This file defines two types of data structures: lists and tail queues
X * similarly to the include file <sys/queue.h>.
X *
X * The difference is that this set of macros can be used for structures that
X * reside in shared memory that may be mapped at different addresses in each
X * process. In most cases, the macros for shared structures exactly mirror
X * the normal macros, although the macro calls require an additional type
X * parameter, only used by the HEAD and ENTRY macros of the standard macros.
X *
X * Since we use relative offsets of type ssize_t rather than pointers, 0
X * (aka NULL) is a valid offset and cannot be used to indicate the end
X * of a list. Therefore, we use -1 to indicate end of list.
X *
X * The macros ending in "P" return pointers without checking for end or
X * beginning of lists, the others check for end of list and evaluate to
X * either a pointer or NULL.
X *
X * For details on the use of these macros, see the queue(3) manual page.
X */
X
X#if defined(__cplusplus)
Xextern "C" {
X#endif
X
X/*
X * Shared memory list definitions.
X */
X#define SH_LIST_HEAD(name) \
Xstruct name { \
X ssize_t slh_first; /* first element */ \
X}
X
X#define SH_LIST_HEAD_INITIALIZER(head) \
X { -1 }
X
X#define SH_LIST_ENTRY \
Xstruct { \
X ssize_t sle_next; /* relative offset to next element */ \
X ssize_t sle_prev; /* relative offset of prev element */ \
X}
X
X/*
X * Shared memory list functions.
X */
X
X#define SH_LIST_EMPTY(head) \
X ((head)->slh_first == -1)
X
X#define SH_LIST_FIRSTP(head, type) \
X ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first))
X
X#define SH_LIST_FIRST(head, type) \
X (SH_LIST_EMPTY(head) ? NULL : \
X ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first)))
X
X#define SH_LIST_NEXTP(elm, field, type) \
X ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next))
X
X#define SH_LIST_NEXT(elm, field, type) \
X ((elm)->field.sle_next == -1 ? NULL : \
X ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next)))
X
X /*
X *__SH_LIST_PREV_OFF is private API. It calculates the address of
X * the elm->field.sle_next member of a SH_LIST structure. All offsets
X * between elements are relative to that point in SH_LIST structures.
X */
X#define __SH_LIST_PREV_OFF(elm, field) \
X ((ssize_t *)(((u_int8_t *)(elm)) + (elm)->field.sle_prev))
X
X#define SH_LIST_PREV(elm, field, type) \
X (struct type *)((ssize_t)elm - (*__SH_LIST_PREV_OFF(elm, field)))
X
X#define SH_LIST_FOREACH(var, head, field, type) \
X for ((var) = SH_LIST_FIRST((head), type); \
X (var); \
X (var) = SH_LIST_NEXT((var), field, type))
X
X#define SH_PTR_TO_OFF(src, dest) \
X ((ssize_t)(((u_int8_t *)(dest)) - ((u_int8_t *)(src))))
X
X/*
X * Given correct A.next: B.prev = SH_LIST_NEXT_TO_PREV(A)
X * in a list [A, B]
X * The prev value is always the offset from an element to its preceeding
X * element's next location, not the beginning of the structure. To get
X * to the beginning of an element structure in memory given an element
X * do the following:
X * A = B - (B.prev + (&B.next - B))
X * Take the element's next pointer and calculate what the corresponding
X * Prev pointer should be -- basically it is the negation plus the offset
X * of the next field in the structure.
X */
X#define SH_LIST_NEXT_TO_PREV(elm, field) \
X (((elm)->field.sle_next == -1 ? 0 : -(elm)->field.sle_next) + \
X SH_PTR_TO_OFF(elm, &(elm)->field.sle_next))
X
X#define SH_LIST_INIT(head) (head)->slh_first = -1
X
X#define SH_LIST_INSERT_BEFORE(head, listelm, elm, field, type) do { \
X if (listelm == SH_LIST_FIRST(head, type)) { \
X SH_LIST_INSERT_HEAD(head, elm, field, type); \
X } else { \
X (elm)->field.sle_next = SH_PTR_TO_OFF(elm, listelm); \
X (elm)->field.sle_prev = SH_LIST_NEXT_TO_PREV( \
X SH_LIST_PREV((listelm), field, type), field) + \
X (elm)->field.sle_next; \
X (SH_LIST_PREV(listelm, field, type))->field.sle_next = \
X (SH_PTR_TO_OFF((SH_LIST_PREV(listelm, field, \
X type)), elm)); \
X (listelm)->field.sle_prev = SH_LIST_NEXT_TO_PREV(elm, field); \
X } \
X} while (0)
X
X#define SH_LIST_INSERT_AFTER(listelm, elm, field, type) do { \
X if ((listelm)->field.sle_next != -1) { \
X (elm)->field.sle_next = SH_PTR_TO_OFF(elm, \
X SH_LIST_NEXTP(listelm, field, type)); \
X SH_LIST_NEXTP(listelm, field, type)->field.sle_prev = \
X SH_LIST_NEXT_TO_PREV(elm, field); \
X } else \
X (elm)->field.sle_next = -1; \
X (listelm)->field.sle_next = SH_PTR_TO_OFF(listelm, elm); \
X (elm)->field.sle_prev = SH_LIST_NEXT_TO_PREV(listelm, field); \
X} while (0)
X
X#define SH_LIST_INSERT_HEAD(head, elm, field, type) do { \
X if ((head)->slh_first != -1) { \
X (elm)->field.sle_next = \
X (head)->slh_first - SH_PTR_TO_OFF(head, elm); \
X SH_LIST_FIRSTP(head, type)->field.sle_prev = \
X SH_LIST_NEXT_TO_PREV(elm, field); \
X } else \
X (elm)->field.sle_next = -1; \
X (head)->slh_first = SH_PTR_TO_OFF(head, elm); \
X (elm)->field.sle_prev = SH_PTR_TO_OFF(elm, &(head)->slh_first); \
X} while (0)
X
X#define SH_LIST_REMOVE(elm, field, type) do { \
X if ((elm)->field.sle_next != -1) { \
X SH_LIST_NEXTP(elm, field, type)->field.sle_prev = \
X (elm)->field.sle_prev - (elm)->field.sle_next; \
X *__SH_LIST_PREV_OFF(elm, field) += (elm)->field.sle_next;\
X } else \
X *__SH_LIST_PREV_OFF(elm, field) = -1; \
X} while (0)
X
X#define SH_LIST_REMOVE_HEAD(head, field, type) do { \
X if (!SH_LIST_EMPTY(head)) { \
X SH_LIST_REMOVE(SH_LIST_FIRSTP(head, type), field, type);\
X } \
X} while (0)
X
X/*
X * Shared memory tail queue definitions.
X */
X#define SH_TAILQ_HEAD(name) \
Xstruct name { \
X ssize_t stqh_first; /* relative offset of first element */ \
X ssize_t stqh_last; /* relative offset of last's next */ \
X}
X
X#define SH_TAILQ_HEAD_INITIALIZER(head) \
X { -1, 0 }
X
X#define SH_TAILQ_ENTRY \
Xstruct { \
X ssize_t stqe_next; /* relative offset of next element */ \
X ssize_t stqe_prev; /* relative offset of prev's next */ \
X}
X
X/*
X * Shared memory tail queue functions.
X */
X
X#define SH_TAILQ_EMPTY(head) \
X ((head)->stqh_first == -1)
X
X#define SH_TAILQ_FIRSTP(head, type) \
X ((struct type *)((u_int8_t *)(head) + (head)->stqh_first))
X
X#define SH_TAILQ_FIRST(head, type) \
X (SH_TAILQ_EMPTY(head) ? NULL : SH_TAILQ_FIRSTP(head, type))
X
X#define SH_TAILQ_NEXTP(elm, field, type) \
X ((struct type *)((u_int8_t *)(elm) + (elm)->field.stqe_next))
X
X#define SH_TAILQ_NEXT(elm, field, type) \
X ((elm)->field.stqe_next == -1 ? NULL : \
X ((struct type *)((u_int8_t *)(elm) + (elm)->field.stqe_next)))
X
X /*
X * __SH_TAILQ_PREV_OFF is private API. It calculates the address of
X * the elm->field.stqe_next member of a SH_TAILQ structure. All
X * offsets between elements are relative to that point in SH_TAILQ
X * structures.
X */
X#define __SH_TAILQ_PREV_OFF(elm, field) \
X ((ssize_t *)(((u_int8_t *)(elm)) + (elm)->field.stqe_prev))
X
X#define SH_TAILQ_PREVP(elm, field, type) \
X (struct type *)((ssize_t)elm - (*__SH_TAILQ_PREV_OFF(elm, field)))
X
X#define SH_TAILQ_PREV(head, elm, field, type) \
X (((elm) == SH_TAILQ_FIRST(head, type)) ? NULL : \
X (struct type *)((ssize_t)elm - (*__SH_TAILQ_PREV_OFF(elm, field))))
X
X /*
X * __SH_TAILQ_LAST_OFF is private API. It calculates the address of
X * the stqe_next member of a SH_TAILQ structure in the last element
X * of this list. All offsets between elements are relative to that
X * point in SH_TAILQ structures.
X */
X#define __SH_TAILQ_LAST_OFF(head) \
X ((ssize_t *)(((u_int8_t *)(head)) + (head)->stqh_last))
X
X#define SH_TAILQ_LAST(head, field, type) \
X (SH_TAILQ_EMPTY(head) ? NULL : \
X (struct type *)((ssize_t)(head) + \
X ((ssize_t)((head)->stqh_last) - \
X ((ssize_t)SH_PTR_TO_OFF(SH_TAILQ_FIRST(head, type), \
X &(SH_TAILQ_FIRST(head, type)->field.stqe_next))))))
X
X/*
X * Given correct A.next: B.prev = SH_TAILQ_NEXT_TO_PREV(A)
X * in a list [A, B]
X * The prev value is always the offset from an element to its preceeding
X * element's next location, not the beginning of the structure. To get
X * to the beginning of an element structure in memory given an element
X * do the following:
X * A = B - (B.prev + (&B.next - B))
X */
X#define SH_TAILQ_NEXT_TO_PREV(elm, field) \
X (((elm)->field.stqe_next == -1 ? 0 : \
X (-(elm)->field.stqe_next) + \
X SH_PTR_TO_OFF(elm, &(elm)->field.stqe_next)))
X
X#define SH_TAILQ_FOREACH(var, head, field, type) \
X for ((var) = SH_TAILQ_FIRST((head), type); \
X (var); \
X (var) = SH_TAILQ_NEXT((var), field, type))
X
X#define SH_TAILQ_FOREACH_REVERSE(var, head, field, type) \
X for ((var) = SH_TAILQ_LAST((head), field, type); \
X (var); \
X (var) = SH_TAILQ_PREV((head), (var), field, type))
X
X#define SH_TAILQ_INIT(head) { \
X (head)->stqh_first = -1; \
X (head)->stqh_last = SH_PTR_TO_OFF(head, &(head)->stqh_first); \
X}
X
X#define SH_TAILQ_INSERT_HEAD(head, elm, field, type) do { \
X if ((head)->stqh_first != -1) { \
X (elm)->field.stqe_next = \
X (head)->stqh_first - SH_PTR_TO_OFF(head, elm); \
X SH_TAILQ_FIRSTP(head, type)->field.stqe_prev = \
X SH_TAILQ_NEXT_TO_PREV(elm, field); \
X } else { \
X (head)->stqh_last = \
X SH_PTR_TO_OFF(head, &(elm)->field.stqe_next); \
X (elm)->field.stqe_next = -1; \
X } \
X (head)->stqh_first = SH_PTR_TO_OFF(head, elm); \
X (elm)->field.stqe_prev = \
X SH_PTR_TO_OFF(elm, &(head)->stqh_first); \
X} while (0)
X
X#define SH_TAILQ_INSERT_TAIL(head, elm, field) do { \
X (elm)->field.stqe_next = -1; \
X (elm)->field.stqe_prev = \
X -SH_PTR_TO_OFF(head, elm) + (head)->stqh_last; \
X if ((head)->stqh_last == \
X SH_PTR_TO_OFF((head), &(head)->stqh_first)) \
X (head)->stqh_first = SH_PTR_TO_OFF(head, elm); \
X else \
X *__SH_TAILQ_LAST_OFF(head) = -(head)->stqh_last + \
X SH_PTR_TO_OFF((elm), &(elm)->field.stqe_next) + \
X SH_PTR_TO_OFF(head, elm); \
X (head)->stqh_last = \
X SH_PTR_TO_OFF(head, &((elm)->field.stqe_next)); \
X} while (0)
X
X#define SH_TAILQ_INSERT_BEFORE(head, listelm, elm, field, type) do { \
X if (listelm == SH_TAILQ_FIRST(head, type)) { \
X SH_TAILQ_INSERT_HEAD(head, elm, field, type); \
X } else { \
X (elm)->field.stqe_next = SH_PTR_TO_OFF(elm, listelm); \
X (elm)->field.stqe_prev = SH_TAILQ_NEXT_TO_PREV( \
X SH_TAILQ_PREVP((listelm), field, type), field) + \
X (elm)->field.stqe_next; \
X (SH_TAILQ_PREVP(listelm, field, type))->field.stqe_next =\
X (SH_PTR_TO_OFF((SH_TAILQ_PREVP(listelm, field, type)), \
X elm)); \
X (listelm)->field.stqe_prev = \
X SH_TAILQ_NEXT_TO_PREV(elm, field); \
X } \
X} while (0)
X
X#define SH_TAILQ_INSERT_AFTER(head, listelm, elm, field, type) do { \
X if ((listelm)->field.stqe_next != -1) { \
X (elm)->field.stqe_next = (listelm)->field.stqe_next - \
X SH_PTR_TO_OFF(listelm, elm); \
X SH_TAILQ_NEXTP(listelm, field, type)->field.stqe_prev = \
X SH_TAILQ_NEXT_TO_PREV(elm, field); \
X } else { \
X (elm)->field.stqe_next = -1; \
X (head)->stqh_last = \
X SH_PTR_TO_OFF(head, &elm->field.stqe_next); \
X } \
X (listelm)->field.stqe_next = SH_PTR_TO_OFF(listelm, elm); \
X (elm)->field.stqe_prev = SH_TAILQ_NEXT_TO_PREV(listelm, field); \
X} while (0)
X
X#define SH_TAILQ_REMOVE(head, elm, field, type) do { \
X if ((elm)->field.stqe_next != -1) { \
X SH_TAILQ_NEXTP(elm, field, type)->field.stqe_prev = \
X (elm)->field.stqe_prev + \
X SH_PTR_TO_OFF(SH_TAILQ_NEXTP(elm, \
X field, type), elm); \
X *__SH_TAILQ_PREV_OFF(elm, field) += elm->field.stqe_next;\
X } else { \
X (head)->stqh_last = (elm)->field.stqe_prev + \
X SH_PTR_TO_OFF(head, elm); \
X *__SH_TAILQ_PREV_OFF(elm, field) = -1; \
X } \
X} while (0)
X
X#if defined(__cplusplus)
X}
X#endif
X#endif /* !_SYS_SHQUEUE_H_ */
END-of-shqueue.h
exit
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200211101732.gAAHWZ59035339>