Libc-1439.40.11.tar.gz

[apple/libc.git] / stdlib / FreeBSD / qsort.3

diff --git a/stdlib/FreeBSD/qsort.3 b/stdlib/FreeBSD/qsort.3
index c1a17e7851a62f2ba5a4565f0cc46e7c1031dbe8..f137a8d0a1242606702da05ac7314e1ceb04498e 100644 (file)
--- a/stdlib/FreeBSD/qsort.3
+++ b/stdlib/FreeBSD/qsort.3
@@ -13,10 +13,6 @@
 .\" 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.
 .\" 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.
 .\" 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.


@@ -34,47 +30,84 @@
 .\" SUCH DAMAGE.
 .\"
 .\"     @(#)qsort.3    8.1 (Berkeley) 6/4/93
 .\" SUCH DAMAGE.
 .\"
 .\"     @(#)qsort.3    8.1 (Berkeley) 6/4/93

-.\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.13 2002/12/18 12:45:10 ru Exp $
+.\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.17 2007/01/09 00:28:10 imp Exp $

 .\"
 .\"

-.Dd September 7, 2002
+.Dd September 30, 2003

 .Dt QSORT 3
 .Os
 .Sh NAME
 .Dt QSORT 3
 .Os
 .Sh NAME

-.Nm qsort , qsort_r , 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
 .Nd sort functions

-.Sh LIBRARY
-.Lb libc

 .Sh SYNOPSIS
 .In stdlib.h
 .Sh SYNOPSIS
 .In stdlib.h

-.Ft void
-.Fo qsort
+.Ft int
+.Fo heapsort

 .Fa "void *base"
 .Fa "void *base"

-.Fa "size_t nmemb"
-.Fa "size_t size"
+.Fa "size_t nel"
+.Fa "size_t width"

 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 .Fc
 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 .Fc

-.Ft void
-.Fo qsort_r
+#ifdef UNIFDEF_BLOCKS
+.Ft int
+.Fo heapsort_b

 .Fa "void *base"
 .Fa "void *base"

-.Fa "size_t nmemb"
-.Fa "size_t size"
-.Fa "void *thunk"
-.Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]"
+.Fa "size_t nel"
+.Fa "size_t width"
+.Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"

 .Fc
 .Fc

+#endif

 .Ft int
 .Ft int

-.Fo heapsort
+.Fo mergesort

 .Fa "void *base"
 .Fa "void *base"

-.Fa "size_t nmemb"
-.Fa "size_t size"
+.Fa "size_t nel"
+.Fa "size_t width"

 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 .Fc
 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 .Fc

+#ifdef UNIFDEF_BLOCKS

 .Ft int
 .Ft int

-.Fo mergesort
+.Fo mergesort_b

 .Fa "void *base"
 .Fa "void *base"

-.Fa "size_t nmemb"
-.Fa "size_t size"
+.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
+.Fa "void *base"
+.Fa "size_t nel"
+.Fa "size_t width"

 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 .Fc
 .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
 .Sh DESCRIPTION
 The
 .Fn qsort


@@ -84,7 +117,7 @@ The
 function is a modified selection sort.
 The
 .Fn mergesort
 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
 intended for sorting data with pre-existing order.
 .Pp
 The


@@ -92,19 +125,19 @@ The
 and
 .Fn heapsort
 functions sort an array of
 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
 objects, the initial member of which is pointed to by
 .Fa base .
 The size of each object is specified by

-.Fa size .
+.Fa width .

 The
 .Fn mergesort
 function
 behaves similarly, but
 .Em requires
 that
 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
 .Dq "sizeof(void *) / 2" .
 .Pp
 The contents of the array


@@ -139,7 +172,7 @@ and
 .Fn heapsort
 are
 .Em not
 .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
 .Fn mergesort
 the sorted array is undefined.
 The
 .Fn mergesort


@@ -149,11 +182,13 @@ The
 .Fn qsort
 and
 .Fn qsort_r
 .Fn qsort
 and
 .Fn qsort_r

-functions are an implementation of C.A.R. Hoare's
+functions are an implementation of C.A.R.
+Hoare's

 .Dq quicksort
 algorithm,
 .Dq quicksort
 algorithm,

