[gtk/wip/otte/sortlistmodel: 5/33] sorter: Introduce GtkSortKeys

[Benjamin Otte <otte src gnome org>]

commit 0941d391268eed07b0deb51b81e76de796e86980
Author: Benjamin Otte <otte redhat com>
Date:   Wed Jul 15 20:17:55 2020 +0200

    sorter: Introduce GtkSortKeys
    
    GtkSortKeys is an immutable struct that can be used to manage "sort
    keys" for items.
    
    Sort keys are memory that is created specifically for sorting. Because
    sorting involves lots of comparisons, it's a good idea to prepare the
    data relevant for sorting in advance and sort on that data.
    
    In measurements with a PropertyExpression on a string sorter, it's about
    ??? faster

 gtk/gtksorter.c          | 153 ++++++++++++++++++++++++++++++++++++++++++++++-
 gtk/gtksorter.h          |   1 +
 gtk/gtksorterprivate.h   |  33 ++++++++++
 gtk/gtksortkeys.c        |  97 ++++++++++++++++++++++++++++++
 gtk/gtksortkeysprivate.h |  95 +++++++++++++++++++++++++++++
 gtk/meson.build          |   1 +
 6 files changed, 378 insertions(+), 2 deletions(-)
---
diff --git a/gtk/gtksorter.c b/gtk/gtksorter.c
index c07340870d..d6c38dd54a 100644
--- a/gtk/gtksorter.c
+++ b/gtk/gtksorter.c
@@ -19,7 +19,7 @@
 
 #include "config.h"
 
-#include "gtksorter.h"
+#include "gtksorterprivate.h"
 
 #include "gtkintl.h"
 #include "gtktypebuiltins.h"
@@ -48,12 +48,26 @@
  * and provide one's own sorter.
  */
 
+typedef struct _GtkSorterPrivate GtkSorterPrivate;
+typedef struct _GtkDefaultSortKeys GtkDefaultSortKeys;
+
+struct _GtkSorterPrivate
+{
+  GtkSortKeys *keys;
+};
+
+struct _GtkDefaultSortKeys
+{
+  GtkSortKeys keys;
+  GtkSorter *sorter;
+};
+
 enum {
   CHANGED,
   LAST_SIGNAL
 };
 
-G_DEFINE_TYPE (GtkSorter, gtk_sorter, G_TYPE_OBJECT)
+G_DEFINE_TYPE_WITH_PRIVATE (GtkSorter, gtk_sorter, G_TYPE_OBJECT)
 
 static guint signals[LAST_SIGNAL] = { 0 };
 
@@ -73,9 +87,24 @@ gtk_sorter_default_get_order (GtkSorter *self)
   return GTK_SORTER_ORDER_PARTIAL;
 }
 
+static void
+gtk_sorter_dispose (GObject *object)
+{
+  GtkSorter *self = GTK_SORTER (object);
+  GtkSorterPrivate *priv = gtk_sorter_get_instance_private (self);
+
+  g_clear_pointer (&priv->keys, gtk_sort_keys_unref);
+
+  G_OBJECT_CLASS (gtk_sorter_parent_class)->dispose (object);
+}
+
 static void
 gtk_sorter_class_init (GtkSorterClass *class)
 {
+  GObjectClass *object_class = G_OBJECT_CLASS (class);
+
+  object_class->dispose = gtk_sorter_dispose;
+
   class->compare = gtk_sorter_default_compare;
   class->get_order = gtk_sorter_default_get_order;
 
@@ -181,6 +210,98 @@ gtk_sorter_get_order (GtkSorter *self)
   return GTK_SORTER_GET_CLASS (self)->get_order (self);
 }
 
