git.saurik.com Git - apple/libc.git/blame_incremental

... / ...

Commit	Line	Data
	1	.\" Copyright (c) 1990, 1991, 1993
	2	.\" The Regents of the University of California. All rights reserved.
	3	.\"
	4	.\" This code is derived from software contributed to Berkeley by
	5	.\" the American National Standards Committee X3, on Information
	6	.\" Processing Systems.
	7	.\"
	8	.\" Redistribution and use in source and binary forms, with or without
	9	.\" modification, are permitted provided that the following conditions
	10	.\" are met:
	11	.\" 1. Redistributions of source code must retain the above copyright
	12	.\" notice, this list of conditions and the following disclaimer.
	13	.\" 2. Redistributions in binary form must reproduce the above copyright
	14	.\" notice, this list of conditions and the following disclaimer in the
	15	.\" documentation and/or other materials provided with the distribution.
	16	.\" 4. Neither the name of the University nor the names of its contributors
	17	.\" may be used to endorse or promote products derived from this software
	18	.\" without specific prior written permission.
	19	.\"
	20	.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	21	.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	22	.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	23	.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	24	.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	25	.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	26	.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	27	.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	28	.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	29	.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	30	.\" SUCH DAMAGE.
	31	.\"
	32	.\" @(#)qsort.3 8.1 (Berkeley) 6/4/93
	33	.\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.17 2007/01/09 00:28:10 imp Exp $
	34	.\"
	35	.Dd Nov 25, 2008
	36	.Dt PSORT 3
	37	.Os "Mac OS X"
	38	.Sh NAME
	39	.Nm psort ,
	40	#ifdef UNIFDEF_BLOCKS
	41	.Nm psort_b ,
	42	#endif
	43	.Nm psort_r
	44	.Nd parallel sort functions
	45	.Sh SYNOPSIS
	46	.In stdlib.h
	47	.Ft void
	48	.Fo psort
	49	.Fa "void *base"
	50	.Fa "size_t nel"
	51	.Fa "size_t width"
	52	.Fa "int \[lp]compar\[rp]\[lp]const void , const void \*[rp]"
	53	.Fc
	54	#ifdef UNIFDEF_BLOCKS
	55	.Ft void
	56	.Fo psort_b
	57	.Fa "void *base"
	58	.Fa "size_t nel"
	59	.Fa "size_t width"
	60	.Fa "int \[lp]^compar\[rp]\[lp]const void , const void \[rp]"
	61	.Fc
	62	#endif
	63	.Ft void
	64	.Fo psort_r
	65	.Fa "void *base"
	66	.Fa "size_t nel"
	67	.Fa "size_t width"
	68	.Fa "void *thunk"
	69	.Fa "int \[lp]compar\[rp]\[lp]void , const void , const void \[rp]"
	70	.Fc
	71	.Sh DESCRIPTION
	72	The
	73	#ifdef UNIFDEF_BLOCKS
	74	.Fn psort ,
	75	.Fn psort_b ,
	76	#else
	77	.Fn psort
	78	#endif
	79	and
	80	.Fn psort_r
	81	functions are parallel sort routines that are drop-in compatible with the
	82	corresponding
	83	.Fn qsort
	84	function (see
	85	.Xr qsort 3
	86	for a description of the arguments).
	87	On multiprocessor machines, multiple threads may be created to simultaneously
	88	perform the sort calculations, resulting in an overall faster sort result.
	89	Overhead in managing the threads limits the maximum speed improvement to
	90	somewhat less that the number of processors available.
	91	For example, on a 4-processor machine, a typical sort on a large array might
	92	result in 3.2 times faster sorting than a regular
	93	.Fn qsort .
	94	.Sh RESTRICTIONS
	95	Because of the multi-threaded nature of the sort, the comparison function
	96	is expected to perform its own synchronization that might be required for
	97	data physically
	98	.Em outside
	99	the two objects passed to the comparison function.
	100	However, no synchronization is required for the two
	101	object themselves, unless some third party is also accessing those objects.
	102	.Pp
	103	Additional memory is temporary allocated to deal with the parallel nature
	104	of the computation.
	105	.Pp
	106	Because of the overhead of maintaining multiple threads, the
	107	.Fn psort
	108	family of routines may choose to just call
	109	.Xr qsort 3
	110	when there is no advantage to parallelizing (for example, when the number of
	111	objects in the array is too small, or only one processor is available).
	112	.Pp
	113	Like
	114	.Xr qsort 3 ,
	115	the sort is not stable.
	116	.Sh RETURN VALUES
	117	The
	118	#ifdef UNIFDEF_BLOCKS
	119	.Fn psort ,
	120	.Fn psort_b
	121	#else
	122	.Fn psort
	123	#endif
	124	and
	125	.Fn psort_r
	126	functions
	127	return no value.
	128	.Sh SEE ALSO
	129	.Xr qsort 3
	130	.Sh SEE ALSO
	131	.Xr sort 1 ,
	132	.Xr radixsort 3
	133	.Rs
	134	.%A Hoare, C.A.R.
	135	.%D 1962
	136	.%T "Quicksort"
	137	.%J "The Computer Journal"
	138	.%V 5:1
	139	.%P pp. 10-15
	140	.Re
	141	.Rs
	142	.%A Williams, J.W.J
	143	.%D 1964
	144	.%T "Heapsort"
	145	.%J "Communications of the ACM"
	146	.%V 7:1
	147	.%P pp. 347-348
	148	.Re
	149	.Rs
	150	.%A Knuth, D.E.
	151	.%D 1968
	152	.%B "The Art of Computer Programming"
	153	.%V Vol. 3
	154	.%T "Sorting and Searching"
	155	.%P pp. 114-123, 145-149
	156	.Re
	157	.Rs
	158	.%A McIlroy, P.M.
	159	.%T "Optimistic Sorting and Information Theoretic Complexity"
	160	.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
	161	.%V January 1992
	162	.Re
	163	.Rs
	164	.%A Bentley, J.L.
	165	.%A McIlroy, M.D.
	166	.%T "Engineering a Sort Function"
	167	.%J "Software--Practice and Experience"
	168	.%V Vol. 23(11)
	169	.%P pp. 1249-1265
	170	.%D November\ 1993
	171	.Re
	172	.Sh STANDARDS
	173	The
	174	.Fn qsort
	175	function
	176	conforms to
	177	.St -isoC .