499 lines
14 KiB
C
499 lines
14 KiB
C
|
/*
|
||
|
|
* Copyright © 2003 Davide Libenzi
|
||
|
|
* 2018 Benjamin Otte
|
||
|
|
*
|
||
|
|
* This library is free software; you can redistribute it and/or
|
||
|
|
* modify it under the terms of the GNU Lesser General Public
|
||
|
|
* License as published by the Free Software Foundation; either
|
||
|
|
* version 2.1 of the License, or (at your option) any later version.
|
||
|
|
*
|
||
|
|
* This library is distributed in the hope that it will be useful,
|
||
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
||
|
|
* Lesser General Public License for more details.
|
||
|
|
*
|
||
|
|
* You should have received a copy of the GNU Lesser General Public
|
||
|
|
* License along with this library. If not, see <http://www.gnu.org/licenses/>.
|
||
|
|
*
|
||
|
|
* Authors: Davide Libenzi <davidel@xmailserver.org>
|
||
|
|
* Benjamin Otte <otte@gnome.org>
|
||
|
|
*/
|
||
|
|
|
||
|
|
#include "config.h"
|
||
|
|
|
||
|
|
#include "gskdiffprivate.h"
|
||
|
|
|
||
|
|
|
||
|
|
#define XDL_MAX_COST_MIN 256
|
||
|
|
#define XDL_HEUR_MIN_COST 256
|
||
|
|
#define XDL_LINE_MAX G_MAXSSIZE
|
||
|
|
#define XDL_SNAKE_CNT 20
|
||
|
|
#define XDL_K_HEUR 4
|
||
|
|
#define MAXCOST 20
|
||
|
|
|
||
|
|
struct _GskDiffSettings {
|
||
|
|
GCompareDataFunc compare_func;
|
||
|
|
GskKeepFunc keep_func;
|
||
|
|
GskDeleteFunc delete_func;
|
||
|
|
GskInsertFunc insert_func;
|
||
|
|
|
||
|
|
guint allow_abort : 1;
|
||
|
|
};
|
||
|
|
|
||
|
|
typedef struct _SplitResult {
|
||
|
|
long i1, i2;
|
||
|
|
int min_lo, min_hi;
|
||
|
|
} SplitResult;
|
||
|
|
|
||
|
|
GskDiffSettings *
|
||
|
|
gsk_diff_settings_new (GCompareDataFunc compare_func,
|
||
|
|
GskKeepFunc keep_func,
|
||
|
|
GskDeleteFunc delete_func,
|
||
|
|
GskInsertFunc insert_func)
|
||
|
|
{
|
||
|
|
GskDiffSettings *settings;
|
||
|
|
|
||
|
|
settings = g_new0 (GskDiffSettings, 1);
|
||
|
|
|
||
|
|
settings->compare_func = compare_func;
|
||
|
|
settings->keep_func = keep_func;
|
||
|
|
settings->delete_func = delete_func;
|
||
|
|
settings->insert_func = insert_func;
|
||
|
|
|
||
|
|
return settings;
|
||
|
|
}
|
||
|
|
|
||
|
|
void
|
||
|
|
gsk_diff_settings_set_allow_abort (GskDiffSettings *settings,
|
||
|
|
gboolean allow_abort)
|
||
|
|
{
|
||
|
|
settings->allow_abort = allow_abort;
|
||
|
|
}
|
||
|
|
|
||
|
|
void
|
||
|
|
gsk_diff_settings_free (GskDiffSettings *settings)
|
||
|
|
{
|
||
|
|
g_free (settings);
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers.
|
||
|
|
* Basically considers a "box" (off1, off2, lim1, lim2) and scan from both
|
||
|
|
* the forward diagonal starting from (off1, off2) and the backward diagonal
|
||
|
|
* starting from (lim1, lim2). If the K values on the same diagonal crosses
|
||
|
|
* returns the furthest point of reach. We might end up having to expensive
|
||
|
|
* cases using this algorithm is full, so a little bit of heuristic is needed
|
||
|
|
* to cut the search and to return a suboptimal point.
|
||
|
|
*/
|
||
|
|
static GskDiffResult
|
||
|
|
split (gconstpointer *elem1,
|
||
|
|
gssize off1,
|
||
|
|
gssize lim1,
|
||
|
|
gconstpointer *elem2,
|
||
|
|
gssize off2,
|
||
|
|
gssize lim2,
|
||
|
|
gssize *kvdf,
|
||
|
|
gssize *kvdb,
|
||
|
|
gboolean need_min,
|
||
|
|
const GskDiffSettings *settings,
|
||
|
|
gpointer data,
|
||
|
|
SplitResult *spl)
|
||
|
|
{
|
||
|
|
gssize dmin = off1 - lim2, dmax = lim1 - off2;
|
||
|
|
gssize fmid = off1 - off2, bmid = lim1 - lim2;
|
||
|
|
gboolean odd = (fmid - bmid) & 1;
|
||
|
|
gssize fmin = fmid, fmax = fmid;
|
||
|
|
gssize bmin = bmid, bmax = bmid;
|
||
|
|
gssize ec, d, i1, i2, prev1, best, dd, v, k;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Set initial diagonal values for both forward and backward path.
|
||
|
|
*/
|
||
|
|
kvdf[fmid] = off1;
|
||
|
|
kvdb[bmid] = lim1;
|
||
|
|
|
||
|
|
for (ec = 1;; ec++)
|
||
|
|
{
|
||
|
|
gboolean got_snake = FALSE;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* We need to extent the diagonal "domain" by one. If the next
|
||
|
|
* values exits the box boundaries we need to change it in the
|
||
|
|
* opposite direction because (max - min) must be a power of two.
|
||
|
|
* Also we initialize the external K value to -1 so that we can
|
||
|
|
* avoid extra conditions check inside the core loop.
|
||
|
|
*/
|
||
|
|
if (fmin > dmin)
|
||
|
|
kvdf[--fmin - 1] = -1;
|
||
|
|
else
|
||
|
|
++fmin;
|
||
|
|
if (fmax < dmax)
|
||
|
|
kvdf[++fmax + 1] = -1;
|
||
|
|
else
|
||
|
|
--fmax;
|
||
|
|
|
||
|
|
for (d = fmax; d >= fmin; d -= 2)
|
||
|
|
{
|
||
|
|
if (kvdf[d - 1] >= kvdf[d + 1])
|
||
|
|
i1 = kvdf[d - 1] + 1;
|
||
|
|
else
|
||
|
|
i1 = kvdf[d + 1];
|
||
|
|
prev1 = i1;
|
||
|
|
i2 = i1 - d;
|
||
|
|
for (; i1 < lim1 && i2 < lim2; i1++, i2++)
|
||
|
|
{
|
||
|
|
if (settings->compare_func (elem1[i1], elem2[i2], data) != 0)
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
if (i1 - prev1 > XDL_SNAKE_CNT)
|
||
|
|
got_snake = TRUE;
|
||
|
|
kvdf[d] = i1;
|
||
|
|
if (odd && bmin <= d && d <= bmax && kvdb[d] <= i1)
|
||
|
|
{
|
||
|
|
spl->i1 = i1;
|
||
|
|
spl->i2 = i2;
|
||
|
|
spl->min_lo = spl->min_hi = 1;
|
||
|
|
return GSK_DIFF_OK;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* We need to extent the diagonal "domain" by one. If the next
|
||
|
|
* values exits the box boundaries we need to change it in the
|
||
|
|
* opposite direction because (max - min) must be a power of two.
|
||
|
|
* Also we initialize the external K value to -1 so that we can
|
||
|
|
* avoid extra conditions check inside the core loop.
|
||
|
|
*/
|
||
|
|
if (bmin > dmin)
|
||
|
|
kvdb[--bmin - 1] = XDL_LINE_MAX;
|
||
|
|
else
|
||
|
|
++bmin;
|
||
|
|
if (bmax < dmax)
|
||
|
|
kvdb[++bmax + 1] = XDL_LINE_MAX;
|
||
|
|
else
|
||
|
|
--bmax;
|
||
|
|
|
||
|
|
for (d = bmax; d >= bmin; d -= 2)
|
||
|
|
{
|
||
|
|
if (kvdb[d - 1] < kvdb[d + 1])
|
||
|
|
i1 = kvdb[d - 1];
|
||
|
|
else
|
||
|
|
i1 = kvdb[d + 1] - 1;
|
||
|
|
prev1 = i1;
|
||
|
|
i2 = i1 - d;
|
||
|
|
for (; i1 > off1 && i2 > off2; i1--, i2--)
|
||
|
|
{
|
||
|
|
if (settings->compare_func (elem1[i1 - 1], elem2[i2 - 1], data) != 0)
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
if (prev1 - i1 > XDL_SNAKE_CNT)
|
||
|
|
got_snake = TRUE;
|
||
|
|
kvdb[d] = i1;
|
||
|
|
if (!odd && fmin <= d && d <= fmax && i1 <= kvdf[d])
|
||
|
|
{
|
||
|
|
spl->i1 = i1;
|
||
|
|
spl->i2 = i2;
|
||
|
|
spl->min_lo = spl->min_hi = 1;
|
||
|
|
return GSK_DIFF_OK;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
if (need_min)
|
||
|
|
continue;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* If the edit cost is above the heuristic trigger and if
|
||
|
|
* we got a good snake, we sample current diagonals to see
|
||
|
|
* if some of them have reached an "interesting" path. Our
|
||
|
|
* measure is a function of the distance from the diagonal
|
||
|
|
* corner (i1 + i2) penalized with the distance from the
|
||
|
|
* mid diagonal itself. If this value is above the current
|
||
|
|
* edit cost times a magic factor (XDL_K_HEUR) we consider
|
||
|
|
* it interesting.
|
||
|
|
*/
|
||
|
|
if (got_snake && ec > XDL_HEUR_MIN_COST)
|
||
|
|
{
|
||
|
|
for (best = 0, d = fmax; d >= fmin; d -= 2)
|
||
|
|
{
|
||
|
|
dd = d > fmid ? d - fmid: fmid - d;
|
||
|
|
i1 = kvdf[d];
|
||
|
|
i2 = i1 - d;
|
||
|
|
v = (i1 - off1) + (i2 - off2) - dd;
|
||
|
|
|
||
|
|
if (v > XDL_K_HEUR * ec && v > best &&
|
||
|
|
off1 + XDL_SNAKE_CNT <= i1 && i1 < lim1 &&
|
||
|
|
off2 + XDL_SNAKE_CNT <= i2 && i2 < lim2)
|
||
|
|
{
|
||
|
|
for (k = 1; ; k++)
|
||
|
|
{
|
||
|
|
if (settings->compare_func (elem1[i1 - k], elem2[i2 - k], data) != 0)
|
||
|
|
break;
|
||
|
|
if (k == XDL_SNAKE_CNT)
|
||
|
|
{
|
||
|
|
best = v;
|
||
|
|
spl->i1 = i1;
|
||
|
|
spl->i2 = i2;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (best > 0)
|
||
|
|
{
|
||
|
|
spl->min_lo = 1;
|
||
|
|
spl->min_hi = 0;
|
||
|
|
return GSK_DIFF_OK;
|
||
|
|
}
|
||
|
|
|
||
|
|
for (best = 0, d = bmax; d >= bmin; d -= 2)
|
||
|
|
{
|
||
|
|
dd = d > bmid ? d - bmid: bmid - d;
|
||
|
|
i1 = kvdb[d];
|
||
|
|
i2 = i1 - d;
|
||
|
|
v = (lim1 - i1) + (lim2 - i2) - dd;
|
||
|
|
|
||
|
|
if (v > XDL_K_HEUR * ec && v > best &&
|
||
|
|
off1 < i1 && i1 <= lim1 - XDL_SNAKE_CNT &&
|
||
|
|
off2 < i2 && i2 <= lim2 - XDL_SNAKE_CNT)
|
||
|
|
{
|
||
|
|
for (k = 0; ; k++)
|
||
|
|
{
|
||
|
|
if (settings->compare_func (elem1[i1 + k], elem2[i2 + k], data) != 0)
|
||
|
|
break;
|
||
|
|
|
||
|
|
if (k == XDL_SNAKE_CNT - 1)
|
||
|
|
{
|
||
|
|
best = v;
|
||
|
|
spl->i1 = i1;
|
||
|
|
spl->i2 = i2;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (best > 0)
|
||
|
|
{
|
||
|
|
spl->min_lo = 0;
|
||
|
|
spl->min_hi = 1;
|
||
|
|
return GSK_DIFF_OK;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Enough is enough. We spent too much time here and now we collect
|
||
|
|
* the furthest reaching path using the (i1 + i2) measure.
|
||
|
|
*/
|
||
|
|
if (ec >= MAXCOST)
|
||
|
|
{
|
||
|
|
gssize fbest, fbest1, bbest, bbest1;
|
||
|
|
|
||
|
|
if (settings->allow_abort)
|
||
|
|
return GSK_DIFF_ABORTED;
|
||
|
|
|
||
|
|
fbest = fbest1 = -1;
|
||
|
|
for (d = fmax; d >= fmin; d -= 2)
|
||
|
|
{
|
||
|
|
i1 = MIN (kvdf[d], lim1);
|
||
|
|
i2 = i1 - d;
|
||
|
|
if (lim2 < i2)
|
||
|
|
i1 = lim2 + d, i2 = lim2;
|
||
|
|
if (fbest < i1 + i2)
|
||
|
|
{
|
||
|
|
fbest = i1 + i2;
|
||
|
|
fbest1 = i1;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
bbest = bbest1 = XDL_LINE_MAX;
|
||
|
|
for (d = bmax; d >= bmin; d -= 2)
|
||
|
|
{
|
||
|
|
i1 = MAX (off1, kvdb[d]);
|
||
|
|
i2 = i1 - d;
|
||
|
|
if (i2 < off2)
|
||
|
|
i1 = off2 + d, i2 = off2;
|
||
|
|
if (i1 + i2 < bbest)
|
||
|
|
{
|
||
|
|
bbest = i1 + i2;
|
||
|
|
bbest1 = i1;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
if ((lim1 + lim2) - bbest < fbest - (off1 + off2))
|
||
|
|
{
|
||
|
|
spl->i1 = fbest1;
|
||
|
|
spl->i2 = fbest - fbest1;
|
||
|
|
spl->min_lo = 1;
|
||
|
|
spl->min_hi = 0;
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
spl->i1 = bbest1;
|
||
|
|
spl->i2 = bbest - bbest1;
|
||
|
|
spl->min_lo = 0;
|
||
|
|
spl->min_hi = 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
return GSK_DIFF_OK;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Rule: "Divide et Impera". Recursively split the box in sub-boxes by calling
|
||
|
|
* the box splitting function. Note that the real job (marking changed lines)
|
||
|
|
* is done in the two boundary reaching checks.
|
||
|
|
*/
|
||
|
|
static GskDiffResult
|
||
|
|
compare (gconstpointer *elem1,
|
||
|
|
gssize off1,
|
||
|
|
gssize lim1,
|
||
|
|
gconstpointer *elem2,
|
||
|
|
gssize off2,
|
||
|
|
gssize lim2,
|
||
|
|
gssize *kvdf,
|
||
|
|
gssize *kvdb,
|
||
|
|
gboolean need_min,
|
||
|
|
const GskDiffSettings *settings,
|
||
|
|
gpointer data)
|
||
|
|
{
|
||
|
|
GskDiffResult res;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Shrink the box by walking through each diagonal snake (SW and NE).
|
||
|
|
*/
|
||
|
|
for (; off1 < lim1 && off2 < lim2; off1++, off2++)
|
||
|
|
{
|
||
|
|
if (settings->compare_func (elem1[off1], elem2[off2], data) != 0)
|
||
|
|
break;
|
||
|
|
|
||
|
|
res = settings->keep_func (elem1[off1], elem2[off2], data);
|
||
|
|
if (res != GSK_DIFF_OK)
|
||
|
|
return res;
|
||
|
|
}
|
||
|
|
|
||
|
|
for (; off1 < lim1 && off2 < lim2; lim1--, lim2--)
|
||
|
|
{
|
||
|
|
if (settings->compare_func (elem1[lim1 - 1], elem2[lim2 - 1], data) != 0)
|
||
|
|
break;
|
||
|
|
|
||
|
|
res = settings->keep_func (elem1[lim1 - 1], elem2[lim2 - 1], data);
|
||
|
|
if (res != GSK_DIFF_OK)
|
||
|
|
return res;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* If one dimension is empty, then all records on the other one must
|
||
|
|
* be obviously changed.
|
||
|
|
*/
|
||
|
|
if (off1 == lim1)
|
||
|
|
{
|
||
|
|
for (; off2 < lim2; off2++)
|
||
|
|
{
|
||
|
|
res = settings->insert_func (elem2[off2], off2, data);
|
||
|
|
if (res != GSK_DIFF_OK)
|
||
|
|
return res;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
else if (off2 == lim2)
|
||
|
|
{
|
||
|
|
for (; off1 < lim1; off1++)
|
||
|
|
{
|
||
|
|
res = settings->delete_func (elem1[off1], off1, data);
|
||
|
|
if (res != GSK_DIFF_OK)
|
||
|
|
return res;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
SplitResult spl = { 0, };
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Divide ...
|
||
|
|
*/
|
||
|
|
res = split (elem1, off1, lim1,
|
||
|
|
elem2, off2, lim2,
|
||
|
|
kvdf, kvdb, need_min,
|
||
|
|
settings, data,
|
||
|
|
&spl);
|
||
|
|
if (res != GSK_DIFF_OK)
|
||
|
|
return res;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* ... et Impera.
|
||
|
|
*/
|
||
|
|
res = compare (elem1, off1, spl.i1,
|
||
|
|
elem2, off2, spl.i2,
|
||
|
|
kvdf, kvdb, spl.min_lo,
|
||
|
|
settings, data);
|
||
|
|
if (res != GSK_DIFF_OK)
|
||
|
|
return res;
|
||
|
|
res = compare (elem1, spl.i1, lim1,
|
||
|
|
elem2, spl.i2, lim2,
|
||
|
|
kvdf, kvdb, spl.min_hi,
|
||
|
|
settings, data);
|
||
|
|
if (res != GSK_DIFF_OK)
|
||
|
|
return res;
|
||
|
|
}
|
||
|
|
|
||
|
|
return GSK_DIFF_OK;
|
||
|
|
}
|
||
|
|
|
||
|
|
#if 0
|
||
|
|
ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
|
||
|
|
if (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) {
|
||
|
|
|
||
|
|
xdl_free_env(xe);
|
||
|
|
return -1;
|
||
|
|
}
|
||
|
|
kvdf = kvd;
|
||
|
|
kvdb = kvdf + ndiags;
|
||
|
|
kvdf += xe->xdf2.nreff + 1;
|
||
|
|
kvdb += xe->xdf2.nreff + 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;
|
||
|
|
xenv.heur_min = XDL_HEUR_MIN_COST;
|
||
|
|
|
||
|
|
dd1.nrec = xe->xdf1.nreff;
|
||
|
|
dd1.ha = xe->xdf1.ha;
|
||
|
|
dd1.rchg = xe->xdf1.rchg;
|
||
|
|
dd1.rindex = xe->xdf1.rindex;
|
||
|
|
dd2.nrec = xe->xdf2.nreff;
|
||
|
|
dd2.ha = xe->xdf2.ha;
|
||
|
|
dd2.rchg = xe->xdf2.rchg;
|
||
|
|
dd2.rindex = xe->xdf2.rindex;
|
||
|
|
#endif
|
||
|
|
|
||
|
|
GskDiffResult
|
||
|
|
gsk_diff (gconstpointer *elem1,
|
||
|
|
gsize n1,
|
||
|
|
gconstpointer *elem2,
|
||
|
|
gsize n2,
|
||
|
|
const GskDiffSettings *settings,
|
||
|
|
gpointer data)
|
||
|
|
{
|
||
|
|
gsize ndiags;
|
||
|
|
gssize *kvd, *kvdf, *kvdb;
|
||
|
|
GskDiffResult res;
|
||
|
|
|
||
|
|
ndiags = n1 + n2 + 3;
|
||
|
|
|
||
|
|
kvd = g_new (gssize, 2 * ndiags + 2);
|
||
|
|
kvdf = kvd;
|
||
|
|
kvdb = kvd + ndiags;
|
||
|
|
kvdf += n2 + 1;
|
||
|
|
kvdb += n2 + 1;
|
||
|
|
|
||
|
|
res = compare (elem1, 0, n1,
|
||
|
|
elem2, 0, n2,
|
||
|
|
kvdf, kvdb, FALSE,
|
||
|
|
settings, data);
|
||
|
|
|
||
|
|
g_free (kvd);
|
||
|
|
|
||
|
|
return res;
|
||
|
|
}
|
||
|
|
|