+static int
+gtk_default_sort_keys_compare (gconstpointer a,
+                               gconstpointer b,
+                               gpointer      data)
+{
+  GtkDefaultSortKeys *self = data;
+  gpointer *key_a = (gpointer *) a;
+  gpointer *key_b = (gpointer *) b;
+
+  return gtk_sorter_compare (self->sorter, *key_a, *key_b);
+}
+
+static void
+gtk_default_sort_keys_free (GtkSortKeys *keys)
+{
+  GtkDefaultSortKeys *self = (GtkDefaultSortKeys *) keys;
+
+  g_object_unref (self->sorter);
+
+  g_slice_free (GtkDefaultSortKeys, self);
+}
+
+static gboolean
+gtk_default_sort_keys_is_compatible (GtkSortKeys *keys,
+                                     GtkSortKeys *other)
+{
+  if (keys->klass != other->klass)
+    return FALSE;
+
+  return TRUE;
+}
+
+static void
+gtk_default_sort_keys_init_key (GtkSortKeys *self,
+                                gpointer     item,
+                                gpointer     key_memory)
+{
+  gpointer *key = (gpointer *) key_memory;
+
+  *key = g_object_ref (item);
+}
+
+static void
+gtk_default_sort_keys_clear_key (GtkSortKeys *self,
+                                 gpointer     key_memory)
+{
+  gpointer *key = (gpointer *) key_memory;
+
+  g_object_unref (*key);
+}
+
+static const GtkSortKeysClass GTK_DEFAULT_SORT_KEYS_CLASS = 
+{
+  gtk_default_sort_keys_free,
+  gtk_default_sort_keys_compare,
+  gtk_default_sort_keys_is_compatible,
+  gtk_default_sort_keys_init_key,
+  gtk_default_sort_keys_clear_key,
+};
+
+/*<private>
+ * gtk_sorter_get_keys:
+ * @self: a #GtkSorter
+ *
+ * Gets a #GtkSortKeys that can be used as an alternative to
+ * @self for faster sorting.
+ *
+ * The sort keys can change every time #GtkSorter::changed is emitted.
+ * When the keys change, you should redo all comparisons with the new
+ * keys.  
+ * When gtk_sort_keys_is_compatible() for the old and new keys returns
+ * %TRUE, you can reuse keys you generated previously.
+ *
+ * Returns: (transfer full): the sort keys to sort with
+ **/
+GtkSortKeys *
+gtk_sorter_get_keys (GtkSorter *self)
+{
+  GtkSorterPrivate *priv = gtk_sorter_get_instance_private (self);
+  GtkDefaultSortKeys *fallback;
+
+  g_return_val_if_fail (GTK_IS_SORTER (self), NULL);
+
+  if (priv->keys)
+    return gtk_sort_keys_ref (priv->keys);
+
+  fallback = gtk_sort_keys_new (GtkDefaultSortKeys, &GTK_DEFAULT_SORT_KEYS_CLASS, sizeof (gpointer), sizeof 
(gpointer));
+  fallback->sorter = g_object_ref (self);
+
+  return (GtkSortKeys *) fallback;
+}
+
 /**
  * gtk_sorter_changed:
  * @self: a #GtkSorter
@@ -205,3 +326,31 @@ gtk_sorter_changed (GtkSorter       *self,
 
   g_signal_emit (self, signals[CHANGED], 0, change);
 }
+
+/*<private>
+ * gtk_sorter_changed_with_keys
+ * @self: a #GtkSorter
+ * @change: How the sorter changed
+ * @keys: (not nullable) (transfer full): New keys to use
+ *
+ * Updates the sorter's keys to @keys and then calls gtk_sorter_changed().
+ * If you do not want to update the keys, call that function instead.
+ *
+ * This function should also be called in your_sorter_init() to initialize
+ * the keys to use with your sorter.
+ */
+void
+gtk_sorter_changed_with_keys (GtkSorter       *self,
+                              GtkSorterChange  change,
+                              GtkSortKeys     *keys)
+{
+  GtkSorterPrivate *priv = gtk_sorter_get_instance_private (self);
+
+  g_return_if_fail (GTK_IS_SORTER (self));
+  g_return_if_fail (keys != NULL);
+
+  g_clear_pointer (&priv->keys, gtk_sort_keys_unref);
+  priv->keys = keys;
+
+  gtk_sorter_changed (self, change);
+}
diff --git a/gtk/gtksorter.h b/gtk/gtksorter.h
index 9dc78f20db..108c3cb8c9 100644
--- a/gtk/gtksorter.h
+++ b/gtk/gtksorter.h
@@ -115,6 +115,7 @@ GDK_AVAILABLE_IN_ALL
 void                    gtk_sorter_changed                      (GtkSorter              *self,
                                                                  GtkSorterChange         change);
 
