Function get_correspondences

range-diff.c:327–397

}

static void get_correspondences(struct string_list *a, struct string_list *b,
				int creation_factor, size_t max_memory)
{
	int n = a->nr + b->nr;
	int *cost, c, *a2b, *b2a;
	int i, j;
	size_t cost_size = st_mult(n, n);
	size_t cost_bytes = st_mult(sizeof(int), cost_size);
	if (cost_bytes >= max_memory) {
		struct strbuf cost_str = STRBUF_INIT;
		struct strbuf max_str = STRBUF_INIT;
		strbuf_humanise_bytes(&cost_str, cost_bytes);
		strbuf_humanise_bytes(&max_str, max_memory);
		die(_("range-diff: unable to compute the range-diff, since it "
		      "exceeds the maximum memory for the cost matrix: %s "
		      "(%"PRIuMAX" bytes) needed, limited to %s (%"PRIuMAX" bytes)"),
		    cost_str.buf, (uintmax_t)cost_bytes, max_str.buf, (uintmax_t)max_memory);
	}
	ALLOC_ARRAY(cost, cost_size);
	ALLOC_ARRAY(a2b, n);
	ALLOC_ARRAY(b2a, n);

	for (i = 0; i < a->nr; i++) {
		struct patch_util *a_util = a->items[i].util;

		for (j = 0; j < b->nr; j++) {
			struct patch_util *b_util = b->items[j].util;

			if (a_util->matching == j)
				c = 0;
			else if (a_util->matching < 0 && b_util->matching < 0)
				c = diffsize(a_util->diff, b_util->diff);
			else
				c = COST_MAX;
			cost[i + n * j] = c;
		}

		c = a_util->matching < 0 ?
			a_util->diffsize * creation_factor / 100 : COST_MAX;
		for (j = b->nr; j < n; j++)
			cost[i + n * j] = c;
	}

	for (j = 0; j < b->nr; j++) {
		struct patch_util *util = b->items[j].util;

		c = util->matching < 0 ?
			util->diffsize * creation_factor / 100 : COST_MAX;
		for (i = a->nr; i < n; i++)
			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);