Implement C99's _Exit() interface.

Implement a version of qsort that provides a thunk to the comparison function.

Update manual pages.

6 files changed, 158 insertions, 55 deletions

diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc
index 19200b9d4fcb..69b206ae364b 100644
--- a/lib/libc/stdlib/Makefile.inc
+++ b/lib/libc/stdlib/Makefile.inc
@@ -4,11 +4,11 @@
 # machine-independent stdlib sources
 .PATH: ${.CURDIR}/../libc/${MACHINE_ARCH}/stdlib ${.CURDIR}/../libc/stdlib
 
-MISRCS+=abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \
+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 \
 	getsubopt.c hcreate.c heapsort.c imaxabs.c imaxdiv.c \
 	labs.c ldiv.c llabs.c lldiv.c malloc.c merge.c putenv.c \
-	qsort.c radixsort.c rand.c random.c reallocf.c realpath.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
@@ -26,9 +26,10 @@ MAN+=	abort.3 abs.3 alloca.3 atexit.3 atof.3 atoi.3 atol.3 bsearch.3 \
 	realpath.3 strfmon.3 strtod.3 strtol.3 strtoul.3 system.3 tsearch.3
 
 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+=qsort.3 heapsort.3 qsort.3 mergesort.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 \
 	random.3 srandomdev.3
diff --git a/lib/libc/stdlib/_Exit.c b/lib/libc/stdlib/_Exit.c
new file mode 100644
index 000000000000..e7f0f5104f93
--- /dev/null
+++ b/lib/libc/stdlib/_Exit.c
@@ -0,0 +1,22 @@
+/*
+ * This file is in the public domain.  Written by Garrett A. Wollman,
+ * 2002-09-07.
+ *
+ * $FreeBSD$
+ */
+
+#include <stdlib.h>
+#include <unistd.h>
+
+/*
+ * ISO C99 added this function to provide for Standard C applications
+ * which needed something like POSIX _exit().  A new interface was created
+ * in case it turned out that _exit() was insufficient to meet the
+ * requirements of ISO C.  (That's probably not the case, but here
+ * is where you would put the extra code if it were.)
+ */
+void
+_Exit(int code)
+{
+	_exit(code);
+}
diff --git a/lib/libc/stdlib/exit.3 b/lib/libc/stdlib/exit.3
index bbe0d1faee32..b5e64bd669bd 100644
--- a/lib/libc/stdlib/exit.3
+++ b/lib/libc/stdlib/exit.3
@@ -36,11 +36,11 @@
 .\"     @(#)exit.3	8.1 (Berkeley) 6/4/93
 .\" $FreeBSD$
 .\"
-.Dd September 6, 2002
+.Dd September 9, 2002
 .Dt EXIT 3
 .Os
 .Sh NAME
-.Nm exit
+.Nm exit , _Exit
 .Nd perform normal program termination
 .Sh LIBRARY
 .Lb libc
@@ -48,12 +48,18 @@
 .In stdlib.h
 .Ft void
 .Fn exit "int status"
+.Ft void
+.Fn _Exit "int status"
 .Sh DESCRIPTION
-.Fn Exit
-terminates a process.
+The
+.Fn exit
+and
+.Fn _Exit
+functions terminate a process.
 .Pp
-Before termination it performs the following functions in the
-order listed:
+Before termination,
+.Fn exit
+performs the following functions in the order listed:
 .Bl -enum -offset indent
 .It
 Call the functions registered with the
@@ -69,16 +75,31 @@ Unlink all files created with the
 function.
 .El
 .Pp
-Passing arbitrary values back to the environment as
-.Ar status
-is considered bad style;
-you should use the values
-.Dv EXIT_SUCCESS
+The
+.Fn _Exit
+function terminates without calling the functions registered with the
+.Xr atexit 3
+function, and may or may not perform the other actions listed.
+Both functions make the low-order eight bits of the
+.Fa status
+argument available to a parent process which has called a
+.Xr wait 2 Ns -family
+function.
+.Pp
+The C Standard
+.Pq St -isoC-99
+defines the values
+.Li 0 ,
+.Dv EXIT_SUCCESS ,
 and
-.Dv EXIT_FAILURE .
-If portability is not a concern, you may
-use the values described in
-.Xr sysexits 3 .
+.Dv EXIT_FAILURE
+as possible values of
+.Fa status .
+Cooperating processes may use other values;
+in a program which might be called by a mail transfer agent, the
+the values described in
+.Xr sysexits 3
+may be used to provide more information to the parent process.
 .Pp
 Note that
 .Fn exit
