- Remove the old insque() and remque() functions and their manual

   page from the compatibility library.
 - Add new implementations of insque() and remque() which conform to
   IEEE Std 1003.1-2001 to libc.  Add a new manual page for them and
   connect them to the build.
 - Add the prototypes of insque() and remque() to the search.h
   header.

9 files changed, 152 insertions, 216 deletions

diff --git a/include/search.h b/include/search.h
index a62f772..566aac8 100644
--- a/include/search.h
+++ b/include/search.h
@@ -38,21 +38,25 @@ typedef	struct node {
 	char         *key;
 	struct node  *llink, *rlink;
 } node_t;
+
+struct que_elem {
+	struct que_elem *next;
+	struct que_elem *prev;
+};
 #endif
 
 __BEGIN_DECLS
 int	 hcreate(size_t);
 void	 hdestroy(void);
 ENTRY	*hsearch(ENTRY, ACTION);
+void	 insque(void *, void *);
+void	 remque(void *);
 void	*tdelete(const void * __restrict, void ** __restrict,
 	    int (*)(const void *, const void *));
 void	*tfind(const void *, void * const *,
 	    int (*)(const void *, const void *));
 void	*tsearch(const void *, void **, int (*)(const void *, const void *));
 void	 twalk(const void *, void (*)(const void *, VISIT, int));
-/*
- * XXX missing insque(), lsearch(), remque().
- */
 __END_DECLS
 
 #endif /* !_SEARCH_H_ */
diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc
index a65ef1e..b04c2da 100644
--- a/lib/libc/stdlib/Makefile.inc
+++ b/lib/libc/stdlib/Makefile.inc
@@ -6,12 +6,12 @@
 
 MISRCS+=_Exit.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \
 	bsearch.c calloc.c div.c exit.c getenv.c getopt.c getopt_long.c \
-	getsubopt.c hcreate.c heapsort.c imaxabs.c imaxdiv.c \
+	getsubopt.c hcreate.c heapsort.c imaxabs.c imaxdiv.c insque.c \
 	labs.c ldiv.c llabs.c lldiv.c malloc.c merge.c putenv.c \
 	qsort.c qsort_r.c radixsort.c rand.c random.c reallocf.c realpath.c \
-	setenv.c strfmon.c strhash.c strtod.c strtoimax.c strtol.c strtoll.c \
-	strtoq.c strtoul.c strtoull.c strtoumax.c strtouq.c system.c \
-	tdelete.c tfind.c tsearch.c twalk.c
+	remque.c setenv.c strfmon.c strhash.c strtod.c strtoimax.c strtol.c \
+	strtoll.c strtoq.c strtoul.c strtoull.c strtoumax.c strtouq.c \
+	system.c tdelete.c tfind.c tsearch.c twalk.c
 
 # machine-dependent stdlib sources
 .if exists(${.CURDIR}/../libc/${MACHINE_ARCH}/stdlib/Makefile.inc)
@@ -21,7 +21,7 @@ MISRCS+=_Exit.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \
 .if ${LIB} == "c"
 MAN+=	abort.3 abs.3 alloca.3 atexit.3 atof.3 atoi.3 atol.3 bsearch.3 \
 	div.3 exit.3 getenv.3 getopt.3 getopt_long.3 getsubopt.3 hcreate.3 \
-	imaxabs.3 imaxdiv.3 labs.3 ldiv.3 llabs.3 lldiv.3 \
+	imaxabs.3 imaxdiv.3 insque.3 labs.3 ldiv.3 llabs.3 lldiv.3 \
 	malloc.3 memory.3 qsort.3 radixsort.3 rand.3 random.3 \
 	realpath.3 strfmon.3 strtod.3 strtol.3 strtoul.3 system.3 tsearch.3
 
@@ -29,6 +29,7 @@ MLINKS+=atol.3 atoll.3
 MLINKS+=exit.3 _Exit.3
 MLINKS+=getenv.3 putenv.3 getenv.3 setenv.3 getenv.3 unsetenv.3
 MLINKS+=hcreate.3 hdestroy.3 hcreate.3 hsearch.3
+MLINKS+=insque.3 remque.3
 MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 qsort.3 qsort_r.3
 MLINKS+=rand.3 rand_r.3 rand.3 srand.3 rand.3 sranddev.3
 MLINKS+=random.3 initstate.3 random.3 setstate.3 random.3 srandom.3 \
