[gtk/wip/otte/sortlistmodel] timsort: Add gtk_tim_sort_set_already_sorted()

[Benjamin Otte <otte src gnome org>]

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

    timsort: Add gtk_tim_sort_set_already_sorted()
    
    ... and use it in Tim1SortModel

 gtk/gtktim1sortmodel.c  | 27 ++++++++++++++++++---------
 gtk/gtktimsort-impl.c   |  4 ----
 gtk/gtktimsort.c        | 16 ++++++++++++++++
 gtk/gtktimsortprivate.h |  2 ++
 4 files changed, 36 insertions(+), 13 deletions(-)
---
diff --git a/gtk/gtktim1sortmodel.c b/gtk/gtktim1sortmodel.c
index 99ebd917fe..832a2976f4 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_already_sorted (&sort, already_sorted);
+
+  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..a76913fbd3 100644
--- a/gtk/gtktimsort.c
+++ b/gtk/gtktimsort.c
@@ -129,6 +129,10 @@ gtk_tim_sort_push_run (GtkTimSort *self,
   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 +171,18 @@ gtk_tim_sort_ensure_capacity (GtkTimSort *self,
   return self->tmp;
 }
 
+void
+gtk_tim_sort_set_already_sorted (GtkTimSort *self,
+                                 gsize       already_sorted)
+{
+  g_assert (self);
+  g_assert (self->pending_runs == 0);
+  g_assert (already_sorted <= self->size);
+
+  if (already_sorted > 1)
+    gtk_tim_sort_push_run (self, self->base, already_sorted);
+}
+
 #if 1
 #define WIDTH 4
 #include "gtktimsort-impl.c"
diff --git a/gtk/gtktimsortprivate.h b/gtk/gtktimsortprivate.h
index d44c74c470..f3875c2cb5 100644
--- a/gtk/gtktimsortprivate.h
+++ b/gtk/gtktimsortprivate.h
@@ -95,6 +95,8 @@ void            gtk_tim_sort_init                               (GtkTimSort
                                                                  gpointer                data);
 void            gtk_tim_sort_finish                             (GtkTimSort             *self);
 
+void            gtk_tim_sort_set_already_sorted                 (GtkTimSort             *self,
+                                                                 gsize                   already_sorted);
 gboolean        gtk_tim_sort_step                               (GtkTimSort             *self);
 
 void            gtk_tim_sort                                    (gpointer                base,