[gnumeric] Sheet: improve delayed redrawing a bit.

[Morten Welinder <mortenw src gnome org>]

commit 66e965a41be22753c1b8b2fb87a28b2724a56709
Author: Morten Welinder <terra gnome org>
Date:   Wed Apr 29 22:57:01 2020 -0400

    Sheet: improve delayed redrawing a bit.

 ChangeLog   |  5 ++++
 NEWS        |  2 +-
 src/sheet.c | 95 +++++++++++++++++++++++++++++++++++++++++++++++++++++--------
 src/sheet.h |  2 +-
 4 files changed, 90 insertions(+), 14 deletions(-)
---
diff --git a/ChangeLog b/ChangeLog
index 5c1602b0d..ac52b9b1e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,10 @@
 2020-04-29  Morten Welinder  <terra gnome org>
 
+       * src/sheet.c (cb_pending_redraw_handler): Do some cheap merging
+       of ranges before redrawing.  That should away some degenerate
+       cases.
+       (sheet_queue_redraw_range): Switch to using array for ranges.
+
        * src/ssconvert.c (convert): Infer image format from filename for
        object export just as for regular conversion.
 
diff --git a/NEWS b/NEWS
index 67265bd8c..55d27fc67 100644
--- a/NEWS
+++ b/NEWS
@@ -1,7 +1,7 @@
 Gnumeric 1.12.47
 
 Andreas:
-    * Fix chart name roundtrip through ODF. [#477]
+       * Fix chart name roundtrip through ODF. [#477]
 
 Jean:
        * Fix crash when the embedded spreadsheet is invalid. [#481]
diff --git a/src/sheet.c b/src/sheet.c
index 3f0558fcf..cb3ae17f5 100644
--- a/src/sheet.c
+++ b/src/sheet.c
@@ -70,6 +70,8 @@
 #include <stdlib.h>
 #include <string.h>
 
+static gboolean debug_redraw;
+
 static GnmSheetSize *
 gnm_sheet_size_copy (GnmSheetSize *size)
 {
@@ -854,7 +856,9 @@ gnm_sheet_init (Sheet *sheet)
 
        sheet->index_in_wb = -1;
 
+       sheet->pending_redraw = g_array_new (FALSE, FALSE, sizeof (GnmRange));
        sheet->pending_redraw_src = 0;
+       debug_redraw = gnm_debug_flag ("redraw-ranges");
 }
 
 static Sheet the_invalid_sheet;
@@ -3244,20 +3248,85 @@ sheet_redraw_range (Sheet const *sheet, GnmRange const *range)
        gnm_app_recalc_finish ();
 }
 
+static gboolean
+merge_ranges (GnmRange *a, GnmRange const *b)
+{
+       if (a->start.row == b->start.row &&
+           a->end.row == b->end.row &&
+           a->end.col + 1 >= b->start.col) {
+               // "a" is just left of "b", possibly with overlap
+               a->end.col = MAX (a->end.col, b->end.col);
+               return TRUE;
+       }
+
+       if (a->start.col == b->start.col &&
+           a->end.col == b->end.col &&
+           a->end.row + 1 >= b->start.row) {
+               // "a" is just on top of "b", possibly with overlap
+               a->end.row = MAX (a->end.row, b->end.row);
+               return TRUE;
+       }
+
+       if (range_contained (b, a)) {
+               // "b" is inside "a"
+               return TRUE;
+       }
+
+       // Punt.
+       return FALSE;
+}
+
+static gboolean
+try_merge_pair (GArray *arr, unsigned ui1, unsigned ui2)
+{
+       GnmRange *ra = &g_array_index (arr, GnmRange, ui1);
+       GnmRange *rb = &g_array_index (arr, GnmRange, ui2);
+
+       if (merge_ranges (ra, rb)) {
+               g_array_remove_index (arr, ui2);
+               return TRUE;
+       } else
+               return FALSE;
+}
+
+
 static gboolean
 cb_pending_redraw_handler (Sheet *sheet)
 {
-       while (sheet->pending_redraw) {
-               GnmRange *r = sheet->pending_redraw->data;
-               sheet->pending_redraw =
-                       g_slist_delete_link (sheet->pending_redraw,
-                                            sheet->pending_redraw);
+       unsigned ui, len;
+       GArray *arr = sheet->pending_redraw;
+
+       // It's possible that more redraws will arrive as we process these
+       // so be careful only to touch the right ones.
+
+       if (debug_redraw)
+               g_printerr ("Entering redraw with %u ranges\n", arr->len);
+       if (arr->len >= 2) {
+               g_array_sort (arr, (GCompareFunc) gnm_range_compare);
+               // Two cheap passes through the ranges.
+               for (ui = arr->len - 1; ui > 0; ui--)
+                       try_merge_pair (arr, ui - 1, ui);
+               for (ui = arr->len - 1; ui > 0; ui--)
+                       try_merge_pair (arr, ui - 1, ui);
+               if (debug_redraw)
+                       g_printerr ("Down to %u ranges\n", arr->len);
+       }
+
+       // Lock down the length we handle here
+       len = arr->len;
+       for (ui = 0; ui < len; ui++) {
+               GnmRange const *r = &g_array_index (arr, GnmRange, ui);
+               if (debug_redraw)
+                       g_printerr ("Redrawing %s\n", range_as_string (r));
                sheet_redraw_range (sheet, r);
-               g_free (r);
        }
+       g_array_remove_range (arr, 0, len);
 
-       sheet->pending_redraw_src = 0;
-       return FALSE;
+       if (arr->len == 0) {
+               sheet->pending_redraw_src = 0;
+               return FALSE;
+       } else
+               return TRUE;
 }
 
 /**
@@ -3274,9 +3343,11 @@ sheet_queue_redraw_range (Sheet *sheet, GnmRange const *range)
        g_return_if_fail (IS_SHEET (sheet));
        g_return_if_fail (range != NULL);
 
-       sheet->pending_redraw =
-               g_slist_prepend (sheet->pending_redraw,
-                                g_memdup (range, sizeof (*range)));
+       if (debug_redraw)
+               g_printerr ("Adding %s\n", range_as_string (range));
+
+       g_array_append_val (sheet->pending_redraw, *range);
+
        if (sheet->pending_redraw_src == 0)
                sheet->pending_redraw_src =
                        g_timeout_add (0,
@@ -4898,7 +4969,7 @@ gnm_sheet_finalize (GObject *obj)
                g_source_remove (sheet->pending_redraw_src);
                sheet->pending_redraw_src = 0;
        }
-       g_slist_free_full (sheet->pending_redraw, g_free);
+       g_array_free (sheet->pending_redraw, TRUE);
 
        if (debug_FMR) {
                g_printerr ("Sheet %p is %s\n", sheet, sheet->name_quoted);
diff --git a/src/sheet.h b/src/sheet.h
index 50cf7d97c..bbc25a0d1 100644
--- a/src/sheet.h
+++ b/src/sheet.h
@@ -107,7 +107,7 @@ struct _Sheet {
 
        GnmDepContainer *deps;
 
-       GSList *pending_redraw;
+       GArray *pending_redraw;
        guint pending_redraw_src;
 
        GSList           *slicers;