X-Git-Url: https://git.hcoop.net/bpt/emacs.git/blobdiff_plain/3e2bea7c253f0393f9209b4b75f724bf0166fded..8fab6dedbf0d2bd0f97ed8a4abeb717fac384b14:/src/scroll.c diff --git a/src/scroll.c b/src/scroll.c index 7432a3ea06..e8981fcfb5 100644 --- a/src/scroll.c +++ b/src/scroll.c @@ -1,11 +1,12 @@ /* Calculate what line insertion or deletion to do, and do it, - Copyright (C) 1985, 1986, 1990 Free Software Foundation, Inc. + Copyright (C) 1985, 1986, 1990, 1993, 1994, 2002, 2003, 2004, + 2005, 2006 Free Software Foundation, Inc. This file is part of GNU Emacs. GNU Emacs is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 1, or (at your option) +the Free Software Foundation; either version 2, or (at your option) any later version. GNU Emacs is distributed in the hope that it will be useful, @@ -15,57 +16,58 @@ GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GNU Emacs; see the file COPYING. If not, write to -the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ +the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, +Boston, MA 02110-1301, USA. */ -#include "config.h" +#include +#include +#include #include "termchar.h" #include "lisp.h" #include "dispextern.h" -#include "screen.h" - -extern struct display_line **ophys_lines; - -#define max(a, b) ((a) > (b) ? (a) : (b)) -#define min(a, b) ((a) < (b) ? (a) : (b)) +#include "keyboard.h" +#include "frame.h" +#include "window.h" /* All costs measured in characters. - So no cost can exceed the area of a screen, measured in characters. - Let's hope this is never more than 15000 characters. */ + So no cost can exceed the area of a frame, measured in characters. + Let's hope this is never more than 1000000 characters. */ -#define INFINITY 15000 +#define INFINITY 1000000 struct matrix_elt { /* Cost of outputting through this line if no insert/delete is done just above it. */ - short writecost; + int writecost; /* Cost of outputting through this line if an insert is done just above it. */ - short insertcost; + int insertcost; /* Cost of outputting through this line if a delete is done just above it. */ - short deletecost; + int deletecost; /* Number of inserts so far in this run of inserts, for the cost in insertcost. */ - char insertcount; + unsigned char insertcount; /* Number of deletes so far in this run of deletes, for the cost in deletecost. */ - char deletecount; + unsigned char deletecount; + /* Number of writes so far since the last insert + or delete for the cost in writecost. */ + unsigned char writecount; }; -/* See do_line_insertion_deletion_costs for info on these arrays. */ - -#ifndef MULTI_SCREEN -static int *insert_line_cost; -static int *delete_line_cost; -static int *insert_n_lines_cost; -static int *delete_n_lines_cost; -#endif +static void do_direct_scrolling P_ ((struct glyph_matrix *, + struct matrix_elt *, + int, int)); +static void do_scrolling P_ ((struct glyph_matrix *, + struct matrix_elt *, + int, int)); -/* Determine, in matrix[i,j], the cost of updating the first j old lines - into the first i new lines. +/* Determine, in matrix[i,j], the cost of updating the first j old + lines into the first i new lines using the general scrolling method. This involves using insert or delete somewhere if i != j. For each matrix elements, three kinds of costs are recorded: the smallest cost that ends with an insert, the smallest @@ -77,45 +79,48 @@ static int *delete_n_lines_cost; /* draw_cost[VPOS] is the cost of outputting new line at VPOS. old_hash[VPOS] is the hash code of the old line at VPOS. new_hash[VPOS] is the hash code of the new line at VPOS. - Note that these are not true screen vpos's, but relative + Note that these are not true frame vpos's, but relative to the place at which the first mismatch between old and new contents appears. */ static void -calculate_scrolling (screen, matrix, window_size, lines_below, +calculate_scrolling (frame, matrix, window_size, lines_below, draw_cost, old_hash, new_hash, free_at_end) - SCREEN_PTR screen; + FRAME_PTR frame; /* matrix is of size window_size + 1 on each side. */ struct matrix_elt *matrix; - int window_size; + int window_size, lines_below; int *draw_cost; int *old_hash; int *new_hash; int free_at_end; { register int i, j; - int screen_height = SCREEN_HEIGHT (screen); + int frame_lines = FRAME_LINES (frame); register struct matrix_elt *p, *p1; register int cost, cost1; int lines_moved = window_size + (scroll_region_ok ? 0 : lines_below); /* first_insert_cost[I] is the cost of doing the first insert-line - at the I'th line of the lines we are considering, + at the i'th line of the lines we are considering, where I is origin 1 (as it is below). */ int *first_insert_cost - = &SCREEN_INSERT_COST (screen)[screen_height - 1 - lines_moved]; + = &FRAME_INSERT_COST (frame)[frame_lines - 1 - lines_moved]; int *first_delete_cost - = &SCREEN_DELETE_COST (screen)[screen_height - 1 - lines_moved]; + = &FRAME_DELETE_COST (frame)[frame_lines - 1 - lines_moved]; int *next_insert_cost - = &SCREEN_INSERTN_COST (screen)[screen_height - 1 - lines_moved]; + = &FRAME_INSERTN_COST (frame)[frame_lines - 1 - lines_moved]; int *next_delete_cost - = &SCREEN_DELETEN_COST (screen)[screen_height - 1 - lines_moved]; + = &FRAME_DELETEN_COST (frame)[frame_lines - 1 - lines_moved]; /* Discourage long scrolls on fast lines. - Don't scroll nearly a full screen height unless it saves + Don't scroll nearly a full frame height unless it saves at least 1/4 second. */ - int extra_cost = baud_rate / (10 * 4 * SCREEN_HEIGHT (screen)); + int extra_cost = baud_rate / (10 * 4 * FRAME_LINES (frame)); + + if (baud_rate <= 0) + extra_cost = 1; /* initialize the top left corner of the matrix */ matrix->writecost = 0; @@ -149,8 +154,8 @@ calculate_scrolling (screen, matrix, window_size, lines_below, matrix[j].insertcount = 0; } - /* `i' represents the vpos among new screen contents. - `j' represents the vpos among the old screen contents. */ + /* `i' represents the vpos among new frame contents. + `j' represents the vpos among the old frame contents. */ p = matrix + window_size + 2; /* matrix [1, 1] */ for (i = 1; i <= window_size; i++, p++) for (j = 1; j <= window_size; j++, p++) @@ -191,13 +196,13 @@ calculate_scrolling (screen, matrix, window_size, lines_below, else { cost = p1->writecost + first_insert_cost[i]; - if (p1->insertcount > i) + if ((int) p1->insertcount > i) abort (); cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount]; } p->insertcost = min (cost, cost1) + draw_cost[i] + extra_cost; p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1; - if (p->insertcount > i) + if ((int) p->insertcount > i) abort (); /* Calculate the cost if we do a delete line after @@ -222,142 +227,590 @@ calculate_scrolling (screen, matrix, window_size, lines_below, p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1; } } + + -/* Perform insert-lines and delete-lines operations - according to the costs in the matrix. - Updates the contents of the screen to record what was done. */ +/* Perform insert-lines and delete-lines operations on CURRENT_MATRIX + according to the costs in MATRIX, using the general scrolling + method that is used if the terminal does not support the setting of + scroll windows (scroll_region_ok == 0). + + WINDOW_SIZE is the number of lines being considered for scrolling + and UNCHANGED_AT_TOP is the vpos of the first line being + considered. These two arguments can specify any contiguous range + of lines. */ static void -do_scrolling (screen, matrix, window_size, unchanged_at_top) - SCREEN_PTR screen; +do_scrolling (current_matrix, matrix, window_size, unchanged_at_top) + struct glyph_matrix *current_matrix; struct matrix_elt *matrix; int window_size; int unchanged_at_top; { - register struct matrix_elt *p; - register int i, j; - register struct screen_glyphs *current_screen; - register struct screen_glyphs *temp_screen; - struct queue { int count, pos; } *queue; - int offset = unchanged_at_top; - int qi = 0; - int window = 0; - register int tem; - int next; - - queue = (struct queue *) alloca (SCREEN_HEIGHT (screen) - * sizeof (struct queue)); - - current_screen = SCREEN_CURRENT_GLYPHS (screen); - temp_screen = SCREEN_TEMP_GLYPHS (screen); - - bcopy (current_screen->glyphs, temp_screen->glyphs, - current_screen->height * sizeof (GLYPH *)); - bcopy (current_screen->used, temp_screen->used, - current_screen->height * sizeof (int)); - bcopy (current_screen->highlight, temp_screen->highlight, - current_screen->height * sizeof (char)); - bzero (temp_screen->enable, temp_screen->height * sizeof (char)); - bcopy (current_screen->bufp, temp_screen->bufp, - current_screen->height * sizeof (int)); - -#ifdef HAVE_X_WINDOWS - if (SCREEN_IS_X (screen)) - { - bcopy (current_screen->nruns, temp_screen->nruns, - current_screen->height * sizeof (int)); - bcopy (current_screen->face_list, temp_screen->face_list, - current_screen->height * sizeof (struct run *)); - bcopy (current_screen->top_left_x, temp_screen->top_left_x, - current_screen->height * sizeof (short)); - bcopy (current_screen->top_left_y, temp_screen->top_left_y, - current_screen->height * sizeof (short)); - bcopy (current_screen->pix_width, temp_screen->pix_width, - current_screen->height * sizeof (short)); - bcopy (current_screen->pix_height, temp_screen->pix_height, - current_screen->height * sizeof (short)); - } -#endif - + struct matrix_elt *p; + int i, j, k; + + /* Set to 1 if we have set a terminal window with + set_terminal_window. */ + int terminal_window_p = 0; + + /* A queue for line insertions to be done. */ + struct queue { int count, pos; }; + struct queue *queue_start + = (struct queue *) alloca (current_matrix->nrows * sizeof (struct queue)); + struct queue *queue = queue_start; + + char *retained_p = (char *) alloca (window_size * sizeof (char)); + int *copy_from = (int *) alloca (window_size * sizeof (int)); + + /* Zero means line is empty. */ + bzero (retained_p, window_size * sizeof (char)); + for (k = 0; k < window_size; ++k) + copy_from[k] = -1; + +#define CHECK_BOUNDS \ + do \ + { \ + int k; \ + for (k = 0; k < window_size; ++k) \ + xassert (copy_from[k] == -1 \ + || (copy_from[k] >= 0 && copy_from[k] < window_size)); \ + } \ + while (0); + + /* When j is advanced, this corresponds to deleted lines. + When i is advanced, this corresponds to inserted lines. */ i = j = window_size; - while (i > 0 || j > 0) { p = matrix + i * (window_size + 1) + j; - tem = p->insertcost; - if (tem < p->writecost && tem < p->deletecost) + + if (p->insertcost < p->writecost && p->insertcost < p->deletecost) { - /* Insert should be done at vpos i-1, plus maybe some before */ - queue[qi].count = p->insertcount; + /* Insert should be done at vpos i-1, plus maybe some before. + Queue the screen operation to be performed. */ + queue->count = p->insertcount; + queue->pos = i + unchanged_at_top - p->insertcount; + ++queue; + + /* By incrementing I, we leave room in the result rows + for the empty rows opened up. */ i -= p->insertcount; - queue[qi++].pos = i + unchanged_at_top; } else if (p->deletecost < p->writecost) { - /* Old line at vpos j-1, and maybe some before it, - should be deleted */ + /* Old line at vpos j-1, and maybe some before it, should be + deleted. By decrementing J, we skip some lines in the + temp_rows which is equivalent to omitting these lines in + the result rows, thus deleting them. */ j -= p->deletecount; - if (!window) + + /* Set the terminal window, if not done already. */ + if (! terminal_window_p) { set_terminal_window (window_size + unchanged_at_top); - window = 1; + terminal_window_p = 1; } + + /* Delete lines on the terminal. */ ins_del_lines (j + unchanged_at_top, - p->deletecount); } else { - /* Best thing done here is no insert or delete */ - /* Old line at vpos j-1 ends up at vpos i-1 */ - current_screen->glyphs[i + offset - 1] - = temp_screen->glyphs[j + offset - 1]; - current_screen->used[i + offset - 1] - = temp_screen->used[j + offset - 1]; - current_screen->highlight[i + offset - 1] - = temp_screen->highlight[j + offset - 1]; - - temp_screen->enable[j + offset - 1] = 1; - i--; - j--; + /* Best thing done here is no insert or delete, i.e. a write. */ + --i, --j; + xassert (i >= 0 && i < window_size); + xassert (j >= 0 && j < window_size); + copy_from[i] = j; + retained_p[j] = 1; + +#if GLYPH_DEBUG + CHECK_BOUNDS; +#endif } } - if (!window && qi) + /* Now do all insertions queued above. */ + if (queue > queue_start) + { + int next = -1; + + /* Set the terminal window if not yet done. */ + if (!terminal_window_p) + { + set_terminal_window (window_size + unchanged_at_top); + terminal_window_p = 1; + } + + do + { + --queue; + + /* Do the deletion on the terminal. */ + ins_del_lines (queue->pos, queue->count); + + /* All lines in the range deleted become empty in the glyph + matrix. Assign to them glyph rows that are not retained. + K is the starting position of the deleted range relative + to the window we are working in. */ + k = queue->pos - unchanged_at_top; + for (j = 0; j < queue->count; ++j) + { + /* Find the next row not retained. */ + while (retained_p[++next]) + ; + + /* Record that this row is to be used for the empty + glyph row j. */ + copy_from[k + j] = next; + } + } + while (queue > queue_start); + + } + + for (k = 0; k < window_size; ++k) + xassert (copy_from[k] >= 0 && copy_from[k] < window_size); + + /* Perform the row swizzling. */ + mirrored_line_dance (current_matrix, unchanged_at_top, window_size, + copy_from, retained_p); + + /* Some sanity checks if GLYPH_DEBUG != 0. */ + CHECK_MATRIX (current_matrix); + + if (terminal_window_p) + set_terminal_window (0); +} + + +/* Determine, in matrix[i,j], the cost of updating the first j + old lines into the first i new lines using the direct + scrolling method. When the old line and the new line have + different hash codes, the calculated cost of updating old + line j into new line i includes the cost of outputting new + line i, and if i != j, the cost of outputting the old line j + is also included, as a penalty for moving the line and then + erasing it. In addition, the cost of updating a sequence of + lines with constant i - j includes the cost of scrolling the + old lines into their new positions, unless i == j. Scrolling + is achieved by setting the screen window to avoid affecting + other lines below, and inserting or deleting lines at the top + of the scrolled region. The cost of scrolling a sequence of + lines includes the fixed cost of specifying a scroll region, + plus a variable cost which can depend upon the number of lines + involved and the distance by which they are scrolled, and an + extra cost to discourage long scrolls. + + As reflected in the matrix, an insert or delete does not + correspond directly to the insertion or deletion which is + used in scrolling lines. An insert means that the value of i + has increased without a corresponding increase in the value + of j. A delete means that the value of j has increased + without a corresponding increase in the value of i. A write + means that i and j are both increased by the same amount, and + that the old lines will be moved to their new positions. + + An insert following a delete is allowed only if i > j. + A delete following an insert is allowed only if i < j. + These restrictions ensure that the new lines in an insert + will always be blank as an effect of the neighboring writes. + Thus the calculated cost of an insert is simply the cost of + outputting the new line contents. The direct cost of a + delete is zero. Inserts and deletes indirectly affect the + total cost through their influence on subsequent writes. */ + +/* The vectors draw_cost, old_hash, and new_hash have the same + meanings here as in calculate_scrolling, and old_draw_cost + is the equivalent of draw_cost for the old line contents */ + +static void +calculate_direct_scrolling (frame, matrix, window_size, lines_below, + draw_cost, old_draw_cost, old_hash, new_hash, + free_at_end) + FRAME_PTR frame; + /* matrix is of size window_size + 1 on each side. */ + struct matrix_elt *matrix; + int window_size, lines_below; + int *draw_cost; + int *old_draw_cost; + int *old_hash; + int *new_hash; + int free_at_end; +{ + register int i, j; + int frame_lines = FRAME_LINES (frame); + register struct matrix_elt *p, *p1; + register int cost, cost1, delta; + + /* first_insert_cost[-I] is the cost of doing the first insert-line + at a position I lines above the bottom line in the scroll window. */ + int *first_insert_cost + = &FRAME_INSERT_COST (frame)[frame_lines - 1]; + int *first_delete_cost + = &FRAME_DELETE_COST (frame)[frame_lines - 1]; + int *next_insert_cost + = &FRAME_INSERTN_COST (frame)[frame_lines - 1]; + int *next_delete_cost + = &FRAME_DELETEN_COST (frame)[frame_lines - 1]; + + int scroll_overhead; + + /* Discourage long scrolls on fast lines. + Don't scroll nearly a full frame height unless it saves + at least 1/4 second. */ + int extra_cost = baud_rate / (10 * 4 * FRAME_LINES (frame)); + + if (baud_rate <= 0) + extra_cost = 1; + + /* Overhead of setting the scroll window, plus the extra cost + cost of scrolling by a distance of one. The extra cost is + added once for consistency with the cost vectors */ + scroll_overhead = scroll_region_cost + extra_cost; + + /* initialize the top left corner of the matrix */ + matrix->writecost = 0; + matrix->insertcost = INFINITY; + matrix->deletecost = INFINITY; + matrix->writecount = 0; + matrix->insertcount = 0; + matrix->deletecount = 0; + + /* initialize the left edge of the matrix */ + cost = 0; + for (i = 1; i <= window_size; i++) + { + p = matrix + i * (window_size + 1); + cost += draw_cost[i]; + p->insertcost = cost; + p->writecost = INFINITY; + p->deletecost = INFINITY; + p->insertcount = i; + p->writecount = 0; + p->deletecount = 0; + } + + /* initialize the top edge of the matrix */ + for (j = 1; j <= window_size; j++) { - set_terminal_window (window_size + unchanged_at_top); - window = 1; + matrix[j].deletecost = 0; + matrix[j].writecost = INFINITY; + matrix[j].insertcost = INFINITY; + matrix[j].deletecount = j; + matrix[j].writecount = 0; + matrix[j].insertcount = 0; } - /* Now do all insertions */ + /* `i' represents the vpos among new frame contents. + `j' represents the vpos among the old frame contents. */ + p = matrix + window_size + 2; /* matrix [1, 1] */ + + for (i = 1; i <= window_size; i++, p++) + for (j = 1; j <= window_size; j++, p++) + { + /* p contains the address of matrix [i, j] */ + + /* First calculate the cost assuming we do + not insert or delete above this line. + That is, if we update through line i-1 + based on old lines through j-1, + and then just change old line j to new line i. + + Depending on which choice gives the lower cost, + this usually involves either scrolling a single line + or extending a sequence of scrolled lines, but + when i == j, no scrolling is required. */ + p1 = p - window_size - 2; /* matrix [i-1, j-1] */ + cost = p1->insertcost; + if (cost > p1->deletecost) + cost = p1->deletecost; + cost1 = p1->writecost; + if (i == j) + { + if (cost > cost1) + { + cost = cost1; + p->writecount = p1->writecount + 1; + } + else + p->writecount = 1; + if (old_hash[j] != new_hash[i]) + { + cost += draw_cost[i]; + } + } + else + { + if (i > j) + { + delta = i - j; + + /* The cost added here for scrolling the first line by + a distance N includes the overhead of setting the + scroll window, the cost of inserting N lines at a + position N lines above the bottom line of the window, + and an extra cost which is proportional to N. */ + cost += scroll_overhead + first_insert_cost[-delta] + + (delta-1) * (next_insert_cost[-delta] + extra_cost); + + /* In the most general case, the insertion overhead and + the multiply factor can grow linearly as the distance + from the bottom of the window increases. The incremental + cost of scrolling an additional line depends upon the + rate of change of these two parameters. Each of these + growth rates can be determined by a simple difference. + To reduce the cumulative effects of rounding error, we + vary the position at which the difference is computed. */ + cost1 += first_insert_cost[-j] - first_insert_cost[1-j] + + (delta-1) * (next_insert_cost[-j] - next_insert_cost[1-j]); + } + else + { + delta = j - i; + cost += scroll_overhead + first_delete_cost[-delta] + + (delta-1) * (next_delete_cost[-delta] + extra_cost); + cost1 += first_delete_cost[-i] - first_delete_cost[1-i] + + (delta-1) * ( next_delete_cost[-i] - next_delete_cost[1-i]); + } + if (cost1 < cost) + { + cost = cost1; + p->writecount = p1->writecount + 1; + } + else + p->writecount = 1; + if (old_hash[j] != new_hash[i]) + { + cost += draw_cost[i] + old_draw_cost[j]; + } + } + p->writecost = cost; + + /* Calculate the cost if we do an insert-line + before outputting this line. + That is, we update through line i-1 + based on old lines through j, + do an insert-line on line i, + and then output line i from scratch, + leaving old lines starting from j for reuse below. */ + p1 = p - window_size - 1; /* matrix [i-1, j] */ + cost = p1->writecost; + /* If i > j, an insert is allowed after a delete. */ + if (i > j && p1->deletecost < cost) + cost = p1->deletecost; + if (p1->insertcost <= cost) + { + cost = p1->insertcost; + p->insertcount = p1->insertcount + 1; + } + else + p->insertcount = 1; + cost += draw_cost[i]; + p->insertcost = cost; + + /* Calculate the cost if we do a delete line after + outputting this line. + That is, we update through line i + based on old lines through j-1, + and throw away old line j. */ + p1 = p - 1; /* matrix [i, j-1] */ + cost = p1->writecost; + /* If i < j, a delete is allowed after an insert. */ + if (i < j && p1->insertcost < cost) + cost = p1->insertcost; + cost1 = p1->deletecost; + if (p1->deletecost <= cost) + { + cost = p1->deletecost; + p->deletecount = p1->deletecount + 1; + } + else + p->deletecount = 1; + p->deletecost = cost; + } +} + + + +/* Perform insert-lines and delete-lines operations on CURRENT_MATRIX + according to the costs in MATRIX, using the direct scrolling method + which is used when the terminal supports setting a scroll window + (scroll_region_ok). + + WINDOW_SIZE is the number of lines being considered for scrolling + and UNCHANGED_AT_TOP is the vpos of the first line being + considered. These two arguments can specify any contiguous range + of lines. + + In the direct scrolling method, a new scroll window is selected + before each insertion or deletion, so that groups of lines can be + scrolled directly to their final vertical positions. This method + is described in more detail in calculate_direct_scrolling, where + the cost matrix for this approach is constructed. */ + +static void +do_direct_scrolling (current_matrix, cost_matrix, window_size, + unchanged_at_top) + struct glyph_matrix *current_matrix; + struct matrix_elt *cost_matrix; + int window_size; + int unchanged_at_top; +{ + struct matrix_elt *p; + int i, j; + + /* A queue of deletions and insertions to be performed. */ + struct alt_queue { int count, pos, window; }; + struct alt_queue *queue_start = (struct alt_queue *) + alloca (window_size * sizeof *queue_start); + struct alt_queue *queue = queue_start; + + /* Set to 1 if a terminal window has been set with + set_terminal_window: */ + int terminal_window_p = 0; + + /* A nonzero value of write_follows indicates that a write has been + selected, allowing either an insert or a delete to be selected + next. When write_follows is zero, a delete cannot be selected + unless j < i, and an insert cannot be selected unless i < j. + This corresponds to a similar restriction (with the ordering + reversed) in calculate_direct_scrolling, which is intended to + ensure that lines marked as inserted will be blank. */ + int write_follows_p = 1; + + /* For each row in the new matrix what row of the old matrix it is. */ + int *copy_from = (int *) alloca (window_size * sizeof (int)); + + /* Non-zero for each row in the new matrix that is retained from the + old matrix. Lines not retained are empty. */ + char *retained_p = (char *) alloca (window_size * sizeof (char)); + + bzero (retained_p, window_size * sizeof (char)); + + /* Perform some sanity checks when GLYPH_DEBUG is on. */ + CHECK_MATRIX (current_matrix); + + /* We are working on the line range UNCHANGED_AT_TOP ... + UNCHANGED_AT_TOP + WINDOW_SIZE (not including) in CURRENT_MATRIX. + We step through lines in this range from the end to the start. I + is an index into new lines, j an index into old lines. The cost + matrix determines what to do for ranges of indices. + + If i is decremented without also decrementing j, this corresponds + to inserting empty lines in the result. If j is decremented + without also decrementing i, this corresponds to omitting these + lines in the new rows, i.e. rows are deleted. */ + i = j = window_size; - next = unchanged_at_top; - for (i = qi - 1; i >= 0; i--) + while (i > 0 || j > 0) { - ins_del_lines (queue[i].pos, queue[i].count); - - /* Mark the inserted lines as clear, - and put into them the line-contents strings - that were discarded during the deletions. - Those are the ones for which temp_screen->enable was not set. */ - tem = queue[i].pos; - for (j = tem + queue[i].count - 1; j >= tem; j--) + p = cost_matrix + i * (window_size + 1) + j; + + if (p->insertcost < p->writecost + && p->insertcost < p->deletecost + && (write_follows_p || i < j)) + { + /* Insert is cheaper than deleting or writing lines. Leave + a hole in the result display that will be filled with + empty lines when the queue is emptied. */ + queue->count = 0; + queue->window = i; + queue->pos = i - p->insertcount; + ++queue; + + i -= p->insertcount; + write_follows_p = 0; + } + else if (p->deletecost < p->writecost + && (write_follows_p || i > j)) + { + /* Deleting lines is cheaper. By decrementing J, omit + deletecount lines from the original. */ + write_follows_p = 0; + j -= p->deletecount; + } + else { - current_screen->enable[j] = 0; - while (temp_screen->enable[next]) - next++; - current_screen->glyphs[j] = temp_screen->glyphs[next++]; + /* One or more lines should be written. In the direct + scrolling method we do this by scrolling the lines to the + place they belong. */ + int n_to_write = p->writecount; + write_follows_p = 1; + xassert (n_to_write > 0); + + if (i > j) + { + /* Immediately insert lines */ + set_terminal_window (i + unchanged_at_top); + terminal_window_p = 1; + ins_del_lines (j - n_to_write + unchanged_at_top, i - j); + } + else if (i < j) + { + /* Queue the deletion of a group of lines */ + queue->pos = i - n_to_write + unchanged_at_top; + queue->window = j + unchanged_at_top; + queue->count = i - j; + ++queue; + } + + while (n_to_write > 0) + { + --i, --j, --n_to_write; + copy_from[i] = j; + retained_p[j] = 1; + } } } - if (window) + /* Do queued operations. */ + if (queue > queue_start) + { + int next = -1; + + do + { + --queue; + if (queue->count) + { + set_terminal_window (queue->window); + terminal_window_p = 1; + ins_del_lines (queue->pos, queue->count); + } + else + { + for (j = queue->window - 1; j >= queue->pos; --j) + { + while (retained_p[++next]) + ; + copy_from[j] = next; + } + } + } + while (queue > queue_start); + } + + /* Now, for each row I in the range of rows we are working on, + copy_from[i] gives the original line to copy to I, and + retained_p[copy_from[i]] is zero if line I in the new display is + empty. */ + mirrored_line_dance (current_matrix, unchanged_at_top, window_size, + copy_from, retained_p); + + if (terminal_window_p) set_terminal_window (0); } + + void -scrolling_1 (screen, window_size, unchanged_at_top, unchanged_at_bottom, - draw_cost, old_hash, new_hash, free_at_end) - SCREEN_PTR screen; +scrolling_1 (frame, window_size, unchanged_at_top, unchanged_at_bottom, + draw_cost, old_draw_cost, old_hash, new_hash, free_at_end) + FRAME_PTR frame; int window_size, unchanged_at_top, unchanged_at_bottom; int *draw_cost; + int *old_draw_cost; int *old_hash; int *new_hash; int free_at_end; @@ -366,17 +819,32 @@ scrolling_1 (screen, window_size, unchanged_at_top, unchanged_at_bottom, matrix = ((struct matrix_elt *) alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix)); - calculate_scrolling (screen, matrix, window_size, unchanged_at_bottom, - draw_cost, old_hash, new_hash, - free_at_end); - do_scrolling (screen, matrix, window_size, unchanged_at_top); + if (scroll_region_ok) + { + calculate_direct_scrolling (frame, matrix, window_size, + unchanged_at_bottom, + draw_cost, old_draw_cost, + old_hash, new_hash, free_at_end); + do_direct_scrolling (frame->current_matrix, + matrix, window_size, unchanged_at_top); + } + else + { + calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom, + draw_cost, old_hash, new_hash, + free_at_end); + do_scrolling (frame->current_matrix, matrix, window_size, + unchanged_at_top); + } } + + -/* Return number of lines in common between current and desired screen contents - described to us only as vectors of hash codes OLDHASH and NEWHASH. - Consider only vpos range START to END (not including END). - Ignore short lines on the assumption that - avoiding redrawing such a line will have little weight. */ +/* Return number of lines in common between current and desired frame + contents described to us only as vectors of hash codes OLDHASH and + NEWHASH. Consider only vpos range START to END (not including + END). Ignore short lines on the assumption that avoiding redrawing + such a line will have little weight. */ int scrolling_max_lines_saved (start, end, oldhash, newhash, cost) @@ -399,11 +867,9 @@ scrolling_max_lines_saved (start, end, oldhash, newhash, cost) bzero (lines, sizeof lines); - /* Put new lines' hash codes in hash table. - Ignore lines shorter than the threshold. - Thus, if the lines that are in common - are mainly the ones that are short, - they won't count. */ + /* Put new lines' hash codes in hash table. Ignore lines shorter + than the threshold. Thus, if the lines that are in common are + mainly the ones that are short, they won't count. */ for (i = start; i < end; i++) { if (cost[i] > threshold) @@ -414,9 +880,8 @@ scrolling_max_lines_saved (start, end, oldhash, newhash, cost) } } - /* Look up old line hash codes in the hash table. - Count number of matches between old lines and new. */ - + /* Look up old line hash codes in the hash table. Count number of + matches between old lines and new. */ for (i = start; i < end; i++) { h = oldhash[i] & 0777; @@ -431,21 +896,21 @@ scrolling_max_lines_saved (start, end, oldhash, newhash, cost) return matchcount; } -/* Return a measure of the cost of moving the lines - starting with vpos FROM, up to but not including vpos TO, - down by AMOUNT lines (AMOUNT may be negative). - These are the same arguments that might be given to - scroll_screen_lines to perform this scrolling. */ - -scroll_cost (screen, from, to, amount) - SCREEN_PTR screen; +/* Return a measure of the cost of moving the lines starting with vpos + FROM, up to but not including vpos TO, down by AMOUNT lines (AMOUNT + may be negative). These are the same arguments that might be given + to scroll_frame_lines to perform this scrolling. */ + +int +scroll_cost (frame, from, to, amount) + FRAME_PTR frame; int from, to, amount; { - /* Compute how many lines, at bottom of screen, + /* Compute how many lines, at bottom of frame, will not be involved in actual motion. */ int limit = to; int offset; - int height = SCREEN_HEIGHT (screen); + int height = FRAME_LINES (frame); if (amount == 0) return 0; @@ -466,60 +931,60 @@ scroll_cost (screen, from, to, amount) offset = height - limit; return - (SCREEN_INSERT_COST (screen)[offset + from] - + (amount - 1) * SCREEN_INSERTN_COST (screen)[offset + from] - + SCREEN_DELETEN_COST (screen)[offset + to] - + (amount - 1) * SCREEN_DELETE_COST (screen)[offset + to]); + (FRAME_INSERT_COST (frame)[offset + from] + + (amount - 1) * FRAME_INSERTN_COST (frame)[offset + from] + + FRAME_DELETE_COST (frame)[offset + to] + + (amount - 1) * FRAME_DELETEN_COST (frame)[offset + to]); } /* Calculate the line insertion/deletion overhead and multiply factor values */ static void -line_ins_del (screen, ov1, pf1, ovn, pfn, ov, mf) - SCREEN_PTR screen; +line_ins_del (frame, ov1, pf1, ovn, pfn, ov, mf) + FRAME_PTR frame; int ov1, ovn; int pf1, pfn; register int *ov, *mf; { register int i; - register int screen_height = SCREEN_HEIGHT (screen); + register int frame_lines = FRAME_LINES (frame); register int insert_overhead = ov1 * 10; register int next_insert_cost = ovn * 10; - for (i = 0; i < screen_height; i++) + for (i = frame_lines-1; i >= 0; i--) { - mf[screen_height - i] = next_insert_cost / 10; + mf[i] = next_insert_cost / 10; next_insert_cost += pfn; - ov[screen_height - i] = (insert_overhead + next_insert_cost) / 10; + ov[i] = (insert_overhead + next_insert_cost) / 10; insert_overhead += pf1; } } static void -ins_del_costs (screen, +ins_del_costs (frame, one_line_string, multi_string, setup_string, cleanup_string, costvec, ncostvec, coefficient) - SCREEN_PTR screen; + FRAME_PTR frame; char *one_line_string, *multi_string; char *setup_string, *cleanup_string; int *costvec, *ncostvec; int coefficient; { if (multi_string) - line_ins_del (screen, + line_ins_del (frame, string_cost (multi_string) * coefficient, per_line_cost (multi_string) * coefficient, 0, 0, costvec, ncostvec); else if (one_line_string) - line_ins_del (screen, + line_ins_del (frame, string_cost (setup_string) + string_cost (cleanup_string), 0, string_cost (one_line_string), per_line_cost (one_line_string), costvec, ncostvec); else - line_ins_del (screen, + line_ins_del (frame, 9999, 0, 9999, 0, costvec, ncostvec); } @@ -527,7 +992,7 @@ ins_del_costs (screen, /* Calculate the insert and delete line costs. Note that this is done even when running with a window system because we want to know how long scrolling takes (and avoid it). - This must be redone whenever the screen height changes. + This must be redone whenever the frame height changes. We keep the ID costs in a precomputed array based on the position at which the I or D is performed. Also, there are two kinds of ID @@ -536,71 +1001,75 @@ ins_del_costs (screen, only) and those that must repeatedly insert one line. The cost to insert N lines at line L is - [tt.t_ILov + (screen_height + 1 - L) * tt.t_ILpf] + - N * [tt.t_ILnov + (screen_height + 1 - L) * tt.t_ILnpf] + [tt.t_ILov + (frame_lines + 1 - L) * tt.t_ILpf] + + N * [tt.t_ILnov + (frame_lines + 1 - L) * tt.t_ILnpf] ILov represents the basic insert line overhead. ILpf is the padding required to allow the terminal time to move a line: insertion at line - L changes (screen_height + 1 - L) lines. + L changes (frame_lines + 1 - L) lines. The first bracketed expression above is the overhead; the second is the multiply factor. Both are dependent only on the position at which the insert is performed. We store the overhead in - SCREEN_INSERT_COST (screen) and the multiply factor in - SCREEN_INSERTN_COST (screen). Note however that any insertion + FRAME_INSERT_COST (frame) and the multiply factor in + FRAME_INSERTN_COST (frame). Note however that any insertion must include at least one multiply factor. Rather than compute this - as SCREEN_INSERT_COST (screen)[line]+SCREEN_INSERTN_COST (screen)[line], - we add SCREEN_INSERTN_COST (screen) into SCREEN_INSERT_COST (screen). + as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line], + we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame). This is reasonable because of the particular algorithm used in calcM. Deletion is essentially the same as insertion. */ -do_line_insertion_deletion_costs (screen, +void +do_line_insertion_deletion_costs (frame, ins_line_string, multi_ins_string, del_line_string, multi_del_string, setup_string, cleanup_string, coefficient) - SCREEN_PTR screen; + FRAME_PTR frame; char *ins_line_string, *multi_ins_string; char *del_line_string, *multi_del_string; char *setup_string, *cleanup_string; int coefficient; { - if (SCREEN_INSERT_COST (screen) != 0) + if (FRAME_INSERT_COST (frame) != 0) { - SCREEN_INSERT_COST (screen) - = (int *) xrealloc (SCREEN_INSERT_COST (screen), - SCREEN_HEIGHT (screen) * sizeof (int)); - SCREEN_DELETEN_COST (screen) - = (int *) xrealloc (SCREEN_DELETEN_COST (screen), - SCREEN_HEIGHT (screen) * sizeof (int)); - SCREEN_INSERTN_COST (screen) - = (int *) xrealloc (SCREEN_INSERTN_COST (screen), - SCREEN_HEIGHT (screen) * sizeof (int)); - SCREEN_DELETE_COST (screen) - = (int *) xrealloc (SCREEN_DELETE_COST (screen), - SCREEN_HEIGHT (screen) * sizeof (int)); + FRAME_INSERT_COST (frame) = + (int *) xrealloc (FRAME_INSERT_COST (frame), + FRAME_LINES (frame) * sizeof (int)); + FRAME_DELETEN_COST (frame) = + (int *) xrealloc (FRAME_DELETEN_COST (frame), + FRAME_LINES (frame) * sizeof (int)); + FRAME_INSERTN_COST (frame) = + (int *) xrealloc (FRAME_INSERTN_COST (frame), + FRAME_LINES (frame) * sizeof (int)); + FRAME_DELETE_COST (frame) = + (int *) xrealloc (FRAME_DELETE_COST (frame), + FRAME_LINES (frame) * sizeof (int)); } else { - SCREEN_INSERT_COST (screen) - = (int *) xmalloc (SCREEN_HEIGHT (screen) * sizeof (int)); - SCREEN_DELETEN_COST (screen) - = (int *) xmalloc (SCREEN_HEIGHT (screen) * sizeof (int)); - SCREEN_INSERTN_COST (screen) - = (int *) xmalloc (SCREEN_HEIGHT (screen) * sizeof (int)); - SCREEN_DELETE_COST (screen) - = (int *) xmalloc (SCREEN_HEIGHT (screen) * sizeof (int)); + FRAME_INSERT_COST (frame) = + (int *) xmalloc (FRAME_LINES (frame) * sizeof (int)); + FRAME_DELETEN_COST (frame) = + (int *) xmalloc (FRAME_LINES (frame) * sizeof (int)); + FRAME_INSERTN_COST (frame) = + (int *) xmalloc (FRAME_LINES (frame) * sizeof (int)); + FRAME_DELETE_COST (frame) = + (int *) xmalloc (FRAME_LINES (frame) * sizeof (int)); } - ins_del_costs (screen, + ins_del_costs (frame, ins_line_string, multi_ins_string, setup_string, cleanup_string, - SCREEN_INSERT_COST (screen), SCREEN_INSERTN_COST (screen), + FRAME_INSERT_COST (frame), FRAME_INSERTN_COST (frame), coefficient); - ins_del_costs (screen, + ins_del_costs (frame, del_line_string, multi_del_string, setup_string, cleanup_string, - SCREEN_DELETEN_COST (screen), SCREEN_DELETE_COST (screen), + FRAME_DELETE_COST (frame), FRAME_DELETEN_COST (frame), coefficient); } + +/* arch-tag: cdb7149c-48e7-4793-a948-2786c8e45485 + (do not change this comment) */