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