Fix typos.
[emacs.git] / src / scroll.c
blob05f6fdf85f05934caa5ac8c5763d815de174d24d
1 /* Calculate what line insertion or deletion to do, and do it
3 Copyright (C) 1985-1986, 1990, 1993-1994, 2001-2011
4 Free Software 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>
24 #include <setjmp.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 (FRAME_PTR 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, int *old_hash, int *new_hash,
94 int free_at_end)
96 register int i, j;
97 EMACS_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 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 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;
249 /* Set to 1 if we have set a terminal window with
250 set_terminal_window. It's unsigned to work around GCC bug 48228. */
251 unsigned int 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 = (struct queue *) alloca (current_matrix->nrows * sizeof (struct queue));
257 struct queue *queue = queue_start;
259 char *retained_p = (char *) alloca (window_size * sizeof (char));
260 int *copy_from = (int *) alloca (window_size * sizeof (int));
262 /* Zero means line is empty. */
263 memset (retained_p, 0, window_size * sizeof (char));
264 for (k = 0; k < window_size; ++k)
265 copy_from[k] = -1;
267 #if GLYPH_DEBUG
268 # define CHECK_BOUNDS \
269 do \
271 int ck; \
272 for (ck = 0; ck < window_size; ++ck) \
273 xassert (copy_from[ck] == -1 \
274 || (copy_from[ck] >= 0 && copy_from[ck] < window_size)); \
276 while (0);
277 #endif
279 /* When j is advanced, this corresponds to deleted lines.
280 When i is advanced, this corresponds to inserted lines. */
281 i = j = window_size;
282 while (i > 0 || j > 0)
284 p = matrix + i * (window_size + 1) + j;
286 if (p->insertcost < p->writecost && p->insertcost < p->deletecost)
288 /* Insert should be done at vpos i-1, plus maybe some before.
289 Queue the screen operation to be performed. */
290 queue->count = p->insertcount;
291 queue->pos = i + unchanged_at_top - p->insertcount;
292 ++queue;
294 /* By incrementing I, we leave room in the result rows
295 for the empty rows opened up. */
296 i -= p->insertcount;
298 else if (p->deletecost < p->writecost)
300 /* Old line at vpos j-1, and maybe some before it, should be
301 deleted. By decrementing J, we skip some lines in the
302 temp_rows which is equivalent to omitting these lines in
303 the result rows, thus deleting them. */
304 j -= p->deletecount;
306 /* Set the terminal window, if not done already. */
307 if (! terminal_window_p)
309 set_terminal_window (frame, window_size + unchanged_at_top);
310 terminal_window_p = 1;
313 /* Delete lines on the terminal. */
314 ins_del_lines (frame, j + unchanged_at_top, - p->deletecount);
316 else
318 /* Best thing done here is no insert or delete, i.e. a write. */
319 --i, --j;
320 xassert (i >= 0 && i < window_size);
321 xassert (j >= 0 && j < window_size);
322 copy_from[i] = j;
323 retained_p[j] = 1;
325 #if GLYPH_DEBUG
326 CHECK_BOUNDS;
327 #endif
331 /* Now do all insertions queued above. */
332 if (queue > queue_start)
334 int next = -1;
336 /* Set the terminal window if not yet done. */
337 if (!terminal_window_p)
339 set_terminal_window (frame, window_size + unchanged_at_top);
340 terminal_window_p = 1;
345 --queue;
347 /* Do the deletion on the terminal. */
348 ins_del_lines (frame, queue->pos, queue->count);
350 /* All lines in the range deleted become empty in the glyph
351 matrix. Assign to them glyph rows that are not retained.
352 K is the starting position of the deleted range relative
353 to the window we are working in. */
354 k = queue->pos - unchanged_at_top;
355 for (j = 0; j < queue->count; ++j)
357 /* Find the next row not retained. */
358 while (retained_p[++next])
361 /* Record that this row is to be used for the empty
362 glyph row j. */
363 copy_from[k + j] = next;
366 while (queue > queue_start);
370 for (k = 0; k < window_size; ++k)
371 xassert (copy_from[k] >= 0 && copy_from[k] < window_size);
373 /* Perform the row swizzling. */
374 mirrored_line_dance (current_matrix, unchanged_at_top, window_size,
375 copy_from, retained_p);
377 /* Some sanity checks if GLYPH_DEBUG != 0. */
378 CHECK_MATRIX (current_matrix);
380 if (terminal_window_p)
381 set_terminal_window (frame, 0);
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 (FRAME_PTR 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 int *old_hash, int *new_hash,
432 int free_at_end)
434 register int i, j;
435 EMACS_INT frame_lines = FRAME_LINES (frame);
436 register struct matrix_elt *p, *p1;
437 register 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_lines - 1];
443 int *first_delete_cost
444 = &FRAME_DELETE_COST (frame)[frame_lines - 1];
445 int *next_insert_cost
446 = &FRAME_INSERTN_COST (frame)[frame_lines - 1];
447 int *next_delete_cost
448 = &FRAME_DELETEN_COST (frame)[frame_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 = (int) (baud_rate / (10 * 4 * FRAME_LINES (frame)));
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;
654 /* A queue of deletions and insertions to be performed. */
655 struct alt_queue { int count, pos, window; };
656 struct alt_queue *queue_start = (struct alt_queue *)
657 alloca (window_size * sizeof *queue_start);
658 struct alt_queue *queue = queue_start;
660 /* Set to 1 if a terminal window has been set with
661 set_terminal_window: */
662 int terminal_window_p = 0;
664 /* A nonzero value of write_follows indicates that a write has been
665 selected, allowing either an insert or a delete to be selected
666 next. When write_follows is zero, a delete cannot be selected
667 unless j < i, and an insert cannot be selected unless i < j.
668 This corresponds to a similar restriction (with the ordering
669 reversed) in calculate_direct_scrolling, which is intended to
670 ensure that lines marked as inserted will be blank. */
671 int write_follows_p = 1;
673 /* For each row in the new matrix what row of the old matrix it is. */
674 int *copy_from = (int *) alloca (window_size * sizeof (int));
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 = (char *) alloca (window_size * sizeof (char));
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 xassert (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);
798 void
799 scrolling_1 (FRAME_PTR frame, int window_size, int unchanged_at_top,
800 int unchanged_at_bottom, int *draw_cost, int *old_draw_cost,
801 int *old_hash, int *new_hash, int free_at_end)
803 struct matrix_elt *matrix;
804 matrix = ((struct matrix_elt *)
805 alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
807 if (FRAME_SCROLL_REGION_OK (frame))
809 calculate_direct_scrolling (frame, matrix, window_size,
810 unchanged_at_bottom,
811 draw_cost, old_draw_cost,
812 old_hash, new_hash, free_at_end);
813 do_direct_scrolling (frame, frame->current_matrix,
814 matrix, window_size, unchanged_at_top);
816 else
818 calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
819 draw_cost, old_hash, new_hash,
820 free_at_end);
821 do_scrolling (frame,
822 frame->current_matrix, matrix, window_size,
823 unchanged_at_top);
829 /* Return number of lines in common between current and desired frame
830 contents described to us only as vectors of hash codes OLDHASH and
831 NEWHASH. Consider only vpos range START to END (not including
832 END). Ignore short lines on the assumption that avoiding redrawing
833 such a line will have little weight. */
836 scrolling_max_lines_saved (int start, int end,
837 int *oldhash, int *newhash,
838 int *cost)
840 struct { int hash; int count; } lines[01000];
841 register int i, h;
842 register int matchcount = 0;
843 int avg_length = 0;
844 int threshold;
846 /* Compute a threshold which is 1/4 of average length of these lines. */
848 for (i = start; i < end; i++)
849 avg_length += cost[i];
851 avg_length /= end - start;
852 threshold = avg_length / 4;
854 memset (lines, 0, sizeof lines);
856 /* Put new lines' hash codes in hash table. Ignore lines shorter
857 than the threshold. Thus, if the lines that are in common are
858 mainly the ones that are short, they won't count. */
859 for (i = start; i < end; i++)
861 if (cost[i] > threshold)
863 h = newhash[i] & 0777;
864 lines[h].hash = newhash[i];
865 lines[h].count++;
869 /* Look up old line hash codes in the hash table. Count number of
870 matches between old lines and new. */
871 for (i = start; i < end; i++)
873 h = oldhash[i] & 0777;
874 if (oldhash[i] == lines[h].hash)
876 matchcount++;
877 if (--lines[h].count == 0)
878 lines[h].hash = 0;
882 return matchcount;
885 /* Calculate the line insertion/deletion
886 overhead and multiply factor values */
888 static void
889 line_ins_del (FRAME_PTR frame, int ov1, int pf1, int ovn, int pfn,
890 register int *ov, register int *mf)
892 register EMACS_INT i;
893 register EMACS_INT frame_lines = FRAME_LINES (frame);
894 register int insert_overhead = ov1 * 10;
895 register int next_insert_cost = ovn * 10;
897 for (i = frame_lines-1; i >= 0; i--)
899 mf[i] = next_insert_cost / 10;
900 next_insert_cost += pfn;
901 ov[i] = (insert_overhead + next_insert_cost) / 10;
902 insert_overhead += pf1;
906 static void
907 ins_del_costs (FRAME_PTR frame,
908 const char *one_line_string, const char *multi_string,
909 const char *setup_string, const char *cleanup_string,
910 int *costvec, int *ncostvec,
911 int coefficient)
913 if (multi_string)
914 line_ins_del (frame,
915 string_cost (multi_string) * coefficient,
916 per_line_cost (multi_string) * coefficient,
917 0, 0, costvec, ncostvec);
918 else if (one_line_string)
919 line_ins_del (frame,
920 string_cost (setup_string) + string_cost (cleanup_string), 0,
921 string_cost (one_line_string),
922 per_line_cost (one_line_string),
923 costvec, ncostvec);
924 else
925 line_ins_del (frame,
926 9999, 0, 9999, 0,
927 costvec, ncostvec);
930 /* Calculate the insert and delete line costs.
931 Note that this is done even when running with a window system
932 because we want to know how long scrolling takes (and avoid it).
933 This must be redone whenever the frame height changes.
935 We keep the ID costs in a precomputed array based on the position
936 at which the I or D is performed. Also, there are two kinds of ID
937 costs: the "once-only" and the "repeated". This is to handle both
938 those terminals that are able to insert N lines at a time (once-
939 only) and those that must repeatedly insert one line.
941 The cost to insert N lines at line L is
942 [tt.t_ILov + (frame_lines + 1 - L) * tt.t_ILpf] +
943 N * [tt.t_ILnov + (frame_lines + 1 - L) * tt.t_ILnpf]
945 ILov represents the basic insert line overhead. ILpf is the padding
946 required to allow the terminal time to move a line: insertion at line
947 L changes (frame_lines + 1 - L) lines.
949 The first bracketed expression above is the overhead; the second is
950 the multiply factor. Both are dependent only on the position at
951 which the insert is performed. We store the overhead in
952 FRAME_INSERT_COST (frame) and the multiply factor in
953 FRAME_INSERTN_COST (frame). Note however that any insertion
954 must include at least one multiply factor. Rather than compute this
955 as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line],
956 we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame).
957 This is reasonable because of the particular algorithm used in calcM.
959 Deletion is essentially the same as insertion.
962 void
963 do_line_insertion_deletion_costs (FRAME_PTR frame,
964 const char *ins_line_string,
965 const char *multi_ins_string,
966 const char *del_line_string,
967 const char *multi_del_string,
968 const char *setup_string,
969 const char *cleanup_string,
970 int coefficient)
972 FRAME_INSERT_COST (frame) =
973 xnrealloc (FRAME_INSERT_COST (frame), FRAME_LINES (frame), sizeof (int));
974 FRAME_DELETEN_COST (frame) =
975 xnrealloc (FRAME_DELETEN_COST (frame), FRAME_LINES (frame), sizeof (int));
976 FRAME_INSERTN_COST (frame) =
977 xnrealloc (FRAME_INSERTN_COST (frame), FRAME_LINES (frame), sizeof (int));
978 FRAME_DELETE_COST (frame) =
979 xnrealloc (FRAME_DELETE_COST (frame), FRAME_LINES (frame), sizeof (int));
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);