Merge from emacs-24; up to 2012-12-27T20:09:45Z!juri@jurta.org
[bpt/emacs.git] / src / scroll.c
1 /* Calculate what line insertion or deletion to do, and do it
2
3 Copyright (C) 1985-1986, 1990, 1993-1994, 2001-2013 Free Software
4 Foundation, Inc.
5
6 This file is part of GNU Emacs.
7
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.
12
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.
17
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/>. */
20
21
22 #include <config.h>
23 #include <stdio.h>
24
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"
32
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. */
36
37 #define INFINITY 1000000
38
39 struct matrix_elt
40 {
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;
59 };
60
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);
69
70 \f
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. */
80
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. */
87
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)
95 {
96 register int i, j;
97 int frame_lines = FRAME_LINES (frame);
98 register struct matrix_elt *p, *p1;
99 register int cost, cost1;
100
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];
114
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)));
119
120 if (baud_rate <= 0)
121 extra_cost = 1;
122
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;
129
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++)
133 {
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;
141 }
142
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++)
146 {
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;
153 }
154
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++)
160 {
161 /* p contains the address of matrix [i, j] */
162
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;
177
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)
190 {
191 cost = p1->writecost;
192 cost1 = p1->insertcost;
193 }
194 else
195 {
196 cost = p1->writecost + first_insert_cost[i];
197 if ((int) p1->insertcount > i)
198 emacs_abort ();
199 cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
200 }
201 p->insertcost = min (cost, cost1) + draw_cost[i] + extra_cost;
202 p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
203 if ((int) p->insertcount > i)
204 emacs_abort ();
205
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)
215 {
216 cost = p1->writecost;
217 cost1 = p1->deletecost;
218 }
219 else
220 {
221 cost = p1->writecost + first_delete_cost[i];
222 cost1 = p1->deletecost + next_delete_cost[i];
223 }
224 p->deletecost = min (cost, cost1);
225 p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1;
226 }
227 }
228
229
230 \f
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).
235
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. */
240
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)
245 {
246 struct matrix_elt *p;
247 int i, j, k;
248
249 /* True if we have set a terminal window with set_terminal_window. */
250 bool terminal_window_p = 0;
251
252 /* A queue for line insertions to be done. */
253 struct queue { int count, pos; };
254 struct queue *queue_start
255 = alloca (current_matrix->nrows * sizeof *queue_start);
256 struct queue *queue = queue_start;
257
258 char *retained_p = alloca (window_size * sizeof *retained_p);
259 int *copy_from = alloca (window_size * sizeof *copy_from);
260
261 /* Zero means line is empty. */
262 memset (retained_p, 0, window_size * sizeof (char));
263 for (k = 0; k < window_size; ++k)
264 copy_from[k] = -1;
265
266 #ifdef GLYPH_DEBUG
267 # define CHECK_BOUNDS \
268 do \
269 { \
270 int ck; \
271 for (ck = 0; ck < window_size; ++ck) \
272 eassert (copy_from[ck] == -1 \
273 || (copy_from[ck] >= 0 && copy_from[ck] < window_size)); \
274 } \
275 while (0);
276 #endif
277
278 /* When j is advanced, this corresponds to deleted lines.
279 When i is advanced, this corresponds to inserted lines. */
280 i = j = window_size;
281 while (i > 0 || j > 0)
282 {
283 p = matrix + i * (window_size + 1) + j;
284
285 if (p->insertcost < p->writecost && p->insertcost < p->deletecost)
286 {
287 /* Insert should be done at vpos i-1, plus maybe some before.
288 Queue the screen operation to be performed. */
289 queue->count = p->insertcount;
290 queue->pos = i + unchanged_at_top - p->insertcount;
291 ++queue;
292
293 /* By incrementing I, we leave room in the result rows
294 for the empty rows opened up. */
295 i -= p->insertcount;
296 }
297 else if (p->deletecost < p->writecost)
298 {
299 /* Old line at vpos j-1, and maybe some before it, should be
300 deleted. By decrementing J, we skip some lines in the
301 temp_rows which is equivalent to omitting these lines in
302 the result rows, thus deleting them. */
303 j -= p->deletecount;
304
305 /* Set the terminal window, if not done already. */
306 if (! terminal_window_p)
307 {
308 set_terminal_window (frame, window_size + unchanged_at_top);
309 terminal_window_p = 1;
310 }
311
312 /* Delete lines on the terminal. */
313 ins_del_lines (frame, j + unchanged_at_top, - p->deletecount);
314 }
315 else
316 {
317 /* Best thing done here is no insert or delete, i.e. a write. */
318 --i, --j;
319 eassert (i >= 0 && i < window_size);
320 eassert (j >= 0 && j < window_size);
321 copy_from[i] = j;
322 retained_p[j] = 1;
323
324 #ifdef GLYPH_DEBUG
325 CHECK_BOUNDS;
326 #endif
327 }
328 }
329
330 /* Now do all insertions queued above. */
331 if (queue > queue_start)
332 {
333 int next = -1;
334
335 /* Set the terminal window if not yet done. */
336 if (!terminal_window_p)
337 {
338 set_terminal_window (frame, window_size + unchanged_at_top);
339 terminal_window_p = 1;
340 }
341
342 do
343 {
344 --queue;
345
346 /* Do the deletion on the terminal. */
347 ins_del_lines (frame, queue->pos, queue->count);
348
349 /* All lines in the range deleted become empty in the glyph
350 matrix. Assign to them glyph rows that are not retained.
351 K is the starting position of the deleted range relative
352 to the window we are working in. */
353 k = queue->pos - unchanged_at_top;
354 for (j = 0; j < queue->count; ++j)
355 {
356 /* Find the next row not retained. */
357 while (retained_p[++next])
358 ;
359
360 /* Record that this row is to be used for the empty
361 glyph row j. */
362 copy_from[k + j] = next;
363 }
364 }
365 while (queue > queue_start);
366
367 }
368
369 for (k = 0; k < window_size; ++k)
370 eassert (copy_from[k] >= 0 && copy_from[k] < window_size);
371
372 /* Perform the row swizzling. */
373 mirrored_line_dance (current_matrix, unchanged_at_top, window_size,
374 copy_from, retained_p);
375
376 /* Some sanity checks if GLYPH_DEBUG is defined. */
377 CHECK_MATRIX (current_matrix);
378
379 if (terminal_window_p)
380 set_terminal_window (frame, 0);
381 }
382
383 \f
384 /* Determine, in matrix[i,j], the cost of updating the first j
385 old lines into the first i new lines using the direct
386 scrolling method. When the old line and the new line have
387 different hash codes, the calculated cost of updating old
388 line j into new line i includes the cost of outputting new
389 line i, and if i != j, the cost of outputting the old line j
390 is also included, as a penalty for moving the line and then
391 erasing it. In addition, the cost of updating a sequence of
392 lines with constant i - j includes the cost of scrolling the
393 old lines into their new positions, unless i == j. Scrolling
394 is achieved by setting the screen window to avoid affecting
395 other lines below, and inserting or deleting lines at the top
396 of the scrolled region. The cost of scrolling a sequence of
397 lines includes the fixed cost of specifying a scroll region,
398 plus a variable cost which can depend upon the number of lines
399 involved and the distance by which they are scrolled, and an
400 extra cost to discourage long scrolls.
401
402 As reflected in the matrix, an insert or delete does not
403 correspond directly to the insertion or deletion which is
404 used in scrolling lines. An insert means that the value of i
405 has increased without a corresponding increase in the value
406 of j. A delete means that the value of j has increased
407 without a corresponding increase in the value of i. A write
408 means that i and j are both increased by the same amount, and
409 that the old lines will be moved to their new positions.
410
411 An insert following a delete is allowed only if i > j.
412 A delete following an insert is allowed only if i < j.
413 These restrictions ensure that the new lines in an insert
414 will always be blank as an effect of the neighboring writes.
415 Thus the calculated cost of an insert is simply the cost of
416 outputting the new line contents. The direct cost of a
417 delete is zero. Inserts and deletes indirectly affect the
418 total cost through their influence on subsequent writes. */
419
420 /* The vectors draw_cost, old_hash, and new_hash have the same
421 meanings here as in calculate_scrolling, and old_draw_cost
422 is the equivalent of draw_cost for the old line contents */
423
424 static void
425 calculate_direct_scrolling (FRAME_PTR frame,
426 /* matrix is of size window_size + 1 on each side. */
427 struct matrix_elt *matrix,
428 int window_size, int lines_below,
429 int *draw_cost, int *old_draw_cost,
430 int *old_hash, int *new_hash,
431 int free_at_end)
432 {
433 register int i, j;
434 int frame_lines = FRAME_LINES (frame);
435 register struct matrix_elt *p, *p1;
436 register int cost, cost1, delta;
437
438 /* first_insert_cost[-I] is the cost of doing the first insert-line
439 at a position I lines above the bottom line in the scroll window. */
440 int *first_insert_cost
441 = &FRAME_INSERT_COST (frame)[frame_lines - 1];
442 int *first_delete_cost
443 = &FRAME_DELETE_COST (frame)[frame_lines - 1];
444 int *next_insert_cost
445 = &FRAME_INSERTN_COST (frame)[frame_lines - 1];
446 int *next_delete_cost
447 = &FRAME_DELETEN_COST (frame)[frame_lines - 1];
448
449 int scroll_overhead;
450
451 /* Discourage long scrolls on fast lines.
452 Don't scroll nearly a full frame height unless it saves
453 at least 1/4 second. */
454 int extra_cost = (int) (baud_rate / (10 * 4 * FRAME_LINES (frame)));
455
456 if (baud_rate <= 0)
457 extra_cost = 1;
458
459 /* Overhead of setting the scroll window, plus the extra cost
460 cost of scrolling by a distance of one. The extra cost is
461 added once for consistency with the cost vectors */
462 scroll_overhead
463 = FRAME_SCROLL_REGION_COST (frame) + extra_cost;
464
465 /* initialize the top left corner of the matrix */
466 matrix->writecost = 0;
467 matrix->insertcost = INFINITY;
468 matrix->deletecost = INFINITY;
469 matrix->writecount = 0;
470 matrix->insertcount = 0;
471 matrix->deletecount = 0;
472
473 /* initialize the left edge of the matrix */
474 cost = 0;
475 for (i = 1; i <= window_size; i++)
476 {
477 p = matrix + i * (window_size + 1);
478 cost += draw_cost[i];
479 p->insertcost = cost;
480 p->writecost = INFINITY;
481 p->deletecost = INFINITY;
482 p->insertcount = i;
483 p->writecount = 0;
484 p->deletecount = 0;
485 }
486
487 /* initialize the top edge of the matrix */
488 for (j = 1; j <= window_size; j++)
489 {
490 matrix[j].deletecost = 0;
491 matrix[j].writecost = INFINITY;
492 matrix[j].insertcost = INFINITY;
493 matrix[j].deletecount = j;
494 matrix[j].writecount = 0;
495 matrix[j].insertcount = 0;
496 }
497
498 /* `i' represents the vpos among new frame contents.
499 `j' represents the vpos among the old frame contents. */
500 p = matrix + window_size + 2; /* matrix [1, 1] */
501
502 for (i = 1; i <= window_size; i++, p++)
503 for (j = 1; j <= window_size; j++, p++)
504 {
505 /* p contains the address of matrix [i, j] */
506
507 /* First calculate the cost assuming we do
508 not insert or delete above this line.
509 That is, if we update through line i-1
510 based on old lines through j-1,
511 and then just change old line j to new line i.
512
513 Depending on which choice gives the lower cost,
514 this usually involves either scrolling a single line
515 or extending a sequence of scrolled lines, but
516 when i == j, no scrolling is required. */
517 p1 = p - window_size - 2; /* matrix [i-1, j-1] */
518 cost = p1->insertcost;
519 if (cost > p1->deletecost)
520 cost = p1->deletecost;
521 cost1 = p1->writecost;
522 if (i == j)
523 {
524 if (cost > cost1)
525 {
526 cost = cost1;
527 p->writecount = p1->writecount + 1;
528 }
529 else
530 p->writecount = 1;
531 if (old_hash[j] != new_hash[i])
532 {
533 cost += draw_cost[i];
534 }
535 }
536 else
537 {
538 if (i > j)
539 {
540 delta = i - j;
541
542 /* The cost added here for scrolling the first line by
543 a distance N includes the overhead of setting the
544 scroll window, the cost of inserting N lines at a
545 position N lines above the bottom line of the window,
546 and an extra cost which is proportional to N. */
547 cost += scroll_overhead + first_insert_cost[-delta] +
548 (delta-1) * (next_insert_cost[-delta] + extra_cost);
549
550 /* In the most general case, the insertion overhead and
551 the multiply factor can grow linearly as the distance
552 from the bottom of the window increases. The incremental
553 cost of scrolling an additional line depends upon the
554 rate of change of these two parameters. Each of these
555 growth rates can be determined by a simple difference.
556 To reduce the cumulative effects of rounding error, we
557 vary the position at which the difference is computed. */
558 cost1 += first_insert_cost[-j] - first_insert_cost[1-j] +
559 (delta-1) * (next_insert_cost[-j] - next_insert_cost[1-j]);
560 }
561 else
562 {
563 delta = j - i;
564 cost += scroll_overhead + first_delete_cost[-delta] +
565 (delta-1) * (next_delete_cost[-delta] + extra_cost);
566 cost1 += first_delete_cost[-i] - first_delete_cost[1-i] +
567 (delta-1) * ( next_delete_cost[-i] - next_delete_cost[1-i]);
568 }
569 if (cost1 < cost)
570 {
571 cost = cost1;
572 p->writecount = p1->writecount + 1;
573 }
574 else
575 p->writecount = 1;
576 if (old_hash[j] != new_hash[i])
577 {
578 cost += draw_cost[i] + old_draw_cost[j];
579 }
580 }
581 p->writecost = cost;
582
583 /* Calculate the cost if we do an insert-line
584 before outputting this line.
585 That is, we update through line i-1
586 based on old lines through j,
587 do an insert-line on line i,
588 and then output line i from scratch,
589 leaving old lines starting from j for reuse below. */
590 p1 = p - window_size - 1; /* matrix [i-1, j] */
591 cost = p1->writecost;
592 /* If i > j, an insert is allowed after a delete. */
593 if (i > j && p1->deletecost < cost)
594 cost = p1->deletecost;
595 if (p1->insertcost <= cost)
596 {
597 cost = p1->insertcost;
598 p->insertcount = p1->insertcount + 1;
599 }
600 else
601 p->insertcount = 1;
602 cost += draw_cost[i];
603 p->insertcost = cost;
604
605 /* Calculate the cost if we do a delete line after
606 outputting this line.
607 That is, we update through line i
608 based on old lines through j-1,
609 and throw away old line j. */
610 p1 = p - 1; /* matrix [i, j-1] */
611 cost = p1->writecost;
612 /* If i < j, a delete is allowed after an insert. */
613 if (i < j && p1->insertcost < cost)
614 cost = p1->insertcost;
615 cost1 = p1->deletecost;
616 if (p1->deletecost <= cost)
617 {
618 cost = p1->deletecost;
619 p->deletecount = p1->deletecount + 1;
620 }
621 else
622 p->deletecount = 1;
623 p->deletecost = cost;
624 }
625 }
626
627
628 \f
629 /* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
630 according to the costs in MATRIX, using the direct scrolling method
631 which is used when the terminal supports setting a scroll window
632 (scroll_region_ok).
633
634 WINDOW_SIZE is the number of lines being considered for scrolling
635 and UNCHANGED_AT_TOP is the vpos of the first line being
636 considered. These two arguments can specify any contiguous range
637 of lines.
638
639 In the direct scrolling method, a new scroll window is selected
640 before each insertion or deletion, so that groups of lines can be
641 scrolled directly to their final vertical positions. This method
642 is described in more detail in calculate_direct_scrolling, where
643 the cost matrix for this approach is constructed. */
644
645 static void
646 do_direct_scrolling (struct frame *frame, struct glyph_matrix *current_matrix,
647 struct matrix_elt *cost_matrix, int window_size,
648 int unchanged_at_top)
649 {
650 struct matrix_elt *p;
651 int i, j;
652
653 /* A queue of deletions and insertions to be performed. */
654 struct alt_queue { int count, pos, window; };
655 struct alt_queue *queue_start = (struct alt_queue *)
656 alloca (window_size * sizeof *queue_start);
657 struct alt_queue *queue = queue_start;
658
659 /* True if a terminal window has been set with set_terminal_window. */
660 bool terminal_window_p = 0;
661
662 /* If true, a write has been selected, allowing either an insert or a
663 delete to be selected next. If false, a delete cannot be selected
664 unless j < i, and an insert cannot be selected unless i < j.
665 This corresponds to a similar restriction (with the ordering
666 reversed) in calculate_direct_scrolling, which is intended to
667 ensure that lines marked as inserted will be blank. */
668 bool write_follows_p = 1;
669
670 /* For each row in the new matrix what row of the old matrix it is. */
671 int *copy_from = alloca (window_size * sizeof *copy_from);
672
673 /* Non-zero for each row in the new matrix that is retained from the
674 old matrix. Lines not retained are empty. */
675 char *retained_p = alloca (window_size * sizeof *retained_p);
676
677 memset (retained_p, 0, window_size * sizeof (char));
678
679 /* Perform some sanity checks when GLYPH_DEBUG is on. */
680 CHECK_MATRIX (current_matrix);
681
682 /* We are working on the line range UNCHANGED_AT_TOP ...
683 UNCHANGED_AT_TOP + WINDOW_SIZE (not including) in CURRENT_MATRIX.
684 We step through lines in this range from the end to the start. I
685 is an index into new lines, j an index into old lines. The cost
686 matrix determines what to do for ranges of indices.
687
688 If i is decremented without also decrementing j, this corresponds
689 to inserting empty lines in the result. If j is decremented
690 without also decrementing i, this corresponds to omitting these
691 lines in the new rows, i.e. rows are deleted. */
692 i = j = window_size;
693
694 while (i > 0 || j > 0)
695 {
696 p = cost_matrix + i * (window_size + 1) + j;
697
698 if (p->insertcost < p->writecost
699 && p->insertcost < p->deletecost
700 && (write_follows_p || i < j))
701 {
702 /* Insert is cheaper than deleting or writing lines. Leave
703 a hole in the result display that will be filled with
704 empty lines when the queue is emptied. */
705 queue->count = 0;
706 queue->window = i;
707 queue->pos = i - p->insertcount;
708 ++queue;
709
710 i -= p->insertcount;
711 write_follows_p = 0;
712 }
713 else if (p->deletecost < p->writecost
714 && (write_follows_p || i > j))
715 {
716 /* Deleting lines is cheaper. By decrementing J, omit
717 deletecount lines from the original. */
718 write_follows_p = 0;
719 j -= p->deletecount;
720 }
721 else
722 {
723 /* One or more lines should be written. In the direct
724 scrolling method we do this by scrolling the lines to the
725 place they belong. */
726 int n_to_write = p->writecount;
727 write_follows_p = 1;
728 eassert (n_to_write > 0);
729
730 if (i > j)
731 {
732 /* Immediately insert lines */
733 set_terminal_window (frame, i + unchanged_at_top);
734 terminal_window_p = 1;
735 ins_del_lines (frame, j - n_to_write + unchanged_at_top, i - j);
736 }
737 else if (i < j)
738 {
739 /* Queue the deletion of a group of lines */
740 queue->pos = i - n_to_write + unchanged_at_top;
741 queue->window = j + unchanged_at_top;
742 queue->count = i - j;
743 ++queue;
744 }
745
746 while (n_to_write > 0)
747 {
748 --i, --j, --n_to_write;
749 copy_from[i] = j;
750 retained_p[j] = 1;
751 }
752 }
753 }
754
755 /* Do queued operations. */
756 if (queue > queue_start)
757 {
758 int next = -1;
759
760 do
761 {
762 --queue;
763 if (queue->count)
764 {
765 set_terminal_window (frame, queue->window);
766 terminal_window_p = 1;
767 ins_del_lines (frame, queue->pos, queue->count);
768 }
769 else
770 {
771 for (j = queue->window - 1; j >= queue->pos; --j)
772 {
773 while (retained_p[++next])
774 ;
775 copy_from[j] = next;
776 }
777 }
778 }
779 while (queue > queue_start);
780 }
781
782 /* Now, for each row I in the range of rows we are working on,
783 copy_from[i] gives the original line to copy to I, and
784 retained_p[copy_from[i]] is zero if line I in the new display is
785 empty. */
786 mirrored_line_dance (current_matrix, unchanged_at_top, window_size,
787 copy_from, retained_p);
788
789 if (terminal_window_p)
790 set_terminal_window (frame, 0);
791 }
792
793
794 \f
795 void
796 scrolling_1 (FRAME_PTR frame, int window_size, int unchanged_at_top,
797 int unchanged_at_bottom, int *draw_cost, int *old_draw_cost,
798 int *old_hash, int *new_hash, int free_at_end)
799 {
800 struct matrix_elt *matrix;
801 matrix = ((struct matrix_elt *)
802 alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
803
804 if (FRAME_SCROLL_REGION_OK (frame))
805 {
806 calculate_direct_scrolling (frame, matrix, window_size,
807 unchanged_at_bottom,
808 draw_cost, old_draw_cost,
809 old_hash, new_hash, free_at_end);
810 do_direct_scrolling (frame, frame->current_matrix,
811 matrix, window_size, unchanged_at_top);
812 }
813 else
814 {
815 calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
816 draw_cost, old_hash, new_hash,
817 free_at_end);
818 do_scrolling (frame,
819 frame->current_matrix, matrix, window_size,
820 unchanged_at_top);
821 }
822 }
823
824
825 \f
826 /* Return number of lines in common between current and desired frame
827 contents described to us only as vectors of hash codes OLDHASH and
828 NEWHASH. Consider only vpos range START to END (not including
829 END). Ignore short lines on the assumption that avoiding redrawing
830 such a line will have little weight. */
831
832 int
833 scrolling_max_lines_saved (int start, int end,
834 int *oldhash, int *newhash,
835 int *cost)
836 {
837 struct { int hash; int count; } lines[01000];
838 register int i, h;
839 register int matchcount = 0;
840 int avg_length = 0;
841 int threshold;
842
843 /* Compute a threshold which is 1/4 of average length of these lines. */
844
845 for (i = start; i < end; i++)
846 avg_length += cost[i];
847
848 avg_length /= end - start;
849 threshold = avg_length / 4;
850
851 memset (lines, 0, sizeof lines);
852
853 /* Put new lines' hash codes in hash table. Ignore lines shorter
854 than the threshold. Thus, if the lines that are in common are
855 mainly the ones that are short, they won't count. */
856 for (i = start; i < end; i++)
857 {
858 if (cost[i] > threshold)
859 {
860 h = newhash[i] & 0777;
861 lines[h].hash = newhash[i];
862 lines[h].count++;
863 }
864 }
865
866 /* Look up old line hash codes in the hash table. Count number of
867 matches between old lines and new. */
868 for (i = start; i < end; i++)
869 {
870 h = oldhash[i] & 0777;
871 if (oldhash[i] == lines[h].hash)
872 {
873 matchcount++;
874 if (--lines[h].count == 0)
875 lines[h].hash = 0;
876 }
877 }
878
879 return matchcount;
880 }
881 \f
882 /* Calculate the line insertion/deletion
883 overhead and multiply factor values */
884
885 static void
886 line_ins_del (FRAME_PTR frame, int ov1, int pf1, int ovn, int pfn,
887 register int *ov, register int *mf)
888 {
889 register int i;
890 register int frame_lines = FRAME_LINES (frame);
891 register int insert_overhead = ov1 * 10;
892 register int next_insert_cost = ovn * 10;
893
894 for (i = frame_lines-1; i >= 0; i--)
895 {
896 mf[i] = next_insert_cost / 10;
897 next_insert_cost += pfn;
898 ov[i] = (insert_overhead + next_insert_cost) / 10;
899 insert_overhead += pf1;
900 }
901 }
902
903 static void
904 ins_del_costs (FRAME_PTR frame,
905 const char *one_line_string, const char *multi_string,
906 const char *setup_string, const char *cleanup_string,
907 int *costvec, int *ncostvec,
908 int coefficient)
909 {
910 if (multi_string)
911 line_ins_del (frame,
912 string_cost (multi_string) * coefficient,
913 per_line_cost (multi_string) * coefficient,
914 0, 0, costvec, ncostvec);
915 else if (one_line_string)
916 line_ins_del (frame,
917 string_cost (setup_string) + string_cost (cleanup_string), 0,
918 string_cost (one_line_string),
919 per_line_cost (one_line_string),
920 costvec, ncostvec);
921 else
922 line_ins_del (frame,
923 9999, 0, 9999, 0,
924 costvec, ncostvec);
925 }
926
927 /* Calculate the insert and delete line costs.
928 Note that this is done even when running with a window system
929 because we want to know how long scrolling takes (and avoid it).
930 This must be redone whenever the frame height changes.
931
932 We keep the ID costs in a precomputed array based on the position
933 at which the I or D is performed. Also, there are two kinds of ID
934 costs: the "once-only" and the "repeated". This is to handle both
935 those terminals that are able to insert N lines at a time (once-
936 only) and those that must repeatedly insert one line.
937
938 The cost to insert N lines at line L is
939 [tt.t_ILov + (frame_lines + 1 - L) * tt.t_ILpf] +
940 N * [tt.t_ILnov + (frame_lines + 1 - L) * tt.t_ILnpf]
941
942 ILov represents the basic insert line overhead. ILpf is the padding
943 required to allow the terminal time to move a line: insertion at line
944 L changes (frame_lines + 1 - L) lines.
945
946 The first bracketed expression above is the overhead; the second is
947 the multiply factor. Both are dependent only on the position at
948 which the insert is performed. We store the overhead in
949 FRAME_INSERT_COST (frame) and the multiply factor in
950 FRAME_INSERTN_COST (frame). Note however that any insertion
951 must include at least one multiply factor. Rather than compute this
952 as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line],
953 we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame).
954 This is reasonable because of the particular algorithm used in calcM.
955
956 Deletion is essentially the same as insertion.
957 */
958
959 void
960 do_line_insertion_deletion_costs (FRAME_PTR frame,
961 const char *ins_line_string,
962 const char *multi_ins_string,
963 const char *del_line_string,
964 const char *multi_del_string,
965 const char *setup_string,
966 const char *cleanup_string,
967 int coefficient)
968 {
969 FRAME_INSERT_COST (frame) =
970 xnrealloc (FRAME_INSERT_COST (frame), FRAME_LINES (frame), sizeof (int));
971 FRAME_DELETEN_COST (frame) =
972 xnrealloc (FRAME_DELETEN_COST (frame), FRAME_LINES (frame), sizeof (int));
973 FRAME_INSERTN_COST (frame) =
974 xnrealloc (FRAME_INSERTN_COST (frame), FRAME_LINES (frame), sizeof (int));
975 FRAME_DELETE_COST (frame) =
976 xnrealloc (FRAME_DELETE_COST (frame), FRAME_LINES (frame), sizeof (int));
977
978 ins_del_costs (frame,
979 ins_line_string, multi_ins_string,
980 setup_string, cleanup_string,
981 FRAME_INSERT_COST (frame), FRAME_INSERTN_COST (frame),
982 coefficient);
983 ins_del_costs (frame,
984 del_line_string, multi_del_string,
985 setup_string, cleanup_string,
986 FRAME_DELETE_COST (frame), FRAME_DELETEN_COST (frame),
987 coefficient);
988 }