1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License").  You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22/*
23 * Copyright (c) 1995-1999 by Sun Microsystems, Inc.
24 * All rights reserved.
25 */
26
27#pragma ident	"%Z%%M%	%I%	%E% SMI"
28
29/* LINTLIBRARY */
30
31/*
32 * doupdate.c
33 *
34 * XCurses Library
35 *
36 * Copyright 1990, 1995 by Mortice Kern Systems Inc.  All rights reserved.
37 *
38 */
39
40#ifdef M_RCSID
41#ifndef lint
42static char const rcsID[] =
43"$Header: /team/ps/sun_xcurses/archive/local_changes/xcurses/src/lib/"
44"libxcurses/src/libc/xcurses/rcs/doupdate.c 1.22 1998/06/04 12:13:38 "
45"cbates Exp $";
46#endif
47#endif
48
49#include <sys/isa_defs.h>
50#include <private.h>
51#include <string.h>
52#include <signal.h>
53
54#undef SIGTSTP
55
56/*
57 * This value is the ideal length for the cursor addressing sequence
58 * being four bytes long, ie. "<escape><cursor addressing code><row><col>".
59 * eg. VT52 - "\EYrc" or ADM3A - "\E=rc"
60 */
61#define	JUMP_SIZE	4
62
63/*
64 * This value is the ideal length for the clear-to-eol sequence
65 * being two bytes long, ie "<escape><clear eol code>".
66 */
67#define	CEOL_SIZE	2
68
69#define	GOTO(r, c)	((void) __m_mvcur(curscr->_cury, curscr->_curx,\
70	r, c, __m_outc), curscr->_cury = r, curscr->_curx = c)
71
72typedef struct cost_op {
73	short	cost;
74	short	op;
75} lcost;
76
77typedef void (*t_action)(int, int);
78
79
80#define	LC(i, j) 	(lc[(i) * (LINES + 1) + (j)])
81
82static lcost *lc = NULL;
83#if defined(_LP64)
84static unsigned int	*nhash = NULL;
85#else
86static unsigned long	*nhash = NULL;
87#endif
88static t_action *del = NULL;
89static t_action *ins_rep = NULL;
90
91static WINDOW	*newscr;
92
93static void erase_bottom(int, int);
94static void clear_bottom(int);
95static void complex(void);
96static int cost(int, int);
97static void lines_delete(int, int);
98static void lines_insert(int, int);
99static void lines_replace(int, int);
100static void script(int, int);
101static int scroll_up(int);
102static void simple(void);
103static void text_replace(int);
104#if 0
105static int scroll_dn(int);
106#endif
107
108
109/*
110 * Wrapper that streams Curses output.
111 *
112 * All escape sequences going to the screen come through here.
113 * All ordinary characters go to the screen via the putc in doupdate.c
114 */
115int
116__m_outc(int ch)
117{
118	return (putc(ch, __m_screen->_of));
119}
120
121/*
122 * Allocate or grow doupdate() structures.
123 */
124int
125__m_doupdate_init(void)
126{
127	void	*new;
128	static short	nlines = 0;
129
130	if (lines <= 0)
131		return (-1);
132
133	if (lines <= nlines)
134		return (0);
135
136	new = malloc((lines + 1) * (lines + 1) * sizeof (*lc));
137	if (new == NULL)
138		return (-1);
139	if (lc != NULL)
140		free(lc);
141	lc = (lcost *) new;
142
143	new = malloc((lines + lines) * sizeof (*del));
144	if (new == NULL)
145		return (-1);
146	if (del != NULL)
147		free(del);
148	del = (t_action *) new;
149	ins_rep = del + lines;
150
151	new = malloc(lines * sizeof (*nhash));
152	if (new == NULL)
153		return (-1);
154	if (nhash != NULL)
155		free(nhash);
156#if defined(_LP64)
157	nhash = (unsigned int *) new;
158#else
159	nhash = (unsigned long *) new;
160#endif
161
162	nlines = lines;
163
164	return (0);
165}
166
167static void
168erase_bottom(int start, int end)
169{
170	int i;
171
172	for (i = start; i < end; ++i) {
173		(void) __m_cc_erase(curscr, i, 0, i, curscr->_maxx - 1);
174		__m_cc_hash(curscr, __m_screen->_hash, i);
175	}
176}
177
178/*
179 *  Clear from the start of the current row to bottom of screen.
180 */
181static void
182clear_bottom(int y)
183{
184	/* Restore default color pair before doing area clears. */
185	if (back_color_erase)
186		(void) vid_puts(WA_NORMAL, 0, (void *) 0, __m_outc);
187
188	if (y == 0 && clear_screen != NULL) {
189		(void) TPUTS(clear_screen, 1, __m_outc);
190	} else {
191		(void) __m_mvcur(-1, -1, y, 0, __m_outc);
192		if (clr_eos != NULL) {
193			(void) TPUTS(clr_eos, 1, __m_outc);
194		} else if (clr_eol != NULL) {
195			for (;;) {
196				(void) TPUTS(clr_eol, 1, __m_outc);
197				if (LINES <= y)
198					break;
199				(void) __m_mvcur(y, 0, y + 1, 0, __m_outc);
200				++y;
201			}
202		}
203	}
204
205	curscr->_cury = y;
206	curscr->_curx = 0;
207}
208
209
210
211/*
212 * Rewrite of text_replace() implementation by C. Bates of MKS
213 *
214 * This code creates a list of 'regions' for each test line which
215 * is to be replaced. Each region describes a portion of the line.
216 * Logic is performed on the list of regions, then the regions
217 * are used to generate output.
218 */
219typedef	struct LineRegion {
220	int	col;	/* Starting column of region */
221	int	size;	/* Size of region */
222	/* 0: Difference Region, 1: Common Region, 2: Delete Region */
223	int	type;
224} LineRegion;
225#define	REGION_DIFFERENT	0
226#define	REGION_COMMON		1
227#define	REGION_DELETE		2
228
229#define	DELETE_SEARCH_LIMIT	4
230#define	DELETE_THRESHOLD	10
231
232static LineRegion	regions[1024];
233int	nRegions = 0;
234
235/*
236 * Return the first column of the completely blank End-of-line
237 */
238static int
239_find_blank_tail(int row)
240{
241	cchar_t	*nptr;
242	int	tail = COLS;
243
244	if (!clr_eol)
245		return (COLS);
246	/*
247	 * Find start of blank tail region.
248	 */
249	nptr = &newscr->_line[row][COLS];
250	for (; 0 < tail; --tail) {
251		if (!__m_cc_compare(--nptr, &newscr->_bg, 1))
252			break;
253	}
254	return (tail);
255}
256
257/*
258 * Send all the characters in the region to the terminal
259 */
260static void
261_writeRegion(int row, LineRegion region)
262{
263	short	npair;
264	attr_t	nattr;
265	int	i;
266	cchar_t	*optr = &curscr->_line[row][region.col];
267	cchar_t	*nptr = &newscr->_line[row][region.col];
268
269	for (i = 0; i < region.size; i++, nptr++, optr++) {
270		nattr = nptr->_at;
271		npair = nptr->_co;
272
273		/*
274		 * Change attribute state.
275		 */
276		if ((ATTR_STATE != nattr) || (optr->_at != nattr) ||
277			(cur_term->_co != npair)) {
278			(void) vid_puts(nattr, npair, NULL, __m_outc);
279		}
280		/*
281		 * Don't display internal characters.
282		 */
283		if (nptr->_f)
284			(void) __m_cc_write(nptr);
285
286		/*
287		 * Update copy of screen image.
288		 */
289		*optr = *nptr;
290		curscr->_curx = region.col + i + 1;
291	}
292}
293
294/*
295 * Delete some characters from the terminal for this region
296 */
297static void
298_deleteRegion(int row, LineRegion region)
299{
300	int	i;
301	cchar_t	*optr = &curscr->_line[row][region.col];
302
303	if ((region.size <= 1) || !parm_dch) {
304		for (i = 0; i < region.size; i++)
305			(void) TPUTS(delete_character, 1, __m_outc);
306	} else {
307		(void) TPUTS(tparm(parm_dch, (long)region.size,
308			0, 0, 0, 0, 0, 0, 0, 0), region.size, __m_outc);
309	}
310	for (i = region.col; i < COLS - region.size; i++) {
311		/*
312		 * Delete the chars in the image of the real screen
313		 */
314		*optr = *(optr + region.size);
315		optr++;
316	}
317}
318
319/*
320 * Use clr_eol control if possible
321 */
322static void
323_clearToEOL(int row, int tail)
324{
325	if (tail < COLS) {
326		GOTO(row, tail);
327		/*
328		 * Restore default color pair before area clear.
329		 */
330		if (back_color_erase)
331			(void) vid_puts(WA_NORMAL, 0, NULL, __m_outc);
332
333		(void) TPUTS(clr_eol, 1, __m_outc);
334		(void) __m_cc_erase(curscr, row, tail, row, COLS - 1);
335	}
336}
337
338/*
339 * Delete leading common region
340 */
341static void
342_normalizeRegions1(void)
343{
344	int	iRegion;
345
346	/*
347	 * Delete leading common region
348	 */
349	if (regions[0].type == REGION_COMMON) {
350		nRegions--;
351		for (iRegion = 0; iRegion < nRegions; iRegion++) {
352			regions[iRegion] = regions[iRegion + 1];
353		}
354	}
355}
356
357/*
358 * Give each region a size, then delete all trailing common regions
359 */
360static void
361_normalizeRegions2(void)
362{
363	int	iRegion;
364
365	for (iRegion = 0; iRegion < nRegions - 1; iRegion++) {
366		regions[iRegion].size = regions[iRegion + 1].col -
367			regions[iRegion].col;
368	}
369	regions[nRegions - 1].size = COLS - regions[nRegions - 1].col;
370
371	/*
372	 * Delete trailing common regions
373	 */
374	while (regions[nRegions - 1].type == REGION_COMMON)
375		nRegions--;
376}
377
378/*
379 * Tiny common regions are merged into adjacent difference regions
380 */
381static void
382_mergeTinyRegions(void)
383{
384	int	from;
385	int	to;
386	for (from = 1, to = 1; from < nRegions; ) {
387		if ((regions[from].type == REGION_COMMON) &&
388			(regions[from].size < JUMP_SIZE)) {
389			/*
390			 * Merge out tiny common regions
391			 */
392			regions[to - 1].size += regions[from].size;
393			/*
394			 * Now join adjacent non-common regions
395			 */
396			if (++from < nRegions)
397				regions[to - 1].size += regions[from++].size;
398		} else {
399			regions[to++] = regions[from++];
400		}
401	}
402	nRegions = to;
403}
404
405/*
406 * Create the initial list of regions for this row
407 */
408static int
409_findRegions(int row)
410{
411	int	cmp;
412	int	old_cmp;
413	int	col;
414	int	bestDeleteCount;
415	cchar_t	*nptr = &newscr->_line[row][0];
416	cchar_t	*optr = &curscr->_line[row][0];
417
418	col = 0;
419	nRegions = 0;
420	bestDeleteCount = 0;
421	if ((__m_screen->_flags & S_INS_DEL_CHAR) &&
422		(parm_dch || delete_character)) {
423		int	bestFit = 0;
424		int	deletePoint;
425		int	deleteCount;
426		int	matches;
427
428		/*
429		 * Skip to first difference
430		 */
431		for (col = 0; col < COLS; col++) {
432			if (!__m_cc_compare(&optr[col], &nptr[col], 1))
433				break;
434		}
435		deletePoint = col;
436		for (deleteCount = 1; deleteCount < DELETE_SEARCH_LIMIT;
437			deleteCount++) {
438			matches = 0;
439			for (col = deletePoint; col < COLS - deleteCount;
440				col++) {
441				if (__m_cc_compare(&optr[col + deleteCount],
442					&nptr[col], 1))
443					matches++;
444				else
445					break;
446			}
447			if (matches > bestFit) {
448				bestFit = matches;
449				bestDeleteCount = deleteCount;
450			}
451		}
452		if (bestFit > DELETE_THRESHOLD) {
453			regions[nRegions].type = REGION_DELETE;
454			regions[nRegions].col = deletePoint;
455			regions[nRegions].size = bestDeleteCount;
456			nRegions++;
457			col = deletePoint + bestDeleteCount;
458		} else {
459			col = 0;
460			nRegions = 0;
461			/* Forget trying to use character delete */
462			bestDeleteCount = 0;
463		}
464	}
465	for (old_cmp = -1; col + bestDeleteCount < COLS; col++) {
466		cmp = __m_cc_compare(&optr[col + bestDeleteCount],
467			&nptr[col], 1);
468		if (cmp != old_cmp) {
469			regions[nRegions].type = cmp ? REGION_COMMON :
470				REGION_DIFFERENT;
471			regions[nRegions].col = col;
472			regions[nRegions].size = 0;	/* Determine later */
473			nRegions++;
474			old_cmp = cmp;
475		}
476	}
477	if (bestDeleteCount) {
478		/*
479		 * Force update of end-of-line if delete is to be used
480		 */
481		regions[nRegions].type = REGION_DIFFERENT;
482		regions[nRegions].col = col;
483		regions[nRegions].size = 0;	/* Determine later */
484		nRegions++;
485	}
486	_normalizeRegions1();
487	if (nRegions == 0)
488		return (0);		/* No difference regions */
489
490	_normalizeRegions2();
491	return (1);
492}
493
494/*
495 * Determine if Clr-EOL optimization can be used, and
496 * adjust regions accordingly
497 */
498static int
499_ceolAdjustRegions(int row)
500{
501	int	iRegion;
502	int	blankEolStart = _find_blank_tail(row);
503
504	for (iRegion = 0; iRegion < nRegions; iRegion++) {
505		switch (regions[iRegion].type) {
506		case REGION_DIFFERENT:
507			if (regions[iRegion].col >= blankEolStart) {
508				/*
509				 * Delete this and all following regions
510				 */
511				nRegions = iRegion;
512				return (blankEolStart);
513			}
514			if (regions[iRegion].col + regions[iRegion].size >
515				blankEolStart) {
516				/*
517				 * Truncate this region to end
518				 * where blank EOL starts
519				 */
520				regions[iRegion].size = blankEolStart -
521					regions[iRegion].col;
522				/*
523				 * Delete all following regions
524				 */
525				nRegions = iRegion + 1;
526				return (blankEolStart);
527			}
528			break;
529		case REGION_COMMON:
530			break;
531		case REGION_DELETE:		/* Scrap the whole thing */
532			return (COLS);
533		}
534	}
535	return (COLS);	/* Couldn't use Clear EOL optimization */
536}
537
538/*
539 * Generate output, based on region list
540 */
541static void
542_updateRegions(int row)
543{
544	int	ceolStart;
545	int	iRegion;
546
547	ceolStart = _ceolAdjustRegions(row);
548
549	/*
550	 * regions are guaranteed to start with a non-common region.
551	 * tiny common regions have also been merged into
552	 * bracketting common-regions.
553	 */
554	if (nRegions) {
555		for (iRegion = 0; iRegion < nRegions; iRegion++) {
556			switch (regions[iRegion].type) {
557			case REGION_COMMON:
558				break;
559			case REGION_DELETE:
560				/*
561				 * Start of non-common region
562				 */
563				GOTO(row, regions[iRegion].col);
564				_deleteRegion(row, regions[iRegion]);
565				break;
566			case REGION_DIFFERENT:
567				/*
568				 * Star of non-common region
569				 */
570				GOTO(row, regions[iRegion].col);
571				_writeRegion(row, regions[iRegion]);
572				break;
573			}
574		}
575	}
576	if (ceolStart != COLS) {
577		_clearToEOL(row, ceolStart);
578	}
579}
580
581/*
582 * The new text_replace algorithm, which uses regions
583 */
584static void
585text_replace(int row)
586{
587	if (!_findRegions(row))
588		return;
589	_mergeTinyRegions();
590	_updateRegions(row);
591
592	/*
593	 * Line wrapping checks.
594	 */
595	if (COLS <= curscr->_curx) {
596		--curscr->_curx;
597		if (auto_right_margin && (row < LINES - 1)) {
598			if (eat_newline_glitch) {
599				(void) __m_outc('\r');
600				(void) __m_outc('\n');
601			}
602			++curscr->_cury;
603			curscr->_curx = 0;
604		}
605	}
606}
607
608/*
609 * Replace a block of lines.
610 * Only ever used for complex().
611 */
612static void
613lines_replace(int from, int to_1)
614{
615	for (; from < to_1; ++from)
616		text_replace(from);
617}
618
619/*
620 * Delete a block of lines.
621 * Only ever used for complex().
622 */
623static void
624lines_delete(int from, int to_1)
625{
626	int count = to_1 - from;
627
628	if (LINES <= to_1) {
629		erase_bottom(from, LINES);
630		clear_bottom(from);
631	} else {
632		GOTO(from, 0);
633		(void) winsdelln(curscr, -count);
634
635		if (parm_delete_line != NULL) {
636			/*
637			 * Assume that the sequence to delete more than one
638			 * line is faster than repeated single delete_lines.
639			 */
640			(void) TPUTS(tparm(parm_delete_line, (long)count,
641				0, 0, 0, 0, 0, 0, 0, 0), count, __m_outc);
642		} else if (delete_line != NULL) {
643			while (from++ < to_1)
644				(void) TPUTS(delete_line, 1, __m_outc);
645		} else  {
646			/* Error -- what to do. */
647			return;
648		}
649	}
650}
651
652/*
653 * Insert a block of lines.
654 * Only ever used for complex().
655 *
656 * We must assume that insert_line and parm_insert_line reset the
657 * cursor column to zero.  Therefore it is text_replace() responsiblity
658 * to move the cursor to the correct column to begin the update.
659 */
660static void
661lines_insert(int from, int to_1)
662{
663	int	row;
664	int	count = to_1 - from;
665
666	/*
667	 * Position the cursor and insert a block of lines into the screen
668	 * image now, insert lines into the physical screen, then draw the
669	 * new screen lines.
670	 */
671	GOTO(from, 0);
672	(void) winsdelln(curscr, count);
673
674	if (parm_insert_line != NULL) {
675		/*
676		 * Assume that the sequence to insert more than one line is
677		 * faster than repeated single insert_lines.
678		 */
679		(void) TPUTS(tparm(parm_insert_line, (long)count,
680			0, 0, 0, 0, 0, 0, 0, 0), count, __m_outc);
681	} else if (insert_line != NULL) {
682		/*
683		 * For the single line insert we use to iterate moving
684		 * the cursor, inserting, and then drawing a line.  That
685		 * would appear to be slow but visually appealing.  However,
686		 * people on slow terminals want speed and those on fast
687		 * terminal won't see it.
688		 */
689		for (row = from; row < to_1; ++row)
690			(void) TPUTS(insert_line, 1, __m_outc);
691	} else {
692		/* Error -- what to do. */
693		return;
694	}
695
696	for (row = from; row < to_1; ++row)
697		text_replace(row);
698}
699
700static int
701scroll_up(int n)
702{
703	int	count = n;
704	int	start, finish, to;
705
706	if (scroll_forward != NULL) {
707		GOTO(LINES-1, 0);
708		while (0 < n--)
709			(void) TPUTS(scroll_forward, 1, __m_outc);
710	} else if (parm_delete_line != NULL && 1 < n) {
711		GOTO(0, 0);
712		(void) TPUTS(tparm(parm_delete_line, (long)n,
713			0, 0, 0, 0, 0, 0, 0, 0), n, __m_outc);
714	} else if (delete_line != NULL) {
715		GOTO(0, 0);
716		while (0 < n--)
717			(void) TPUTS(delete_line, 1, __m_outc);
718	} else {
719		return (0);
720	}
721
722	/* Scroll recorded image. */
723	start = 0;
724	finish = count-1;
725	to = lines;
726
727	(void) __m_cc_erase(curscr, start, 0, finish, curscr->_maxx-1);
728	(void) __m_ptr_move((void **) curscr->_line,
729		curscr->_maxy, start, finish, to);
730
731	simple();
732
733	return (1);
734}
735
736#if 0
737static int
738scroll_dn(int n)
739{
740	int	count = n;
741	int	start, finish, to;
742
743	if (LINES < n)
744		return (0);
745
746	if (scroll_reverse != NULL) {
747		GOTO(0, 0);
748		while (0 < n--)
749			(void) TPUTS(scroll_reverse, 1, __m_outc);
750	} else if (parm_insert_line != NULL && 1 < n) {
751		GOTO(0, 0);
752		(void) TPUTS(tparm(parm_insert_line, (long)n,
753			0, 0, 0, 0, 0, 0, 0, 0), n, __m_outc);
754	} else if (insert_line != NULL) {
755		GOTO(0, 0);
756		while (0 < n--)
757			(void) TPUTS(insert_line, 1, __m_outc);
758	} else {
759		return (0);
760	}
761
762	/* Scroll recorded image. */
763	start = lines - count;
764	finish = lines - 1;
765	to = 0;
766
767	(void) __m_cc_erase(curscr, start, 0, finish, curscr->_maxx-1);
768	(void) __m_ptr_move((void **) curscr->_line,
769		curscr->_maxy, start, finish, to);
770
771	simple();
772
773	return (1);
774}
775#endif
776
777/*
778 * Dynamic programming algorithm for the string edit problem.
779 *
780 * This is a modified Gosling cost algorithm that takes into account
781 * null/move operations.
782 *
783 * Costs for move, delete, replace, and insert are 0, 1, 2, and 3
784 * repectively.
785 */
786#define	MOVE_COST	0
787#define	REPLACE_COST	10
788#define	INSERT_COST	12
789#define	DELETE_COST	1
790
791static int
792cost(int fr, int lr)
793{
794	lcost	*lcp;
795	int	or, nr, cc;
796#if defined(_LP64)
797	unsigned int	*ohash = __m_screen->_hash;
798#else
799	unsigned long	*ohash = __m_screen->_hash;
800#endif
801
802	/*
803	 * Prepare initial row and column of cost matrix.
804	 *
805	 *	0 3 6 9 ...
806	 *	1
807	 *	2
808	 *	3
809	 *	:
810	 */
811	LC(fr, fr).cost = MOVE_COST;
812	for (cc = 1, ++lr, nr = fr+1; nr <= lr; ++nr, ++cc) {
813		/* Top row is 3, 6, 9, ... */
814		LC(fr, nr).cost = cc * INSERT_COST;
815		LC(fr, nr).op = 'i';
816
817		/* Left column is 1, 2, 3, ... */
818		LC(nr, fr).cost = cc * DELETE_COST;
819		LC(nr, fr).op = 'd';
820	}
821
822	for (--lr, or = fr; or <= lr; ++or) {
823		for (nr = fr; nr <= lr; ++nr) {
824			lcp = &LC(or + 1, nr + 1);
825
826			/* Assume move op. */
827			lcp->cost = LC(or, nr).cost;
828			lcp->op = 'm';
829
830			if (ohash[or] != nhash[nr]) {
831				/* Lines are different, assume replace op. */
832				lcp->cost += REPLACE_COST;
833				lcp->op = 'r';
834			}
835
836			/* Compare insert op. */
837			if ((cc = LC(or + 1, nr).cost + INSERT_COST) <
838				lcp->cost) {
839				lcp->cost = cc;
840				lcp->op = 'i';
841			}
842
843			/* Compare delete op. */
844			if ((cc = LC(or, nr + 1).cost + DELETE_COST) <
845				lcp->cost) {
846				lcp->cost = cc;
847				lcp->op = 'd';
848			}
849		}
850	}
851
852	return (LC(lr + 1, lr + 1).cost);
853}
854
855/*
856 * Build edit script.
857 *
858 * Normally this would be a recursve routine doing the deletes, inserts,
859 * and replaces on individual lines. Instead we build the script so that
860 * we can later do the operations on a block basis.  For terminals with
861 * parm_delete or parm_insert strings this will be better in terms of the
862 * number of characters sent to delete and insert a block of lines.
863 *
864 * Also we can optimize the script so that tail inserts become replaces.
865 * This saves unnecessary inserts operations when the tail can just be
866 * overwritten.
867 */
868static void
869script(int fr, int lr)
870{
871	int	i, j;
872	cchar_t	*cp;
873
874	i = j = lr + 1;
875
876	(void) memset(del, 0, sizeof (*del) * LINES);
877	(void) memset(ins_rep, 0, sizeof (*ins_rep) * LINES);
878
879	do {
880		/*
881		 * We don't have to bounds check i or j becuase row fr and
882		 * column fr of lc have been preset in order to guarantee the
883		 * correct motion.
884		 */
885		switch (LC(i, j).op) {
886		case 'i':
887			--j;
888			ins_rep[j] = lines_insert;
889			break;
890		case 'd':
891			--i;
892			del[i] = lines_delete;
893			break;
894		case 'm':
895			--i;
896			--j;
897			break;
898		case 'r':
899			--i;
900			--j;
901			ins_rep[j] = lines_replace;
902			break;
903		}
904	} while (fr < i || fr < j);
905
906	/* Optimize Tail Inserts */
907	for (i = LINES-1; 0 <= i && ins_rep[i] == lines_insert; --i) {
908		/* Make each character in the screen line image invalid. */
909		for (cp = curscr->_line[i], j = 0; j < COLS; ++j, ++cp)
910			cp->_n = -1;
911		ins_rep[i] = lines_replace;
912	}
913}
914
915/*
916 * Complex update algorithm using insert/delete line operations.
917 *
918 * References:
919 * [MyM86]	E.W. Myers & W. Miller, Row Replacement Algorithms for
920 *		Screen Editors, TR 86-19, Dept. Computer Science, U. of Arizona
921 * [MyM87]	E.W. Myers & W. Miller, A Simple Row Replacement Method,
922 *		TR 86-28, Dept. Computer Science, U. of Arizona
923 * [Mil87]	W. Miller, A Software Tools Sampler, Prentice-Hall, 1987
924 * [Gos81]	James Gosling, A redisplay algorithm, Proceedings of the
925 *		ACM Symposium on Text Manipulation, SIGPLAN Notices,
926 *		16(6) June 1981, pg 123-129
927 *
928 * All the above were reviewed and experimented with.  Due to the nature of
929 * Curses' having to handling overlapping WINDOWs, the only suitable
930 * algorithum is [Gos81].  The others are better suited to editor type
931 * applications that have one window being the entire terminal screen.
932 *
933 */
934static void
935complex(void)
936{
937	int	fr = -1;
938	int	i, j, lr;
939	t_action	func;
940
941	/* Find block of lines to change */
942	for (i = 0; i < LINES; ++i) {
943		if (newscr->_first[i] < newscr->_last[i]) {
944			/* Compute new hash. */
945			__m_cc_hash(newscr, nhash, i);
946			if (fr == -1)
947				fr = i;
948			lr = i;
949		} else {
950			/* Line not dirty so hash same as before. */
951			nhash[i] = __m_screen->_hash[i];
952		}
953	}
954
955	if (fr != -1) {
956		/* Gosling */
957		(void) cost(fr, lr);
958		script(fr, lr);
959
960		/* Do deletes first in reverse order. */
961		for (j = lr; fr <= j; --j) {
962			if (del[j] != (t_action) 0) {
963				for (i = j-1; fr <= i; --i)
964					if (del[i] == (t_action) 0)
965						break;
966
967				lines_delete(i+1, j+1);
968				j = i;
969			}
970		}
971
972		/* Do insert/replace in forward order. */
973		for (i = fr; i <= lr; ++i) {
974			if ((func = ins_rep[i]) != (t_action) 0) {
975				/* Find size of block */
976				for (j = i; j <= lr && ins_rep[j] == func; ++j)
977					;
978				(*func)(i, j);
979				i = j - 1;
980			}
981		}
982		/*
983		 * _line[], which contains pointers to screen lines,
984		 * may be shuffled.
985		 */
986		for (i = fr; i <= lr; ++i) {
987			/* Save new hash for next update. */
988			__m_screen->_hash[i] = nhash[i];
989
990			/* Mark line as untouched. */
991			newscr->_first[i] = newscr->_maxx;
992			newscr->_last[i] = -1;
993		}
994	}
995}
996
997/*
998 * Simple screen update algorithm
999 *
1000 * We perform a simple incremental update of the terminal screen.
1001 * Only the segment of a line that was touched is replaced on the
1002 * line.
1003 */
1004static void
1005simple(void)
1006{
1007	int row;
1008
1009	for (row = 0; row < newscr->_maxy; ++row) {
1010		if (newscr->_first[row] < newscr->_last[row]) {
1011			text_replace(row);
1012
1013			/* Mark line as untouched. */
1014			newscr->_first[row] = newscr->_maxx;
1015			newscr->_last[row] = -1;
1016			__m_cc_hash(curscr, __m_screen->_hash, row);
1017		}
1018	}
1019
1020	newscr->_flags &= ~W_REDRAW_WINDOW;
1021}
1022
1023void
1024wtouchln_hard(WINDOW *w, int y, int n)
1025{
1026	int	last;
1027
1028	last = w->_maxx;
1029
1030	for (; (y < w->_maxy) && (0 < n); ++y, --n) {
1031		/*
1032		 * Force compare in doupdate to fail.
1033		 * Touch should be unconditional
1034		 */
1035(void) memset(&__m_screen->_curscr->_line[w->_begy + y][w->_begx],
1036	0xff, last * sizeof (cchar_t));
1037	}
1038}
1039/*
1040 * Send all changes made to _newscr to the physical terminal.
1041 *
1042 * If idlok() is set TRUE then doupdate will try and use hardware insert
1043 * and delete line sequences in an effort to optimize output.  idlok()
1044 * should really only be used in applications that want a proper scrolling
1045 * effect.
1046 *
1047 * Added scroll heuristic to handle special case where a full size window
1048 * with full size scroll region, will scroll the window and replace dirty
1049 * lines instead of performing usual cost/script operations.
1050 */
1051int
1052doupdate(void)
1053{
1054#ifdef SIGTSTP
1055	int (*oldsig)(int) = signal(SIGTSTP, SIG_IGN);
1056#endif
1057
1058	if (pollTypeahead()) {
1059		return (OK);
1060	}
1061	newscr = __m_screen->_newscr;
1062
1063	if (__m_screen->_flags & S_ENDWIN) {
1064		/* Return from temporary escape done with endwin(). */
1065		__m_screen->_flags &= ~S_ENDWIN;
1066
1067		(void) reset_prog_mode();
1068		if (enter_ca_mode != NULL)
1069			(void) TPUTS(enter_ca_mode, 1, __m_outc);
1070		if (keypad_xmit != NULL)
1071			(void) TPUTS(keypad_xmit, 1, __m_outc);
1072		if (ena_acs != NULL)
1073			(void) TPUTS(ena_acs, 1, __m_outc);
1074
1075		/* Force redraw of screen. */
1076		newscr->_flags |= W_CLEAR_WINDOW;
1077	}
1078	/*
1079	 * When redrawwing a window, we not only assume that line
1080	 * noise may have lost characters, but line noise may have
1081	 * generated bogus characters on the screen outside the
1082	 * the window in question, in which case redraw the entire
1083	 * screen to be sure.
1084	 */
1085	if ((newscr->_flags & (W_CLEAR_WINDOW | W_REDRAW_WINDOW)) ||
1086		(curscr->_flags & W_CLEAR_WINDOW)) {
1087		erase_bottom(0, newscr->_maxy);
1088		clear_bottom(0);
1089		(void) wtouchln(newscr, 0, newscr->_maxy, 1);
1090		newscr->_flags &= ~W_CLEAR_WINDOW;
1091		curscr->_flags &= ~W_CLEAR_WINDOW;
1092	}
1093
1094	/*
1095	 * Scrolling heuristic should only be used if lines being
1096	 * scrolled are clean because scrolling overrides updates
1097	 *
1098	 * Right now, the following code should always turn off
1099	 * scrolling, because the internal scroll touches the
1100	 * scrolled lines. This thing requires a lot more care
1101	 * than I have right now...
1102	 */
1103	if (newscr->_scroll) {
1104		int	y;
1105		for (y = 0; y < newscr->_maxy; ++y) {
1106			if (0 <= newscr->_last[y]) {
1107				newscr->_scroll = 0;
1108			}
1109		}
1110		newscr->_scroll = 0;	/* Just fudge it for now ... */
1111	}
1112	if (newscr->_flags & W_REDRAW_WINDOW) {
1113		simple();
1114	} else {
1115		if (newscr->_scroll == 0) {
1116			if (__m_screen->_flags & S_INS_DEL_LINE) {
1117				complex();
1118			} else {
1119				simple();
1120			}
1121		} else {
1122			if (!scroll_up(newscr->_scroll)) {
1123				if (__m_screen->_flags & S_INS_DEL_LINE) {
1124					complex();
1125				} else {
1126					simple();
1127				}
1128			}
1129		}
1130	}
1131
1132	if (!(newscr->_flags & W_LEAVE_CURSOR))	{
1133		GOTO(newscr->_cury, newscr->_curx);
1134	}
1135
1136	if (!(curscr->_flags & W_FLUSH)) {
1137		(void) fflush(__m_screen->_of);
1138	}
1139
1140	newscr->_scroll = curscr->_scroll = 0;
1141
1142	/* Send labels to terminal that supports them. */
1143	__m_slk_doupdate();
1144#ifdef SIGTSTP
1145	signal(SIGTSTP, oldsig);
1146#endif
1147
1148	return (OK);
1149}
1150
1151/*
1152 * If true, the implementation may use hardware insert and delete,
1153 * character features of the terminal.  The window parameter
1154 * is ignored.
1155 */
1156/* ARGSUSED */
1157void
1158idcok(WINDOW *w, bool bf)
1159{
1160	__m_screen->_flags &= ~S_INS_DEL_CHAR;
1161	if (bf)
1162		__m_screen->_flags |= S_INS_DEL_CHAR;
1163}
1164
1165/*
1166 * If true, the implementation may use hardware insert, delete,
1167 * and scroll line features of the terminal.  The window parameter
1168 * is ignored.
1169 */
1170/* ARGSUSED */
1171int
1172idlok(WINDOW *w, bool bf)
1173{
1174	__m_screen->_flags &= ~S_INS_DEL_LINE;
1175	if (bf && has_il())
1176		__m_screen->_flags |= S_INS_DEL_LINE;
1177
1178	return (OK);
1179}
1180
1181/*
1182 * Use the POSIX 32-bit CRC function to compute a hash value
1183 * for the window line.
1184 */
1185void
1186#if defined(_LP64)
1187__m_cc_hash(WINDOW *w, unsigned int *array, int y)
1188#else
1189__m_cc_hash(WINDOW *w, unsigned long *array, int y)
1190#endif
1191{
1192	array[y] = 0;
1193	m_crcposix(&array[y], (unsigned char *) w->_line[y],
1194		(size_t)(w->_maxx * sizeof (**w->_line)));
1195}
1196