summaryrefslogtreecommitdiff
path: root/lib/diffseq.h
diff options
context:
space:
mode:
authorStefan Monnier <monnier@iro.umontreal.ca>2022-09-25 16:15:16 -0400
committerStefan Monnier <monnier@iro.umontreal.ca>2022-09-25 16:15:16 -0400
commit650c20f1ca4e07591a727e1cfcc74b3363d15985 (patch)
tree85d11f6437cde22f410c25e0e5f71a3131ebd07d /lib/diffseq.h
parent8869332684c2302b5ba1ead4568bbc7ba1c0183e (diff)
parent4b85ae6a24380fb67a3315eaec9233f17a872473 (diff)
downloademacs-650c20f1ca4e07591a727e1cfcc74b3363d15985.tar.gz
emacs-650c20f1ca4e07591a727e1cfcc74b3363d15985.tar.bz2
emacs-650c20f1ca4e07591a727e1cfcc74b3363d15985.zip
Merge 'master' into noverlay
Diffstat (limited to 'lib/diffseq.h')
-rw-r--r--lib/diffseq.h136
1 files changed, 88 insertions, 48 deletions
diff --git a/lib/diffseq.h b/lib/diffseq.h
index b6f9f6f9d19..0f76ea1d5ad 100644
--- a/lib/diffseq.h
+++ b/lib/diffseq.h
@@ -1,11 +1,11 @@
/* Analyze differences between two vectors.
- Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2017 Free Software
+ Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2022 Free Software
Foundation, Inc.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 3 of the License, or
+ the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
@@ -28,13 +28,13 @@
The basic algorithm is described in:
"An O(ND) Difference Algorithm and its Variations", Eugene W. Myers,
Algorithmica Vol. 1, 1986, pp. 251-266,
- <http://dx.doi.org/10.1007/BF01840446>.
+ <https://doi.org/10.1007/BF01840446>.
See especially section 4.2, which describes the variation used below.
The basic algorithm was independently discovered as described in:
"Algorithms for Approximate String Matching", Esko Ukkonen,
Information and Control Vol. 64, 1985, pp. 100-118,
- <http://dx.doi.org/10.1016/S0019-9958(85)80046-2>.
+ <https://doi.org/10.1016/S0019-9958(85)80046-2>.
Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE
heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
@@ -51,10 +51,14 @@
EXTRA_CONTEXT_FIELDS Declarations of fields for 'struct context'.
NOTE_DELETE(ctxt, xoff) Record the removal of the object xvec[xoff].
NOTE_INSERT(ctxt, yoff) Record the insertion of the object yvec[yoff].
+ NOTE_ORDERED (Optional) A boolean expression saying that
+ NOTE_DELETE and NOTE_INSERT calls must be
+ issued in offset order.
EARLY_ABORT(ctxt) (Optional) A boolean expression that triggers an
early abort of the computation.
USE_HEURISTIC (Optional) Define if you want to support the
heuristic for large vectors.
+
It is also possible to use this file with abstract arrays. In this case,
xvec and yvec are not represented in memory. They only exist conceptually.
In this case, the list of defines above is amended as follows:
@@ -63,6 +67,7 @@
XVECREF_YVECREF_EQUAL(ctxt, xoff, yoff)
A three-argument macro: References xvec[xoff] and
yvec[yoff] and tests these elements for equality.
+
Before including this file, you also need to include:
#include <limits.h>
#include <stdbool.h>
@@ -78,6 +83,10 @@
# define EARLY_ABORT(ctxt) false
#endif
+#ifndef NOTE_ORDERED
+# define NOTE_ORDERED false
+#endif
+
/* Use this to suppress gcc's "...may be used before initialized" warnings.
Beware: The Code argument must not contain commas. */
#ifndef IF_LINT
@@ -88,15 +97,6 @@
# endif
#endif
-/* As above, but when Code must contain one comma. */
-#ifndef IF_LINT2
-# if defined GCC_LINT || defined lint
-# define IF_LINT2(Code1, Code2) Code1, Code2
-# else
-# define IF_LINT2(Code1, Code2) /* empty */
-# endif
-#endif
-
/*
* Context of comparison operation.
*/
@@ -468,49 +468,89 @@ compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
#define XREF_YREF_EQUAL(x,y) XVECREF_YVECREF_EQUAL (ctxt, x, y)
#endif
- /* Slide down the bottom initial diagonal. */
- while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xoff, yoff))
+ while (true)
{
- xoff++;
- yoff++;
- }
+ /* Slide down the bottom initial diagonal. */
+ while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xoff, yoff))
+ {
+ xoff++;
+ yoff++;
+ }
- /* Slide up the top initial diagonal. */
- while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xlim - 1, ylim - 1))
- {
- xlim--;
- ylim--;
- }
+ /* Slide up the top initial diagonal. */
+ while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xlim - 1, ylim - 1))
+ {
+ xlim--;
+ ylim--;
+ }
- /* Handle simple cases. */
- if (xoff == xlim)
- while (yoff < ylim)
- {
- NOTE_INSERT (ctxt, yoff);
- if (EARLY_ABORT (ctxt))
- return true;
- yoff++;
- }
- else if (yoff == ylim)
- while (xoff < xlim)
- {
- NOTE_DELETE (ctxt, xoff);
- if (EARLY_ABORT (ctxt))
- return true;
- xoff++;
- }
- else
- {
- struct partition part IF_LINT2 (= { .xmid = 0, .ymid = 0 });
+ /* Handle simple cases. */
+ if (xoff == xlim)
+ {
+ while (yoff < ylim)
+ {
+ NOTE_INSERT (ctxt, yoff);
+ if (EARLY_ABORT (ctxt))
+ return true;
+ yoff++;
+ }
+ break;
+ }
+ if (yoff == ylim)
+ {
+ while (xoff < xlim)
+ {
+ NOTE_DELETE (ctxt, xoff);
+ if (EARLY_ABORT (ctxt))
+ return true;
+ xoff++;
+ }
+ break;
+ }
+
+ struct partition part;
/* Find a point of correspondence in the middle of the vectors. */
diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
/* Use the partitions to split this problem into subproblems. */
- if (compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt))
- return true;
- if (compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt))
- return true;
+ OFFSET xoff1, xlim1, yoff1, ylim1, xoff2, xlim2, yoff2, ylim2;
+ bool find_minimal1, find_minimal2;
+ if (!NOTE_ORDERED
+ && ((xlim + ylim) - (part.xmid + part.ymid)
+ < (part.xmid + part.ymid) - (xoff + yoff)))
+ {
+ /* The second problem is smaller and the caller doesn't
+ care about order, so do the second problem first to
+ lessen recursion. */
+ xoff1 = part.xmid; xlim1 = xlim;
+ yoff1 = part.ymid; ylim1 = ylim;
+ find_minimal1 = part.hi_minimal;
+
+ xoff2 = xoff; xlim2 = part.xmid;
+ yoff2 = yoff; ylim2 = part.ymid;
+ find_minimal2 = part.lo_minimal;
+ }
+ else
+ {
+ xoff1 = xoff; xlim1 = part.xmid;
+ yoff1 = yoff; ylim1 = part.ymid;
+ find_minimal1 = part.lo_minimal;
+
+ xoff2 = part.xmid; xlim2 = xlim;
+ yoff2 = part.ymid; ylim2 = ylim;
+ find_minimal2 = part.hi_minimal;
+ }
+
+ /* Recurse to do one subproblem. */
+ bool early = compareseq (xoff1, xlim1, yoff1, ylim1, find_minimal1, ctxt);
+ if (early)
+ return early;
+
+ /* Iterate to do the other subproblem. */
+ xoff = xoff2; xlim = xlim2;
+ yoff = yoff2; ylim = ylim2;
+ find_minimal = find_minimal2;
}
return false;
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-15 11:54:32 +0000