Initialize stack_top when a new thread is created.
[emacs.git] / src / scroll.c
blobe2d3656dc439b2c70f516d958af19904e478f7ac
1 /* Calculate what line insertion or deletion to do, and do it,
2 Copyright (C) 1985, 1986, 1990, 1993, 1994, 2001, 2002, 2003, 2004,
3 2005, 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
5 This file is part of GNU Emacs.
7 GNU Emacs is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 GNU Emacs is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */
21 #include <config.h>
22 #include <stdio.h>
23 #include <string.h>
24 #include <setjmp.h>
25 #include "lisp.h"
26 #include "termchar.h"
27 #include "dispextern.h"
28 #include "keyboard.h"
29 #include "frame.h"
30 #include "window.h"
31 #include "termhooks.h"
33 /* All costs measured in characters.
34 So no cost can exceed the area of a frame, measured in characters.
35 Let's hope this is never more than 1000000 characters. */
37 #define INFINITY 1000000
39 struct matrix_elt
41 /* Cost of outputting through this line
42 if no insert/delete is done just above it. */
43 int writecost;
44 /* Cost of outputting through this line
45 if an insert is done just above it. */
46 int insertcost;
47 /* Cost of outputting through this line
48 if a delete is done just above it. */
49 int deletecost;
50 /* Number of inserts so far in this run of inserts,
51 for the cost in insertcost. */
52 unsigned char insertcount;
53 /* Number of deletes so far in this run of deletes,
54 for the cost in deletecost. */
55 unsigned char deletecount;
56 /* Number of writes so far since the last insert
57 or delete for the cost in writecost. */
58 unsigned char writecount;
61 static void do_direct_scrolling P_ ((struct frame *,
62 struct glyph_matrix *,
63 struct matrix_elt *,
64 int, int));
65 static void do_scrolling P_ ((struct frame *,
66 struct glyph_matrix *,
67 struct matrix_elt *,
68 int, int));
71 /* Determine, in matrix[i,j], the cost of updating the first j old
72 lines into the first i new lines using the general scrolling method.
73 This involves using insert or delete somewhere if i != j.
74 For each matrix elements, three kinds of costs are recorded:
75 the smallest cost that ends with an insert, the smallest
76 cost that ends with a delete, and the smallest cost that
77 ends with neither one. These are kept separate because
78 on some terminals the cost of doing an insert varies
79 depending on whether one was just done, etc. */
81 /* draw_cost[VPOS] is the cost of outputting new line at VPOS.
82 old_hash[VPOS] is the hash code of the old line at VPOS.
83 new_hash[VPOS] is the hash code of the new line at VPOS.
84 Note that these are not true frame vpos's, but relative
85 to the place at which the first mismatch between old and
86 new contents appears. */
88 static void
89 calculate_scrolling (frame, matrix, window_size, lines_below,
90 draw_cost, old_hash, new_hash,
91 free_at_end)
92 FRAME_PTR frame;
93 /* matrix is of size window_size + 1 on each side. */
94 struct matrix_elt *matrix;
95 int window_size, lines_below;
96 int *draw_cost;
97 int *old_hash;
98 int *new_hash;
99 int free_at_end;
101 register int i, j;
102 int frame_lines = FRAME_LINES (frame);
103 register struct matrix_elt *p, *p1;
104 register int cost, cost1;
106 int lines_moved = window_size
107 + (FRAME_SCROLL_REGION_OK (frame) ? 0 : lines_below);
108 /* first_insert_cost[I] is the cost of doing the first insert-line
109 at the i'th line of the lines we are considering,
110 where I is origin 1 (as it is below). */
111 int *first_insert_cost
112 = &FRAME_INSERT_COST (frame)[frame_lines - 1 - lines_moved];
113 int *first_delete_cost
114 = &FRAME_DELETE_COST (frame)[frame_lines - 1 - lines_moved];
115 int *next_insert_cost
116 = &FRAME_INSERTN_COST (frame)[frame_lines - 1 - lines_moved];
117 int *next_delete_cost
118 = &FRAME_DELETEN_COST (frame)[frame_lines - 1 - lines_moved];
120 /* Discourage long scrolls on fast lines.
121 Don't scroll nearly a full frame height unless it saves
122 at least 1/4 second. */
123 int extra_cost = baud_rate / (10 * 4 * FRAME_LINES (frame));
125 if (baud_rate <= 0)
126 extra_cost = 1;
128 /* initialize the top left corner of the matrix */
129 matrix->writecost = 0;
130 matrix->insertcost = INFINITY;
131 matrix->deletecost = INFINITY;
132 matrix->insertcount = 0;
133 matrix->deletecount = 0;
135 /* initialize the left edge of the matrix */
136 cost = first_insert_cost[1] - next_insert_cost[1];
137 for (i = 1; i <= window_size; i++)
139 p = matrix + i * (window_size + 1);
140 cost += draw_cost[i] + next_insert_cost[i] + extra_cost;
141 p->insertcost = cost;
142 p->writecost = INFINITY;
143 p->deletecost = INFINITY;
144 p->insertcount = i;
145 p->deletecount = 0;
148 /* initialize the top edge of the matrix */
149 cost = first_delete_cost[1] - next_delete_cost[1];
150 for (j = 1; j <= window_size; j++)
152 cost += next_delete_cost[j];
153 matrix[j].deletecost = cost;
154 matrix[j].writecost = INFINITY;
155 matrix[j].insertcost = INFINITY;
156 matrix[j].deletecount = j;
157 matrix[j].insertcount = 0;
160 /* `i' represents the vpos among new frame contents.
161 `j' represents the vpos among the old frame contents. */
162 p = matrix + window_size + 2; /* matrix [1, 1] */
163 for (i = 1; i <= window_size; i++, p++)
164 for (j = 1; j <= window_size; j++, p++)
166 /* p contains the address of matrix [i, j] */
168 /* First calculate the cost assuming we do
169 not insert or delete above this line.
170 That is, if we update through line i-1
171 based on old lines through j-1,
172 and then just change old line j to new line i. */
173 p1 = p - window_size - 2; /* matrix [i-1, j-1] */
174 cost = p1->writecost;
175 if (cost > p1->insertcost)
176 cost = p1->insertcost;
177 if (cost > p1->deletecost)
178 cost = p1->deletecost;
179 if (old_hash[j] != new_hash[i])
180 cost += draw_cost[i];
181 p->writecost = cost;
183 /* Calculate the cost if we do an insert-line
184 before outputting this line.
185 That is, we update through line i-1
186 based on old lines through j,
187 do an insert-line on line i,
188 and then output line i from scratch,
189 leaving old lines starting from j for reuse below. */
190 p1 = p - window_size - 1; /* matrix [i-1, j] */
191 /* No need to think about doing a delete followed
192 immediately by an insert. It cannot be as good
193 as not doing either of them. */
194 if (free_at_end == i)
196 cost = p1->writecost;
197 cost1 = p1->insertcost;
199 else
201 cost = p1->writecost + first_insert_cost[i];
202 if ((int) p1->insertcount > i)
203 abort ();
204 cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
206 p->insertcost = min (cost, cost1) + draw_cost[i] + extra_cost;
207 p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
208 if ((int) p->insertcount > i)
209 abort ();
211 /* Calculate the cost if we do a delete line after
212 outputting this line.
213 That is, we update through line i
214 based on old lines through j-1,
215 and throw away old line j. */
216 p1 = p - 1; /* matrix [i, j-1] */
217 /* No need to think about doing an insert followed
218 immediately by a delete. */
219 if (free_at_end == i)
221 cost = p1->writecost;
222 cost1 = p1->deletecost;
224 else
226 cost = p1->writecost + first_delete_cost[i];
227 cost1 = p1->deletecost + next_delete_cost[i];
229 p->deletecost = min (cost, cost1);
230 p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1;
236 /* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
237 according to the costs in MATRIX, using the general scrolling
238 method that is used if the terminal does not support the setting of
239 scroll windows (scroll_region_ok == 0).
241 WINDOW_SIZE is the number of lines being considered for scrolling
242 and UNCHANGED_AT_TOP is the vpos of the first line being
243 considered. These two arguments can specify any contiguous range
244 of lines. */
246 static void
247 do_scrolling (frame, current_matrix, matrix, window_size, unchanged_at_top)
248 struct frame *frame;
249 struct glyph_matrix *current_matrix;
250 struct matrix_elt *matrix;
251 int window_size;
252 int unchanged_at_top;
254 struct matrix_elt *p;
255 int i, j, k;
257 /* Set to 1 if we have set a terminal window with
258 set_terminal_window. */
259 int terminal_window_p = 0;
261 /* A queue for line insertions to be done. */
262 struct queue { int count, pos; };
263 struct queue *queue_start
264 = (struct queue *) alloca (current_matrix->nrows * sizeof (struct queue));
265 struct queue *queue = queue_start;
267 char *retained_p = (char *) alloca (window_size * sizeof (char));
268 int *copy_from = (int *) alloca (window_size * sizeof (int));
270 /* Zero means line is empty. */
271 bzero (retained_p, window_size * sizeof (char));
272 for (k = 0; k < window_size; ++k)
273 copy_from[k] = -1;
275 #define CHECK_BOUNDS \
276 do \
278 int k; \
279 for (k = 0; k < window_size; ++k) \
280 xassert (copy_from[k] == -1 \
281 || (copy_from[k] >= 0 && copy_from[k] < window_size)); \
283 while (0);
285 /* When j is advanced, this corresponds to deleted lines.
286 When i is advanced, this corresponds to inserted lines. */
287 i = j = window_size;
288 while (i > 0 || j > 0)
290 p = matrix + i * (window_size + 1) + j;
292 if (p->insertcost < p->writecost && p->insertcost < p->deletecost)
294 /* Insert should be done at vpos i-1, plus maybe some before.
295 Queue the screen operation to be performed. */
296 queue->count = p->insertcount;
297 queue->pos = i + unchanged_at_top - p->insertcount;
298 ++queue;
300 /* By incrementing I, we leave room in the result rows
301 for the empty rows opened up. */
302 i -= p->insertcount;
304 else if (p->deletecost < p->writecost)
306 /* Old line at vpos j-1, and maybe some before it, should be
307 deleted. By decrementing J, we skip some lines in the
308 temp_rows which is equivalent to omitting these lines in
309 the result rows, thus deleting them. */
310 j -= p->deletecount;
312 /* Set the terminal window, if not done already. */
313 if (! terminal_window_p)
315 set_terminal_window (frame, window_size + unchanged_at_top);
316 terminal_window_p = 1;
319 /* Delete lines on the terminal. */
320 ins_del_lines (frame, j + unchanged_at_top, - p->deletecount);
322 else
324 /* Best thing done here is no insert or delete, i.e. a write. */
325 --i, --j;
326 xassert (i >= 0 && i < window_size);
327 xassert (j >= 0 && j < window_size);
328 copy_from[i] = j;
329 retained_p[j] = 1;
331 #if GLYPH_DEBUG
332 CHECK_BOUNDS;
333 #endif
337 /* Now do all insertions queued above. */
338 if (queue > queue_start)
340 int next = -1;
342 /* Set the terminal window if not yet done. */
343 if (!terminal_window_p)
345 set_terminal_window (frame, window_size + unchanged_at_top);
346 terminal_window_p = 1;
351 --queue;
353 /* Do the deletion on the terminal. */
354 ins_del_lines (frame, queue->pos, queue->count);
356 /* All lines in the range deleted become empty in the glyph
357 matrix. Assign to them glyph rows that are not retained.
358 K is the starting position of the deleted range relative
359 to the window we are working in. */
360 k = queue->pos - unchanged_at_top;
361 for (j = 0; j < queue->count; ++j)
363 /* Find the next row not retained. */
364 while (retained_p[++next])
367 /* Record that this row is to be used for the empty
368 glyph row j. */
369 copy_from[k + j] = next;
372 while (queue > queue_start);
376 for (k = 0; k < window_size; ++k)
377 xassert (copy_from[k] >= 0 && copy_from[k] < window_size);
379 /* Perform the row swizzling. */
380 mirrored_line_dance (current_matrix, unchanged_at_top, window_size,
381 copy_from, retained_p);
383 /* Some sanity checks if GLYPH_DEBUG != 0. */
384 CHECK_MATRIX (current_matrix);
386 if (terminal_window_p)
387 set_terminal_window (frame, 0);
391 /* Determine, in matrix[i,j], the cost of updating the first j
392 old lines into the first i new lines using the direct
393 scrolling method. When the old line and the new line have
394 different hash codes, the calculated cost of updating old
395 line j into new line i includes the cost of outputting new
396 line i, and if i != j, the cost of outputting the old line j
397 is also included, as a penalty for moving the line and then
398 erasing it. In addition, the cost of updating a sequence of
399 lines with constant i - j includes the cost of scrolling the
400 old lines into their new positions, unless i == j. Scrolling
401 is achieved by setting the screen window to avoid affecting
402 other lines below, and inserting or deleting lines at the top
403 of the scrolled region. The cost of scrolling a sequence of
404 lines includes the fixed cost of specifying a scroll region,
405 plus a variable cost which can depend upon the number of lines
406 involved and the distance by which they are scrolled, and an
407 extra cost to discourage long scrolls.
409 As reflected in the matrix, an insert or delete does not
410 correspond directly to the insertion or deletion which is
411 used in scrolling lines. An insert means that the value of i
412 has increased without a corresponding increase in the value
413 of j. A delete means that the value of j has increased
414 without a corresponding increase in the value of i. A write
415 means that i and j are both increased by the same amount, and
416 that the old lines will be moved to their new positions.
418 An insert following a delete is allowed only if i > j.
419 A delete following an insert is allowed only if i < j.
420 These restrictions ensure that the new lines in an insert
421 will always be blank as an effect of the neighboring writes.
422 Thus the calculated cost of an insert is simply the cost of
423 outputting the new line contents. The direct cost of a
424 delete is zero. Inserts and deletes indirectly affect the
425 total cost through their influence on subsequent writes. */
427 /* The vectors draw_cost, old_hash, and new_hash have the same
428 meanings here as in calculate_scrolling, and old_draw_cost
429 is the equivalent of draw_cost for the old line contents */
431 static void
432 calculate_direct_scrolling (frame, matrix, window_size, lines_below,
433 draw_cost, old_draw_cost, old_hash, new_hash,
434 free_at_end)
435 FRAME_PTR frame;
436 /* matrix is of size window_size + 1 on each side. */
437 struct matrix_elt *matrix;
438 int window_size, lines_below;
439 int *draw_cost;
440 int *old_draw_cost;
441 int *old_hash;
442 int *new_hash;
443 int free_at_end;
445 register int i, j;
446 int frame_lines = FRAME_LINES (frame);
447 register struct matrix_elt *p, *p1;
448 register int cost, cost1, delta;
450 /* first_insert_cost[-I] is the cost of doing the first insert-line
451 at a position I lines above the bottom line in the scroll window. */
452 int *first_insert_cost
453 = &FRAME_INSERT_COST (frame)[frame_lines - 1];
454 int *first_delete_cost
455 = &FRAME_DELETE_COST (frame)[frame_lines - 1];
456 int *next_insert_cost
457 = &FRAME_INSERTN_COST (frame)[frame_lines - 1];
458 int *next_delete_cost
459 = &FRAME_DELETEN_COST (frame)[frame_lines - 1];
461 int scroll_overhead;
463 /* Discourage long scrolls on fast lines.
464 Don't scroll nearly a full frame height unless it saves
465 at least 1/4 second. */
466 int extra_cost = baud_rate / (10 * 4 * FRAME_LINES (frame));
468 if (baud_rate <= 0)
469 extra_cost = 1;
471 /* Overhead of setting the scroll window, plus the extra cost
472 cost of scrolling by a distance of one. The extra cost is
473 added once for consistency with the cost vectors */
474 scroll_overhead
475 = FRAME_SCROLL_REGION_COST (frame) + extra_cost;
477 /* initialize the top left corner of the matrix */
478 matrix->writecost = 0;
479 matrix->insertcost = INFINITY;
480 matrix->deletecost = INFINITY;
481 matrix->writecount = 0;
482 matrix->insertcount = 0;
483 matrix->deletecount = 0;
485 /* initialize the left edge of the matrix */
486 cost = 0;
487 for (i = 1; i <= window_size; i++)
489 p = matrix + i * (window_size + 1);
490 cost += draw_cost[i];
491 p->insertcost = cost;
492 p->writecost = INFINITY;
493 p->deletecost = INFINITY;
494 p->insertcount = i;
495 p->writecount = 0;
496 p->deletecount = 0;
499 /* initialize the top edge of the matrix */
500 for (j = 1; j <= window_size; j++)
502 matrix[j].deletecost = 0;
503 matrix[j].writecost = INFINITY;
504 matrix[j].insertcost = INFINITY;
505 matrix[j].deletecount = j;
506 matrix[j].writecount = 0;
507 matrix[j].insertcount = 0;
510 /* `i' represents the vpos among new frame contents.
511 `j' represents the vpos among the old frame contents. */
512 p = matrix + window_size + 2; /* matrix [1, 1] */
514 for (i = 1; i <= window_size; i++, p++)
515 for (j = 1; j <= window_size; j++, p++)
517 /* p contains the address of matrix [i, j] */
519 /* First calculate the cost assuming we do
520 not insert or delete above this line.
521 That is, if we update through line i-1
522 based on old lines through j-1,
523 and then just change old line j to new line i.
525 Depending on which choice gives the lower cost,
526 this usually involves either scrolling a single line
527 or extending a sequence of scrolled lines, but
528 when i == j, no scrolling is required. */
529 p1 = p - window_size - 2; /* matrix [i-1, j-1] */
530 cost = p1->insertcost;
531 if (cost > p1->deletecost)
532 cost = p1->deletecost;
533 cost1 = p1->writecost;
534 if (i == j)
536 if (cost > cost1)
538 cost = cost1;
539 p->writecount = p1->writecount + 1;
541 else
542 p->writecount = 1;
543 if (old_hash[j] != new_hash[i])
545 cost += draw_cost[i];
548 else
550 if (i > j)
552 delta = i - j;
554 /* The cost added here for scrolling the first line by
555 a distance N includes the overhead of setting the
556 scroll window, the cost of inserting N lines at a
557 position N lines above the bottom line of the window,
558 and an extra cost which is proportional to N. */
559 cost += scroll_overhead + first_insert_cost[-delta] +
560 (delta-1) * (next_insert_cost[-delta] + extra_cost);
562 /* In the most general case, the insertion overhead and
563 the multiply factor can grow linearly as the distance
564 from the bottom of the window increases. The incremental
565 cost of scrolling an additional line depends upon the
566 rate of change of these two parameters. Each of these
567 growth rates can be determined by a simple difference.
568 To reduce the cumulative effects of rounding error, we
569 vary the position at which the difference is computed. */
570 cost1 += first_insert_cost[-j] - first_insert_cost[1-j] +
571 (delta-1) * (next_insert_cost[-j] - next_insert_cost[1-j]);
573 else
575 delta = j - i;
576 cost += scroll_overhead + first_delete_cost[-delta] +
577 (delta-1) * (next_delete_cost[-delta] + extra_cost);
578 cost1 += first_delete_cost[-i] - first_delete_cost[1-i] +
579 (delta-1) * ( next_delete_cost[-i] - next_delete_cost[1-i]);
581 if (cost1 < cost)
583 cost = cost1;
584 p->writecount = p1->writecount + 1;
586 else
587 p->writecount = 1;
588 if (old_hash[j] != new_hash[i])
590 cost += draw_cost[i] + old_draw_cost[j];
593 p->writecost = cost;
595 /* Calculate the cost if we do an insert-line
596 before outputting this line.
597 That is, we update through line i-1
598 based on old lines through j,
599 do an insert-line on line i,
600 and then output line i from scratch,
601 leaving old lines starting from j for reuse below. */
602 p1 = p - window_size - 1; /* matrix [i-1, j] */
603 cost = p1->writecost;
604 /* If i > j, an insert is allowed after a delete. */
605 if (i > j && p1->deletecost < cost)
606 cost = p1->deletecost;
607 if (p1->insertcost <= cost)
609 cost = p1->insertcost;
610 p->insertcount = p1->insertcount + 1;
612 else
613 p->insertcount = 1;
614 cost += draw_cost[i];
615 p->insertcost = cost;
617 /* Calculate the cost if we do a delete line after
618 outputting this line.
619 That is, we update through line i
620 based on old lines through j-1,
621 and throw away old line j. */
622 p1 = p - 1; /* matrix [i, j-1] */
623 cost = p1->writecost;
624 /* If i < j, a delete is allowed after an insert. */
625 if (i < j && p1->insertcost < cost)
626 cost = p1->insertcost;
627 cost1 = p1->deletecost;
628 if (p1->deletecost <= cost)
630 cost = p1->deletecost;
631 p->deletecount = p1->deletecount + 1;
633 else
634 p->deletecount = 1;
635 p->deletecost = cost;
641 /* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
642 according to the costs in MATRIX, using the direct scrolling method
643 which is used when the terminal supports setting a scroll window
644 (scroll_region_ok).
646 WINDOW_SIZE is the number of lines being considered for scrolling
647 and UNCHANGED_AT_TOP is the vpos of the first line being
648 considered. These two arguments can specify any contiguous range
649 of lines.
651 In the direct scrolling method, a new scroll window is selected
652 before each insertion or deletion, so that groups of lines can be
653 scrolled directly to their final vertical positions. This method
654 is described in more detail in calculate_direct_scrolling, where
655 the cost matrix for this approach is constructed. */
657 static void
658 do_direct_scrolling (frame, current_matrix, cost_matrix,
659 window_size, unchanged_at_top)
660 struct frame *frame;
661 struct glyph_matrix *current_matrix;
662 struct matrix_elt *cost_matrix;
663 int window_size;
664 int unchanged_at_top;
666 struct matrix_elt *p;
667 int i, j;
669 /* A queue of deletions and insertions to be performed. */
670 struct alt_queue { int count, pos, window; };
671 struct alt_queue *queue_start = (struct alt_queue *)
672 alloca (window_size * sizeof *queue_start);
673 struct alt_queue *queue = queue_start;
675 /* Set to 1 if a terminal window has been set with
676 set_terminal_window: */
677 int terminal_window_p = 0;
679 /* A nonzero value of write_follows indicates that a write has been
680 selected, allowing either an insert or a delete to be selected
681 next. When write_follows is zero, a delete cannot be selected
682 unless j < i, and an insert cannot be selected unless i < j.
683 This corresponds to a similar restriction (with the ordering
684 reversed) in calculate_direct_scrolling, which is intended to
685 ensure that lines marked as inserted will be blank. */
686 int write_follows_p = 1;
688 /* For each row in the new matrix what row of the old matrix it is. */
689 int *copy_from = (int *) alloca (window_size * sizeof (int));
691 /* Non-zero for each row in the new matrix that is retained from the
692 old matrix. Lines not retained are empty. */
693 char *retained_p = (char *) alloca (window_size * sizeof (char));
695 bzero (retained_p, window_size * sizeof (char));
697 /* Perform some sanity checks when GLYPH_DEBUG is on. */
698 CHECK_MATRIX (current_matrix);
700 /* We are working on the line range UNCHANGED_AT_TOP ...
701 UNCHANGED_AT_TOP + WINDOW_SIZE (not including) in CURRENT_MATRIX.
702 We step through lines in this range from the end to the start. I
703 is an index into new lines, j an index into old lines. The cost
704 matrix determines what to do for ranges of indices.
706 If i is decremented without also decrementing j, this corresponds
707 to inserting empty lines in the result. If j is decremented
708 without also decrementing i, this corresponds to omitting these
709 lines in the new rows, i.e. rows are deleted. */
710 i = j = window_size;
712 while (i > 0 || j > 0)
714 p = cost_matrix + i * (window_size + 1) + j;
716 if (p->insertcost < p->writecost
717 && p->insertcost < p->deletecost
718 && (write_follows_p || i < j))
720 /* Insert is cheaper than deleting or writing lines. Leave
721 a hole in the result display that will be filled with
722 empty lines when the queue is emptied. */
723 queue->count = 0;
724 queue->window = i;
725 queue->pos = i - p->insertcount;
726 ++queue;
728 i -= p->insertcount;
729 write_follows_p = 0;
731 else if (p->deletecost < p->writecost
732 && (write_follows_p || i > j))
734 /* Deleting lines is cheaper. By decrementing J, omit
735 deletecount lines from the original. */
736 write_follows_p = 0;
737 j -= p->deletecount;
739 else
741 /* One or more lines should be written. In the direct
742 scrolling method we do this by scrolling the lines to the
743 place they belong. */
744 int n_to_write = p->writecount;
745 write_follows_p = 1;
746 xassert (n_to_write > 0);
748 if (i > j)
750 /* Immediately insert lines */
751 set_terminal_window (frame, i + unchanged_at_top);
752 terminal_window_p = 1;
753 ins_del_lines (frame, j - n_to_write + unchanged_at_top, i - j);
755 else if (i < j)
757 /* Queue the deletion of a group of lines */
758 queue->pos = i - n_to_write + unchanged_at_top;
759 queue->window = j + unchanged_at_top;
760 queue->count = i - j;
761 ++queue;
764 while (n_to_write > 0)
766 --i, --j, --n_to_write;
767 copy_from[i] = j;
768 retained_p[j] = 1;
773 /* Do queued operations. */
774 if (queue > queue_start)
776 int next = -1;
780 --queue;
781 if (queue->count)
783 set_terminal_window (frame, queue->window);
784 terminal_window_p = 1;
785 ins_del_lines (frame, queue->pos, queue->count);
787 else
789 for (j = queue->window - 1; j >= queue->pos; --j)
791 while (retained_p[++next])
793 copy_from[j] = next;
797 while (queue > queue_start);
800 /* Now, for each row I in the range of rows we are working on,
801 copy_from[i] gives the original line to copy to I, and
802 retained_p[copy_from[i]] is zero if line I in the new display is
803 empty. */
804 mirrored_line_dance (current_matrix, unchanged_at_top, window_size,
805 copy_from, retained_p);
807 if (terminal_window_p)
808 set_terminal_window (frame, 0);
813 void
814 scrolling_1 (frame, window_size, unchanged_at_top, unchanged_at_bottom,
815 draw_cost, old_draw_cost, old_hash, new_hash, free_at_end)
816 FRAME_PTR frame;
817 int window_size, unchanged_at_top, unchanged_at_bottom;
818 int *draw_cost;
819 int *old_draw_cost;
820 int *old_hash;
821 int *new_hash;
822 int free_at_end;
824 struct matrix_elt *matrix;
825 matrix = ((struct matrix_elt *)
826 alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
828 if (FRAME_SCROLL_REGION_OK (frame))
830 calculate_direct_scrolling (frame, matrix, window_size,
831 unchanged_at_bottom,
832 draw_cost, old_draw_cost,
833 old_hash, new_hash, free_at_end);
834 do_direct_scrolling (frame, frame->current_matrix,
835 matrix, window_size, unchanged_at_top);
837 else
839 calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
840 draw_cost, old_hash, new_hash,
841 free_at_end);
842 do_scrolling (frame,
843 frame->current_matrix, matrix, window_size,
844 unchanged_at_top);
850 /* Return number of lines in common between current and desired frame
851 contents described to us only as vectors of hash codes OLDHASH and
852 NEWHASH. Consider only vpos range START to END (not including
853 END). Ignore short lines on the assumption that avoiding redrawing
854 such a line will have little weight. */
857 scrolling_max_lines_saved (start, end, oldhash, newhash, cost)
858 int start, end;
859 int *oldhash, *newhash, *cost;
861 struct { int hash; int count; } lines[01000];
862 register int i, h;
863 register int matchcount = 0;
864 int avg_length = 0;
865 int threshold;
867 /* Compute a threshold which is 1/4 of average length of these lines. */
869 for (i = start; i < end; i++)
870 avg_length += cost[i];
872 avg_length /= end - start;
873 threshold = avg_length / 4;
875 bzero (lines, sizeof lines);
877 /* Put new lines' hash codes in hash table. Ignore lines shorter
878 than the threshold. Thus, if the lines that are in common are
879 mainly the ones that are short, they won't count. */
880 for (i = start; i < end; i++)
882 if (cost[i] > threshold)
884 h = newhash[i] & 0777;
885 lines[h].hash = newhash[i];
886 lines[h].count++;
890 /* Look up old line hash codes in the hash table. Count number of
891 matches between old lines and new. */
892 for (i = start; i < end; i++)
894 h = oldhash[i] & 0777;
895 if (oldhash[i] == lines[h].hash)
897 matchcount++;
898 if (--lines[h].count == 0)
899 lines[h].hash = 0;
903 return matchcount;
906 /* Return a measure of the cost of moving the lines starting with vpos
907 FROM, up to but not including vpos TO, down by AMOUNT lines (AMOUNT
908 may be negative). These are the same arguments that might be given
909 to scroll_frame_lines to perform this scrolling. */
912 scroll_cost (frame, from, to, amount)
913 FRAME_PTR frame;
914 int from, to, amount;
916 /* Compute how many lines, at bottom of frame,
917 will not be involved in actual motion. */
918 int limit = to;
919 int offset;
920 int height = FRAME_LINES (frame);
922 if (amount == 0)
923 return 0;
925 if (! FRAME_SCROLL_REGION_OK (frame))
926 limit = height;
927 else if (amount > 0)
928 limit += amount;
930 if (amount < 0)
932 int temp = to;
933 to = from + amount;
934 from = temp + amount;
935 amount = - amount;
938 offset = height - limit;
940 return
941 (FRAME_INSERT_COST (frame)[offset + from]
942 + (amount - 1) * FRAME_INSERTN_COST (frame)[offset + from]
943 + FRAME_DELETE_COST (frame)[offset + to]
944 + (amount - 1) * FRAME_DELETEN_COST (frame)[offset + to]);
947 /* Calculate the line insertion/deletion
948 overhead and multiply factor values */
950 static void
951 line_ins_del (frame, ov1, pf1, ovn, pfn, ov, mf)
952 FRAME_PTR frame;
953 int ov1, ovn;
954 int pf1, pfn;
955 register int *ov, *mf;
957 register int i;
958 register int frame_lines = FRAME_LINES (frame);
959 register int insert_overhead = ov1 * 10;
960 register int next_insert_cost = ovn * 10;
962 for (i = frame_lines-1; i >= 0; i--)
964 mf[i] = next_insert_cost / 10;
965 next_insert_cost += pfn;
966 ov[i] = (insert_overhead + next_insert_cost) / 10;
967 insert_overhead += pf1;
971 static void
972 ins_del_costs (frame,
973 one_line_string, multi_string,
974 setup_string, cleanup_string,
975 costvec, ncostvec, coefficient)
976 FRAME_PTR frame;
977 char *one_line_string, *multi_string;
978 char *setup_string, *cleanup_string;
979 int *costvec, *ncostvec;
980 int coefficient;
982 if (multi_string)
983 line_ins_del (frame,
984 string_cost (multi_string) * coefficient,
985 per_line_cost (multi_string) * coefficient,
986 0, 0, costvec, ncostvec);
987 else if (one_line_string)
988 line_ins_del (frame,
989 string_cost (setup_string) + string_cost (cleanup_string), 0,
990 string_cost (one_line_string),
991 per_line_cost (one_line_string),
992 costvec, ncostvec);
993 else
994 line_ins_del (frame,
995 9999, 0, 9999, 0,
996 costvec, ncostvec);
999 /* Calculate the insert and delete line costs.
1000 Note that this is done even when running with a window system
1001 because we want to know how long scrolling takes (and avoid it).
1002 This must be redone whenever the frame height changes.
1004 We keep the ID costs in a precomputed array based on the position
1005 at which the I or D is performed. Also, there are two kinds of ID
1006 costs: the "once-only" and the "repeated". This is to handle both
1007 those terminals that are able to insert N lines at a time (once-
1008 only) and those that must repeatedly insert one line.
1010 The cost to insert N lines at line L is
1011 [tt.t_ILov + (frame_lines + 1 - L) * tt.t_ILpf] +
1012 N * [tt.t_ILnov + (frame_lines + 1 - L) * tt.t_ILnpf]
1014 ILov represents the basic insert line overhead. ILpf is the padding
1015 required to allow the terminal time to move a line: insertion at line
1016 L changes (frame_lines + 1 - L) lines.
1018 The first bracketed expression above is the overhead; the second is
1019 the multiply factor. Both are dependent only on the position at
1020 which the insert is performed. We store the overhead in
1021 FRAME_INSERT_COST (frame) and the multiply factor in
1022 FRAME_INSERTN_COST (frame). Note however that any insertion
1023 must include at least one multiply factor. Rather than compute this
1024 as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line],
1025 we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame).
1026 This is reasonable because of the particular algorithm used in calcM.
1028 Deletion is essentially the same as insertion.
1031 void
1032 do_line_insertion_deletion_costs (frame,
1033 ins_line_string, multi_ins_string,
1034 del_line_string, multi_del_string,
1035 setup_string, cleanup_string, coefficient)
1036 FRAME_PTR frame;
1037 char *ins_line_string, *multi_ins_string;
1038 char *del_line_string, *multi_del_string;
1039 char *setup_string, *cleanup_string;
1040 int coefficient;
1042 if (FRAME_INSERT_COST (frame) != 0)
1044 FRAME_INSERT_COST (frame) =
1045 (int *) xrealloc (FRAME_INSERT_COST (frame),
1046 FRAME_LINES (frame) * sizeof (int));
1047 FRAME_DELETEN_COST (frame) =
1048 (int *) xrealloc (FRAME_DELETEN_COST (frame),
1049 FRAME_LINES (frame) * sizeof (int));
1050 FRAME_INSERTN_COST (frame) =
1051 (int *) xrealloc (FRAME_INSERTN_COST (frame),
1052 FRAME_LINES (frame) * sizeof (int));
1053 FRAME_DELETE_COST (frame) =
1054 (int *) xrealloc (FRAME_DELETE_COST (frame),
1055 FRAME_LINES (frame) * sizeof (int));
1057 else
1059 FRAME_INSERT_COST (frame) =
1060 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int));
1061 FRAME_DELETEN_COST (frame) =
1062 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int));
1063 FRAME_INSERTN_COST (frame) =
1064 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int));
1065 FRAME_DELETE_COST (frame) =
1066 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int));
1069 ins_del_costs (frame,
1070 ins_line_string, multi_ins_string,
1071 setup_string, cleanup_string,
1072 FRAME_INSERT_COST (frame), FRAME_INSERTN_COST (frame),
1073 coefficient);
1074 ins_del_costs (frame,
1075 del_line_string, multi_del_string,
1076 setup_string, cleanup_string,
1077 FRAME_DELETE_COST (frame), FRAME_DELETEN_COST (frame),
1078 coefficient);
1081 /* arch-tag: cdb7149c-48e7-4793-a948-2786c8e45485
1082 (do not change this comment) */