vim: src/xdiff/xhistogram.c annotate

annotate src/xdiff/xhistogram.c @ 34251:9870ee5a6a16

runtime(Filelist): include README_vimlogo.txt (#13944) Commit: https://github.com/vim/vim/commit/f430e7daebc8fb0023884e753c99c3d2f51936af Author: Philip H <47042125+pheiduck@users.noreply.github.com> Date: Wed Jan 31 20:51:48 2024 +0100 runtime(Filelist): include README_vimlogo.txt (https://github.com/vim/vim/issues/13944) Signed-off-by: Philip H <47042125+pheiduck@users.noreply.github.com> Signed-off-by: Christian Brabandt <cb@256bit.org>

author	Christian Brabandt <cb@256bit.org>
date	Wed, 31 Jan 2024 21:00:02 +0100
parents	f84e5db372ea
children

rev	line source
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	1 /*
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	2 * Copyright (C) 2010, Google Inc.
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	3 * and other copyright owners as documented in JGit's IP log.
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	4 *
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	5 * This program and the accompanying materials are made available
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	6 * under the terms of the Eclipse Distribution License v1.0 which
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	7 * accompanies this distribution, is reproduced below, and is
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	8 * available at http://www.eclipse.org/org/documents/edl-v10.php
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	9 *
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	10 * All rights reserved.
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	11 *
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	12 * Redistribution and use in source and binary forms, with or
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	13 * without modification, are permitted provided that the following
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	14 * conditions are met:
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	15 *
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	16 * - Redistributions of source code must retain the above copyright
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	17 * notice, this list of conditions and the following disclaimer.
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	18 *
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	19 * - Redistributions in binary form must reproduce the above
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	20 * copyright notice, this list of conditions and the following
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	21 * disclaimer in the documentation and/or other materials provided
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	22 * with the distribution.
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	23 *
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	24 * - Neither the name of the Eclipse Foundation, Inc. nor the
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	25 * names of its contributors may be used to endorse or promote
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	26 * products derived from this software without specific prior
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	27 * written permission.
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	28 *
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	30 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	31 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	33 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	34 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	36 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	37 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	38 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	41 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	42 */
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	43
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	44 #include "xinclude.h"
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	45
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	46 #define MAX_PTR INT_MAX
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	47 #define MAX_CNT INT_MAX
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	48
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	49 #define LINE_END(n) (line##n + count##n - 1)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	50 #define LINE_END_PTR(n) (line##n + count##n - 1)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	51
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	52 struct histindex {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	53 struct record {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	54 unsigned int ptr, cnt;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	55 struct record *next;
25709 d5142d87f898 patch 8.2.3390: included xdiff code is outdated Bram Moolenaar <Bram@vim.org> parents: 18802 diff changeset	56 } *records, / an occurrence */
d5142d87f898 patch 8.2.3390: included xdiff code is outdated Bram Moolenaar <Bram@vim.org> parents: 18802 diff changeset	57 *line_map; / map of line to record chain */
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	58 chastore_t rcha;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	59 unsigned int *next_ptrs;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	60 unsigned int table_bits,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	61 records_size,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	62 line_map_size;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	63
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	64 unsigned int max_chain_length,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	65 key_shift,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	66 ptr_shift;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	67
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	68 unsigned int cnt,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	69 has_common;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	70
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	71 xdfenv_t *env;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	72 xpparam_t const *xpp;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	73 };
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	74
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	75 struct region {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	76 unsigned int begin1, end1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	77 unsigned int begin2, end2;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	78 };
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	79
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	80 #define LINE_MAP(i, a) (i->line_map[(a) - i->ptr_shift])
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	81
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	82 #define NEXT_PTR(index, ptr) \
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	83 (index->next_ptrs[(ptr) - index->ptr_shift])
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	84
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	85 #define CNT(index, ptr) \
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	86 ((LINE_MAP(index, ptr))->cnt)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	87
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	88 #define REC(env, s, l) \
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	89 (env->xdf##s.recs[l - 1])
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	90
32174 f84e5db372ea patch 9.0.1418: the included xdiff code is a bit outdated Bram Moolenaar <Bram@vim.org> parents: 25709 diff changeset	91 static int cmp_recs(xrecord_t r1, xrecord_t r2)
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	92 {
32174 f84e5db372ea patch 9.0.1418: the included xdiff code is a bit outdated Bram Moolenaar <Bram@vim.org> parents: 25709 diff changeset	93 return r1->ha == r2->ha;
f84e5db372ea patch 9.0.1418: the included xdiff code is a bit outdated Bram Moolenaar <Bram@vim.org> parents: 25709 diff changeset	94
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	95 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	96
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	97 #define CMP(i, s1, l1, s2, l2) \
32174 f84e5db372ea patch 9.0.1418: the included xdiff code is a bit outdated Bram Moolenaar <Bram@vim.org> parents: 25709 diff changeset	98 (cmp_recs(REC(i->env, s1, l1), REC(i->env, s2, l2)))
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	99
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	100 #define TABLE_HASH(index, side, line) \
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	101 XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	102
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	103 static int scanA(struct histindex *index, int line1, int count1)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	104 {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	105 int ptr, tbl_idx;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	106 unsigned int chain_len;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	107 struct record *rec_chain, rec;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	108
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	109 for (ptr = LINE_END(1); line1 <= ptr; ptr--) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	110 tbl_idx = TABLE_HASH(index, 1, ptr);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	111 rec_chain = index->records + tbl_idx;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	112 rec = *rec_chain;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	113
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	114 chain_len = 0;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	115 while (rec) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	116 if (CMP(index, 1, rec->ptr, 1, ptr)) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	117 /*
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	118 * ptr is identical to another element. Insert
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	119 * it onto the front of the existing element
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	120 * chain.
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	121 */
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	122 NEXT_PTR(index, ptr) = rec->ptr;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	123 rec->ptr = ptr;
25709 d5142d87f898 patch 8.2.3390: included xdiff code is outdated Bram Moolenaar <Bram@vim.org> parents: 18802 diff changeset	124 /* cap rec->cnt at MAX_CNT */
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	125 rec->cnt = XDL_MIN(MAX_CNT, rec->cnt + 1);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	126 LINE_MAP(index, ptr) = rec;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	127 goto continue_scan;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	128 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	129
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	130 rec = rec->next;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	131 chain_len++;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	132 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	133
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	134 if (chain_len == index->max_chain_length)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	135 return -1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	136
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	137 /*
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	138 * This is the first time we have ever seen this particular
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	139 * element in the sequence. Construct a new chain for it.
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	140 */
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	141 if (!(rec = xdl_cha_alloc(&index->rcha)))
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	142 return -1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	143 rec->ptr = ptr;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	144 rec->cnt = 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	145 rec->next = *rec_chain;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	146 *rec_chain = rec;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	147 LINE_MAP(index, ptr) = rec;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	148
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	149 continue_scan:
25709 d5142d87f898 patch 8.2.3390: included xdiff code is outdated Bram Moolenaar <Bram@vim.org> parents: 18802 diff changeset	150 ; /* no op */
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	151 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	152
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	153 return 0;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	154 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	155
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	156 static int try_lcs(struct histindex index, struct region lcs, int b_ptr,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	157 int line1, int count1, int line2, int count2)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	158 {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	159 unsigned int b_next = b_ptr + 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	160 struct record *rec = index->records[TABLE_HASH(index, 2, b_ptr)];
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	161 unsigned int as, ae, bs, be, np, rc;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	162 int should_break;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	163
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	164 for (; rec; rec = rec->next) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	165 if (rec->cnt > index->cnt) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	166 if (!index->has_common)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	167 index->has_common = CMP(index, 1, rec->ptr, 2, b_ptr);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	168 continue;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	169 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	170
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	171 as = rec->ptr;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	172 if (!CMP(index, 1, as, 2, b_ptr))
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	173 continue;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	174
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	175 index->has_common = 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	176 for (;;) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	177 should_break = 0;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	178 np = NEXT_PTR(index, as);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	179 bs = b_ptr;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	180 ae = as;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	181 be = bs;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	182 rc = rec->cnt;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	183
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	184 while (line1 < (int)as && line2 < (int)bs
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	185 && CMP(index, 1, as - 1, 2, bs - 1)) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	186 as--;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	187 bs--;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	188 if (1 < rc)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	189 rc = XDL_MIN(rc, CNT(index, as));
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	190 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	191 while ((int)ae < LINE_END(1) && (int)be < LINE_END(2)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	192 && CMP(index, 1, ae + 1, 2, be + 1)) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	193 ae++;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	194 be++;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	195 if (1 < rc)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	196 rc = XDL_MIN(rc, CNT(index, ae));
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	197 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	198
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	199 if (b_next <= be)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	200 b_next = be + 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	201 if (lcs->end1 - lcs->begin1 < ae - as \|\| rc < index->cnt) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	202 lcs->begin1 = as;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	203 lcs->begin2 = bs;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	204 lcs->end1 = ae;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	205 lcs->end2 = be;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	206 index->cnt = rc;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	207 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	208
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	209 if (np == 0)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	210 break;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	211
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	212 while (np <= ae) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	213 np = NEXT_PTR(index, np);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	214 if (np == 0) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	215 should_break = 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	216 break;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	217 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	218 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	219
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	220 if (should_break)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	221 break;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	222
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	223 as = np;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	224 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	225 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	226 return b_next;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	227 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	228
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	229 static int fall_back_to_classic_diff(xpparam_t const xpp, xdfenv_t env,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	230 int line1, int count1, int line2, int count2)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	231 {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	232 xpparam_t xpparam;
25709 d5142d87f898 patch 8.2.3390: included xdiff code is outdated Bram Moolenaar <Bram@vim.org> parents: 18802 diff changeset	233
d5142d87f898 patch 8.2.3390: included xdiff code is outdated Bram Moolenaar <Bram@vim.org> parents: 18802 diff changeset	234 memset(&xpparam, 0, sizeof(xpparam));
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	235 xpparam.flags = xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	236
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	237 return xdl_fall_back_diff(env, &xpparam,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	238 line1, count1, line2, count2);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	239 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	240
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	241 static inline void free_index(struct histindex *index)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	242 {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	243 xdl_free(index->records);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	244 xdl_free(index->line_map);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	245 xdl_free(index->next_ptrs);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	246 xdl_cha_free(&index->rcha);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	247 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	248
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	249 static int find_lcs(xpparam_t const xpp, xdfenv_t env,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	250 struct region *lcs,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	251 int line1, int count1, int line2, int count2)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	252 {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	253 int b_ptr;
32174 f84e5db372ea patch 9.0.1418: the included xdiff code is a bit outdated Bram Moolenaar <Bram@vim.org> parents: 25709 diff changeset	254 int ret = -1;
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	255 struct histindex index;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	256
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	257 memset(&index, 0, sizeof(index));
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	258
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	259 index.env = env;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	260 index.xpp = xpp;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	261
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	262 index.records = NULL;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	263 index.line_map = NULL;
25709 d5142d87f898 patch 8.2.3390: included xdiff code is outdated Bram Moolenaar <Bram@vim.org> parents: 18802 diff changeset	264 /* in case of early xdl_cha_free() */
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	265 index.rcha.head = NULL;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	266
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	267 index.table_bits = xdl_hashbits(count1);
32174 f84e5db372ea patch 9.0.1418: the included xdiff code is a bit outdated Bram Moolenaar <Bram@vim.org> parents: 25709 diff changeset	268 index.records_size = 1 << index.table_bits;
f84e5db372ea patch 9.0.1418: the included xdiff code is a bit outdated Bram Moolenaar <Bram@vim.org> parents: 25709 diff changeset	269 if (!XDL_CALLOC_ARRAY(index.records, index.records_size))
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	270 goto cleanup;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	271
32174 f84e5db372ea patch 9.0.1418: the included xdiff code is a bit outdated Bram Moolenaar <Bram@vim.org> parents: 25709 diff changeset	272 index.line_map_size = count1;
f84e5db372ea patch 9.0.1418: the included xdiff code is a bit outdated Bram Moolenaar <Bram@vim.org> parents: 25709 diff changeset	273 if (!XDL_CALLOC_ARRAY(index.line_map, index.line_map_size))
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	274 goto cleanup;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	275
32174 f84e5db372ea patch 9.0.1418: the included xdiff code is a bit outdated Bram Moolenaar <Bram@vim.org> parents: 25709 diff changeset	276 if (!XDL_CALLOC_ARRAY(index.next_ptrs, index.line_map_size))
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	277 goto cleanup;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	278
25709 d5142d87f898 patch 8.2.3390: included xdiff code is outdated Bram Moolenaar <Bram@vim.org> parents: 18802 diff changeset	279 /* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	280 if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	281 goto cleanup;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	282
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	283 index.ptr_shift = line1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	284 index.max_chain_length = 64;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	285
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	286 if (scanA(&index, line1, count1))
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	287 goto cleanup;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	288
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	289 index.cnt = index.max_chain_length + 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	290
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	291 for (b_ptr = line2; b_ptr <= LINE_END(2); )
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	292 b_ptr = try_lcs(&index, lcs, b_ptr, line1, count1, line2, count2);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	293
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	294 if (index.has_common && index.max_chain_length < index.cnt)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	295 ret = 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	296 else
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	297 ret = 0;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	298
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	299 cleanup:
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	300 free_index(&index);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	301 return ret;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	302 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	303
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	304 static int histogram_diff(xpparam_t const xpp, xdfenv_t env,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	305 int line1, int count1, int line2, int count2)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	306 {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	307 struct region lcs;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	308 int lcs_found;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	309 int result;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	310 redo:
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	311 result = -1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	312
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	313 if (count1 <= 0 && count2 <= 0)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	314 return 0;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	315
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	316 if (LINE_END(1) >= MAX_PTR)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	317 return -1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	318
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	319 if (!count1) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	320 while(count2--)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	321 env->xdf2.rchg[line2++ - 1] = 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	322 return 0;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	323 } else if (!count2) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	324 while(count1--)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	325 env->xdf1.rchg[line1++ - 1] = 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	326 return 0;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	327 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	328
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	329 memset(&lcs, 0, sizeof(lcs));
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	330 lcs_found = find_lcs(xpp, env, &lcs, line1, count1, line2, count2);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	331 if (lcs_found < 0)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	332 goto out;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	333 else if (lcs_found)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	334 result = fall_back_to_classic_diff(xpp, env, line1, count1, line2, count2);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	335 else {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	336 if (lcs.begin1 == 0 && lcs.begin2 == 0) {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	337 while (count1--)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	338 env->xdf1.rchg[line1++ - 1] = 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	339 while (count2--)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	340 env->xdf2.rchg[line2++ - 1] = 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	341 result = 0;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	342 } else {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	343 result = histogram_diff(xpp, env,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	344 line1, lcs.begin1 - line1,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	345 line2, lcs.begin2 - line2);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	346 if (result)
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	347 goto out;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	348 /*
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	349 * result = histogram_diff(xpp, env,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	350 * lcs.end1 + 1, LINE_END(1) - lcs.end1,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	351 * lcs.end2 + 1, LINE_END(2) - lcs.end2);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	352 * but let's optimize tail recursion ourself:
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	353 */
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	354 count1 = LINE_END(1) - lcs.end1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	355 line1 = lcs.end1 + 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	356 count2 = LINE_END(2) - lcs.end2;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	357 line2 = lcs.end2 + 1;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	358 goto redo;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	359 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	360 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	361 out:
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	362 return result;
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	363 }
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	364
32174 f84e5db372ea patch 9.0.1418: the included xdiff code is a bit outdated Bram Moolenaar <Bram@vim.org> parents: 25709 diff changeset	365 int xdl_do_histogram_diff(xpparam_t const xpp, xdfenv_t env)
14696 195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	366 {
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	367 return histogram_diff(xpp, env,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	368 env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	369 env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);
195e8b1fcbbf patch 8.1.0360: using an external diff program is slow and inflexible Christian Brabandt <cb@256bit.org> parents: diff changeset	370 }

Mercurial > vim

annotate src/xdiff/xhistogram.c @ 34251:9870ee5a6a16