wip: incremental sort

This is the dumbest possible sortmodel using an array:
Just grab all the items, put them in the array, qsort() the array.

demos/gtk-demo/listview_colors.c

@@ -883,53 +883,6 @@ compare_blue (gconstpointer a,
     return GTK_ORDERING_EQUAL;
 }
 
-static void
-clear_timeout (gpointer data)
-{
-  guint timeout = GPOINTER_TO_UINT (data);
-
-  if (timeout)
-    g_source_remove (timeout);
-}
-
-static gboolean
-start_reveal (gpointer data)
-{
-  gtk_revealer_set_transition_type (GTK_REVEALER (data), GTK_REVEALER_TRANSITION_TYPE_CROSSFADE);
-  gtk_revealer_set_reveal_child (GTK_REVEALER (data), TRUE);
-
-  g_object_set_data (G_OBJECT (data), "timeout", NULL);
-
-  return G_SOURCE_REMOVE;
-}
-
-static void
-sorting_changed (GObject     *model,
-                 GParamSpec  *pspec,
-                 GtkRevealer *revealer)
-{
-  gboolean sorting;
-
-  g_object_get (model, "sorting", &sorting, NULL);
-
-  if (sorting)
-    {
-      guint timeout;
-
-      timeout = g_timeout_add (2000, start_reveal, revealer);
-      g_object_set_data_full (G_OBJECT (revealer), "timeout",
-                              GUINT_TO_POINTER (timeout),
-                              clear_timeout);
-    }
-  else
-    {
-      g_object_set_data (G_OBJECT (revealer), "timeout", NULL);
-
-      gtk_revealer_set_transition_type (GTK_REVEALER (revealer), GTK_REVEALER_TRANSITION_TYPE_NONE);
-      gtk_revealer_set_reveal_child (GTK_REVEALER (revealer), FALSE);
-    }
-}
-
 static GtkWidget *window = NULL;
 
 GtkWidget *
@@ -959,8 +912,6 @@ do_listview_colors (GtkWidget *do_widget)
       GtkWidget *selection_info_toggle;
       GtkWidget *selection_info_revealer;
       GtkCssProvider *provider;
-      GtkWidget *revealer;
-      GtkWidget *spinner;
 
       provider = gtk_css_provider_new ();
       gtk_css_provider_load_from_resource (provider, "/listview_colors/listview_colors.css");
@@ -1096,17 +1047,6 @@ do_listview_colors (GtkWidget *do_widget)
       gtk_drop_down_set_selected (GTK_DROP_DOWN (dropdown), 3); /* 4096 */
       gtk_header_bar_pack_start (GTK_HEADER_BAR (header), dropdown);
 
-      revealer = gtk_revealer_new ();
-      gtk_revealer_set_transition_type (GTK_REVEALER (revealer), GTK_REVEALER_TRANSITION_TYPE_CROSSFADE);
-      gtk_revealer_set_transition_duration (GTK_REVEALER (revealer), 2000);
-      spinner = gtk_spinner_new ();
-      gtk_revealer_set_child (GTK_REVEALER (revealer), spinner);
-      gtk_header_bar_pack_end (GTK_HEADER_BAR (header), revealer);
-
-      g_signal_connect (model, "notify::sorting", G_CALLBACK (sorting_changed), revealer);
-      g_object_bind_property (model, "sorting", spinner, "spinning", G_BINDING_DEFAULT);
-
-
       sorters = g_list_store_new (GTK_TYPE_SORTER);
 
       /* An empty multisorter doesn't do any sorting and the sortmodel is

gtk/gtk.h

@@ -235,8 +235,6 @@
 #include <gtk/gtksorter.h>
 #include <gtk/gtksor2listmodel.h>
 #include <gtk/gtksor3listmodel.h>
-#include <gtk/gtksor4listmodel.h>
-#include <gtk/gtksor5listmodel.h>
 #include <gtk/gtksortlistmodel.h>
 #include <gtk/gtkstacksidebar.h>
 #include <gtk/gtksizegroup.h>
@@ -260,8 +258,6 @@
 #include <gtk/gtktexttag.h>
 #include <gtk/gtktexttagtable.h>
 #include <gtk/gtktextview.h>
-#include <gtk/gtktim1sortmodel.h>
-#include <gtk/gtktim2sortmodel.h>
 #include <gtk/gtktogglebutton.h>
 #include <gtk/gtktooltip.h>
 #include <gtk/gtktestutils.h>

gtk/gtkfilterlistmodel.c

@@ -178,7 +178,7 @@ gtk_filter_list_model_run_filter (GtkFilterListModel *self,
     }
 
   if (more)
-    gtk_bitset_remove_range_closed (self->pending, 0, pos - 1);
+    gtk_bitset_remove_range_closed (self->pending, 0, pos);
   else
     g_clear_pointer (&self->pending, gtk_bitset_unref);
   g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_PENDING]);
@@ -494,7 +494,7 @@ gtk_filter_list_model_refilter (GtkFilterListModel *self,
           {
           default:
             g_assert_not_reached ();
-            /* fallthrough */
+            G_GNUC_FALLTHROUGH;
           case GTK_FILTER_CHANGE_DIFFERENT:
             self->matches = gtk_bitset_new_empty ();
             pending = gtk_bitset_new_range (0, g_list_model_get_n_items (self->model));

gtk/gtksor2listmodel.c

@@ -307,7 +307,7 @@ gtk_sor2_list_model_class_init (GtkSor2ListModelClass *class)
                            P_("Model"),
                            P_("The model being sorted"),
                            G_TYPE_LIST_MODEL,
-                           GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
+                           GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY | G_PARAM_EXPLICIT_NOTIFY);
 
   g_object_class_install_properties (gobject_class, NUM_PROPERTIES, properties);
 }
@@ -422,13 +422,6 @@ gtk_sor2_list_model_set_sorter (GtkSor2ListModel *self,
       g_signal_connect (sorter, "changed", G_CALLBACK (gtk_sor2_list_model_sorter_changed_cb), self);
       gtk_sor2_list_model_sorter_changed_cb (sorter, GTK_SORTER_CHANGE_DIFFERENT, self);
     }
-  else
-    {
-      guint n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
-      if (n_items > 1)
-        g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items);
-    }
-
 
   g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTER]);
 }

gtk/gtksor3listmodel.c

@@ -23,7 +23,6 @@
 
 #include "gtkintl.h"
 #include "gtkprivate.h"
-#include "gdk/gdkprofilerprivate.h"
 
 #define GTK_VECTOR_ELEMENT_TYPE GObject *
 #define GTK_VECTOR_TYPE_NAME SortArray
@@ -94,8 +93,6 @@ enum {
   PROP_0,
   PROP_MODEL,
   PROP_SORTER,
-  PROP_SORTING,
-  PROP_INCREMENTAL,
   NUM_PROPERTIES
 };
 
@@ -111,11 +108,6 @@ struct _GtkSor3ListModel
   guint sorting_cb;
   guint sorted_to;
   PivotStack stack;
-
-  gint64 start_time;
-  guint steps;
-
-  gboolean incremental;
 };
 
 struct _GtkSor3ListModelClass
@@ -198,18 +190,6 @@ gtk_sor3_list_model_stop_sorting (GtkSor3ListModel *self)
 {
   g_clear_handle_id (&self->sorting_cb, g_source_remove);
   pivot_stack_set_size (&self->stack, 0);
-
-  if (GDK_PROFILER_IS_RUNNING)
-    {
-      guint n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
-
-      if (self->start_time != 0)
-        gdk_profiler_add_markf (self->start_time, g_get_monotonic_time () - self->start_time, "quicksort", "sorting %u items, %u steps", n_items, self->steps);
-
-      self->start_time = 0;
-    }
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTING]);
 }
 
 static inline int
@@ -219,16 +199,11 @@ compare (GtkSorter *sorter, GObject *a, GObject *b)
 }
 
 static inline void
-swap (SortArray *items, guint i, guint j, guint *changed_start, guint *changed_end)
+swap (SortArray *items, guint i, guint j)
 {
   GObject *tmp = sort_array_get (items, i);
-  g_assert (i < j);
   *sort_array_index (items, i) = sort_array_get (items, j);
   *sort_array_index (items, j) = tmp;
-  if (i < *changed_start)
-    *changed_start = i;
-  if (*changed_end < j)
-    *changed_end = j;
 }
 
 /* This is pretty much the incremental quicksort that is described
@@ -240,7 +215,7 @@ swap (SortArray *items, guint i, guint j, guint *changed_start, guint *changed_e
  * which is the incremental part.
  */
 static guint
-partition (SortArray *items, guint first, guint end, GtkSorter *sorter, guint *changed_start, guint *changed_end)
+partition (SortArray *items, guint first, guint end, GtkSorter *sorter)
 {
   guint mid;
   guint i, j;
@@ -249,13 +224,13 @@ partition (SortArray *items, guint first, guint end, GtkSorter *sorter, guint *c
   mid = first + (end - first) / 2;
   if (compare (sorter, sort_array_get (items, mid),
                        sort_array_get (items, first)) < 0)
-      swap (items, first, mid, changed_start, changed_end);
+      swap (items, mid, first);
   if (compare (sorter, sort_array_get (items, end),
                        sort_array_get (items, first)) < 0)
-      swap (items, first, end, changed_start, changed_end);
+      swap (items, end, first);
   if (compare (sorter, sort_array_get (items, mid),
                        sort_array_get (items, end)) < 0)
-      swap (items, mid, end, changed_start, changed_end);
+      swap (items, mid, end);
 
   pivot = sort_array_get (items, end);
 
@@ -266,14 +241,14 @@ partition (SortArray *items, guint first, guint end, GtkSorter *sorter, guint *c
       while (compare (sorter, sort_array_get (items, i), pivot) < 0) i++;
       while (j > i && compare (sorter, sort_array_get (items, j), pivot) >= 0) j--;
       if (i >= j) return j;
-      swap (items, i, j, changed_start, changed_end);
+      swap (items, i, j);
     }
 
   return j;
 }
 
 static gpointer
-iqs (SortArray *items, guint pos, PivotStack *stack, GtkSorter *sorter, guint *changed_start, guint *changed_end)
+iqs (SortArray *items, guint pos, PivotStack *stack, GtkSorter *sorter)
 {
   guint top;
   guint pivot;
@@ -285,10 +260,10 @@ iqs (SortArray *items, guint pos, PivotStack *stack, GtkSorter *sorter, guint *c
       return sort_array_get (items, pos);
     }
 
-  pivot = partition (items, pos, top, sorter, changed_start, changed_end);
+  pivot = partition (items, pos, top, sorter);
   pivot_stack_push (stack, pivot);
 
-  return iqs (items, pos, stack, sorter, changed_start, changed_end);
+  return iqs (items, pos, stack, sorter);
 }
 
 static gboolean
@@ -299,40 +274,21 @@ gtk_sor3_list_model_sort_cb (gpointer data)
   guint end;
   guint n_items;
   guint i;
-  gint64 begin = g_get_monotonic_time ();
-  guint changed_start;
-  guint changed_end;
-  guint changed_items = 0;
-
-  self->steps++;
 
   start = self->sorted_to;
   n_items = sort_array_get_size (&self->items);
-  end = n_items - start;
-
-  changed_start = G_MAXUINT;
-  changed_end = 0;
+  end = MIN (512, n_items - start);
 
   for (i = 0; i < end; i++)
     {
-      iqs (&self->items, self->sorted_to, &self->stack, self->sorter, &changed_start, &changed_end);
+      iqs (&self->items, self->sorted_to, &self->stack, self->sorter);
       self->sorted_to++;
-
-      if (g_get_monotonic_time () - begin > 1500)
-        break;
     }
 
   if (self->sorted_to >= n_items)
     gtk_sor3_list_model_stop_sorting (self);
 
-   if (changed_start != GTK_INVALID_LIST_POSITION)
-     {
-       changed_items = changed_end - changed_start + 1;
-       g_list_model_items_changed (G_LIST_MODEL (self), changed_start, changed_items, changed_items);
-     }
-
-  if (GDK_PROFILER_IS_RUNNING)
-    gdk_profiler_add_markf (begin, g_get_monotonic_time () - begin, "quicksort", "sort step (%u:%u)", changed_start, changed_items);
+  g_list_model_items_changed (G_LIST_MODEL (self), start, n_items - start, n_items - start);
 
   return G_SOURCE_CONTINUE;
 }
@@ -346,65 +302,18 @@ gtk_sor3_list_model_start_sorting (GtkSor3ListModel *self)
   g_assert (pivot_stack_get_size (&self->stack) == 0);
   g_assert (self->sorting_cb == 0);
 
-  self->start_time = g_get_monotonic_time ();
-  self->steps = 0;
-
   pivot_stack_push (&self->stack, (guint)sort_array_get_size (&self->items) - 1);
   self->sorted_to = 0;
 
   self->sorting_cb = g_idle_add (gtk_sor3_list_model_sort_cb, self);
   g_source_set_name_by_id (self->sorting_cb, "[gtk] gtk_sor3_list_model_sort_cb");
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTING]);
 }
 
-static void
-gtk_sor3_list_model_sort_fully (GtkSor3ListModel *self)
-{
-  guint n_items;
-  guint i;
-  gint64 begin = g_get_monotonic_time ();
-  guint changed_start;
-  guint changed_end;
-  guint changed_items = 0;
-
-  pivot_stack_set_size (&self->stack, 0);
-  pivot_stack_push (&self->stack, (guint)sort_array_get_size (&self->items) - 1);
-  self->sorted_to = 0;
-
-  n_items = sort_array_get_size (&self->items);
-
-  changed_start = G_MAXUINT;
-  changed_end = 0;
-
-  for (i = 0; i < n_items; i++)
-    {
-      iqs (&self->items, self->sorted_to, &self->stack, self->sorter, &changed_start, &changed_end);
-      self->sorted_to++;
-    }
-
-   if (changed_start != GTK_INVALID_LIST_POSITION)
-     {
-       changed_items = changed_end - changed_start + 1;
-       g_list_model_items_changed (G_LIST_MODEL (self), changed_start, changed_items, changed_items);
-     }
-
-  if (GDK_PROFILER_IS_RUNNING)
-    gdk_profiler_add_markf (begin, g_get_monotonic_time () - begin, "quicksort", "sort fully (%u:%u)", changed_start, changed_items);
-}
 static void
 gtk_sor3_list_model_resort (GtkSor3ListModel *self)
 {
-  guint64 begin = g_get_monotonic_time ();
-
   gtk_sor3_list_model_stop_sorting (self);
-  if (self->incremental)
-    gtk_sor3_list_model_start_sorting (self);
-  else
-    gtk_sor3_list_model_sort_fully (self);
-
-  if (GDK_PROFILER_IS_RUNNING)
-    gdk_profiler_add_mark (begin, g_get_monotonic_time () - begin, "resort", NULL);
+  gtk_sor3_list_model_start_sorting (self);
 }
 
 static void
@@ -425,9 +334,6 @@ gtk_sor3_list_model_items_changed_cb (GListModel       *model,
   g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items - added + removed, n_items);
 }
 
-static void gtk_sor3_list_model_set_incremental (GtkSor3ListModel *self,
-                                                 gboolean          incremental);
-
 static void
 gtk_sor3_list_model_set_property (GObject      *object,
                                   guint         prop_id,
@@ -446,10 +352,6 @@ gtk_sor3_list_model_set_property (GObject      *object,
       gtk_sor3_list_model_set_sorter (self, g_value_get_object (value));
       break;
 
-    case PROP_INCREMENTAL:
-      gtk_sor3_list_model_set_incremental (self, g_value_get_boolean (value));
-      break;
-
     default:
       G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
       break;
@@ -474,14 +376,6 @@ gtk_sor3_list_model_get_property (GObject     *object,
       g_value_set_object (value, self->sorter);
       break;
 
-    case PROP_SORTING:
-      g_value_set_boolean (value, self->sorting_cb != 0);
-      break;
-
-    case PROP_INCREMENTAL:
-      g_value_set_boolean (value, self->incremental);
-      break;
-
     default:
       G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
       break;
@@ -574,21 +468,7 @@ gtk_sor3_list_model_class_init (GtkSor3ListModelClass *class)
                            P_("Model"),
                            P_("The model being sorted"),
                            G_TYPE_LIST_MODEL,
-                           GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
-
-  properties[PROP_SORTING] =
-      g_param_spec_boolean ("sorting",
-                           P_("Sorting"),
-                           P_("Whether sorting is currently underway"),
-                           FALSE,
-                           GTK_PARAM_READABLE | G_PARAM_EXPLICIT_NOTIFY);
-
-  properties[PROP_INCREMENTAL] =
-      g_param_spec_boolean ("incremental",
-                           P_("Incremental"),
-                           P_("Whether to sort incrementally"),
-                           FALSE,
-                           GTK_PARAM_READABLE | G_PARAM_EXPLICIT_NOTIFY);
+                           GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY | G_PARAM_EXPLICIT_NOTIFY);
 
   g_object_class_install_properties (gobject_class, NUM_PROPERTIES, properties);
 }
@@ -722,17 +602,3 @@ gtk_sor3_list_model_get_sorter (GtkSor3ListModel *self)
 
   return self->sorter;
 }
-
-static void
-gtk_sor3_list_model_set_incremental (GtkSor3ListModel *self,
-                                     gboolean          incremental)
-{
-  g_return_if_fail (GTK_IS_SOR3_LIST_MODEL (self));
-
-  if (self->incremental == incremental)
-    return;
-
-  self->incremental = incremental;
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_INCREMENTAL]);
-}

gtk/gtksor4listmodel.c

