X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=xdiff%2Fxdiffi.c;h=b95ade2c1b58a48a91bf9a87c7a3893559580225;hb=HEAD;hp=8ea04837ec14b776aaa9d4a400c48072235fafa6;hpb=d93067d9c7fb210766c7282d662289f54d53f93a;p=git.git diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c index 8ea04837..b95ade2c 100644 --- a/xdiff/xdiffi.c +++ b/xdiff/xdiffi.c @@ -45,6 +45,8 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1, long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl, xdalgoenv_t *xenv); static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2); +static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo); + @@ -218,7 +220,7 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1, if (ec >= xenv->mxcost) { long fbest, fbest1, bbest, bbest1; - fbest = -1; + fbest = fbest1 = -1; for (d = fmax; d >= fmin; d -= 2) { i1 = XDL_MIN(kvdf[d], lim1); i2 = i1 - d; @@ -230,7 +232,7 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1, } } - bbest = XDL_LINE_MAX; + bbest = bbest1 = XDL_LINE_MAX; for (d = bmax; d >= bmin; d -= 2) { i1 = XDL_MAX(off1, kvdb[d]); i2 = i1 - d; @@ -296,6 +298,7 @@ int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1, } else { long ec; xdpsplit_t spl; + spl.i1 = spl.i2 = 0; /* * Divide ... @@ -349,12 +352,7 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, kvdf += xe->xdf2.nreff + 1; kvdb += xe->xdf2.nreff + 1; - /* - * Classical integer square root approximation using shifts. - */ - xenv.mxcost = 1; - for (; ndiags; ndiags >>= 2) - xenv.mxcost <<= 1; + xenv.mxcost = xdl_bogosqrt(ndiags); if (xenv.mxcost < XDL_MAX_COST_MIN) xenv.mxcost = XDL_MAX_COST_MIN; xenv.snake_cnt = XDL_SNAKE_CNT; @@ -399,6 +397,110 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, } +static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo) { + long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec; + char *rchg = xdf->rchg, *rchgo = xdfo->rchg; + xrecord_t **recs = xdf->recs; + + /* + * This is the same of what GNU diff does. Move back and forward + * change groups for a consistent and pretty diff output. This also + * helps in finding joineable change groups and reduce the diff size. + */ + for (ix = ixo = 0;;) { + /* + * Find the first changed line in the to-be-compacted file. + * We need to keep track of both indexes, so if we find a + * changed lines group on the other file, while scanning the + * to-be-compacted file, we need to skip it properly. Note + * that loops that are testing for changed lines on rchg* do + * not need index bounding since the array is prepared with + * a zero at position -1 and N. + */ + for (; ix < nrec && !rchg[ix]; ix++) + while (rchgo[ixo++]); + if (ix == nrec) + break; + + /* + * Record the start of a changed-group in the to-be-compacted file + * and find the end of it, on both to-be-compacted and other file + * indexes (ix and ixo). + */ + ixs = ix; + for (ix++; rchg[ix]; ix++); + for (; rchgo[ixo]; ixo++); + + do { + grpsiz = ix - ixs; + + /* + * If the line before the current change group, is equal to + * the last line of the current change group, shift backward + * the group. + */ + while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha && + XDL_RECMATCH(recs[ixs - 1], recs[ix - 1])) { + rchg[--ixs] = 1; + rchg[--ix] = 0; + + /* + * This change might have joined two change groups, + * so we try to take this scenario in account by moving + * the start index accordingly (and so the other-file + * end-of-group index). + */ + for (; rchg[ixs - 1]; ixs--); + while (rchgo[--ixo]); + } + + /* + * Record the end-of-group position in case we are matched + * with a group of changes in the other file (that is, the + * change record before the enf-of-group index in the other + * file is set). + */ + ixref = rchgo[ixo - 1] ? ix: nrec; + + /* + * If the first line of the current change group, is equal to + * the line next of the current change group, shift forward + * the group. + */ + while (ix < nrec && recs[ixs]->ha == recs[ix]->ha && + XDL_RECMATCH(recs[ixs], recs[ix])) { + rchg[ixs++] = 0; + rchg[ix++] = 1; + + /* + * This change might have joined two change groups, + * so we try to take this scenario in account by moving + * the start index accordingly (and so the other-file + * end-of-group index). Keep tracking the reference + * index in case we are shifting together with a + * corresponding group of changes in the other file. + */ + for (; rchg[ix]; ix++); + while (rchgo[++ixo]) + ixref = ix; + } + } while (grpsiz != ix - ixs); + + /* + * Try to move back the possibly merged group of changes, to match + * the recorded postion in the other file. + */ + while (ixref < ix) { + rchg[--ixs] = 1; + rchg[--ix] = 0; + while (rchgo[--ixo]); + } + } + + return 0; +} + + int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { xdchange_t *cscr = NULL, *xch; char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg; @@ -444,13 +546,13 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, return -1; } - - if (xdl_build_script(&xe, &xscr) < 0) { + if (xdl_change_compact(&xe.xdf1, &xe.xdf2) < 0 || + xdl_change_compact(&xe.xdf2, &xe.xdf1) < 0 || + xdl_build_script(&xe, &xscr) < 0) { xdl_free_env(&xe); return -1; } - if (xscr) { if (xdl_emit_diff(&xe, xscr, ecb, xecfg) < 0) { @@ -458,10 +560,8 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdl_free_env(&xe); return -1; } - xdl_free_script(xscr); } - xdl_free_env(&xe); return 0;