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