Merge branch 'rs/mergesort'

Make our mergesort implementation type-safe.

* rs/mergesort:
  mergesort: remove llist_mergesort()
  packfile: use DEFINE_LIST_SORT
  fetch-pack: use DEFINE_LIST_SORT
  commit: use DEFINE_LIST_SORT
  blame: use DEFINE_LIST_SORT
  test-mergesort: use DEFINE_LIST_SORT
  test-mergesort: use DEFINE_LIST_SORT_DEBUG
  mergesort: add macros for typed sort of linked lists
  mergesort: tighten merge loop
  mergesort: unify ranks loops

3 files changed, 10 insertions, 30 deletions

diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index ebf68f7..202e54a 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c
@@ -13,19 +13,10 @@ struct line {
 	struct line *next;
 };
 
-static void *get_next(const void *a)
-{
-	return ((const struct line *)a)->next;
-}
-
-static void set_next(void *a, void *b)
-{
-	((struct line *)a)->next = b;
-}
+DEFINE_LIST_SORT(static, sort_lines, struct line, next);
 
-static int compare_strings(const void *a, const void *b)
+static int compare_strings(const struct line *x, const struct line *y)
 {
-	const struct line *x = a, *y = b;
 	return strcmp(x->text, y->text);
 }
 
@@ -47,7 +38,7 @@ static int sort_stdin(void)
 		p = line;
 	}
 
-	lines = llist_mergesort(lines, get_next, set_next, compare_strings);
+	sort_lines(&lines, compare_strings);
 
 	while (lines) {
 		puts(lines->text);
@@ -273,21 +264,11 @@ struct number {
 	struct number *next;
 };
 
-static void *get_next_number(const void *a)
-{
-	stats.get_next++;
-	return ((const struct number *)a)->next;
-}
-
-static void set_next_number(void *a, void *b)
-{
-	stats.set_next++;
-	((struct number *)a)->next = b;
-}
+DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,
+		       stats.get_next++, stats.set_next++);
 
-static int compare_numbers(const void *av, const void *bv)
+static int compare_numbers(const struct number *an, const struct number *bn)
 {
-	const struct number *an = av, *bn = bv;
 	int a = an->value, b = bn->value;
 	stats.compare++;
 	return (a > b) - (a < b);
@@ -325,8 +306,7 @@ static int test(const struct dist *dist, const struct mode *mode, int n, int m)
 	*tail = NULL;
 
 	stats.get_next = stats.set_next = stats.compare = 0;
-	list = llist_mergesort(list, get_next_number, set_next_number,
-			       compare_numbers);
+	sort_numbers(&list, compare_numbers);
 
 	QSORT(arr, n, compare_ints);
 	for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {
diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh
index ed366e2..ae4ddac 100755
--- a/t/perf/p0071-sort.sh
+++ b/t/perf/p0071-sort.sh
@@ -40,11 +40,11 @@ done
 
 for file in unsorted sorted reversed
 do
-	test_perf "llist_mergesort() $file" "
+	test_perf "DEFINE_LIST_SORT $file" "
 		test-tool mergesort sort <$file >actual
 	"
 
-	test_expect_success "llist_mergesort() $file sorts like sort(1)" "
+	test_expect_success "DEFINE_LIST_SORT $file sorts like sort(1)" "
 		test_cmp_bin sorted actual
 	"
 done
diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh
index 6f9a501..ba8ad1d 100755
--- a/t/t0071-sort.sh
+++ b/t/t0071-sort.sh
@@ -5,7 +5,7 @@ test_description='verify sort functions'
 TEST_PASSES_SANITIZE_LEAK=true
 . ./test-lib.sh
 
-test_expect_success 'llist_mergesort()' '
+test_expect_success 'DEFINE_LIST_SORT_DEBUG' '
 	test-tool mergesort test
 '