Page MenuHomeFreeBSD
Files F167389650

D58876.id184396.diff
No OneTemporary
Actions

D58876.id184396.diff
View Options

diff --git a/include/stdlib.h b/include/stdlib.h
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -411,6 +411,9 @@
/* 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 @@
(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
--- a/lib/libc/stdlib/Makefile.inc
+++ b/lib/libc/stdlib/Makefile.inc
@@ -13,6 +13,7 @@
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 @@
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
--- a/lib/libc/stdlib/Symbol.map
+++ b/lib/libc/stdlib/Symbol.map
@@ -132,6 +132,7 @@
};
FBSD_1.9 {
+ bsearch_s;
memalignment;
recallocarray;
strfromd;
diff --git a/lib/libc/stdlib/bsearch.3 b/lib/libc/stdlib/bsearch.3
--- 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 @@
.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 @@
.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,12 @@
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.
diff --git a/lib/libc/stdlib/bsearch.c b/lib/libc/stdlib/bsearch.c
--- 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 @@
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 @@
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
--- /dev/null
+++ b/lib/libc/stdlib/bsearch_s.c
@@ -0,0 +1,7 @@
+/*
+ * Copyright (c) 2026 Faraz Vahedi <kfv@FreeBSD.org>
+ *
+ * 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
--- 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 @@
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
--- /dev/null
+++ b/lib/libc/tests/stdlib/bsearch_b_test.c
@@ -0,0 +1,58 @@
+/*
+ * Copyright (c) 2026 Faraz Vahedi <kfv@FreeBSD.org>
+ *
+ * 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
--- /dev/null
+++ b/lib/libc/tests/stdlib/bsearch_s_test.c
@@ -0,0 +1,134 @@
+/*
+ * Copyright (c) 2026 Faraz Vahedi <kfv@FreeBSD.org>
+ *
+ * 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 e;
+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
+h(const char * restrict msg __unused, void * restrict ptr __unused,
+ errno_t error)
+{
+ e = 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)
+{
+ e = 0;
+ compar_calls = 0;
+ ATF_CHECK(bsearch_s(key, base, nmemb, size, compar, thunk) == NULL);
+ ATF_CHECK(e > 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(h);
+ 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 };
+
+ e = 0;
+ compar_calls = 0;
+ set_constraint_handler_s(h);
+ ATF_CHECK(bsearch_s(&key, b, 0, sizeof(int), searchhelp_s,
+ &thunk) == NULL);
+ ATF_CHECK(e == 0);
+ ATF_CHECK_EQ(compar_calls, 0);
+ ATF_CHECK(bsearch_s(NULL, NULL, 0, 0, NULL, NULL) == NULL);
+ ATF_CHECK(e == 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;
+
+ e = 0;
+ compar_calls = 0;
+ set_constraint_handler_s(h);
+ found = bsearch_s(&key, b, nitems(b), sizeof(int), searchhelp_s,
+ &thunk);
+ ATF_CHECK(e == 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
--- /dev/null
+++ b/lib/libc/tests/stdlib/bsearch_test.c
@@ -0,0 +1,92 @@
+/*
+ * Copyright (c) 2026 Faraz Vahedi <kfv@FreeBSD.org>
+ *
+ * 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
--- /dev/null
+++ b/lib/libc/tests/stdlib/test-search.h
@@ -0,0 +1,51 @@
+/*
+ * Copyright (c) 2026 Faraz Vahedi <kfv@FreeBSD.org>
+ *
+ * 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 */

File Metadata

Mime Type
text/plain
Expires
Sat, Aug 22, 12:24 PM (2 h, 38 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
37042966
Default Alt Text
D58876.id184396.diff (15 KB)

Event Timeline