Re: [Xen-devel] [PATCH] libxl: Include a version of bsd's queue.h

[Roger Pau Monnà <roger.pau@xxxxxxxxxxxxx>]

2011/10/25 Ian Jackson <Ian.Jackson@xxxxxxxxxxxxx>:
> We would like some linked list macros which are (a) well known to be
> sane and (b) typesafe. ÂBSD's queue.h meets these criteria.
>
> The files in this changeset were obtained with:
> Âsvn co -r 221843 svn://svn.freebsd.org/base/head/sys/sys/
> Âsvn co -r 221843 svn://svn.freebsd.org/base/head/share/man/man3
>
> We also provide some simple perlery to arrange to add the libxl_
> namespace prefix to the macros. ÂThis will allow us to #include our
> modified queue.h in our public header file without clashing with
> anyone else who is also using another version of queue.h.
>
> Signed-off-by: Ian Jackson <ian.jackson@xxxxxxxxxxxxx>
>
> ---
> Âtools/libxl/Makefile        Â|  Â5 +-
> Âtools/libxl/bsd-queue.3 Â Â Â Â Â Â | 1044 
> +++++++++++++++++++++++++++++++++++
> Âtools/libxl/bsd-sys-queue-h-seddery | Â 67 +++
> Âtools/libxl/bsd-sys-queue.h     | Â637 +++++++++++++++++++++
> Â4 files changed, 1752 insertions(+), 1 deletions(-)
>
> diff --git a/tools/libxl/Makefile b/tools/libxl/Makefile
> index 51e5132..5d7e0f5 100644
> --- a/tools/libxl/Makefile
> +++ b/tools/libxl/Makefile
> @@ -42,7 +42,7 @@ LIBXL_OBJS += _libxl_types.o libxl_flask.o 
> _libxl_types_internal.o
>
> Â$(LIBXL_OBJS): CFLAGS += $(CFLAGS_libxenctrl) $(CFLAGS_libxenguest) 
> $(CFLAGS_libxenstore) $(CFLAGS_libblktapctl)
>
> -AUTOINCS= libxlu_cfg_y.h libxlu_cfg_l.h
> +AUTOINCS= libxlu_cfg_y.h libxlu_cfg_l.h _libxl_list.h
> ÂAUTOSRCS= libxlu_cfg_y.c libxlu_cfg_l.c
> ÂLIBXLU_OBJS = libxlu_cfg_y.o libxlu_cfg_l.o libxlu_cfg.o \
> Â Â Â Âlibxlu_disk_l.o libxlu_disk.o
> @@ -81,6 +81,9 @@ _libxl_paths.h: genpath
> Â Â Â Ârm -f $@.tmp
> Â Â Â Â$(call move-if-changed,$@.2.tmp,$@)
>
> +_libxl_list.h: bsd-sys-queue-h-seddery bsd-sys-queue.h
> + Â Â Â ./$^ --prefix=libxl >$@.new && mv -f $@.new $@
> +
> Âlibxl_paths.c: _libxl_paths.h
>
> Âlibxl.h: _libxl_types.h
> diff --git a/tools/libxl/bsd-queue.3 b/tools/libxl/bsd-queue.3
> new file mode 100644
> index 0000000..007ca5c
> --- /dev/null
> +++ b/tools/libxl/bsd-queue.3
> @@ -0,0 +1,1044 @@
> +.\" Copyright (c) 1993
> +.\" Â ÂThe Regents of the University of California. ÂAll rights reserved.
> +.\"
> +.\" Redistribution and use in source and binary forms, with or without
> +.\" modification, are permitted provided that the following conditions
> +.\" are met:
> +.\" 1. Redistributions of source code must retain the above copyright
> +.\" Â Ânotice, this list of conditions and the following disclaimer.
> +.\" 2. Redistributions in binary form must reproduce the above copyright
> +.\" Â Ânotice, this list of conditions and the following disclaimer in the
> +.\" Â Âdocumentation and/or other materials provided with the distribution.
> +.\" 3. All advertising materials mentioning features or use of this software
> +.\" Â Âmust display the following acknowledgement:
> +.\" Â ÂThis product includes software developed by the University of
> +.\" Â ÂCalifornia, Berkeley and its contributors.
> +.\" 4. Neither the name of the University nor the names of its contributors
> +.\" Â Âmay be used to endorse or promote products derived from this software
> +.\" Â Âwithout specific prior written permission.
> +.\"
> +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
> +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
> +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 
> PURPOSE
> +.\" ARE DISCLAIMED. ÂIN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
> +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
> CONSEQUENTIAL
> +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
> +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
> +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 
> STRICT
> +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
> +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> +.\" SUCH DAMAGE.
> +.\"
> +.\" Â Â@(#)queue.3 Â Â 8.2 (Berkeley) 1/24/94
> +.\" $FreeBSD$
> +.\"
> +.Dd May 13, 2011
> +.Dt QUEUE 3
> +.Os
> +.Sh NAME
> +.Nm SLIST_EMPTY ,
> +.Nm SLIST_ENTRY ,
> +.Nm SLIST_FIRST ,
> +.Nm SLIST_FOREACH ,
> +.Nm SLIST_FOREACH_SAFE ,
> +.Nm SLIST_HEAD ,
> +.Nm SLIST_HEAD_INITIALIZER ,
> +.Nm SLIST_INIT ,
> +.Nm SLIST_INSERT_AFTER ,
> +.Nm SLIST_INSERT_HEAD ,
> +.Nm SLIST_NEXT ,
> +.Nm SLIST_REMOVE_AFTER ,
> +.Nm SLIST_REMOVE_HEAD ,
> +.Nm SLIST_REMOVE ,
> +.Nm SLIST_SWAP ,
> +.Nm STAILQ_CONCAT ,
> +.Nm STAILQ_EMPTY ,
> +.Nm STAILQ_ENTRY ,
> +.Nm STAILQ_FIRST ,
> +.Nm STAILQ_FOREACH ,
> +.Nm STAILQ_FOREACH_SAFE ,
> +.Nm STAILQ_HEAD ,
> +.Nm STAILQ_HEAD_INITIALIZER ,
> +.Nm STAILQ_INIT ,
> +.Nm STAILQ_INSERT_AFTER ,
> +.Nm STAILQ_INSERT_HEAD ,
> +.Nm STAILQ_INSERT_TAIL ,
> +.Nm STAILQ_LAST ,
> +.Nm STAILQ_NEXT ,
> +.Nm STAILQ_REMOVE_AFTER ,
> +.Nm STAILQ_REMOVE_HEAD ,
> +.Nm STAILQ_REMOVE ,
> +.Nm STAILQ_SWAP ,
> +.Nm LIST_EMPTY ,
> +.Nm LIST_ENTRY ,
> +.Nm LIST_FIRST ,
> +.Nm LIST_FOREACH ,
> +.Nm LIST_FOREACH_SAFE ,
> +.Nm LIST_HEAD ,
> +.Nm LIST_HEAD_INITIALIZER ,
> +.Nm LIST_INIT ,
> +.Nm LIST_INSERT_AFTER ,
> +.Nm LIST_INSERT_BEFORE ,
> +.Nm LIST_INSERT_HEAD ,
> +.Nm LIST_NEXT ,
> +.Nm LIST_REMOVE ,
> +.Nm LIST_SWAP ,
> +.Nm TAILQ_CONCAT ,
> +.Nm TAILQ_EMPTY ,
> +.Nm TAILQ_ENTRY ,
> +.Nm TAILQ_FIRST ,
> +.Nm TAILQ_FOREACH ,
> +.Nm TAILQ_FOREACH_SAFE ,
> +.Nm TAILQ_FOREACH_REVERSE ,
> +.Nm TAILQ_FOREACH_REVERSE_SAFE ,
> +.Nm TAILQ_HEAD ,
> +.Nm TAILQ_HEAD_INITIALIZER ,
> +.Nm TAILQ_INIT ,
> +.Nm TAILQ_INSERT_AFTER ,
> +.Nm TAILQ_INSERT_BEFORE ,
> +.Nm TAILQ_INSERT_HEAD ,
> +.Nm TAILQ_INSERT_TAIL ,
> +.Nm TAILQ_LAST ,
> +.Nm TAILQ_NEXT ,
> +.Nm TAILQ_PREV ,
> +.Nm TAILQ_REMOVE ,
> +.Nm TAILQ_SWAP
> +.Nd implementations of singly-linked lists, singly-linked tail queues,
> +lists and tail queues
> +.Sh SYNOPSIS
> +.In sys/queue.h
> +.\"
> +.Fn SLIST_EMPTY "SLIST_HEAD *head"
> +.Fn SLIST_ENTRY "TYPE"
> +.Fn SLIST_FIRST "SLIST_HEAD *head"
> +.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
> +.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" 
> "TYPE *temp_var"
> +.Fn SLIST_HEAD "HEADNAME" "TYPE"
> +.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
> +.Fn SLIST_INIT "SLIST_HEAD *head"
> +.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
> +.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
> +.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
> +.Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
> +.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
> +.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
> +.Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME"
> +.\"
> +.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
> +.Fn STAILQ_EMPTY "STAILQ_HEAD *head"
> +.Fn STAILQ_ENTRY "TYPE"
> +.Fn STAILQ_FIRST "STAILQ_HEAD *head"
> +.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
> +.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" 
> "TYPE *temp_var"
> +.Fn STAILQ_HEAD "HEADNAME" "TYPE"
> +.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
> +.Fn STAILQ_INIT "STAILQ_HEAD *head"
> +.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" 
> "STAILQ_ENTRY NAME"
> +.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
> +.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
> +.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
> +.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
> +.Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
> +.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
> +.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
> +.Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "STAILQ_ENTRY NAME"
> +.\"
> +.Fn LIST_EMPTY "LIST_HEAD *head"
> +.Fn LIST_ENTRY "TYPE"
> +.Fn LIST_FIRST "LIST_HEAD *head"
> +.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
> +.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE 
> *temp_var"
> +.Fn LIST_HEAD "HEADNAME" "TYPE"
> +.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
> +.Fn LIST_INIT "LIST_HEAD *head"
> +.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
> +.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
> +.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
> +.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
> +.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
> +.Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
> +.\"
> +.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
> +.Fn TAILQ_EMPTY "TAILQ_HEAD *head"
> +.Fn TAILQ_ENTRY "TYPE"
> +.Fn TAILQ_FIRST "TAILQ_HEAD *head"
> +.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
> +.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" 
> "TYPE *temp_var"
> +.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" 
> "TAILQ_ENTRY NAME"
> +.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" 
> "TAILQ_ENTRY NAME" "TYPE *temp_var"
> +.Fn TAILQ_HEAD "HEADNAME" "TYPE"
> +.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
> +.Fn TAILQ_INIT "TAILQ_HEAD *head"
> +.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" 
> "TAILQ_ENTRY NAME"
> +.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
> +.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
> +.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
> +.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
> +.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
> +.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
> +.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
> +.Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY 
> NAME"
> +.\"
> +.Sh DESCRIPTION
> +These macros define and operate on four types of data structures:
> +singly-linked lists, singly-linked tail queues, lists, and tail queues.
> +All four structures support the following functionality:
> +.Bl -enum -compact -offset indent
> +.It
> +Insertion of a new entry at the head of the list.
> +.It
> +Insertion of a new entry after any element in the list.
> +.It
> +O(1) removal of an entry from the head of the list.
> +.It
> +Forward traversal through the list.
> +.It
> +Swawpping the contents of two lists.
> +.El
> +.Pp
> +Singly-linked lists are the simplest of the four data structures
> +and support only the above functionality.
> +Singly-linked lists are ideal for applications with large datasets
> +and few or no removals,
> +or for implementing a LIFO queue.
> +Singly-linked lists add the following functionality:
> +.Bl -enum -compact -offset indent
> +.It
> +O(n) removal of any entry in the list.
> +.El
> +.Pp
> +Singly-linked tail queues add the following functionality:
> +.Bl -enum -compact -offset indent
> +.It
> +Entries can be added at the end of a list.
> +.It
> +O(n) removal of any entry in the list.
> +.It
> +They may be concatenated.
> +.El
> +However:
> +.Bl -enum -compact -offset indent
> +.It
> +All list insertions must specify the head of the list.
> +.It
> +Each head entry requires two pointers rather than one.
> +.It
> +Code size is about 15% greater and operations run about 20% slower
> +than singly-linked lists.
> +.El
> +.Pp
> +Singly-linked tailqs are ideal for applications with large datasets and
> +few or no removals,
> +or for implementing a FIFO queue.
> +.Pp
> +All doubly linked types of data structures (lists and tail queues)
> +additionally allow:
> +.Bl -enum -compact -offset indent
> +.It
> +Insertion of a new entry before any element in the list.
> +.It
> +O(1) removal of any entry in the list.
> +.El
> +However:
> +.Bl -enum -compact -offset indent
> +.It
> +Each element requires two pointers rather than one.
> +.It
> +Code size and execution time of operations (except for removal) is about
> +twice that of the singly-linked data-structures.
> +.El
> +.Pp
> +Linked lists are the simplest of the doubly linked data structures and 
> support
> +only the above functionality over singly-linked lists.
> +.Pp
> +Tail queues add the following functionality:
> +.Bl -enum -compact -offset indent
> +.It
> +Entries can be added at the end of a list.
> +.It
> +They may be traversed backwards, from tail to head.
> +.It
> +They may be concatenated.
> +.El
> +However:
> +.Bl -enum -compact -offset indent
> +.It
> +All list insertions and removals must specify the head of the list.
> +.It
> +Each head entry requires two pointers rather than one.
> +.It
> +Code size is about 15% greater and operations run about 20% slower
> +than singly-linked lists.
> +.El
> +.Pp
> +In the macro definitions,
> +.Fa TYPE
> +is the name of a user defined structure,
> +that must contain a field of type
> +.Li SLIST_ENTRY ,
> +.Li STAILQ_ENTRY ,
> +.Li LIST_ENTRY ,
> +or
> +.Li TAILQ_ENTRY ,
> +named
> +.Fa NAME .
> +The argument
> +.Fa HEADNAME
> +is the name of a user defined structure that must be declared
> +using the macros
> +.Li SLIST_HEAD ,
> +.Li STAILQ_HEAD ,
> +.Li LIST_HEAD ,
> +or
> +.Li TAILQ_HEAD .
> +See the examples below for further explanation of how these
> +macros are used.
> +.Sh SINGLY-LINKED LISTS
> +A singly-linked list is headed by a structure defined by the
> +.Nm SLIST_HEAD
> +macro.
> +This structure contains a single pointer to the first element
> +on the list.
> +The elements are singly linked for minimum space and pointer manipulation
> +overhead at the expense of O(n) removal for arbitrary elements.
> +New elements can be added to the list after an existing element or
> +at the head of the list.
> +An
> +.Fa SLIST_HEAD
> +structure is declared as follows:
> +.Bd -literal -offset indent
> +SLIST_HEAD(HEADNAME, TYPE) head;
> +.Ed
> +.Pp
> +where
> +.Fa HEADNAME
> +is the name of the structure to be defined, and
> +.Fa TYPE
> +is the type of the elements to be linked into the list.
> +A pointer to the head of the list can later be declared as:
> +.Bd -literal -offset indent
> +struct HEADNAME *headp;
> +.Ed
> +.Pp
> +(The names
> +.Li head
> +and
> +.Li headp
> +are user selectable.)
> +.Pp
> +The macro
> +.Nm SLIST_HEAD_INITIALIZER
> +evaluates to an initializer for the list
> +.Fa head .
> +.Pp
> +The macro
> +.Nm SLIST_EMPTY
> +evaluates to true if there are no elements in the list.
> +.Pp
> +The macro
> +.Nm SLIST_ENTRY
> +declares a structure that connects the elements in
> +the list.
> +.Pp
> +The macro
> +.Nm SLIST_FIRST
> +returns the first element in the list or NULL if the list is empty.
> +.Pp
> +The macro
> +.Nm SLIST_FOREACH
> +traverses the list referenced by
> +.Fa head
> +in the forward direction, assigning each element in
> +turn to
> +.Fa var .
> +.Pp
> +The macro
> +.Nm SLIST_FOREACH_SAFE
> +traverses the list referenced by
> +.Fa head
> +in the forward direction, assigning each element in
> +turn to
> +.Fa var .
> +However, unlike
> +.Fn SLIST_FOREACH
> +here it is permitted to both remove
> +.Fa var
> +as well as free it from within the loop safely without interfering with the
> +traversal.
> +.Pp
> +The macro
> +.Nm SLIST_INIT
> +initializes the list referenced by
> +.Fa head .
> +.Pp
> +The macro
> +.Nm SLIST_INSERT_HEAD
> +inserts the new element
> +.Fa elm
> +at the head of the list.
> +.Pp
> +The macro
> +.Nm SLIST_INSERT_AFTER
> +inserts the new element
> +.Fa elm
> +after the element
> +.Fa listelm .
> +.Pp
> +The macro
> +.Nm SLIST_NEXT
> +returns the next element in the list.
> +.Pp
> +The macro
> +.Nm SLIST_REMOVE_AFTER
> +removes the element after
> +.Fa elm
> +from the list. Unlike
> +.Fa SLIST_REMOVE ,
> +this macro does not traverse the entire list.
> +.Pp
> +The macro
> +.Nm SLIST_REMOVE_HEAD
> +removes the element
> +.Fa elm
> +from the head of the list.
> +For optimum efficiency,
> +elements being removed from the head of the list should explicitly use
> +this macro instead of the generic
> +.Fa SLIST_REMOVE
> +macro.
> +.Pp
> +The macro
> +.Nm SLIST_REMOVE
> +removes the element
> +.Fa elm
> +from the list.
> +.Pp
> +The macro
> +.Nm SLIST_SWAP
> +swaps the contents of
> +.Fa head1
> +and
> +.Fa head2 .
> +.Sh SINGLY-LINKED LIST EXAMPLE
> +.Bd -literal
> +SLIST_HEAD(slisthead, entry) head =
> + Â ÂSLIST_HEAD_INITIALIZER(head);
> +struct slisthead *headp; Â Â Â Â Â Â Â /* Singly-linked List head. */
> +struct entry {
> + Â Â Â ...
> + Â Â Â SLIST_ENTRY(entry) entries; Â Â /* Singly-linked List. */
> + Â Â Â ...
> +} *n1, *n2, *n3, *np;
> +
> +SLIST_INIT(&head); Â Â Â Â Â Â Â Â Â Â /* Initialize the list. */
> +
> +n1 = malloc(sizeof(struct entry)); Â Â /* Insert at the head. */
> +SLIST_INSERT_HEAD(&head, n1, entries);
> +
> +n2 = malloc(sizeof(struct entry)); Â Â /* Insert after. */
> +SLIST_INSERT_AFTER(n1, n2, entries);
> +
> +SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
> +free(n2);
> +
> +n3 = SLIST_FIRST(&head);
> +SLIST_REMOVE_HEAD(&head, entries); Â Â /* Deletion from the head. */
> +free(n3);
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Forward traversal. */
> +SLIST_FOREACH(np, &head, entries)
> + Â Â Â np-> ...
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Safe forward traversal. */
> +SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
> + Â Â Â np->do_stuff();
> + Â Â Â ...
> + Â Â Â SLIST_REMOVE(&head, np, entry, entries);
> + Â Â Â free(np);
> +}
> +
> +while (!SLIST_EMPTY(&head)) { Â Â Â Â Â/* List Deletion. */
> + Â Â Â n1 = SLIST_FIRST(&head);
> + Â Â Â SLIST_REMOVE_HEAD(&head, entries);
> + Â Â Â free(n1);
> +}
> +.Ed
> +.Sh SINGLY-LINKED TAIL QUEUES
> +A singly-linked tail queue is headed by a structure defined by the
> +.Nm STAILQ_HEAD
> +macro.
> +This structure contains a pair of pointers,
> +one to the first element in the tail queue and the other to
> +the last element in the tail queue.
> +The elements are singly linked for minimum space and pointer
> +manipulation overhead at the expense of O(n) removal for arbitrary
> +elements.
> +New elements can be added to the tail queue after an existing element,
> +at the head of the tail queue, or at the end of the tail queue.
> +A
> +.Fa STAILQ_HEAD
> +structure is declared as follows:
> +.Bd -literal -offset indent
> +STAILQ_HEAD(HEADNAME, TYPE) head;
> +.Ed
> +.Pp
> +where
> +.Li HEADNAME
> +is the name of the structure to be defined, and
> +.Li TYPE
> +is the type of the elements to be linked into the tail queue.
> +A pointer to the head of the tail queue can later be declared as:
> +.Bd -literal -offset indent
> +struct HEADNAME *headp;
> +.Ed
> +.Pp
> +(The names
> +.Li head
> +and
> +.Li headp
> +are user selectable.)
> +.Pp
> +The macro
> +.Nm STAILQ_HEAD_INITIALIZER
> +evaluates to an initializer for the tail queue
> +.Fa head .
> +.Pp
> +The macro
> +.Nm STAILQ_CONCAT
> +concatenates the tail queue headed by
> +.Fa head2
> +onto the end of the one headed by
> +.Fa head1
> +removing all entries from the former.
> +.Pp
> +The macro
> +.Nm STAILQ_EMPTY
> +evaluates to true if there are no items on the tail queue.
> +.Pp
> +The macro
> +.Nm STAILQ_ENTRY
> +declares a structure that connects the elements in
> +the tail queue.
> +.Pp
> +The macro
> +.Nm STAILQ_FIRST
> +returns the first item on the tail queue or NULL if the tail queue
> +is empty.
> +.Pp
> +The macro
> +.Nm STAILQ_FOREACH
> +traverses the tail queue referenced by
> +.Fa head
> +in the forward direction, assigning each element
> +in turn to
> +.Fa var .
> +.Pp
> +The macro
> +.Nm STAILQ_FOREACH_SAFE
> +traverses the tail queue referenced by
> +.Fa head
> +in the forward direction, assigning each element
> +in turn to
> +.Fa var .
> +However, unlike
> +.Fn STAILQ_FOREACH
> +here it is permitted to both remove
> +.Fa var
> +as well as free it from within the loop safely without interfering with the
> +traversal.
> +.Pp
> +The macro
> +.Nm STAILQ_INIT
> +initializes the tail queue referenced by
> +.Fa head .
> +.Pp
> +The macro
> +.Nm STAILQ_INSERT_HEAD
> +inserts the new element
> +.Fa elm
> +at the head of the tail queue.
> +.Pp
> +The macro
> +.Nm STAILQ_INSERT_TAIL
> +inserts the new element
> +.Fa elm
> +at the end of the tail queue.
> +.Pp
> +The macro
> +.Nm STAILQ_INSERT_AFTER
> +inserts the new element
> +.Fa elm
> +after the element
> +.Fa listelm .
> +.Pp
> +The macro
> +.Nm STAILQ_LAST
> +returns the last item on the tail queue.
> +If the tail queue is empty the return value is
> +.Dv NULL .
> +.Pp
> +The macro
> +.Nm STAILQ_NEXT
> +returns the next item on the tail queue, or NULL this item is the last.
> +.Pp
> +The macro
> +.Nm STAILQ_REMOVE_AFTER
> +removes the element after
> +.Fa elm
> +from the tail queue. Unlike
> +.Fa STAILQ_REMOVE ,
> +this macro does not traverse the entire tail queue.
> +.Pp
> +The macro
> +.Nm STAILQ_REMOVE_HEAD
> +removes the element at the head of the tail queue.
> +For optimum efficiency,
> +elements being removed from the head of the tail queue should
> +use this macro explicitly rather than the generic
> +.Fa STAILQ_REMOVE
> +macro.
> +.Pp
> +The macro
> +.Nm STAILQ_REMOVE
> +removes the element
> +.Fa elm
> +from the tail queue.
> +.Pp
> +The macro
> +.Nm STAILQ_SWAP
> +swaps the contents of
> +.Fa head1
> +and
> +.Fa head2 .
> +.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
> +.Bd -literal
> +STAILQ_HEAD(stailhead, entry) head =
> + Â ÂSTAILQ_HEAD_INITIALIZER(head);
> +struct stailhead *headp; Â Â Â Â Â Â Â /* Singly-linked tail queue head. */
> +struct entry {
> + Â Â Â ...
> + Â Â Â STAILQ_ENTRY(entry) entries; Â Â/* Tail queue. */
> + Â Â Â ...
> +} *n1, *n2, *n3, *np;
> +
> +STAILQ_INIT(&head); Â Â Â Â Â Â Â Â Â Â/* Initialize the queue. */
> +
> +n1 = malloc(sizeof(struct entry)); Â Â /* Insert at the head. */
> +STAILQ_INSERT_HEAD(&head, n1, entries);
> +
> +n1 = malloc(sizeof(struct entry)); Â Â /* Insert at the tail. */
> +STAILQ_INSERT_TAIL(&head, n1, entries);
> +
> +n2 = malloc(sizeof(struct entry)); Â Â /* Insert after. */
> +STAILQ_INSERT_AFTER(&head, n1, n2, entries);
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Deletion. */
> +STAILQ_REMOVE(&head, n2, entry, entries);
> +free(n2);
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Deletion from the head. */
> +n3 = STAILQ_FIRST(&head);
> +STAILQ_REMOVE_HEAD(&head, entries);
> +free(n3);
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Forward traversal. */
> +STAILQ_FOREACH(np, &head, entries)
> + Â Â Â np-> ...
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Safe forward traversal. */
> +STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
> + Â Â Â np->do_stuff();
> + Â Â Â ...
> + Â Â Â STAILQ_REMOVE(&head, np, entry, entries);
> + Â Â Â free(np);
> +}
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* TailQ Deletion. */
> +while (!STAILQ_EMPTY(&head)) {
> + Â Â Â n1 = STAILQ_FIRST(&head);
> + Â Â Â STAILQ_REMOVE_HEAD(&head, entries);
> + Â Â Â free(n1);
> +}
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Faster TailQ Deletion. */
> +n1 = STAILQ_FIRST(&head);
> +while (n1 != NULL) {
> + Â Â Â n2 = STAILQ_NEXT(n1, entries);
> + Â Â Â free(n1);
> + Â Â Â n1 = n2;
> +}
> +STAILQ_INIT(&head);
> +.Ed
> +.Sh LISTS
> +A list is headed by a structure defined by the
> +.Nm LIST_HEAD
> +macro.
> +This structure contains a single pointer to the first element
> +on the list.
> +The elements are doubly linked so that an arbitrary element can be
> +removed without traversing the list.
> +New elements can be added to the list after an existing element,
> +before an existing element, or at the head of the list.
> +A
> +.Fa LIST_HEAD
> +structure is declared as follows:
> +.Bd -literal -offset indent
> +LIST_HEAD(HEADNAME, TYPE) head;
> +.Ed
> +.Pp
> +where
> +.Fa HEADNAME
> +is the name of the structure to be defined, and
> +.Fa TYPE
> +is the type of the elements to be linked into the list.
> +A pointer to the head of the list can later be declared as:
> +.Bd -literal -offset indent
> +struct HEADNAME *headp;
> +.Ed
> +.Pp
> +(The names
> +.Li head
> +and
> +.Li headp
> +are user selectable.)
> +.Pp
> +The macro
> +.Nm LIST_HEAD_INITIALIZER
> +evaluates to an initializer for the list
> +.Fa head .
> +.Pp
> +The macro
> +.Nm LIST_EMPTY
> +evaluates to true if there are no elements in the list.
> +.Pp
> +The macro
> +.Nm LIST_ENTRY
> +declares a structure that connects the elements in
> +the list.
> +.Pp
> +The macro
> +.Nm LIST_FIRST
> +returns the first element in the list or NULL if the list
> +is empty.
> +.Pp
> +The macro
> +.Nm LIST_FOREACH
> +traverses the list referenced by
> +.Fa head
> +in the forward direction, assigning each element in turn to
> +.Fa var .
> +.Pp
> +The macro
> +.Nm LIST_FOREACH_SAFE
> +traverses the list referenced by
> +.Fa head
> +in the forward direction, assigning each element in turn to
> +.Fa var .
> +However, unlike
> +.Fn LIST_FOREACH
> +here it is permitted to both remove
> +.Fa var
> +as well as free it from within the loop safely without interfering with the
> +traversal.
> +.Pp
> +The macro
> +.Nm LIST_INIT
> +initializes the list referenced by
> +.Fa head .
> +.Pp
> +The macro
> +.Nm LIST_INSERT_HEAD
> +inserts the new element
> +.Fa elm
> +at the head of the list.
> +.Pp
> +The macro
> +.Nm LIST_INSERT_AFTER
> +inserts the new element
> +.Fa elm
> +after the element
> +.Fa listelm .
> +.Pp
> +The macro
> +.Nm LIST_INSERT_BEFORE
> +inserts the new element
> +.Fa elm
> +before the element
> +.Fa listelm .
> +.Pp
> +The macro
> +.Nm LIST_NEXT
> +returns the next element in the list, or NULL if this is the last.
> +.Pp
> +The macro
> +.Nm LIST_REMOVE
> +removes the element
> +.Fa elm
> +from the list.
> +.Pp
> +The macro
> +.Nm LIST_SWAP
> +swaps the contents of
> +.Fa head1
> +and
> +.Fa head2 .
> +.Sh LIST EXAMPLE
> +.Bd -literal
> +LIST_HEAD(listhead, entry) head =
> + Â ÂLIST_HEAD_INITIALIZER(head);
> +struct listhead *headp; Â Â Â Â Â Â Â Â Â Â Â Â/* List head. */
> +struct entry {
> + Â Â Â ...
> + Â Â Â LIST_ENTRY(entry) entries; Â Â Â/* List. */
> + Â Â Â ...
> +} *n1, *n2, *n3, *np, *np_temp;
> +
> +LIST_INIT(&head); Â Â Â Â Â Â Â Â Â Â Â/* Initialize the list. */
> +
> +n1 = malloc(sizeof(struct entry)); Â Â /* Insert at the head. */
> +LIST_INSERT_HEAD(&head, n1, entries);
> +
> +n2 = malloc(sizeof(struct entry)); Â Â /* Insert after. */
> +LIST_INSERT_AFTER(n1, n2, entries);
> +
> +n3 = malloc(sizeof(struct entry)); Â Â /* Insert before. */
> +LIST_INSERT_BEFORE(n2, n3, entries);
> +
> +LIST_REMOVE(n2, entries); Â Â Â Â Â Â Â/* Deletion. */
> +free(n2);
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Forward traversal. */
> +LIST_FOREACH(np, &head, entries)
> + Â Â Â np-> ...
> +
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Safe forward traversal. */
> +LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
> + Â Â Â np->do_stuff();
> + Â Â Â ...
> + Â Â Â LIST_REMOVE(np, entries);
> + Â Â Â free(np);
> +}
> +
> +while (!LIST_EMPTY(&head)) { Â Â Â Â Â /* List Deletion. */
> + Â Â Â n1 = LIST_FIRST(&head);
> + Â Â Â LIST_REMOVE(n1, entries);
> + Â Â Â free(n1);
> +}
> +
> +n1 = LIST_FIRST(&head); Â Â Â Â Â Â Â Â Â Â Â Â/* Faster List Deletion. */
> +while (n1 != NULL) {
> + Â Â Â n2 = LIST_NEXT(n1, entries);
> + Â Â Â free(n1);
> + Â Â Â n1 = n2;
> +}
> +LIST_INIT(&head);
> +.Ed
> +.Sh TAIL QUEUES
> +A tail queue is headed by a structure defined by the
> +.Nm TAILQ_HEAD
> +macro.
> +This structure contains a pair of pointers,
> +one to the first element in the tail queue and the other to
> +the last element in the tail queue.
> +The elements are doubly linked so that an arbitrary element can be
> +removed without traversing the tail queue.
> +New elements can be added to the tail queue after an existing element,
> +before an existing element, at the head of the tail queue,
> +or at the end of the tail queue.
> +A
> +.Fa TAILQ_HEAD
> +structure is declared as follows:
> +.Bd -literal -offset indent
> +TAILQ_HEAD(HEADNAME, TYPE) head;
> +.Ed
> +.Pp
> +where
> +.Li HEADNAME
> +is the name of the structure to be defined, and
> +.Li TYPE
> +is the type of the elements to be linked into the tail queue.
> +A pointer to the head of the tail queue can later be declared as:
> +.Bd -literal -offset indent
> +struct HEADNAME *headp;
> +.Ed
> +.Pp
> +(The names
> +.Li head
> +and
> +.Li headp
> +are user selectable.)
> +.Pp
> +The macro
> +.Nm TAILQ_HEAD_INITIALIZER
> +evaluates to an initializer for the tail queue
> +.Fa head .
> +.Pp
> +The macro
> +.Nm TAILQ_CONCAT
> +concatenates the tail queue headed by
> +.Fa head2
> +onto the end of the one headed by
> +.Fa head1
> +removing all entries from the former.
> +.Pp
> +The macro
> +.Nm TAILQ_EMPTY
> +evaluates to true if there are no items on the tail queue.
> +.Pp
> +The macro
> +.Nm TAILQ_ENTRY
> +declares a structure that connects the elements in
> +the tail queue.
> +.Pp
> +The macro
> +.Nm TAILQ_FIRST
> +returns the first item on the tail queue or NULL if the tail queue
> +is empty.
> +.Pp
> +The macro
> +.Nm TAILQ_FOREACH
> +traverses the tail queue referenced by
> +.Fa head
> +in the forward direction, assigning each element in turn to
> +.Fa var .
> +.Fa var
> +is set to
> +.Dv NULL
> +if the loop completes normally, or if there were no elements.
> +.Pp
> +The macro
> +.Nm TAILQ_FOREACH_REVERSE
> +traverses the tail queue referenced by
> +.Fa head
> +in the reverse direction, assigning each element in turn to
> +.Fa var .
> +.Pp
> +The macros
> +.Nm TAILQ_FOREACH_SAFE
> +and
> +.Nm TAILQ_FOREACH_REVERSE_SAFE
> +traverse the list referenced by
> +.Fa head
> +in the forward or reverse direction respectively,
> +assigning each element in turn to
> +.Fa var .
> +However, unlike their unsafe counterparts,
> +.Nm TAILQ_FOREACH
> +and
> +.Nm TAILQ_FOREACH_REVERSE
> +permit to both remove
> +.Fa var
> +as well as free it from within the loop safely without interfering with the
> +traversal.
> +.Pp
> +The macro
> +.Nm TAILQ_INIT
> +initializes the tail queue referenced by
> +.Fa head .
> +.Pp
> +The macro
> +.Nm TAILQ_INSERT_HEAD
> +inserts the new element
> +.Fa elm
> +at the head of the tail queue.
> +.Pp
> +The macro
> +.Nm TAILQ_INSERT_TAIL
> +inserts the new element
> +.Fa elm
> +at the end of the tail queue.
> +.Pp
> +The macro
> +.Nm TAILQ_INSERT_AFTER
> +inserts the new element
> +.Fa elm
> +after the element
> +.Fa listelm .
> +.Pp
> +The macro
> +.Nm TAILQ_INSERT_BEFORE
> +inserts the new element
> +.Fa elm
> +before the element
> +.Fa listelm .
> +.Pp
> +The macro
> +.Nm TAILQ_LAST
> +returns the last item on the tail queue.
> +If the tail queue is empty the return value is
> +.Dv NULL .
> +.Pp
> +The macro
> +.Nm TAILQ_NEXT
> +returns the next item on the tail queue, or NULL if this item is the last.
> +.Pp
> +The macro
> +.Nm TAILQ_PREV
> +returns the previous item on the tail queue, or NULL if this item
> +is the first.
> +.Pp
> +The macro
> +.Nm TAILQ_REMOVE
> +removes the element
> +.Fa elm
> +from the tail queue.
> +.Pp
> +The macro
> +.Nm TAILQ_SWAP
> +swaps the contents of
> +.Fa head1
> +and
> +.Fa head2 .
> +.Sh TAIL QUEUE EXAMPLE
> +.Bd -literal
> +TAILQ_HEAD(tailhead, entry) head =
> + Â ÂTAILQ_HEAD_INITIALIZER(head);
> +struct tailhead *headp; Â Â Â Â Â Â Â Â Â Â Â Â/* Tail queue head. */
> +struct entry {
> + Â Â Â ...
> + Â Â Â TAILQ_ENTRY(entry) entries; Â Â /* Tail queue. */
> + Â Â Â ...
> +} *n1, *n2, *n3, *np;
> +
> +TAILQ_INIT(&head); Â Â Â Â Â Â Â Â Â Â /* Initialize the queue. */
> +
> +n1 = malloc(sizeof(struct entry)); Â Â /* Insert at the head. */
> +TAILQ_INSERT_HEAD(&head, n1, entries);
> +
> +n1 = malloc(sizeof(struct entry)); Â Â /* Insert at the tail. */
> +TAILQ_INSERT_TAIL(&head, n1, entries);
> +
> +n2 = malloc(sizeof(struct entry)); Â Â /* Insert after. */
> +TAILQ_INSERT_AFTER(&head, n1, n2, entries);
> +
> +n3 = malloc(sizeof(struct entry)); Â Â /* Insert before. */
> +TAILQ_INSERT_BEFORE(n2, n3, entries);
> +
> +TAILQ_REMOVE(&head, n2, entries); Â Â Â/* Deletion. */
> +free(n2);
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Forward traversal. */
> +TAILQ_FOREACH(np, &head, entries)
> + Â Â Â np-> ...
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Safe forward traversal. */
> +TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
> + Â Â Â np->do_stuff();
> + Â Â Â ...
> + Â Â Â TAILQ_REMOVE(&head, np, entries);
> + Â Â Â free(np);
> +}
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Reverse traversal. */
> +TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
> + Â Â Â np-> ...
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* TailQ Deletion. */
> +while (!TAILQ_EMPTY(&head)) {
> + Â Â Â n1 = TAILQ_FIRST(&head);
> + Â Â Â TAILQ_REMOVE(&head, n1, entries);
> + Â Â Â free(n1);
> +}
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Faster TailQ Deletion. */
> +n1 = TAILQ_FIRST(&head);
> +while (n1 != NULL) {
> + Â Â Â n2 = TAILQ_NEXT(n1, entries);
> + Â Â Â free(n1);
> + Â Â Â n1 = n2;
> +}
> +TAILQ_INIT(&head);
> +.Ed
> +.Sh SEE ALSO
> +.Xr tree 3
> +.Sh HISTORY
> +The
> +.Nm queue
> +functions first appeared in
> +.Bx 4.4 .
> diff --git a/tools/libxl/bsd-sys-queue-h-seddery 
> b/tools/libxl/bsd-sys-queue-h-seddery
> new file mode 100755
> index 0000000..0bab8e0
> --- /dev/null
> +++ b/tools/libxl/bsd-sys-queue-h-seddery
> @@ -0,0 +1,67 @@
> +#!/usr/bin/perl -p

