[gtk/wip/otte/sortlistmodel: 101/134] timsort: Add gtk_tim_sort_set_runs()

[Benjamin Otte <otte src gnome org>]

commit f32c48cb36cb7261a28d57f297927d06d951a876
Author: Benjamin Otte <otte redhat com>
Date:   Sat Jul 11 06:02:58 2020 +0200

    timsort: Add gtk_tim_sort_set_runs()
    
    ... and use it in the SortListModel
    
    Setting runs allows declaring already sorted regions so the sort does
    not attempt to sort them again.
    
    This massively speeds up partial inserts where we can reuse the sorted
    model as a run and only resort the newly inserted parts.
    
    Benchmarks:
    
        appending half the model
                        qsort  timsort
        128,000 items    94ms     69ms
        256,000 items   202ms    143ms
        512,000 items   488ms    328ms
    
        appending 1 item
                        qsort  timsort
          8,000 items   1.5ms    0.0ms
         16,000 items   3.1ms    0.0ms
                  ...
        512,000 items     ---    1.8ms

 gtk/gtksortlistmodel.c  | 27 ++++++++++++++++---------
 gtk/gtktim1sortmodel.c  | 27 ++++++++++++++++---------
 gtk/gtktimsort-impl.c   |  4 ----
 gtk/gtktimsort.c        | 53 +++++++++++++++++++++++++++++++++++++++++++++++++
 gtk/gtktimsortprivate.h |  5 +++++
 5 files changed, 94 insertions(+), 22 deletions(-)
---
diff --git a/gtk/gtksortlistmodel.c b/gtk/gtksortlistmodel.c
index cdfce89f01..f7db707e5a 100644
--- a/gtk/gtksortlistmodel.c
+++ b/gtk/gtksortlistmodel.c
@@ -175,13 +175,22 @@ sort_func (gconstpointer a,
 }
 
 static void
-gtk_sort_list_model_resort (GtkSortListModel *self)
+gtk_sort_list_model_resort (GtkSortListModel *self,
+                            guint             already_sorted)
 {
-  gtk_tim_sort (sort_array_get_data (&self->items),
-                sort_array_get_size (&self->items),
-                sizeof (SortItem),
-                sort_func,
-                self->sorter);
+  GtkTimSort sort;
+
+  gtk_tim_sort_init (&sort,
+                     sort_array_get_data (&self->items),
+                     sort_array_get_size (&self->items),
+                     sizeof (SortItem),
+                     sort_func,
+                     self->sorter);
+  gtk_tim_sort_set_runs (&sort, (gsize[2]) { already_sorted, 0 });
+
+  while (gtk_tim_sort_step (&sort));
+
+  gtk_tim_sort_finish (&sort);
 }
 
 static void
