1 /* Calculate what line insertion or deletion to do, and do it
2
3 Copyright (C) 1985-1986, 1990, 1993-1994, 2001-2023 Free Software
4 Foundation, Inc.
5
6 This file is part of GNU Emacs.
7
8 GNU Emacs is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or (at
11 your option) any later version.
12
13 GNU Emacs is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>. */
20
21
22 #include <config.h>
23
24 #include "lisp.h"
25 #include "termchar.h"
26 #include "dispextern.h"
27 #include "frame.h"
28 #include "termhooks.h"
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 int insertcount;
44 /* Number of deletes so far in this run of deletes,
45 for the cost in deletecost. */
46 int deletecount;
47 /* Number of writes so far since the last insert
48 or delete for the cost in writecost. */
49 int writecount;
50 };
51
52 static void do_direct_scrolling (struct frame *,
53 struct glyph_matrix *,
54 struct matrix_elt *,
55 int, int);
56 static void do_scrolling (struct frame *,
57 struct glyph_matrix *,
58 struct matrix_elt *,
59 int, int);
60
61
62 /* Determine, in matrix[i,j], the cost of updating the first j old
63 lines into the first i new lines using the general scrolling method.
64 This involves using insert or delete somewhere if i != j.
65 For each matrix elements, three kinds of costs are recorded:
66 the smallest cost that ends with an insert, the smallest
67 cost that ends with a delete, and the smallest cost that
68 ends with neither one. These are kept separate because
69 on some terminals the cost of doing an insert varies
70 depending on whether one was just done, etc. */
71
72 /* draw_cost[VPOS] is the cost of outputting new line at VPOS.
73 old_hash[VPOS] is the hash code of the old line at VPOS.
74 new_hash[VPOS] is the hash code of the new line at VPOS.
75 Note that these are not true frame vpos's, but relative
76 to the place at which the first mismatch between old and
77 new contents appears. */
78
79 static void
80 calculate_scrolling (struct frame *frame,
81 /* matrix is of size window_size + 1 on each side. */
82 struct matrix_elt *matrix,
83 int window_size, int lines_below,
84 int *draw_cost, unsigned *old_hash, unsigned *new_hash,
85 int free_at_end)
86 {
87 int i, j;
88 int frame_total_lines = FRAME_TOTAL_LINES (frame);
89 struct matrix_elt *p, *p1;
90 int cost, cost1;
91
92 int lines_moved = window_size
93 + (FRAME_SCROLL_REGION_OK (frame) ? 0 : lines_below);
94 /* first_insert_cost[I] is the cost of doing the first insert-line
95 at the i'th line of the lines we are considering,
96 where I is origin 1 (as it is below). */
97 int *first_insert_cost
98 = &FRAME_INSERT_COST (frame)[frame_total_lines - 1 - lines_moved];
99 int *first_delete_cost
100 = &FRAME_DELETE_COST (frame)[frame_total_lines - 1 - lines_moved];
101 int *next_insert_cost
102 = &FRAME_INSERTN_COST (frame)[frame_total_lines - 1 - lines_moved];
103 int *next_delete_cost
104 = &FRAME_DELETEN_COST (frame)[frame_total_lines - 1 - lines_moved];
105
106 /* Discourage long scrolls on fast lines.
107 Don't scroll nearly a full frame height unless it saves
108 at least 1/4 second. */
109 int extra_cost
110 = clip_to_bounds (1, baud_rate / (10 * 4) / frame_total_lines, INT_MAX / 2);
111
112 /* initialize the top left corner of the matrix */
113 matrix->writecost = 0;
114 matrix->insertcost = SCROLL_INFINITY;
115 matrix->deletecost = SCROLL_INFINITY;
116 matrix->insertcount = 0;
117 matrix->deletecount = 0;
118
119 /* initialize the left edge of the matrix */
120 cost = first_insert_cost[1] - next_insert_cost[1];
121 for (i = 1; i <= window_size; i++)
122 {
123 p = matrix + i * (window_size + 1);
124 cost += draw_cost[i] + next_insert_cost[i] + extra_cost;
125 p->insertcost = cost;
126 p->writecost = SCROLL_INFINITY;
127 p->deletecost = SCROLL_INFINITY;
128 p->insertcount = i;
129 p->deletecount = 0;
130 }
131
132 /* initialize the top edge of the matrix */
133 cost = first_delete_cost[1] - next_delete_cost[1];
134 for (j = 1; j <= window_size; j++)
135 {
136 cost += next_delete_cost[j];
137 matrix[j].deletecost = cost;
138 matrix[j].writecost = SCROLL_INFINITY;
139 matrix[j].insertcost = SCROLL_INFINITY;
140 matrix[j].deletecount = j;
141 matrix[j].insertcount = 0;
142 }
143
144 /* `i' represents the vpos among new frame contents.
145 `j' represents the vpos among the old frame contents. */
146 p = matrix + window_size + 2; /* matrix [1, 1] */
147 for (i = 1; i <= window_size; i++, p++)
148 for (j = 1; j <= window_size; j++, p++)
149 {
150 /* p contains the address of matrix [i, j] */
151
152 /* First calculate the cost assuming we do
153 not insert or delete above this line.
154 That is, if we update through line i-1
155 based on old lines through j-1,
156 and then just change old line j to new line i. */
157 p1 = p - window_size - 2; /* matrix [i-1, j-1] */
158 cost = p1->writecost;
159 if (cost > p1->insertcost)
160 cost = p1->insertcost;
161 if (cost > p1->deletecost)
162 cost = p1->deletecost;
163 if (old_hash[j] != new_hash[i])
164 cost += draw_cost[i];
165 p->writecost = cost;
166
167 /* Calculate the cost if we do an insert-line
168 before outputting this line.
169 That is, we update through line i-1
170 based on old lines through j,
171 do an insert-line on line i,
172 and then output line i from scratch,
173 leaving old lines starting from j for reuse below. */
174 p1 = p - window_size - 1; /* matrix [i-1, j] */
175 /* No need to think about doing a delete followed
176 immediately by an insert. It cannot be as good
177 as not doing either of them. */
178 if (free_at_end == i)
179 {
180 cost = p1->writecost;
181 cost1 = p1->insertcost;
182 }
183 else
184 {
185 cost = p1->writecost + first_insert_cost[i];
186 if (p1->insertcount > i)
187 emacs_abort ();
188 cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
189 }
190 p->insertcost = min (cost, cost1) + draw_cost[i] + extra_cost;
191 p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
192 if (p->insertcount > i)
193 emacs_abort ();
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
219
220 /* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
221 according to the costs in MATRIX, using the general scrolling
222 method that is used if the terminal does not support the setting of
223 scroll windows (scroll_region_ok == 0).
224
225 WINDOW_SIZE is the number of lines being considered for scrolling
226 and UNCHANGED_AT_TOP is the vpos of the first line being
227 considered. These two arguments can specify any contiguous range
228 of lines. */
229
230 static void
231 do_scrolling (struct frame *frame, struct glyph_matrix *current_matrix,
232 struct matrix_elt *matrix, int window_size,
233 int unchanged_at_top)
234 {
235 struct matrix_elt *p;
236 int i, j, k;
237 USE_SAFE_ALLOCA;
238
239 /* True if we have set a terminal window with set_terminal_window. */
240 bool terminal_window_p = 0;
241
242 /* A queue for line insertions to be done. */
243 struct queue { int count, pos; };
244 struct queue *queue_start;
245 SAFE_NALLOCA (queue_start, 1, current_matrix->nrows);
246 struct queue *queue = queue_start;
247
248 char *retained_p = SAFE_ALLOCA (window_size);
249 int *copy_from;
250 SAFE_NALLOCA (copy_from, 1, window_size);
251
252 /* Zero means line is empty. */
253 memset (retained_p, 0, window_size * sizeof (char));
254 for (k = 0; k < window_size; ++k)
255 copy_from[k] = -1;
256
257 #ifdef GLYPH_DEBUG
258 # define CHECK_BOUNDS \
259 do \
260 { \
261 int ck; \
262 for (ck = 0; ck < window_size; ++ck) \
263 eassert (copy_from[ck] == -1 \
264 || (copy_from[ck] >= 0 && copy_from[ck] < window_size)); \
265 } \
266 while (0);
267 #endif
268
269 /* When j is advanced, this corresponds to deleted lines.
270 When i is advanced, this corresponds to inserted lines. */
271 i = j = window_size;
272 while (i > 0 || j > 0)
273 {
274 p = matrix + i * (window_size + 1) + j;
275
276 if (p->insertcost < p->writecost && p->insertcost < p->deletecost)
277 {
278 /* Insert should be done at vpos i-1, plus maybe some before.
279 Queue the screen operation to be performed. */
280 queue->count = p->insertcount;
281 queue->pos = i + unchanged_at_top - p->insertcount;
282 ++queue;
283
284 /* By incrementing I, we leave room in the result rows
285 for the empty rows opened up. */
286 i -= p->insertcount;
287 }
288 else if (p->deletecost < p->writecost)
289 {
290 /* Old line at vpos j-1, and maybe some before it, should be
291 deleted. By decrementing J, we skip some lines in the
292 temp_rows which is equivalent to omitting these lines in
293 the result rows, thus deleting them. */
294 j -= p->deletecount;
295
296 /* Set the terminal window, if not done already. */
297 if (! terminal_window_p)
298 {
299 set_terminal_window (frame, window_size + unchanged_at_top);
300 terminal_window_p = 1;
301 }
302
303 /* Delete lines on the terminal. */
304 ins_del_lines (frame, j + unchanged_at_top, - p->deletecount);
305 }
306 else
307 {
308 /* Best thing done here is no insert or delete, i.e. a write. */
309 --i, --j;
310 eassert (i >= 0 && i < window_size);
311 eassert (j >= 0 && j < window_size);
312 copy_from[i] = j;
313 retained_p[j] = 1;
314
315 #ifdef GLYPH_DEBUG
316 CHECK_BOUNDS;
317 #endif
318 }
319 }
320
321 /* Now do all insertions queued above. */
322 if (queue > queue_start)
323 {
324 int next = -1;
325
326 /* Set the terminal window if not yet done. */
327 if (!terminal_window_p)
328 {
329 set_terminal_window (frame, window_size + unchanged_at_top);
330 terminal_window_p = 1;
331 }
332
333 do
334 {
335 --queue;
336
337 /* Do the deletion on the terminal. */
338 ins_del_lines (frame, queue->pos, queue->count);
339
340 /* All lines in the range deleted become empty in the glyph
341 matrix. Assign to them glyph rows that are not retained.
342 K is the starting position of the deleted range relative
343 to the window we are working in. */
344 k = queue->pos - unchanged_at_top;
345 for (j = 0; j < queue->count; ++j)
346 {
347 /* Find the next row not retained. */
348 while (retained_p[++next])
349 ;
350
351 /* Record that this row is to be used for the empty
352 glyph row j. */
353 copy_from[k + j] = next;
354 }
355 }
356 while (queue > queue_start);
357
358 }
359
360 for (k = 0; k < window_size; ++k)
361 eassert (copy_from[k] >= 0 && copy_from[k] < window_size);
362
363 /* Perform the row swizzling. */
364 mirrored_line_dance (current_matrix, unchanged_at_top, window_size,
365 copy_from, retained_p);
366
367 /* Some sanity checks if GLYPH_DEBUG is defined. */
368 CHECK_MATRIX (current_matrix);
369
370 if (terminal_window_p)
371 set_terminal_window (frame, 0);
372 SAFE_FREE ();
373 }
374
375
376 /* Determine, in matrix[i,j], the cost of updating the first j
377 old lines into the first i new lines using the direct
378 scrolling method. When the old line and the new line have
379 different hash codes, the calculated cost of updating old
380 line j into new line i includes the cost of outputting new
381 line i, and if i != j, the cost of outputting the old line j
382 is also included, as a penalty for moving the line and then
383 erasing it. In addition, the cost of updating a sequence of
384 lines with constant i - j includes the cost of scrolling the
385 old lines into their new positions, unless i == j. Scrolling
386 is achieved by setting the screen window to avoid affecting
387 other lines below, and inserting or deleting lines at the top
388 of the scrolled region. The cost of scrolling a sequence of
389 lines includes the fixed cost of specifying a scroll region,
390 plus a variable cost which can depend upon the number of lines
391 involved and the distance by which they are scrolled, and an
392 extra cost to discourage long scrolls.
393
394 As reflected in the matrix, an insert or delete does not
395 correspond directly to the insertion or deletion which is
396 used in scrolling lines. An insert means that the value of i
397 has increased without a corresponding increase in the value
398 of j. A delete means that the value of j has increased
399 without a corresponding increase in the value of i. A write
400 means that i and j are both increased by the same amount, and
401 that the old lines will be moved to their new positions.
402
403 An insert following a delete is allowed only if i > j.
404 A delete following an insert is allowed only if i < j.
405 These restrictions ensure that the new lines in an insert
406 will always be blank as an effect of the neighboring writes.
407 Thus the calculated cost of an insert is simply the cost of
408 outputting the new line contents. The direct cost of a
409 delete is zero. Inserts and deletes indirectly affect the
410 total cost through their influence on subsequent writes. */
411
412 /* The vectors draw_cost, old_hash, and new_hash have the same
413 meanings here as in calculate_scrolling, and old_draw_cost
414 is the equivalent of draw_cost for the old line contents */
415
416 static void
417 calculate_direct_scrolling (struct frame *frame,
418 /* matrix is of size window_size + 1 on each side. */
419 struct matrix_elt *matrix,
420 int window_size, int lines_below,
421 int *draw_cost, int *old_draw_cost,
422 unsigned *old_hash, unsigned *new_hash,
423 int free_at_end)
424 {
425 int i, j;
426 int frame_total_lines = FRAME_TOTAL_LINES (frame);
427 struct matrix_elt *p, *p1;
428 int cost, cost1, delta;
429
430 /* first_insert_cost[-I] is the cost of doing the first insert-line
431 at a position I lines above the bottom line in the scroll window. */
432 int *first_insert_cost
433 = &FRAME_INSERT_COST (frame)[frame_total_lines - 1];
434 int *first_delete_cost
435 = &FRAME_DELETE_COST (frame)[frame_total_lines - 1];
436 int *next_insert_cost
437 = &FRAME_INSERTN_COST (frame)[frame_total_lines - 1];
438 int *next_delete_cost
439 = &FRAME_DELETEN_COST (frame)[frame_total_lines - 1];
440
441 int scroll_overhead;
442
443 /* Discourage long scrolls on fast lines.
444 Don't scroll nearly a full frame height unless it saves
445 at least 1/4 second. */
446 int extra_cost
447 = clip_to_bounds (1, baud_rate / (10 * 4) / frame_total_lines, INT_MAX / 2);
448
449 /* Overhead of setting the scroll window, plus the extra
450 cost of scrolling by a distance of one. The extra cost is
451 added once for consistency with the cost vectors */
452 scroll_overhead
453 = FRAME_SCROLL_REGION_COST (frame) + extra_cost;
454
455 /* initialize the top left corner of the matrix */
456 matrix->writecost = 0;
457 matrix->insertcost = SCROLL_INFINITY;
458 matrix->deletecost = SCROLL_INFINITY;
459 matrix->writecount = 0;
460 matrix->insertcount = 0;
461 matrix->deletecount = 0;
462
463 /* initialize the left edge of the matrix */
464 cost = 0;
465 for (i = 1; i <= window_size; i++)
466 {
467 p = matrix + i * (window_size + 1);
468 cost += draw_cost[i];
469 p->insertcost = cost;
470 p->writecost = SCROLL_INFINITY;
471 p->deletecost = SCROLL_INFINITY;
472 p->insertcount = i;
473 p->writecount = 0;
474 p->deletecount = 0;
475 }
476
477 /* initialize the top edge of the matrix */
478 for (j = 1; j <= window_size; j++)
479 {
480 matrix[j].deletecost = 0;
481 matrix[j].writecost = SCROLL_INFINITY;
482 matrix[j].insertcost = SCROLL_INFINITY;
483 matrix[j].deletecount = j;
484 matrix[j].writecount = 0;
485 matrix[j].insertcount = 0;
486 }
487
488 /* `i' represents the vpos among new frame contents.
489 `j' represents the vpos among the old frame contents. */
490 p = matrix + window_size + 2; /* matrix [1, 1] */
491
492 for (i = 1; i <= window_size; i++, p++)
493 for (j = 1; j <= window_size; j++, p++)
494 {
495 /* p contains the address of matrix [i, j] */
496
497 /* First calculate the cost assuming we do
498 not insert or delete above this line.
499 That is, if we update through line i-1
500 based on old lines through j-1,
501 and then just change old line j to new line i.
502
503 Depending on which choice gives the lower cost,
504 this usually involves either scrolling a single line
505 or extending a sequence of scrolled lines, but
506 when i == j, no scrolling is required. */
507 p1 = p - window_size - 2; /* matrix [i-1, j-1] */
508 cost = p1->insertcost;
509 if (cost > p1->deletecost)
510 cost = p1->deletecost;
511 cost1 = p1->writecost;
512 if (i == j)
513 {
514 if (cost > cost1)
515 {
516 cost = cost1;
517 p->writecount = p1->writecount + 1;
518 }
519 else
520 p->writecount = 1;
521 if (old_hash[j] != new_hash[i])
522 {
523 cost += draw_cost[i];
524 }
525 }
526 else
527 {
528 if (i > j)
529 {
530 delta = i - j;
531
532 /* The cost added here for scrolling the first line by
533 a distance N includes the overhead of setting the
534 scroll window, the cost of inserting N lines at a
535 position N lines above the bottom line of the window,
536 and an extra cost which is proportional to N. */
537 cost += scroll_overhead + first_insert_cost[-delta] +
538 (delta-1) * (next_insert_cost[-delta] + extra_cost);
539
540 /* In the most general case, the insertion overhead and
541 the multiply factor can grow linearly as the distance
542 from the bottom of the window increases. The incremental
543 cost of scrolling an additional line depends upon the
544 rate of change of these two parameters. Each of these
545 growth rates can be determined by a simple difference.
546 To reduce the cumulative effects of rounding error, we
547 vary the position at which the difference is computed. */
548 cost1 += first_insert_cost[-j] - first_insert_cost[1-j] +
549 (delta-1) * (next_insert_cost[-j] - next_insert_cost[1-j]);
550 }
551 else
552 {
553 delta = j - i;
554 cost += scroll_overhead + first_delete_cost[-delta] +
555 (delta-1) * (next_delete_cost[-delta] + extra_cost);
556 cost1 += first_delete_cost[-i] - first_delete_cost[1-i] +
557 (delta-1) * ( next_delete_cost[-i] - next_delete_cost[1-i]);
558 }
559 if (cost1 < cost)
560 {
561 cost = cost1;
562 p->writecount = p1->writecount + 1;
563 }
564 else
565 p->writecount = 1;
566 if (old_hash[j] != new_hash[i])
567 {
568 cost += draw_cost[i] + old_draw_cost[j];
569 }
570 }
571 p->writecost = cost;
572
573 /* Calculate the cost if we do an insert-line
574 before outputting this line.
575 That is, we update through line i-1
576 based on old lines through j,
577 do an insert-line on line i,
578 and then output line i from scratch,
579 leaving old lines starting from j for reuse below. */
580 p1 = p - window_size - 1; /* matrix [i-1, j] */
581 cost = p1->writecost;
582 /* If i > j, an insert is allowed after a delete. */
583 if (i > j && p1->deletecost < cost)
584 cost = p1->deletecost;
585 if (p1->insertcost <= cost)
586 {
587 cost = p1->insertcost;
588 p->insertcount = p1->insertcount + 1;
589 }
590 else
591 p->insertcount = 1;
592 cost += draw_cost[i];
593 p->insertcost = cost;
594
595 /* Calculate the cost if we do a delete line after
596 outputting this line.
597 That is, we update through line i
598 based on old lines through j-1,
599 and throw away old line j. */
600 p1 = p - 1; /* matrix [i, j-1] */
601 cost = p1->writecost;
602 /* If i < j, a delete is allowed after an insert. */
603 if (i < j && p1->insertcost < cost)
604 cost = p1->insertcost;
605 cost1 = p1->deletecost;
606 if (p1->deletecost <= cost)
607 {
608 cost = p1->deletecost;
609 p->deletecount = p1->deletecount + 1;
610 }
611 else
612 p->deletecount = 1;
613 p->deletecost = cost;
614 }
615 }
616
617
618
619 /* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
620 according to the costs in MATRIX, using the direct scrolling method
621 which is used when the terminal supports setting a scroll window
622 (scroll_region_ok).
623
624 WINDOW_SIZE is the number of lines being considered for scrolling
625 and UNCHANGED_AT_TOP is the vpos of the first line being
626 considered. These two arguments can specify any contiguous range
627 of lines.
628
629 In the direct scrolling method, a new scroll window is selected
630 before each insertion or deletion, so that groups of lines can be
631 scrolled directly to their final vertical positions. This method
632 is described in more detail in calculate_direct_scrolling, where
633 the cost matrix for this approach is constructed. */
634
635 static void
636 do_direct_scrolling (struct frame *frame, struct glyph_matrix *current_matrix,
637 struct matrix_elt *cost_matrix, int window_size,
638 int unchanged_at_top)
639 {
640 struct matrix_elt *p;
641 int i, j;
642 USE_SAFE_ALLOCA;
643
644 /* A queue of deletions and insertions to be performed. */
645 struct alt_queue { int count, pos, window; };
646 struct alt_queue *queue_start;
647 SAFE_NALLOCA (queue_start, 1, window_size);
648 struct alt_queue *queue = queue_start;
649
650 /* True if a terminal window has been set with set_terminal_window. */
651 bool terminal_window_p = 0;
652
653 /* If true, a write has been selected, allowing either an insert or a
654 delete to be selected next. If false, a delete cannot be selected
655 unless j < i, and an insert cannot be selected unless i < j.
656 This corresponds to a similar restriction (with the ordering
657 reversed) in calculate_direct_scrolling, which is intended to
658 ensure that lines marked as inserted will be blank. */
659 bool write_follows_p = 1;
660
661 /* For each row in the new matrix what row of the old matrix it is. */
662 int *copy_from;
663 SAFE_NALLOCA (copy_from, 1, window_size);
664
665 /* Non-zero for each row in the new matrix that is retained from the
666 old matrix. Lines not retained are empty. */
667 char *retained_p = SAFE_ALLOCA (window_size);
668
669 memset (retained_p, 0, window_size * sizeof (char));
670
671 /* Perform some sanity checks when GLYPH_DEBUG is on. */
672 CHECK_MATRIX (current_matrix);
673
674 /* We are working on the line range UNCHANGED_AT_TOP ...
675 UNCHANGED_AT_TOP + WINDOW_SIZE (not including) in CURRENT_MATRIX.
676 We step through lines in this range from the end to the start. I
677 is an index into new lines, j an index into old lines. The cost
678 matrix determines what to do for ranges of indices.
679
680 If i is decremented without also decrementing j, this corresponds
681 to inserting empty lines in the result. If j is decremented
682 without also decrementing i, this corresponds to omitting these
683 lines in the new rows, i.e. rows are deleted. */
684 i = j = window_size;
685
686 while (i > 0 || j > 0)
687 {
688 p = cost_matrix + i * (window_size + 1) + j;
689
690 if (p->insertcost < p->writecost
691 && p->insertcost < p->deletecost
692 && (write_follows_p || i < j))
693 {
694 /* Insert is cheaper than deleting or writing lines. Leave
695 a hole in the result display that will be filled with
696 empty lines when the queue is emptied. */
697 queue->count = 0;
698 queue->window = i;
699 queue->pos = i - p->insertcount;
700 ++queue;
701
702 i -= p->insertcount;
703 write_follows_p = 0;
704 }
705 else if (p->deletecost < p->writecost
706 && (write_follows_p || i > j))
707 {
708 /* Deleting lines is cheaper. By decrementing J, omit
709 deletecount lines from the original. */
710 write_follows_p = 0;
711 j -= p->deletecount;
712 }
713 else
714 {
715 /* One or more lines should be written. In the direct
716 scrolling method we do this by scrolling the lines to the
717 place they belong. */
718 int n_to_write = p->writecount;
719 write_follows_p = 1;
720 eassert (n_to_write > 0);
721
722 if (i > j)
723 {
724 /* Immediately insert lines */
725 set_terminal_window (frame, i + unchanged_at_top);
726 terminal_window_p = 1;
727 ins_del_lines (frame, j - n_to_write + unchanged_at_top, i - j);
728 }
729 else if (i < j)
730 {
731 /* Queue the deletion of a group of lines */
732 queue->pos = i - n_to_write + unchanged_at_top;
733 queue->window = j + unchanged_at_top;
734 queue->count = i - j;
735 ++queue;
736 }
737
738 while (n_to_write > 0)
739 {
740 --i, --j, --n_to_write;
741 copy_from[i] = j;
742 retained_p[j] = 1;
743 }
744 }
745 }
746
747 /* Do queued operations. */
748 if (queue > queue_start)
749 {
750 int next = -1;
751
752 do
753 {
754 --queue;
755 if (queue->count)
756 {
757 set_terminal_window (frame, queue->window);
758 terminal_window_p = 1;
759 ins_del_lines (frame, queue->pos, queue->count);
760 }
761 else
762 {
763 for (j = queue->window - 1; j >= queue->pos; --j)
764 {
765 while (retained_p[++next])
766 ;
767 copy_from[j] = next;
768 }
769 }
770 }
771 while (queue > queue_start);
772 }
773
774 /* Now, for each row I in the range of rows we are working on,
775 copy_from[i] gives the original line to copy to I, and
776 retained_p[copy_from[i]] is zero if line I in the new display is
777 empty. */
778 mirrored_line_dance (current_matrix, unchanged_at_top, window_size,
779 copy_from, retained_p);
780
781 if (terminal_window_p)
782 set_terminal_window (frame, 0);
783 SAFE_FREE ();
784 }
785
786
787
788 void
789 scrolling_1 (struct frame *frame, int window_size, int unchanged_at_top,
790 int unchanged_at_bottom, int *draw_cost, int *old_draw_cost,
791 unsigned *old_hash, unsigned *new_hash, int free_at_end)
792 {
793 USE_SAFE_ALLOCA;
794 struct matrix_elt *matrix;
795 SAFE_NALLOCA (matrix, window_size + 1, window_size + 1);
796
797 if (FRAME_SCROLL_REGION_OK (frame))
798 {
799 calculate_direct_scrolling (frame, matrix, window_size,
800 unchanged_at_bottom,
801 draw_cost, old_draw_cost,
802 old_hash, new_hash, free_at_end);
803 do_direct_scrolling (frame, frame->current_matrix,
804 matrix, window_size, unchanged_at_top);
805 }
806 else
807 {
808 calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
809 draw_cost, old_hash, new_hash,
810 free_at_end);
811 do_scrolling (frame,
812 frame->current_matrix, matrix, window_size,
813 unchanged_at_top);
814 }
815
816 SAFE_FREE ();
817 }
818
819
820
821 /* Return number of lines in common between current and desired frame
822 contents described to us only as vectors of hash codes OLDHASH and
823 NEWHASH. Consider only vpos range START to END (not including
824 END). Ignore short lines on the assumption that avoiding redrawing
825 such a line will have little weight. */
826
827 int
828 scrolling_max_lines_saved (int start, int end,
829 unsigned *oldhash, unsigned *newhash,
830 int *cost)
831 {
832 enum { LOG2_NLINES = 9 };
833 enum { NLINES = 1 << LOG2_NLINES };
834 struct { unsigned hash; int count; } lines[NLINES];
835 int i, h;
836 int matchcount = 0;
837 int avg_length = 0;
838 int threshold;
839
840 /* Compute a threshold which is 1/4 of average length of these lines. */
841
842 for (i = start; i < end; i++)
843 avg_length += cost[i];
844
845 avg_length /= end - start;
846 threshold = avg_length / 4;
847
848 memset (lines, 0, sizeof lines);
849
850 /* Put new lines' hash codes in hash table. Ignore lines shorter
851 than the threshold. Thus, if the lines that are in common are
852 mainly the ones that are short, they won't count. */
853 for (i = start; i < end; i++)
854 {
855 if (cost[i] > threshold)
856 {
857 h = newhash[i] & (NLINES - 1);
858 lines[h].hash = newhash[i];
859 lines[h].count++;
860 }
861 }
862
863 /* Look up old line hash codes in the hash table. Count number of
864 matches between old lines and new. */
865 for (i = start; i < end; i++)
866 {
867 h = oldhash[i] & (NLINES - 1);
868 if (oldhash[i] == lines[h].hash)
869 {
870 matchcount++;
871 if (--lines[h].count == 0)
872 lines[h].hash = 0;
873 }
874 }
875
876 return matchcount;
877 }
878
879 /* Calculate the line insertion/deletion
880 overhead and multiply factor values */
881
882 static void
883 line_ins_del (struct frame *frame, int ov1, int pf1, int ovn, int pfn,
884 int *ov, int *mf)
885 {
886 int i;
887 int frame_total_lines = FRAME_TOTAL_LINES (frame);
888 int insert_overhead = ov1 * 10;
889 int next_insert_cost = ovn * 10;
890
891 for (i = frame_total_lines - 1; i >= 0; i--)
892 {
893 mf[i] = next_insert_cost / 10;
894 next_insert_cost += pfn;
895 ov[i] = (insert_overhead + next_insert_cost) / 10;
896 insert_overhead += pf1;
897 }
898 }
899
900 static void
901 ins_del_costs (struct frame *frame,
902 const char *one_line_string, const char *multi_string,
903 const char *setup_string, const char *cleanup_string,
904 int *costvec, int *ncostvec,
905 int coefficient)
906 {
907 if (multi_string)
908 line_ins_del (frame,
909 string_cost (multi_string) * coefficient,
910 per_line_cost (multi_string) * coefficient,
911 0, 0, costvec, ncostvec);
912 else if (one_line_string)
913 line_ins_del (frame,
914 string_cost (setup_string) + string_cost (cleanup_string), 0,
915 string_cost (one_line_string),
916 per_line_cost (one_line_string),
917 costvec, ncostvec);
918 else
919 line_ins_del (frame,
920 9999, 0, 9999, 0,
921 costvec, ncostvec);
922 }
923
924 /* Calculate the insert and delete line costs.
925 Note that this is done even when running with a window system
926 because we want to know how long scrolling takes (and avoid it).
927 This must be redone whenever the frame height changes.
928
929 We keep the ID costs in a precomputed array based on the position
930 at which the I or D is performed. Also, there are two kinds of ID
931 costs: the "once-only" and the "repeated". This is to handle both
932 those terminals that are able to insert N lines at a time (once-
933 only) and those that must repeatedly insert one line.
934
935 The cost to insert N lines at line L is
936 [tt.t_ILov + (frame_total_lines + 1 - L) * tt.t_ILpf] +
937 N * [tt.t_ILnov + (frame_total_lines + 1 - L) * tt.t_ILnpf]
938
939 ILov represents the basic insert line overhead. ILpf is the padding
940 required to allow the terminal time to move a line: insertion at line
941 L changes (frame_total_lines + 1 - L) lines.
942
943 The first bracketed expression above is the overhead; the second is
944 the multiply factor. Both are dependent only on the position at
945 which the insert is performed. We store the overhead in
946 FRAME_INSERT_COST (frame) and the multiply factor in
947 FRAME_INSERTN_COST (frame). Note however that any insertion
948 must include at least one multiply factor. Rather than compute this
949 as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line],
950 we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame).
951 This is reasonable because of the particular algorithm used in calcM.
952
953 Deletion is essentially the same as insertion.
954 */
955
956 void
957 do_line_insertion_deletion_costs (struct frame *frame,
958 const char *ins_line_string,
959 const char *multi_ins_string,
960 const char *del_line_string,
961 const char *multi_del_string,
962 const char *setup_string,
963 const char *cleanup_string,
964 int coefficient)
965 {
966 int frame_total_lines = FRAME_TOTAL_LINES (frame);
967 FRAME_INSERT_COST (frame) =
968 xnrealloc (FRAME_INSERT_COST (frame), frame_total_lines, sizeof (int));
969 FRAME_DELETEN_COST (frame) =
970 xnrealloc (FRAME_DELETEN_COST (frame), frame_total_lines, sizeof (int));
971 FRAME_INSERTN_COST (frame) =
972 xnrealloc (FRAME_INSERTN_COST (frame), frame_total_lines, sizeof (int));
973 FRAME_DELETE_COST (frame) =
974 xnrealloc (FRAME_DELETE_COST (frame), frame_total_lines, sizeof (int));
975
976 ins_del_costs (frame,
977 ins_line_string, multi_ins_string,
978 setup_string, cleanup_string,
979 FRAME_INSERT_COST (frame), FRAME_INSERTN_COST (frame),
980 coefficient);
981 ins_del_costs (frame,
982 del_line_string, multi_del_string,
983 setup_string, cleanup_string,
984 FRAME_DELETE_COST (frame), FRAME_DELETEN_COST (frame),
985 coefficient);
986 }