Hi Peff,
On Sat, 5 May 2018, Jeff King wrote:
> 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:
>
> > +/*
> > + * 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.
Sure. I did mean to return errors in those case, but I guess it is not
worth the trouble (what would we do in case of out-of-memory?).
> > +/*
> > + * 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?
Fixed.
Ciao,
Dscho
