summaryrefslogtreecommitdiff
path: root/src/models/gtd-list-store.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/models/gtd-list-store.c')
-rw-r--r--src/models/gtd-list-store.c567
1 files changed, 567 insertions, 0 deletions
diff --git a/src/models/gtd-list-store.c b/src/models/gtd-list-store.c
new file mode 100644
index 0000000..bd30bcc
--- /dev/null
+++ b/src/models/gtd-list-store.c
@@ -0,0 +1,567 @@
+/* gtd-list-store.c
+ *
+ * Copyright 2018 Georges Basile Stavracas Neto <georges.stavracas@gmail.com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#define G_LOG_DOMAIN "GtdListStore"
+
+#include "gtd-list-store.h"
+
+#include <gio/gio.h>
+
+/**
+ * SECTION:gtdliststore
+ * @title: GtdListStore
+ * @short_description: A simple implementation of #GListModel
+ * @include: gio/gio.h
+ *
+ * #GtdListStore is a simple implementation of #GListModel that stores all
+ * items in memory.
+ *
+ * It provides insertions, deletions, and lookups in logarithmic time
+ * with a fast path for the common case of iterating the list linearly.
+ */
+
+/**
+ * GtdListStore:
+ *
+ * #GtdListStore is an opaque data structure and can only be accessed
+ * using the following functions.
+ **/
+
+struct _GtdListStore
+{
+ GObject parent;
+
+ GType item_type;
+ GSequence *items;
+
+ GHashTable *item_to_iter;
+
+ /* cache */
+ gint64 length;
+ gint64 last_position;
+ GSequenceIter *last_iter;
+};
+
+enum
+{
+ PROP_0,
+ PROP_ITEM_TYPE,
+ N_PROPERTIES
+};
+
+static void gtd_list_store_iface_init (GListModelInterface *iface);
+
+G_DEFINE_TYPE_WITH_CODE (GtdListStore, gtd_list_store, G_TYPE_OBJECT,
+ G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtd_list_store_iface_init));
+
+static void
+remove_item_from_sequence_cb (gpointer item,
+ gpointer user_data)
+{
+ GSequenceIter *it;
+ GtdListStore *store;
+
+ store = (GtdListStore *)user_data;
+ it = g_hash_table_lookup (store->item_to_iter, item);
+
+ g_hash_table_remove (store->item_to_iter, item);
+ g_sequence_remove (it);
+}
+
+static void
+gtd_list_store_items_changed (GtdListStore *store,
+ guint position,
+ guint removed,
+ guint added)
+{
+ /* check if the iter cache may have been invalidated */
+ if (position <= store->last_position)
+ {
+ store->last_iter = NULL;
+ store->last_position = -1;
+ }
+
+ store->length -= removed;
+ store->length += added;
+
+ g_list_model_items_changed (G_LIST_MODEL (store), position, removed, added);
+}
+
+static void
+gtd_list_store_dispose (GObject *object)
+{
+ GtdListStore *store = GTD_LIST_STORE (object);
+
+ g_clear_pointer (&store->item_to_iter, g_hash_table_destroy);
+ g_clear_pointer (&store->items, g_sequence_free);
+
+ G_OBJECT_CLASS (gtd_list_store_parent_class)->dispose (object);
+}
+
+static void
+gtd_list_store_get_property (GObject *object,
+ guint property_id,
+ GValue *value,
+ GParamSpec *pspec)
+{
+ GtdListStore *store = GTD_LIST_STORE (object);
+
+ switch (property_id)
+ {
+ case PROP_ITEM_TYPE:
+ g_value_set_gtype (value, store->item_type);
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
+ }
+}
+
+static void
+gtd_list_store_set_property (GObject *object,
+ guint property_id,
+ const GValue *value,
+ GParamSpec *pspec)
+{
+ GtdListStore *store = GTD_LIST_STORE (object);
+
+ switch (property_id)
+ {
+ case PROP_ITEM_TYPE: /* construct-only */
+ store->item_type = g_value_get_gtype (value);
+ if (!g_type_is_a (store->item_type, G_TYPE_OBJECT))
+ g_critical ("GtdListStore cannot store items of type '%s'. Items must be GObjects.",
+ g_type_name (store->item_type));
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
+ }
+}
+
+static void
+gtd_list_store_class_init (GtdListStoreClass *klass)
+{
+ GObjectClass *object_class = G_OBJECT_CLASS (klass);
+
+ object_class->dispose = gtd_list_store_dispose;
+ object_class->get_property = gtd_list_store_get_property;
+ object_class->set_property = gtd_list_store_set_property;
+
+ /**
+ * GtdListStore:item-type:
+ *
+ * The type of items contained in this list store. Items must be
+ * subclasses of #GObject.
+ **/
+ g_object_class_install_property (object_class, PROP_ITEM_TYPE,
+ g_param_spec_gtype ("item-type", "", "", G_TYPE_OBJECT,
+ G_PARAM_CONSTRUCT_ONLY | G_PARAM_READWRITE | G_PARAM_STATIC_STRINGS));
+}
+
+static GType
+gtd_list_store_get_item_type (GListModel *list)
+{
+ GtdListStore *store = GTD_LIST_STORE (list);
+
+ return store->item_type;
+}
+
+static guint
+gtd_list_store_get_n_items (GListModel *list)
+{
+ GtdListStore *store = GTD_LIST_STORE (list);
+
+ return store->length;
+}
+
+static gpointer
+gtd_list_store_get_item (GListModel *list,
+ guint position)
+{
+ GtdListStore *store = GTD_LIST_STORE (list);
+ GSequenceIter *it = NULL;
+
+ if (store->last_position != -1)
+ {
+ if (store->last_position == position + 1)
+ it = g_sequence_iter_prev (store->last_iter);
+ else if (store->last_position == position - 1)
+ it = g_sequence_iter_next (store->last_iter);
+ else if (store->last_position == position)
+ it = store->last_iter;
+ }
+
+ if (it == NULL)
+ it = g_sequence_get_iter_at_pos (store->items, position);
+
+ store->last_iter = it;
+ store->last_position = position;
+
+ if (g_sequence_iter_is_end (it))
+ return NULL;
+ else
+ return g_object_ref (g_sequence_get (it));
+}
+
+static void
+gtd_list_store_iface_init (GListModelInterface *iface)
+{
+ iface->get_item_type = gtd_list_store_get_item_type;
+ iface->get_n_items = gtd_list_store_get_n_items;
+ iface->get_item = gtd_list_store_get_item;
+}
+
+static void
+gtd_list_store_init (GtdListStore *store)
+{
+ store->item_to_iter = g_hash_table_new (g_direct_hash, g_direct_equal);
+ store->items = g_sequence_new (g_object_unref);
+ store->last_position = -1;
+}
+
+/**
+ * gtd_list_store_new:
+ * @item_type: the #GType of items in the list
+ *
+ * Creates a new #GtdListStore with items of type @item_type. @item_type
+ * must be a subclass of #GObject.
+ *
+ * Returns: a new #GtdListStore
+ */
+GtdListStore *
+gtd_list_store_new (GType item_type)
+{
+ /* We only allow GObjects as item types right now. This might change
+ * in the future.
+ */
+ g_return_val_if_fail (g_type_is_a (item_type, G_TYPE_OBJECT), NULL);
+
+ return g_object_new (GTD_TYPE_LIST_STORE,
+ "item-type", item_type,
+ NULL);
+}
+
+/**
+ * gtd_list_store_insert:
+ * @store: a #GtdListStore
+ * @position: the position at which to insert the new item
+ * @item: (type GObject): the new item
+ *
+ * Inserts @item into @store at @position. @item must be of type
+ * #GtdListStore:item-type or derived from it. @position must be smaller
+ * than the length of the list, or equal to it to append.
+ *
+ * This function takes a ref on @item.
+ *
+ * Use gtd_list_store_splice() to insert multiple items at the same time
+ * efficiently.
+ */
+void
+gtd_list_store_insert (GtdListStore *store,
+ guint position,
+ gpointer item)
+{
+ GSequenceIter *new_it;
+ GSequenceIter *it;
+
+ g_return_if_fail (GTD_IS_LIST_STORE (store));
+ g_return_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type));
+ g_return_if_fail (position <= (guint) g_sequence_get_length (store->items));
+
+ it = g_sequence_get_iter_at_pos (store->items, position);
+ new_it = g_sequence_insert_before (it, g_object_ref (item));
+
+ g_hash_table_insert (store->item_to_iter, item, new_it);
+
+ gtd_list_store_items_changed (store, position, 0, 1);
+}
+
+/**
+ * gtd_list_store_insert_sorted:
+ * @store: a #GtdListStore
+ * @item: (type GObject): the new item
+ * @compare_func: (scope call): pairwise comparison function for sorting
+ * @user_data: (closure): user data for @compare_func
+ *
+ * Inserts @item into @store at a position to be determined by the
+ * @compare_func.
+ *
+ * The list must already be sorted before calling this function or the
+ * result is undefined. Usually you would approach this by only ever
+ * inserting items by way of this function.
+ *
+ * This function takes a ref on @item.
+ *
+ * Returns: the position at which @item was inserted
+ */
+guint
+gtd_list_store_insert_sorted (GtdListStore *store,
+ gpointer item,
+ GCompareDataFunc compare_func,
+ gpointer user_data)
+{
+ GSequenceIter *it;
+ guint position;
+
+ g_return_val_if_fail (GTD_IS_LIST_STORE (store), 0);
+ g_return_val_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type), 0);
+ g_return_val_if_fail (compare_func != NULL, 0);
+
+ it = g_sequence_insert_sorted (store->items, g_object_ref (item), compare_func, user_data);
+ position = g_sequence_iter_get_position (it);
+
+ g_hash_table_insert (store->item_to_iter, item, it);
+
+ gtd_list_store_items_changed (store, position, 0, 1);
+
+ return position;
+}
+
+/**
+ * gtd_list_store_sort:
+ * @store: a #GtdListStore
+ * @compare_func: (scope call): pairwise comparison function for sorting
+ * @user_data: (closure): user data for @compare_func
+ *
+ * Sort the items in @store according to @compare_func.
+ */
+void
+gtd_list_store_sort (GtdListStore *store,
+ GCompareDataFunc compare_func,
+ gpointer user_data)
+{
+ gint n_items;
+
+ g_return_if_fail (GTD_IS_LIST_STORE (store));
+ g_return_if_fail (compare_func != NULL);
+
+ g_sequence_sort (store->items, compare_func, user_data);
+
+ n_items = g_sequence_get_length (store->items);
+ gtd_list_store_items_changed (store, 0, n_items, n_items);
+}
+
+/**
+ * gtd_list_store_append:
+ * @store: a #GtdListStore
+ * @item: (type GObject): the new item
+ *
+ * Appends @item to @store. @item must be of type #GtdListStore:item-type.
+ *
+ * This function takes a ref on @item.
+ *
+ * Use gtd_list_store_splice() to append multiple items at the same time
+ * efficiently.
+ */
+void
+gtd_list_store_append (GtdListStore *store,
+ gpointer item)
+{
+ GSequenceIter *it;
+ guint n_items;
+
+ g_return_if_fail (GTD_IS_LIST_STORE (store));
+ g_return_if_fail (g_type_is_a (G_OBJECT_TYPE (item), store->item_type));
+
+ n_items = g_sequence_get_length (store->items);
+ it = g_sequence_append (store->items, g_object_ref (item));
+
+ g_hash_table_insert (store->item_to_iter, item, it);
+
+ gtd_list_store_items_changed (store, n_items, 0, 1);
+}
+
+/**
+ * gtd_list_store_remove:
+ * @store: a #GtdListStore
+ * @item: the item that is to be removed
+ *
+ * Removes the item from @store.
+ *
+ * Use gtd_list_store_splice() to remove multiple items at the same time
+ * efficiently.
+ */
+void
+gtd_list_store_remove (GtdListStore *store,
+ gpointer item)
+{
+ GSequenceIter *it;
+ guint position;
+
+ g_return_if_fail (GTD_IS_LIST_STORE (store));
+
+ it = g_hash_table_lookup (store->item_to_iter, item);
+ if (!it)
+ return;
+
+ g_return_if_fail (!g_sequence_iter_is_end (it));
+
+ position = g_sequence_iter_get_position (it);
+
+ g_hash_table_remove (store->item_to_iter, item);
+ g_sequence_remove (it);
+ gtd_list_store_items_changed (store, position, 1, 0);
+}
+
+/**
+ * gtd_list_store_remove_at_position:
+ * @store: a #GtdListStore
+ * @position: the position of the item that is to be removed
+ *
+ * Removes the item from @store that is at @position. @position must be
+ * smaller than the current length of the list.
+ *
+ * Use gtd_list_store_splice() to remove multiple items at the same time
+ * efficiently.
+ */
+void
+gtd_list_store_remove_at_position (GtdListStore *store,
+ guint position)
+{
+ GSequenceIter *it;
+
+ g_return_if_fail (GTD_IS_LIST_STORE (store));
+
+ it = g_sequence_get_iter_at_pos (store->items, position);
+ g_return_if_fail (!g_sequence_iter_is_end (it));
+
+ g_hash_table_remove (store->item_to_iter, g_sequence_get (it));
+ g_sequence_remove (it);
+ gtd_list_store_items_changed (store, position, 1, 0);
+}
+
+/**
+ * gtd_list_store_remove_all:
+ * @store: a #GtdListStore
+ *
+ * Removes all items from @store.
+ */
+void
+gtd_list_store_remove_all (GtdListStore *store)
+{
+ guint n_items;
+
+ g_return_if_fail (GTD_IS_LIST_STORE (store));
+
+ n_items = g_sequence_get_length (store->items);
+ g_sequence_remove_range (g_sequence_get_begin_iter (store->items),
+ g_sequence_get_end_iter (store->items));
+ g_hash_table_remove_all (store->item_to_iter);
+
+ gtd_list_store_items_changed (store, 0, n_items, 0);
+}
+
+/**
+ * gtd_list_store_splice:
+ * @store: a #GtdListStore
+ * @position: the position at which to make the change
+ * @n_removals: the number of items to remove
+ * @additions: (array length=n_additions) (element-type GObject): the items to add
+ * @n_additions: the number of items to add
+ *
+ * Changes @store by removing @n_removals items and adding @n_additions
+ * items to it. @additions must contain @n_additions items of type
+ * #GtdListStore:item-type. %NULL is not permitted.
+ *
+ * This function is more efficient than gtd_list_store_insert() and
+ * gtd_list_store_remove(), because it only emits
+ * #GListModel::items-changed once for the change.
+ *
+ * This function takes a ref on each item in @additions.
+ *
+ * The parameters @position and @n_removals must be correct (ie:
+ * @position + @n_removals must be less than or equal to the length of
+ * the list at the time this function is called).
+ */
+void
+gtd_list_store_splice (GtdListStore *store,
+ guint position,
+ guint n_removals,
+ gpointer *additions,
+ guint n_additions)
+{
+ GSequenceIter *it;
+ guint n_items;
+
+ g_return_if_fail (GTD_IS_LIST_STORE (store));
+ g_return_if_fail (position + n_removals >= position); /* overflow */
+
+ n_items = g_sequence_get_length (store->items);
+ g_return_if_fail (position + n_removals <= n_items);
+
+ it = g_sequence_get_iter_at_pos (store->items, position);
+
+ if (n_removals)
+ {
+ GSequenceIter *end;
+
+ end = g_sequence_iter_move (it, n_removals);
+ g_sequence_foreach_range (it, end, remove_item_from_sequence_cb, store);
+
+ it = end;
+ }
+
+ if (n_additions)
+ {
+ guint i;
+
+ for (i = 0; i < n_additions; i++)
+ {
+ if G_UNLIKELY (!g_type_is_a (G_OBJECT_TYPE (additions[i]), store->item_type))
+ {
+ g_critical ("%s: item %d is a %s instead of a %s. GtdListStore is now in an undefined state.",
+ G_STRFUNC, i, G_OBJECT_TYPE_NAME (additions[i]), g_type_name (store->item_type));
+ return;
+ }
+
+ it = g_sequence_insert_before (it, g_object_ref (additions[i]));
+ g_hash_table_insert (store->item_to_iter, additions[i], it);
+
+ it = g_sequence_iter_next (it);
+ }
+ }
+
+ gtd_list_store_items_changed (store, position, n_removals, n_additions);
+}
+
+/**
+ * gtd_list_store_get_item_position:
+ * @store: a #GtdListStore
+ * @item: the item to retrieve the position
+ *
+ * Retrieves the position of @items inside @store. It is a programming
+ * error to pass an @item that is not contained in @store.
+ *
+ * Returns: the position of @item in @store.
+ */
+guint
+gtd_list_store_get_item_position (GtdListStore *store,
+ gpointer item)
+{
+ GSequenceIter *iter;
+
+ g_return_val_if_fail (GTD_IS_LIST_STORE (store), 0);
+
+ iter = g_hash_table_lookup (store->item_to_iter, item);
+ g_assert (iter != NULL);
+
+ return g_sequence_iter_get_position (iter);
+}
generated by cgit v1.2.3 (git 2.46.0) at 2026-02-04 05:03:59 +0000