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