+
 G_END_DECLS
 
 #endif /* __GTK_SORTER_H__ */
diff --git a/gtk/gtksorterprivate.h b/gtk/gtksorterprivate.h
new file mode 100644
index 0000000000..2bbe2950d0
--- /dev/null
+++ b/gtk/gtksorterprivate.h
@@ -0,0 +1,33 @@
+/*
+ * 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.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/>.
+ */
+
+#ifndef __GTK_SORTER_PRIVATE_H__
+#define __GTK_SORTER_PRIVATE_H__
+
+#include <gtk/gtksorter.h>
+
+#include "gtk/gtksortkeysprivate.h"
+
+GtkSortKeys *           gtk_sorter_get_keys                     (GtkSorter              *self);
+
+void                    gtk_sorter_changed_with_keys            (GtkSorter              *self,
+                                                                 GtkSorterChange         change,
+                                                                 GtkSortKeys            *keys);
+
+
+#endif /* __GTK_SORTER_PRIVATE_H__ */
+
diff --git a/gtk/gtksortkeys.c b/gtk/gtksortkeys.c
new file mode 100644
index 0000000000..d99939fe1b
--- /dev/null
+++ b/gtk/gtksortkeys.c
@@ -0,0 +1,97 @@
+/*
+ * 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.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/>.
+ */
+
+#include "config.h"
+
+#include "gtksortkeysprivate.h"
+
+#include "gtkcssstyleprivate.h"
+#include "gtkstyleproviderprivate.h"
+
+GtkSortKeys *
+gtk_sort_keys_alloc (const GtkSortKeysClass *klass,
+                     gsize                   size,
+                     gsize                   key_size,
+                     gsize                   key_align)
+{
+  GtkSortKeys *self;
+
+  g_return_val_if_fail (key_align > 0, NULL);
+
+  self = g_slice_alloc0 (size);
+
+  self->klass = klass;
+  self->ref_count = 1;
+
+  self->key_size = key_size;
+  self->key_align = key_align;
+
+  return self;
+}
+
+GtkSortKeys *
+gtk_sort_keys_ref (GtkSortKeys *self)
+{
+  self->ref_count += 1;
+
+  return self;
+}
+
+void
+gtk_sort_keys_unref (GtkSortKeys *self)
+{
+  self->ref_count -= 1;
+  if (self->ref_count > 0)
+    return;
+
+  self->klass->free (self);
+}
+
+gsize
+gtk_sort_keys_get_key_size (GtkSortKeys *self)
+{
+  return self->key_size;
+}
+
+gsize
+gtk_sort_keys_get_key_align (GtkSortKeys *self)
+{
+  return self->key_align;
+}
+
+GCompareDataFunc
+gtk_sort_keys_get_key_compare_func (GtkSortKeys *self)
+{
+  return self->klass->key_compare;
+}
+
+gboolean
+gtk_sort_keys_is_compatible (GtkSortKeys *self,
+                             GtkSortKeys *other)
+{
+  if (self == other)
+    return TRUE;
+
+  return self->klass->is_compatible (self, other);
+}
+
+gboolean
+gtk_sort_keys_needs_clear_key (GtkSortKeys *self)
+{
+  return self->klass->clear_key != NULL;
+}
+
diff --git a/gtk/gtksortkeysprivate.h b/gtk/gtksortkeysprivate.h
new file mode 100644
index 0000000000..d213ffb43b
--- /dev/null
+++ b/gtk/gtksortkeysprivate.h
@@ -0,0 +1,95 @@
+/*
+ * 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.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/>.
+ */
+
+#ifndef __GTK_SORT_KEYS_PRIVATE_H__
+#define __GTK_SORT_KEYS_PRIVATE_H__
+
+#include <gdk/gdk.h>
+#include <gtk/gtkenums.h>
+#include <gtk/gtksorter.h>
+
+typedef struct _GtkSortKeys GtkSortKeys;
+typedef struct _GtkSortKeysClass GtkSortKeysClass;
+
+struct _GtkSortKeys
+{
+  const GtkSortKeysClass *klass;
+  gint ref_count;
+
+  gsize key_size;
+  gsize key_align; /* must be power of 2 */
+};
+
+struct _GtkSortKeysClass
+{
+  void                  (* free)                                (GtkSortKeys            *self);
+
+  GCompareDataFunc key_compare;
+
+  gboolean              (* is_compatible)                       (GtkSortKeys            *self,
+                                                                 GtkSortKeys            *other);
+
+  void                  (* init_key)                            (GtkSortKeys            *self,
+                                                                 gpointer                item,
+                                                                 gpointer                key_memory);
+  void                  (* clear_key)                           (GtkSortKeys            *self,
+                                                                 gpointer                key_memory);
+};
+
+GtkSortKeys *           gtk_sort_keys_alloc                     (const GtkSortKeysClass *klass,
+                                                                 gsize                   size,
+                                                                 gsize                   key_size,
+                                                                 gsize                   key_align);
+#define gtk_sort_keys_new(_name, _klass, _key_size, _key_align) \
+    ((_name *) gtk_sort_keys_alloc ((_klass), sizeof (_name), (_key_size), (_key_align)))
+GtkSortKeys *           gtk_sort_keys_ref                       (GtkSortKeys            *self);
+void                    gtk_sort_keys_unref                     (GtkSortKeys            *self);
+
+gsize                   gtk_sort_keys_get_key_size              (GtkSortKeys            *self);
+gsize                   gtk_sort_keys_get_key_align             (GtkSortKeys            *self);
+GCompareDataFunc        gtk_sort_keys_get_key_compare_func      (GtkSortKeys            *self);
+gboolean                gtk_sort_keys_is_compatible             (GtkSortKeys            *self,
+                                                                 GtkSortKeys            *other);
+gboolean                gtk_sort_keys_needs_clear_key           (GtkSortKeys            *self);
+
+#define GTK_SORT_KEYS_ALIGN(_size,_align) (((_size) + (_align) - 1) & ~((_align) - 1))
+static inline int
+gtk_sort_keys_compare (GtkSortKeys *self,
+                       gconstpointer a,
+                       gconstpointer b)
+{
+  return self->klass->key_compare (a, b, self);
+}
+                       
+static inline void
+gtk_sort_keys_init_key (GtkSortKeys *self,
+                        gpointer       item,
+                        gpointer       key_memory)
+{
+  self->klass->init_key (self, item, key_memory);
+}
+
+static inline void
+gtk_sort_keys_clear_key (GtkSortKeys *self,
+                         gpointer       key_memory)
+{
+  if (self->klass->clear_key)
+    self->klass->clear_key (self, key_memory);
+}
+
+#endif /* __GTK_SORT_KEYS_PRIVATE_H__ */
+
diff --git a/gtk/meson.build b/gtk/meson.build
index 689814ebbe..0d77686708 100644
--- a/gtk/meson.build
+++ b/gtk/meson.build
@@ -133,6 +133,7 @@ gtk_private_sources = files([
   'gtksearchengine.c',
   'gtksearchenginemodel.c',
   'gtksizerequestcache.c',
+  'gtksortkeys.c',
   'gtkstyleanimation.c',
   'gtkstylecascade.c',
   'gtkstyleproperty.c',