insdelchar.c

操作系统SunOS 4.1.3版本的源码

/*	Copyright (c) 1984 AT&T	*/
/*	  All Rights Reserved  	*/

/*	THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T	*/
/*	The copyright notice above does not evidence any   	*/
/*	actual or intended publication of such source code.	*/

#ifndef lint
static	char sccsid[] = "@(#)insdelchar.c 1.1 92/07/30 SMI"; /* from S5R3 1.4.1.1 */
#endif

/*
 * Modify current screen line 'old' to match desired line 'new'.
 * 'ln' is the line number on the screen.
 * x x:set tabstop=4 shiftwidth=4:
 */

#include "curses.ext"

#define min(a,b) ((a)<(b) ? (a) : (b))
#define max(a,b) ((a)>(b) ? (a) : (b))

/* Macros for costs to insert and delete nchars on this terminal */
#define costic(nchars) (_cost(icfixed) + ((nchars)*_cost(icvar)) )
#define costdc(nchars) (_cost(dcfixed) + _cost(dcvar)*nchars)

#define CHECKSTEP 10	/* Check every # chars for match */
#define MINDIFF    8	/* Don't use I/D if < # chars different */

static char chardiff[256];
static int shift[50], low[50], high[50], matchcount;
static chtype *nb, *ob;
static char *cp;
static int maxlen, olen, nlen;
static int movecost = 0, firstnonblank, firstdiff;
static chtype nullline[] = {0, 0};
#ifdef DEBUG
static int call_time = 0;
#endif /* DEBUG */

_id_char (old, new, ln)
register struct line   *old, *new;
int ln;
{
	register int ur;

	matchcount = 0;

	/* Quick checks for empty lines. */
	if (old) {
		olen = old->length; ob = old->body;
	} else {
		olen = 0; ob = nullline;
	}
	if (new) {
		nlen = new->length; nb = new->body;
	} else {
		nlen = 0; nb = nullline;
	}
	if (nlen <= 0) {
		if (olen > 0)
			_clrline(ln,ob,olen);
		return;
	}
	maxlen = max(olen, nlen);

#ifdef DEBUG
	if (outf) {
		fprintf(outf, "time %d\n", ++call_time);
		_dump_idc(old, new, ln);
	}
#endif

	if (movecost == 0) {
		register int i, j;
		i = _cost(Cursor_address);
		j = _cost(Parm_right_cursor);
		movecost = _cost(Column_address);
		if (i < movecost) movecost = i;
		if (j < movecost) movecost = j;
	}

	/*
	 * If any of these functions returns non-zero, punt and be quick
	 * about it. This handles many common cases with little overhead.
	 */
	if ((ur = _idc_flag_uneq()) || _idc_findmatch() || _idc_costs()) {
		if (ur >= 0)
			_idc_repchar(old, ln);
		return;
	}

	/* Do the fancy ins/del char stuff */
#ifdef DEBUG
	_idc_delchar(old, new, ln);
	_idc_inschar(old, new, ln);
#else
	_idc_delchar(old, ln);
	_idc_inschar(old, ln);
#endif /* DEBUG */
	_chk_typeahead();
}

/*
 * Find chars that line up exactly in new and old lines.
 * Return 1 iff insert/delete should be avoided.  Return
 * -1 if the lines are identical, for immediate return.
 *
 * The variables set below are:
 *
 * given line old:|    abcdefghijklm
 *   and line new:|          ghijktuvwxyz
 * we get:
 *                |                ^ minlen = 13 = minimum length
 *                |                     ^ maxlen = 18 = maximum length
 *                |    ^ firstdiff = 0 = 1st char diff between 2 lines
 *                |          ^ firstnonblank = 6 = 1st non-blank in new line
 *                |    ^^^^^^     ^^^ seen = 8 = count diffs btw. 2 lines
 *                |               ^^^ nbseen = 3 = count diffs after firstnonblank
 *                |0000111111000001111111 <- chardiff
 *
 * chardiff[] is used by _idc_findmatch(), _idc_costs(), _idc_delchar() and
 * _idc_inschar(). firstdiff and firstnonblank are used by _idc_repchar().
 *
 */
