--- psort.3.orig 2009-05-20 15:59:00.000000000 -0700 +++ psort.3 2009-05-20 16:08:34.000000000 -0700 @@ -36,60 +36,20 @@ .\" @(#)qsort.3 8.1 (Berkeley) 6/4/93 .\" $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 +.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" @@ -97,7 +57,7 @@ .Fc #ifdef UNIFDEF_BLOCKS .Ft void -.Fo qsort_b +.Fo psort_b .Fa "void *base" .Fa "size_t nel" .Fa "size_t width" @@ -105,7 +65,7 @@ .Fc #endif .Ft void -.Fo qsort_r +.Fo psort_r .Fa "void *base" .Fa "size_t nel" .Fa "size_t width" @@ -114,255 +74,60 @@ .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. -#endif -.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 -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 +.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 heapsort , -.Fn heapsort_b , -.Fn mergesort -and -.Fn mergesort_b +.Fn psort , +.Fn psort_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 +.Fn psort #endif -is less than -.Dq "sizeof(void *) / 2" . -.It Bq Er ENOMEM -The -#ifdef UNIFDEF_BLOCKS -.Fn heapsort , -.Fn heapsort_b , -.Fn mergesort -and -.Fn mergesort_b -#else -.Fn heapsort and -.Fn mergesort -#endif +.Fn psort_r 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. +return no value. .Sh SEE ALSO -.Xr sort 1 , -.Xr radixsort 3 -.Rs -.%A Hoare, C.A.R. -.%D 1962 -.%T "Quicksort" -.%J "The Computer Journal" -.%V 5:1 -.%P pp. 10-15 -.Re -.Rs -.%A Williams, J.W.J -.%D 1964 -.%T "Heapsort" -.%J "Communications of the ACM" -.%V 7:1 -.%P pp. 347-348 -.Re -.Rs -.%A Knuth, D.E. -.%D 1968 -.%B "The Art of Computer Programming" -.%V Vol. 3 -.%T "Sorting and Searching" -.%P pp. 114-123, 145-149 -.Re -.Rs -.%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 "Software--Practice and Experience" -.%V Vol. 23(11) -.%P pp. 1249-1265 -.%D November\ 1993 -.Re -.Sh STANDARDS -The -.Fn qsort -function -conforms to -.St -isoC . +.Xr qsort 3