Re: [PATCH 10/10] xdiff: move xdl_cleanup_records() from xprepare.c to xdiffi.c

> From: Ezekiel Newren <ezekielnewren@gmail.com>
> 
> Only the classic diff uses xdl_cleanup_records(). Move it,
> xdl_clean_mmatch(), and the macros to xdiffi.c and call
> xdl_cleanup_records() inside of xdl_do_classic_diff(). This better
> organizes the code related to the classic diff.

> Signed-off-by: Ezekiel Newren <ezekielnewren@gmail.com>
> ---
>   xdiff/xdiffi.c   | 180 ++++++++++++++++++++++++++++++++++++++++++++
>   xdiff/xprepare.c | 191 +----------------------------------------------
>   2 files changed, 181 insertions(+), 190 deletions(-)
> 
> diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
> index e3196c7245..0f1fd7cf80 100644
> --- a/xdiff/xdiffi.c
> +++ b/xdiff/xdiffi.c
> @@ -21,6 +21,7 @@
>    */
>   
>   #include "xinclude.h"
> +#include "compat/ivec.h"
>   
>   static size_t get_hash(xdfile_t *xdf, long index)
>   {
> @@ -33,6 +34,14 @@ static size_t get_hash(xdfile_t *xdf, long index)
>   #define XDL_SNAKE_CNT 20
>   #define XDL_K_HEUR 4
>   
> +#define XDL_KPDIS_RUN 4
> +#define XDL_MAX_EQLIMIT 1024
> +#define XDL_SIMSCAN_WINDOW 100
> +
> +#define DISCARD 0
> +#define KEEP 1
> +#define INVESTIGATE 2
> +
>   typedef struct s_xdpsplit {
>   	long i1, i2;
>   	int min_lo, min_hi;
> @@ -311,6 +320,175 @@ int xdl_recs_cmp(xdfile_t *xdf1, long off1, long lim1,
>   }
>   
>   
> +static bool xdl_clean_mmatch(uint8_t const *action, long i, long s, long e) {
> +	long r, rdis0, rpdis0, rdis1, rpdis1;
> +
> +	/*
> +	 * Limits the window that is examined during the similar-lines
> +	 * scan. The loops below stops when action[i - r] == KEEP
> +	 * (line that has no match), but there are corner cases where
> +	 * the loop proceed all the way to the extremities by causing
> +	 * huge performance penalties in case of big files.
> +	 */
> +	if (i - s > XDL_SIMSCAN_WINDOW)
> +		s = i - XDL_SIMSCAN_WINDOW;
> +	if (e - i > XDL_SIMSCAN_WINDOW)
> +		e = i + XDL_SIMSCAN_WINDOW;
> +
> +	/*
> +	 * Scans the lines before 'i' to find a run of lines that either
> +	 * have no match (action[j] == DISCARD) or have multiple matches
> +	 * (action[j] == INVESTIGATE). Note that we always call this
> +	 * function with action[i] == INVESTIGATE, so the current line
> +	 * (i) is already a multimatch line.
> +	 */
> +	for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {
> +		if (action[i - r] == DISCARD)
> +			rdis0++;
> +		else if (action[i - r] == INVESTIGATE)
> +			rpdis0++;
> +		else if (action[i - r] == KEEP)
> +			break;
> +		else
> +			BUG("Illegal value for action[i - r]");
> +	}
> +	/*
> +	 * If the run before the line 'i' found only multimatch lines,
> +	 * we return false 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
> +	 * (action[j] == DISCARD).
> +	 */
> +	if (rdis0 == 0)
> +		return 0;
> +	for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {
> +		if (action[i + r] == DISCARD)
> +			rdis1++;
> +		else if (action[i + r] == INVESTIGATE)
> +			rpdis1++;
> +		else if (action[i + r] == KEEP)
> +			break;
> +		else
> +			BUG("Illegal value for action[i + r]");
> +	}
> +	/*
> +	 * If the run after the line 'i' found only multimatch lines,
> +	 * we return false and hence we don't make the current line (i)
> +	 * discarded.
> +	 */
> +	if (rdis1 == 0)
> +		return false;
> +	rdis1 += rdis0;
> +	rpdis1 += rpdis0;
> +
> +	return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1);
> +}
> +
> +struct xoccurrence
> +{
> +	size_t file1, file2;
> +};
> +
> +
> +DEFINE_IVEC_TYPE(struct xoccurrence, xoccurrence);
> +
> +
> +/*
> + * Try to reduce the problem complexity, discard records that have no
> + * matches on the other file. Also, lines that have multiple matches
> + * might be potentially discarded if they appear in a run of discardable.
> + */
> +static int xdl_cleanup_records(xdfenv_t *xe, uint64_t flags) {
> +	long i;
> +	size_t nm, mlim;
> +	xrecord_t *recs;
> +	uint8_t *action1 = NULL, *action2 = NULL;
> +	struct IVec_xoccurrence occ;
> +	bool need_min = !!(flags & XDF_NEED_MINIMAL);
> +	int ret = 0;
> +	ptrdiff_t dend1 = xe->xdf1.nrec - 1 - xe->delta_end;
> +	ptrdiff_t dend2 = xe->xdf2.nrec - 1 - xe->delta_end;
> +
> +	IVEC_INIT(occ);
> +	ivec_zero(&occ, xe->mph_size);
> +
> +	for (size_t j = 0; j < xe->xdf1.nrec; j++) {
> +		size_t mph1 = xe->xdf1.recs[j].minimal_perfect_hash;
> +		occ.ptr[mph1].file1 += 1;
> +	}
> +
> +	for (size_t j = 0; j < xe->xdf2.nrec; j++) {
> +		size_t mph2 = xe->xdf2.recs[j].minimal_perfect_hash;
> +		occ.ptr[mph2].file2 += 1;
> +	}
> +
> +	/*
> +	 * Create temporary arrays that will help us decide if
> +	 * changed[i] should remain false, or become true.
> +	 */
> +	if (!XDL_CALLOC_ARRAY(action1, xe->xdf1.nrec + 1)) {
> +		ret = -1;
> +		goto cleanup;
> +	}
> +	if (!XDL_CALLOC_ARRAY(action2, xe->xdf2.nrec + 1)) {
> +		ret = -1;
> +		goto cleanup;
> +	}
> +
> +	/*
> +	 * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.
> +	 */
> +	if ((mlim = xdl_bogosqrt((long)xe->xdf1.nrec)) > XDL_MAX_EQLIMIT)
> +		mlim = XDL_MAX_EQLIMIT;
> +	for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start]; i <= dend1; i++, recs++) {
> +		nm = occ.ptr[recs->minimal_perfect_hash].file2;
> +		action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
> +	}
> +
> +	if ((mlim = xdl_bogosqrt((long)xe->xdf2.nrec)) > XDL_MAX_EQLIMIT)
> +		mlim = XDL_MAX_EQLIMIT;
> +	for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start]; i <= dend2; i++, recs++) {
> +		nm = occ.ptr[recs->minimal_perfect_hash].file1;
> +		action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
> +	}
> +
> +	/*
> +	 * Use temporary arrays to decide if changed[i] should remain
> +	 * false, or become true.
> +	 */
> +	xe->xdf1.nreff = 0;
> +	for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start];
> +	     i <= dend1; i++, recs++) {
> +		if (action1[i] == KEEP ||
> +		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xe->delta_start, dend1))) {
> +			xe->xdf1.reference_index[xe->xdf1.nreff++] = i;
> +			/* changed[i] remains false, i.e. keep */
> +		} else
> +			xe->xdf1.changed[i] = true;
> +			/* i.e. discard */
> +	}
> +
> +	xe->xdf2.nreff = 0;
> +	for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start];
> +	     i <= dend2; i++, recs++) {
> +		if (action2[i] == KEEP ||
> +		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xe->delta_start, dend2))) {
> +			xe->xdf2.reference_index[xe->xdf2.nreff++] = i;
> +			/* changed[i] remains false, i.e. keep */
> +		} else
> +			xe->xdf2.changed[i] = true;
> +			/* i.e. discard */
> +	}
> +
> +cleanup:
> +	xdl_free(action1);
> +	xdl_free(action2);
> +	ivec_free(&occ);
> +
> +	return ret;
> +}
> +
> +
>   int xdl_do_classic_diff(xdfenv_t *xe, uint64_t flags)
>   {
>   	long ndiags;
> @@ -318,6 +496,8 @@ int xdl_do_classic_diff(xdfenv_t *xe, uint64_t flags)
>   	xdalgoenv_t xenv;
>   	int res;
>   
> +	xdl_cleanup_records(xe, flags);
> +
>   	/*
>   	 * Allocate and setup K vectors to be used by the differential
>   	 * algorithm.
> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
> index b53a3b80c4..3f555e29f4 100644
> --- a/xdiff/xprepare.c
> +++ b/xdiff/xprepare.c
> @@ -24,14 +24,6 @@
>   #include "compat/ivec.h"
>   
>   
> -#define XDL_KPDIS_RUN 4
> -#define XDL_MAX_EQLIMIT 1024
> -#define XDL_SIMSCAN_WINDOW 100
> -
> -#define DISCARD 0
> -#define KEEP 1
> -#define INVESTIGATE 2
> -
>   typedef struct s_xdlclass {
>   	struct s_xdlclass *next;
>   	xrecord_t rec;
> @@ -50,8 +42,6 @@ typedef struct s_xdlclassifier {
>   } xdlclassifier_t;
>   
>   
> -
> -
>   static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
>   	memset(cf, 0, sizeof(xdlclassifier_t));
>   
> @@ -186,175 +176,6 @@ void xdl_free_env(xdfenv_t *xe) {
>   }
>   
>   
> -static bool xdl_clean_mmatch(uint8_t const *action, long i, long s, long e) {
> -	long r, rdis0, rpdis0, rdis1, rpdis1;
> -
> -	/*
> -	 * Limits the window that is examined during the similar-lines
> -	 * scan. The loops below stops when action[i - r] == KEEP
> -	 * (line that has no match), but there are corner cases where
> -	 * the loop proceed all the way to the extremities by causing
> -	 * huge performance penalties in case of big files.
> -	 */
> -	if (i - s > XDL_SIMSCAN_WINDOW)
> -		s = i - XDL_SIMSCAN_WINDOW;
> -	if (e - i > XDL_SIMSCAN_WINDOW)
> -		e = i + XDL_SIMSCAN_WINDOW;
> -
> -	/*
> -	 * Scans the lines before 'i' to find a run of lines that either
> -	 * have no match (action[j] == DISCARD) or have multiple matches
> -	 * (action[j] == INVESTIGATE). Note that we always call this
> -	 * function with action[i] == INVESTIGATE, so the current line
> -	 * (i) is already a multimatch line.
> -	 */
> -	for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {
> -		if (action[i - r] == DISCARD)
> -			rdis0++;
> -		else if (action[i - r] == INVESTIGATE)
> -			rpdis0++;
> -		else if (action[i - r] == KEEP)
> -			break;
> -		else
> -			BUG("Illegal value for action[i - r]");
> -	}
> -	/*
> -	 * If the run before the line 'i' found only multimatch lines,
> -	 * we return false 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
> -	 * (action[j] == DISCARD).
> -	 */
> -	if (rdis0 == 0)
> -		return 0;
> -	for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {
> -		if (action[i + r] == DISCARD)
> -			rdis1++;
> -		else if (action[i + r] == INVESTIGATE)
> -			rpdis1++;
> -		else if (action[i + r] == KEEP)
> -			break;
> -		else
> -			BUG("Illegal value for action[i + r]");
> -	}
> -	/*
> -	 * If the run after the line 'i' found only multimatch lines,
> -	 * we return false and hence we don't make the current line (i)
> -	 * discarded.
> -	 */
> -	if (rdis1 == 0)
> -		return false;
> -	rdis1 += rdis0;
> -	rpdis1 += rpdis0;
> -
> -	return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1);
> -}
> -
> -struct xoccurrence
> -{
> -	size_t file1, file2;
> -};
> -
> -
> -DEFINE_IVEC_TYPE(struct xoccurrence, xoccurrence);
> -
> -
> -/*
> - * Try to reduce the problem complexity, discard records that have no
> - * matches on the other file. Also, lines that have multiple matches
> - * might be potentially discarded if they appear in a run of discardable.
> - */
> -static int xdl_cleanup_records(xdfenv_t *xe, uint64_t flags) {
> -	long i;
> -	size_t nm, mlim;
> -	xrecord_t *recs;
> -	uint8_t *action1 = NULL, *action2 = NULL;
> -	struct IVec_xoccurrence occ;
> -	bool need_min = !!(flags & XDF_NEED_MINIMAL);
> -	int ret = 0;
> -	ptrdiff_t dend1 = xe->xdf1.nrec - 1 - xe->delta_end;
> -	ptrdiff_t dend2 = xe->xdf2.nrec - 1 - xe->delta_end;
> -
> -	IVEC_INIT(occ);
> -	ivec_zero(&occ, xe->mph_size);
> -
> -	for (size_t j = 0; j < xe->xdf1.nrec; j++) {
> -		size_t mph1 = xe->xdf1.recs[j].minimal_perfect_hash;
> -		occ.ptr[mph1].file1 += 1;
> -	}
> -
> -	for (size_t j = 0; j < xe->xdf2.nrec; j++) {
> -		size_t mph2 = xe->xdf2.recs[j].minimal_perfect_hash;
> -		occ.ptr[mph2].file2 += 1;
> -	}
> -
> -	/*
> -	 * Create temporary arrays that will help us decide if
> -	 * changed[i] should remain false, or become true.
> -	 */
> -	if (!XDL_CALLOC_ARRAY(action1, xe->xdf1.nrec + 1)) {
> -		ret = -1;
> -		goto cleanup;
> -	}
> -	if (!XDL_CALLOC_ARRAY(action2, xe->xdf2.nrec + 1)) {
> -		ret = -1;
> -		goto cleanup;
> -	}
> -
> -	/*
> -	 * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.
> -	 */
> -	if ((mlim = xdl_bogosqrt((long)xe->xdf1.nrec)) > XDL_MAX_EQLIMIT)
> -		mlim = XDL_MAX_EQLIMIT;
> -	for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start]; i <= dend1; i++, recs++) {
> -		nm = occ.ptr[recs->minimal_perfect_hash].file2;
> -		action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
> -	}
> -
> -	if ((mlim = xdl_bogosqrt((long)xe->xdf2.nrec)) > XDL_MAX_EQLIMIT)
> -		mlim = XDL_MAX_EQLIMIT;
> -	for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start]; i <= dend2; i++, recs++) {
> -		nm = occ.ptr[recs->minimal_perfect_hash].file1;
> -		action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
> -	}
> -
> -	/*
> -	 * Use temporary arrays to decide if changed[i] should remain
> -	 * false, or become true.
> -	 */
> -	xe->xdf1.nreff = 0;
> -	for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start];
> -	     i <= dend1; i++, recs++) {
> -		if (action1[i] == KEEP ||
> -		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xe->delta_start, dend1))) {
> -			xe->xdf1.reference_index[xe->xdf1.nreff++] = i;
> -			/* changed[i] remains false, i.e. keep */
> -		} else
> -			xe->xdf1.changed[i] = true;
> -			/* i.e. discard */
> -	}
> -
> -	xe->xdf2.nreff = 0;
> -	for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start];
> -	     i <= dend2; i++, recs++) {
> -		if (action2[i] == KEEP ||
> -		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xe->delta_start, dend2))) {
> -			xe->xdf2.reference_index[xe->xdf2.nreff++] = i;
> -			/* changed[i] remains false, i.e. keep */
> -		} else
> -			xe->xdf2.changed[i] = true;
> -			/* i.e. discard */
> -	}
> -
> -cleanup:
> -	xdl_free(action1);
> -	xdl_free(action2);
> -	ivec_free(&occ);
> -
> -	return ret;
> -}
> -
> -
>   /*
>    * Early trim initial and terminal matching records.
>    */
> @@ -414,19 +235,9 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
>   	}
>   
>   	xe->mph_size = cf.count;
> +	xdl_free_classifier(&cf);
>   
>   	xdl_trim_ends(xe);
> -	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
> -	    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
> -	    xdl_cleanup_records(xe, xpp->flags) < 0) {
> -
> -		xdl_free_ctx(&xe->xdf2);
> -		xdl_free_ctx(&xe->xdf1);
> -		xdl_free_classifier(&cf);
> -		return -1;
> -	}
> -
> -	xdl_free_classifier(&cf);
>   
>   	return 0;
>   }