1/*
2 * Copyright © 2019 Matthias Clasen
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
16 *
17 * Authors: Matthias Clasen <mclasen@redhat.com>
18 */
19
20#include "config.h"
21
22#include "gtktreelistrowsorter.h"
23
24#include "gtktreelistmodel.h"
25
26#include "gtkintl.h"
27#include "gtksorterprivate.h"
28#include "gtktypebuiltins.h"
29
30/**
31 * GtkTreeListRowSorter:
32 *
33 * `GtkTreeListRowSorter` is a special-purpose sorter that will apply a given
34 * sorter to the levels in a tree.
35 *
36 * Here is an example for setting up a column view with a tree model and
37 * a `GtkTreeListSorter`:
38 *
39 * ```c
40 * column_sorter = gtk_column_view_get_sorter (view);
41 * sorter = gtk_tree_list_row_sorter_new (g_object_ref (column_sorter));
42 * sort_model = gtk_sort_list_model_new (tree_model, sorter);
43 * selection = gtk_single_selection_new (sort_model);
44 * gtk_column_view_set_model (view, G_LIST_MODEL (selection));
45 * ```
46 */
47
48struct _GtkTreeListRowSorter
49{
50 GtkSorter parent_instance;
51
52 GtkSorter *sorter;
53};
54
55enum {
56 PROP_0,
57 PROP_SORTER,
58 NUM_PROPERTIES
59};
60
61static GParamSpec *properties[NUM_PROPERTIES] = { NULL, };
62
63G_DEFINE_TYPE (GtkTreeListRowSorter, gtk_tree_list_row_sorter, GTK_TYPE_SORTER)
64
65#define MAX_KEY_DEPTH (8)
66
67/* our key is a gpointer[MAX_KEY_DEPTH] and contains:
68 *
69 * key[0] != NULL:
70 * The depth of the item is <= MAX_KEY_DEPTH so we can put the keys
71 * inline. This is the key for the ancestor at depth 0.
72 *
73 * key[0] == NULL && key[1] != NULL:
74 * The depth of the item is > MAX_KEY_DEPTH so it had to be allocated.
75 * key[1] contains this allocated and NULL-terminated array.
76 *
77 * key[0] == NULL && key[1] == NULL:
78 * The item is not a TreeListRow. To break ties, we put the item in key[2] to
79 * allow a direct compare.
80 */
81typedef struct _GtkTreeListRowSortKeys GtkTreeListRowSortKeys;
82typedef struct _GtkTreeListRowCacheKey GtkTreeListRowCacheKey;
83struct _GtkTreeListRowSortKeys
84{
85 GtkSortKeys keys;
86
87 GtkSortKeys *sort_keys;
88 GHashTable *cached_keys;
89};
90
91struct _GtkTreeListRowCacheKey
92{
93 GtkTreeListRow *row;
94 guint ref_count;
95};
96
97static GtkTreeListRowCacheKey *
98cache_key_from_key (GtkTreeListRowSortKeys *self,
99 gpointer key)
100{
101 if (self->sort_keys == NULL)
102 return key;
103
104 return (GtkTreeListRowCacheKey *) ((char *) key + GTK_SORT_KEYS_ALIGN (gtk_sort_keys_get_key_size (self->sort_keys), G_ALIGNOF (GtkTreeListRowCacheKey)));
105}
106
107static void
108gtk_tree_list_row_sort_keys_free (GtkSortKeys *keys)
109{
110 GtkTreeListRowSortKeys *self = (GtkTreeListRowSortKeys *) keys;
111
112 g_assert (g_hash_table_size (self->cached_keys) == 0);
113 g_hash_table_unref (hash_table: self->cached_keys);
114 if (self->sort_keys)
115 gtk_sort_keys_unref (self: self->sort_keys);
116 g_slice_free (GtkTreeListRowSortKeys, self);
117}
118
119static inline gboolean
120unpack (gpointer *key,
121 gpointer **out_keys,
122 gsize *out_max_size)
123{
124 if (key[0])
125 {
126 *out_keys = key;
127 *out_max_size = MAX_KEY_DEPTH;
128 return TRUE;
129 }
130 else if (key[1])
131 {
132 *out_keys = (gpointer *) key[1];
133 *out_max_size = G_MAXSIZE;
134 return TRUE;
135 }
136 else
137 {
138 return FALSE;
139 }
140}
141
142static int
143gtk_tree_list_row_sort_keys_compare (gconstpointer a,
144 gconstpointer b,
145 gpointer data)
146{
147 GtkTreeListRowSortKeys *self = (GtkTreeListRowSortKeys *) data;
148 gpointer *keysa = (gpointer *) a;
149 gpointer *keysb = (gpointer *) b;
150 gsize sizea, sizeb;
151 gboolean resa, resb;
152 gsize i;
153 GtkOrdering result;
154
155 resa = unpack (key: keysa, out_keys: &keysa, out_max_size: &sizea);
156 resb = unpack (key: keysb, out_keys: &keysb, out_max_size: &sizeb);
157 if (!resa)
158 return resb ? GTK_ORDERING_LARGER : (keysa[2] < keysb[2] ? GTK_ORDERING_SMALLER :
159 (keysb[2] > keysa[2] ? GTK_ORDERING_LARGER : GTK_ORDERING_EQUAL));
160 else if (!resb)
161 return GTK_ORDERING_SMALLER;
162
163 for (i = 0; i < MIN (sizea, sizeb); i++)
164 {
165 if (keysa[i] == keysb[i])
166 {
167 if (keysa[i] == NULL)
168 return GTK_ORDERING_EQUAL;
169 continue;
170 }
171 else if (keysa[i] == NULL)
172 return GTK_ORDERING_SMALLER;
173 else if (keysb[i] == NULL)
174 return GTK_ORDERING_LARGER;
175
176 if (self->sort_keys)
177 result = gtk_sort_keys_compare (self: self->sort_keys, a: keysa[i], b: keysb[i]);
178 else
179 result = GTK_ORDERING_EQUAL;
180
181 if (result == GTK_ORDERING_EQUAL)
182 {
183 /* We must break ties here because if a ever gets a child,
184 * it would need to go right in between a and b. */
185 GtkTreeListRowCacheKey *cachea = cache_key_from_key (self, key: keysa[i]);
186 GtkTreeListRowCacheKey *cacheb = cache_key_from_key (self, key: keysb[i]);
187 if (gtk_tree_list_row_get_position (self: cachea->row) < gtk_tree_list_row_get_position (self: cacheb->row))
188 result = GTK_ORDERING_SMALLER;
189 else
190 result = GTK_ORDERING_LARGER;
191 }
192 return result;
193 }
194
195 if (sizea < sizeb)
196 return GTK_ORDERING_SMALLER;
197 else if (sizea > sizeb)
198 return GTK_ORDERING_LARGER;
199 else
200 return GTK_ORDERING_EQUAL;
201}
202
203static gboolean
204gtk_tree_list_row_sort_keys_is_compatible (GtkSortKeys *keys,
205 GtkSortKeys *other)
206{
207 GtkTreeListRowSortKeys *self = (GtkTreeListRowSortKeys *) keys;
208 GtkTreeListRowSortKeys *compare;
209
210 /* FIXME https://gitlab.gnome.org/GNOME/gtk/-/issues/3228 */
211 return FALSE;
212
213 if (keys->klass != other->klass)
214 return FALSE;
215
216 compare = (GtkTreeListRowSortKeys *) other;
217
218 if (self->sort_keys && compare->sort_keys)
219 return gtk_sort_keys_is_compatible (self: self->sort_keys, other: compare->sort_keys);
220 else
221 return self->sort_keys == compare->sort_keys;
222}
223
224static gpointer
225gtk_tree_list_row_sort_keys_ref_key (GtkTreeListRowSortKeys *self,
226 GtkTreeListRow *row)
227{
228 GtkTreeListRowCacheKey *cache_key;
229 gpointer key;
230
231 key = g_hash_table_lookup (hash_table: self->cached_keys, key: row);
232 if (key)
233 {
234 cache_key = cache_key_from_key (self, key);
235 cache_key->ref_count++;
236 return key;
237 }
238
239 if (self->sort_keys)
240 key = g_malloc (GTK_SORT_KEYS_ALIGN (gtk_sort_keys_get_key_size (self->sort_keys), G_ALIGNOF (GtkTreeListRowCacheKey))
241 + sizeof (GtkTreeListRowCacheKey));
242 else
243 key = g_malloc (n_bytes: sizeof (GtkTreeListRowCacheKey));
244 cache_key = cache_key_from_key (self, key);
245 cache_key->row = g_object_ref (row);
246 cache_key->ref_count = 1;
247 if (self->sort_keys)
248 {
249 gpointer item = gtk_tree_list_row_get_item (self: row);
250 gtk_sort_keys_init_key (self: self->sort_keys, item, key_memory: key);
251 g_object_unref (object: item);
252 }
253
254 g_hash_table_insert (hash_table: self->cached_keys, key: row, value: key);
255 return key;
256}
257
258static void
259gtk_tree_list_row_sort_keys_unref_key (GtkTreeListRowSortKeys *self,
260 gpointer key)
261{
262 GtkTreeListRowCacheKey *cache_key = cache_key_from_key (self, key);
263
264 cache_key->ref_count--;
265 if (cache_key->ref_count > 0)
266 return;
267
268 if (self->sort_keys)
269 gtk_sort_keys_clear_key (self: self->sort_keys, key_memory: key);
270
271 g_hash_table_remove (hash_table: self->cached_keys, key: cache_key->row);
272 g_object_unref (object: cache_key->row);
273 g_free (mem: key);
274}
275
276static void
277gtk_tree_list_row_sort_keys_init_key (GtkSortKeys *keys,
278 gpointer item,
279 gpointer key_memory)
280{
281 GtkTreeListRowSortKeys *self = (GtkTreeListRowSortKeys *) keys;
282 gpointer *key = (gpointer *) key_memory;
283 GtkTreeListRow *row, *parent;
284 guint i, depth;
285
286 if (!GTK_IS_TREE_LIST_ROW (ptr: item))
287 {
288 key[0] = NULL;
289 key[1] = NULL;
290 key[2] = item;
291 return;
292 }
293
294 row = GTK_TREE_LIST_ROW (ptr: item);
295 depth = gtk_tree_list_row_get_depth (self: row) + 1;
296 if (depth > MAX_KEY_DEPTH)
297 {
298 key[0] = NULL;
299 key[1] = g_new (gpointer, depth + 1);
300 key = key[1];
301 key[depth] = NULL;
302 }
303 else if (depth < MAX_KEY_DEPTH)
304 {
305 key[depth] = NULL;
306 }
307
308 g_object_ref (row);
309 for (i = depth; i-- > 0; )
310 {
311 key[i] = gtk_tree_list_row_sort_keys_ref_key (self, row);
312 parent = gtk_tree_list_row_get_parent (self: row);
313 g_object_unref (object: row);
314 row = parent;
315 }
316 g_assert (row == NULL);
317}
318
319static void
320gtk_tree_list_row_sort_keys_clear_key (GtkSortKeys *keys,
321 gpointer key_memory)
322{
323 GtkTreeListRowSortKeys *self = (GtkTreeListRowSortKeys *) keys;
324 gpointer *key = (gpointer *) key_memory;
325 gsize i, max;
326
327 if (!unpack (key, out_keys: &key, out_max_size: &max))
328 return;
329
330 for (i = 0; i < max && key[i] != NULL; i++)
331 gtk_tree_list_row_sort_keys_unref_key (self, key: key[i]);
332
333 if (key[0] == NULL)
334 g_free (mem: key[1]);
335}
336
337static const GtkSortKeysClass GTK_TREE_LIST_ROW_SORT_KEYS_CLASS =
338{
339 gtk_tree_list_row_sort_keys_free,
340 gtk_tree_list_row_sort_keys_compare,
341 gtk_tree_list_row_sort_keys_is_compatible,
342 gtk_tree_list_row_sort_keys_init_key,
343 gtk_tree_list_row_sort_keys_clear_key,
344};
345
346static GtkSortKeys *
347gtk_tree_list_row_sort_keys_new (GtkTreeListRowSorter *self)
348{
349 GtkTreeListRowSortKeys *result;
350
351 result = gtk_sort_keys_new (GtkTreeListRowSortKeys,
352 &GTK_TREE_LIST_ROW_SORT_KEYS_CLASS,
353 sizeof (gpointer[MAX_KEY_DEPTH]),
354 sizeof (gpointer[MAX_KEY_DEPTH]));
355
356 if (self->sorter)
357 result->sort_keys = gtk_sorter_get_keys (self: self->sorter);
358 result->cached_keys = g_hash_table_new (NULL, NULL);
359
360 return (GtkSortKeys *) result;
361}
362
363static GtkOrdering
364gtk_tree_list_row_sorter_compare (GtkSorter *sorter,
365 gpointer item1,
366 gpointer item2)
367{
368 GtkTreeListRowSorter *self = GTK_TREE_LIST_ROW_SORTER (ptr: sorter);
369 GtkTreeListRow *r1, *r2;
370 GtkTreeListRow *p1, *p2;
371 guint d1, d2;
372 GtkOrdering result = GTK_ORDERING_EQUAL;
373
374 /* break ties here so we really are a total order */
375 if (!GTK_IS_TREE_LIST_ROW (ptr: item1))
376 return GTK_IS_TREE_LIST_ROW (ptr: item2) ? GTK_ORDERING_LARGER : (item1 < item2 ? GTK_ORDERING_SMALLER : GTK_ORDERING_LARGER);
377 else if (!GTK_IS_TREE_LIST_ROW (ptr: item2))
378 return GTK_ORDERING_SMALLER;
379
380 r1 = GTK_TREE_LIST_ROW (ptr: item1);
381 r2 = GTK_TREE_LIST_ROW (ptr: item2);
382
383 g_object_ref (r1);
384 g_object_ref (r2);
385
386 d1 = gtk_tree_list_row_get_depth (self: r1);
387 d2 = gtk_tree_list_row_get_depth (self: r2);
388
389 /* First, get to the same depth */
390 while (d1 > d2)
391 {
392 p1 = gtk_tree_list_row_get_parent (self: r1);
393 g_object_unref (object: r1);
394 r1 = p1;
395 d1--;
396 result = GTK_ORDERING_LARGER;
397 }
398 while (d2 > d1)
399 {
400 p2 = gtk_tree_list_row_get_parent (self: r2);
401 g_object_unref (object: r2);
402 r2 = p2;
403 d2--;
404 result = GTK_ORDERING_SMALLER;
405 }
406
407 /* Now walk up until we find a common parent */
408 if (r1 != r2)
409 {
410 while (TRUE)
411 {
412 p1 = gtk_tree_list_row_get_parent (self: r1);
413 p2 = gtk_tree_list_row_get_parent (self: r2);
414 if (p1 == p2)
415 {
416 gpointer obj1 = gtk_tree_list_row_get_item (self: r1);
417 gpointer obj2 = gtk_tree_list_row_get_item (self: r2);
418
419 if (self->sorter == NULL)
420 result = GTK_ORDERING_EQUAL;
421 else
422 result = gtk_sorter_compare (self: self->sorter, item1: obj1, item2: obj2);
423
424 /* We must break ties here because if r1 ever gets a child,
425 * it would need to go right in between r1 and r2. */
426 if (result == GTK_ORDERING_EQUAL)
427 {
428 if (gtk_tree_list_row_get_position (self: r1) < gtk_tree_list_row_get_position (self: r2))
429 result = GTK_ORDERING_SMALLER;
430 else
431 result = GTK_ORDERING_LARGER;
432 }
433
434 g_object_unref (object: obj1);
435 g_object_unref (object: obj2);
436
437 break;
438 }
439 else
440 {
441 g_object_unref (object: r1);
442 r1 = p1;
443 g_object_unref (object: r2);
444 r2 = p2;
445 }
446 }
447 }
448
449 g_object_unref (object: r1);
450 g_object_unref (object: r2);
451
452 return result;
453}
454
455static GtkSorterOrder
456gtk_tree_list_row_sorter_get_order (GtkSorter *sorter)
457{
458 /* Must be a total order, because we need an exact position where new items go */
459 return GTK_SORTER_ORDER_TOTAL;
460}
461
462static void
463propagate_changed (GtkSorter *sorter,
464 GtkSorterChange change,
465 GtkTreeListRowSorter *self)
466{
467 gtk_sorter_changed_with_keys (self: GTK_SORTER (ptr: self),
468 change,
469 keys: gtk_tree_list_row_sort_keys_new (self));
470}
471
472static void
473gtk_tree_list_row_sorter_dispose (GObject *object)
474{
475 GtkTreeListRowSorter *self = GTK_TREE_LIST_ROW_SORTER (ptr: object);
476
477 if (self->sorter)
478 g_signal_handlers_disconnect_by_func (self->sorter, propagate_changed, self);
479 g_clear_object (&self->sorter);
480
481 G_OBJECT_CLASS (gtk_tree_list_row_sorter_parent_class)->dispose (object);
482}
483
484static void
485gtk_tree_list_row_sorter_set_property (GObject *object,
486 guint prop_id,
487 const GValue *value,
488 GParamSpec *pspec)
489{
490 GtkTreeListRowSorter *self = GTK_TREE_LIST_ROW_SORTER (ptr: object);
491
492 switch (prop_id)
493 {
494 case PROP_SORTER:
495 gtk_tree_list_row_sorter_set_sorter (self, sorter: GTK_SORTER (ptr: g_value_get_object (value)));
496 break;
497
498 default:
499 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
500 break;
501 }
502}
503
504static void
505gtk_tree_list_row_sorter_get_property (GObject *object,
506 guint prop_id,
507 GValue *value,
508 GParamSpec *pspec)
509{
510 GtkTreeListRowSorter *self = GTK_TREE_LIST_ROW_SORTER (ptr: object);
511
512 switch (prop_id)
513 {
514 case PROP_SORTER:
515 g_value_set_object (value, v_object: self->sorter);
516 break;
517
518 default:
519 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
520 break;
521 }
522}
523
524static void
525gtk_tree_list_row_sorter_class_init (GtkTreeListRowSorterClass *class)
526{
527 GtkSorterClass *sorter_class = GTK_SORTER_CLASS (ptr: class);
528 GObjectClass *object_class = G_OBJECT_CLASS (class);
529
530 sorter_class->compare = gtk_tree_list_row_sorter_compare;
531 sorter_class->get_order = gtk_tree_list_row_sorter_get_order;
532
533 object_class->dispose = gtk_tree_list_row_sorter_dispose;
534 object_class->set_property = gtk_tree_list_row_sorter_set_property;
535 object_class->get_property = gtk_tree_list_row_sorter_get_property;
536
537 /**
538 * GtkTreeListRowSorter:sorter:
539 *
540 * The underlying sorter
541 */
542 properties[PROP_SORTER] =
543 g_param_spec_object (name: "sorter",
544 P_("Sorter"),
545 P_("The underlying sorter"),
546 GTK_TYPE_SORTER,
547 flags: G_PARAM_READWRITE | G_PARAM_STATIC_STRINGS | G_PARAM_EXPLICIT_NOTIFY);
548
549 g_object_class_install_properties (oclass: object_class, n_pspecs: NUM_PROPERTIES, pspecs: properties);
550}
551
552static void
553gtk_tree_list_row_sorter_init (GtkTreeListRowSorter *self)
554{
555 gtk_sorter_changed_with_keys (self: GTK_SORTER (ptr: self),
556 change: GTK_SORTER_CHANGE_DIFFERENT,
557 keys: gtk_tree_list_row_sort_keys_new (self));
558}
559
560/**
561 * gtk_tree_list_row_sorter_new:
562 * @sorter: (nullable) (transfer full): a `GtkSorter`
563 *
564 * Create a special-purpose sorter that applies the sorting
565 * of @sorter to the levels of a `GtkTreeListModel`.
566 *
567 * Note that this sorter relies on [property@Gtk.TreeListModel:passthrough]
568 * being %FALSE as it can only sort [class@Gtk.TreeListRow]s.
569 *
570 * Returns: a new `GtkTreeListRowSorter`
571 */
572GtkTreeListRowSorter *
573gtk_tree_list_row_sorter_new (GtkSorter *sorter)
574{
575 GtkTreeListRowSorter *result;
576
577 g_return_val_if_fail (sorter == NULL || GTK_IS_SORTER (sorter), NULL);
578
579 result = g_object_new (GTK_TYPE_TREE_LIST_ROW_SORTER,
580 first_property_name: "sorter", sorter,
581 NULL);
582
583 g_clear_object (&sorter);
584
585 return result;
586}
587
588/**
589 * gtk_tree_list_row_sorter_set_sorter:
590 * @self: a `GtkTreeListRowSorter`
591 * @sorter: (nullable) (transfer none): The sorter to use
592 *
593 * Sets the sorter to use for items with the same parent.
594 *
595 * This sorter will be passed the [property@Gtk.TreeListRow:item] of
596 * the tree list rows passed to @self.
597 */
598void
599gtk_tree_list_row_sorter_set_sorter (GtkTreeListRowSorter *self,
600 GtkSorter *sorter)
601{
602 g_return_if_fail (GTK_IS_TREE_LIST_ROW_SORTER (self));
603 g_return_if_fail (sorter == NULL || GTK_IS_SORTER (sorter));
604
605 if (self->sorter == sorter)
606 return;
607
608 if (self->sorter)
609 g_signal_handlers_disconnect_by_func (self->sorter, propagate_changed, self);
610 g_set_object (&self->sorter, sorter);
611 if (self->sorter)
612 g_signal_connect (sorter, "changed", G_CALLBACK (propagate_changed), self);
613
614 gtk_sorter_changed_with_keys (self: GTK_SORTER (ptr: self),
615 change: GTK_SORTER_CHANGE_DIFFERENT,
616 keys: gtk_tree_list_row_sort_keys_new (self));
617
618 g_object_notify_by_pspec (G_OBJECT (self), pspec: properties[PROP_SORTER]);
619}
620
621/**
622 * gtk_tree_list_row_sorter_get_sorter:
623 * @self: a `GtkTreeListRowSorter`
624 *
625 * Returns the sorter used by @self.
626 *
627 * Returns: (transfer none) (nullable): the sorter used
628 */
629GtkSorter *
630gtk_tree_list_row_sorter_get_sorter (GtkTreeListRowSorter *self)
631{
632 g_return_val_if_fail (GTK_IS_TREE_LIST_ROW_SORTER (self), NULL);
633
634 return self->sorter;
635}
636

source code of gtk/gtk/gtktreelistrowsorter.c