Changeset View
Changeset View
Standalone View
Standalone View
head/lib/libc/stdlib/qsort.3
Show All 26 Lines | |||||
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||||
.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | ||||
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | ||||
.\" SUCH DAMAGE. | .\" SUCH DAMAGE. | ||||
.\" | .\" | ||||
.\" @(#)qsort.3 8.1 (Berkeley) 6/4/93 | .\" @(#)qsort.3 8.1 (Berkeley) 6/4/93 | ||||
.\" $FreeBSD$ | .\" $FreeBSD$ | ||||
.\" | .\" | ||||
.Dd February 20, 2013 | .Dd January 14, 2020 | ||||
.Dt QSORT 3 | .Dt QSORT 3 | ||||
.Os | .Os | ||||
.Sh NAME | .Sh NAME | ||||
.Nm qsort , | .Nm qsort , | ||||
.Nm qsort_b , | .Nm qsort_b , | ||||
.Nm qsort_r , | .Nm qsort_r , | ||||
.Nm heapsort , | .Nm heapsort , | ||||
.Nm heapsort_b , | .Nm heapsort_b , | ||||
▲ Show 20 Lines • Show All 49 Lines • ▼ Show 20 Lines | |||||
.Fc | .Fc | ||||
.Ft int | .Ft int | ||||
.Fo mergesort_b | .Fo mergesort_b | ||||
.Fa "void *base" | .Fa "void *base" | ||||
.Fa "size_t nmemb" | .Fa "size_t nmemb" | ||||
.Fa "size_t size" | .Fa "size_t size" | ||||
.Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]" | .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]" | ||||
.Fc | .Fc | ||||
.Fd #define __STDC_WANT_LIB_EXT1__ 1 | |||||
.Ft errno_t | |||||
.Fo qsort_s | |||||
.Fa "void *base" | |||||
.Fa "rsize_t nmemb" | |||||
.Fa "rsize_t size" | |||||
.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *, void *\*[rp]" | |||||
.Fa "void *thunk" | |||||
.Fc | |||||
.Sh DESCRIPTION | .Sh DESCRIPTION | ||||
The | The | ||||
.Fn qsort | .Fn qsort | ||||
function is a modified partition-exchange sort, or quicksort. | function is a modified partition-exchange sort, or quicksort. | ||||
The | The | ||||
.Fn heapsort | .Fn heapsort | ||||
function is a modified selection sort. | function is a modified selection sort. | ||||
The | The | ||||
▲ Show 20 Lines • Show All 124 Lines • ▼ Show 20 Lines | |||||
Normally, | Normally, | ||||
.Fn qsort | .Fn qsort | ||||
is faster than | is faster than | ||||
.Fn mergesort | .Fn mergesort | ||||
is faster than | is faster than | ||||
.Fn heapsort . | .Fn heapsort . | ||||
Memory availability and pre-existing order in the data can make this | Memory availability and pre-existing order in the data can make this | ||||
untrue. | untrue. | ||||
.Pp | |||||
The | |||||
.Fn qsort_s | |||||
function behaves the same as | |||||
.Fn qsort_r , except that: | |||||
.Bl -dash | |||||
.It | |||||
The order of arguments is different | |||||
.It | |||||
The order of arguments to | |||||
.Fa compar | |||||
is different | |||||
.It | |||||
if | |||||
.Fa nmemb | |||||
or | |||||
.Fa size | |||||
are greater than | |||||
.Dv RSIZE_MAX , | |||||
or | |||||
.Fa nmemb | |||||
is not zero and | |||||
.Fa compar | |||||
is NULL, then the runtime-constraint handler is called, and | |||||
.Fn qsort_s | |||||
returns an error. | |||||
Note that the handler is called before | |||||
.Fn qsort_s | |||||
returns the error, and the handler function might not return. | |||||
.El | |||||
.Sh RETURN VALUES | .Sh RETURN VALUES | ||||
The | The | ||||
.Fn qsort | .Fn qsort | ||||
and | and | ||||
.Fn qsort_r | .Fn qsort_r | ||||
functions | functions | ||||
return no value. | return no value. | ||||
The | |||||
.Fn qsort_s | |||||
function returns zero on success, non-zero on error. | |||||
.Pp | .Pp | ||||
.Rv -std heapsort mergesort | .Rv -std heapsort mergesort | ||||
.Sh EXAMPLES | .Sh EXAMPLES | ||||
A sample program that sorts an array of | A sample program that sorts an array of | ||||
.Vt int | .Vt int | ||||
values in place using | values in place using | ||||
.Fn qsort , | .Fn qsort , | ||||
and then prints the sorted array to standard output is: | and then prints the sorted array to standard output is: | ||||
Show All 27 Lines | main(void) | ||||
qsort(&int_array, array_size, sizeof(int_array[0]), int_compare); | qsort(&int_array, array_size, sizeof(int_array[0]), int_compare); | ||||
for (k = 0; k < array_size; k++) | for (k = 0; k < array_size; k++) | ||||
printf(" %d", int_array[k]); | printf(" %d", int_array[k]); | ||||
puts(""); | puts(""); | ||||
return (EXIT_SUCCESS); | return (EXIT_SUCCESS); | ||||
} | } | ||||
.Ed | .Ed | ||||
.Sh COMPATIBILITY | .Sh COMPATIBILITY | ||||
The order of arguments for the comparison function used with | |||||
.Fn qsort_r | |||||
is different from the one used by | |||||
.Fn qsort_s , | |||||
and the GNU libc implementation of | |||||
.Fn qsort_r . | |||||
When porting software written for GNU libc, it is usually possible | |||||
to replace | |||||
.Fn qsort_r | |||||
with | |||||
.Fn qsort_s | |||||
to work around this problem. | |||||
.Pp | |||||
Previous versions of | Previous versions of | ||||
.Fn qsort | .Fn qsort | ||||
did not permit the comparison routine itself to call | did not permit the comparison routine itself to call | ||||
.Fn qsort 3 . | .Fn qsort 3 . | ||||
This is no longer true. | This is no longer true. | ||||
.Sh ERRORS | .Sh ERRORS | ||||
The | The | ||||
.Fn heapsort | .Fn heapsort | ||||
▲ Show 20 Lines • Show All 62 Lines • ▼ Show 20 Lines | |||||
.%D November\ 1993 | .%D November\ 1993 | ||||
.Re | .Re | ||||
.Sh STANDARDS | .Sh STANDARDS | ||||
The | The | ||||
.Fn qsort | .Fn qsort | ||||
function | function | ||||
conforms to | conforms to | ||||
.St -isoC . | .St -isoC . | ||||
.Fn qsort_s | |||||
conforms to | |||||
.St -isoC-2011 | |||||
K.3.6.3.2. | |||||
.Sh HISTORY | .Sh HISTORY | ||||
The variants of these functions that take blocks as arguments first appeared in | The variants of these functions that take blocks as arguments first appeared in | ||||
Mac OS X. | Mac OS X. | ||||
This implementation was created by David Chisnall. | This implementation was created by David Chisnall. |