diff options
Diffstat (limited to 'xdiff/xpatience.c')
| -rw-r--r-- | xdiff/xpatience.c | 48 |
1 files changed, 40 insertions, 8 deletions
diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c index a613efc703..f3573d9f00 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -13,8 +13,8 @@ * 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, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * @@ -62,6 +62,12 @@ struct hashmap { * initially, "next" reflects only the order in file1. */ struct entry *next, *previous; + + /* + * If 1, this entry can serve as an anchor. See + * Documentation/diff-options.txt for more information. + */ + unsigned anchor : 1; } *entries, *first, *last; /* were common records found? */ unsigned long has_matches; @@ -70,8 +76,19 @@ struct hashmap { xpparam_t const *xpp; }; +static int is_anchor(xpparam_t const *xpp, const char *line) +{ + int i; + for (i = 0; i < xpp->anchors_nr; i++) { + if (!strncmp(line, xpp->anchors[i], strlen(xpp->anchors[i]))) + return 1; + } + return 0; +} + /* The argument "pass" is 1 for the first file, 2 for the second. */ -static void insert_record(int line, struct hashmap *map, int pass) +static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map, + int pass) { xrecord_t **records = pass == 1 ? map->env->xdf1.recs : map->env->xdf2.recs; @@ -110,6 +127,7 @@ static void insert_record(int line, struct hashmap *map, int pass) return; map->entries[index].line1 = line; map->entries[index].hash = record->ha; + map->entries[index].anchor = is_anchor(xpp, map->env->xdf1.recs[line - 1]->ptr); if (!map->first) map->first = map->entries + index; if (map->last) { @@ -147,11 +165,11 @@ static int fill_hashmap(mmfile_t *file1, mmfile_t *file2, /* First, fill with entries from the first file */ while (count1--) - insert_record(line1++, result, 1); + insert_record(xpp, line1++, result, 1); /* Then search for matches in the second file */ while (count2--) - insert_record(line2++, result, 2); + insert_record(xpp, line2++, result, 2); return 0; } @@ -166,7 +184,7 @@ static int binary_search(struct entry **sequence, int longest, int left = -1, right = longest; while (left + 1 < right) { - int middle = (left + right) / 2; + int middle = left + (right - left) / 2; /* by construction, no two entries can be equal */ if (sequence[middle]->line2 > entry->line2) right = middle; @@ -192,14 +210,28 @@ static struct entry *find_longest_common_sequence(struct hashmap *map) int longest = 0, i; struct entry *entry; + /* + * If not -1, this entry in sequence must never be overridden. + * Therefore, overriding entries before this has no effect, so + * do not do that either. + */ + int anchor_i = -1; + for (entry = map->first; entry; entry = entry->next) { if (!entry->line2 || entry->line2 == NON_UNIQUE) continue; i = binary_search(sequence, longest, entry); entry->previous = i < 0 ? NULL : sequence[i]; - sequence[++i] = entry; - if (i == longest) + ++i; + if (i <= anchor_i) + continue; + sequence[i] = entry; + if (entry->anchor) { + anchor_i = i; + longest = anchor_i + 1; + } else if (i == longest) { longest++; + } } /* No common unique lines were found */ |