static
_idc_flag_uneq()
{
	register int j, seen = 0, nbseen = 0;
	register chtype *p = ob, *q = nb;
	register int minlen = olen + nlen - maxlen;

	/* nothing on old line? */
	if (olen <= 0) {
		for (firstdiff = 0;
		     (*q++ == ' ') && (firstdiff < minlen);
		     firstdiff++)
			;
		firstnonblank = firstdiff;
		return 1;
	}

	/* find first non-blank; fill in chardiff[] & seen */
	cp = chardiff;
	for (j = minlen; (j > 0) && (*q == ' '); j--)
		if (*cp++ = (*p++ != *q++))
			seen++;
	firstnonblank = minlen - j;

	/* continue with chardiff[] & seen & nbseen */
	for ( ; j>0; j--)
		if (*cp++ = (*p++ != *q++))
			seen++, nbseen++;

	/* are the lines the same? */
	if (seen == 0 && olen == nlen)
		return -1;	/* Lines are identical */

	/* find the first difference */
	if (seen == 0)
		firstdiff = minlen;
	else for (j = 0; j < minlen; j++)
		if (chardiff[j]) {
			firstdiff = j;
			break;
		}

	/* continue with chardiff[] */
	for (j=maxlen-minlen; j>0; j--)
		*cp++ = 1;
	if (olen != nlen)
		seen++, nbseen++;

#ifdef DEBUG
	if (outf) {
		fprintf(outf, "chardiff:           ");	/* line up with _dump_idc */
		for (j = 0; j < maxlen; j++)
			fprintf(outf, chardiff[j] ? "^" : ".");
		fprintf(outf, "\n");
		fprintf(outf, "maxlen = %d\n", maxlen);
	}
#endif /* DEBUG */

	/* are lines similar enough? */
	if (seen < MINDIFF || nbseen < MINDIFF) {
#ifdef DEBUG
		if(outf) fprintf(outf, "noid because diffs seen (%d) < MINDIFF %d, or diffs seen after first nonblank (%d after %d) < MINDIFF\n", seen, MINDIFF, nbseen, firstnonblank);
#endif
		return 1;
	}
	return 0;
}

/*
 * Find matching parts in the new and old lines.
 * Return 1 iff insert/delete should be avoided.
 *
 * As an example, consider the following case of old and new lines. The
 * booleans set in chardiff[] denoting differing characters are indicated
 * with a '^'.
 *
 * old:   79 SEND: Send all messages to recipients and of the messageABC23456789| PUSH ENTER
 * new:   79 SEND: Send the message to all recipients the message center23456789| PUSH ENTER
 *           0    +    1    +    2    +    3    +    4    +    5    +    6    +    7    +
 * chardiff: ...........^^^........^^^^^^^^^^^^^^^^^^^^^^.^^^^^^^^^^^^^^....................
 *
 * The output from this routine is the set of arrays low, high and shift.
 * The low and high arrays indicate groups of characters in the new line
 * which match groups of characters in the old line. If it takes an
 * insertion or deletion to make the groups match, the distance away is
 * indicated by the shift value. The corresponding low and high columns from
 * the old line are gotten from subtracting the shift value for that group.
 * Characters between the groups will be overstruck. The values of low,
 * high and shift for this example is given here. The corresponding low
 * and high columns from the old line are indicated by the olow and ohigh
 * columns.
 *
 *    i   low   high    shift   olow    ohigh
 *    0   -1    -1      0       -1      -1
 *    1   0     10      0       0       10
 *    2   29    40      3       26      37
 *    3   41    51      -4      45      55
 *    4   59    78      0       59      78
 *    5   79    79      0       79      79
 *
 * Group 1, columns 0-10 from old "SEND: Send " match columns 0-10 from new.
 * Group 1-2, columns 11-25 from old "all messages to" will be overstruck
 *    with "the message to ".
 * Group 2, columns 26-37 from old " recipients " match new columns 29-40
 *    " recipients ". The old must be shifted right 3 columns by deleting
 *    "and" from the end of old and inserting "all" at the beginning.
 * Group 2-3, there is nothing to overstrike between.
 * Group 3, columns 45-55 from old "the message" match new columns 41-51
 *    "the message". The old must be shifted left 4 columns by deleting
 *    "the ".
 * Group 3-4, columns 52-58. After making the above deletions, the old
 *    "ABC" will be above the new " cen", which must be overstruck
 *    followed by an insertion of "ter".
 * Group 4, at this point columns 59-78 of old "23456789| PUSH ENTER" will
 *    match columns 59-78 of new "23456789| PUSH ENTER" and the line is
 *    done.
 * Groups 0 and 5 act as sentinels during the algorithms.
 */
