From nobody Wed Apr 19 12:20:13 2023 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4Q1fxv3BBcz45PdY; Wed, 19 Apr 2023 12:20:19 +0000 (UTC) (envelope-from yuri@aetern.org) Received: from out1-smtp.messagingengine.com (out1-smtp.messagingengine.com [66.111.4.25]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4Q1fxv1bGyz4KR7; Wed, 19 Apr 2023 12:20:19 +0000 (UTC) (envelope-from yuri@aetern.org) Authentication-Results: mx1.freebsd.org; none Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailout.nyi.internal (Postfix) with ESMTP id 1823B5C010A; Wed, 19 Apr 2023 08:20:18 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute1.internal (MEProxy); Wed, 19 Apr 2023 08:20:18 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aetern.org; h=cc :content-transfer-encoding:content-type:content-type:date:date :from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:sender:subject:subject:to:to; s=fm2; t= 1681906818; x=1681993218; bh=w6JdW/TdzFH85QQA1Um5sS7U8Euu/LA7SuV RsNGTp2o=; b=His/+bPl3gV6ED8WjKW5w5kaD2Ja1jSNsicOXMTxqtRdYiwTDoE sOyvdhFT251pIeSQL67wduLH6NpjpDdc8ZLf5Bw+SSAyEqZkpnAHXomsoUeGj5be kfudyXrWfw+k3N1vlVS023mIRtlrI5XTWCSgscuhxAs0MzV44Bel+HVL+576MO2x PnTr2g8OnaCBdVXjOTYMz1n3KRkA7Z2luX5Tmm5YYWv5hkbIrOpbhTX5Mrh60TzQ +5RQXBZvMtEGMzAnTeuBuK718vrDQMvI9vkNZrbsTpon5MMiqCVFwsH/thIlQXOx /llA+8DfO+W6f2+mO/8+Kq9Uswmau568WCA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :content-type:date:date:feedback-id:feedback-id:from:from :in-reply-to:in-reply-to:message-id:mime-version:references :reply-to:sender:subject:subject:to:to:x-me-proxy:x-me-proxy :x-me-sender:x-me-sender:x-sasl-enc; s=fm3; t=1681906818; x= 1681993218; bh=w6JdW/TdzFH85QQA1Um5sS7U8Euu/LA7SuVRsNGTp2o=; b=B H7e44NKmAPvJz4I8WKzSUbNepstW7ZPfZRRc0sOqDGAHovBHTIfsR41oQ5eyBOap kuMZWvScBFM24uX2HYd5WjlzZ3kVmxC07jx2ICAivwVfkHWnPVJqMO2jS+qs036t 0oipyeMKsmcIQOYDYUsa6nUUGo51p/y/Vs1T5PwvzSQGdAVsITBYm6ljw+BxW38X dPLqwuDjPaCj8ww0re/Hlc+KGqYvAB8E0r5NlDEv6vUja1QdJ8lj8ifuquE9xFeW OABEqyKswx62sH+flGYbbYu/wIMAfl3qddPIXW0TNmVuTWYP+lRm1xdYSt2s1Sle sGUUFKHV5RNL9zQPofN7g== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvhedrfedttddgheduucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurhepkfffgggfuffvfhfhjggtgfesthejredttdefjeenucfhrhhomhepjghurhhi uceohihurhhisegrvghtvghrnhdrohhrgheqnecuggftrfgrthhtvghrnhepgeehleevue ehhffggfetteffieffhfduteduteeuvdehvdfhffdvtefhffejjedvnecuffhomhgrihhn pehfrhgvvggsshgurdhorhhgnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpe hmrghilhhfrhhomhephihurhhisegrvghtvghrnhdrohhrgh X-ME-Proxy: Feedback-ID: i0d79475b:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Wed, 19 Apr 2023 08:20:16 -0400 (EDT) Message-ID: <614f21af-0de6-2264-265d-2aab212800a9@aetern.org> Date: Wed, 19 Apr 2023 14:20:13 +0200 List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101 Thunderbird/102.10.0 Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm. Content-Language: en-US To: Hans Petter Selasky , src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> From: Yuri In-Reply-To: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Rspamd-Queue-Id: 4Q1fxv1bGyz4KR7 X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:19151, ipnet:66.111.4.0/24, country:US] X-Rspamd-Pre-Result: action=no action; module=replies; Message is reply to one we originated X-ThisMailContainsUnwantedMimeParts: N Hans Petter Selasky wrote: > The branch main has been updated by hselasky: > > URL: https://cgit.FreeBSD.org/src/commit/?id=8dcf3a82c54cb216df3213a013047907636a01da > > commit 8dcf3a82c54cb216df3213a013047907636a01da > Author: Hans Petter Selasky > AuthorDate: 2022-09-08 10:16:43 +0000 > Commit: Hans Petter Selasky > CommitDate: 2023-04-19 12:04:22 +0000 > > 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 > --- > include/stdlib.h | 13 +++ > lib/libc/stdlib/Makefile.inc | 4 +- > lib/libc/stdlib/Symbol.map | 4 + > lib/libc/stdlib/bsort.3 | 203 ++++++++++++++++++++++++++++++++ > lib/libc/stdlib/bsort.c | 267 +++++++++++++++++++++++++++++++++++++++++++ > lib/libc/stdlib/bsort_r.c | 25 ++++ > lib/libc/stdlib/bsort_s.c | 5 + > 7 files changed, 520 insertions(+), 1 deletion(-) > > 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 > > diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc > index 964e7ce30594..7503a82a6045 100644 > --- a/lib/libc/stdlib/Makefile.inc > +++ b/lib/libc/stdlib/Makefile.inc > @@ -11,6 +11,7 @@ MISRCS+=C99_Exit.c a64l.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.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 \ > @@ -36,7 +37,7 @@ 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 qsort.3 \ > + lsearch.3 memory.3 ptsname.3 bsort.3 qsort.3 \ > quick_exit.3 \ > radixsort.3 rand.3 random.3 reallocarray.3 reallocf.3 realpath.3 \ > set_constraint_handler_s.3 \ > @@ -54,6 +55,7 @@ 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 > diff --git a/lib/libc/stdlib/Symbol.map b/lib/libc/stdlib/Symbol.map > index a105f781734d..50583a30ad3d 100644 > --- a/lib/libc/stdlib/Symbol.map > +++ b/lib/libc/stdlib/Symbol.map > @@ -126,6 +126,10 @@ FBSD_1.6 { > }; > > FBSD_1.7 { > + bsort; > + bsort_b; > + bsort_r; > + bsort_s; > clearenv; > qsort_r; > secure_getenv; > diff --git a/lib/libc/stdlib/bsort.3 b/lib/libc/stdlib/bsort.3 > new file mode 100644 > index 000000000000..9cc2edc04dd2 > --- /dev/null > +++ b/lib/libc/stdlib/bsort.3 > @@ -0,0 +1,203 @@ > +.\" > +.\" 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$ > +.\" > +.Dd April 19, 2023 > +.Dt BSORT 3 > +.Os > +.Sh NAME > +.Nm bsort , > +.Nm bsort_b , > +.Nm bsort_r > +and > +.Nm bsort_s > +.Nd sort functions mandoc: lib/libc/stdlib/bsort.3:34:1: WARNING: bad NAME section content: text mandoc: lib/libc/stdlib/bsort.3:35:2: WARNING: missing comma before name: Nm bsort_s This should be a list of Nm macros, without any additional content: .Sh NAME .Nm bsort , .Nm bsort_b , .Nm bsort_r , .Nm bsort_s > +.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 radixsort 3 Same for SEE ALSO section: .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 > new file mode 100644 > index 000000000000..0c470654cfe7 > --- /dev/null > +++ b/lib/libc/stdlib/bsort.c > @@ -0,0 +1,267 @@ > +/*- > + * 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 > new file mode 100644 > index 000000000000..762f3c5aa1ec > --- /dev/null > +++ b/lib/libc/stdlib/bsort_r.c > @@ -0,0 +1,25 @@ > +/* > + * 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 > new file mode 100644 > index 000000000000..57abde76a257 > --- /dev/null > +++ b/lib/libc/stdlib/bsort_s.c > @@ -0,0 +1,5 @@ > +/* > + * This file is in the public domain. > + */ > +#define I_AM_BSORT_S > +#include "bsort.c"