summaryrefslogtreecommitdiff
path: root/xdiff
diff options
context:
space:
mode:
Diffstat (limited to 'xdiff')
-rw-r--r--xdiff/xdiff.h2
-rw-r--r--xdiff/xdiffi.c60
-rw-r--r--xdiff/xdiffi.h6
-rw-r--r--xdiff/xemit.c6
-rw-r--r--xdiff/xhistogram.c38
-rw-r--r--xdiff/xmacros.h19
-rw-r--r--xdiff/xmerge.c105
-rw-r--r--xdiff/xpatience.c51
-rw-r--r--xdiff/xprepare.c70
-rw-r--r--xdiff/xutils.c19
-rw-r--r--xdiff/xutils.h3
11 files changed, 209 insertions, 170 deletions
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h
index b29deca..bb56b23 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h
@@ -66,6 +66,7 @@ extern "C" {
/* merge output styles */
#define XDL_MERGE_DIFF3 1
+#define XDL_MERGE_ZEALOUS_DIFF3 2
typedef struct s_mmfile {
char *ptr;
@@ -119,6 +120,7 @@ typedef struct s_bdiffparam {
#define xdl_malloc(x) xmalloc(x)
+#define xdl_calloc(n, sz) xcalloc(n, sz)
#define xdl_free(ptr) free(ptr)
#define xdl_realloc(ptr,x) xrealloc(ptr,x)
diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index a4542c0..344c2df 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -315,16 +315,19 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
long *kvd, *kvdf, *kvdb;
xdalgoenv_t xenv;
diffdata_t dd1, dd2;
+ int res;
- if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF)
- return xdl_do_patience_diff(mf1, mf2, xpp, xe);
-
- 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)
+ return -1;
- if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {
+ if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF) {
+ res = xdl_do_patience_diff(xpp, xe);
+ goto out;
+ }
- return -1;
+ if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) {
+ res = xdl_do_histogram_diff(xpp, xe);
+ goto out;
}
/*
@@ -334,7 +337,7 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
* One is to store the forward path and one to store the backward path.
*/
ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
- if (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) {
+ if (!XDL_ALLOC_ARRAY(kvd, 2 * ndiags + 2)) {
xdl_free_env(xe);
return -1;
@@ -359,17 +362,15 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
dd2.rchg = xe->xdf2.rchg;
dd2.rindex = xe->xdf2.rindex;
- if (xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,
- kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0, &xenv) < 0) {
-
- xdl_free(kvd);
- xdl_free_env(xe);
- return -1;
- }
-
+ res = xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,
+ kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0,
+ &xenv);
xdl_free(kvd);
+ out:
+ if (res < 0)
+ xdl_free_env(xe);
- return 0;
+ return res;
}
@@ -390,12 +391,9 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
}
-static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags)
+static int recs_match(xrecord_t *rec1, xrecord_t *rec2)
{
- return (rec1->ha == rec2->ha &&
- xdl_recmatch(rec1->ptr, rec1->size,
- rec2->ptr, rec2->size,
- flags));
+ return (rec1->ha == rec2->ha);
}
/*
@@ -759,10 +757,10 @@ static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g)
* following group, expand this group to include it. Return 0 on success or -1
* if g cannot be slid down.
*/
-static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g, long flags)
+static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g)
{
if (g->end < xdf->nrec &&
- recs_match(xdf->recs[g->start], xdf->recs[g->end], flags)) {
+ recs_match(xdf->recs[g->start], xdf->recs[g->end])) {
xdf->rchg[g->start++] = 0;
xdf->rchg[g->end++] = 1;
@@ -780,10 +778,10 @@ static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g, long flags)
* into a previous group, expand this group to include it. Return 0 on success
* or -1 if g cannot be slid up.
*/
-static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g, long flags)
+static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g)
{
if (g->start > 0 &&
- recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1], flags)) {
+ recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1])) {
xdf->rchg[--g->start] = 1;
xdf->rchg[--g->end] = 0;
@@ -833,7 +831,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
end_matching_other = -1;
/* Shift the group backward as much as possible: */
- while (!group_slide_up(xdf, &g, flags))
+ while (!group_slide_up(xdf, &g))
if (group_previous(xdfo, &go))
BUG("group sync broken sliding up");
@@ -848,7 +846,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
/* Now shift the group forward as far as possible: */
while (1) {
- if (group_slide_down(xdf, &g, flags))
+ if (group_slide_down(xdf, &g))
break;
if (group_next(xdfo, &go))
BUG("group sync broken sliding down");
@@ -875,7 +873,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
* other file that it can align with.
*/
while (go.end == go.start) {
- if (group_slide_up(xdf, &g, flags))
+ if (group_slide_up(xdf, &g))
BUG("match disappeared");
if (group_previous(xdfo, &go))
BUG("group sync broken sliding to match");
@@ -918,7 +916,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
}
while (g.end > best_shift) {
- if (group_slide_up(xdf, &g, flags))
+ if (group_slide_up(xdf, &g))
BUG("best shift unreached");
if (group_previous(xdfo, &go))
BUG("group sync broken sliding to blank line");
@@ -975,7 +973,7 @@ void xdl_free_script(xdchange_t *xscr) {
}
}
-static int xdl_call_hunk_func(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
+static int xdl_call_hunk_func(xdfenv_t *xe UNUSED, xdchange_t *xscr, xdemitcb_t *ecb,
xdemitconf_t const *xecfg)
{
xdchange_t *xch, *xche;
diff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h
index 8f1c7c8..126c9d8 100644
--- a/xdiff/xdiffi.h
+++ b/xdiff/xdiffi.h
@@ -56,9 +56,7 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr);
void xdl_free_script(xdchange_t *xscr);
int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
xdemitconf_t const *xecfg);
-int xdl_do_patience_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
- xdfenv_t *env);
-int xdl_do_histogram_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
- xdfenv_t *env);
+int xdl_do_patience_diff(xpparam_t const *xpp, xdfenv_t *env);
+int xdl_do_histogram_diff(xpparam_t const *xpp, xdfenv_t *env);
#endif /* #if !defined(XDIFFI_H) */
diff --git a/xdiff/xemit.c b/xdiff/xemit.c
index 1cbf2b9..75f0fe4 100644
--- a/xdiff/xemit.c
+++ b/xdiff/xemit.c
@@ -65,7 +65,7 @@ xdchange_t *xdl_get_hunk(xdchange_t **xscr, xdemitconf_t const *xecfg)
*xscr = xch;
}
- if (*xscr == NULL)
+ if (!*xscr)
return NULL;
lxch = *xscr;
@@ -95,7 +95,7 @@ xdchange_t *xdl_get_hunk(xdchange_t **xscr, xdemitconf_t const *xecfg)
}
-static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)
+static long def_ff(const char *rec, long len, char *buf, long sz)
{
if (len > 0 &&
(isalpha((unsigned char)*rec) || /* identifier? */
@@ -117,7 +117,7 @@ static long match_func_rec(xdfile_t *xdf, xdemitconf_t const *xecfg, long ri,
const char *rec;
long len = xdl_get_rec(xdf, ri, &rec);
if (!xecfg->find_func)
- return def_ff(rec, len, buf, sz, xecfg->find_func_priv);
+ return def_ff(rec, len, buf, sz);
return xecfg->find_func(rec, len, buf, sz, xecfg->find_func_priv);
}
diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c
index e694bfd..16a8fe2 100644
--- a/xdiff/xhistogram.c
+++ b/xdiff/xhistogram.c
@@ -88,19 +88,14 @@ struct region {
#define REC(env, s, l) \
(env->xdf##s.recs[l - 1])
-static int cmp_recs(xpparam_t const *xpp,
- xrecord_t *r1, xrecord_t *r2)
+static int cmp_recs(xrecord_t *r1, xrecord_t *r2)
{
- return r1->ha == r2->ha &&
- xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,
- xpp->flags);
-}
+ return r1->ha == r2->ha;
-#define CMP_ENV(xpp, env, s1, l1, s2, l2) \
- (cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2)))
+}
#define CMP(i, s1, l1, s2, l2) \
- (cmp_recs(i->xpp, REC(i->env, s1, l1), REC(i->env, s2, l2)))
+ (cmp_recs(REC(i->env, s1, l1), REC(i->env, s2, l2)))
#define TABLE_HASH(index, side, line) \
XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)
@@ -256,7 +251,7 @@ static int find_lcs(xpparam_t const *xpp, xdfenv_t *env,
int line1, int count1, int line2, int count2)
{
int b_ptr;
- int sz, ret = -1;
+ int ret = -1;
struct histindex index;
memset(&index, 0, sizeof(index));
@@ -270,23 +265,16 @@ static int find_lcs(xpparam_t const *xpp, xdfenv_t *env,
index.rcha.head = NULL;
index.table_bits = xdl_hashbits(count1);
- sz = index.records_size = 1 << index.table_bits;
- sz *= sizeof(struct record *);
- if (!(index.records = (struct record **) xdl_malloc(sz)))
+ index.records_size = 1 << index.table_bits;
+ if (!XDL_CALLOC_ARRAY(index.records, index.records_size))
goto cleanup;
- memset(index.records, 0, sz);
- sz = index.line_map_size = count1;
- sz *= sizeof(struct record *);
- if (!(index.line_map = (struct record **) xdl_malloc(sz)))
+ index.line_map_size = count1;
+ if (!XDL_CALLOC_ARRAY(index.line_map, index.line_map_size))
goto cleanup;
- memset(index.line_map, 0, sz);
- sz = index.line_map_size;
- sz *= sizeof(unsigned int);
- if (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz)))
+ if (!XDL_CALLOC_ARRAY(index.next_ptrs, index.line_map_size))
goto cleanup;
- memset(index.next_ptrs, 0, sz);
/* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */
if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)
@@ -374,12 +362,8 @@ out:
return result;
}
-int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2,
- xpparam_t const *xpp, xdfenv_t *env)
+int xdl_do_histogram_diff(xpparam_t const *xpp, xdfenv_t *env)
{
- if (xdl_prepare_env(file1, file2, xpp, env) < 0)
- return -1;
-
return histogram_diff(xpp, env,
env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,
env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);
diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h
index 2809a28..8487bb3 100644
--- a/xdiff/xmacros.h
+++ b/xdiff/xmacros.h
@@ -34,7 +34,6 @@
#define XDL_ADDBITS(v,b) ((v) + ((v) >> (b)))
#define XDL_MASKBITS(b) ((1UL << (b)) - 1)
#define XDL_HASHLONG(v,b) (XDL_ADDBITS((unsigned long)(v), b) & XDL_MASKBITS(b))
-#define XDL_PTRFREE(p) do { if (p) { xdl_free(p); (p) = NULL; } } while (0)
#define XDL_LE32_PUT(p, v) \
do { \
unsigned char *__p = (unsigned char *) (p); \
@@ -50,5 +49,23 @@ do { \
((unsigned long) __p[2]) << 16 | ((unsigned long) __p[3]) << 24; \
} while (0)
+/* Allocate an array of nr elements, returns NULL on failure */
+#define XDL_ALLOC_ARRAY(p, nr) \
+ ((p) = SIZE_MAX / sizeof(*(p)) >= (size_t)(nr) \
+ ? xdl_malloc((nr) * sizeof(*(p))) \
+ : NULL)
+
+/* Allocate an array of nr zeroed out elements, returns NULL on failure */
+#define XDL_CALLOC_ARRAY(p, nr) ((p) = xdl_calloc(nr, sizeof(*(p))))
+
+/*
+ * Ensure array p can accommodate at least nr elements, growing the
+ * array and updating alloc (which is the number of allocated
+ * elements) as necessary. Frees p and returns -1 on failure, returns
+ * 0 on success
+ */
+#define XDL_ALLOC_GROW(p, nr, alloc) \
+ (-!((nr) <= (alloc) || \
+ ((p) = xdl_alloc_grow_helper((p), (nr), &(alloc), sizeof(*(p))))))
#endif /* #if !defined(XMACROS_H) */
diff --git a/xdiff/xmerge.c b/xdiff/xmerge.c
index 1659edb..af40c88 100644
--- a/xdiff/xmerge.c
+++ b/xdiff/xmerge.c
@@ -230,7 +230,7 @@ static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1,
size += xdl_recs_copy(xe1, m->i1, m->chg1, needs_cr, 1,
dest ? dest + size : NULL);
- if (style == XDL_MERGE_DIFF3) {
+ if (style == XDL_MERGE_DIFF3 || style == XDL_MERGE_ZEALOUS_DIFF3) {
/* Shared preimage */
if (!dest) {
size += marker_size + 1 + needs_cr + marker3_size;
@@ -322,6 +322,40 @@ static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1,
return size;
}
+static int recmatch(xrecord_t *rec1, xrecord_t *rec2, unsigned long flags)
+{
+ return xdl_recmatch(rec1->ptr, rec1->size,
+ rec2->ptr, rec2->size, flags);
+}
+
+/*
+ * Remove any common lines from the beginning and end of the conflicted region.
+ */
+static void xdl_refine_zdiff3_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
+ xpparam_t const *xpp)
+{
+ xrecord_t **rec1 = xe1->xdf2.recs, **rec2 = xe2->xdf2.recs;
+ for (; m; m = m->next) {
+ /* let's handle just the conflicts */
+ if (m->mode)
+ continue;
+
+ while(m->chg1 && m->chg2 &&
+ recmatch(rec1[m->i1], rec2[m->i2], xpp->flags)) {
+ m->chg1--;
+ m->chg2--;
+ m->i1++;
+ m->i2++;
+ }
+ while (m->chg1 && m->chg2 &&
+ recmatch(rec1[m->i1 + m->chg1 - 1],
+ rec2[m->i2 + m->chg2 - 1], xpp->flags)) {
+ m->chg1--;
+ m->chg2--;
+ }
+ }
+}
+
/*
* Sometimes, changes are not quite identical, but differ in only a few
* lines. Try hard to show only these few lines as conflicting.
@@ -482,7 +516,22 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
int style = xmp->style;
int favor = xmp->favor;
- if (style == XDL_MERGE_DIFF3) {
+ /*
+ * XDL_MERGE_DIFF3 does not attempt to refine conflicts by looking
+ * at common areas of sides 1 & 2, because the base (side 0) does
+ * not match and is being shown. Similarly, simplification of
+ * non-conflicts is also skipped due to the skipping of conflict
+ * refinement.
+ *
+ * XDL_MERGE_ZEALOUS_DIFF3, on the other hand, will attempt to
+ * refine conflicts looking for common areas of sides 1 & 2.
+ * However, since the base is being shown and does not match,
+ * it will only look for common areas at the beginning or end
+ * of the conflict block. Since XDL_MERGE_ZEALOUS_DIFF3's
+ * conflict refinement is much more limited in this fashion, the
+ * conflict simplification will be skipped.
+ */
+ if (style == XDL_MERGE_DIFF3 || style == XDL_MERGE_ZEALOUS_DIFF3) {
/*
* "diff3 -m" output does not make sense for anything
* more aggressive than XDL_MERGE_EAGER.
@@ -603,10 +652,12 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
if (!changes)
changes = c;
/* refine conflicts */
- if (XDL_MERGE_ZEALOUS <= level &&
- (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 ||
- xdl_simplify_non_conflicts(xe1, changes,
- XDL_MERGE_ZEALOUS < level) < 0)) {
+ if (style == XDL_MERGE_ZEALOUS_DIFF3) {
+ xdl_refine_zdiff3_conflicts(xe1, xe2, changes, xpp);
+ } else if (XDL_MERGE_ZEALOUS <= level &&
+ (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 ||
+ xdl_simplify_non_conflicts(xe1, changes,
+ XDL_MERGE_ZEALOUS < level) < 0)) {
xdl_cleanup_merge(changes);
return -1;
}
@@ -633,42 +684,42 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2,
xmparam_t const *xmp, mmbuffer_t *result)
{
- xdchange_t *xscr1, *xscr2;
+ xdchange_t *xscr1 = NULL, *xscr2 = NULL;
xdfenv_t xe1, xe2;
- int status;
+ int status = -1;
xpparam_t const *xpp = &xmp->xpp;
result->ptr = NULL;
result->size = 0;
- if (xdl_do_diff(orig, mf1, xpp, &xe1) < 0) {
- return -1;
- }
- if (xdl_do_diff(orig, mf2, xpp, &xe2) < 0) {
- xdl_free_env(&xe1);
+ if (xdl_do_diff(orig, mf1, xpp, &xe1) < 0)
return -1;
- }
+
+ if (xdl_do_diff(orig, mf2, xpp, &xe2) < 0)
+ goto free_xe1; /* avoid double free of xe2 */
+
if (xdl_change_compact(&xe1.xdf1, &xe1.xdf2, xpp->flags) < 0 ||
xdl_change_compact(&xe1.xdf2, &xe1.xdf1, xpp->flags) < 0 ||
- xdl_build_script(&xe1, &xscr1) < 0) {
- xdl_free_env(&xe1);
- return -1;
- }
+ xdl_build_script(&xe1, &xscr1) < 0)
+ goto out;
+
if (xdl_change_compact(&xe2.xdf1, &xe2.xdf2, xpp->flags) < 0 ||
xdl_change_compact(&xe2.xdf2, &xe2.xdf1, xpp->flags) < 0 ||
- xdl_build_script(&xe2, &xscr2) < 0) {
- xdl_free_script(xscr1);
- xdl_free_env(&xe1);
- xdl_free_env(&xe2);
- return -1;
- }
- status = 0;
+ xdl_build_script(&xe2, &xscr2) < 0)
+ goto out;
+
if (!xscr1) {
result->ptr = xdl_malloc(mf2->size);
+ if (!result->ptr)
+ goto out;
+ status = 0;
memcpy(result->ptr, mf2->ptr, mf2->size);
result->size = mf2->size;
} else if (!xscr2) {
result->ptr = xdl_malloc(mf1->size);
+ if (!result->ptr)
+ goto out;
+ status = 0;
memcpy(result->ptr, mf1->ptr, mf1->size);
result->size = mf1->size;
} else {
@@ -676,11 +727,13 @@ int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2,
&xe2, xscr2,
xmp, result);
}
+ out:
xdl_free_script(xscr1);
xdl_free_script(xscr2);
- xdl_free_env(&xe1);
xdl_free_env(&xe2);
+ free_xe1:
+ xdl_free_env(&xe1);
return status;
}
diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c
index c5d48e8..a2d8955 100644
--- a/xdiff/xpatience.c
+++ b/xdiff/xpatience.c
@@ -69,7 +69,6 @@ struct hashmap {
} *entries, *first, *last;
/* were common records found? */
unsigned long has_matches;
- mmfile_t *file1, *file2;
xdfenv_t *env;
xpparam_t const *xpp;
};
@@ -139,23 +138,17 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,
*
* It is assumed that env has been prepared using xdl_prepare().
*/
-static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,
- xpparam_t const *xpp, xdfenv_t *env,
+static int fill_hashmap(xpparam_t const *xpp, xdfenv_t *env,
struct hashmap *result,
int line1, int count1, int line2, int count2)
{
- result->file1 = file1;
- result->file2 = file2;
result->xpp = xpp;
result->env = env;
/* We know exactly how large we want the hash map */
result->alloc = count1 * 2;
- result->entries = (struct entry *)
- xdl_malloc(result->alloc * sizeof(struct entry));
- if (!result->entries)
+ if (!XDL_CALLOC_ARRAY(result->entries, result->alloc))
return -1;
- memset(result->entries, 0, result->alloc * sizeof(struct entry));
/* First, fill with entries from the first file */
while (count1--)
@@ -198,9 +191,9 @@ static int binary_search(struct entry **sequence, int longest,
* item per sequence length: the sequence with the smallest last
* element (in terms of line2).
*/
-static struct entry *find_longest_common_sequence(struct hashmap *map)
+static int find_longest_common_sequence(struct hashmap *map, struct entry **res)
{
- struct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *));
+ struct entry **sequence;
int longest = 0, i;
struct entry *entry;
@@ -211,6 +204,9 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)
*/
int anchor_i = -1;
+ if (!XDL_ALLOC_ARRAY(sequence, map->nr))
+ return -1;
+
for (entry = map->first; entry; entry = entry->next) {
if (!entry->line2 || entry->line2 == NON_UNIQUE)
continue;
@@ -230,8 +226,9 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)
/* No common unique lines were found */
if (!longest) {
+ *res = NULL;
xdl_free(sequence);
- return NULL;
+ return 0;
}
/* Iterate starting at the last element, adjusting the "next" members */
@@ -241,8 +238,9 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)
entry->previous->next = entry;
entry = entry->previous;
}
+ *res = entry;
xdl_free(sequence);
- return entry;
+ return 0;
}
static int match(struct hashmap *map, int line1, int line2)
@@ -252,8 +250,7 @@ static int match(struct hashmap *map, int line1, int line2)
return record1->ha == record2->ha;
}
-static int patience_diff(mmfile_t *file1, mmfile_t *file2,
- xpparam_t const *xpp, xdfenv_t *env,
+static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,
int line1, int count1, int line2, int count2);
static int walk_common_sequence(struct hashmap *map, struct entry *first,
@@ -284,8 +281,7 @@ static int walk_common_sequence(struct hashmap *map, struct entry *first,
/* Recurse */
if (next1 > line1 || next2 > line2) {
- if (patience_diff(map->file1, map->file2,
- map->xpp, map->env,
+ if (patience_diff(map->xpp, map->env,
line1, next1 - line1,
line2, next2 - line2))
return -1;
@@ -324,8 +320,7 @@ static int fall_back_to_classic_diff(struct hashmap *map,
*
* This function assumes that env was prepared with xdl_prepare_env().
*/
-static int patience_diff(mmfile_t *file1, mmfile_t *file2,
- xpparam_t const *xpp, xdfenv_t *env,
+static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,
int line1, int count1, int line2, int count2)
{
struct hashmap map;
@@ -344,7 +339,7 @@ static int patience_diff(mmfile_t *file1, mmfile_t *file2,
}
memset(&map, 0, sizeof(map));
- if (fill_hashmap(file1, file2, xpp, env, &map,
+ if (fill_hashmap(xpp, env, &map,
line1, count1, line2, count2))
return -1;
@@ -358,25 +353,21 @@ static int patience_diff(mmfile_t *file1, mmfile_t *file2,
return 0;
}
- first = find_longest_common_sequence(&map);
+ result = find_longest_common_sequence(&map, &first);
+ if (result)
+ goto out;
if (first)
result = walk_common_sequence(&map, first,
line1, count1, line2, count2);
else
result = fall_back_to_classic_diff(&map,
line1, count1, line2, count2);
-
+ out:
xdl_free(map.entries);
return result;
}
-int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2,
- xpparam_t const *xpp, xdfenv_t *env)
+int xdl_do_patience_diff(xpparam_t const *xpp, xdfenv_t *env)
{
- if (xdl_prepare_env(file1, file2, xpp, env) < 0)
- return -1;
-
- /* environment is cleaned up in xdl_diff() */
- return patience_diff(file1, file2, xpp, env,
- 1, env->xdf1.nrec, 1, env->xdf2.nrec);
+ return patience_diff(xpp, env, 1, env->xdf1.nrec, 1, env->xdf2.nrec);
}
diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index abeb8fb..c84549f 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c
@@ -78,15 +78,14 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
return -1;
}
- if (!(cf->rchash = (xdlclass_t **) xdl_malloc(cf->hsize * sizeof(xdlclass_t *)))) {
+ if (!XDL_CALLOC_ARRAY(cf->rchash, cf->hsize)) {
xdl_cha_free(&cf->ncha);
return -1;
}
- memset(cf->rchash, 0, cf->hsize * sizeof(xdlclass_t *));
cf->alloc = size;
- if (!(cf->rcrecs = (xdlclass_t **) xdl_malloc(cf->alloc * sizeof(xdlclass_t *)))) {
+ if (!XDL_ALLOC_ARRAY(cf->rcrecs, cf->alloc)) {
xdl_free(cf->rchash);
xdl_cha_free(&cf->ncha);
@@ -112,7 +111,6 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t
long hi;
char const *line;
xdlclass_t *rcrec;
- xdlclass_t **rcrecs;
line = rec->ptr;
hi = (long) XDL_HASHLONG(rec->ha, cf->hbits);
@@ -128,14 +126,8 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t
return -1;
}
rcrec->idx = cf->count++;
- if (cf->count > cf->alloc) {
- cf->alloc *= 2;
- if (!(rcrecs = (xdlclass_t **) xdl_realloc(cf->rcrecs, cf->alloc * sizeof(xdlclass_t *)))) {
-
+ if (XDL_ALLOC_GROW(cf->rcrecs, cf->count, cf->alloc))
return -1;
- }
- cf->rcrecs = rcrecs;
- }
cf->rcrecs[rcrec->idx] = rcrec;
rcrec->line = line;
rcrec->size = rec->size;
@@ -164,7 +156,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
unsigned long hav;
char const *blk, *cur, *top, *prev;
xrecord_t *crec;
- xrecord_t **recs, **rrecs;
+ xrecord_t **recs;
xrecord_t **rhash;
unsigned long *ha;
char *rchg;
@@ -178,51 +170,42 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0)
goto abort;
- if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *))))
+ if (!XDL_ALLOC_ARRAY(recs, narec))
goto abort;
- if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)
- hbits = hsize = 0;
- else {
- hbits = xdl_hashbits((unsigned int) narec);
- hsize = 1 << hbits;
- if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
- goto abort;
- memset(rhash, 0, hsize * sizeof(xrecord_t *));
- }
+ hbits = xdl_hashbits((unsigned int) narec);
+ hsize = 1 << hbits;
+ if (!XDL_CALLOC_ARRAY(rhash, hsize))
+ goto abort;
nrec = 0;
- if ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {
+ if ((cur = blk = xdl_mmfile_first(mf, &bsize))) {
for (top = blk + bsize; cur < top; ) {
prev = cur;
hav = xdl_hash_record(&cur, top, xpp->flags);
- if (nrec >= narec) {
- narec *= 2;
- if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *))))
- goto abort;
- recs = rrecs;
- }
+ if (XDL_ALLOC_GROW(recs, nrec + 1, narec))
+ goto abort;
if (!(crec = xdl_cha_alloc(&xdf->rcha)))
goto abort;
crec->ptr = prev;
crec->size = (long) (cur - prev);
crec->ha = hav;
recs[nrec++] = crec;
-
- if ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
- xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
+ if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
goto abort;
}
}
- if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char))))
+ if (!XDL_CALLOC_ARRAY(rchg, nrec + 2))
goto abort;
- memset(rchg, 0, (nrec + 2) * sizeof(char));
- if (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long))))
- goto abort;
- if (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long))))
- goto abort;
+ if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
+ (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) {
+ if (!XDL_ALLOC_ARRAY(rindex, nrec + 1))
+ goto abort;
+ if (!XDL_ALLOC_ARRAY(ha, nrec + 1))
+ goto abort;
+ }
xdf->nrec = nrec;
xdf->recs = recs;
@@ -279,8 +262,7 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
enl1 = xdl_guess_lines(mf1, sample) + 1;
enl2 = xdl_guess_lines(mf2, sample) + 1;
- if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF &&
- xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
+ if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
return -1;
if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
@@ -305,8 +287,7 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
return -1;
}
- if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)
- xdl_free_classifier(&cf);
+ xdl_free_classifier(&cf);
return 0;
}
@@ -388,11 +369,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
xdlclass_t *rcrec;
char *dis, *dis1, *dis2;
- if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {
-
+ if (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2))
return -1;
- }
- memset(dis, 0, xdf1->nrec + xdf2->nrec + 2);
dis1 = dis;
dis2 = dis1 + xdf1->nrec + 1;
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index cfa6e22..9e36f24 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -122,7 +122,7 @@ long xdl_guess_lines(mmfile_t *mf, long sample) {
long nl = 0, size, tsize = 0;
char const *data, *cur, *top;
- if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
+ if ((cur = data = xdl_mmfile_first(mf, &size))) {
for (top = data + size; nl < sample && cur < top; ) {
nl++;
if (!(cur = memchr(cur, '\n', top - cur)))
@@ -432,3 +432,20 @@ int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
return 0;
}
+
+void* xdl_alloc_grow_helper(void *p, long nr, long *alloc, size_t size)
+{
+ void *tmp = NULL;
+ size_t n = ((LONG_MAX - 16) / 2 >= *alloc) ? 2 * *alloc + 16 : LONG_MAX;
+ if (nr > n)
+ n = nr;
+ if (SIZE_MAX / size >= n)
+ tmp = xdl_realloc(p, n * size);
+ if (tmp) {
+ *alloc = n;
+ } else {
+ xdl_free(p);
+ *alloc = 0;
+ }
+ return tmp;
+}
diff --git a/xdiff/xutils.h b/xdiff/xutils.h
index fba7bae..fd0bba9 100644
--- a/xdiff/xutils.h
+++ b/xdiff/xutils.h
@@ -42,6 +42,7 @@ int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
int line1, int count1, int line2, int count2);
-
+/* Do not call this function, use XDL_ALLOC_GROW instead */
+void* xdl_alloc_grow_helper(void* p, long nr, long* alloc, size_t size);
#endif /* #if !defined(XUTILS_H) */
generated by cgit v0.10.2-6-g49f6 at 2024-04-27 20:47:47 (GMT)