static
_idc_findmatch()
{
	register int k, h, l;
	register int nhub, ohub, nb_nhub;
	register chtype *chp;
	int ostart, highwat;

	/* Search for matches */
	shift[0] = 0; low[0] = high[0] = -1; matchcount = 1; highwat = 0;

	/* Look for ohub code matching nhub, stepping nhub through by CHECKSTEP. */
	for (nhub=0; nhub<nlen; nhub += CHECKSTEP) {

		/* ohub value for where to start looking */
		ostart = chardiff[nhub] ? highwat : nhub;

		/*
		 * This loop is likely to burn most of the CPU time, hence
		 * extra effort is taken to make it run quickly.
		 */
		nb_nhub = nb[nhub];	/* constant within loop */
		for (chp=ob+ostart,ohub=ostart; ohub<olen; ohub++) {
			if (nb_nhub == *chp++ /*ob[ohub]*/) {
				/*
				 * Found a possible match.  See how far in
				 * both directions it goes.  The double loops
				 * are a speed trick.  This is really ugly,
				 * but has to be very fast.
				 */
				/* to the left .. */
				if (nhub <= ohub) {
					for (l=nhub,k=ohub; l>=0 && nb[l]==ob[k]; l--,k--)
						;
				} else {
					for (l=nhub,k=ohub; k>=0 && nb[l]==ob[k]; l--,k--)
						;
				}
				l++;
				if (l < 0)
					l = 0;
				/* .. and the right */
				if (nhub >= ohub) {
					for (h=nhub,k=ohub; h<maxlen && nb[h]==ob[k]; h++,k++)
						;
				} else {
					for (h=nhub,k=ohub; k<maxlen && nb[h]==ob[k]; h++,k++)
						;
				}
				h--;
				if (h >= maxlen)
					h = maxlen - 1;
				if (h-l > MINDIFF) {	/* Count if at least MINDIFF long */
					int s = nhub-ohub;		/* amount shifted */
					int oh;				/* old high value */
					/* Maybe this match includes the previous match */
					if (l <= low[matchcount-1])
						matchcount--;
					/* If we overlap, do not count that part */
					if (l <= high[matchcount-1])
						l = high[matchcount-1] + 1;
					/* Cannot overlap in the old part, either */
					oh = high[matchcount-1] - shift[matchcount-1];
					if (l - s <= oh)
						l = oh + s + 1;
					/* Record high, low, nhub, ohub in list of matches */
					high[matchcount] = h;
					low[matchcount] = l;
					shift[matchcount++] = s;
					highwat = h - s + 2;
					nhub = highwat;
					break;
				}
			}
		}
	}
	shift[matchcount] = 0; low[matchcount] = high[matchcount] = maxlen;

#ifdef DEBUG
	if (outf) {
		fprintf(outf, "matchcount = %d\n", matchcount);
		_dump_shift((struct line *)0, (struct line *)0, 0, 0, "", 0);
	}
#endif

	return matchcount <= 1;
}

/*
 * Calculate the approximate costs with and without insert/delete char.
 * Return 1 iff insert/delete should be avoided.
 *
 * The cost NOT using insert/delete is derived from the chardiff[]
 * array. Groups of characters that are different would have to be
 * overstruck. Groups of characters that are the same would be skipped
 * over using cursor_address, parm_right_cursor or column_address.
 *
 * Similarly, the cost using insert/delete also includes the cost to
 * insert or delete characters from the ends of the groups.
 */
static
_idc_costs()
{
	register int i, j, k;
	register int cid, cnoid;

	cid = 0;
	if (low[1] > 0)
		cid += movecost + low[1];
	for (i=1; i<matchcount; i++) {
		j = shift[i] - shift[i-1];
		k = (j==0) ? 0 : (j<0) ? costdc(-j) : costic(j);
		if (j || (low[i+1] > high[i] + 1)) {
			cid += movecost +	/* to get cursor there */
				k +				/* i/d char cost */
				(low[i+1]-high[i] - 1);		/* cost to redraw next diff */
#ifdef DEBUG
			if (outf) fprintf(outf, "i %d, add %d + %d + %d for %d\n", i,
				movecost , k, (low[i+1]-high[i] - 1) , cid);
#endif
		}
	}
	cnoid = 0;
	for (i=0; i<nlen; i++)
		if (chardiff[i]) {
			cnoid++;
			if (!chardiff[i-1])
				cnoid += movecost;
		}
	if (nlen < maxlen)
		cnoid += _cost(Clr_eol);

#ifdef DEBUG
	if (outf)
		fprintf(outf, "costid %d, costnoid %d, noid %d\n", cid, cnoid, cnoid <= cid);
#endif
	return cnoid <= cid;
}

