[gtk/wip/otte/sortlistmodel: 10/33] treelistrowsorter: Implement GtkSortKeys

[Benjamin Otte <otte src gnome org>]

commit 26e7a0d0504e30cc7012feadf8d9714492ef44f4
Author: Benjamin Otte <otte redhat com>
Date:   Sun Jul 19 04:58:06 2020 +0200

    treelistrowsorter: Implement GtkSortKeys

 gtk/gtktreelistrowsorter.c | 311 ++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 308 insertions(+), 3 deletions(-)
---
diff --git a/gtk/gtktreelistrowsorter.c b/gtk/gtktreelistrowsorter.c
index 8b1f57eeca..39cb1c6e55 100644
--- a/gtk/gtktreelistrowsorter.c
+++ b/gtk/gtktreelistrowsorter.c
@@ -24,6 +24,7 @@
 #include "gtktreelistmodel.h"
 
 #include "gtkintl.h"
+#include "gtksorterprivate.h"
 #include "gtktypebuiltins.h"
 
 /**
@@ -64,6 +65,301 @@ static GParamSpec *properties[NUM_PROPERTIES] = { NULL, };
 
 G_DEFINE_TYPE (GtkTreeListRowSorter, gtk_tree_list_row_sorter, GTK_TYPE_SORTER)
 
+#define MAX_KEY_DEPTH (8)
+
+/* our key is a gpointer[MAX_KEY_DEPTH] and contains:
+ *
+ * key[0] != NULL:
+ * The depth of the item is <= MAX_KEY_DEPTH so we can put the keys
+ * inline. This is the key for the ancestor at depth 0.
+ *
+ * key[0] == NULL && key[1] != NULL:
+ * The depth of the item is > MAX_KEY_DEPTH so it had to be allocated.
+ * key[1] contains this allocated and NULL-terminated array.
+ *
+ * key[0] == NULL && key[1] == NULL:
+ * The item is not a TreeListRow. To break ties, we put the item in key[2] to
+ * allow a direct compare.
+ */
+typedef struct _GtkTreeListRowSortKeys GtkTreeListRowSortKeys;
+typedef struct _GtkTreeListRowCacheKey GtkTreeListRowCacheKey;
+struct _GtkTreeListRowSortKeys
+{
+  GtkSortKeys keys;
+
+  GtkSortKeys *sort_keys;
+  GHashTable *cached_keys;
+};
+
+struct _GtkTreeListRowCacheKey
+{
+  GtkTreeListRow *row;
+  guint ref_count;
+};
+
+static GtkTreeListRowCacheKey *
+cache_key_from_key (GtkTreeListRowSortKeys *self,
+                    gpointer                key)
+{
+  if (self->sort_keys == NULL)
+    return key;
+
+  return (GtkTreeListRowCacheKey *) ((char *) key + GTK_SORT_KEYS_ALIGN (gtk_sort_keys_get_key_size 
(self->sort_keys), G_ALIGNOF (GtkTreeListRowCacheKey)));
+}
+
+static void
+gtk_tree_list_row_sort_keys_free (GtkSortKeys *keys)
+{
+  GtkTreeListRowSortKeys *self = (GtkTreeListRowSortKeys *) keys;
+
+  g_assert (g_hash_table_size (self->cached_keys) == 0);
+  g_hash_table_unref (self->cached_keys);
+  if (self->sort_keys)
+    gtk_sort_keys_unref (self->sort_keys);
+  g_slice_free (GtkTreeListRowSortKeys, self);
+}
+
+static inline gboolean
+unpack (gpointer  *key,
+        gpointer **out_keys,
+        gsize     *out_max_size)
+{
+  if (key[0])
+    {
+      *out_keys = key;
+      *out_max_size = MAX_KEY_DEPTH;
+      return TRUE;
+    }
+  else if (key[1])
+    {
+      *out_keys = (gpointer *) key[1];
+      *out_max_size = G_MAXSIZE;
+      return TRUE;
+    }
+  else
+    {
+      return FALSE;
+    }
+}
+
+static int
+gtk_tree_list_row_sort_keys_compare (gconstpointer a,
+                                     gconstpointer b,
+                                     gpointer      data)
+{
+  GtkTreeListRowSortKeys *self = (GtkTreeListRowSortKeys *) data;
+  gpointer *keysa = (gpointer *) a;
+  gpointer *keysb = (gpointer *) b;
+  gsize sizea, sizeb;
+  gboolean resa, resb;
+  gsize i;
+  GtkOrdering result;
+
+  resa = unpack (keysa, &keysa, &sizea);
+  resb = unpack (keysb, &keysb, &sizeb);
+  if (!resa)
+    return resb ? GTK_ORDERING_LARGER : (keysa[2] < keysb[2] ? GTK_ORDERING_SMALLER : 
+                                        (keysb[2] > keysa[2] ? GTK_ORDERING_LARGER : GTK_ORDERING_EQUAL));
+  else if (!resb)
+    return GTK_ORDERING_SMALLER;
+
+  for (i = 0; i < MIN (sizea, sizeb); i++)
+    {
+      if (keysa[i] == keysb[i])
+        {
+          if (keysa[i] == NULL)
+            return GTK_ORDERING_EQUAL;
+          continue;
+        }
+      else if (keysa[i] == NULL)
+        return GTK_ORDERING_SMALLER;
+      else if (keysb[i] == NULL)
+        return GTK_ORDERING_LARGER;
+
+      if (self->sort_keys)
+        result = gtk_sort_keys_compare (self->sort_keys, keysa[i], keysb[i]);
+      else
+        result = GTK_ORDERING_EQUAL;
+
+      if (result == GTK_ORDERING_EQUAL)
+        {
+          /* We must break ties here because if a ever gets a child,
+           * it would need to go right inbetween a and b. */
+          GtkTreeListRowCacheKey *cachea = cache_key_from_key (self, keysa[i]);
+          GtkTreeListRowCacheKey *cacheb = cache_key_from_key (self, keysb[i]);
+          if (gtk_tree_list_row_get_position (cachea->row) < gtk_tree_list_row_get_position (cacheb->row))
+            result = GTK_ORDERING_SMALLER;
+          else
+            result = GTK_ORDERING_LARGER;
+        }
+      return result;
+    }
+
+  if (sizea < sizeb)
+    return GTK_ORDERING_SMALLER;
+  else if (sizea > sizeb)
+    return GTK_ORDERING_LARGER;
+  else
+    return GTK_ORDERING_EQUAL;
+}
+
+static gboolean
+gtk_tree_list_row_sort_keys_is_compatible (GtkSortKeys *keys,
+                                           GtkSortKeys *other)
+{
+  GtkTreeListRowSortKeys *self = (GtkTreeListRowSortKeys *) keys;
+  GtkTreeListRowSortKeys *compare;
+
+  if (keys->klass != other->klass)
+    return FALSE;
+
+  compare = (GtkTreeListRowSortKeys *) other;
+
+  if (self->sort_keys && compare->sort_keys)
+    return gtk_sort_keys_is_compatible (self->sort_keys, compare->sort_keys);
+  else
+    return self->sort_keys == compare->sort_keys;
+}
+
+static gpointer
+gtk_tree_list_row_sort_keys_ref_key (GtkTreeListRowSortKeys *self,
+                                     GtkTreeListRow         *row)
+{
+  GtkTreeListRowCacheKey *cache_key;
+  gpointer key;
+
+  key = g_hash_table_lookup (self->cached_keys, row);
+  if (key)
+    {
+      cache_key = cache_key_from_key (self, key);
+      cache_key->ref_count++;
+      return key;
+    }
+
+  if (self->sort_keys)
+    key = g_malloc (GTK_SORT_KEYS_ALIGN (gtk_sort_keys_get_key_size (self->sort_keys), G_ALIGNOF 
(GtkTreeListRowCacheKey))
+                    + sizeof (GtkTreeListRowCacheKey));
+  else
+    key = g_malloc (sizeof (GtkTreeListRowCacheKey));
+  cache_key = cache_key_from_key (self, key);
+  cache_key->row = g_object_ref (row);
+  cache_key->ref_count = 1;
+  if (self->sort_keys)
+    {
+      gpointer item = gtk_tree_list_row_get_item (row);
+      gtk_sort_keys_init_key (self->sort_keys, item, key);
+      g_object_unref (item);
+    }
+
+  g_hash_table_insert (self->cached_keys, row, key);
+  return key;
+}
+
+static void
+gtk_tree_list_row_sort_keys_unref_key (GtkTreeListRowSortKeys *self,
+                                       gpointer                key)
+{
+  GtkTreeListRowCacheKey *cache_key = cache_key_from_key (self, key);
+
+  cache_key->ref_count--;
+  if (cache_key->ref_count > 0)
+    return;
+
+  if (self->sort_keys)
+    gtk_sort_keys_clear_key (self->sort_keys, key);
+
+  g_hash_table_remove (self->cached_keys, cache_key->row);
+  g_object_unref (cache_key->row);
+  g_free (key);
+}
+
+static void
+gtk_tree_list_row_sort_keys_init_key (GtkSortKeys *keys,
+                                      gpointer     item,
+                                      gpointer     key_memory)
+{
+  GtkTreeListRowSortKeys *self = (GtkTreeListRowSortKeys *) keys;
+  gpointer *key = (gpointer *) key_memory;
+  GtkTreeListRow *row, *parent;
+  guint i, depth;
+
+  if (!GTK_IS_TREE_LIST_ROW (item))
+    {
+      key[0] = NULL;
+      key[1] = NULL;
+      key[2] = item;
+      return;
+    }
+
+  row = GTK_TREE_LIST_ROW (item);
+  depth = gtk_tree_list_row_get_depth (row) + 1;
+  if (depth > MAX_KEY_DEPTH)
+    {
+      key[0] = NULL;
+      key[1] = g_new (gpointer, depth + 1);
+      key = key[1];
+      key[depth] = NULL;
+    }
+  else if (depth < MAX_KEY_DEPTH)
+    {
+      key[depth] = NULL;
+    }
+
+  g_object_ref (row);
+  for (i = depth; i-- > 0; )
+    {
+      key[i] = gtk_tree_list_row_sort_keys_ref_key (self, row);
+      parent = gtk_tree_list_row_get_parent (row);
+      g_object_unref (row);
+      row = parent;
+    }
+  g_assert (row == NULL);
+}
+
+static void
+gtk_tree_list_row_sort_keys_clear_key (GtkSortKeys *keys,
+                                       gpointer     key_memory)
+{
+  GtkTreeListRowSortKeys *self = (GtkTreeListRowSortKeys *) keys;
+  gpointer *key = (gpointer *) key_memory;
+  gsize i, max;
+
+  if (!unpack (key, &key, &max))
+    return;
+
+  for (i = 0; i < max && key[i] != NULL; i++)
+    gtk_tree_list_row_sort_keys_unref_key (self, key[i]);
+  
+  if (key[0] == NULL)
+    g_free (key[1]);
+}
+
+static const GtkSortKeysClass GTK_TREE_LIST_ROW_SORT_KEYS_CLASS =
+{
+  gtk_tree_list_row_sort_keys_free,
+  gtk_tree_list_row_sort_keys_compare,
+  gtk_tree_list_row_sort_keys_is_compatible,
+  gtk_tree_list_row_sort_keys_init_key,
+  gtk_tree_list_row_sort_keys_clear_key,
+};
+
+static GtkSortKeys *
+gtk_tree_list_row_sort_keys_new (GtkTreeListRowSorter *self)
+{
+  GtkTreeListRowSortKeys *result;
+
+  result = gtk_sort_keys_new (GtkTreeListRowSortKeys,
+                              &GTK_TREE_LIST_ROW_SORT_KEYS_CLASS,
+                              sizeof (gpointer[MAX_KEY_DEPTH]),
+                              sizeof (gpointer[MAX_KEY_DEPTH]));
+
+  if (self->sorter)
+    result->sort_keys = gtk_sort_keys_ref (gtk_sorter_get_keys (self->sorter));
+  result->cached_keys = g_hash_table_new (NULL, NULL);
+
+  return (GtkSortKeys *) result;
+}
+
 static GtkOrdering
 gtk_tree_list_row_sorter_compare (GtkSorter *sorter,
                                   gpointer   item1,
@@ -164,9 +460,13 @@ gtk_tree_list_row_sorter_get_order (GtkSorter *sorter)
 }
 
 static void
