You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by Tony Finch <do...@dotat.at> on 2000/07/19 06:25:26 UTC
[PATCH] use BSD queue.h for bucket lists
Following the general policy of not reinventing the wheel when someone
else has already invented an excellent one, I thought it would be a
generally Good Thing to use the 4.4BSD queue(3) macros for all linked
lists in Apache. This patch changes the bucket brigades to use them.
Since the queue.h file is mostly verbatim from FreeBSD (apart from the
_CONCAT macros which I added and have sent to FreeBSD for addition),
should we import it as-is or tack the Apache licence on the top?
Tony.
--
f.a.n.finch fanf@covalent.net dot@dotat.at
457 honey wagon hayride
--- apache-2.0/src/lib/apr/buckets/ap_buf.c Tue Jul 18 23:29:53 2000
+++ apache-2.0-queue/src/lib/apr/buckets/ap_buf.c Wed Jul 19 04:14:19 2000
@@ -100,8 +100,12 @@
APR_EXPORT(ap_status_t) ap_bucket_brigade_destroy(void *data)
{
ap_bucket_brigade *b = data;
+ ap_bucket *e;
+
+ TAILQ_FOREACH(e, &b->list, link) {
+ ap_bucket_destroy(e);
+ }
- ap_bucket_list_destroy(b->head);
/* The brigade itself is allocated out of a pool, so we don't actually
* want to free it. If we did, we would do that free() here.
*/
@@ -109,50 +113,19 @@
return APR_SUCCESS;
}
-APR_EXPORT(ap_status_t) ap_bucket_list_destroy(ap_bucket *e)
-{
- ap_bucket *cur = e;
- ap_bucket *next;
-
- while (cur) {
- next = cur->next;
- ap_bucket_destroy(cur);
- cur = next;
- }
- return APR_SUCCESS;
-}
-
APR_EXPORT(ap_bucket_brigade *) ap_bucket_brigade_create(ap_pool_t *p)
{
ap_bucket_brigade *b;
b = ap_palloc(p, sizeof(*b));
b->p = p;
- b->head = b->tail = NULL;
+ TAILQ_INIT(&b->list);
ap_register_cleanup(b->p, b, ap_bucket_brigade_destroy,
ap_bucket_brigade_destroy);
return b;
}
-APR_EXPORT(void) ap_bucket_brigade_append_buckets(ap_bucket_brigade *b,
- ap_bucket *e)
-{
- ap_bucket *cur = e;
-
- if (b->tail) {
- b->tail->next = e;
- e->prev = b->tail;
- while (cur->next) {
- cur = cur->next;
- }
- b->tail = cur;
- }
- else {
- b->head = b->tail = e;
- }
-}
-
APR_EXPORT(int) ap_bucket_brigade_to_iovec(ap_bucket_brigade *b,
struct iovec *vec, int nvec)
{
@@ -160,12 +133,11 @@
struct iovec *orig;
orig = vec;
- e = b->head;
- while (e && nvec) {
+ TAILQ_FOREACH(e, &b->list, link) {
+ if (nvec-- == 0)
+ break;
vec->iov_base = (void *)ap_get_bucket_char_str(e);
vec->iov_len = ap_get_bucket_len(e);
- e = e->next;
- --nvec;
++vec;
}
return vec - orig;
@@ -174,33 +146,25 @@
APR_EXPORT(void) ap_bucket_brigade_catenate(ap_bucket_brigade *a,
ap_bucket_brigade *b)
{
- if (b->head) {
- if (a->tail) {
- a->tail->next = b->head;
- }
- b->head->prev = a->tail;
- a->tail = b->tail;
- if (!a->head) {
- a->head = b->head;
- }
- b->head = NULL;
- b->tail = b->head;
- }
+ TAILQ_CONCAT(&a->list, &b->list, link);
+}
+
+APR_EXPORT(void) ap_bucket_brigade_add_bucket(ap_bucket_brigade *b,
+ ap_bucket *e)
+{
+ TAILQ_INSERT_TAIL(&b->list, e, link);
}
APR_EXPORT(void) ap_consume_buckets(ap_bucket_brigade *b, int nvec)
{
- int i;
+ ap_bucket *e;
- for (i=0; i < nvec; i++) {
- if (b->head == b->tail) {
- ap_bucket_destroy(b->head);
- b->head = b->tail = NULL;
- break;
- }
- b->head = b->head->next;
- ap_bucket_destroy(b->head->prev);
- b->head->prev = NULL;
+ TAILQ_FOREACH(e, &b->list, link) {
+ if (nvec-- == 0)
+ break;
+ e = TAILQ_FIRST(&b->list);
+ ap_bucket_destroy(e);
+ TAILQ_REMOVE(&b->list, e, link);
}
}
@@ -208,24 +172,26 @@
ap_bucket_brigade *b,
ap_iol *iol)
{
+# define NVEC 16 /* seems like a reasonable number to me */
ap_status_t status;
int iov_used;
- struct iovec vec[16]; /* seems like a reasonable number to me */
+ struct iovec vec[NVEC];
ap_ssize_t bytes = 0;
*total_bytes = 0;
do {
- iov_used = ap_bucket_brigade_to_iovec(b, vec, 16);
+ iov_used = ap_bucket_brigade_to_iovec(b, vec, NVEC);
status = iol_writev(iol, vec, iov_used, &bytes);
- ap_consume_buckets(b, 16);
+ ap_consume_buckets(b, iov_used);
if (status != APR_SUCCESS) {
return status;
}
*total_bytes += bytes;
- } while (iov_used == 16);
+ } while (iov_used == NVEC);
return APR_SUCCESS;
+# undef NVEC
}
APR_EXPORT(const char *) ap_get_bucket_char_str(ap_bucket *b)
@@ -251,9 +217,8 @@
int j, k, rv;
ap_ssize_t i;
- if (b->tail && b->tail->color == AP_BUCKET_rwmem) {
- ap_bucket *rw;
- rw = b->tail;
+ r = TAILQ_LAST(b);
+ if (!TAILQ_EMPTY(&b->list) && r->color == AP_BUCKET_rwmem)
/* I have no idea if this is a good idea or not. Probably not.
* Basically, if the last bucket in the list is a rwmem bucket,
* then we just add to it instead of allocating a new read only
@@ -266,14 +231,14 @@
break;
j = strlen(x);
- rv = rw->insert(rw, x, j, &i);
+ rv = r->insert(rw, x, j, &i);
if (i != j) {
/* Do we need better error reporting? */
return -1;
}
k += i;
- ap_bucket_brigade_append_buckets(b, rw);
+ ap_bucket_brigade_add_bucket(b, r);
}
}
@@ -291,7 +256,7 @@
}
k += i;
- ap_bucket_brigade_append_buckets(b, r);
+ ap_bucket_brigade_add_bucket(b, r);
}
return k;
@@ -317,7 +282,7 @@
ap_bucket *r;
int res, i;
- res = ap_vsnprintf(buf, 4096, fmt, va);
+ res = ap_vsnprintf(buf, sizeof(buf), fmt, va);
r = ap_bucket_new(AP_BUCKET_rwmem);
res = r->insert(r, buf, strlen(buf), &i);
--- apache-2.0/src/lib/apr/buckets/apr_buf.h Tue Jul 18 23:29:53 2000
+++ apache-2.0-queue/src/lib/apr/buckets/apr_buf.h Wed Jul 19 04:16:43 2000
@@ -59,6 +59,7 @@
#include "apr_errno.h"
#include "../../../include/ap_iol.h"
#include "apr_private.h"
+#include "bsd_queue.h"
#ifdef HAVE_SYS_UIO_H
#include <sys/uio.h> /* for struct iovec */
#endif
@@ -81,6 +82,7 @@
typedef struct ap_bucket ap_bucket;
struct ap_bucket {
+ TAILQ_ENTRY(ap_bucket) link; /* next & previous buckets */
ap_bucket_color_e color; /* what type of bucket is it */
void (*free)(void *e); /* can be NULL */
void *data; /* for use by free() */
@@ -96,9 +98,6 @@
*/
int (*insert)(ap_bucket *e, const void *buf, ap_size_t nbytes, ap_ssize_t *w);
ap_status_t (*split)(ap_bucket *e, ap_size_t nbytes);
-
- ap_bucket *next; /* The next node in the bucket list */
- ap_bucket *prev; /* The prev node in the bucket list */
};
typedef struct ap_bucket_brigade ap_bucket_brigade;
@@ -108,8 +107,7 @@
but this lets me register a cleanup
to put a limit on the brigade's
lifetime. */
- ap_bucket *head; /* The start of the brigade */
- ap_bucket *tail; /* The end of the brigade */
+ TAILQ_HEAD(, ap_bucket) list;
};
/* ****** Different bucket types *****/
@@ -149,8 +147,8 @@
/* destroy an enitre bucket brigade */
APR_EXPORT(ap_status_t) ap_bucket_brigade_destroy(void *b);
-/* append bucket(s) to a bucket_brigade */
-APR_EXPORT(void) ap_bucket_brigade_append_buckets(ap_bucket_brigade *b,
+/* add a bucket to the end of a bucket_brigade */
+APR_EXPORT(void) ap_bucket_brigade_add_bucket(ap_bucket_brigade *b,
ap_bucket *e);
/* consume nbytes from beginning of b -- call ap_bucket_destroy as
@@ -189,9 +187,6 @@
/* destroy a bucket */
APR_EXPORT(ap_status_t) ap_bucket_destroy(ap_bucket *e);
-
-/* destroy an entire list of buckets */
-APR_EXPORT(ap_status_t) ap_bucket_list_destroy(ap_bucket *e);
/* Convert a bucket to a char * */
APR_EXPORT(const char *) ap_get_bucket_char_str(ap_bucket *b);
diff -Nru apache-2.0/src/lib/apr/buckets/bsd_queue.3 apache-2.0-queue/src/lib/apr/buckets/bsd_queue.3
--- apache-2.0/src/lib/apr/buckets/bsd_queue.3 Thu Jan 1 00:00:00 1970
+++ apache-2.0-queue/src/lib/apr/buckets/bsd_queue.3 Wed Jul 19 03:25:39 2000
@@ -0,0 +1,1066 @@
+.\" 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: src/share/man/man3/queue.3,v 1.15.2.2 2000/05/05 01:44:21 archie Exp $
+.\"
+.Dd January 24, 1994
+.Dt QUEUE 3
+.Os BSD 4
+.Sh NAME
+.Nm SLIST_EMPTY ,
+.Nm SLIST_ENTRY ,
+.Nm SLIST_FIRST ,
+.Nm SLIST_FOREACH ,
+.Nm SLIST_HEAD ,
+.Nm SLIST_INIT ,
+.Nm SLIST_INSERT_AFTER ,
+.Nm SLIST_INSERT_HEAD ,
+.Nm SLIST_NEXT ,
+.Nm SLIST_REMOVE_HEAD ,
+.Nm SLIST_REMOVE ,
+.Nm STAILQ_EMPTY ,
+.Nm STAILQ_ENTRY ,
+.Nm STAILQ_FIRST ,
+.Nm STAILQ_FOREACH ,
+.Nm STAILQ_HEAD ,
+.Nm STAILQ_INIT ,
+.Nm STAILQ_INSERT_AFTER ,
+.Nm STAILQ_INSERT_HEAD ,
+.Nm STAILQ_INSERT_TAIL ,
+.Nm STAILQ_LAST ,
+.Nm STAILQ_NEXT ,
+.Nm STAILQ_REMOVE_HEAD ,
+.Nm STAILQ_REMOVE ,
+.Nm LIST_EMPTY ,
+.Nm LIST_ENTRY ,
+.Nm LIST_FIRST ,
+.Nm LIST_FOREACH ,
+.Nm LIST_HEAD ,
+.Nm LIST_INIT ,
+.Nm LIST_INSERT_AFTER ,
+.Nm LIST_INSERT_BEFORE ,
+.Nm LIST_INSERT_HEAD ,
+.Nm LIST_NEXT ,
+.Nm LIST_REMOVE ,
+.Nm TAILQ_EMPTY ,
+.Nm TAILQ_ENTRY ,
+.Nm TAILQ_FIRST ,
+.Nm TAILQ_FOREACH ,
+.Nm TAILQ_FOREACH_REVERSE ,
+.Nm TAILQ_HEAD ,
+.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_CONCAT ,
+.Nm CIRCLEQ_EMPTY ,
+.Nm CIRCLEQ_ENTRY ,
+.Nm CIRCLEQ_FIRST ,
+.Nm CIRCLEQ_FOREACH ,
+.Nm CIRCLEQ_FOREACH_REVERSE ,
+.Nm CIRCLEQ_HEAD ,
+.Nm CIRCLEQ_INIT ,
+.Nm CIRCLEQ_INSERT_AFTER ,
+.Nm CIRCLEQ_INSERT_BEFORE ,
+.Nm CIRCLEQ_INSERT_HEAD ,
+.Nm CIRCLEQ_INSERT_TAIL ,
+.Nm CIRCLE_LAST ,
+.Nm CIRCLE_NEXT ,
+.Nm CIRCLE_PREV ,
+.Nm CIRCLEQ_REMOVE ,
+.Nm CIRCLEQ_CONCAT
+.Nd implementations of singly-linked lists, singly-linked tail queues,
+lists, tail queues, and circular queues
+.Sh SYNOPSIS
+.Fd #include <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_HEAD "HEADNAME" "TYPE"
+.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_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
+.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
+.\"
+.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_HEAD "HEADNAME" "TYPE"
+.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"
+.Fn STAILQ_NEXT "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 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_HEAD "HEADNAME" "TYPE"
+.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 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_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
+.Fn TAILQ_HEAD "HEADNAME" "TYPE"
+.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_CONCAT "TAILQ_HEAD *queue1" "TAILQ_HEAD *queue2" "TAILQ_ENTRY NAME"
+.\"
+.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_ENTRY "TYPE"
+.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
+.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_CONCAT "CIRCLEQ_HEAD *queue1" "CIRCLEQ_HEAD *queue2" "CIRCLEQ_ENTRY NAME"
+.Sh DESCRIPTION
+These macros define and operate on five types of data structures:
+singly-linked lists, singly-linked tail queues, lists, tail queues,
+and circular queues.
+All five 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
+O(n) removal of any entry in the list.
+.It
+Forward traversal through the list.
+.El
+.Pp
+Singly-linked lists are the simplest of the five 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.
+.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.
+.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, tail queues, and circle
+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 elements 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
+Circular 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
+The termination condition for traversal is more complex.
+.It
+Code size is about 40% greater and operations run about 45% slower
+than 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 ,
+.Li TAILQ_ENTRY ,
+or
+.Li CIRCLEQ_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 ,
+.Li TAILQ_HEAD ,
+or
+.Li CIRCLEQ_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_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_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_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.
+.Sh SINGLY-LINKED LIST EXAMPLE
+.Bd -literal
+SLIST_HEAD(slisthead, entry) 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. */
+free(n3);
+
+ /* Forward traversal. */
+SLIST_FOREACH(np, &head, entries)
+ 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_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_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 undefined.
+.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_HEAD
+removes the element
+.Fa elm
+from 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.
+.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
+.Bd -literal
+STAILQ_HEAD(stailhead, entry) 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-> ...
+ /* TailQ Deletion. */
+while (!STAILQ_EMPTY(&head)) {
+ n1 = STAILQ_HEAD(&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_EMPTY
+evaluates to true if their 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_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.
+.Sh LIST EXAMPLE
+.Bd -literal
+LIST_HEAD(listhead, entry) head;
+struct listhead *headp; /* List head. */
+struct entry {
+ ...
+ LIST_ENTRY(entry) entries; /* List. */
+ ...
+} *n1, *n2, *n3, *np;
+
+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-> ...
+
+while (!LIST_EMPTY(&head)) { /* List Deletion. */
+ n1 = LIST_FIRST(&head);
+ LIST_REMOVE(n1, entries);
+ free(n1);
+}
+
+n1 = LIST_FIRST(&head); /* Faster List Delete. */
+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_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 .
+.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 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 undefined.
+.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_CONCAT
+concatenates
+.Fa queue2
+onto the end of
+.Fa queue1 ,
+leaving
+.Fa queue2
+empty.
+.Sh TAIL QUEUE EXAMPLE
+.Bd -literal
+TAILQ_HEAD(tailhead, entry) 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-> ...
+ /* 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 CIRCULAR QUEUES
+A circular queue is headed by a structure defined by the
+.Nm CIRCLEQ_HEAD
+macro.
+This structure contains a pair of pointers,
+one to the first element in the circular queue and the other to the
+last element in the circular queue.
+The elements are doubly linked so that an arbitrary element can be
+removed without traversing the queue.
+New elements can be added to the queue after an existing element,
+before an existing element, at the head of the queue, or at the end
+of the queue.
+A
+.Fa CIRCLEQ_HEAD
+structure is declared as follows:
+.Bd -literal -offset indent
+CIRCLEQ_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 circular queue.
+A pointer to the head of the circular 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 CIRCLEQ_EMPTY
+evaluates to true if there are no items on the circle queue.
+.Pp
+The macro
+.Nm CIRCLEQ_ENTRY
+declares a structure that connects the elements in
+the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_FIRST
+returns the first item on the circle queue.
+.Pp
+The macro
+.Nm CICRLEQ_FOREACH
+traverses the circle queue referenced by
+.Fa head
+in the forward direction, assigning each element in turn to
+.Fa var .
+.Pp
+The macro
+.Nm CICRLEQ_FOREACH_REVERSE
+traverses the circle queue referenced by
+.Fa head
+in the reverse direction, assigning each element in turn to
+.Fa var .
+.Pp
+The macro
+.Nm CIRCLEQ_INIT
+initializes the circular queue referenced by
+.Fa head .
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_HEAD
+inserts the new element
+.Fa elm
+at the head of the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_TAIL
+inserts the new element
+.Fa elm
+at the end of the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_AFTER
+inserts the new element
+.Fa elm
+after the element
+.Fa listelm .
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_BEFORE
+inserts the new element
+.Fa elm
+before the element
+.Fa listelm .
+.Pp
+The macro
+.Nm CIRCLEQ_LAST
+returns the last item on the circle queue.
+.Pp
+The macro
+.Nm CIRCLEQ_NEXT
+returns the next item on the circle queue.
+.Pp
+The macro
+.Nm CIRCLEQ_PREV
+returns the previous item on the circle queue.
+.Pp
+The macro
+.Nm CIRCLEQ_REMOVE
+removes the element
+.Fa elm
+from the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_CONCAT
+concatenates
+.Fa queue2
+onto the end of
+.Fa queue1 ,
+leaving
+.Fa queue2
+empty.
+.Sh CIRCULAR QUEUE EXAMPLE
+.Bd -literal
+CIRCLEQ_HEAD(circleq, entry) head;
+struct circleq *headp; /* Circular queue head. */
+struct entry {
+ ...
+ CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
+ ...
+} *n1, *n2, *np;
+
+CIRCLEQ_INIT(&head); /* Initialize the circular queue. */
+
+n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
+CIRCLEQ_INSERT_HEAD(&head, n1, entries);
+
+n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
+CIRCLEQ_INSERT_TAIL(&head, n1, entries);
+
+n2 = malloc(sizeof(struct entry)); /* Insert after. */
+CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
+
+n2 = malloc(sizeof(struct entry)); /* Insert before. */
+CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
+
+CIRCLEQ_REMOVE(&head, n1, entries); /* Deletion. */
+free(n1);
+ /* Forward traversal. */
+CIRCLEQ_FOREACH(np, &head, entries)
+ np-> ...
+ /* Reverse traversal. */
+CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
+ np-> ...
+ /* CircleQ Deletion. */
+while (CIRCLEQ_FIRST(&head) != (void *)&head) {
+ n1 = CIRCLEQ_HEAD(&head);
+ CIRCLEQ_REMOVE(&head, n1, entries);
+ free(n1);
+}
+ /* Faster CircleQ Deletion. */
+n1 = CIRCLEQ_FIRST(&head);
+while (n1 != (void *)&head) {
+ n2 = CIRCLEQ_NEXT(n1, entries);
+ free(n1);
+ n1 = n2;
+}
+CIRCLEQ_INIT(&head);
+.Ed
+.Sh HISTORY
+The
+.Nm queue
+functions first appeared in
+.Bx 4.4 .
diff -Nru apache-2.0/src/lib/apr/buckets/bsd_queue.3~ apache-2.0-queue/src/lib/apr/buckets/bsd_queue.3~
--- apache-2.0/src/lib/apr/buckets/bsd_queue.3~ Thu Jan 1 00:00:00 1970
+++ apache-2.0-queue/src/lib/apr/buckets/bsd_queue.3~ Wed Jul 19 03:17:19 2000
@@ -0,0 +1,1038 @@
+.\" 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: src/share/man/man3/queue.3,v 1.15.2.2 2000/05/05 01:44:21 archie Exp $
+.\"
+.Dd January 24, 1994
+.Dt QUEUE 3
+.Os BSD 4
+.Sh NAME
+.Nm SLIST_EMPTY ,
+.Nm SLIST_ENTRY ,
+.Nm SLIST_FIRST ,
+.Nm SLIST_FOREACH ,
+.Nm SLIST_HEAD ,
+.Nm SLIST_INIT ,
+.Nm SLIST_INSERT_AFTER ,
+.Nm SLIST_INSERT_HEAD ,
+.Nm SLIST_NEXT ,
+.Nm SLIST_REMOVE_HEAD ,
+.Nm SLIST_REMOVE ,
+.Nm STAILQ_EMPTY ,
+.Nm STAILQ_ENTRY ,
+.Nm STAILQ_FIRST ,
+.Nm STAILQ_FOREACH ,
+.Nm STAILQ_HEAD ,
+.Nm STAILQ_INIT ,
+.Nm STAILQ_INSERT_AFTER ,
+.Nm STAILQ_INSERT_HEAD ,
+.Nm STAILQ_INSERT_TAIL ,
+.Nm STAILQ_LAST ,
+.Nm STAILQ_NEXT ,
+.Nm STAILQ_REMOVE_HEAD ,
+.Nm STAILQ_REMOVE ,
+.Nm LIST_EMPTY ,
+.Nm LIST_ENTRY ,
+.Nm LIST_FIRST ,
+.Nm LIST_FOREACH ,
+.Nm LIST_HEAD ,
+.Nm LIST_INIT ,
+.Nm LIST_INSERT_AFTER ,
+.Nm LIST_INSERT_BEFORE ,
+.Nm LIST_INSERT_HEAD ,
+.Nm LIST_NEXT ,
+.Nm LIST_REMOVE ,
+.Nm TAILQ_EMPTY ,
+.Nm TAILQ_ENTRY ,
+.Nm TAILQ_FIRST ,
+.Nm TAILQ_FOREACH ,
+.Nm TAILQ_FOREACH_REVERSE ,
+.Nm TAILQ_HEAD ,
+.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 CIRCLEQ_EMPTY ,
+.Nm CIRCLEQ_ENTRY ,
+.Nm CIRCLEQ_FIRST ,
+.Nm CIRCLEQ_FOREACH ,
+.Nm CIRCLEQ_FOREACH_REVERSE ,
+.Nm CIRCLEQ_HEAD ,
+.Nm CIRCLEQ_INIT ,
+.Nm CIRCLEQ_INSERT_AFTER ,
+.Nm CIRCLEQ_INSERT_BEFORE ,
+.Nm CIRCLEQ_INSERT_HEAD ,
+.Nm CIRCLEQ_INSERT_TAIL ,
+.Nm CIRCLE_LAST ,
+.Nm CIRCLE_NEXT ,
+.Nm CIRCLE_PREV ,
+.Nm CIRCLEQ_REMOVE
+.Nd implementations of singly-linked lists, singly-linked tail queues,
+lists, tail queues, and circular queues
+.Sh SYNOPSIS
+.Fd #include <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_HEAD "HEADNAME" "TYPE"
+.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_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
+.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
+.\"
+.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_HEAD "HEADNAME" "TYPE"
+.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"
+.Fn STAILQ_NEXT "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 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_HEAD "HEADNAME" "TYPE"
+.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 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_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
+.Fn TAILQ_HEAD "HEADNAME" "TYPE"
+.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 CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_ENTRY "TYPE"
+.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
+.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Sh DESCRIPTION
+These macros define and operate on five types of data structures:
+singly-linked lists, singly-linked tail queues, lists, tail queues,
+and circular queues.
+All five 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
+O(n) removal of any entry in the list.
+.It
+Forward traversal through the list.
+.El
+.Pp
+Singly-linked lists are the simplest of the five 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.
+.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.
+.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, tail queues, and circle
+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 elements 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.
+.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
+Circular 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.
+.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
+The termination condition for traversal is more complex.
+.It
+Code size is about 40% greater and operations run about 45% slower
+than 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 ,
+.Li TAILQ_ENTRY ,
+or
+.Li CIRCLEQ_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 ,
+.Li TAILQ_HEAD ,
+or
+.Li CIRCLEQ_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_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_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_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.
+.Sh SINGLY-LINKED LIST EXAMPLE
+.Bd -literal
+SLIST_HEAD(slisthead, entry) 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. */
+free(n3);
+
+ /* Forward traversal. */
+SLIST_FOREACH(np, &head, entries)
+ 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_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_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 undefined.
+.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_HEAD
+removes the element
+.Fa elm
+from 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.
+.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
+.Bd -literal
+STAILQ_HEAD(stailhead, entry) 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-> ...
+ /* TailQ Deletion. */
+while (!STAILQ_EMPTY(&head)) {
+ n1 = STAILQ_HEAD(&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_EMPTY
+evaluates to true if their 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_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.
+.Sh LIST EXAMPLE
+.Bd -literal
+LIST_HEAD(listhead, entry) head;
+struct listhead *headp; /* List head. */
+struct entry {
+ ...
+ LIST_ENTRY(entry) entries; /* List. */
+ ...
+} *n1, *n2, *n3, *np;
+
+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-> ...
+
+while (!LIST_EMPTY(&head)) { /* List Deletion. */
+ n1 = LIST_FIRST(&head);
+ LIST_REMOVE(n1, entries);
+ free(n1);
+}
+
+n1 = LIST_FIRST(&head); /* Faster List Delete. */
+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_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 .
+.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 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 undefined.
+.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.
+.Sh TAIL QUEUE EXAMPLE
+.Bd -literal
+TAILQ_HEAD(tailhead, entry) 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-> ...
+ /* 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 CIRCULAR QUEUES
+A circular queue is headed by a structure defined by the
+.Nm CIRCLEQ_HEAD
+macro.
+This structure contains a pair of pointers,
+one to the first element in the circular queue and the other to the
+last element in the circular queue.
+The elements are doubly linked so that an arbitrary element can be
+removed without traversing the queue.
+New elements can be added to the queue after an existing element,
+before an existing element, at the head of the queue, or at the end
+of the queue.
+A
+.Fa CIRCLEQ_HEAD
+structure is declared as follows:
+.Bd -literal -offset indent
+CIRCLEQ_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 circular queue.
+A pointer to the head of the circular 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 CIRCLEQ_EMPTY
+evaluates to true if there are no items on the circle queue.
+.Pp
+The macro
+.Nm CIRCLEQ_ENTRY
+declares a structure that connects the elements in
+the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_FIRST
+returns the first item on the circle queue.
+.Pp
+The macro
+.Nm CICRLEQ_FOREACH
+traverses the circle queue referenced by
+.Fa head
+in the forward direction, assigning each element in turn to
+.Fa var .
+.Pp
+The macro
+.Nm CICRLEQ_FOREACH_REVERSE
+traverses the circle queue referenced by
+.Fa head
+in the reverse direction, assigning each element in turn to
+.Fa var .
+.Pp
+The macro
+.Nm CIRCLEQ_INIT
+initializes the circular queue referenced by
+.Fa head .
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_HEAD
+inserts the new element
+.Fa elm
+at the head of the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_TAIL
+inserts the new element
+.Fa elm
+at the end of the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_AFTER
+inserts the new element
+.Fa elm
+after the element
+.Fa listelm .
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_BEFORE
+inserts the new element
+.Fa elm
+before the element
+.Fa listelm .
+.Pp
+The macro
+.Nm CIRCLEQ_LAST
+returns the last item on the circle queue.
+.Pp
+The macro
+.Nm CIRCLEQ_NEXT
+returns the next item on the circle queue.
+.Pp
+The macro
+.Nm CIRCLEQ_PREV
+returns the previous item on the circle queue.
+.Pp
+The macro
+.Nm CIRCLEQ_REMOVE
+removes the element
+.Fa elm
+from the circular queue.
+.Sh CIRCULAR QUEUE EXAMPLE
+.Bd -literal
+CIRCLEQ_HEAD(circleq, entry) head;
+struct circleq *headp; /* Circular queue head. */
+struct entry {
+ ...
+ CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
+ ...
+} *n1, *n2, *np;
+
+CIRCLEQ_INIT(&head); /* Initialize the circular queue. */
+
+n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
+CIRCLEQ_INSERT_HEAD(&head, n1, entries);
+
+n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
+CIRCLEQ_INSERT_TAIL(&head, n1, entries);
+
+n2 = malloc(sizeof(struct entry)); /* Insert after. */
+CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
+
+n2 = malloc(sizeof(struct entry)); /* Insert before. */
+CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
+
+CIRCLEQ_REMOVE(&head, n1, entries); /* Deletion. */
+free(n1);
+ /* Forward traversal. */
+CIRCLEQ_FOREACH(np, &head, entries)
+ np-> ...
+ /* Reverse traversal. */
+CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
+ np-> ...
+ /* CircleQ Deletion. */
+while (CIRCLEQ_FIRST(&head) != (void *)&head) {
+ n1 = CIRCLEQ_HEAD(&head);
+ CIRCLEQ_REMOVE(&head, n1, entries);
+ free(n1);
+}
+ /* Faster CircleQ Deletion. */
+n1 = CIRCLEQ_FIRST(&head);
+while (n1 != (void *)&head) {
+ n2 = CIRCLEQ_NEXT(n1, entries);
+ free(n1);
+ n1 = n2;
+}
+CIRCLEQ_INIT(&head);
+.Ed
+.Sh HISTORY
+The
+.Nm queue
+functions first appeared in
+.Bx 4.4 .
--- apache-2.0/src/lib/apr/buckets/bsd_queue.h Thu Jan 1 00:00:00 1970
+++ apache-2.0-queue/src/lib/apr/buckets/bsd_queue.h Wed Jul 19 03:15:10 2000
@@ -0,0 +1,569 @@
+/*
+ * 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.
+ * 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.h 8.5 (Berkeley) 8/20/94
+ * $FreeBSD: src/sys/sys/queue.h,v 1.32.2.2 2000/05/05 01:40:02 archie Exp $
+ */
+
+#ifndef _SYS_QUEUE_H_
+#define _SYS_QUEUE_H_
+
+/*
+ * This file defines five types of data structures: singly-linked lists,
+ * singly-linked tail queues, lists, tail queues, and circular 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. Tail
+ * queues may be concated.
+ *
+ * A circle 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 circle queue may be traversed in either direction, but has a more
+ * complex end of list detection. Circle queues may be concatenated.
+ *
+ * For details on the use of these macros, see the queue(3) manual page.
+ *
+ *
+ * SLIST LIST STAILQ TAILQ CIRCLEQ
+ * _HEAD + + + + +
+ * _ENTRY + + + + +
+ * _INIT + + + + +
+ * _EMPTY + + + + +
+ * _FIRST + + + + +
+ * _NEXT + + + + +
+ * _PREV - - - + +
+ * _LAST - - + + +
+ * _FOREACH + + + + +
+ * _FOREACH_REVERSE - - - + +
+ * _INSERT_HEAD + + + + +
+ * _INSERT_BEFORE - + - + +
+ * _INSERT_AFTER + + + + +
+ * _INSERT_TAIL - - + + +
+ * _REMOVE_HEAD + - + - -
+ * _REMOVE + + + + +
+ * _CONCAT - - - + +
+ *
+ */
+
+/*
+ * Singly-linked List definitions.
+ */
+#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) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
+
+#define SLIST_INIT(head) { \
+ (head)->slh_first = NULL; \
+}
+
+#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
+ (elm)->field.sle_next = (slistelm)->field.sle_next; \
+ (slistelm)->field.sle_next = (elm); \
+} while (0)
+
+#define SLIST_INSERT_HEAD(head, elm, field) do { \
+ (elm)->field.sle_next = (head)->slh_first; \
+ (head)->slh_first = (elm); \
+} while (0)
+
+#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
+
+#define SLIST_REMOVE_HEAD(head, field) do { \
+ (head)->slh_first = (head)->slh_first->field.sle_next; \
+} while (0)
+
+#define SLIST_REMOVE(head, elm, type, field) do { \
+ if ((head)->slh_first == (elm)) { \
+ SLIST_REMOVE_HEAD((head), field); \
+ } \
+ else { \
+ struct type *curelm = (head)->slh_first; \
+ while( curelm->field.sle_next != (elm) ) \
+ curelm = curelm->field.sle_next; \
+ curelm->field.sle_next = \
+ curelm->field.sle_next->field.sle_next; \
+ } \
+} while (0)
+
+/*
+ * Singly-linked Tail queue definitions.
+ */
+#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_EMPTY(head) ((head)->stqh_first == NULL)
+
+#define STAILQ_INIT(head) do { \
+ (head)->stqh_first = NULL; \
+ (head)->stqh_last = &(head)->stqh_first; \
+} while (0)
+
+#define STAILQ_FIRST(head) ((head)->stqh_first)
+#define STAILQ_LAST(head) (*(head)->stqh_last)
+
+#define STAILQ_FOREACH(var, head, field) \
+ for((var) = (head)->stqh_first; (var); (var) = (var)->field.stqe_next)
+
+#define STAILQ_INSERT_HEAD(head, elm, field) do { \
+ if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
+ (head)->stqh_last = &(elm)->field.stqe_next; \
+ (head)->stqh_first = (elm); \
+} while (0)
+
+#define STAILQ_INSERT_TAIL(head, elm, field) do { \
+ (elm)->field.stqe_next = NULL; \
+ *(head)->stqh_last = (elm); \
+ (head)->stqh_last = &(elm)->field.stqe_next; \
+} while (0)
+
+#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
+ if (((elm)->field.stqe_next = (tqelm)->field.stqe_next) == NULL)\
+ (head)->stqh_last = &(elm)->field.stqe_next; \
+ (tqelm)->field.stqe_next = (elm); \
+} while (0)
+
+#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
+
+#define STAILQ_REMOVE_HEAD(head, field) do { \
+ if (((head)->stqh_first = \
+ (head)->stqh_first->field.stqe_next) == NULL) \
+ (head)->stqh_last = &(head)->stqh_first; \
+} while (0)
+
+#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
+ if (((head)->stqh_first = (elm)->field.stqe_next) == NULL) \
+ (head)->stqh_last = &(head)->stqh_first; \
+} while (0)
+
+#define STAILQ_REMOVE(head, elm, type, field) do { \
+ if ((head)->stqh_first == (elm)) { \
+ STAILQ_REMOVE_HEAD(head, field); \
+ } \
+ else { \
+ struct type *curelm = (head)->stqh_first; \
+ while( curelm->field.stqe_next != (elm) ) \
+ curelm = curelm->field.stqe_next; \
+ if((curelm->field.stqe_next = \
+ curelm->field.stqe_next->field.stqe_next) == NULL) \
+ (head)->stqh_last = &(curelm)->field.stqe_next; \
+ } \
+} while (0)
+
+/*
+ * List definitions.
+ */
+#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.
+ */
+
+#define LIST_EMPTY(head) ((head)->lh_first == NULL)
+
+#define LIST_FIRST(head) ((head)->lh_first)
+
+#define LIST_FOREACH(var, head, field) \
+ for((var) = (head)->lh_first; (var); (var) = (var)->field.le_next)
+
+#define LIST_INIT(head) do { \
+ (head)->lh_first = NULL; \
+} while (0)
+
+#define LIST_INSERT_AFTER(listelm, elm, field) do { \
+ if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
+ (listelm)->field.le_next->field.le_prev = \
+ &(elm)->field.le_next; \
+ (listelm)->field.le_next = (elm); \
+ (elm)->field.le_prev = &(listelm)->field.le_next; \
+} while (0)
+
+#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
+ (elm)->field.le_prev = (listelm)->field.le_prev; \
+ (elm)->field.le_next = (listelm); \
+ *(listelm)->field.le_prev = (elm); \
+ (listelm)->field.le_prev = &(elm)->field.le_next; \
+} while (0)
+
+#define LIST_INSERT_HEAD(head, elm, field) do { \
+ if (((elm)->field.le_next = (head)->lh_first) != NULL) \
+ (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
+ (head)->lh_first = (elm); \
+ (elm)->field.le_prev = &(head)->lh_first; \
+} while (0)
+
+#define LIST_NEXT(elm, field) ((elm)->field.le_next)
+
+#define LIST_REMOVE(elm, field) do { \
+ if ((elm)->field.le_next != NULL) \
+ (elm)->field.le_next->field.le_prev = \
+ (elm)->field.le_prev; \
+ *(elm)->field.le_prev = (elm)->field.le_next; \
+} while (0)
+
+/*
+ * Tail queue definitions.
+ */
+#define TAILQ_HEAD(name, type) \
+struct name { \
+ struct type *tqh_first; /* first element */ \
+ struct type **tqh_last; /* addr of last next element */ \
+}
+
+#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 */ \
+}
+
+/*
+ * Tail queue functions.
+ */
+#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
+
+#define TAILQ_FOREACH(var, head, field) \
+ for (var = TAILQ_FIRST(head); var; var = TAILQ_NEXT(var, field))
+
+#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
+ for ((var) = TAILQ_LAST((head), headname); \
+ (var); \
+ (var) = TAILQ_PREV((var), headname, field))
+
+#define TAILQ_FIRST(head) ((head)->tqh_first)
+
+#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_INIT(head) do { \
+ (head)->tqh_first = NULL; \
+ (head)->tqh_last = &(head)->tqh_first; \
+} while (0)
+
+#define TAILQ_INSERT_HEAD(head, elm, field) do { \
+ if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
+ (head)->tqh_first->field.tqe_prev = \
+ &(elm)->field.tqe_next; \
+ else \
+ (head)->tqh_last = &(elm)->field.tqe_next; \
+ (head)->tqh_first = (elm); \
+ (elm)->field.tqe_prev = &(head)->tqh_first; \
+} while (0)
+
+#define TAILQ_INSERT_TAIL(head, elm, field) do { \
+ (elm)->field.tqe_next = NULL; \
+ (elm)->field.tqe_prev = (head)->tqh_last; \
+ *(head)->tqh_last = (elm); \
+ (head)->tqh_last = &(elm)->field.tqe_next; \
+} while (0)
+
+#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
+ if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
+ (elm)->field.tqe_next->field.tqe_prev = \
+ &(elm)->field.tqe_next; \
+ else \
+ (head)->tqh_last = &(elm)->field.tqe_next; \
+ (listelm)->field.tqe_next = (elm); \
+ (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
+} while (0)
+
+#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
+ (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
+ (elm)->field.tqe_next = (listelm); \
+ *(listelm)->field.tqe_prev = (elm); \
+ (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
+} while (0)
+
+#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); \
+ } \
+} while (0)
+
+#define TAILQ_REMOVE(head, elm, field) do { \
+ if (((elm)->field.tqe_next) != NULL) \
+ (elm)->field.tqe_next->field.tqe_prev = \
+ (elm)->field.tqe_prev; \
+ else \
+ (head)->tqh_last = (elm)->field.tqe_prev; \
+ *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
+} while (0)
+
+/*
+ * Circular queue definitions.
+ */
+#define CIRCLEQ_HEAD(name, type) \
+struct name { \
+ struct type *cqh_first; /* first element */ \
+ struct type *cqh_last; /* last element */ \
+}
+
+#define CIRCLEQ_ENTRY(type) \
+struct { \
+ struct type *cqe_next; /* next element */ \
+ struct type *cqe_prev; /* previous element */ \
+}
+
+/*
+ * Circular queue functions.
+ */
+#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
+
+#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
+
+#define CIRCLEQ_FOREACH(var, head, field) \
+ for((var) = (head)->cqh_first; \
+ (var) != (void *)(head); \
+ (var) = (var)->field.cqe_next)
+
+#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
+ for((var) = (head)->cqh_last; \
+ (var) != (void *)(head); \
+ (var) = (var)->field.cqe_prev)
+
+#define CIRCLEQ_INIT(head) do { \
+ (head)->cqh_first = (void *)(head); \
+ (head)->cqh_last = (void *)(head); \
+} while (0)
+
+#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
+ (elm)->field.cqe_next = (listelm)->field.cqe_next; \
+ (elm)->field.cqe_prev = (listelm); \
+ if ((listelm)->field.cqe_next == (void *)(head)) \
+ (head)->cqh_last = (elm); \
+ else \
+ (listelm)->field.cqe_next->field.cqe_prev = (elm); \
+ (listelm)->field.cqe_next = (elm); \
+} while (0)
+
+#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
+ (elm)->field.cqe_next = (listelm); \
+ (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
+ if ((listelm)->field.cqe_prev == (void *)(head)) \
+ (head)->cqh_first = (elm); \
+ else \
+ (listelm)->field.cqe_prev->field.cqe_next = (elm); \
+ (listelm)->field.cqe_prev = (elm); \
+} while (0)
+
+#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
+ (elm)->field.cqe_next = (head)->cqh_first; \
+ (elm)->field.cqe_prev = (void *)(head); \
+ if ((head)->cqh_last == (void *)(head)) \
+ (head)->cqh_last = (elm); \
+ else \
+ (head)->cqh_first->field.cqe_prev = (elm); \
+ (head)->cqh_first = (elm); \
+} while (0)
+
+#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
+ (elm)->field.cqe_next = (void *)(head); \
+ (elm)->field.cqe_prev = (head)->cqh_last; \
+ if ((head)->cqh_first == (void *)(head)) \
+ (head)->cqh_first = (elm); \
+ else \
+ (head)->cqh_last->field.cqe_next = (elm); \
+ (head)->cqh_last = (elm); \
+} while (0)
+
+#define CIRCLEQ_CONCAT(head1, head2, field) do { \
+ if (!CIRCLEQ_EMPTY(head2)) { \
+ if (!CIRCLEQ_EMPTY(head1)) { \
+ (head1)->cqh_last->field.cqe_next = \
+ (head2)->cqh_first; \
+ (head2)->cqh_first->field.cqe_prev = \
+ (head1)->cqh_last; \
+ } else { \
+ (head1)->cqh_first = (head2)->cqh_first; \
+ (head2)->cqh_first->field.cqe_prev = \
+ (void *)(head1); \
+ } \
+ (head1)->cqh_last = (head2)->cqh_last; \
+ (head2)->cqh_last->field.cqe_next = \
+ (void *)(head1); \
+ CIRCLEQ_INIT(head2); \
+ } \
+} while (0)
+
+#define CIRCLEQ_LAST(head) ((head)->cqh_last)
+
+#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)
+
+#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
+
+#define CIRCLEQ_REMOVE(head, elm, field) do { \
+ if ((elm)->field.cqe_next == (void *)(head)) \
+ (head)->cqh_last = (elm)->field.cqe_prev; \
+ else \
+ (elm)->field.cqe_next->field.cqe_prev = \
+ (elm)->field.cqe_prev; \
+ if ((elm)->field.cqe_prev == (void *)(head)) \
+ (head)->cqh_first = (elm)->field.cqe_next; \
+ else \
+ (elm)->field.cqe_prev->field.cqe_next = \
+ (elm)->field.cqe_next; \
+} while (0)
+
+#ifdef _KERNEL
+
+/*
+ * XXX insque() and remque() are an old way of handling certain queues.
+ * They bogusly assumes that all queue heads look alike.
+ */
+
+struct quehead {
+ struct quehead *qh_link;
+ struct quehead *qh_rlink;
+};
+
+#ifdef __GNUC__
+
+static __inline void
+insque(void *a, void *b)
+{
+ struct quehead *element = a, *head = b;
+
+ element->qh_link = head->qh_link;
+ element->qh_rlink = head;
+ head->qh_link = element;
+ element->qh_link->qh_rlink = element;
+}
+
+static __inline void
+remque(void *a)
+{
+ struct quehead *element = a;
+
+ element->qh_link->qh_rlink = element->qh_rlink;
+ element->qh_rlink->qh_link = element->qh_link;
+ element->qh_rlink = 0;
+}
+
+#else /* !__GNUC__ */
+
+void insque __P((void *a, void *b));
+void remque __P((void *a));
+
+#endif /* __GNUC__ */
+
+#endif /* _KERNEL */
+
+#endif /* !_SYS_QUEUE_H_ */
Re: [PATCH] use BSD queue.h for bucket lists
Posted by Tony Finch <do...@dotat.at>.
Greg Stein <gs...@lyra.org> wrote:
>On Tue, Aug 15, 2000 at 03:17:40AM +0000, Tony Finch wrote:
>> Did we come to any conclusion about linked list macro sets? I don't
>> like manual pointer juggling if I can avoid it, so I'd like to use
>> either dean's or BSD's macros or even an entirely new wheel.
>
>euh... I'm not exactly sure how these would help us over the simple
>next/prev pointers that we have in there now.
They help prevent bugs.
Tony.
--
en oeccget g mtcaa f.a.n.finch
v spdlkishrhtewe y dot@dotat.at
eatp o v eiti i d. fanf@covalent.net
Re: [PATCH] use BSD queue.h for bucket lists
Posted by Greg Stein <gs...@lyra.org>.
On Tue, Aug 15, 2000 at 03:17:40AM +0000, Tony Finch wrote:
> Did we come to any conclusion about linked list macro sets? I don't
> like manual pointer juggling if I can avoid it, so I'd like to use
> either dean's or BSD's macros or even an entirely new wheel.
euh... I'm not exactly sure how these would help us over the simple
next/prev pointers that we have in there now.
I'm a bit reluctant to toss in add'l complexity for marginal gains.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: [PATCH] use BSD queue.h for bucket lists
Posted by dean gaudet <dg...@arctic.org>.
On Tue, 15 Aug 2000, Tony Finch wrote:
> Did we come to any conclusion about linked list macro sets? I don't
> like manual pointer juggling if I can avoid it, so I'd like to use
> either dean's or BSD's macros or even an entirely new wheel.
>
> dean BSD new wheel
> +0 +1 -0
BSD +1
regarding my ring stuff i'd rather just go about submitting those to the
BSD folks.
however, you realise that including a BSD header file in apache will mean
we might have to rename all the symbols.
-dean
Re: [PATCH] use BSD queue.h for bucket lists
Posted by Tony Finch <do...@dotat.at>.
Did we come to any conclusion about linked list macro sets? I don't
like manual pointer juggling if I can avoid it, so I'd like to use
either dean's or BSD's macros or even an entirely new wheel.
dean BSD new wheel
+0 +1 -0
Tony.
--
en oeccget g mtcaa f.a.n.finch
v spdlkishrhtewe y dot@dotat.at
eatp o v eiti i d. fanf@covalent.net
Re: [PATCH] use BSD queue.h for bucket lists
Posted by dean gaudet <dg...@arctic.org>.
On Wed, 19 Jul 2000, Tony Finch wrote:
> Following the general policy of not reinventing the wheel when someone
> else has already invented an excellent one, I thought it would be a
> generally Good Thing to use the 4.4BSD queue(3) macros for all linked
> lists in Apache. This patch changes the bucket brigades to use them.
>
> Since the queue.h file is mostly verbatim from FreeBSD (apart from the
> _CONCAT macros which I added and have sent to FreeBSD for addition),
> should we import it as-is or tack the Apache licence on the top?
huh, that's weird. CIRCLEQ *should* be able to do insert without the
if() statement... and without the head pointer.
+#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
+ (elm)->field.cqe_next = (listelm)->field.cqe_next; \
+ (elm)->field.cqe_prev = (listelm); \
+ if ((listelm)->field.cqe_next == (void *)(head)) \
+ (head)->cqh_last = (elm); \
+ else \
+ (listelm)->field.cqe_next->field.cqe_prev = (elm); \
+ (listelm)->field.cqe_next = (elm); \
+} while (0)
oh i know why. there's an offsetof()/casting trick optimisation they're
missing.
here's my ring implementation which are essentially CIRCLEQs but with a
tighter append operation.
in my case i initialise the head with pointers that are offset by the
offsetof elm->field, and that makes the if () disappear. both result in 1
load, and 4 stores, but mine is generally a few less instructions, and
never branches. (both versions degenerate to each other when field is the
first element of the struct so that its at offset 0)
-dean
#ifndef SPLIM_RING_H
#define SPLIM_RING_H 1
/* XXX: hrm might be able to clean this up some, not sure */
#include <stddef.h> /* for offsetof */
/*
the macros in this file implement a doubly-linked ring data structure.
a doubly-linked ring is similar to a doubly-linked list except that the
end points back to the beginning, and vice-versa. This eliminates a
bunch of special cases and makes them more efficient than lists.
the easiest way to understand this data structure is to get a piece of
paper and a pen and start drawing the elements and their links as you
step through the operations.
a few notes about the implementation:
many list implementations use a structure such as:
struct list {
struct list *next;
struct list *prev;
void *elt;
};
this has its purposes and its benefits. ring doesn't do this, ring
is embedded into the elements to save memory/cycles:
struct elt {
struct elt *next;
struct elt *prev;
... rest of element
};
this requires us to know a priori what rings an element could possibly
be on. (although it's pretty obvious how you'd use these templates
to generate a generic ring object.)
it is possible for an element to be on multiple rings, you just declare
foo_next/foo_prev fields within the element for each ring.
rings have a sentinel -- the list header itself is the sentinel. it is
not an element, but we play typecasting games which make it appear to
be an element.
the sentinel is used when iterating around the ring -- you know you've
hit the end of the ring when you see the sentinel.
to use ring you have to embed a foo_next and foo_prev field into
your element struct -- they must be in that order, next then prev.
then you instantiate the template with the ring_template(base, foo)
macro where base is the type of your structure. this defines
foo_ring_t which is the list header type; and it defines a slew
of foo_xxxx() inline functions which manipulate your foo.
thanks to the folks at WATCOM in Waterloo, Canada, which is where
i first learned of doubly-linked rings.
*/
/*
base is the base type of the structure that will be placed into
the ring
foo is the name of the list
*/
#define ring_template(base, foo) \
typedef struct { \
base *foo##_next; \
base *foo##_prev; \
} foo##_ring_t; \
\
static inline void foo##_ring_init(foo##_ring_t *l); \
static inline void foo##_ring_init(foo##_ring_t *l) \
{ \
l->foo##_next = (base *)((char *)l - offsetof(base, foo##_next)); \
l->foo##_prev = (base *)((char *)l - offsetof(base, foo##_next)); \
} \
\
static inline void foo##_elt_init(base *elt); \
static inline void foo##_elt_init(base *elt) \
{ \
elt->foo##_next = elt; \
elt->foo##_prev = elt; \
} \
\
static inline base *foo##_first(foo##_ring_t *l); \
static inline base *foo##_first(foo##_ring_t *l) \
{ \
return l->foo##_next; \
} \
\
static inline base *foo##_last(foo##_ring_t *l); \
static inline base *foo##_last(foo##_ring_t *l) \
{ \
return l->foo##_prev; \
} \
\
static inline base *foo##_sentinel(foo##_ring_t *l); \
static inline base *foo##_sentinel(foo##_ring_t *l) \
{ \
return (base *)((char *)l - offsetof(base, foo##_next)); \
} \
\
static inline void foo##_unlink(base *elt); \
static inline void foo##_unlink(base *elt) \
{ \
elt->foo##_next->foo##_prev = elt->foo##_prev; \
elt->foo##_prev->foo##_next = elt->foo##_next; \
elt->foo##_next = elt; \
elt->foo##_prev = elt; \
} \
\
static inline void foo##_append(foo##_ring_t *l, base *elt); \
static inline void foo##_append(foo##_ring_t *l, base *elt) \
{ \
elt->foo##_prev = l->foo##_prev; \
elt->foo##_next = foo##_sentinel(l); \
l->foo##_prev->foo##_next = elt; \
l->foo##_prev = elt; \
} \
\
static inline void foo##_prepend(foo##_ring_t *l, base *elt); \
static inline void foo##_prepend(foo##_ring_t *l, base *elt) \
{ \
elt->foo##_next = l->foo##_next; \
elt->foo##_prev = foo##_sentinel(l); \
l->foo##_next->foo##_prev = elt; \
l->foo##_next = elt; \
} \
\
static inline void foo##_insert_before(base *x, base *y); \
static inline void foo##_insert_before(base *x, base *y) \
{ \
x->foo##_prev = y->foo##_prev; \
x->foo##_next = y; \
y->foo##_prev->foo##_next = x; \
y->foo##_prev = x; \
} \
\
static inline void foo##_insert_after(base *x, base *y); \
static inline void foo##_insert_after(base *x, base *y) \
{ \
x->foo##_next = y->foo##_next; \
x->foo##_prev = y; \
y->foo##_next->foo##_prev = x; \
y->foo##_next = x; \
} \
\
static inline int foo##_is_empty(foo##_ring_t *l); \
static inline int foo##_is_empty(foo##_ring_t *l) \
{ \
return l->foo##_next == foo##_sentinel(l); \
} \
\
static inline base *foo##_dequeue(foo##_ring_t *l); \
static inline base *foo##_dequeue(foo##_ring_t *l) \
{ \
base *elt; \
\
elt = l->foo##_next; \
foo##_unlink(elt); \
return elt; \
} \
\
/* caller must ensure x and y are not sentinels */ \
/* x == y works perfectly fine */ \
static inline void foo##_splice_after(base *z, base *x, base *y); \
static inline void foo##_splice_after(base *z, base *x, base *y) \
{ \
x->foo##_prev->foo##_next = y->foo##_next; \
y->foo##_next->foo##_prev = x->foo##_prev; \
x->foo##_prev = z; \
z->foo##_next->foo##_prev = y; \
y->foo##_next = z->foo##_next; \
z->foo##_next = x; \
} \
/* caller must ensure x and y are not sentinels */ \
/* x == y works perfectly fine */ \
static inline void foo##_splice_before(base *z, base *x, base *y); \
static inline void foo##_splice_before(base *z, base *x, base *y) \
{ \
y->foo##_next->foo##_prev = x->foo##_prev; \
x->foo##_prev->foo##_next = y->foo##_next; \
y->foo##_next = z; \
z->foo##_prev->foo##_next = x; \
x->foo##_prev = z->foo##_prev; \
z->foo##_prev = y; \
}
#endif