diff --git a/lib/libc/stdlib/insque.3 b/lib/libc/stdlib/insque.3
new file mode 100644
index 0000000..7df48f0
--- /dev/null
+++ b/lib/libc/stdlib/insque.3
@@ -0,0 +1,59 @@
+.\"
+.\" Initial implementation:
+.\" Copyright (c) 2002 Robert Drehmel
+.\" All rights reserved.
+.\"
+.\" As long as the above copyright statement and this notice remain
+.\" unchanged, you can do what ever you want with this file. 
+.\"
+.\" $FreeBSD$
+.\"
+.Dd October 10, 2002
+.Dt INSQUE 3
+.Os
+.Sh NAME
+.Nm insque ,
+.Nm remque
+.Nd doubly-linked list management
+.Sh LIBRARY
+.Lb libc
+.Sh SYNOPSIS
+.In search.h
+.Ft void
+.Fn insque "void *element1" "void *pred"
+.Ft void
+.Fn remque "void *element"
+.Sh DESCRIPTION
+.Pp
+The
+.Fn insque
+and
+.Fn remque
+functions encapsulate the ever-repeating task of doing insertion and
+removal operations on doubly linked lists.  The functions expect their
+arguments to point to a structure whose first and second members are
+pointers to the next and previous element, respectively.
+The
+.Fn insque
+functions also allows the
+.Fa pred
+argument to be a NULL pointer for the initialization of a new list's
+head element.
+.Sh HISTORY
+The
+.Fn insque
+and
+.Fn remque
+functions appeared in
+.Bx 4.2 .
+In
+.Fx 5.0 ,
+they reappeared conforming to
+.St -p1003.1-2001 .
+.Sh STANDARDS
+The
+.Fn insque
+and
+.Fn remque
+functions conform to
+.St -p1003.1-2001 .
diff --git a/lib/libc/stdlib/insque.c b/lib/libc/stdlib/insque.c
new file mode 100644
index 0000000..08d179a
--- /dev/null
+++ b/lib/libc/stdlib/insque.c
@@ -0,0 +1,48 @@
+/*
+ * Initial implementation:
+ * Copyright (c) 2002 Robert Drehmel
+ * All rights reserved.
+ *
+ * As long as the above copyright statement and this notice remain
+ * unchanged, you can do what ever you want with this file. 
+ *
+ * $FreeBSD$
+ */
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#define	_SEARCH_PRIVATE
+#include <search.h>
+#ifdef DEBUG
+#include <stdio.h>
+#else
+#include <stdlib.h>	/* for NULL */
+#endif
+
+void insque(void *element, void *pred)
+{
+	struct que_elem *prev, *next, *elem;
+
+	elem = (struct que_elem *)element;
+	prev = (struct que_elem *)pred;
+
+	if (prev == NULL) {
+		elem->prev = elem->next = NULL;
+		return;
+	}
+
+	next = prev->next;
+	if (next != NULL) {
+#ifdef DEBUG
+		if (next->prev != prev) {
+			fprintf(stderr, "insque: Inconsistency detected:"
+			    " next(%p)->prev(%p) != prev(%p)\n",
+			    next, next->prev, prev);
+		}
+#endif
+		next->prev = elem;
+	}
+	prev->next = elem;
+	elem->prev = prev;
+	elem->next = next;
+}
diff --git a/lib/libc/stdlib/remque.c b/lib/libc/stdlib/remque.c
new file mode 100644
index 0000000..2341188
--- /dev/null
+++ b/lib/libc/stdlib/remque.c
@@ -0,0 +1,31 @@
+/*
+ * Initial implementation:
+ * Copyright (c) 2002 Robert Drehmel
+ * All rights reserved.
+ *
+ * As long as the above copyright statement and this notice remain
+ * unchanged, you can do what ever you want with this file. 
+ *
+ * $FreeBSD$
+ */
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#define	_SEARCH_PRIVATE
+#include <search.h>
+#include <stdlib.h>	/* for NULL */
+
+void remque(void *element)
+{
+	struct que_elem *prev, *next, *elem;
+
+	elem = (struct que_elem *)element;
+
+	prev = elem->prev;
+	next = elem->next;
+
+	if (prev != NULL)
+		prev->next = next;
+	if (next != NULL)
+		next->prev = prev;
+}
diff --git a/lib/libcompat/4.3/insque.3 b/lib/libcompat/4.3/insque.3
deleted file mode 100644
index 2744dae..0000000
--- a/lib/libcompat/4.3/insque.3
+++ /dev/null
@@ -1,89 +0,0 @@
-.\" Copyright (c) 1983, 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.
-.\"
-.\"     @(#)insque.3	8.2 (Berkeley) 12/11/93
-.\" $FreeBSD$
-.\"
-.Dd December 11, 1993
-.Dt INSQUE 3
-.Os
-.Sh NAME
-.Nm insque ,
-.Nm remque
-.Nd insert/remove element from a queue
-.Sh LIBRARY
-.Lb libcompat
-.Sh SYNOPSIS
-.Bd -literal
-struct qelem {
-	struct	qelem *q_forw;
-	struct	qelem *q_back;
-	char	q_data[];
-};
-.Ed
-.Pp
-.Ft void
-.Fn insque "struct qelem *elem" "struct qelem *pred"
-.Ft void
-.Fn remque "struct qelem *elem"
-.Sh DESCRIPTION
-.Bf -symbolic
-The insque and remque functions are considered obsolete.
-.Ef
-.Pp
-The
-.Fn insque
-and
-.Fn remque
-functions
-manipulate queues built from doubly linked lists.  Each
-element in the queue must be in the form of
-.Dq Li struct qelem .
-The function
-.Fn insque
-inserts
-.Fa elem
-in a queue immediately after
-.Fa pred ;
-.Fn remque
-removes an entry
-.Fa elem
-from a queue.
-.Sh SEE ALSO
-.%T "VAX Architecture Handbook" ,
-pp. 228-235.
-.Sh HISTORY
-The
-.Fn insque
-and
-.Fn remque
-functions appeared in
-.Bx 4.2 .
diff --git a/lib/libcompat/4.3/insque.c b/lib/libcompat/4.3/insque.c
deleted file mode 100644
index d290860..0000000
--- a/lib/libcompat/4.3/insque.c
+++ /dev/null
@@ -1,59 +0,0 @@
-/*
- * Copyright (c) 1987, 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.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)insque.c	8.1 (Berkeley) 6/4/93";
-#endif /* LIBC_SCCS and not lint */
-#include <sys/cdefs.h>
-__FBSDID("$FreeBSD$");
-
-/*
- * insque -- vax insque instruction
- *
- * NOTE: this implementation is non-atomic!!
- */
-
-struct vaxque {		/* queue format expected by VAX queue instructions */
-	struct vaxque	*vq_next;
-	struct vaxque	*vq_prev;
-};
-
-void
-insque(e, prev)
-	struct vaxque *e, *prev;
-{
-	e->vq_prev = prev;
-	e->vq_next = prev->vq_next;
-	prev->vq_next->vq_prev = e;
-	prev->vq_next = e;
-}
diff --git a/lib/libcompat/4.3/remque.c b/lib/libcompat/4.3/remque.c
deleted file mode 100644
index b57046c..0000000
--- a/lib/libcompat/4.3/remque.c
+++ /dev/null
@@ -1,57 +0,0 @@
-/*
- * Copyright (c) 1987, 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.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)remque.c	8.1 (Berkeley) 6/4/93";
-#endif /* LIBC_SCCS and not lint */
-#include <sys/cdefs.h>
-__FBSDID("$FreeBSD$");
-
-/*
- * remque -- vax remque instruction
- *
- * NOTE: this implementation is non-atomic!!
- */
-
-struct vaxque {		/* queue format expected by VAX queue instructions */
-	struct vaxque	*vq_next;
-	struct vaxque	*vq_prev;
-};
-
-void
-remque(e)
-	struct vaxque *e;
-{
-	e->vq_prev->vq_next = e->vq_next;
-	e->vq_next->vq_prev = e->vq_prev;
-}
diff --git a/lib/libcompat/Makefile b/lib/libcompat/Makefile
index 668f7b6..bd1dd9e 100644
--- a/lib/libcompat/Makefile
+++ b/lib/libcompat/Makefile
@@ -24,14 +24,12 @@ MLINKS+=cftime.3 ascftime.3
 # compat 4.3 sources
 # XXX MISSING:	ecvt.c gcvt.c sibuf.c sobuf.c strout.c
 SRCS+=	cfree.c lsearch.c regex.c rexec.c
-SRCS+=	insque.c remque.c
 
 # XXX MISSING:	ecvt.0
-MAN+=	4.3/cfree.3 4.3/insque.3 4.3/lsearch.3 4.3/re_comp.3 4.3/rexec.3
+MAN+=	4.3/cfree.3 4.3/lsearch.3 4.3/re_comp.3 4.3/rexec.3
 
 # XXX MISSING:	ecvt.3, so can't MLINK
 #MLINKS+=ecvt.3 fcvt.3 ecvt.3 gcvt.3
-MLINKS+=insque.3 remque.3
 MLINKS+=re_comp.3 re_exec.3
 MLINKS+=lsearch.3 lfind.3