The patch titled
Subject: lib/test_min_heap: add test for heap_del()
has been added to the -mm mm-nonmm-unstable branch. Its filename is
lib-test_min_heap-add-test-for-heap_del.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/lib-test_min_heap-add-test-for-heap_del.patch
This patch will later appear in the mm-nonmm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
Subject: lib/test_min_heap: add test for heap_del()
Date: Fri, 24 May 2024 23:29:56 +0800
Add test cases for the min_heap_del() to ensure its functionality is
thoroughly tested.
Link: https://lkml.kernel.org/r/20240524152958.919343-15-visitorckw@xxxxxxxxx
Signed-off-by: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
Reviewed-by: Ian Rogers <irogers@xxxxxxxxxx>
Cc: Adrian Hunter <adrian.hunter@xxxxxxxxx>
Cc: Alexander Shishkin <alexander.shishkin@xxxxxxxxxxxxxxx>
Cc: Arnaldo Carvalho de Melo <acme@xxxxxxxxxx>
Cc: Bagas Sanjaya <bagasdotme@xxxxxxxxx>
Cc: Brian Foster <bfoster@xxxxxxxxxx>
Cc: Ching-Chun (Jim) Huang <jserv@xxxxxxxxxxxxxxxx>
Cc: Coly Li <colyli@xxxxxxx>
Cc: Ingo Molnar <mingo@xxxxxxxxxx>
Cc: Jiri Olsa <jolsa@xxxxxxxxxx>
Cc: Kent Overstreet <kent.overstreet@xxxxxxxxx>
Cc: Mark Rutland <mark.rutland@xxxxxxx>
Cc: Matthew Sakai <msakai@xxxxxxxxxx>
Cc: Namhyung Kim <namhyung@xxxxxxxxxx>
Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Cc: Randy Dunlap <rdunlap@xxxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
lib/test_min_heap.c | 36 ++++++++++++++++++++++++++++++++++++
1 file changed, 36 insertions(+)
--- a/lib/test_min_heap.c~lib-test_min_heap-add-test-for-heap_del
+++ a/lib/test_min_heap.c
@@ -165,6 +165,40 @@ static __init int test_heap_pop_push(boo
return err;
}
+static __init int test_heap_del(bool min_heap)
+{
+ int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0,
+ -3, -1, -2, -4, 0x8000000, 0x7FFFFFF };
+ struct min_heap_test heap;
+
+ min_heap_init(&heap, values, ARRAY_SIZE(values));
+ heap.nr = ARRAY_SIZE(values);
+ struct min_heap_callbacks funcs = {
+ .less = min_heap ? less_than : greater_than,
+ .swp = swap_ints,
+ };
+ int i, err;
+
+ /* Test with known set of values. */
+ min_heapify_all(&heap, &funcs, NULL);
+ for (i = 0; i < ARRAY_SIZE(values) / 2; i++)
+ min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL);
+ err = pop_verify_heap(min_heap, &heap, &funcs);
+
+
+ /* Test with randomly generated values. */
+ heap.nr = ARRAY_SIZE(values);
+ for (i = 0; i < heap.nr; i++)
+ values[i] = get_random_u32();
+ min_heapify_all(&heap, &funcs, NULL);
+
+ for (i = 0; i < ARRAY_SIZE(values) / 2; i++)
+ min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL);
+ err += pop_verify_heap(min_heap, &heap, &funcs);
+
+ return err;
+}
+
static int __init test_min_heap_init(void)
{
int err = 0;
@@ -175,6 +209,8 @@ static int __init test_min_heap_init(voi
err += test_heap_push(false);
err += test_heap_pop_push(true);
err += test_heap_pop_push(false);
+ err += test_heap_del(true);
+ err += test_heap_del(false);
if (err) {
pr_err("test failed with %d errors\n", err);
return -EINVAL;
_
Patches currently in -mm which might be from visitorckw@xxxxxxxxx are
perf-core-fix-several-typos.patch
bcache-fix-typo.patch
bcachefs-fix-typo.patch
lib-min_heap-add-type-safe-interface.patch
lib-min_heap-add-min_heap_init.patch
lib-min_heap-add-min_heap_peek.patch
lib-min_heap-add-min_heap_full.patch
lib-min_heap-add-args-for-min_heap_callbacks.patch
lib-min_heap-add-min_heap_sift_up.patch
lib-min_heap-add-min_heap_del.patch
lib-min_heap-update-min_heap_push-and-min_heap_pop-to-return-bool-values.patch
lib-min_heap-rename-min_heapify-to-min_heap_sift_down.patch
lib-min_heap-update-min_heap_push-to-use-min_heap_sift_up.patch
lib-test_min_heap-add-test-for-heap_del.patch
bcache-remove-heap-related-macros-and-switch-to-generic-min_heap.patch
bcachefs-remove-heap-related-macros-and-switch-to-generic-min_heap.patch
