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
42 static 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
72 typedef struct cost_op {
73 short cost;
74 short op;
75 } lcost;
76
77 typedef void (*t_action)(int, int);
78
79
80 #define LC(i, j) (lc[(i) * (LINES + 1) + (j)])
81
82 static lcost *lc = NULL;
83 #if defined(_LP64)
84 static unsigned int *nhash = NULL;
85 #else
86 static unsigned long *nhash = NULL;
87 #endif
88 static t_action *del = NULL;
89 static t_action *ins_rep = NULL;
90
91 static WINDOW *newscr;
92
93 static void erase_bottom(int, int);
94 static void clear_bottom(int);
95 static void complex(void);
96 static int cost(int, int);
97 static void lines_delete(int, int);
98 static void lines_insert(int, int);
99 static void lines_replace(int, int);
100 static void script(int, int);
101 static int scroll_up(int);
102 static void simple(void);
103 static void text_replace(int);
104 #if 0
105 static 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 */
115 int
__m_outc(int ch)116 __m_outc(int ch)
117 {
118 return (putc(ch, __m_screen->_of));
119 }
120
121 /*
122 * Allocate or grow doupdate() structures.
123 */
124 int
__m_doupdate_init(void)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
167 static void
erase_bottom(int start,int end)168 erase_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 */
181 static void
clear_bottom(int y)182 clear_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 */
219 typedef 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
232 static LineRegion regions[1024];
233 int nRegions = 0;
234
235 /*
236 * Return the first column of the completely blank End-of-line
237 */
238 static int
_find_blank_tail(int row)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 */
260 static void
_writeRegion(int row,LineRegion region)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 */
297 static void
_deleteRegion(int row,LineRegion region)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 */
322 static void
_clearToEOL(int row,int tail)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 */
341 static void
_normalizeRegions1(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 */
360 static void
_normalizeRegions2(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 */
381 static void
_mergeTinyRegions(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 */
408 static int
_findRegions(int row)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 */
498 static int
_ceolAdjustRegions(int row)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 */
541 static void
_updateRegions(int row)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 */
584 static void
text_replace(int row)585 text_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 */
612 static void
lines_replace(int from,int to_1)613 lines_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 */
623 static void
lines_delete(int from,int to_1)624 lines_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 */
660 static void
lines_insert(int from,int to_1)661 lines_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
700 static int
scroll_up(int n)701 scroll_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
737 static int
738 scroll_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
791 static int
cost(int fr,int lr)792 cost(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 */
868 static void
script(int fr,int lr)869 script(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 */
934 static void
complex(void)935 complex(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 */
1004 static void
simple(void)1005 simple(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
1023 void
wtouchln_hard(WINDOW * w,int y,int n)1024 wtouchln_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 */
1051 int
doupdate(void)1052 doupdate(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 */
1157 void
idcok(WINDOW * w,bool bf)1158 idcok(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 */
1171 int
idlok(WINDOW * w,bool bf)1172 idlok(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 */
1185 void
1186 #if defined(_LP64)
__m_cc_hash(WINDOW * w,unsigned int * array,int y)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