![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to scroll.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / emacs / src|
Return to scroll.c CVS log | Up to [Apple XNU] / GNUtools / emacs / src |
1.1 root 1: /* Calculate what ins/del line to do, and do it, for Emacs redisplay.
2: Copyright (C) 1985, 1986, 1990 Free Software Foundation, Inc.
3:
4: This file is part of GNU Emacs.
5:
6: GNU Emacs is free software; you can redistribute it and/or modify
7: it under the terms of the GNU General Public License as published by
8: the Free Software Foundation; either version 1, or (at your option)
9: any later version.
10:
11: GNU Emacs is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14: GNU General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with GNU Emacs; see the file COPYING. If not, write to
18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20:
21: #include <stdio.h>
22: #include "config.h"
23: #include "termchar.h"
24: #include "termhooks.h"
25: #include "dispextern.h"
26:
27: #define max(a, b) ((a) > (b) ? (a) : (b))
28: #define min(a, b) ((a) < (b) ? (a) : (b))
29:
30: struct matrix_elt
31: {
32: /* Cost of outputting through this line
33: if no insert/delete is done just above it. */
34: int writecost;
35: /* Cost of outputting through this line
36: if an insert is done just above it. */
37: int insertcost;
38: /* Cost of outputting through this line
39: if a delete is done just above it. */
40: int deletecost;
41: /* Number of inserts so far in this run of inserts,
42: for the cost in insertcost. */
43: char insertcount;
44: /* Number of deletes so far in this run of deletes,
45: for the cost in deletecost. */
46: char deletecount;
47: };
48:
49: /* This exceeds the sum of any reasonable number of INFINITY's. */
50: #define SUPER_INFINITY (1000 * INFINITY)
51:
52: /* See CalcIDCosts for on the arrays below */
53: int *ILcost;
54: int *DLcost;
55: int *ILncost;
56: int *DLncost;
57:
58: scrolling_1 (window_size, unchanged_at_top, unchanged_at_bottom,
59: draw_cost, old_hash, new_hash, free_at_end)
60: int window_size, unchanged_at_top, unchanged_at_bottom;
61: int *draw_cost;
62: int *old_hash;
63: int *new_hash;
64: int free_at_end;
65: {
66: struct matrix_elt *matrix;
67: matrix = ((struct matrix_elt *)
68: alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
69:
70: calculate_scrolling (matrix, window_size, unchanged_at_bottom,
71: draw_cost, old_hash, new_hash,
72: free_at_end);
73: do_scrolling (matrix, window_size, unchanged_at_top);
74: }
75:
76: /* Determine, in matrix[i,j], the cost of updating the first j old lines
77: into the first i new lines.
78: This involves using insert or delete somewhere if i != j.
79: For each matrix elements, three kinds of costs are recorded:
80: the smallest cost that ends with an insert, the smallest
81: cost that ends with a delete, and the smallest cost that
82: ends with neither one. These are kept separate because
83: on some terminals the cost of doing an insert varies
84: depending on whether one was just done, etc. */
85:
86: /* draw_cost[VPOS] is the cost of outputting new line at VPOS.
87: old_hash[VPOS] is the hash code of the old line at VPOS.
88: new_hash[VPOS] is the hash code of the new line at VPOS.
89: Note that these are not true screen vpos's, but relative
90: to the place at which the first mismatch between old and
91: new contents appears. */
92:
93: calculate_scrolling (matrix, window_size, lines_below,
94: draw_cost, old_hash, new_hash,
95: free_at_end)
96: /* matrix is of size window_size + 1 on each side. */
97: struct matrix_elt *matrix;
98: int window_size;
99: int *draw_cost;
100: int *old_hash;
101: int *new_hash;
102: int free_at_end;
103: {
104: register int i, j;
105: register struct matrix_elt *p, *p1;
106: register int cost, cost1;
107:
108: int lines_moved = window_size + (scroll_region_ok ? 0 : lines_below);
109: /* We subtract 1 to compensate for the fact that i and j have values
110: starting with 1. */
111: int *first_insert_cost = &ILcost[screen_height - lines_moved - 1];
112: int *first_delete_cost = &DLcost[screen_height - lines_moved - 1];
113: int *next_insert_cost = &ILncost[screen_height - lines_moved - 1];
114: int *next_delete_cost = &DLncost[screen_height - lines_moved - 1];
115:
116: /* initialize the top left corner of the matrix */
117: matrix->writecost = 0;
118: matrix->insertcost = SUPER_INFINITY;
119: matrix->deletecost = SUPER_INFINITY;
120: matrix->insertcount = 0;
121: matrix->deletecount = 0;
122:
123: /* initialize the left edge of the matrix */
124: cost = first_insert_cost[1] - next_insert_cost[1];
125: for (i = 1; i <= window_size; i++)
126: {
127: p = matrix + i * (window_size + 1);
128: cost += draw_cost[i] + next_insert_cost[i];
129: p->insertcost = cost;
130: p->writecost = SUPER_INFINITY;
131: p->deletecost = SUPER_INFINITY;
132: p->insertcount = i;
133: p->deletecount = 0;
134: }
135:
136: /* initialize the top edge of the matrix */
137: cost = first_delete_cost[1] - next_delete_cost[1];
138: for (j = 1; j <= window_size; j++)
139: {
140: cost += next_delete_cost[j];
141: matrix[j].deletecost = cost;
142: matrix[j].writecost = SUPER_INFINITY;
143: matrix[j].insertcost = SUPER_INFINITY;
144: matrix[j].deletecount = j;
145: matrix[j].insertcount = 0;
146: }
147:
148: /* `i' represents the vpos among new screen contents.
149: `j' represents the vpos among the old screen contents. */
150: p = matrix + window_size + 2; /* matrix [1, 1] */
151: for (i = 1; i <= window_size; i++, p++)
152: for (j = 1; j <= window_size; j++, p++)
153: {
154: /* p contains the address of matrix [i, j] */
155:
156: /* First calculate the cost assuming we do
157: not insert or delete above this line.
158: That is, if we update through line i-1
159: based on old lines through j-1,
160: and then just change old line j to new line i. */
161: p1 = p - window_size - 2; /* matrix [i-1, j-1] */
162: cost = p1->writecost;
163: if (cost > p1->insertcost)
164: cost = p1->insertcost;
165: if (cost > p1->deletecost)
166: cost = p1->deletecost;
167: if (old_hash[j] != new_hash[i])
168: cost += draw_cost[i];
169: p->writecost = cost;
170:
171: /* Calculate the cost if we do an insert-line
172: before outputting this line.
173: That is, we update through line i-1
174: based on old lines through j,
175: do an insert-line on line i,
176: and then output line i from scratch,
177: leaving old lines starting from j for reuse below. */
178: p1 = p - window_size - 1; /* matrix [i-1, j] */
179: /* No need to think about doing a delete followed
180: immediately by an insert. It cannot be as good
181: as not doing either of them. */
182: if (free_at_end == i)
183: {
184: cost = p1->writecost;
185: cost1 = p1->insertcost;
186: }
187: else
188: {
189: cost = p1->writecost + first_insert_cost[i];
190: if (p1->insertcount > i)
191: abort ();
192: cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
193: }
194: p->insertcost = min (cost, cost1) + draw_cost[i];
195: p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
196: if (p->insertcount > i)
197: abort ();
198:
199: /* Calculate the cost if we do a delete line after
200: outputting this line.
201: That is, we update through line i
202: based on old lines through j-1,
203: and throw away old line j. */
204: p1 = p - 1; /* matrix [i, j-1] */
205: /* No need to think about doing an insert followed
206: immediately by a delete. */
207: if (free_at_end == i)
208: {
209: cost = p1->writecost;
210: cost1 = p1->deletecost;
211: }
212: else
213: {
214: cost = p1->writecost + first_delete_cost[i];
215: cost1 = p1->deletecost + next_delete_cost[i];
216: }
217: p->deletecost = min (cost, cost1);
218: p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1;
219: }
220: }
221:
222: /* Perform insert-lines and delete-lines operations
223: according to the costs in the matrix.
224: Updates the contents of current_screen to record what was done. */
225:
226: do_scrolling (matrix, window_size, unchanged_at_top)
227: struct matrix_elt *matrix;
228: int window_size;
229: int unchanged_at_top;
230: {
231: register struct matrix_elt *p;
232: register int i, j;
233: struct queue { int count, pos; } *queue;
234: int offset = unchanged_at_top;
235: int qi = 0;
236: int window = 0;
237: register int tem;
238: int next;
239:
240: queue = (struct queue *) alloca (screen_height * sizeof (struct queue));
241:
242: bcopy (current_screen->contents, temp_screen->contents,
243: current_screen->height * sizeof (char *));
244: bcopy (current_screen->used, temp_screen->used,
245: current_screen->height * sizeof (int));
246: bcopy (current_screen->highlight, temp_screen->highlight,
247: current_screen->height);
248: bzero (temp_screen->enable, temp_screen->height);
249:
250: /* First do all deletions of lines; queue up insertions.
251: Also move lines to correct slots in current_screen. */
252:
253: i = j = window_size;
254:
255: while (i > 0 || j > 0)
256: {
257: p = matrix + i * (window_size + 1) + j;
258: tem = p->insertcost;
259: if (tem < p->writecost && tem < p->deletecost)
260: {
261: /* Insert should be done at vpos i-1, plus maybe some before */
262: queue[qi].count = p->insertcount;
263: i -= p->insertcount;
264: queue[qi++].pos = i + unchanged_at_top;
265: }
266: else if (p->deletecost < p->writecost)
267: {
268: /* Old line at vpos j-1, and maybe some before it,
269: should be deleted */
270: j -= p->deletecount;
271: if (!window)
272: {
273: set_terminal_window (window_size + unchanged_at_top);
274: window = 1;
275: }
276: ins_del_lines (j + unchanged_at_top, - p->deletecount);
277: }
278: else
279: {
280: /* Best thing done here is no insert or delete */
281: /* Old line at vpos j-1 ends up at vpos i-1 */
282: current_screen->contents[i + offset - 1]
283: = temp_screen->contents[j + offset - 1];
284: current_screen->used[i + offset - 1]
285: = temp_screen->used[j + offset - 1];
286: current_screen->highlight[i + offset - 1]
287: = temp_screen->highlight[j + offset - 1];
288:
289: temp_screen->enable[j + offset - 1] = 1;
290: i--;
291: j--;
292: }
293: }
294:
295: if (!window && qi)
296: {
297: set_terminal_window (window_size + unchanged_at_top);
298: window = 1;
299: }
300:
301: /* Now do all insertions */
302:
303: next = unchanged_at_top;
304: for (i = qi - 1; i >= 0; i--)
305: {
306: ins_del_lines (queue[i].pos, queue[i].count);
307: /* Mark the inserted lines as clear,
308: and put into them the line-contents strings
309: that were discarded during the deletions.
310: Those are the ones for which temp_screen->enable was not set. */
311: tem = queue[i].pos;
312: for (j = tem + queue[i].count - 1; j >= tem; j--)
313: {
314: current_screen->enable[j] = 0;
315: while (temp_screen->enable[next]) next++;
316: current_screen->contents[j] = temp_screen->contents[next++];
317: }
318: }
319:
320: if (window)
321: set_terminal_window (0);
322: }
323:
324: /* Return number of lines in common between current screen contents
325: and the text to be displayed,
326: considering only vpos range START to END (not including END).
327: Ignores short lines (length < 20) on the assumption that
328: avoiding redrawing such a line will have little weight. */
329:
330: int
331: scrolling_max_lines_saved (start, end, oldhash, newhash, cost)
332: int start, end;
333: int *oldhash, *newhash, *cost;
334: {
335: struct { int hash; int count; } lines[01000];
336: register int i, h;
337: register int matchcount = 0;
338:
339: bzero (lines, sizeof lines);
340:
341: /* Put new lines' hash codes in hash table. */
342: for (i = start; i < end; i++)
343: {
344: if (cost[i] > 20)
345: {
346: h = newhash[i] & 0777;
347: lines[h].hash = newhash[i];
348: lines[h].count++;
349: }
350: }
351:
352: /* Look up old line hash codes in the hash table.
353: Count number of matches between old lines and new. */
354:
355: for (i = start; i < end; i++)
356: {
357: h = oldhash[i] & 0777;
358: if (oldhash[i] == lines[h].hash)
359: {
360: matchcount++;
361: if (--lines[h].count == 0)
362: lines[h].hash = 0;
363: }
364: }
365:
366: return matchcount;
367: }
368:
369: /* Return a measure of the cost of moving the lines
370: starting with vpos FROM, up to but not including vpos TO,
371: down by AMOUNT lines (AMOUNT may be negative).
372: These are the same arguments that might be given to
373: scroll_screen_lines to perform this scrolling. */
374:
375: scroll_cost (from, to, amount)
376: int from, to, amount;
377: {
378: /* Compute how many lines, at bottom of screen,
379: will not be involved in actual motion. */
380: int ok_below = screen_height - to;
381: if (amount > 0) ok_below -= amount;
382: if (! scroll_region_ok) ok_below = 0;
383:
384: if (amount == 0)
385: return 0;
386:
387: if (amount < 0)
388: {
389: int temp = to;
390: to = from + amount;
391: from = temp + amount;
392: amount = - amount;
393: }
394:
395: from += ok_below;
396: to += ok_below;
397:
398: return (ILcost[from] + (amount - 1) * ILncost[from]
399: + DLcost[to] + (amount - 1) * DLncost[to]);
400: }
401:
402: /* Calculate the insert and delete line costs.
403:
404: We keep the ID costs in a precomputed array based on the position
405: at which the I or D is performed. Also, there are two kinds of ID
406: costs: the "once-only" and the "repeated". This is to handle both
407: those terminals that are able to insert N lines at a time (once-
408: only) and those that must repeatedly insert one line.
409:
410: The cost to insert N lines at line L is
411: [tt.t_ILov + (screen_height + 1 - L) * tt.t_ILpf] +
412: N * [tt.t_ILnov + (screen_height + 1 - L) * tt.t_ILnpf]
413:
414: ILov represents the basic insert line overhead. ILpf is the padding
415: required to allow the terminal time to move a line: insertion at line
416: L changes (screen_height + 1 - L) lines.
417:
418: The first bracketed expression above is the overhead; the second is
419: the multiply factor. Both are dependent only on the position at
420: which the insert is performed. We store the overhead in ILcost and
421: the multiply factor in ILncost. Note however that any insertion
422: must include at least one multiply factor. Rather than compute this
423: as ILcost[line]+ILncost[line], we add ILncost into ILcost. This is
424: reasonable because of the particular algorithm used in calcM.
425:
426: Deletion is essentially the same as insertion.
427: */
428:
429: CalcIDCosts (ins_line_string, multi_ins_string,
430: del_line_string, multi_del_string,
431: setup_string, cleanup_string)
432: char *ins_line_string, *multi_ins_string;
433: char *del_line_string, *multi_del_string;
434: char *setup_string, *cleanup_string;
435: {
436: /* Discourage long scrolls slightly on fast lines.
437: This says that scrolling nearly the full length of the screen
438: is not worth it if reprinting takes less than 1/4 second. */
439: int extra = baud_rate / (10 * 4 * screen_height);
440:
441: if (ILcost != 0)
442: {
443: ILcost = (int *) xrealloc (ILcost, screen_height * sizeof (int));
444: DLcost = (int *) xrealloc (DLcost, screen_height * sizeof (int));
445: ILncost = (int *) xrealloc (ILncost, screen_height * sizeof (int));
446: DLncost = (int *) xrealloc (DLncost, screen_height * sizeof (int));
447: }
448: else
449: {
450: ILcost = (int *) xmalloc (screen_height * sizeof (int));
451: DLcost = (int *) xmalloc (screen_height * sizeof (int));
452: ILncost = (int *) xmalloc (screen_height * sizeof (int));
453: DLncost = (int *) xmalloc (screen_height * sizeof (int));
454: }
455:
456: CalcIDCosts1 (ins_line_string, multi_ins_string,
457: setup_string, cleanup_string,
458: ILcost, ILncost, extra);
459: CalcIDCosts1 (del_line_string, multi_del_string,
460: setup_string, cleanup_string,
461: DLcost, DLncost, 0);
462: }
463:
464: CalcIDCosts1 (one_line_string, multi_string,
465: setup_string, cleanup_string,
466: costvec, ncostvec, extra)
467: char *one_line_string, *multi_string;
468: char *setup_string, *cleanup_string;
469: int *costvec, *ncostvec;
470: int extra;
471: {
472: if (calculate_costs_hook)
473: (*calculate_costs_hook) (extra, costvec, ncostvec);
474: else if (dont_calculate_costs)
475: CalcLID (0, 0, 0, 0, costvec, ncostvec);
476: else if (multi_string)
477: CalcLID (string_cost (multi_string),
478: per_line_cost (multi_string),
479: extra, 0, costvec, ncostvec);
480: else if (one_line_string)
481: CalcLID (string_cost (setup_string) + string_cost (cleanup_string), 0,
482: string_cost (one_line_string) + extra,
483: per_line_cost (one_line_string),
484: costvec, ncostvec);
485: else
486: CalcLID (9999, 0, 9999, 0,
487: costvec, ncostvec);
488: }
489:
490: /* Calculate the line ID overhead and multiply factor values */
491: CalcLID (ov1, pf1, ovn, pfn, ov, mf)
492: int ov1, ovn;
493: int pf1, pfn;
494: register int *ov, *mf;
495: {
496: register int i;
497: register int insert_overhead = ov1 * 10 + screen_height * pf1;
498: register int next_insert_cost = ovn * 10 + screen_height * pfn;
499:
500: for (i = 0; i < screen_height; i++)
501: {
502: *mf++ = next_insert_cost / 10;
503: next_insert_cost -= pfn;
504: *ov++ = (insert_overhead + next_insert_cost) / 10;
505: insert_overhead -= pf1;
506: }
507: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.