Update the queue man page for the new SLIST and STAILQ macros.

1 files changed, 331 insertions, 14 deletions

diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3
index f7636a0..85972d9 100644
--- a/share/man/man3/queue.3
+++ b/share/man/man3/queue.3
@@ -35,6 +35,21 @@
 .Dt QUEUE 3
 .Os BSD 4
 .Sh NAME
+.Nm SLIST_ENTRY ,
+.Nm SLIST_HEAD ,
+.Nm SLIST_INIT ,
+.Nm SLIST_INSERT_AFTER ,
+.Nm SLIST_INSERT_HEAD ,
+.Nm SLIST_REMOVE_HEAD ,
+.Nm SLIST_REMOVE ,
+.Nm STAILQ_ENTRY ,
+.Nm STAILQ_HEAD ,
+.Nm STAILQ_INIT ,
+.Nm STAILQ_INSERT_AFTER ,
+.Nm STAILQ_INSERT_HEAD ,
+.Nm STAILQ_INSERT_TAIL ,
+.Nm STAILQ_REMOVE_HEAD ,
+.Nm STAILQ_REMOVE ,
 .Nm LIST_ENTRY ,
 .Nm LIST_HEAD ,
 .Nm LIST_INIT ,
@@ -58,15 +73,33 @@
 .Nm CIRCLEQ_INSERT_HEAD ,
 .Nm CIRCLEQ_INSERT_TAIL ,
 .Nm CIRCLEQ_REMOVE
-.Nd implementations of lists, tail queues, and circular queues
+.Nd implementations of singly-linked lists, singly-linked tail queues,
+lists, tail queues, and circular queues
 .Sh SYNOPSIS
 .Fd #include <sys/queue.h>
 .sp
+.Fn SLIST_ENTRY "TYPE"
+.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_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
+.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
+.sp
+.Fn STAILQ_ENTRY "TYPE"
+.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_REMOVE_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
+.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
+.sp
 .Fn LIST_ENTRY "TYPE"
 .Fn LIST_HEAD "HEADNAME" "TYPE"
 .Fn LIST_INIT "LIST_HEAD *head"
-.Fn LIST_INSERT_AFTER "LIST_ENTRY *listelm" "TYPE *elm" "LIST_ENTRY NAME"
-.Fn LIST_INSERT_BEFORE "LIST_ENTRY *listelm" "TYPE *elm" "LIST_ENTRY NAME"
+.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_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
 .sp
@@ -88,24 +121,68 @@
 .Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 .Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 .Sh DESCRIPTION
-These macros define and operate on three types of data structures:
-lists, tail queues, and circular queues.
-All three structures support the following functionality:
+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
-Insertion of a new entry before any element in the list.
+O(1) removal of an entry from the head of the list.
 .It
-Removal of any entry in the list.
+O(n) removal of any entry in the list.
 .It
 Forward traversal through the list.
 .El
 .Pp
-Lists are the simplest of the three data structures and support
-only the above functionality.
+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
@@ -120,7 +197,7 @@ All list insertions and removals must specify the head of the list.
 Each head entry requires two pointers rather than one.
 .It
 Code size is about 15% greater and operations run about 20% slower
-than lists.
+than singly-linked lists.
 .El
 .Pp
 Circular queues add the following functionality:
@@ -147,6 +224,8 @@ 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
@@ -157,12 +236,249 @@ 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
+.sp
+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
+.sp
+(The names
+.Li head
+and
+.Li headp
+are user selectable.)
+.Pp
+The macro
+.Nm SLIST_ENTRY
+declares a structure that connects the elements in
+the list.
+.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_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 = head.slh_first;
+SLIST_REMOVE_HEAD(&head, entries);	/* Deletion. */
+free(n3);
+
+					/* Forward traversal. */
+for (np = head.slh_first; np != NULL; np = np->entries.sle_next)
+	np-> ...
+
+while (head.slh_first != NULL) {	/* List Deletion. */
+	n1 = head.slh_first;
+	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
+.sp
+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
+.sp
+(The names
+.Li head
+and
+.Li headp
+are user selectable.)
+.Pp
+The macro
+.Nm STAILQ_ENTRY
+declares a structure that connects the elements in
+the tail queue.
+.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_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 = head.stqh_first;
+STAILQ_REMOVE_HEAD(&head, entries);
+free(n3);
+
+					/* Forward traversal. */
+for (np = head.stqh_first; np != NULL; np = np->entries.stqe_next)
+	np-> ...
+					/* TailQ Deletion. */
+while (head.stqh_first != NULL) {
+	n1 = head.stqh_first;
+	TAILQ_REMOVE_HEAD(&head, entries);
+	free(n1);
+}
+					/* Faster TailQ Deletion. */
+n1 = head.stqh_first;
+while (n1 != NULL) {
+	n2 = n1->entries.stqe_next;
+	free(n1);
+	n1 = n2;
+}
+STAILQ_INIT(&head);
+.Ed
 .Sh LISTS
 A list is headed by a structure defined by the
 .Nm LIST_HEAD
@@ -171,8 +487,8 @@ 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 or
-at the head of 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:
@@ -284,7 +600,8 @@ 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,
-at the head of the tail queue, or at the end of the tail queue.
+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: