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

source code of gtk/subprojects/glib/gio/gliststore.c