From nobody Tue Sep 22 19:01:34 2026 X-Original-To: dev-commits-src-branches@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 4hq8b32s39z6svrG for ; Tue, 22 Sep 2026 19:01:35 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (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-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "YR2" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id 4hq8b30K0rz4Rmx for ; Tue, 22 Sep 2026 19:01:35 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1790103695; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=9lyEdI+d93GcUt25mLb7RScAqo7wznxxp/pfyG/qWd0=; b=iroLBb0vMtEACN0GqMbgk8bVwbnH9ByJzaZvXlynQTrhqFOgk9+PBfOdZErK7zQi3ucgju VULdbNXY2gM2eKSWT3bjLMcxyJRMkonttoTwYDoq28TLdipZVEooRNb3DlGQd+6dtFmorC OK56AJKUWsnCOmUADZWJ35/cgsPOYPX3t4qV34X3jV+lMl0vTZM9OAmeXqmF6ASf2K6JgG 4g0/8cEUXSdNjziCZlrJ28iqCdyn8JLup5scHt33P5tz+5u5GlGlgFgJiiCuBt269qDCzj 1QgjJFmkM3N7+sgs+qAYes+4XlPED+rDD1pPnZBDFuiFQxBmzsIJ2L0fTFAP1A== ARC-Seal: i=1; a=rsa-sha256; d=freebsd.org; s=dkim; cv=none; t=1790103695; b=iox9cQ9eVlAILu0KWdJtkDEY0ws0lFg62PkAb5n+NCac+fAsA3nkBh/uD6iZzg9KTmq4bm qc0yvXxonUM3R7Lx/ph+6kWAipESCXq5p4UHI1UD078ghdTBjf2z8UEjZvrVzCw8s0xvTZ VqfdJiU/XmTW4lsLCN6B0TyqMwo1lKCcUsxctrxKDko9RbHKtVeHBberqVD5mYWn/QMRmA AYZ9ClXjMp9Cq932ls4XwVqIKRIdAmIn35DWrBnHOZGDfFhQKu3XYz2ROb0lH+5TZpgzml xPwfW5PjpujyO8c/Z1kaIchEQ71JRVGulxJQk9wmLQlj/sq3UFSkrdDAW5WV/g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1790103695; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=9lyEdI+d93GcUt25mLb7RScAqo7wznxxp/pfyG/qWd0=; b=ljzCoFp2Tovd0uNe/BwpqU3o9vLXtzNSi8UF5Tx7BphXcKhJLbLVaL/UbdxfObVCVpoL5W kIYznYxxE9VgsFweeSNh/Qz5f/End3TdMFcuxtlKNyByjWLQlCWKVhZ6LcFX85cMTEGseE Bmjx16i+usceGwBUQlb6ZYGjFCzgX5EtYRMLDOPp5WHGfu/7c+ZopQXd0jwX8dFLJfC4GX qNw6+z24h4Xrk4YBUUIW/eEBChNLAb4bMFPFEy6IBnNJuk4nPMNqKjwAdJoyv+suj8jOmX D5bTOjzJvln2Xo9t4Sb2FgeD9y0McFpg880vrqeYpsrLgCUZDNbJQkFS6vgj3w== ARC-Authentication-Results: i=1; mx1.freebsd.org; none Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) by mxrelay.nyi.freebsd.org (Postfix) with ESMTP id 4hq8b26T9RzK6f for ; Tue, 22 Sep 2026 19:01:34 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from git (uid 1279) (envelope-from git@FreeBSD.org) id 18f62 by gitrepo.freebsd.org (DragonFly Mail Agent v0.13+ on gitrepo.freebsd.org); Tue, 22 Sep 2026 19:01:34 +0000 To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Faraz Vahedi Subject: git: 91973f51fc6a - stable/15 - libc: Implement bsearch_s(), document bsearch_b(), and add unit tests List-Id: Commits to the stable branches of the FreeBSD src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-branches List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-branches@freebsd.org Sender: owner-dev-commits-src-branches@FreeBSD.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: kfv X-Git-Repository: src X-Git-Refname: refs/heads/stable/15 X-Git-Reftype: branch X-Git-Commit: 91973f51fc6a8a8ff3205d971a5b97726f05ad5d Auto-Submitted: auto-generated Date: Tue, 22 Sep 2026 19:01:34 +0000 Message-Id: <6ab2d08e.18f62.69ed7224@gitrepo.freebsd.org> The branch stable/15 has been updated by kfv: URL: https://cgit.FreeBSD.org/src/commit/?id=91973f51fc6a8a8ff3205d971a5b97726f05ad5d commit 91973f51fc6a8a8ff3205d971a5b97726f05ad5d Author: Faraz Vahedi AuthorDate: 2026-08-22 15:01:27 +0000 Commit: Faraz Vahedi CommitDate: 2026-09-22 17:26:14 +0000 libc: Implement bsearch_s(), document bsearch_b(), and add unit tests - Implement bsearch_s() as per §K.3.6.3.2 in C23, first specified in C11. It behaves identically to bsearch(), except the callback is called with a third argument, context, which is passed through from the caller, and it also performs runtime constraint checking on its arguments. - Document bsearch_b(), bsearch_s(), and add history section - Add rudimentary unit tests for bsearch(), bsearch_b(), and bsearch_s() Reviewed by: dteske, fuz Approved by: dteske (mentor), fuz (mentor) MFC after: 1 month Differential Revision: https://reviews.freebsd.org/D58876 (cherry picked from commit d59c7ea2701fe7b73b32eef49a7c712ef38de5a0) --- include/stdlib.h | 10 +++ lib/libc/stdlib/Makefile.inc | 3 + lib/libc/stdlib/Symbol.map | 1 + lib/libc/stdlib/bsearch.3 | 108 ++++++++++++++++++++++++-- lib/libc/stdlib/bsearch.c | 38 ++++++++++ lib/libc/stdlib/bsearch_s.c | 7 ++ lib/libc/tests/stdlib/Makefile | 7 +- lib/libc/tests/stdlib/bsearch_b_test.c | 58 ++++++++++++++ lib/libc/tests/stdlib/bsearch_s_test.c | 134 +++++++++++++++++++++++++++++++++ lib/libc/tests/stdlib/bsearch_test.c | 92 ++++++++++++++++++++++ lib/libc/tests/stdlib/test-search.h | 51 +++++++++++++ 11 files changed, 503 insertions(+), 6 deletions(-) diff --git a/include/stdlib.h b/include/stdlib.h index 01a56b32116a..68f8c989333c 100644 --- a/include/stdlib.h +++ b/include/stdlib.h @@ -409,6 +409,9 @@ _Noreturn void abort_handler_s(const char * __restrict, void * __restrict, /* K3.6.1.3 */ void ignore_handler_s(const char * __restrict, void * __restrict, errno_t); /* K.3.6.3.2 */ +void *bsearch_s(const void *, const void *, rsize_t, rsize_t, + int (*)(const void *, const void *, void *), void *); +/* K.3.6.3.3 */ errno_t qsort_s(void *, rsize_t, rsize_t, int (*)(const void *, const void *, void *), void *); #endif /* __EXT1_VISIBLE */ @@ -426,6 +429,13 @@ __NULLABILITY_PRAGMA_POP (const void *)(bsearch_b)((key), (base), (nmemb), (size), (compar)), \ (bsearch_b)((key), (base), (nmemb), (size), (compar))) #endif +#if __EXT1_VISIBLE +#define bsearch_s(key, base, nmemb, size, compar, context) \ + __qualsel((base), \ + (const void *)(bsearch_s)((key), (base), (nmemb), (size), \ + (compar), (context)), \ + (bsearch_s)((key), (base), (nmemb), (size), (compar), (context))) +#endif #endif #endif /* !_STDLIB_H_ */ diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc index 4fb304259012..3275c48370ef 100644 --- a/lib/libc/stdlib/Makefile.inc +++ b/lib/libc/stdlib/Makefile.inc @@ -13,6 +13,7 @@ MISRCS+= \ atoll.c \ bsearch.c \ bsearch_b.c \ + bsearch_s.c \ cxa_thread_atexit.c \ cxa_thread_atexit_impl.c \ div.c \ @@ -106,6 +107,8 @@ MAN+= a64l.3 abort.3 abs.3 atexit.3 atof.3 \ MLINKS+=a64l.3 l64a.3 \ a64l.3 l64a_r.3 MLINKS+=atol.3 atoll.3 +MLINKS+=bsearch.3 bsearch_b.3 \ + bsearch.3 bsearch_s.3 MLINKS+=exit.3 _Exit.3 MLINKS+=getenv.3 clearenv.3 \ getenv.3 putenv.3 \ diff --git a/lib/libc/stdlib/Symbol.map b/lib/libc/stdlib/Symbol.map index 229f1d0c5b65..4816be000ece 100644 --- a/lib/libc/stdlib/Symbol.map +++ b/lib/libc/stdlib/Symbol.map @@ -132,6 +132,7 @@ FBSD_1.8 { }; FBSD_1.9 { + bsearch_s; memalignment; recallocarray; strfromd; diff --git a/lib/libc/stdlib/bsearch.3 b/lib/libc/stdlib/bsearch.3 index 4d1e7b1171b9..814b71028af0 100644 --- a/lib/libc/stdlib/bsearch.3 +++ b/lib/libc/stdlib/bsearch.3 @@ -29,11 +29,13 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.Dd June 21, 2026 +.Dd August 15, 2026 .Dt BSEARCH 3 .Os .Sh NAME -.Nm bsearch +.Nm bsearch , +.Nm bsearch_b , +.Nm bsearch_s .Nd binary search of a sorted table .Sh LIBRARY .Lb libc @@ -41,6 +43,11 @@ .In stdlib.h .Ft "QVoid *" .Fn bsearch "const void *key" "QVoid *base" "size_t nmemb" "size_t size" "int (*compar) (const void *, const void *)" +.Ft "QVoid *" +.Fn bsearch_b "const void *key" "QVoid *base" "size_t nmemb" "size_t size" "int (^compar) (const void *, const void *)" +.Fd #define __STDC_WANT_LIB_EXT1__ 1 +.Ft "QVoid *" +.Fn bsearch_s "const void *key" "QVoid *base" "rsize_t nmemb" "rsize_t size" "int (*compar) (const void *, const void *, void *)" "void *context" .Sh DESCRIPTION The .Fn bsearch @@ -74,11 +81,68 @@ sample function in .Xr qsort 3 for a comparison function that is also compatible with .Fn bsearch . +.Pp +The +.Fn bsearch_b +function behaves identically to +.Fn bsearch , +except the callback +.Fa compar +takes a block pointer instead of a function pointer. +.Pp +The +.Fn bsearch_s +function behaves identically to +.Fn bsearch , +except the callback +.Fa compar +is called with a third argument, +.Fa context , +which is passed through from the caller. +Runtime-constraint violation occurs if: +.Bl -bullet +.It +.Fa nmemb +or +.Fa size +is greater than +.Dv RSIZE_MAX +.It +.Fa nmemb +is not zero and any of +.Fa key , +.Fa base , +or +.Fa compar +is a null pointer +.El +.Pp +On a runtime-constraint violation, the runtime-constraint handler is +invoked, +.Fn bsearch_s +does not search the array, and a null pointer is returned. +Note that the handler is called before +.Fn bsearch_s +returns, and the handler function might not return. +If +.Fa nmemb +is zero, the comparison function is not called, no match is found, +and +.Fa key , +.Fa base , +and +.Fa compar +may be null pointers. .Sh RETURN VALUES The -.Fn bsearch -function returns a pointer to a matching member of the array, or a null +.Fn bsearch , +.Fn bsearch_b , +and +.Fn bsearch_s +functions return a pointer to a matching member of the array, or a null pointer if no match is found. +.Fn bsearch_s +also returns a null pointer if there is a runtime-constraint violation. If two members compare as equal, which member is matched is unspecified. .Sh EXAMPLES A sample program that searches people by age in a sorted array: @@ -147,7 +211,8 @@ main(void) .Sh SEE ALSO .Xr db 3 , .Xr lsearch 3 , -.Xr qsort 3 +.Xr qsort 3 , +.Xr set_constraint_handler_s 3 .\" .Xr tsearch 3 .Sh STANDARDS The @@ -155,3 +220,36 @@ The function conforms to .St -isoC-2023 , where it is specified as a qualifier-preserving function. +.Pp +The +.Fn bsearch_s +function conforms to +.St -isoC-2023 , +section K.3.6.3.2. +Like +.Fn bsearch , +it is specified as a qualifier-preserving function. +.Sh HISTORY +The +.Fn bsearch , +initially specified in the +.St -svid1 , +first appeared in +.At V.2 +and later in +.Bx 4.3 . +It was first standardized in +.St -isoC . +.Pp +The +.Fn bsearch_b +function first appeared in Mac OS X and was later added to +.Fx 11.0 +as an extension. +.Pp +The +.Fn bsearch_s +function first appeared in +.Fx 16.0 . +It was first standardized in +.St -isoC-2011 . diff --git a/lib/libc/stdlib/bsearch.c b/lib/libc/stdlib/bsearch.c index 96c728e1c997..6bfd44d4df6d 100644 --- a/lib/libc/stdlib/bsearch.c +++ b/lib/libc/stdlib/bsearch.c @@ -32,10 +32,18 @@ #include #include +#ifdef I_AM_BSEARCH_S +#include +#include +#include "libc_private.h" +#endif + #ifdef I_AM_BSEARCH_B #include "block_abi.h" #define COMPAR(x,y) CALL_BLOCK(compar, x, y) typedef DECLARE_BLOCK(int, compar_block, const void *, const void *); +#elif defined(I_AM_BSEARCH_S) +#define COMPAR(x,y) compar((x), (y), context) #else #define COMPAR(x,y) compar(x, y) #endif @@ -60,6 +68,10 @@ typedef DECLARE_BLOCK(int, compar_block, const void *, const void *); void * bsearch_b(const void *key, const void *base0, size_t nmemb, size_t size, compar_block compar) +#elif defined(I_AM_BSEARCH_S) +void * +bsearch_s(const void *key, const void *base0, rsize_t nmemb, rsize_t size, + int (*compar)(const void *, const void *, void *), void *context) #else void * bsearch(const void *key, const void *base0, size_t nmemb, size_t size, @@ -71,6 +83,32 @@ bsearch(const void *key, const void *base0, size_t nmemb, size_t size, int cmp; const void *p; +#ifdef I_AM_BSEARCH_S + if (nmemb > RSIZE_MAX) { + __throw_constraint_handler_s("bsearch_s : nmemb > RSIZE_MAX", + EINVAL); + return (NULL); + } else if (size > RSIZE_MAX) { + __throw_constraint_handler_s("bsearch_s : size > RSIZE_MAX", + EINVAL); + return (NULL); + } else if (nmemb != 0) { + if (key == NULL) { + __throw_constraint_handler_s("bsearch_s : key == NULL", + EINVAL); + return (NULL); + } else if (base0 == NULL) { + __throw_constraint_handler_s("bsearch_s : base == NULL", + EINVAL); + return (NULL); + } else if (compar == NULL) { + __throw_constraint_handler_s("bsearch_s : compar == NULL", + EINVAL); + return (NULL); + } + } +#endif + for (lim = nmemb; lim != 0; lim >>= 1) { p = base + (lim >> 1) * size; cmp = COMPAR(key, p); diff --git a/lib/libc/stdlib/bsearch_s.c b/lib/libc/stdlib/bsearch_s.c new file mode 100644 index 000000000000..03722ffe6370 --- /dev/null +++ b/lib/libc/stdlib/bsearch_s.c @@ -0,0 +1,7 @@ +/* + * Copyright (c) 2026 Faraz Vahedi + * + * SPDX-License-Identifier: BSD-2-Clause + */ +#define I_AM_BSEARCH_S +#include "bsearch.c" diff --git a/lib/libc/tests/stdlib/Makefile b/lib/libc/tests/stdlib/Makefile index 52d74ee33a76..8a17fc159d49 100644 --- a/lib/libc/tests/stdlib/Makefile +++ b/lib/libc/tests/stdlib/Makefile @@ -1,5 +1,10 @@ .include +ATF_TESTS_C+= bsearch_test +.if ${COMPILER_FEATURES:Mblocks} +ATF_TESTS_C+= bsearch_b_test +.endif +ATF_TESTS_C+= bsearch_s_test ATF_TESTS_C+= clearenv_test ATF_TESTS_C+= cxa_atexit_test ATF_TESTS_C+= dynthr_test @@ -65,7 +70,7 @@ CFLAGS+= -I${.CURDIR} LIBADD.cxa_thread_atexit_test+= pthread # Tests that require blocks support -.for t in qsort_b_test +.for t in bsearch_b_test qsort_b_test CFLAGS.${t}.c+= -fblocks LIBADD.${t}+= BlocksRuntime .endfor diff --git a/lib/libc/tests/stdlib/bsearch_b_test.c b/lib/libc/tests/stdlib/bsearch_b_test.c new file mode 100644 index 000000000000..4c04a723f639 --- /dev/null +++ b/lib/libc/tests/stdlib/bsearch_b_test.c @@ -0,0 +1,58 @@ +/* + * Copyright (c) 2026 Faraz Vahedi + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +/* + * Test for bsearch_b() routine. + */ + +#include + +#include "test-search.h" + +#define THUNK 42 + +static void * +do_bsearch_b(const int *key, const int *base, size_t n, void *ctx) +{ + int thunk = *(int *)ctx; + + return (bsearch_b(key, base, n, sizeof(int), + ^(const void *a, const void *b) { + ATF_REQUIRE_EQ(thunk, THUNK); + return (searchhelp(a, b)); + })); +} + +ATF_TC_WITHOUT_HEAD(bsearch_b_test); +ATF_TC_BODY(bsearch_b_test, tc) +{ + int testvector[SVEC_LEN]; + int thunk = THUNK; + int key, j; + + for (j = 0; j <= SVEC_LEN; j++) { + if (j == 0) { + key = 0; + ATF_CHECK(bsearch_b(&key, testvector, 0, + sizeof(testvector[0]), + ^(const void *a __unused, const void *b __unused) { + atf_tc_fail( + "comparison block invoked unexpectedly"); + return (0); + }) == NULL); + continue; + } + check_sorted_search(do_bsearch_b, &thunk, testvector, + (size_t)j); + } +} + +ATF_TP_ADD_TCS(tp) +{ + ATF_TP_ADD_TC(tp, bsearch_b_test); + + return (atf_no_error()); +} diff --git a/lib/libc/tests/stdlib/bsearch_s_test.c b/lib/libc/tests/stdlib/bsearch_s_test.c new file mode 100644 index 000000000000..b41343400ba3 --- /dev/null +++ b/lib/libc/tests/stdlib/bsearch_s_test.c @@ -0,0 +1,134 @@ +/* + * Copyright (c) 2026 Faraz Vahedi + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +/* + * Test for bsearch_s() routine. + */ + +#include +#include + +#define THUNK 42 + +#include "test-search.h" + +static errno_t error_code; +static int compar_calls; + +static int +searchhelp_s(const void *a, const void *b, void *thunk) +{ + compar_calls++; + if (thunk != NULL) + ATF_REQUIRE_EQ(*(int *)thunk, THUNK); + return (searchhelp(a, b)); +} + +static void +constraint_handler(const char * restrict msg __unused, + void * restrict ptr __unused, errno_t error) +{ + error_code = error; +} + +static void +expect_viol(const void *key, const void *base, rsize_t nmemb, rsize_t size, + int (*compar)(const void *, const void *, void *), void *thunk) +{ + error_code = 0; + compar_calls = 0; + ATF_CHECK(bsearch_s(key, base, nmemb, size, compar, thunk) == NULL); + ATF_CHECK(error_code > 0); + ATF_CHECK_EQ(compar_calls, 0); +} + +static void * +do_bsearch_s(const int *key, const int *base, size_t n, void *ctx) +{ + return (bsearch_s(key, base, n, sizeof(int), searchhelp_s, ctx)); +} + +ATF_TC_WITHOUT_HEAD(bsearch_s_constraints); +ATF_TC_BODY(bsearch_s_constraints, tc) +{ + int thunk = THUNK; + int key = 4; + int b[] = { 4, 7, 81 }; + + set_constraint_handler_s(constraint_handler); + expect_viol(&key, b, -1, sizeof(int), searchhelp_s, &thunk); + expect_viol(&key, b, RSIZE_MAX + 1, sizeof(int), searchhelp_s, &thunk); + expect_viol(&key, b, nitems(b), -1, searchhelp_s, &thunk); + expect_viol(&key, b, nitems(b), RSIZE_MAX + 1, searchhelp_s, &thunk); + expect_viol(NULL, b, nitems(b), sizeof(int), searchhelp_s, &thunk); + expect_viol(&key, NULL, 1, sizeof(int), searchhelp_s, &thunk); + expect_viol(&key, b, nitems(b), sizeof(int), NULL, &thunk); + /* size > RSIZE_MAX is a violation even when nmemb is zero. */ + expect_viol(&key, b, 0, RSIZE_MAX + 1, searchhelp_s, &thunk); +} + +ATF_TC_WITHOUT_HEAD(bsearch_s_nmemb_zero); +ATF_TC_BODY(bsearch_s_nmemb_zero, tc) +{ + int thunk = THUNK; + int key = 4; + int b[] = { 4, 7, 81 }; + + error_code = 0; + compar_calls = 0; + set_constraint_handler_s(constraint_handler); + ATF_CHECK(bsearch_s(&key, b, 0, sizeof(int), searchhelp_s, + &thunk) == NULL); + ATF_CHECK(error_code == 0); + ATF_CHECK_EQ(compar_calls, 0); + ATF_CHECK(bsearch_s(NULL, NULL, 0, 0, NULL, NULL) == NULL); + ATF_CHECK(error_code == 0); +} + +ATF_TC_WITHOUT_HEAD(bsearch_s_h); +ATF_TC_BODY(bsearch_s_h, tc) +{ + int thunk = THUNK; + int b[] = { 4, 7, 81 }; + int key = 7; + int *found; + + error_code = 0; + compar_calls = 0; + set_constraint_handler_s(constraint_handler); + found = bsearch_s(&key, b, nitems(b), sizeof(int), searchhelp_s, + &thunk); + ATF_CHECK(error_code == 0); + ATF_CHECK(compar_calls > 0); + ATF_CHECK(found == &b[1]); + + compar_calls = 0; + found = bsearch_s(&key, b, nitems(b), sizeof(int), searchhelp_s, NULL); + ATF_CHECK(found == &b[1]); + ATF_CHECK(compar_calls > 0); +} + +ATF_TC_WITHOUT_HEAD(bsearch_s_test); +ATF_TC_BODY(bsearch_s_test, tc) +{ + int testvector[SVEC_LEN]; + int thunk = THUNK; + int j; + + for (j = 1; j <= SVEC_LEN; j++) + check_sorted_search(do_bsearch_s, &thunk, testvector, + (size_t)j); +} + +ATF_TP_ADD_TCS(tp) +{ + ATF_TP_ADD_TC(tp, bsearch_s_constraints); + ATF_TP_ADD_TC(tp, bsearch_s_nmemb_zero); + ATF_TP_ADD_TC(tp, bsearch_s_h); + ATF_TP_ADD_TC(tp, bsearch_s_test); + + return (atf_no_error()); +} diff --git a/lib/libc/tests/stdlib/bsearch_test.c b/lib/libc/tests/stdlib/bsearch_test.c new file mode 100644 index 000000000000..6da8096b85a9 --- /dev/null +++ b/lib/libc/tests/stdlib/bsearch_test.c @@ -0,0 +1,92 @@ +/* + * Copyright (c) 2026 Faraz Vahedi + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +/* + * Test for bsearch() routine. + */ + +#include + +#include "test-search.h" + +static const void *expected_key; +static const void *expected_base; +static size_t expected_nmemb; + +static int +searchhelp_check(const void *a, const void *b) +{ + const char *p, *base; + + ATF_CHECK(a == expected_key); + p = b; + base = expected_base; + ATF_CHECK(((size_t)(p - base) % sizeof(int)) == 0); + ATF_CHECK(p >= base); + ATF_CHECK(p < base + expected_nmemb * sizeof(int)); + return (searchhelp(a, b)); +} + +static int +searchhelp_never(const void *a __unused, const void *b __unused) +{ + atf_tc_fail("comparison function invoked unexpectedly"); + return (0); +} + +static void * +do_bsearch(const int *key, const int *base, size_t n, void *ctx __unused) +{ + expected_key = key; + return (bsearch(key, base, n, sizeof(int), searchhelp_check)); +} + +ATF_TC_WITHOUT_HEAD(bsearch_test); +ATF_TC_BODY(bsearch_test, tc) +{ + int testvector[SVEC_LEN]; + int key, j; + + for (j = 0; j <= SVEC_LEN; j++) { + if (j == 0) { + key = 0; + ATF_CHECK(bsearch(&key, testvector, 0, + sizeof(testvector[0]), searchhelp_never) == NULL); + continue; + } + expected_base = testvector; + expected_nmemb = (size_t)j; + check_sorted_search(do_bsearch, NULL, testvector, (size_t)j); + } +} + +ATF_TC_WITHOUT_HEAD(bsearch_duplicates); +ATF_TC_BODY(bsearch_duplicates, tc) +{ + int d[] = { 1, 2, 2, 2, 3 }; + int e[] = { 7, 7, 7 }; + int key, *found; + + key = 2; + found = bsearch(&key, d, nitems(d), sizeof(d[0]), searchhelp); + ATF_REQUIRE(found != NULL); + ATF_CHECK(found >= &d[1] && found <= &d[3]); + ATF_CHECK_EQ(*found, 2); + + key = 7; + found = bsearch(&key, e, nitems(e), sizeof(e[0]), searchhelp); + ATF_REQUIRE(found != NULL); + ATF_CHECK(found >= &e[0] && found <= &e[2]); + ATF_CHECK_EQ(*found, 7); +} + +ATF_TP_ADD_TCS(tp) +{ + ATF_TP_ADD_TC(tp, bsearch_test); + ATF_TP_ADD_TC(tp, bsearch_duplicates); + + return (atf_no_error()); +} diff --git a/lib/libc/tests/stdlib/test-search.h b/lib/libc/tests/stdlib/test-search.h new file mode 100644 index 000000000000..3d805585eaae --- /dev/null +++ b/lib/libc/tests/stdlib/test-search.h @@ -0,0 +1,51 @@ +/* + * Copyright (c) 2026 Faraz Vahedi + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#ifndef _TEST_SEARCH_H +#define _TEST_SEARCH_H + +#include + +#include + +#include + +#define SVEC_LEN 1024 + +typedef void *search_int_t(const int *, const int *, size_t, void *); + +static int +searchhelp(const void *a, const void *b) +{ + const int *oa = a, *ob = b; + + return ((*oa > *ob) - (*oa < *ob)); +} + +/* + * Fill v[i] = i, then confirm every element is found and -1 and n are not. + */ +static void +check_sorted_search(search_int_t *search, void *ctx, int *v, size_t n) +{ + size_t i; + int key; + + for (i = 0; i < n; i++) + v[i] = (int)i; + for (i = 0; i < n; i++) { + key = v[i]; + ATF_CHECK(search(&key, v, n, ctx) == &v[i]); + } + if (n != 0) { + key = -1; + ATF_CHECK(search(&key, v, n, ctx) == NULL); + key = (int)n; + ATF_CHECK(search(&key, v, n, ctx) == NULL); + } +} + +#endif /* !_TEST_SEARCH_H */