diff options
Diffstat (limited to 'xdiff')
-rw-r--r-- | xdiff/xdiff.h | 17 | ||||
-rw-r--r-- | xdiff/xdiffi.c | 50 | ||||
-rw-r--r-- | xdiff/xdiffi.h | 1 | ||||
-rw-r--r-- | xdiff/xemit.c | 148 | ||||
-rw-r--r-- | xdiff/xemit.h | 2 | ||||
-rw-r--r-- | xdiff/xhistogram.c | 4 | ||||
-rw-r--r-- | xdiff/xmerge.c | 4 | ||||
-rw-r--r-- | xdiff/xpatience.c | 2 | ||||
-rw-r--r-- | xdiff/xprepare.c | 31 | ||||
-rw-r--r-- | xdiff/xutils.c | 162 | ||||
-rw-r--r-- | xdiff/xutils.h | 4 |
11 files changed, 319 insertions, 106 deletions
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h index 4beb10c678..c0339919cc 100644 --- a/xdiff/xdiff.h +++ b/xdiff/xdiff.h @@ -32,17 +32,18 @@ extern "C" { #define XDF_IGNORE_WHITESPACE (1 << 2) #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3) #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4) +#define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL) + #define XDF_PATIENCE_DIFF (1 << 5) #define XDF_HISTOGRAM_DIFF (1 << 6) -#define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL) +#define XDF_DIFF_ALGORITHM_MASK (XDF_PATIENCE_DIFF | XDF_HISTOGRAM_DIFF) +#define XDF_DIFF_ALG(x) ((x) & XDF_DIFF_ALGORITHM_MASK) -#define XDL_PATCH_NORMAL '-' -#define XDL_PATCH_REVERSE '+' -#define XDL_PATCH_MODEMASK ((1 << 8) - 1) -#define XDL_PATCH_IGNOREBSPACE (1 << 8) +#define XDF_IGNORE_BLANK_LINES (1 << 7) #define XDL_EMIT_FUNCNAMES (1 << 0) #define XDL_EMIT_COMMON (1 << 1) +#define XDL_EMIT_FUNCCONTEXT (1 << 2) #define XDL_MMB_READONLY (1 << 0) @@ -87,13 +88,17 @@ typedef struct s_xdemitcb { typedef long (*find_func_t)(const char *line, long line_len, char *buffer, long buffer_size, void *priv); +typedef int (*xdl_emit_hunk_consume_func_t)(long start_a, long count_a, + long start_b, long count_b, + void *cb_data); + typedef struct s_xdemitconf { long ctxlen; long interhunkctxlen; unsigned long flags; find_func_t find_func; void *find_func_priv; - void (*emit_func)(); + xdl_emit_hunk_consume_func_t hunk_func; } xdemitconf_t; typedef struct s_bdiffparam { diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c index 75a3922750..2358a2d632 100644 --- a/xdiff/xdiffi.c +++ b/xdiff/xdiffi.c @@ -328,10 +328,10 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdalgoenv_t xenv; diffdata_t dd1, dd2; - if (xpp->flags & XDF_PATIENCE_DIFF) + if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF) return xdl_do_patience_diff(mf1, mf2, xpp, xe); - if (xpp->flags & XDF_HISTOGRAM_DIFF) + if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) return xdl_do_histogram_diff(mf1, mf2, xpp, xe); if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) { @@ -394,6 +394,7 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, xch->i2 = i2; xch->chg1 = chg1; xch->chg2 = chg2; + xch->ignore = 0; return xch; } @@ -490,7 +491,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { /* * Try to move back the possibly merged group of changes, to match - * the recorded postion in the other file. + * the recorded position in the other file. */ while (ixref < ix) { rchg[--ixs] = 1; @@ -538,13 +539,49 @@ void xdl_free_script(xdchange_t *xscr) { } } +static int xdl_call_hunk_func(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, + xdemitconf_t const *xecfg) +{ + xdchange_t *xch, *xche; + + for (xch = xscr; xch; xch = xche->next) { + xche = xdl_get_hunk(&xch, xecfg); + if (!xch) + break; + if (xecfg->hunk_func(xch->i1, xche->i1 + xche->chg1 - xch->i1, + xch->i2, xche->i2 + xche->chg2 - xch->i2, + ecb->priv) < 0) + return -1; + } + return 0; +} + +static void xdl_mark_ignorable(xdchange_t *xscr, xdfenv_t *xe, long flags) +{ + xdchange_t *xch; + + for (xch = xscr; xch; xch = xch->next) { + int ignore = 1; + xrecord_t **rec; + long i; + + rec = &xe->xdf1.recs[xch->i1]; + for (i = 0; i < xch->chg1 && ignore; i++) + ignore = xdl_blankline(rec[i]->ptr, rec[i]->size, flags); + + rec = &xe->xdf2.recs[xch->i2]; + for (i = 0; i < xch->chg2 && ignore; i++) + ignore = xdl_blankline(rec[i]->ptr, rec[i]->size, flags); + + xch->ignore = ignore; + } +} int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdemitconf_t const *xecfg, xdemitcb_t *ecb) { xdchange_t *xscr; xdfenv_t xe; - emit_func_t ef = xecfg->emit_func ? - (emit_func_t)xecfg->emit_func : xdl_emit_diff; + emit_func_t ef = xecfg->hunk_func ? xdl_call_hunk_func : xdl_emit_diff; if (xdl_do_diff(mf1, mf2, xpp, &xe) < 0) { @@ -558,6 +595,9 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, return -1; } if (xscr) { + if (xpp->flags & XDF_IGNORE_BLANK_LINES) + xdl_mark_ignorable(xscr, &xe, xpp->flags); + if (ef(&xe, xscr, ecb, xecfg) < 0) { xdl_free_script(xscr); diff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h index 7a92ea9c4d..8b81206c9a 100644 --- a/xdiff/xdiffi.h +++ b/xdiff/xdiffi.h @@ -41,6 +41,7 @@ typedef struct s_xdchange { struct s_xdchange *next; long i1, i2; long chg1, chg2; + int ignore; } xdchange_t; diff --git a/xdiff/xemit.c b/xdiff/xemit.c index 277e2eec5b..4266ada23f 100644 --- a/xdiff/xemit.c +++ b/xdiff/xemit.c @@ -56,16 +56,51 @@ static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t * /* * Starting at the passed change atom, find the latest change atom to be included * inside the differential hunk according to the specified configuration. + * Also advance xscr if the first changes must be discarded. */ -xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg) { - xdchange_t *xch, *xchp; +xdchange_t *xdl_get_hunk(xdchange_t **xscr, xdemitconf_t const *xecfg) +{ + xdchange_t *xch, *xchp, *lxch; long max_common = 2 * xecfg->ctxlen + xecfg->interhunkctxlen; + long max_ignorable = xecfg->ctxlen; + unsigned long ignored = 0; /* number of ignored blank lines */ + + /* remove ignorable changes that are too far before other changes */ + for (xchp = *xscr; xchp && xchp->ignore; xchp = xchp->next) { + xch = xchp->next; + + if (xch == NULL || + xch->i1 - (xchp->i1 + xchp->chg1) >= max_ignorable) + *xscr = xch; + } + + if (*xscr == NULL) + return NULL; + + lxch = *xscr; + + for (xchp = *xscr, xch = xchp->next; xch; xchp = xch, xch = xch->next) { + long distance = xch->i1 - (xchp->i1 + xchp->chg1); + if (distance > max_common) + break; - for (xchp = xscr, xch = xscr->next; xch; xchp = xch, xch = xch->next) - if (xch->i1 - (xchp->i1 + xchp->chg1) > max_common) + if (distance < max_ignorable && (!xch->ignore || lxch == xchp)) { + lxch = xch; + ignored = 0; + } else if (distance < max_ignorable && xch->ignore) { + ignored += xch->chg2; + } else if (lxch != xchp && + xch->i1 + ignored - (lxch->i1 + lxch->chg1) > max_common) { break; + } else if (!xch->ignore) { + lxch = xch; + ignored = 0; + } else { + ignored += xch->chg2; + } + } - return xchp; + return lxch; } @@ -73,7 +108,7 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv) { if (len > 0 && (isalpha((unsigned char)*rec) || /* identifier? */ - *rec == '_' || /* also identifier? */ + *rec == '_' || /* also identifier? */ *rec == '$')) { /* identifiers from VMS and other esoterico */ if (len > sz) len = sz; @@ -87,7 +122,7 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv) static int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, xdemitconf_t const *xecfg) { - xdfile_t *xdf = &xe->xdf1; + xdfile_t *xdf = &xe->xdf2; const char *rchg = xdf->rchg; long ix; @@ -100,24 +135,63 @@ static int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, return 0; } +struct func_line { + long len; + char buf[80]; +}; + +static long get_func_line(xdfenv_t *xe, xdemitconf_t const *xecfg, + struct func_line *func_line, long start, long limit) +{ + find_func_t ff = xecfg->find_func ? xecfg->find_func : def_ff; + long l, size, step = (start > limit) ? -1 : 1; + char *buf, dummy[1]; + + buf = func_line ? func_line->buf : dummy; + size = func_line ? sizeof(func_line->buf) : sizeof(dummy); + + for (l = start; l != limit && 0 <= l && l < xe->xdf1.nrec; l += step) { + const char *rec; + long reclen = xdl_get_rec(&xe->xdf1, l, &rec); + long len = ff(rec, reclen, buf, size, xecfg->find_func_priv); + if (len >= 0) { + if (func_line) + func_line->len = len; + return l; + } + } + return -1; +} + int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, xdemitconf_t const *xecfg) { long s1, s2, e1, e2, lctx; xdchange_t *xch, *xche; - char funcbuf[80]; - long funclen = 0; long funclineprev = -1; - find_func_t ff = xecfg->find_func ? xecfg->find_func : def_ff; + struct func_line func_line = { 0 }; if (xecfg->flags & XDL_EMIT_COMMON) return xdl_emit_common(xe, xscr, ecb, xecfg); for (xch = xscr; xch; xch = xche->next) { - xche = xdl_get_hunk(xch, xecfg); + xche = xdl_get_hunk(&xch, xecfg); + if (!xch) + break; s1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0); s2 = XDL_MAX(xch->i2 - xecfg->ctxlen, 0); + if (xecfg->flags & XDL_EMIT_FUNCCONTEXT) { + long fs1 = get_func_line(xe, xecfg, NULL, xch->i1, -1); + if (fs1 < 0) + fs1 = 0; + if (fs1 < s1) { + s2 -= s1 - fs1; + s1 = fs1; + } + } + + again: lctx = xecfg->ctxlen; lctx = XDL_MIN(lctx, xe->xdf1.nrec - (xche->i1 + xche->chg1)); lctx = XDL_MIN(lctx, xe->xdf2.nrec - (xche->i2 + xche->chg2)); @@ -125,34 +199,50 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, e1 = xche->i1 + xche->chg1 + lctx; e2 = xche->i2 + xche->chg2 + lctx; + if (xecfg->flags & XDL_EMIT_FUNCCONTEXT) { + long fe1 = get_func_line(xe, xecfg, NULL, + xche->i1 + xche->chg1, + xe->xdf1.nrec); + if (fe1 < 0) + fe1 = xe->xdf1.nrec; + if (fe1 > e1) { + e2 += fe1 - e1; + e1 = fe1; + } + + /* + * Overlap with next change? Then include it + * in the current hunk and start over to find + * its new end. + */ + if (xche->next) { + long l = xche->next->i1; + if (l <= e1 || + get_func_line(xe, xecfg, NULL, l, e1) < 0) { + xche = xche->next; + goto again; + } + } + } + /* * Emit current hunk header. */ if (xecfg->flags & XDL_EMIT_FUNCNAMES) { - long l; - for (l = s1 - 1; l >= 0 && l > funclineprev; l--) { - const char *rec; - long reclen = xdl_get_rec(&xe->xdf1, l, &rec); - long newfunclen = ff(rec, reclen, funcbuf, - sizeof(funcbuf), - xecfg->find_func_priv); - if (newfunclen >= 0) { - funclen = newfunclen; - break; - } - } + get_func_line(xe, xecfg, &func_line, + s1 - 1, funclineprev); funclineprev = s1 - 1; } if (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2, - funcbuf, funclen, ecb) < 0) + func_line.buf, func_line.len, ecb) < 0) return -1; /* * Emit pre-context. */ - for (; s1 < xch->i1; s1++) - if (xdl_emit_record(&xe->xdf1, s1, " ", ecb) < 0) + for (; s2 < xch->i2; s2++) + if (xdl_emit_record(&xe->xdf2, s2, " ", ecb) < 0) return -1; for (s1 = xch->i1, s2 = xch->i2;; xch = xch->next) { @@ -160,7 +250,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, * Merge previous with current change atom. */ for (; s1 < xch->i1 && s2 < xch->i2; s1++, s2++) - if (xdl_emit_record(&xe->xdf1, s1, " ", ecb) < 0) + if (xdl_emit_record(&xe->xdf2, s2, " ", ecb) < 0) return -1; /* @@ -186,8 +276,8 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, /* * Emit post-context. */ - for (s1 = xche->i1 + xche->chg1; s1 < e1; s1++) - if (xdl_emit_record(&xe->xdf1, s1, " ", ecb) < 0) + for (s2 = xche->i2 + xche->chg2; s2 < e2; s2++) + if (xdl_emit_record(&xe->xdf2, s2, " ", ecb) < 0) return -1; } diff --git a/xdiff/xemit.h b/xdiff/xemit.h index c2e2e83027..d29710770c 100644 --- a/xdiff/xemit.h +++ b/xdiff/xemit.h @@ -27,7 +27,7 @@ typedef int (*emit_func_t)(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, xdemitconf_t const *xecfg); -xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg); +xdchange_t *xdl_get_hunk(xdchange_t **xscr, xdemitconf_t const *xecfg); int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, xdemitconf_t const *xecfg); diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c index 18f6f997c3..73210cb6f3 100644 --- a/xdiff/xhistogram.c +++ b/xdiff/xhistogram.c @@ -55,7 +55,7 @@ struct histindex { struct record { unsigned int ptr, cnt; struct record *next; - } **records, /* an ocurrence */ + } **records, /* an occurrence */ **line_map; /* map of line to record chain */ chastore_t rcha; unsigned int *next_ptrs; @@ -252,7 +252,7 @@ static int fall_back_to_classic_diff(struct histindex *index, int line1, int count1, int line2, int count2) { xpparam_t xpp; - xpp.flags = index->xpp->flags & ~XDF_HISTOGRAM_DIFF; + xpp.flags = index->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK; return xdl_fall_back_diff(index->env, &xpp, line1, count1, line2, count2); diff --git a/xdiff/xmerge.c b/xdiff/xmerge.c index 9e13b25abc..625198e058 100644 --- a/xdiff/xmerge.c +++ b/xdiff/xmerge.c @@ -245,11 +245,11 @@ static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1, dest ? dest + size : NULL); /* Postimage from side #1 */ if (m->mode & 1) - size += xdl_recs_copy(xe1, m->i1, m->chg1, 1, + size += xdl_recs_copy(xe1, m->i1, m->chg1, (m->mode & 2), dest ? dest + size : NULL); /* Postimage from side #2 */ if (m->mode & 2) - size += xdl_recs_copy(xe2, m->i2, m->chg2, 1, + size += xdl_recs_copy(xe2, m->i2, m->chg2, 0, dest ? dest + size : NULL); } else continue; diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c index fdd7d0263f..04e1a1ab2a 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -288,7 +288,7 @@ static int fall_back_to_classic_diff(struct hashmap *map, int line1, int count1, int line2, int count2) { xpparam_t xpp; - xpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF; + xpp.flags = map->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK; return xdl_fall_back_diff(map->env, &xpp, line1, count1, line2, count2); diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index 5a33d1a869..63a22c630e 100644 --- a/xdiff/xprepare.c +++ b/xdiff/xprepare.c @@ -181,7 +181,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) goto abort; - if (xpp->flags & XDF_HISTOGRAM_DIFF) + if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) hbits = hsize = 0; else { hbits = xdl_hashbits((unsigned int) narec); @@ -209,8 +209,8 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ crec->ha = hav; recs[nrec++] = crec; - if (!(xpp->flags & XDF_HISTOGRAM_DIFF) && - xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) + if ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && + xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) goto abort; } } @@ -273,16 +273,15 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, * (nrecs) will be updated correctly anyway by * xdl_prepare_ctx(). */ - sample = xpp->flags & XDF_HISTOGRAM_DIFF ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1; + sample = (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF + ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1); enl1 = xdl_guess_lines(mf1, sample) + 1; enl2 = xdl_guess_lines(mf2, sample) + 1; - if (!(xpp->flags & XDF_HISTOGRAM_DIFF) && - xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) { - + if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF && + xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) return -1; - } if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) { @@ -296,9 +295,9 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, return -1; } - if (!(xpp->flags & XDF_PATIENCE_DIFF) && - !(xpp->flags & XDF_HISTOGRAM_DIFF) && - xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) { + if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && + (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && + xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) { xdl_free_ctx(&xe->xdf2); xdl_free_ctx(&xe->xdf1); @@ -383,7 +382,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { * might be potentially discarded if they happear in a run of discardable. */ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) { - long i, nm, nreff; + long i, nm, nreff, mlim; xrecord_t **recs; xdlclass_t *rcrec; char *dis, *dis1, *dis2; @@ -396,16 +395,20 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd dis1 = dis; dis2 = dis1 + xdf1->nrec + 1; + if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT) + mlim = XDL_MAX_EQLIMIT; for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { rcrec = cf->rcrecs[(*recs)->ha]; nm = rcrec ? rcrec->len2 : 0; - dis1[i] = (nm == 0) ? 0: 1; + dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1; } + if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT) + mlim = XDL_MAX_EQLIMIT; for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { rcrec = cf->rcrecs[(*recs)->ha]; nm = rcrec ? rcrec->len1 : 0; - dis2[i] = (nm == 0) ? 0: 1; + dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1; } for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; diff --git a/xdiff/xutils.c b/xdiff/xutils.c index 0de084e53f..62cb23dfd3 100644 --- a/xdiff/xutils.c +++ b/xdiff/xutils.c @@ -20,6 +20,8 @@ * */ +#include <limits.h> +#include <assert.h> #include "xinclude.h" @@ -120,35 +122,6 @@ void *xdl_cha_alloc(chastore_t *cha) { return data; } - -void *xdl_cha_first(chastore_t *cha) { - chanode_t *sncur; - - if (!(cha->sncur = sncur = cha->head)) - return NULL; - - cha->scurr = 0; - - return (char *) sncur + sizeof(chanode_t) + cha->scurr; -} - - -void *xdl_cha_next(chastore_t *cha) { - chanode_t *sncur; - - if (!(sncur = cha->sncur)) - return NULL; - cha->scurr += cha->isize; - if (cha->scurr == sncur->icurr) { - if (!(sncur = cha->sncur = sncur->next)) - return NULL; - cha->scurr = 0; - } - - return (char *) sncur + sizeof(chanode_t) + cha->scurr; -} - - long xdl_guess_lines(mmfile_t *mf, long sample) { long nl = 0, size, tsize = 0; char const *data, *cur, *top; @@ -170,6 +143,19 @@ long xdl_guess_lines(mmfile_t *mf, long sample) { return nl + 1; } +int xdl_blankline(const char *line, long size, long flags) +{ + long i; + + if (!(flags & XDF_WHITESPACE_FLAGS)) + return (size <= 1); + + for (i = 0; i < size && XDL_ISSPACE(line[i]); i++) + ; + + return (i == size); +} + int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags) { int i1, i2; @@ -276,6 +262,109 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data, return ha; } +#ifdef XDL_FAST_HASH + +#define REPEAT_BYTE(x) ((~0ul / 0xff) * (x)) + +#define ONEBYTES REPEAT_BYTE(0x01) +#define NEWLINEBYTES REPEAT_BYTE(0x0a) +#define HIGHBITS REPEAT_BYTE(0x80) + +/* Return the high bit set in the first byte that is a zero */ +static inline unsigned long has_zero(unsigned long a) +{ + return ((a - ONEBYTES) & ~a) & HIGHBITS; +} + +static inline long count_masked_bytes(unsigned long mask) +{ + if (sizeof(long) == 8) { + /* + * Jan Achrenius on G+: microoptimized version of + * the simpler "(mask & ONEBYTES) * ONEBYTES >> 56" + * that works for the bytemasks without having to + * mask them first. + */ + /* + * return mask * 0x0001020304050608 >> 56; + * + * Doing it like this avoids warnings on 32-bit machines. + */ + long a = (REPEAT_BYTE(0x01) / 0xff + 1); + return mask * a >> (sizeof(long) * 7); + } else { + /* Carl Chatfield / Jan Achrenius G+ version for 32-bit */ + /* (000000 0000ff 00ffff ffffff) -> ( 1 1 2 3 ) */ + long a = (0x0ff0001 + mask) >> 23; + /* Fix the 1 for 00 case */ + return a & mask; + } +} + +unsigned long xdl_hash_record(char const **data, char const *top, long flags) +{ + unsigned long hash = 5381; + unsigned long a = 0, mask = 0; + char const *ptr = *data; + char const *end = top - sizeof(unsigned long) + 1; + + if (flags & XDF_WHITESPACE_FLAGS) + return xdl_hash_record_with_whitespace(data, top, flags); + + ptr -= sizeof(unsigned long); + do { + hash += hash << 5; + hash ^= a; + ptr += sizeof(unsigned long); + if (ptr >= end) + break; + a = *(unsigned long *)ptr; + /* Do we have any '\n' bytes in this word? */ + mask = has_zero(a ^ NEWLINEBYTES); + } while (!mask); + + if (ptr >= end) { + /* + * There is only a partial word left at the end of the + * buffer. Because we may work with a memory mapping, + * we have to grab the rest byte by byte instead of + * blindly reading it. + * + * To avoid problems with masking in a signed value, + * we use an unsigned char here. + */ + const char *p; + for (p = top - 1; p >= ptr; p--) + a = (a << 8) + *((const unsigned char *)p); + mask = has_zero(a ^ NEWLINEBYTES); + if (!mask) + /* + * No '\n' found in the partial word. Make a + * mask that matches what we read. + */ + mask = 1UL << (8 * (top - ptr) + 7); + } + + /* The mask *below* the first high bit set */ + mask = (mask - 1) & ~mask; + mask >>= 7; + hash += hash << 5; + hash ^= a & mask; + + /* Advance past the last (possibly partial) word */ + ptr += count_masked_bytes(mask); + + if (ptr < top) { + assert(*ptr == '\n'); + ptr++; + } + + *data = ptr; + + return hash; +} + +#else /* XDL_FAST_HASH */ unsigned long xdl_hash_record(char const **data, char const *top, long flags) { unsigned long ha = 5381; @@ -293,6 +382,7 @@ unsigned long xdl_hash_record(char const **data, char const *top, long flags) { return ha; } +#endif /* XDL_FAST_HASH */ unsigned int xdl_hashbits(unsigned int size) { unsigned int val = 1, bits = 0; @@ -324,20 +414,6 @@ int xdl_num_out(char *out, long val) { return str - out; } - -long xdl_atol(char const *str, char const **next) { - long val, base; - char const *top; - - for (top = str; XDL_ISDIGIT(*top); top++); - if (next) - *next = top; - for (val = 0, base = 1, top--; top >= str; top--, base *= 10) - val += base * (long)(*top - '0'); - return val; -} - - int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, const char *func, long funclen, xdemitcb_t *ecb) { int nb = 0; diff --git a/xdiff/xutils.h b/xdiff/xutils.h index 714719a89c..4646ce5752 100644 --- a/xdiff/xutils.h +++ b/xdiff/xutils.h @@ -31,14 +31,12 @@ int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize, int xdl_cha_init(chastore_t *cha, long isize, long icount); void xdl_cha_free(chastore_t *cha); void *xdl_cha_alloc(chastore_t *cha); -void *xdl_cha_first(chastore_t *cha); -void *xdl_cha_next(chastore_t *cha); long xdl_guess_lines(mmfile_t *mf, long sample); +int xdl_blankline(const char *line, long size, long flags); int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags); unsigned long xdl_hash_record(char const **data, char const *top, long flags); unsigned int xdl_hashbits(unsigned int size); int xdl_num_out(char *out, long val); -long xdl_atol(char const *str, char const **next); int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, const char *func, long funclen, xdemitcb_t *ecb); int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, |