From: Muhammed Dilshad A Date: Wed, 07 Oct 2026 13:50:24 GMT Subject: [PATCH v2 2/3] mergesort: move sorting tests to the unit-test framework Message-ID: <0429552774367ddcc3c2fda78e09a83650ccfa02.1791365181.git.dilsheddilu123@gmail.com> In-Reply-To: The mergesort certification checks exercise C code directly, so they do not need a shell test and test-tool command. Move their distributions and transformations to Clar, retaining the sorted-value, stability and list length checks. Add small cases for both list sort macros and debug hooks. Keep node storage available to the cleanup fixture and bound validation so a failed assertion can release it without walking a broken list. Remove the unused generate command along with the old test command, leaving sort available for the sorting benchmark. Suggested-by: Patrick Steinhardt Signed-off-by: Muhammed Dilshad A --- Makefile | 1 + t/helper/test-mergesort.c | 345 +--------------------------------- t/meson.build | 2 +- t/t0071-sort.sh | 18 -- t/unit-tests/u-mergesort.c | 369 +++++++++++++++++++++++++++++++++++++ 5 files changed, 372 insertions(+), 363 deletions(-) delete mode 100755 t/t0071-sort.sh create mode 100644 t/unit-tests/u-mergesort.c diff --git a/Makefile b/Makefile index a96be506b5..cac535ba19 100644 --- a/Makefile +++ b/Makefile @@ -1541,6 +1541,7 @@ CLAR_TEST_SUITES += u-hash CLAR_TEST_SUITES += u-hashmap CLAR_TEST_SUITES += u-list-objects-filter-options CLAR_TEST_SUITES += u-mem-pool +CLAR_TEST_SUITES += u-mergesort CLAR_TEST_SUITES += u-odb-inmemory CLAR_TEST_SUITES += u-oid-array CLAR_TEST_SUITES += u-oidmap diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 3b8c428b14..e8b8de239b 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -1,16 +1,8 @@ -#define DISABLE_SIGN_COMPARE_WARNINGS - #include "test-tool.h" #include "mem-pool.h" #include "mergesort.h" #include "strbuf.h" -static uint32_t minstd_rand(uint32_t *state) -{ - *state = (uint64_t)*state * 48271 % 2147483647; - return *state; -} - struct line { char *text; struct line *next; @@ -66,345 +58,10 @@ static int sort_stdin(void) return 0; } -static void dist_sawtooth(int *arr, int n, int m) -{ - int i; - for (i = 0; i < n; i++) - arr[i] = i % m; -} - -static void dist_rand(int *arr, int n, int m) -{ - int i; - uint32_t seed = 1; - for (i = 0; i < n; i++) - arr[i] = minstd_rand(&seed) % m; -} - -static void dist_stagger(int *arr, int n, int m) -{ - int i; - for (i = 0; i < n; i++) - arr[i] = (i * m + i) % n; -} - -static void dist_plateau(int *arr, int n, int m) -{ - int i; - for (i = 0; i < n; i++) - arr[i] = (i < m) ? i : m; -} - -static void dist_shuffle(int *arr, int n, int m) -{ - int i, j, k; - uint32_t seed = 1; - for (i = j = 0, k = 1; i < n; i++) - arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2); -} - -#define DIST(name) { #name, dist_##name } - -static struct dist { - const char *name; - void (*fn)(int *arr, int n, int m); -} dist[] = { - DIST(sawtooth), - DIST(rand), - DIST(stagger), - DIST(plateau), - DIST(shuffle), -}; - -static const struct dist *get_dist_by_name(const char *name) -{ - int i; - for (i = 0; i < ARRAY_SIZE(dist); i++) { - if (!strcmp(dist[i].name, name)) - return &dist[i]; - } - return NULL; -} - -static void mode_copy(int *arr UNUSED, int n UNUSED) -{ - /* nothing */ -} - -static void mode_reverse(int *arr, int n) -{ - int i, j; - for (i = 0, j = n - 1; i < j; i++, j--) - SWAP(arr[i], arr[j]); -} - -static void mode_reverse_1st_half(int *arr, int n) -{ - mode_reverse(arr, n / 2); -} - -static void mode_reverse_2nd_half(int *arr, int n) -{ - int half = n / 2; - mode_reverse(arr + half, n - half); -} - -static int compare_ints(const void *av, const void *bv) -{ - const int *ap = av, *bp = bv; - int a = *ap, b = *bp; - return (a > b) - (a < b); -} - -static void mode_sort(int *arr, int n) -{ - QSORT(arr, n, compare_ints); -} - -static void mode_dither(int *arr, int n) -{ - int i; - for (i = 0; i < n; i++) - arr[i] += i % 5; -} - -static void unriffle(int *arr, int n, int *tmp) -{ - int i, j; - COPY_ARRAY(tmp, arr, n); - for (i = j = 0; i < n; i += 2) - arr[j++] = tmp[i]; - for (i = 1; i < n; i += 2) - arr[j++] = tmp[i]; -} - -static void unriffle_recursively(int *arr, int n, int *tmp) -{ - if (n > 1) { - int half = n / 2; - unriffle(arr, n, tmp); - unriffle_recursively(arr, half, tmp); - unriffle_recursively(arr + half, n - half, tmp); - } -} - -static void mode_unriffle(int *arr, int n) -{ - int *tmp; - ALLOC_ARRAY(tmp, n); - unriffle_recursively(arr, n, tmp); - free(tmp); -} - -static unsigned int prev_pow2(unsigned int n) -{ - unsigned int pow2 = 1; - while (pow2 * 2 < n) - pow2 *= 2; - return pow2; -} - -static void unriffle_recursively_skewed(int *arr, int n, int *tmp) -{ - if (n > 1) { - int pow2 = prev_pow2(n); - int rest = n - pow2; - unriffle(arr + pow2 - rest, rest * 2, tmp); - unriffle_recursively_skewed(arr, pow2, tmp); - unriffle_recursively_skewed(arr + pow2, rest, tmp); - } -} - -static void mode_unriffle_skewed(int *arr, int n) -{ - int *tmp; - ALLOC_ARRAY(tmp, n); - unriffle_recursively_skewed(arr, n, tmp); - free(tmp); -} - -#define MODE(name) { #name, mode_##name } - -static struct mode { - const char *name; - void (*fn)(int *arr, int n); -} mode[] = { - MODE(copy), - MODE(reverse), - MODE(reverse_1st_half), - MODE(reverse_2nd_half), - MODE(sort), - MODE(dither), - MODE(unriffle), - MODE(unriffle_skewed), -}; - -static const struct mode *get_mode_by_name(const char *name) -{ - int i; - for (i = 0; i < ARRAY_SIZE(mode); i++) { - if (!strcmp(mode[i].name, name)) - return &mode[i]; - } - return NULL; -} - -static int generate(int argc, const char **argv) -{ - const struct dist *dist = NULL; - const struct mode *mode = NULL; - int i, n, m, *arr; - - if (argc != 4) - return 1; - - dist = get_dist_by_name(argv[0]); - mode = get_mode_by_name(argv[1]); - n = strtol(argv[2], NULL, 10); - m = strtol(argv[3], NULL, 10); - if (!dist || !mode) - return 1; - - ALLOC_ARRAY(arr, n); - dist->fn(arr, n, m); - mode->fn(arr, n); - for (i = 0; i < n; i++) - printf("%08x\n", arr[i]); - free(arr); - return 0; -} - -static struct stats { - int get_next, set_next, compare; -} stats; - -struct number { - int value, rank; - struct number *next; -}; - -DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next, - stats.get_next++, stats.set_next++); - -static int compare_numbers(const struct number *an, const struct number *bn) -{ - int a = an->value, b = bn->value; - stats.compare++; - return (a > b) - (a < b); -} - -static void clear_numbers(struct number *list) -{ - while (list) { - struct number *next = list->next; - free(list); - list = next; - } -} - -static int test(const struct dist *dist, const struct mode *mode, int n, int m) -{ - int *arr; - size_t i; - struct number *curr, *list, **tail; - int is_sorted = 1; - int is_stable = 1; - const char *verdict; - int result = -1; - - ALLOC_ARRAY(arr, n); - dist->fn(arr, n, m); - mode->fn(arr, n); - for (i = 0, tail = &list; i < n; i++) { - curr = xmalloc(sizeof(*curr)); - curr->value = arr[i]; - curr->rank = i; - *tail = curr; - tail = &curr->next; - } - *tail = NULL; - - stats.get_next = stats.set_next = stats.compare = 0; - sort_numbers(&list, compare_numbers); - - QSORT(arr, n, compare_ints); - for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) { - if (arr[i] != curr->value) - is_sorted = 0; - if (curr->next && curr->value == curr->next->value && - curr->rank >= curr->next->rank) - is_stable = 0; - } - if (i < n) { - verdict = "too short"; - } else if (curr) { - verdict = "too long"; - } else if (!is_sorted) { - verdict = "not sorted"; - } else if (!is_stable) { - verdict = "unstable"; - } else { - verdict = "OK"; - result = 0; - } - - printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n", - dist->name, mode->name, n, m, stats.get_next, stats.set_next, - stats.compare, verdict); - - clear_numbers(list); - free(arr); - - return result; -} - -/* - * A version of the qsort certification program from "Engineering a Sort - * Function" by Bentley and McIlroy, Software—Practice and Experience, - * Volume 23, Issue 11, 1249–1265 (November 1993). - */ -static int run_tests(int argc, const char **argv) -{ - const char *argv_default[] = { "100", "1023", "1024", "1025" }; - if (!argc) - return run_tests(ARRAY_SIZE(argv_default), argv_default); - printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n", - "distribut", "mode", "n", "m", "get_next", "set_next", - "compare", "verdict"); - while (argc--) { - int i, j, m, n = strtol(*argv++, NULL, 10); - for (i = 0; i < ARRAY_SIZE(dist); i++) { - for (j = 0; j < ARRAY_SIZE(mode); j++) { - for (m = 1; m < 2 * n; m *= 2) { - if (test(&dist[i], &mode[j], n, m)) - return 1; - } - } - } - } - return 0; -} - int cmd__mergesort(int argc, const char **argv) { - int i; - const char *sep; - - if (argc == 6 && !strcmp(argv[1], "generate")) - return generate(argc - 2, argv + 2); if (argc == 2 && !strcmp(argv[1], "sort")) return sort_stdin(); - if (argc > 1 && !strcmp(argv[1], "test")) - return run_tests(argc - 2, argv + 2); - fprintf(stderr, "usage: test-tool mergesort generate \n"); - fprintf(stderr, " or: test-tool mergesort sort\n"); - fprintf(stderr, " or: test-tool mergesort test [...]\n"); - fprintf(stderr, "\n"); - for (i = 0, sep = "distributions: "; i < ARRAY_SIZE(dist); i++, sep = ", ") - fprintf(stderr, "%s%s", sep, dist[i].name); - fprintf(stderr, "\n"); - for (i = 0, sep = "modes: "; i < ARRAY_SIZE(mode); i++, sep = ", ") - fprintf(stderr, "%s%s", sep, mode[i].name); - fprintf(stderr, "\n"); + fprintf(stderr, "usage: test-tool mergesort sort\n"); return 129; } diff --git a/t/meson.build b/t/meson.build index f65eb04684..2752321e0d 100644 --- a/t/meson.build +++ b/t/meson.build @@ -6,6 +6,7 @@ clar_test_suites = [ 'unit-tests/u-hashmap.c', 'unit-tests/u-list-objects-filter-options.c', 'unit-tests/u-mem-pool.c', + 'unit-tests/u-mergesort.c', 'unit-tests/u-odb-inmemory.c', 'unit-tests/u-oid-array.c', 'unit-tests/u-oidmap.c', @@ -119,7 +120,6 @@ integration_tests = [ 't0067-parse_pathspec_file.sh', 't0068-for-each-repo.sh', 't0070-fundamental.sh', - 't0071-sort.sh', 't0080-unit-test-output.sh', 't0081-find-pack.sh', 't0090-cache-tree.sh', diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh deleted file mode 100755 index 97890da29f..0000000000 --- a/t/t0071-sort.sh +++ /dev/null @@ -1,18 +0,0 @@ -#!/bin/sh - -test_description='verify sort functions' - -. ./test-lib.sh - -test_expect_success 'DEFINE_LIST_SORT_DEBUG' ' - test-tool mergesort test -' - -test_expect_success 'sort stdin' ' - printf "%s\n" c a b >input && - printf "%s\n" a b c >expect && - test-tool mergesort sort actual && - test_cmp expect actual -' - -test_done diff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c new file mode 100644 index 0000000000..e621c9ec21 --- /dev/null +++ b/t/unit-tests/u-mergesort.c @@ -0,0 +1,369 @@ +#include "unit-test.h" +#include "mergesort.h" + +static uint32_t minstd_rand(uint32_t *state) +{ + *state = (uint64_t)*state * 48271 % 2147483647; + return *state; +} + +static void dist_sawtooth(int *arr, int n, int m) +{ + int i; + for (i = 0; i < n; i++) + arr[i] = i % m; +} + +static void dist_rand(int *arr, int n, int m) +{ + int i; + uint32_t seed = 1; + for (i = 0; i < n; i++) + arr[i] = minstd_rand(&seed) % m; +} + +static void dist_stagger(int *arr, int n, int m) +{ + int i; + for (i = 0; i < n; i++) + arr[i] = (i * m + i) % n; +} + +static void dist_plateau(int *arr, int n, int m) +{ + int i; + for (i = 0; i < n; i++) + arr[i] = (i < m) ? i : m; +} + +static void dist_shuffle(int *arr, int n, int m) +{ + int i, j, k; + uint32_t seed = 1; + for (i = j = 0, k = 1; i < n; i++) + arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2); +} + +#define DIST(name) { #name, dist_##name } + +static struct dist { + const char *name; + void (*fn)(int *arr, int n, int m); +} dist[] = { + DIST(sawtooth), + DIST(rand), + DIST(stagger), + DIST(plateau), + DIST(shuffle), +}; + +static void mode_copy(int *arr UNUSED, int n UNUSED) +{ + /* nothing */ +} + +static void mode_reverse(int *arr, int n) +{ + int i, j; + for (i = 0, j = n - 1; i < j; i++, j--) + SWAP(arr[i], arr[j]); +} + +static void mode_reverse_1st_half(int *arr, int n) +{ + mode_reverse(arr, n / 2); +} + +static void mode_reverse_2nd_half(int *arr, int n) +{ + int half = n / 2; + mode_reverse(arr + half, n - half); +} + +static int compare_ints(const void *av, const void *bv) +{ + const int *ap = av, *bp = bv; + int a = *ap, b = *bp; + return (a > b) - (a < b); +} + +static void mode_sort(int *arr, int n) +{ + QSORT(arr, n, compare_ints); +} + +static void mode_dither(int *arr, int n) +{ + int i; + for (i = 0; i < n; i++) + arr[i] += i % 5; +} + +static void unriffle(int *arr, int n, int *tmp) +{ + int i, j; + COPY_ARRAY(tmp, arr, n); + for (i = j = 0; i < n; i += 2) + arr[j++] = tmp[i]; + for (i = 1; i < n; i += 2) + arr[j++] = tmp[i]; +} + +static void unriffle_recursively(int *arr, int n, int *tmp) +{ + if (n > 1) { + int half = n / 2; + unriffle(arr, n, tmp); + unriffle_recursively(arr, half, tmp); + unriffle_recursively(arr + half, n - half, tmp); + } +} + +static void mode_unriffle(int *arr, int n) +{ + int *tmp; + ALLOC_ARRAY(tmp, n); + unriffle_recursively(arr, n, tmp); + free(tmp); +} + +static unsigned int prev_pow2(unsigned int n) +{ + unsigned int pow2 = 1; + while (pow2 * 2 < n) + pow2 *= 2; + return pow2; +} + +static void unriffle_recursively_skewed(int *arr, int n, int *tmp) +{ + if (n > 1) { + int pow2 = prev_pow2(n); + int rest = n - pow2; + unriffle(arr + pow2 - rest, rest * 2, tmp); + unriffle_recursively_skewed(arr, pow2, tmp); + unriffle_recursively_skewed(arr + pow2, rest, tmp); + } +} + +static void mode_unriffle_skewed(int *arr, int n) +{ + int *tmp; + ALLOC_ARRAY(tmp, n); + unriffle_recursively_skewed(arr, n, tmp); + free(tmp); +} + +#define MODE(name) { #name, mode_##name } + +static struct mode { + const char *name; + void (*fn)(int *arr, int n); +} mode[] = { + MODE(copy), + MODE(reverse), + MODE(reverse_1st_half), + MODE(reverse_2nd_half), + MODE(sort), + MODE(dither), + MODE(unriffle), + MODE(unriffle_skewed), +}; + +static struct stats { + int get_next, set_next; +} stats; + +struct number { + int value, rank; + struct number *next; +}; + +DEFINE_LIST_SORT_DEBUG(static, sort_numbers_debug, struct number, next, + stats.get_next++, stats.set_next++); +DEFINE_LIST_SORT(static, sort_numbers, struct number, next); + +static int compare_numbers(const struct number *an, const struct number *bn) +{ + int a = an->value, b = bn->value; + return (a > b) - (a < b); +} + +/* Free the storage directly, even if an assertion fails on a broken list. */ +static int *values; +static struct number *numbers; + +void test_mergesort__cleanup(void) +{ + FREE_AND_NULL(values); + FREE_AND_NULL(numbers); +} + +static struct number *prepare_list(const int *arr, int n) +{ + int i; + + ALLOC_ARRAY(numbers, n); + for (i = 0; i < n; i++) { + numbers[i].value = arr[i]; + numbers[i].rank = i; + numbers[i].next = i + 1 < n ? &numbers[i + 1] : NULL; + } + stats.get_next = stats.set_next = 0; + return n ? numbers : NULL; +} + +static void check_list(struct number *list, const int *expected, + const int *ranks, int n, const char *context) +{ + struct number *previous = NULL; + int i; + + /* Bound traversal so a cycle is reported as an overlong list. */ + for (i = 0; i < n; i++) { + cl_assert_(list, context); + cl_assert_equal_i_(list->value, expected[i], "%s: index %d", + context, i); + if (previous && previous->value == list->value) + cl_assert_lt_i_(previous->rank, list->rank, + "%s: stability at index %d", context, i); + if (ranks) + cl_assert_equal_i_(list->rank, ranks[i], + "%s: rank at index %d", context, i); + previous = list; + list = list->next; + } + cl_assert_(list == NULL, context); +} + +/* + * A version of the qsort certification program from "Engineering a Sort + * Function" by Bentley and McIlroy, Software—Practice and Experience, + * Volume 23, Issue 11, 1249–1265 (November 1993). + */ +static void certify(const struct dist *distribution) +{ + static const int sizes[] = { 100, 1023, 1024, 1025 }; + size_t i, j; + int m; + + for (i = 0; i < ARRAY_SIZE(sizes); i++) { + int n = sizes[i]; + + for (j = 0; j < ARRAY_SIZE(mode); j++) { + for (m = 1; m < 2 * n; m *= 2) { + struct number *list; + char context[128]; + + xsnprintf(context, sizeof(context), + "%s %s n=%d m=%d", + distribution->name, mode[j].name, n, m); + ALLOC_ARRAY(values, n); + distribution->fn(values, n, m); + mode[j].fn(values, n); + list = prepare_list(values, n); + sort_numbers_debug(&list, compare_numbers); + QSORT(values, n, compare_ints); + check_list(list, values, NULL, n, context); + test_mergesort__cleanup(); + } + } + } +} + +void test_mergesort__sawtooth(void) +{ + certify(&dist[0]); +} + +void test_mergesort__rand(void) +{ + certify(&dist[1]); +} + +void test_mergesort__stagger(void) +{ + certify(&dist[2]); +} + +void test_mergesort__plateau(void) +{ + certify(&dist[3]); +} + +void test_mergesort__shuffle(void) +{ + certify(&dist[4]); +} + +static void check_small(const int *input, const int *expected, + const int *ranks, int n, const char *name) +{ + int debug; + + for (debug = 0; debug < 2; debug++) { + struct number *list = prepare_list(input, n); + char context[128]; + + xsnprintf(context, sizeof(context), "%s %s n=%d", + debug ? "debug" : "normal", name, n); + if (debug) + sort_numbers_debug(&list, compare_numbers); + else + sort_numbers(&list, compare_numbers); + check_list(list, expected, ranks, n, context); + test_mergesort__cleanup(); + } +} + +void test_mergesort__empty(void) +{ + check_small(NULL, NULL, NULL, 0, "empty"); +} + +void test_mergesort__singleton(void) +{ + const int input[] = { 42 }; + const int ranks[] = { 0 }; + + check_small(input, input, ranks, ARRAY_SIZE(input), "singleton"); +} + +void test_mergesort__reversed_pair(void) +{ + const int input[] = { 2, 1 }; + const int expected[] = { 1, 2 }; + const int ranks[] = { 1, 0 }; + + check_small(input, expected, ranks, ARRAY_SIZE(input), "reversed pair"); +} + +void test_mergesort__equal_pair(void) +{ + const int input[] = { 1, 1 }; + const int ranks[] = { 0, 1 }; + + check_small(input, input, ranks, ARRAY_SIZE(input), "equal pair"); +} + +void test_mergesort__mixed_values(void) +{ + const int input[] = { INT_MAX, -1, 0, INT_MIN, -1, INT_MAX, 0 }; + const int expected[] = { INT_MIN, -1, -1, 0, 0, INT_MAX, INT_MAX }; + const int ranks[] = { 3, 1, 4, 2, 6, 0, 5 }; + + check_small(input, expected, ranks, ARRAY_SIZE(input), "mixed values"); +} + +void test_mergesort__debug_hooks(void) +{ + const int input[] = { 2, 1 }; + const int expected[] = { 1, 2 }; + const int ranks[] = { 1, 0 }; + struct number *list = prepare_list(input, ARRAY_SIZE(input)); + + sort_numbers_debug(&list, compare_numbers); + check_list(list, expected, ranks, ARRAY_SIZE(input), "debug hooks"); + cl_assert_gt_i(stats.get_next, 0); + cl_assert_gt_i(stats.set_next, 0); +} -- 2.55.0