-propagate_changed (GtkSorter *sorter, GtkSorterChange change, gpointer data)
+propagate_changed (GtkSorter *sorter,
+                   GtkSorterChange change,
+                   GtkTreeListRowSorter *self)
 {
-  gtk_sorter_changed (GTK_SORTER (data), change);
+  gtk_sorter_changed_with_keys (GTK_SORTER (self),
+                                change,
+                                gtk_tree_list_row_sort_keys_new (self));
 }
 
 static void
@@ -252,6 +552,9 @@ gtk_tree_list_row_sorter_class_init (GtkTreeListRowSorterClass *class)
 static void
 gtk_tree_list_row_sorter_init (GtkTreeListRowSorter *self)
 {
+  gtk_sorter_changed_with_keys (GTK_SORTER (self),
+                                GTK_SORTER_CHANGE_DIFFERENT,
+                                gtk_tree_list_row_sort_keys_new (self));
 }
 
 /**
@@ -308,7 +611,9 @@ gtk_tree_list_row_sorter_set_sorter (GtkTreeListRowSorter *self,
   if (self->sorter)
     g_signal_connect (sorter, "changed", G_CALLBACK (propagate_changed), self);
 
-  gtk_sorter_changed (GTK_SORTER (self), GTK_SORTER_CHANGE_DIFFERENT);
+  gtk_sorter_changed_with_keys (GTK_SORTER (self),
+                                GTK_SORTER_CHANGE_DIFFERENT,
+                                gtk_tree_list_row_sort_keys_new (self));
 
   g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTER]);
 }