diff options
| author | Hans Petter Selasky <hselasky@FreeBSD.org> | 2022-09-08 10:16:43 +0000 |
|---|---|---|
| committer | Hans Petter Selasky <hselasky@FreeBSD.org> | 2023-04-19 12:04:22 +0000 |
| commit | 8dcf3a82c54cb216df3213a013047907636a01da (patch) | |
| tree | e65bb310889a0864aa9718e4522e0e850bbca6ac /include | |
| parent | 4fee5114c3749f2b12404b89e616d4cb69a01c92 (diff) | |
| download | src-8dcf3a82c54cb216df3213a013047907636a01da.tar.gz src-8dcf3a82c54cb216df3213a013047907636a01da.zip | |
libc: Implement bsort(3) a bitonic type of sorting algorithm.
The bsort(3) algorithm works by swapping objects, similarly to qsort(3),
and does not require any significant amount of additional memory.
The bsort(3) algorithm doesn't suffer from the processing time issues
known the plague the qsort(3) family of algorithms, and is bounded by
a complexity of O(log2(N) * log2(N) * N), where N is the number of
elements in the sorting array. The additional complexity compared to
mergesort(3) is a fair tradeoff in situations where no memory may
be allocated.
The bsort(3) APIs are identical to those of qsort(3), allowing for
easy drop-in and testing.
The design of the bsort(3) algorithm allows for future parallell CPU
execution when sorting arrays. The current version of the bsort(3)
algorithm is single threaded. This is possible because fixed areas
of the sorting data is compared at a time, and can easily be divided
among different CPU's to sort large arrays faster.
Reviewed by: gbe@, delphij@, pauamma_gundo.com (manpages)
Sponsored by: NVIDIA Networking
Differential Revision: https://reviews.freebsd.org/D36493
Diffstat (limited to 'include')
| -rw-r--r-- | include/stdlib.h | 13 |
1 files changed, 13 insertions, 0 deletions
diff --git a/include/stdlib.h b/include/stdlib.h index 730223e7fd77..857092b9053e 100644 --- a/include/stdlib.h +++ b/include/stdlib.h @@ -107,6 +107,10 @@ 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); @@ -300,6 +304,8 @@ int heapsort(void *, size_t, size_t, #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 @@ -313,6 +319,8 @@ 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 @@ -397,6 +405,11 @@ errno_t qsort_s(void *, rsize_t, rsize_t, int (*)(const void *, const void *, void *), void *); #endif /* __EXT1_VISIBLE */ +#if __BSD_VISIBLE +errno_t bsort_s(void *, rsize_t, rsize_t, + int (*)(const void *, const void *, void *), void *); +#endif /* __BSD_VISIBLE */ + __END_DECLS __NULLABILITY_PRAGMA_POP |