Re: [PATCH v3 1/3] Implement the patience diff algorithm

> On Wed, 7 Jan 2009, Johannes Schindelin wrote:
> 
> > The patience diff algorithm produces slightly more intuitive output 
> > than the classic Myers algorithm, as it does not try to minimize the 
> > number of +/- lines first, but tries to preserve the lines that are 
> > unique.
> 
> Johannes, sorry I had not time to follow this one.

> > +/*
> > + *  LibXDiff by Davide Libenzi ( File Differential Library )
> > + *  Copyright (C) 2003-2009 Davide Libenzi, Johannes E. Schindelin
> > + *
> > + *  This library is free software; you can redistribute it and/or
> > + *  modify it under the terms of the GNU Lesser General Public
> > + *  License as published by the Free Software Foundation; either
> > + *  version 2.1 of the License, or (at your option) any later version.
> > + *
> > + *  This library is distributed in the hope that it will be useful,
> > + *  but WITHOUT ANY WARRANTY; without even the implied warranty of
> > + *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> > + *  Lesser General Public License for more details.
> > + *
> > + *  You should have received a copy of the GNU Lesser General Public
> > + *  License along with this library; if not, write to the Free Software
> > + *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
> > + *
> > + *  Davide Libenzi <davidel@xmailserver.org>
> 
> You do not need to give me credit for something I don't even know how it 
> works ;)

> > +static int fall_back_to_classic_diff(struct hashmap *map,
> > +		int line1, int count1, int line2, int count2)
> > +{
> > +	/*
> > +	 * This probably does not work outside Git, since
> > +	 * we have a very simple mmfile structure.
> > +	 *
> > +	 * Note: ideally, we would reuse the prepared environment, but
> > +	 * the libxdiff interface does not (yet) allow for diffing only
> > +	 * ranges of lines instead of the whole files.
> > +	 */
> > +	mmfile_t subfile1, subfile2;
> > +	xpparam_t xpp;
> > +	xdfenv_t env;
> > +
> > +	subfile1.ptr = (char *)map->env->xdf1.recs[line1 - 1]->ptr;
> > +	subfile1.size = map->env->xdf1.recs[line1 + count1 - 2]->ptr +
> > +		map->env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;
> > +	subfile2.ptr = (char *)map->env->xdf2.recs[line2 - 1]->ptr;
> > +	subfile2.size = map->env->xdf2.recs[line2 + count2 - 2]->ptr +
> > +		map->env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;
> > +	xpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF;
> > +	if (xdl_do_diff(&subfile1, &subfile2, &xpp, &env) < 0)
> > +		return -1;
> 
> xdiff allows for diffing ranges, and the most efficent method is exactly 
> how you did ;) Once you know the lines pointers, there's no need to pass 
> it the whole file and have it scan it whole to find the lines range it 
> has to diff. Just pass the limited view like you did.