revision traversal: retire BOUNDARY_SHOW
[gitweb.git] / xdiff / xprepare.c
index 27a08791a2eee9f5f0565509e2c6bf2aa7b768c8..1be7b3195059bebffe83d17301f3ff0fb261799e 100644 (file)
@@ -25,6 +25,7 @@
 
 
 #define XDL_KPDIS_RUN 4
+#define XDL_MAX_EQLIMIT 1024
 
 
 
@@ -42,12 +43,13 @@ typedef struct s_xdlclassifier {
        xdlclass_t **rchash;
        chastore_t ncha;
        long count;
+       long flags;
 } xdlclassifier_t;
 
 
 
 
-static int xdl_init_classifier(xdlclassifier_t *cf, long size);
+static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags);
 static void xdl_free_classifier(xdlclassifier_t *cf);
 static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,
                               xrecord_t *rec);
@@ -62,9 +64,11 @@ static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2);
 
 
 
-static int xdl_init_classifier(xdlclassifier_t *cf, long size) {
+static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
        long i;
 
+       cf->flags = flags;
+
        cf->hbits = xdl_hashbits((unsigned int) size);
        cf->hsize = 1 << cf->hbits;
 
@@ -102,8 +106,9 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned
        line = rec->ptr;
        hi = (long) XDL_HASHLONG(rec->ha, cf->hbits);
        for (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next)
-               if (rcrec->ha == rec->ha && rcrec->size == rec->size &&
-                   !memcmp(line, rcrec->line, rec->size))
+               if (rcrec->ha == rec->ha &&
+                               xdl_recmatch(rcrec->line, rcrec->size,
+                                       rec->ptr, rec->size, cf->flags))
                        break;
 
        if (!rcrec) {
@@ -172,7 +177,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
                                top = blk + bsize;
                        }
                        prev = cur;
-                       hav = xdl_hash_record(&cur, top);
+                       hav = xdl_hash_record(&cur, top, xpp->flags);
                        if (nrec >= narec) {
                                narec *= 2;
                                if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *)))) {
@@ -267,7 +272,7 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
        enl1 = xdl_guess_lines(mf1) + 1;
        enl2 = xdl_guess_lines(mf2) + 1;
 
-       if (xdl_init_classifier(&cf, enl1 + enl2 + 1) < 0) {
+       if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) {
 
                return -1;
        }
@@ -305,26 +310,48 @@ void xdl_free_env(xdfenv_t *xe) {
 
 
 static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
-       long r, rdis, rpdis;
-
-       for (r = 1, rdis = 0, rpdis = 1; (i - r) >= s; r++) {
+       long r, rdis0, rpdis0, rdis1, rpdis1;
+
+       /*
+        * Scans the lines before 'i' to find a run of lines that either
+        * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1).
+        * Note that we always call this function with dis[i] > 1, so the
+        * current line (i) is already a multimatch line.
+        */
+       for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {
                if (!dis[i - r])
-                       rdis++;
+                       rdis0++;
                else if (dis[i - r] == 2)
-                       rpdis++;
+                       rpdis0++;
                else
                        break;
        }
-       for (r = 1; (i + r) <= e; r++) {
+       /*
+        * If the run before the line 'i' found only multimatch lines, we
+        * return 0 and hence we don't make the current line (i) discarded.
+        * We want to discard multimatch lines only when they appear in the
+        * middle of runs with nomatch lines (dis[j] == 0).
+        */
+       if (rdis0 == 0)
+               return 0;
+       for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {
                if (!dis[i + r])
-                       rdis++;
+                       rdis1++;
                else if (dis[i + r] == 2)
-                       rpdis++;
+                       rpdis1++;
                else
                        break;
        }
-
-       return rpdis * XDL_KPDIS_RUN < (rpdis + rdis);
+       /*
+        * If the run after the line 'i' found only multimatch lines, we
+        * return 0 and hence we don't make the current line (i) discarded.
+        */
+       if (rdis1 == 0)
+               return 0;
+       rdis1 += rdis0;
+       rpdis1 += rpdis0;
+
+       return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1);
 }
 
 
@@ -334,34 +361,40 @@ 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(xdfile_t *xdf1, xdfile_t *xdf2) {
-       long i, rhi, nreff;
+       long i, nm, rhi, nreff, mlim;
        unsigned long hav;
        xrecord_t **recs;
        xrecord_t *rec;
        char *dis, *dis1, *dis2;
 
-       if (!(dis = (char *) xdl_malloc((xdf1->nrec + xdf2->nrec + 2) * sizeof(char)))) {
+       if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {
 
                return -1;
        }
-       memset(dis, 0, (xdf1->nrec + xdf2->nrec + 2) * sizeof(char));
+       memset(dis, 0, xdf1->nrec + xdf2->nrec + 2);
        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++) {
                hav = (*recs)->ha;
                rhi = (long) XDL_HASHLONG(hav, xdf2->hbits);
-               for (rec = xdf2->rhash[rhi]; rec; rec = rec->next)
-                       if (rec->ha == hav && ++dis1[i] == 2)
+               for (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)
+                       if (rec->ha == hav && ++nm == mlim)
                                break;
+               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++) {
                hav = (*recs)->ha;
                rhi = (long) XDL_HASHLONG(hav, xdf1->hbits);
-               for (rec = xdf1->rhash[rhi]; rec; rec = rec->next)
-                       if (rec->ha == hav && ++dis2[i] == 2)
+               for (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)
+                       if (rec->ha == hav && ++nm == mlim)
                                break;
+               dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
        }
 
        for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];