@@ -1,551 +0,0 @@
-/*
- * Copyright © 2018 Benjamin Otte
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library. If not, see <http://www.gnu.org/licenses/>.
- *
- * Authors: Benjamin Otte <otte@gnome.org>
- */
-
-#include "config.h"
-
-#include "gtksor4listmodel.h"
-
-#include "gtkintl.h"
-#include "gtkprivate.h"
-
-typedef struct _SortItem SortItem;
-struct _SortItem
-{
-  GObject *item;
-  guint position;
-};
-
-static void
-sort_item_clear (gpointer data)
-{
-  SortItem *si = data;
-
-  g_clear_object (&si->item);
-}
-
-#define GTK_VECTOR_ELEMENT_TYPE SortItem
-#define GTK_VECTOR_TYPE_NAME SortArray
-#define GTK_VECTOR_NAME sort_array
-#define GTK_VECTOR_FREE_FUNC sort_item_clear
-#define GTK_VECTOR_BY_VALUE 1
-#include "gtkvectorimpl.c"
-
-/**
- * SECTION:gtksor4listmodel
- * @title: GtkSor4ListModel
- * @short_description: A list model that sorts its items
- * @see_also: #GListModel, #GtkSorter
- *
- * #GtkSor4ListModel is a list model that takes a list model and
- * sorts its elements according to a #GtkSorter.
- *
- * #GtkSor4ListModel is a generic model and because of that it
- * cannot take advantage of any external knowledge when sorting.
- * If you run into performance issues with #GtkSor4ListModel, it
- * is strongly recommended that you write your own sorting list
- * model.
- */
-
-enum {
-  PROP_0,
-  PROP_MODEL,
-  PROP_SORTER,
-  NUM_PROPERTIES
-};
-
-struct _GtkSor4ListModel
-{
-  GObject parent_instance;
-
-  GListModel *model;
-  GtkSorter *sorter;
-
-  SortArray items; /* empty if known unsorted */
-};
-
-struct _GtkSor4ListModelClass
-{
-  GObjectClass parent_class;
-};
-
-static GParamSpec *properties[NUM_PROPERTIES] = { NULL, };
-
-static GType
-gtk_sor4_list_model_get_item_type (GListModel *list)
-{
-  return G_TYPE_OBJECT;
-}
-
-static guint
-gtk_sor4_list_model_get_n_items (GListModel *list)
-{
-  GtkSor4ListModel *self = GTK_SOR4_LIST_MODEL (list);
-
-  if (self->model == NULL)
-    return 0;
-
-  return g_list_model_get_n_items (self->model);
-}
-
-static gpointer
-gtk_sor4_list_model_get_item (GListModel *list,
-                              guint       position)
-{
-  GtkSor4ListModel *self = GTK_SOR4_LIST_MODEL (list);
-
-  if (self->model == NULL)
-    return NULL;
-
-  if (sort_array_is_empty (&self->items))
-    return g_list_model_get_item (self->model, position);
-
-  if (position >= sort_array_get_size (&self->items))
-    return NULL;
-
-  return g_object_ref (sort_array_get (&self->items, position)->item);
-}
-
-static void
-gtk_sor4_list_model_model_init (GListModelInterface *iface)
-{
-  iface->get_item_type = gtk_sor4_list_model_get_item_type;
-  iface->get_n_items = gtk_sor4_list_model_get_n_items;
-  iface->get_item = gtk_sor4_list_model_get_item;
-}
-
-G_DEFINE_TYPE_WITH_CODE (GtkSor4ListModel, gtk_sor4_list_model, G_TYPE_OBJECT,
-                         G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_sor4_list_model_model_init))
-
-static void
-gtk_sor4_list_model_clear_items (GtkSor4ListModel *self)
-{
-  sort_array_clear (&self->items);
-} 
-
-static gboolean
-gtk_sor4_list_model_should_sort (GtkSor4ListModel *self)
-{
-  return self->sorter != NULL &&
-         self->model != NULL &&
-         gtk_sorter_get_order (self->sorter) != GTK_SORTER_ORDER_NONE;
-}
-
-static void
-gtk_sor4_list_model_create_items (GtkSor4ListModel *self)
-{
-  guint i, n_items;
-
-  if (!gtk_sor4_list_model_should_sort (self))
-    return;
-
-  n_items = g_list_model_get_n_items (self->model);
-  sort_array_reserve (&self->items, n_items);
-  for (i = 0; i < n_items; i++)
-    {
-      sort_array_append (&self->items, &(SortItem) { g_list_model_get_item (self->model, i), i });
-    }
-}
-
-static int
-sort_func (gconstpointer a,
-           gconstpointer b,
-           gpointer      data)
-{
-  SortItem *sa = (SortItem *) a;
-  SortItem *sb = (SortItem *) b;
-
-  return gtk_sorter_compare (data, sa->item, sb->item);
-}
-
-static void
-gtk_sor4_list_model_resort (GtkSor4ListModel *self)
-{
-  g_qsort_with_data (sort_array_get_data (&self->items),
-                     sort_array_get_size (&self->items),
-                     sizeof (SortItem),
-                     sort_func,
-                     self->sorter);
-}
-
-static void
-gtk_sor4_list_model_remove_items (GtkSor4ListModel *self,
-                                  guint             position,
-                                  guint             removed,
-                                  guint             added,
-                                  guint            *unmodified_start,
-                                  guint            *unmodified_end)
-{
-  guint i, n_items, valid;
-  guint start, end;
-
-  n_items = sort_array_get_size (&self->items);
-  start = n_items;
-  end = n_items;
-  
-  valid = 0;
-  for (i = 0; i < n_items; i++)
-    {
-      SortItem *si = sort_array_index (&self->items, i);
-
-      if (si->position >= position + removed)
-        si->position = si->position - removed + added;
-      else if (si->position >= position)
-        { 
-          start = MIN (start, valid);
-          end = n_items - i - 1;
-          sort_item_clear (si);
-          continue;
-        }
-      if (valid < i)
-        *sort_array_index (&self->items, valid) = *sort_array_index (&self->items, i);
-      valid++;
-    }
-
-  g_assert (valid == n_items - removed);
-  memset (sort_array_index (&self->items, valid), 0, sizeof (SortItem) * removed); 
-  sort_array_set_size (&self->items, valid);
-
-  *unmodified_start = start;
-  *unmodified_end = end;
-}
-
-static void
-gtk_sor4_list_model_items_changed_cb (GListModel       *model,
-                                      guint             position,
-                                      guint             removed,
-                                      guint             added,
-                                      GtkSor4ListModel *self)
-{
-  guint i, n_items, start, end;
-
-  if (removed == 0 && added == 0)
-    return;
-
-  if (!gtk_sor4_list_model_should_sort (self))
-    {
-      g_list_model_items_changed (G_LIST_MODEL (self), position, removed, added);
-      return;
-    }
-
-  gtk_sor4_list_model_remove_items (self, position, removed, added, &start, &end);
-  if (added > 0)
-    {
-      sort_array_reserve (&self->items, sort_array_get_size (&self->items) + added);
-      for (i = position; i < position + added; i++)
-        {
-          sort_array_append (&self->items, &(SortItem) { g_list_model_get_item (self->model, i), i });
-        }
-      gtk_sor4_list_model_resort (self);
-
-      for (i = 0; i < start; i++)
-        {
-          SortItem *si = sort_array_get (&self->items, i);
-          if (si->position >= position && si->position < position + added)
-            {
-              start = i;
-              break;
-            }
-        }
-      n_items = sort_array_get_size (&self->items);
-      for (i = 0; i < end; i++)
-        {
-          SortItem *si = sort_array_get (&self->items, n_items - i - 1);
-          if (si->position >= position && si->position < position + added)
-            {
-              end = i;
-              break;
-            }
-        }
-    }
-
-  n_items = sort_array_get_size (&self->items) - start - end;
-  g_list_model_items_changed (G_LIST_MODEL (self), start, n_items - added + removed, n_items);
-}
-
-static void
-gtk_sor4_list_model_set_property (GObject      *object,
-                                  guint         prop_id,
-                                  const GValue *value,
-                                  GParamSpec   *pspec)
-{
-  GtkSor4ListModel *self = GTK_SOR4_LIST_MODEL (object);
-
-  switch (prop_id)
-    {
-    case PROP_MODEL:
-      gtk_sor4_list_model_set_model (self, g_value_get_object (value));
-      break;
-
-    case PROP_SORTER:
-      gtk_sor4_list_model_set_sorter (self, g_value_get_object (value));
-      break;
-
-    default:
-      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
-      break;
-    }
-}
-
-static void 
-gtk_sor4_list_model_get_property (GObject     *object,
-                                  guint        prop_id,
-                                  GValue      *value,
-                                  GParamSpec  *pspec)
-{
-  GtkSor4ListModel *self = GTK_SOR4_LIST_MODEL (object);
-
-  switch (prop_id)
-    {
-    case PROP_MODEL:
-      g_value_set_object (value, self->model);
-      break;
-
-    case PROP_SORTER:
-      g_value_set_object (value, self->sorter);
-      break;
-
-    default:
-      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
-      break;
-    }
-}
-
-static void
-gtk_sor4_list_model_sorter_changed_cb (GtkSorter        *sorter,
-                                       int               change,
-                                       GtkSor4ListModel *self)
-{
-  guint n_items;
-
-  if (gtk_sorter_get_order (sorter) == GTK_SORTER_ORDER_NONE)
-    gtk_sor4_list_model_clear_items (self);
-  else if (sort_array_is_empty (&self->items))
-    gtk_sor4_list_model_create_items (self);
-
-  gtk_sor4_list_model_resort (self);
-
-  n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
-  if (n_items > 1)
-    g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items);
-}
-
-static void
-gtk_sor4_list_model_clear_model (GtkSor4ListModel *self)
-{
-  if (self->model == NULL)
-    return;
-
-  g_signal_handlers_disconnect_by_func (self->model, gtk_sor4_list_model_items_changed_cb, self);
-  g_clear_object (&self->model);
-  gtk_sor4_list_model_clear_items (self);
-}
-
-static void
-gtk_sor4_list_model_clear_sorter (GtkSor4ListModel *self)
-{
-  if (self->sorter == NULL)
-    return;
-
-  g_signal_handlers_disconnect_by_func (self->sorter, gtk_sor4_list_model_sorter_changed_cb, self);
-  g_clear_object (&self->sorter);
-  gtk_sor4_list_model_clear_items (self);
-}
-
-static void
-gtk_sor4_list_model_dispose (GObject *object)
-{
-  GtkSor4ListModel *self = GTK_SOR4_LIST_MODEL (object);
-
-  gtk_sor4_list_model_clear_model (self);
-  gtk_sor4_list_model_clear_sorter (self);
-
-  G_OBJECT_CLASS (gtk_sor4_list_model_parent_class)->dispose (object);
-};
-
-static void
-gtk_sor4_list_model_class_init (GtkSor4ListModelClass *class)
-{
-  GObjectClass *gobject_class = G_OBJECT_CLASS (class);
-
-  gobject_class->set_property = gtk_sor4_list_model_set_property;
-  gobject_class->get_property = gtk_sor4_list_model_get_property;
-  gobject_class->dispose = gtk_sor4_list_model_dispose;
-
-  /**
-   * GtkSor4ListModel:sorter:
-   *
-   * The sorter for this model
-   */
-  properties[PROP_SORTER] =
-      g_param_spec_object ("sorter",
-                            P_("Sorter"),
-                            P_("The sorter for this model"),
-                            GTK_TYPE_SORTER,
-                            GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
-
-  /**
-   * GtkSor4ListModel:model:
-   *
-   * The model being sorted
-   */
-  properties[PROP_MODEL] =
-      g_param_spec_object ("model",
-                           P_("Model"),
-                           P_("The model being sorted"),
-                           G_TYPE_LIST_MODEL,
-                           GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
-
-  g_object_class_install_properties (gobject_class, NUM_PROPERTIES, properties);
-}
-
-static void
-gtk_sor4_list_model_init (GtkSor4ListModel *self)
-{
-}
-
-/**
- * gtk_sor4_list_model_new:
- * @model: (allow-none): the model to sort
- * @sorter: (allow-none): the #GtkSorter to sort @model with
- *
- * Creates a new sort list model that uses the @sorter to sort @model.
- *
- * Returns: a new #GtkSor4ListModel
- **/
-GtkSor4ListModel *
-gtk_sor4_list_model_new (GListModel *model,
-                         GtkSorter  *sorter)
-{
-  GtkSor4ListModel *result;
-
-  g_return_val_if_fail (model == NULL || G_IS_LIST_MODEL (model), NULL);
-  g_return_val_if_fail (sorter == NULL || GTK_IS_SORTER (sorter), NULL);
-
-  result = g_object_new (GTK_TYPE_SOR4_LIST_MODEL,
-                         "model", model,
-                         "sorter", sorter,
-                         NULL);
-
-  return result;
-}
-
-/**
- * gtk_sor4_list_model_set_model:
- * @self: a #GtkSor4ListModel
- * @model: (allow-none): The model to be sorted
- *
- * Sets the model to be sorted. The @model's item type must conform to
- * the item type of @self.
- **/
-void
-gtk_sor4_list_model_set_model (GtkSor4ListModel *self,
-                               GListModel       *model)
-{
-  guint removed, added;
-
-  g_return_if_fail (GTK_IS_SOR4_LIST_MODEL (self));
-  g_return_if_fail (model == NULL || G_IS_LIST_MODEL (model));
-
-  if (self->model == model)
-    return;
-
-  removed = g_list_model_get_n_items (G_LIST_MODEL (self));
-  gtk_sor4_list_model_clear_model (self);
-
-  if (model)
-    {
-      self->model = g_object_ref (model);
-      g_signal_connect (model, "items-changed", G_CALLBACK (gtk_sor4_list_model_items_changed_cb), self);
-      added = g_list_model_get_n_items (model);
-
-      gtk_sor4_list_model_create_items (self);
-      gtk_sor4_list_model_resort (self);
-    }
-  else
-    added = 0;
-  
-  if (removed > 0 || added > 0)
-    g_list_model_items_changed (G_LIST_MODEL (self), 0, removed, added);
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_MODEL]);
-}
-
-/**
- * gtk_sor4_list_model_get_model:
- * @self: a #GtkSor4ListModel
- *
- * Gets the model currently sorted or %NULL if none.
- *
- * Returns: (nullable) (transfer none): The model that gets sorted
- **/
-GListModel *
-gtk_sor4_list_model_get_model (GtkSor4ListModel *self)
-{
-  g_return_val_if_fail (GTK_IS_SOR4_LIST_MODEL (self), NULL);
-
-  return self->model;
-}
-
-/**
- * gtk_sor4_list_model_set_sorter:
- * @self: a #GtkSor4ListModel
- * @sorter: (allow-none): the #GtkSorter to sort @model with
- *
- * Sets a new sorter on @self.
- */
-void
-gtk_sor4_list_model_set_sorter (GtkSor4ListModel *self,
-                                GtkSorter        *sorter)
-{
-  g_return_if_fail (GTK_IS_SOR4_LIST_MODEL (self));
-  g_return_if_fail (sorter == NULL || GTK_IS_SORTER (sorter));
-
-  gtk_sor4_list_model_clear_sorter (self);
-
-  if (sorter)
-    {
-      self->sorter = g_object_ref (sorter);
-      g_signal_connect (sorter, "changed", G_CALLBACK (gtk_sor4_list_model_sorter_changed_cb), self);
-      gtk_sor4_list_model_sorter_changed_cb (sorter, GTK_SORTER_CHANGE_DIFFERENT, self);
-    }
-  else
-    {
-      guint n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
-      if (n_items > 1)
-        g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items);
-    }
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTER]);
-}
-
-/**
- * gtk_sor4_list_model_get_sorter:
- * @self: a #GtkSor4LisTModel
- *
- * Gets the sorter that is used to sort @self.
- *
- * Returns: (nullable) (transfer none): the sorter of #self
- */
-GtkSorter *
-gtk_sor4_list_model_get_sorter (GtkSor4ListModel *self)
-{
-  g_return_val_if_fail (GTK_IS_SOR4_LIST_MODEL (self), NULL);
-
-  return self->sorter;
-}

gtk/gtksor4listmodel.h

@@ -1,57 +0,0 @@
-/*
- * Copyright © 2018 Benjamin Otte
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library. If not, see <http://www.gnu.org/licenses/>.
- *
- * Authors: Benjamin Otte <otte@gnome.org>
- */
-
-#ifndef __GTK_SOR4_LIST_MODEL_H__
-#define __GTK_SOR4_LIST_MODEL_H__
-
-
-#if !defined (__GTK_H_INSIDE__) && !defined (GTK_COMPILATION)
-#error "Only <gtk/gtk.h> can be included directly."
-#endif
-
-#include <gio/gio.h>
-#include <gtk/gtkwidget.h>
-#include <gtk/gtksorter.h>
-
-
-G_BEGIN_DECLS
-
-#define GTK_TYPE_SOR4_LIST_MODEL (gtk_sor4_list_model_get_type ())
-
-GDK_AVAILABLE_IN_ALL
-G_DECLARE_FINAL_TYPE (GtkSor4ListModel, gtk_sor4_list_model, GTK, SOR4_LIST_MODEL, GObject)
-
-GDK_AVAILABLE_IN_ALL
-GtkSor4ListModel *      gtk_sor4_list_model_new                 (GListModel            *model,
-                                                                 GtkSorter             *sorter);
-GDK_AVAILABLE_IN_ALL
-void                    gtk_sor4_list_model_set_sorter          (GtkSor4ListModel       *self,
-                                                                 GtkSorter              *sorter);
-GDK_AVAILABLE_IN_ALL
-GtkSorter *             gtk_sor4_list_model_get_sorter          (GtkSor4ListModel       *self);
-
-GDK_AVAILABLE_IN_ALL
-void                    gtk_sor4_list_model_set_model           (GtkSor4ListModel       *self,
-                                                                 GListModel             *model);
-GDK_AVAILABLE_IN_ALL
-GListModel *            gtk_sor4_list_model_get_model           (GtkSor4ListModel       *self);
-
-G_END_DECLS
-
-#endif /* __GTK_SOR4_LIST_MODEL_H__ */

gtk/gtksor5listmodel.c

@@ -1,549 +0,0 @@
-/*
- * Copyright © 2018 Benjamin Otte
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library. If not, see <http://www.gnu.org/licenses/>.
- *
- * Authors: Benjamin Otte <otte@gnome.org>
- */
-
-#include "config.h"
-
-#include "gtksor5listmodel.h"
-
-#include "gtkintl.h"
-#include "gtkprivate.h"
-
-#define GTK_VECTOR_ELEMENT_TYPE GObject *
-#define GTK_VECTOR_TYPE_NAME SortArray
-#define GTK_VECTOR_NAME sort_array
-#define GTK_VECTOR_FREE_FUNC g_object_unref
-#define GTK_VECTOR_PREALLOC 16
-#include "gtkvectorimpl.c"
-
-/**
- * SECTION:gtksor5listmodel
- * @title: GtkSor5ListModel
- * @short_description: A list model that sorts its items
- * @see_also: #GListModel, #GtkSorter
- *
- * #GtkSor5ListModel is a list model that takes a list model and
- * sorts its elements according to a #GtkSorter.
- *
- * #GtkSor5ListModel is a generic model and because of that it
- * cannot take advantage of any external knowledge when sorting.
- * If you run into performance issues with #GtkSor5ListModel, it
- * is strongly recommended that you write your own sorting list
- * model.
- */
-
-enum {
-  PROP_0,
-  PROP_MODEL,
-  PROP_SORTER,
-  NUM_PROPERTIES
-};
-
-struct _GtkSor5ListModel
-{
-  GObject parent_instance;
-
-  GListModel *model;
-  GtkSorter *sorter;
-
-  SortArray items; /* empty if known unsorted */
-
-  guint sorting_cb;
-  guint size;
-  guint start;
-};
-
-struct _GtkSor5ListModelClass
-{
-  GObjectClass parent_class;
-};
-
-static GParamSpec *properties[NUM_PROPERTIES] = { NULL, };
-
-static GType
-gtk_sor5_list_model_get_item_type (GListModel *list)
-{
-  return G_TYPE_OBJECT;
-}
-
-static guint
-gtk_sor5_list_model_get_n_items (GListModel *list)
-{
-  GtkSor5ListModel *self = GTK_SOR5_LIST_MODEL (list);
-
-  if (self->model == NULL)
-    return 0;
-
-  return g_list_model_get_n_items (self->model);
-}
-
-static gpointer
-gtk_sor5_list_model_get_item (GListModel *list,
-                              guint       position)
-{
-  GtkSor5ListModel *self = GTK_SOR5_LIST_MODEL (list);
-
-  if (self->model == NULL)
-    return NULL;
-
-  if (sort_array_is_empty (&self->items))
-    return g_list_model_get_item (self->model, position);
-
-  if (position >= sort_array_get_size (&self->items))
-    return NULL;
-
-  return g_object_ref (sort_array_get (&self->items, position));
-}
-
-static void
-gtk_sor5_list_model_model_init (GListModelInterface *iface)
-{
-  iface->get_item_type = gtk_sor5_list_model_get_item_type;
-  iface->get_n_items = gtk_sor5_list_model_get_n_items;
-  iface->get_item = gtk_sor5_list_model_get_item;
-}
-
-G_DEFINE_TYPE_WITH_CODE (GtkSor5ListModel, gtk_sor5_list_model, G_TYPE_OBJECT,
-                         G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_sor5_list_model_model_init))
-
-static void
-gtk_sor5_list_model_clear_items (GtkSor5ListModel *self)
-{
-  sort_array_clear (&self->items);
-}
-
-static void
-gtk_sor5_list_model_create_items (GtkSor5ListModel *self)
-{
-  guint i, n_items;
-
-  if (self->sorter == NULL ||
-      self->model == NULL ||
-      gtk_sorter_get_order (self->sorter) == GTK_SORTER_ORDER_NONE)
-    return;
-
-  n_items = g_list_model_get_n_items (self->model);
-  sort_array_reserve (&self->items, n_items);
-  for (i = 0; i < n_items; i++)
-    sort_array_append (&self->items, g_list_model_get_item (self->model, i));
-}
-
-static void
-gtk_sor5_list_model_stop_sorting (GtkSor5ListModel *self)
-{
-  g_clear_handle_id (&self->sorting_cb, g_source_remove);
-}
-
-static guint
-merge (SortArray *items,
-       guint      start,
-       guint      mid,
-       guint      end,
-       GtkSorter *sorter)
-{
-  int start2 = mid + 1;
-  int c = 0;
-
-  if (mid == end)
-    return 0;
-
-  if (gtk_sorter_compare (sorter,
-                          sort_array_get (items, mid),
-                          sort_array_get (items, start2)) <= 0)
-    return 1;
-
-  while (start <= mid && start2 <= end)
-    {
-      c++;
-      if (gtk_sorter_compare (sorter,
-                              sort_array_get (items, start),
-                              sort_array_get (items, start2)) <= 0)
-        start++;
-      else
-        {
-          GObject *value = sort_array_get (items, start2);
-          int index = start2;
-
-          while (index != start)
-            {
-              c++;
-              *sort_array_index (items, index) = sort_array_get (items, index - 1);
-              index--;
-            }
-
-          c++;
-          *sort_array_index (items, start) = value;
-
-          start++;
-          mid++;
-          start2++;
-        }
-    }
-
-  return c;
-}
-
-static gboolean
-gtk_sor5_list_model_sort_cb (gpointer data)
-{
-  GtkSor5ListModel *self = GTK_SOR5_LIST_MODEL (data);
-  guint n_items = sort_array_get_size (&self->items);
-  guint i;
-  guint s, e;
-
-  s = self->start;
-  e = self->start;
-
-  i = 0;
-  while (i < 10000)
-    {
-      guint mid = MIN (self->start + self->size - 1, n_items - 1);
-      guint end = MIN (self->start + 2 * self->size - 1, n_items - 1);
-
-      i += merge (&self->items, self->start, mid, end, self->sorter);
-
-      s = MIN (s, self->start);
-      e = MAX (e, end);
-
-      self->start += 2 * self->size;
-      if (self->start >= n_items - 1)
-        {
-          self->start = 0;
-          self->size *= 2;
-          if (self->size >= n_items)
-            {
-              gtk_sor5_list_model_stop_sorting (self);
-              break;
-            }
-        }
-    }
-
-  //g_print ("items changed %u:%u\n", s, e - s + 1);
-  g_list_model_items_changed (G_LIST_MODEL (self), s, e - s + 1, e - s + 1);
-
-  return G_SOURCE_CONTINUE;
-}
-
-static void
-gtk_sor5_list_model_start_sorting (GtkSor5ListModel *self)
-{
-  if (sort_array_get_size (&self->items) == 0)
-    return;
-
-  g_assert (self->sorting_cb == 0);
-
-  self->size = 1;
-  self->start = 0;
-
-  self->sorting_cb = g_idle_add (gtk_sor5_list_model_sort_cb, self);
-  g_source_set_name_by_id (self->sorting_cb, "[gtk] gtk_sor5_list_model_sort_cb");
-}
-
-static void
-gtk_sor5_list_model_resort (GtkSor5ListModel *self)
-{
-  gtk_sor5_list_model_stop_sorting (self);
-  gtk_sor5_list_model_start_sorting (self);
-}
-
-static void
-gtk_sor5_list_model_items_changed_cb (GListModel       *model,
-                                      guint             position,
-                                      guint             removed,
-                                      guint             added,
-                                      GtkSor5ListModel *self)
-{
-  guint n_items;
-
-  /* doesn't free() the array */
-  sort_array_set_size (&self->items, 0);
-  gtk_sor5_list_model_create_items (self);
-  gtk_sor5_list_model_resort (self);
-
-  n_items = g_list_model_get_n_items (model);
-  g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items - added + removed, n_items);
-}
-
-static void
-gtk_sor5_list_model_set_property (GObject      *object,
-                                  guint         prop_id,
-                                  const GValue *value,
-                                  GParamSpec   *pspec)
-{
-  GtkSor5ListModel *self = GTK_SOR5_LIST_MODEL (object);
-
-  switch (prop_id)
-    {
-    case PROP_MODEL:
-      gtk_sor5_list_model_set_model (self, g_value_get_object (value));
-      break;
-
-    case PROP_SORTER:
-      gtk_sor5_list_model_set_sorter (self, g_value_get_object (value));
-      break;
-
-    default:
-      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
-      break;
-    }
-}
-
-static void
-gtk_sor5_list_model_get_property (GObject     *object,
-                                  guint        prop_id,
-                                  GValue      *value,
-                                  GParamSpec  *pspec)
-{
-  GtkSor5ListModel *self = GTK_SOR5_LIST_MODEL (object);
-
-  switch (prop_id)
-    {
-    case PROP_MODEL:
-      g_value_set_object (value, self->model);
-      break;
-
-    case PROP_SORTER:
-      g_value_set_object (value, self->sorter);
-      break;
-
-    default:
-      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
-      break;
-    }
-}
-
-static void
-gtk_sor5_list_model_sorter_changed_cb (GtkSorter        *sorter,
-                                       int               change,
-                                       GtkSor5ListModel *self)
-{
-  guint n_items;
-
-  if (gtk_sorter_get_order (sorter) == GTK_SORTER_ORDER_NONE)
-    gtk_sor5_list_model_clear_items (self);
-  else if (sort_array_is_empty (&self->items))
-    gtk_sor5_list_model_create_items (self);
-
-  gtk_sor5_list_model_resort (self);
-
-  n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
-  if (n_items > 1)
-    g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items);
-}
-
-static void
-gtk_sor5_list_model_clear_model (GtkSor5ListModel *self)
-{
-  if (self->model == NULL)
-    return;
-
-  g_signal_handlers_disconnect_by_func (self->model, gtk_sor5_list_model_items_changed_cb, self);
-  g_clear_object (&self->model);
-  gtk_sor5_list_model_stop_sorting (self);
-  gtk_sor5_list_model_clear_items (self);
-}
-
-static void
-gtk_sor5_list_model_clear_sorter (GtkSor5ListModel *self)
-{
-  if (self->sorter == NULL)
-    return;
-
-  g_signal_handlers_disconnect_by_func (self->sorter, gtk_sor5_list_model_sorter_changed_cb, self);
-  g_clear_object (&self->sorter);
-  gtk_sor5_list_model_stop_sorting (self);
-  gtk_sor5_list_model_clear_items (self);
-}
-
-static void
-gtk_sor5_list_model_dispose (GObject *object)
-{
-  GtkSor5ListModel *self = GTK_SOR5_LIST_MODEL (object);
-
-  gtk_sor5_list_model_stop_sorting (self);
-  gtk_sor5_list_model_clear_model (self);
-  gtk_sor5_list_model_clear_sorter (self);
-
-  G_OBJECT_CLASS (gtk_sor5_list_model_parent_class)->dispose (object);
-};
-
-static void
-gtk_sor5_list_model_class_init (GtkSor5ListModelClass *class)
-{
-  GObjectClass *gobject_class = G_OBJECT_CLASS (class);
-
-  gobject_class->set_property = gtk_sor5_list_model_set_property;
-  gobject_class->get_property = gtk_sor5_list_model_get_property;
-  gobject_class->dispose = gtk_sor5_list_model_dispose;
-
-  /**
-   * GtkSor5ListModel:sorter:
-   *
-   * The sorter for this model
-   */
-  properties[PROP_SORTER] =
-      g_param_spec_object ("sorter",
-                            P_("Sorter"),
-                            P_("The sorter for this model"),
-                            GTK_TYPE_SORTER,
-                            GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
-
-  /**
-   * GtkSor5ListModel:model:
-   *
-   * The model being sorted
-   */
-  properties[PROP_MODEL] =
-      g_param_spec_object ("model",
-                           P_("Model"),
-                           P_("The model being sorted"),
-                           G_TYPE_LIST_MODEL,
-                           GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
-
-  g_object_class_install_properties (gobject_class, NUM_PROPERTIES, properties);
-}
-
-static void
-gtk_sor5_list_model_init (GtkSor5ListModel *self)
-{
-}
-
-/**
- * gtk_sor5_list_model_new:
- * @model: (allow-none): the model to sort
- * @sorter: (allow-none): the #GtkSorter to sort @model with
- *
- * Creates a new sort list model that uses the @sorter to sort @model.
- *
- * Returns: a new #GtkSor5ListModel
- **/
-GtkSor5ListModel *
-gtk_sor5_list_model_new (GListModel *model,
-                         GtkSorter  *sorter)
-{
-  GtkSor5ListModel *result;
-
-  g_return_val_if_fail (model == NULL || G_IS_LIST_MODEL (model), NULL);
-  g_return_val_if_fail (sorter == NULL || GTK_IS_SORTER (sorter), NULL);
-
-  result = g_object_new (GTK_TYPE_SOR5_LIST_MODEL,
-                         "model", model,
-                         "sorter", sorter,
-                         NULL);
-
-  return result;
-}
-
-/**
- * gtk_sor5_list_model_set_model:
- * @self: a #GtkSor5ListModel
- * @model: (allow-none): The model to be sorted
- *
- * Sets the model to be sorted. The @model's item type must conform to
- * the item type of @self.
- **/
-void
-gtk_sor5_list_model_set_model (GtkSor5ListModel *self,
-                               GListModel       *model)
-{
-  guint removed, added;
-
-  g_return_if_fail (GTK_IS_SOR5_LIST_MODEL (self));
-  g_return_if_fail (model == NULL || G_IS_LIST_MODEL (model));
-
-  if (self->model == model)
-    return;
-
-  removed = g_list_model_get_n_items (G_LIST_MODEL (self));
-  gtk_sor5_list_model_clear_model (self);
-
-  if (model)
-    {
-      self->model = g_object_ref (model);
-      g_signal_connect (model, "items-changed", G_CALLBACK (gtk_sor5_list_model_items_changed_cb), self);
-      added = g_list_model_get_n_items (model);
-
-      gtk_sor5_list_model_create_items (self);
-      gtk_sor5_list_model_resort (self);
-    }
-  else
-    added = 0;
-  
-  if (removed > 0 || added > 0)
-    g_list_model_items_changed (G_LIST_MODEL (self), 0, removed, added);
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_MODEL]);
-}
-
-/**
- * gtk_sor5_list_model_get_model:
- * @self: a #GtkSor5ListModel
- *
- * Gets the model currently sorted or %NULL if none.
- *
- * Returns: (nullable) (transfer none): The model that gets sorted
- **/
-GListModel *
-gtk_sor5_list_model_get_model (GtkSor5ListModel *self)
-{
-  g_return_val_if_fail (GTK_IS_SOR5_LIST_MODEL (self), NULL);
-
-  return self->model;
-}
-
-/**
- * gtk_sor5_list_model_set_sorter:
- * @self: a #GtkSor5ListModel
- * @sorter: (allow-none): the #GtkSorter to sort @model with
- *
- * Sets a new sorter on @self.
- */
-void
-gtk_sor5_list_model_set_sorter (GtkSor5ListModel *self,
-                                GtkSorter        *sorter)
-{
-  g_return_if_fail (GTK_IS_SOR5_LIST_MODEL (self));
-  g_return_if_fail (sorter == NULL || GTK_IS_SORTER (sorter));
-
-  gtk_sor5_list_model_clear_sorter (self);
-
-  if (sorter)
-    {
-      self->sorter = g_object_ref (sorter);
-      g_signal_connect (sorter, "changed", G_CALLBACK (gtk_sor5_list_model_sorter_changed_cb), self);
-      gtk_sor5_list_model_sorter_changed_cb (sorter, GTK_SORTER_CHANGE_DIFFERENT, self);
-    }
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTER]);
-}
-
-/**
- * gtk_sor5_list_model_get_sorter:
- * @self: a #GtkSor5LisTModel
- *
- * Gets the sorter that is used to sort @self.
- *
- * Returns: (nullable) (transfer none): the sorter of #self
- */
-GtkSorter *
-gtk_sor5_list_model_get_sorter (GtkSor5ListModel *self)
-{
-  g_return_val_if_fail (GTK_IS_SOR5_LIST_MODEL (self), NULL);
-
-  return self->sorter;
-}

gtk/gtksor5listmodel.h

@@ -1,57 +0,0 @@
-/*
- * Copyright © 2018 Benjamin Otte
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library. If not, see <http://www.gnu.org/licenses/>.
- *
- * Authors: Benjamin Otte <otte@gnome.org>
- */
-
-#ifndef __GTK_SOR5_LIST_MODEL_H__
-#define __GTK_SOR5_LIST_MODEL_H__
-
-
-#if !defined (__GTK_H_INSIDE__) && !defined (GTK_COMPILATION)
-#error "Only <gtk/gtk.h> can be included directly."
-#endif
-
-#include <gio/gio.h>
-#include <gtk/gtkwidget.h>
-#include <gtk/gtksorter.h>
-
-
-G_BEGIN_DECLS
-
-#define GTK_TYPE_SOR5_LIST_MODEL (gtk_sor5_list_model_get_type ())
-
-GDK_AVAILABLE_IN_ALL
-G_DECLARE_FINAL_TYPE (GtkSor5ListModel, gtk_sor5_list_model, GTK, SOR5_LIST_MODEL, GObject)
-
-GDK_AVAILABLE_IN_ALL
-GtkSor5ListModel *      gtk_sor5_list_model_new                 (GListModel            *model,
-                                                                 GtkSorter             *sorter);
-GDK_AVAILABLE_IN_ALL
-void                    gtk_sor5_list_model_set_sorter          (GtkSor5ListModel       *self,
-                                                                 GtkSorter              *sorter);
-GDK_AVAILABLE_IN_ALL
-GtkSorter *             gtk_sor5_list_model_get_sorter          (GtkSor5ListModel       *self);
-
-GDK_AVAILABLE_IN_ALL
-void                    gtk_sor5_list_model_set_model           (GtkSor5ListModel       *self,
-                                                                 GListModel             *model);
-GDK_AVAILABLE_IN_ALL
-GListModel *            gtk_sor5_list_model_get_model           (GtkSor5ListModel       *self);
-
-G_END_DECLS
-
-#endif /* __GTK_SOR5_LIST_MODEL_H__ */

gtk/gtksortlistmodel.c

@@ -403,7 +403,7 @@ gtk_sort_list_model_class_init (GtkSortListModelClass *class)
                            P_("Model"),
                            P_("The model being sorted"),
                            G_TYPE_LIST_MODEL,
-                           GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
+                           GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY | G_PARAM_EXPLICIT_NOTIFY);
 
   g_object_class_install_properties (gobject_class, NUM_PROPERTIES, properties);
 }

gtk/gtkstringlist.c

@@ -57,12 +57,6 @@
 
  */
 
-#define GTK_VECTOR_ELEMENT_TYPE GtkStringObject *
-#define GTK_VECTOR_NAME objects
-#define GTK_VECTOR_TYPE_NAME Objects
-#define GTK_VECTOR_FREE_FUNC g_object_unref
-#include "gtkvectorimpl.c"
-
 struct _GtkStringObject
 {
   GObject parent_instance;
@@ -196,7 +190,7 @@ struct _GtkStringList
 {
   GObject parent_instance;
 
-  Objects items;
+  GSequence *items;
 };
 
 struct _GtkStringListClass
@@ -215,7 +209,7 @@ gtk_string_list_get_n_items (GListModel *list)
 {
   GtkStringList *self = GTK_STRING_LIST (list);
 
-  return objects_get_size (&self->items);
+  return g_sequence_get_length (self->items);
 }
 
 static gpointer
@@ -223,11 +217,14 @@ gtk_string_list_get_item (GListModel *list,
                           guint       position)
 {
   GtkStringList *self = GTK_STRING_LIST (list);
+  GSequenceIter *iter;
 
-  if (position >= objects_get_size (&self->items))
+  iter = g_sequence_get_iter_at_pos (self->items, position);
+
+  if (g_sequence_iter_is_end (iter))
     return NULL;
-
-  return g_object_ref (objects_get (&self->items, position));
+  else
+    return g_object_ref (g_sequence_get (iter));
 }
 
 static void
@@ -334,7 +331,7 @@ item_end_element (GtkBuildableParseContext  *context,
           g_string_assign (data->string, translated);
         }
 
-      gtk_string_list_append (data->list, data->string->str);
+      g_sequence_append (data->list->items, gtk_string_object_new (data->string->str));
     }
 
   data->translatable = FALSE;
@@ -414,7 +411,7 @@ gtk_string_list_dispose (GObject *object)
 {
   GtkStringList *self = GTK_STRING_LIST (object);
 
-  objects_clear (&self->items);
+  g_clear_pointer (&self->items, g_sequence_free);
 
   G_OBJECT_CLASS (gtk_string_list_parent_class)->dispose (object);
 }
@@ -430,7 +427,7 @@ gtk_string_list_class_init (GtkStringListClass *class)
 static void
 gtk_string_list_init (GtkStringList *self)
 {
-  objects_init (&self->items);
+  self->items = g_sequence_new (g_object_unref);
 }
 
 /**
@@ -479,19 +476,32 @@ gtk_string_list_splice (GtkStringList      *self,
                         guint               n_removals,
                         const char * const *additions)
 {
-  guint add;
+  GSequenceIter *it;
+  guint add, n_items;
 
   g_return_if_fail (GTK_IS_STRING_LIST (self));
   g_return_if_fail (position + n_removals >= position); /* overflow */
-  g_return_if_fail (position + n_removals <= objects_get_size (&self->items));
 
-  objects_splice (&self->items, position, n_removals, NULL, 0);
+  n_items = g_sequence_get_length (self->items);
+  g_return_if_fail (position + n_removals <= n_items);
+
+  it = g_sequence_get_iter_at_pos (self->items, position);
+
+  if (n_removals)
+    {
+      GSequenceIter *end;
+
+      end = g_sequence_iter_move (it, n_removals);
+      g_sequence_remove_range (it, end);
+
+      it = end;
+    }
 
   if (additions)
     {
       for (add = 0; additions[add]; add++)
         {
-          objects_append (&self->items, gtk_string_object_new (additions[add]));
+          g_sequence_insert_before (it, gtk_string_object_new (additions[add]));
         }
     }
   else
@@ -515,11 +525,14 @@ void
 gtk_string_list_append (GtkStringList *self,
                         const char    *string)
 {
+  guint n_items;
+
   g_return_if_fail (GTK_IS_STRING_LIST (self));
 
-  objects_append (&self->items, gtk_string_object_new (string));
+  n_items = g_sequence_get_length (self->items);
+  g_sequence_append (self->items, gtk_string_object_new (string));
 
-  g_list_model_items_changed (G_LIST_MODEL (self), objects_get_size (&self->items) - 1, 0, 1);
+  g_list_model_items_changed (G_LIST_MODEL (self), n_items, 0, 1);
 }
 
 /**
@@ -541,11 +554,14 @@ void
 gtk_string_list_take (GtkStringList *self,
                       char          *string)
 {
+  guint n_items;
+
   g_return_if_fail (GTK_IS_STRING_LIST (self));
 
-  objects_append (&self->items, gtk_string_object_new_take (string));
+  n_items = g_sequence_get_length (self->items);
+  g_sequence_append (self->items, gtk_string_object_new_take (string));
 
-  g_list_model_items_changed (G_LIST_MODEL (self), objects_get_size (&self->items) - 1, 0, 1);
+  g_list_model_items_changed (G_LIST_MODEL (self), n_items, 0, 1);
 }
 
 /**
@@ -560,9 +576,16 @@ void
 gtk_string_list_remove (GtkStringList *self,
                         guint          position)
 {
+  GSequenceIter *iter;
+
   g_return_if_fail (GTK_IS_STRING_LIST (self));
 
-  gtk_string_list_splice (self, position, 1, NULL);
+  iter = g_sequence_get_iter_at_pos (self->items, position);
+  g_return_if_fail (!g_sequence_iter_is_end (iter));
+
+  g_sequence_remove (iter);
+
+  g_list_model_items_changed (G_LIST_MODEL (self), position, 1, 0);
 }
 
 /**
@@ -582,10 +605,20 @@ const char *
 gtk_string_list_get_string (GtkStringList *self,
                             guint          position)
 {
+  GSequenceIter *iter;
+
   g_return_val_if_fail (GTK_IS_STRING_LIST (self), NULL);
 
-  if (position >= objects_get_size (&self->items))
-    return NULL;
+  iter = g_sequence_get_iter_at_pos (self->items, position);
 
-  return objects_get (&self->items, position)->string;
+  if (g_sequence_iter_is_end (iter))
+    {
+      return NULL;
+    }
+  else
+    {
+      GtkStringObject *obj = g_sequence_get (iter);
+
+      return obj->string;
+    }
 }

gtk/gtktim1sortmodel.c

@@ -1,561 +0,0 @@
-/*
- * Copyright © 2018 Benjamin Otte
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library. If not, see <http://www.gnu.org/licenses/>.
- *
- * Authors: Benjamin Otte <otte@gnome.org>
- */
-
-#include "config.h"
-
-#include "gtktim1sortmodel.h"
-
-#include "gtkintl.h"
-#include "gtkprivate.h"
-#include "gtktimsortprivate.h"
-
-typedef struct _SortItem SortItem;
-struct _SortItem
-{
-  GObject *item;
-  guint position;
-};
-
-static void
-sort_item_clear (gpointer data)
-{
-  SortItem *si = data;
-
-  g_clear_object (&si->item);
-}
-
-#define GTK_VECTOR_ELEMENT_TYPE SortItem
-#define GTK_VECTOR_TYPE_NAME SortArray
-#define GTK_VECTOR_NAME sort_array
-#define GTK_VECTOR_FREE_FUNC sort_item_clear
-#define GTK_VECTOR_BY_VALUE 1
-#include "gtkvectorimpl.c"
-
-/**
- * SECTION:gtksor4listmodel
- * @title: GtkTim1SortModel
- * @short_description: A list model that sorts its items
- * @see_also: #GListModel, #GtkSorter
- *
- * #GtkTim1SortModel is a list model that takes a list model and
- * sorts its elements according to a #GtkSorter.
- *
- * #GtkTim1SortModel is a generic model and because of that it
- * cannot take advantage of any external knowledge when sorting.
- * If you run into performance issues with #GtkTim1SortModel, it
- * is strongly recommended that you write your own sorting list
- * model.
- */
-
-enum {
-  PROP_0,
-  PROP_MODEL,
-  PROP_SORTER,
-  NUM_PROPERTIES
-};
-
-struct _GtkTim1SortModel
-{
-  GObject parent_instance;
-
-  GListModel *model;
-  GtkSorter *sorter;
-
-  SortArray items; /* empty if known unsorted */
-};
-
-struct _GtkTim1SortModelClass
-{
-  GObjectClass parent_class;
-};
-
-static GParamSpec *properties[NUM_PROPERTIES] = { NULL, };
-
-static GType
-gtk_tim1_sort_model_get_item_type (GListModel *list)
-{
-  return G_TYPE_OBJECT;
-}
-
-static guint
-gtk_tim1_sort_model_get_n_items (GListModel *list)
-{
-  GtkTim1SortModel *self = GTK_TIM1_SORT_MODEL (list);
-
-  if (self->model == NULL)
-    return 0;
-
-  return g_list_model_get_n_items (self->model);
-}
-
-static gpointer
-gtk_tim1_sort_model_get_item (GListModel *list,
-                              guint       position)
-{
-  GtkTim1SortModel *self = GTK_TIM1_SORT_MODEL (list);
-
-  if (self->model == NULL)
-    return NULL;
-
-  if (sort_array_is_empty (&self->items))
-    return g_list_model_get_item (self->model, position);
-
-  if (position >= sort_array_get_size (&self->items))
-    return NULL;
-
-  return g_object_ref (sort_array_get (&self->items, position)->item);
-}
-
-static void
-gtk_tim1_sort_model_model_init (GListModelInterface *iface)
-{
-  iface->get_item_type = gtk_tim1_sort_model_get_item_type;
-  iface->get_n_items = gtk_tim1_sort_model_get_n_items;
-  iface->get_item = gtk_tim1_sort_model_get_item;
-}
-
-G_DEFINE_TYPE_WITH_CODE (GtkTim1SortModel, gtk_tim1_sort_model, G_TYPE_OBJECT,
-                         G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_tim1_sort_model_model_init))
-
-static void
-gtk_tim1_sort_model_clear_items (GtkTim1SortModel *self)
-{
-  sort_array_clear (&self->items);
-} 
-
-static gboolean
-gtk_tim1_sort_model_should_sort (GtkTim1SortModel *self)
-{
-  return self->sorter != NULL &&
-         self->model != NULL &&
-         gtk_sorter_get_order (self->sorter) != GTK_SORTER_ORDER_NONE;
-}
-
-static void
-gtk_tim1_sort_model_create_items (GtkTim1SortModel *self)
-{
-  guint i, n_items;
-
-  if (!gtk_tim1_sort_model_should_sort (self))
-    return;
-
-  n_items = g_list_model_get_n_items (self->model);
-  sort_array_reserve (&self->items, n_items);
-  for (i = 0; i < n_items; i++)
-    {
-      sort_array_append (&self->items, &(SortItem) { g_list_model_get_item (self->model, i), i });
-    }
-}
-
-static int
-sort_func (gconstpointer a,
-           gconstpointer b,
-           gpointer      data)
-{
-  SortItem *sa = (SortItem *) a;
-  SortItem *sb = (SortItem *) b;
-
-  return gtk_sorter_compare (data, sa->item, sb->item);
-}
-
-static void
-gtk_tim1_sort_model_resort (GtkTim1SortModel *self,
-                            guint             already_sorted)
-{
-  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
-gtk_tim1_sort_model_remove_items (GtkTim1SortModel *self,
-                                  guint             position,
-                                  guint             removed,
-                                  guint             added,
-                                  guint            *unmodified_start,
-                                  guint            *unmodified_end)
-{
-  guint i, n_items, valid;
-  guint start, end;
-
-  n_items = sort_array_get_size (&self->items);
-  start = n_items;
-  end = n_items;
-  
-  valid = 0;
-  for (i = 0; i < n_items; i++)
-    {
-      SortItem *si = sort_array_index (&self->items, i);
-
-      if (si->position >= position + removed)
-        si->position = si->position - removed + added;
-      else if (si->position >= position)
-        { 
-          start = MIN (start, valid);
-          end = n_items - i - 1;
-          sort_item_clear (si);
-          continue;
-        }
-      if (valid < i)
-        *sort_array_index (&self->items, valid) = *sort_array_index (&self->items, i);
-      valid++;
-    }
-
-  g_assert (valid == n_items - removed);
-  memset (sort_array_index (&self->items, valid), 0, sizeof (SortItem) * removed); 
-  sort_array_set_size (&self->items, valid);
-
-  *unmodified_start = start;
-  *unmodified_end = end;
-}
-
-static void
-gtk_tim1_sort_model_items_changed_cb (GListModel       *model,
-                                      guint             position,
-                                      guint             removed,
-                                      guint             added,
-                                      GtkTim1SortModel *self)
-{
-  guint i, n_items, start, end;
-
-  if (removed == 0 && added == 0)
-    return;
-
-  if (!gtk_tim1_sort_model_should_sort (self))
-    {
-      g_list_model_items_changed (G_LIST_MODEL (self), position, removed, added);
-      return;
-    }
-
-  gtk_tim1_sort_model_remove_items (self, position, removed, added, &start, &end);
-  if (added > 0)
-    {
-      sort_array_reserve (&self->items, sort_array_get_size (&self->items) + added);
-      for (i = position; i < position + added; i++)
-        {
-          sort_array_append (&self->items, &(SortItem) { g_list_model_get_item (self->model, i), i });
-        }
-      gtk_tim1_sort_model_resort (self, sort_array_get_size (&self->items) - added);
-
-      for (i = 0; i < start; i++)
-        {
-          SortItem *si = sort_array_get (&self->items, i);
-          if (si->position >= position && si->position < position + added)
-            {
-              start = i;
-              break;
-            }
-        }
-      n_items = sort_array_get_size (&self->items);
-      for (i = 0; i < end; i++)
-        {
-          SortItem *si = sort_array_get (&self->items, n_items - i - 1);
-          if (si->position >= position && si->position < position + added)
-            {
-              end = i;
-              break;
-            }
-        }
-    }
-
-  n_items = sort_array_get_size (&self->items) - start - end;
-  g_list_model_items_changed (G_LIST_MODEL (self), start, n_items - added + removed, n_items);
-}
-
-static void
-gtk_tim1_sort_model_set_property (GObject      *object,
-                                  guint         prop_id,
-                                  const GValue *value,
-                                  GParamSpec   *pspec)
-{
-  GtkTim1SortModel *self = GTK_TIM1_SORT_MODEL (object);
-
-  switch (prop_id)
-    {
-    case PROP_MODEL:
-      gtk_tim1_sort_model_set_model (self, g_value_get_object (value));
-      break;
-
-    case PROP_SORTER:
-      gtk_tim1_sort_model_set_sorter (self, g_value_get_object (value));
-      break;
-
-    default:
-      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
-      break;
-    }
-}
-
-static void 
-gtk_tim1_sort_model_get_property (GObject     *object,
-                                  guint        prop_id,
-                                  GValue      *value,
-                                  GParamSpec  *pspec)
-{
-  GtkTim1SortModel *self = GTK_TIM1_SORT_MODEL (object);
-
-  switch (prop_id)
-    {
-    case PROP_MODEL:
-      g_value_set_object (value, self->model);
-      break;
-
-    case PROP_SORTER:
-      g_value_set_object (value, self->sorter);
-      break;
-
-    default:
-      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
-      break;
-    }
-}
-
-static void
-gtk_tim1_sort_model_sorter_changed_cb (GtkSorter        *sorter,
-                                       int               change,
-                                       GtkTim1SortModel *self)
-{
-  guint n_items;
-
-  if (gtk_sorter_get_order (sorter) == GTK_SORTER_ORDER_NONE)
-    gtk_tim1_sort_model_clear_items (self);
-  else if (sort_array_is_empty (&self->items))
-    gtk_tim1_sort_model_create_items (self);
-
-  gtk_tim1_sort_model_resort (self, 0);
-
-  n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
-  if (n_items > 1)
-    g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items);
-}
-
-static void
-gtk_tim1_sort_model_clear_model (GtkTim1SortModel *self)
-{
-  if (self->model == NULL)
-    return;
-
-  g_signal_handlers_disconnect_by_func (self->model, gtk_tim1_sort_model_items_changed_cb, self);
-  g_clear_object (&self->model);
-  gtk_tim1_sort_model_clear_items (self);
-}
-
-static void
-gtk_tim1_sort_model_clear_sorter (GtkTim1SortModel *self)
-{
-  if (self->sorter == NULL)
-    return;
-
-  g_signal_handlers_disconnect_by_func (self->sorter, gtk_tim1_sort_model_sorter_changed_cb, self);
-  g_clear_object (&self->sorter);
-  gtk_tim1_sort_model_clear_items (self);
-}
-
-static void
-gtk_tim1_sort_model_dispose (GObject *object)
-{
-  GtkTim1SortModel *self = GTK_TIM1_SORT_MODEL (object);
-
-  gtk_tim1_sort_model_clear_model (self);
-  gtk_tim1_sort_model_clear_sorter (self);
-
-  G_OBJECT_CLASS (gtk_tim1_sort_model_parent_class)->dispose (object);
-};
-
-static void
-gtk_tim1_sort_model_class_init (GtkTim1SortModelClass *class)
-{
-  GObjectClass *gobject_class = G_OBJECT_CLASS (class);
-
-  gobject_class->set_property = gtk_tim1_sort_model_set_property;
-  gobject_class->get_property = gtk_tim1_sort_model_get_property;
-  gobject_class->dispose = gtk_tim1_sort_model_dispose;
-
-  /**
-   * GtkTim1SortModel:sorter:
-   *
-   * The sorter for this model
-   */
-  properties[PROP_SORTER] =
-      g_param_spec_object ("sorter",
-                            P_("Sorter"),
-                            P_("The sorter for this model"),
-                            GTK_TYPE_SORTER,
-                            GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
-
-  /**
-   * GtkTim1SortModel:model:
-   *
-   * The model being sorted
-   */
-  properties[PROP_MODEL] =
-      g_param_spec_object ("model",
-                           P_("Model"),
-                           P_("The model being sorted"),
-                           G_TYPE_LIST_MODEL,
-                           GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
-
-  g_object_class_install_properties (gobject_class, NUM_PROPERTIES, properties);
-}
-
-static void
-gtk_tim1_sort_model_init (GtkTim1SortModel *self)
-{
-}
-
-/**
- * gtk_tim1_sort_model_new:
- * @model: (allow-none): the model to sort
- * @sorter: (allow-none): the #GtkSorter to sort @model with
- *
- * Creates a new sort list model that uses the @sorter to sort @model.
- *
- * Returns: a new #GtkTim1SortModel
- **/
-GtkTim1SortModel *
-gtk_tim1_sort_model_new (GListModel *model,
-                         GtkSorter  *sorter)
-{
-  GtkTim1SortModel *result;
-
-  g_return_val_if_fail (model == NULL || G_IS_LIST_MODEL (model), NULL);
-  g_return_val_if_fail (sorter == NULL || GTK_IS_SORTER (sorter), NULL);
-
-  result = g_object_new (GTK_TYPE_TIM1_SORT_MODEL,
-                         "model", model,
-                         "sorter", sorter,
-                         NULL);
-
-  return result;
-}
-
-/**
- * gtk_tim1_sort_model_set_model:
- * @self: a #GtkTim1SortModel
- * @model: (allow-none): The model to be sorted
- *
- * Sets the model to be sorted. The @model's item type must conform to
- * the item type of @self.
- **/
-void
-gtk_tim1_sort_model_set_model (GtkTim1SortModel *self,
-                               GListModel       *model)
-{
-  guint removed, added;
-
-  g_return_if_fail (GTK_IS_TIM1_SORT_MODEL (self));
-  g_return_if_fail (model == NULL || G_IS_LIST_MODEL (model));
-
-  if (self->model == model)
-    return;
-
-  removed = g_list_model_get_n_items (G_LIST_MODEL (self));
-  gtk_tim1_sort_model_clear_model (self);
-
-  if (model)
-    {
-      self->model = g_object_ref (model);
-      g_signal_connect (model, "items-changed", G_CALLBACK (gtk_tim1_sort_model_items_changed_cb), self);
-      added = g_list_model_get_n_items (model);
-
-      gtk_tim1_sort_model_create_items (self);
-      gtk_tim1_sort_model_resort (self, 0);
-    }
-  else
-    added = 0;
-  
-  if (removed > 0 || added > 0)
-    g_list_model_items_changed (G_LIST_MODEL (self), 0, removed, added);
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_MODEL]);
-}
-
-/**
- * gtk_tim1_sort_model_get_model:
- * @self: a #GtkTim1SortModel
- *
- * Gets the model currently sorted or %NULL if none.
- *
- * Returns: (nullable) (transfer none): The model that gets sorted
- **/
-GListModel *
-gtk_tim1_sort_model_get_model (GtkTim1SortModel *self)
-{
-  g_return_val_if_fail (GTK_IS_TIM1_SORT_MODEL (self), NULL);
-
-  return self->model;
-}
-
-/**
- * gtk_tim1_sort_model_set_sorter:
- * @self: a #GtkTim1SortModel
- * @sorter: (allow-none): the #GtkSorter to sort @model with
- *
- * Sets a new sorter on @self.
- */
-void
-gtk_tim1_sort_model_set_sorter (GtkTim1SortModel *self,
-                                GtkSorter        *sorter)
-{
-  g_return_if_fail (GTK_IS_TIM1_SORT_MODEL (self));
-  g_return_if_fail (sorter == NULL || GTK_IS_SORTER (sorter));
-
-  gtk_tim1_sort_model_clear_sorter (self);
-
-  if (sorter)
-    {
-      self->sorter = g_object_ref (sorter);
-      g_signal_connect (sorter, "changed", G_CALLBACK (gtk_tim1_sort_model_sorter_changed_cb), self);
-      gtk_tim1_sort_model_sorter_changed_cb (sorter, GTK_SORTER_CHANGE_DIFFERENT, self);
-    }
-  else
-    {
-      guint n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
-      if (n_items > 1)
-        g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items);
-    }
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTER]);
-}
-
-/**
- * gtk_tim1_sort_model_get_sorter:
- * @self: a #GtkSor4LisTModel
- *
- * Gets the sorter that is used to sort @self.
- *
- * Returns: (nullable) (transfer none): the sorter of #self
- */
-GtkSorter *
-gtk_tim1_sort_model_get_sorter (GtkTim1SortModel *self)
-{
-  g_return_val_if_fail (GTK_IS_TIM1_SORT_MODEL (self), NULL);
-
-  return self->sorter;
-}

gtk/gtktim1sortmodel.h

@@ -1,57 +0,0 @@
-/*
- * Copyright © 2018 Benjamin Otte
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library. If not, see <http://www.gnu.org/licenses/>.
- *
- * Authors: Benjamin Otte <otte@gnome.org>
- */
-
-#ifndef __GTK_TIM1_SORT_MODEL_H__
-#define __GTK_TIM1_SORT_MODEL_H__
-
-
-#if !defined (__GTK_H_INSIDE__) && !defined (GTK_COMPILATION)
-#error "Only <gtk/gtk.h> can be included directly."
-#endif
-
-#include <gio/gio.h>
-#include <gtk/gtkwidget.h>
-#include <gtk/gtksorter.h>
-
-
-G_BEGIN_DECLS
-
-#define GTK_TYPE_TIM1_SORT_MODEL (gtk_tim1_sort_model_get_type ())
-
-GDK_AVAILABLE_IN_ALL
-G_DECLARE_FINAL_TYPE (GtkTim1SortModel, gtk_tim1_sort_model, GTK, TIM1_SORT_MODEL, GObject)
-
-GDK_AVAILABLE_IN_ALL
-GtkTim1SortModel *      gtk_tim1_sort_model_new                 (GListModel            *model,
-                                                                 GtkSorter             *sorter);
-GDK_AVAILABLE_IN_ALL
-void                    gtk_tim1_sort_model_set_sorter          (GtkTim1SortModel       *self,
-                                                                 GtkSorter              *sorter);
-GDK_AVAILABLE_IN_ALL
-GtkSorter *             gtk_tim1_sort_model_get_sorter          (GtkTim1SortModel       *self);
-
-GDK_AVAILABLE_IN_ALL
-void                    gtk_tim1_sort_model_set_model           (GtkTim1SortModel       *self,
-                                                                 GListModel             *model);
-GDK_AVAILABLE_IN_ALL
-GListModel *            gtk_tim1_sort_model_get_model           (GtkTim1SortModel       *self);
-
-G_END_DECLS
-
-#endif /* __GTK_TIM1_SORT_MODEL_H__ */

gtk/gtktim2sortmodel.c

@@ -1,639 +0,0 @@
-/*
- * Copyright © 2018 Benjamin Otte
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library. If not, see <http://www.gnu.org/licenses/>.
- *
- * Authors: Benjamin Otte <otte@gnome.org>
- */
-
-#include "config.h"
-
-#include "gtktim2sortmodel.h"
-
-#include "gtkintl.h"
-#include "gtkprivate.h"
-#include "gdk/gdkprofilerprivate.h"
-#include "gtktimsortprivate.h"
-
-typedef struct _SortItem SortItem;
-struct _SortItem
-{
-  GObject *item;
-  guint position;
-};
-
-static void
-sort_item_clear (gpointer data)
-{
-  SortItem *si = data;
-
-  g_clear_object (&si->item);
-}
-
-#define GTK_VECTOR_ELEMENT_TYPE SortItem
-#define GTK_VECTOR_TYPE_NAME SortArray
-#define GTK_VECTOR_NAME sort_array
-#define GTK_VECTOR_FREE_FUNC sort_item_clear
-#define GTK_VECTOR_BY_VALUE 1
-#include "gtkvectorimpl.c"
-
-/**
- * SECTION:gtksor4listmodel
- * @title: GtkTim2SortModel
- * @short_description: A list model that sorts its items
- * @see_also: #GListModel, #GtkSorter
- *
- * #GtkTim2SortModel is a list model that takes a list model and
- * sorts its elements according to a #GtkSorter.
- *
- * #GtkTim2SortModel is a generic model and because of that it
- * cannot take advantage of any external knowledge when sorting.
- * If you run into performance issues with #GtkTim2SortModel, it
- * is strongly recommended that you write your own sorting list
- * model.
- */
-
-enum {
-  PROP_0,
-  PROP_MODEL,
-  PROP_SORTER,
-  PROP_SORTING,
-  NUM_PROPERTIES
-};
-
-struct _GtkTim2SortModel
-{
-  GObject parent_instance;
-
-  GListModel *model;
-  GtkSorter *sorter;
-
-  GtkTimSort sort; /* ongoing sort operation */
-  guint sort_cb; /* 0 or current ongoing sort callback */
-  SortArray items; /* empty if known unsorted */
-
-  gint64 start_time;
-  guint steps;
-};
-
-struct _GtkTim2SortModelClass
-{
-  GObjectClass parent_class;
-};
-
-static GParamSpec *properties[NUM_PROPERTIES] = { NULL, };
-
-static GType
-gtk_tim2_sort_model_get_item_type (GListModel *list)
-{
-  return G_TYPE_OBJECT;
-}
-
-static guint
-gtk_tim2_sort_model_get_n_items (GListModel *list)
-{
-  GtkTim2SortModel *self = GTK_TIM2_SORT_MODEL (list);
-
-  if (self->model == NULL)
-    return 0;
-
-  return g_list_model_get_n_items (self->model);
-}
-
-static gpointer
-gtk_tim2_sort_model_get_item (GListModel *list,
-                              guint       position)
-{
-  GtkTim2SortModel *self = GTK_TIM2_SORT_MODEL (list);
-
-  if (self->model == NULL)
-    return NULL;
-
-  if (sort_array_is_empty (&self->items))
-    return g_list_model_get_item (self->model, position);
-
-  if (position >= sort_array_get_size (&self->items))
-    return NULL;
-
-  return g_object_ref (sort_array_get (&self->items, position)->item);
-}
-
-static void
-gtk_tim2_sort_model_model_init (GListModelInterface *iface)
-{
-  iface->get_item_type = gtk_tim2_sort_model_get_item_type;
-  iface->get_n_items = gtk_tim2_sort_model_get_n_items;
-  iface->get_item = gtk_tim2_sort_model_get_item;
-}
-
-G_DEFINE_TYPE_WITH_CODE (GtkTim2SortModel, gtk_tim2_sort_model, G_TYPE_OBJECT,
-                         G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_tim2_sort_model_model_init))
-
-static gboolean
-gtk_tim2_sort_model_is_sorting (GtkTim2SortModel *self)
-{
-  return self->sort_cb != 0;
-}
-
-static void
-gtk_tim2_sort_model_stop_sorting (GtkTim2SortModel *self)
-{
-  if (self->sort_cb == 0)
-    return;
-
-  gtk_tim_sort_finish (&self->sort);
-  g_clear_handle_id (&self->sort_cb, g_source_remove);
-
-  if (GDK_PROFILER_IS_RUNNING)
-    {
-      if (self->start_time != 0)
-        gdk_profiler_add_markf (self->start_time, g_get_monotonic_time () - self->start_time, "sort", "sorting %u", (guint)sort_array_get_size (&self->items));
-
-      self->start_time = 0;
-    }
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTING]);
-}
-
-static gboolean
-gtk_tim2_sort_model_sort_cb (gpointer data)
-{
-  GtkTim2SortModel *self = data;
-  gint64 begin = g_get_monotonic_time ();
-
-  if (gtk_tim_sort_step (&self->sort))
-    {
-      guint n_items = sort_array_get_size (&self->items);
-      g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items);
-
-      if (GDK_PROFILER_IS_RUNNING)
-        gdk_profiler_add_markf (begin, g_get_monotonic_time () - begin, "sort", "sort step (%u:%u)", 0, n_items);
-
-      return G_SOURCE_CONTINUE;
-    }
-
-  if (GDK_PROFILER_IS_RUNNING)
-    gdk_profiler_add_markf (begin, g_get_monotonic_time () - begin, "sort", "sort step (%u:%u)", 0, (guint)sort_array_get_size (&self->items));
-
-  gtk_tim2_sort_model_stop_sorting (self);
-  return G_SOURCE_REMOVE;
-}
-
-static void
-gtk_tim2_sort_model_start_sorting (GtkTim2SortModel *self)
-{
-  if (self->sort_cb != 0)
-    return;
-
-  self->sort_cb = g_idle_add (gtk_tim2_sort_model_sort_cb, self);
-
-  self->start_time = g_get_monotonic_time ();
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTING]);
-}
-
-static void
-gtk_tim2_sort_model_clear_items (GtkTim2SortModel *self)
-{
-  gtk_tim2_sort_model_stop_sorting (self);
-  sort_array_clear (&self->items);
-} 
-
-static gboolean
-gtk_tim2_sort_model_should_sort (GtkTim2SortModel *self)
-{
-  return self->sorter != NULL &&
-         self->model != NULL &&
-         gtk_sorter_get_order (self->sorter) != GTK_SORTER_ORDER_NONE;
-}
-
-static void
-gtk_tim2_sort_model_create_items (GtkTim2SortModel *self)
-{
-  guint i, n_items;
-
-  if (!gtk_tim2_sort_model_should_sort (self))
-    return;
-
-  n_items = g_list_model_get_n_items (self->model);
-  sort_array_reserve (&self->items, n_items);
-  for (i = 0; i < n_items; i++)
-    {
-      sort_array_append (&self->items, &(SortItem) { g_list_model_get_item (self->model, i), i });
-    }
-}
-
-static int
-sort_func (gconstpointer a,
-           gconstpointer b,
-           gpointer      data)
-{
-  SortItem *sa = (SortItem *) a;
-  SortItem *sb = (SortItem *) b;
-
-  return gtk_sorter_compare (data, sa->item, sb->item);
-}
-
-static void
-gtk_tim2_sort_model_resort (GtkTim2SortModel *self,
-                            guint             already_sorted)
-{
-  if (GDK_PROFILER_IS_RUNNING)
-    gdk_profiler_add_mark (g_get_monotonic_time (), 0, "resort", NULL);
-
-  if (gtk_tim2_sort_model_is_sorting (self))
-    {
-      already_sorted = 0;
-      gtk_tim2_sort_model_stop_sorting (self);
-    }
-
-  gtk_tim_sort_init (&self->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 (&self->sort, already_sorted);
-
-  gtk_tim2_sort_model_start_sorting (self);
-}
-
-static void
-gtk_tim2_sort_model_remove_items (GtkTim2SortModel *self,
-                                  guint             position,
-                                  guint             removed,
-                                  guint             added,
-                                  guint            *unmodified_start,
-                                  guint            *unmodified_end)
-{
-  guint i, n_items, valid;
-  guint start, end;
-
-  n_items = sort_array_get_size (&self->items);
-  start = n_items;
-  end = n_items;
-  
-  valid = 0;
-  for (i = 0; i < n_items; i++)
-    {
-      SortItem *si = sort_array_index (&self->items, i);
-
-      if (si->position >= position + removed)
-        si->position = si->position - removed + added;
-      else if (si->position >= position)
-        { 
-          start = MIN (start, valid);
-          end = n_items - i - 1;
-          sort_item_clear (si);
-          continue;
-        }
-      if (valid < i)
-        *sort_array_index (&self->items, valid) = *sort_array_index (&self->items, i);
-      valid++;
-    }
-
-  g_assert (valid == n_items - removed);
-  memset (sort_array_index (&self->items, valid), 0, sizeof (SortItem) * removed); 
-  sort_array_set_size (&self->items, valid);
-
-  *unmodified_start = start;
-  *unmodified_end = end;
-}
-
-static void
-gtk_tim2_sort_model_items_changed_cb (GListModel       *model,
-                                      guint             position,
-                                      guint             removed,
-                                      guint             added,
-                                      GtkTim2SortModel *self)
-{
-  guint i, n_items, start, end;
-  gboolean was_sorting;
-
-  if (removed == 0 && added == 0)
-    return;
-
-  if (!gtk_tim2_sort_model_should_sort (self))
-    {
-      g_list_model_items_changed (G_LIST_MODEL (self), position, removed, added);
-      return;
-    }
-
-  was_sorting = gtk_tim2_sort_model_is_sorting (self);
-  gtk_tim2_sort_model_stop_sorting (self);
-
-  gtk_tim2_sort_model_remove_items (self, position, removed, added, &start, &end);
-
-  if (added > 0)
-    {
-      sort_array_reserve (&self->items, sort_array_get_size (&self->items) + added);
-      for (i = position; i < position + added; i++)
-        {
-          sort_array_append (&self->items, &(SortItem) { g_list_model_get_item (self->model, i), i });
-        }
-
-      gtk_tim2_sort_model_resort (self, was_sorting ? 0 : sort_array_get_size (&self->items) - added);
-    }
-  else
-    {
-      if (was_sorting)
-        gtk_tim2_sort_model_resort (self, 0);
-    }
-
-  n_items = sort_array_get_size (&self->items) - start - end;
-  g_list_model_items_changed (G_LIST_MODEL (self), start, n_items - added + removed, n_items);
-}
-
-static void
-gtk_tim2_sort_model_set_property (GObject      *object,
-                                  guint         prop_id,
-                                  const GValue *value,
-                                  GParamSpec   *pspec)
-{
-  GtkTim2SortModel *self = GTK_TIM2_SORT_MODEL (object);
-
-  switch (prop_id)
-    {
-    case PROP_MODEL:
-      gtk_tim2_sort_model_set_model (self, g_value_get_object (value));
-      break;
-
-    case PROP_SORTER:
-      gtk_tim2_sort_model_set_sorter (self, g_value_get_object (value));
-      break;
-
-    default:
-      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
-      break;
-    }
-}
-
-static void 
-gtk_tim2_sort_model_get_property (GObject     *object,
-                                  guint        prop_id,
-                                  GValue      *value,
-                                  GParamSpec  *pspec)
-{
-  GtkTim2SortModel *self = GTK_TIM2_SORT_MODEL (object);
-
-  switch (prop_id)
-    {
-    case PROP_MODEL:
-      g_value_set_object (value, self->model);
-      break;
-
-    case PROP_SORTER:
-      g_value_set_object (value, self->sorter);
-      break;
-
-    case PROP_SORTING:
-      g_value_set_boolean (value, self->sort_cb != 0);
-      break;
-
-    default:
-      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
-      break;
-    }
-}
-
-static void
-gtk_tim2_sort_model_sorter_changed_cb (GtkSorter        *sorter,
-                                       int               change,
-                                       GtkTim2SortModel *self)
-{
-  guint n_items;
-
-  if (gtk_sorter_get_order (sorter) == GTK_SORTER_ORDER_NONE)
-    gtk_tim2_sort_model_clear_items (self);
-  else if (sort_array_is_empty (&self->items))
-    gtk_tim2_sort_model_create_items (self);
-
-  gtk_tim2_sort_model_resort (self, 0);
-
-  n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
-  if (n_items > 1)
-    g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items);
-}
-
-static void
-gtk_tim2_sort_model_clear_model (GtkTim2SortModel *self)
-{
-  if (self->model == NULL)
-    return;
-
-  g_signal_handlers_disconnect_by_func (self->model, gtk_tim2_sort_model_items_changed_cb, self);
-  g_clear_object (&self->model);
-  gtk_tim2_sort_model_clear_items (self);
-}
-
-static void
-gtk_tim2_sort_model_clear_sorter (GtkTim2SortModel *self)
-{
-  if (self->sorter == NULL)
-    return;
-
-  g_signal_handlers_disconnect_by_func (self->sorter, gtk_tim2_sort_model_sorter_changed_cb, self);
-  g_clear_object (&self->sorter);
-  gtk_tim2_sort_model_clear_items (self);
-}
-
-static void
-gtk_tim2_sort_model_dispose (GObject *object)
-{
-  GtkTim2SortModel *self = GTK_TIM2_SORT_MODEL (object);
-
-  gtk_tim2_sort_model_clear_model (self);
-  gtk_tim2_sort_model_clear_sorter (self);
-
-  G_OBJECT_CLASS (gtk_tim2_sort_model_parent_class)->dispose (object);
-};
-
-static void
-gtk_tim2_sort_model_class_init (GtkTim2SortModelClass *class)
-{
-  GObjectClass *gobject_class = G_OBJECT_CLASS (class);
-
-  gobject_class->set_property = gtk_tim2_sort_model_set_property;
-  gobject_class->get_property = gtk_tim2_sort_model_get_property;
-  gobject_class->dispose = gtk_tim2_sort_model_dispose;
-
-  /**
-   * GtkTim2SortModel:sorter:
-   *
-   * The sorter for this model
-   */
-  properties[PROP_SORTER] =
-      g_param_spec_object ("sorter",
-                            P_("Sorter"),
-                            P_("The sorter for this model"),
-                            GTK_TYPE_SORTER,
-                            GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
-
-  /**
-   * GtkTim2SortModel:model:
-   *
-   * The model being sorted
-   */
-  properties[PROP_MODEL] =
-      g_param_spec_object ("model",
-                           P_("Model"),
-                           P_("The model being sorted"),
-                           G_TYPE_LIST_MODEL,
-                           GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
-
-  properties[PROP_SORTING] =
-      g_param_spec_boolean ("sorting",
-                           P_("Sorting"),
-                           P_("Whether sorting is currently underway"),
-                           FALSE,
-                           GTK_PARAM_READABLE | G_PARAM_EXPLICIT_NOTIFY);
-
-  g_object_class_install_properties (gobject_class, NUM_PROPERTIES, properties);
-}
-
-static void
-gtk_tim2_sort_model_init (GtkTim2SortModel *self)
-{
-}
-
-/**
- * gtk_tim2_sort_model_new:
- * @model: (allow-none): the model to sort
- * @sorter: (allow-none): the #GtkSorter to sort @model with
- *
- * Creates a new sort list model that uses the @sorter to sort @model.
- *
- * Returns: a new #GtkTim2SortModel
- **/
-GtkTim2SortModel *
-gtk_tim2_sort_model_new (GListModel *model,
-                         GtkSorter  *sorter)
-{
-  GtkTim2SortModel *result;
-
-  g_return_val_if_fail (model == NULL || G_IS_LIST_MODEL (model), NULL);
-  g_return_val_if_fail (sorter == NULL || GTK_IS_SORTER (sorter), NULL);
-
-  result = g_object_new (GTK_TYPE_TIM2_SORT_MODEL,
-                         "model", model,
-                         "sorter", sorter,
-                         NULL);
-
-  return result;
-}
-
-/**
- * gtk_tim2_sort_model_set_model:
- * @self: a #GtkTim2SortModel
- * @model: (allow-none): The model to be sorted
- *
- * Sets the model to be sorted. The @model's item type must conform to
- * the item type of @self.
- **/
-void
-gtk_tim2_sort_model_set_model (GtkTim2SortModel *self,
-                               GListModel       *model)
-{
-  guint removed, added;
-
-  g_return_if_fail (GTK_IS_TIM2_SORT_MODEL (self));
-  g_return_if_fail (model == NULL || G_IS_LIST_MODEL (model));
-
-  if (self->model == model)
-    return;
-
-  removed = g_list_model_get_n_items (G_LIST_MODEL (self));
-  gtk_tim2_sort_model_clear_model (self);
-
-  if (model)
-    {
-      self->model = g_object_ref (model);
-      g_signal_connect (model, "items-changed", G_CALLBACK (gtk_tim2_sort_model_items_changed_cb), self);
-      added = g_list_model_get_n_items (model);
-
-      gtk_tim2_sort_model_create_items (self);
-      gtk_tim2_sort_model_resort (self, 0);
-    }
-  else
-    added = 0;
-  
-  if (removed > 0 || added > 0)
-    g_list_model_items_changed (G_LIST_MODEL (self), 0, removed, added);
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_MODEL]);
-}
-
-/**
- * gtk_tim2_sort_model_get_model:
- * @self: a #GtkTim2SortModel
- *
- * Gets the model currently sorted or %NULL if none.
- *
- * Returns: (nullable) (transfer none): The model that gets sorted
- **/
-GListModel *
-gtk_tim2_sort_model_get_model (GtkTim2SortModel *self)
-{
-  g_return_val_if_fail (GTK_IS_TIM2_SORT_MODEL (self), NULL);
-
-  return self->model;
-}
-
-/**
- * gtk_tim2_sort_model_set_sorter:
- * @self: a #GtkTim2SortModel
- * @sorter: (allow-none): the #GtkSorter to sort @model with
- *
- * Sets a new sorter on @self.
- */
-void
-gtk_tim2_sort_model_set_sorter (GtkTim2SortModel *self,
-                                GtkSorter        *sorter)
-{
-  g_return_if_fail (GTK_IS_TIM2_SORT_MODEL (self));
-  g_return_if_fail (sorter == NULL || GTK_IS_SORTER (sorter));
-
-  gtk_tim2_sort_model_clear_sorter (self);
-
-  if (sorter)
-    {
-      self->sorter = g_object_ref (sorter);
-      g_signal_connect (sorter, "changed", G_CALLBACK (gtk_tim2_sort_model_sorter_changed_cb), self);
-      gtk_tim2_sort_model_sorter_changed_cb (sorter, GTK_SORTER_CHANGE_DIFFERENT, self);
-    }
-  else
-    {
-      guint n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
-      if (n_items > 1)
-        g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items);
-    }
-
-  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTER]);
-}
-
-/**
- * gtk_tim2_sort_model_get_sorter:
- * @self: a #GtkSor4LisTModel
- *
- * Gets the sorter that is used to sort @self.
- *
- * Returns: (nullable) (transfer none): the sorter of #self
- */
-GtkSorter *
-gtk_tim2_sort_model_get_sorter (GtkTim2SortModel *self)
-{
-  g_return_val_if_fail (GTK_IS_TIM2_SORT_MODEL (self), NULL);
-
-  return self->sorter;
-}

gtk/gtktim2sortmodel.h

@@ -1,57 +0,0 @@
-/*
- * Copyright © 2018 Benjamin Otte
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library. If not, see <http://www.gnu.org/licenses/>.
- *
- * Authors: Benjamin Otte <otte@gnome.org>
- */
-
-#ifndef __GTK_TIM2_SORT_MODEL_H__
-#define __GTK_TIM2_SORT_MODEL_H__
-
-
-#if !defined (__GTK_H_INSIDE__) && !defined (GTK_COMPILATION)
-#error "Only <gtk/gtk.h> can be included directly."
-#endif
-
-#include <gio/gio.h>
-#include <gtk/gtkwidget.h>
-#include <gtk/gtksorter.h>
-
-
-G_BEGIN_DECLS
-
-#define GTK_TYPE_TIM2_SORT_MODEL (gtk_tim2_sort_model_get_type ())
-
-GDK_AVAILABLE_IN_ALL
-G_DECLARE_FINAL_TYPE (GtkTim2SortModel, gtk_tim2_sort_model, GTK, TIM2_SORT_MODEL, GObject)
-
-GDK_AVAILABLE_IN_ALL
-GtkTim2SortModel *      gtk_tim2_sort_model_new                 (GListModel            *model,
-                                                                 GtkSorter             *sorter);
-GDK_AVAILABLE_IN_ALL
-void                    gtk_tim2_sort_model_set_sorter          (GtkTim2SortModel       *self,
-                                                                 GtkSorter              *sorter);
-GDK_AVAILABLE_IN_ALL
-GtkSorter *             gtk_tim2_sort_model_get_sorter          (GtkTim2SortModel       *self);
-
-GDK_AVAILABLE_IN_ALL
-void                    gtk_tim2_sort_model_set_model           (GtkTim2SortModel       *self,
-                                                                 GListModel             *model);
-GDK_AVAILABLE_IN_ALL
-GListModel *            gtk_tim2_sort_model_get_model           (GtkTim2SortModel       *self);
-
-G_END_DECLS
-
-#endif /* __GTK_TIM2_SORT_MODEL_H__ */

gtk/gtktimsort-impl.c

@@ -1,940 +0,0 @@
-/*
- * Copyright (C) 2020 Benjamin Otte
- * Copyright (C) 2011 Patrick O. Perry
- * Copyright (C) 2008 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#ifndef NAME
-#define NAME WIDTH
-#endif
-
-#define DEFINE_TEMP(temp) gpointer temp = g_alloca (WIDTH)
-#define ASSIGN(x, y) memcpy (x, y, WIDTH)
-#define INCPTR(x) ((gpointer) ((char *) (x) + WIDTH))
-#define DECPTR(x) ((gpointer) ((char *) (x) - WIDTH))
-#define ELEM(a, i) ((char *) (a) + (i) * WIDTH)
-#define LEN(n) ((n) * WIDTH)
-
-#define CONCAT(x, y) gtk_tim_sort_ ## x ## _ ## y
-#define MAKE_STR(x, y) CONCAT (x, y)
-#define gtk_tim_sort(x) MAKE_STR (x, NAME)
-
-/*
- * Reverse the specified range of the specified array.
- *
- * @param a the array in which a range is to be reversed
- * @param hi the index after the last element in the range to be reversed
- */
-static void gtk_tim_sort(reverse_range) (GtkTimSort *self,
-                                         gpointer    a,
-                                         gsize       hi)
-{
-  DEFINE_TEMP (t);
-  char *front = a;
-  char *back = ELEM (a, hi - 1);
-
-  g_assert (hi > 0);
-
-  while (front < back)
-    {
-      ASSIGN (t, front);
-      ASSIGN (front, back);
-      ASSIGN (back, t);
-      front = INCPTR (front);
-      back = DECPTR (back);
-    }
-}
-
-/*
- * Returns the length of the run beginning at the specified position in
- * the specified array and reverses the run if it is descending (ensuring
- * that the run will always be ascending when the method returns).
- *
- * A run is the longest ascending sequence with:
- *
- *    a[0] <= a[1] <= a[2] <= ...
- *
- * or the longest descending sequence with:
- *
- *    a[0] >  a[1] >  a[2] >  ...
- *
- * For its intended use in a stable mergesort, the strictness of the
- * definition of "descending" is needed so that the call can safely
- * reverse a descending sequence without violating stability.
- *
- * @param a the array in which a run is to be counted and possibly reversed
- * @param hi index after the last element that may be contained in the run.
- *        It is required that {@code 0 < hi}.
- * @param compare the comparator to used for the sort
- * @return  the length of the run beginning at the specified position in
- *          the specified array
- */
-static gsize
-gtk_tim_sort(prepare_run) (GtkTimSort *self)
-{
-  gsize run_hi = 1;
-  char *cur;
-  char *next;
-
-  if (self->size <= run_hi)
-    return self->size;
-
-  cur = INCPTR (self->base);
-  next = INCPTR (cur);
-  run_hi++;
-
-  /* Find end of run, and reverse range if descending */
-  if (gtk_tim_sort_compare (self, cur, self->base) < 0)          /* Descending */
-    {
-      while (run_hi < self->size && gtk_tim_sort_compare (self, next, cur) < 0)
-        {
-          run_hi++;
-          cur = next;
-          next = INCPTR (next);
-        }
-      gtk_tim_sort(reverse_range) (self, self->base, run_hi);
-    }
-  else                          /* Ascending */
-    {
-      while (run_hi < self->size && gtk_tim_sort_compare (self, next, cur) >= 0)
-        {
-          run_hi++;
-          cur = next;
-          next = INCPTR (next);
-        }
-    }
-
-  return run_hi;
-}
-
-/*
- * Sorts the specified portion of the specified array using a binary
- * insertion sort.  This is the best method for sorting small numbers
- * of elements.  It requires O(n log n) compares, but O(n^2) data
- * movement (worst case).
- *
- * If the initial part of the specified range is already sorted,
- * this method can take advantage of it: the method assumes that the
- * elements from index {@code lo}, inclusive, to {@code start},
- * exclusive are already sorted.
- *
- * @param a the array in which a range is to be sorted
- * @param hi the index after the last element in the range to be sorted
- * @param start the index of the first element in the range that is
- *        not already known to be sorted ({@code lo <= start <= hi})
- */
-static void gtk_tim_sort(binary_sort) (GtkTimSort *self,
-                                       gpointer    a,
-                                       gsize       hi,
-                                       gsize       start)
-{
-  DEFINE_TEMP (pivot);
-  char *startp;
-
-  g_assert (start <= hi);
-
-  if (start == 0)
-    start++;
-
-  startp = ELEM (a, start);
-
-  for (; start < hi; start++, startp = INCPTR (startp))
-    {
-      /* Set left (and right) to the index where a[start] (pivot) belongs */
-      char *leftp = a;
-      gsize right = start;
-      gsize n;
-
-      /*
-       * Invariants:
-       *   pivot >= all in [0, left).
-       *   pivot <  all in [right, start).
-       */
-      while (0 < right)
-        {
-          gsize mid = right >> 1;
-          gpointer midp = ELEM (leftp, mid);
-          if (gtk_tim_sort_compare (self, startp, midp) < 0)
-            {
-              right = mid;
-            }
-          else
-            {
-              leftp = INCPTR (midp);
-              right -= (mid + 1);
-            }
-        }
-      g_assert (0 == right);
-
-      /*
-       * The invariants still hold: pivot >= all in [lo, left) and
-       * pivot < all in [left, start), so pivot belongs at left.  Note
-       * that if there are elements equal to pivot, left points to the
-       * first slot after them -- that's why this sort is stable.
-       * Slide elements over to make room to make room for pivot.
-       */
-      n = startp - leftp;               /* The number of bytes to move */
-
-      ASSIGN (pivot, startp);
-      memmove (INCPTR (leftp), leftp, n);         /* POP: overlaps */
-
-      /* a[left] = pivot; */
-      ASSIGN (leftp, pivot);
-    }
-}
-
-static gboolean
-gtk_tim_sort(merge_append) (GtkTimSort *self)
-{
-  /* Identify next run */
-  gsize run_len;
-
-  run_len = gtk_tim_sort(prepare_run) (self);
-  if (run_len == 0)
-    return FALSE;
-
-  /* If run is short, extend to min(self->min_run, self->size) */
-  if (run_len < self->min_run)
-    {
-      gsize force = MIN (self->size, self->min_run);
-      gtk_tim_sort(binary_sort) (self, self->base, force, run_len);
-      run_len = force;
-    }
-  /* Push run onto pending-run stack, and maybe merge */
-  gtk_tim_sort_push_run (self, self->base, run_len);
-
-  return TRUE;
-}
-
-#if 0
-static int gtk_tim_sort(timsort) (void *a, gsize nel)
-{
-  int err = SUCCESS;
-  GtkTimSort self;
-  gsize self->min_run;
-
-  g_assert (a || !nel || !width);
-  g_assert (c);
-
-  if (nel < 2 || !width)
-    return err;                 /* Arrays of size 0 and 1 are always sorted */
-
-  /* If array is small, do a "mini-TimSort" with no merges */
-  if (nel < MIN_MERGE)
-    {
-      gsize initRunLen =
-        gtk_tim_sort(prepare_run) (a, nel, CMPARGS (c, carg));
-      gtk_tim_sort(binary_sort) (self, a, nel, initRunLen, CMPARGS (c, carg));
-      return err;
-    }
-
-  /*
-   * March over the array once, left to right, finding natural runs,
-   * extending short natural runs to self->min_run elements, and merging runs
-   * to maintain stack invariant.
-   */
-  if ((err = timsort_init (&self, a, nel, CMPARGS (c, carg))))
-    return err;
-
-  do
-    {
-      /* Identify next run */
-      gsize run_len =
-        gtk_tim_sort(prepare_run) (a, nel, CMPARGS (c, carg));
-
-      /* If run is short, extend to min(self->min_run, nel) */
-      if (run_len < self->min_run)
-        {
-          gsize force = nel <= self->min_run ? nel : self->min_run;
-          gtk_tim_sort(binary_sort) (a, force, run_len, CMPARGS (c, carg));
-          run_len = force;
-        }
-      /* Push run onto pending-run stack, and maybe merge */
-      gtk_tim_sort_push_run (&self, a, run_len);
-      if ((err = gtk_tim_sort(mergeCollapse) (&self)))
-        goto out;
-
-      /* Advance to find next run */
-      a = ELEM (a, run_len);
-      nel -= run_len;
-    }
-  while (nel != 0);
-
-  /* Merge all remaining runs to complete sort */
-  if ((err = gtk_tim_sort(merge_force_collapse) (&self)))
-    goto out;
-
-  g_assert (self.pending_runs == 1);
-out:
-  timsort_deinit (&self);
-  return err;
-}
-#endif
-
-/*
- * Locates the position at which to insert the specified key into the
- * specified sorted range; if the range contains an element equal to key,
- * returns the index of the leftmost equal element.
- *
- * @param key the key whose insertion point to search for
- * @param base the array in which to search
- * @param len the length of the range; must be > 0
- * @param hint the index at which to begin the search, 0 <= hint < n.
- *     The closer hint is to the result, the faster this method will run.
- * @param c the comparator used to order the range, and to search
- * @return the int k,  0 <= k <= n such that a[b + k - 1] < key <= a[b + k],
- *    pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
- *    In other words, key belongs at index b + k; or in other words,
- *    the first k elements of a should precede key, and the last n - k
- *    should follow it.
- */
-static gsize
-gtk_tim_sort(gallop_left) (GtkTimSort *self,
-                           gpointer    key,
-                           gpointer    base,
-                           gsize       len,
-                           gsize       hint)
-{
-  char *hintp = ELEM (base, hint);
-  gsize last_ofs = 0;
-  gsize ofs = 1;
-
-  g_assert (len > 0 && hint < len);
-  if (gtk_tim_sort_compare (self, key, hintp) > 0)
-    {
-      /* Gallop right until a[hint+last_ofs] < key <= a[hint+ofs] */
-      gsize max_ofs = len - hint;
-      while (ofs < max_ofs
-             && gtk_tim_sort_compare (self, key, ELEM (hintp, ofs)) > 0)
-        {
-          last_ofs = ofs;
-          ofs = (ofs << 1) + 1;                 /* eventually this becomes SIZE_MAX */
-        }
-      if (ofs > max_ofs)
-        ofs = max_ofs;
-
-      /* Make offsets relative to base */
-      last_ofs += hint + 1;              /* POP: we add 1 here so last_ofs stays non-negative */
-      ofs += hint;
-    }
-  else                          /* key <= a[hint] */
-  /* Gallop left until a[hint-ofs] < key <= a[hint-last_ofs] */
-    {
-      const gsize max_ofs = hint + 1;
-      gsize tmp;
-      while (ofs < max_ofs
-             && gtk_tim_sort_compare (self, key, ELEM (hintp, -ofs)) <= 0)
-        {
-          last_ofs = ofs;
-          ofs = (ofs << 1) + 1;                 /* no need to check for overflow */
-        }
-      if (ofs > max_ofs)
-        ofs = max_ofs;
-
-      /* Make offsets relative to base */
-      tmp = last_ofs;
-      last_ofs = hint + 1 - ofs;                 /* POP: we add 1 here so last_ofs stays non-negative */
-      ofs = hint - tmp;
-    }
-  g_assert (last_ofs <= ofs && ofs <= len);
-
-  /*
-   * Now a[last_ofs-1] < key <= a[ofs], so key belongs somewhere
-   * to the right of last_ofs but no farther right than ofs.  Do a binary
-   * search, with invariant a[last_ofs - 1] < key <= a[ofs].
-   */
-  /* last_ofs++; POP: we added 1 above to keep last_ofs non-negative */
-  while (last_ofs < ofs)
-    {
-      /*gsize m = last_ofs + ((ofs - last_ofs) >> 1); */
-      /* http://stackoverflow.com/questions/4844165/safe-integer-middle-value-formula */
-      gsize m = (last_ofs & ofs) + ((last_ofs ^ ofs) >> 1);
-
-      if (gtk_tim_sort_compare (self, key, ELEM (base, m)) > 0)
-        last_ofs = m + 1;                        /* a[m] < key */
-      else
-        ofs = m;                        /* key <= a[m] */
-    }
-  g_assert (last_ofs == ofs);      /* so a[ofs - 1] < key <= a[ofs] */
-  return ofs;
-}
-
-/*
- * Like gallop_left, except that if the range contains an element equal to
- * key, gallop_right returns the index after the rightmost equal element.
- *
- * @param key the key whose insertion point to search for
- * @param base the array in which to search
- * @param len the length of the range; must be > 0
- * @param hint the index at which to begin the search, 0 <= hint < n.
- *     The closer hint is to the result, the faster this method will run.
- * @param c the comparator used to order the range, and to search
- * @return the int k,  0 <= k <= n such that a[b + k - 1] <= key < a[b + k]
- */
-static gsize
-gtk_tim_sort(gallop_right) (GtkTimSort *self,
-                            gpointer    key,
-                            gpointer    base,
-                            gsize       len,
-                            gsize       hint)
-{
-  char *hintp = ELEM (base, hint);
-  gsize ofs = 1;
-  gsize last_ofs = 0;
-
-  g_assert (len > 0 && hint < len);
-
-  if (gtk_tim_sort_compare (self, key, hintp) < 0)
-    {
-      /* Gallop left until a[hint - ofs] <= key < a[hint - last_ofs] */
-      gsize max_ofs = hint + 1;
-      gsize tmp;
-      while (ofs < max_ofs
-             && gtk_tim_sort_compare (self, key, ELEM (hintp, -ofs)) < 0)
-        {
-          last_ofs = ofs;
-          ofs = (ofs << 1) + 1;                 /* no need to check for overflow */
-        }
-      if (ofs > max_ofs)
-        ofs = max_ofs;
-
-      /* Make offsets relative to base */
-      tmp = last_ofs;
-      last_ofs = hint + 1 - ofs;
-      ofs = hint - tmp;
-    }
-  else                          /* a[hint] <= key */
-  /* Gallop right until a[hint + last_ofs] <= key < a[hint + ofs] */
-    {
-      gsize max_ofs = len - hint;
-      while (ofs < max_ofs
-             && gtk_tim_sort_compare (self, key, ELEM (hintp, ofs)) >= 0)
-        {
-          last_ofs = ofs;
-          ofs = (ofs << 1) + 1;                 /* no need to check for overflow */
-        }
-      if (ofs > max_ofs)
-        ofs = max_ofs;
-
-      /* Make offsets relative to base */
-      last_ofs += hint + 1;
-      ofs += hint;
-    }
-  g_assert (last_ofs <= ofs && ofs <= len);
-
-  /*
-   * Now a[last_ofs - 1] <= key < a[ofs], so key belongs somewhere to
-   * the right of last_ofs but no farther right than ofs.  Do a binary
-   * search, with invariant a[last_ofs - 1] <= key < a[ofs].
-   */
-  while (last_ofs < ofs)
-    {
-      /* gsize m = last_ofs + ((ofs - last_ofs) >> 1); */
-      gsize m = (last_ofs & ofs) + ((last_ofs ^ ofs) >> 1);
-
-      if (gtk_tim_sort_compare (self, key, ELEM (base, m)) < 0)
-        ofs = m;                        /* key < a[m] */
-      else
-        last_ofs = m + 1;                        /* a[m] <= key */
-    }
-  g_assert (last_ofs == ofs);      /* so a[ofs - 1] <= key < a[ofs] */
-  return ofs;
-}
-
-/*
- * Merges two adjacent runs in place, in a stable fashion.  The first
- * element of the first run must be greater than the first element of the
- * second run (a[base1] > a[base2]), and the last element of the first run
- * (a[base1 + len1-1]) must be greater than all elements of the second run.
- *
- * For performance, this method should be called only when len1 <= len2;
- * its twin, merge_hi should be called if len1 >= len2.  (Either method
- * may be called if len1 == len2.)
- *
- * @param base1 first element in first run to be merged
- * @param len1  length of first run to be merged (must be > 0)
- * @param base2 first element in second run to be merged
- *        (must be aBase + aLen)
- * @param len2  length of second run to be merged (must be > 0)
- */
-static void
-gtk_tim_sort(merge_lo) (GtkTimSort *self,
-                        gpointer    base1,
-                        gsize       len1,
-                        gpointer    base2,
-                        gsize       len2)
-{
-  /* Copy first run into temp array */
-  gpointer tmp = gtk_tim_sort_ensure_capacity (self, len1);
-  char *cursor1;
-  char *cursor2;
-  char *dest;
-  gsize min_gallop;
-
-  g_assert (len1 > 0 && len2 > 0 && ELEM (base1, len1) == base2);
-
-  /* System.arraycopy(a, base1, tmp, 0, len1); */
-  memcpy (tmp, base1, LEN (len1));     /* POP: can't overlap */
-
-  cursor1 = tmp;                /* Indexes into tmp array */
-  cursor2 = base2;              /* Indexes int a */
-  dest = base1;                 /* Indexes int a */
-
-  /* Move first element of second run and deal with degenerate cases */
-  /* a[dest++] = a[cursor2++]; */
-  ASSIGN (dest, cursor2);
-  dest = INCPTR (dest);
-  cursor2 = INCPTR (cursor2);
-
-  if (--len2 == 0)
-    {
-      memcpy (dest, cursor1, LEN (len1));         /* POP: can't overlap */
-      return;
-    }
-  if (len1 == 1)
-    {
-      memmove (dest, cursor2, LEN (len2));         /* POP: overlaps */
-
-      /* a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge */
-      ASSIGN (ELEM (dest, len2), cursor1);
-      return;
-    }
-
-  /* Use local variable for performance */
-  min_gallop = self->min_gallop;
-
-  while (TRUE)
-    {
-      gsize count1 = 0;                 /* Number of times in a row that first run won */
-      gsize count2 = 0;                 /* Number of times in a row that second run won */
-
-      /*
-       * Do the straightforward thing until (if ever) one run starts
-       * winning consistently.
-       */
-      do
-        {
-          g_assert (len1 > 1 && len2 > 0);
-          if (gtk_tim_sort_compare (self, cursor2, cursor1) < 0)
-            {
-              ASSIGN (dest, cursor2);
-              dest = INCPTR (dest);
-              cursor2 = INCPTR (cursor2);
-              count2++;
-              count1 = 0;
-              if (--len2 == 0)
-                goto outer;
-              if (count2 >= min_gallop)
-                break;
-            }
-          else
-            {
-              ASSIGN (dest, cursor1);
-              dest = INCPTR (dest);
-              cursor1 = INCPTR (cursor1);
-              count1++;
-              count2 = 0;
-              if (--len1 == 1)
-                goto outer;
-              if (count1 >= min_gallop)
-                break;
-            }
-        }
-      while (TRUE);                /* (count1 | count2) < min_gallop); */
-
-      /*
-       * One run is winning so consistently that galloping may be a
-       * huge win. So try that, and continue galloping until (if ever)
-       * neither run appears to be winning consistently anymore.
-       */
-      do
-        {
-          g_assert (len1 > 1 && len2 > 0);
-          count1 = gtk_tim_sort(gallop_right) (self, cursor2, cursor1, len1, 0);
-          if (count1 != 0)
-            {
-              memcpy (dest, cursor1, LEN (count1));                 /* POP: can't overlap */
-              dest = ELEM (dest, count1);
-              cursor1 = ELEM (cursor1, count1);
-              len1 -= count1;
-              if (len1 <= 1)                    /* len1 == 1 || len1 == 0 */
-                goto outer;
-            }
-          ASSIGN (dest, cursor2);
-          dest = INCPTR (dest);
-          cursor2 = INCPTR (cursor2);
-          if (--len2 == 0)
-            goto outer;
-
-          count2 = gtk_tim_sort(gallop_left) (self, cursor1, cursor2, len2, 0);
-          if (count2 != 0)
-            {
-              memmove (dest, cursor2, LEN (count2));                 /* POP: might overlap */
-              dest = ELEM (dest, count2);
-              cursor2 = ELEM (cursor2, count2);
-              len2 -= count2;
-              if (len2 == 0)
-                goto outer;
-            }
-          ASSIGN (dest, cursor1);
-          dest = INCPTR (dest);
-          cursor1 = INCPTR (cursor1);
-          if (--len1 == 1)
-            goto outer;
-          if (min_gallop > 0)
-            min_gallop--;
-        }
-      while (count1 >= MIN_GALLOP || count2 >= MIN_GALLOP);
-      min_gallop += 2;           /* Penalize for leaving gallop mode */
-    }                           /* End of "outer" loop */
-outer:
-  self->min_gallop = min_gallop < 1 ? 1 : min_gallop;        /* Write back to field */
-
-  if (len1 == 1)
-    {
-      g_assert (len2 > 0);
-      memmove (dest, cursor2, LEN (len2));              /*  POP: might overlap */
-      ASSIGN (ELEM (dest, len2), cursor1);              /*  Last elt of run 1 to end of merge */
-    }
-  else if (len1 == 0)
-    {
-      g_critical ("Comparison method violates its general contract");
-      return;
-    }
-  else
-    {
-      g_assert (len2 == 0);
-      g_assert (len1 > 1);
-      memcpy (dest, cursor1, LEN (len1));         /* POP: can't overlap */
-    }
-}
-
-/*
- * Like merge_lo, except that this method should be called only if
- * len1 >= len2; merge_lo should be called if len1 <= len2.  (Either method
- * may be called if len1 == len2.)
- *
- * @param base1 first element in first run to be merged
- * @param len1  length of first run to be merged (must be > 0)
- * @param base2 first element in second run to be merged
- *        (must be aBase + aLen)
- * @param len2  length of second run to be merged (must be > 0)
- */
-static void
-gtk_tim_sort(merge_hi) (GtkTimSort *self,
-                        gpointer    base1,
-                        gsize       len1,
-                        gpointer    base2,
-                        gsize       len2)
-{
-  /* Copy second run into temp array */
-  gpointer tmp = gtk_tim_sort_ensure_capacity (self, len2);
-  char *cursor1;        /* Indexes into a */
-  char *cursor2;        /* Indexes into tmp array */
-  char *dest;           /* Indexes into a */
-  gsize min_gallop;
-
-  g_assert (len1 > 0 && len2 > 0 && ELEM (base1, len1) == base2);
-
-  memcpy (tmp, base2, LEN (len2));     /* POP: can't overlap */
-
-  cursor1 = ELEM (base1, len1 - 1);     /* Indexes into a */
-  cursor2 = ELEM (tmp, len2 - 1);       /* Indexes into tmp array */
-  dest = ELEM (base2, len2 - 1);        /* Indexes into a */
-
-  /* Move last element of first run and deal with degenerate cases */
-  /* a[dest--] = a[cursor1--]; */
-  ASSIGN (dest, cursor1);
-  dest = DECPTR (dest);
-  cursor1 = DECPTR (cursor1);
-  if (--len1 == 0)
-    {
-      memcpy (ELEM (dest, -(len2 - 1)), tmp, LEN (len2));        /* POP: can't overlap */
-      return;
-    }
-  if (len2 == 1)
-    {
-      dest = ELEM (dest, -len1);
-      cursor1 = ELEM (cursor1, -len1);
-      memmove (ELEM (dest, 1), ELEM (cursor1, 1), LEN (len1));       /* POP: overlaps */
-      /* a[dest] = tmp[cursor2]; */
-      ASSIGN (dest, cursor2);
-      return;
-    }
-
-  /* Use local variable for performance */
-  min_gallop = self->min_gallop;
-
-  while (TRUE)
-    {
-      gsize count1 = 0;                 /* Number of times in a row that first run won */
-      gsize count2 = 0;                 /* Number of times in a row that second run won */
-
-      /*
-       * Do the straightforward thing until (if ever) one run
-       * appears to win consistently.
-       */
-      do
-        {
-          g_assert (len1 > 0 && len2 > 1);
-          if (gtk_tim_sort_compare (self, cursor2, cursor1) < 0)
-            {
-              ASSIGN (dest, cursor1);
-              dest = DECPTR (dest);
-              cursor1 = DECPTR (cursor1);
-              count1++;
-              count2 = 0;
-              if (--len1 == 0)
-                goto outer;
-            }
-          else
-            {
-              ASSIGN (dest, cursor2);
-              dest = DECPTR (dest);
-              cursor2 = DECPTR (cursor2);
-              count2++;
-              count1 = 0;
-              if (--len2 == 1)
-                goto outer;
-            }
-        }
-      while ((count1 | count2) < min_gallop);
-
-      /*
-       * One run is winning so consistently that galloping may be a
-       * huge win. So try that, and continue galloping until (if ever)
-       * neither run appears to be winning consistently anymore.
-       */
-      do
-        {
-          g_assert (len1 > 0 && len2 > 1);
-          count1 = len1 - gtk_tim_sort(gallop_right) (self, cursor2, base1, len1, len1 - 1);
-          if (count1 != 0)
-            {
-              dest = ELEM (dest, -count1);
-              cursor1 = ELEM (cursor1, -count1);
-              len1 -= count1;
-              memmove (INCPTR (dest), INCPTR (cursor1),
-                       LEN (count1));                /* POP: might overlap */
-              if (len1 == 0)
-                goto outer;
-            }
-          ASSIGN (dest, cursor2);
-          dest = DECPTR (dest);
-          cursor2 = DECPTR (cursor2);
-          if (--len2 == 1)
-            goto outer;
-
-          count2 = len2 - gtk_tim_sort(gallop_left) (self, cursor1, tmp, len2, len2 - 1);
-          if (count2 != 0)
-            {
-              dest = ELEM (dest, -count2);
-              cursor2 = ELEM (cursor2, -count2);
-              len2 -= count2;
-              memcpy (INCPTR (dest), INCPTR (cursor2), LEN (count2));               /* POP: can't overlap */
-              if (len2 <= 1)                    /* len2 == 1 || len2 == 0 */
-                goto outer;
-            }
-          ASSIGN (dest, cursor1);
-          dest = DECPTR (dest);
-          cursor1 = DECPTR (cursor1);
-          if (--len1 == 0)
-            goto outer;
-          if (min_gallop > 0)
-            min_gallop--;
-        }
-      while (count1 >= MIN_GALLOP || count2 >= MIN_GALLOP);
-      min_gallop += 2;           /* Penalize for leaving gallop mode */
-    }                           /* End of "outer" loop */
-outer:
-  self->min_gallop = min_gallop < 1 ? 1 : min_gallop;        /* Write back to field */
-
-  if (len2 == 1)
-    {
-      g_assert (len1 > 0);
-      dest = ELEM (dest, -len1);
-      cursor1 = ELEM (cursor1, -len1);
-      memmove (INCPTR (dest), INCPTR (cursor1), LEN (len1));       /* POP: might overlap */
-      /* a[dest] = tmp[cursor2];  // Move first elt of run2 to front of merge */
-      ASSIGN (dest, cursor2);
-    }
-  else if (len2 == 0)
-    {
-      g_critical ("Comparison method violates its general contract");
-      return;
-    }
-  else
-    {
-      g_assert (len1 == 0);
-      g_assert (len2 > 0);
-      memcpy (ELEM (dest, -(len2 - 1)), tmp, LEN (len2));        /* POP: can't overlap */
-    }
-}
-
-/*
- * Merges the two runs at stack indices i and i+1.  Run i must be
- * the penultimate or antepenultimate run on the stack.  In other words,
- * i must be equal to pending_runs-2 or pending_runs-3.
- *
- * @param i stack index of the first of the two runs to merge
- */
-static void
-gtk_tim_sort(merge_at) (GtkTimSort *self,
-                        gsize       i)
-{
-  gpointer base1 = self->run[i].base;
-  gsize len1 = self->run[i].len;
-  gpointer base2 = self->run[i + 1].base;
-  gsize len2 = self->run[i + 1].len;
-  gsize k;
-
-  g_assert (self->pending_runs >= 2);
-  g_assert (i == self->pending_runs - 2 || i == self->pending_runs - 3);
-  g_assert (len1 > 0 && len2 > 0);
-  g_assert (ELEM (base1, len1) == base2);
-
-  /*
-   * Record the length of the combined runs; if i is the 3rd-last
-   * run now, also slide over the last run (which isn't involved
-   * in this merge).  The current run (i+1) goes away in any case.
-   */
-  self->run[i].len = len1 + len2;
-  if (i == self->pending_runs - 3)
-    {
-      self->run[i + 1] = self->run[i + 2];
-    }
-  self->pending_runs--;
-
-  /*
-   * Find where the first element of run2 goes in run1. Prior elements
-   * in run1 can be ignored (because they're already in place).
-   */
-  k = gtk_tim_sort(gallop_right) (self, base2, base1, len1, 0);
-  base1 = ELEM (base1, k);
-  len1 -= k;
-  if (len1 == 0)
-    return;
-
-  /*
-   * Find where the last element of run1 goes in run2. Subsequent elements
-   * in run2 can be ignored (because they're already in place).
-   */
-  len2 = gtk_tim_sort(gallop_left) (self,
-                                    ELEM (base1, len1 - 1),
-                                    base2, len2, len2 - 1);
-  if (len2 == 0)
-    return;
-
-  /* Merge remaining runs, using tmp array with min(len1, len2) elements */
-  if (len1 <= len2)
-    gtk_tim_sort(merge_lo) (self, base1, len1, base2, len2);
-  else
-    gtk_tim_sort(merge_hi) (self, base1, len1, base2, len2);
-}
-
-
-/*
- * Examines the stack of runs waiting to be merged and merges adjacent runs
- * until the stack invariants are reestablished:
- *
- *     1. run_len[i - 3] > run_len[i - 2] + run_len[i - 1]
- *     2. run_len[i - 2] > run_len[i - 1]
- *
- * This method is called each time a new run is pushed onto the stack,
- * so the invariants are guaranteed to hold for i < pending_runs upon
- * entry to the method.
- *
- * POP:
- * Modified according to http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf
- *
- * and
- *
- * https://bugs.openjdk.java.net/browse/JDK-8072909 (suggestion 2)
- *
- */
-static gboolean
-gtk_tim_sort(merge_collapse) (GtkTimSort *self)
-{
-  GtkTimSortRun *run = self->run;
-  gsize n;
-
-  if (self->pending_runs <= 1)
-    return FALSE;
-
-  n = self->pending_runs - 2;
-  if ((n > 0 && run[n - 1].len <= run[n].len + run[n + 1].len) ||
-      (n > 1 && run[n - 2].len <= run[n].len + run[n - 1].len))
-    {
-      if (run[n - 1].len < run[n + 1].len)
-        n--;
-    }
-  else if (run[n].len > run[n + 1].len)
-    {
-      return FALSE; /* Invariant is established */
-    }
-  
-  gtk_tim_sort(merge_at) (self, n);
-  return TRUE;
-}
-
-/*
- * Merges all runs on the stack until only one remains.  This method is
- * called once, to complete the sort.
- */
-static gboolean
-gtk_tim_sort(merge_force_collapse) (GtkTimSort *self)
-{
-  gsize n;
-
-  if (self->pending_runs <= 1)
-    return FALSE;
-
-  n = self->pending_runs - 2;
-  if (n > 0 && self->run[n - 1].len < self->run[n + 1].len)
-    n--;
-  gtk_tim_sort(merge_at) (self, n);
-  return TRUE;
-}
-
-static gboolean
-gtk_tim_sort(step) (GtkTimSort * self)
-{
-  g_assert (self);
-
-  if (gtk_tim_sort(merge_collapse) (self))
-    return TRUE;
-
-  if (gtk_tim_sort(merge_append) (self))
-    return TRUE;
-
-  if (gtk_tim_sort(merge_force_collapse) (self))
-    return TRUE;
-
-  return FALSE;
-}
-
-#undef DEFINE_TEMP
-#undef ASSIGN
-#undef INCPTR
-#undef DECPTR
-#undef ELEM
-#undef LEN
-
-#undef CONCAT
-#undef MAKE_STR
-#undef gtk_tim_sort
-
-#undef WIDTH
-#undef NAME

gtk/gtktimsort.c

