Changeset View
Changeset View
Standalone View
Standalone View
lib/libc/stdlib/bsort.3
- This file was added.
.\" | ||||||||||||||||||||
.\" Copyright (c) 2022 Hans Petter Selasky | ||||||||||||||||||||
.\" | ||||||||||||||||||||
.\" Redistribution and use in source and binary forms, with or without | ||||||||||||||||||||
.\" modification, are permitted provided that the following conditions | ||||||||||||||||||||
.\" are met: | ||||||||||||||||||||
.\" 1. Redistributions of source code must retain the above copyright | ||||||||||||||||||||
.\" notice, this list of conditions and the following disclaimer. | ||||||||||||||||||||
.\" 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. | ||||||||||||||||||||
.\" | ||||||||||||||||||||
.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND | ||||||||||||||||||||
.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||||||||||||||||||||
.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||||||||||||||||||||
.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | ||||||||||||||||||||
.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | ||||||||||||||||||||
.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | ||||||||||||||||||||
.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | ||||||||||||||||||||
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||||||||||||||||||||
.\" 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 | ||||||||||||||||||||
.\" SUCH DAMAGE. | ||||||||||||||||||||
.\" | ||||||||||||||||||||
.\" $FreeBSD$ | ||||||||||||||||||||
.\" | ||||||||||||||||||||
pauamma_gundo.com: Do we still use that? I foegot. | ||||||||||||||||||||
Done Inline ActionsI just copied from qsort.3 . Should I remove it? hselasky: I just copied from qsort.3 . Should I remove it? | ||||||||||||||||||||
.Dd October 2, 2022 | ||||||||||||||||||||
.Dt BSORT 3 | ||||||||||||||||||||
.Os | ||||||||||||||||||||
.Sh NAME | ||||||||||||||||||||
.Nm bsort , | ||||||||||||||||||||
.Nm bsort_b , | ||||||||||||||||||||
.Nm bsort_r | ||||||||||||||||||||
and | ||||||||||||||||||||
.Nm bsort_s | ||||||||||||||||||||
.Nd sort functions | ||||||||||||||||||||
.Sh LIBRARY | ||||||||||||||||||||
.Lb libc | ||||||||||||||||||||
.Sh SYNOPSIS | ||||||||||||||||||||
.In stdlib.h | ||||||||||||||||||||
.Ft void | ||||||||||||||||||||
.Fo bsort | ||||||||||||||||||||
.Fa "void *base" | ||||||||||||||||||||
.Fa "size_t nmemb" | ||||||||||||||||||||
.Fa "size_t size" | ||||||||||||||||||||
.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" | ||||||||||||||||||||
.Fc | ||||||||||||||||||||
.Ft void | ||||||||||||||||||||
.Fo bsort_b | ||||||||||||||||||||
.Fa "void *base" | ||||||||||||||||||||
.Fa "size_t nmemb" | ||||||||||||||||||||
.Fa "size_t size" | ||||||||||||||||||||
.Fa "bsort_block compar" | ||||||||||||||||||||
.Fc | ||||||||||||||||||||
.Ft void | ||||||||||||||||||||
.Fo bsort_r | ||||||||||||||||||||
.Fa "void *base" | ||||||||||||||||||||
.Fa "size_t nmemb" | ||||||||||||||||||||
.Fa "size_t size" | ||||||||||||||||||||
.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *, void *\*[rp]" | ||||||||||||||||||||
.Fa "void *thunk" | ||||||||||||||||||||
.Fc | ||||||||||||||||||||
.Fd #define __STDC_WANT_LIB_EXT1__ 1 | ||||||||||||||||||||
.Ft errno_t | ||||||||||||||||||||
.Fo bsort_s | ||||||||||||||||||||
.Fa "void *base" | ||||||||||||||||||||
.Fa "size_t nmemb" | ||||||||||||||||||||
.Fa "size_t size" | ||||||||||||||||||||
.Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]" | ||||||||||||||||||||
.Fa "void *thunk" | ||||||||||||||||||||
.Fc | ||||||||||||||||||||
.Sh DESCRIPTION | ||||||||||||||||||||
The | ||||||||||||||||||||
.Fn bsort | ||||||||||||||||||||
function is based on so-called in-place bitonic sorting. | ||||||||||||||||||||
Bitonic sorting is suitable for parallel execution, | ||||||||||||||||||||
because the elements in the array to sort are compared in a predefined | ||||||||||||||||||||
sequence that doesn't depend on the data. | ||||||||||||||||||||
The complexity of the | ||||||||||||||||||||
Done Inline Actions
pauamma_gundo.com: | ||||||||||||||||||||
.Fn bsort | ||||||||||||||||||||
algorithm is bounded by O(log2(N) * log2(N) * N), where N is the | ||||||||||||||||||||
number of elements in the sorting array. | ||||||||||||||||||||
The | ||||||||||||||||||||
.Fn bsort | ||||||||||||||||||||
function provides a reliable in-place sorting algorithm, | ||||||||||||||||||||
with little memory usage and without the excess processing usage | ||||||||||||||||||||
caveats of other algorithms like | ||||||||||||||||||||
.Xr qsort 3 . | ||||||||||||||||||||
.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 bsort_r | ||||||||||||||||||||
function behaves identically to | ||||||||||||||||||||
.Fn bsort , | ||||||||||||||||||||
except that it takes an additional argument, | ||||||||||||||||||||
.Fa thunk , | ||||||||||||||||||||
which is passed unchanged as the last argument to the function | ||||||||||||||||||||
.Fa compar | ||||||||||||||||||||
points to. | ||||||||||||||||||||
Done Inline Actions
pauamma_gundo.com: | ||||||||||||||||||||
This allows the comparison function to access additional | ||||||||||||||||||||
data without using global variables, and thus | ||||||||||||||||||||
.Fn bsort_r | ||||||||||||||||||||
is suitable for use in functions which must be reentrant. | ||||||||||||||||||||
The | ||||||||||||||||||||
.Fn bsort_b | ||||||||||||||||||||
function behaves identically to | ||||||||||||||||||||
.Fn bsort , | ||||||||||||||||||||
except that it takes a block, rather than a function pointer. | ||||||||||||||||||||
.Pp | ||||||||||||||||||||
The algorithm implemented by | ||||||||||||||||||||
.Fn bsort , | ||||||||||||||||||||
.Fn bsort_b , | ||||||||||||||||||||
.Fn bsort_r | ||||||||||||||||||||
and | ||||||||||||||||||||
.Fn bsort_s | ||||||||||||||||||||
is | ||||||||||||||||||||
Done Inline Actions
Unless they implement different sorting algorithms. pauamma_gundo.com: Unless they implement different sorting algorithms. | ||||||||||||||||||||
.Em not | ||||||||||||||||||||
stable, that is, if two members compare as equal, their order in | ||||||||||||||||||||
the sorted array is undefined. | ||||||||||||||||||||
.Pp | ||||||||||||||||||||
The | ||||||||||||||||||||
.Fn bsort_s | ||||||||||||||||||||
function behaves the same as | ||||||||||||||||||||
.Fn bsort_r | ||||||||||||||||||||
except that if | ||||||||||||||||||||
Done Inline Actionstypo excepth -> except gbe: typo excepth -> except | ||||||||||||||||||||
.Fa size | ||||||||||||||||||||
is greater than | ||||||||||||||||||||
.Dv RSIZE_MAX | ||||||||||||||||||||
or | ||||||||||||||||||||
.Fa nmemb | ||||||||||||||||||||
Done Inline ActionsSpurious line, or mdoc subtlety I'm missing? pauamma_gundo.com: Spurious line, or mdoc subtlety I'm missing? | ||||||||||||||||||||
is not zero and | ||||||||||||||||||||
.Fa compar | ||||||||||||||||||||
is | ||||||||||||||||||||
.Dv NULL , | ||||||||||||||||||||
Done Inline Actions
Check that this is what you meant. Does this need a .Xr set_constraint_handler_s 3 like there is in memset(3)? pauamma_gundo.com: Check that this is what you meant.
Does this need a `.Xr set_constraint_handler_s 3` like… | ||||||||||||||||||||
Done Inline Actions
Based on #bsddocs discussion pauamma_gundo.com: Based on #bsddocs discussion | ||||||||||||||||||||
then the runtime-constraint handler is called, and | ||||||||||||||||||||
.Fn bsort_s | ||||||||||||||||||||
returns an error. | ||||||||||||||||||||
Note that the handler is called before | ||||||||||||||||||||
.Fn bsort_s | ||||||||||||||||||||
returns the error, and the handler function might not return. | ||||||||||||||||||||
.Sh RETURN VALUES | ||||||||||||||||||||
The | ||||||||||||||||||||
.Fn bsort , | ||||||||||||||||||||
.Fn bsort_b | ||||||||||||||||||||
and | ||||||||||||||||||||
.Fn bsort_r | ||||||||||||||||||||
functions | ||||||||||||||||||||
return no value. | ||||||||||||||||||||
The | ||||||||||||||||||||
.Fn bsort_s | ||||||||||||||||||||
function returns zero on success, non-zero on error. | ||||||||||||||||||||
.Sh EXAMPLES | ||||||||||||||||||||
A sample program that sorts an array of | ||||||||||||||||||||
.Vt int | ||||||||||||||||||||
values in place using | ||||||||||||||||||||
.Fn bsort , | ||||||||||||||||||||
and then prints the sorted array to standard output is: | ||||||||||||||||||||
.Bd -literal | ||||||||||||||||||||
#include <stdio.h> | ||||||||||||||||||||
#include <stdlib.h> | ||||||||||||||||||||
/* | ||||||||||||||||||||
* Custom comparison function that compares 'int' values through pointers | ||||||||||||||||||||
* passed by bsort(3). | ||||||||||||||||||||
*/ | ||||||||||||||||||||
static int | ||||||||||||||||||||
int_compare(const void *p1, const void *p2) | ||||||||||||||||||||
{ | ||||||||||||||||||||
int left = *(const int *)p1; | ||||||||||||||||||||
int right = *(const int *)p2; | ||||||||||||||||||||
return ((left > right) - (left < right)); | ||||||||||||||||||||
} | ||||||||||||||||||||
/* | ||||||||||||||||||||
* Sort an array of 'int' values and print it to standard output. | ||||||||||||||||||||
*/ | ||||||||||||||||||||
int | ||||||||||||||||||||
main(void) | ||||||||||||||||||||
{ | ||||||||||||||||||||
int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 }; | ||||||||||||||||||||
size_t array_size = sizeof(int_array) / sizeof(int_array[0]); | ||||||||||||||||||||
size_t k; | ||||||||||||||||||||
bsort(&int_array, array_size, sizeof(int_array[0]), int_compare); | ||||||||||||||||||||
for (k = 0; k < array_size; k++) | ||||||||||||||||||||
printf(" %d", int_array[k]); | ||||||||||||||||||||
puts(""); | ||||||||||||||||||||
return (EXIT_SUCCESS); | ||||||||||||||||||||
} | ||||||||||||||||||||
.Ed | ||||||||||||||||||||
.Sh SEE ALSO | ||||||||||||||||||||
.Xr sort 1 , | ||||||||||||||||||||
.Xr qsort 3 | ||||||||||||||||||||
and | ||||||||||||||||||||
.Xr radixsort 3 | ||||||||||||||||||||
.Sh HISTORY | ||||||||||||||||||||
This implementation was created by Hans Petter Selasky. |
Do we still use that? I foegot.