[PATCH] lib/tests: Add KUnit tests for bsearch()
however liu
The generic binary search function bsearch() has no unit tests, while
the adjacent sort() function already has KUnit test coverage.
Add comprehensive KUnit tests covering:
- Empty arrays, single-element arrays
- First/middle/last element hits
- Keys outside the array range and in gaps between elements
- Duplicate elements and all-identical arrays
- Different element sizes (u8, int, u64)
- Descending-order arrays with reversed comparator
- Struct-based search where key type differs from element type
The tests exercise both the exported bsearch() and the inline
__inline_bsearch() implementation through the standard API.
Signed-off-by: Liu Zhuoran <liuho...@gmail.com>
---
lib/Kconfig.debug | 10 ++
lib/tests/Makefile | 1 +
lib/tests/bsearch_kunit.c | 275 ++++++++++++++++++++++++++++++++++++++
3 files changed, 286 insertions(+)
create mode 100644 lib/tests/bsearch_kunit.c
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 8ff5adcfe..67d600e86 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2348,6 +2348,16 @@ config TEST_SORT
If unsure, say N.
+config BSEARCH_KUNIT_TEST
+ tristate "Array-based bsearch test" if !KUNIT_ALL_TESTS
+ depends on KUNIT
+ default KUNIT_ALL_TESTS
+ help
+ This option enables the KUnit test for 'bsearch()' at boot,
+ or at module load time.
+
+ If unsure, say N.
+
config TEST_DIV64
tristate "64bit/32bit division and modulo test"
depends on DEBUG_KERNEL || m
diff --git a/lib/tests/Makefile b/lib/tests/Makefile
index 7e9c2fa52..4c8b758ef 100644
--- a/lib/tests/Makefile
+++ b/lib/tests/Makefile
@@ -5,6 +5,7 @@
# KUnit tests
CFLAGS_bitfield_kunit.o := $(DISABLE_STRUCTLEAK_PLUGIN)
obj-$(CONFIG_BASE64_KUNIT) += base64_kunit.o
+obj-$(CONFIG_BSEARCH_KUNIT_TEST) += bsearch_kunit.o
obj-$(CONFIG_BITOPS_KUNIT) += bitops_kunit.o
obj-$(CONFIG_BITFIELD_KUNIT) += bitfield_kunit.o
obj-$(CONFIG_BITS_TEST) += test_bits.o
diff --git a/lib/tests/bsearch_kunit.c b/lib/tests/bsearch_kunit.c
new file mode 100644
index 000000000..b3b1d5d98
--- /dev/null
+++ b/lib/tests/bsearch_kunit.c
@@ -0,0 +1,275 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * KUnit tests for bsearch()
+ */
+
+#include <kunit/test.h>
+#include <linux/bsearch.h>
+#include <linux/module.h>
+
+static int cmp_int(const void *a, const void *b)
+{
+ return *(int *)a - *(int *)b;
+}
+
+static int cmp_int_desc(const void *a, const void *b)
+{
+ return *(int *)b - *(int *)a;
+}
+
+/* Empty array should return NULL */
+static void bsearch_test_empty(struct kunit *test)
+{
+ int arr[] = {1};
+ int key = 1;
+ void *result;
+
+ result = bsearch(&key, arr, 0, sizeof(int), cmp_int);
+ KUNIT_EXPECT_PTR_EQ(test, result, NULL);
+}
+
+/* Single element: found */
+static void bsearch_test_single_hit(struct kunit *test)
+{
+ int arr[] = {42};
+ int key = 42;
+ void *result;
+
+ result = bsearch(&key, arr, 1, sizeof(int), cmp_int);
+ KUNIT_EXPECT_NOT_NULL(test, result);
+ KUNIT_EXPECT_EQ(test, *(int *)result, 42);
+}
+
+/* Single element: not found */
+static void bsearch_test_single_miss(struct kunit *test)
+{
+ int arr[] = {42};
+ int key = 99;
+ void *result;
+
+ result = bsearch(&key, arr, 1, sizeof(int), cmp_int);
+ KUNIT_EXPECT_PTR_EQ(test, result, NULL);
+}
+
+/* Multi-element: key at beginning */
+static void bsearch_test_first_element(struct kunit *test)
+{
+ int arr[] = {10, 20, 30, 40, 50};
+ int key = 10;
+ void *result;
+
+ result = bsearch(&key, arr, 5, sizeof(int), cmp_int);
+ KUNIT_EXPECT_NOT_NULL(test, result);
+ KUNIT_EXPECT_EQ(test, *(int *)result, 10);
+}
+
+/* Multi-element: key at end */
+static void bsearch_test_last_element(struct kunit *test)
+{
+ int arr[] = {10, 20, 30, 40, 50};
+ int key = 50;
+ void *result;
+
+ result = bsearch(&key, arr, 5, sizeof(int), cmp_int);
+ KUNIT_EXPECT_NOT_NULL(test, result);
+ KUNIT_EXPECT_EQ(test, *(int *)result, 50);
+}
+
+/* Multi-element: key in the middle */
+static void bsearch_test_middle_element(struct kunit *test)
+{
+ int arr[] = {10, 20, 30, 40, 50};
+ int key = 30;
+ void *result;
+
+ result = bsearch(&key, arr, 5, sizeof(int), cmp_int);
+ KUNIT_EXPECT_NOT_NULL(test, result);
+ KUNIT_EXPECT_EQ(test, *(int *)result, 30);
+}
+
+/* Key smaller than all elements */
+static void bsearch_test_below_range(struct kunit *test)
+{
+ int arr[] = {10, 20, 30};
+ int key = 5;
+ void *result;
+
+ result = bsearch(&key, arr, 3, sizeof(int), cmp_int);
+ KUNIT_EXPECT_PTR_EQ(test, result, NULL);
+}
+
+/* Key larger than all elements */
+static void bsearch_test_above_range(struct kunit *test)
+{
+ int arr[] = {10, 20, 30};
however liu
+ void *result;
+
+ result = bsearch(&key, arr, 3, sizeof(int), cmp_int);
+ KUNIT_EXPECT_PTR_EQ(test, result, NULL);
+}
+
+static void bsearch_test_in_gap(struct kunit *test)
+{
+ int arr[] = {10, 20, 30, 40, 50};
+ void *result;
+
+ result = bsearch(&key, arr, 5, sizeof(int), cmp_int);
+}
+
+static void bsearch_test_duplicates(struct kunit *test)
+{
+ int arr[] = {10, 20, 20, 20, 30};
+ int key = 20;
+ void *result;
+
+ result = bsearch(&key, arr, 5, sizeof(int), cmp_int);
+ KUNIT_EXPECT_NOT_NULL(test, result);
+}
+
+/* All elements identical */
+static void bsearch_test_all_same(struct kunit *test)
+{
+ int arr[] = {7, 7, 7, 7};
+ int key = 7;
+ void *result;
+
+ result = bsearch(&key, arr, 4, sizeof(int), cmp_int);
+ KUNIT_EXPECT_NOT_NULL(test, result);
+ KUNIT_EXPECT_EQ(test, *(int *)result, 7);
+}
+
+/* Descending order with reversed comparator */
+static void bsearch_test_descending(struct kunit *test)
+{
+ int arr[] = {50, 40, 30, 20, 10};
+ int key = 30;
+ void *result;
+
+ KUNIT_EXPECT_NOT_NULL(test, result);
+ KUNIT_EXPECT_EQ(test, *(int *)result, 30);
+}
+
+static int cmp_u8(const void *a, const void *b)
+{
+ return *(u8 *)a - *(u8 *)b;
+}
+
+static void bsearch_test_u8(struct kunit *test)
+{
+ u8 arr[] = {1, 3, 5, 7, 9, 11};
+ u8 key = 7;
+ void *result;
+
+ result = bsearch(&key, arr, 6, sizeof(u8), cmp_u8);
+ KUNIT_EXPECT_NOT_NULL(test, result);
+ KUNIT_EXPECT_EQ(test, *(u8 *)result, (u8)7);
+}
+
+/* 8-byte elements (u64) */
+static int cmp_u64(const void *a, const void *b)
+{
+ if (*(u64 *)a < *(u64 *)b)
+ return -1;
+ if (*(u64 *)a > *(u64 *)b)
+ return 1;
+ return 0;
+}
+
+static void bsearch_test_u64(struct kunit *test)
+{
+ u64 arr[] = {100, 200, 300, 400, 500};
+ u64 key = 300;
+ void *result;
+
+ result = bsearch(&key, arr, 5, sizeof(u64), cmp_u64);
+ KUNIT_EXPECT_NOT_NULL(test, result);
+ KUNIT_EXPECT_EQ(test, *(u64 *)result, (u64)300);
+}
+
+/* Two elements: hit first, hit last, miss */
+static void bsearch_test_two_elements(struct kunit *test)
+{
+ int arr[] = {10, 20};
+ int key;
+ void *result;
+
+ key = 10;
+ result = bsearch(&key, arr, 2, sizeof(int), cmp_int);
+ KUNIT_EXPECT_NOT_NULL(test, result);
+ KUNIT_EXPECT_EQ(test, *(int *)result, 10);
+
+ result = bsearch(&key, arr, 2, sizeof(int), cmp_int);
+ KUNIT_EXPECT_NOT_NULL(test, result);
+ KUNIT_EXPECT_EQ(test, *(int *)result, 20);
+
+ key = 15;
+ result = bsearch(&key, arr, 2, sizeof(int), cmp_int);
+ KUNIT_EXPECT_PTR_EQ(test, result, NULL);
+}
+
+struct sample {
+ int id;
+ const char *name;
+};
+
+static int cmp_sample(const void *key, const void *element)
+{
+ return *(const int *)key - ((const struct sample *)element)->id;
+}
+
+static void bsearch_test_struct(struct kunit *test)
+{
+ struct sample arr[] = {
+ {10, "alpha"},
+ {20, "beta"},
+ {30, "gamma"},
+ {40, "delta"},
+ };
+ int key = 30;
+
+ result = bsearch(&key, arr, 4, sizeof(struct sample), cmp_sample);
+ KUNIT_ASSERT_NOT_NULL(test, result);
+ KUNIT_EXPECT_EQ(test, result->id, 30);
+ KUNIT_EXPECT_STREQ(test, result->name, "gamma");
+}
+
+static struct kunit_case bsearch_test_cases[] = {
+ KUNIT_CASE(bsearch_test_empty),
+ KUNIT_CASE(bsearch_test_single_hit),
+ KUNIT_CASE(bsearch_test_single_miss),
+ KUNIT_CASE(bsearch_test_first_element),
+ KUNIT_CASE(bsearch_test_last_element),
+ KUNIT_CASE(bsearch_test_middle_element),
+ KUNIT_CASE(bsearch_test_below_range),
+ KUNIT_CASE(bsearch_test_above_range),
+ KUNIT_CASE(bsearch_test_in_gap),
+ KUNIT_CASE(bsearch_test_duplicates),
+ KUNIT_CASE(bsearch_test_all_same),
+ KUNIT_CASE(bsearch_test_descending),
+ KUNIT_CASE(bsearch_test_u8),
+ KUNIT_CASE(bsearch_test_u64),
+ KUNIT_CASE(bsearch_test_two_elements),
+ KUNIT_CASE(bsearch_test_struct),
+ {}
+};
+
+static struct kunit_suite bsearch_test_suite = {
+ .name = "bsearch",
+ .test_cases = bsearch_test_cases,
+};
+
+kunit_test_suites(&bsearch_test_suite);
+
+MODULE_DESCRIPTION("KUnit tests for bsearch()");
+MODULE_LICENSE("GPL");
--
2.54.0