gio/gliststore.c

   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 (G_LIST_MODEL (store), position, removed, added);
  88 }
  89
  90 static void
  91 g_list_store_dispose (GObject *object)
  92 {
  93   GListStore *store = G_LIST_STORE (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 (object);
 107
 108   switch (property_id)
 109     {
 110     case PROP_ITEM_TYPE:
 111       g_value_set_gtype (value, 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 (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 (object_class, PROP_ITEM_TYPE,
 157     g_param_spec_gtype ("item-type", "", "", G_TYPE_OBJECT,
 158                         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 (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 (list);
 173
 174   return g_sequence_get_length (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 (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 (store->last_iter);
 188       else if (position > 0 && store->last_position == position - 1)
 189         it = g_sequence_iter_next (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 (store->items, 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 (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 (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                        "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 <= g_sequence_get_length (store->items));
 273
 274   it = g_sequence_get_iter_at_pos (store->items, position);
 275   g_sequence_insert_before (it, g_object_ref (item));
 276
 277   g_list_store_items_changed (store, position, 0, 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 (store->items, g_object_ref (item), compare_func, user_data);
 314   position = g_sequence_iter_get_position (it);
 315
 316   g_list_store_items_changed (store, position, 0, 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 (store->items, compare_func, user_data);
 342
 343   n_items = g_sequence_get_length (store->items);
 344   g_list_store_items_changed (store, 0, n_items, 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 (store->items);
 371   g_sequence_append (store->items, g_object_ref (item));
 372
 373   g_list_store_items_changed (store, n_items, 0, 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 (store->items, position);
 398   g_return_if_fail (!g_sequence_iter_is_end (it));
 399
 400   g_sequence_remove (it);
 401   g_list_store_items_changed (store, position, 1, 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 (store->items);
 420   g_sequence_remove_range (g_sequence_get_begin_iter (store->items),
 421                            g_sequence_get_end_iter (store->items));
 422
 423   g_list_store_items_changed (store, 0, n_items, 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 (store->items);
 464   g_return_if_fail (position + n_removals <= n_items);
 465
 466   it = g_sequence_get_iter_at_pos (store->items, position);
 467
 468   if (n_removals)
 469     {
 470       GSequenceIter *end;
 471
 472       end = g_sequence_iter_move (it, n_removals);
 473       g_sequence_remove_range (it, end);
 474
 475       it = end;
 476     }
 477
 478   if (n_additions)
 479     {
 480       gint 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 (it, g_object_ref (additions[i]));
 492         }
 493     }
 494
 495   g_list_store_items_changed (store, position, n_removals, 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 (store->items);
 531   end = g_sequence_get_end_iter (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                                             g_direct_equal,
 578                                             position);
 579 }