@@ -252,7 +261,7 @@ gtk_sort_list_model_items_changed_cb (GListModel       *model,
         {
           sort_array_append (&self->items, &(SortItem) { g_list_model_get_item (self->model, i), i });
         }
-      gtk_sort_list_model_resort (self);
+      gtk_sort_list_model_resort (self, sort_array_get_size (&self->items) - added);
 
       for (i = 0; i < start; i++)
         {
@@ -339,7 +348,7 @@ gtk_sort_list_model_sorter_changed_cb (GtkSorter        *sorter,
   else if (sort_array_is_empty (&self->items))
     gtk_sort_list_model_create_items (self);
 
-  gtk_sort_list_model_resort (self);
+  gtk_sort_list_model_resort (self, 0);
 
   n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
   if (n_items > 1)
@@ -476,7 +485,7 @@ gtk_sort_list_model_set_model (GtkSortListModel *self,
       added = g_list_model_get_n_items (model);
 
       gtk_sort_list_model_create_items (self);
-      gtk_sort_list_model_resort (self);
+      gtk_sort_list_model_resort (self, 0);
     }
   else
     added = 0;
diff --git a/gtk/gtktim1sortmodel.c b/gtk/gtktim1sortmodel.c
index bf7c24f076..19f4e851b4 100644
--- a/gtk/gtktim1sortmodel.c
+++ b/gtk/gtktim1sortmodel.c
@@ -175,13 +175,22 @@ sort_func (gconstpointer a,
 }
 
 static void
-gtk_tim1_sort_model_resort (GtkTim1SortModel *self)
+gtk_tim1_sort_model_resort (GtkTim1SortModel *self,
+                            guint             already_sorted)
 {
-  gtk_tim_sort (sort_array_get_data (&self->items),
-                sort_array_get_size (&self->items),
-                sizeof (SortItem),
-                sort_func,
-                self->sorter);
+  GtkTimSort sort;
+
+  gtk_tim_sort_init (&sort,
+                     sort_array_get_data (&self->items),
+                     sort_array_get_size (&self->items),
+                     sizeof (SortItem),
+                     sort_func,
+                     self->sorter);
+  gtk_tim_sort_set_runs (&sort, (gsize[2]) { already_sorted, 0});
+
+  while (gtk_tim_sort_step (&sort));
+
+  gtk_tim_sort_finish (&sort);
 }
 
 static void
@@ -252,7 +261,7 @@ gtk_tim1_sort_model_items_changed_cb (GListModel       *model,
         {
           sort_array_append (&self->items, &(SortItem) { g_list_model_get_item (self->model, i), i });
         }
-      gtk_tim1_sort_model_resort (self);
+      gtk_tim1_sort_model_resort (self, sort_array_get_size (&self->items) - added);
 
       for (i = 0; i < start; i++)
         {
@@ -339,7 +348,7 @@ gtk_tim1_sort_model_sorter_changed_cb (GtkSorter        *sorter,
   else if (sort_array_is_empty (&self->items))
     gtk_tim1_sort_model_create_items (self);
 
-  gtk_tim1_sort_model_resort (self);
+  gtk_tim1_sort_model_resort (self, 0);
 
   n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
   if (n_items > 1)
@@ -476,7 +485,7 @@ gtk_tim1_sort_model_set_model (GtkTim1SortModel *self,
       added = g_list_model_get_n_items (model);
 
       gtk_tim1_sort_model_create_items (self);
-      gtk_tim1_sort_model_resort (self);
+      gtk_tim1_sort_model_resort (self, 0);
     }
   else
     added = 0;
diff --git a/gtk/gtktimsort-impl.c b/gtk/gtktimsort-impl.c
index e6f9f3bba6..5dd1c98d3f 100644
--- a/gtk/gtktimsort-impl.c
+++ b/gtk/gtktimsort-impl.c
@@ -215,10 +215,6 @@ gtk_tim_sort(merge_append) (GtkTimSort *self)
   /* Push run onto pending-run stack, and maybe merge */
   gtk_tim_sort_push_run (self, self->base, run_len);
 
-  /* Advance to find next run */
-  self->base = ELEM (self->base, run_len);
-  self->size -= run_len;
-
   return TRUE;
 }
 
diff --git a/gtk/gtktimsort.c b/gtk/gtktimsort.c
index 451a63a902..c59682cebd 100644
--- a/gtk/gtktimsort.c
+++ b/gtk/gtktimsort.c
@@ -125,10 +125,15 @@ gtk_tim_sort_push_run (GtkTimSort *self,
                        gsize       len)
 {
   g_assert (self->pending_runs < GTK_TIM_SORT_MAX_PENDING);
+  g_assert (len <= self->size);
 
   self->run[self->pending_runs].base = base;
   self->run[self->pending_runs].len = len;
   self->pending_runs++;
+
+  /* Advance to find next run */
+  self->base = ((char *) self->base) + len * self->element_size;
+  self->size -= len;
 }
 
 /**
@@ -167,6 +172,54 @@ gtk_tim_sort_ensure_capacity (GtkTimSort *self,
   return self->tmp;
 }
 
+/*<private>
+ * gtk_tim_sort_get_runs:
+ * @self: a #GtkTimSort
+ * @runs: (out) (caller-allocates): Place to store the 0-terminated list of
+ *     runs
+ *
+ * Stores the already presorted list of runs - ranges of items that are
+ * known to be sorted among themselves.
+ *
+ * This can be used with gtk_tim_sort_set_runs() when resuming a sort later.
+ **/
+void
+gtk_tim_sort_get_runs (GtkTimSort *self,
+                       gsize       runs[GTK_TIM_SORT_MAX_PENDING + 1])
+{
+  gsize i;
+
+  g_return_if_fail (self);
+  g_return_if_fail (runs);
+
+  for (i = 0; i < self->pending_runs; i++)
+    runs[i] = self->run[i].len;
+}
+
+/*<private>
+ * gtk_tim_sort_set_runs:
+ * @self: a freshly initialized #GtkTimSort
+ * @runs: (array length=zero-terminated): a 0-terminated list of runs
+ *
+ * Sets the list of runs. A run is a range of items that are already
+ * sorted correctly among themselves. Runs must appear at the beginning of
+ * the array.
+ *
+ * Runs can only be set at the beginning of the sort operation.
+ **/
+void
+gtk_tim_sort_set_runs (GtkTimSort *self,
+                       gsize      *runs)
+{
+  gsize i;
+
+  g_return_if_fail (self);
+  g_return_if_fail (self->pending_runs == 0);
+
+  for (i = 0; runs[i] != 0; i++)
+    gtk_tim_sort_push_run (self, self->base, runs[i]);
+}
+
 #if 1
 #define WIDTH 4
 #include "gtktimsort-impl.c"
diff --git a/gtk/gtktimsortprivate.h b/gtk/gtktimsortprivate.h
index d44c74c470..f6ebd348e9 100644
--- a/gtk/gtktimsortprivate.h
+++ b/gtk/gtktimsortprivate.h
@@ -95,6 +95,11 @@ void            gtk_tim_sort_init                               (GtkTimSort
                                                                  gpointer                data);
 void            gtk_tim_sort_finish                             (GtkTimSort             *self);
 
+void            gtk_tim_sort_get_runs                           (GtkTimSort             *self,
+                                                                 gsize                   
runs[GTK_TIM_SORT_MAX_PENDING + 1]);
+void            gtk_tim_sort_set_runs                           (GtkTimSort             *self,
+                                                                 gsize                  *runs);
+
 gboolean        gtk_tim_sort_step                               (GtkTimSort             *self);
 
 void            gtk_tim_sort                                    (gpointer                base,