git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v3 2/4] mergesort: simplify the unit tests

From
MAMuhammed Dilshad A <dilsheddilu123@gmail.com>
Date
Oct 9, 2026, 15:08 UTC
Message-ID
<73ca97b0c721233a0e9d7b3cbc02fcbdf288c579.1791556668.git.dilsheddilu123@gmail.com>
In-Reply-To
<cover.1791556668.git.dilsheddilu123@gmail.com>

The old certification test combined several distributions with eight transformations. That setup was useful for comparing sorting algorithms, but it makes these unit tests harder to follow.

Replace the grid and its function tables with direct tests for sorted, reversed, equal-value and repeatable random input. Keep the checks for sorted values, the original order of equal values, and list length. Keep the sizes around 1024 to exercise merges across a power-of-two boundary.

Suggested-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>
---
 t/unit-tests/u-mergesort.c | 301 ++++++++-----------------------------
 1 file changed, 59 insertions(+), 242 deletions(-)
diff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c
index 56646b020b..50bca1db46 100644
--- a/t/unit-tests/u-mergesort.c
+++ b/t/unit-tests/u-mergesort.c
@@ -1,288 +1,105 @@
 #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),
+struct number {
+	int value;
+	size_t rank;
+	struct number *next;
 };
 
-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;
-}
+DEFINE_LIST_SORT(static, sort_numbers, struct number, next);
 
-static void unriffle(int *arr, int n, int *tmp)
+static int compare_numbers(const struct number *a, const struct number *b)
 {
-	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];
+	return (a->value > b->value) - (a->value < b->value);
 }
 
-static void unriffle_recursively(int *arr, int n, int *tmp)
+static int compare_ints(const void *va, const void *vb)
 {
-	if (n > 1) {
-		int half = n / 2;
-		unriffle(arr, n, tmp);
-		unriffle_recursively(arr, half, tmp);
-		unriffle_recursively(arr + half, n - half, tmp);
-	}
-}
+	const int *a = va, *b = vb;
 
-static void mode_unriffle(int *arr, int n)
-{
-	int *tmp;
-	ALLOC_ARRAY(tmp, n);
-	unriffle_recursively(arr, n, tmp);
-	free(tmp);
+	return (*a > *b) - (*a < *b);
 }
 
-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),
-};
-
-struct number {
-	int value, rank;
-	struct number *next;
-};
-
-DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,
-		       (void)0, (void)0);
-
-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;
+static int *expected;
 
 void test_mergesort__cleanup(void)
 {
-	FREE_AND_NULL(values);
 	FREE_AND_NULL(numbers);
+	FREE_AND_NULL(expected);
 }
 
-static struct number *prepare_list(const int *arr, int n)
+static void check_sort(const int *input, size_t nr)
 {
-	int i;
+	struct number *list, *previous = NULL;
 
-	ALLOC_ARRAY(numbers, n);
-	for (i = 0; i < n; i++) {
-		numbers[i].value = arr[i];
+	ALLOC_ARRAY(numbers, nr);
+	ALLOC_ARRAY(expected, nr);
+	COPY_ARRAY(expected, input, nr);
+	QSORT(expected, nr, compare_ints);
+	for (size_t i = 0; i < nr; i++) {
+		numbers[i].value = input[i];
 		numbers[i].rank = i;
-		numbers[i].next = i + 1 < n ? &numbers[i + 1] : NULL;
+		numbers[i].next = i + 1 < nr ? &numbers[i + 1] : NULL;
 	}
-	return n ? numbers : NULL;
-}
-
-static void check_list(struct number *list, const int *expected,
-		       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);
+	list = nr ? numbers : NULL;
+	sort_numbers(&list, compare_numbers);
+	for (size_t i = 0; i < nr; i++) {
+		cl_assert_(list, "list is too short");
+		cl_assert_equal_i_(list->value, expected[i],
+				   "size %zu, item %zu", nr, i);
 		if (previous && previous->value == list->value)
 			cl_assert_lt_i_(previous->rank, list->rank,
-					"%s: stability at index %d", context, i);
+					"stability: size %zu, item %zu", nr, i);
 		previous = list;
 		list = list->next;
 	}