-a variant of partition-exchange sorting; in particular, see D.E. Knuth's
-Algorithm Q.
+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
 .Sy Quicksort
 takes O N lg N average time.
 This implementation uses median selection to avoid its


@@ -161,10 +196,13 @@ O N**2 worst-case behavior.
 .Pp
 The
 .Fn heapsort
 .Pp
 The
 .Fn heapsort

-function is an implementation of J.W.J. William's
+function is an implementation of
+.An "J.W.J. William" Ns 's

 .Dq heapsort
 algorithm,
 .Dq heapsort
 algorithm,

-a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
+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
 .Sy Heapsort
 takes O N lg N worst-case time.
 Its


@@ -178,8 +216,8 @@ does not allocate memory, it is implemented using recursion.
 The function
 .Fn mergesort
 requires additional memory of size
 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.
 The
 .Fn mergesort
 bytes; it should be used only when space is not at a premium.
 The
 .Fn mergesort


@@ -191,50 +229,91 @@ Normally,
 .Fn qsort
 is faster than
 .Fn mergesort
 .Fn qsort
 is faster than
 .Fn mergesort

-is faster than
+which is faster than

 .Fn heapsort .
 Memory availability and pre-existing order in the data can make this
 untrue.
 .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
 .Sh RETURN VALUES
 The

+#ifdef UNIFDEF_BLOCKS
+.Fn qsort ,
+.Fn qsort_b
+#else

 .Fn qsort
 .Fn qsort

+#endif

 and
 .Fn qsort_r
 functions
 return no value.
 .Pp
 and
 .Fn qsort_r
 functions
 return no value.
 .Pp

-.Rv -std heapsort mergesort
+#ifdef UNIFDEF_BLOCKS
+.ds HEAPSORT_B heapsort_b
+.ds MERGESORT_B mergesort_b
+#endif
+.Rv -std heapsort \*[HEAPSORT_B] mergesort \*[MERGESORT_B]
+.Sh COMPATIBILITY
+Previous versions of
+.Fn qsort
+did not permit the comparison routine itself to call
+.Fn qsort 3 .
+This is no longer true.

 .Sh ERRORS
 The
 .Sh ERRORS
 The

+#ifdef UNIFDEF_BLOCKS
+.Fn heapsort ,
+.Fn heapsort_b ,
+.Fn mergesort ,
+and
+.Fn mergesort_b
+#else

 .Fn heapsort
 and
 .Fn mergesort
 .Fn heapsort
 and
 .Fn mergesort

+#endif

 functions succeed unless:
 .Bl -tag -width Er
 .It Bq Er EINVAL
 The
 functions succeed unless:
 .Bl -tag -width Er
 .It Bq Er EINVAL
 The

-.Fa size
+.Fa width

 argument is zero, or,
 the
 argument is zero, or,
 the

-.Fa size
+.Fa width

 argument to
 .Fn mergesort
 argument to
 .Fn mergesort

+#ifdef UNIFDEF_BLOCKS
+or
+.Fn mergesort_b
+#endif

 is less than
 .Dq "sizeof(void *) / 2" .
 .It Bq Er ENOMEM
 The
 is less than
 .Dq "sizeof(void *) / 2" .
 .It Bq Er ENOMEM
 The

+#ifdef UNIFDEF_BLOCKS
+.Fn heapsort ,
+.Fn heapsort_b ,
+.Fn mergesort ,
+or
+.Fn mergesort_b
+#else

 .Fn heapsort
 or
 .Fn mergesort
 .Fn heapsort
 or
 .Fn mergesort

+#endif

 functions
 were unable to allocate memory.
 .El
 functions
 were unable to allocate memory.
 .El

-.Sh COMPATIBILITY
-Previous versions of
-.Fn qsort
-did not permit the comparison routine itself to call
-.Fn qsort 3 .
-This is no longer true.

 .Sh SEE ALSO
 .Xr sort 1 ,
 .Xr radixsort 3
 .Sh SEE ALSO
 .Xr sort 1 ,
 .Xr radixsort 3


@@ -263,16 +342,19 @@ This is no longer true.
 .%P pp. 114-123, 145-149
 .Re
 .Rs
 .%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.
 .%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"
 .%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
 .Re
 .Sh STANDARDS
 The