@@ -87,16 +108,19 @@ using
 .Xr atexit 3
 itself call
 .Fn exit .
-Such functions should call
-.Xr _exit 2
+Such functions must call
+.Fn _Exit
 instead (although this has other effects as well which may not be desired).
 .Sh RETURN VALUES
 The
 .Fn exit
-function
-never returns.
+and
+.Fn _Exit
+functions
+never return.
 .Sh SEE ALSO
 .Xr _exit 2 ,
+.Xr wait 2 ,
 .Xr atexit 3 ,
 .Xr intro 3 ,
 .Xr sysexits 3 ,
@@ -104,6 +128,7 @@ never returns.
 .Sh STANDARDS
 The
 .Fn exit
-function
-conforms to
-.St -isoC .
+and
+.Fn _Exit
+functions conform to
+.St -isoC-99 .
diff --git a/lib/libc/stdlib/qsort.3 b/lib/libc/stdlib/qsort.3
index 4675de4ecd83..39d6e0c25e1a 100644
--- a/lib/libc/stdlib/qsort.3
+++ b/lib/libc/stdlib/qsort.3
@@ -36,11 +36,11 @@
 .\"     @(#)qsort.3	8.1 (Berkeley) 6/4/93
 .\" $FreeBSD$
 .\"
-.Dd June 4, 1993
+.Dd September 7, 2002
 .Dt QSORT 3
 .Os
 .Sh NAME
-.Nm qsort , heapsort , mergesort
+.Nm qsort , qsort_r , heapsort , mergesort
 .Nd sort functions
 .Sh LIBRARY
 .Lb libc
@@ -48,6 +48,14 @@
 .In stdlib.h
 .Ft void
 .Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
+.Ft void
+.Fo qsort_r
+.Fa "void *base"
+.Fa "size_t nmemb"
+.Fa "size_t size"
+.Fa "void *thunk"
+.Fa "int (*compar)(void *, const void *, const void *)"
+.Fc
 .Ft int
 .Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
 .Ft int
@@ -94,24 +102,40 @@ The comparison function must return an integer less than, equal to, or
 greater than zero if the first argument is considered to be respectively
 less than, equal to, or greater than the second.
 .Pp
-The functions
-.Fn qsort
+The
+.Fn qsort_r
+function behaves identically to
+.Fn qsort ,
+except that it takes an additional argument,
+.Fa thunk ,
+which is passed unchanged as the first argument to function pointed to
+.Fa compar .
+This allows the comparison function to access additional
+data without using global variables, and thus 
+.Fn qsort_r
+is suitable for use in functions which must be reentrant.
+.Pp
+The algorithms implemented by
+.Fn qsort ,
+.Fn qsort_r ,
 and
 .Fn heapsort
 are
 .Em not
 stable, that is, if two members compare as equal, their order in
 the sorted array is undefined.
-The function
+The
 .Fn mergesort
-is stable.
+algorithm is stable.
 .Pp
 The
 .Fn qsort
-function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
+and
+.Fn qsort_r
+functions are an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
 a variant of partition-exchange sorting; in particular, see D.E. Knuth's
 Algorithm Q.
-.Fn Qsort
+.Sy Quicksort
 takes O N lg N average time.
 This implementation uses median selection to avoid its
 O N**2 worst-case behavior.
@@ -120,7 +144,7 @@ The
 .Fn heapsort
 function is an implementation of J.W.J. William's ``heapsort'' algorithm,
 a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
-.Fn Heapsort
+.Sy Heapsort
 takes O N lg N worst-case time.
 Its
 .Em only
@@ -151,8 +175,10 @@ untrue.
 .Sh RETURN VALUES
 The
 .Fn qsort
-function
-returns no value.
+and
+.Fn qsort_r
+functions
+return no value.
 .Pp
 .Rv -std heapsort mergesort
 .Sh ERRORS
diff --git a/lib/libc/stdlib/qsort.c b/lib/libc/stdlib/qsort.c
index 8e6cd619c25c..47e563ad703e 100644
--- a/lib/libc/stdlib/qsort.c
+++ b/lib/libc/stdlib/qsort.c
@@ -39,8 +39,12 @@ __FBSDID("$FreeBSD$");
 
 #include <stdlib.h>
 
+#ifdef I_AM_QSORT_R
+typedef int		 cmp_t(void *, const void *, const void *);
+#else
 typedef int		 cmp_t(const void *, const void *);
