diff --git a/include/stdlib.h b/include/stdlib.h index 3ad28cf68847..730223e7fd77 100644 --- a/include/stdlib.h +++ b/include/stdlib.h @@ -1,416 +1,403 @@ /*- * SPDX-License-Identifier: BSD-3-Clause * * Copyright (c) 1990, 1993 * The Regents of the University of California. All rights reserved. * * 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. * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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. * * @(#)stdlib.h 8.5 (Berkeley) 5/19/95 * $FreeBSD$ */ #ifndef _STDLIB_H_ #define _STDLIB_H_ #include #include #include __NULLABILITY_PRAGMA_PUSH #if __BSD_VISIBLE #ifndef _RUNE_T_DECLARED typedef __rune_t rune_t; #define _RUNE_T_DECLARED #endif #endif #ifndef _SIZE_T_DECLARED typedef __size_t size_t; #define _SIZE_T_DECLARED #endif #ifndef __cplusplus #ifndef _WCHAR_T_DECLARED typedef ___wchar_t wchar_t; #define _WCHAR_T_DECLARED #endif #endif typedef struct { int quot; /* quotient */ int rem; /* remainder */ } div_t; typedef struct { long quot; long rem; } ldiv_t; #define EXIT_FAILURE 1 #define EXIT_SUCCESS 0 /* * I.e., INT_MAX; rand(3) returns a signed integer but must produce output in * the range [0, RAND_MAX], so half of the possible output range is unused. */ #define RAND_MAX 0x7fffffff __BEGIN_DECLS #ifdef _XLOCALE_H_ #include #endif extern int __mb_cur_max; extern int ___mb_cur_max(void); #define MB_CUR_MAX ((size_t)___mb_cur_max()) _Noreturn void abort(void); int abs(int) __pure2; int atexit(void (* _Nonnull)(void)); double atof(const char *); int atoi(const char *); long atol(const char *); void *bsearch(const void *, const void *, size_t, size_t, int (*)(const void * _Nonnull, const void *)); void *calloc(size_t, size_t) __malloc_like __result_use_check __alloc_size2(1, 2); div_t div(int, int) __pure2; _Noreturn void exit(int); void free(void *); char *getenv(const char *); long labs(long) __pure2; ldiv_t ldiv(long, long) __pure2; void *malloc(size_t) __malloc_like __result_use_check __alloc_size(1); int mblen(const char *, size_t); size_t mbstowcs(wchar_t * __restrict , const char * __restrict, size_t); int mbtowc(wchar_t * __restrict, const char * __restrict, size_t); -#if __BSD_VISIBLE -void bsort(void *, size_t, size_t, - int (* _Nonnull)(const void *, const void *)); -#endif void qsort(void *, size_t, size_t, int (* _Nonnull)(const void *, const void *)); int rand(void); void *realloc(void *, size_t) __result_use_check __alloc_size(2); void srand(unsigned); double strtod(const char * __restrict, char ** __restrict); float strtof(const char * __restrict, char ** __restrict); long strtol(const char * __restrict, char ** __restrict, int); long double strtold(const char * __restrict, char ** __restrict); unsigned long strtoul(const char * __restrict, char ** __restrict, int); int system(const char *); int wctomb(char *, wchar_t); size_t wcstombs(char * __restrict, const wchar_t * __restrict, size_t); /* * Functions added in C99 which we make conditionally available in the * BSD^C89 namespace if the compiler supports `long long'. * The #if test is more complicated than it ought to be because * __BSD_VISIBLE implies __ISO_C_VISIBLE == 1999 *even if* `long long' * is not supported in the compilation environment (which therefore means * that it can't really be ISO C99). * * (The only other extension made by C99 in this header is _Exit().) */ #if __ISO_C_VISIBLE >= 1999 || defined(__cplusplus) #ifdef __LONG_LONG_SUPPORTED /* LONGLONG */ typedef struct { long long quot; long long rem; } lldiv_t; /* LONGLONG */ long long atoll(const char *); /* LONGLONG */ long long llabs(long long) __pure2; /* LONGLONG */ lldiv_t lldiv(long long, long long) __pure2; /* LONGLONG */ long long strtoll(const char * __restrict, char ** __restrict, int); /* LONGLONG */ unsigned long long strtoull(const char * __restrict, char ** __restrict, int); #endif /* __LONG_LONG_SUPPORTED */ _Noreturn void _Exit(int); #endif /* __ISO_C_VISIBLE >= 1999 */ /* * If we're in a mode greater than C99, expose C11 functions. */ #if __ISO_C_VISIBLE >= 2011 || __cplusplus >= 201103L void * aligned_alloc(size_t, size_t) __malloc_like __alloc_align(1) __alloc_size(2); int at_quick_exit(void (*)(void)); _Noreturn void quick_exit(int); #endif /* __ISO_C_VISIBLE >= 2011 */ /* * Extensions made by POSIX relative to C. */ #if __POSIX_VISIBLE >= 199506 || __XSI_VISIBLE char *realpath(const char * __restrict, char * __restrict); #endif #if __POSIX_VISIBLE >= 199506 int rand_r(unsigned *); /* (TSF) */ #endif #if __POSIX_VISIBLE >= 200112 int posix_memalign(void **, size_t, size_t); /* (ADV) */ int setenv(const char *, const char *, int); int unsetenv(const char *); #endif #if __POSIX_VISIBLE >= 200809 || __XSI_VISIBLE int getsubopt(char **, char *const *, char **); #ifndef _MKDTEMP_DECLARED char *mkdtemp(char *); #define _MKDTEMP_DECLARED #endif #ifndef _MKSTEMP_DECLARED int mkstemp(char *); #define _MKSTEMP_DECLARED #endif #endif /* __POSIX_VISIBLE >= 200809 || __XSI_VISIBLE */ /* * The only changes to the XSI namespace in revision 6 were the deletion * of the ttyslot() and valloc() functions, which FreeBSD never declared * in this header. For revision 7, ecvt(), fcvt(), and gcvt(), which * FreeBSD also does not have, and mktemp(), are to be deleted. */ #if __XSI_VISIBLE /* XXX XSI requires pollution from here. We'd rather not. */ long a64l(const char *); double drand48(void); /* char *ecvt(double, int, int * __restrict, int * __restrict); */ double erand48(unsigned short[3]); /* char *fcvt(double, int, int * __restrict, int * __restrict); */ /* char *gcvt(double, int, int * __restrict, int * __restrict); */ char *initstate(unsigned int, char *, size_t); long jrand48(unsigned short[3]); char *l64a(long); void lcong48(unsigned short[7]); long lrand48(void); #if !defined(_MKTEMP_DECLARED) && (__BSD_VISIBLE || __XSI_VISIBLE <= 600) char *mktemp(char *); #define _MKTEMP_DECLARED #endif long mrand48(void); long nrand48(unsigned short[3]); int putenv(char *); long random(void); unsigned short *seed48(unsigned short[3]); char *setstate(/* const */ char *); void srand48(long); void srandom(unsigned int); #endif /* __XSI_VISIBLE */ #if __XSI_VISIBLE int grantpt(int); int posix_openpt(int); char *ptsname(int); int unlockpt(int); #endif /* __XSI_VISIBLE */ #if __BSD_VISIBLE /* ptsname_r will be included in POSIX issue 8 */ int ptsname_r(int, char *, size_t); #endif #if __BSD_VISIBLE extern const char *malloc_conf; extern void (*malloc_message)(void *, const char *); /* * The alloca() function can't be implemented in C, and on some * platforms it can't be implemented at all as a callable function. * The GNU C compiler provides a built-in alloca() which we can use. * On platforms where alloca() is not in libc, programs which use it * will fail to link when compiled with non-GNU compilers. */ #if __GNUC__ >= 2 #undef alloca /* some GNU bits try to get cute and define this on their own */ #define alloca(sz) __builtin_alloca(sz) #endif void abort2(const char *, int, void **) __dead2; __uint32_t arc4random(void); void arc4random_buf(void *, size_t); __uint32_t arc4random_uniform(__uint32_t); #ifdef __BLOCKS__ int atexit_b(void (^ _Nonnull)(void)); void *bsearch_b(const void *, const void *, size_t, size_t, int (^ _Nonnull)(const void *, const void *)); #endif char *getbsize(int *, long *); /* getcap(3) functions */ char *cgetcap(char *, const char *, int); int cgetclose(void); int cgetent(char **, char **, const char *); int cgetfirst(char **, char **); int cgetmatch(const char *, const char *); int cgetnext(char **, char **); int cgetnum(char *, const char *, long *); int cgetset(const char *); int cgetstr(char *, const char *, char **); int cgetustr(char *, const char *, char **); int clearenv(void); int daemon(int, int); int daemonfd(int, int); char *devname(__dev_t, __mode_t); char *devname_r(__dev_t, __mode_t, char *, int); char *fdevname(int); char *fdevname_r(int, char *, int); int getloadavg(double [], int); const char * getprogname(void); int heapsort(void *, size_t, size_t, int (* _Nonnull)(const void *, const void *)); #ifdef __BLOCKS__ int heapsort_b(void *, size_t, size_t, int (^ _Nonnull)(const void *, const void *)); -void bsort_b(void *, size_t, size_t, - int (^ _Nonnull)(const void *, const void *)); void qsort_b(void *, size_t, size_t, int (^ _Nonnull)(const void *, const void *)); #endif int l64a_r(long, char *, int); int mergesort(void *, size_t, size_t, int (*)(const void *, const void *)); #ifdef __BLOCKS__ int mergesort_b(void *, size_t, size_t, int (^)(const void *, const void *)); #endif int mkostemp(char *, int); int mkostemps(char *, int, int); int mkostempsat(int, char *, int, int); void qsort_r(void *, size_t, size_t, int (*)(const void *, const void *, void *), void *); -void bsort_r(void *, size_t, size_t, - int (*)(const void *, const void *, void *), void *); int radixsort(const unsigned char **, int, const unsigned char *, unsigned); void *reallocarray(void *, size_t, size_t) __result_use_check __alloc_size2(2, 3); void *reallocf(void *, size_t) __result_use_check __alloc_size(2); int rpmatch(const char *); char *secure_getenv(const char *); void setprogname(const char *); int sradixsort(const unsigned char **, int, const unsigned char *, unsigned); void srandomdev(void); long long strtonum(const char *, long long, long long, const char **); /* Deprecated interfaces, to be removed. */ __int64_t strtoq(const char *, char **, int); __uint64_t strtouq(const char *, char **, int); /* * In FreeBSD 14, the prototype of qsort_r() was modified to comply with * POSIX. The standardized qsort_r()'s order of last two parameters was * changed, and the comparator function is now taking thunk as its last * parameter, and both are different from the ones expected by the historical * FreeBSD qsort_r() interface. * * Apply a workaround where we explicitly link against the historical * interface, qsort_r@FBSD_1.0, in case when qsort_r() is called with * the last parameter with a function pointer that exactly matches the * historical FreeBSD qsort_r() comparator signature, so applications * written for the historical interface can continue to work without * modification. */ #if defined(__generic) || defined(__cplusplus) void __qsort_r_compat(void *, size_t, size_t, void *, int (*)(void *, const void *, const void *)); __sym_compat(qsort_r, __qsort_r_compat, FBSD_1.0); #endif #if defined(__generic) && !defined(__cplusplus) #define qsort_r(base, nel, width, arg4, arg5) \ __generic(arg5, int (*)(void *, const void *, const void *), \ __qsort_r_compat, qsort_r)(base, nel, width, arg4, arg5) #elif defined(__cplusplus) __END_DECLS extern "C++" { static inline void qsort_r(void *base, size_t nmemb, size_t size, void *thunk, int (*compar)(void *, const void *, const void *)) { __qsort_r_compat(base, nmemb, size, thunk, compar); } } __BEGIN_DECLS #endif extern char *suboptarg; /* getsubopt(3) external variable */ #endif /* __BSD_VISIBLE */ #if __EXT1_VISIBLE #ifndef _RSIZE_T_DEFINED #define _RSIZE_T_DEFINED typedef size_t rsize_t; #endif #ifndef _ERRNO_T_DEFINED #define _ERRNO_T_DEFINED typedef int errno_t; #endif /* K.3.6 */ typedef void (*constraint_handler_t)(const char * __restrict, void * __restrict, errno_t); /* K.3.6.1.1 */ constraint_handler_t set_constraint_handler_s(constraint_handler_t handler); /* K.3.6.1.2 */ _Noreturn void abort_handler_s(const char * __restrict, void * __restrict, errno_t); /* K3.6.1.3 */ void ignore_handler_s(const char * __restrict, void * __restrict, errno_t); /* K.3.6.3.2 */ errno_t qsort_s(void *, rsize_t, rsize_t, int (*)(const void *, const void *, void *), void *); - -#if __BSD_VISIBLE -errno_t bsort_s(void *, rsize_t, rsize_t, - int (*)(const void *, const void *, void *), void *); -#endif /* __BSD_VISIBLE */ #endif /* __EXT1_VISIBLE */ __END_DECLS __NULLABILITY_PRAGMA_POP #endif /* !_STDLIB_H_ */ diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc index 7503a82a6045..964e7ce30594 100644 --- a/lib/libc/stdlib/Makefile.inc +++ b/lib/libc/stdlib/Makefile.inc @@ -1,71 +1,69 @@ # from @(#)Makefile.inc 8.3 (Berkeley) 2/4/95 # $FreeBSD$ # machine-independent stdlib sources .PATH: ${LIBC_SRCTOP}/${LIBC_ARCH}/stdlib ${LIBC_SRCTOP}/stdlib MISRCS+=C99_Exit.c a64l.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \ bsearch.c \ cxa_thread_atexit.c cxa_thread_atexit_impl.c \ div.c exit.c getenv.c getopt.c getopt_long.c \ getsubopt.c hcreate.c hcreate_r.c hdestroy_r.c heapsort.c heapsort_b.c \ hsearch_r.c imaxabs.c imaxdiv.c \ insque.c l64a.c labs.c ldiv.c llabs.c lldiv.c lsearch.c \ - bsort.c bsort_r.c bsort_s.c \ merge.c mergesort_b.c ptsname.c qsort.c qsort_r.c qsort_r_compat.c \ qsort_s.c quick_exit.c radixsort.c rand.c \ random.c reallocarray.c reallocf.c realpath.c remque.c \ set_constraint_handler_s.c strfmon.c strtoimax.c \ strtol.c strtold.c strtoll.c strtoq.c strtoul.c strtonum.c strtoull.c \ strtoumax.c strtouq.c system.c tdelete.c tfind.c tsearch.c twalk.c CFLAGS.qsort.c+= -Wsign-compare # Work around an issue on case-insensitive file systems. # libc has both _Exit.c and _exit.s and they both yield # _exit.o (case insensitively speaking). CLEANFILES+=C99_Exit.c C99_Exit.c: ${LIBC_SRCTOP}/stdlib/_Exit.c .NOMETA ln -sf ${.ALLSRC} ${.TARGET} SYM_MAPS+= ${LIBC_SRCTOP}/stdlib/Symbol.map # machine-dependent stdlib sources .sinclude "${LIBC_SRCTOP}/${LIBC_ARCH}/stdlib/Makefile.inc" MAN+= a64l.3 abort.3 abs.3 alloca.3 atexit.3 atof.3 \ atoi.3 atol.3 at_quick_exit.3 bsearch.3 \ div.3 exit.3 getenv.3 getopt.3 getopt_long.3 getsubopt.3 \ hcreate.3 imaxabs.3 imaxdiv.3 insque.3 labs.3 ldiv.3 llabs.3 lldiv.3 \ - lsearch.3 memory.3 ptsname.3 bsort.3 qsort.3 \ + lsearch.3 memory.3 ptsname.3 qsort.3 \ quick_exit.3 \ radixsort.3 rand.3 random.3 reallocarray.3 reallocf.3 realpath.3 \ set_constraint_handler_s.3 \ strfmon.3 strtod.3 strtol.3 strtonum.3 strtoul.3 system.3 \ tsearch.3 MLINKS+=a64l.3 l64a.3 a64l.3 l64a_r.3 MLINKS+=atol.3 atoll.3 MLINKS+=exit.3 _Exit.3 MLINKS+=getenv.3 clearenv.3 getenv.3 putenv.3 getenv.3 secure_getenv.3 \ getenv.3 setenv.3 getenv.3 unsetenv.3 MLINKS+=getopt_long.3 getopt_long_only.3 MLINKS+=hcreate.3 hdestroy.3 hcreate.3 hsearch.3 MLINKS+=hcreate.3 hcreate_r.3 hcreate.3 hdestroy_r.3 hcreate.3 hsearch_r.3 MLINKS+=insque.3 remque.3 MLINKS+=lsearch.3 lfind.3 MLINKS+=ptsname.3 grantpt.3 ptsname.3 ptsname_r.3 ptsname.3 unlockpt.3 -MLINKS+=bsort.3 bsort_r.3 bsort.3 bsort_b.3 bsort.3 bsort_s.3 MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 qsort.3 qsort_r.3 \ qsort.3 qsort_s.3 MLINKS+=rand.3 rand_r.3 rand.3 srand.3 MLINKS+=random.3 initstate.3 random.3 setstate.3 random.3 srandom.3 \ random.3 srandomdev.3 MLINKS+=radixsort.3 sradixsort.3 MLINKS+=set_constraint_handler_s.3 abort_handler_s.3 MLINKS+=set_constraint_handler_s.3 ignore_handler_s.3 MLINKS+=strfmon.3 strfmon_l.3 MLINKS+=strtod.3 strtof.3 strtod.3 strtold.3 MLINKS+=strtol.3 strtoll.3 strtol.3 strtoq.3 strtol.3 strtoimax.3 MLINKS+=strtoul.3 strtoull.3 strtoul.3 strtouq.3 strtoul.3 strtoumax.3 MLINKS+=tsearch.3 tdelete.3 tsearch.3 tfind.3 tsearch.3 twalk.3 diff --git a/lib/libc/stdlib/Symbol.map b/lib/libc/stdlib/Symbol.map index 50583a30ad3d..a105f781734d 100644 --- a/lib/libc/stdlib/Symbol.map +++ b/lib/libc/stdlib/Symbol.map @@ -1,144 +1,140 @@ /* * $FreeBSD$ */ FBSD_1.0 { _Exit; a64l; abort; abs; atexit; __cxa_atexit; __cxa_finalize; atof; atoi; atol; atoll; bsearch; div; __isthreaded; exit; getenv; opterr; optind; optopt; optreset; optarg; getopt; getopt_long; getopt_long_only; suboptarg; getsubopt; grantpt; ptsname; unlockpt; hcreate; hdestroy; hsearch; heapsort; imaxabs; imaxdiv; insque; l64a; l64a_r; labs; ldiv; llabs; lldiv; lsearch; lfind; mergesort; putenv; qsort; radixsort; sradixsort; rand_r; srandom; srandomdev; initstate; setstate; random; reallocf; realpath; remque; setenv; unsetenv; strfmon; strtoimax; strtol; strtoll; strtonum; strtoq; strtoul; strtoull; strtoumax; strtouq; system; tdelete; tfind; tsearch; twalk; }; FBSD_1.3 { at_quick_exit; atof_l; atoi_l; atol_l; atoll_l; quick_exit; strtod_l; strtof_l; strtoimax_l; strtol_l; strtold_l; strtoll_l; strtoul_l; strtoull_l; strtoumax_l; }; FBSD_1.4 { atexit_b; bsearch_b; heapsort_b; mergesort_b; qsort_b; hcreate_r; hdestroy_r; hsearch_r; reallocarray; }; FBSD_1.5 { __cxa_thread_atexit; __cxa_thread_atexit_impl; abort_handler_s; ignore_handler_s; set_constraint_handler_s; }; FBSD_1.6 { ptsname_r; qsort_s; rand; srand; }; FBSD_1.7 { - bsort; - bsort_b; - bsort_r; - bsort_s; clearenv; qsort_r; secure_getenv; }; FBSDprivate_1.0 { __system; _system; __libc_system; __cxa_thread_call_dtors; __libc_atexit; }; diff --git a/lib/libc/stdlib/bsort.3 b/lib/libc/stdlib/bsort.3 deleted file mode 100644 index d0cadcacccc0..000000000000 --- a/lib/libc/stdlib/bsort.3 +++ /dev/null @@ -1,201 +0,0 @@ -.\" -.\" 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 20, 2023 -.Dt BSORT 3 -.Os -.Sh NAME -.Nm bsort , -.Nm bsort_b , -.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 , -.Xr radixsort 3 -.Sh HISTORY -This implementation was created by Hans Petter Selasky. diff --git a/lib/libc/stdlib/bsort.c b/lib/libc/stdlib/bsort.c deleted file mode 100644 index 0c470654cfe7..000000000000 --- a/lib/libc/stdlib/bsort.c +++ /dev/null @@ -1,267 +0,0 @@ -/*- - * SPDX-License-Identifier: BSD-2-Clause - * - * Copyright (c) 2016-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. - */ - -#include -#include - -#include -#include -#include -#include -#include - -#include "libc_private.h" - -/* - * A variant of bitonic sorting - * - * Worst case sorting complexity: log2(N) * log2(N) * N - * Additional memory and stack usage: none - */ - -#if defined(I_AM_BSORT_R) -typedef int cmp_t (const void *, const void *, void *); -#define ARG_PROTO void *arg, -#define ARG_NAME arg , -#define CMP(fn,arg,a,b) (fn)(a, b, arg) -#elif defined(I_AM_BSORT_S) -typedef int cmp_t (const void *, const void *, void *); -#define ARG_PROTO void *arg, -#define ARG_NAME arg , -#define CMP(fn,arg,a,b) (fn)(a, b, arg) -#else -typedef int cmp_t (const void *, const void *); -#define ARG_PROTO -#define ARG_NAME -#define CMP(fn,arg,a,b) (fn)(a, b) -#endif - -static inline void -bsort_swap(char *pa, char *pb, const size_t es) -{ - if (__builtin_constant_p(es) && es == 8) { - uint64_t tmp; - - /* swap */ - tmp = *(uint64_t *)pa; - *(uint64_t *)pa = *(uint64_t *)pb; - *(uint64_t *)pb = tmp; - } else if (__builtin_constant_p(es) && es == 4) { - uint32_t tmp; - - /* swap */ - tmp = *(uint32_t *)pa; - *(uint32_t *)pa = *(uint32_t *)pb; - *(uint32_t *)pb = tmp; - } else if (__builtin_constant_p(es) && es == 2) { - uint16_t tmp; - - /* swap */ - tmp = *(uint16_t *)pa; - *(uint16_t *)pa = *(uint16_t *)pb; - *(uint16_t *)pb = tmp; - } else if (__builtin_constant_p(es) && es == 1) { - uint8_t tmp; - - /* swap */ - tmp = *(uint8_t *)pa; - *(uint8_t *)pa = *(uint8_t *)pb; - *(uint8_t *)pb = tmp; - } else if (es <= 256) { - char tmp[es] __aligned(8); - - /* swap using fast memcpy() */ - memcpy(tmp, pa, es); - memcpy(pa, pb, es); - memcpy(pb, tmp, es); - } else { - /* swap byte-by-byte to avoid huge stack usage */ - for (size_t x = 0; x != es; x++) { - char tmp; - - /* swap */ - tmp = pa[x]; - pa[x] = pb[x]; - pb[x] = tmp; - } - } -} - -/* The following function returns true when the array is completely sorted. */ -static inline bool -bsort_complete(void *ptr, const size_t lim, const size_t es, ARG_PROTO cmp_t *fn) -{ - for (size_t x = 1; x != lim; x++) { - if (CMP(fn, arg, ptr, (char *)ptr + es) > 0) - return (false); - ptr = (char *)ptr + es; - } - return (true); -} - -static inline void -bsort_xform(char *ptr, const size_t n, size_t lim, const size_t es, ARG_PROTO cmp_t *fn) -{ -#define BSORT_TABLE_MAX (1UL << 4) - size_t x, y, z; - unsigned t, u, v; - size_t p[BSORT_TABLE_MAX]; - char *q[BSORT_TABLE_MAX]; - - lim *= es; - x = n; - for (;;) { - /* optimise */ - if (x >= BSORT_TABLE_MAX) - v = BSORT_TABLE_MAX; - else if (x >= 2) - v = x; - else - break; - - /* divide down */ - x /= v; - - /* generate ramp table */ - for (t = 0; t != v; t += 2) { - p[t] = (t * x); - p[t + 1] = (t + 2) * x - 1; - } - - /* bitonic sort */ - for (y = 0; y != n; y += (v * x)) { - for (z = 0; z != x; z++) { - const size_t w = y + z; - - /* p[0] is always zero and is omitted */ - q[0] = ptr + w * es; - - /* insertion sort */ - for (t = 1; t != v; t++) { - q[t] = ptr + (w ^ p[t]) * es; - - /* check for array lengths not power of two */ - if ((size_t)(q[t] - ptr) >= lim) - break; - for (u = t; u != 0 && CMP(fn, arg, q[u - 1], q[u]) > 0; u--) - bsort_swap(q[u - 1], q[u], es); - } - } - } - } -} - -static void -local_bsort(void *ptr, const size_t n, const size_t es, ARG_PROTO cmp_t *fn) -{ - size_t max; - - /* if there are less than 2 elements, then sorting is not needed */ - if (__predict_false(n < 2)) - return; - - /* compute power of two, into max */ - if (sizeof(size_t) <= sizeof(unsigned long)) - max = 1UL << (8 * sizeof(unsigned long) - __builtin_clzl(n) - 1); - else - max = 1ULL << (8 * sizeof(unsigned long long) - __builtin_clzll(n) - 1); - - /* round up power of two, if needed */ - if (!powerof2(n)) - max <<= 1; - - /* optimize common sort scenarios */ - switch (es) { - case 8: - while (!bsort_complete(ptr, n, 8, ARG_NAME fn)) - bsort_xform(ptr, max, n, 8, ARG_NAME fn); - break; - case 4: - while (!bsort_complete(ptr, n, 4, ARG_NAME fn)) - bsort_xform(ptr, max, n, 4, ARG_NAME fn); - break; - case 2: - while (!bsort_complete(ptr, n, 2, ARG_NAME fn)) - bsort_xform(ptr, max, n, 2, ARG_NAME fn); - break; - case 1: - while (!bsort_complete(ptr, n, 1, ARG_NAME fn)) - bsort_xform(ptr, max, n, 1, ARG_NAME fn); - break; - case 0: - /* undefined behaviour */ - break; - default: - while (!bsort_complete(ptr, n, es, ARG_NAME fn)) - bsort_xform(ptr, max, n, es, ARG_NAME fn); - break; - } -} - -#if defined(I_AM_BSORT_R) -void -bsort_r(void *a, size_t n, size_t es, cmp_t *cmp, void *arg) -{ - local_bsort(a, n, es, cmp, arg); -} -#elif defined(I_AM_BSORT_S) -errno_t -bsort_s(void *a, rsize_t n, rsize_t es, cmp_t *cmp, void *arg) -{ - if (n > RSIZE_MAX) { - __throw_constraint_handler_s("bsort_s : n > RSIZE_MAX", EINVAL); - return (EINVAL); - } else if (es > RSIZE_MAX) { - __throw_constraint_handler_s("bsort_s : es > RSIZE_MAX", - EINVAL); - return (EINVAL); - } else if (n != 0) { - if (a == NULL) { - __throw_constraint_handler_s("bsort_s : a == NULL", - EINVAL); - return (EINVAL); - } else if (cmp == NULL) { - __throw_constraint_handler_s("bsort_s : cmp == NULL", - EINVAL); - return (EINVAL); - } else if (es <= 0) { - __throw_constraint_handler_s("bsort_s : es <= 0", - EINVAL); - return (EINVAL); - } - } - - local_bsort(a, n, es, cmp, arg); - return (0); -} -#else -void -bsort(void *a, size_t n, size_t es, cmp_t *cmp) -{ - local_bsort(a, n, es, cmp); -} -#endif diff --git a/lib/libc/stdlib/bsort_r.c b/lib/libc/stdlib/bsort_r.c deleted file mode 100644 index 762f3c5aa1ec..000000000000 --- a/lib/libc/stdlib/bsort_r.c +++ /dev/null @@ -1,25 +0,0 @@ -/* - * This file is in the public domain. - */ -#include "block_abi.h" -#define I_AM_BSORT_R -#include "bsort.c" - -typedef DECLARE_BLOCK(int, bsort_block, const void *, const void *); - -static int -bsort_b_compare(const void *pa, const void *pb, void *arg) -{ - bsort_block compar; - int (*cmp)(void *, const void *, const void *); - - compar = arg; - cmp = (void *)compar->invoke; - return (cmp(compar, pa, pb)); -} - -void -bsort_b(void *base, size_t nel, size_t width, bsort_block compar) -{ - bsort_r(base, nel, width, &bsort_b_compare, compar); -} diff --git a/lib/libc/stdlib/bsort_s.c b/lib/libc/stdlib/bsort_s.c deleted file mode 100644 index 57abde76a257..000000000000 --- a/lib/libc/stdlib/bsort_s.c +++ /dev/null @@ -1,5 +0,0 @@ -/* - * This file is in the public domain. - */ -#define I_AM_BSORT_S -#include "bsort.c"