# HG changeset patch # User Gerd Moellmann # Date 962224130 0 # Node ID 171ba59e1cb0c2b78aca84f3e95f25677f9fb4eb # Parent 6fe8f444b6a3b3869d846f778ff6f406476a42b7 (struct row_entry): New structure. (row_entry_pool, row_entry_pool_size, row_entry_idx, row_table) (row_table_size, old_lines, new_lines, old_lines_size) (new_lines_size, run_pool, runs_size, runs): New variables. (add_row_entry): New function. (scrolling_window): Use data structures allocated with xmalloc and held in global variables, instead of allocing them with alloca and holding them in local variables. Use a larger hash table whose size depends on glyph matrix sizes. Don't use bzero to clear the hash table; instead, clear used slots only. diff -r 6fe8f444b6a3 -r 171ba59e1cb0 src/dispnew.c --- a/src/dispnew.c Wed Jun 28 20:28:21 2000 +0000 +++ b/src/dispnew.c Wed Jun 28 20:28:50 2000 +0000 @@ -4217,6 +4217,120 @@ } +/* Set WINDOW->must_be_updated_p to ON_P for all windows in the window + tree rooted at W. */ + +void +set_window_update_flags (w, on_p) + struct window *w; + int on_p; +{ + while (w) + { + if (!NILP (w->hchild)) + set_window_update_flags (XWINDOW (w->hchild), on_p); + else if (!NILP (w->vchild)) + set_window_update_flags (XWINDOW (w->vchild), on_p); + else + w->must_be_updated_p = on_p; + + w = NILP (w->next) ? 0 : XWINDOW (w->next); + } +} + + + +/*********************************************************************** + Window-Based Scrolling + ***********************************************************************/ + +/* Structure describing rows in scrolling_window. */ + +struct row_entry +{ + /* Number of occurrences of this row in desired and current matrix. */ + int old_uses, new_uses; + + /* Vpos of row in new matrix. */ + int new_line_number; + + /* Bucket index of this row_entry in the hash table row_table. */ + int bucket; + + /* The row described by this entry. */ + struct glyph_row *row; + + /* Hash collision chain. */ + struct row_entry *next; +}; + +/* A pool to allocate row_entry structures from, and the size of the + pool. The pool is reallocated in scrolling_window when we find + that we need a larger one. */ + +static struct row_entry *row_entry_pool; +static int row_entry_pool_size; + +/* Index of next free entry in row_entry_pool. */ + +static int row_entry_idx; + +/* The hash table used during scrolling, and the table's size. This + table is used to quickly identify equal rows in the desired and + current matrix. */ + +static struct row_entry **row_table; +static int row_table_size; + +/* Vectors of pointers to row_entry structures belonging to the + current and desired matrix, and the size of the vectors. */ + +static struct row_entry **old_lines, **new_lines; +static int old_lines_size, new_lines_size; + +/* A pool to allocate run structures from, and its size. */ + +static struct run *run_pool; +static int runs_size; + +/* A vector of runs of lines found during scrolling. */ + +static struct run **runs; + +static struct row_entry *add_row_entry P_ ((struct window *, + struct glyph_row *)); + + +/* Add glyph row ROW to the scrolling hash table during the scrolling + of window W. */ + +static INLINE struct row_entry * +add_row_entry (w, row) + struct window *w; + struct glyph_row *row; +{ + struct row_entry *entry; + int i = row->hash % row_table_size; + + entry = row_table[i]; + while (entry && !row_equal_p (w, entry->row, row)) + entry = entry->next; + + if (entry == NULL) + { + entry = row_entry_pool + row_entry_idx++; + entry->row = row; + entry->old_uses = entry->new_uses = 0; + entry->new_line_number = 0; + entry->bucket = i; + entry->next = row_table[i]; + row_table[i] = entry; + } + + return entry; +} + + /* Try to reuse part of the current display of W by scrolling lines. HEADER_LINE_P non-zero means W has a top mode line. @@ -4248,39 +4362,20 @@ struct window *w; int header_line_p; { - struct symbol - { - /* Number of occurrences of this line in old and new matrix. */ - short old_uses, new_uses; - - /* Vpos of line in new matrix. */ - short new_line_number; - - /* The line itself. */ - struct glyph_row *row; - - /* Hash collision chain. */ - struct symbol *next; - }; - - int SYMBOL_TABLE_SIZE = 101; - struct symbol **table; - struct symbol **old_line_syms, **new_line_syms; - int i, j, first_old, first_new, last_old, last_new; - struct symbol *sym; - struct run **runs; - int nruns; struct glyph_matrix *desired_matrix = w->desired_matrix; struct glyph_matrix *current_matrix = w->current_matrix; int yb = window_text_bottom_y (w); + int i, j, first_old, first_new, last_old, last_new; + int nruns, nbytes, n, run_idx; + struct row_entry *entry; /* Skip over rows equal at the start. */ i = header_line_p ? 1 : 0; while (i < current_matrix->nrows - 1 && MATRIX_ROW_ENABLED_P (current_matrix, i) && MATRIX_ROW_ENABLED_P (desired_matrix, i) - && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (desired_matrix, i)) < yb - && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (current_matrix, i)) < yb + && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (desired_matrix, i)) <= yb + && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (current_matrix, i)) <= yb && row_equal_p (w, MATRIX_ROW (desired_matrix, i), MATRIX_ROW (current_matrix, i))) @@ -4302,7 +4397,7 @@ i = first_new + 1; while (i < desired_matrix->nrows - 1 && MATRIX_ROW (desired_matrix, i)->enabled_p - && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (desired_matrix, i)) < yb) + && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (desired_matrix, i)) <= yb) ++i; if (!MATRIX_ROW (desired_matrix, i)->enabled_p) @@ -4316,7 +4411,7 @@ disabled. */ i = first_old + 1; while (i < current_matrix->nrows - 1 - && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (current_matrix, i)) < yb) + && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (current_matrix, i)) <= yb) ++i; last_old = i; @@ -4339,76 +4434,84 @@ if (last_new == first_new) return 0; - /* Allocate a hash table in which all rows will be inserted. */ - table = (struct symbol **) alloca (SYMBOL_TABLE_SIZE * sizeof *table); - bzero (table, SYMBOL_TABLE_SIZE * sizeof *table); - - /* For each row in the current matrix, record the symbol belonging - to the row in OLD_LINE_SYMS. */ - old_line_syms = (struct symbol **) alloca (current_matrix->nrows - * sizeof *old_line_syms); - new_line_syms = (struct symbol **) alloca (desired_matrix->nrows - * sizeof *new_line_syms); - -#define ADDSYM(ROW) \ - do \ - { \ - struct glyph_row *row_ = (ROW); \ - int i_ = row_->hash % SYMBOL_TABLE_SIZE; \ - sym = table[i_]; \ - while (sym && !row_equal_p (w, sym->row, row_)) \ - sym = sym->next; \ - if (sym == NULL) \ - { \ - sym = (struct symbol *) alloca (sizeof *sym); \ - sym->row = row_; \ - sym->old_uses = sym->new_uses = 0; \ - sym->next = table[i_]; \ - table[i_] = sym; \ - } \ - } \ - while (0) - - /* Add current rows to the symbol table. */ + /* Reallocate vectors, tables etc. if necessary. */ + + if (current_matrix->nrows > old_lines_size) + { + old_lines_size = current_matrix->nrows; + nbytes = old_lines_size * sizeof *old_lines; + old_lines = (struct row_entry **) xrealloc (old_lines, nbytes); + } + + if (desired_matrix->nrows > new_lines_size) + { + new_lines_size = desired_matrix->nrows; + nbytes = new_lines_size * sizeof *new_lines; + new_lines = (struct row_entry **) xrealloc (new_lines, nbytes); + } + + n = desired_matrix->nrows + current_matrix->nrows; + if (3 * n > row_table_size) + { + row_table_size = next_almost_prime (3 * n); + nbytes = row_table_size * sizeof *row_table; + row_table = (struct row_entry **) xrealloc (row_table, nbytes); + bzero (row_table, nbytes); + } + + if (n > row_entry_pool_size) + { + row_entry_pool_size = n; + nbytes = row_entry_pool_size * sizeof *row_entry_pool; + row_entry_pool = (struct row_entry *) xrealloc (row_entry_pool, nbytes); + } + + if (desired_matrix->nrows > runs_size) + { + runs_size = desired_matrix->nrows; + nbytes = runs_size * sizeof *runs; + runs = (struct run **) xrealloc (runs, nbytes); + nbytes = runs_size * sizeof *run_pool; + run_pool = (struct run *) xrealloc (run_pool, nbytes); + } + + nruns = run_idx = 0; + row_entry_idx = 0; + + /* Add rows from the current and desired matrix to the hash table + row_hash_table to be able to find equal ones quickly. */ + for (i = first_old; i < last_old; ++i) { if (MATRIX_ROW (current_matrix, i)->enabled_p) { - ADDSYM (MATRIX_ROW (current_matrix, i)); - old_line_syms[i] = sym; - ++sym->old_uses; + entry = add_row_entry (w, MATRIX_ROW (current_matrix, i)); + old_lines[i] = entry; + ++entry->old_uses; } else - old_line_syms[i] = NULL; + old_lines[i] = NULL; } - /* Add desired rows to the symbol table. */ for (i = first_new; i < last_new; ++i) { xassert (MATRIX_ROW_ENABLED_P (desired_matrix, i)); - ADDSYM (MATRIX_ROW (desired_matrix, i)); - ++sym->new_uses; - new_line_syms[i] = sym; - sym->new_line_number = i; + entry = add_row_entry (w, MATRIX_ROW (desired_matrix, i)); + ++entry->new_uses; + entry->new_line_number = i; + new_lines[i] = entry; } -#undef ADDSYM - - /* Record in runs which moves were found, ordered by pixel - height of copied areas. */ - nruns = 0; - runs = (struct run **) alloca (desired_matrix->nrows * sizeof *runs); - /* Identify moves based on lines that are unique and equal in both matrices. */ for (i = first_old; i < last_old;) - if (old_line_syms[i] - && old_line_syms[i]->old_uses == 1 - && old_line_syms[i]->new_uses == 1) + if (old_lines[i] + && old_lines[i]->old_uses == 1 + && old_lines[i]->new_uses == 1) { int j, k; - int new_line = old_line_syms[i]->new_line_number; - struct run *run = (struct run *) alloca (sizeof *run); + int new_line = old_lines[i]->new_line_number; + struct run *run = run_pool + run_idx++; /* Record move. */ run->current_vpos = i; @@ -4423,7 +4526,7 @@ k = new_line - 1; while (j > first_old && k > first_new - && old_line_syms[j] == new_line_syms[k]) + && old_lines[j] == new_lines[k]) { int h = MATRIX_ROW (current_matrix, j)->height; --run->current_vpos; @@ -4440,7 +4543,7 @@ k = new_line + 1; while (j < last_old && k < last_new - && old_line_syms[j] == new_line_syms[k]) + && old_lines[j] == new_lines[k]) { int h = MATRIX_ROW (current_matrix, j)->height; ++run->nrows; @@ -4518,33 +4621,15 @@ } } + /* Clear the hash table, for the next time. */ + for (i = 0; i < row_entry_idx; ++i) + row_table[row_entry_pool[i].bucket] = NULL; + /* Value is non-zero to indicate that we scrolled the display. */ return 1; } -/* Set WINDOW->must_be_updated_p TO ON_P for all windows WINDOW in the - window tree rooted at W. */ - -void -set_window_update_flags (w, on_p) - struct window *w; - int on_p; -{ - while (w) - { - if (!NILP (w->hchild)) - set_window_update_flags (XWINDOW (w->hchild), on_p); - else if (!NILP (w->vchild)) - set_window_update_flags (XWINDOW (w->vchild), on_p); - else - w->must_be_updated_p = on_p; - - w = NILP (w->next) ? 0 : XWINDOW (w->next); - } -} - - /************************************************************************ Frame-Based Updates