[9ae8f17cfc8ba7fd8fb34b2a194ef965a3b36a40839a46eeab1350e916692ac9/wip/otte/sortlistmodel] Add a 3rd sortmodel implementation
- From: Benjamin Otte <otte src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [9ae8f17cfc8ba7fd8fb34b2a194ef965a3b36a40839a46eeab1350e916692ac9/wip/otte/sortlistmodel] Add a 3rd sortmodel implementation
- Date: Wed, 8 Jul 2020 01:08:09 +0000 (UTC)
commit 19b4b35481b37cac4ccc679114c66406f974e62b
Author: Benjamin Otte <otte redhat com>
Date: Wed Jul 8 03:05:08 2020 +0200
Add a 3rd sortmodel implementation
This one tracks the original positions on top of just the items so that
it can remove items.
It now takes twice as much memory but removes half of a million items in
50ms.
gtk/gtk.h | 1 +
gtk/gtksor3listmodel.c | 512 +++++++++++++++++++++++++++++++++++++++
gtk/gtksor3listmodel.h | 57 +++++
gtk/meson.build | 2 +
testsuite/gtk/sort-performance.c | 3 +-
5 files changed, 574 insertions(+), 1 deletion(-)
---
diff --git a/gtk/gtk.h b/gtk/gtk.h
index 10959b7dbb..4a82242e2c 100644
--- a/gtk/gtk.h
+++ b/gtk/gtk.h
@@ -234,6 +234,7 @@
#include <gtk/gtksnapshot.h>
#include <gtk/gtksorter.h>
#include <gtk/gtksor2listmodel.h>
+#include <gtk/gtksor3listmodel.h>
#include <gtk/gtksortlistmodel.h>
#include <gtk/gtkstacksidebar.h>
#include <gtk/gtksizegroup.h>
diff --git a/gtk/gtksor3listmodel.c b/gtk/gtksor3listmodel.c
new file mode 100644
index 0000000000..ffbfd4a0fe
--- /dev/null
+++ b/gtk/gtksor3listmodel.c
@@ -0,0 +1,512 @@
+/*
+ * Copyright © 2018 Benjamin Otte
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Benjamin Otte <otte gnome org>
+ */
+
+#include "config.h"
+
+#include "gtksor3listmodel.h"
+
+#include "gtkintl.h"
+#include "gtkprivate.h"
+
+typedef struct _SortItem SortItem;
+struct _SortItem
+{
+ GObject *item;
+ guint position;
+};
+
+static void
+sort_item_clear (gpointer data)
+{
+ SortItem *si = data;
+
+ g_clear_object (&si->item);
+}
+
+#define GTK_VECTOR_ELEMENT_TYPE SortItem
+#define GTK_VECTOR_TYPE_NAME SortArray
+#define GTK_VECTOR_NAME sort_array
+#define GTK_VECTOR_FREE_FUNC sort_item_clear
+#define GTK_VECTOR_BY_VALUE 1
+#include "gtkvectorimpl.c"
+
+/**
+ * SECTION:gtksor3listmodel
+ * @title: GtkSor3ListModel
+ * @short_description: A list model that sorts its items
+ * @see_also: #GListModel, #GtkSorter
+ *
+ * #GtkSor3ListModel is a list model that takes a list model and
+ * sorts its elements according to a #GtkSorter.
+ *
+ * #GtkSor3ListModel is a generic model and because of that it
+ * cannot take advantage of any external knowledge when sorting.
+ * If you run into performance issues with #GtkSor3ListModel, it
+ * is strongly recommended that you write your own sorting list
+ * model.
+ */
+
+enum {
+ PROP_0,
+ PROP_MODEL,
+ PROP_SORTER,
+ NUM_PROPERTIES
+};
+
+struct _GtkSor3ListModel
+{
+ GObject parent_instance;
+
+ GListModel *model;
+ GtkSorter *sorter;
+
+ SortArray items; /* empty if known unsorted */
+};
+
+struct _GtkSor3ListModelClass
+{
+ GObjectClass parent_class;
+};
+
+static GParamSpec *properties[NUM_PROPERTIES] = { NULL, };
+
+static GType
+gtk_sor3_list_model_get_item_type (GListModel *list)
+{
+ return G_TYPE_OBJECT;
+}
+
+static guint
+gtk_sor3_list_model_get_n_items (GListModel *list)
+{
+ GtkSor3ListModel *self = GTK_SOR3_LIST_MODEL (list);
+
+ if (self->model == NULL)
+ return 0;
+
+ return g_list_model_get_n_items (self->model);
+}
+
+static gpointer
+gtk_sor3_list_model_get_item (GListModel *list,
+ guint position)
+{
+ GtkSor3ListModel *self = GTK_SOR3_LIST_MODEL (list);
+
+ if (self->model == NULL)
+ return NULL;
+
+ if (sort_array_is_empty (&self->items))
+ return g_list_model_get_item (self->model, position);
+
+ if (position >= sort_array_get_size (&self->items))
+ return NULL;
+
+ return g_object_ref (sort_array_get (&self->items, position)->item);
+}
+
+static void
+gtk_sor3_list_model_model_init (GListModelInterface *iface)
+{
+ iface->get_item_type = gtk_sor3_list_model_get_item_type;
+ iface->get_n_items = gtk_sor3_list_model_get_n_items;
+ iface->get_item = gtk_sor3_list_model_get_item;
+}
+
+G_DEFINE_TYPE_WITH_CODE (GtkSor3ListModel, gtk_sor3_list_model, G_TYPE_OBJECT,
+ G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_sor3_list_model_model_init))
+
+static void
+gtk_sor3_list_model_clear_items (GtkSor3ListModel *self)
+{
+ sort_array_clear (&self->items);
+}
+
+static gboolean
+gtk_sor3_list_model_should_sort (GtkSor3ListModel *self)
+{
+ return self->sorter != NULL &&
+ self->model != NULL &&
+ gtk_sorter_get_order (self->sorter) != GTK_SORTER_ORDER_NONE;
+}
+
+static void
+gtk_sor3_list_model_create_items (GtkSor3ListModel *self)
+{
+ guint i, n_items;
+
+ if (!gtk_sor3_list_model_should_sort (self))
+ return;
+
+ n_items = g_list_model_get_n_items (self->model);
+ sort_array_reserve (&self->items, n_items);
+ for (i = 0; i < n_items; i++)
+ {
+ sort_array_append (&self->items, &(SortItem) { g_list_model_get_item (self->model, i), i });
+ }
+}
+
+static int
+sort_func (gconstpointer a,
+ gconstpointer b,
+ gpointer data)
+{
+ SortItem *sa = (SortItem *) a;
+ SortItem *sb = (SortItem *) b;
+
+ return gtk_sorter_compare (data, sa->item, sb->item);
+}
+
+static void
+gtk_sor3_list_model_resort (GtkSor3ListModel *self)
+{
+ g_qsort_with_data (sort_array_get_data (&self->items),
+ sort_array_get_size (&self->items),
+ sizeof (SortItem),
+ sort_func,
+ self->sorter);
+}
+
+static void
+gtk_sor3_list_model_remove_items (GtkSor3ListModel *self,
+ guint position,
+ guint removed,
+ guint added)
+{
+ guint i, n_items, valid;
+
+ n_items = sort_array_get_size (&self->items);
+
+ valid = 0;
+ for (i = 0; i < n_items; i++)
+ {
+ SortItem *si = sort_array_index (&self->items, i);
+
+ if (si->position >= position + removed)
+ si->position = si->position - removed + added;
+ else if (si->position >= position)
+ {
+ sort_item_clear (si);
+ continue;
+ }
+ if (valid < i)
+ *sort_array_index (&self->items, valid) = *sort_array_index (&self->items, i);
+ valid++;
+ }
+
+ g_assert (valid == n_items - removed);
+ memset (sort_array_index (&self->items, valid), 0, sizeof (SortItem) * removed);
+ sort_array_set_size (&self->items, valid);
+}
+
+static void
+gtk_sor3_list_model_items_changed_cb (GListModel *model,
+ guint position,
+ guint removed,
+ guint added,
+ GtkSor3ListModel *self)
+{
+ guint i, n_items;
+
+ if (!gtk_sor3_list_model_should_sort (self))
+ {
+ g_list_model_items_changed (G_LIST_MODEL (self), position, removed, added);
+ return;
+ }
+
+ gtk_sor3_list_model_remove_items (self, position, removed, added);
+ if (added > 0)
+ {
+ sort_array_reserve (&self->items, sort_array_get_size (&self->items) + added);
+ for (i = position; i < position + added; i++)
+ {
+ sort_array_append (&self->items, &(SortItem) { g_list_model_get_item (self->model, i), i });
+ }
+ gtk_sor3_list_model_resort (self);
+ }
+
+ n_items = g_list_model_get_n_items (model);
+ g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items - added + removed, n_items);
+}
+
+static void
+gtk_sor3_list_model_set_property (GObject *object,
+ guint prop_id,
+ const GValue *value,
+ GParamSpec *pspec)
+{
+ GtkSor3ListModel *self = GTK_SOR3_LIST_MODEL (object);
+
+ switch (prop_id)
+ {
+ case PROP_MODEL:
+ gtk_sor3_list_model_set_model (self, g_value_get_object (value));
+ break;
+
+ case PROP_SORTER:
+ gtk_sor3_list_model_set_sorter (self, g_value_get_object (value));
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+ break;
+ }
+}
+
+static void
+gtk_sor3_list_model_get_property (GObject *object,
+ guint prop_id,
+ GValue *value,
+ GParamSpec *pspec)
+{
+ GtkSor3ListModel *self = GTK_SOR3_LIST_MODEL (object);
+
+ switch (prop_id)
+ {
+ case PROP_MODEL:
+ g_value_set_object (value, self->model);
+ break;
+
+ case PROP_SORTER:
+ g_value_set_object (value, self->sorter);
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+ break;
+ }
+}
+
+static void
+gtk_sor3_list_model_sorter_changed_cb (GtkSorter *sorter,
+ int change,
+ GtkSor3ListModel *self)
+{
+ guint n_items;
+
+ if (gtk_sorter_get_order (sorter) == GTK_SORTER_ORDER_NONE)
+ gtk_sor3_list_model_clear_items (self);
+ else if (sort_array_is_empty (&self->items))
+ gtk_sor3_list_model_create_items (self);
+
+ gtk_sor3_list_model_resort (self);
+
+ n_items = g_list_model_get_n_items (G_LIST_MODEL (self));
+ if (n_items > 1)
+ g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items);
+}
+
+static void
+gtk_sor3_list_model_clear_model (GtkSor3ListModel *self)
+{
+ if (self->model == NULL)
+ return;
+
+ g_signal_handlers_disconnect_by_func (self->model, gtk_sor3_list_model_items_changed_cb, self);
+ g_clear_object (&self->model);
+ gtk_sor3_list_model_clear_items (self);
+}
+
+static void
+gtk_sor3_list_model_clear_sorter (GtkSor3ListModel *self)
+{
+ if (self->sorter == NULL)
+ return;
+
+ g_signal_handlers_disconnect_by_func (self->sorter, gtk_sor3_list_model_sorter_changed_cb, self);
+ g_clear_object (&self->sorter);
+ gtk_sor3_list_model_clear_items (self);
+}
+
+static void
+gtk_sor3_list_model_dispose (GObject *object)
+{
+ GtkSor3ListModel *self = GTK_SOR3_LIST_MODEL (object);
+
+ gtk_sor3_list_model_clear_model (self);
+ gtk_sor3_list_model_clear_sorter (self);
+
+ G_OBJECT_CLASS (gtk_sor3_list_model_parent_class)->dispose (object);
+};
+
+static void
+gtk_sor3_list_model_class_init (GtkSor3ListModelClass *class)
+{
+ GObjectClass *gobject_class = G_OBJECT_CLASS (class);
+
+ gobject_class->set_property = gtk_sor3_list_model_set_property;
+ gobject_class->get_property = gtk_sor3_list_model_get_property;
+ gobject_class->dispose = gtk_sor3_list_model_dispose;
+
+ /**
+ * GtkSor3ListModel:sorter:
+ *
+ * The sorter for this model
+ */
+ properties[PROP_SORTER] =
+ g_param_spec_object ("sorter",
+ P_("Sorter"),
+ P_("The sorter for this model"),
+ GTK_TYPE_SORTER,
+ GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
+
+ /**
+ * GtkSor3ListModel:model:
+ *
+ * The model being sorted
+ */
+ properties[PROP_MODEL] =
+ g_param_spec_object ("model",
+ P_("Model"),
+ P_("The model being sorted"),
+ G_TYPE_LIST_MODEL,
+ GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
+
+ g_object_class_install_properties (gobject_class, NUM_PROPERTIES, properties);
+}
+
+static void
+gtk_sor3_list_model_init (GtkSor3ListModel *self)
+{
+}
+
+/**
+ * gtk_sor3_list_model_new:
+ * @model: (allow-none): the model to sort
+ * @sorter: (allow-none): the #GtkSorter to sort @model with
+ *
+ * Creates a new sort list model that uses the @sorter to sort @model.
+ *
+ * Returns: a new #GtkSor3ListModel
+ **/
+GtkSor3ListModel *
+gtk_sor3_list_model_new (GListModel *model,
+ GtkSorter *sorter)
+{
+ GtkSor3ListModel *result;
+
+ g_return_val_if_fail (model == NULL || G_IS_LIST_MODEL (model), NULL);
+ g_return_val_if_fail (sorter == NULL || GTK_IS_SORTER (sorter), NULL);
+
+ result = g_object_new (GTK_TYPE_SOR3_LIST_MODEL,
+ "model", model,
+ "sorter", sorter,
+ NULL);
+
+ return result;
+}
+
+/**
+ * gtk_sor3_list_model_set_model:
+ * @self: a #GtkSor3ListModel
+ * @model: (allow-none): The model to be sorted
+ *
+ * Sets the model to be sorted. The @model's item type must conform to
+ * the item type of @self.
+ **/
+void
+gtk_sor3_list_model_set_model (GtkSor3ListModel *self,
+ GListModel *model)
+{
+ guint removed, added;
+
+ g_return_if_fail (GTK_IS_SOR3_LIST_MODEL (self));
+ g_return_if_fail (model == NULL || G_IS_LIST_MODEL (model));
+
+ if (self->model == model)
+ return;
+
+ removed = g_list_model_get_n_items (G_LIST_MODEL (self));
+ gtk_sor3_list_model_clear_model (self);
+
+ if (model)
+ {
+ self->model = g_object_ref (model);
+ g_signal_connect (model, "items-changed", G_CALLBACK (gtk_sor3_list_model_items_changed_cb), self);
+ added = g_list_model_get_n_items (model);
+
+ gtk_sor3_list_model_create_items (self);
+ gtk_sor3_list_model_resort (self);
+ }
+ else
+ added = 0;
+
+ if (removed > 0 || added > 0)
+ g_list_model_items_changed (G_LIST_MODEL (self), 0, removed, added);
+
+ g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_MODEL]);
+}
+
+/**
+ * gtk_sor3_list_model_get_model:
+ * @self: a #GtkSor3ListModel
+ *
+ * Gets the model currently sorted or %NULL if none.
+ *
+ * Returns: (nullable) (transfer none): The model that gets sorted
+ **/
+GListModel *
+gtk_sor3_list_model_get_model (GtkSor3ListModel *self)
+{
+ g_return_val_if_fail (GTK_IS_SOR3_LIST_MODEL (self), NULL);
+
+ return self->model;
+}
+
+/**
+ * gtk_sor3_list_model_set_sorter:
+ * @self: a #GtkSor3ListModel
+ * @sorter: (allow-none): the #GtkSorter to sort @model with
+ *
+ * Sets a new sorter on @self.
+ */
+void
+gtk_sor3_list_model_set_sorter (GtkSor3ListModel *self,
+ GtkSorter *sorter)
+{
+ g_return_if_fail (GTK_IS_SOR3_LIST_MODEL (self));
+ g_return_if_fail (sorter == NULL || GTK_IS_SORTER (sorter));
+
+ gtk_sor3_list_model_clear_sorter (self);
+
+ if (sorter)
+ {
+ self->sorter = g_object_ref (sorter);
+ g_signal_connect (sorter, "changed", G_CALLBACK (gtk_sor3_list_model_sorter_changed_cb), self);
+ gtk_sor3_list_model_sorter_changed_cb (sorter, GTK_SORTER_CHANGE_DIFFERENT, self);
+ }
+
+ g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_SORTER]);
+}
+
+/**
+ * gtk_sor3_list_model_get_sorter:
+ * @self: a #GtkSor3LisTModel
+ *
+ * Gets the sorter that is used to sort @self.
+ *
+ * Returns: (nullable) (transfer none): the sorter of #self
+ */
+GtkSorter *
+gtk_sor3_list_model_get_sorter (GtkSor3ListModel *self)
+{
+ g_return_val_if_fail (GTK_IS_SOR3_LIST_MODEL (self), NULL);
+
+ return self->sorter;
+}
diff --git a/gtk/gtksor3listmodel.h b/gtk/gtksor3listmodel.h
new file mode 100644
index 0000000000..196693d585
--- /dev/null
+++ b/gtk/gtksor3listmodel.h
@@ -0,0 +1,57 @@
+/*
+ * Copyright © 2018 Benjamin Otte
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Benjamin Otte <otte gnome org>
+ */
+
+#ifndef __GTK_SOR3_LIST_MODEL_H__
+#define __GTK_SOR3_LIST_MODEL_H__
+
+
+#if !defined (__GTK_H_INSIDE__) && !defined (GTK_COMPILATION)
+#error "Only <gtk/gtk.h> can be included directly."
+#endif
+
+#include <gio/gio.h>
+#include <gtk/gtkwidget.h>
+#include <gtk/gtksorter.h>
+
+
+G_BEGIN_DECLS
+
+#define GTK_TYPE_SOR3_LIST_MODEL (gtk_sor3_list_model_get_type ())
+
+GDK_AVAILABLE_IN_ALL
+G_DECLARE_FINAL_TYPE (GtkSor3ListModel, gtk_sor3_list_model, GTK, SOR3_LIST_MODEL, GObject)
+
+GDK_AVAILABLE_IN_ALL
+GtkSor3ListModel * gtk_sor3_list_model_new (GListModel *model,
+ GtkSorter *sorter);
+GDK_AVAILABLE_IN_ALL
+void gtk_sor3_list_model_set_sorter (GtkSor3ListModel *self,
+ GtkSorter *sorter);
+GDK_AVAILABLE_IN_ALL
+GtkSorter * gtk_sor3_list_model_get_sorter (GtkSor3ListModel *self);
+
+GDK_AVAILABLE_IN_ALL
+void gtk_sor3_list_model_set_model (GtkSor3ListModel *self,
+ GListModel *model);
+GDK_AVAILABLE_IN_ALL
+GListModel * gtk_sor3_list_model_get_model (GtkSor3ListModel *self);
+
+G_END_DECLS
+
+#endif /* __GTK_SOR3_LIST_MODEL_H__ */
diff --git a/gtk/meson.build b/gtk/meson.build
index cdc1ca6ed2..1398c932ab 100644
--- a/gtk/meson.build
+++ b/gtk/meson.build
@@ -372,6 +372,7 @@ gtk_public_sources = files([
'gtksnapshot.c',
'gtksorter.c',
'gtksor2listmodel.c',
+ 'gtksor3listmodel.c',
'gtksortlistmodel.c',
'gtkspinbutton.c',
'gtkspinner.c',
@@ -642,6 +643,7 @@ gtk_public_headers = files([
'gtksnapshot.h',
'gtksorter.h',
'gtksor2listmodel.h',
+ 'gtksor3listmodel.h',
'gtksortlistmodel.h',
'gtkspinbutton.h',
'gtkspinner.h',
diff --git a/testsuite/gtk/sort-performance.c b/testsuite/gtk/sort-performance.c
index ef021b7a1f..873bc4a3bd 100644
--- a/testsuite/gtk/sort-performance.c
+++ b/testsuite/gtk/sort-performance.c
@@ -251,7 +251,8 @@ run_test (GtkStringList *source,
{
GType types[] = {
GTK_TYPE_SORT_LIST_MODEL,
- GTK_TYPE_SOR2_LIST_MODEL
+ GTK_TYPE_SOR2_LIST_MODEL,
+ GTK_TYPE_SOR3_LIST_MODEL
};
guint random = g_random_int ();
guint i;
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