This should be something like:

#!/usr/bin/env perl

For this script to work on BSD systems, which usually have perl in
/usr/pkg/bin/perl or /usr/local/bin/perl

> +#
> +# This script is part of the Xen build system. ÂIt has a very
> +# permissive licence to avoid complicating the licence of the
> +# generated header file and to allow this seddery to be reused by
> +# other projects.
> +#
> +# Permission is hereby granted, free of charge, to any person
> +# obtaining a copy of this individual file (the "Software"), to deal
> +# in the Software without restriction, including without limitation
> +# the rights to use, copy, modify, merge, publish, distribute,
> +# sublicense, and/or sell copies of the Software, and to permit
> +# persons to whom the Software is furnished to do so, subject to the
> +# following conditions:
> +#
> +# The above copyright notice and this permission notice shall be
> +# included in all copies or substantial portions of the Software.
> +#
> +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
> +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
> +# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
> +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
> +# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
> +# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
> +# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
> +# SOFTWARE.
> +#
> +# Copyright (C) 2011 Citrix Ltd
> +
> +our $namespace, $ucnamespace;
> +
> +BEGIN {
> + Â Âdie unless @ARGV;
> + Â Â$namespace = pop @ARGV;
> + Â Â$namespace =~ s/^--prefix=// or die;
> + Â Â$ucnamespace = uc $namespace;
> +
> + Â Âprint <<END or die $!;
> +/*
> + * DO NOT EDIT THIS FILE
> + *
> + * Generated automatically by bsd-sys-queue-h-seddery to
> + * Â- introduce ${ucnamespace}_ and ${namespace}_ namespace prefixes
> + * Â- turn "struct type" into "type" so that type arguments
> + * Â Â to the macros are type names not struct tags
> + *
> + * The purpose of this seddery is to allow the resulting file to be
> + * freely included by software which might also want to include other
> + * list macros, and to be used when struct tags are not being used or
> + * not known.
> + */
> +END
> +}
> +
> +s/\b( _SYS_QUEUE |
> + Â Â ÂSLIST | LIST | STAILQ | TAILQ | QUEUE
> + Â Â Â)/${ucnamespace}_$1/xg;
> +
> +s/\b( TRACEBUF | TRASHIT |
> + Â Â ÂQMD_
> + Â Â Â)/${ucnamespace}__$1/xg;
> +
> +s/\b(
> + Â Â Âqm_
> + Â Â Â)/${namespace}__$1/xg;
> +
> +s/\b struct \s+ type \b/type/xg;
> diff --git a/tools/libxl/bsd-sys-queue.h b/tools/libxl/bsd-sys-queue.h
> new file mode 100644
> index 0000000..274e636
> --- /dev/null
> +++ b/tools/libxl/bsd-sys-queue.h
> @@ -0,0 +1,637 @@
> +/*-
> + * Copyright (c) 1991, 1993
> + * Â Â The Regents of the University of California. ÂAll rights reserved.
> + *
> + * Redistribution and use in source and binary forms, with or without
> + * modification, are permitted provided that the following conditions
> + * are met:
> + * 1. Redistributions of source code must retain the above copyright
> + * Â Ânotice, this list of conditions and the following disclaimer.
> + * 2. Redistributions in binary form must reproduce the above copyright
> + * Â Ânotice, this list of conditions and the following disclaimer in the
> + * Â Âdocumentation and/or other materials provided with the distribution.
> + * 4. Neither the name of the University nor the names of its contributors
> + * Â Âmay be used to endorse or promote products derived from this software
> + * Â Âwithout specific prior written permission.
> + *
> + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
> + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
> + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
> + * ARE DISCLAIMED. ÂIN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
> + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
> + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
> + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
> + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
> + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
> + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> + * SUCH DAMAGE.
> + *
> + *   @(#)queue.h   8.5 (Berkeley) 8/20/94
> + * $FreeBSD$
> + */
> +
> +#ifndef _SYS_QUEUE_H_
> +#define    Â_SYS_QUEUE_H_
> +
> +#include <sys/cdefs.h>
> +
> +/*
> + * This file defines four types of data structures: singly-linked lists,
> + * singly-linked tail queues, lists and tail queues.
> + *
> + * A singly-linked list is headed by a single forward pointer. The elements
> + * are singly linked for minimum space and pointer manipulation overhead at
> + * the expense of O(n) removal for arbitrary elements. New elements can be
> + * added to the list after an existing element or at the head of the list.
> + * Elements being removed from the head of the list should use the explicit
> + * macro for this purpose for optimum efficiency. A singly-linked list may
> + * only be traversed in the forward direction. ÂSingly-linked lists are ideal
> + * for applications with large datasets and few or no removals or for
> + * implementing a LIFO queue.
> + *
> + * A singly-linked tail queue is headed by a pair of pointers, one to the
> + * head of the list and the other to the tail of the list. The elements are
> + * singly linked for minimum space and pointer manipulation overhead at the
> + * expense of O(n) removal for arbitrary elements. New elements can be added
> + * to the list after an existing element, at the head of the list, or at the
> + * end of the list. Elements being removed from the head of the tail queue
> + * should use the explicit macro for this purpose for optimum efficiency.
> + * A singly-linked tail queue may only be traversed in the forward direction.
> + * Singly-linked tail queues are ideal for applications with large datasets
> + * and few or no removals or for implementing a FIFO queue.
> + *
> + * A list is headed by a single forward pointer (or an array of forward
> + * pointers for a hash table header). The elements are doubly linked
> + * so that an arbitrary element can be removed without a need to
> + * traverse the list. New elements can be added to the list before
> + * or after an existing element or at the head of the list. A list
> + * may only be traversed in the forward direction.
> + *
> + * A tail queue is headed by a pair of pointers, one to the head of the
> + * list and the other to the tail of the list. The elements are doubly
> + * linked so that an arbitrary element can be removed without a need to
> + * traverse the list. New elements can be added to the list before or
> + * after an existing element, at the head of the list, or at the end of
> + * the list. A tail queue may be traversed in either direction.
> + *
> + * For details on the use of these macros, see the queue(3) manual page.
> + *
> + *
> + * Â Â Â Â Â Â Â Â Â Â Â Â Â Â SLIST Â LIST Â ÂSTAILQ ÂTAILQ
> + * _HEAD Â Â Â Â Â Â Â Â Â Â Â + Â Â Â + Â Â Â + Â Â Â +
> + * _HEAD_INITIALIZER Â Â Â Â Â + Â Â Â + Â Â Â + Â Â Â +
> + * _ENTRY Â Â Â Â Â Â Â Â Â Â Â+ Â Â Â + Â Â Â + Â Â Â +
> + * _INIT Â Â Â Â Â Â Â Â Â Â Â + Â Â Â + Â Â Â + Â Â Â +
> + * _EMPTY Â Â Â Â Â Â Â Â Â Â Â+ Â Â Â + Â Â Â + Â Â Â +
> + * _FIRST Â Â Â Â Â Â Â Â Â Â Â+ Â Â Â + Â Â Â + Â Â Â +
> + * _NEXT Â Â Â Â Â Â Â Â Â Â Â + Â Â Â + Â Â Â + Â Â Â +
> + * _PREV Â Â Â Â Â Â Â Â Â Â Â - Â Â Â - Â Â Â - Â Â Â +
> + * _LAST Â Â Â Â Â Â Â Â Â Â Â - Â Â Â - Â Â Â + Â Â Â +
> + * _FOREACH Â Â Â Â Â Â Â Â Â Â+ Â Â Â + Â Â Â + Â Â Â +
> + * _FOREACH_SAFE Â Â Â Â Â Â Â + Â Â Â + Â Â Â + Â Â Â +
> + * _FOREACH_REVERSE Â Â Â Â Â Â- Â Â Â - Â Â Â - Â Â Â +
> + * _FOREACH_REVERSE_SAFE Â Â Â - Â Â Â - Â Â Â - Â Â Â +
> + * _INSERT_HEAD Â Â Â Â Â Â Â Â Â Â Â Â+ Â Â Â + Â Â Â + Â Â Â +
> + * _INSERT_BEFORE Â Â Â Â Â Â Â- Â Â Â + Â Â Â - Â Â Â +
> + * _INSERT_AFTER Â Â Â Â Â Â Â + Â Â Â + Â Â Â + Â Â Â +
> + * _INSERT_TAIL Â Â Â Â Â Â Â Â Â Â Â Â- Â Â Â - Â Â Â + Â Â Â +
> + * _CONCAT Â Â Â Â Â Â Â Â Â Â - Â Â Â - Â Â Â + Â Â Â +
> + * _REMOVE_AFTER Â Â Â Â Â Â Â + Â Â Â - Â Â Â + Â Â Â -
> + * _REMOVE_HEAD Â Â Â Â Â Â Â Â Â Â Â Â+ Â Â Â - Â Â Â + Â Â Â -
> + * _REMOVE Â Â Â Â Â Â Â Â Â Â + Â Â Â + Â Â Â + Â Â Â +
> + * _SWAP Â Â Â Â Â Â Â Â Â Â Â + Â Â Â + Â Â Â + Â Â Â +
> + *
> + */
> +#ifdef QUEUE_MACRO_DEBUG
> +/* Store the last 2 places the queue element or head was altered */
> +struct qm_trace {
> + Â Â Â char * lastfile;
> + Â Â Â int lastline;
> + Â Â Â char * prevfile;
> + Â Â Â int prevline;
> +};
> +
> +#define    ÂTRACEBUF    Âstruct qm_trace trace;
> +#define    ÂTRASHIT(x)   Âdo {(x) = (void *)-1;} while (0)
> +#define    ÂQMD_SAVELINK(name, link)    Âvoid **name = (void *)&(link)
> +
> +#define    ÂQMD_TRACE_HEAD(head) do {                   
> Â \
> + Â Â Â (head)->trace.prevline = (head)->trace.lastline; Â Â Â Â Â Â Â Â\
> + Â Â Â (head)->trace.prevfile = (head)->trace.lastfile; Â Â Â Â Â Â Â Â\
> + Â Â Â (head)->trace.lastline = __LINE__; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (head)->trace.lastfile = __FILE__; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂQMD_TRACE_ELEM(elem) do {                   
> Â \
> + Â Â Â (elem)->trace.prevline = (elem)->trace.lastline; Â Â Â Â Â Â Â Â\
> + Â Â Â (elem)->trace.prevfile = (elem)->trace.lastfile; Â Â Â Â Â Â Â Â\
> + Â Â Â (elem)->trace.lastline = __LINE__; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (elem)->trace.lastfile = __FILE__; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#else
> +#define    ÂQMD_TRACE_ELEM(elem)
> +#define    ÂQMD_TRACE_HEAD(head)
> +#define    ÂQMD_SAVELINK(name, link)
> +#define    ÂTRACEBUF
> +#define    ÂTRASHIT(x)
> +#endif /* QUEUE_MACRO_DEBUG */
> +
> +/*
> + * Singly-linked List declarations.
> + */
> +#define    ÂSLIST_HEAD(name, type)                    Â
>  Â\
> +struct name { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â struct type *slh_first; /* first element */ Â Â Â Â Â Â Â Â Â Â \
> +}
> +
> +#define    ÂSLIST_HEAD_INITIALIZER(head)                 Â
>  Â\
> + Â Â Â { NULL }
> +
> +#define    ÂSLIST_ENTRY(type)                       
> Â \
> +struct { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â struct type *sle_next; Â/* next element */ Â Â Â Â Â Â Â Â Â Â Â\
> +}
> +
> +/*
> + * Singly-linked List functions.
> + */
> +#define    ÂSLIST_EMPTY(head)    ((head)->slh_first == NULL)
> +
> +#define    ÂSLIST_FIRST(head)    ((head)->slh_first)
> +
> +#define    ÂSLIST_FOREACH(var, head, field)                
> Â \
> + Â Â Â for ((var) = SLIST_FIRST((head)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â (var); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â (var) = SLIST_NEXT((var), field))
> +
> +#define    ÂSLIST_FOREACH_SAFE(var, head, field, tvar)          Â
>  Â\
> + Â Â Â for ((var) = SLIST_FIRST((head)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â (var) && ((tvar) = SLIST_NEXT((var), field), 1); Â Â Â Â Â Â\
> + Â Â Â Â Â (var) = (tvar))
> +
> +#define    ÂSLIST_FOREACH_PREVPTR(var, varp, head, field)         
> Â \
> + Â Â Â for ((varp) = &SLIST_FIRST((head)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â ((var) = *(varp)) != NULL; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â (varp) = &SLIST_NEXT((var), field))
> +
> +#define    ÂSLIST_INIT(head) do {                     
> Â \
> + Â Â Â SLIST_FIRST((head)) = NULL; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> +} while (0)
> +
> +#define    ÂSLIST_INSERT_AFTER(slistelm, elm, field) do {         
> Â \
> + Â Â Â SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); Â Â Â \
> + Â Â Â SLIST_NEXT((slistelm), field) = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂSLIST_INSERT_HEAD(head, elm, field) do {           Â
>  Â\
> + Â Â Â SLIST_NEXT((elm), field) = SLIST_FIRST((head)); Â Â Â Â Â Â Â Â \
> + Â Â Â SLIST_FIRST((head)) = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂSLIST_NEXT(elm, field) Â((elm)->field.sle_next)
> +
> +#define    ÂSLIST_REMOVE(head, elm, type, field) do {           
> Â \
> + Â Â Â QMD_SAVELINK(oldnext, (elm)->field.sle_next); Â Â Â Â Â Â Â Â Â \
> + Â Â Â if (SLIST_FIRST((head)) == (elm)) { Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â SLIST_REMOVE_HEAD((head), field); Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â } Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â else { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â struct type *curelm = SLIST_FIRST((head)); Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â while (SLIST_NEXT(curelm, field) != (elm)) Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â Â Â Â Â curelm = SLIST_NEXT(curelm, field); Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â SLIST_REMOVE_AFTER(curelm, field); Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â } Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â TRASHIT(*oldnext); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define SLIST_REMOVE_AFTER(elm, field) do { Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â SLIST_NEXT(elm, field) = Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â SLIST_NEXT(SLIST_NEXT(elm, field), field); Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂSLIST_REMOVE_HEAD(head, field) do {              
> Â \
> + Â Â Â SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); Â \
> +} while (0)
> +
> +#define SLIST_SWAP(head1, head2, type) do { Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â struct type *swap_first = SLIST_FIRST(head1); Â Â Â Â Â Â Â Â Â \
> + Â Â Â SLIST_FIRST(head1) = SLIST_FIRST(head2); Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â SLIST_FIRST(head2) = swap_first; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +/*
> + * Singly-linked Tail queue declarations.
> + */
> +#define    ÂSTAILQ_HEAD(name, type)                    
> Â \
> +struct name { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â struct type *stqh_first;/* first element */ Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â struct type **stqh_last;/* addr of last next element */ Â Â Â Â \
> +}
> +
> +#define    ÂSTAILQ_HEAD_INITIALIZER(head)                 
> Â \
> + Â Â Â { NULL, &(head).stqh_first }
> +
> +#define    ÂSTAILQ_ENTRY(type)                      Â
>  Â\
> +struct { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â struct type *stqe_next; /* next element */ Â Â Â Â Â Â Â Â Â Â Â\
> +}
> +
> +/*
> + * Singly-linked Tail queue functions.
> + */
> +#define    ÂSTAILQ_CONCAT(head1, head2) do {               Â
>  Â\
> + Â Â Â if (!STAILQ_EMPTY((head2))) { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â *(head1)->stqh_last = (head2)->stqh_first; Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â (head1)->stqh_last = (head2)->stqh_last; Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â STAILQ_INIT((head2)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â } Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> +} while (0)
> +
> +#define    ÂSTAILQ_EMPTY(head)   Â((head)->stqh_first == NULL)
> +
> +#define    ÂSTAILQ_FIRST(head)   Â((head)->stqh_first)
> +
> +#define    ÂSTAILQ_FOREACH(var, head, field)               Â
>  Â\
> + Â Â Â for((var) = STAILQ_FIRST((head)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â(var); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â(var) = STAILQ_NEXT((var), field))
> +
> +
> +#define    ÂSTAILQ_FOREACH_SAFE(var, head, field, tvar)          
> Â \
> + Â Â Â for ((var) = STAILQ_FIRST((head)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â (var) && ((tvar) = STAILQ_NEXT((var), field), 1); Â Â Â Â Â \
> + Â Â Â Â Â (var) = (tvar))
> +
> +#define    ÂSTAILQ_INIT(head) do {                    Â
>  Â\
> + Â Â Â STAILQ_FIRST((head)) = NULL; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (head)->stqh_last = &STAILQ_FIRST((head)); Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂSTAILQ_INSERT_AFTER(head, tqelm, elm, field) do {       
> Â \
> + Â Â Â if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == 
> NULL)\
> + Â Â Â Â Â Â Â (head)->stqh_last = &STAILQ_NEXT((elm), field); Â Â Â Â \
> + Â Â Â STAILQ_NEXT((tqelm), field) = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂSTAILQ_INSERT_HEAD(head, elm, field) do {           
> Â \
> + Â Â Â if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
> + Â Â Â Â Â Â Â (head)->stqh_last = &STAILQ_NEXT((elm), field); Â Â Â Â \
> + Â Â Â STAILQ_FIRST((head)) = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> +} while (0)
> +
> +#define    ÂSTAILQ_INSERT_TAIL(head, elm, field) do {           
> Â \
> + Â Â Â STAILQ_NEXT((elm), field) = NULL; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â *(head)->stqh_last = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â (head)->stqh_last = &STAILQ_NEXT((elm), field); Â Â Â Â Â Â Â Â \
> +} while (0)
> +
> +#define    ÂSTAILQ_LAST(head, type, field)                Â
>  Â\
> + Â Â Â (STAILQ_EMPTY((head)) ? Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â NULL : Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â ((struct type *)(void *) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â ((char *)((head)->stqh_last) - __offsetof(struct type, 
> field))))
> +
> +#define    ÂSTAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
> +
> +#define    ÂSTAILQ_REMOVE(head, elm, type, field) do {          Â
>  Â\
> + Â Â Â QMD_SAVELINK(oldnext, (elm)->field.stqe_next); Â Â Â Â Â Â Â Â Â\
> + Â Â Â if (STAILQ_FIRST((head)) == (elm)) { Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â STAILQ_REMOVE_HEAD((head), field); Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â } Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â else { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â struct type *curelm = STAILQ_FIRST((head)); Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â while (STAILQ_NEXT(curelm, field) != (elm)) Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â Â Â Â Â curelm = STAILQ_NEXT(curelm, field); Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â STAILQ_REMOVE_AFTER(head, curelm, field); Â Â Â Â Â Â Â \
> + Â Â Â } Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â TRASHIT(*oldnext); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define STAILQ_REMOVE_AFTER(head, elm, field) do { Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â if ((STAILQ_NEXT(elm, field) = Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â ÂSTAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) Â Â Â\
> + Â Â Â Â Â Â Â (head)->stqh_last = &STAILQ_NEXT((elm), field); Â Â Â Â \
> +} while (0)
> +
> +#define    ÂSTAILQ_REMOVE_HEAD(head, field) do {             Â
>  Â\
> + Â Â Â if ((STAILQ_FIRST((head)) = Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â ÂSTAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) Â Â Â Â \
> + Â Â Â Â Â Â Â (head)->stqh_last = &STAILQ_FIRST((head)); Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define STAILQ_SWAP(head1, head2, type) do { Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â struct type *swap_first = STAILQ_FIRST(head1); Â Â Â Â Â Â Â Â Â\
> + Â Â Â struct type **swap_last = (head1)->stqh_last; Â Â Â Â Â Â Â Â Â \
> + Â Â Â STAILQ_FIRST(head1) = STAILQ_FIRST(head2); Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (head1)->stqh_last = (head2)->stqh_last; Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â STAILQ_FIRST(head2) = swap_first; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â (head2)->stqh_last = swap_last; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â if (STAILQ_EMPTY(head1)) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â (head1)->stqh_last = &STAILQ_FIRST(head1); Â Â Â Â Â Â Â\
> + Â Â Â if (STAILQ_EMPTY(head2)) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â (head2)->stqh_last = &STAILQ_FIRST(head2); Â Â Â Â Â Â Â\
> +} while (0)
> +
> +
> +/*
> + * List declarations.
> + */
> +#define    ÂLIST_HEAD(name, type)                     
> Â \
> +struct name { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â struct type *lh_first; Â/* first element */ Â Â Â Â Â Â Â Â Â Â \
> +}
> +
> +#define    ÂLIST_HEAD_INITIALIZER(head)                  
> Â \
> + Â Â Â { NULL }
> +
> +#define    ÂLIST_ENTRY(type)                       Â
>  Â\
> +struct { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â struct type *le_next; Â /* next element */ Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â struct type **le_prev; Â/* address of previous next element */ Â\
> +}
> +
> +/*
> + * List functions.
> + */
> +
> +#if (defined(_KERNEL) && defined(INVARIANTS))
> +#define    ÂQMD_LIST_CHECK_HEAD(head, field) do {             
> Â \
> + Â Â Â if (LIST_FIRST((head)) != NULL && Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â LIST_FIRST((head))->field.le_prev != Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â&LIST_FIRST((head))) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â panic("Bad list head %p first->prev != head", (head)); Â\
> +} while (0)
> +
> +#define    ÂQMD_LIST_CHECK_NEXT(elm, field) do {             Â
>  Â\
> + Â Â Â if (LIST_NEXT((elm), field) != NULL && Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â LIST_NEXT((elm), field)->field.le_prev != Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â&((elm)->field.le_next)) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â panic("Bad link elm %p next->prev != elm", (elm)); Â Â Â\
> +} while (0)
> +
> +#define    ÂQMD_LIST_CHECK_PREV(elm, field) do {             Â
>  Â\
> + Â Â Â if (*(elm)->field.le_prev != (elm)) Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â panic("Bad link elm %p prev->next != elm", (elm)); Â Â Â\
> +} while (0)
> +#else
> +#define    ÂQMD_LIST_CHECK_HEAD(head, field)
> +#define    ÂQMD_LIST_CHECK_NEXT(elm, field)
> +#define    ÂQMD_LIST_CHECK_PREV(elm, field)
> +#endif /* (_KERNEL && INVARIANTS) */
> +
> +#define    ÂLIST_EMPTY(head)    Â((head)->lh_first == NULL)
> +
> +#define    ÂLIST_FIRST(head)    Â((head)->lh_first)
> +
> +#define    ÂLIST_FOREACH(var, head, field)                Â
>  Â\
> + Â Â Â for ((var) = LIST_FIRST((head)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â (var); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â (var) = LIST_NEXT((var), field))
> +
> +#define    ÂLIST_FOREACH_SAFE(var, head, field, tvar)           
> Â \
> + Â Â Â for ((var) = LIST_FIRST((head)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â (var) && ((tvar) = LIST_NEXT((var), field), 1); Â Â Â Â Â Â \
> + Â Â Â Â Â (var) = (tvar))
> +
> +#define    ÂLIST_INIT(head) do {                     Â
>  Â\
> + Â Â Â LIST_FIRST((head)) = NULL; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂLIST_INSERT_AFTER(listelm, elm, field) do {          
> Â \
> + Â Â Â QMD_LIST_CHECK_NEXT(listelm, field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
> + Â Â Â Â Â Â Â LIST_NEXT((listelm), field)->field.le_prev = Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â Â Â &LIST_NEXT((elm), field); Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â LIST_NEXT((listelm), field) = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (elm)->field.le_prev = &LIST_NEXT((listelm), field); Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂLIST_INSERT_BEFORE(listelm, elm, field) do {         Â
>  Â\
> + Â Â Â QMD_LIST_CHECK_PREV(listelm, field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (elm)->field.le_prev = (listelm)->field.le_prev; Â Â Â Â Â Â Â Â\
> + Â Â Â LIST_NEXT((elm), field) = (listelm); Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â *(listelm)->field.le_prev = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (listelm)->field.le_prev = &LIST_NEXT((elm), field); Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂLIST_INSERT_HEAD(head, elm, field) do {            
> Â \
> + Â Â Â QMD_LIST_CHECK_HEAD((head), field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) Â Â \
> + Â Â Â Â Â Â Â LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
> + Â Â Â LIST_FIRST((head)) = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â (elm)->field.le_prev = &LIST_FIRST((head)); Â Â Â Â Â Â Â Â Â Â \
> +} while (0)
> +
> +#define    ÂLIST_NEXT(elm, field)  ((elm)->field.le_next)
> +
> +#define    ÂLIST_REMOVE(elm, field) do {                 Â
>  Â\
> + Â Â Â QMD_SAVELINK(oldnext, (elm)->field.le_next); Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â QMD_SAVELINK(oldprev, (elm)->field.le_prev); Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â QMD_LIST_CHECK_NEXT(elm, field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â QMD_LIST_CHECK_PREV(elm, field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â if (LIST_NEXT((elm), field) != NULL) Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â LIST_NEXT((elm), field)->field.le_prev = Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â Â Â (elm)->field.le_prev; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â *(elm)->field.le_prev = LIST_NEXT((elm), field); Â Â Â Â Â Â Â Â\
> + Â Â Â TRASHIT(*oldnext); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â TRASHIT(*oldprev); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define LIST_SWAP(head1, head2, type, field) do { Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â struct type *swap_tmp = LIST_FIRST((head1)); Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â LIST_FIRST((head1)) = LIST_FIRST((head2)); Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â LIST_FIRST((head2)) = swap_tmp; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â if ((swap_tmp = LIST_FIRST((head1))) != NULL) Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â swap_tmp->field.le_prev = &LIST_FIRST((head1)); Â Â Â Â \
> + Â Â Â if ((swap_tmp = LIST_FIRST((head2))) != NULL) Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â swap_tmp->field.le_prev = &LIST_FIRST((head2)); Â Â Â Â \
> +} while (0)
> +
> +/*
> + * Tail queue declarations.
> + */
> +#define    ÂTAILQ_HEAD(name, type)                    Â
>  Â\
> +struct name { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â struct type *tqh_first; /* first element */ Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â struct type **tqh_last; /* addr of last next element */ Â Â Â Â \
> + Â Â Â TRACEBUF Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +}
> +
> +#define    ÂTAILQ_HEAD_INITIALIZER(head)                 Â
>  Â\
> + Â Â Â { NULL, &(head).tqh_first }
> +
> +#define    ÂTAILQ_ENTRY(type)                       
> Â \
> +struct { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â struct type *tqe_next; Â/* next element */ Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â struct type **tqe_prev; /* address of previous next element */ Â\
> + Â Â Â TRACEBUF Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +}
> +
> +/*
> + * Tail queue functions.
> + */
> +#if (defined(_KERNEL) && defined(INVARIANTS))
> +#define    ÂQMD_TAILQ_CHECK_HEAD(head, field) do {            Â
>  Â\
> + Â Â Â if (!TAILQ_EMPTY(head) && Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â TAILQ_FIRST((head))->field.tqe_prev != Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â&TAILQ_FIRST((head))) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â panic("Bad tailq head %p first->prev != head", (head)); \
> +} while (0)
> +
> +#define    ÂQMD_TAILQ_CHECK_TAIL(head, field) do {            Â
>  Â\
> + Â Â Â if (*(head)->tqh_last != NULL) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); Â\
> +} while (0)
> +
> +#define    ÂQMD_TAILQ_CHECK_NEXT(elm, field) do {             
> Â \
> + Â Â Â if (TAILQ_NEXT((elm), field) != NULL && Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â TAILQ_NEXT((elm), field)->field.tqe_prev != Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â&((elm)->field.tqe_next)) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â panic("Bad link elm %p next->prev != elm", (elm)); Â Â Â\
> +} while (0)
> +
> +#define    ÂQMD_TAILQ_CHECK_PREV(elm, field) do {             
> Â \
> + Â Â Â if (*(elm)->field.tqe_prev != (elm)) Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â panic("Bad link elm %p prev->next != elm", (elm)); Â Â Â\
> +} while (0)
> +#else
> +#define    ÂQMD_TAILQ_CHECK_HEAD(head, field)
> +#define    ÂQMD_TAILQ_CHECK_TAIL(head, headname)
> +#define    ÂQMD_TAILQ_CHECK_NEXT(elm, field)
> +#define    ÂQMD_TAILQ_CHECK_PREV(elm, field)
> +#endif /* (_KERNEL && INVARIANTS) */
> +
> +#define    ÂTAILQ_CONCAT(head1, head2, field) do {            Â
>  Â\
> + Â Â Â if (!TAILQ_EMPTY(head2)) { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â *(head1)->tqh_last = (head2)->tqh_first; Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
> + Â Â Â Â Â Â Â (head1)->tqh_last = (head2)->tqh_last; Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â TAILQ_INIT((head2)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â QMD_TRACE_HEAD(head1); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â QMD_TRACE_HEAD(head2); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â } Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> +} while (0)
> +
> +#define    ÂTAILQ_EMPTY(head)    ((head)->tqh_first == NULL)
> +
> +#define    ÂTAILQ_FIRST(head)    ((head)->tqh_first)
> +
> +#define    ÂTAILQ_FOREACH(var, head, field)                
> Â \
> + Â Â Â for ((var) = TAILQ_FIRST((head)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â (var); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â (var) = TAILQ_NEXT((var), field))
> +
> +#define    ÂTAILQ_FOREACH_SAFE(var, head, field, tvar)          Â
>  Â\
> + Â Â Â for ((var) = TAILQ_FIRST((head)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â (var) && ((tvar) = TAILQ_NEXT((var), field), 1); Â Â Â Â Â Â\
> + Â Â Â Â Â (var) = (tvar))
> +
> +#define    ÂTAILQ_FOREACH_REVERSE(var, head, headname, field)       
> Â \
> + Â Â Â for ((var) = TAILQ_LAST((head), headname); Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â (var); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â (var) = TAILQ_PREV((var), headname, field))
> +
> +#define    ÂTAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) Â
>  Â\
> + Â Â Â for ((var) = TAILQ_LAST((head), headname); Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); Â\
> + Â Â Â Â Â (var) = (tvar))
> +
> +#define    ÂTAILQ_INIT(head) do {                     
> Â \
> + Â Â Â TAILQ_FIRST((head)) = NULL; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â (head)->tqh_last = &TAILQ_FIRST((head)); Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â QMD_TRACE_HEAD(head); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> +} while (0)
> +
> +#define    ÂTAILQ_INSERT_AFTER(head, listelm, elm, field) do {      Â
>  Â\
> + Â Â Â QMD_TAILQ_CHECK_NEXT(listelm, field); Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != 
> NULL)\
> + Â Â Â Â Â Â Â TAILQ_NEXT((elm), field)->field.tqe_prev = Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â Â Â &TAILQ_NEXT((elm), field); Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â else { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â (head)->tqh_last = &TAILQ_NEXT((elm), field); Â Â Â Â Â \
> + Â Â Â Â Â Â Â QMD_TRACE_HEAD(head); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â } Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â TAILQ_NEXT((listelm), field) = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); Â Â Â Â Â\
> + Â Â Â QMD_TRACE_ELEM(&(elm)->field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â QMD_TRACE_ELEM(&listelm->field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂTAILQ_INSERT_BEFORE(listelm, elm, field) do {         
> Â \
> + Â Â Â QMD_TAILQ_CHECK_PREV(listelm, field); Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â (elm)->field.tqe_prev = (listelm)->field.tqe_prev; Â Â Â Â Â Â Â\
> + Â Â Â TAILQ_NEXT((elm), field) = (listelm); Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â *(listelm)->field.tqe_prev = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); Â Â Â Â Â\
> + Â Â Â QMD_TRACE_ELEM(&(elm)->field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â QMD_TRACE_ELEM(&listelm->field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂTAILQ_INSERT_HEAD(head, elm, field) do {           Â
>  Â\
> + Â Â Â QMD_TAILQ_CHECK_HEAD(head, field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) Â \
> + Â Â Â Â Â Â Â TAILQ_FIRST((head))->field.tqe_prev = Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â Â Â &TAILQ_NEXT((elm), field); Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +    else                              Â\
> + Â Â Â Â Â Â Â (head)->tqh_last = &TAILQ_NEXT((elm), field); Â Â Â Â Â \
> + Â Â Â TAILQ_FIRST((head)) = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (elm)->field.tqe_prev = &TAILQ_FIRST((head)); Â Â Â Â Â Â Â Â Â \
> + Â Â Â QMD_TRACE_HEAD(head); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â QMD_TRACE_ELEM(&(elm)->field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂTAILQ_INSERT_TAIL(head, elm, field) do {           Â
>  Â\
> + Â Â Â QMD_TAILQ_CHECK_TAIL(head, field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â TAILQ_NEXT((elm), field) = NULL; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (elm)->field.tqe_prev = (head)->tqh_last; Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â *(head)->tqh_last = (elm); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (head)->tqh_last = &TAILQ_NEXT((elm), field); Â Â Â Â Â Â Â Â Â \
> + Â Â Â QMD_TRACE_HEAD(head); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â QMD_TRACE_ELEM(&(elm)->field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define    ÂTAILQ_LAST(head, headname)                  Â
>  Â\
> + Â Â Â (*(((struct headname *)((head)->tqh_last))->tqh_last))
> +
> +#define    ÂTAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
> +
> +#define    ÂTAILQ_PREV(elm, headname, field)               Â
>  Â\
> + Â Â Â (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
> +
> +#define    ÂTAILQ_REMOVE(head, elm, field) do {              
> Â \
> + Â Â Â QMD_SAVELINK(oldnext, (elm)->field.tqe_next); Â Â Â Â Â Â Â Â Â \
> + Â Â Â QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); Â Â Â Â Â Â Â Â Â \
> + Â Â Â QMD_TAILQ_CHECK_NEXT(elm, field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â QMD_TAILQ_CHECK_PREV(elm, field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â if ((TAILQ_NEXT((elm), field)) != NULL) Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â TAILQ_NEXT((elm), field)->field.tqe_prev = Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â Â Â (elm)->field.tqe_prev; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â else { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â (head)->tqh_last = (elm)->field.tqe_prev; Â Â Â Â Â Â Â \
> + Â Â Â Â Â Â Â QMD_TRACE_HEAD(head); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â } Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); Â Â Â Â Â Â Â\
> + Â Â Â TRASHIT(*oldnext); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â TRASHIT(*oldprev); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â QMD_TRACE_ELEM(&(elm)->field); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#define TAILQ_SWAP(head1, head2, type, field) do { Â Â Â Â Â Â Â Â Â Â \
> + Â Â Â struct type *swap_first = (head1)->tqh_first; Â Â Â Â Â Â Â Â Â \
> + Â Â Â struct type **swap_last = (head1)->tqh_last; Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (head1)->tqh_first = (head2)->tqh_first; Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (head1)->tqh_last = (head2)->tqh_last; Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (head2)->tqh_first = swap_first; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â (head2)->tqh_last = swap_last; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â if ((swap_first = (head1)->tqh_first) != NULL) Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â swap_first->field.tqe_prev = &(head1)->tqh_first; Â Â Â \
> +    else                              Â\
> + Â Â Â Â Â Â Â (head1)->tqh_last = &(head1)->tqh_first; Â Â Â Â Â Â Â Â\
> + Â Â Â if ((swap_first = (head2)->tqh_first) != NULL) Â Â Â Â Â Â Â Â Â\
> + Â Â Â Â Â Â Â swap_first->field.tqe_prev = &(head2)->tqh_first; Â Â Â \
> +    else                              Â\
> + Â Â Â Â Â Â Â (head2)->tqh_last = &(head2)->tqh_first; Â Â Â Â Â Â Â Â\
> +} while (0)
> +
> +#endif /* !_SYS_QUEUE_H_ */
> --
> tg: (92a50a8..) t/xen/bsd-queue (depends on: t/xen/gitignore)
>
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@xxxxxxxxxxxxxxxxxxx
> http://lists.xensource.com/xen-devel
>

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-devel