From patchwork Mon Apr 28 16:21:49 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: hypatia.sva@posteo.eu X-Patchwork-Id: 111183 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0A7683857BB3 for ; Mon, 28 Apr 2025 16:49:07 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0A7683857BB3 Authentication-Results: sourceware.org; dkim=pass (2048-bit key, secure) header.d=posteo.eu header.i=@posteo.eu header.a=rsa-sha256 header.s=2017 header.b=V66M9Hn8 X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mout02.posteo.de (mout02.posteo.de [185.67.36.66]) by sourceware.org (Postfix) with ESMTPS id DA07F3858CD9 for ; Mon, 28 Apr 2025 16:21:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org DA07F3858CD9 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=posteo.eu Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=posteo.eu ARC-Filter: OpenARC Filter v1.0.0 sourceware.org DA07F3858CD9 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=185.67.36.66 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1745857312; cv=none; b=kI2nFC6Kf0YAMXM/Xvtck63O9FOBe/TofNa8d5lYWrjiPB+qzsBlGzlwwgdfwjsMpNff3OYX6o6Nb23wrCCBxgwND8NCihcRwgdpcn8EvdCaNvJQYQKFZftxXP6P/zNp5RrOMyKZH2QOHP5eWecRwCMfVpms12Q2V1MQlIBj4L0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1745857312; c=relaxed/simple; bh=TezvwYc4lHS8XUSthqEDcx7xy/0utTNUZXfIA5D0pEE=; h=DKIM-Signature:MIME-Version:Date:From:To:Subject:Message-ID; b=oE6K5nsL63YFoCcfC0iVizlgyNPpViGiN128mL5HUkAFjwdBwqmjrFXMMprwbtOXNB1XWJ03TtcbZ1sSDD2eigflrnk+h7R+kfUdUY7YmRwUy6jikBxyhpdSzxlb561zkd5A59hzAPFLVbzZmb+FZ8kqdRKQYVo8GTqwZ9YsmN0= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from submission (posteo.de [185.67.36.169]) by mout02.posteo.de (Postfix) with ESMTPS id 4B4A3240101 for ; Mon, 28 Apr 2025 18:21:49 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.eu; s=2017; t=1745857310; bh=TezvwYc4lHS8XUSthqEDcx7xy/0utTNUZXfIA5D0pEE=; h=MIME-Version:Date:From:To:Subject:Message-ID:Content-Type: Content-Transfer-Encoding:From; b=V66M9Hn8kx+mqmIl1hRb7ckGfgbucuSe2nZbVadzjaQ359o6y8Qd/vEwb50J0u4aG PtzFIBylqMUjcIhn67AEAEaBqYt2PCaVbwzFlznxyrwlT5O2EExPvJdxH9aKP9J27v B09Uw5UJu/7uyCZKvPbm1uxKnjuZwxib/m8WtxghernXFCg6zmCLuS77K/V4rTtE2A Va8OkkNQvNEcWO+99HN+2+GmGUuYnU0gI3WwaWZWgJ+wCKZRAzuFAkeHH6BBzPXvIA XF1oYlQVJRYtEuccLXtrOecFSZntUG4zqZ/LOuwNImKfljMGTIy3W7I1oCZS1qZmvT UjjzoZ8FMHuug== Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4ZmTH14876z6v0l for ; Mon, 28 Apr 2025 18:21:49 +0200 (CEST) MIME-Version: 1.0 Date: Mon, 28 Apr 2025 16:21:49 +0000 From: hypatia.sva@posteo.eu To: libc-alpha@sourceware.org Subject: [PATCH-idea] qsort and bsearch variants for built-in types Message-ID: X-Spam-Status: No, score=-2.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, KAM_LOTSOFHASH, PROLO_LEO1, RCVD_IN_VALIDITY_RPBL_BLOCKED, RCVD_IN_VALIDITY_SAFE_BLOCKED, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces~patchwork=sourceware.org@sourceware.org Hello glibc-developers, I don't know if this is exactly the right mailing list for new feature / implementation proposals for glibc, but since it is the main list for development we thought we should give it a go, We thought about why bsearch and qsort, although builtin features of libc, are almost never used. The main reason for me personally was always that it seemed kind of silly to give a new cmp-function for floats or integers, since the function call would likely be much slower than the actual comparison instruction, so I would usually just roll my own, likely technically less efficient search and sort. However, there would be an easy solution to this: add dedicated variants for qsort and bsearch for the built-in types that have no need for indirect calls to a comparison function! I did write a prototype of this that _should_ work, but since I'm no glibc developer there might be something about the way glibc is built that makes this in need of more additions. Also this code is not very optimized and doesn't have documentation or tests. Feedback is appreciated, also as to how I should move with this or if you think this is appropriate at all to be posted/suggested here. WIth regards, Hypatia of Sva. Patch: +#endif +extern float * bsearch_float (float __key, const float * __base, size_t __nmemb) __nonnull ((2)); +extern double * bsearch_double (double __key, const double * __base, size_t __nmemb) __nonnull ((2)); +#endif + #ifdef __USE_EXTERN_INLINES # include #endif @@ -973,6 +988,18 @@ extern void qsort_r (void *__base, size_t __nmemb, size_t __size, __compar_d_fn_t __compar, void *__arg) __nonnull ((1, 4)); +#ifdef _STDINT_H +extern void qsort_int8_t (int8_t *const __base, size_t __nmemb) __nonnull ((1)); +extern void qsort_uint8_t (uint8_t *const __base, size_t __nmemb) __nonnull ((1)); +extern void qsort_int16_t (int16_t *const __base, size_t __nmemb) __nonnull ((1)); +extern void qsort_uint16_t(uint16_t *const __base, size_t __nmemb) __nonnull ((1)); +extern void qsort_int32_t (int32_t *const __base, size_t __nmemb) __nonnull ((1)); +extern void qsort_uint32_t(uint32_t *const __base, size_t __nmemb) __nonnull ((1)); +extern void qsort_int64_t (int64_t *const __base, size_t __nmemb) __nonnull ((1)); +extern void qsort_uint64_t(uint64_t *const __base, size_t __nmemb) __nonnull ((1)); +#endif +extern void qsort_float (float *const __base, size_t __nmemb) __nonnull ((1)); +extern void qsort_double (double *const __base, size_t __nmemb) __nonnull ((1)); #endif diff -bur a/bits/stdlib-bsearch.h b/bits/stdlib-bsearch.h --- a/bits/stdlib-bsearch.h 2025-04-28 09:55:22.355824635 +0200 +++ b/bits/stdlib-bsearch.h 2025-04-28 18:00:59.724154783 +0200 @@ -48,3 +48,163 @@ return NULL; } + +#ifdef __USE_GNU + +#define _SEARCH_FUNCTION_TOKENIZE(A,B) A ## B +#define SEARCH_FUNCTION_TOKENIZE(A,B) _SEARCH_FUNCTION_TOKENIZE(A,B) + +#define DEFINE_SEARCH_FUNCTION_PART_1(T) \ +__extern_inline T * \ +SEARCH_FUNCTION_TOKENIZE(__bsearch_,T) (T __key, const T *__base, size_t __nmemb) \ +{ \ + const T *__p; \ + \ + while (__nmemb) \ + { \ + __p = __base[(__nmemb >> 1)]; \ + if (__key == __p[0] ) \ + { \ + + +#define DEFINE_SEARCH_FUNCTION_PART_2(T) \ + return (T *) __p; \ + + +#define DEFINE_SEARCH_FUNCTION_PART_3(T) \ + } \ + if (__key > __p[0]) \ + { \ + __base = &(__p[1]); \ + --__nmemb; \ + } \ + __nmemb >>= 1; \ + } \ + \ + return NULL; \ +} \ + + +#ifdef _STDINT_H + +DEFINE_SEARCH_FUNCTION_PART_1(int8_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wcast-qual" +#endif +DEFINE_SEARCH_FUNCTION_PART_2(int8_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic pop +#endif +DEFINE_SEARCH_FUNCTION_PART_3(int8_t) + +DEFINE_SEARCH_FUNCTION_PART_1(uint8_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wcast-qual" +#endif +DEFINE_SEARCH_FUNCTION_PART_2(uint8_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic pop +#endif +DEFINE_SEARCH_FUNCTION_PART_3(uint8_t) + +DEFINE_SEARCH_FUNCTION_PART_1(int16_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wcast-qual" +#endif +DEFINE_SEARCH_FUNCTION_PART_2(int16_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic pop +#endif +DEFINE_SEARCH_FUNCTION_PART_3(int16_t) + +DEFINE_SEARCH_FUNCTION_PART_1(uint16_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wcast-qual" +#endif +DEFINE_SEARCH_FUNCTION_PART_2(uint16_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic pop +#endif +DEFINE_SEARCH_FUNCTION_PART_3(uint16_t) + +DEFINE_SEARCH_FUNCTION_PART_1(int32_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wcast-qual" +#endif +DEFINE_SEARCH_FUNCTION_PART_2(int32_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic pop +#endif +DEFINE_SEARCH_FUNCTION_PART_3(int32_t) + +DEFINE_SEARCH_FUNCTION_PART_1(uint32_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wcast-qual" +#endif +DEFINE_SEARCH_FUNCTION_PART_2(uint32_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic pop +#endif +DEFINE_SEARCH_FUNCTION_PART_3(uint32_t) + +DEFINE_SEARCH_FUNCTION_PART_1(int64_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wcast-qual" +#endif +DEFINE_SEARCH_FUNCTION_PART_2(int64_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic pop +#endif +DEFINE_SEARCH_FUNCTION_PART_3(int64_t) + +DEFINE_SEARCH_FUNCTION_PART_1(uint64_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wcast-qual" +#endif +DEFINE_SEARCH_FUNCTION_PART_2(uint64_t) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic pop +#endif +DEFINE_SEARCH_FUNCTION_PART_3(uint64_t) + +#endif + +DEFINE_SEARCH_FUNCTION_PART_1(float) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wcast-qual" +#endif +DEFINE_SEARCH_FUNCTION_PART_2(float) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic pop +#endif +DEFINE_SEARCH_FUNCTION_PART_3(float) + +DEFINE_SEARCH_FUNCTION_PART_1(double) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wcast-qual" +#endif +DEFINE_SEARCH_FUNCTION_PART_2(double) +#if __GNUC_PREREQ(4, 6) +# pragma GCC diagnostic pop +#endif +DEFINE_SEARCH_FUNCTION_PART_3(double) + + +#undef DEFINE_SEARCH_FUNCTION_PART_1 +#undef DEFINE_SEARCH_FUNCTION_PART_2 +#undef DEFINE_SEARCH_FUNCTION_PART_3 +#undef SEARCH_FUNCTION_TOKENIZE +#undef _SEARCH_FUNCTION_TOKENIZE + + +#endif Binärdateien a/.git/index und b/.git/index sind verschieden. diff -bur a/.git/logs/HEAD b/.git/logs/HEAD --- a/.git/logs/HEAD 2025-04-28 10:01:12.823144879 +0200 +++ b/.git/logs/HEAD 2025-04-28 10:01:20.987205087 +0200 @@ -1,3 +1,3 @@ 0000000000000000000000000000000000000000 77930e0447e0b37a129db0e13c6c6f5e60a3019e Sva 1745826922 +0200 clone: from https://sourceware.org/git/glibc.git 77930e0447e0b37a129db0e13c6c6f5e60a3019e 77930e0447e0b37a129db0e13c6c6f5e60a3019e Sva 1745826955 +0200 checkout: moving from master to master -77930e0447e0b37a129db0e13c6c6f5e60a3019e 77930e0447e0b37a129db0e13c6c6f5e60a3019e Sva 1745827272 +0200 checkout: moving from master to master +77930e0447e0b37a129db0e13c6c6f5e60a3019e 77930e0447e0b37a129db0e13c6c6f5e60a3019e Sva 1745827280 +0200 checkout: moving from master to master diff -bur a/include/stdlib.h b/include/stdlib.h --- a/include/stdlib.h 2025-04-28 09:55:22.571824500 +0200 +++ b/include/stdlib.h 2025-04-28 18:05:12.349677803 +0200 @@ -90,9 +90,50 @@ extern __typeof (secure_getenv) __libc_secure_getenv; libc_hidden_proto (__libc_secure_getenv) libc_hidden_proto (bsearch) +extern __typeof (bsearch_int8_t ) __bsearch_int8_t ; +extern __typeof (bsearch_uint8_t ) __bsearch_uint8_t ; +extern __typeof (bsearch_int16_t ) __bsearch_int16_t ; +extern __typeof (bsearch_uint16_t) __bsearch_uint16_t; +extern __typeof (bsearch_int32_t ) __bsearch_int32_t ; +extern __typeof (bsearch_uint32_t) __bsearch_uint32_t; +extern __typeof (bsearch_int64_t ) __bsearch_int64_t ; +extern __typeof (bsearch_uint64_t) __bsearch_uint64_t; +extern __typeof (bsearch_float ) __bsearch_float ; +extern __typeof (bsearch_double ) __bsearch_double ; +libc_hidden_proto (__bsearch_int8_t ) +libc_hidden_proto (__bsearch_uint8_t ) +libc_hidden_proto (__bsearch_int16_t ) +libc_hidden_proto (__bsearch_uint16_t) +libc_hidden_proto (__bsearch_int32_t ) +libc_hidden_proto (__bsearch_uint32_t) +libc_hidden_proto (__bsearch_int64_t ) +libc_hidden_proto (__bsearch_uint64_t) +libc_hidden_proto (__bsearch_float ) +libc_hidden_proto (__bsearch_double ) + libc_hidden_proto (qsort) extern __typeof (qsort_r) __qsort_r; libc_hidden_proto (__qsort_r) +extern __typeof (qsort_int8_t ) __qsort_int8_t ; +extern __typeof (qsort_uint8_t ) __qsort_uint8_t ; +extern __typeof (qsort_int16_t ) __qsort_int16_t ; +extern __typeof (qsort_uint16_t) __qsort_uint16_t; +extern __typeof (qsort_int32_t ) __qsort_int32_t ; +extern __typeof (qsort_uint32_t) __qsort_uint32_t; +extern __typeof (qsort_int64_t ) __qsort_int64_t ; +extern __typeof (qsort_uint64_t) __qsort_uint64_t; +extern __typeof (qsort_float ) __qsort_float ; +extern __typeof (qsort_double ) __qsort_double ; +libc_hidden_proto (__qsort_int8_t ) +libc_hidden_proto (__qsort_uint8_t ) +libc_hidden_proto (__qsort_int16_t ) +libc_hidden_proto (__qsort_uint16_t) +libc_hidden_proto (__qsort_int32_t ) +libc_hidden_proto (__qsort_uint32_t) +libc_hidden_proto (__qsort_int64_t ) +libc_hidden_proto (__qsort_uint64_t) +libc_hidden_proto (__qsort_float ) +libc_hidden_proto (__qsort_double ) libc_hidden_proto (lrand48_r) libc_hidden_proto (wctomb) diff -bur a/stdlib/bsearch.c b/stdlib/bsearch.c --- a/stdlib/bsearch.c 2025-04-28 09:55:23.175823953 +0200 +++ b/stdlib/bsearch.c 2025-04-28 18:04:14.253319647 +0200 @@ -21,3 +21,25 @@ #define __extern_inline /* Empty, so we get a normal definition. */ #include libc_hidden_def (bsearch) + +libc_hidden_def(__bsearch_int8_t ) +libc_hidden_def(__bsearch_uint8_t ) +libc_hidden_def(__bsearch_int16_t ) +libc_hidden_def(__bsearch_uint16_t) +libc_hidden_def(__bsearch_int32_t ) +libc_hidden_def(__bsearch_uint32_t) +libc_hidden_def(__bsearch_int64_t ) +libc_hidden_def(__bsearch_uint64_t) +libc_hidden_def(__bsearch_float ) +libc_hidden_def(__bsearch_double ) + +weak_alias(__bsearch_int8_t , bsearch_int8_t ) +weak_alias(__bsearch_uint8_t , bsearch_uint8_t ) +weak_alias(__bsearch_int16_t , bsearch_int16_t ) +weak_alias(__bsearch_uint16_t, bsearch_uint16_t) +weak_alias(__bsearch_int32_t , bsearch_int32_t ) +weak_alias(__bsearch_uint32_t, bsearch_uint32_t) +weak_alias(__bsearch_int64_t , bsearch_int64_t ) +weak_alias(__bsearch_uint64_t, bsearch_uint64_t) +weak_alias(__bsearch_float , bsearch_float ) +weak_alias(__bsearch_double , bsearch_double ) diff -bur a/stdlib/qsort.c b/stdlib/qsort.c --- a/stdlib/qsort.c 2025-04-28 09:55:23.179823947 +0200 +++ b/stdlib/qsort.c 2025-04-28 17:39:52.316626215 +0200 @@ -424,3 +424,303 @@ return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL); } libc_hidden_def (qsort) + + + +#define _SORT_FUNCTION_TOKENIZE(A,B) A ## B +#define SORT_FUNCTION_TOKENIZE(A,B) _SORT_FUNCTION_TOKENIZE(A,B) + +#define DEFINE_SORT_FUNCTION(T) \ +static inline void \ +SORT_FUNCTION_TOKENIZE(siftdown_, T) (T *base, size_t k, size_t n, \ + enum swap_type_t swap_type) \ +{ \ + while (2 * k + 1 <= n) \ + { \ + size_t j = 2 * k + 1; \ + if (j < n && base[j] < base[j+1]) \ + j++; \ + \ + if (j == k || base[k] >= base[j]) \ + break; \ + \ + do_swap (&(base[j]), &(base[k]), sizeof(float), swap_type); \ + \ + k = j; \ + } \ +} \ + \ +static inline void \ +SORT_FUNCTION_TOKENIZE(heapify_, T) (T *base, size_t n, enum swap_type_t swap_type) \ +{ \ + size_t k = n / 2; \ + while (1) \ + { \ + SORT_FUNCTION_TOKENIZE(siftdown_, T) (base, k, n, swap_type); \ + if (k-- == 0) \ + break; \ + } \ +} \ + \ +static void \ +SORT_FUNCTION_TOKENIZE(heapsort_r_, T) (T *base, size_t n) \ +{ \ + if (n == 0) \ + return; \ + \ + enum swap_type_t swap_type = get_swap_type (base, sizeof(T)); \ + \ + SORT_FUNCTION_TOKENIZE(heapify_, T) (base, n, swap_type); \ + \ + while (true) \ + { \ + do_swap (base, base + (n * sizeof(T)), sizeof(T), swap_type); \ + \ + n--; \ + if (n == 0) \ + break; \ + \ + SORT_FUNCTION_TOKENIZE(siftdown_, T) (base, 0, n, swap_type); \ + } \ +} \ + \ +static void \ +SORT_FUNCTION_TOKENIZE(msort_with_tmp_, T) (const struct msort_param *p, void *b, \ + size_t n) \ +{ \ + char *b1, *b2; \ + size_t n1, n2; \ + \ + if (n <= 1) \ + return; \ + \ + n1 = n / 2; \ + n2 = n - n1; \ + b1 = b; \ + b2 = (char *) b + (n1 * p->s); \ + \ + SORT_FUNCTION_TOKENIZE(msort_with_tmp_, T) (p, b1, n1); \ + SORT_FUNCTION_TOKENIZE(msort_with_tmp_, T) (p, b2, n2); \ + \ + char *tmp = p->t; \ + const size_t s = p->s; \ + \ + void *arg = p->arg; \ + switch (p->var) \ + { \ + case SWAP_WORDS_32: \ + while (n1 > 0 && n2 > 0) \ + { \ + if (*((T*)b1) <= *((T*)b2)) \ + { \ + *(u32_alias_t *) tmp = *(u32_alias_t *) b1; \ + b1 += sizeof (u32_alias_t); \ + --n1; \ + } \ + else \ + { \ + *(u32_alias_t *) tmp = *(u32_alias_t *) b2; \ + b2 += sizeof (u32_alias_t); \ + --n2; \ + } \ + tmp += sizeof (u32_alias_t); \ + } \ + break; \ + case SWAP_WORDS_64: \ + while (n1 > 0 && n2 > 0) \ + { \ + if (*((T*)b1) <= *((T*)b2)) \ + { \ + *(u64_alias_t *) tmp = *(u64_alias_t *) b1; \ + b1 += sizeof (u64_alias_t); \ + --n1; \ + } \ + else \ + { \ + *(u64_alias_t *) tmp = *(u64_alias_t *) b2; \ + b2 += sizeof (u64_alias_t); \ + --n2; \ + } \ + tmp += sizeof (u64_alias_t); \ + } \ + break; \ + case SWAP_VOID_ARG: \ + while (n1 > 0 && n2 > 0) \ + { \ + if (*((T*)(*(const void **)b1)) <= *((T*)(*(const void **)b1))) \ + { \ + *(void **) tmp = *(void **) b1; \ + b1 += sizeof (void *); \ + --n1; \ + } \ + else \ + { \ + *(void **) tmp = *(void **) b2; \ + b2 += sizeof (void *); \ + --n2; \ + } \ + tmp += sizeof (void *); \ + } \ + break; \ + default: \ + while (n1 > 0 && n2 > 0) \ + { \ + if (*((T*)b1) <= *((T*)b2)) \ + { \ + tmp = (char *) __mempcpy (tmp, b1, s); \ + b1 += s; \ + --n1; \ + } \ + else \ + { \ + tmp = (char *) __mempcpy (tmp, b2, s); \ + b2 += s; \ + --n2; \ + } \ + } \ + break; \ + } \ + \ + if (n1 > 0) \ + memcpy (tmp, b1, n1 * s); \ + memcpy (b, p->t, (n - n2) * s); \ +} \ + \ + \ +static void \ +__attribute_used__ \ +SORT_FUNCTION_TOKENIZE(indirect_msort_with_tmp_, T) (const struct msort_param *p, \ + void *b, size_t n, size_t s) \ +{ \ + char *ip = (char *) b; \ + void **tp = (void **) (p->t + n * sizeof (void *)); \ + void **t = tp; \ + void *tmp_storage = (void *) (tp + n); \ + \ + while ((void *) t < tmp_storage) \ + { \ + *t++ = ip; \ + ip += s; \ + } \ + SORT_FUNCTION_TOKENIZE(msort_with_tmp_, T) (p, p->t + n * sizeof (void *), n); \ + \ + char *kp; \ + size_t i; \ + for (i = 0, ip = (char *) b; i < n; i++, ip += s) \ + if ((kp = tp[i]) != ip) \ + { \ + size_t j = i; \ + char *jp = ip; \ + memcpy (tmp_storage, ip, s); \ + \ + do \ + { \ + size_t k = (kp - (char *) b) / s; \ + tp[j] = jp; \ + memcpy (jp, kp, s); \ + j = k; \ + jp = kp; \ + kp = tp[k]; \ + } \ + while (kp != ip); \ + \ + tp[j] = jp; \ + memcpy (jp, tmp_storage, s); \ + } \ +} \ + \ +static void \ +SORT_FUNCTION_TOKENIZE(qsort_r_mergesort_, T) (T *const pbase, size_t total_elems, \ + void *buf) \ +{ \ + if (sizeof(T) > INDIRECT_SORT_SIZE_THRES) \ + { \ + const struct msort_param msort_param = \ + { \ + .s = sizeof (void *), \ + .cmp = NULL, \ + .arg = NULL, \ + .var = SWAP_VOID_ARG, \ + .t = buf, \ + }; \ + SORT_FUNCTION_TOKENIZE(indirect_msort_with_tmp_, T) (&msort_param, pbase, \ + total_elems, sizeof(T)); \ + } \ + else \ + { \ + const struct msort_param msort_param = \ + { \ + .s = sizeof(T), \ + .cmp = NULL, \ + .arg = NULL, \ + .var = get_swap_type (pbase, sizeof(T)), \ + .t = buf, \ + }; \ + SORT_FUNCTION_TOKENIZE(msort_with_tmp_, T) (&msort_param, pbase, \ + total_elems); \ + } \ +} \ + \ +static bool \ +SORT_FUNCTION_TOKENIZE(qsort_r_malloc_, T) (T *const pbase, size_t total_elems, \ + size_t total_size) \ +{ \ + int save = errno; \ + char *buf = malloc (total_size); \ + __set_errno (save); \ + if (buf == NULL) \ + return false; \ + \ + pthread_cleanup_combined_push (free, buf); \ + SORT_FUNCTION_TOKENIZE(qsort_r_mergesort_, T) (pbase, total_elems, buf); \ + pthread_cleanup_combined_pop (0); \ + \ + free (buf); \ + \ + return true; \ +} \ + \ +void \ +SORT_FUNCTION_TOKENIZE(__qsort_, T) (T *const pbase, size_t total_elems) \ +{ \ + if (total_elems <= 1) \ + return; \ + \ + size_t total_size = total_elems * sizeof(T); \ + \ + if (sizeof(T) > INDIRECT_SORT_SIZE_THRES) \ + total_size = 2 * total_elems * sizeof (void *) + sizeof(T); \ + \ + if (total_size <= QSORT_STACK_SIZE) \ + { \ + _Alignas (uint64_t) char tmp[QSORT_STACK_SIZE]; \ + SORT_FUNCTION_TOKENIZE(qsort_r_mergesort_, T) (pbase, total_elems, tmp); \ + } \ + else \ + { \ + if (!SORT_FUNCTION_TOKENIZE(qsort_r_malloc_, T) \ + (pbase, total_elems, arg, total_size)) \ + \ + SORT_FUNCTION_TOKENIZE(heapsort_r_, T) (pbase, total_elems - 1); \ + } \ +} \ + \ +libc_hidden_def (SORT_FUNCTION_TOKENIZE(__qsort_, T)) \ +weak_alias (SORT_FUNCTION_TOKENIZE(__qsort_, T), SORT_FUNCTION_TOKENIZE(qsort_, T)) \ + + +DEFINE_SORT_FUNCTION(int8_t) +DEFINE_SORT_FUNCTION(uint8_t) +DEFINE_SORT_FUNCTION(int16_t) +DEFINE_SORT_FUNCTION(uint16_t) +DEFINE_SORT_FUNCTION(int32_t) +DEFINE_SORT_FUNCTION(uint32_t) +DEFINE_SORT_FUNCTION(int64_t) +DEFINE_SORT_FUNCTION(uint64_t) + +DEFINE_SORT_FUNCTION(float) +DEFINE_SORT_FUNCTION(double) + +#undef DEFINE_SORT_FUNCTION +#undef SORT_FUNCTION_TOKENIZE +#undef _SORT_FUNCTION_TOKENIZE diff -bur a/stdlib/stdlib.h b/stdlib/stdlib.h --- a/stdlib/stdlib.h 2025-04-28 09:55:23.183823940 +0200 +++ b/stdlib/stdlib.h 2025-04-28 18:10:08.211553172 +0200 @@ -961,6 +961,21 @@ size_t __nmemb, size_t __size, __compar_fn_t __compar) __nonnull ((1, 2, 5)) __wur; +#ifdef __USE_GNU +#ifdef _STDINT_H +extern int8_t * bsearch_int8_t (int8_t __key, const int8_t * __base, size_t __nmemb) __nonnull ((2)); +extern uint8_t * bsearch_uint8_t (uint8_t __key, const uint8_t * __base, size_t __nmemb) __nonnull ((2)); +extern int16_t * bsearch_int16_t (int16_t __key, const int16_t * __base, size_t __nmemb) __nonnull ((2)); +extern uint16_t * bsearch_uint16_t(uint16_t __key, const uint16_t * __base, size_t __nmemb) __nonnull ((2)); +extern int32_t * bsearch_int32_t (int32_t __key, const int32_t * __base, size_t __nmemb) __nonnull ((2)); +extern uint32_t * bsearch_uint32_t(uint32_t __key, const uint32_t * __base, size_t __nmemb) __nonnull ((2)); +extern int64_t * bsearch_int64_t (int64_t __key, const int64_t * __base, size_t __nmemb) __nonnull ((2)); +extern uint64_t * bsearch_uint64_t(uint64_t __key, const uint64_t * __base, size_t __nmemb) __nonnull ((2));