-	cl_assert_(list == NULL, context);
+	cl_assert_(list == NULL, "list is too long");
+	test_mergesort__cleanup();
 }
 
-/*
- * 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];
+static const size_t sizes[] = { 100, 1023, 1024, 1025 };
 
-		for (j = 0; j < ARRAY_SIZE(mode); j++) {
-			for (m = 1; m < 2 * n; m *= 2) {
-				struct number *list;
-				char context[128];
+void test_mergesort__sorted(void)
+{
+	int input[1025];
 
-				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(&list, compare_numbers);
-				QSORT(values, n, compare_ints);
-				check_list(list, values, n, context);
-				test_mergesort__cleanup();
-			}
-		}
-	}
+	for (size_t i = 0; i < ARRAY_SIZE(input); i++)
+		input[i] = i;
+	for (size_t i = 0; i < ARRAY_SIZE(sizes); i++)
+		check_sort(input, sizes[i]);
 }
 
-void test_mergesort__sawtooth(void)
+void test_mergesort__reversed(void)
 {
-	certify(&dist[0]);
-}
+	int input[1025];
 
-void test_mergesort__rand(void)
-{
-	certify(&dist[1]);
+	for (size_t i = 0; i < ARRAY_SIZE(sizes); i++) {
+		for (size_t j = 0; j < sizes[i]; j++)
+			input[j] = sizes[i] - j;
+		check_sort(input, sizes[i]);
+	}
 }
 
-void test_mergesort__stagger(void)
+void test_mergesort__equal_values(void)
 {
-	certify(&dist[2]);
-}
+	int input[1025] = { 0 };
 
-void test_mergesort__plateau(void)
-{
-	certify(&dist[3]);
+	for (size_t i = 0; i < ARRAY_SIZE(sizes); i++)
+		check_sort(input, sizes[i]);
 }
 
-void test_mergesort__shuffle(void)
+void test_mergesort__random(void)
 {
-	certify(&dist[4]);
+	int input[1025];
+	uint32_t seed = 1;
+
+	for (size_t i = 0; i < ARRAY_SIZE(input); i++) {
+		seed = (uint64_t)seed * 48271 % 2147483647;
+		input[i] = seed % 32;
+	}
+	for (size_t i = 0; i < ARRAY_SIZE(sizes); i++)
+		check_sort(input, sizes[i]);
 }

-- 
2.55.0
Previous: Junio C HamanoNext: Muhammed Dilshad A
Message 15 of 17 in “test-mergesort: plug memory leaks in sort_stdin()”
  1. test-mergesort: plug memory leaks in sort_stdin()Muhammed Dilshad A, Oct 7, 2026
  2. Patrick SteinhardtOct 7, 2026
  3. Junio C HamanoOct 7, 2026
  4. 0/3 mergesort: move tests to Clar and retire the helperMuhammed Dilshad A, Oct 7, 2026
  5. 1/3 test-mergesort: plug memory leaks in sort_stdin()Muhammed Dilshad A, Oct 7, 2026
  6. 2/3 mergesort: move sorting tests to the unit-test frameworkMuhammed Dilshad A, Oct 7, 2026
  7. Patrick SteinhardtOct 9, 2026
  8. Muhammed Dilshad AOct 9, 2026
  9. 3/3 t: retire the sorting benchmark and mergesort helperMuhammed Dilshad A, Oct 7, 2026
  10. Patrick SteinhardtOct 9, 2026
  11. Muhammed Dilshad AOct 9, 2026
  12. 0/4 mergesort: move tests to Clar and remove the helperMuhammed Dilshad A, Oct 9, 2026
  13. 1/4 mergesort: move sorting tests to ClarMuhammed Dilshad A, Oct 9, 2026
  14. Junio C HamanoOct 11, 2026
  15. 2/4 mergesort: simplify the unit testsMuhammed Dilshad A, Oct 9, 2026
  16. 3/4 mergesort: cover empty and small listsMuhammed Dilshad A, Oct 9, 2026
  17. 4/4 t: retire the sorting benchmark and mergesort helperMuhammed Dilshad A, Oct 9, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.