Re: [PATCH v2 01/18] Add a function to solve least-cost assignment problems
- From
Jeff King <peff@peff.net>
- Date
- May 5, 2018, 18:24 UTC
- Message-ID
- <20180505182427.GB17700@sigill.intra.peff.net>
- In-Reply-To
- <3f51970cbc44bfe34133c48c0844ed3723e83808.1525448066.git.johannes.schindelin@gmx.de>
On Fri, May 04, 2018 at 05:34:29PM +0200, Johannes Schindelin wrote:
> The Jonker-Volgenant algorithm was implemented to answer questions such > as: given two different versions of a topic branch (or iterations of a > patch series), what is the best pairing of commits/patches between the > different versions?
I love git-tbdiff, so I'm excited to see it getting more exposure (and a speedup). Thanks for working on this!
Two minor nits on this patch:
Show 8 quoted lines
> +/*
> + * The parameter `cost` is the cost matrix: the cost to assign column j to row
> + * i is `cost[j + column_count * i].
> + */
> +int compute_assignment(int column_count, int row_count, double *cost,
> + int *column2row, int *row2column)
> +{
> + double *v = xmalloc(sizeof(double) * column_count), *d;Please use st_mult, xcalloc, or ALLOC_ARRAY here to avoid unchecked multiplication in an allocation. This is probably hard to exploit in practice (since you'd need sizeof(size_t)/8 columns, which presumably requires allocating some heavier-weight struct per item). But it makes auditing easier if we avoid the pattern altogether.
Show 14 quoted lines
> +/* > + * Compute an assignment of columns -> rows (and vice versa) such that every > + * column is assigned to at most one row (and vice versa) minimizing the > + * overall cost. > + * > + * The parameter `cost` is the cost matrix: the cost to assign column j to row > + * i is `cost[j + column_count * i]. > + * > + * The arrays column2row and row2column will be populated with the respective > + * assignments (-1 for unassigned, which can happen only if column_count != > + * row_count). > + */ > +int compute_assignment(int column_count, int row_count, double *cost, > + int *column2row, int *row2column);
It looks like this always returns zero. Is there a ever a case where we would return an error if this? If not, should it just be void?
-Peff