@@ -1,220 +0,0 @@
-/* Lots of code for an adaptive, stable, natural mergesort.  There are many
- * pieces to this algorithm; read listsort.txt for overviews and details.
- */
-
-#include "config.h"
-
-#include "gtktimsortprivate.h"
-
-/*
- * This is the minimum sized sequence that will be merged.  Shorter
- * sequences will be lengthened by calling binarySort.  If the entire
- * array is less than this length, no merges will be performed.
- *
- * This constant should be a power of two.  It was 64 in Tim Peter's C
- * implementation, but 32 was empirically determined to work better in
- * [Android's Java] implementation.  In the unlikely event that you set
- * this constant to be a number that's not a power of two, you'll need
- * to change the compute_min_run() computation.
- *
- * If you decrease this constant, you must change the
- * GTK_TIM_SORT_MAX_PENDING value, or you risk running out of space.
- * See Python's listsort.txt for a discussion of the minimum stack
- * length required as a function of the length of the array being sorted and
- * the minimum merge sequence length.
- */
-#define MIN_MERGE 32
-
-
-/*
- * When we get into galloping mode, we stay there until both runs win less
- * often than MIN_GALLOP consecutive times.
- */
-#define MIN_GALLOP 7
-
-/*
- * Returns the minimum acceptable run length for an array of the specified
- * length. Natural runs shorter than this will be extended with binary sort.
- *
- * Roughly speaking, the computation is:
- *
- *  If n < MIN_MERGE, return n (it's too small to bother with fancy stuff).
- *  Else if n is an exact power of 2, return MIN_MERGE/2.
- *  Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k
- *   is close to, but strictly less than, an exact power of 2.
- *
- * For the rationale, see listsort.txt.
- *
- * @param n the length of the array to be sorted
- * @return the length of the minimum run to be merged
- */
-static gsize
-compute_min_run (gsize n)
-{
-  gsize r = 0; // Becomes 1 if any 1 bits are shifted off
-
-  while (n >= MIN_MERGE) {
-    r |= (n & 1);
-    n >>= 1;
-  }
-  return n + r;
-}
-
-void
-gtk_tim_sort_init (GtkTimSort       *self,
-                   gpointer          base,
-                   gsize             size,
-                   gsize             element_size,
-                   GCompareDataFunc  compare_func,
-                   gpointer          data)
-{
-  self->element_size = element_size;
-  self->base = base;
-  self->size = size;
-  self->compare_func = compare_func;
-  self->data = data;
-
-  self->min_gallop = MIN_GALLOP;
-  self->min_run = compute_min_run (size);
-
-  self->tmp = NULL;
-  self->tmp_length = 0;
-  self->pending_runs = 0;
-}
-
-void
-gtk_tim_sort_finish (GtkTimSort *self)
-{
-  g_free (self->tmp);
-}
-
-void
-gtk_tim_sort (gpointer         base,
-              gsize            size,
-              gsize            element_size,
-              GCompareDataFunc compare_func,
-              gpointer         user_data)
-{
-  GtkTimSort self;
-
-  gtk_tim_sort_init (&self, base, size, element_size, compare_func, user_data);
-
-  while (gtk_tim_sort_step (&self));
-
-  gtk_tim_sort_finish (&self);
-}
-
-static inline int
-gtk_tim_sort_compare (GtkTimSort *self,
-                      gpointer    a,
-                      gpointer    b)
-{
-  return self->compare_func (a, b, self->data);
-}
-
-
-/**
- * Pushes the specified run onto the pending-run stack.
- *
- * @param runBase index of the first element in the run
- * @param runLen  the number of elements in the run
- */
-static void
-gtk_tim_sort_push_run (GtkTimSort *self,
-                       void       *base,
-                       gsize       len)
-{
-  g_assert (self->pending_runs < GTK_TIM_SORT_MAX_PENDING);
-
-  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;
-}
-
-/**
- * Ensures that the external array tmp has at least the specified
- * number of elements, increasing its size if necessary.  The size
- * increases exponentially to ensure amortized linear time complexity.
- *
- * @param min_capacity the minimum required capacity of the tmp array
- * @return tmp, whether or not it grew
- */
-static gpointer
-gtk_tim_sort_ensure_capacity (GtkTimSort *self,
-                              gsize       min_capacity)
-{
-  if (self->tmp_length < min_capacity)
-    {
-      /* Compute smallest power of 2 > min_capacity */
-      gsize new_size = min_capacity;
-      new_size |= new_size >> 1;
-      new_size |= new_size >> 2;
-      new_size |= new_size >> 4;
-      new_size |= new_size >> 8;
-      new_size |= new_size >> 16;
-      if (sizeof(new_size) > 4)
-        new_size |= new_size >> 32;
-
-      new_size++;
-      if (new_size == 0) /* (overflow) Not bloody likely! */
-        new_size = min_capacity;
-
-      g_free (self->tmp);
-      self->tmp_length = new_size;
-      self->tmp = g_malloc (self->tmp_length * self->element_size);
-  }
-
-  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"
-
-#define WIDTH 8
-#include "gtktimsort-impl.c"
-
-#define WIDTH 16
-#include "gtktimsort-impl.c"
-#endif
-
-#define NAME default
-#define WIDTH (self->element_size)
-#include "gtktimsort-impl.c"
-
-gboolean
-gtk_tim_sort_step (GtkTimSort *self)
-{
-  g_assert (self);
-
-  switch (self->element_size)
-  {
-#if 1
-    case 4:
-      return gtk_tim_sort_step_4 (self);
-    case 8:
-      return gtk_tim_sort_step_8 (self);
-    case 16:
-      return gtk_tim_sort_step_16 (self);
-#endif
-    default:
-      return gtk_tim_sort_step_default(self);
-  }
-}
-

gtk/gtktimsortprivate.h

@@ -1,108 +0,0 @@
-/*
- * Copyright © 2020 Benjamin Otte
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library. If not, see <http://www.gnu.org/licenses/>.
- */
-
-#ifndef __GTK_TIMSORT_PRIVATE_H__
-#define __GTK_TIMSORT_PRIVATE_H__
-
-#include <gdk/gdk.h>
-
-/* The maximum number of entries in a GtkTimState's pending-runs stack.
- * This is enough to sort arrays of size up to about
- *     32 * phi ** GTK_TIM_SORT_MAX_PENDING
- * where phi ~= 1.618.  85 is ridiculously large enough, good for an array
- * with 2**64 elements.
- */
-#define GTK_TIM_SORT_MAX_PENDING 86
-
-typedef struct _GtkTimSort GtkTimSort;
-typedef struct _GtkTimSortRun GtkTimSortRun;
-
-struct _GtkTimSortRun
-{
-  void *base;
-  gsize len;
-};
-
-struct _GtkTimSort 
-{
-  /*
-   * Size of elements. Used to decide on fast paths.
-   */
-  gsize element_size;
-
-  /* The comparator for this sort.
-   */
-  GCompareDataFunc compare_func;
-  gpointer         data;
-
-  /*
-   * The array being sorted.
-   */
-  gpointer base;
-  gsize size;
-
-  /*
-   * This controls when we get *into* galloping mode.  It is initialized
-   * to MIN_GALLOP.  The mergeLo and mergeHi methods nudge it higher for
-   * random data, and lower for highly structured data.
-   */
-  gsize min_gallop;
-
-  /*
-   * The minimum run length. See compute_min_run() for details.
-   */
-  gsize min_run;
-
-  /*
-   * Temp storage for merges.
-   */
-  void *tmp;
-  gsize tmp_length;
-
-  /*
-   * A stack of pending runs yet to be merged.  Run i starts at
-   * address base[i] and extends for len[i] elements.  It's always
-   * true (so long as the indices are in bounds) that:
-   *
-   *     runBase[i] + runLen[i] == runBase[i + 1]
-   *
-   * so we could cut the storage for this, but it's a minor amount,
-   * and keeping all the info explicit simplifies the code.
-   */
-  gsize pending_runs;	// Number of pending runs on stack
-  GtkTimSortRun run[GTK_TIM_SORT_MAX_PENDING];
-};
-
-void            gtk_tim_sort_init                               (GtkTimSort             *self,
-                                                                 gpointer                base,
-                                                                 gsize                   size,
-                                                                 gsize                   element_size,
-                                                                 GCompareDataFunc        compare_func,
-                                                                 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,
-                                                                 gsize                   size,
-                                                                 gsize                   element_size,
-                                                                 GCompareDataFunc        compare_func,
-                                                                 gpointer                user_data);
-
-#endif /* __GTK_TIMSORT_PRIVATE_H__ */

gtk/gtkvectorimpl.c

@@ -105,8 +105,8 @@ gtk_vector(clear) (GtkVector *self)
 
 #ifdef GTK_VECTOR_PREALLOC
   if (self->start != self->preallocated)
-#endif
     g_free (self->start);
+#endif
   gtk_vector(init) (self);
 }
 

gtk/meson.build

@@ -141,7 +141,6 @@ gtk_private_sources = files([
   'gtktextbtree.c',
   'gtktexthistory.c',
   'gtktextviewchild.c',
-  'gtktimsort.c',
   'gtktrashmonitor.c',
   'gtktreedatalist.c',
 ])
