The branch main has been updated by kfv: URL: https://cgit.FreeBSD.org/src/commit/?id=d59c7ea2701fe7b73b32eef49a7c712ef38de5a0
commit d59c7ea2701fe7b73b32eef49a7c712ef38de5a0 Author: Faraz Vahedi <[email protected]> AuthorDate: 2026-08-22 15:01:27 +0000 Commit: Faraz Vahedi <[email protected]> CommitDate: 2026-08-22 15:01:27 +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 --- 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 d61e2de99693..a384956eb435 100644 --- a/include/stdlib.h +++ b/include/stdlib.h @@ -411,6 +411,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 */ @@ -428,6 +431,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 7ff6a6c46ea5..497f163acf96 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 \ @@ -109,6 +110,8 @@ MLINKS+=abs.3 labs.3 \ abs.3 llabs.3 \ abs.3 imaxabs.3 MLINKS+=atol.3 atoll.3 +MLINKS+=bsearch.3 bsearch_b.3 \ + bsearch.3 bsearch_s.3 MLINKS+=div.3 ldiv.3 \ div.3 lldiv.3 \ div.3 imaxdiv.3 diff --git a/lib/libc/stdlib/Symbol.map b/lib/libc/stdlib/Symbol.map index df4922f1df60..be063fea8707 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 <stddef.h> #include <stdlib.h> +#ifdef I_AM_BSEARCH_S +#include <errno.h> +#include <stdint.h> +#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 <[email protected]> + * + * 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 1a0206bcdab9..00836dd0259c 100644 --- a/lib/libc/tests/stdlib/Makefile +++ b/lib/libc/tests/stdlib/Makefile @@ -1,5 +1,10 @@ .include <src.opts.mk> +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 @@ -66,7 +71,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 <[email protected]> + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +/* + * Test for bsearch_b() routine. + */ + +#include <stdlib.h> + +#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 <[email protected]> + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +/* + * Test for bsearch_s() routine. + */ + +#include <stdint.h> +#include <stdlib.h> + +#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 <[email protected]> + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +/* + * Test for bsearch() routine. + */ + +#include <stdlib.h> + +#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 <[email protected]> + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#ifndef _TEST_SEARCH_H +#define _TEST_SEARCH_H + +#include <sys/param.h> + +#include <stddef.h> + +#include <atf-c.h> + +#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 */
