[RFC,04/10] range-diff: zero out elements in "cost" first

Commit Message

Ævar Arnfjörð Bjarmason Dec. 9, 2021, 7:19 p.m. UTC

Have the get_correspondences() function use CALLOC_ARRAY instead of
looping over the newly allocated "cost" to zero out some of its
elements.

The for-loop that zero'd out elements in "cost" wasn't the first loop
in that function, nor did it cover all of its elements, but regardless
of that this change doesn't affect its end-state. None of the
for-loops touched the same items in the array, so we could have (and
an earlier WIP version of this change did) moved the for-loop we're
deleting to come first in get_correspondences().

This can be seen from a careful reading of this code added in in
d9c66f0b5bf (range-diff: first rudimentary implementation,
2018-08-13) (as well as adding some printf-debugging) we'll set all
elements in the in the "n * n" allocated array. That's "n = A+B" where
"A" and "B" are the number of commits in our respective ranges.

So let's just allocate this with CALLOC_ARRAY(), and skip these two
for-loops. Furthermore let's remove the early exit condition from
compute_assignment() in favor of an assert that it must be called with
"column_count > 1", then "get_correspondences()" can skip calling it
when no further filling of the "a2b" and "b2a" arrays is needed.

Signed-off-by: Ævar Arnfjörð Bjarmason <[e-mail]>
---
 linear-assignment.c |  7 +------
 range-diff.c        | 13 +++++--------
 2 files changed, 6 insertions(+), 14 deletions(-)

Patch

diff --git a/linear-assignment.c b/linear-assignment.c
index ecffc09be6e..0c0786a63b6 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -19,12 +19,7 @@  void compute_assignment(int column_count, int row_count, int *cost,
 	int *free_row, free_count = 0, saved_free_count, *pred, *col;
 	int i, j, phase;
 
-	if (column_count < 2) {
-		memset(column2row, 0, sizeof(int) * column_count);
-		memset(row2column, 0, sizeof(int) * row_count);
-		return;
-	}
-
+	assert(column_count > 1);
 	memset(column2row, -1, sizeof(int) * column_count);
 	memset(row2column, -1, sizeof(int) * row_count);
 	ALLOC_ARRAY(v, column_count);
diff --git a/range-diff.c b/range-diff.c
index 41003033752..b0ccb46ff4c 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -312,9 +312,9 @@  static void get_correspondences(struct string_list *a, struct string_list *b,
 	int *cost, c, *a2b, *b2a;
 	size_t i, j;
 
-	ALLOC_ARRAY(cost, st_mult(n, n));
-	ALLOC_ARRAY(a2b, n);
-	ALLOC_ARRAY(b2a, n);
+	CALLOC_ARRAY(cost, st_mult(n, n));
+	CALLOC_ARRAY(a2b, n);
+	CALLOC_ARRAY(b2a, n);
 
 	for (i = 0; i < a->nr; i++) {
 		struct patch_util *a_util = a->items[i].util;
@@ -346,11 +346,8 @@  static void get_correspondences(struct string_list *a, struct string_list *b,
 			cost[i + n * j] = c;
 	}
 
-	for (i = a->nr; i < n; i++)
-		for (j = b->nr; j < n; j++)
-			cost[i + n * j] = 0;
-
-	compute_assignment(n, n, cost, a2b, b2a);
+	if (n > 1)
+		compute_assignment(n, n, cost, a2b, b2a);
 
 	for (i = 0; i < a->nr; i++)
 		if (a2b[i] >= 0 && a2b[i] < b->nr) {