>Number:         4126
>Category:       lib
>Synopsis:       queue(3) doesn't document SIMPLEQ_*
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    lib-bug-people (Library Bug People)
>State:          open
>Class:          doc-bug
>Submitter-Id:   lm
>Arrival-Date:   Sat Sep 20 08:50:01 1997
>Last-Modified:
>Originator:     Luke Mewburn
>Organization:
NetBSD Foundation
>Release:        whenever
>Environment:
System: NetBSD karybdis 1.2G NetBSD 1.2G (LUKEM) #7: Sun Aug 17 14:04:56 EST 1997 lukem@karybdis:/z/src/current/src/sys/arch/i386/compile/LUKEM i386

>Description:
	the queue(3) manpage doesn't document the SIMPLEQ_* macros
	that are defined in <sys/queue.h>

	mycroft mentioned a while ago that maybe we should deprecate
	this stuff and just change the code using it to use the other
	queue(3) stuff (/sys/arch/vax/* and /sys/dev/ic/aic* are the
	only things using it currently), rather than `support' SIMPLEQ
	by documented.

	imho, we either convert the stuff away from SIMPLEQ, or
	decide that the macros should stay. that's why i've submitted
	this PR (rather than just change the man page, which is what
	I'd do in normal circumstances). someone High up wanna make
	a decision?

>How-To-Repeat:
	man 3 queue... look for SIMPLEQ instructions

>Fix:
	if SIMPLEQ_* is to stay, apply this patch:

Index: Makefile
===================================================================
RCS file: /cvsroot/src/share/man/man3/Makefile,v
retrieving revision 1.12
diff -u -r1.12 Makefile
--- Makefile	1997/06/24 06:00:06	1.12
+++ Makefile	1997/07/02 06:21:16
@@ -5,15 +5,18 @@
 MLINKS+=end.3 edata.3 end.3 etext.3
 MLINKS+=queue.3 list_entry.3 queue.3 list_head.3 queue.3 list_init.3
 MLINKS+=queue.3 list_insert_after.3 queue.3 list_insert_before.3
-MLINKS+=queue.3 list_insert_head.3
-MLINKS+=queue.3 list_remove.3 queue.3 tailq_entry.3 queue.3 tailq_head.3
-MLINKS+=queue.3 tailq_init.3 queue.3 tailq_insert_after.3
-MLINKS+=queue.3 tailq_insert_before.3
+MLINKS+=queue.3 list_insert_head.3 queue.3 list_remove.3
+MLINKS+=queue.3 simpleq_entry.3 queue.3 simpleq_head.3 queue.3 simpleq_init.3
+MLINKS+=queue.3 simpleq_insert_head.3 queue.3 simpleq_insert_tail.3
+MLINKS+=queue.3 simpleq_insert_after.3 queue.3 simpleq_remove_head.3
+MLINKS+=queue.3 tailq_entry.3 queue.3 tailq_head.3 queue.3 tailq_init.3
+MLINKS+=queue.3 tailq_insert_after.3 queue.3 tailq_insert_before.3
 MLINKS+=queue.3 tailq_insert_head.3 queue.3 tailq_insert_tail.3
-MLINKS+=queue.3 tailq_remove.3 queue.3 circleq_entry.3 queue.3 circleq_head.3
-MLINKS+=queue.3 circleq_init.3 queue.3 circleq_insert_after.3
-MLINKS+=queue.3 circleq_insert_before.3 queue.3 circleq_insert_head.3
-MLINKS+=queue.3 circleq_insert_tail.3 queue.3 circleq_remove.3
+MLINKS+=queue.3 tailq_remove.3
+MLINKS+=queue.3 circleq_entry.3 queue.3 circleq_head.3 queue.3 circleq_init.3
+MLINKS+=queue.3 circleq_insert_after.3 queue.3 circleq_insert_before.3
+MLINKS+=queue.3 circleq_insert_head.3 queue.3 circleq_insert_tail.3
+MLINKS+=queue.3 circleq_remove.3
 MLINKS+=stdarg.3 varargs.3 stdarg.3 va_arg.3 stdarg.3 va_end.3
 MLINKS+=stdarg.3 va_start.3
 MLINKS+=dlfcn.3 dlopen.3 dlfcn.3 dlclose.3 dlfcn.3 dlsym.3 dlfcn.3 dlctl.3 \
Index: queue.3
===================================================================
RCS file: /cvsroot/src/share/man/man3/queue.3,v
retrieving revision 1.6
diff -u -r1.6 queue.3
--- queue.3	1997/05/29 01:48:39	1.6
+++ queue.3	1997/07/02 06:21:18
@@ -33,7 +33,7 @@
 .\"
 .\"	@(#)queue.3	8.1 (Berkeley) 12/13/93
 .\"
-.Dd December 13, 1993
+.Dd June 30, 1997
 .Dt QUEUE 3
 .Os BSD 4
 .Sh NAME
@@ -45,6 +45,14 @@
 .Nm LIST_INSERT_BEFORE ,
 .Nm LIST_INSERT_HEAD ,
 .Nm LIST_REMOVE ,
+.Nm SIMPLEQ_ENTRY ,
+.Nm SIMPLEQ_HEAD ,
+.Nm SIMPLEQ_HEAD_INITIALIZER ,
+.Nm SIMPLEQ_INIT ,
+.Nm SIMPLEQ_INSERT_HEAD ,
+.Nm SIMPLEQ_INSERT_TAIL ,
+.Nm SIMPLEQ_INSERT_AFTER ,
+.Nm SIMPLEQ_REMOVE_HEAD ,
 .Nm TAILQ_ENTRY ,
 .Nm TAILQ_HEAD ,
 .Nm TAILQ_HEAD_INITIALIZER ,
@@ -76,6 +84,15 @@
 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
 .sp
+.Fn SIMPLEQ_ENTRY "TYPE"
+.Fn SIMPLEQ_HEAD "HEADNAME" "TYPE"
+.Fn SIMPLEQ_HEAD_INITIALIZER "head"
+.Fn SIMPLEQ_INIT "SIMPLEQ_HEAD *head"
+.Fn SIMPLEQ_INSERT_AFTER "SIMPLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
+.Fn SIMPLEQ_INSERT_HEAD "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
+.Fn SIMPLEQ_INSERT_TAIL "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
+.Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
+.sp
 .Fn TAILQ_ENTRY "TYPE"
 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
 .Fn TAILQ_HEAD_INITIALIZER "head"
@@ -96,9 +113,9 @@
 .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 four types of data structures:
+lists, simple queues, tail queues, and circular queues.
+All four structures support the following functionality:
 .Bl -enum -compact -offset indent
 .It
 Insertion of a new entry at the head of the list.
@@ -110,9 +127,26 @@
 Forward traversal through the list.
 .El
 .Pp
-Lists are the simplest of the three data structures and support
+Lists are the simplest of the four data structures and support
 only the above functionality.
 .Pp
+Simple 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
+Entries may not be added before any element in the list.
+.It
+Only the first entry in the list may be removed.
+.It
+All list insertions and removals must specify the head of the list.
+.It
+Each head entry requires two pointers rather than one.
+.El
+.Pp
 Tail queues add the following functionality:
 .Bl -enum -compact -offset indent
 .It
@@ -155,6 +189,7 @@
 is the name of a user defined structure,
 that must contain a field of type
 .Li LIST_ENTRY ,
+.Li SIMPLEQ_ENTRY ,
 .Li TAILQ_ENTRY ,
 or
 .Li CIRCLEQ_ENTRY ,
@@ -165,6 +200,7 @@
 is the name of a user defined structure that must be declared
 using the macros
 .Li LIST_HEAD ,
+.Li SIMPLEQ_HEAD ,
 .Li TAILQ_HEAD ,
 or
 .Li CIRCLEQ_HEAD .
@@ -274,6 +310,110 @@
 while (head.lh_first != NULL)		/* Delete. */
 	LIST_REMOVE(head.lh_first, entries);
 .Ed
+.Sh SIMPLE QUEUES
+A simple queue is headed by a structure defined by the
+.Nm SIMPLEQ_HEAD
+macro.
+This structure contains a pair of pointers,
+one to the first element in the simple queue and the other to
+the last element in the simple queue.
+The elements are doubly linked so that an arbitrary element can be
+removed without traversing the simple 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
+the queue.
+A
+.Fa SIMPLEQ_HEAD
+structure is declared as follows:
+.Bd -literal -offset indent
+SIMPLEQ_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 simple queue.
+A pointer to the head of the simple 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 SIMPLEQ_ENTRY
+declares a structure that connects the elements in
+the simple queue.
+.Pp
+The macro
+.Nm SIMPLEQ_HEAD_INITIALIZER
+provides a value which can be used to initialize a simple queue head at
+compile time, and is used at the point that the simple queue head
+variable is declared, like:
+.Bd -literal -offset indent
+struct HEADNAME head = SIMPLEQ_HEAD_INITIALIZER(head);
+.Ed
+.Pp
+The macro
+.Nm SIMPLEQ_INIT
+initializes the simple queue referenced by
+.Fa head .
+.Pp
+The macro
+.Nm SIMPLEQ_INSERT_HEAD
+inserts the new element
+.Fa elm
+at the head of the simple queue.
+.Pp
+The macro
+.Nm SIMPLEQ_INSERT_TAIL
+inserts the new element
+.Fa elm
+at the end of the simple queue.
+.Pp
+The macro
+.Nm SIMPLEQ_INSERT_AFTER
+inserts the new element
+.Fa elm
+after the element
+.Fa listelm .
+.Pp
+The macro
+.Nm SIMPLEQ_REMOVE_HEAD
+removes the first element from the simple queue.
+.Sh SIMPLE QUEUE EXAMPLE
+.Bd -literal
+SIMPLEQ_HEAD(simplehead, entry) head;
+struct simplehead *headp;		/* Simple queue head. */
+struct entry {
+	...
+	SIMPLEQ_ENTRY(entry) entries;	/* Simple queue. */
+	...
+} *n1, *n2, *np;
+
+SIMPLEQ_INIT(&head);			/* Initialize the queue. */
+
+n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
+SIMPLEQ_INSERT_HEAD(&head, n1, entries);
+
+n1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
+SIMPLEQ_INSERT_TAIL(&head, n1, entries);
+
+n2 = malloc(sizeof(struct entry));	/* Insert after. */
+SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries);
+
+					/* Forward traversal. */
+for (np = head.sqh_first; np != NULL; np = np->entries.sqe_next)
+	np-> ...
+					/* Delete. */
+while (head.sqh_first != NULL)
+	SIMPLEQ_REMOVE_HEAD(&head, head.sqh_first, entries);
+.Ed
 .Sh TAIL QUEUES
 A tail queue is headed by a structure defined by the
 .Nm TAILQ_HEAD
@@ -511,3 +651,7 @@
 The
 .Nm queue
 functions first appeared in 4.4BSD.
+The
+.Nm SIMPLEQ
+functions first appeared in
+.Nx 1.2 .
>Audit-Trail:
>Unformatted: