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 | |
79 | enum { |
80 | PROP_0, |
81 | PROP_INCREMENTAL, |
82 | PROP_MODEL, |
83 | PROP_PENDING, |
84 | PROP_SORTER, |
85 | NUM_PROPERTIES |
86 | }; |
87 | |
88 | struct _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 | |
108 | struct _GtkSortListModelClass |
109 | { |
110 | GObjectClass parent_class; |
111 | }; |
112 | |
113 | static GParamSpec *properties[NUM_PROPERTIES] = { NULL, }; |
114 | |
115 | static guint |
116 | pos_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 | |
126 | static gpointer |
127 | key_from_pos (GtkSortListModel *self, |
128 | guint pos) |
129 | { |
130 | return (char *) self->keys + self->key_size * pos; |
131 | } |
132 | |
133 | static GType |
134 | gtk_sort_list_model_get_item_type (GListModel *list) |
135 | { |
136 | return G_TYPE_OBJECT; |
137 | } |
138 | |
139 | static guint |
140 | gtk_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 | |
150 | static gpointer |
151 | gtk_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 | |
168 | static void |
169 | gtk_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 | |
176 | G_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 | |
179 | static gboolean |
180 | gtk_sort_list_model_is_sorting (GtkSortListModel *self) |
181 | { |
182 | return self->sort_cb != 0; |
183 | } |
184 | |
185 | static void |
186 | gtk_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 | |
207 | static gboolean |
208 | gtk_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 | |
275 | static gboolean |
276 | gtk_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 | |
293 | static int |
294 | sort_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 | |
309 | static gboolean |
310 | gtk_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 | |
334 | static void |
335 | gtk_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 | |
347 | static void |
348 | gtk_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 | |
372 | static void |
373 | gtk_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 | |
383 | static void |
384 | gtk_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 | |
424 | static gboolean |
425 | gtk_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 | |
432 | static void |
433 | gtk_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 | |
445 | static void |
446 | gtk_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. */ |
464 | static void |
465 | gtk_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 | |
565 | static void |
566 | gtk_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 | |
625 | static void |
626 | gtk_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 | |
653 | static void |
654 | gtk_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 | |
685 | static void |
686 | gtk_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 | |
739 | static void |
740 | gtk_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 | |
751 | static void |
752 | gtk_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 | |
761 | static void |
762 | gtk_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 | |
772 | static void |
773 | gtk_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 | |
832 | static void |
833 | gtk_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 | */ |
846 | GtkSortListModel * |
847 | gtk_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 | */ |
876 | void |
877 | gtk_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 | */ |
921 | GListModel * |
922 | gtk_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 | */ |
936 | void |
937 | gtk_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 | */ |
964 | GtkSorter * |
965 | gtk_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 | */ |
994 | void |
995 | gtk_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 | */ |
1027 | gboolean |
1028 | gtk_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 | */ |
1059 | guint |
1060 | gtk_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 | |