Branch data Line data Source code
1 : : /*
2 : : * Copyright 2015 Lars Uebernickel
3 : : * Copyright 2015 Ryan Lortie
4 : : *
5 : : * SPDX-License-Identifier: LGPL-2.1-or-later
6 : : *
7 : : * This library is free software; you can redistribute it and/or
8 : : * modify it under the terms of the GNU Lesser General Public
9 : : * License as published by the Free Software Foundation; either
10 : : * version 2.1 of the License, or (at your option) any later version.
11 : : *
12 : : * This library is distributed in the hope that it will be useful,
13 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : : * Lesser General Public License for more details.
16 : : *
17 : : * You should have received a copy of the GNU Lesser General
18 : : * Public License along with this library; if not, see <http://www.gnu.org/licenses/>.
19 : : *
20 : : * Authors:
21 : : * Lars Uebernickel <lars@uebernic.de>
22 : : * Ryan Lortie <desrt@desrt.ca>
23 : : */
24 : :
25 : : #include "config.h"
26 : :
27 : : #include "gliststore.h"
28 : : #include "glistmodel.h"
29 : :
30 : : /**
31 : : * GListStore:
32 : : *
33 : : * `GListStore` is a simple implementation of [iface@Gio.ListModel] that stores
34 : : * all items in memory.
35 : : *
36 : : * It provides insertions, deletions, and lookups in logarithmic time
37 : : * with a fast path for the common case of iterating the list linearly.
38 : : */
39 : :
40 : : struct _GListStore
41 : : {
42 : : GObject parent_instance;
43 : :
44 : : GType item_type;
45 : : GSequence *items;
46 : :
47 : : /* cache */
48 : : guint last_position;
49 : : GSequenceIter *last_iter;
50 : : gboolean last_position_valid;
51 : : };
52 : :
53 : : enum
54 : : {
55 : : PROP_0,
56 : : PROP_ITEM_TYPE,
57 : : PROP_N_ITEMS,
58 : : N_PROPERTIES
59 : : };
60 : :
61 : : static void g_list_store_iface_init (GListModelInterface *iface);
62 : :
63 : 16722 : G_DEFINE_TYPE_WITH_CODE (GListStore, g_list_store, G_TYPE_OBJECT,
64 : 3 : G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, g_list_store_iface_init));
65 : :
66 : : static GParamSpec *properties[N_PROPERTIES] = { NULL, };
67 : :
68 : : static void
69 : 4098 : g_list_store_items_changed (GListStore *store,
70 : : guint position,
71 : : guint removed,
72 : : guint added)
73 : : {
74 : : /* check if the iter cache may have been invalidated */
75 : 4098 : if (position <= store->last_position)
76 : : {
77 : 69 : store->last_iter = NULL;
78 : 69 : store->last_position = 0;
79 : 69 : store->last_position_valid = FALSE;
80 : 36 : }
81 : :
82 : 4098 : g_list_model_items_changed (G_LIST_MODEL (store), position, removed, added);
83 : 4098 : if (removed != added)
84 : 4086 : g_object_notify_by_pspec (G_OBJECT (store), properties[PROP_N_ITEMS]);
85 : 4098 : }
86 : :
87 : : static void
88 : 35 : g_list_store_dispose (GObject *object)
89 : : {
90 : 35 : GListStore *store = G_LIST_STORE (object);
91 : :
92 : 35 : g_clear_pointer (&store->items, g_sequence_free);
93 : :
94 : 35 : G_OBJECT_CLASS (g_list_store_parent_class)->dispose (object);
95 : 35 : }
96 : :
97 : : static void
98 : 56 : g_list_store_get_property (GObject *object,
99 : : guint property_id,
100 : : GValue *value,
101 : : GParamSpec *pspec)
102 : : {
103 : 56 : GListStore *store = G_LIST_STORE (object);
104 : :
105 : 56 : switch (property_id)
106 : : {
107 : 2 : case PROP_ITEM_TYPE:
108 : 3 : g_value_set_gtype (value, store->item_type);
109 : 3 : break;
110 : :
111 : 27 : case PROP_N_ITEMS:
112 : 53 : g_value_set_uint (value, g_sequence_get_length (store->items));
113 : 53 : break;
114 : :
115 : 0 : default:
116 : 0 : G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
117 : 0 : }
118 : 56 : }
119 : :
120 : : static void
121 : 35 : g_list_store_set_property (GObject *object,
122 : : guint property_id,
123 : : const GValue *value,
124 : : GParamSpec *pspec)
125 : : {
126 : 35 : GListStore *store = G_LIST_STORE (object);
127 : :
128 : 35 : switch (property_id)
129 : : {
130 : 18 : case PROP_ITEM_TYPE: /* construct-only */
131 : 35 : g_assert (g_type_is_a (g_value_get_gtype (value), G_TYPE_OBJECT));
132 : 35 : store->item_type = g_value_get_gtype (value);
133 : 35 : break;
134 : :
135 : 0 : default:
136 : 0 : G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
137 : 0 : }
138 : 35 : }
139 : :
140 : : static void
141 : 6 : g_list_store_class_init (GListStoreClass *klass)
142 : : {
143 : 6 : GObjectClass *object_class = G_OBJECT_CLASS (klass);
144 : :
145 : 6 : object_class->dispose = g_list_store_dispose;
146 : 6 : object_class->get_property = g_list_store_get_property;
147 : 6 : object_class->set_property = g_list_store_set_property;
148 : :
149 : : /**
150 : : * GListStore:item-type:
151 : : *
152 : : * The type of items contained in this list store. Items must be
153 : : * subclasses of #GObject.
154 : : *
155 : : * Since: 2.44
156 : : **/
157 : 6 : properties[PROP_ITEM_TYPE] =
158 : 6 : g_param_spec_gtype ("item-type", NULL, NULL, G_TYPE_OBJECT,
159 : : G_PARAM_CONSTRUCT_ONLY | G_PARAM_READWRITE | G_PARAM_STATIC_STRINGS);
160 : :
161 : : /**
162 : : * GListStore:n-items:
163 : : *
164 : : * The number of items contained in this list store.
165 : : *
166 : : * Since: 2.74
167 : : **/
168 : 6 : properties[PROP_N_ITEMS] =
169 : 6 : g_param_spec_uint ("n-items", NULL, NULL, 0, G_MAXUINT, 0,
170 : : G_PARAM_READABLE | G_PARAM_STATIC_STRINGS);
171 : :
172 : 6 : g_object_class_install_properties (object_class, N_PROPERTIES, properties);
173 : 6 : }
174 : :
175 : : static GType
176 : 2 : g_list_store_get_item_type (GListModel *list)
177 : : {
178 : 2 : GListStore *store = G_LIST_STORE (list);
179 : :
180 : 2 : return store->item_type;
181 : : }
182 : :
183 : : static guint
184 : 74 : g_list_store_get_n_items (GListModel *list)
185 : : {
186 : 74 : GListStore *store = G_LIST_STORE (list);
187 : :
188 : 74 : return g_sequence_get_length (store->items);
189 : : }
190 : :
191 : : static gpointer
192 : 12312 : g_list_store_get_item (GListModel *list,
193 : : guint position)
194 : : {
195 : 12312 : GListStore *store = G_LIST_STORE (list);
196 : 12312 : GSequenceIter *it = NULL;
197 : :
198 : 12312 : if (store->last_position_valid)
199 : : {
200 : 12278 : if (position < G_MAXUINT && store->last_position == position + 1)
201 : 2 : it = g_sequence_iter_prev (store->last_iter);
202 : 12276 : else if (position > 0 && store->last_position == position - 1)
203 : 2108 : it = g_sequence_iter_next (store->last_iter);
204 : 10168 : else if (store->last_position == position)
205 : 6156 : it = store->last_iter;
206 : 6139 : }
207 : :
208 : 12312 : if (it == NULL)
209 : 4046 : it = g_sequence_get_iter_at_pos (store->items, position);
210 : :
211 : 12312 : store->last_iter = it;
212 : 12312 : store->last_position = position;
213 : 12312 : store->last_position_valid = TRUE;
214 : :
215 : 12312 : if (g_sequence_iter_is_end (it))
216 : 26 : return NULL;
217 : : else
218 : 12286 : return g_object_ref (g_sequence_get (it));
219 : 6156 : }
220 : :
221 : : static void
222 : 6 : g_list_store_iface_init (GListModelInterface *iface)
223 : : {
224 : 6 : iface->get_item_type = g_list_store_get_item_type;
225 : 6 : iface->get_n_items = g_list_store_get_n_items;
226 : 6 : iface->get_item = g_list_store_get_item;
227 : 6 : }
228 : :
229 : : static void
230 : 36 : g_list_store_init (GListStore *store)
231 : : {
232 : 36 : store->items = g_sequence_new (g_object_unref);
233 : 36 : store->last_position = 0;
234 : 36 : store->last_position_valid = FALSE;
235 : 36 : }
236 : :
237 : : /**
238 : : * g_list_store_new:
239 : : * @item_type: the #GType of items in the list
240 : : *
241 : : * Creates a new #GListStore with items of type @item_type. @item_type
242 : : * must be a subclass of #GObject.
243 : : *
244 : : * Returns: a new #GListStore
245 : : * Since: 2.44
246 : : */
247 : : GListStore *
248 : 34 : g_list_store_new (GType item_type)
249 : : {
250 : : /* We only allow GObjects as item types right now. This might change
251 : : * in the future.
252 : : */
253 : 34 : g_return_val_if_fail (g_type_is_a (item_type, G_TYPE_OBJECT), NULL);
254 : :
255 : 51 : return g_object_new (G_TYPE_LIST_STORE,
256 : 17 : "item-type", item_type,
257 : : NULL);
258 : 17 : }
259 : :
260 : : /**
261 : : * g_list_store_insert:
262 : : * @store: a #GListStore
263 : : * @position: the position at which to insert the new item
264 : : * @item: (type GObject): the new item
265 : : *
266 : : * Inserts @item into @store at @position. @item must be of type
267 : : * #GListStore:item-type or derived from it. @position must be smaller
268 : : * than the length of the list, or equal to it to append.
269 : : *
270 : : * This function takes a ref on @item.
271 : : *
272 : : * Use g_list_store_splice() to insert multiple items at the same time
273 : : * efficiently.
274 : : *
275 : : * Since: 2.44
276 : : */
277 : : void
278 : 6 : g_list_store_insert (GListStore *store,
279 : : guint position,
280 : : gpointer item)
281 : : {
282 : : GSequenceIter *it;
283 : :
284 : 6 : g_return_if_fail (G_IS_LIST_STORE (store));
285 : 6 : g_return_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type));
286 : 6 : g_return_if_fail (position <= (guint) g_sequence_get_length (store->items));
287 : :
288 : 4 : it = g_sequence_get_iter_at_pos (store->items, position);
289 : 4 : g_sequence_insert_before (it, g_object_ref (item));
290 : :
291 : 4 : g_list_store_items_changed (store, position, 0, 1);
292 : 3 : }
293 : :
294 : : /**
295 : : * g_list_store_insert_sorted:
296 : : * @store: a #GListStore
297 : : * @item: (type GObject): the new item
298 : : * @compare_func: (scope call) (closure user_data): pairwise comparison function for sorting
299 : : * @user_data: user data for @compare_func
300 : : *
301 : : * Inserts @item into @store at a position to be determined by the
302 : : * @compare_func.
303 : : *
304 : : * The list must already be sorted before calling this function or the
305 : : * result is undefined. Usually you would approach this by only ever
306 : : * inserting items by way of this function.
307 : : *
308 : : * This function takes a ref on @item.
309 : : *
310 : : * Returns: the position at which @item was inserted
311 : : *
312 : : * Since: 2.44
313 : : */
314 : : guint
315 : 4002 : g_list_store_insert_sorted (GListStore *store,
316 : : gpointer item,
317 : : GCompareDataFunc compare_func,
318 : : gpointer user_data)
319 : : {
320 : : GSequenceIter *it;
321 : : guint position;
322 : :
323 : 4002 : g_return_val_if_fail (G_IS_LIST_STORE (store), 0);
324 : 4002 : g_return_val_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type), 0);
325 : 4002 : g_return_val_if_fail (compare_func != NULL, 0);
326 : :
327 : 4002 : it = g_sequence_insert_sorted (store->items, g_object_ref (item), compare_func, user_data);
328 : 4002 : position = g_sequence_iter_get_position (it);
329 : :
330 : 4002 : g_list_store_items_changed (store, position, 0, 1);
331 : :
332 : 4002 : return position;
333 : 2001 : }
334 : :
335 : : /**
336 : : * g_list_store_sort:
337 : : * @store: a #GListStore
338 : : * @compare_func: (scope call) (closure user_data): pairwise comparison function for sorting
339 : : * @user_data: user data for @compare_func
340 : : *
341 : : * Sort the items in @store according to @compare_func.
342 : : *
343 : : * Since: 2.46
344 : : */
345 : : void
346 : 6 : g_list_store_sort (GListStore *store,
347 : : GCompareDataFunc compare_func,
348 : : gpointer user_data)
349 : : {
350 : : gint n_items;
351 : :
352 : 6 : g_return_if_fail (G_IS_LIST_STORE (store));
353 : 6 : g_return_if_fail (compare_func != NULL);
354 : :
355 : 6 : g_sequence_sort (store->items, compare_func, user_data);
356 : :
357 : 6 : n_items = g_sequence_get_length (store->items);
358 : 6 : g_list_store_items_changed (store, 0, n_items, n_items);
359 : 3 : }
360 : :
361 : : /**
362 : : * g_list_store_append:
363 : : * @store: a #GListStore
364 : : * @item: (type GObject): the new item
365 : : *
366 : : * Appends @item to @store. @item must be of type #GListStore:item-type.
367 : : *
368 : : * This function takes a ref on @item.
369 : : *
370 : : * Use g_list_store_splice() to append multiple items at the same time
371 : : * efficiently.
372 : : *
373 : : * Since: 2.44
374 : : */
375 : : void
376 : 46 : g_list_store_append (GListStore *store,
377 : : gpointer item)
378 : : {
379 : : guint n_items;
380 : :
381 : 46 : g_return_if_fail (G_IS_LIST_STORE (store));
382 : 46 : g_return_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type));
383 : :
384 : 46 : n_items = g_sequence_get_length (store->items);
385 : 46 : g_sequence_append (store->items, g_object_ref (item));
386 : :
387 : 46 : g_list_store_items_changed (store, n_items, 0, 1);
388 : 23 : }
389 : :
390 : : /**
391 : : * g_list_store_remove:
392 : : * @store: a #GListStore
393 : : * @position: the position of the item that is to be removed
394 : : *
395 : : * Removes the item from @store that is at @position. @position must be
396 : : * smaller than the current length of the list.
397 : : *
398 : : * Use g_list_store_splice() to remove multiple items at the same time
399 : : * efficiently.
400 : : *
401 : : * Since: 2.44
402 : : */
403 : : void
404 : 10 : g_list_store_remove (GListStore *store,
405 : : guint position)
406 : : {
407 : : GSequenceIter *it;
408 : :
409 : 10 : g_return_if_fail (G_IS_LIST_STORE (store));
410 : :
411 : 10 : it = g_sequence_get_iter_at_pos (store->items, position);
412 : 10 : g_return_if_fail (!g_sequence_iter_is_end (it));
413 : :
414 : 6 : g_sequence_remove (it);
415 : 6 : g_list_store_items_changed (store, position, 1, 0);
416 : 5 : }
417 : :
418 : : /**
419 : : * g_list_store_remove_all:
420 : : * @store: a #GListStore
421 : : *
422 : : * Removes all items from @store.
423 : : *
424 : : * Since: 2.44
425 : : */
426 : : void
427 : 6 : g_list_store_remove_all (GListStore *store)
428 : : {
429 : : guint n_items;
430 : :
431 : 6 : g_return_if_fail (G_IS_LIST_STORE (store));
432 : :
433 : 6 : n_items = g_sequence_get_length (store->items);
434 : 6 : if (n_items == 0)
435 : 2 : return;
436 : 6 : g_sequence_remove_range (g_sequence_get_begin_iter (store->items),
437 : 2 : g_sequence_get_end_iter (store->items));
438 : :
439 : 4 : g_list_store_items_changed (store, 0, n_items, 0);
440 : 3 : }
441 : :
442 : : /**
443 : : * g_list_store_splice:
444 : : * @store: a #GListStore
445 : : * @position: the position at which to make the change
446 : : * @n_removals: the number of items to remove
447 : : * @additions: (array length=n_additions) (element-type GObject): the items to add
448 : : * @n_additions: the number of items to add
449 : : *
450 : : * Changes @store by removing @n_removals items and adding @n_additions
451 : : * items to it. @additions must contain @n_additions items of type
452 : : * #GListStore:item-type. %NULL is not permitted.
453 : : *
454 : : * This function is more efficient than g_list_store_insert() and
455 : : * g_list_store_remove(), because it only emits
456 : : * #GListModel::items-changed once for the change.
457 : : *
458 : : * This function takes a ref on each item in @additions.
459 : : *
460 : : * The parameters @position and @n_removals must be correct (ie:
461 : : * @position + @n_removals must be less than or equal to the length of
462 : : * the list at the time this function is called).
463 : : *
464 : : * Since: 2.44
465 : : */
466 : : void
467 : 44 : g_list_store_splice (GListStore *store,
468 : : guint position,
469 : : guint n_removals,
470 : : gpointer *additions,
471 : : guint n_additions)
472 : : {
473 : : GSequenceIter *it;
474 : : guint n_items;
475 : :
476 : 44 : g_return_if_fail (G_IS_LIST_STORE (store));
477 : 44 : g_return_if_fail (position + n_removals >= position); /* overflow */
478 : :
479 : 44 : n_items = g_sequence_get_length (store->items);
480 : 44 : g_return_if_fail (position + n_removals <= n_items);
481 : :
482 : 38 : if (n_removals == 0 && n_additions == 0)
483 : 6 : return;
484 : :
485 : 32 : it = g_sequence_get_iter_at_pos (store->items, position);
486 : :
487 : 32 : if (n_removals)
488 : : {
489 : : GSequenceIter *end;
490 : :
491 : 16 : end = g_sequence_iter_move (it, n_removals);
492 : 16 : g_sequence_remove_range (it, end);
493 : :
494 : 16 : it = end;
495 : 8 : }
496 : :
497 : 32 : if (n_additions)
498 : : {
499 : : guint i;
500 : :
501 : 100 : for (i = 0; i < n_additions; i++)
502 : : {
503 : 76 : if G_UNLIKELY (!g_type_is_a (G_OBJECT_TYPE (additions[i]), store->item_type))
504 : : {
505 : 2 : g_critical ("%s: item %d is a %s instead of a %s. GListStore is now in an undefined state.",
506 : 1 : G_STRFUNC, i, G_OBJECT_TYPE_NAME (additions[i]), g_type_name (store->item_type));
507 : 2 : return;
508 : : }
509 : :
510 : 74 : g_sequence_insert_before (it, g_object_ref (additions[i]));
511 : 37 : }
512 : 12 : }
513 : :
514 : 30 : g_list_store_items_changed (store, position, n_removals, n_additions);
515 : 22 : }
516 : :
517 : : static gboolean
518 : 76 : simple_equal (gconstpointer a,
519 : : gconstpointer b,
520 : : gpointer equal_func)
521 : : {
522 : 76 : return ((GEqualFunc) equal_func) (a, b);
523 : : }
524 : :
525 : : /**
526 : : * g_list_store_find_with_equal_func:
527 : : * @store: a #GListStore
528 : : * @item: (type GObject) (nullable): an item
529 : : * @equal_func: (scope call): A custom equality check function
530 : : * @position: (out) (optional): the first position of @item, if it was found.
531 : : *
532 : : * Looks up the given @item in the list store by looping over the items and
533 : : * comparing them with @equal_func until the first occurrence of @item which
534 : : * matches. If @item was not found, then @position will not be set, and this
535 : : * method will return %FALSE.
536 : : *
537 : : * @item is always passed as second parameter to @equal_func.
538 : : *
539 : : * Since GLib 2.76 it is possible to pass `NULL` for @item.
540 : : *
541 : : * Returns: Whether @store contains @item. If it was found, @position will be
542 : : * set to the position where @item occurred for the first time.
543 : : *
544 : : * Since: 2.64
545 : : */
546 : : gboolean
547 : 30 : g_list_store_find_with_equal_func (GListStore *store,
548 : : gpointer item,
549 : : GEqualFunc equal_func,
550 : : guint *position)
551 : : {
552 : 30 : g_return_val_if_fail (equal_func != NULL, FALSE);
553 : :
554 : 45 : return g_list_store_find_with_equal_func_full (store, item, simple_equal,
555 : 15 : equal_func, position);
556 : 15 : }
557 : :
558 : : /**
559 : : * g_list_store_find_with_equal_func_full:
560 : : * @store: a #GListStore
561 : : * @item: (type GObject) (nullable): an item
562 : : * @equal_func: (scope call) (closure user_data): A custom equality check function
563 : : * @user_data: user data for @equal_func
564 : : * @position: (out) (optional): the first position of @item, if it was found.
565 : : *
566 : : * Like g_list_store_find_with_equal_func() but with an additional @user_data
567 : : * that is passed to @equal_func.
568 : : *
569 : : * @item is always passed as second parameter to @equal_func.
570 : : *
571 : : * Since GLib 2.76 it is possible to pass `NULL` for @item.
572 : : *
573 : : * Returns: Whether @store contains @item. If it was found, @position will be
574 : : * set to the position where @item occurred for the first time.
575 : : *
576 : : * Since: 2.74
577 : : */
578 : : gboolean
579 : 32 : g_list_store_find_with_equal_func_full (GListStore *store,
580 : : gpointer item,
581 : : GEqualFuncFull equal_func,
582 : : gpointer user_data,
583 : : guint *position)
584 : : {
585 : : GSequenceIter *iter, *begin, *end;
586 : :
587 : 32 : g_return_val_if_fail (G_IS_LIST_STORE (store), FALSE);
588 : 32 : g_return_val_if_fail (item == NULL || g_type_is_a (G_OBJECT_TYPE (item), store->item_type),
589 : : FALSE);
590 : 32 : g_return_val_if_fail (equal_func != NULL, FALSE);
591 : :
592 : : /* NOTE: We can't use g_sequence_lookup() or g_sequence_search(), because we
593 : : * can't assume the sequence is sorted. */
594 : 32 : begin = g_sequence_get_begin_iter (store->items);
595 : 32 : end = g_sequence_get_end_iter (store->items);
596 : :
597 : 32 : iter = begin;
598 : 94 : while (iter != end)
599 : : {
600 : : gpointer iter_item;
601 : :
602 : 84 : iter_item = g_sequence_get (iter);
603 : 84 : if (equal_func (iter_item, item, user_data))
604 : : {
605 : 22 : if (position)
606 : 14 : *position = g_sequence_iter_get_position (iter);
607 : 22 : return TRUE;
608 : : }
609 : :
610 : 62 : iter = g_sequence_iter_next (iter);
611 : : }
612 : :
613 : 10 : return FALSE;
614 : 16 : }
615 : :
616 : : /**
617 : : * g_list_store_find:
618 : : * @store: a #GListStore
619 : : * @item: (type GObject): an item
620 : : * @position: (out) (optional): the first position of @item, if it was found.
621 : : *
622 : : * Looks up the given @item in the list store by looping over the items until
623 : : * the first occurrence of @item. If @item was not found, then @position will
624 : : * not be set, and this method will return %FALSE.
625 : : *
626 : : * If you need to compare the two items with a custom comparison function, use
627 : : * g_list_store_find_with_equal_func() with a custom #GEqualFunc instead.
628 : : *
629 : : * Returns: Whether @store contains @item. If it was found, @position will be
630 : : * set to the position where @item occurred for the first time.
631 : : *
632 : : * Since: 2.64
633 : : */
634 : : gboolean
635 : 28 : g_list_store_find (GListStore *store,
636 : : gpointer item,
637 : : guint *position)
638 : : {
639 : 42 : return g_list_store_find_with_equal_func (store,
640 : 14 : item,
641 : : g_direct_equal,
642 : 14 : position);
643 : : }
|
