![[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 [CSRG BSD Unix] / 43BSD / contrib / emacs / src|
Return to scroll.c CVS log | Up to [CSRG BSD Unix] / 43BSD / contrib / emacs / src |
1.1 root 1: /* Calculate what ins/del line to do, and do it, for Emacs redisplay.
2: Copyright (C) 1985 Richard M. Stallman.
3:
4: This file is part of GNU Emacs.
5:
6: GNU Emacs is distributed in the hope that it will be useful,
7: but WITHOUT ANY WARRANTY. No author or distributor
8: accepts responsibility to anyone for the consequences of using it
9: or for whether it serves any particular purpose or works at all,
10: unless he says so in writing. Refer to the GNU Emacs General Public
11: License for full details.
12:
13: Everyone is granted permission to copy, modify and redistribute
14: GNU Emacs, but only under the conditions described in the
15: GNU Emacs General Public License. A copy of this license is
16: supposed to have been given to you along with GNU Emacs so you
17: can know your rights and responsibilities. It should be in a
18: file named COPYING. Among other things, the copyright notice
19: and this notice must be preserved on all copies. */
20:
21:
22: #include "config.h"
23: #include "termchar.h"
24: #include "dispextern.h"
25:
26: #define max(a, b) ((a) > (b) ? (a) : (b))
27: #define min(a, b) ((a) < (b) ? (a) : (b))
28:
29: /* All costs measured in characters. Therefore, no cost
30: can exceed MScreenLength * MScreenWidth (or so).
31: That is about 10000, which fits in a short. */
32:
33: #define INFINITY 15000
34:
35: struct matrix_elt
36: {
37: /* Cost of outputting through this line
38: if no insert/delete is done just above it. */
39: short writecost;
40: /* Cost of outputting through this line
41: if an insert is done just above it. */
42: short insertcost;
43: /* Cost of outputting through this line
44: if a delete is done just above it. */
45: short deletecost;
46: /* Number of inserts so far in this run of inserts,
47: for the cost in insertcost. */
48: char insertcount;
49: /* Number of deletes so far in this run of deletes,
50: for the cost in deletecost. */
51: char deletecount;
52: };
53:
54: /* See CalcIDCosts for on the arrays below */
55: int ILcost[MScreenLength];/* ov(n) + 1*mf(n) */
56: int DLcost[MScreenLength];/* ov(n) + 1*mf(n) */
57: int ILncost[MScreenLength];/* mf(n) */
58: int DLncost[MScreenLength];/* mf(n) */
59:
60: scrolling_1 (window_size, unchanged_at_top, unchanged_at_bottom,
61: draw_cost, old_hash, new_hash, free_at_end)
62: int window_size, unchanged_at_top, unchanged_at_bottom;
63: int *draw_cost;
64: int *old_hash;
65: int *new_hash;
66: int free_at_end;
67: {
68: struct matrix_elt *matrix;
69: matrix = ((struct matrix_elt *)
70: alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
71:
72: calculate_scrolling (matrix, window_size, unchanged_at_bottom,
73: draw_cost, old_hash, new_hash,
74: free_at_end);
75: do_scrolling (matrix, window_size, unchanged_at_top);
76: }
77:
78: /* Determine, in matrix[i,j], the cost of updating the first j old lines
79: into the first i new lines.
80: This involves using insert or delete somewhere if i != j.
81: For each matrix elements, three kinds of costs are recorded:
82: the smallest cost that ends with an insert, the smallest
83: cost that ends with a delete, and the smallest cost that
84: ends with neither one. These are kept separate because
85: on some terminals the cost of doing an insert varies
86: depending on whether one was just done, etc. */
87:
88: /* draw_cost[VPOS] is the cost of outputting new line at VPOS.
89: old_hash[VPOS] is the hash code of the old line at VPOS.
90: new_hash[VPOS] is the hash code of the new line at VPOS.
91: Note that these are not true screen vpos's, but relative
92: to the place at which the first mismatch between old and
93: new contents appears. */
94:
95: calculate_scrolling (matrix, window_size, lines_below,
96: draw_cost, old_hash, new_hash,
97: free_at_end)
98: /* matrix is of size window_size + 1 on each side. */
99: struct matrix_elt *matrix;
100: int window_size;
101: int *draw_cost;
102: int *old_hash;
103: int *new_hash;
104: int free_at_end;
105: {
106: register int i, j;
107: register struct matrix_elt *p, *p1;
108: register int cost, cost1;
109:
110: int lines_moved = window_size + (scroll_region_ok ? 0 : lines_below);
111: int *first_insert_cost = &ILcost[screen_height - lines_moved];
112: int *first_delete_cost = &DLcost[screen_height - lines_moved];
113: int *next_insert_cost = &ILncost[screen_height - lines_moved];
114: int *next_delete_cost = &DLncost[screen_height - lines_moved];
115:
116: /* initialize the top left corner of the matrix */
117: matrix->writecost = 0;
118: matrix->insertcost = INFINITY;
119: matrix->deletecost = 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 = INFINITY;
131: p->deletecost = 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 = INFINITY;
143: matrix[j].insertcost = INFINITY;
144: matrix[j].deletecount = j;
145: matrix[j].insertcount = j;
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: cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
191: }
192: p->insertcost = min (cost, cost1) + draw_cost[i];
193: p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
194:
195: /* Calculate the cost if we do a delete line after
196: outputting this line.
197: That is, we update through line i
198: based on old lines through j-1,
199: and throw away old line j. */
200: p1 = p - 1; /* matrix [i, j-1] */
201: /* No need to think about doing an insert followed
202: immediately by a delete. */
203: if (free_at_end == i)
204: {
205: cost = p1->writecost;
206: cost1 = p1->deletecost;
207: }
208: else
209: {
210: cost = p1->writecost + first_delete_cost[i];
211: cost1 = p1->deletecost + next_delete_cost[i];
212: }
213: p->deletecost = min (cost, cost1);
214: p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1;
215: }
216: }
217:
218: /* Perform insert-lines and delete-lines operations
219: according to the costs in the matrix.
220: Updates the contents of PhysScreen to record what was done. */
221:
222: do_scrolling (matrix, window_size, unchanged_at_top)
223: struct matrix_elt *matrix;
224: int window_size;
225: int unchanged_at_top;
226: {
227: register struct matrix_elt *p;
228: register int i, j;
229: struct { int count, pos; } queue[MScreenLength];
230: int offset = unchanged_at_top;
231: int qi = 0;
232: int window = 0;
233: register int tem;
234: extern struct display_line *PhysScreen[MScreenLength + 1];
235: extern struct display_line *OPhysScreen[MScreenLength + 1];
236:
237: /* First do all deletions of lines; queue up insertions.
238: Also move lines to correct slots in PhysScreen */
239:
240: i = j = window_size;
241:
242: while (i > 0 || j > 0)
243: {
244: p = matrix + i * (window_size + 1) + j;
245: tem = p->insertcost;
246: if (tem < p->writecost && tem < p->deletecost)
247: {
248: /* Insert should be done at vpos i-1, plus maybe some before */
249: queue[qi].count = p->insertcount;
250: i -= p->insertcount;
251: queue[qi++].pos = i + unchanged_at_top;
252: }
253: else if (p->deletecost < p->writecost)
254: {
255: /* Old line at vpos j-1, and maybe some before it,
256: should be deleted */
257: j -= p->deletecount;
258: if (!window)
259: {
260: set_terminal_window (window_size + unchanged_at_top);
261: window = 1;
262: }
263: ins_del_lines (j + unchanged_at_top, - p->deletecount);
264: }
265: else
266: {
267: /* Best thing done here is no insert or delete */
268: /* Old line at vpos j-1 ends up at vpos i-1 */
269: PhysScreen[i + offset] = OPhysScreen[j + offset];
270: i--;
271: j--;
272: }
273: }
274:
275: if (!window && qi)
276: {
277: set_terminal_window (window_size + unchanged_at_top);
278: window = 1;
279: }
280:
281: /* Now do all insertions */
282:
283: for (i = qi - 1; i >= 0; i--)
284: {
285: ins_del_lines (queue[i].pos, queue[i].count);
286: /* mark the inserted lines as clear */
287: tem = queue[i].pos;
288: for (j = tem + queue[i].count; j > tem; j--)
289: PhysScreen[j] = 0;
290: }
291:
292: if (window)
293: set_terminal_window (0);
294: }
295:
296: /* Return number of lines in common between PhysScreen and DesiredScreen,
297: considering only vpos range START to END (not including END).
298: Ignores short lines (length < 20) on the assumption that
299: avoiding redrawing such a line will have little weight. */
300:
301: int
302: scrolling_max_lines_saved (start, end, oldhash, newhash, cost)
303: int start, end;
304: int *oldhash, *newhash, *cost;
305: {
306: struct { int hash; int count; } lines[01000];
307: register int i, h;
308: register int matchcount = 0;
309:
310: bzero (lines, sizeof lines);
311:
312: /* Put new lines' hash codes in hash table. */
313: for (i = start; i < end; i++)
314: {
315: if (cost[i] > 20)
316: {
317: h = newhash[i] & 0777;
318: lines[h].hash = newhash[i];
319: lines[h].count++;
320: }
321: }
322:
323: /* Look up old line hash codes in the hash table.
324: Count number of matches between old lines and new. */
325:
326: for (i = start; i < end; i++)
327: {
328: h = oldhash[i] & 0777;
329: if (oldhash[i] == lines[h].hash)
330: {
331: matchcount++;
332: if (--lines[h].count == 0)
333: lines[h].hash = 0;
334: }
335: }
336:
337: return matchcount;
338: }
339:
340: /* Calculate the insert and delete line costs.
341:
342: We keep the ID costs in a precomputed array based on the position
343: at which the I or D is performed. Also, there are two kinds of ID
344: costs: the "once-only" and the "repeated". This is to handle both
345: those terminals that are able to insert N lines at a time (once-
346: only) and those that must repeatedly insert one line.
347:
348: The cost to insert N lines at line L is
349: [tt.t_ILov + (screen_height + 1 - L) * tt.t_ILpf] +
350: N * [tt.t_ILnov + (screen_height + 1 - L) * tt.t_ILnpf]
351:
352: ILov represents the basic insert line overhead. ILpf is the padding
353: required to allow the terminal time to move a line: insertion at line
354: L changes (screen_height + 1 - L) lines.
355:
356: The first bracketed expression above is the overhead; the second is
357: the multiply factor. Both are dependent only on the position at
358: which the insert is performed. We store the overhead in ILcost and
359: the multiply factor in ILncost. Note however that any insertion
360: must include at least one multiply factor. Rather than compute this
361: as ILcost[line]+ILncost[line], we add ILncost into ILcost. This is
362: reasonable because of the particular algorithm used in calcM.
363:
364: Deletion is essentially the same as insertion.
365: */
366:
367: CalcIDCosts (ins_line_string, multi_ins_string,
368: del_line_string, multi_del_string,
369: setup_string, cleanup_string)
370: char *ins_line_string, *multi_ins_string;
371: char *del_line_string, *multi_del_string;
372: char *setup_string, *cleanup_string;
373: {
374: /* Discourage long scrolls slightly on fast lines.
375: This says that scrolling nearly the full length of the screen
376: is not worth it if reprinting takes less than 1/4 second. */
377: int extra = baud_rate / (10 * 4 * screen_height);
378:
379: CalcIDCosts1 (ins_line_string, multi_ins_string,
380: setup_string, cleanup_string,
381: ILcost, ILncost, extra);
382: CalcIDCosts1 (del_line_string, multi_del_string,
383: setup_string, cleanup_string,
384: DLcost, DLncost, 0);
385: }
386:
387: CalcIDCosts1 (one_line_string, multi_string,
388: setup_string, cleanup_string,
389: costvec, ncostvec, extra)
390: char *one_line_string, *multi_string;
391: char *setup_string, *cleanup_string;
392: int *costvec, *ncostvec;
393: int extra;
394: {
395: if (multi_string)
396: CalcLID (string_cost (multi_string),
397: per_line_cost (multi_string),
398: extra, 0, costvec, ncostvec);
399: else if (one_line_string)
400: CalcLID (string_cost (setup_string) + string_cost (cleanup_string), 0,
401: string_cost (one_line_string) + extra,
402: per_line_cost (one_line_string),
403: costvec, ncostvec);
404: else
405: CalcLID (9999, 0, 9999, 0,
406: costvec, ncostvec);
407: }
408:
409: /* Calculate the line ID overhead and multiply factor values */
410: CalcLID (ov1, pf1, ovn, pfn, ov, mf)
411: int ov1, ovn;
412: int pf1, pfn;
413: register int *ov, *mf;
414: {
415: register int i;
416: register int insert_overhead = ov1 * 10 + screen_height * pf1;
417: register int next_insert_cost = ovn * 10 + screen_height * pfn;
418:
419: for (i = screen_height - 1; i > 0; i--)
420: {
421: *mf++ = next_insert_cost / 10;
422: next_insert_cost -= pfn;
423: *ov++ = (insert_overhead + next_insert_cost) / 10;
424: insert_overhead -= pf1;
425: }
426: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.