--- Libc/Libc-262/stdlib/qsort.3
+++ Libc/Libc-594.9.5/stdlib/qsort.3
@@ -34,24 +34,84 @@
 .\" SUCH DAMAGE.
 .\"
 .\"     @(#)qsort.3	8.1 (Berkeley) 6/4/93
-.\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.10 2001/09/07 14:46:35 asmodai Exp $
-.\"
-.Dd June 4, 1993
+.\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.15 2004/07/02 23:52:12 ru Exp $
+.\"
+.Dd September 30, 2003
 .Dt QSORT 3
 .Os
 .Sh NAME
-.Nm qsort , heapsort , mergesort
+.Nm heapsort ,
+#ifdef UNIFDEF_BLOCKS
+.Nm heapsort_b ,
+#endif
+.Nm mergesort ,
+#ifdef UNIFDEF_BLOCKS
+.Nm mergesort_b ,
+#endif
+.Nm qsort ,
+#ifdef UNIFDEF_BLOCKS
+.Nm qsort_b ,
+#endif
+.Nm qsort_r
 .Nd sort functions
-.Sh LIBRARY
-.Lb libc
 .Sh SYNOPSIS
 .In stdlib.h
+.Ft int
+.Fo heapsort
+.Fa "void *base"
+.Fa "size_t nel"
+.Fa "size_t width"
+.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
+.Fc
+#ifdef UNIFDEF_BLOCKS
+.Ft int
+.Fo heapsort_b
+.Fa "void *base"
+.Fa "size_t nel"
+.Fa "size_t width"
+.Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
+.Fc
+#endif
+.Ft int
+.Fo mergesort
+.Fa "void *base"
+.Fa "size_t nel"
+.Fa "size_t width"
+.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
+.Fc
+#ifdef UNIFDEF_BLOCKS
+.Ft int
+.Fo mergesort_b
+.Fa "void *base"
+.Fa "size_t nel"
+.Fa "size_t width"
+.Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
+.Fc
+#endif
 .Ft void
-.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
-.Ft int
-.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
-.Ft int
-.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
+.Fo qsort
+.Fa "void *base"
+.Fa "size_t nel"
+.Fa "size_t width"
+.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
+.Fc
+#ifdef UNIFDEF_BLOCKS
+.Ft void
+.Fo qsort_b
+.Fa "void *base"
+.Fa "size_t nel"
+.Fa "size_t width"
+.Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
+.Fc
+#endif
+.Ft void
+.Fo qsort_r
+.Fa "void *base"
+.Fa "size_t nel"
+.Fa "size_t width"
+.Fa "void *thunk"
+.Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]"
+.Fc
 .Sh DESCRIPTION
 The
 .Fn qsort
@@ -61,7 +121,7 @@
 function is a modified selection sort.
 The
 .Fn mergesort
-function is a modified merge sort with exponential search
+function is a modified merge sort with exponential search,
 intended for sorting data with pre-existing order.
 .Pp
 The
@@ -69,17 +129,19 @@
 and
 .Fn heapsort
 functions sort an array of
-.Fa nmemb
+.Fa nel
 objects, the initial member of which is pointed to by
 .Fa base .
 The size of each object is specified by
-.Fa size .
-.Fn Mergesort
+.Fa width .
+The
+.Fn mergesort
+function
 behaves similarly, but
 .Em requires
 that
-.Fa size
-be greater than
+.Fa width
+be greater than or equal to
 .Dq "sizeof(void *) / 2" .
 .Pp
 The contents of the array
@@ -94,33 +156,58 @@
 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
+stable; that is, if two members compare as equal, their order in
 the sorted array is undefined.
-The function
-.Fn mergesort
-is stable.
-.Pp
-The
-.Fn qsort
-function is 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
+The
+.Fn mergesort
+algorithm is stable.
+.Pp
+The
+.Fn qsort
+and
+.Fn qsort_r
+functions are an implementation of C.A.R.
+Hoare's
+.Dq quicksort
+algorithm,
+a variant of partition-exchange sorting; in particular, see
+.An D.E. Knuth Ns 's
+.%T "Algorithm Q" .
+.Sy Quicksort
 takes O N lg N average time.
 This implementation uses median selection to avoid its
 O N**2 worst-case behavior.
 .Pp
 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
