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 };
  59
  60 enum
  61 {
  62   PROP_0,
  63   PROP_ITEM_TYPE,
  64   N_PROPERTIES
  65 };
  66
  67 static void g_list_store_iface_init (GListModelInterface *iface);
  68
  69 G_DEFINE_TYPE_WITH_CODE (GListStore, g_list_store, G_TYPE_OBJECT,
  70                          G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, g_list_store_iface_init));
  71
  72 static void
  73 g_list_store_items_changed (GListStore *store,
  74                             guint       position,
  75                             guint       removed,
  76                             guint       added)
  77 {
  78   /* check if the iter cache may have been invalidated */
  79   if (position <= store->last_position)
  80     {
  81       store->last_iter = NULL;
  82       store->last_position = -1u;
  83     }
  84
  85   g_list_model_items_changed (G_LIST_MODEL (store), position, removed, added);
  86 }
  87
  88 static void
  89 g_list_store_dispose (GObject *object)
  90 {
  91   GListStore *store = G_LIST_STORE (object);
  92
  93   g_clear_pointer (&store->items, g_sequence_free);
  94
  95   G_OBJECT_CLASS (g_list_store_parent_class)->dispose (object);
  96 }
  97
  98 static void
  99 g_list_store_get_property (GObject    *object,
 100                            guint       property_id,
 101                            GValue     *value,
 102                            GParamSpec *pspec)
 103 {
 104   GListStore *store = G_LIST_STORE (object);
 105
 106   switch (property_id)
 107     {
 108     case PROP_ITEM_TYPE:
 109       g_value_set_gtype (value, store->item_type);
 110       break;
 111
 112     default:
 113       G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
 114     }
 115 }
 116
 117 static void
 118 g_list_store_set_property (GObject      *object,
 119                            guint         property_id,
 120                            const GValue *value,
 121                            GParamSpec   *pspec)
 122 {
 123   GListStore *store = G_LIST_STORE (object);
 124
 125   switch (property_id)
 126     {
 127     case PROP_ITEM_TYPE: /* construct-only */
 128       store->item_type = g_value_get_gtype (value);
 129       if (!g_type_is_a (store->item_type, G_TYPE_OBJECT))
 130         g_critical ("GListStore cannot store items of type '%s'. Items must be GObjects.",
 131                     g_type_name (store->item_type));
 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 != -1u)
 185     {
 186       if (store->last_position == position + 1)
 187         it = g_sequence_iter_prev (store->last_iter);
 188       else if (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
 200   if (g_sequence_iter_is_end (it))
 201     return NULL;
 202   else
 203     return g_object_ref (g_sequence_get (it));
 204 }
 205
 206 static void
 207 g_list_store_iface_init (GListModelInterface *iface)
 208 {
 209   iface->get_item_type = g_list_store_get_item_type;
 210   iface->get_n_items = g_list_store_get_n_items;
 211   iface->get_item = g_list_store_get_item;
 212 }
 213
 214 static void
 215 g_list_store_init (GListStore *store)
 216 {
 217   store->items = g_sequence_new (g_object_unref);
 218   store->last_position = -1u;
 219 }
 220
 221 /**
 222  * g_list_store_new:
 223  * @item_type: the #GType of items in the list
 224  *
 225  * Creates a new #GListStore with items of type @item_type. @item_type
 226  * must be a subclass of #GObject.
 227  *
 228  * Returns: a new #GListStore
 229  * Since: 2.44
 230  */
 231 GListStore *
 232 g_list_store_new (GType item_type)
 233 {
 234   /* We only allow GObjects as item types right now. This might change
 235    * in the future.
 236    */
 237   g_return_val_if_fail (g_type_is_a (item_type, G_TYPE_OBJECT), NULL);
 238
 239   return g_object_new (G_TYPE_LIST_STORE,
 240                        "item-type", item_type,
 241                        NULL);
 242 }
 243
 244 /**
 245  * g_list_store_insert:
 246  * @store: a #GListStore
 247  * @position: the position at which to insert the new item
 248  * @item: (type GObject): the new item
 249  *
 250  * Inserts @item into @store at @position. @item must be of type
 251  * #GListStore:item-type or derived from it. @position must be smaller
 252  * than the length of the list, or equal to it to append.
 253  *
 254  * This function takes a ref on @item.
 255  *
 256  * Use g_list_store_splice() to insert multiple items at the same time
 257  * efficiently.
 258  *
 259  * Since: 2.44
 260  */
 261 void
 262 g_list_store_insert (GListStore *store,
 263                      guint       position,
 264                      gpointer    item)
 265 {
 266   GSequenceIter *it;
 267
 268   g_return_if_fail (G_IS_LIST_STORE (store));
 269   g_return_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type));
 270   g_return_if_fail (position <= g_sequence_get_length (store->items));
 271
 272   it = g_sequence_get_iter_at_pos (store->items, position);
 273   g_sequence_insert_before (it, g_object_ref (item));
 274
 275   g_list_store_items_changed (store, position, 0, 1);
 276 }
 277
 278 /**
 279  * g_list_store_insert_sorted:
 280  * @store: a #GListStore
 281  * @item: (type GObject): the new item
 282  * @compare_func: (scope call): pairwise comparison function for sorting
 283  * @user_data: (closure): user data for @compare_func
 284  *
 285  * Inserts @item into @store at a position to be determined by the
 286  * @compare_func.
 287  *
 288  * The list must already be sorted before calling this function or the
 289  * result is undefined.  Usually you would approach this by only ever
 290  * inserting items by way of this function.
 291  *
 292  * This function takes a ref on @item.
 293  *
 294  * Returns: the position at which @item was inserted
 295  *
 296  * Since: 2.44
 297  */
 298 guint
 299 g_list_store_insert_sorted (GListStore       *store,
 300                             gpointer          item,
 301                             GCompareDataFunc  compare_func,
 302                             gpointer          user_data)
 303 {
 304   GSequenceIter *it;
 305   guint position;
 306
 307   g_return_val_if_fail (G_IS_LIST_STORE (store), 0);
 308   g_return_val_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type), 0);
 309   g_return_val_if_fail (compare_func != NULL, 0);
 310
 311   it = g_sequence_insert_sorted (store->items, g_object_ref (item), compare_func, user_data);
 312   position = g_sequence_iter_get_position (it);
 313
 314   g_list_store_items_changed (store, position, 0, 1);
 315
 316   return position;
 317 }
 318
 319 /**
 320  * g_list_store_sort:
 321  * @store: a #GListStore
 322  * @compare_func: (scope call): pairwise comparison function for sorting
 323  * @user_data: (closure): user data for @compare_func
 324  *
 325  * Sort the items in @store according to @compare_func.
 326  *
 327  * Since: 2.46
 328  */
 329 void
 330 g_list_store_sort (GListStore       *store,
 331                    GCompareDataFunc  compare_func,
 332                    gpointer          user_data)
 333 {
 334   gint n_items;
 335
 336   g_return_if_fail (G_IS_LIST_STORE (store));
 337   g_return_if_fail (compare_func != NULL);
 338
 339   g_sequence_sort (store->items, compare_func, user_data);
 340
 341   n_items = g_sequence_get_length (store->items);
 342   g_list_store_items_changed (store, 0, n_items, n_items);
 343 }
 344
 345 /**
 346  * g_list_store_append:
 347  * @store: a #GListStore
 348  * @item: (type GObject): the new item
 349  *
 350  * Appends @item to @store. @item must be of type #GListStore:item-type.
 351  *
 352  * This function takes a ref on @item.
 353  *
 354  * Use g_list_store_splice() to append multiple items at the same time
 355  * efficiently.
 356  *
 357  * Since: 2.44
 358  */
 359 void
 360 g_list_store_append (GListStore *store,
 361                      gpointer    item)
 362 {
 363   guint n_items;
 364
 365   g_return_if_fail (G_IS_LIST_STORE (store));
 366   g_return_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type));
 367
 368   n_items = g_sequence_get_length (store->items);
 369   g_sequence_append (store->items, g_object_ref (item));
 370
 371   g_list_store_items_changed (store, n_items, 0, 1);
 372 }
 373
 374 /**
 375  * g_list_store_remove:
 376  * @store: a #GListStore
 377  * @position: the position of the item that is to be removed
 378  *
 379  * Removes the item from @store that is at @position. @position must be
 380  * smaller than the current length of the list.
 381  *
 382  * Use g_list_store_splice() to remove multiple items at the same time
 383  * efficiently.
 384  *
 385  * Since: 2.44
 386  */
 387 void
 388 g_list_store_remove (GListStore *store,
 389                      guint       position)
 390 {
 391   GSequenceIter *it;
 392
 393   g_return_if_fail (G_IS_LIST_STORE (store));
 394
 395   it = g_sequence_get_iter_at_pos (store->items, position);
 396   g_return_if_fail (!g_sequence_iter_is_end (it));
 397
 398   g_sequence_remove (it);
 399   g_list_store_items_changed (store, position, 1, 0);
 400 }
 401
 402 /**
 403  * g_list_store_remove_all:
 404  * @store: a #GListStore
 405  *
 406  * Removes all items from @store.
 407  *
 408  * Since: 2.44
 409  */
 410 void
 411 g_list_store_remove_all (GListStore *store)
 412 {
 413   guint n_items;
 414
 415   g_return_if_fail (G_IS_LIST_STORE (store));
 416
 417   n_items = g_sequence_get_length (store->items);
 418   g_sequence_remove_range (g_sequence_get_begin_iter (store->items),
 419                            g_sequence_get_end_iter (store->items));
 420
 421   g_list_store_items_changed (store, 0, n_items, 0);
 422 }
 423
 424 /**
 425  * g_list_store_splice:
 426  * @store: a #GListStore
 427  * @position: the position at which to make the change
 428  * @n_removals: the number of items to remove
 429  * @additions: (array length=n_additions) (element-type GObject): the items to add
 430  * @n_additions: the number of items to add
 431  *
 432  * Changes @store by removing @n_removals items and adding @n_additions
 433  * items to it. @additions must contain @n_additions items of type
 434  * #GListStore:item-type.  %NULL is not permitted.
 435  *
 436  * This function is more efficient than g_list_store_insert() and
 437  * g_list_store_remove(), because it only emits
 438  * #GListModel::items-changed once for the change.
 439  *
 440  * This function takes a ref on each item in @additions.
 441  *
 442  * The parameters @position and @n_removals must be correct (ie:
 443  * @position + @n_removals must be less than or equal to the length of
 444  * the list at the time this function is called).
 445  *
 446  * Since: 2.44
 447  */
 448 void
 449 g_list_store_splice (GListStore *store,
 450                      guint       position,
 451                      guint       n_removals,
 452                      gpointer   *additions,
 453                      guint       n_additions)
 454 {
 455   GSequenceIter *it;
 456   guint n_items;
 457
 458   g_return_if_fail (G_IS_LIST_STORE (store));
 459   g_return_if_fail (position + n_removals >= position); /* overflow */
 460
 461   n_items = g_sequence_get_length (store->items);
 462   g_return_if_fail (position + n_removals <= n_items);
 463
 464   it = g_sequence_get_iter_at_pos (store->items, position);
 465
 466   if (n_removals)
 467     {
 468       GSequenceIter *end;
 469
 470       end = g_sequence_iter_move (it, n_removals);
 471       g_sequence_remove_range (it, end);
 472
 473       it = end;
 474     }
 475
 476   if (n_additions)
 477     {
 478       gint i;
 479
 480       for (i = 0; i < n_additions; i++)
 481         {
 482           if G_UNLIKELY (!g_type_is_a (G_OBJECT_TYPE (additions[i]), store->item_type))
 483             {
 484               g_critical ("%s: item %d is a %s instead of a %s.  GListStore is now in an undefined state.",
 485                           G_STRFUNC, i, G_OBJECT_TYPE_NAME (additions[i]), g_type_name (store->item_type));
 486               return;
 487             }
 488
 489           it = g_sequence_insert_before (it, g_object_ref (additions[i]));
 490           it = g_sequence_iter_next (it);
 491         }
 492     }
 493
 494   g_list_store_items_changed (store, position, n_removals, n_additions);
 495 }