From mboxrd@z Thu Jan 1 00:00:00 1970 From: Davide Libenzi Subject: Re: [PATCH v3 1/3] Implement the patience diff algorithm Date: Wed, 7 Jan 2009 10:10:09 -0800 (PST) Message-ID: References: <20081104004001.GB29458@artemis.corp> <20081104083042.GB3788@artemis.corp> <20081104152351.GA21842@artemis.corp> <20090106111712.GB30766@artemis.corp> <20090107143926.GB831@artemis.corp> Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Cc: Pierre Habouzit , Linus Torvalds , Francis Galiegue , Git ML To: Johannes Schindelin X-From: git-owner@vger.kernel.org Wed Jan 07 19:11:46 2009 Return-path: Envelope-to: gcvg-git-2@gmane.org Received: from vger.kernel.org ([209.132.176.167]) by lo.gmane.org with esmtp (Exim 4.50) id 1LKcsT-0004XS-Qc for gcvg-git-2@gmane.org; Wed, 07 Jan 2009 19:11:38 +0100 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755447AbZAGSKO (ORCPT ); Wed, 7 Jan 2009 13:10:14 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1755346AbZAGSKO (ORCPT ); Wed, 7 Jan 2009 13:10:14 -0500 Received: from x35.xmailserver.org ([64.71.152.41]:36025 "EHLO x35.xmailserver.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755248AbZAGSKL (ORCPT ); Wed, 7 Jan 2009 13:10:11 -0500 X-AuthUser: davidel@xmailserver.org Received: from alien.or.mcafeemobile.com by x35.xmailserver.org with [XMail 1.26 ESMTP Server] id for from ; Wed, 7 Jan 2009 13:10:10 -0500 X-X-Sender: davide@alien.or.mcafeemobile.com In-Reply-To: User-Agent: Alpine 1.10 (DEB 962 2008-03-14) X-GPG-FINGRPRINT: CFAE 5BEE FD36 F65E E640 56FE 0974 BF23 270F 474E X-GPG-PUBLIC_KEY: http://www.xmailserver.org/davidel.asc Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Archived-At: 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. A couple of minor comments that arose just at glancing at the patch. > +/* > + * 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 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. - Davide