+function is an implementation of
+.An "J.W.J. William" Ns 's
+.Dq heapsort
+algorithm,
+a variant of selection sorting; in particular, see
+.An "D.E. Knuth" Ns 's
+.%T "Algorithm H" .
+.Sy Heapsort
 takes O N lg N worst-case time.
 Its
 .Em only
@@ -133,49 +220,96 @@
 The function
 .Fn mergesort
 requires additional memory of size
-.Fa nmemb *
-.Fa size
+.Fa nel *
+.Fa width
 bytes; it should be used only when space is not at a premium.
-.Fn Mergesort
+The
+.Fn mergesort
+function
 is optimized for data with pre-existing order; its worst case
 time is O N lg N; its best case is O N.
 .Pp
 Normally,
 .Fn qsort
 is faster than
-.Fn mergesort
-is faster than
+.Fn mergesort ,
+which is faster than
 .Fn heapsort .
 Memory availability and pre-existing order in the data can make this
 untrue.
+#ifdef UNIFDEF_BLOCKS
+.Pp
+The
+.Fn heapsort_b ,
+.Fn mergesort_b ,
+and
+.Fn qsort_b
+routines are like the corresponding routines without the _b suffix, expect
+that the
+.Fa compar
+callback is a block pointer instead of a function pointer.
+#endif
 .Sh RETURN VALUES
 The
-.Fn qsort
-function
-returns no value.
-.Pp
-.Rv -std heapsort mergesort
+#ifdef UNIFDEF_BLOCKS
+.Fn qsort ,
+.Fn qsort_b
+#else
+.Fn qsort
+#endif
+and
+.Fn qsort_r
+functions
+return no value.
+.Pp
+#ifdef UNIFDEF_BLOCKS
+.ds HEAPSORT_B heapsort_b
+.ds MERGESORT_B mergesort_b
+#endif
+.Rv -std heapsort \*[HEAPSORT_B] mergesort \*[MERGESORT_B]
 .Sh ERRORS
 The
-.Fn heapsort
-and
-.Fn mergesort
+#ifdef UNIFDEF_BLOCKS
+.Fn heapsort ,
+.Fn heapsort_b ,
+.Fn mergesort
+and
+.Fn mergesort_b
+#else
+.Fn heapsort
+and
+.Fn mergesort
+#endif
 functions succeed unless:
 .Bl -tag -width Er
 .It Bq Er EINVAL
 The
-.Fa size
+.Fa width
 argument is zero, or,
 the
-.Fa size
+.Fa width
 argument to
 .Fn mergesort
+#ifdef UNIFDEF_BLOCKS
+or
+.Fn mergesort_b
+#endif
 is less than
 .Dq "sizeof(void *) / 2" .
 .It Bq Er ENOMEM
-.Fn Heapsort
-or
-.Fn mergesort
+The
+#ifdef UNIFDEF_BLOCKS
+.Fn heapsort ,
+.Fn heapsort_b ,
+.Fn mergesort
+and
+.Fn mergesort_b
+#else
+.Fn heapsort
+and
+.Fn mergesort
+#endif
+functions
 were unable to allocate memory.
 .El
 .Sh COMPATIBILITY
@@ -212,16 +346,19 @@
 .%P pp. 114-123, 145-149
 .Re
 .Rs
-.%A Mcilroy, P.M.
+.%A McIlroy, P.M.
 .%T "Optimistic Sorting and Information Theoretic Complexity"
 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 .%V January 1992
 .Re
 .Rs
 .%A Bentley, J.L.
+.%A McIlroy, M.D.
 .%T "Engineering a Sort Function"
-.%J "bentley@research.att.com"
-.%V January 1992
+.%J "Software--Practice and Experience"
+.%V Vol. 23(11)
+.%P pp. 1249-1265
+.%D November\ 1993
 .Re
 .Sh STANDARDS
 The