]>
code.delx.au - gnu-emacs/blob - src/scroll.c
1 /* Calculate what line insertion or deletion to do, and do it,
2 Copyright (C) 1985-1986, 1990, 1993-1994, 2001-2011 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 3 of the License, or
9 (at your option) 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. If not, see <http://www.gnu.org/licenses/>. */
25 #include "dispextern.h"
29 #include "termhooks.h"
31 /* All costs measured in characters.
32 So no cost can exceed the area of a frame, measured in characters.
33 Let's hope this is never more than 1000000 characters. */
35 #define INFINITY 1000000
39 /* Cost of outputting through this line
40 if no insert/delete is done just above it. */
42 /* Cost of outputting through this line
43 if an insert is done just above it. */
45 /* Cost of outputting through this line
46 if a delete is done just above it. */
48 /* Number of inserts so far in this run of inserts,
49 for the cost in insertcost. */
50 unsigned char insertcount
;
51 /* Number of deletes so far in this run of deletes,
52 for the cost in deletecost. */
53 unsigned char deletecount
;
54 /* Number of writes so far since the last insert
55 or delete for the cost in writecost. */
56 unsigned char writecount
;
59 static void do_direct_scrolling (struct frame
*,
60 struct glyph_matrix
*,
63 static void do_scrolling (struct frame
*,
64 struct glyph_matrix
*,
69 /* Determine, in matrix[i,j], the cost of updating the first j old
70 lines into the first i new lines using the general scrolling method.
71 This involves using insert or delete somewhere if i != j.
72 For each matrix elements, three kinds of costs are recorded:
73 the smallest cost that ends with an insert, the smallest
74 cost that ends with a delete, and the smallest cost that
75 ends with neither one. These are kept separate because
76 on some terminals the cost of doing an insert varies
77 depending on whether one was just done, etc. */
79 /* draw_cost[VPOS] is the cost of outputting new line at VPOS.
80 old_hash[VPOS] is the hash code of the old line at VPOS.
81 new_hash[VPOS] is the hash code of the new line at VPOS.
82 Note that these are not true frame vpos's, but relative
83 to the place at which the first mismatch between old and
84 new contents appears. */
87 calculate_scrolling (FRAME_PTR frame
,
88 /* matrix is of size window_size + 1 on each side. */
89 struct matrix_elt
*matrix
,
90 int window_size
, int lines_below
,
91 int *draw_cost
, int *old_hash
, int *new_hash
,
95 EMACS_INT frame_lines
= FRAME_LINES (frame
);
96 register struct matrix_elt
*p
, *p1
;
97 register int cost
, cost1
;
99 int lines_moved
= window_size
100 + (FRAME_SCROLL_REGION_OK (frame
) ? 0 : lines_below
);
101 /* first_insert_cost[I] is the cost of doing the first insert-line
102 at the i'th line of the lines we are considering,
103 where I is origin 1 (as it is below). */
104 int *first_insert_cost
105 = &FRAME_INSERT_COST (frame
)[frame_lines
- 1 - lines_moved
];
106 int *first_delete_cost
107 = &FRAME_DELETE_COST (frame
)[frame_lines
- 1 - lines_moved
];
108 int *next_insert_cost
109 = &FRAME_INSERTN_COST (frame
)[frame_lines
- 1 - lines_moved
];
110 int *next_delete_cost
111 = &FRAME_DELETEN_COST (frame
)[frame_lines
- 1 - lines_moved
];
113 /* Discourage long scrolls on fast lines.
114 Don't scroll nearly a full frame height unless it saves
115 at least 1/4 second. */
116 int extra_cost
= (int) (baud_rate
/ (10 * 4 * FRAME_LINES (frame
)));
121 /* initialize the top left corner of the matrix */
122 matrix
->writecost
= 0;
123 matrix
->insertcost
= INFINITY
;
124 matrix
->deletecost
= INFINITY
;
125 matrix
->insertcount
= 0;
126 matrix
->deletecount
= 0;
128 /* initialize the left edge of the matrix */
129 cost
= first_insert_cost
[1] - next_insert_cost
[1];
130 for (i
= 1; i
<= window_size
; i
++)
132 p
= matrix
+ i
* (window_size
+ 1);
133 cost
+= draw_cost
[i
] + next_insert_cost
[i
] + extra_cost
;
134 p
->insertcost
= cost
;
135 p
->writecost
= INFINITY
;
136 p
->deletecost
= INFINITY
;
141 /* initialize the top edge of the matrix */
142 cost
= first_delete_cost
[1] - next_delete_cost
[1];
143 for (j
= 1; j
<= window_size
; j
++)
145 cost
+= next_delete_cost
[j
];
146 matrix
[j
].deletecost
= cost
;
147 matrix
[j
].writecost
= INFINITY
;
148 matrix
[j
].insertcost
= INFINITY
;
149 matrix
[j
].deletecount
= j
;
150 matrix
[j
].insertcount
= 0;
153 /* `i' represents the vpos among new frame contents.
154 `j' represents the vpos among the old frame contents. */
155 p
= matrix
+ window_size
+ 2; /* matrix [1, 1] */
156 for (i
= 1; i
<= window_size
; i
++, p
++)
157 for (j
= 1; j
<= window_size
; j
++, p
++)
159 /* p contains the address of matrix [i, j] */
161 /* First calculate the cost assuming we do
162 not insert or delete above this line.
163 That is, if we update through line i-1
164 based on old lines through j-1,
165 and then just change old line j to new line i. */
166 p1
= p
- window_size
- 2; /* matrix [i-1, j-1] */
167 cost
= p1
->writecost
;
168 if (cost
> p1
->insertcost
)
169 cost
= p1
->insertcost
;
170 if (cost
> p1
->deletecost
)
171 cost
= p1
->deletecost
;
172 if (old_hash
[j
] != new_hash
[i
])
173 cost
+= draw_cost
[i
];
176 /* Calculate the cost if we do an insert-line
177 before outputting this line.
178 That is, we update through line i-1
179 based on old lines through j,
180 do an insert-line on line i,
181 and then output line i from scratch,
182 leaving old lines starting from j for reuse below. */
183 p1
= p
- window_size
- 1; /* matrix [i-1, j] */
184 /* No need to think about doing a delete followed
185 immediately by an insert. It cannot be as good
186 as not doing either of them. */
187 if (free_at_end
== i
)
189 cost
= p1
->writecost
;
190 cost1
= p1
->insertcost
;
194 cost
= p1
->writecost
+ first_insert_cost
[i
];
195 if ((int) p1
->insertcount
> i
)
197 cost1
= p1
->insertcost
+ next_insert_cost
[i
- p1
->insertcount
];
199 p
->insertcost
= min (cost
, cost1
) + draw_cost
[i
] + extra_cost
;
200 p
->insertcount
= (cost
< cost1
) ? 1 : p1
->insertcount
+ 1;
201 if ((int) p
->insertcount
> i
)
204 /* Calculate the cost if we do a delete line after
205 outputting this line.
206 That is, we update through line i
207 based on old lines through j-1,
208 and throw away old line j. */
209 p1
= p
- 1; /* matrix [i, j-1] */
210 /* No need to think about doing an insert followed
211 immediately by a delete. */
212 if (free_at_end
== i
)
214 cost
= p1
->writecost
;
215 cost1
= p1
->deletecost
;
219 cost
= p1
->writecost
+ first_delete_cost
[i
];
220 cost1
= p1
->deletecost
+ next_delete_cost
[i
];
222 p
->deletecost
= min (cost
, cost1
);
223 p
->deletecount
= (cost
< cost1
) ? 1 : p1
->deletecount
+ 1;
229 /* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
230 according to the costs in MATRIX, using the general scrolling
231 method that is used if the terminal does not support the setting of
232 scroll windows (scroll_region_ok == 0).
234 WINDOW_SIZE is the number of lines being considered for scrolling
235 and UNCHANGED_AT_TOP is the vpos of the first line being
236 considered. These two arguments can specify any contiguous range
240 do_scrolling (struct frame
*frame
, struct glyph_matrix
*current_matrix
, struct matrix_elt
*matrix
, int window_size
, int unchanged_at_top
)
242 struct matrix_elt
*p
;
245 /* Set to 1 if we have set a terminal window with
246 set_terminal_window. */
247 int terminal_window_p
= 0;
249 /* A queue for line insertions to be done. */
250 struct queue
{ int count
, pos
; };
251 struct queue
*queue_start
252 = (struct queue
*) alloca (current_matrix
->nrows
* sizeof (struct queue
));
253 struct queue
*queue
= queue_start
;
255 char *retained_p
= (char *) alloca (window_size
* sizeof (char));
256 int *copy_from
= (int *) alloca (window_size
* sizeof (int));
258 /* Zero means line is empty. */
259 memset (retained_p
, 0, window_size
* sizeof (char));
260 for (k
= 0; k
< window_size
; ++k
)
263 #define CHECK_BOUNDS \
267 for (k = 0; k < window_size; ++k) \
268 xassert (copy_from[k] == -1 \
269 || (copy_from[k] >= 0 && copy_from[k] < window_size)); \
273 /* When j is advanced, this corresponds to deleted lines.
274 When i is advanced, this corresponds to inserted lines. */
276 while (i
> 0 || j
> 0)
278 p
= matrix
+ i
* (window_size
+ 1) + j
;
280 if (p
->insertcost
< p
->writecost
&& p
->insertcost
< p
->deletecost
)
282 /* Insert should be done at vpos i-1, plus maybe some before.
283 Queue the screen operation to be performed. */
284 queue
->count
= p
->insertcount
;
285 queue
->pos
= i
+ unchanged_at_top
- p
->insertcount
;
288 /* By incrementing I, we leave room in the result rows
289 for the empty rows opened up. */
292 else if (p
->deletecost
< p
->writecost
)
294 /* Old line at vpos j-1, and maybe some before it, should be
295 deleted. By decrementing J, we skip some lines in the
296 temp_rows which is equivalent to omitting these lines in
297 the result rows, thus deleting them. */
300 /* Set the terminal window, if not done already. */
301 if (! terminal_window_p
)
303 set_terminal_window (frame
, window_size
+ unchanged_at_top
);
304 terminal_window_p
= 1;
307 /* Delete lines on the terminal. */
308 ins_del_lines (frame
, j
+ unchanged_at_top
, - p
->deletecount
);
312 /* Best thing done here is no insert or delete, i.e. a write. */
314 xassert (i
>= 0 && i
< window_size
);
315 xassert (j
>= 0 && j
< window_size
);
325 /* Now do all insertions queued above. */
326 if (queue
> queue_start
)
330 /* Set the terminal window if not yet done. */
331 if (!terminal_window_p
)
333 set_terminal_window (frame
, window_size
+ unchanged_at_top
);
334 terminal_window_p
= 1;
341 /* Do the deletion on the terminal. */
342 ins_del_lines (frame
, queue
->pos
, queue
->count
);
344 /* All lines in the range deleted become empty in the glyph
345 matrix. Assign to them glyph rows that are not retained.
346 K is the starting position of the deleted range relative
347 to the window we are working in. */
348 k
= queue
->pos
- unchanged_at_top
;
349 for (j
= 0; j
< queue
->count
; ++j
)
351 /* Find the next row not retained. */
352 while (retained_p
[++next
])
355 /* Record that this row is to be used for the empty
357 copy_from
[k
+ j
] = next
;
360 while (queue
> queue_start
);
364 for (k
= 0; k
< window_size
; ++k
)
365 xassert (copy_from
[k
] >= 0 && copy_from
[k
] < window_size
);
367 /* Perform the row swizzling. */
368 mirrored_line_dance (current_matrix
, unchanged_at_top
, window_size
,
369 copy_from
, retained_p
);
371 /* Some sanity checks if GLYPH_DEBUG != 0. */
372 CHECK_MATRIX (current_matrix
);
374 if (terminal_window_p
)
375 set_terminal_window (frame
, 0);
379 /* Determine, in matrix[i,j], the cost of updating the first j
380 old lines into the first i new lines using the direct
381 scrolling method. When the old line and the new line have
382 different hash codes, the calculated cost of updating old
383 line j into new line i includes the cost of outputting new
384 line i, and if i != j, the cost of outputting the old line j
385 is also included, as a penalty for moving the line and then
386 erasing it. In addition, the cost of updating a sequence of
387 lines with constant i - j includes the cost of scrolling the
388 old lines into their new positions, unless i == j. Scrolling
389 is achieved by setting the screen window to avoid affecting
390 other lines below, and inserting or deleting lines at the top
391 of the scrolled region. The cost of scrolling a sequence of
392 lines includes the fixed cost of specifying a scroll region,
393 plus a variable cost which can depend upon the number of lines
394 involved and the distance by which they are scrolled, and an
395 extra cost to discourage long scrolls.
397 As reflected in the matrix, an insert or delete does not
398 correspond directly to the insertion or deletion which is
399 used in scrolling lines. An insert means that the value of i
400 has increased without a corresponding increase in the value
401 of j. A delete means that the value of j has increased
402 without a corresponding increase in the value of i. A write
403 means that i and j are both increased by the same amount, and
404 that the old lines will be moved to their new positions.
406 An insert following a delete is allowed only if i > j.
407 A delete following an insert is allowed only if i < j.
408 These restrictions ensure that the new lines in an insert
409 will always be blank as an effect of the neighboring writes.
410 Thus the calculated cost of an insert is simply the cost of
411 outputting the new line contents. The direct cost of a
412 delete is zero. Inserts and deletes indirectly affect the
413 total cost through their influence on subsequent writes. */
415 /* The vectors draw_cost, old_hash, and new_hash have the same
416 meanings here as in calculate_scrolling, and old_draw_cost
417 is the equivalent of draw_cost for the old line contents */
420 calculate_direct_scrolling (FRAME_PTR frame
,
421 /* matrix is of size window_size + 1 on each side. */
422 struct matrix_elt
*matrix
,
423 int window_size
, int lines_below
,
424 int *draw_cost
, int *old_draw_cost
,
425 int *old_hash
, int *new_hash
,
429 EMACS_INT frame_lines
= FRAME_LINES (frame
);
430 register struct matrix_elt
*p
, *p1
;
431 register int cost
, cost1
, delta
;
433 /* first_insert_cost[-I] is the cost of doing the first insert-line
434 at a position I lines above the bottom line in the scroll window. */
435 int *first_insert_cost
436 = &FRAME_INSERT_COST (frame
)[frame_lines
- 1];
437 int *first_delete_cost
438 = &FRAME_DELETE_COST (frame
)[frame_lines
- 1];
439 int *next_insert_cost
440 = &FRAME_INSERTN_COST (frame
)[frame_lines
- 1];
441 int *next_delete_cost
442 = &FRAME_DELETEN_COST (frame
)[frame_lines
- 1];
446 /* Discourage long scrolls on fast lines.
447 Don't scroll nearly a full frame height unless it saves
448 at least 1/4 second. */
449 int extra_cost
= (int) (baud_rate
/ (10 * 4 * FRAME_LINES (frame
)));
454 /* Overhead of setting the scroll window, plus the extra cost
455 cost of scrolling by a distance of one. The extra cost is
456 added once for consistency with the cost vectors */
458 = FRAME_SCROLL_REGION_COST (frame
) + extra_cost
;
460 /* initialize the top left corner of the matrix */
461 matrix
->writecost
= 0;
462 matrix
->insertcost
= INFINITY
;
463 matrix
->deletecost
= INFINITY
;
464 matrix
->writecount
= 0;
465 matrix
->insertcount
= 0;
466 matrix
->deletecount
= 0;
468 /* initialize the left edge of the matrix */
470 for (i
= 1; i
<= window_size
; i
++)
472 p
= matrix
+ i
* (window_size
+ 1);
473 cost
+= draw_cost
[i
];
474 p
->insertcost
= cost
;
475 p
->writecost
= INFINITY
;
476 p
->deletecost
= INFINITY
;
482 /* initialize the top edge of the matrix */
483 for (j
= 1; j
<= window_size
; j
++)
485 matrix
[j
].deletecost
= 0;
486 matrix
[j
].writecost
= INFINITY
;
487 matrix
[j
].insertcost
= INFINITY
;
488 matrix
[j
].deletecount
= j
;
489 matrix
[j
].writecount
= 0;
490 matrix
[j
].insertcount
= 0;
493 /* `i' represents the vpos among new frame contents.
494 `j' represents the vpos among the old frame contents. */
495 p
= matrix
+ window_size
+ 2; /* matrix [1, 1] */
497 for (i
= 1; i
<= window_size
; i
++, p
++)
498 for (j
= 1; j
<= window_size
; j
++, p
++)
500 /* p contains the address of matrix [i, j] */
502 /* First calculate the cost assuming we do
503 not insert or delete above this line.
504 That is, if we update through line i-1
505 based on old lines through j-1,
506 and then just change old line j to new line i.
508 Depending on which choice gives the lower cost,
509 this usually involves either scrolling a single line
510 or extending a sequence of scrolled lines, but
511 when i == j, no scrolling is required. */
512 p1
= p
- window_size
- 2; /* matrix [i-1, j-1] */
513 cost
= p1
->insertcost
;
514 if (cost
> p1
->deletecost
)
515 cost
= p1
->deletecost
;
516 cost1
= p1
->writecost
;
522 p
->writecount
= p1
->writecount
+ 1;
526 if (old_hash
[j
] != new_hash
[i
])
528 cost
+= draw_cost
[i
];
537 /* The cost added here for scrolling the first line by
538 a distance N includes the overhead of setting the
539 scroll window, the cost of inserting N lines at a
540 position N lines above the bottom line of the window,
541 and an extra cost which is proportional to N. */
542 cost
+= scroll_overhead
+ first_insert_cost
[-delta
] +
543 (delta
-1) * (next_insert_cost
[-delta
] + extra_cost
);
545 /* In the most general case, the insertion overhead and
546 the multiply factor can grow linearly as the distance
547 from the bottom of the window increases. The incremental
548 cost of scrolling an additional line depends upon the
549 rate of change of these two parameters. Each of these
550 growth rates can be determined by a simple difference.
551 To reduce the cumulative effects of rounding error, we
552 vary the position at which the difference is computed. */
553 cost1
+= first_insert_cost
[-j
] - first_insert_cost
[1-j
] +
554 (delta
-1) * (next_insert_cost
[-j
] - next_insert_cost
[1-j
]);
559 cost
+= scroll_overhead
+ first_delete_cost
[-delta
] +
560 (delta
-1) * (next_delete_cost
[-delta
] + extra_cost
);
561 cost1
+= first_delete_cost
[-i
] - first_delete_cost
[1-i
] +
562 (delta
-1) * ( next_delete_cost
[-i
] - next_delete_cost
[1-i
]);
567 p
->writecount
= p1
->writecount
+ 1;
571 if (old_hash
[j
] != new_hash
[i
])
573 cost
+= draw_cost
[i
] + old_draw_cost
[j
];
578 /* Calculate the cost if we do an insert-line
579 before outputting this line.
580 That is, we update through line i-1
581 based on old lines through j,
582 do an insert-line on line i,
583 and then output line i from scratch,
584 leaving old lines starting from j for reuse below. */
585 p1
= p
- window_size
- 1; /* matrix [i-1, j] */
586 cost
= p1
->writecost
;
587 /* If i > j, an insert is allowed after a delete. */
588 if (i
> j
&& p1
->deletecost
< cost
)
589 cost
= p1
->deletecost
;
590 if (p1
->insertcost
<= cost
)
592 cost
= p1
->insertcost
;
593 p
->insertcount
= p1
->insertcount
+ 1;
597 cost
+= draw_cost
[i
];
598 p
->insertcost
= cost
;
600 /* Calculate the cost if we do a delete line after
601 outputting this line.
602 That is, we update through line i
603 based on old lines through j-1,
604 and throw away old line j. */
605 p1
= p
- 1; /* matrix [i, j-1] */
606 cost
= p1
->writecost
;
607 /* If i < j, a delete is allowed after an insert. */
608 if (i
< j
&& p1
->insertcost
< cost
)
609 cost
= p1
->insertcost
;
610 cost1
= p1
->deletecost
;
611 if (p1
->deletecost
<= cost
)
613 cost
= p1
->deletecost
;
614 p
->deletecount
= p1
->deletecount
+ 1;
618 p
->deletecost
= cost
;
624 /* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
625 according to the costs in MATRIX, using the direct scrolling method
626 which is used when the terminal supports setting a scroll window
629 WINDOW_SIZE is the number of lines being considered for scrolling
630 and UNCHANGED_AT_TOP is the vpos of the first line being
631 considered. These two arguments can specify any contiguous range
634 In the direct scrolling method, a new scroll window is selected
635 before each insertion or deletion, so that groups of lines can be
636 scrolled directly to their final vertical positions. This method
637 is described in more detail in calculate_direct_scrolling, where
638 the cost matrix for this approach is constructed. */
641 do_direct_scrolling (struct frame
*frame
, struct glyph_matrix
*current_matrix
,
642 struct matrix_elt
*cost_matrix
, int window_size
,
643 int unchanged_at_top
)
645 struct matrix_elt
*p
;
648 /* A queue of deletions and insertions to be performed. */
649 struct alt_queue
{ int count
, pos
, window
; };
650 struct alt_queue
*queue_start
= (struct alt_queue
*)
651 alloca (window_size
* sizeof *queue_start
);
652 struct alt_queue
*queue
= queue_start
;
654 /* Set to 1 if a terminal window has been set with
655 set_terminal_window: */
656 int terminal_window_p
= 0;
658 /* A nonzero value of write_follows indicates that a write has been
659 selected, allowing either an insert or a delete to be selected
660 next. When write_follows is zero, a delete cannot be selected
661 unless j < i, and an insert cannot be selected unless i < j.
662 This corresponds to a similar restriction (with the ordering
663 reversed) in calculate_direct_scrolling, which is intended to
664 ensure that lines marked as inserted will be blank. */
665 int write_follows_p
= 1;
667 /* For each row in the new matrix what row of the old matrix it is. */
668 int *copy_from
= (int *) alloca (window_size
* sizeof (int));
670 /* Non-zero for each row in the new matrix that is retained from the
671 old matrix. Lines not retained are empty. */
672 char *retained_p
= (char *) alloca (window_size
* sizeof (char));
674 memset (retained_p
, 0, window_size
* sizeof (char));
676 /* Perform some sanity checks when GLYPH_DEBUG is on. */
677 CHECK_MATRIX (current_matrix
);
679 /* We are working on the line range UNCHANGED_AT_TOP ...
680 UNCHANGED_AT_TOP + WINDOW_SIZE (not including) in CURRENT_MATRIX.
681 We step through lines in this range from the end to the start. I
682 is an index into new lines, j an index into old lines. The cost
683 matrix determines what to do for ranges of indices.
685 If i is decremented without also decrementing j, this corresponds
686 to inserting empty lines in the result. If j is decremented
687 without also decrementing i, this corresponds to omitting these
688 lines in the new rows, i.e. rows are deleted. */
691 while (i
> 0 || j
> 0)
693 p
= cost_matrix
+ i
* (window_size
+ 1) + j
;
695 if (p
->insertcost
< p
->writecost
696 && p
->insertcost
< p
->deletecost
697 && (write_follows_p
|| i
< j
))
699 /* Insert is cheaper than deleting or writing lines. Leave
700 a hole in the result display that will be filled with
701 empty lines when the queue is emptied. */
704 queue
->pos
= i
- p
->insertcount
;
710 else if (p
->deletecost
< p
->writecost
711 && (write_follows_p
|| i
> j
))
713 /* Deleting lines is cheaper. By decrementing J, omit
714 deletecount lines from the original. */
720 /* One or more lines should be written. In the direct
721 scrolling method we do this by scrolling the lines to the
722 place they belong. */
723 int n_to_write
= p
->writecount
;
725 xassert (n_to_write
> 0);
729 /* Immediately insert lines */
730 set_terminal_window (frame
, i
+ unchanged_at_top
);
731 terminal_window_p
= 1;
732 ins_del_lines (frame
, j
- n_to_write
+ unchanged_at_top
, i
- j
);
736 /* Queue the deletion of a group of lines */
737 queue
->pos
= i
- n_to_write
+ unchanged_at_top
;
738 queue
->window
= j
+ unchanged_at_top
;
739 queue
->count
= i
- j
;
743 while (n_to_write
> 0)
745 --i
, --j
, --n_to_write
;
752 /* Do queued operations. */
753 if (queue
> queue_start
)
762 set_terminal_window (frame
, queue
->window
);
763 terminal_window_p
= 1;
764 ins_del_lines (frame
, queue
->pos
, queue
->count
);
768 for (j
= queue
->window
- 1; j
>= queue
->pos
; --j
)
770 while (retained_p
[++next
])
776 while (queue
> queue_start
);
779 /* Now, for each row I in the range of rows we are working on,
780 copy_from[i] gives the original line to copy to I, and
781 retained_p[copy_from[i]] is zero if line I in the new display is
783 mirrored_line_dance (current_matrix
, unchanged_at_top
, window_size
,
784 copy_from
, retained_p
);
786 if (terminal_window_p
)
787 set_terminal_window (frame
, 0);
793 scrolling_1 (FRAME_PTR frame
, int window_size
, int unchanged_at_top
,
794 int unchanged_at_bottom
, int *draw_cost
, int *old_draw_cost
,
795 int *old_hash
, int *new_hash
, int free_at_end
)
797 struct matrix_elt
*matrix
;
798 matrix
= ((struct matrix_elt
*)
799 alloca ((window_size
+ 1) * (window_size
+ 1) * sizeof *matrix
));
801 if (FRAME_SCROLL_REGION_OK (frame
))
803 calculate_direct_scrolling (frame
, matrix
, window_size
,
805 draw_cost
, old_draw_cost
,
806 old_hash
, new_hash
, free_at_end
);
807 do_direct_scrolling (frame
, frame
->current_matrix
,
808 matrix
, window_size
, unchanged_at_top
);
812 calculate_scrolling (frame
, matrix
, window_size
, unchanged_at_bottom
,
813 draw_cost
, old_hash
, new_hash
,
816 frame
->current_matrix
, matrix
, window_size
,
823 /* Return number of lines in common between current and desired frame
824 contents described to us only as vectors of hash codes OLDHASH and
825 NEWHASH. Consider only vpos range START to END (not including
826 END). Ignore short lines on the assumption that avoiding redrawing
827 such a line will have little weight. */
830 scrolling_max_lines_saved (int start
, int end
, int *oldhash
, int *newhash
, int *cost
)
832 struct { int hash
; int count
; } lines
[01000];
834 register int matchcount
= 0;
838 /* Compute a threshold which is 1/4 of average length of these lines. */
840 for (i
= start
; i
< end
; i
++)
841 avg_length
+= cost
[i
];
843 avg_length
/= end
- start
;
844 threshold
= avg_length
/ 4;
846 memset (lines
, 0, sizeof lines
);
848 /* Put new lines' hash codes in hash table. Ignore lines shorter
849 than the threshold. Thus, if the lines that are in common are
850 mainly the ones that are short, they won't count. */
851 for (i
= start
; i
< end
; i
++)
853 if (cost
[i
] > threshold
)
855 h
= newhash
[i
] & 0777;
856 lines
[h
].hash
= newhash
[i
];
861 /* Look up old line hash codes in the hash table. Count number of
862 matches between old lines and new. */
863 for (i
= start
; i
< end
; i
++)
865 h
= oldhash
[i
] & 0777;
866 if (oldhash
[i
] == lines
[h
].hash
)
869 if (--lines
[h
].count
== 0)
877 /* Return a measure of the cost of moving the lines starting with vpos
878 FROM, up to but not including vpos TO, down by AMOUNT lines (AMOUNT
882 scroll_cost (FRAME_PTR frame
, int from
, int to
, int amount
)
884 /* Compute how many lines, at bottom of frame,
885 will not be involved in actual motion. */
886 EMACS_INT limit
= to
;
888 EMACS_INT height
= FRAME_LINES (frame
);
893 if (! FRAME_SCROLL_REGION_OK (frame
))
902 from
= temp
+ amount
;
906 offset
= height
- limit
;
909 (FRAME_INSERT_COST (frame
)[offset
+ from
]
910 + (amount
- 1) * FRAME_INSERTN_COST (frame
)[offset
+ from
]
911 + FRAME_DELETE_COST (frame
)[offset
+ to
]
912 + (amount
- 1) * FRAME_DELETEN_COST (frame
)[offset
+ to
]);
915 /* Calculate the line insertion/deletion
916 overhead and multiply factor values */
919 line_ins_del (FRAME_PTR frame
, int ov1
, int pf1
, int ovn
, int pfn
, register int *ov
, register int *mf
)
921 register EMACS_INT i
;
922 register EMACS_INT frame_lines
= FRAME_LINES (frame
);
923 register int insert_overhead
= ov1
* 10;
924 register int next_insert_cost
= ovn
* 10;
926 for (i
= frame_lines
-1; i
>= 0; i
--)
928 mf
[i
] = next_insert_cost
/ 10;
929 next_insert_cost
+= pfn
;
930 ov
[i
] = (insert_overhead
+ next_insert_cost
) / 10;
931 insert_overhead
+= pf1
;
936 ins_del_costs (FRAME_PTR frame
,
937 char *one_line_string
, char *multi_string
,
938 char *setup_string
, char *cleanup_string
,
939 int *costvec
, int *ncostvec
,
944 string_cost (multi_string
) * coefficient
,
945 per_line_cost (multi_string
) * coefficient
,
946 0, 0, costvec
, ncostvec
);
947 else if (one_line_string
)
949 string_cost (setup_string
) + string_cost (cleanup_string
), 0,
950 string_cost (one_line_string
),
951 per_line_cost (one_line_string
),
959 /* Calculate the insert and delete line costs.
960 Note that this is done even when running with a window system
961 because we want to know how long scrolling takes (and avoid it).
962 This must be redone whenever the frame height changes.
964 We keep the ID costs in a precomputed array based on the position
965 at which the I or D is performed. Also, there are two kinds of ID
966 costs: the "once-only" and the "repeated". This is to handle both
967 those terminals that are able to insert N lines at a time (once-
968 only) and those that must repeatedly insert one line.
970 The cost to insert N lines at line L is
971 [tt.t_ILov + (frame_lines + 1 - L) * tt.t_ILpf] +
972 N * [tt.t_ILnov + (frame_lines + 1 - L) * tt.t_ILnpf]
974 ILov represents the basic insert line overhead. ILpf is the padding
975 required to allow the terminal time to move a line: insertion at line
976 L changes (frame_lines + 1 - L) lines.
978 The first bracketed expression above is the overhead; the second is
979 the multiply factor. Both are dependent only on the position at
980 which the insert is performed. We store the overhead in
981 FRAME_INSERT_COST (frame) and the multiply factor in
982 FRAME_INSERTN_COST (frame). Note however that any insertion
983 must include at least one multiply factor. Rather than compute this
984 as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line],
985 we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame).
986 This is reasonable because of the particular algorithm used in calcM.
988 Deletion is essentially the same as insertion.
992 do_line_insertion_deletion_costs (FRAME_PTR frame
,
993 char *ins_line_string
, char *multi_ins_string
,
994 char *del_line_string
, char *multi_del_string
,
995 char *setup_string
, char *cleanup_string
,
998 if (FRAME_INSERT_COST (frame
) != 0)
1000 FRAME_INSERT_COST (frame
) =
1001 (int *) xrealloc (FRAME_INSERT_COST (frame
),
1002 FRAME_LINES (frame
) * sizeof (int));
1003 FRAME_DELETEN_COST (frame
) =
1004 (int *) xrealloc (FRAME_DELETEN_COST (frame
),
1005 FRAME_LINES (frame
) * sizeof (int));
1006 FRAME_INSERTN_COST (frame
) =
1007 (int *) xrealloc (FRAME_INSERTN_COST (frame
),
1008 FRAME_LINES (frame
) * sizeof (int));
1009 FRAME_DELETE_COST (frame
) =
1010 (int *) xrealloc (FRAME_DELETE_COST (frame
),
1011 FRAME_LINES (frame
) * sizeof (int));
1015 FRAME_INSERT_COST (frame
) =
1016 (int *) xmalloc (FRAME_LINES (frame
) * sizeof (int));
1017 FRAME_DELETEN_COST (frame
) =
1018 (int *) xmalloc (FRAME_LINES (frame
) * sizeof (int));
1019 FRAME_INSERTN_COST (frame
) =
1020 (int *) xmalloc (FRAME_LINES (frame
) * sizeof (int));
1021 FRAME_DELETE_COST (frame
) =
1022 (int *) xmalloc (FRAME_LINES (frame
) * sizeof (int));
1025 ins_del_costs (frame
,
1026 ins_line_string
, multi_ins_string
,
1027 setup_string
, cleanup_string
,
1028 FRAME_INSERT_COST (frame
), FRAME_INSERTN_COST (frame
),
1030 ins_del_costs (frame
,
1031 del_line_string
, multi_del_string
,
1032 setup_string
, cleanup_string
,
1033 FRAME_DELETE_COST (frame
), FRAME_DELETEN_COST (frame
),