/*
 * Simple replacement strategy, not using insert/delete char.
 * _clrbol() gets rid of any leading blanks and
 * showstring does all the replacement work.
 */
static
_idc_repchar(old, ln)
register struct line *old;
{
#ifdef DEBUG
	if (outf)
		fprintf(outf, "doing simple replace char, starting at col %d with blanks to col %d\n", firstdiff, firstnonblank);
#endif

	firstdiff = _clrbol(firstnonblank, firstdiff, ln, ob);

	/* no need to blank out blanks */
	if (firstdiff == olen && nb[firstdiff] == ' ')
		while (nb[++firstdiff] == ' ')
			;

	/* Avoid extra cursor motion to left margin or to same text */
/* - untested
	while ((chardiff[firstdiff] == 0) && (firstdiff < minlen))
		firstdiff++;
*/
	_pos(ln, firstdiff);
	_showstring(ln, firstdiff, nb+firstdiff, nb+nlen-1, old);
	if (nlen < maxlen) {
		_pos(ln, nlen);
		_clreol();
	}
	_chk_typeahead();
}

/*
 * Ins/del char update strategy.  Do all deletions first to avoid
 * losing text from right edge of screen.
 */
#ifdef DEBUG
static
_idc_delchar(old, new, ln)
register struct line *old, *new;
#else
static
_idc_delchar(old, ln)
register struct line *old;
#endif /* DEBUG */
{
	register int i, l, oh_im1_p1, k;
	register chtype *p, *q, *r;
	int hi_im1, shif_im1, j;

#ifdef DEBUG
	if (outf) fprintf(outf, "doing delete chars\n");
#endif
	/* Do the deletions */
	for (i=1; i<matchcount; i++) {
#ifdef DEBUG
		if (outf) fprintf(outf, "comparing shift[i=%d] = %d to shift[i-1=%d] = %d.\n", i, shift[i], i-1, shift[i-1]);
#endif /* DEBUG */
		if (shift[i] < shift[i-1]) {		/* If it is a deletion */
			/*
			 * Overall strategy: there are two possibilities:
			 * the previous area is about to be shifted off
			 * the right end, so that we need to delete something
			 * from the end of that area, or we are in a region
			 * that needs to have text removed from the
			 * beginning. Both may occur together.
			 *
			 * In the first case, in which shift[i-1] > 0,
			 * we move to the end of the previous area and
			 * delete the extra characters.
			 *
			 *    QfghijkAB
			 *    QdefghiAB
			 *
			 * In the above example, the "jk" needs to be
			 * deleted so that the "de" may be inserted later
			 * in the insert routine.
			 *
			 * In the second case, there are two parts:
			 * first overstrike things that do not need to
			 * be deleted, then delete the rest.
			 *
			 *    Q d e f g h i A B		new
			 *    Q w x y z A B		old
			 *
			 * In the above example, we overstrike the "wxyz"
			 * over the old "defg", then delete the old "hi".
			 *
			 * If both cases occur together, we move to the
			 * end of the previous area and do the overstrikes
			 * there. Then both sets of character deletions
			 * get done together.
			 *
			 * In both cases, shift[i-1]-shift[i] will be the
			 * number of characters to be deleted, and
			 * low[i] - high[i-1] + 1 will be the number of
			 * characters to be overstruck.
			 */
			hi_im1 = high[i-1];
			shif_im1 = shift[i-1];
			oh_im1_p1 = hi_im1 - shif_im1 + 1;/* old start col (ohigh[i-1]+1)*/
			/* output overstrike part */
			p = nb + hi_im1 + 1;
			q = nb + low[i] - 1;
			/* number overstruck = low[i] - high[i-1] + 1 */
			if (p <= q) {
#ifdef DEBUG
				if (outf) fprintf(outf, "del-overstriking %d chars at column %d\n", q - p + 1, oh_im1_p1);
#endif /* DEBUG */
				_pos(ln, oh_im1_p1);
				_showstring(ln, oh_im1_p1, p, q, old);
				/* update internal copy of screen */
				r = ob + oh_im1_p1;
				oh_im1_p1 += q - p + 1;
				while (p <= q)	/* update old buffer */
					*r++ = *p++;
#ifdef DEBUG
				_dump_shift(old, new, ln, 1, "del-replacement", i);
#endif /* DEBUG */
			}

			if (shif_im1 > 0)	/* position to delete */
				l = oh_im1_p1;
			else
				l = low[i];