diff --git a/lib/libc/stdlib/bsort.3 b/lib/libc/stdlib/bsort.3 index 9cc2edc04dd2..d0cadcacccc0 100644 --- a/lib/libc/stdlib/bsort.3 +++ b/lib/libc/stdlib/bsort.3 @@ -1,203 +1,201 @@ .\" -.\" Copyright (c) 2022 Hans Petter Selasky +.\" Copyright (c) 2022-2023 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$ .\" -.Dd April 19, 2023 +.Dd April 20, 2023 .Dt BSORT 3 .Os .Sh NAME .Nm bsort , .Nm bsort_b , -.Nm bsort_r -and +.Nm bsort_r , .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 not depending on the data. The complexity of the .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 it takes an additional argument, .Fa thunk , which is passed unchanged as the last argument to the function .Fa compar points to. 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 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 .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 if .Fa size is greater than .Dv RSIZE_MAX , or .Fa nmemb is not zero and .Fa compar is .Dv NULL or .Fa size is zero, then the runtime-constraint handler is called, and .Fn bsort_s returns an error. Note 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 sorting an array of .Vt int values in place using .Fn bsort , and then prints the sorted array to standard output is: .Bd -literal #include #include /* * Custom comparison function comparing '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 qsort 3 , .Xr radixsort 3 .Sh HISTORY This implementation was created by Hans Petter Selasky.