gio/gliststore.c

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