--- psort.3.orig 2010-10-07 21:34:52.000000000 -0700 +++ psort.3 2010-10-07 21:45:11.000000000 -0700 @@ -32,60 +32,20 @@ .\" @(#)qsort.3 8.1 (Berkeley) 6/4/93 .\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.17 2007/01/09 00:28:10 imp Exp $ .\" -.Dd September 30, 2003 -.Dt QSORT 3 -.Os +.Dd Nov 25, 2008 +.Dt PSORT 3 +.Os "Mac OS X" .Sh NAME -.Nm heapsort , +.Nm psort , #ifdef UNIFDEF_BLOCKS -.Nm heapsort_b , +.Nm psort_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 +.Nm psort_r +.Nd parallel sort functions .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 -.Fo qsort +.Fo psort .Fa "void *base" .Fa "size_t nel" .Fa "size_t width" @@ -93,7 +53,7 @@ .Fc #ifdef UNIFDEF_BLOCKS .Ft void -.Fo qsort_b +.Fo psort_b .Fa "void *base" .Fa "size_t nel" .Fa "size_t width" @@ -101,7 +61,7 @@ .Fc #endif .Ft void -.Fo qsort_r +.Fo psort_r .Fa "void *base" .Fa "size_t nel" .Fa "size_t width" @@ -110,210 +70,63 @@ .Fc .Sh DESCRIPTION The -.Fn qsort -function is a modified partition-exchange sort, or quicksort. -The -.Fn heapsort -function is a modified selection sort. -The -.Fn mergesort -function is a modified merge sort with exponential search, -intended for sorting data with pre-existing order. -.Pp -The -.Fn qsort -and -.Fn heapsort -functions sort an array of -.Fa nel -objects, the initial member of which is pointed to by -.Fa base . -The size of each object is specified by -.Fa width . -The -.Fn mergesort -function -behaves similarly, but -.Em requires -that -.Fa width -be greater than or equal to -.Dq "sizeof(void *) / 2" . -.Pp -The contents of the array -.Fa base -are sorted in ascending order according to -a comparison function pointed to by -.Fa compar , -which requires two arguments pointing to the objects being -compared. -.Pp -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 -.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 -.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 -.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 -advantage over -.Fn qsort -is that it uses almost no additional memory; while -.Fn qsort -does not allocate memory, it is implemented using recursion. -.Pp -The function -.Fn mergesort -requires additional memory of size -.Fa nel * -.Fa width -bytes; it should be used only when space is not at a premium. -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 -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. +.Fn psort , +.Fn psort_b , +#else +.Fn psort #endif +and +.Fn psort_r +functions are parallel sort routines that are drop-in compatible with the +corresponding +.Fn qsort +function (see +.Xr qsort 3 +for a description of the arguments). +On multiprocessor machines, multiple threads may be created to simultaneously +perform the sort calculations, resulting in an overall faster sort result. +Overhead in managing the threads limits the maximum speed improvement to +somewhat less that the number of processors available. +For example, on a 4-processor machine, a typical sort on a large array might +result in 3.2 times faster sorting than a regular +.Fn qsort . +.Sh RESTRICTIONS +Because of the multi-threaded nature of the sort, the comparison function +is expected to perform its own synchronization that might be required for +data physically +.Em outside +the two objects passed to the comparison function. +However, no synchronization is required for the two +object themselves, unless some third party is also accessing those objects. +.Pp +Additional memory is temporary allocated to deal with the parallel nature +of the computation. +.Pp +Because of the overhead of maintaining multiple threads, the +.Fn psort +family of routines may choose to just call +.Xr qsort 3 +when there is no advantage to parallelizing (for example, when the number of +objects in the array is too small, or only one processor is available). +.Pp +Like +.Xr qsort 3 , +the sort is not stable. .Sh RETURN VALUES The #ifdef UNIFDEF_BLOCKS -.Fn qsort , -.Fn qsort_b +.Fn psort , +.Fn psort_b #else -.Fn qsort +.Fn psort #endif and -.Fn qsort_r +.Fn psort_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 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 -#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 width -argument is zero, or, -the -.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 -The -#ifdef UNIFDEF_BLOCKS -.Fn heapsort , -.Fn heapsort_b , -.Fn mergesort , -or -.Fn mergesort_b -#else -.Fn heapsort -or -.Fn mergesort -#endif -functions -were unable to allocate memory. -.El +.Sh SEE ALSO +.Xr qsort 3 .Sh SEE ALSO .Xr sort 1 , .Xr radixsort 3