[gtk/wip/otte/sortlistmodel2: 22/27] sortlistmodel: Properly compute runs

[Benjamin Otte <otte src gnome org>]

commit 880b897832fe0e0b840e5fe5f7ae38af03d5c03d
Author: Benjamin Otte <otte redhat com>
Date:   Tue Jul 21 04:50:05 2020 +0200

    sortlistmodel: Properly compute runs
    
    When updating a (partially) sorted model, take the known runs for the
    existing sort and apply them to the new sort. That way, we don't have to
    check the whole model again.
    
    Benchmarks:
    
          appending half the items to a model of strings
                            old      new
          512,000 items   437ms    389ms
        1,024,000 items  1006ms    914ms
    
          appending 10% of the items to a model of strings
                            old      new
          512,000 items   206ms    132ms
        1,024,000 items   438ms    301ms
    
          appending 1 item to a model of strings
                            old      new
           64,000 items   1.8ms   0.00ms
          512,000 items     ---   0.01ms

 gtk/gtksortlistmodel.c | 55 +++++++++++++++++++++++++++++++++++---------------
 1 file changed, 39 insertions(+), 16 deletions(-)
---
diff --git a/gtk/gtksortlistmodel.c b/gtk/gtksortlistmodel.c
index 72db0c05db..df11ea7fda 100644
--- a/gtk/gtksortlistmodel.c
+++ b/gtk/gtksortlistmodel.c
@@ -414,6 +414,7 @@ gtk_sort_list_model_update_items (GtkSortListModel *self,
                                   guint            *unmodified_end)
 {
   guint i, n_items, valid;
+  guint run_index, valid_run, valid_run_end, run_end;
   guint start, end;
   gpointer *old_keys;
 
@@ -445,28 +446,50 @@ gtk_sort_list_model_update_items (GtkSortListModel *self,
 
   /* then, update the positions */
   valid = 0;
-  for (i = 0; i < n_items; i++)
+  valid_run = 0;
+  valid_run_end = 0;
+  run_index = 0;
+  run_end = 0;
+  for (i = 0; i < n_items;)
     {
-      guint pos = ((char *) self->positions[i] - (char *) old_keys) / self->key_size;
-
-      if (pos >= position + removed)
-        pos = pos - removed + added;
-      else if (pos >= position)
-        { 
-          start = MIN (start, valid);
-          end = n_items - i - 1;
-          continue;
+      if (runs[run_index] == 0)
+        {
+          run_end = n_items;
+          valid_run_end = G_MAXUINT;
+        }
+      else
+        {
+          run_end += runs[run_index++];
         }
 
-      self->positions[valid] = key_from_pos (self, pos);
-      valid++;
-    }
-  self->positions = g_renew (gpointer, self->positions, n_items - removed + added);
+      for (; i < run_end; i++)
+        {
+          guint pos = ((char *) self->positions[i] - (char *) old_keys) / self->key_size;
+
+          if (pos >= position + removed)
+            pos = pos - removed + added;
+          else if (pos >= position)
+            { 
+              start = MIN (start, valid);
+              end = n_items - i - 1;
+              continue;
+            }
 
-  /* FIXME */
-  runs[0] = 0;
+          self->positions[valid] = key_from_pos (self, pos);
+          valid++;
+        }
 
+      if (valid_run_end < valid)
+        {
+          runs[valid_run++] = valid - valid_run_end;
+          valid_run_end = valid;
+        }
+    }
+  g_assert (i == n_items);
   g_assert (valid == n_items - removed);
+  runs[valid_run] = 0;
+
+  self->positions = g_renew (gpointer, self->positions, n_items - removed + added);
 
   self->n_items = n_items - removed + added;