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