gnulib: lib/diffseq.h annotate

annotate lib/diffseq.h @ 7451:6c5a4b5959bb diff-merge

Actually use the EQUAL macro.

author	Bruno Haible <bruno@clisp.org>
date	Thu, 21 Dec 2006 20:09:09 +0000
parents	050f00681985
children

rev	line source
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	1 /* Analyze differences between two vectors.
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	2 Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006 Free Software Foundation, Inc.
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	3
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	4 This program is free software; you can redistribute it and/or modify
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	5 it under the terms of the GNU General Public License as published by
7437 e70f23471c45 Fix FSF address. Bruno Haible <bruno@clisp.org> parents: 7436 diff changeset	6 the Free Software Foundation; either version 2, or (at your option)
e70f23471c45 Fix FSF address. Bruno Haible <bruno@clisp.org> parents: 7436 diff changeset	7 any later version.
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	8
7437 e70f23471c45 Fix FSF address. Bruno Haible <bruno@clisp.org> parents: 7436 diff changeset	9 This program is distributed in the hope that it will be useful,
e70f23471c45 Fix FSF address. Bruno Haible <bruno@clisp.org> parents: 7436 diff changeset	10 but WITHOUT ANY WARRANTY; without even the implied warranty of
e70f23471c45 Fix FSF address. Bruno Haible <bruno@clisp.org> parents: 7436 diff changeset	11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
e70f23471c45 Fix FSF address. Bruno Haible <bruno@clisp.org> parents: 7436 diff changeset	12 GNU General Public License for more details.
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	13
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	14 You should have received a copy of the GNU General Public License
7437 e70f23471c45 Fix FSF address. Bruno Haible <bruno@clisp.org> parents: 7436 diff changeset	15 along with this program; if not, write to the Free Software Foundation,
e70f23471c45 Fix FSF address. Bruno Haible <bruno@clisp.org> parents: 7436 diff changeset	16 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	17
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	18
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	19 /* The basic idea is to consider two vectors as similar if, when
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	20 transforming the first vector into the second vector through a
7448 050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	21 sequence of edits (inserts and deletes of one element each),
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	22 this sequence is short - or equivalently, if the ordered list
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	23 of elements that are untouched by these edits is long. For a
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	24 good introduction to the subject, read about the "Levenshtein
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	25 distance" in Wikipedia.
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	26
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	27 The basic algorithm is described in:
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	28 "An O(ND) Difference Algorithm and its Variations", Eugene Myers,
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	29 Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	30 see especially section 4.2, which describes the variation used below.
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	31
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	32 The basic algorithm was independently discovered as described in:
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	33 "Algorithms for Approximate String Matching", E. Ukkonen,
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	34 Information and Control Vol. 64, 1985, pp. 100-118.
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	35
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	36 Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	37 heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	38 at the price of producing suboptimal output for large inputs with
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	39 many differences. */
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	40
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	41 /* Before including this file, you need to define:
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	42 ELEMENT The element type of the vectors being compared.
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	43 EQUAL A two-argument macro that tests two elements for
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	44 equality.
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	45 OFFSET A signed integer type sufficient to hold the
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	46 difference between two indices. Usually
7434 2ee32ecdec9d Make the heuristic dependent on USE_HEURISTIC and the variable 'heuristic'. Bruno Haible <bruno@clisp.org> parents: 7433 diff changeset	47 something like ssize_t.
7448 050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	48 EXTRA_CONTEXT_FIELDS Declarations of fields for 'struct context'.
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	49 NOTE_DELETE(ctxt, xoff) Record the removal of the object xvec[xoff].
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	50 NOTE_INSERT(ctxt, yoff) Record the insertion of the object yvec[yoff].
7434 2ee32ecdec9d Make the heuristic dependent on USE_HEURISTIC and the variable 'heuristic'. Bruno Haible <bruno@clisp.org> parents: 7433 diff changeset	51 USE_HEURISTIC (Optional) Define if you want to support the
2ee32ecdec9d Make the heuristic dependent on USE_HEURISTIC and the variable 'heuristic'. Bruno Haible <bruno@clisp.org> parents: 7433 diff changeset	52 heuristic for large vectors. */
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	53
7432 3312c900de96 Make generic: introduce OFFSET_MAX. Bruno Haible <bruno@clisp.org> parents: 7431 diff changeset	54 /* Maximum value of type OFFSET. */
3312c900de96 Make generic: introduce OFFSET_MAX. Bruno Haible <bruno@clisp.org> parents: 7431 diff changeset	55 #define OFFSET_MAX \
7445 6636813345ea Fix mistakes in previous revisions. Bruno Haible <bruno@clisp.org> parents: 7444 diff changeset	56 ((((OFFSET)1 << (sizeof (OFFSET) * CHAR_BIT - 2)) - 1) * 2 + 1)
7432 3312c900de96 Make generic: introduce OFFSET_MAX. Bruno Haible <bruno@clisp.org> parents: 7431 diff changeset	57
7440 5b42c8de7c5f Remove an IF_LINT that is probably not necessary any more. Bruno Haible <bruno@clisp.org> parents: 7439 diff changeset	58 /* Use this to suppress gcc's `...may be used before initialized' warnings. */
5b42c8de7c5f Remove an IF_LINT that is probably not necessary any more. Bruno Haible <bruno@clisp.org> parents: 7439 diff changeset	59 #ifndef IF_LINT
5b42c8de7c5f Remove an IF_LINT that is probably not necessary any more. Bruno Haible <bruno@clisp.org> parents: 7439 diff changeset	60 # ifdef lint
5b42c8de7c5f Remove an IF_LINT that is probably not necessary any more. Bruno Haible <bruno@clisp.org> parents: 7439 diff changeset	61 # define IF_LINT(Code) Code
5b42c8de7c5f Remove an IF_LINT that is probably not necessary any more. Bruno Haible <bruno@clisp.org> parents: 7439 diff changeset	62 # else
5b42c8de7c5f Remove an IF_LINT that is probably not necessary any more. Bruno Haible <bruno@clisp.org> parents: 7439 diff changeset	63 # define IF_LINT(Code) /* empty */
5b42c8de7c5f Remove an IF_LINT that is probably not necessary any more. Bruno Haible <bruno@clisp.org> parents: 7439 diff changeset	64 # endif
5b42c8de7c5f Remove an IF_LINT that is probably not necessary any more. Bruno Haible <bruno@clisp.org> parents: 7439 diff changeset	65 #endif
5b42c8de7c5f Remove an IF_LINT that is probably not necessary any more. Bruno Haible <bruno@clisp.org> parents: 7439 diff changeset	66
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	67 /*
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	68 * Context of comparison operation.
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	69 */
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	70 struct context
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	71 {
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	72 /* Vectors being compared. */
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	73 const ELEMENT *xvec;
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	74 const ELEMENT *yvec;
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	75
7448 050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	76 /* Extra fields. */
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	77 EXTRA_CONTEXT_FIELDS
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	78
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	79 /* Vector, indexed by diagonal, containing 1 + the X coordinate of the point
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	80 furthest along the given diagonal in the forward search of the edit
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	81 matrix. */
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	82 OFFSET *fdiag;
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	83
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	84 /* Vector, indexed by diagonal, containing the X coordinate of the point
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	85 furthest along the given diagonal in the backward search of the edit
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	86 matrix. */
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	87 OFFSET *bdiag;
7434 2ee32ecdec9d Make the heuristic dependent on USE_HEURISTIC and the variable 'heuristic'. Bruno Haible <bruno@clisp.org> parents: 7433 diff changeset	88
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	89 #ifdef USE_HEURISTIC
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	90 /* This corresponds to the diff -H flag. With this heuristic, for
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	91 vectors with a constant small density of changes, the algorithm is
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	92 linear in the vectors size. */
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	93 int heuristic;
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	94 #endif
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	95
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	96 /* Edit scripts longer than this are too expensive to compute. */
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	97 OFFSET too_expensive;
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	98
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	99 /* Snakes bigger than this are considered `big'. */
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	100 #define SNAKE_LIMIT 20
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	101 };
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	102
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	103 struct partition
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	104 {
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	105 /* Midpoints of this partition. */
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	106 OFFSET xmid;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	107 OFFSET ymid;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	108
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	109 /* True if low half will be analyzed minimally. */
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	110 bool lo_minimal;
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	111
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	112 /* Likewise for high half. */
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	113 bool hi_minimal;
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	114 };
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	115
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	116 /* Find the midpoint of the shortest edit script for a specified portion
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	117 of the two vectors.
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	118
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	119 Scan from the beginnings of the vectors, and simultaneously from the ends,
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	120 doing a breadth-first search through the space of edit-sequence.
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	121 When the two searches meet, we have found the midpoint of the shortest
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	122 edit sequence.
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	123
7430 f53f84143fe3 Update comments for use of 'bool'. Bruno Haible <bruno@clisp.org> parents: 7428 diff changeset	124 If FIND_MINIMAL is true, find the minimal edit script regardless
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	125 of expense. Otherwise, if the search is too expensive, use
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	126 heuristics to stop the search and report a suboptimal answer.
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	127
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	128 Set PART->(xmid,ymid) to the midpoint (XMID,YMID). The diagonal number
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	129 XMID - YMID equals the number of inserted elements minus the number
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	130 of deleted elements (counting only elements before the midpoint).
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	131
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	132 Set PART->lo_minimal to true iff the minimal edit script for the
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	133 left half of the partition is known; similarly for PART->hi_minimal.
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	134
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	135 This function assumes that the first elements of the specified portions
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	136 of the two vectors do not match, and likewise that the last elements do not
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	137 match. The caller must trim matching elements from the beginning and end
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	138 of the portions it is going to specify.
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	139
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	140 If we return the "wrong" partitions, the worst this can do is cause
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	141 suboptimal diff output. It cannot cause incorrect diff output. */
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	142
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	143 static void
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	144 diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	145 struct partition part, struct context ctxt)
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	146 {
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	147 OFFSET const fd = ctxt->fdiag; / Give the compiler a chance. */
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	148 OFFSET const bd = ctxt->bdiag; / Additional help for the compiler. */
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	149 const ELEMENT const xv = ctxt->xvec; / Still more help for the compiler. */
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	150 const ELEMENT const yv = ctxt->yvec; / And more and more . . . */
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	151 const OFFSET dmin = xoff - ylim; /* Minimum valid diagonal. */
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	152 const OFFSET dmax = xlim - yoff; /* Maximum valid diagonal. */
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	153 const OFFSET fmid = xoff - yoff; /* Center diagonal of top-down search. */
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	154 const OFFSET bmid = xlim - ylim; /* Center diagonal of bottom-up search. */
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	155 OFFSET fmin = fmid;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	156 OFFSET fmax = fmid; /* Limits of top-down search. */
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	157 OFFSET bmin = bmid;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	158 OFFSET bmax = bmid; /* Limits of bottom-up search. */
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	159 OFFSET c; /* Cost. */
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	160 bool odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	161 diagonal with respect to the northwest. */
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	162
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	163 fd[fmid] = xoff;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	164 bd[bmid] = xlim;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	165
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	166 for (c = 1;; ++c)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	167 {
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	168 OFFSET d; /* Active diagonal. */
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	169 bool big_snake = false;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	170
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	171 /* Extend the top-down search by an edit step in each diagonal. */
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	172 if (fmin > dmin)
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	173 fd[--fmin - 1] = -1;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	174 else
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	175 ++fmin;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	176 if (fmax < dmax)
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	177 fd[++fmax + 1] = -1;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	178 else
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	179 --fmax;
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	180 for (d = fmax; d >= fmin; d -= 2)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	181 {
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	182 OFFSET x;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	183 OFFSET y;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	184 OFFSET oldx;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	185 OFFSET tlo = fd[d - 1];
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	186 OFFSET thi = fd[d + 1];
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	187
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	188 if (tlo >= thi)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	189 x = tlo + 1;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	190 else
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	191 x = thi;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	192 oldx = x;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	193 y = x - d;
7451 6c5a4b5959bb Actually use the EQUAL macro. Bruno Haible <bruno@clisp.org> parents: 7448 diff changeset	194 while (x < xlim && y < ylim && EQUAL (xv[x], yv[y]))
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	195 {
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	196 ++x;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	197 ++y;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	198 }
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	199 if (x - oldx > SNAKE_LIMIT)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	200 big_snake = true;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	201 fd[d] = x;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	202 if (odd && bmin <= d && d <= bmax && bd[d] <= x)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	203 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	204 part->xmid = x;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	205 part->ymid = y;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	206 part->lo_minimal = part->hi_minimal = true;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	207 return;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	208 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	209 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	210
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	211 /* Similarly extend the bottom-up search. */
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	212 if (bmin > dmin)
7432 3312c900de96 Make generic: introduce OFFSET_MAX. Bruno Haible <bruno@clisp.org> parents: 7431 diff changeset	213 bd[--bmin - 1] = OFFSET_MAX;
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	214 else
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	215 ++bmin;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	216 if (bmax < dmax)
7432 3312c900de96 Make generic: introduce OFFSET_MAX. Bruno Haible <bruno@clisp.org> parents: 7431 diff changeset	217 bd[++bmax + 1] = OFFSET_MAX;
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	218 else
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	219 --bmax;
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	220 for (d = bmax; d >= bmin; d -= 2)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	221 {
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	222 OFFSET x;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	223 OFFSET y;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	224 OFFSET oldx;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	225 OFFSET tlo = bd[d - 1];
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	226 OFFSET thi = bd[d + 1];
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	227
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	228 if (tlo < thi)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	229 x = tlo;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	230 else
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	231 x = thi - 1;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	232 oldx = x;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	233 y = x - d;
7451 6c5a4b5959bb Actually use the EQUAL macro. Bruno Haible <bruno@clisp.org> parents: 7448 diff changeset	234 while (x > xoff && y > yoff && EQUAL (xv[x - 1], yv[y - 1]))
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	235 {
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	236 --x;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	237 --y;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	238 }
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	239 if (oldx - x > SNAKE_LIMIT)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	240 big_snake = true;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	241 bd[d] = x;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	242 if (!odd && fmin <= d && d <= fmax && x <= fd[d])
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	243 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	244 part->xmid = x;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	245 part->ymid = y;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	246 part->lo_minimal = part->hi_minimal = true;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	247 return;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	248 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	249 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	250
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	251 if (find_minimal)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	252 continue;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	253
7434 2ee32ecdec9d Make the heuristic dependent on USE_HEURISTIC and the variable 'heuristic'. Bruno Haible <bruno@clisp.org> parents: 7433 diff changeset	254 #ifdef USE_HEURISTIC
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	255 /* Heuristic: check occasionally for a diagonal that has made lots
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	256 of progress compared with the edit distance. If we have any
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	257 such, find the one that has made the most progress and return it
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	258 as if it had succeeded.
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	259
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	260 With this heuristic, for vectors with a constant small density
4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	261 of changes, the algorithm is linear in the vector size. */
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	262
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	263 if (c > 200 && big_snake && ctxt->heuristic)
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	264 {
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	265 OFFSET best;
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	266
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	267 best = 0;
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	268 for (d = fmax; d >= fmin; d -= 2)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	269 {
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	270 OFFSET dd = d - fmid;
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	271 OFFSET x = fd[d];
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	272 OFFSET y = x - d;
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	273 OFFSET v = (x - xoff) * 2 - dd;
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	274
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	275 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	276 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	277 if (v > best
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	278 && xoff + SNAKE_LIMIT <= x && x < xlim
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	279 && yoff + SNAKE_LIMIT <= y && y < ylim)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	280 {
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	281 /* We have a good enough best diagonal; now insist
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	282 that it end with a significant snake. */
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	283 int k;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	284
7451 6c5a4b5959bb Actually use the EQUAL macro. Bruno Haible <bruno@clisp.org> parents: 7448 diff changeset	285 for (k = 1; EQUAL (xv[x - k], yv[y - k]); k++)
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	286 if (k == SNAKE_LIMIT)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	287 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	288 best = v;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	289 part->xmid = x;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	290 part->ymid = y;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	291 break;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	292 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	293 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	294 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	295 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	296 if (best > 0)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	297 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	298 part->lo_minimal = true;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	299 part->hi_minimal = false;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	300 return;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	301 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	302
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	303 best = 0;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	304 for (d = bmax; d >= bmin; d -= 2)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	305 {
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	306 OFFSET dd = d - bmid;
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	307 OFFSET x = bd[d];
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	308 OFFSET y = x - d;
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	309 OFFSET v = (xlim - x) * 2 + dd;
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	310
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	311 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	312 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	313 if (v > best
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	314 && xoff < x && x <= xlim - SNAKE_LIMIT
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	315 && yoff < y && y <= ylim - SNAKE_LIMIT)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	316 {
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	317 /* We have a good enough best diagonal; now insist
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	318 that it end with a significant snake. */
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	319 int k;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	320
7451 6c5a4b5959bb Actually use the EQUAL macro. Bruno Haible <bruno@clisp.org> parents: 7448 diff changeset	321 for (k = 0; EQUAL (xv[x + k], yv[y + k]); k++)
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	322 if (k == SNAKE_LIMIT - 1)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	323 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	324 best = v;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	325 part->xmid = x;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	326 part->ymid = y;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	327 break;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	328 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	329 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	330 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	331 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	332 if (best > 0)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	333 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	334 part->lo_minimal = false;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	335 part->hi_minimal = true;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	336 return;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	337 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	338 }
7434 2ee32ecdec9d Make the heuristic dependent on USE_HEURISTIC and the variable 'heuristic'. Bruno Haible <bruno@clisp.org> parents: 7433 diff changeset	339 #endif /* USE_HEURISTIC */
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	340
7444 59373e106e46 Improve variable declaration order. Bruno Haible <bruno@clisp.org> parents: 7440 diff changeset	341 /* Heuristic: if we've gone well beyond the call of duty, give up
59373e106e46 Improve variable declaration order. Bruno Haible <bruno@clisp.org> parents: 7440 diff changeset	342 and report halfway between our best results so far. */
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	343 if (c >= ctxt->too_expensive)
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	344 {
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	345 OFFSET fxybest;
7444 59373e106e46 Improve variable declaration order. Bruno Haible <bruno@clisp.org> parents: 7440 diff changeset	346 OFFSET fxbest IF_LINT (= 0);
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	347 OFFSET bxybest;
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	348 OFFSET bxbest IF_LINT (= 0);
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	349
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	350 /* Find forward diagonal that maximizes X + Y. */
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	351 fxybest = -1;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	352 for (d = fmax; d >= fmin; d -= 2)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	353 {
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	354 OFFSET x;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	355 OFFSET y;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	356
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	357 x = MIN (fd[d], xlim);
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	358 y = x - d;
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	359 if (ylim < y)
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	360 {
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	361 x = ylim + d;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	362 y = ylim;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	363 }
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	364 if (fxybest < x + y)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	365 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	366 fxybest = x + y;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	367 fxbest = x;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	368 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	369 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	370
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	371 /* Find backward diagonal that minimizes X + Y. */
7432 3312c900de96 Make generic: introduce OFFSET_MAX. Bruno Haible <bruno@clisp.org> parents: 7431 diff changeset	372 bxybest = OFFSET_MAX;
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	373 for (d = bmax; d >= bmin; d -= 2)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	374 {
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	375 OFFSET x;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	376 OFFSET y;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	377
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	378 x = MAX (xoff, bd[d]);
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	379 y = x - d;
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	380 if (y < yoff)
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	381 {
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	382 x = yoff + d;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	383 y = yoff;
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	384 }
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	385 if (x + y < bxybest)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	386 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	387 bxybest = x + y;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	388 bxbest = x;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	389 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	390 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	391
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	392 /* Use the better of the two diagonals. */
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	393 if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	394 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	395 part->xmid = fxbest;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	396 part->ymid = fxybest - fxbest;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	397 part->lo_minimal = true;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	398 part->hi_minimal = false;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	399 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	400 else
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	401 {
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	402 part->xmid = bxbest;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	403 part->ymid = bxybest - bxbest;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	404 part->lo_minimal = false;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	405 part->hi_minimal = true;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	406 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	407 return;
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	408 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	409 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	410 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	411
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	412 /* Compare in detail contiguous subsequences of the two vectors
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	413 which are known, as a whole, to match each other.
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	414
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	415 The subsequence of vector 0 is [XOFF, XLIM) and likewise for vector 1.
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	416
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	417 Note that XLIM, YLIM are exclusive bounds. All indices into the vectors
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	418 are origin-0.
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	419
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	420 If FIND_MINIMAL, find a minimal difference no matter how
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	421 expensive it is.
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	422
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	423 The results are recorded in the vectors files[N].changed, by storing 1
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	424 in the element for each line that is an insertion or deletion. */
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	425
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	426 static void
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	427 compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	428 bool find_minimal, struct context *ctxt)
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	429 {
7439 1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	430 const ELEMENT const xv = ctxt->xvec; / Help the compiler. */
1191ef4e9ea4 Make closer to fstrcmp.c: mostly comments, and declare only one variable per Bruno Haible <bruno@clisp.org> parents: 7437 diff changeset	431 const ELEMENT *const yv = ctxt->yvec;
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	432
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	433 /* Slide down the bottom initial diagonal. */
7451 6c5a4b5959bb Actually use the EQUAL macro. Bruno Haible <bruno@clisp.org> parents: 7448 diff changeset	434 while (xoff < xlim && yoff < ylim && EQUAL (xv[xoff], yv[yoff]))
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	435 {
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	436 ++xoff;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	437 ++yoff;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	438 }
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	439 /* Slide up the top initial diagonal. */
7451 6c5a4b5959bb Actually use the EQUAL macro. Bruno Haible <bruno@clisp.org> parents: 7448 diff changeset	440 while (xlim > xoff && ylim > yoff && EQUAL (xv[xlim - 1], yv[ylim - 1]))
7431 4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	441 {
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	442 --xlim;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	443 --ylim;
4be22146f91d Modernize the coding style. Bruno Haible <bruno@clisp.org> parents: 7430 diff changeset	444 }
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	445
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	446 /* Handle simple cases. */
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	447 if (xoff == xlim)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	448 while (yoff < ylim)
7448 050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	449 {
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	450 NOTE_INSERT (ctxt, yoff);
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	451 yoff++;
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	452 }
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	453 else if (yoff == ylim)
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	454 while (xoff < xlim)
7448 050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	455 {
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	456 NOTE_DELETE (ctxt, xoff);
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	457 xoff++;
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	458 }
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	459 else
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	460 {
7440 5b42c8de7c5f Remove an IF_LINT that is probably not necessary any more. Bruno Haible <bruno@clisp.org> parents: 7439 diff changeset	461 struct partition part;
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	462
7433 4266f326be34 Update comments. Talk about vectors instead of files/strings, and about Bruno Haible <bruno@clisp.org> parents: 7432 diff changeset	463 /* Find a point of correspondence in the middle of the vectors. */
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	464 diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	465
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	466 /* Use the partitions to split this problem into subproblems. */
7436 bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	467 compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt);
bea4f38a0f8d Make multithread-safe. Bruno Haible <bruno@clisp.org> parents: 7434 diff changeset	468 compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt);
7427 52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	469 }
52e82ab76173 Move the heart of the diff algorithm from analyze.c to diffseq.h. Bruno Haible <bruno@clisp.org> parents: diff changeset	470 }
7428 7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	471
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	472 #undef ELEMENT
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	473 #undef EQUAL
7f2348458267 Make generic: introduce type parameters. Bruno Haible <bruno@clisp.org> parents: 7427 diff changeset	474 #undef OFFSET
7432 3312c900de96 Make generic: introduce OFFSET_MAX. Bruno Haible <bruno@clisp.org> parents: 7431 diff changeset	475 #undef OFFSET_MAX
7448 050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	476 #undef EXTRA_CONTEXT_FIELDS
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	477 #undef NOTE_DELETE
050f00681985 Make generic: New macro EXTRA_CONTEXT_FIELDS, NOTE_DELETE, NOTE_INSERT. Bruno Haible <bruno@clisp.org> parents: 7445 diff changeset	478 #undef NOTE_INSERT

Mercurial > gnulib

annotate lib/diffseq.h @ 7451:6c5a4b5959bb diff-merge