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 G_DEFINE_TYPE_WITH_CODE (GListStore, g_list_store, G_TYPE_OBJECT,
64 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 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 if (position <= store->last_position)
76 {
77 store->last_iter = NULL;
78 store->last_position = 0;
79 store->last_position_valid = FALSE;
80 }
81
82 g_list_model_items_changed (G_LIST_MODEL (store), position, removed, added);
83 if (removed != added)
84 g_object_notify_by_pspec (G_OBJECT (store), properties[PROP_N_ITEMS]);
85 }
86
87 static void
88 g_list_store_dispose (GObject *object)
89 {
90 GListStore *store = G_LIST_STORE (object);
91
92 g_clear_pointer (&store->items, g_sequence_free);
93
94 G_OBJECT_CLASS (g_list_store_parent_class)->dispose (object);
95 }
96
97 static void
98 g_list_store_get_property (GObject *object,
99 guint property_id,
100 GValue *value,
101 GParamSpec *pspec)
102 {
103 GListStore *store = G_LIST_STORE (object);
104
105 switch (property_id)
106 {
107 case PROP_ITEM_TYPE:
108 g_value_set_gtype (value, store->item_type);
109 break;
110
111 case PROP_N_ITEMS:
112 g_value_set_uint (value, g_sequence_get_length (store->items));
113 break;
114
115 default:
116 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
117 }
118 }
119
120 static void
121 g_list_store_set_property (GObject *object,
122 guint property_id,
123 const GValue *value,
124 GParamSpec *pspec)
125 {
126 GListStore *store = G_LIST_STORE (object);
127
128 switch (property_id)
129 {
130 case PROP_ITEM_TYPE: /* construct-only */
131 g_assert (g_type_is_a (g_value_get_gtype (value), G_TYPE_OBJECT));
132 store->item_type = g_value_get_gtype (value);
133 break;
134
135 default:
136 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
137 }
138 }
139
140 static void
141 g_list_store_class_init (GListStoreClass *klass)
142 {
143 GObjectClass *object_class = G_OBJECT_CLASS (klass);
144
145 object_class->dispose = g_list_store_dispose;
146 object_class->get_property = g_list_store_get_property;
147 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 properties[PROP_ITEM_TYPE] =
158 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 properties[PROP_N_ITEMS] =
169 g_param_spec_uint ("n-items", NULL, NULL, 0, G_MAXUINT, 0,
170 G_PARAM_READABLE | G_PARAM_STATIC_STRINGS);
171
172 g_object_class_install_properties (object_class, N_PROPERTIES, properties);
173 }
174
175 static GType
176 g_list_store_get_item_type (GListModel *list)
177 {
178 GListStore *store = G_LIST_STORE (list);
179
180 return store->item_type;
181 }
182
183 static guint
184 g_list_store_get_n_items (GListModel *list)
185 {
186 GListStore *store = G_LIST_STORE (list);
187
188 return g_sequence_get_length (store->items);
189 }
190
191 static gpointer
192 g_list_store_get_item (GListModel *list,
193 guint position)
194 {
195 GListStore *store = G_LIST_STORE (list);
196 GSequenceIter *it = NULL;
197
198 if (store->last_position_valid)
199 {
200 if (position < G_MAXUINT && store->last_position == position + 1)
201 it = g_sequence_iter_prev (store->last_iter);
202 else if (position > 0 && store->last_position == position - 1)
203 it = g_sequence_iter_next (store->last_iter);
204 else if (store->last_position == position)
205 it = store->last_iter;
206 }
207
208 if (it == NULL)
209 it = g_sequence_get_iter_at_pos (store->items, position);
210
211 store->last_iter = it;
212 store->last_position = position;
213 store->last_position_valid = TRUE;
214
215 if (g_sequence_iter_is_end (it))
216 return NULL;
217 else
218 return g_object_ref (g_sequence_get (it));
219 }
220
221 static void
222 g_list_store_iface_init (GListModelInterface *iface)
223 {
224 iface->get_item_type = g_list_store_get_item_type;
225 iface->get_n_items = g_list_store_get_n_items;
226 iface->get_item = g_list_store_get_item;
227 }
228
229 static void
230 g_list_store_init (GListStore *store)
231 {
232 store->items = g_sequence_new (g_object_unref);
233 store->last_position = 0;
234 store->last_position_valid = FALSE;
235 }
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 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 g_return_val_if_fail (g_type_is_a (item_type, G_TYPE_OBJECT), NULL);
254
255 return g_object_new (G_TYPE_LIST_STORE,
256 "item-type", item_type,
257 NULL);
258 }
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 g_list_store_insert (GListStore *store,
279 guint position,
280 gpointer item)
281 {
282 GSequenceIter *it;
283
284 g_return_if_fail (G_IS_LIST_STORE (store));
285 g_return_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type));
286 g_return_if_fail (position <= (guint) g_sequence_get_length (store->items));
287
288 it = g_sequence_get_iter_at_pos (store->items, position);
289 g_sequence_insert_before (it, g_object_ref (item));
290
291 g_list_store_items_changed (store, position, 0, 1);
292 }
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 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 g_return_val_if_fail (G_IS_LIST_STORE (store), 0);
324 g_return_val_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type), 0);
325 g_return_val_if_fail (compare_func != NULL, 0);
326
327 it = g_sequence_insert_sorted (store->items, g_object_ref (item), compare_func, user_data);
328 position = g_sequence_iter_get_position (it);
329
330 g_list_store_items_changed (store, position, 0, 1);
331
332 return position;
333 }
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 g_list_store_sort (GListStore *store,
347 GCompareDataFunc compare_func,
348 gpointer user_data)
349 {
350 gint n_items;
351
352 g_return_if_fail (G_IS_LIST_STORE (store));
353 g_return_if_fail (compare_func != NULL);
354
355 g_sequence_sort (store->items, compare_func, user_data);
356
357 n_items = g_sequence_get_length (store->items);
358 g_list_store_items_changed (store, 0, n_items, n_items);
359 }
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 g_list_store_append (GListStore *store,
377 gpointer item)
378 {
379 guint n_items;
380
381 g_return_if_fail (G_IS_LIST_STORE (store));
382 g_return_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type));
383
384 n_items = g_sequence_get_length (store->items);
385 g_sequence_append (store->items, g_object_ref (item));
386
387 g_list_store_items_changed (store, n_items, 0, 1);
388 }
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 g_list_store_remove (GListStore *store,
405 guint position)
406 {
407 GSequenceIter *it;
408
409 g_return_if_fail (G_IS_LIST_STORE (store));
410
411 it = g_sequence_get_iter_at_pos (store->items, position);
412 g_return_if_fail (!g_sequence_iter_is_end (it));
413
414 g_sequence_remove (it);
415 g_list_store_items_changed (store, position, 1, 0);
416 }
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 g_list_store_remove_all (GListStore *store)
428 {
429 guint n_items;
430
431 g_return_if_fail (G_IS_LIST_STORE (store));
432
433 n_items = g_sequence_get_length (store->items);
434 g_sequence_remove_range (g_sequence_get_begin_iter (store->items),
435 g_sequence_get_end_iter (store->items));
436
437 g_list_store_items_changed (store, 0, n_items, 0);
438 }
439
440 /**
441 * g_list_store_splice:
442 * @store: a #GListStore
443 * @position: the position at which to make the change
444 * @n_removals: the number of items to remove
445 * @additions: (array length=n_additions) (element-type GObject): the items to add
446 * @n_additions: the number of items to add
447 *
448 * Changes @store by removing @n_removals items and adding @n_additions
449 * items to it. @additions must contain @n_additions items of type
450 * #GListStore:item-type. %NULL is not permitted.
451 *
452 * This function is more efficient than g_list_store_insert() and
453 * g_list_store_remove(), because it only emits
454 * #GListModel::items-changed once for the change.
455 *
456 * This function takes a ref on each item in @additions.
457 *
458 * The parameters @position and @n_removals must be correct (ie:
459 * @position + @n_removals must be less than or equal to the length of
460 * the list at the time this function is called).
461 *
462 * Since: 2.44
463 */
464 void
465 g_list_store_splice (GListStore *store,
466 guint position,
467 guint n_removals,
468 gpointer *additions,
469 guint n_additions)
470 {
471 GSequenceIter *it;
472 guint n_items;
473
474 g_return_if_fail (G_IS_LIST_STORE (store));
475 g_return_if_fail (position + n_removals >= position); /* overflow */
476
477 n_items = g_sequence_get_length (store->items);
478 g_return_if_fail (position + n_removals <= n_items);
479
480 it = g_sequence_get_iter_at_pos (store->items, position);
481
482 if (n_removals)
483 {
484 GSequenceIter *end;
485
486 end = g_sequence_iter_move (it, n_removals);
487 g_sequence_remove_range (it, end);
488
489 it = end;
490 }
491
492 if (n_additions)
493 {
494 guint i;
495
496 for (i = 0; i < n_additions; i++)
497 {
498 if G_UNLIKELY (!g_type_is_a (G_OBJECT_TYPE (additions[i]), store->item_type))
499 {
500 g_critical ("%s: item %d is a %s instead of a %s. GListStore is now in an undefined state.",
501 G_STRFUNC, i, G_OBJECT_TYPE_NAME (additions[i]), g_type_name (store->item_type));
502 return;
503 }
504
505 g_sequence_insert_before (it, g_object_ref (additions[i]));
506 }
507 }
508
509 g_list_store_items_changed (store, position, n_removals, n_additions);
510 }
511
512 static gboolean
513 simple_equal (gconstpointer a,
514 gconstpointer b,
515 gpointer equal_func)
516 {
517 return ((GEqualFunc) equal_func) (a, b);
518 }
519
520 /**
521 * g_list_store_find_with_equal_func:
522 * @store: a #GListStore
523 * @item: (type GObject) (nullable): an item
524 * @equal_func: (scope call): A custom equality check function
525 * @position: (out) (optional): the first position of @item, if it was found.
526 *
527 * Looks up the given @item in the list store by looping over the items and
528 * comparing them with @equal_func until the first occurrence of @item which
529 * matches. If @item was not found, then @position will not be set, and this
530 * method will return %FALSE.
531 *
532 * @item is always passed as second parameter to @equal_func.
533 *
534 * Since GLib 2.76 it is possible to pass `NULL` for @item.
535 *
536 * Returns: Whether @store contains @item. If it was found, @position will be
537 * set to the position where @item occurred for the first time.
538 *
539 * Since: 2.64
540 */
541 gboolean
542 g_list_store_find_with_equal_func (GListStore *store,
543 gpointer item,
544 GEqualFunc equal_func,
545 guint *position)
546 {
547 g_return_val_if_fail (equal_func != NULL, FALSE);
548
549 return g_list_store_find_with_equal_func_full (store, item, simple_equal,
550 equal_func, position);
551 }
552
553 /**
554 * g_list_store_find_with_equal_func_full:
555 * @store: a #GListStore
556 * @item: (type GObject) (nullable): an item
557 * @equal_func: (scope call) (closure user_data): A custom equality check function
558 * @user_data: user data for @equal_func
559 * @position: (out) (optional): the first position of @item, if it was found.
560 *
561 * Like g_list_store_find_with_equal_func() but with an additional @user_data
562 * that is passed to @equal_func.
563 *
564 * @item is always passed as second parameter to @equal_func.
565 *
566 * Since GLib 2.76 it is possible to pass `NULL` for @item.
567 *
568 * Returns: Whether @store contains @item. If it was found, @position will be
569 * set to the position where @item occurred for the first time.
570 *
571 * Since: 2.74
572 */
573 gboolean
574 g_list_store_find_with_equal_func_full (GListStore *store,
575 gpointer item,
576 GEqualFuncFull equal_func,
577 gpointer user_data,
578 guint *position)
579 {
580 GSequenceIter *iter, *begin, *end;
581
582 g_return_val_if_fail (G_IS_LIST_STORE (store), FALSE);
583 g_return_val_if_fail (item == NULL || g_type_is_a (G_OBJECT_TYPE (item), store->item_type),
584 FALSE);
585 g_return_val_if_fail (equal_func != NULL, FALSE);
586
587 /* NOTE: We can't use g_sequence_lookup() or g_sequence_search(), because we
588 * can't assume the sequence is sorted. */
589 begin = g_sequence_get_begin_iter (store->items);
590 end = g_sequence_get_end_iter (store->items);
591
592 iter = begin;
593 while (iter != end)
594 {
595 gpointer iter_item;
596
597 iter_item = g_sequence_get (iter);
598 if (equal_func (iter_item, item, user_data))
599 {
600 if (position)
601 *position = g_sequence_iter_get_position (iter);
602 return TRUE;
603 }
604
605 iter = g_sequence_iter_next (iter);
606 }
607
608 return FALSE;
609 }
610
611 /**
612 * g_list_store_find:
613 * @store: a #GListStore
614 * @item: (type GObject): an item
615 * @position: (out) (optional): the first position of @item, if it was found.
616 *
617 * Looks up the given @item in the list store by looping over the items until
618 * the first occurrence of @item. If @item was not found, then @position will
619 * not be set, and this method will return %FALSE.
620 *
621 * If you need to compare the two items with a custom comparison function, use
622 * g_list_store_find_with_equal_func() with a custom #GEqualFunc instead.
623 *
624 * Returns: Whether @store contains @item. If it was found, @position will be
625 * set to the position where @item occurred for the first time.
626 *
627 * Since: 2.64
628 */
629 gboolean
630 g_list_store_find (GListStore *store,
631 gpointer item,
632 guint *position)
633 {
634 return g_list_store_find_with_equal_func (store,
635 item,
636 g_direct_equal,
637 position);
638 }