[gtk/wip/otte/sortlistmodel2: 4/27] sortlistmodel: Use timsort

[Benjamin Otte <otte src gnome org>]

commit 800170b47dfede5e9de300eaed630ddebd5c27de
Author: Benjamin Otte <otte redhat com>
Date:   Fri Jul 17 02:47:22 2020 +0200

    sortlistmodel: Use timsort
    
    Simply replace the old qsort() call with a timsort() call.
    
    This is ultimately relevant because timsort is a LOT faster in merging
    to already sorted lists (think items-chaged adding some items) or
    reversing an existing list (think columnview sort order changes).
    
    Benchmarks:
    
        initially sorting the model
                        qsort  timsort
        128,000 items   124ms    111ms
        256,000 items   264ms    250ms

 gtk/gtksortlistmodel.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)
---
diff --git a/gtk/gtksortlistmodel.c b/gtk/gtksortlistmodel.c
index 93d51c5951..cdfce89f01 100644
--- a/gtk/gtksortlistmodel.c
+++ b/gtk/gtksortlistmodel.c
@@ -23,6 +23,7 @@
 
 #include "gtkintl.h"
 #include "gtkprivate.h"
+#include "gtktimsortprivate.h"
 
 typedef struct _SortItem SortItem;
 struct _SortItem
@@ -176,11 +177,11 @@ sort_func (gconstpointer a,
 static void
 gtk_sort_list_model_resort (GtkSortListModel *self)
 {
-  g_qsort_with_data (sort_array_get_data (&self->items),
-                     sort_array_get_size (&self->items),
-                     sizeof (SortItem),
-                     sort_func,
-                     self->sorter);
+  gtk_tim_sort (sort_array_get_data (&self->items),
+                sort_array_get_size (&self->items),
+                sizeof (SortItem),
+                sort_func,
+                self->sorter);
 }
 
 static void