@@ -374,8 +373,6 @@ gtk_public_sources = files([
   'gtksorter.c',
   'gtksor2listmodel.c',
   'gtksor3listmodel.c',
-  'gtksor4listmodel.c',
-  'gtksor5listmodel.c',
   'gtksortlistmodel.c',
   'gtkspinbutton.c',
   'gtkspinner.c',
@@ -405,8 +402,6 @@ gtk_public_sources = files([
   'gtktexttypes.c',
   'gtktextutil.c',
   'gtktextview.c',
-  'gtktim1sortmodel.c',
-  'gtktim2sortmodel.c',
   'gtktogglebutton.c',
   'gtktooltip.c',
   'gtktooltipwindow.c',
@@ -649,8 +644,6 @@ gtk_public_headers = files([
   'gtksorter.h',
   'gtksor2listmodel.h',
   'gtksor3listmodel.h',
-  'gtksor4listmodel.h',
-  'gtksor5listmodel.h',
   'gtksortlistmodel.h',
   'gtkspinbutton.h',
   'gtkspinner.h',
@@ -673,8 +666,6 @@ gtk_public_headers = files([
   'gtktexttag.h',
   'gtktexttagtable.h',
   'gtktextview.h',
-  'gtktim1sortmodel.h',
-  'gtktim2sortmodel.h',
   'gtktogglebutton.h',
   'gtktooltip.h',
   'gtktreednd.h',

tests/meson.build

@@ -11,7 +11,6 @@ gtk_tests = [
   ['scrolling-performance', ['frame-stats.c', 'variable.c']],
   ['blur-performance', ['../gsk/gskcairoblur.c']],
   ['simple'],
-  ['sorting'],
   ['video-timer', ['variable.c']],
   ['testaccel'],
   ['testadjustsize'],

tests/sorting.c

@@ -1,90 +0,0 @@
-#include <gtk/gtk.h>
-
-static GListModel *
-get_model (guint size)
-{
-  GtkStringList *model;
-  guint i;
-
-  model = gtk_string_list_new (NULL);
-
-  for (i = 0; i < size; i++)
-    {
-      char *string = g_strdup_printf ("%d", g_random_int_range (0, 1000000));
-      gtk_string_list_append (model, string);
-      g_free (string);
-    }
-
-  return G_LIST_MODEL (model);
-}
-
-static int
-sort_func (gconstpointer a, gconstpointer b, gpointer data)
-{
-  return strcmp (gtk_string_object_get_string (GTK_STRING_OBJECT ((gpointer)a)),
-                 gtk_string_object_get_string (GTK_STRING_OBJECT ((gpointer)b)));
-}
-
-static void
-sorting_changed (GtkSor3ListModel *model)
-{
-  gboolean sorting;
-
-  g_object_get (model, "sorting", &sorting, NULL);
-
-  if (!sorting)
-    exit (0);
-}
-
-static gboolean
-start_sort (gpointer data)
-{
-  GListModel *model = data;
-  GListModel *sort;
-  GtkSorter *sorter;
-
-  sorter = GTK_SORTER (gtk_custom_sorter_new (sort_func, NULL, NULL));
-
-  if (g_getenv ("TIMSORT"))
-    {
-      sort = G_LIST_MODEL (gtk_tim2_sort_model_new (model, NULL));
-      gtk_tim2_sort_model_set_sorter (GTK_TIM2_SORT_MODEL (sort), sorter);
-    }
-  else
-    {
-      sort = G_LIST_MODEL (gtk_sor3_list_model_new (model, NULL));
-      gtk_sor3_list_model_set_sorter (GTK_SOR3_LIST_MODEL (sort), sorter);
-    }
-
-  g_signal_connect (sort, "notify::sorting", G_CALLBACK (sorting_changed), NULL);
-
-  return G_SOURCE_REMOVE;
-}
-
-int main (int argc, char *argv[])
-{
-  GListModel *model;
-  guint32 seed;
-
-  seed = g_random_int ();
-
-  if (argc > 2)
-    {
-      if (strcmp (argv[1], "--seed") == 0)
-        seed = atoi (argv[2]);
-    }
-
-  g_print ("seed %u\n", seed);
-  g_random_set_seed (seed);
-
-  gtk_init ();
-
-  model = get_model (1000000);
-
-  g_idle_add (start_sort, model);
-
-  while (1)
-    g_main_context_iteration (NULL, TRUE);
-
-  return 0;
-}

testsuite/css/data.c

@@ -52,9 +52,6 @@ Test tests[] = {
   { "charset",
     "data:text/plain;charset=ISO-8859-1,Timm B\344der",
     "text/plain", CONTENTS("Timm Bäder") },
-  { "charset",
-    "data:text/plain;charset=ISO-8859-1,Timm%20B%E4der",
-    "text/plain", CONTENTS("Timm Bäder") },
   { "charset_base64",
     "data:text/plain;charset=ISO-8859-5;base64,wOPh29DdILjW0ePb0OLe0g==",
     "text/plain", CONTENTS("Руслан Ижбулатов") },

testsuite/gtk/filterlistmodel-exhaustive.c

@@ -1,5 +1,7 @@
-/*
- * Copyright © 2020 Benjamin Otte
+/* GtkRBTree tests.
+ *
+ * Copyright (C) 2011, Red Hat, Inc.
+ * Authors: Benjamin Otte <otte@gnome.org>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -322,7 +324,7 @@ test_two_filters (gconstpointer model_id)
 
           for (k = 0; k < 10; k++)
             {
-              source = create_source_model (0, 1000);
+              source = create_source_model (0, 20);
               gtk_filter_list_model_set_model (compare, source);
               gtk_filter_list_model_set_model (model1, source);
               g_object_unref (source);
@@ -416,7 +418,7 @@ test_model_changes (gconstpointer model_id)
       if (add)
         {
           /* We want at least one element, otherwise the filters will see no changes */
-          GListModel *source = create_source_model (1, 50);
+          GListModel *source = create_source_model (1, 20);
           GtkFilterListModel *model1 = create_filter_list_model (model_id, source, multi);
           g_list_store_splice (store1,
                                position,

testsuite/gtk/filterlistmodel.c

@@ -88,11 +88,6 @@ add (GListStore *store,
   g_string_set_size (changes, 0); \
 }G_STMT_END
 
-#define ignore_changes(model) G_STMT_START{ \
-  GString *changes = g_object_get_qdata (G_OBJECT (model), changes_quark); \
-  g_string_set_size (changes, 0); \
-}G_STMT_END
-
 static GListStore *
 new_empty_store (void)
 {
@@ -350,33 +345,6 @@ test_change_filter (void)
   g_object_unref (filter);
 }
 
-static void
-test_incremental (void)
-{
-  GtkFilterListModel *filter;
-  GtkFilter *custom;
-  
-  /* everything is filtered */
-  filter = new_model (1000, is_larger_than, GUINT_TO_POINTER (10000));
-  gtk_filter_list_model_set_incremental (filter, TRUE);
-  assert_model (filter, "");
-  assert_changes (filter, "");
-
-  custom = gtk_custom_filter_new (is_near, GUINT_TO_POINTER (512), NULL);
-  gtk_filter_list_model_set_filter (filter, custom);
-  g_object_unref (custom);
-  assert_model (filter, "");
-  assert_changes (filter, "");
-
-  while (g_main_context_pending (NULL))
-    g_main_context_iteration (NULL, TRUE);
-  assert_model (filter, "510 511 512 513 514");
-  /* implementation detail */
-  ignore_changes (filter);
-
-  g_object_unref (filter);
-}
-
 int
 main (int argc, char *argv[])
 {
@@ -389,7 +357,6 @@ main (int argc, char *argv[])
   g_test_add_func ("/filterlistmodel/create", test_create);
   g_test_add_func ("/filterlistmodel/empty_set_filter", test_empty_set_filter);
   g_test_add_func ("/filterlistmodel/change_filter", test_change_filter);
-  g_test_add_func ("/filterlistmodel/incremental", test_incremental);
 
   return g_test_run ();
 }

testsuite/gtk/meson.build

@@ -59,15 +59,12 @@ tests = [
   ['slicelistmodel'],
   ['sorter'],
   ['sortlistmodel'],
-  ['sortlistmodel-tests'],
-  ['sort-performance'],
   ['spinbutton'],
   ['stringlist'],
   ['templates'],
   ['textbuffer'],
   ['textiter'],
   ['theme-validate'],
-  ['timsort', ['timsort.c', '../../gtk/gtktimsort.c']],
   ['tooltips'],
   ['treelistmodel'],
   ['treemodel', ['treemodel.c', 'liststore.c', 'treestore.c', 'filtermodel.c',

testsuite/gtk/sort-performance.c

@@ -1,555 +0,0 @@
-#include <gtk/gtk.h>
-#include <math.h>
-
-#define MAX_SIZE 1024000
-#define MAX_TIME (G_USEC_PER_SEC / 2)
-
-static inline guint
-quick_random (guint prev)
-{
-  prev ^= prev << 13;
-  prev ^= prev >> 17;
-  prev ^= prev << 5;
-  return prev;
-}
-
-static guint comparisons = 0;
-
-static int
-compare_string_object (gconstpointer a,
-                       gconstpointer b,
-                       gpointer      unused)
-{
-  GtkStringObject *sa = (GtkStringObject *) a;
-  GtkStringObject *sb = (GtkStringObject *) b;
-
-  comparisons++;
-
-  return gtk_ordering_from_cmpfunc (strcmp (gtk_string_object_get_string (sa),
-                                            gtk_string_object_get_string (sb)));
-}
-
-static GtkSorter *
-create_sorter (void)
-{
-  return gtk_custom_sorter_new (compare_string_object, NULL, NULL);
-}
-
-static void
-count_changed_cb (GListModel *model,
-                  guint       position,
-                  guint       removed,
-                  guint       added,
-                  guint      *counter)
-{
-  *counter += MAX (removed, added);
-}
-
-static gint64
-snapshot_time (gint64  last,
-               gint64 *inout_max)
-{
-  gint64 now = g_get_monotonic_time ();
-  *inout_max = MAX (*inout_max, now - last);
-  return now;
-}
-
-static void
-set_model (const char *testname,
-           GType       type,
-           GListModel *source,
-           guint       random)
-{
-  gint64 start, end, max, total;
-  GtkSliceListModel *slice;
-  GtkSorter *sorter;
-  GListModel *sort;
-  guint n_changed, size = 1000;
-
-  slice = gtk_slice_list_model_new (source, 0, size);
-  sorter = create_sorter ();
-  sort = g_object_new (type,
-                       "sorter", sorter,
-                       NULL);
-  g_signal_connect (sort, "items-changed", G_CALLBACK (count_changed_cb), &n_changed);
-  g_object_unref (sorter);
-
-  while (TRUE)
-    {
-      while (g_main_context_pending (NULL))
-        g_main_context_iteration (NULL, TRUE);
-      comparisons = 0;
-      n_changed = 0;
-      max = 0;
-
-      start = end = g_get_monotonic_time ();
-      g_object_set (sort, "model", slice, NULL);
-      end = snapshot_time (end, &max);
-      while (g_main_context_pending (NULL))
-        {
-          g_main_context_iteration (NULL, TRUE);
-          end = snapshot_time (end, &max);
-        }
-
-      total = (end - start);
-
-      g_print ("\"%s\", \"%s\",%8u,%8uus,%8uus, %8u,%9u\n",
-               testname,
-               g_type_name (type),
-               size,
-               (guint) total,
-               (guint) max,
-               comparisons,
-               n_changed);
-
-      if (total > MAX_TIME)
-        break;
-
-      size *= 2;
-      if (4 * total > 2 * MAX_TIME)
-        break;
-
-      gtk_slice_list_model_set_size (slice, size);
-      g_object_set (sort, "model", NULL, NULL);
-    }
-
-  g_object_unref (sort);
-  g_object_unref (slice);
-}
-
-static void
-append (const char *testname,
-        GType       type,
-        GListModel *source,
-        guint       random,
-        guint       fraction)
-{
-  gint64 start, end, max, total;
-  GtkSliceListModel *slice;
-  GtkSorter *sorter;
-  GListModel *sort;
-  guint n_changed, size = 1000;
-
-  slice = gtk_slice_list_model_new (source, 0, (fraction - 1) * size / fraction);
-  sorter = create_sorter ();
-  sort = g_object_new (type,
-                       "model", slice,
-                       "sorter", sorter,
-                       NULL);
-  g_signal_connect (sort, "items-changed", G_CALLBACK (count_changed_cb), &n_changed);
-  g_object_unref (sorter);
-
-  while (TRUE)
-    {
-      gtk_slice_list_model_set_size (slice, (fraction - 1) * size / fraction);
-      while (g_main_context_pending (NULL))
-        g_main_context_iteration (NULL, TRUE);
-      comparisons = 0;
-      n_changed = 0;
-      max = 0;
-
-      start = end = g_get_monotonic_time ();
-      gtk_slice_list_model_set_size (slice, size);
-      end = snapshot_time (end, &max);
-      while (g_main_context_pending (NULL))
-        {
-          g_main_context_iteration (NULL, TRUE);
-          end = snapshot_time (end, &max);
-        }
-
-      total = (end - start);
-
-      g_print ("\"%s\", \"%s\",%8u,%8uus,%8uus, %8u,%9u\n",
-               testname,
-               g_type_name (type),
-               size,
-               (guint) total,
-               (guint) max,
-               comparisons,
-               n_changed);
-
-      if (total > MAX_TIME)
-        break;
-
-      size *= 2;
-      if (4 * total > 2 * MAX_TIME ||
-          size > MAX_SIZE)
-        break;
-    }
-
-  g_object_unref (sort);
-  g_object_unref (slice);
-}
-
-static void
-append_half (const char *name,
-             GType       type,
-             GListModel *source,
-             guint       random)
-{
-  append (name, type, source, random, 2);
-}
-
-static void
-append_10th (const char *name,
-             GType       type,
-             GListModel *source,
-             guint       random)
-{
-  append (name, type, source, random, 10);
-}
-
-static void
-append_100th (const char *name,
-              GType       type,
-              GListModel *source,
-              guint       random)
-{
-  append (name, type, source, random, 100);
-}
-
-static void
-remove_test (const char *testname,
-             GType       type,
-             GListModel *source,
-             guint       random,
-             guint       fraction)
-{
-  gint64 start, end, max, total;
-  GtkSliceListModel *slice;
-  GtkSorter *sorter;
-  GListModel *sort;
-  guint n_changed, size = 1000;
-
-  slice = gtk_slice_list_model_new (source, 0, size);
-  sorter = create_sorter ();
-  sort = g_object_new (type,
-                       "model", slice,
-                       "sorter", sorter,
-                       NULL);
-  g_signal_connect (sort, "items-changed", G_CALLBACK (count_changed_cb), &n_changed);
-  g_object_unref (sorter);
-
-  while (TRUE)
-    {
-      gtk_slice_list_model_set_size (slice, size);
-      while (g_main_context_pending (NULL))
-        g_main_context_iteration (NULL, TRUE);
-      comparisons = 0;
-      n_changed = 0;
-      max = 0;
-
-      start = end = g_get_monotonic_time ();
-      gtk_slice_list_model_set_size (slice, (fraction - 1) * size / fraction);
-      end = snapshot_time (end, &max);
-      while (g_main_context_pending (NULL))
-        {
-          g_main_context_iteration (NULL, TRUE);
-          end = snapshot_time (end, &max);
-        }
-
-      total = (end - start);
-
-      g_print ("\"%s\", \"%s\",%8u,%8uus,%8uus, %8u,%9u\n",
-               testname,
-               g_type_name (type),
-               size,
-               (guint) total,
-               (guint) max,
-               comparisons,
-               n_changed);
-
-      if (total > MAX_TIME)
-        break;
-
-      size *= 2;
-      if (4 * total > 2 * MAX_TIME ||
-          size > MAX_SIZE)
-        break;
-    }
-
-  g_object_unref (sort);
-  g_object_unref (slice);
-}
-
-static void
-remove_half (const char *name,
-             GType       type,
-             GListModel *source,
-             guint       random)
-{
-  remove_test (name, type, source, random, 2);
-}
-
-static void
-remove_10th (const char *name,
-             GType       type,
-             GListModel *source,
-             guint       random)
-{
-  remove_test (name, type, source, random, 10);
-}
-
-static void
-remove_100th (const char *name,
-              GType       type,
-              GListModel *source,
-              guint       random)
-{
-  remove_test (name, type, source, random, 100);
-}
-
-static void
-run_test (GtkStringList      *source,
-          const char * const *tests,
-          const char         *test_name,
-          void (* test_func) (const char *name, GType type, GListModel *source, guint random))
-{
-  GType types[] = { 
-    GTK_TYPE_SORT_LIST_MODEL,
-    GTK_TYPE_SOR2_LIST_MODEL,
-    GTK_TYPE_SOR3_LIST_MODEL,
-    GTK_TYPE_SOR4_LIST_MODEL,
-    GTK_TYPE_SOR5_LIST_MODEL,
-    GTK_TYPE_TIM1_SORT_MODEL,
-    GTK_TYPE_TIM2_SORT_MODEL,
-  };
-  guint random = g_random_int ();
-  guint i;
-
-  if (tests != NULL && !g_strv_contains (tests, test_name))
-    return;
-
-  for (i = 0; i < G_N_ELEMENTS (types); i++)
-    {
-      test_func (test_name, types[i], G_LIST_MODEL (source), random);
-    }
-}
-
-static void
-append_n (const char *testname,
-          GType       type,
-          GListModel *source,
-          guint       random,
-          guint       n)
-{
-  gint64 start, end, max, total;
-  GtkSliceListModel *slice;
-  GtkSorter *sorter;
-  GListModel *sort;
-  guint i, n_changed, size = 1000;
-
-  slice = gtk_slice_list_model_new (source, 0, size);
-  sorter = create_sorter ();
-  sort = g_object_new (type,
-                       "model", slice,
-                       "sorter", sorter,
-                       NULL);
-  g_signal_connect (sort, "items-changed", G_CALLBACK (count_changed_cb), &n_changed);
-  g_object_unref (sorter);
-
-  while (TRUE)
-    {
-      gtk_slice_list_model_set_size (slice, size - n * 100);
-      while (g_main_context_pending (NULL))
-        g_main_context_iteration (NULL, TRUE);
-      comparisons = 0;
-      n_changed = 0;
-      max = 0;
-
-      start = end = g_get_monotonic_time ();
-      for (i = 0; i < 100; i++)
-        {
-          gtk_slice_list_model_set_size (slice, size - n * (100 - i));
-          end = snapshot_time (end, &max);
-          while (g_main_context_pending (NULL))
-            {
-              g_main_context_iteration (NULL, TRUE);
-              end = snapshot_time (end, &max);
-            }
-        }
-
-      total = (end - start);
-
-      g_print ("\"%s\", \"%s\",%8u,%8uus,%8uus, %8u,%9u\n",
-               testname,
-               g_type_name (type),
-               size,
-               (guint) total,
-               (guint) max,
-               comparisons,
-               n_changed);
-
-      if (total > MAX_TIME)
-        break;
-
-      size *= 2;
-      if (4 * total > 2 * MAX_TIME ||
-          size > MAX_SIZE)
-        break;
-    }
-
-  g_object_unref (sort);
-  g_object_unref (slice);
-}
-
-static void
-append_1 (const char *name,
-          GType       type,
-          GListModel *source,
-          guint       random)
-{
-  append_n (name, type, source, random, 1);
-}
-
-static void
-append_2 (const char *name,
-          GType       type,
-          GListModel *source,
-          guint       random)
-{
-  append_n (name, type, source, random, 2);
-}
-
-static void
-append_10 (const char *name,
-           GType       type,
-           GListModel *source,
-           guint       random)
-{
-  append_n (name, type, source, random, 10);
-}
-
-static void
-remove_n (const char *testname,
-          GType       type,
-          GListModel *source,
-          guint       random,
-          guint       n)
-{
-  gint64 start, end, max, total;
-  GtkSliceListModel *slice;
-  GtkSorter *sorter;
-  GListModel *sort;
-  guint i, n_changed, size = 1000;
-
-  slice = gtk_slice_list_model_new (source, 0, size);
-  sorter = create_sorter ();
-  sort = g_object_new (type,
-                       "model", slice,
-                       "sorter", sorter,
-                       NULL);
-  g_signal_connect (sort, "items-changed", G_CALLBACK (count_changed_cb), &n_changed);
-  g_object_unref (sorter);
-
-  while (TRUE)
-    {
-      gtk_slice_list_model_set_size (slice, size);
-      while (g_main_context_pending (NULL))
-        g_main_context_iteration (NULL, TRUE);
-      comparisons = 0;
-      n_changed = 0;
-      max = 0;
-
-      start = end = g_get_monotonic_time ();
-      for (i = 0; i < 100; i++)
-        {
-          gtk_slice_list_model_set_size (slice, size - n * (i + 1));
-          end = snapshot_time (end, &max);
-          while (g_main_context_pending (NULL))
-            {
-              g_main_context_iteration (NULL, TRUE);
-              end = snapshot_time (end, &max);
-            }
-        }
-
-      total = (end - start);
-
-      g_print ("\"%s\", \"%s\",%8u,%8uus,%8uus, %8u,%9u\n",
-               testname,
-               g_type_name (type),
-               size,
-               (guint) total,
-               (guint) max,
-               comparisons,
-               n_changed);
-
-      if (total > MAX_TIME)
-        break;
-
-      size *= 2;
-      if (4 * total > 2 * MAX_TIME ||
-          size > MAX_SIZE)
-        break;
-    }
-
-  g_object_unref (sort);
-  g_object_unref (slice);
-}
-
-static void
-remove_1 (const char *name,
-          GType       type,
-          GListModel *source,
-          guint       random)
-{
-  remove_n (name, type, source, random, 1);
-}
-
-static void
-remove_2 (const char *name,
-          GType       type,
-          GListModel *source,
-          guint       random)
-{
-  remove_n (name, type, source, random, 2);
-}
-
-static void
-remove_10 (const char *name,
-           GType       type,
-           GListModel *source,
-           guint       random)
-{
-  remove_n (name, type, source, random, 10);
-}
-
-int
-main (int argc, char *argv[])
-{
-  GtkStringList *source;
-  guint random = g_random_int ();
-  guint i;
-  const char * const *tests;
-
-  gtk_test_init (&argc, &argv);
-
-  source = gtk_string_list_new (NULL);
-  for (i = 0; i < MAX_SIZE; i++)
-    {
-      gtk_string_list_take (source, g_strdup_printf ("%u", random));
-      random = quick_random  (random);
-    }
-
-  if (argc < 2)
-    tests = NULL;
-  else
-    tests = (const char **) argv + 1;
-
-  g_print ("\"test\",\"model\",\"model size\",\"time\",\"max time\",\"comparisons\",\"changes\"\n");
-  run_test (source, tests, "set-model", set_model);
-  run_test (source, tests, "append-half", append_half);
-  run_test (source, tests, "append-10th", append_10th);
-  run_test (source, tests, "append-100th", append_100th);
-  run_test (source, tests, "remove-half", remove_half);
-  run_test (source, tests, "remove-10th", remove_10th);
-  run_test (source, tests, "remove-100th", remove_100th);
-  run_test (source, tests, "append-1", append_1);
-  run_test (source, tests, "append-2", append_2);
-  run_test (source, tests, "append-10", append_10);
-  run_test (source, tests, "remove-1", remove_1);
-  run_test (source, tests, "remove-2", remove_2);
-  run_test (source, tests, "remove-10", remove_10);
-
-  return g_test_run ();
-}

testsuite/gtk/sortlistmodel-tests.c

@@ -1,302 +0,0 @@
-/*
- * Copyright © 2020 Matthias Clasen
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library. If not, see <http://www.gnu.org/licenses/>.
- */
-
-#include <gtk/gtk.h>
-#include <locale.h>
-
-static GListModel *
-get_random_model (guint size)
-{
-  GListStore *store = g_list_store_new (G_TYPE_OBJECT);
-  guint n;
-  guint i;
-
-  n = g_random_int_range (size / 2, size);
-  for (i = 0; i < n; i++)
-    {
-      char *string = g_strdup_printf ("%d", g_random_int_range (0, 1000000));
-      g_list_store_append (store, gtk_string_object_new (string));
-      g_free (string);
-    }
-
-  return G_LIST_MODEL (store);
-}
-
-static GListModel *
-copy_model (GListModel *model)
-{
-  GListStore *store = g_list_store_new (G_TYPE_OBJECT);
-  guint i, n;
-
-  n = g_list_model_get_n_items (model);
-  for (i = 0; i < n; i++)
-    {
-      gpointer item = g_list_model_get_item (model, i);
-      g_list_store_append (store, item);
-      g_object_unref (item);
-    }
-
-  return G_LIST_MODEL (store);
-}
-
-static GListModel *
-get_aaaa_model (guint size)
-{
-  GListStore *store = g_list_store_new (G_TYPE_OBJECT);
-  guint i;
-
-  for (i = 0; i < size; i++)
-    {
-      g_list_store_append (store, gtk_string_object_new ("AAA"));
-    }
-
-  return G_LIST_MODEL (store);
-}
-
-static int
-compare_func (gconstpointer a, gconstpointer b, gpointer data)
-{
-  const GtkStringObject *ao = a;
-  const GtkStringObject *bo = b;
-  char *ar, *br;
-  int ret;
-
-  ar = g_utf8_strreverse (gtk_string_object_get_string ((GtkStringObject*)ao), -1);
-  br = g_utf8_strreverse (gtk_string_object_get_string ((GtkStringObject*)bo), -1);
-  ret = strcmp (ar, br);
-  g_free (ar);
-  g_free (br);
-
-  return ret;
-}
-
-static GtkSorter *
-get_random_string_sorter (void)
-{
-  GtkSorter *sorter;
-
-  switch (g_random_int_range (0, 3))
-    {
-    case 0:
-      sorter = gtk_string_sorter_new (gtk_property_expression_new (GTK_TYPE_STRING_OBJECT, NULL, "string"));
-      break;
-
-    case 1:
-      sorter = gtk_string_sorter_new (gtk_property_expression_new (GTK_TYPE_STRING_OBJECT, NULL, "string"));
-      gtk_string_sorter_set_ignore_case (GTK_STRING_SORTER (sorter), TRUE);
-      break;
-
-    case 2:
-      sorter = gtk_custom_sorter_new (compare_func, NULL, NULL);
-      break;
-
-    default:
-      g_assert_not_reached ();
-    }
-
-  return sorter;
-}
-
-static void
-assert_model_equal (GListModel *model1, GListModel *model2)
-{
-  guint n1, n2, i;
-
-  n1 = g_list_model_get_n_items (model1);
-  n2 = g_list_model_get_n_items (model2);
-
-  g_assert_cmpuint (n1, ==, n2);
-
-  for (i = 0; i < n1; i++)
-    {
-      GObject *o1, *o2;
-
-      o1 = g_list_model_get_item (model1, i);
-      o2 = g_list_model_get_item (model2, i);
-
-      g_assert_cmpstr (gtk_string_object_get_string (GTK_STRING_OBJECT (o1)),
-                       ==,
-                       gtk_string_object_get_string (GTK_STRING_OBJECT (o2)));
-
-      g_object_unref (o1);
-      g_object_unref (o2);
-    }
-}
-
-static void
-assert_model_equal2 (GListModel *model1, GListModel *model2)
-{
-  guint n1, n2, i;
-
-  n1 = g_list_model_get_n_items (model1);
-  n2 = g_list_model_get_n_items (model2);
-
-  g_assert_cmpuint (n1, ==, n2);
-
-  for (i = 0; i < n1; i++)
-    {
-      GObject *o1, *o2;
-
-      o1 = g_list_model_get_item (model1, i);
-      o2 = g_list_model_get_item (model2, i);
-
-      g_assert_true (o1 == o2);
-
-      g_object_unref (o1);
-      g_object_unref (o2);
-    }
-}
-
-static void
-test_two_sorters (void)
-{
-  GListModel *store;
-  GListModel *model1, *model2, *model3;
-  GtkSorter *sorter1, *sorter2, *sorter3;
-  guint i;
-
-  for (i = 0; i < 100; i++)
-    {
-      store = get_random_model (1000);
-      sorter1 = get_random_string_sorter ();
-      sorter2 = get_random_string_sorter ();
-
-      model1 = G_LIST_MODEL (gtk_sort_list_model_new (store, sorter1));
-      model2 = G_LIST_MODEL (gtk_sort_list_model_new (model1, sorter2));
-
-      sorter3 = gtk_multi_sorter_new ();
-      gtk_multi_sorter_append (GTK_MULTI_SORTER (sorter3), g_object_ref (sorter2));
-      gtk_multi_sorter_append (GTK_MULTI_SORTER (sorter3), g_object_ref (sorter1));
-
-      model3 = G_LIST_MODEL (gtk_sort_list_model_new (store, sorter3));
-
-      assert_model_equal (model2, model3);
-
-      g_object_unref (model1);
-      g_object_unref (model2);
-      g_object_unref (model3);
-      g_object_unref (sorter1);
-      g_object_unref (sorter2);
-      g_object_unref (sorter3);
-    }
-}
-
-static void
-test_sort_twice (void)
-{
-  GListModel *store;
-  GListModel *model1, *model2;
-  GtkSorter *sorter;
-  guint i;
-
-  for (i = 0; i < 100; i++)
-    {
-      store = get_random_model (1000);
-      sorter = get_random_string_sorter ();
-
-      model1 = G_LIST_MODEL (gtk_sort_list_model_new (store, sorter));
-      model2 = G_LIST_MODEL (gtk_sort_list_model_new (model1, sorter));
-
-      assert_model_equal (model1, model2);
-
-      g_object_unref (store);
-      g_object_unref (model1);
-      g_object_unref (model2);
-      g_object_unref (sorter);
-    }
-}
-
-static void
-test_stable_sort (void)
-{
-  GListModel *store;
-  GListModel *model;
-  GtkSorter *sorter;
-  guint i;
-
-  for (i = 0; i < 100; i++)
-    {
-      store = get_aaaa_model (1000);
-      sorter = get_random_string_sorter ();
-
-      model = G_LIST_MODEL (gtk_sort_list_model_new (store, sorter));
-
-      assert_model_equal2 (model, store);
-
-      g_object_unref (store);
-      g_object_unref (model);
-      g_object_unref (sorter);
-    }
-}
-
-static void
-test_insert_random (void)
-{
-  GListModel *store1;
-  GListModel *store2;
-  GtkSorter *sorter;
-  GtkSortListModel *s1, *s2;
-  guint i, j;
-
-  for (i = 0; i < 20; i++)
-    {
-      store1 = get_random_model (1000);
-      store2 = copy_model (store1);
-
-      sorter = get_random_string_sorter ();
-
-      s1 = gtk_sort_list_model_new (G_LIST_MODEL (store1), sorter);
-      s2 = gtk_sort_list_model_new (G_LIST_MODEL (store2), sorter);
-
-      for (j = 0; j < 20; j++)
-        {
-          char *string = g_strdup_printf ("%d", g_random_int_range (0, 100000));
-          GtkStringObject *obj = gtk_string_object_new (string);
-          guint pos1 = g_random_int_range (0, g_list_model_get_n_items (store1) + 1);
-          guint pos2 = g_random_int_range (0, g_list_model_get_n_items (store2) + 1);
-
-          g_list_store_insert (G_LIST_STORE (store1), pos1, obj);
-          g_list_store_insert (G_LIST_STORE (store2), pos2, obj);
-
-          g_object_unref (obj);
-          g_free (string);
-
-          assert_model_equal (G_LIST_MODEL (s1), G_LIST_MODEL (s2));
-        }
-
-      g_object_unref (s1);
-      g_object_unref (s2);
-
-      g_object_unref (sorter);
-      g_object_unref (store1);
-      g_object_unref (store2);
-    }
-}
-
-int
-main (int argc, char *argv[])
-{
-  g_test_init (&argc, &argv, NULL);
-  setlocale (LC_ALL, "C");
-
-  g_test_add_func ("/sortlistmodel/two-sorters", test_two_sorters);
-  g_test_add_func ("/sortlistmodel/sort-twice", test_sort_twice);
-  g_test_add_func ("/sortlistmodel/stable-sort", test_stable_sort);
-  g_test_add_func ("/sortlistmodel/insert-random", test_insert_random);
-
-  return g_test_run ();
-}

testsuite/gtk/timsort.c

@@ -1,159 +0,0 @@
-/*
- * Copyright © 2020 Benjamin Otte
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library. If not, see <http://www.gnu.org/licenses/>.
- */
-
-#include <locale.h>
-
-#include <gtk/gtk.h>
-
-#include "gtk/gtktimsortprivate.h"
-
-#define assert_sort_equal(a, b, size, n) \
-  g_assert_cmpmem (a, sizeof (size) * n, b, sizeof (size) * n)
-
-static int
-compare_int (gconstpointer a,
-             gconstpointer b,
-             gpointer      unused)
-{
-  int ia = *(const int *) a;
-  int ib = *(const int *) b;
-
-  return ia < ib ? -1 : (ia > ib);
-}
-
-G_GNUC_UNUSED static void
-dump (int *a,
-      gsize n)
-{
-  gsize i;
-
-  for (i = 0; i < n; i++)
-    {
-      if (i)
-        g_print(", ");
-      g_print ("%d", a[i]);
-    }
-  g_print ("\n");
-}
-
-static void
-run_comparison (gpointer         a,
-                gsize            n,
-                gsize            element_size,
-                GCompareDataFunc compare_func,
-                gpointer         data)
-{
-  gint64 start, mid, end;
-  gpointer b;
-
-  b = g_memdup (a, element_size * n);
-
-  start = g_get_monotonic_time ();
-  gtk_tim_sort (a, n, element_size, compare_func, data);
-  mid = g_get_monotonic_time ();
-  g_qsort_with_data (b, n, element_size, compare_func, data);
-  end = g_get_monotonic_time ();
-
-  g_test_message ("%zu items in %ldus vs %ldus (%ld%%)", n, mid - start, end - mid, 100 * (mid - start) / MAX (1, end - mid));
-  assert_sort_equal (a, b, int, n);
-
-  g_free (b);
-}
-
-static void
-test_integers (void)
-{
-  int *a;
-  gsize i, n, run;
-
-  a = g_new (int, 1000);
-
-  for (run = 0; run < 10; run++)
-    {
-      n = g_test_rand_int_range (0, 1000);
-      for (i = 0; i < n; i++)
-        a[i] = g_test_rand_int ();
-
-      run_comparison (a, n, sizeof (int), compare_int, NULL);
-    }
-
-  g_free (a);
-}
-
-static void
-test_integers_runs (void)
-{
-  int *a;
-  gsize i, j, n, run;
-
-  a = g_new (int, 1000);
-
-  for (run = 0; run < 10; run++)
-    {
-      n = g_test_rand_int_range (0, 1000);
-      for (i = 0; i < n; i++)
-        {
-          a[i] = g_test_rand_int ();
-          j = i + g_test_rand_int_range (0, 20);
-          j = MIN (n, j);
-          if (g_test_rand_bit ())
-            {
-              for (i++; i < j; i++)
-                a[i] = a[i - 1] + 1;
-            }
-          else
-            {
-              for (i++; i < j; i++)
-                a[i] = a[i - 1] - 1;
-            }
-        }
-
-      run_comparison (a, n, sizeof (int), compare_int, NULL);
-    }
-
-  g_free (a);
-}
-
-static void
-test_integers_huge (void)
-{
-  int *a;
-  gsize i, n;
-
-  n = g_test_rand_int_range (5 * 1000 * 1000, 10 * 1000 * 1000);
-
-  a = g_new (int, n);
-  for (i = 0; i < n; i++)
-    a[i] = g_test_rand_int ();
-
-  run_comparison (a, n, sizeof (int), compare_int, NULL);
-
-  g_free (a);
-}
-
-int
-main (int argc, char *argv[])
-{
-  g_test_init (&argc, &argv, NULL);
-  setlocale (LC_ALL, "C");
-
-  g_test_add_func ("/timsort/integers", test_integers);
-  g_test_add_func ("/timsort/integers/runs", test_integers_runs);
-  g_test_add_func ("/timsort/integers/huge", test_integers_huge);
-
-  return g_test_run ();
-}