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 | |
48 | struct _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 | |
61 | enum |
62 | { |
63 | PROP_0, |
64 | PROP_ITEM_TYPE, |
65 | N_PROPERTIES |
66 | }; |
67 | |
68 | static void g_list_store_iface_init (GListModelInterface *iface); |
69 | |
70 | G_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 | |
73 | static void |
74 | g_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 | |
90 | static void |
91 | g_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 | |
100 | static void |
101 | g_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 | |
119 | static void |
120 | g_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 | |
139 | static void |
140 | g_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 | |
161 | static GType |
162 | g_list_store_get_item_type (GListModel *list) |
163 | { |
164 | GListStore *store = G_LIST_STORE (ptr: list); |
165 | |
166 | return store->item_type; |
167 | } |
168 | |
169 | static guint |
170 | g_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 | |
177 | static gpointer |
178 | g_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 | |
207 | static void |
208 | g_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 | |
215 | static void |
216 | g_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 | */ |
233 | GListStore * |
234 | g_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 | */ |
263 | void |
264 | g_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 | */ |
300 | guint |
301 | g_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 | */ |
331 | void |
332 | g_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 | */ |
361 | void |
362 | g_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 | */ |
389 | void |
390 | g_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 | */ |
412 | void |
413 | g_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 | */ |
450 | void |
451 | g_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 | */ |
515 | gboolean |
516 | g_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 | */ |
570 | gboolean |
571 | g_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 | |