changeset 29980:171ba59e1cb0

(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.

--- 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