diff options
| author | Junio C Hamano <gitster@pobox.com> | 2025-12-09 07:54:55 +0900 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2025-12-09 07:54:55 +0900 |
| commit | 7fc0b33b5d9ced74819132a094528154f83f4a6a (patch) | |
| tree | f880ec1d13f74a4a0d3cf5f0da0d9daf12077c28 | |
| parent | fe0e6ffa1998ad28e8362420a20e5fd655dcd569 (diff) | |
| parent | c7e3b8085bb2f74371f5017f42c58b0acf01b915 (diff) | |
Merge branch 'yc/xdiff-patience-optim'
The way patience diff finds LCS has been optimized.
* yc/xdiff-patience-optim:
xdiff: optimize patience diff's LCS search
| -rw-r--r-- | xdiff/xpatience.c | 5 |
1 files changed, 4 insertions, 1 deletions
diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c index a0b31eb5d8..9580d18032 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -211,7 +211,10 @@ static int find_longest_common_sequence(struct hashmap *map, struct entry **res) for (entry = map->first; entry; entry = entry->next) { if (!entry->line2 || entry->line2 == NON_UNIQUE) continue; - i = binary_search(sequence, longest, entry); + if (longest == 0 || entry->line2 > sequence[longest - 1]->line2) + i = longest - 1; + else + i = binary_search(sequence, longest, entry); entry->previous = i < 0 ? NULL : sequence[i]; ++i; if (i <= anchor_i) |