-static inline char	*med3(char *, char *, char *, cmp_t *);
+#endif
+static inline char	*med3(char *, char *, char *, cmp_t *, void *);
 static inline void	 swapfunc(char *, char *, int, int);
 
 #define min(a, b)	(a) < (b) ? a : b
@@ -83,21 +87,32 @@ swapfunc(a, b, n, swaptype)
 
 #define vecswap(a, b, n) 	if ((n) > 0) swapfunc(a, b, n, swaptype)
 
+#ifdef I_AM_QSORT_R
+#define	CMP(t, x, y) (cmp((t), (x), (y)))
+#else
+#define	CMP(t, x, y) (cmp((x), (y)))
+#endif
+
 static inline char *
-med3(a, b, c, cmp)
-	char *a, *b, *c;
-	cmp_t *cmp;
+med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk
+#ifndef I_AM_QSORT_R
+__unused
+#endif
+)
 {
-	return cmp(a, b) < 0 ?
-	       (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
-              :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
+	return CMP(thunk, a, b) < 0 ?
+	       (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
+              :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
 }
 
+#ifdef I_AM_QSORT_R
+void
+qsort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp)
+#else
+#define thunk NULL
 void
-qsort(a, n, es, cmp)
-	void *a;
-	size_t n, es;
-	cmp_t *cmp;
+qsort(void *a, size_t n, size_t es, cmp_t *cmp)
+#endif
 {
 	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 	int d, r, swaptype, swap_cnt;
@@ -106,7 +121,8 @@ loop:	SWAPINIT(a, es);
 	swap_cnt = 0;
 	if (n < 7) {
 		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
-			for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
+			for (pl = pm; 
+			     pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
 			     pl -= es)
 				swap(pl, pl - es);
 		return;
@@ -117,18 +133,18 @@ loop:	SWAPINIT(a, es);
 		pn = (char *)a + (n - 1) * es;
 		if (n > 40) {
 			d = (n / 8) * es;
-			pl = med3(pl, pl + d, pl + 2 * d, cmp);
-			pm = med3(pm - d, pm, pm + d, cmp);
-			pn = med3(pn - 2 * d, pn - d, pn, cmp);
+			pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
+			pm = med3(pm - d, pm, pm + d, cmp, thunk);
+			pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
 		}
-		pm = med3(pl, pm, pn, cmp);
+		pm = med3(pl, pm, pn, cmp, thunk);
 	}
 	swap(a, pm);
 	pa = pb = (char *)a + es;
 
 	pc = pd = (char *)a + (n - 1) * es;
 	for (;;) {
-		while (pb <= pc && (r = cmp(pb, a)) <= 0) {
+		while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) {
 			if (r == 0) {
 				swap_cnt = 1;
 				swap(pa, pb);
@@ -136,7 +152,7 @@ loop:	SWAPINIT(a, es);
 			}
 			pb += es;
 		}
-		while (pb <= pc && (r = cmp(pc, a)) >= 0) {
+		while (pb <= pc && (r = CMP(thunk, pc, a)) >= 0) {
 			if (r == 0) {
 				swap_cnt = 1;
 				swap(pc, pd);
@@ -153,7 +169,8 @@ loop:	SWAPINIT(a, es);
 	}
 	if (swap_cnt == 0) {  /* Switch to insertion sort */
 		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
-			for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
+			for (pl = pm; 
+			     pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
 			     pl -= es)
 				swap(pl, pl - es);
 		return;
@@ -165,7 +182,11 @@ loop:	SWAPINIT(a, es);
 	r = min(pd - pc, pn - pd - es);
 	vecswap(pb, pn - r, r);
 	if ((r = pb - pa) > es)
+#ifdef I_AM_QSORT_R
+		qsort_r(a, r / es, es, thunk, cmp);
+#else
 		qsort(a, r / es, es, cmp);
+#endif
 	if ((r = pd - pc) > es) {
 		/* Iterate rather than recurse to save stack space */
 		a = pn - r;
diff --git a/lib/libc/stdlib/qsort_r.c b/lib/libc/stdlib/qsort_r.c
new file mode 100644
index 000000000000..d86873604f59
--- /dev/null
+++ b/lib/libc/stdlib/qsort_r.c
@@ -0,0 +1,8 @@
+/*
+ * This file is in the public domain.  Originally written by Garrett
+ * A. Wollman.
+ *
+ * $FreeBSD$
+ */
+#define I_AM_QSORT_R
+#include "qsort.c"