{"thread":{"id":"66479","subject":"[PATCH] test-mergesort: plug memory leaks in sort_stdin()","startedAt":"2026-10-07T03:42:05Z","lastAt":"2026-10-12T04:11:18Z","messageCount":18,"participants":["Muhammed Dilshad A","Patrick Steinhardt","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"554346","messageId":"20261007034205.32619-1-dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":null,"subject":"[PATCH] test-mergesort: plug memory leaks in sort_stdin()","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-07T03:42:05Z","receivedAt":"2026-10-07T03:42:05Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"The sort_stdin() helper allocates an input buffer and a memory pool for\nthe list of lines, but returns without releasing either. Discard the\npool and release the strbuf after printing the sorted lines.\n\nAdd a test for the sort subcommand to t0071. The existing test only\nexercises the test subcommand, leaving these leaks undetected by the\nregular leak-sanitized test suite.\n\nSigned-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>\n---\n t/helper/test-mergesort.c | 2 ++\n t/t0071-sort.sh           | 7 +++++++\n 2 files changed, 9 insertions(+)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 791e128793..3b8c428b14 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -61,6 +61,8 @@ static int sort_stdin(void)\n \t\tputs(lines->text);\n \t\tlines = lines->next;\n \t}\n+\tmem_pool_discard(&lines_pool, 0);\n+\tstrbuf_release(&sb);\n \treturn 0;\n }\n \ndiff --git a/t/t0071-sort.sh b/t/t0071-sort.sh\nindex 2236a7e956..97890da29f 100755\n--- a/t/t0071-sort.sh\n+++ b/t/t0071-sort.sh\n@@ -8,4 +8,11 @@ test_expect_success 'DEFINE_LIST_SORT_DEBUG' '\n \ttest-tool mergesort test\n '\n \n+test_expect_success 'sort stdin' '\n+\tprintf \"%s\\n\" c a b >input &&\n+\tprintf \"%s\\n\" a b c >expect &&\n+\ttest-tool mergesort sort <input >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.55.0\n\n\n"},{"id":"554354","messageId":"asXi-1RlWhqPMWjL@pks.im","threadId":"66479","inReplyTo":"20261007034205.32619-1-dilsheddilu123@gmail.com","subject":"Re: [PATCH] test-mergesort: plug memory leaks in sort_stdin()","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-10-07T06:13:15Z","receivedAt":"2026-10-07T06:13:15Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Oct 07, 2026 at 09:12:05AM +0530, Muhammed Dilshad A wrote:\n> The sort_stdin() helper allocates an input buffer and a memory pool for\n> the list of lines, but returns without releasing either. Discard the\n> pool and release the strbuf after printing the sorted lines.\n\nMakes sense.\n\n> Add a test for the sort subcommand to t0071. The existing test only\n> exercises the test subcommand, leaving these leaks undetected by the\n> regular leak-sanitized test suite.\n\nI was briefly wondering whether we could get rid of t0071 altogether in\nfavor of converting the tests into a unit test, and then drop the test\nhelper. And that's certainly doable, and I'd argue it would also be the\nright thing to do. But unfortunately it wouldn't allow us to get rid of\nthe test helper completely as the \"mergesort sort\" subcommand is used as\npart of our performance tests.\n\nI would claim that the benchmark itself is of dubious value. It was nice\nenough to have some numbers when we were working on the implementation\nof the mergesort, but carrying it with us nowadays feels like a bit of a\nwaste as chances for regression are somewhat slim here. And if we ever\nwanted to iterate further on the merge sort implementation we could\nstill introduce a new benchmark, that's easy enough to do.\n\nBut anyway, that's of course a much bigger scope, and I'm fine to just\nfix the bugs for now.\n\n> diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\n> index 791e128793..3b8c428b14 100644\n> --- a/t/helper/test-mergesort.c\n> +++ b/t/helper/test-mergesort.c\n> @@ -61,6 +61,8 @@ static int sort_stdin(void)\n>  \t\tputs(lines->text);\n>  \t\tlines = lines->next;\n>  \t}\n> +\tmem_pool_discard(&lines_pool, 0);\n> +\tstrbuf_release(&sb);\n>  \treturn 0;\n>  }\n\nThe fix is obviously correct.\n\n> diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh\n> index 2236a7e956..97890da29f 100755\n> --- a/t/t0071-sort.sh\n> +++ b/t/t0071-sort.sh\n> @@ -8,4 +8,11 @@ test_expect_success 'DEFINE_LIST_SORT_DEBUG' '\n>  \ttest-tool mergesort test\n>  '\n>  \n> +test_expect_success 'sort stdin' '\n> +\tprintf \"%s\\n\" c a b >input &&\n> +\tprintf \"%s\\n\" a b c >expect &&\n> +\ttest-tool mergesort sort <input >actual &&\n> +\ttest_cmp expect actual\n> +'\n\nAnd having a test makes sense, I guess.\n\nI noticed that there's another \"generate\" subcommand here that is\nentirely unused. Do we maybe want to also remove it while at it? The\ntest suite passes with the below diff.\n\nThanks!\n\nPatrick\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 791e128793..9200c4bb4a 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -114,16 +114,6 @@ static struct dist {\n \tDIST(shuffle),\n };\n \n-static const struct dist *get_dist_by_name(const char *name)\n-{\n-\tint i;\n-\tfor (i = 0; i < ARRAY_SIZE(dist); i++) {\n-\t       if (!strcmp(dist[i].name, name))\n-\t\t       return &dist[i];\n-\t}\n-\treturn NULL;\n-}\n-\n static void mode_copy(int *arr UNUSED, int n UNUSED)\n {\n \t/* nothing */\n@@ -237,41 +227,6 @@ static struct mode {\n \tMODE(unriffle_skewed),\n };\n \n-static const struct mode *get_mode_by_name(const char *name)\n-{\n-\tint i;\n-\tfor (i = 0; i < ARRAY_SIZE(mode); i++) {\n-\t       if (!strcmp(mode[i].name, name))\n-\t\t       return &mode[i];\n-\t}\n-\treturn NULL;\n-}\n-\n-static int generate(int argc, const char **argv)\n-{\n-\tconst struct dist *dist = NULL;\n-\tconst struct mode *mode = NULL;\n-\tint i, n, m, *arr;\n-\n-\tif (argc != 4)\n-\t\treturn 1;\n-\n-\tdist = get_dist_by_name(argv[0]);\n-\tmode = get_mode_by_name(argv[1]);\n-\tn = strtol(argv[2], NULL, 10);\n-\tm = strtol(argv[3], NULL, 10);\n-\tif (!dist || !mode)\n-\t\treturn 1;\n-\n-\tALLOC_ARRAY(arr, n);\n-\tdist->fn(arr, n, m);\n-\tmode->fn(arr, n);\n-\tfor (i = 0; i < n; i++)\n-\t\tprintf(\"%08x\\n\", arr[i]);\n-\tfree(arr);\n-\treturn 0;\n-}\n-\n static struct stats {\n \tint get_next, set_next, compare;\n } stats;\n@@ -388,14 +343,11 @@ int cmd__mergesort(int argc, const char **argv)\n \tint i;\n \tconst char *sep;\n \n-\tif (argc == 6 && !strcmp(argv[1], \"generate\"))\n-\t\treturn generate(argc - 2, argv + 2);\n \tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n \t\treturn sort_stdin();\n \tif (argc > 1 && !strcmp(argv[1], \"test\"))\n \t\treturn run_tests(argc - 2, argv + 2);\n-\tfprintf(stderr, \"usage: test-tool mergesort generate <distribution> <mode> <n> <m>\\n\");\n-\tfprintf(stderr, \"   or: test-tool mergesort sort\\n\");\n+\tfprintf(stderr, \"usage: test-tool mergesort sort\\n\");\n \tfprintf(stderr, \"   or: test-tool mergesort test [<n>...]\\n\");\n \tfprintf(stderr, \"\\n\");\n \tfor (i = 0, sep = \"distributions: \"; i < ARRAY_SIZE(dist); i++, sep = \", \")\n\n"},{"id":"554375","messageId":"cover.1791365181.git.dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"20261007034205.32619-1-dilsheddilu123@gmail.com","subject":"[PATCH v2 0/3] mergesort: move tests to Clar and retire the helper","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-07T13:50:22Z","receivedAt":"2026-10-07T13:50:22Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"Hi Patrick,\n\nThanks for the review. I followed up on the larger cleanup you mentioned.\nThe sorting tests now run in Clar, and I have removed the old benchmark\nand its helper. This also removes the unused generate subcommand.\n\nThe new suite keeps all 1,680 cases from the old certification test and\nadds checks for empty and small lists using both sort macros. It checks\nsorting order, stability and list length. Cleanup frees the backing\narrays directly, so a failed assertion does not need to walk list links.\n\nChanges since v1:\n\n* Patch 1 is unchanged.\n* Patch 2 moves the tests to Clar and removes the unused generate and\n  test commands. The sort command remains available for the benchmark.\n* Patch 3 removes p0071 and the remaining sort helper, along with their\n  build and command registrations.\n\nI kept the leak fix first so it can still be applied on its own if you\nwould prefer to keep the broader cleanup for a separate series.\n\nThe Make and Meson unit tests pass, and the mergesort unit suite also\npasses with LeakSanitizer enabled. The production sorting implementation\nis unchanged.\n\nMuhammed Dilshad A (3):\n  test-mergesort: plug memory leaks in sort_stdin()\n  mergesort: move sorting tests to the unit-test framework\n  t: retire the sorting benchmark and mergesort helper\n\n Makefile                   |   2 +-\n t/helper/meson.build       |   1 -\n t/helper/test-mergesort.c  | 408 -------------------------------------\n t/helper/test-tool.c       |   1 -\n t/helper/test-tool.h       |   1 -\n t/meson.build              |   3 +-\n t/perf/p0071-sort.sh       |  52 -----\n t/t0071-sort.sh            |  11 -\n t/unit-tests/u-mergesort.c | 369 +++++++++++++++++++++++++++++++++\n 9 files changed, 371 insertions(+), 477 deletions(-)\n delete mode 100644 t/helper/test-mergesort.c\n delete mode 100755 t/perf/p0071-sort.sh\n delete mode 100755 t/t0071-sort.sh\n create mode 100644 t/unit-tests/u-mergesort.c\n\n\nbase-commit: 6de20f6092dcf9bdb1c8efe03db4b70c82b423dd\n-- \n2.55.0\n\n"},{"id":"554376","messageId":"2a91f29982cf18ef6ee6770c671b33e042acd308.1791365181.git.dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"cover.1791365181.git.dilsheddilu123@gmail.com","subject":"[PATCH v2 1/3] test-mergesort: plug memory leaks in sort_stdin()","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-07T13:50:23Z","receivedAt":"2026-10-07T13:50:23Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"The sort_stdin() helper allocates an input buffer and a memory pool for\nthe list of lines, but returns without releasing either. Discard the\npool and release the strbuf after printing the sorted lines.\n\nAdd a test for the sort subcommand to t0071. The existing test only\nexercises the test subcommand, leaving these leaks undetected by the\nregular leak-sanitized test suite.\n\nSigned-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>\n---\n t/helper/test-mergesort.c | 2 ++\n t/t0071-sort.sh           | 7 +++++++\n 2 files changed, 9 insertions(+)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 791e128793..3b8c428b14 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -61,6 +61,8 @@ static int sort_stdin(void)\n \t\tputs(lines->text);\n \t\tlines = lines->next;\n \t}\n+\tmem_pool_discard(&lines_pool, 0);\n+\tstrbuf_release(&sb);\n \treturn 0;\n }\n \ndiff --git a/t/t0071-sort.sh b/t/t0071-sort.sh\nindex 2236a7e956..97890da29f 100755\n--- a/t/t0071-sort.sh\n+++ b/t/t0071-sort.sh\n@@ -8,4 +8,11 @@ test_expect_success 'DEFINE_LIST_SORT_DEBUG' '\n \ttest-tool mergesort test\n '\n \n+test_expect_success 'sort stdin' '\n+\tprintf \"%s\\n\" c a b >input &&\n+\tprintf \"%s\\n\" a b c >expect &&\n+\ttest-tool mergesort sort <input >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.55.0\n\n\n"},{"id":"554377","messageId":"0429552774367ddcc3c2fda78e09a83650ccfa02.1791365181.git.dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"cover.1791365181.git.dilsheddilu123@gmail.com","subject":"[PATCH v2 2/3] mergesort: move sorting tests to the unit-test framework","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-07T13:50:24Z","receivedAt":"2026-10-07T13:50:24Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"The mergesort certification checks exercise C code directly, so they do\nnot need a shell test and test-tool command. Move their distributions and\ntransformations to Clar, retaining the sorted-value, stability and list\nlength checks. Add small cases for both list sort macros and debug hooks.\n\nKeep node storage available to the cleanup fixture and bound validation\nso a failed assertion can release it without walking a broken list.\nRemove the unused generate command along with the old test command,\nleaving sort available for the sorting benchmark.\n\nSuggested-by: Patrick Steinhardt <ps@pks.im>\nSigned-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>\n---\n Makefile                   |   1 +\n t/helper/test-mergesort.c  | 345 +---------------------------------\n t/meson.build              |   2 +-\n t/t0071-sort.sh            |  18 --\n t/unit-tests/u-mergesort.c | 369 +++++++++++++++++++++++++++++++++++++\n 5 files changed, 372 insertions(+), 363 deletions(-)\n delete mode 100755 t/t0071-sort.sh\n create mode 100644 t/unit-tests/u-mergesort.c\n\ndiff --git a/Makefile b/Makefile\nindex a96be506b5..cac535ba19 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1541,6 +1541,7 @@ CLAR_TEST_SUITES += u-hash\n CLAR_TEST_SUITES += u-hashmap\n CLAR_TEST_SUITES += u-list-objects-filter-options\n CLAR_TEST_SUITES += u-mem-pool\n+CLAR_TEST_SUITES += u-mergesort\n CLAR_TEST_SUITES += u-odb-inmemory\n CLAR_TEST_SUITES += u-oid-array\n CLAR_TEST_SUITES += u-oidmap\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 3b8c428b14..e8b8de239b 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -1,16 +1,8 @@\n-#define DISABLE_SIGN_COMPARE_WARNINGS\n-\n #include \"test-tool.h\"\n #include \"mem-pool.h\"\n #include \"mergesort.h\"\n #include \"strbuf.h\"\n \n-static uint32_t minstd_rand(uint32_t *state)\n-{\n-\t*state = (uint64_t)*state * 48271 % 2147483647;\n-\treturn *state;\n-}\n-\n struct line {\n \tchar *text;\n \tstruct line *next;\n@@ -66,345 +58,10 @@ static int sort_stdin(void)\n \treturn 0;\n }\n \n-static void dist_sawtooth(int *arr, int n, int m)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = i % m;\n-}\n-\n-static void dist_rand(int *arr, int n, int m)\n-{\n-\tint i;\n-\tuint32_t seed = 1;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = minstd_rand(&seed) % m;\n-}\n-\n-static void dist_stagger(int *arr, int n, int m)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = (i * m + i) % n;\n-}\n-\n-static void dist_plateau(int *arr, int n, int m)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = (i < m) ? i : m;\n-}\n-\n-static void dist_shuffle(int *arr, int n, int m)\n-{\n-\tint i, j, k;\n-\tuint32_t seed = 1;\n-\tfor (i = j = 0, k = 1; i < n; i++)\n-\t\tarr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);\n-}\n-\n-#define DIST(name) { #name, dist_##name }\n-\n-static struct dist {\n-\tconst char *name;\n-\tvoid (*fn)(int *arr, int n, int m);\n-} dist[] = {\n-\tDIST(sawtooth),\n-\tDIST(rand),\n-\tDIST(stagger),\n-\tDIST(plateau),\n-\tDIST(shuffle),\n-};\n-\n-static const struct dist *get_dist_by_name(const char *name)\n-{\n-\tint i;\n-\tfor (i = 0; i < ARRAY_SIZE(dist); i++) {\n-\t       if (!strcmp(dist[i].name, name))\n-\t\t       return &dist[i];\n-\t}\n-\treturn NULL;\n-}\n-\n-static void mode_copy(int *arr UNUSED, int n UNUSED)\n-{\n-\t/* nothing */\n-}\n-\n-static void mode_reverse(int *arr, int n)\n-{\n-\tint i, j;\n-\tfor (i = 0, j = n - 1; i < j; i++, j--)\n-\t\tSWAP(arr[i], arr[j]);\n-}\n-\n-static void mode_reverse_1st_half(int *arr, int n)\n-{\n-\tmode_reverse(arr, n / 2);\n-}\n-\n-static void mode_reverse_2nd_half(int *arr, int n)\n-{\n-\tint half = n / 2;\n-\tmode_reverse(arr + half, n - half);\n-}\n-\n-static int compare_ints(const void *av, const void *bv)\n-{\n-\tconst int *ap = av, *bp = bv;\n-\tint a = *ap, b = *bp;\n-\treturn (a > b) - (a < b);\n-}\n-\n-static void mode_sort(int *arr, int n)\n-{\n-\tQSORT(arr, n, compare_ints);\n-}\n-\n-static void mode_dither(int *arr, int n)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] += i % 5;\n-}\n-\n-static void unriffle(int *arr, int n, int *tmp)\n-{\n-\tint i, j;\n-\tCOPY_ARRAY(tmp, arr, n);\n-\tfor (i = j = 0; i < n; i += 2)\n-\t\tarr[j++] = tmp[i];\n-\tfor (i = 1; i < n; i += 2)\n-\t\tarr[j++] = tmp[i];\n-}\n-\n-static void unriffle_recursively(int *arr, int n, int *tmp)\n-{\n-\tif (n > 1) {\n-\t\tint half = n / 2;\n-\t\tunriffle(arr, n, tmp);\n-\t\tunriffle_recursively(arr, half, tmp);\n-\t\tunriffle_recursively(arr + half, n - half, tmp);\n-\t}\n-}\n-\n-static void mode_unriffle(int *arr, int n)\n-{\n-\tint *tmp;\n-\tALLOC_ARRAY(tmp, n);\n-\tunriffle_recursively(arr, n, tmp);\n-\tfree(tmp);\n-}\n-\n-static unsigned int prev_pow2(unsigned int n)\n-{\n-\tunsigned int pow2 = 1;\n-\twhile (pow2 * 2 < n)\n-\t\tpow2 *= 2;\n-\treturn pow2;\n-}\n-\n-static void unriffle_recursively_skewed(int *arr, int n, int *tmp)\n-{\n-\tif (n > 1) {\n-\t\tint pow2 = prev_pow2(n);\n-\t\tint rest = n - pow2;\n-\t\tunriffle(arr + pow2 - rest, rest * 2, tmp);\n-\t\tunriffle_recursively_skewed(arr, pow2, tmp);\n-\t\tunriffle_recursively_skewed(arr + pow2, rest, tmp);\n-\t}\n-}\n-\n-static void mode_unriffle_skewed(int *arr, int n)\n-{\n-\tint *tmp;\n-\tALLOC_ARRAY(tmp, n);\n-\tunriffle_recursively_skewed(arr, n, tmp);\n-\tfree(tmp);\n-}\n-\n-#define MODE(name) { #name, mode_##name }\n-\n-static struct mode {\n-\tconst char *name;\n-\tvoid (*fn)(int *arr, int n);\n-} mode[] = {\n-\tMODE(copy),\n-\tMODE(reverse),\n-\tMODE(reverse_1st_half),\n-\tMODE(reverse_2nd_half),\n-\tMODE(sort),\n-\tMODE(dither),\n-\tMODE(unriffle),\n-\tMODE(unriffle_skewed),\n-};\n-\n-static const struct mode *get_mode_by_name(const char *name)\n-{\n-\tint i;\n-\tfor (i = 0; i < ARRAY_SIZE(mode); i++) {\n-\t       if (!strcmp(mode[i].name, name))\n-\t\t       return &mode[i];\n-\t}\n-\treturn NULL;\n-}\n-\n-static int generate(int argc, const char **argv)\n-{\n-\tconst struct dist *dist = NULL;\n-\tconst struct mode *mode = NULL;\n-\tint i, n, m, *arr;\n-\n-\tif (argc != 4)\n-\t\treturn 1;\n-\n-\tdist = get_dist_by_name(argv[0]);\n-\tmode = get_mode_by_name(argv[1]);\n-\tn = strtol(argv[2], NULL, 10);\n-\tm = strtol(argv[3], NULL, 10);\n-\tif (!dist || !mode)\n-\t\treturn 1;\n-\n-\tALLOC_ARRAY(arr, n);\n-\tdist->fn(arr, n, m);\n-\tmode->fn(arr, n);\n-\tfor (i = 0; i < n; i++)\n-\t\tprintf(\"%08x\\n\", arr[i]);\n-\tfree(arr);\n-\treturn 0;\n-}\n-\n-static struct stats {\n-\tint get_next, set_next, compare;\n-} stats;\n-\n-struct number {\n-\tint value, rank;\n-\tstruct number *next;\n-};\n-\n-DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,\n-\t\t       stats.get_next++, stats.set_next++);\n-\n-static int compare_numbers(const struct number *an, const struct number *bn)\n-{\n-\tint a = an->value, b = bn->value;\n-\tstats.compare++;\n-\treturn (a > b) - (a < b);\n-}\n-\n-static void clear_numbers(struct number *list)\n-{\n-\twhile (list) {\n-\t\tstruct number *next = list->next;\n-\t\tfree(list);\n-\t\tlist = next;\n-\t}\n-}\n-\n-static int test(const struct dist *dist, const struct mode *mode, int n, int m)\n-{\n-\tint *arr;\n-\tsize_t i;\n-\tstruct number *curr, *list, **tail;\n-\tint is_sorted = 1;\n-\tint is_stable = 1;\n-\tconst char *verdict;\n-\tint result = -1;\n-\n-\tALLOC_ARRAY(arr, n);\n-\tdist->fn(arr, n, m);\n-\tmode->fn(arr, n);\n-\tfor (i = 0, tail = &list; i < n; i++) {\n-\t\tcurr = xmalloc(sizeof(*curr));\n-\t\tcurr->value = arr[i];\n-\t\tcurr->rank = i;\n-\t\t*tail = curr;\n-\t\ttail = &curr->next;\n-\t}\n-\t*tail = NULL;\n-\n-\tstats.get_next = stats.set_next = stats.compare = 0;\n-\tsort_numbers(&list, compare_numbers);\n-\n-\tQSORT(arr, n, compare_ints);\n-\tfor (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {\n-\t\tif (arr[i] != curr->value)\n-\t\t\tis_sorted = 0;\n-\t\tif (curr->next && curr->value == curr->next->value &&\n-\t\t    curr->rank >= curr->next->rank)\n-\t\t\tis_stable = 0;\n-\t}\n-\tif (i < n) {\n-\t\tverdict = \"too short\";\n-\t} else if (curr) {\n-\t\tverdict = \"too long\";\n-\t} else if (!is_sorted) {\n-\t\tverdict = \"not sorted\";\n-\t} else if (!is_stable) {\n-\t\tverdict = \"unstable\";\n-\t} else {\n-\t\tverdict = \"OK\";\n-\t\tresult = 0;\n-\t}\n-\n-\tprintf(\"%-9s %-16s %8d %8d %8d %8d %8d %s\\n\",\n-\t       dist->name, mode->name, n, m, stats.get_next, stats.set_next,\n-\t       stats.compare, verdict);\n-\n-\tclear_numbers(list);\n-\tfree(arr);\n-\n-\treturn result;\n-}\n-\n-/*\n- * A version of the qsort certification program from \"Engineering a Sort\n- * Function\" by Bentley and McIlroy, Software—Practice and Experience,\n- * Volume 23, Issue 11, 1249–1265 (November 1993).\n- */\n-static int run_tests(int argc, const char **argv)\n-{\n-\tconst char *argv_default[] = { \"100\", \"1023\", \"1024\", \"1025\" };\n-\tif (!argc)\n-\t\treturn run_tests(ARRAY_SIZE(argv_default), argv_default);\n-\tprintf(\"%-9s %-16s %8s %8s %8s %8s %8s %s\\n\",\n-\t       \"distribut\", \"mode\", \"n\", \"m\", \"get_next\", \"set_next\",\n-\t       \"compare\", \"verdict\");\n-\twhile (argc--) {\n-\t\tint i, j, m, n = strtol(*argv++, NULL, 10);\n-\t\tfor (i = 0; i < ARRAY_SIZE(dist); i++) {\n-\t\t\tfor (j = 0; j < ARRAY_SIZE(mode); j++) {\n-\t\t\t\tfor (m = 1; m < 2 * n; m *= 2) {\n-\t\t\t\t\tif (test(&dist[i], &mode[j], n, m))\n-\t\t\t\t\t\treturn 1;\n-\t\t\t\t}\n-\t\t\t}\n-\t\t}\n-\t}\n-\treturn 0;\n-}\n-\n int cmd__mergesort(int argc, const char **argv)\n {\n-\tint i;\n-\tconst char *sep;\n-\n-\tif (argc == 6 && !strcmp(argv[1], \"generate\"))\n-\t\treturn generate(argc - 2, argv + 2);\n \tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n \t\treturn sort_stdin();\n-\tif (argc > 1 && !strcmp(argv[1], \"test\"))\n-\t\treturn run_tests(argc - 2, argv + 2);\n-\tfprintf(stderr, \"usage: test-tool mergesort generate <distribution> <mode> <n> <m>\\n\");\n-\tfprintf(stderr, \"   or: test-tool mergesort sort\\n\");\n-\tfprintf(stderr, \"   or: test-tool mergesort test [<n>...]\\n\");\n-\tfprintf(stderr, \"\\n\");\n-\tfor (i = 0, sep = \"distributions: \"; i < ARRAY_SIZE(dist); i++, sep = \", \")\n-\t\tfprintf(stderr, \"%s%s\", sep, dist[i].name);\n-\tfprintf(stderr, \"\\n\");\n-\tfor (i = 0, sep = \"modes: \"; i < ARRAY_SIZE(mode); i++, sep = \", \")\n-\t\tfprintf(stderr, \"%s%s\", sep, mode[i].name);\n-\tfprintf(stderr, \"\\n\");\n+\tfprintf(stderr, \"usage: test-tool mergesort sort\\n\");\n \treturn 129;\n }\ndiff --git a/t/meson.build b/t/meson.build\nindex f65eb04684..2752321e0d 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -6,6 +6,7 @@ clar_test_suites = [\n   'unit-tests/u-hashmap.c',\n   'unit-tests/u-list-objects-filter-options.c',\n   'unit-tests/u-mem-pool.c',\n+  'unit-tests/u-mergesort.c',\n   'unit-tests/u-odb-inmemory.c',\n   'unit-tests/u-oid-array.c',\n   'unit-tests/u-oidmap.c',\n@@ -119,7 +120,6 @@ integration_tests = [\n   't0067-parse_pathspec_file.sh',\n   't0068-for-each-repo.sh',\n   't0070-fundamental.sh',\n-  't0071-sort.sh',\n   't0080-unit-test-output.sh',\n   't0081-find-pack.sh',\n   't0090-cache-tree.sh',\ndiff --git a/t/t0071-sort.sh b/t/t0071-sort.sh\ndeleted file mode 100755\nindex 97890da29f..0000000000\n--- a/t/t0071-sort.sh\n+++ /dev/null\n@@ -1,18 +0,0 @@\n-#!/bin/sh\n-\n-test_description='verify sort functions'\n-\n-. ./test-lib.sh\n-\n-test_expect_success 'DEFINE_LIST_SORT_DEBUG' '\n-\ttest-tool mergesort test\n-'\n-\n-test_expect_success 'sort stdin' '\n-\tprintf \"%s\\n\" c a b >input &&\n-\tprintf \"%s\\n\" a b c >expect &&\n-\ttest-tool mergesort sort <input >actual &&\n-\ttest_cmp expect actual\n-'\n-\n-test_done\ndiff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c\nnew file mode 100644\nindex 0000000000..e621c9ec21\n--- /dev/null\n+++ b/t/unit-tests/u-mergesort.c\n@@ -0,0 +1,369 @@\n+#include \"unit-test.h\"\n+#include \"mergesort.h\"\n+\n+static uint32_t minstd_rand(uint32_t *state)\n+{\n+\t*state = (uint64_t)*state * 48271 % 2147483647;\n+\treturn *state;\n+}\n+\n+static void dist_sawtooth(int *arr, int n, int m)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = i % m;\n+}\n+\n+static void dist_rand(int *arr, int n, int m)\n+{\n+\tint i;\n+\tuint32_t seed = 1;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = minstd_rand(&seed) % m;\n+}\n+\n+static void dist_stagger(int *arr, int n, int m)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = (i * m + i) % n;\n+}\n+\n+static void dist_plateau(int *arr, int n, int m)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = (i < m) ? i : m;\n+}\n+\n+static void dist_shuffle(int *arr, int n, int m)\n+{\n+\tint i, j, k;\n+\tuint32_t seed = 1;\n+\tfor (i = j = 0, k = 1; i < n; i++)\n+\t\tarr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);\n+}\n+\n+#define DIST(name) { #name, dist_##name }\n+\n+static struct dist {\n+\tconst char *name;\n+\tvoid (*fn)(int *arr, int n, int m);\n+} dist[] = {\n+\tDIST(sawtooth),\n+\tDIST(rand),\n+\tDIST(stagger),\n+\tDIST(plateau),\n+\tDIST(shuffle),\n+};\n+\n+static void mode_copy(int *arr UNUSED, int n UNUSED)\n+{\n+\t/* nothing */\n+}\n+\n+static void mode_reverse(int *arr, int n)\n+{\n+\tint i, j;\n+\tfor (i = 0, j = n - 1; i < j; i++, j--)\n+\t\tSWAP(arr[i], arr[j]);\n+}\n+\n+static void mode_reverse_1st_half(int *arr, int n)\n+{\n+\tmode_reverse(arr, n / 2);\n+}\n+\n+static void mode_reverse_2nd_half(int *arr, int n)\n+{\n+\tint half = n / 2;\n+\tmode_reverse(arr + half, n - half);\n+}\n+\n+static int compare_ints(const void *av, const void *bv)\n+{\n+\tconst int *ap = av, *bp = bv;\n+\tint a = *ap, b = *bp;\n+\treturn (a > b) - (a < b);\n+}\n+\n+static void mode_sort(int *arr, int n)\n+{\n+\tQSORT(arr, n, compare_ints);\n+}\n+\n+static void mode_dither(int *arr, int n)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] += i % 5;\n+}\n+\n+static void unriffle(int *arr, int n, int *tmp)\n+{\n+\tint i, j;\n+\tCOPY_ARRAY(tmp, arr, n);\n+\tfor (i = j = 0; i < n; i += 2)\n+\t\tarr[j++] = tmp[i];\n+\tfor (i = 1; i < n; i += 2)\n+\t\tarr[j++] = tmp[i];\n+}\n+\n+static void unriffle_recursively(int *arr, int n, int *tmp)\n+{\n+\tif (n > 1) {\n+\t\tint half = n / 2;\n+\t\tunriffle(arr, n, tmp);\n+\t\tunriffle_recursively(arr, half, tmp);\n+\t\tunriffle_recursively(arr + half, n - half, tmp);\n+\t}\n+}\n+\n+static void mode_unriffle(int *arr, int n)\n+{\n+\tint *tmp;\n+\tALLOC_ARRAY(tmp, n);\n+\tunriffle_recursively(arr, n, tmp);\n+\tfree(tmp);\n+}\n+\n+static unsigned int prev_pow2(unsigned int n)\n+{\n+\tunsigned int pow2 = 1;\n+\twhile (pow2 * 2 < n)\n+\t\tpow2 *= 2;\n+\treturn pow2;\n+}\n+\n+static void unriffle_recursively_skewed(int *arr, int n, int *tmp)\n+{\n+\tif (n > 1) {\n+\t\tint pow2 = prev_pow2(n);\n+\t\tint rest = n - pow2;\n+\t\tunriffle(arr + pow2 - rest, rest * 2, tmp);\n+\t\tunriffle_recursively_skewed(arr, pow2, tmp);\n+\t\tunriffle_recursively_skewed(arr + pow2, rest, tmp);\n+\t}\n+}\n+\n+static void mode_unriffle_skewed(int *arr, int n)\n+{\n+\tint *tmp;\n+\tALLOC_ARRAY(tmp, n);\n+\tunriffle_recursively_skewed(arr, n, tmp);\n+\tfree(tmp);\n+}\n+\n+#define MODE(name) { #name, mode_##name }\n+\n+static struct mode {\n+\tconst char *name;\n+\tvoid (*fn)(int *arr, int n);\n+} mode[] = {\n+\tMODE(copy),\n+\tMODE(reverse),\n+\tMODE(reverse_1st_half),\n+\tMODE(reverse_2nd_half),\n+\tMODE(sort),\n+\tMODE(dither),\n+\tMODE(unriffle),\n+\tMODE(unriffle_skewed),\n+};\n+\n+static struct stats {\n+\tint get_next, set_next;\n+} stats;\n+\n+struct number {\n+\tint value, rank;\n+\tstruct number *next;\n+};\n+\n+DEFINE_LIST_SORT_DEBUG(static, sort_numbers_debug, struct number, next,\n+\t\t       stats.get_next++, stats.set_next++);\n+DEFINE_LIST_SORT(static, sort_numbers, struct number, next);\n+\n+static int compare_numbers(const struct number *an, const struct number *bn)\n+{\n+\tint a = an->value, b = bn->value;\n+\treturn (a > b) - (a < b);\n+}\n+\n+/* Free the storage directly, even if an assertion fails on a broken list. */\n+static int *values;\n+static struct number *numbers;\n+\n+void test_mergesort__cleanup(void)\n+{\n+\tFREE_AND_NULL(values);\n+\tFREE_AND_NULL(numbers);\n+}\n+\n+static struct number *prepare_list(const int *arr, int n)\n+{\n+\tint i;\n+\n+\tALLOC_ARRAY(numbers, n);\n+\tfor (i = 0; i < n; i++) {\n+\t\tnumbers[i].value = arr[i];\n+\t\tnumbers[i].rank = i;\n+\t\tnumbers[i].next = i + 1 < n ? &numbers[i + 1] : NULL;\n+\t}\n+\tstats.get_next = stats.set_next = 0;\n+\treturn n ? numbers : NULL;\n+}\n+\n+static void check_list(struct number *list, const int *expected,\n+\t\t       const int *ranks, int n, const char *context)\n+{\n+\tstruct number *previous = NULL;\n+\tint i;\n+\n+\t/* Bound traversal so a cycle is reported as an overlong list. */\n+\tfor (i = 0; i < n; i++) {\n+\t\tcl_assert_(list, context);\n+\t\tcl_assert_equal_i_(list->value, expected[i], \"%s: index %d\",\n+\t\t\t\t   context, i);\n+\t\tif (previous && previous->value == list->value)\n+\t\t\tcl_assert_lt_i_(previous->rank, list->rank,\n+\t\t\t\t\t\"%s: stability at index %d\", context, i);\n+\t\tif (ranks)\n+\t\t\tcl_assert_equal_i_(list->rank, ranks[i],\n+\t\t\t\t\t   \"%s: rank at index %d\", context, i);\n+\t\tprevious = list;\n+\t\tlist = list->next;\n+\t}\n+\tcl_assert_(list == NULL, context);\n+}\n+\n+/*\n+ * A version of the qsort certification program from \"Engineering a Sort\n+ * Function\" by Bentley and McIlroy, Software—Practice and Experience,\n+ * Volume 23, Issue 11, 1249–1265 (November 1993).\n+ */\n+static void certify(const struct dist *distribution)\n+{\n+\tstatic const int sizes[] = { 100, 1023, 1024, 1025 };\n+\tsize_t i, j;\n+\tint m;\n+\n+\tfor (i = 0; i < ARRAY_SIZE(sizes); i++) {\n+\t\tint n = sizes[i];\n+\n+\t\tfor (j = 0; j < ARRAY_SIZE(mode); j++) {\n+\t\t\tfor (m = 1; m < 2 * n; m *= 2) {\n+\t\t\t\tstruct number *list;\n+\t\t\t\tchar context[128];\n+\n+\t\t\t\txsnprintf(context, sizeof(context),\n+\t\t\t\t\t  \"%s %s n=%d m=%d\",\n+\t\t\t\t\t  distribution->name, mode[j].name, n, m);\n+\t\t\t\tALLOC_ARRAY(values, n);\n+\t\t\t\tdistribution->fn(values, n, m);\n+\t\t\t\tmode[j].fn(values, n);\n+\t\t\t\tlist = prepare_list(values, n);\n+\t\t\t\tsort_numbers_debug(&list, compare_numbers);\n+\t\t\t\tQSORT(values, n, compare_ints);\n+\t\t\t\tcheck_list(list, values, NULL, n, context);\n+\t\t\t\ttest_mergesort__cleanup();\n+\t\t\t}\n+\t\t}\n+\t}\n+}\n+\n+void test_mergesort__sawtooth(void)\n+{\n+\tcertify(&dist[0]);\n+}\n+\n+void test_mergesort__rand(void)\n+{\n+\tcertify(&dist[1]);\n+}\n+\n+void test_mergesort__stagger(void)\n+{\n+\tcertify(&dist[2]);\n+}\n+\n+void test_mergesort__plateau(void)\n+{\n+\tcertify(&dist[3]);\n+}\n+\n+void test_mergesort__shuffle(void)\n+{\n+\tcertify(&dist[4]);\n+}\n+\n+static void check_small(const int *input, const int *expected,\n+\t\t\tconst int *ranks, int n, const char *name)\n+{\n+\tint debug;\n+\n+\tfor (debug = 0; debug < 2; debug++) {\n+\t\tstruct number *list = prepare_list(input, n);\n+\t\tchar context[128];\n+\n+\t\txsnprintf(context, sizeof(context), \"%s %s n=%d\",\n+\t\t\t  debug ? \"debug\" : \"normal\", name, n);\n+\t\tif (debug)\n+\t\t\tsort_numbers_debug(&list, compare_numbers);\n+\t\telse\n+\t\t\tsort_numbers(&list, compare_numbers);\n+\t\tcheck_list(list, expected, ranks, n, context);\n+\t\ttest_mergesort__cleanup();\n+\t}\n+}\n+\n+void test_mergesort__empty(void)\n+{\n+\tcheck_small(NULL, NULL, NULL, 0, \"empty\");\n+}\n+\n+void test_mergesort__singleton(void)\n+{\n+\tconst int input[] = { 42 };\n+\tconst int ranks[] = { 0 };\n+\n+\tcheck_small(input, input, ranks, ARRAY_SIZE(input), \"singleton\");\n+}\n+\n+void test_mergesort__reversed_pair(void)\n+{\n+\tconst int input[] = { 2, 1 };\n+\tconst int expected[] = { 1, 2 };\n+\tconst int ranks[] = { 1, 0 };\n+\n+\tcheck_small(input, expected, ranks, ARRAY_SIZE(input), \"reversed pair\");\n+}\n+\n+void test_mergesort__equal_pair(void)\n+{\n+\tconst int input[] = { 1, 1 };\n+\tconst int ranks[] = { 0, 1 };\n+\n+\tcheck_small(input, input, ranks, ARRAY_SIZE(input), \"equal pair\");\n+}\n+\n+void test_mergesort__mixed_values(void)\n+{\n+\tconst int input[] = { INT_MAX, -1, 0, INT_MIN, -1, INT_MAX, 0 };\n+\tconst int expected[] = { INT_MIN, -1, -1, 0, 0, INT_MAX, INT_MAX };\n+\tconst int ranks[] = { 3, 1, 4, 2, 6, 0, 5 };\n+\n+\tcheck_small(input, expected, ranks, ARRAY_SIZE(input), \"mixed values\");\n+}\n+\n+void test_mergesort__debug_hooks(void)\n+{\n+\tconst int input[] = { 2, 1 };\n+\tconst int expected[] = { 1, 2 };\n+\tconst int ranks[] = { 1, 0 };\n+\tstruct number *list = prepare_list(input, ARRAY_SIZE(input));\n+\n+\tsort_numbers_debug(&list, compare_numbers);\n+\tcheck_list(list, expected, ranks, ARRAY_SIZE(input), \"debug hooks\");\n+\tcl_assert_gt_i(stats.get_next, 0);\n+\tcl_assert_gt_i(stats.set_next, 0);\n+}\n-- \n2.55.0\n\n"},{"id":"554378","messageId":"b540e3a3d2c30bccaaa0d8dca3428a77c1d2ea76.1791365181.git.dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"cover.1791365181.git.dilsheddilu123@gmail.com","subject":"[PATCH v2 3/3] t: retire the sorting benchmark and mergesort helper","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-07T13:50:25Z","receivedAt":"2026-10-07T13:50:25Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"p0071 compared sorting implementations during mergesort development.\nRetire it as suggested during the unit-test conversion. A new benchmark\ncan be added if later optimization work needs performance measurements.\n\nThe benchmark was the last caller of the sort-only mergesort helper.\nRemoving it allows us to delete the helper and its build and command\nregistrations as well.\n\nSuggested-by: Patrick Steinhardt <ps@pks.im>\nSigned-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>\n---\n Makefile                  |  1 -\n t/helper/meson.build      |  1 -\n t/helper/test-mergesort.c | 67 ---------------------------------------\n t/helper/test-tool.c      |  1 -\n t/helper/test-tool.h      |  1 -\n t/meson.build             |  1 -\n t/perf/p0071-sort.sh      | 52 ------------------------------\n 7 files changed, 124 deletions(-)\n delete mode 100644 t/helper/test-mergesort.c\n delete mode 100755 t/perf/p0071-sort.sh\n\ndiff --git a/Makefile b/Makefile\nindex cac535ba19..4b35808b2e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -835,7 +835,6 @@ TEST_BUILTINS_OBJS += test-hexdump.o\n TEST_BUILTINS_OBJS += test-json-writer.o\n TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o\n TEST_BUILTINS_OBJS += test-match-trees.o\n-TEST_BUILTINS_OBJS += test-mergesort.o\n TEST_BUILTINS_OBJS += test-mktemp.o\n TEST_BUILTINS_OBJS += test-name-hash.o\n TEST_BUILTINS_OBJS += test-online-cpus.o\ndiff --git a/t/helper/meson.build b/t/helper/meson.build\nindex 3235f10ab8..e94e6f10fb 100644\n--- a/t/helper/meson.build\n+++ b/t/helper/meson.build\n@@ -32,7 +32,6 @@ test_tool_sources = [\n   'test-json-writer.c',\n   'test-lazy-init-name-hash.c',\n   'test-match-trees.c',\n-  'test-mergesort.c',\n   'test-mktemp.c',\n   'test-name-hash.c',\n   'test-online-cpus.c',\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\ndeleted file mode 100644\nindex e8b8de239b..0000000000\n--- a/t/helper/test-mergesort.c\n+++ /dev/null\n@@ -1,67 +0,0 @@\n-#include \"test-tool.h\"\n-#include \"mem-pool.h\"\n-#include \"mergesort.h\"\n-#include \"strbuf.h\"\n-\n-struct line {\n-\tchar *text;\n-\tstruct line *next;\n-};\n-\n-DEFINE_LIST_SORT(static, sort_lines, struct line, next);\n-\n-static int compare_strings(const struct line *x, const struct line *y)\n-{\n-\treturn strcmp(x->text, y->text);\n-}\n-\n-static int sort_stdin(void)\n-{\n-\tstruct line *lines;\n-\tstruct line **tail = &lines;\n-\tstruct strbuf sb = STRBUF_INIT;\n-\tstruct mem_pool lines_pool;\n-\tchar *p;\n-\n-\tstrbuf_read(&sb, 0, 0);\n-\n-\t/*\n-\t * Split by newline, but don't create an item\n-\t * for the empty string after the last separator.\n-\t */\n-\tif (sb.len && sb.buf[sb.len - 1] == '\\n')\n-\t\tstrbuf_setlen(&sb, sb.len - 1);\n-\n-\tmem_pool_init(&lines_pool, 0);\n-\tp = sb.buf;\n-\tfor (;;) {\n-\t\tchar *eol = strchr(p, '\\n');\n-\t\tstruct line *line = mem_pool_alloc(&lines_pool, sizeof(*line));\n-\t\tline->text = p;\n-\t\t*tail = line;\n-\t\ttail = &line->next;\n-\t\tif (!eol)\n-\t\t\tbreak;\n-\t\t*eol = '\\0';\n-\t\tp = eol + 1;\n-\t}\n-\t*tail = NULL;\n-\n-\tsort_lines(&lines, compare_strings);\n-\n-\twhile (lines) {\n-\t\tputs(lines->text);\n-\t\tlines = lines->next;\n-\t}\n-\tmem_pool_discard(&lines_pool, 0);\n-\tstrbuf_release(&sb);\n-\treturn 0;\n-}\n-\n-int cmd__mergesort(int argc, const char **argv)\n-{\n-\tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n-\t\treturn sort_stdin();\n-\tfprintf(stderr, \"usage: test-tool mergesort sort\\n\");\n-\treturn 129;\n-}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex b71a22b43b..2e80dc7ab8 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -42,7 +42,6 @@ static struct test_cmd cmds[] = {\n \t{ \"json-writer\", cmd__json_writer },\n \t{ \"lazy-init-name-hash\", cmd__lazy_init_name_hash },\n \t{ \"match-trees\", cmd__match_trees },\n-\t{ \"mergesort\", cmd__mergesort },\n \t{ \"mktemp\", cmd__mktemp },\n \t{ \"name-hash\", cmd__name_hash },\n \t{ \"online-cpus\", cmd__online_cpus },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex f2885b33d5..9442c61ffd 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -35,7 +35,6 @@ int cmd__hexdump(int argc, const char **argv);\n int cmd__json_writer(int argc, const char **argv);\n int cmd__lazy_init_name_hash(int argc, const char **argv);\n int cmd__match_trees(int argc, const char **argv);\n-int cmd__mergesort(int argc, const char **argv);\n int cmd__mktemp(int argc, const char **argv);\n int cmd__name_hash(int argc, const char **argv);\n int cmd__online_cpus(int argc, const char **argv);\ndiff --git a/t/meson.build b/t/meson.build\nindex 2752321e0d..07436b63f4 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -1146,7 +1146,6 @@ benchmarks = [\n   'perf/p0006-read-tree-checkout.sh',\n   'perf/p0007-write-cache.sh',\n   'perf/p0008-odb-fsync.sh',\n-  'perf/p0071-sort.sh',\n   'perf/p0090-cache-tree.sh',\n   'perf/p0100-globbing.sh',\n   'perf/p1006-cat-file.sh',\ndiff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh\ndeleted file mode 100755\nindex ae4ddac864..0000000000\n--- a/t/perf/p0071-sort.sh\n+++ /dev/null\n@@ -1,52 +0,0 @@\n-#!/bin/sh\n-\n-test_description='Basic sort performance tests'\n-. ./perf-lib.sh\n-\n-test_perf_default_repo\n-\n-test_expect_success 'setup' '\n-\tgit ls-files --stage \"*.[ch]\" \"*.sh\" |\n-\tcut -f2 -d\" \" |\n-\tgit cat-file --batch >unsorted\n-'\n-\n-test_perf 'sort(1) unsorted' '\n-\tsort <unsorted >sorted\n-'\n-\n-test_expect_success 'reverse' '\n-\tsort -r <unsorted >reversed\n-'\n-\n-for file in sorted reversed\n-do\n-\ttest_perf \"sort(1) $file\" \"\n-\t\tsort <$file >actual\n-\t\"\n-done\n-\n-for file in unsorted sorted reversed\n-do\n-\n-\ttest_perf \"string_list_sort() $file\" \"\n-\t\ttest-tool string-list sort <$file >actual\n-\t\"\n-\n-\ttest_expect_success \"string_list_sort() $file sorts like sort(1)\" \"\n-\t\ttest_cmp_bin sorted actual\n-\t\"\n-done\n-\n-for file in unsorted sorted reversed\n-do\n-\ttest_perf \"DEFINE_LIST_SORT $file\" \"\n-\t\ttest-tool mergesort sort <$file >actual\n-\t\"\n-\n-\ttest_expect_success \"DEFINE_LIST_SORT $file sorts like sort(1)\" \"\n-\t\ttest_cmp_bin sorted actual\n-\t\"\n-done\n-\n-test_done\n-- \n2.55.0\n\n\n"},{"id":"554395","messageId":"xmqqzewp8lqw.fsf@gitster.g","threadId":"66479","inReplyTo":"asXi-1RlWhqPMWjL@pks.im","subject":"Re: [PATCH] test-mergesort: plug memory leaks in sort_stdin()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-10-07T17:27:03Z","receivedAt":"2026-10-07T17:27:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> I was briefly wondering whether we could get rid of t0071 altogether in\n> favor of converting the tests into a unit test, and then drop the test\n> helper. And that's certainly doable, and I'd argue it would also be the\n> right thing to do.\n\nYup, unlike any \"test-tool\" feature that is specific to some Git\noperation, things like mergesort does not need to be part of\nend-to-end t[0-9]{4}-*.sh test suite.\n\n> But anyway, that's of course a much bigger scope, and I'm fine to just\n> fix the bugs for now.\n\n;-).\n\n> I noticed that there's another \"generate\" subcommand here that is\n> entirely unused. Do we maybe want to also remove it while at it? The\n> test suite passes with the below diff.\n\nGreat.\n\nThanks.\n\n"},{"id":"554583","messageId":"asjVhlTj3MqHcGm4@pks.im","threadId":"66479","inReplyTo":"0429552774367ddcc3c2fda78e09a83650ccfa02.1791365181.git.dilsheddilu123@gmail.com","subject":"Re: [PATCH v2 2/3] mergesort: move sorting tests to the unit-test framework","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-10-09T11:52:38Z","receivedAt":"2026-10-09T11:52:38Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Oct 07, 2026 at 07:20:24PM +0530, Muhammed Dilshad A wrote:\n> The mergesort certification checks exercise C code directly, so they do\n> not need a shell test and test-tool command. Move their distributions and\n> transformations to Clar, retaining the sorted-value, stability and list\n> length checks. Add small cases for both list sort macros and debug hooks.\n> \n> Keep node storage available to the cleanup fixture and bound validation\n> so a failed assertion can release it without walking a broken list.\n\nWat...? I have no idea what this means.\n\nI would appreciate it if you would read through the AI generated\nmessages and ask yourself whether a normal human being would understand\nwhat was being generated. In general, we ask you to fully vet all of the\nstuff that is being generated, understand it and convert it into a form\nthat normal human beings understand.\n\nA commit message is _your_ chance to demonstrate that you understand\nwhat you're contributing. If it's this obviously AI generated it raises\na huge red flag as I will immediately assume that you haven't read any\nof the code it wrote.\n\n> diff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c\n> new file mode 100644\n> index 0000000000..e621c9ec21\n> --- /dev/null\n> +++ b/t/unit-tests/u-mergesort.c\n> @@ -0,0 +1,369 @@\n> +#include \"unit-test.h\"\n> +#include \"mergesort.h\"\n> +\n> +static uint32_t minstd_rand(uint32_t *state)\n\nAll of these distributions are kinda cute. But is it really required to\ntest the merge sort with half a dozen different distributions? I dunno,\ncolor me sceptical.\n\nThat being said, you just retain the old status quo, so okay.\n\n[snip]\n> +#define DIST(name) { #name, dist_##name }\n> +\n> +static struct dist {\n> +\tconst char *name;\n> +\tvoid (*fn)(int *arr, int n, int m);\n> +} dist[] = {\n> +\tDIST(sawtooth),\n> +\tDIST(rand),\n> +\tDIST(stagger),\n> +\tDIST(plateau),\n> +\tDIST(shuffle),\n> +};\n\nThis also feels quite overengineered now for the unit test infra.\n\n[snip]\n> +#define MODE(name) { #name, mode_##name }\n> +\n> +static struct mode {\n> +\tconst char *name;\n> +\tvoid (*fn)(int *arr, int n);\n> +} mode[] = {\n> +\tMODE(copy),\n> +\tMODE(reverse),\n> +\tMODE(reverse_1st_half),\n> +\tMODE(reverse_2nd_half),\n> +\tMODE(sort),\n> +\tMODE(dither),\n> +\tMODE(unriffle),\n> +\tMODE(unriffle_skewed),\n> +};\n\nSame. All of this is way too overengineered. It probably was useful at\none point in time to show performance with these different modes and\ndistributions. But even with the performance test we don't use those at\nall anymore, so it just feels needlessly complex by now.\n\nPatrick\n\n"},{"id":"554584","messageId":"asjVkwUYJI6wERWf@pks.im","threadId":"66479","inReplyTo":"cover.1791365181.git.dilsheddilu123@gmail.com","subject":"Re: [PATCH v2 0/3] mergesort: move tests to Clar and retire the helper","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-10-09T11:52:51Z","receivedAt":"2026-10-09T11:52:51Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nOn Wed, Oct 07, 2026 at 07:20:22PM +0530, Muhammed Dilshad A wrote:\n> Hi Patrick,\n> \n> Thanks for the review. I followed up on the larger cleanup you mentioned.\n> The sorting tests now run in Clar, and I have removed the old benchmark\n> and its helper. This also removes the unused generate subcommand.\n\nplease reply to reviews individually instead of replying in the cover\nletter.\n\n> The new suite keeps all 1,680 cases from the old certification test and\n> adds checks for empty and small lists using both sort macros. It checks\n> sorting order, stability and list length. Cleanup frees the backing\n> arrays directly, so a failed assertion does not need to walk list links.\n\nIt would have made it easier to review if the new tests were added in a\nseparate commit.\n\n> Changes since v1:\n> \n> * Patch 1 is unchanged.\n> * Patch 2 moves the tests to Clar and removes the unused generate and\n>   test commands. The sort command remains available for the benchmark.\n> * Patch 3 removes p0071 and the remaining sort helper, along with their\n>   build and command registrations.\n> \n> I kept the leak fix first so it can still be applied on its own if you\n> would prefer to keep the broader cleanup for a separate series.\n\nI dunno, I feel like that's not quite useful. If we didn't want to take\nthe broader cleanup we'd instead apply v1 of your seires. In this\nversion of the patch series it's plain unnecessary churn because we\nremove the code anyway.\n\n> The Make and Meson unit tests pass, and the mergesort unit suite also\n> passes with LeakSanitizer enabled. The production sorting implementation\n> is unchanged.\n\nThis information is quite curious, as it makes me wonder why it is even\nnoteworthy to point out. My basic assumption is that folks who send a\nseries to the mailing list test their stuff, so there is no need to\nexplicitly say so.\n\nI mean I of course know why this is here: it's the typical \"let's check\nall the boxes\" output that AI is so happy to generate. *sigh*\n\nPatrick\n\n"},{"id":"554604","messageId":"20261009135529.141444-1-dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"asjVhlTj3MqHcGm4@pks.im","subject":"Re: [PATCH v2 2/3] mergesort: move sorting tests to the unit-test framework","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-09T13:55:29Z","receivedAt":"2026-10-09T13:55:29Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"Hi Patrick,\n\nSorry, I didn't explain that clearly. The list items are stored in one\nallocated array. Cleanup frees that array directly, so it does not have\nto follow possibly broken list links.\n\nI'll go through the code and simplify the test setup before sending\nanother version. I'll also rewrite the commit message to explain the\nchanges clearly.\n\nRegards,\nDilshad\n\n"},{"id":"554605","messageId":"20261009135654.141970-1-dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"asjVkwUYJI6wERWf@pks.im","subject":"Re: [PATCH v2 0/3] mergesort: move tests to Clar and retire the helper","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-09T13:56:54Z","receivedAt":"2026-10-09T13:56:54Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"Hi Patrick,\n\nI'll keep review replies separate from the cover letter from now on.\n\nI'll drop the leak fix from the next version since that helper is being\nremoved anyway, and put the new tests in a separate commit. I'll keep\nthe cover letter focused on what the series changes.\n\nRegards,\nDilshad\n\n"},{"id":"554608","messageId":"cover.1791556668.git.dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"cover.1791365181.git.dilsheddilu123@gmail.com","subject":"[PATCH v3 0/4] mergesort: move tests to Clar and remove the helper","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-09T15:08:46Z","receivedAt":"2026-10-09T15:08:46Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"Move the mergesort checks from the shell test and helper into Clar, where\nthe tests call the sort functions directly.\n\nSimplify the old distribution/mode grid to direct tests for sorted,\nreversed, equal-value and repeatable random input. Keep the checks for\nsorted values, the original order of equal values, and list length. Add\nempty and small-list cases and a check of the debug hooks separately.\nThe final tests cover fewer input combinations than the old certification\ntest.\n\nRetire p0071, the benchmark used to compare sorting implementations.\nThis removes the last user of the mergesort helper, so remove that too.\n\nThe migration, simplification, additional tests and benchmark removal are\nseparate commits.\n\nChanges since v2:\n\n* Drop the leak-fix patch, since this series removes the helper.\n* Simplify the test inputs and remove the distribution/mode tables.\n* Put the additional tests in their own commit.\n* Rewrite the commit messages to explain the changes more clearly.\n\nMuhammed Dilshad A (4):\n  mergesort: move sorting tests to Clar\n  mergesort: simplify the unit tests\n  mergesort: cover empty and small lists\n  t: retire the sorting benchmark and mergesort helper\n\n Makefile                   |   2 +-\n t/helper/meson.build       |   1 -\n t/helper/test-mergesort.c  | 408 -------------------------------------\n t/helper/test-tool.c       |   1 -\n t/helper/test-tool.h       |   1 -\n t/meson.build              |   3 +-\n t/perf/p0071-sort.sh       |  52 -----\n t/t0071-sort.sh            |  11 -\n t/unit-tests/u-mergesort.c | 168 +++++++++++++++\n 9 files changed, 170 insertions(+), 477 deletions(-)\n delete mode 100644 t/helper/test-mergesort.c\n delete mode 100755 t/perf/p0071-sort.sh\n delete mode 100755 t/t0071-sort.sh\n create mode 100644 t/unit-tests/u-mergesort.c\n\n\nbase-commit: 6de20f6092dcf9bdb1c8efe03db4b70c82b423dd\n-- \n2.55.0\n\n\n"},{"id":"554609","messageId":"21f46a2c9046d1da68233467bafb4b69226f35e6.1791556668.git.dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"cover.1791556668.git.dilsheddilu123@gmail.com","subject":"[PATCH v3 1/4] mergesort: move sorting tests to Clar","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-09T15:08:47Z","receivedAt":"2026-10-09T15:08:47Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"The numeric sorting tests only use mergesort.h. Move them from test-tool\nto Clar, keeping the same inputs and checks for sorted order, stable\nordering of equal values, and list length.\n\nStore the list items in an array so cleanup can free them even if the\nsort leaves the links broken.\n\nRemove t0071 and the helper's generate and test commands. Keep the sort\ncommand for p0071 for now.\n\nSuggested-by: Patrick Steinhardt <ps@pks.im>\nSigned-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>\n---\n Makefile                   |   1 +\n t/helper/test-mergesort.c  | 345 +------------------------------------\n t/meson.build              |   2 +-\n t/t0071-sort.sh            |  11 --\n t/unit-tests/u-mergesort.c | 288 +++++++++++++++++++++++++++++++\n 5 files changed, 291 insertions(+), 356 deletions(-)\n delete mode 100755 t/t0071-sort.sh\n create mode 100644 t/unit-tests/u-mergesort.c\n\ndiff --git a/Makefile b/Makefile\nindex a96be506b5..cac535ba19 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1541,6 +1541,7 @@ CLAR_TEST_SUITES += u-hash\n CLAR_TEST_SUITES += u-hashmap\n CLAR_TEST_SUITES += u-list-objects-filter-options\n CLAR_TEST_SUITES += u-mem-pool\n+CLAR_TEST_SUITES += u-mergesort\n CLAR_TEST_SUITES += u-odb-inmemory\n CLAR_TEST_SUITES += u-oid-array\n CLAR_TEST_SUITES += u-oidmap\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 791e128793..d22a139f9e 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -1,16 +1,8 @@\n-#define DISABLE_SIGN_COMPARE_WARNINGS\n-\n #include \"test-tool.h\"\n #include \"mem-pool.h\"\n #include \"mergesort.h\"\n #include \"strbuf.h\"\n \n-static uint32_t minstd_rand(uint32_t *state)\n-{\n-\t*state = (uint64_t)*state * 48271 % 2147483647;\n-\treturn *state;\n-}\n-\n struct line {\n \tchar *text;\n \tstruct line *next;\n@@ -64,345 +56,10 @@ static int sort_stdin(void)\n \treturn 0;\n }\n \n-static void dist_sawtooth(int *arr, int n, int m)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = i % m;\n-}\n-\n-static void dist_rand(int *arr, int n, int m)\n-{\n-\tint i;\n-\tuint32_t seed = 1;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = minstd_rand(&seed) % m;\n-}\n-\n-static void dist_stagger(int *arr, int n, int m)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = (i * m + i) % n;\n-}\n-\n-static void dist_plateau(int *arr, int n, int m)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = (i < m) ? i : m;\n-}\n-\n-static void dist_shuffle(int *arr, int n, int m)\n-{\n-\tint i, j, k;\n-\tuint32_t seed = 1;\n-\tfor (i = j = 0, k = 1; i < n; i++)\n-\t\tarr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);\n-}\n-\n-#define DIST(name) { #name, dist_##name }\n-\n-static struct dist {\n-\tconst char *name;\n-\tvoid (*fn)(int *arr, int n, int m);\n-} dist[] = {\n-\tDIST(sawtooth),\n-\tDIST(rand),\n-\tDIST(stagger),\n-\tDIST(plateau),\n-\tDIST(shuffle),\n-};\n-\n-static const struct dist *get_dist_by_name(const char *name)\n-{\n-\tint i;\n-\tfor (i = 0; i < ARRAY_SIZE(dist); i++) {\n-\t       if (!strcmp(dist[i].name, name))\n-\t\t       return &dist[i];\n-\t}\n-\treturn NULL;\n-}\n-\n-static void mode_copy(int *arr UNUSED, int n UNUSED)\n-{\n-\t/* nothing */\n-}\n-\n-static void mode_reverse(int *arr, int n)\n-{\n-\tint i, j;\n-\tfor (i = 0, j = n - 1; i < j; i++, j--)\n-\t\tSWAP(arr[i], arr[j]);\n-}\n-\n-static void mode_reverse_1st_half(int *arr, int n)\n-{\n-\tmode_reverse(arr, n / 2);\n-}\n-\n-static void mode_reverse_2nd_half(int *arr, int n)\n-{\n-\tint half = n / 2;\n-\tmode_reverse(arr + half, n - half);\n-}\n-\n-static int compare_ints(const void *av, const void *bv)\n-{\n-\tconst int *ap = av, *bp = bv;\n-\tint a = *ap, b = *bp;\n-\treturn (a > b) - (a < b);\n-}\n-\n-static void mode_sort(int *arr, int n)\n-{\n-\tQSORT(arr, n, compare_ints);\n-}\n-\n-static void mode_dither(int *arr, int n)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] += i % 5;\n-}\n-\n-static void unriffle(int *arr, int n, int *tmp)\n-{\n-\tint i, j;\n-\tCOPY_ARRAY(tmp, arr, n);\n-\tfor (i = j = 0; i < n; i += 2)\n-\t\tarr[j++] = tmp[i];\n-\tfor (i = 1; i < n; i += 2)\n-\t\tarr[j++] = tmp[i];\n-}\n-\n-static void unriffle_recursively(int *arr, int n, int *tmp)\n-{\n-\tif (n > 1) {\n-\t\tint half = n / 2;\n-\t\tunriffle(arr, n, tmp);\n-\t\tunriffle_recursively(arr, half, tmp);\n-\t\tunriffle_recursively(arr + half, n - half, tmp);\n-\t}\n-}\n-\n-static void mode_unriffle(int *arr, int n)\n-{\n-\tint *tmp;\n-\tALLOC_ARRAY(tmp, n);\n-\tunriffle_recursively(arr, n, tmp);\n-\tfree(tmp);\n-}\n-\n-static unsigned int prev_pow2(unsigned int n)\n-{\n-\tunsigned int pow2 = 1;\n-\twhile (pow2 * 2 < n)\n-\t\tpow2 *= 2;\n-\treturn pow2;\n-}\n-\n-static void unriffle_recursively_skewed(int *arr, int n, int *tmp)\n-{\n-\tif (n > 1) {\n-\t\tint pow2 = prev_pow2(n);\n-\t\tint rest = n - pow2;\n-\t\tunriffle(arr + pow2 - rest, rest * 2, tmp);\n-\t\tunriffle_recursively_skewed(arr, pow2, tmp);\n-\t\tunriffle_recursively_skewed(arr + pow2, rest, tmp);\n-\t}\n-}\n-\n-static void mode_unriffle_skewed(int *arr, int n)\n-{\n-\tint *tmp;\n-\tALLOC_ARRAY(tmp, n);\n-\tunriffle_recursively_skewed(arr, n, tmp);\n-\tfree(tmp);\n-}\n-\n-#define MODE(name) { #name, mode_##name }\n-\n-static struct mode {\n-\tconst char *name;\n-\tvoid (*fn)(int *arr, int n);\n-} mode[] = {\n-\tMODE(copy),\n-\tMODE(reverse),\n-\tMODE(reverse_1st_half),\n-\tMODE(reverse_2nd_half),\n-\tMODE(sort),\n-\tMODE(dither),\n-\tMODE(unriffle),\n-\tMODE(unriffle_skewed),\n-};\n-\n-static const struct mode *get_mode_by_name(const char *name)\n-{\n-\tint i;\n-\tfor (i = 0; i < ARRAY_SIZE(mode); i++) {\n-\t       if (!strcmp(mode[i].name, name))\n-\t\t       return &mode[i];\n-\t}\n-\treturn NULL;\n-}\n-\n-static int generate(int argc, const char **argv)\n-{\n-\tconst struct dist *dist = NULL;\n-\tconst struct mode *mode = NULL;\n-\tint i, n, m, *arr;\n-\n-\tif (argc != 4)\n-\t\treturn 1;\n-\n-\tdist = get_dist_by_name(argv[0]);\n-\tmode = get_mode_by_name(argv[1]);\n-\tn = strtol(argv[2], NULL, 10);\n-\tm = strtol(argv[3], NULL, 10);\n-\tif (!dist || !mode)\n-\t\treturn 1;\n-\n-\tALLOC_ARRAY(arr, n);\n-\tdist->fn(arr, n, m);\n-\tmode->fn(arr, n);\n-\tfor (i = 0; i < n; i++)\n-\t\tprintf(\"%08x\\n\", arr[i]);\n-\tfree(arr);\n-\treturn 0;\n-}\n-\n-static struct stats {\n-\tint get_next, set_next, compare;\n-} stats;\n-\n-struct number {\n-\tint value, rank;\n-\tstruct number *next;\n-};\n-\n-DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,\n-\t\t       stats.get_next++, stats.set_next++);\n-\n-static int compare_numbers(const struct number *an, const struct number *bn)\n-{\n-\tint a = an->value, b = bn->value;\n-\tstats.compare++;\n-\treturn (a > b) - (a < b);\n-}\n-\n-static void clear_numbers(struct number *list)\n-{\n-\twhile (list) {\n-\t\tstruct number *next = list->next;\n-\t\tfree(list);\n-\t\tlist = next;\n-\t}\n-}\n-\n-static int test(const struct dist *dist, const struct mode *mode, int n, int m)\n-{\n-\tint *arr;\n-\tsize_t i;\n-\tstruct number *curr, *list, **tail;\n-\tint is_sorted = 1;\n-\tint is_stable = 1;\n-\tconst char *verdict;\n-\tint result = -1;\n-\n-\tALLOC_ARRAY(arr, n);\n-\tdist->fn(arr, n, m);\n-\tmode->fn(arr, n);\n-\tfor (i = 0, tail = &list; i < n; i++) {\n-\t\tcurr = xmalloc(sizeof(*curr));\n-\t\tcurr->value = arr[i];\n-\t\tcurr->rank = i;\n-\t\t*tail = curr;\n-\t\ttail = &curr->next;\n-\t}\n-\t*tail = NULL;\n-\n-\tstats.get_next = stats.set_next = stats.compare = 0;\n-\tsort_numbers(&list, compare_numbers);\n-\n-\tQSORT(arr, n, compare_ints);\n-\tfor (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {\n-\t\tif (arr[i] != curr->value)\n-\t\t\tis_sorted = 0;\n-\t\tif (curr->next && curr->value == curr->next->value &&\n-\t\t    curr->rank >= curr->next->rank)\n-\t\t\tis_stable = 0;\n-\t}\n-\tif (i < n) {\n-\t\tverdict = \"too short\";\n-\t} else if (curr) {\n-\t\tverdict = \"too long\";\n-\t} else if (!is_sorted) {\n-\t\tverdict = \"not sorted\";\n-\t} else if (!is_stable) {\n-\t\tverdict = \"unstable\";\n-\t} else {\n-\t\tverdict = \"OK\";\n-\t\tresult = 0;\n-\t}\n-\n-\tprintf(\"%-9s %-16s %8d %8d %8d %8d %8d %s\\n\",\n-\t       dist->name, mode->name, n, m, stats.get_next, stats.set_next,\n-\t       stats.compare, verdict);\n-\n-\tclear_numbers(list);\n-\tfree(arr);\n-\n-\treturn result;\n-}\n-\n-/*\n- * A version of the qsort certification program from \"Engineering a Sort\n- * Function\" by Bentley and McIlroy, Software—Practice and Experience,\n- * Volume 23, Issue 11, 1249–1265 (November 1993).\n- */\n-static int run_tests(int argc, const char **argv)\n-{\n-\tconst char *argv_default[] = { \"100\", \"1023\", \"1024\", \"1025\" };\n-\tif (!argc)\n-\t\treturn run_tests(ARRAY_SIZE(argv_default), argv_default);\n-\tprintf(\"%-9s %-16s %8s %8s %8s %8s %8s %s\\n\",\n-\t       \"distribut\", \"mode\", \"n\", \"m\", \"get_next\", \"set_next\",\n-\t       \"compare\", \"verdict\");\n-\twhile (argc--) {\n-\t\tint i, j, m, n = strtol(*argv++, NULL, 10);\n-\t\tfor (i = 0; i < ARRAY_SIZE(dist); i++) {\n-\t\t\tfor (j = 0; j < ARRAY_SIZE(mode); j++) {\n-\t\t\t\tfor (m = 1; m < 2 * n; m *= 2) {\n-\t\t\t\t\tif (test(&dist[i], &mode[j], n, m))\n-\t\t\t\t\t\treturn 1;\n-\t\t\t\t}\n-\t\t\t}\n-\t\t}\n-\t}\n-\treturn 0;\n-}\n-\n int cmd__mergesort(int argc, const char **argv)\n {\n-\tint i;\n-\tconst char *sep;\n-\n-\tif (argc == 6 && !strcmp(argv[1], \"generate\"))\n-\t\treturn generate(argc - 2, argv + 2);\n \tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n \t\treturn sort_stdin();\n-\tif (argc > 1 && !strcmp(argv[1], \"test\"))\n-\t\treturn run_tests(argc - 2, argv + 2);\n-\tfprintf(stderr, \"usage: test-tool mergesort generate <distribution> <mode> <n> <m>\\n\");\n-\tfprintf(stderr, \"   or: test-tool mergesort sort\\n\");\n-\tfprintf(stderr, \"   or: test-tool mergesort test [<n>...]\\n\");\n-\tfprintf(stderr, \"\\n\");\n-\tfor (i = 0, sep = \"distributions: \"; i < ARRAY_SIZE(dist); i++, sep = \", \")\n-\t\tfprintf(stderr, \"%s%s\", sep, dist[i].name);\n-\tfprintf(stderr, \"\\n\");\n-\tfor (i = 0, sep = \"modes: \"; i < ARRAY_SIZE(mode); i++, sep = \", \")\n-\t\tfprintf(stderr, \"%s%s\", sep, mode[i].name);\n-\tfprintf(stderr, \"\\n\");\n+\tfprintf(stderr, \"usage: test-tool mergesort sort\\n\");\n \treturn 129;\n }\ndiff --git a/t/meson.build b/t/meson.build\nindex f65eb04684..2752321e0d 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -6,6 +6,7 @@ clar_test_suites = [\n   'unit-tests/u-hashmap.c',\n   'unit-tests/u-list-objects-filter-options.c',\n   'unit-tests/u-mem-pool.c',\n+  'unit-tests/u-mergesort.c',\n   'unit-tests/u-odb-inmemory.c',\n   'unit-tests/u-oid-array.c',\n   'unit-tests/u-oidmap.c',\n@@ -119,7 +120,6 @@ integration_tests = [\n   't0067-parse_pathspec_file.sh',\n   't0068-for-each-repo.sh',\n   't0070-fundamental.sh',\n-  't0071-sort.sh',\n   't0080-unit-test-output.sh',\n   't0081-find-pack.sh',\n   't0090-cache-tree.sh',\ndiff --git a/t/t0071-sort.sh b/t/t0071-sort.sh\ndeleted file mode 100755\nindex 2236a7e956..0000000000\n--- a/t/t0071-sort.sh\n+++ /dev/null\n@@ -1,11 +0,0 @@\n-#!/bin/sh\n-\n-test_description='verify sort functions'\n-\n-. ./test-lib.sh\n-\n-test_expect_success 'DEFINE_LIST_SORT_DEBUG' '\n-\ttest-tool mergesort test\n-'\n-\n-test_done\ndiff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c\nnew file mode 100644\nindex 0000000000..56646b020b\n--- /dev/null\n+++ b/t/unit-tests/u-mergesort.c\n@@ -0,0 +1,288 @@\n+#include \"unit-test.h\"\n+#include \"mergesort.h\"\n+\n+static uint32_t minstd_rand(uint32_t *state)\n+{\n+\t*state = (uint64_t)*state * 48271 % 2147483647;\n+\treturn *state;\n+}\n+\n+static void dist_sawtooth(int *arr, int n, int m)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = i % m;\n+}\n+\n+static void dist_rand(int *arr, int n, int m)\n+{\n+\tint i;\n+\tuint32_t seed = 1;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = minstd_rand(&seed) % m;\n+}\n+\n+static void dist_stagger(int *arr, int n, int m)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = (i * m + i) % n;\n+}\n+\n+static void dist_plateau(int *arr, int n, int m)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = (i < m) ? i : m;\n+}\n+\n+static void dist_shuffle(int *arr, int n, int m)\n+{\n+\tint i, j, k;\n+\tuint32_t seed = 1;\n+\tfor (i = j = 0, k = 1; i < n; i++)\n+\t\tarr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);\n+}\n+\n+#define DIST(name) { #name, dist_##name }\n+\n+static struct dist {\n+\tconst char *name;\n+\tvoid (*fn)(int *arr, int n, int m);\n+} dist[] = {\n+\tDIST(sawtooth),\n+\tDIST(rand),\n+\tDIST(stagger),\n+\tDIST(plateau),\n+\tDIST(shuffle),\n+};\n+\n+static void mode_copy(int *arr UNUSED, int n UNUSED)\n+{\n+\t/* nothing */\n+}\n+\n+static void mode_reverse(int *arr, int n)\n+{\n+\tint i, j;\n+\tfor (i = 0, j = n - 1; i < j; i++, j--)\n+\t\tSWAP(arr[i], arr[j]);\n+}\n+\n+static void mode_reverse_1st_half(int *arr, int n)\n+{\n+\tmode_reverse(arr, n / 2);\n+}\n+\n+static void mode_reverse_2nd_half(int *arr, int n)\n+{\n+\tint half = n / 2;\n+\tmode_reverse(arr + half, n - half);\n+}\n+\n+static int compare_ints(const void *av, const void *bv)\n+{\n+\tconst int *ap = av, *bp = bv;\n+\tint a = *ap, b = *bp;\n+\treturn (a > b) - (a < b);\n+}\n+\n+static void mode_sort(int *arr, int n)\n+{\n+\tQSORT(arr, n, compare_ints);\n+}\n+\n+static void mode_dither(int *arr, int n)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] += i % 5;\n+}\n+\n+static void unriffle(int *arr, int n, int *tmp)\n+{\n+\tint i, j;\n+\tCOPY_ARRAY(tmp, arr, n);\n+\tfor (i = j = 0; i < n; i += 2)\n+\t\tarr[j++] = tmp[i];\n+\tfor (i = 1; i < n; i += 2)\n+\t\tarr[j++] = tmp[i];\n+}\n+\n+static void unriffle_recursively(int *arr, int n, int *tmp)\n+{\n+\tif (n > 1) {\n+\t\tint half = n / 2;\n+\t\tunriffle(arr, n, tmp);\n+\t\tunriffle_recursively(arr, half, tmp);\n+\t\tunriffle_recursively(arr + half, n - half, tmp);\n+\t}\n+}\n+\n+static void mode_unriffle(int *arr, int n)\n+{\n+\tint *tmp;\n+\tALLOC_ARRAY(tmp, n);\n+\tunriffle_recursively(arr, n, tmp);\n+\tfree(tmp);\n+}\n+\n+static unsigned int prev_pow2(unsigned int n)\n+{\n+\tunsigned int pow2 = 1;\n+\twhile (pow2 * 2 < n)\n+\t\tpow2 *= 2;\n+\treturn pow2;\n+}\n+\n+static void unriffle_recursively_skewed(int *arr, int n, int *tmp)\n+{\n+\tif (n > 1) {\n+\t\tint pow2 = prev_pow2(n);\n+\t\tint rest = n - pow2;\n+\t\tunriffle(arr + pow2 - rest, rest * 2, tmp);\n+\t\tunriffle_recursively_skewed(arr, pow2, tmp);\n+\t\tunriffle_recursively_skewed(arr + pow2, rest, tmp);\n+\t}\n+}\n+\n+static void mode_unriffle_skewed(int *arr, int n)\n+{\n+\tint *tmp;\n+\tALLOC_ARRAY(tmp, n);\n+\tunriffle_recursively_skewed(arr, n, tmp);\n+\tfree(tmp);\n+}\n+\n+#define MODE(name) { #name, mode_##name }\n+\n+static struct mode {\n+\tconst char *name;\n+\tvoid (*fn)(int *arr, int n);\n+} mode[] = {\n+\tMODE(copy),\n+\tMODE(reverse),\n+\tMODE(reverse_1st_half),\n+\tMODE(reverse_2nd_half),\n+\tMODE(sort),\n+\tMODE(dither),\n+\tMODE(unriffle),\n+\tMODE(unriffle_skewed),\n+};\n+\n+struct number {\n+\tint value, rank;\n+\tstruct number *next;\n+};\n+\n+DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,\n+\t\t       (void)0, (void)0);\n+\n+static int compare_numbers(const struct number *an, const struct number *bn)\n+{\n+\tint a = an->value, b = bn->value;\n+\treturn (a > b) - (a < b);\n+}\n+\n+/* Free the storage directly, even if an assertion fails on a broken list. */\n+static int *values;\n+static struct number *numbers;\n+\n+void test_mergesort__cleanup(void)\n+{\n+\tFREE_AND_NULL(values);\n+\tFREE_AND_NULL(numbers);\n+}\n+\n+static struct number *prepare_list(const int *arr, int n)\n+{\n+\tint i;\n+\n+\tALLOC_ARRAY(numbers, n);\n+\tfor (i = 0; i < n; i++) {\n+\t\tnumbers[i].value = arr[i];\n+\t\tnumbers[i].rank = i;\n+\t\tnumbers[i].next = i + 1 < n ? &numbers[i + 1] : NULL;\n+\t}\n+\treturn n ? numbers : NULL;\n+}\n+\n+static void check_list(struct number *list, const int *expected,\n+\t\t       int n, const char *context)\n+{\n+\tstruct number *previous = NULL;\n+\tint i;\n+\n+\t/* Bound traversal so a cycle is reported as an overlong list. */\n+\tfor (i = 0; i < n; i++) {\n+\t\tcl_assert_(list, context);\n+\t\tcl_assert_equal_i_(list->value, expected[i], \"%s: index %d\",\n+\t\t\t\t   context, i);\n+\t\tif (previous && previous->value == list->value)\n+\t\t\tcl_assert_lt_i_(previous->rank, list->rank,\n+\t\t\t\t\t\"%s: stability at index %d\", context, i);\n+\t\tprevious = list;\n+\t\tlist = list->next;\n+\t}\n+\tcl_assert_(list == NULL, context);\n+}\n+\n+/*\n+ * A version of the qsort certification program from \"Engineering a Sort\n+ * Function\" by Bentley and McIlroy, Software—Practice and Experience,\n+ * Volume 23, Issue 11, 1249–1265 (November 1993).\n+ */\n+static void certify(const struct dist *distribution)\n+{\n+\tstatic const int sizes[] = { 100, 1023, 1024, 1025 };\n+\tsize_t i, j;\n+\tint m;\n+\n+\tfor (i = 0; i < ARRAY_SIZE(sizes); i++) {\n+\t\tint n = sizes[i];\n+\n+\t\tfor (j = 0; j < ARRAY_SIZE(mode); j++) {\n+\t\t\tfor (m = 1; m < 2 * n; m *= 2) {\n+\t\t\t\tstruct number *list;\n+\t\t\t\tchar context[128];\n+\n+\t\t\t\txsnprintf(context, sizeof(context),\n+\t\t\t\t\t  \"%s %s n=%d m=%d\",\n+\t\t\t\t\t  distribution->name, mode[j].name, n, m);\n+\t\t\t\tALLOC_ARRAY(values, n);\n+\t\t\t\tdistribution->fn(values, n, m);\n+\t\t\t\tmode[j].fn(values, n);\n+\t\t\t\tlist = prepare_list(values, n);\n+\t\t\t\tsort_numbers(&list, compare_numbers);\n+\t\t\t\tQSORT(values, n, compare_ints);\n+\t\t\t\tcheck_list(list, values, n, context);\n+\t\t\t\ttest_mergesort__cleanup();\n+\t\t\t}\n+\t\t}\n+\t}\n+}\n+\n+void test_mergesort__sawtooth(void)\n+{\n+\tcertify(&dist[0]);\n+}\n+\n+void test_mergesort__rand(void)\n+{\n+\tcertify(&dist[1]);\n+}\n+\n+void test_mergesort__stagger(void)\n+{\n+\tcertify(&dist[2]);\n+}\n+\n+void test_mergesort__plateau(void)\n+{\n+\tcertify(&dist[3]);\n+}\n+\n+void test_mergesort__shuffle(void)\n+{\n+\tcertify(&dist[4]);\n+}\n-- \n2.55.0\n\n\n"},{"id":"554610","messageId":"73ca97b0c721233a0e9d7b3cbc02fcbdf288c579.1791556668.git.dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"cover.1791556668.git.dilsheddilu123@gmail.com","subject":"[PATCH v3 2/4] mergesort: simplify the unit tests","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-09T15:08:48Z","receivedAt":"2026-10-09T15:08:48Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"The old certification test combined several distributions with eight\ntransformations. That setup was useful for comparing sorting algorithms,\nbut it makes these unit tests harder to follow.\n\nReplace the grid and its function tables with direct tests for sorted,\nreversed, equal-value and repeatable random input. Keep the checks for\nsorted values, the original order of equal values, and list length.\nKeep the sizes around 1024 to exercise merges across a power-of-two\nboundary.\n\nSuggested-by: Patrick Steinhardt <ps@pks.im>\nSigned-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>\n---\n t/unit-tests/u-mergesort.c | 301 ++++++++-----------------------------\n 1 file changed, 59 insertions(+), 242 deletions(-)\n\ndiff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c\nindex 56646b020b..50bca1db46 100644\n--- a/t/unit-tests/u-mergesort.c\n+++ b/t/unit-tests/u-mergesort.c\n@@ -1,288 +1,105 @@\n #include \"unit-test.h\"\n #include \"mergesort.h\"\n \n-static uint32_t minstd_rand(uint32_t *state)\n-{\n-\t*state = (uint64_t)*state * 48271 % 2147483647;\n-\treturn *state;\n-}\n-\n-static void dist_sawtooth(int *arr, int n, int m)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = i % m;\n-}\n-\n-static void dist_rand(int *arr, int n, int m)\n-{\n-\tint i;\n-\tuint32_t seed = 1;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = minstd_rand(&seed) % m;\n-}\n-\n-static void dist_stagger(int *arr, int n, int m)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = (i * m + i) % n;\n-}\n-\n-static void dist_plateau(int *arr, int n, int m)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] = (i < m) ? i : m;\n-}\n-\n-static void dist_shuffle(int *arr, int n, int m)\n-{\n-\tint i, j, k;\n-\tuint32_t seed = 1;\n-\tfor (i = j = 0, k = 1; i < n; i++)\n-\t\tarr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);\n-}\n-\n-#define DIST(name) { #name, dist_##name }\n-\n-static struct dist {\n-\tconst char *name;\n-\tvoid (*fn)(int *arr, int n, int m);\n-} dist[] = {\n-\tDIST(sawtooth),\n-\tDIST(rand),\n-\tDIST(stagger),\n-\tDIST(plateau),\n-\tDIST(shuffle),\n+struct number {\n+\tint value;\n+\tsize_t rank;\n+\tstruct number *next;\n };\n \n-static void mode_copy(int *arr UNUSED, int n UNUSED)\n-{\n-\t/* nothing */\n-}\n-\n-static void mode_reverse(int *arr, int n)\n-{\n-\tint i, j;\n-\tfor (i = 0, j = n - 1; i < j; i++, j--)\n-\t\tSWAP(arr[i], arr[j]);\n-}\n-\n-static void mode_reverse_1st_half(int *arr, int n)\n-{\n-\tmode_reverse(arr, n / 2);\n-}\n-\n-static void mode_reverse_2nd_half(int *arr, int n)\n-{\n-\tint half = n / 2;\n-\tmode_reverse(arr + half, n - half);\n-}\n-\n-static int compare_ints(const void *av, const void *bv)\n-{\n-\tconst int *ap = av, *bp = bv;\n-\tint a = *ap, b = *bp;\n-\treturn (a > b) - (a < b);\n-}\n-\n-static void mode_sort(int *arr, int n)\n-{\n-\tQSORT(arr, n, compare_ints);\n-}\n-\n-static void mode_dither(int *arr, int n)\n-{\n-\tint i;\n-\tfor (i = 0; i < n; i++)\n-\t\tarr[i] += i % 5;\n-}\n+DEFINE_LIST_SORT(static, sort_numbers, struct number, next);\n \n-static void unriffle(int *arr, int n, int *tmp)\n+static int compare_numbers(const struct number *a, const struct number *b)\n {\n-\tint i, j;\n-\tCOPY_ARRAY(tmp, arr, n);\n-\tfor (i = j = 0; i < n; i += 2)\n-\t\tarr[j++] = tmp[i];\n-\tfor (i = 1; i < n; i += 2)\n-\t\tarr[j++] = tmp[i];\n+\treturn (a->value > b->value) - (a->value < b->value);\n }\n \n-static void unriffle_recursively(int *arr, int n, int *tmp)\n+static int compare_ints(const void *va, const void *vb)\n {\n-\tif (n > 1) {\n-\t\tint half = n / 2;\n-\t\tunriffle(arr, n, tmp);\n-\t\tunriffle_recursively(arr, half, tmp);\n-\t\tunriffle_recursively(arr + half, n - half, tmp);\n-\t}\n-}\n+\tconst int *a = va, *b = vb;\n \n-static void mode_unriffle(int *arr, int n)\n-{\n-\tint *tmp;\n-\tALLOC_ARRAY(tmp, n);\n-\tunriffle_recursively(arr, n, tmp);\n-\tfree(tmp);\n+\treturn (*a > *b) - (*a < *b);\n }\n \n-static unsigned int prev_pow2(unsigned int n)\n-{\n-\tunsigned int pow2 = 1;\n-\twhile (pow2 * 2 < n)\n-\t\tpow2 *= 2;\n-\treturn pow2;\n-}\n-\n-static void unriffle_recursively_skewed(int *arr, int n, int *tmp)\n-{\n-\tif (n > 1) {\n-\t\tint pow2 = prev_pow2(n);\n-\t\tint rest = n - pow2;\n-\t\tunriffle(arr + pow2 - rest, rest * 2, tmp);\n-\t\tunriffle_recursively_skewed(arr, pow2, tmp);\n-\t\tunriffle_recursively_skewed(arr + pow2, rest, tmp);\n-\t}\n-}\n-\n-static void mode_unriffle_skewed(int *arr, int n)\n-{\n-\tint *tmp;\n-\tALLOC_ARRAY(tmp, n);\n-\tunriffle_recursively_skewed(arr, n, tmp);\n-\tfree(tmp);\n-}\n-\n-#define MODE(name) { #name, mode_##name }\n-\n-static struct mode {\n-\tconst char *name;\n-\tvoid (*fn)(int *arr, int n);\n-} mode[] = {\n-\tMODE(copy),\n-\tMODE(reverse),\n-\tMODE(reverse_1st_half),\n-\tMODE(reverse_2nd_half),\n-\tMODE(sort),\n-\tMODE(dither),\n-\tMODE(unriffle),\n-\tMODE(unriffle_skewed),\n-};\n-\n-struct number {\n-\tint value, rank;\n-\tstruct number *next;\n-};\n-\n-DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,\n-\t\t       (void)0, (void)0);\n-\n-static int compare_numbers(const struct number *an, const struct number *bn)\n-{\n-\tint a = an->value, b = bn->value;\n-\treturn (a > b) - (a < b);\n-}\n-\n-/* Free the storage directly, even if an assertion fails on a broken list. */\n-static int *values;\n static struct number *numbers;\n+static int *expected;\n \n void test_mergesort__cleanup(void)\n {\n-\tFREE_AND_NULL(values);\n \tFREE_AND_NULL(numbers);\n+\tFREE_AND_NULL(expected);\n }\n \n-static struct number *prepare_list(const int *arr, int n)\n+static void check_sort(const int *input, size_t nr)\n {\n-\tint i;\n+\tstruct number *list, *previous = NULL;\n \n-\tALLOC_ARRAY(numbers, n);\n-\tfor (i = 0; i < n; i++) {\n-\t\tnumbers[i].value = arr[i];\n+\tALLOC_ARRAY(numbers, nr);\n+\tALLOC_ARRAY(expected, nr);\n+\tCOPY_ARRAY(expected, input, nr);\n+\tQSORT(expected, nr, compare_ints);\n+\tfor (size_t i = 0; i < nr; i++) {\n+\t\tnumbers[i].value = input[i];\n \t\tnumbers[i].rank = i;\n-\t\tnumbers[i].next = i + 1 < n ? &numbers[i + 1] : NULL;\n+\t\tnumbers[i].next = i + 1 < nr ? &numbers[i + 1] : NULL;\n \t}\n-\treturn n ? numbers : NULL;\n-}\n-\n-static void check_list(struct number *list, const int *expected,\n-\t\t       int n, const char *context)\n-{\n-\tstruct number *previous = NULL;\n-\tint i;\n \n-\t/* Bound traversal so a cycle is reported as an overlong list. */\n-\tfor (i = 0; i < n; i++) {\n-\t\tcl_assert_(list, context);\n-\t\tcl_assert_equal_i_(list->value, expected[i], \"%s: index %d\",\n-\t\t\t\t   context, i);\n+\tlist = nr ? numbers : NULL;\n+\tsort_numbers(&list, compare_numbers);\n+\tfor (size_t i = 0; i < nr; i++) {\n+\t\tcl_assert_(list, \"list is too short\");\n+\t\tcl_assert_equal_i_(list->value, expected[i],\n+\t\t\t\t   \"size %zu, item %zu\", nr, i);\n \t\tif (previous && previous->value == list->value)\n \t\t\tcl_assert_lt_i_(previous->rank, list->rank,\n-\t\t\t\t\t\"%s: stability at index %d\", context, i);\n+\t\t\t\t\t\"stability: size %zu, item %zu\", nr, i);\n \t\tprevious = list;\n \t\tlist = list->next;\n \t}\n-\tcl_assert_(list == NULL, context);\n+\tcl_assert_(list == NULL, \"list is too long\");\n+\ttest_mergesort__cleanup();\n }\n \n-/*\n- * A version of the qsort certification program from \"Engineering a Sort\n- * Function\" by Bentley and McIlroy, Software—Practice and Experience,\n- * Volume 23, Issue 11, 1249–1265 (November 1993).\n- */\n-static void certify(const struct dist *distribution)\n-{\n-\tstatic const int sizes[] = { 100, 1023, 1024, 1025 };\n-\tsize_t i, j;\n-\tint m;\n-\n-\tfor (i = 0; i < ARRAY_SIZE(sizes); i++) {\n-\t\tint n = sizes[i];\n+static const size_t sizes[] = { 100, 1023, 1024, 1025 };\n \n-\t\tfor (j = 0; j < ARRAY_SIZE(mode); j++) {\n-\t\t\tfor (m = 1; m < 2 * n; m *= 2) {\n-\t\t\t\tstruct number *list;\n-\t\t\t\tchar context[128];\n+void test_mergesort__sorted(void)\n+{\n+\tint input[1025];\n \n-\t\t\t\txsnprintf(context, sizeof(context),\n-\t\t\t\t\t  \"%s %s n=%d m=%d\",\n-\t\t\t\t\t  distribution->name, mode[j].name, n, m);\n-\t\t\t\tALLOC_ARRAY(values, n);\n-\t\t\t\tdistribution->fn(values, n, m);\n-\t\t\t\tmode[j].fn(values, n);\n-\t\t\t\tlist = prepare_list(values, n);\n-\t\t\t\tsort_numbers(&list, compare_numbers);\n-\t\t\t\tQSORT(values, n, compare_ints);\n-\t\t\t\tcheck_list(list, values, n, context);\n-\t\t\t\ttest_mergesort__cleanup();\n-\t\t\t}\n-\t\t}\n-\t}\n+\tfor (size_t i = 0; i < ARRAY_SIZE(input); i++)\n+\t\tinput[i] = i;\n+\tfor (size_t i = 0; i < ARRAY_SIZE(sizes); i++)\n+\t\tcheck_sort(input, sizes[i]);\n }\n \n-void test_mergesort__sawtooth(void)\n+void test_mergesort__reversed(void)\n {\n-\tcertify(&dist[0]);\n-}\n+\tint input[1025];\n \n-void test_mergesort__rand(void)\n-{\n-\tcertify(&dist[1]);\n+\tfor (size_t i = 0; i < ARRAY_SIZE(sizes); i++) {\n+\t\tfor (size_t j = 0; j < sizes[i]; j++)\n+\t\t\tinput[j] = sizes[i] - j;\n+\t\tcheck_sort(input, sizes[i]);\n+\t}\n }\n \n-void test_mergesort__stagger(void)\n+void test_mergesort__equal_values(void)\n {\n-\tcertify(&dist[2]);\n-}\n+\tint input[1025] = { 0 };\n \n-void test_mergesort__plateau(void)\n-{\n-\tcertify(&dist[3]);\n+\tfor (size_t i = 0; i < ARRAY_SIZE(sizes); i++)\n+\t\tcheck_sort(input, sizes[i]);\n }\n \n-void test_mergesort__shuffle(void)\n+void test_mergesort__random(void)\n {\n-\tcertify(&dist[4]);\n+\tint input[1025];\n+\tuint32_t seed = 1;\n+\n+\tfor (size_t i = 0; i < ARRAY_SIZE(input); i++) {\n+\t\tseed = (uint64_t)seed * 48271 % 2147483647;\n+\t\tinput[i] = seed % 32;\n+\t}\n+\tfor (size_t i = 0; i < ARRAY_SIZE(sizes); i++)\n+\t\tcheck_sort(input, sizes[i]);\n }\n-- \n2.55.0\n\n\n"},{"id":"554611","messageId":"da42c96904489fcd37506916d5aac5be197df382.1791556668.git.dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"cover.1791556668.git.dilsheddilu123@gmail.com","subject":"[PATCH v3 3/4] mergesort: cover empty and small lists","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-09T15:08:49Z","receivedAt":"2026-10-09T15:08:49Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"The existing tests use at least 100 items. Add empty and single-item\nlists, reversed and equal pairs, and a small list with duplicate values\nand integer limits. Add two sorted runs whose values need to interleave\nduring the merge.\n\nAlso check that the debug version sorts a two-item list and calls both\nthe get-next and set-next hooks.\n\nSigned-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>\n---\n t/unit-tests/u-mergesort.c | 63 ++++++++++++++++++++++++++++++++++++++\n 1 file changed, 63 insertions(+)\n\ndiff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c\nindex 50bca1db46..1a5c0a60a8 100644\n--- a/t/unit-tests/u-mergesort.c\n+++ b/t/unit-tests/u-mergesort.c\n@@ -9,6 +9,11 @@ struct number {\n \n DEFINE_LIST_SORT(static, sort_numbers, struct number, next);\n \n+static int get_next_count, set_next_count;\n+\n+DEFINE_LIST_SORT_DEBUG(static, sort_numbers_debug, struct number, next,\n+\t\t       get_next_count++, set_next_count++);\n+\n static int compare_numbers(const struct number *a, const struct number *b)\n {\n \treturn (a->value > b->value) - (a->value < b->value);\n@@ -103,3 +108,61 @@ void test_mergesort__random(void)\n \tfor (size_t i = 0; i < ARRAY_SIZE(sizes); i++)\n \t\tcheck_sort(input, sizes[i]);\n }\n+\n+void test_mergesort__empty(void)\n+{\n+\tcheck_sort(NULL, 0);\n+}\n+\n+void test_mergesort__singleton(void)\n+{\n+\tconst int input[] = { 42 };\n+\n+\tcheck_sort(input, ARRAY_SIZE(input));\n+}\n+\n+void test_mergesort__reversed_pair(void)\n+{\n+\tconst int input[] = { 2, 1 };\n+\n+\tcheck_sort(input, ARRAY_SIZE(input));\n+}\n+\n+void test_mergesort__equal_pair(void)\n+{\n+\tconst int input[] = { 1, 1 };\n+\n+\tcheck_sort(input, ARRAY_SIZE(input));\n+}\n+\n+void test_mergesort__interleaved_runs(void)\n+{\n+\tconst int input[] = { 0, 2, 4, 6, 1, 3, 5, 7 };\n+\n+\tcheck_sort(input, ARRAY_SIZE(input));\n+}\n+\n+void test_mergesort__mixed_values(void)\n+{\n+\tconst int input[] = { INT_MAX, -1, 0, INT_MIN, -1, INT_MAX, 0 };\n+\n+\tcheck_sort(input, ARRAY_SIZE(input));\n+}\n+\n+void test_mergesort__debug_hooks(void)\n+{\n+\tstruct number nodes[] = {\n+\t\t{ .value = 2 },\n+\t\t{ .value = 1 },\n+\t};\n+\tstruct number *list = &nodes[0];\n+\n+\tnodes[0].next = &nodes[1];\n+\tget_next_count = set_next_count = 0;\n+\tsort_numbers_debug(&list, compare_numbers);\n+\tcl_assert_equal_p(list, &nodes[1]);\n+\tcl_assert_equal_p(list->next, &nodes[0]);\n+\tcl_assert_equal_p(list->next->next, NULL);\n+\tcl_assert_gt_i(get_next_count, 0);\n+\tcl_assert_gt_i(set_next_count, 0);\n+}\n-- \n2.55.0\n\n\n"},{"id":"554612","messageId":"d4814912d234fa1347a823b1a411159b50ae3449.1791556668.git.dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"cover.1791556668.git.dilsheddilu123@gmail.com","subject":"[PATCH v3 4/4] t: retire the sorting benchmark and mergesort helper","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-09T15:08:50Z","receivedAt":"2026-10-09T15:08:50Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"p0071 was added to compare sorting implementations during mergesort\ndevelopment. Retire that benchmark. A benchmark can be added again if\nfuture sorting changes need measurements.\n\nWith the numeric tests now in Clar, p0071 is the last user of test-tool\nmergesort. Remove the helper and its command and build registrations.\n\nSuggested-by: Patrick Steinhardt <ps@pks.im>\nSigned-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>\n---\n Makefile                  |  1 -\n t/helper/meson.build      |  1 -\n t/helper/test-mergesort.c | 65 ---------------------------------------\n t/helper/test-tool.c      |  1 -\n t/helper/test-tool.h      |  1 -\n t/meson.build             |  1 -\n t/perf/p0071-sort.sh      | 52 -------------------------------\n 7 files changed, 122 deletions(-)\n delete mode 100644 t/helper/test-mergesort.c\n delete mode 100755 t/perf/p0071-sort.sh\n\ndiff --git a/Makefile b/Makefile\nindex cac535ba19..4b35808b2e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -835,7 +835,6 @@ TEST_BUILTINS_OBJS += test-hexdump.o\n TEST_BUILTINS_OBJS += test-json-writer.o\n TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o\n TEST_BUILTINS_OBJS += test-match-trees.o\n-TEST_BUILTINS_OBJS += test-mergesort.o\n TEST_BUILTINS_OBJS += test-mktemp.o\n TEST_BUILTINS_OBJS += test-name-hash.o\n TEST_BUILTINS_OBJS += test-online-cpus.o\ndiff --git a/t/helper/meson.build b/t/helper/meson.build\nindex 3235f10ab8..e94e6f10fb 100644\n--- a/t/helper/meson.build\n+++ b/t/helper/meson.build\n@@ -32,7 +32,6 @@ test_tool_sources = [\n   'test-json-writer.c',\n   'test-lazy-init-name-hash.c',\n   'test-match-trees.c',\n-  'test-mergesort.c',\n   'test-mktemp.c',\n   'test-name-hash.c',\n   'test-online-cpus.c',\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\ndeleted file mode 100644\nindex d22a139f9e..0000000000\n--- a/t/helper/test-mergesort.c\n+++ /dev/null\n@@ -1,65 +0,0 @@\n-#include \"test-tool.h\"\n-#include \"mem-pool.h\"\n-#include \"mergesort.h\"\n-#include \"strbuf.h\"\n-\n-struct line {\n-\tchar *text;\n-\tstruct line *next;\n-};\n-\n-DEFINE_LIST_SORT(static, sort_lines, struct line, next);\n-\n-static int compare_strings(const struct line *x, const struct line *y)\n-{\n-\treturn strcmp(x->text, y->text);\n-}\n-\n-static int sort_stdin(void)\n-{\n-\tstruct line *lines;\n-\tstruct line **tail = &lines;\n-\tstruct strbuf sb = STRBUF_INIT;\n-\tstruct mem_pool lines_pool;\n-\tchar *p;\n-\n-\tstrbuf_read(&sb, 0, 0);\n-\n-\t/*\n-\t * Split by newline, but don't create an item\n-\t * for the empty string after the last separator.\n-\t */\n-\tif (sb.len && sb.buf[sb.len - 1] == '\\n')\n-\t\tstrbuf_setlen(&sb, sb.len - 1);\n-\n-\tmem_pool_init(&lines_pool, 0);\n-\tp = sb.buf;\n-\tfor (;;) {\n-\t\tchar *eol = strchr(p, '\\n');\n-\t\tstruct line *line = mem_pool_alloc(&lines_pool, sizeof(*line));\n-\t\tline->text = p;\n-\t\t*tail = line;\n-\t\ttail = &line->next;\n-\t\tif (!eol)\n-\t\t\tbreak;\n-\t\t*eol = '\\0';\n-\t\tp = eol + 1;\n-\t}\n-\t*tail = NULL;\n-\n-\tsort_lines(&lines, compare_strings);\n-\n-\twhile (lines) {\n-\t\tputs(lines->text);\n-\t\tlines = lines->next;\n-\t}\n-\treturn 0;\n-}\n-\n-int cmd__mergesort(int argc, const char **argv)\n-{\n-\tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n-\t\treturn sort_stdin();\n-\tfprintf(stderr, \"usage: test-tool mergesort sort\\n\");\n-\treturn 129;\n-}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex b71a22b43b..2e80dc7ab8 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -42,7 +42,6 @@ static struct test_cmd cmds[] = {\n \t{ \"json-writer\", cmd__json_writer },\n \t{ \"lazy-init-name-hash\", cmd__lazy_init_name_hash },\n \t{ \"match-trees\", cmd__match_trees },\n-\t{ \"mergesort\", cmd__mergesort },\n \t{ \"mktemp\", cmd__mktemp },\n \t{ \"name-hash\", cmd__name_hash },\n \t{ \"online-cpus\", cmd__online_cpus },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex f2885b33d5..9442c61ffd 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -35,7 +35,6 @@ int cmd__hexdump(int argc, const char **argv);\n int cmd__json_writer(int argc, const char **argv);\n int cmd__lazy_init_name_hash(int argc, const char **argv);\n int cmd__match_trees(int argc, const char **argv);\n-int cmd__mergesort(int argc, const char **argv);\n int cmd__mktemp(int argc, const char **argv);\n int cmd__name_hash(int argc, const char **argv);\n int cmd__online_cpus(int argc, const char **argv);\ndiff --git a/t/meson.build b/t/meson.build\nindex 2752321e0d..07436b63f4 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -1146,7 +1146,6 @@ benchmarks = [\n   'perf/p0006-read-tree-checkout.sh',\n   'perf/p0007-write-cache.sh',\n   'perf/p0008-odb-fsync.sh',\n-  'perf/p0071-sort.sh',\n   'perf/p0090-cache-tree.sh',\n   'perf/p0100-globbing.sh',\n   'perf/p1006-cat-file.sh',\ndiff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh\ndeleted file mode 100755\nindex ae4ddac864..0000000000\n--- a/t/perf/p0071-sort.sh\n+++ /dev/null\n@@ -1,52 +0,0 @@\n-#!/bin/sh\n-\n-test_description='Basic sort performance tests'\n-. ./perf-lib.sh\n-\n-test_perf_default_repo\n-\n-test_expect_success 'setup' '\n-\tgit ls-files --stage \"*.[ch]\" \"*.sh\" |\n-\tcut -f2 -d\" \" |\n-\tgit cat-file --batch >unsorted\n-'\n-\n-test_perf 'sort(1) unsorted' '\n-\tsort <unsorted >sorted\n-'\n-\n-test_expect_success 'reverse' '\n-\tsort -r <unsorted >reversed\n-'\n-\n-for file in sorted reversed\n-do\n-\ttest_perf \"sort(1) $file\" \"\n-\t\tsort <$file >actual\n-\t\"\n-done\n-\n-for file in unsorted sorted reversed\n-do\n-\n-\ttest_perf \"string_list_sort() $file\" \"\n-\t\ttest-tool string-list sort <$file >actual\n-\t\"\n-\n-\ttest_expect_success \"string_list_sort() $file sorts like sort(1)\" \"\n-\t\ttest_cmp_bin sorted actual\n-\t\"\n-done\n-\n-for file in unsorted sorted reversed\n-do\n-\ttest_perf \"DEFINE_LIST_SORT $file\" \"\n-\t\ttest-tool mergesort sort <$file >actual\n-\t\"\n-\n-\ttest_expect_success \"DEFINE_LIST_SORT $file sorts like sort(1)\" \"\n-\t\ttest_cmp_bin sorted actual\n-\t\"\n-done\n-\n-test_done\n-- \n2.55.0\n\n\n"},{"id":"554709","messageId":"xmqqy0c4emvk.fsf@gitster.g","threadId":"66479","inReplyTo":"21f46a2c9046d1da68233467bafb4b69226f35e6.1791556668.git.dilsheddilu123@gmail.com","subject":"Re: [PATCH v3 1/4] mergesort: move sorting tests to Clar","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-10-11T07:07:27Z","receivedAt":"2026-10-11T07:07:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Muhammed Dilshad A <dilsheddilu123@gmail.com> writes:\n\n> The numeric sorting tests only use mergesort.h. Move them from test-tool\n> to Clar, keeping the same inputs and checks for sorted order, stable\n> ordering of equal values, and list length.\n\nThe above I can parse, I know what these words mean, yet I do not\nthink I understand what the sentences want to say.  What is the\npoint of saying the first sentence, for example?  Is it the reason\nwhy \"Move them ... to Clar\" is a good idea?  Is it what allows us to\n\"Move them ... to Clar\" (in other words, if the tests used more than\njust mergesort.h, moving to Clar would have been impossible)?\n\n> Store the list items in an array so cleanup can free them even if the\n> sort leaves the links broken.\n>\n> Remove t0071 and the helper's generate and test commands. Keep the sort\n> command for p0071 for now.\n>\n> Suggested-by: Patrick Steinhardt <ps@pks.im>\n> Signed-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>\n\n"},{"id":"554740","messageId":"20261012041118.14682-1-dilsheddilu123@gmail.com","threadId":"66479","inReplyTo":"xmqqy0c4emvk.fsf@gitster.g","subject":"Re: [PATCH v3 1/4] mergesort: move sorting tests to Clar","fromName":"Muhammed Dilshad A","fromEmail":"dilsheddilu123@gmail.com","sentAt":"2026-10-12T04:11:18Z","receivedAt":"2026-10-12T04:11:18Z","isPatch":true,"sender":{"key":"dilsheddilu123@gmail.com","avatar":null},"body":"Hi Junio,\n\nUsing more headers would not prevent this move. That first sentence\ndoesn't explain the reason, so I'll remove it.\n\nThese tests work on lists in memory and don't need a Git repository.\nMoving them to Clar replaces the helper's hand-written pass/fail code\nwith the existing unit-test assertions and reporting. It also removes\nthe shell test and the helper's test command.\n\nI'll rewrite the commit message to explain that reason.\n\nRegards,\nDilshad\n\n"}]}