1*d59c7ea2SFaraz Vahedi /*
2*d59c7ea2SFaraz Vahedi * Copyright (c) 2026 Faraz Vahedi <kfv@FreeBSD.org>
3*d59c7ea2SFaraz Vahedi *
4*d59c7ea2SFaraz Vahedi * SPDX-License-Identifier: BSD-2-Clause
5*d59c7ea2SFaraz Vahedi */
6*d59c7ea2SFaraz Vahedi
7*d59c7ea2SFaraz Vahedi /*
8*d59c7ea2SFaraz Vahedi * Test for bsearch() routine.
9*d59c7ea2SFaraz Vahedi */
10*d59c7ea2SFaraz Vahedi
11*d59c7ea2SFaraz Vahedi #include <stdlib.h>
12*d59c7ea2SFaraz Vahedi
13*d59c7ea2SFaraz Vahedi #include "test-search.h"
14*d59c7ea2SFaraz Vahedi
15*d59c7ea2SFaraz Vahedi static const void *expected_key;
16*d59c7ea2SFaraz Vahedi static const void *expected_base;
17*d59c7ea2SFaraz Vahedi static size_t expected_nmemb;
18*d59c7ea2SFaraz Vahedi
19*d59c7ea2SFaraz Vahedi static int
searchhelp_check(const void * a,const void * b)20*d59c7ea2SFaraz Vahedi searchhelp_check(const void *a, const void *b)
21*d59c7ea2SFaraz Vahedi {
22*d59c7ea2SFaraz Vahedi const char *p, *base;
23*d59c7ea2SFaraz Vahedi
24*d59c7ea2SFaraz Vahedi ATF_CHECK(a == expected_key);
25*d59c7ea2SFaraz Vahedi p = b;
26*d59c7ea2SFaraz Vahedi base = expected_base;
27*d59c7ea2SFaraz Vahedi ATF_CHECK(((size_t)(p - base) % sizeof(int)) == 0);
28*d59c7ea2SFaraz Vahedi ATF_CHECK(p >= base);
29*d59c7ea2SFaraz Vahedi ATF_CHECK(p < base + expected_nmemb * sizeof(int));
30*d59c7ea2SFaraz Vahedi return (searchhelp(a, b));
31*d59c7ea2SFaraz Vahedi }
32*d59c7ea2SFaraz Vahedi
33*d59c7ea2SFaraz Vahedi static int
searchhelp_never(const void * a __unused,const void * b __unused)34*d59c7ea2SFaraz Vahedi searchhelp_never(const void *a __unused, const void *b __unused)
35*d59c7ea2SFaraz Vahedi {
36*d59c7ea2SFaraz Vahedi atf_tc_fail("comparison function invoked unexpectedly");
37*d59c7ea2SFaraz Vahedi return (0);
38*d59c7ea2SFaraz Vahedi }
39*d59c7ea2SFaraz Vahedi
40*d59c7ea2SFaraz Vahedi static void *
do_bsearch(const int * key,const int * base,size_t n,void * ctx __unused)41*d59c7ea2SFaraz Vahedi do_bsearch(const int *key, const int *base, size_t n, void *ctx __unused)
42*d59c7ea2SFaraz Vahedi {
43*d59c7ea2SFaraz Vahedi expected_key = key;
44*d59c7ea2SFaraz Vahedi return (bsearch(key, base, n, sizeof(int), searchhelp_check));
45*d59c7ea2SFaraz Vahedi }
46*d59c7ea2SFaraz Vahedi
47*d59c7ea2SFaraz Vahedi ATF_TC_WITHOUT_HEAD(bsearch_test);
ATF_TC_BODY(bsearch_test,tc)48*d59c7ea2SFaraz Vahedi ATF_TC_BODY(bsearch_test, tc)
49*d59c7ea2SFaraz Vahedi {
50*d59c7ea2SFaraz Vahedi int testvector[SVEC_LEN];
51*d59c7ea2SFaraz Vahedi int key, j;
52*d59c7ea2SFaraz Vahedi
53*d59c7ea2SFaraz Vahedi for (j = 0; j <= SVEC_LEN; j++) {
54*d59c7ea2SFaraz Vahedi if (j == 0) {
55*d59c7ea2SFaraz Vahedi key = 0;
56*d59c7ea2SFaraz Vahedi ATF_CHECK(bsearch(&key, testvector, 0,
57*d59c7ea2SFaraz Vahedi sizeof(testvector[0]), searchhelp_never) == NULL);
58*d59c7ea2SFaraz Vahedi continue;
59*d59c7ea2SFaraz Vahedi }
60*d59c7ea2SFaraz Vahedi expected_base = testvector;
61*d59c7ea2SFaraz Vahedi expected_nmemb = (size_t)j;
62*d59c7ea2SFaraz Vahedi check_sorted_search(do_bsearch, NULL, testvector, (size_t)j);
63*d59c7ea2SFaraz Vahedi }
64*d59c7ea2SFaraz Vahedi }
65*d59c7ea2SFaraz Vahedi
66*d59c7ea2SFaraz Vahedi ATF_TC_WITHOUT_HEAD(bsearch_duplicates);
ATF_TC_BODY(bsearch_duplicates,tc)67*d59c7ea2SFaraz Vahedi ATF_TC_BODY(bsearch_duplicates, tc)
68*d59c7ea2SFaraz Vahedi {
69*d59c7ea2SFaraz Vahedi int d[] = { 1, 2, 2, 2, 3 };
70*d59c7ea2SFaraz Vahedi int e[] = { 7, 7, 7 };
71*d59c7ea2SFaraz Vahedi int key, *found;
72*d59c7ea2SFaraz Vahedi
73*d59c7ea2SFaraz Vahedi key = 2;
74*d59c7ea2SFaraz Vahedi found = bsearch(&key, d, nitems(d), sizeof(d[0]), searchhelp);
75*d59c7ea2SFaraz Vahedi ATF_REQUIRE(found != NULL);
76*d59c7ea2SFaraz Vahedi ATF_CHECK(found >= &d[1] && found <= &d[3]);
77*d59c7ea2SFaraz Vahedi ATF_CHECK_EQ(*found, 2);
78*d59c7ea2SFaraz Vahedi
79*d59c7ea2SFaraz Vahedi key = 7;
80*d59c7ea2SFaraz Vahedi found = bsearch(&key, e, nitems(e), sizeof(e[0]), searchhelp);
81*d59c7ea2SFaraz Vahedi ATF_REQUIRE(found != NULL);
82*d59c7ea2SFaraz Vahedi ATF_CHECK(found >= &e[0] && found <= &e[2]);
83*d59c7ea2SFaraz Vahedi ATF_CHECK_EQ(*found, 7);
84*d59c7ea2SFaraz Vahedi }
85*d59c7ea2SFaraz Vahedi
ATF_TP_ADD_TCS(tp)86*d59c7ea2SFaraz Vahedi ATF_TP_ADD_TCS(tp)
87*d59c7ea2SFaraz Vahedi {
88*d59c7ea2SFaraz Vahedi ATF_TP_ADD_TC(tp, bsearch_test);
89*d59c7ea2SFaraz Vahedi ATF_TP_ADD_TC(tp, bsearch_duplicates);
90*d59c7ea2SFaraz Vahedi
91*d59c7ea2SFaraz Vahedi return (atf_no_error());
92*d59c7ea2SFaraz Vahedi }
93