1/*
2 * Copyright © 2018 Benjamin Otte
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: Benjamin Otte <otte@gnome.org>
18 */
19
20#include "config.h"
21
22#include "gtksortlistmodel.h"
23
24#include "gtkbitset.h"
25#include "gtkintl.h"
26#include "gtkprivate.h"
27#include "gtksorterprivate.h"
28#include "timsort/gtktimsortprivate.h"
29
30/* The maximum amount of items to merge for a single merge step
31 *
32 * Making this smaller will result in more steps, which has more overhead and slows
33 * down total sort time.
34 * Making it larger will result in fewer steps, which increases the time taken for
35 * a single step.
36 *
37 * As merges are the most expensive steps, this is essentially a tunable for the
38 * longest time spent in gtk_tim_sort_step().
39 *
40 * Note that this should be reset to 0 when not doing incremental sorting to get
41 * rid of all the overhead.
42 */
43#define GTK_SORT_MAX_MERGE_SIZE (1024)
44
45/* Time we spend in the sort callback before returning to the main loop
46 *
47 * Increasing this number will make the callback take longer and potentially
48 * reduce responsiveness of an application, but will increase the amount of
49 * work done per step. And we emit an ::items-changed() signal after every
50 * step, so if we can avoid that, we recuce the overhead in the list widget
51 * and in turn reduce the total sort time.
52 */
53#define GTK_SORT_STEP_TIME_US (1000) /* 1 millisecond */
54
55/**
56 * GtkSortListModel:
57 *
58 * A `GListModel` that sorts the elements of an underlying model
59 * according to a `GtkSorter`.
60 *
61 * The model is a stable sort. If two items compare equal according
62 * to the sorter, the one that appears first in the original model will
63 * also appear first after sorting.
64 * Note that if you change the sorter, the previous order will have no
65 * influence on the new order. If you want that, consider using a
66 * `GtkMultiSorter` and appending the previous sorter to it.
67 *
68 * The model can be set up to do incremental sorting, so that
69 * sorting long lists doesn't block the UI. See
70 * [method@Gtk.SortListModel.set_incremental] for details.
71 *
72 * `GtkSortListModel` is a generic model and because of that it
73 * cannot take advantage of any external knowledge when sorting.
74 * If you run into performance issues with `GtkSortListModel`,
75 * it is strongly recommended that you write your own sorting list
76 * model.
77 */
78
79enum {
80 PROP_0,
81 PROP_INCREMENTAL,
82 PROP_MODEL,
83 PROP_PENDING,
84 PROP_SORTER,
85 NUM_PROPERTIES
86};
87
88struct _GtkSortListModel
89{
90 GObject parent_instance;
91
92 GListModel *model;
93 GtkSorter *sorter;
94 gboolean incremental;
95
96 GtkTimSort sort; /* ongoing sort operation */
97 guint sort_cb; /* 0 or current ongoing sort callback */
98
99 guint n_items;
100 GtkSortKeys *sort_keys;
101 gsize key_size;
102 gpointer keys;
103 GtkBitset *missing_keys;
104
105 gpointer *positions;
106};
107
108struct _GtkSortListModelClass
109{
110 GObjectClass parent_class;
111};
112
113static GParamSpec *properties[NUM_PROPERTIES] = { NULL, };
114
115static guint
116pos_from_key (GtkSortListModel *self,
117 gpointer key)
118{
119 guint pos = ((char *) key - (char *) self->keys) / self->key_size;
120
121 g_assert (pos < self->n_items);
122
123 return pos;
124}
125
126static gpointer
127key_from_pos (GtkSortListModel *self,
128 guint pos)
129{
130 return (char *) self->keys + self->key_size * pos;
131}
132
133static GType
134gtk_sort_list_model_get_item_type (GListModel *list)
135{
136 return G_TYPE_OBJECT;
137}
138
139static guint
140gtk_sort_list_model_get_n_items (GListModel *list)
141{
142 GtkSortListModel *self = GTK_SORT_LIST_MODEL (ptr: list);
143
144 if (self->model == NULL)
145 return 0;
146
147 return g_list_model_get_n_items (list: self->model);
148}
149
150static gpointer
151gtk_sort_list_model_get_item (GListModel *list,
152 guint position)
153{
154 GtkSortListModel *self = GTK_SORT_LIST_MODEL (ptr: list);
155
156 if (self->model == NULL)
157 return NULL;
158
159 if (position >= self->n_items)
160 return NULL;
161
162 if (self->positions)
163 position = pos_from_key (self, key: self->positions[position]);
164
165 return g_list_model_get_item (list: self->model, position);
166}
167
168static void
169gtk_sort_list_model_model_init (GListModelInterface *iface)
170{
171 iface->get_item_type = gtk_sort_list_model_get_item_type;
172 iface->get_n_items = gtk_sort_list_model_get_n_items;
173 iface->get_item = gtk_sort_list_model_get_item;
174}
175
176G_DEFINE_TYPE_WITH_CODE (GtkSortListModel, gtk_sort_list_model, G_TYPE_OBJECT,
177 G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_sort_list_model_model_init))
178
179static gboolean
180gtk_sort_list_model_is_sorting (GtkSortListModel *self)
181{
182 return self->sort_cb != 0;
183}
184
185static void
186gtk_sort_list_model_stop_sorting (GtkSortListModel *self,
187 gsize *runs)
188{
189 if (self->sort_cb == 0)
190 {
191 if (runs)
192 {
193 runs[0] = self->n_items;
194 runs[1] = 0;
195 }
196 return;
197 }
198
199 if (runs)
200 gtk_tim_sort_get_runs (self: &self->sort, runs);
201 gtk_tim_sort_finish (self: &self->sort);
202 g_clear_handle_id (&self->sort_cb, g_source_remove);
203
204 g_object_notify_by_pspec (G_OBJECT (self), pspec: properties[PROP_PENDING]);
205}
206
207static gboolean
208gtk_sort_list_model_sort_step (GtkSortListModel *self,
209 gboolean finish,
210 guint *out_position,
211 guint *out_n_items)
212{
213 gint64 end_time = g_get_monotonic_time ();
214 gboolean result = FALSE;
215 GtkTimSortRun change;
216 gpointer *start_change, *end_change;
217
218 end_time += GTK_SORT_STEP_TIME_US;
219
220 if (!gtk_bitset_is_empty (self: self->missing_keys))
221 {
222 GtkBitsetIter iter;
223 guint pos;
224
225 for (gtk_bitset_iter_init_first (iter: &iter, set: self->missing_keys, value: &pos);
226 gtk_bitset_iter_is_valid (iter: &iter);
227 gtk_bitset_iter_next (iter: &iter, value: &pos))
228 {
229 gpointer item = g_list_model_get_item (list: self->model, position: pos);
230 gtk_sort_keys_init_key (self: self->sort_keys, item, key_memory: key_from_pos (self, pos));
231 g_object_unref (object: item);
232
233 if (g_get_monotonic_time () >= end_time && !finish)
234 {
235 gtk_bitset_remove_range_closed (self: self->missing_keys, first: 0, last: pos);
236 *out_position = 0;
237 *out_n_items = 0;
238 return TRUE;
239 }
240 }
241 result = TRUE;
242 gtk_bitset_remove_all (self: self->missing_keys);
243 }
244
245 end_change = self->positions;
246 start_change = self->positions + self->n_items;
247
248 while (gtk_tim_sort_step (self: &self->sort, out_change: &change))
249 {
250 result = TRUE;
251 if (change.len)
252 {
253 start_change = MIN (start_change, (gpointer *) change.base);
254 end_change = MAX (end_change, ((gpointer *) change.base) + change.len);
255 }
256
257 if (g_get_monotonic_time () >= end_time && !finish)
258 break;
259 }
260
261 if (start_change < end_change)
262 {
263 *out_position = start_change - self->positions;
264 *out_n_items = end_change - start_change;
265 }
266 else
267 {
268 *out_position = 0;
269 *out_n_items = 0;
270 }
271
272 return result;
273}
274
275static gboolean
276gtk_sort_list_model_sort_cb (gpointer data)
277{
278 GtkSortListModel *self = data;
279 guint pos, n_items;
280
281 if (gtk_sort_list_model_sort_step (self, FALSE, out_position: &pos, out_n_items: &n_items))
282 {
283 if (n_items)
284 g_list_model_items_changed (list: G_LIST_MODEL (ptr: self), position: pos, removed: n_items, added: n_items);
285 g_object_notify_by_pspec (G_OBJECT (self), pspec: properties[PROP_PENDING]);
286 return G_SOURCE_CONTINUE;
287 }
288
289 gtk_sort_list_model_stop_sorting (self, NULL);
290 return G_SOURCE_REMOVE;
291}
292
293static int
294sort_func (gconstpointer a,
295 gconstpointer b,
296 gpointer data)
297{
298 gpointer *sa = (gpointer *) a;
299 gpointer *sb = (gpointer *) b;
300 int result;
301
302 result = gtk_sort_keys_compare (self: data, a: *sa, b: *sb);
303 if (result)
304 return result;
305
306 return *sa < *sb ? -1 : 1;
307}
308
309static gboolean
310gtk_sort_list_model_start_sorting (GtkSortListModel *self,
311 gsize *runs)
312{
313 g_assert (self->sort_cb == 0);
314
315 gtk_tim_sort_init (self: &self->sort,
316 base: self->positions,
317 size: self->n_items,
318 element_size: sizeof (gpointer),
319 compare_func: sort_func,
320 data: self->sort_keys);
321 if (runs)
322 gtk_tim_sort_set_runs (self: &self->sort, runs);
323 if (self->incremental)
324 gtk_tim_sort_set_max_merge_size (self: &self->sort, GTK_SORT_MAX_MERGE_SIZE);
325
326 if (!self->incremental)
327 return FALSE;
328
329 self->sort_cb = g_idle_add (function: gtk_sort_list_model_sort_cb, data: self);
330 g_object_notify_by_pspec (G_OBJECT (self), pspec: properties[PROP_PENDING]);
331 return TRUE;
332}
333
334static void
335gtk_sort_list_model_finish_sorting (GtkSortListModel *self,
336 guint *pos,
337 guint *n_items)
338{
339 gtk_tim_sort_set_max_merge_size (self: &self->sort, max_merge_size: 0);
340
341 gtk_sort_list_model_sort_step (self, TRUE, out_position: pos, out_n_items: n_items);
342 gtk_tim_sort_finish (self: &self->sort);
343
344 gtk_sort_list_model_stop_sorting (self, NULL);
345}
346
347static void
348gtk_sort_list_model_clear_sort_keys (GtkSortListModel *self,
349 guint position,
350 guint n_items)
351{
352 GtkBitsetIter iter;
353 GtkBitset *clear;
354 guint pos;
355
356 if (!gtk_sort_keys_needs_clear_key (self: self->sort_keys))
357 return;
358
359 clear = gtk_bitset_new_range (start: position, n_items);
360 gtk_bitset_subtract (self: clear, other: self->missing_keys);
361
362 for (gtk_bitset_iter_init_first (iter: &iter, set: clear, value: &pos);
363 gtk_bitset_iter_is_valid (iter: &iter);
364 gtk_bitset_iter_next (iter: &iter, value: &pos))
365 {
366 gtk_sort_keys_clear_key (self: self->sort_keys, key_memory: key_from_pos (self, pos));
367 }
368
369 gtk_bitset_unref (self: clear);
370}
371
372static void
373gtk_sort_list_model_clear_keys (GtkSortListModel *self)
374{
375 gtk_sort_list_model_clear_sort_keys (self, position: 0, n_items: self->n_items);
376
377 g_clear_pointer (&self->missing_keys, gtk_bitset_unref);
378 g_clear_pointer (&self->keys, g_free);
379 g_clear_pointer (&self->sort_keys, gtk_sort_keys_unref);
380 self->key_size = 0;
381}
382
383static void
384gtk_sort_list_model_clear_items (GtkSortListModel *self,
385 guint *pos,
386 guint *n_items)
387{
388 gtk_sort_list_model_stop_sorting (self, NULL);
389
390 if (self->sort_keys == NULL)
391 {
392 if (pos || n_items)
393 *pos = *n_items = 0;
394 return;
395 }
396
397 if (pos || n_items)
398 {
399 guint start, end;
400
401 for (start = 0; start < self->n_items; start++)
402 {
403 if (pos_from_key (self, key: self->positions[start]) != + start)
404 break;
405 }
406 for (end = self->n_items; end > start; end--)
407 {
408 if (pos_from_key (self, key: self->positions[end - 1]) != end - 1)
409 break;
410 }
411
412 *n_items = end - start;
413 if (*n_items == 0)
414 *pos = 0;
415 else
416 *pos = start;
417 }
418
419 g_clear_pointer (&self->positions, g_free);
420
421 gtk_sort_list_model_clear_keys (self);
422}
423
424static gboolean
425gtk_sort_list_model_should_sort (GtkSortListModel *self)
426{
427 return self->sorter != NULL &&
428 self->model != NULL &&
429 gtk_sorter_get_order (self: self->sorter) != GTK_SORTER_ORDER_NONE;
430}
431
432static void
433gtk_sort_list_model_create_keys (GtkSortListModel *self)
434{
435 g_assert (self->keys == NULL);
436 g_assert (self->sort_keys == NULL);
437 g_assert (self->key_size == 0);
438
439 self->sort_keys = gtk_sorter_get_keys (self: self->sorter);
440 self->key_size = gtk_sort_keys_get_key_size (self: self->sort_keys);
441 self->keys = g_malloc_n (n_blocks: self->n_items, n_block_bytes: self->key_size);
442 self->missing_keys = gtk_bitset_new_range (start: 0, n_items: self->n_items);
443}
444
445static void
446gtk_sort_list_model_create_items (GtkSortListModel *self)
447{
448 guint i;
449
450 if (!gtk_sort_list_model_should_sort (self))
451 return;
452
453 g_assert (self->sort_keys == NULL);
454
455 self->positions = g_new (gpointer, self->n_items);
456
457 gtk_sort_list_model_create_keys (self);
458
459 for (i = 0; i < self->n_items; i++)
460 self->positions[i] = key_from_pos (self, pos: i);
461}
462
463/* This realloc()s the arrays but does not set the added values. */
464static void
465gtk_sort_list_model_update_items (GtkSortListModel *self,
466 gsize runs[GTK_TIM_SORT_MAX_PENDING + 1],
467 guint position,
468 guint removed,
469 guint added,
470 guint *unmodified_start,
471 guint *unmodified_end)
472{
473 guint i, n_items, valid;
474 guint run_index, valid_run, valid_run_end, run_end;
475 guint start, end;
476 gpointer *old_keys;
477
478 n_items = self->n_items;
479 start = n_items;
480 end = n_items;
481
482 /* first, move the keys over */
483 old_keys = self->keys;
484 gtk_sort_list_model_clear_sort_keys (self, position, n_items: removed);
485
486 if (removed > added)
487 {
488 memmove (dest: key_from_pos (self, pos: position + added),
489 src: key_from_pos (self, pos: position + removed),
490 n: self->key_size * (n_items - position - removed));
491 self->keys = g_realloc_n (mem: self->keys, n_blocks: n_items - removed + added, n_block_bytes: self->key_size);
492 }
493 else if (removed < added)
494 {
495 self->keys = g_realloc_n (mem: self->keys, n_blocks: n_items - removed + added, n_block_bytes: self->key_size);
496 memmove (dest: key_from_pos (self, pos: position + added),
497 src: key_from_pos (self, pos: position + removed),
498 n: self->key_size * (n_items - position - removed));
499 }
500
501 /* then, update the positions */
502 valid = 0;
503 valid_run = 0;
504 valid_run_end = 0;
505 run_index = 0;
506 run_end = 0;
507 for (i = 0; i < n_items;)
508 {
509 if (runs[run_index] == 0)
510 {
511 run_end = n_items;
512 valid_run_end = G_MAXUINT;
513 }
514 else
515 {
516 run_end += runs[run_index++];
517 }
518
519 for (; i < run_end; i++)
520 {
521 guint pos = ((char *) self->positions[i] - (char *) old_keys) / self->key_size;
522
523 if (pos >= position + removed)
524 pos = pos - removed + added;
525 else if (pos >= position)
526 {
527 start = MIN (start, valid);
528 end = n_items - i - 1;
529 continue;
530 }
531
532 self->positions[valid] = key_from_pos (self, pos);
533 valid++;
534 }
535
536 if (valid_run_end < valid)
537 {
538 runs[valid_run++] = valid - valid_run_end;
539 valid_run_end = valid;
540 }
541 }
542 g_assert (i == n_items);
543 g_assert (valid == n_items - removed);
544 runs[valid_run] = 0;
545
546 self->positions = g_renew (gpointer, self->positions, n_items - removed + added);
547
548 if (self->missing_keys)
549 {
550 gtk_bitset_splice (self: self->missing_keys, position, removed, added);
551 gtk_bitset_add_range (self: self->missing_keys, start: position, n_items: added);
552 }
553
554 self->n_items = n_items - removed + added;
555
556 for (i = 0; i < added; i++)
557 {
558 self->positions[self->n_items - added + i] = key_from_pos (self, pos: position + i);
559 }
560
561 *unmodified_start = start;
562 *unmodified_end = end;
563}
564
565static void
566gtk_sort_list_model_items_changed_cb (GListModel *model,
567 guint position,
568 guint removed,
569 guint added,
570 GtkSortListModel *self)
571{
572 gsize runs[GTK_TIM_SORT_MAX_PENDING + 1];
573 guint i, n_items, start, end;
574 gboolean was_sorting;
575
576 if (removed == 0 && added == 0)
577 return;
578
579 if (!gtk_sort_list_model_should_sort (self))
580 {
581 self->n_items = self->n_items - removed + added;
582 g_list_model_items_changed (list: G_LIST_MODEL (ptr: self), position, removed, added);
583 return;
584 }
585
586 was_sorting = gtk_sort_list_model_is_sorting (self);
587 gtk_sort_list_model_stop_sorting (self, runs);
588
589 gtk_sort_list_model_update_items (self, runs, position, removed, added, unmodified_start: &start, unmodified_end: &end);
590
591 if (added > 0)
592 {
593 if (gtk_sort_list_model_start_sorting (self, runs))
594 {
595 end = 0;
596 }
597 else
598 {
599 guint pos, n;
600 gtk_sort_list_model_finish_sorting (self, pos: &pos, n_items: &n);
601 if (n)
602 start = MIN (start, pos);
603 /* find first item that was added */
604 for (i = 0; i < end; i++)
605 {
606 pos = pos_from_key (self, key: self->positions[self->n_items - i - 1]);
607 if (pos >= position && pos < position + added)
608 {
609 end = i;
610 break;
611 }
612 }
613 }
614 }
615 else
616 {
617 if (was_sorting)
618 gtk_sort_list_model_start_sorting (self, runs);
619 }
620
621 n_items = self->n_items - start - end;
622 g_list_model_items_changed (list: G_LIST_MODEL (ptr: self), position: start, removed: n_items - added + removed, added: n_items);
623}
624
625static void
626gtk_sort_list_model_set_property (GObject *object,
627 guint prop_id,
628 const GValue *value,
629 GParamSpec *pspec)
630{
631 GtkSortListModel *self = GTK_SORT_LIST_MODEL (ptr: object);
632
633 switch (prop_id)
634 {
635 case PROP_INCREMENTAL:
636 gtk_sort_list_model_set_incremental (self, incremental: g_value_get_boolean (value));
637 break;
638
639 case PROP_MODEL:
640 gtk_sort_list_model_set_model (self, model: g_value_get_object (value));
641 break;
642
643 case PROP_SORTER:
644 gtk_sort_list_model_set_sorter (self, sorter: g_value_get_object (value));
645 break;
646
647 default:
648 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
649 break;
650 }
651}
652
653static void
654gtk_sort_list_model_get_property (GObject *object,
655 guint prop_id,
656 GValue *value,
657 GParamSpec *pspec)
658{
659 GtkSortListModel *self = GTK_SORT_LIST_MODEL (ptr: object);
660
661 switch (prop_id)
662 {
663 case PROP_INCREMENTAL:
664 g_value_set_boolean (value, v_boolean: self->incremental);
665 break;
666
667 case PROP_MODEL:
668 g_value_set_object (value, v_object: self->model);
669 break;
670
671 case PROP_PENDING:
672 g_value_set_uint (value, v_uint: gtk_sort_list_model_get_pending (self));
673 break;
674
675 case PROP_SORTER:
676 g_value_set_object (value, v_object: self->sorter);
677 break;
678
679 default:
680 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
681 break;
682 }
683}
684
685static void
686gtk_sort_list_model_sorter_changed_cb (GtkSorter *sorter,
687 int change,
688 GtkSortListModel *self)
689{
690 guint pos, n_items;
691
692 if (gtk_sort_list_model_should_sort (self))
693 {
694 gtk_sort_list_model_stop_sorting (self, NULL);
695
696 if (self->sort_keys == NULL)
697 {
698 gtk_sort_list_model_create_items (self);
699 }
700 else
701 {
702 GtkSortKeys *new_keys = gtk_sorter_get_keys (self: sorter);
703
704 if (!gtk_sort_keys_is_compatible (self: new_keys, other: self->sort_keys))
705 {
706 char *old_keys = self->keys;
707 gsize old_key_size = self->key_size;
708 guint i;
709
710 gtk_sort_list_model_clear_keys (self);
711 gtk_sort_list_model_create_keys (self);
712
713 for (i = 0; i < self->n_items; i++)
714 self->positions[i] = key_from_pos (self, pos: ((char *) self->positions[i] - old_keys) / old_key_size);
715
716 gtk_sort_keys_unref (self: new_keys);
717 }
718 else
719 {
720 gtk_sort_keys_unref (self: self->sort_keys);
721 self->sort_keys = new_keys;
722 }
723 }
724
725 if (gtk_sort_list_model_start_sorting (self, NULL))
726 pos = n_items = 0;
727 else
728 gtk_sort_list_model_finish_sorting (self, pos: &pos, n_items: &n_items);
729 }
730 else
731 {
732 gtk_sort_list_model_clear_items (self, pos: &pos, n_items: &n_items);
733 }
734
735 if (n_items > 0)
736 g_list_model_items_changed (list: G_LIST_MODEL (ptr: self), position: pos, removed: n_items, added: n_items);
737}
738
739static void
740gtk_sort_list_model_clear_model (GtkSortListModel *self)
741{
742 if (self->model == NULL)
743 return;
744
745 g_signal_handlers_disconnect_by_func (self->model, gtk_sort_list_model_items_changed_cb, self);
746 g_clear_object (&self->model);
747 gtk_sort_list_model_clear_items (self, NULL, NULL);
748 self->n_items = 0;
749}
750
751static void
752gtk_sort_list_model_clear_sorter (GtkSortListModel *self)
753{
754 if (self->sorter == NULL)
755 return;
756
757 g_signal_handlers_disconnect_by_func (self->sorter, gtk_sort_list_model_sorter_changed_cb, self);
758 g_clear_object (&self->sorter);
759}
760
761static void
762gtk_sort_list_model_dispose (GObject *object)
763{
764 GtkSortListModel *self = GTK_SORT_LIST_MODEL (ptr: object);
765
766 gtk_sort_list_model_clear_model (self);
767 gtk_sort_list_model_clear_sorter (self);
768
769 G_OBJECT_CLASS (gtk_sort_list_model_parent_class)->dispose (object);
770};
771
772static void
773gtk_sort_list_model_class_init (GtkSortListModelClass *class)
774{
775 GObjectClass *gobject_class = G_OBJECT_CLASS (class);
776
777 gobject_class->set_property = gtk_sort_list_model_set_property;
778 gobject_class->get_property = gtk_sort_list_model_get_property;
779 gobject_class->dispose = gtk_sort_list_model_dispose;
780
781 /**
782 * GtkSortListModel:incremental: (attributes org.gtk.Property.get=gtk_sort_list_model_get_incremental org.gtk.Property.set=gtk_sort_list_model_set_incremental)
783 *
784 * If the model should sort items incrementally.
785 */
786 properties[PROP_INCREMENTAL] =
787 g_param_spec_boolean (name: "incremental",
788 P_("Incremental"),
789 P_("Sort items incrementally"),
790 FALSE,
791 GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
792
793 /**
794 * GtkSortListModel:model: (attributes org.gtk.Property.get=gtk_sort_list_model_get_model org.gtk.Property.set=gtk_sort_list_model_set_model)
795 *
796 * The model being sorted.
797 */
798 properties[PROP_MODEL] =
799 g_param_spec_object (name: "model",
800 P_("Model"),
801 P_("The model being sorted"),
802 G_TYPE_LIST_MODEL,
803 GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
804
805 /**
806 * GtkSortListModel:pending: (attributes org.gtk.Property.get=gtk_sort_list_model_get_pending)
807 *
808 * Estimate of unsorted items remaining.
809 */
810 properties[PROP_PENDING] =
811 g_param_spec_uint (name: "pending",
812 P_("Pending"),
813 P_("Estimate of unsorted items remaining"),
814 minimum: 0, G_MAXUINT, default_value: 0,
815 GTK_PARAM_READABLE | G_PARAM_EXPLICIT_NOTIFY);
816
817 /**
818 * GtkSortListModel:sorter: (attributes org.gtk.Property.get=gtk_sort_list_model_get_sorter org.gtk.Property.set=gtk_sort_list_model_set_sorter)
819 *
820 * The sorter for this model.
821 */
822 properties[PROP_SORTER] =
823 g_param_spec_object (name: "sorter",
824 P_("Sorter"),
825 P_("The sorter for this model"),
826 GTK_TYPE_SORTER,
827 GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
828
829 g_object_class_install_properties (oclass: gobject_class, n_pspecs: NUM_PROPERTIES, pspecs: properties);
830}
831
832static void
833gtk_sort_list_model_init (GtkSortListModel *self)
834{
835}
836
837/**
838 * gtk_sort_list_model_new:
839 * @model: (nullable) (transfer full): the model to sort
840 * @sorter: (nullable) (transfer full): the `GtkSorter` to sort @model with,
841 *
842 * Creates a new sort list model that uses the @sorter to sort @model.
843 *
844 * Returns: a new `GtkSortListModel`
845 */
846GtkSortListModel *
847gtk_sort_list_model_new (GListModel *model,
848 GtkSorter *sorter)
849{
850 GtkSortListModel *result;
851
852 g_return_val_if_fail (model == NULL || G_IS_LIST_MODEL (model), NULL);
853 g_return_val_if_fail (sorter == NULL || GTK_IS_SORTER (sorter), NULL);
854
855 result = g_object_new (GTK_TYPE_SORT_LIST_MODEL,
856 first_property_name: "model", model,
857 "sorter", sorter,
858 NULL);
859
860 /* consume the references */
861 g_clear_object (&model);
862 g_clear_object (&sorter);
863
864 return result;
865}
866
867/**
868 * gtk_sort_list_model_set_model: (attributes org.gtk.Method.set_property=model)
869 * @self: a `GtkSortListModel`
870 * @model: (nullable): The model to be sorted
871 *
872 * Sets the model to be sorted.
873 *
874 * The @model's item type must conform to the item type of @self.
875 */
876void
877gtk_sort_list_model_set_model (GtkSortListModel *self,
878 GListModel *model)
879{
880 guint removed;
881
882 g_return_if_fail (GTK_IS_SORT_LIST_MODEL (self));
883 g_return_if_fail (model == NULL || G_IS_LIST_MODEL (model));
884
885 if (self->model == model)
886 return;
887
888 removed = g_list_model_get_n_items (list: G_LIST_MODEL (ptr: self));
889 gtk_sort_list_model_clear_model (self);
890
891 if (model)
892 {
893 guint ignore1, ignore2;
894
895 self->model = g_object_ref (model);
896 self->n_items = g_list_model_get_n_items (list: model);
897 g_signal_connect (model, "items-changed", G_CALLBACK (gtk_sort_list_model_items_changed_cb), self);
898
899 if (gtk_sort_list_model_should_sort (self))
900 {
901 gtk_sort_list_model_create_items (self);
902 if (!gtk_sort_list_model_start_sorting (self, NULL))
903 gtk_sort_list_model_finish_sorting (self, pos: &ignore1, n_items: &ignore2);
904 }
905 }
906
907 if (removed > 0 || self->n_items > 0)
908 g_list_model_items_changed (list: G_LIST_MODEL (ptr: self), position: 0, removed, added: self->n_items);
909
910 g_object_notify_by_pspec (G_OBJECT (self), pspec: properties[PROP_MODEL]);
911}
912
913/**
914 * gtk_sort_list_model_get_model: (attributes org.gtk.Method.get_property=model)
915 * @self: a `GtkSortListModel`
916 *
917 * Gets the model currently sorted or %NULL if none.
918 *
919 * Returns: (nullable) (transfer none): The model that gets sorted
920 */
921GListModel *
922gtk_sort_list_model_get_model (GtkSortListModel *self)
923{
924 g_return_val_if_fail (GTK_IS_SORT_LIST_MODEL (self), NULL);
925
926 return self->model;
927}
928
929/**
930 * gtk_sort_list_model_set_sorter: (attributes org.gtk.Method.set_property=sorter)
931 * @self: a `GtkSortListModel`
932 * @sorter: (nullable): the `GtkSorter` to sort @model with
933 *
934 * Sets a new sorter on @self.
935 */
936void
937gtk_sort_list_model_set_sorter (GtkSortListModel *self,
938 GtkSorter *sorter)
939{
940 g_return_if_fail (GTK_IS_SORT_LIST_MODEL (self));
941 g_return_if_fail (sorter == NULL || GTK_IS_SORTER (sorter));
942
943 gtk_sort_list_model_clear_sorter (self);
944
945 if (sorter)
946 {
947 self->sorter = g_object_ref (sorter);
948 g_signal_connect (sorter, "changed", G_CALLBACK (gtk_sort_list_model_sorter_changed_cb), self);
949 }
950
951 gtk_sort_list_model_sorter_changed_cb (sorter, change: GTK_SORTER_CHANGE_DIFFERENT, self);
952
953 g_object_notify_by_pspec (G_OBJECT (self), pspec: properties[PROP_SORTER]);
954}
955
956/**
957 * gtk_sort_list_model_get_sorter: (attributes org.gtk.Method.get_property=sorter)
958 * @self: a `GtkSortListModel`
959 *
960 * Gets the sorter that is used to sort @self.
961 *
962 * Returns: (nullable) (transfer none): the sorter of #self
963 */
964GtkSorter *
965gtk_sort_list_model_get_sorter (GtkSortListModel *self)
966{
967 g_return_val_if_fail (GTK_IS_SORT_LIST_MODEL (self), NULL);
968
969 return self->sorter;
970}
971
972/**
973 * gtk_sort_list_model_set_incremental: (attributes org.gtk.Method.set_property=incremental)
974 * @self: a `GtkSortListModel`
975 * @incremental: %TRUE to sort incrementally
976 *
977 * Sets the sort model to do an incremental sort.
978 *
979 * When incremental sorting is enabled, the `GtkSortListModel` will not do
980 * a complete sort immediately, but will instead queue an idle handler that
981 * incrementally sorts the items towards their correct position. This of
982 * course means that items do not instantly appear in the right place. It
983 * also means that the total sorting time is a lot slower.
984 *
985 * When your filter blocks the UI while sorting, you might consider
986 * turning this on. Depending on your model and sorters, this may become
987 * interesting around 10,000 to 100,000 items.
988 *
989 * By default, incremental sorting is disabled.
990 *
991 * See [method@Gtk.SortListModel.get_pending] for progress information
992 * about an ongoing incremental sorting operation.
993 */
994void
995gtk_sort_list_model_set_incremental (GtkSortListModel *self,
996 gboolean incremental)
997{
998 g_return_if_fail (GTK_IS_SORT_LIST_MODEL (self));
999
1000 if (self->incremental == incremental)
1001 return;
1002
1003 self->incremental = incremental;
1004
1005 if (!incremental && gtk_sort_list_model_is_sorting (self))
1006 {
1007 guint pos, n_items;
1008
1009 gtk_sort_list_model_finish_sorting (self, pos: &pos, n_items: &n_items);
1010 if (n_items)
1011 g_list_model_items_changed (list: G_LIST_MODEL (ptr: self), position: pos, removed: n_items, added: n_items);
1012 }
1013
1014 g_object_notify_by_pspec (G_OBJECT (self), pspec: properties[PROP_INCREMENTAL]);
1015}
1016
1017/**
1018 * gtk_sort_list_model_get_incremental: (attributes org.gtk.Method.get_property=incremental)
1019 * @self: a `GtkSortListModel`
1020 *
1021 * Returns whether incremental sorting is enabled.
1022 *
1023 * See [method@Gtk.SortListModel.set_incremental].
1024 *
1025 * Returns: %TRUE if incremental sorting is enabled
1026 */
1027gboolean
1028gtk_sort_list_model_get_incremental (GtkSortListModel *self)
1029{
1030 g_return_val_if_fail (GTK_IS_SORT_LIST_MODEL (self), FALSE);
1031
1032 return self->incremental;
1033}
1034
1035/**
1036 * gtk_sort_list_model_get_pending: (attributes org.gtk.Method.get_property=pending)
1037 * @self: a `GtkSortListModel`
1038 *
1039 * Estimates progress of an ongoing sorting operation.
1040 *
1041 * The estimate is the number of items that would still need to be
1042 * sorted to finish the sorting operation if this was a linear
1043 * algorithm. So this number is not related to how many items are
1044 * already correctly sorted.
1045 *
1046 * If you want to estimate the progress, you can use code like this:
1047 * ```c
1048 * pending = gtk_sort_list_model_get_pending (self);
1049 * model = gtk_sort_list_model_get_model (self);
1050 * progress = 1.0 - pending / (double) MAX (1, g_list_model_get_n_items (model));
1051 * ```
1052 *
1053 * If no sort operation is ongoing - in particular when
1054 * [property@Gtk.SortListModel:incremental] is %FALSE - this
1055 * function returns 0.
1056 *
1057 * Returns: a progress estimate of remaining items to sort
1058 */
1059guint
1060gtk_sort_list_model_get_pending (GtkSortListModel *self)
1061{
1062 g_return_val_if_fail (GTK_IS_SORT_LIST_MODEL (self), FALSE);
1063
1064 if (self->sort_cb == 0)
1065 return 0;
1066
1067 /* We do a random guess that 50% of time is spent generating keys
1068 * and the other 50% is spent actually sorting.
1069 *
1070 * This is of course massively wrong, but it depends on the sorter
1071 * in use, and estimating this correctly is hard, so this will have
1072 * to be good enough.
1073 */
1074 if (!gtk_bitset_is_empty (self: self->missing_keys))
1075 {
1076 return (self->n_items + gtk_bitset_get_size (self: self->missing_keys)) / 2;
1077 }
1078 else
1079 {
1080 return (self->n_items - gtk_tim_sort_get_progress (self: &self->sort)) / 2;
1081 }
1082}
1083
1084

source code of gtk/gtk/gtksortlistmodel.c