*** empty log message ***
[emacs.git] / src / scroll.c
blob6c6aa4abf98a559e1932b0b4cc4f87a72a8746cd
1 /* Calculate what line insertion or deletion to do, and do it,
2 Copyright (C) 1985, 1986, 1990, 1993, 1994 Free Software Foundation, Inc.
4 This file is part of GNU Emacs.
6 GNU Emacs is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
11 GNU Emacs is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Emacs; see the file COPYING. If not, write to
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
22 #include <config.h>
23 #include <stdio.h>
24 #include <string.h>
25 #include "termchar.h"
26 #include "lisp.h"
27 #include "dispextern.h"
28 #include "keyboard.h"
29 #include "frame.h"
30 #include "window.h"
32 /* All costs measured in characters.
33 So no cost can exceed the area of a frame, measured in characters.
34 Let's hope this is never more than 1000000 characters. */
36 #define INFINITY 1000000
38 struct matrix_elt
40 /* Cost of outputting through this line
41 if no insert/delete is done just above it. */
42 int writecost;
43 /* Cost of outputting through this line
44 if an insert is done just above it. */
45 int insertcost;
46 /* Cost of outputting through this line
47 if a delete is done just above it. */
48 int deletecost;
49 /* Number of inserts so far in this run of inserts,
50 for the cost in insertcost. */
51 unsigned char insertcount;
52 /* Number of deletes so far in this run of deletes,
53 for the cost in deletecost. */
54 unsigned char deletecount;
55 /* Number of writes so far since the last insert
56 or delete for the cost in writecost. */
57 unsigned char writecount;
60 static void do_direct_scrolling P_ ((struct glyph_matrix *,
61 struct matrix_elt *,
62 int, int));
63 static void do_scrolling P_ ((struct glyph_matrix *,
64 struct matrix_elt *,
65 int, int));
68 /* Determine, in matrix[i,j], the cost of updating the first j old
69 lines into the first i new lines using the general scrolling method.
70 This involves using insert or delete somewhere if i != j.
71 For each matrix elements, three kinds of costs are recorded:
72 the smallest cost that ends with an insert, the smallest
73 cost that ends with a delete, and the smallest cost that
74 ends with neither one. These are kept separate because
75 on some terminals the cost of doing an insert varies
76 depending on whether one was just done, etc. */
78 /* draw_cost[VPOS] is the cost of outputting new line at VPOS.
79 old_hash[VPOS] is the hash code of the old line at VPOS.
80 new_hash[VPOS] is the hash code of the new line at VPOS.
81 Note that these are not true frame vpos's, but relative
82 to the place at which the first mismatch between old and
83 new contents appears. */
85 static void
86 calculate_scrolling (frame, matrix, window_size, lines_below,
87 draw_cost, old_hash, new_hash,
88 free_at_end)
89 FRAME_PTR frame;
90 /* matrix is of size window_size + 1 on each side. */
91 struct matrix_elt *matrix;
92 int window_size, lines_below;
93 int *draw_cost;
94 int *old_hash;
95 int *new_hash;
96 int free_at_end;
98 register int i, j;
99 int frame_lines = FRAME_LINES (frame);
100 register struct matrix_elt *p, *p1;
101 register int cost, cost1;
103 int lines_moved = window_size + (scroll_region_ok ? 0 : lines_below);
104 /* first_insert_cost[I] is the cost of doing the first insert-line
105 at the i'th line of the lines we are considering,
106 where I is origin 1 (as it is below). */
107 int *first_insert_cost
108 = &FRAME_INSERT_COST (frame)[frame_lines - 1 - lines_moved];
109 int *first_delete_cost
110 = &FRAME_DELETE_COST (frame)[frame_lines - 1 - lines_moved];
111 int *next_insert_cost
112 = &FRAME_INSERTN_COST (frame)[frame_lines - 1 - lines_moved];
113 int *next_delete_cost
114 = &FRAME_DELETEN_COST (frame)[frame_lines - 1 - lines_moved];
116 /* Discourage long scrolls on fast lines.
117 Don't scroll nearly a full frame height unless it saves
118 at least 1/4 second. */
119 int extra_cost = baud_rate / (10 * 4 * FRAME_LINES (frame));
121 if (baud_rate <= 0)
122 extra_cost = 1;
124 /* initialize the top left corner of the matrix */
125 matrix->writecost = 0;
126 matrix->insertcost = INFINITY;
127 matrix->deletecost = INFINITY;
128 matrix->insertcount = 0;
129 matrix->deletecount = 0;
131 /* initialize the left edge of the matrix */
132 cost = first_insert_cost[1] - next_insert_cost[1];
133 for (i = 1; i <= window_size; i++)
135 p = matrix + i * (window_size + 1);
136 cost += draw_cost[i] + next_insert_cost[i] + extra_cost;
137 p->insertcost = cost;
138 p->writecost = INFINITY;
139 p->deletecost = INFINITY;
140 p->insertcount = i;
141 p->deletecount = 0;
144 /* initialize the top edge of the matrix */
145 cost = first_delete_cost[1] - next_delete_cost[1];
146 for (j = 1; j <= window_size; j++)
148 cost += next_delete_cost[j];
149 matrix[j].deletecost = cost;
150 matrix[j].writecost = INFINITY;
151 matrix[j].insertcost = INFINITY;
152 matrix[j].deletecount = j;
153 matrix[j].insertcount = 0;
156 /* `i' represents the vpos among new frame contents.
157 `j' represents the vpos among the old frame contents. */
158 p = matrix + window_size + 2; /* matrix [1, 1] */
159 for (i = 1; i <= window_size; i++, p++)
160 for (j = 1; j <= window_size; j++, p++)
162 /* p contains the address of matrix [i, j] */
164 /* First calculate the cost assuming we do
165 not insert or delete above this line.
166 That is, if we update through line i-1
167 based on old lines through j-1,
168 and then just change old line j to new line i. */
169 p1 = p - window_size - 2; /* matrix [i-1, j-1] */
170 cost = p1->writecost;
171 if (cost > p1->insertcost)
172 cost = p1->insertcost;
173 if (cost > p1->deletecost)
174 cost = p1->deletecost;
175 if (old_hash[j] != new_hash[i])
176 cost += draw_cost[i];
177 p->writecost = cost;
179 /* Calculate the cost if we do an insert-line
180 before outputting this line.
181 That is, we update through line i-1
182 based on old lines through j,
183 do an insert-line on line i,
184 and then output line i from scratch,
185 leaving old lines starting from j for reuse below. */
186 p1 = p - window_size - 1; /* matrix [i-1, j] */
187 /* No need to think about doing a delete followed
188 immediately by an insert. It cannot be as good
189 as not doing either of them. */
190 if (free_at_end == i)
192 cost = p1->writecost;
193 cost1 = p1->insertcost;
195 else
197 cost = p1->writecost + first_insert_cost[i];
198 if ((int) p1->insertcount > i)
199 abort ();
200 cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
202 p->insertcost = min (cost, cost1) + draw_cost[i] + extra_cost;
203 p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
204 if ((int) p->insertcount > i)
205 abort ();
207 /* Calculate the cost if we do a delete line after
208 outputting this line.
209 That is, we update through line i
210 based on old lines through j-1,
211 and throw away old line j. */
212 p1 = p - 1; /* matrix [i, j-1] */
213 /* No need to think about doing an insert followed
214 immediately by a delete. */
215 if (free_at_end == i)
217 cost = p1->writecost;
218 cost1 = p1->deletecost;
220 else
222 cost = p1->writecost + first_delete_cost[i];
223 cost1 = p1->deletecost + next_delete_cost[i];
225 p->deletecost = min (cost, cost1);
226 p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1;
232 /* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
233 according to the costs in MATRIX, using the general scrolling
234 method that is used if the terminal does not support the setting of
235 scroll windows (scroll_region_ok == 0).
237 WINDOW_SIZE is the number of lines being considered for scrolling
238 and UNCHANGED_AT_TOP is the vpos of the first line being
239 considered. These two arguments can specify any contiguous range
240 of lines. */
242 static void
243 do_scrolling (current_matrix, matrix, window_size, unchanged_at_top)
244 struct glyph_matrix *current_matrix;
245 struct matrix_elt *matrix;
246 int window_size;
247 int unchanged_at_top;
249 struct matrix_elt *p;
250 int i, j, k;
252 /* Set to 1 if we have set a terminal window with
253 set_terminal_window. */
254 int terminal_window_p = 0;
256 /* A queue for line insertions to be done. */
257 struct queue { int count, pos; };
258 struct queue *queue_start
259 = (struct queue *) alloca (current_matrix->nrows * sizeof (struct queue));
260 struct queue *queue = queue_start;
262 char *retained_p = (char *) alloca (window_size * sizeof (char));
263 int *copy_from = (int *) alloca (window_size * sizeof (int));
265 /* Zero means line is empty. */
266 bzero (retained_p, window_size * sizeof (char));
267 for (k = 0; k < window_size; ++k)
268 copy_from[k] = -1;
270 #define CHECK_BOUNDS \
271 do \
273 int k; \
274 for (k = 0; k < window_size; ++k) \
275 xassert (copy_from[k] == -1 \
276 || (copy_from[k] >= 0 && copy_from[k] < window_size)); \
278 while (0);
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 (window_size + unchanged_at_top);
311 terminal_window_p = 1;
314 /* Delete lines on the terminal. */
315 ins_del_lines (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 xassert (i >= 0 && i < window_size);
322 xassert (j >= 0 && j < window_size);
323 copy_from[i] = j;
324 retained_p[j] = 1;
326 #if 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 (window_size + unchanged_at_top);
341 terminal_window_p = 1;
346 --queue;
348 /* Do the deletion on the terminal. */
349 ins_del_lines (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 xassert (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 != 0. */
379 CHECK_MATRIX (current_matrix);
381 if (terminal_window_p)
382 set_terminal_window (0);
386 /* Determine, in matrix[i,j], the cost of updating the first j
387 old lines into the first i new lines using the direct
388 scrolling method. When the old line and the new line have
389 different hash codes, the calculated cost of updating old
390 line j into new line i includes the cost of outputting new
391 line i, and if i != j, the cost of outputting the old line j
392 is also included, as a penalty for moving the line and then
393 erasing it. In addition, the cost of updating a sequence of
394 lines with constant i - j includes the cost of scrolling the
395 old lines into their new positions, unless i == j. Scrolling
396 is achieved by setting the screen window to avoid affecting
397 other lines below, and inserting or deleting lines at the top
398 of the scrolled region. The cost of scrolling a sequence of
399 lines includes the fixed cost of specifying a scroll region,
400 plus a variable cost which can depend upon the number of lines
401 involved and the distance by which they are scrolled, and an
402 extra cost to discourage long scrolls.
404 As reflected in the matrix, an insert or delete does not
405 correspond directly to the insertion or deletion which is
406 used in scrolling lines. An insert means that the value of i
407 has increased without a corresponding increase in the value
408 of j. A delete means that the value of j has increased
409 without a corresponding increase in the value of i. A write
410 means that i and j are both increased by the same amount, and
411 that the old lines will be moved to their new positions.
413 An insert following a delete is allowed only if i > j.
414 A delete following an insert is allowed only if i < j.
415 These restrictions ensure that the new lines in an insert
416 will always be blank as an effect of the neighboring writes.
417 Thus the calculated cost of an insert is simply the cost of
418 outputting the new line contents. The direct cost of a
419 delete is zero. Inserts and deletes indirectly affect the
420 total cost through their influence on subsequent writes. */
422 /* The vectors draw_cost, old_hash, and new_hash have the same
423 meanings here as in calculate_scrolling, and old_draw_cost
424 is the equivalent of draw_cost for the old line contents */
426 static void
427 calculate_direct_scrolling (frame, matrix, window_size, lines_below,
428 draw_cost, old_draw_cost, old_hash, new_hash,
429 free_at_end)
430 FRAME_PTR frame;
431 /* matrix is of size window_size + 1 on each side. */
432 struct matrix_elt *matrix;
433 int window_size, lines_below;
434 int *draw_cost;
435 int *old_draw_cost;
436 int *old_hash;
437 int *new_hash;
438 int free_at_end;
440 register int i, j;
441 int frame_lines = FRAME_LINES (frame);
442 register struct matrix_elt *p, *p1;
443 register int cost, cost1, delta;
445 /* first_insert_cost[-I] is the cost of doing the first insert-line
446 at a position I lines above the bottom line in the scroll window. */
447 int *first_insert_cost
448 = &FRAME_INSERT_COST (frame)[frame_lines - 1];
449 int *first_delete_cost
450 = &FRAME_DELETE_COST (frame)[frame_lines - 1];
451 int *next_insert_cost
452 = &FRAME_INSERTN_COST (frame)[frame_lines - 1];
453 int *next_delete_cost
454 = &FRAME_DELETEN_COST (frame)[frame_lines - 1];
456 int scroll_overhead;
458 /* Discourage long scrolls on fast lines.
459 Don't scroll nearly a full frame height unless it saves
460 at least 1/4 second. */
461 int extra_cost = baud_rate / (10 * 4 * FRAME_LINES (frame));
463 if (baud_rate <= 0)
464 extra_cost = 1;
466 /* Overhead of setting the scroll window, plus the extra cost
467 cost of scrolling by a distance of one. The extra cost is
468 added once for consistency with the cost vectors */
469 scroll_overhead = scroll_region_cost + extra_cost;
471 /* initialize the top left corner of the matrix */
472 matrix->writecost = 0;
473 matrix->insertcost = INFINITY;
474 matrix->deletecost = INFINITY;
475 matrix->writecount = 0;
476 matrix->insertcount = 0;
477 matrix->deletecount = 0;
479 /* initialize the left edge of the matrix */
480 cost = 0;
481 for (i = 1; i <= window_size; i++)
483 p = matrix + i * (window_size + 1);
484 cost += draw_cost[i];
485 p->insertcost = cost;
486 p->writecost = INFINITY;
487 p->deletecost = INFINITY;
488 p->insertcount = i;
489 p->writecount = 0;
490 p->deletecount = 0;
493 /* initialize the top edge of the matrix */
494 for (j = 1; j <= window_size; j++)
496 matrix[j].deletecost = 0;
497 matrix[j].writecost = INFINITY;
498 matrix[j].insertcost = INFINITY;
499 matrix[j].deletecount = j;
500 matrix[j].writecount = 0;
501 matrix[j].insertcount = 0;
504 /* `i' represents the vpos among new frame contents.
505 `j' represents the vpos among the old frame contents. */
506 p = matrix + window_size + 2; /* matrix [1, 1] */
508 for (i = 1; i <= window_size; i++, p++)
509 for (j = 1; j <= window_size; j++, p++)
511 /* p contains the address of matrix [i, j] */
513 /* First calculate the cost assuming we do
514 not insert or delete above this line.
515 That is, if we update through line i-1
516 based on old lines through j-1,
517 and then just change old line j to new line i.
519 Depending on which choice gives the lower cost,
520 this usually involves either scrolling a single line
521 or extending a sequence of scrolled lines, but
522 when i == j, no scrolling is required. */
523 p1 = p - window_size - 2; /* matrix [i-1, j-1] */
524 cost = p1->insertcost;
525 if (cost > p1->deletecost)
526 cost = p1->deletecost;
527 cost1 = p1->writecost;
528 if (i == j)
530 if (cost > cost1)
532 cost = cost1;
533 p->writecount = p1->writecount + 1;
535 else
536 p->writecount = 1;
537 if (old_hash[j] != new_hash[i])
539 cost += draw_cost[i];
542 else
544 if (i > j)
546 delta = i - j;
548 /* The cost added here for scrolling the first line by
549 a distance N includes the overhead of setting the
550 scroll window, the cost of inserting N lines at a
551 position N lines above the bottom line of the window,
552 and an extra cost which is proportional to N. */
553 cost += scroll_overhead + first_insert_cost[-delta] +
554 (delta-1) * (next_insert_cost[-delta] + extra_cost);
556 /* In the most general case, the insertion overhead and
557 the multiply factor can grow linearly as the distance
558 from the bottom of the window increases. The incremental
559 cost of scrolling an additional line depends upon the
560 rate of change of these two parameters. Each of these
561 growth rates can be determined by a simple difference.
562 To reduce the cumulative effects of rounding error, we
563 vary the position at which the difference is computed. */
564 cost1 += first_insert_cost[-j] - first_insert_cost[1-j] +
565 (delta-1) * (next_insert_cost[-j] - next_insert_cost[1-j]);
567 else
569 delta = j - i;
570 cost += scroll_overhead + first_delete_cost[-delta] +
571 (delta-1) * (next_delete_cost[-delta] + extra_cost);
572 cost1 += first_delete_cost[-i] - first_delete_cost[1-i] +
573 (delta-1) * ( next_delete_cost[-i] - next_delete_cost[1-i]);
575 if (cost1 < cost)
577 cost = cost1;
578 p->writecount = p1->writecount + 1;
580 else
581 p->writecount = 1;
582 if (old_hash[j] != new_hash[i])
584 cost += draw_cost[i] + old_draw_cost[j];
587 p->writecost = cost;
589 /* Calculate the cost if we do an insert-line
590 before outputting this line.
591 That is, we update through line i-1
592 based on old lines through j,
593 do an insert-line on line i,
594 and then output line i from scratch,
595 leaving old lines starting from j for reuse below. */
596 p1 = p - window_size - 1; /* matrix [i-1, j] */
597 cost = p1->writecost;
598 /* If i > j, an insert is allowed after a delete. */
599 if (i > j && p1->deletecost < cost)
600 cost = p1->deletecost;
601 if (p1->insertcost <= cost)
603 cost = p1->insertcost;
604 p->insertcount = p1->insertcount + 1;
606 else
607 p->insertcount = 1;
608 cost += draw_cost[i];
609 p->insertcost = cost;
611 /* Calculate the cost if we do a delete line after
612 outputting this line.
613 That is, we update through line i
614 based on old lines through j-1,
615 and throw away old line j. */
616 p1 = p - 1; /* matrix [i, j-1] */
617 cost = p1->writecost;
618 /* If i < j, a delete is allowed after an insert. */
619 if (i < j && p1->insertcost < cost)
620 cost = p1->insertcost;
621 cost1 = p1->deletecost;
622 if (p1->deletecost <= cost)
624 cost = p1->deletecost;
625 p->deletecount = p1->deletecount + 1;
627 else
628 p->deletecount = 1;
629 p->deletecost = cost;
635 /* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
636 according to the costs in MATRIX, using the direct scrolling method
637 which is used when the terminal supports setting a scroll window
638 (scroll_region_ok).
640 WINDOW_SIZE is the number of lines being considered for scrolling
641 and UNCHANGED_AT_TOP is the vpos of the first line being
642 considered. These two arguments can specify any contiguous range
643 of lines.
645 In the direct scrolling method, a new scroll window is selected
646 before each insertion or deletion, so that groups of lines can be
647 scrolled directly to their final vertical positions. This method
648 is described in more detail in calculate_direct_scrolling, where
649 the cost matrix for this approach is constructed. */
651 static void
652 do_direct_scrolling (current_matrix, cost_matrix, window_size,
653 unchanged_at_top)
654 struct glyph_matrix *current_matrix;
655 struct matrix_elt *cost_matrix;
656 int window_size;
657 int unchanged_at_top;
659 struct matrix_elt *p;
660 int i, j;
662 /* A queue of deletions and insertions to be performed. */
663 struct alt_queue { int count, pos, window; };
664 struct alt_queue *queue_start = (struct alt_queue *)
665 alloca (window_size * sizeof *queue_start);
666 struct alt_queue *queue = queue_start;
668 /* Set to 1 if a terminal window has been set with
669 set_terminal_window: */
670 int terminal_window_p = 0;
672 /* A nonzero value of write_follows indicates that a write has been
673 selected, allowing either an insert or a delete to be selected
674 next. When write_follows is zero, a delete cannot be selected
675 unless j < i, and an insert cannot be selected unless i < j.
676 This corresponds to a similar restriction (with the ordering
677 reversed) in calculate_direct_scrolling, which is intended to
678 ensure that lines marked as inserted will be blank. */
679 int write_follows_p = 1;
681 /* For each row in the new matrix what row of the old matrix it is. */
682 int *copy_from = (int *) alloca (window_size * sizeof (int));
684 /* Non-zero for each row in the new matrix that is retained from the
685 old matrix. Lines not retained are empty. */
686 char *retained_p = (char *) alloca (window_size * sizeof (char));
688 bzero (retained_p, window_size * sizeof (char));
690 /* Perform some sanity checks when GLYPH_DEBUG is on. */
691 CHECK_MATRIX (current_matrix);
693 /* We are working on the line range UNCHANGED_AT_TOP ...
694 UNCHANGED_AT_TOP + WINDOW_SIZE (not including) in CURRENT_MATRIX.
695 We step through lines in this range from the end to the start. I
696 is an index into new lines, j an index into old lines. The cost
697 matrix determines what to do for ranges of indices.
699 If i is decremented without also decrementing j, this corresponds
700 to inserting empty lines in the result. If j is decremented
701 without also decrementing i, this corresponds to omitting these
702 lines in the new rows, i.e. rows are deleted. */
703 i = j = window_size;
705 while (i > 0 || j > 0)
707 p = cost_matrix + i * (window_size + 1) + j;
709 if (p->insertcost < p->writecost
710 && p->insertcost < p->deletecost
711 && (write_follows_p || i < j))
713 /* Insert is cheaper than deleting or writing lines. Leave
714 a hole in the result display that will be filled with
715 empty lines when the queue is emptied. */
716 queue->count = 0;
717 queue->window = i;
718 queue->pos = i - p->insertcount;
719 ++queue;
721 i -= p->insertcount;
722 write_follows_p = 0;
724 else if (p->deletecost < p->writecost
725 && (write_follows_p || i > j))
727 /* Deleting lines is cheaper. By decrementing J, omit
728 deletecount lines from the original. */
729 write_follows_p = 0;
730 j -= p->deletecount;
732 else
734 /* One or more lines should be written. In the direct
735 scrolling method we do this by scrolling the lines to the
736 place they belong. */
737 int n_to_write = p->writecount;
738 write_follows_p = 1;
739 xassert (n_to_write > 0);
741 if (i > j)
743 /* Immediately insert lines */
744 set_terminal_window (i + unchanged_at_top);
745 terminal_window_p = 1;
746 ins_del_lines (j - n_to_write + unchanged_at_top, i - j);
748 else if (i < j)
750 /* Queue the deletion of a group of lines */
751 queue->pos = i - n_to_write + unchanged_at_top;
752 queue->window = j + unchanged_at_top;
753 queue->count = i - j;
754 ++queue;
757 while (n_to_write > 0)
759 --i, --j, --n_to_write;
760 copy_from[i] = j;
761 retained_p[j] = 1;
766 /* Do queued operations. */
767 if (queue > queue_start)
769 int next = -1;
773 --queue;
774 if (queue->count)
776 set_terminal_window (queue->window);
777 terminal_window_p = 1;
778 ins_del_lines (queue->pos, queue->count);
780 else
782 for (j = queue->window - 1; j >= queue->pos; --j)
784 while (retained_p[++next])
786 copy_from[j] = next;
790 while (queue > queue_start);
793 /* Now, for each row I in the range of rows we are working on,
794 copy_from[i] gives the original line to copy to I, and
795 retained_p[copy_from[i]] is zero if line I in the new display is
796 empty. */
797 mirrored_line_dance (current_matrix, unchanged_at_top, window_size,
798 copy_from, retained_p);
800 if (terminal_window_p)
801 set_terminal_window (0);
806 void
807 scrolling_1 (frame, window_size, unchanged_at_top, unchanged_at_bottom,
808 draw_cost, old_draw_cost, old_hash, new_hash, free_at_end)
809 FRAME_PTR frame;
810 int window_size, unchanged_at_top, unchanged_at_bottom;
811 int *draw_cost;
812 int *old_draw_cost;
813 int *old_hash;
814 int *new_hash;
815 int free_at_end;
817 struct matrix_elt *matrix;
818 matrix = ((struct matrix_elt *)
819 alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
821 if (scroll_region_ok)
823 calculate_direct_scrolling (frame, matrix, window_size,
824 unchanged_at_bottom,
825 draw_cost, old_draw_cost,
826 old_hash, new_hash, free_at_end);
827 do_direct_scrolling (frame->current_matrix,
828 matrix, window_size, unchanged_at_top);
830 else
832 calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
833 draw_cost, old_hash, new_hash,
834 free_at_end);
835 do_scrolling (frame->current_matrix, matrix, window_size,
836 unchanged_at_top);
842 /* Return number of lines in common between current and desired frame
843 contents described to us only as vectors of hash codes OLDHASH and
844 NEWHASH. Consider only vpos range START to END (not including
845 END). Ignore short lines on the assumption that avoiding redrawing
846 such a line will have little weight. */
849 scrolling_max_lines_saved (start, end, oldhash, newhash, cost)
850 int start, end;
851 int *oldhash, *newhash, *cost;
853 struct { int hash; int count; } lines[01000];
854 register int i, h;
855 register int matchcount = 0;
856 int avg_length = 0;
857 int threshold;
859 /* Compute a threshold which is 1/4 of average length of these lines. */
861 for (i = start; i < end; i++)
862 avg_length += cost[i];
864 avg_length /= end - start;
865 threshold = avg_length / 4;
867 bzero (lines, sizeof lines);
869 /* Put new lines' hash codes in hash table. Ignore lines shorter
870 than the threshold. Thus, if the lines that are in common are
871 mainly the ones that are short, they won't count. */
872 for (i = start; i < end; i++)
874 if (cost[i] > threshold)
876 h = newhash[i] & 0777;
877 lines[h].hash = newhash[i];
878 lines[h].count++;
882 /* Look up old line hash codes in the hash table. Count number of
883 matches between old lines and new. */
884 for (i = start; i < end; i++)
886 h = oldhash[i] & 0777;
887 if (oldhash[i] == lines[h].hash)
889 matchcount++;
890 if (--lines[h].count == 0)
891 lines[h].hash = 0;
895 return matchcount;
898 /* Return a measure of the cost of moving the lines starting with vpos
899 FROM, up to but not including vpos TO, down by AMOUNT lines (AMOUNT
900 may be negative). These are the same arguments that might be given
901 to scroll_frame_lines to perform this scrolling. */
904 scroll_cost (frame, from, to, amount)
905 FRAME_PTR frame;
906 int from, to, amount;
908 /* Compute how many lines, at bottom of frame,
909 will not be involved in actual motion. */
910 int limit = to;
911 int offset;
912 int height = FRAME_LINES (frame);
914 if (amount == 0)
915 return 0;
917 if (! scroll_region_ok)
918 limit = height;
919 else if (amount > 0)
920 limit += amount;
922 if (amount < 0)
924 int temp = to;
925 to = from + amount;
926 from = temp + amount;
927 amount = - amount;
930 offset = height - limit;
932 return
933 (FRAME_INSERT_COST (frame)[offset + from]
934 + (amount - 1) * FRAME_INSERTN_COST (frame)[offset + from]
935 + FRAME_DELETE_COST (frame)[offset + to]
936 + (amount - 1) * FRAME_DELETEN_COST (frame)[offset + to]);
939 /* Calculate the line insertion/deletion
940 overhead and multiply factor values */
942 static void
943 line_ins_del (frame, ov1, pf1, ovn, pfn, ov, mf)
944 FRAME_PTR frame;
945 int ov1, ovn;
946 int pf1, pfn;
947 register int *ov, *mf;
949 register int i;
950 register int frame_lines = FRAME_LINES (frame);
951 register int insert_overhead = ov1 * 10;
952 register int next_insert_cost = ovn * 10;
954 for (i = frame_lines-1; i >= 0; i--)
956 mf[i] = next_insert_cost / 10;
957 next_insert_cost += pfn;
958 ov[i] = (insert_overhead + next_insert_cost) / 10;
959 insert_overhead += pf1;
963 static void
964 ins_del_costs (frame,
965 one_line_string, multi_string,
966 setup_string, cleanup_string,
967 costvec, ncostvec, coefficient)
968 FRAME_PTR frame;
969 char *one_line_string, *multi_string;
970 char *setup_string, *cleanup_string;
971 int *costvec, *ncostvec;
972 int coefficient;
974 if (multi_string)
975 line_ins_del (frame,
976 string_cost (multi_string) * coefficient,
977 per_line_cost (multi_string) * coefficient,
978 0, 0, costvec, ncostvec);
979 else if (one_line_string)
980 line_ins_del (frame,
981 string_cost (setup_string) + string_cost (cleanup_string), 0,
982 string_cost (one_line_string),
983 per_line_cost (one_line_string),
984 costvec, ncostvec);
985 else
986 line_ins_del (frame,
987 9999, 0, 9999, 0,
988 costvec, ncostvec);
991 /* Calculate the insert and delete line costs.
992 Note that this is done even when running with a window system
993 because we want to know how long scrolling takes (and avoid it).
994 This must be redone whenever the frame height changes.
996 We keep the ID costs in a precomputed array based on the position
997 at which the I or D is performed. Also, there are two kinds of ID
998 costs: the "once-only" and the "repeated". This is to handle both
999 those terminals that are able to insert N lines at a time (once-
1000 only) and those that must repeatedly insert one line.
1002 The cost to insert N lines at line L is
1003 [tt.t_ILov + (frame_lines + 1 - L) * tt.t_ILpf] +
1004 N * [tt.t_ILnov + (frame_lines + 1 - L) * tt.t_ILnpf]
1006 ILov represents the basic insert line overhead. ILpf is the padding
1007 required to allow the terminal time to move a line: insertion at line
1008 L changes (frame_lines + 1 - L) lines.
1010 The first bracketed expression above is the overhead; the second is
1011 the multiply factor. Both are dependent only on the position at
1012 which the insert is performed. We store the overhead in
1013 FRAME_INSERT_COST (frame) and the multiply factor in
1014 FRAME_INSERTN_COST (frame). Note however that any insertion
1015 must include at least one multiply factor. Rather than compute this
1016 as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line],
1017 we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame).
1018 This is reasonable because of the particular algorithm used in calcM.
1020 Deletion is essentially the same as insertion.
1023 void
1024 do_line_insertion_deletion_costs (frame,
1025 ins_line_string, multi_ins_string,
1026 del_line_string, multi_del_string,
1027 setup_string, cleanup_string, coefficient)
1028 FRAME_PTR frame;
1029 char *ins_line_string, *multi_ins_string;
1030 char *del_line_string, *multi_del_string;
1031 char *setup_string, *cleanup_string;
1032 int coefficient;
1034 if (FRAME_INSERT_COST (frame) != 0)
1036 FRAME_INSERT_COST (frame) =
1037 (int *) xrealloc (FRAME_INSERT_COST (frame),
1038 FRAME_LINES (frame) * sizeof (int));
1039 FRAME_DELETEN_COST (frame) =
1040 (int *) xrealloc (FRAME_DELETEN_COST (frame),
1041 FRAME_LINES (frame) * sizeof (int));
1042 FRAME_INSERTN_COST (frame) =
1043 (int *) xrealloc (FRAME_INSERTN_COST (frame),
1044 FRAME_LINES (frame) * sizeof (int));
1045 FRAME_DELETE_COST (frame) =
1046 (int *) xrealloc (FRAME_DELETE_COST (frame),
1047 FRAME_LINES (frame) * sizeof (int));
1049 else
1051 FRAME_INSERT_COST (frame) =
1052 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int));
1053 FRAME_DELETEN_COST (frame) =
1054 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int));
1055 FRAME_INSERTN_COST (frame) =
1056 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int));
1057 FRAME_DELETE_COST (frame) =
1058 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int));
1061 ins_del_costs (frame,
1062 ins_line_string, multi_ins_string,
1063 setup_string, cleanup_string,
1064 FRAME_INSERT_COST (frame), FRAME_INSERTN_COST (frame),
1065 coefficient);
1066 ins_del_costs (frame,
1067 del_line_string, multi_del_string,
1068 setup_string, cleanup_string,
1069 FRAME_DELETE_COST (frame), FRAME_DELETEN_COST (frame),
1070 coefficient);
1073 /* arch-tag: cdb7149c-48e7-4793-a948-2786c8e45485
1074 (do not change this comment) */