[gtk/wip/otte/listmodel: 5/23] gtk: Add GtkTreeListModel
- From: Benjamin Otte <otte src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/wip/otte/listmodel: 5/23] gtk: Add GtkTreeListModel
- Date: Wed, 12 Sep 2018 11:55:24 +0000 (UTC)
commit 9f2910e190909dcc6a7cbed4bf3937e0d31e45c6
Author: Benjamin Otte <otte redhat com>
Date: Tue Jun 12 03:56:21 2018 +0200
gtk: Add GtkTreeListModel
This is a GListModel implementation with a neat API that can be used to
implement trees inside GtkListBox.
xxx: docs
docs/reference/gtk/gtk4-docs.xml | 5 +
gtk/gtk.h | 1 +
gtk/gtkcssrbtree.c | 761 +++++++++++++++++++++++++++++++++++
gtk/gtkcssrbtreeprivate.h | 90 +++++
gtk/gtktreelistmodel.c | 839 +++++++++++++++++++++++++++++++++++++++
gtk/gtktreelistmodel.h | 74 ++++
gtk/meson.build | 3 +
tests/meson.build | 1 +
tests/testtreelistmodel.c | 152 +++++++
testsuite/gtk/meson.build | 1 +
testsuite/gtk/treelistmodel.c | 260 ++++++++++++
11 files changed, 2187 insertions(+)
---
diff --git a/docs/reference/gtk/gtk4-docs.xml b/docs/reference/gtk/gtk4-docs.xml
index 6ad9a1164f..2104d147ea 100644
--- a/docs/reference/gtk/gtk4-docs.xml
+++ b/docs/reference/gtk/gtk4-docs.xml
@@ -41,6 +41,11 @@
<xi:include href="visual_index.xml" />
</chapter>
+ <chapter id="Lists">
+ <title>GListModel support</title>
+ <xi:include href="xml/gtktreelistmodel.xml" />
+ </chapter>
+
<chapter id="Application">
<title>Application support</title>
<xi:include href="xml/gtkapplication.xml" />
diff --git a/gtk/gtk.h b/gtk/gtk.h
index ec151e5b87..6363fe8210 100644
--- a/gtk/gtk.h
+++ b/gtk/gtk.h
@@ -220,6 +220,7 @@
#include <gtk/gtktooltip.h>
#include <gtk/gtktestutils.h>
#include <gtk/gtktreednd.h>
+#include <gtk/gtktreelistmodel.h>
#include <gtk/gtktreemodel.h>
#include <gtk/gtktreemodelfilter.h>
#include <gtk/gtktreemodelsort.h>
diff --git a/gtk/gtkcssrbtree.c b/gtk/gtkcssrbtree.c
new file mode 100644
index 0000000000..4184238691
--- /dev/null
+++ b/gtk/gtkcssrbtree.c
@@ -0,0 +1,761 @@
+/* gtkrbtree.c
+ * Copyright (C) 2000 Red Hat, Inc., Jonathan Blandford <jrb redhat com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 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
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "config.h"
+
+#include "gtkcssrbtreeprivate.h"
+
+#include "gtkdebug.h"
+
+typedef struct _GtkCssRbNode GtkCssRbNode;
+
+struct _GtkCssRbTree
+{
+ guint ref_count;
+
+ gsize element_size;
+ gsize augment_size;
+ GtkCssRbTreeAugmentFunc augment_func;
+ GDestroyNotify clear_func;
+ GDestroyNotify clear_augment_func;
+
+ GtkCssRbNode *root;
+};
+
+struct _GtkCssRbNode
+{
+ guint red :1;
+ guint dirty :1;
+
+ GtkCssRbNode *left;
+ GtkCssRbNode *right;
+ GtkCssRbNode *parent;
+};
+
+#define NODE_FROM_POINTER(ptr) ((GtkCssRbNode *) ((ptr) ? (((guchar *) (ptr)) - sizeof (GtkCssRbNode)) :
NULL))
+#define NODE_TO_POINTER(node) ((gpointer) ((node) ? (((guchar *) (node)) + sizeof (GtkCssRbNode)) : NULL))
+#define NODE_TO_AUG_POINTER(tree, node) ((gpointer) ((node) ? (((guchar *) (node)) + sizeof (GtkCssRbNode) +
(tree)->element_size) : NULL))
+
+static inline gsize
+gtk_css_rb_node_get_size (GtkCssRbTree *tree)
+{
+ return sizeof (GtkCssRbNode) + tree->element_size + tree->augment_size;
+}
+
+static GtkCssRbNode *
+gtk_css_rb_node_new (GtkCssRbTree *tree)
+{
+ GtkCssRbNode *result;
+
+ result = g_slice_alloc0 (gtk_css_rb_node_get_size (tree));
+
+ result->red = TRUE;
+ result->dirty = TRUE;
+
+ return result;
+}
+
+static void
+gtk_css_rb_node_free (GtkCssRbTree *tree,
+ GtkCssRbNode *node)
+{
+ if (tree->clear_func)
+ tree->clear_func (NODE_TO_POINTER (node));
+ if (tree->clear_augment_func)
+ tree->clear_augment_func (NODE_TO_AUG_POINTER (tree, node));
+
+ g_slice_free1 (gtk_css_rb_node_get_size (tree), node);
+}
+
+static void
+gtk_css_rb_node_free_deep (GtkCssRbTree *tree,
+ GtkCssRbNode *node)
+{
+ GtkCssRbNode *right = node->right;
+
+ if (node->left)
+ gtk_css_rb_node_free_deep (tree, node->left);
+
+ gtk_css_rb_node_free (tree, node);
+
+ if (right)
+ gtk_css_rb_node_free_deep (tree, right);
+}
+
+static void
+gtk_css_rb_node_mark_dirty (GtkCssRbNode *node,
+ gboolean mark_parent)
+{
+ if (node->dirty)
+ return;
+
+ node->dirty = TRUE;
+
+ if (mark_parent && node->parent)
+ gtk_css_rb_node_mark_dirty (node->parent, TRUE);
+}
+
+static void
+gtk_css_rb_node_clean (GtkCssRbTree *tree,
+ GtkCssRbNode *node)
+{
+ if (!node->dirty)
+ return;
+
+ node->dirty = FALSE;
+ if (tree->augment_func)
+ tree->augment_func (tree,
+ NODE_TO_AUG_POINTER (tree, node),
+ NODE_TO_POINTER (node),
+ NODE_TO_POINTER (node->left),
+ NODE_TO_POINTER (node->right));
+}
+
+static GtkCssRbNode *
+gtk_css_rb_node_get_first (GtkCssRbNode *node)
+{
+ while (node->left)
+ node = node->left;
+
+ return node;
+}
+
+static GtkCssRbNode *
+gtk_css_rb_node_get_last (GtkCssRbNode *node)
+{
+ while (node->right)
+ node = node->right;
+
+ return node;
+}
+
+static GtkCssRbNode *
+gtk_css_rb_node_get_previous (GtkCssRbNode *node)
+{
+ GtkCssRbNode *parent;
+
+ if (node->left)
+ return gtk_css_rb_node_get_last (node->left);
+
+ for (parent = node->parent; parent != NULL; parent = node->parent)
+ {
+ if (parent->right == node)
+ return parent;
+
+ node = parent;
+ }
+
+ return NULL;
+}
+
+static GtkCssRbNode *
+gtk_css_rb_node_get_next (GtkCssRbNode *node)
+{
+ GtkCssRbNode *parent;
+
+ if (node->right)
+ return gtk_css_rb_node_get_first (node->right);
+
+ for (parent = node->parent; parent != NULL; parent = node->parent)
+ {
+ if (parent->left == node)
+ return parent;
+
+ node = parent;
+ }
+
+ return NULL;
+}
+
+static void
+gtk_css_rb_node_rotate_left (GtkCssRbTree *tree,
+ GtkCssRbNode *node)
+{
+ GtkCssRbNode *right;
+
+ right = node->right;
+
+ node->right = right->left;
+ if (right->left)
+ right->left->parent = node;
+
+ right->parent = node->parent;
+ if (node->parent)
+ {
+ if (node == node->parent->left)
+ node->parent->left = right;
+ else
+ node->parent->right = right;
+ }
+ else
+ {
+ tree->root = right;
+ }
+
+ right->left = node;
+ node->parent = right;
+
+ gtk_css_rb_node_mark_dirty (node, FALSE);
+ gtk_css_rb_node_mark_dirty (right, FALSE);
+}
+
+static void
+gtk_css_rb_node_rotate_right (GtkCssRbTree *tree,
+ GtkCssRbNode *node)
+{
+ GtkCssRbNode *left;
+
+ left = node->left;
+
+ node->left = left->right;
+ if (left->right)
+ left->right->parent = node;
+
+ left->parent = node->parent;
+ if (node->parent)
+ {
+ if (node == node->parent->right)
+ node->parent->right = left;
+ else
+ node->parent->left = left;
+ }
+ else
+ {
+ tree->root = left;
+ }
+
+ /* link node and left */
+ left->right = node;
+ node->parent = left;
+
+ gtk_css_rb_node_mark_dirty (node, FALSE);
+ gtk_css_rb_node_mark_dirty (left, FALSE);
+}
+
+static gboolean
+is_red (GtkCssRbNode *node_or_null)
+{
+ if (node_or_null == NULL)
+ return FALSE;
+ else
+ return node_or_null->red;
+}
+
+static inline gboolean
+is_black (GtkCssRbNode *node_or_null)
+{
+ return !is_red (node_or_null);
+}
+
+static void
+set_black (GtkCssRbNode *node_or_null)
+{
+ if (node_or_null == NULL)
+ return;
+
+ node_or_null->red = FALSE;
+}
+
+static void
+set_red (GtkCssRbNode *node_or_null)
+{
+ if (node_or_null == NULL)
+ return;
+
+ node_or_null->red = TRUE;
+}
+
+static void
+gtk_css_rb_tree_insert_fixup (GtkCssRbTree *tree,
+ GtkCssRbNode *node)
+{
+
+ /* check Red-Black properties */
+ while (node->parent && is_red (node->parent))
+ {
+ /* we have a violation */
+ g_assert (node->parent->parent);
+
+ if (node->parent == node->parent->parent->left)
+ {
+ GtkCssRbNode *uncle = node->parent->parent->right;
+
+ if (is_red (uncle))
+ {
+ /* uncle is red */
+ set_black (node->parent);
+ set_black (uncle);
+ set_red (node->parent->parent);
+ node = node->parent->parent;
+ }
+ else
+ {
+ /* uncle is black */
+ if (node == node->parent->right)
+ {
+ /* make node a left child */
+ node = node->parent;
+ gtk_css_rb_node_rotate_left (tree, node);
+ }
+ /* recolor and rotate */
+ set_black (node->parent);
+ set_red (node->parent->parent);
+ gtk_css_rb_node_rotate_right (tree, node->parent->parent);
+ }
+ }
+ else
+ {
+ /* mirror image of above code */
+ GtkCssRbNode *uncle = node->parent->parent->left;
+
+ if (is_red (uncle))
+ {
+ /* uncle is red */
+ set_black (node->parent);
+ set_black (uncle);
+ set_red (node->parent->parent);
+ node = node->parent->parent;
+ }
+ else
+ {
+ /* uncle is black */
+ if (node == node->parent->left)
+ {
+ node = node->parent;
+ gtk_css_rb_node_rotate_right (tree, node);
+ }
+ set_black (node->parent);
+ set_red (node->parent->parent);
+ gtk_css_rb_node_rotate_left (tree, node->parent->parent);
+ }
+ }
+ }
+
+ set_black (tree->root);
+}
+
+static void
+gtk_css_rb_tree_remove_node_fixup (GtkCssRbTree *tree,
+ GtkCssRbNode *node,
+ GtkCssRbNode *parent)
+{
+ while (node->parent && is_black (node))
+ {
+ if (node == parent->left)
+ {
+ GtkCssRbNode *w = parent->right;
+
+ if (is_red (w))
+ {
+ set_black (w);
+ set_red (parent);
+ gtk_css_rb_node_rotate_left (tree, parent);
+ w = parent->right;
+ }
+ if (is_black (w->left) && is_black (w->right))
+ {
+ set_red (w);
+ node = parent;
+ }
+ else
+ {
+ if (is_black (w->right))
+ {
+ set_black (w->left);
+ set_red (w);
+ gtk_css_rb_node_rotate_right (tree, w);
+ w = parent->right;
+ }
+ w->red = parent->red;
+ set_black (parent);
+ set_black (w->right);
+ gtk_css_rb_node_rotate_left (tree, parent);
+ node = tree->root;
+ }
+ }
+ else
+ {
+ GtkCssRbNode *w = parent->left;
+ if (is_red (w))
+ {
+ set_black (w);
+ set_red (parent);
+ gtk_css_rb_node_rotate_right (tree, parent);
+ w = parent->left;
+ }
+ if (is_black (w->right) && is_black (w->left))
+ {
+ set_red (w);
+ node = parent;
+ }
+ else
+ {
+ if (is_black (w->left))
+ {
+ set_black (w->right);
+ set_red (w);
+ gtk_css_rb_node_rotate_left (tree, w);
+ w = parent->left;
+ }
+ w->red = parent->red;
+ set_black (parent);
+ set_black (w->left);
+ gtk_css_rb_node_rotate_right (tree, parent);
+ node = tree->root;
+ }
+ }
+
+ parent = node->parent;
+ }
+
+ set_black (node);
+}
+
+GtkCssRbTree *
+gtk_css_rb_tree_new_for_size (gsize element_size,
+ gsize augment_size,
+ GtkCssRbTreeAugmentFunc augment_func,
+ GDestroyNotify clear_func,
+ GDestroyNotify clear_augment_func)
+{
+ GtkCssRbTree *tree;
+
+ tree = g_slice_new0 (GtkCssRbTree);
+ tree->ref_count = 1;
+
+ tree->element_size = element_size;
+ tree->augment_size = augment_size;
+ tree->augment_func = augment_func;
+ tree->clear_func = clear_func;
+ tree->clear_augment_func = clear_augment_func;
+
+ return tree;
+}
+
+GtkCssRbTree *
+gtk_css_rb_tree_ref (GtkCssRbTree *tree)
+{
+ tree->ref_count++;
+
+ return tree;
+}
+
+void
+gtk_css_rb_tree_unref (GtkCssRbTree *tree)
+{
+ tree->ref_count--;
+ if (tree->ref_count > 0)
+ return;
+
+ if (tree->root)
+ gtk_css_rb_node_free_deep (tree, tree->root);
+
+ g_slice_free (GtkCssRbTree, tree);
+}
+
+gpointer
+gtk_css_rb_tree_get_first (GtkCssRbTree *tree)
+{
+ if (tree->root == NULL)
+ return NULL;
+
+ return NODE_TO_POINTER (gtk_css_rb_node_get_first (tree->root));
+}
+
+gpointer
+gtk_css_rb_tree_get_last (GtkCssRbTree *tree)
+{
+ if (tree->root == NULL)
+ return NULL;
+
+ return NODE_TO_POINTER (gtk_css_rb_node_get_last (tree->root));
+}
+
+gpointer
+gtk_css_rb_tree_get_previous (GtkCssRbTree *tree,
+ gpointer node)
+{
+ return NODE_TO_POINTER (gtk_css_rb_node_get_previous (NODE_FROM_POINTER (node)));
+}
+
+gpointer
+gtk_css_rb_tree_get_next (GtkCssRbTree *tree,
+ gpointer node)
+{
+ return NODE_TO_POINTER (gtk_css_rb_node_get_next (NODE_FROM_POINTER (node)));
+}
+
+gpointer
+gtk_css_rb_tree_get_root (GtkCssRbTree *tree)
+{
+ return NODE_TO_POINTER (tree->root);
+}
+
+gpointer
+gtk_css_rb_tree_get_parent (GtkCssRbTree *tree,
+ gpointer node)
+{
+ return NODE_TO_POINTER (NODE_FROM_POINTER (node)->parent);
+}
+
+gpointer
+gtk_css_rb_tree_get_left (GtkCssRbTree *tree,
+ gpointer node)
+{
+ return NODE_TO_POINTER (NODE_FROM_POINTER (node)->left);
+}
+
+gpointer
+gtk_css_rb_tree_get_right (GtkCssRbTree *tree,
+ gpointer node)
+{
+ return NODE_TO_POINTER (NODE_FROM_POINTER (node)->right);
+}
+
+gpointer
+gtk_css_rb_tree_get_augment (GtkCssRbTree *tree,
+ gpointer node)
+{
+ GtkCssRbNode *rbnode = NODE_FROM_POINTER (node);
+
+ gtk_css_rb_node_clean (tree, rbnode);
+
+ return NODE_TO_AUG_POINTER (tree, rbnode);
+}
+
+void
+gtk_css_rb_tree_mark_dirty (GtkCssRbTree *tree,
+ gpointer node)
+{
+ gtk_css_rb_node_mark_dirty (NODE_FROM_POINTER (node), TRUE);
+}
+
+gpointer
+gtk_css_rb_tree_insert_before (GtkCssRbTree *tree,
+ gpointer node)
+{
+ GtkCssRbNode *result;
+
+ /* setup new node */
+ result = gtk_css_rb_node_new (tree);
+
+ if (tree->root == NULL)
+ {
+ g_assert (node == NULL);
+ tree->root = result;
+ }
+ else if (node == NULL)
+ {
+ return gtk_css_rb_tree_insert_after (tree, gtk_css_rb_tree_get_last (tree));
+ }
+ else
+ {
+ GtkCssRbNode *current = NODE_FROM_POINTER (node);
+
+ if (current->left)
+ {
+ current = gtk_css_rb_node_get_last (current);
+ current->right = result;
+ }
+ else
+ {
+ current->left = result;
+ }
+ result->parent = current;
+ gtk_css_rb_node_mark_dirty (current, TRUE);
+ }
+
+ gtk_css_rb_tree_insert_fixup (tree, result);
+
+ return NODE_TO_POINTER (result);
+}
+
+gpointer
+gtk_css_rb_tree_insert_after (GtkCssRbTree *tree,
+ gpointer node)
+{
+ GtkCssRbNode *result;
+
+ /* setup new node */
+ result = gtk_css_rb_node_new (tree);
+
+ if (tree->root == NULL)
+ {
+ g_assert (node == NULL);
+ tree->root = result;
+ }
+ else if (node == NULL)
+ {
+ return gtk_css_rb_tree_insert_before (tree, gtk_css_rb_tree_get_first (tree));
+ }
+ else
+ {
+ GtkCssRbNode *current = NODE_FROM_POINTER (node);
+
+ if (current->right )
+ {
+ current = gtk_css_rb_node_get_first (current);
+ current->left = result;
+ }
+ else
+ {
+ current->right = result;
+ }
+ result->parent = current;
+ gtk_css_rb_node_mark_dirty (current, TRUE);
+ }
+
+ gtk_css_rb_tree_insert_fixup (tree, result);
+
+ return NODE_TO_POINTER (result);
+}
+
+void
+gtk_css_rb_tree_remove (GtkCssRbTree *tree,
+ gpointer node)
+{
+ GtkCssRbNode *x, *y, *real_node;
+
+ real_node = NODE_FROM_POINTER (node);
+ y = real_node;
+ if (y->left && y->right)
+ {
+ y = y->right;
+
+ while (y->left)
+ y = y->left;
+ }
+
+ /* x is y's only child, or nil */
+ if (y->left)
+ x = y->left;
+ else
+ x = y->right;
+
+ /* remove y from the parent chain */
+ if (x != NULL)
+ x->parent = y->parent;
+ if (y->parent)
+ {
+ if (y == y->parent->left)
+ y->parent->left = x;
+ else
+ y->parent->right = x;
+ gtk_css_rb_node_mark_dirty (y->parent, TRUE);
+ }
+ else
+ {
+ tree->root = x;
+ }
+
+ /* We need to clean up the validity of the tree.
+ */
+ if (x && is_black (y))
+ gtk_css_rb_tree_remove_node_fixup (tree, x, y->parent);
+
+ if (y != real_node)
+ {
+ /* Move the node over */
+ if (is_red (real_node) != is_red (y))
+ y->red = !y->red;
+
+ y->left = real_node->left;
+ if (y->left)
+ y->left->parent = y;
+ y->right = real_node->right;
+ if (y->right)
+ y->right->parent = y;
+ y->parent = real_node->parent;
+ if (y->parent)
+ {
+ if (y->parent->left == real_node)
+ y->parent->left = y;
+ else
+ y->parent->right = y;
+ gtk_css_rb_node_mark_dirty (y->parent, TRUE);
+ }
+ else
+ {
+ tree->root = y;
+ }
+ gtk_css_rb_node_mark_dirty (y, TRUE);
+ }
+
+ gtk_css_rb_node_free (tree, real_node);
+}
+
+void
+gtk_css_rb_tree_remove_all (GtkCssRbTree *tree)
+{
+ if (tree->root)
+ gtk_css_rb_node_free_deep (tree, tree->root);
+
+ tree->root = NULL;
+}
+
+gpointer
+gtk_css_rb_tree_find (GtkCssRbTree *tree,
+ gpointer *out_before,
+ gpointer *out_after,
+ GtkCssRbTreeFindFunc find_func,
+ gpointer user_data)
+{
+ GtkCssRbNode *node, *before = NULL, *after = NULL;
+ int cmp;
+
+ if (tree->root == NULL)
+ {
+ if (out_before)
+ *out_before = NULL;
+ if (out_after)
+ *out_after = NULL;
+
+ return NULL;
+ }
+
+ node = tree->root;
+ for (cmp = find_func (tree, NODE_TO_POINTER (node), user_data);
+ cmp != 0;
+ cmp = find_func (tree, NODE_TO_POINTER (node), user_data))
+ {
+ if (cmp < 0)
+ {
+ before = node;
+ node = node->right;
+ }
+ else /* cmp > 0 */
+ {
+ after = node;
+ node = node->left;
+ }
+ if (node == NULL)
+ {
+ if (out_before)
+ *out_before = NODE_TO_POINTER (before);
+ if (out_after)
+ *out_after = NODE_TO_POINTER (after);
+ return NULL;;
+ }
+ }
+
+ if (out_before)
+ *out_before = NODE_TO_POINTER (gtk_css_rb_node_get_previous (node));
+ if (out_after)
+ *out_after = NODE_TO_POINTER (gtk_css_rb_node_get_next (node));
+
+ return NODE_TO_POINTER (node);
+}
diff --git a/gtk/gtkcssrbtreeprivate.h b/gtk/gtkcssrbtreeprivate.h
new file mode 100644
index 0000000000..f80108dba8
--- /dev/null
+++ b/gtk/gtkcssrbtreeprivate.h
@@ -0,0 +1,90 @@
+/* gtkrb_tree.h
+ * Copyright (C) 2000 Red Hat, Inc., Jonathan Blandford <jrb redhat com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 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
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* A Red-Black Tree implementation used specifically by GtkTreeView.
+ */
+#ifndef __GTK_CSS_RB_TREE_H__
+#define __GTK_CSS_RB_TREE_H__
+
+#include <glib.h>
+
+
+G_BEGIN_DECLS
+
+
+typedef struct _GtkCssRbTree GtkCssRbTree;
+
+typedef void (* GtkCssRbTreeAugmentFunc) (GtkCssRbTree *tree,
+ gpointer node_augment,
+ gpointer node,
+ gpointer left,
+ gpointer right);
+typedef int (* GtkCssRbTreeFindFunc) (GtkCssRbTree *tree,
+ gpointer node,
+ gpointer user_data);
+
+GtkCssRbTree * gtk_css_rb_tree_new_for_size (gsize element_size,
+ gsize augment_size,
+ GtkCssRbTreeAugmentFunc augment_func,
+ GDestroyNotify clear_func,
+ GDestroyNotify clear_augment_func);
+#define gtk_css_rb_tree_new(type, augment_type, augment_func, clear_func, clear_augment_func) \
+ gtk_css_rb_tree_new_for_size (sizeof (type), sizeof (augment_type), (augment_func), (clear_func),
(clear_augment_func))
+
+GtkCssRbTree * gtk_css_rb_tree_ref (GtkCssRbTree *tree);
+void gtk_css_rb_tree_unref (GtkCssRbTree *tree);
+
+gpointer gtk_css_rb_tree_get_first (GtkCssRbTree *tree);
+gpointer gtk_css_rb_tree_get_last (GtkCssRbTree *tree);
+gpointer gtk_css_rb_tree_get_previous (GtkCssRbTree *tree,
+ gpointer node);
+gpointer gtk_css_rb_tree_get_next (GtkCssRbTree *tree,
+ gpointer node);
+
+gpointer gtk_css_rb_tree_get_root (GtkCssRbTree *tree);
+gpointer gtk_css_rb_tree_get_parent (GtkCssRbTree *tree,
+ gpointer node);
+gpointer gtk_css_rb_tree_get_left (GtkCssRbTree *tree,
+ gpointer node);
+gpointer gtk_css_rb_tree_get_right (GtkCssRbTree *tree,
+ gpointer node);
+gpointer gtk_css_rb_tree_get_augment (GtkCssRbTree *tree,
+ gpointer node);
+
+void gtk_css_rb_tree_mark_dirty (GtkCssRbTree *tree,
+ gpointer node);
+
+gpointer gtk_css_rb_tree_insert_before (GtkCssRbTree *tree,
+ gpointer node);
+gpointer gtk_css_rb_tree_insert_after (GtkCssRbTree *tree,
+ gpointer node);
+void gtk_css_rb_tree_remove (GtkCssRbTree *tree,
+ gpointer node);
+void gtk_css_rb_tree_remove_all (GtkCssRbTree *tree);
+
+gpointer gtk_css_rb_tree_find (GtkCssRbTree *tree,
+ gpointer *out_before,
+ gpointer *out_after,
+ GtkCssRbTreeFindFunc find_func,
+ gpointer user_data);
+
+
+
+G_END_DECLS
+
+
+#endif /* __GTK_CSS_RB_TREE_H__ */
diff --git a/gtk/gtktreelistmodel.c b/gtk/gtktreelistmodel.c
new file mode 100644
index 0000000000..dd6e58defc
--- /dev/null
+++ b/gtk/gtktreelistmodel.c
@@ -0,0 +1,839 @@
+/*
+ * 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 "gtktreelistmodel.h"
+
+#include "gtkcssrbtreeprivate.h"
+#include "gtkintl.h"
+#include "gtkprivate.h"
+
+enum {
+ PROP_0,
+ PROP_AUTOEXPAND,
+ PROP_ROOT_MODEL,
+ NUM_PROPERTIES
+};
+
+typedef struct _TreeNode TreeNode;
+typedef struct _TreeAugment TreeAugment;
+
+struct _TreeNode
+{
+ GListModel *model;
+ GtkCssRbTree *children;
+ union {
+ TreeNode *parent;
+ GtkTreeListModel *list;
+ };
+
+ guint empty : 1;
+ guint is_root : 1;
+};
+
+struct _TreeAugment
+{
+ guint n_items;
+ guint n_local;
+};
+
+struct _GtkTreeListModel
+{
+ GObject parent_instance;
+
+ TreeNode root_node;
+
+ GtkTreeListModelCreateModelFunc create_func;
+ gpointer user_data;
+ GDestroyNotify user_destroy;
+
+ guint autoexpand : 1;
+};
+
+struct _GtkTreeListModelClass
+{
+ GObjectClass parent_class;
+};
+
+static GParamSpec *properties[NUM_PROPERTIES] = { NULL, };
+
+static GtkTreeListModel *
+tree_node_get_tree_list_model (TreeNode *node)
+{
+ for (; !node->is_root; node = node->parent)
+ { }
+
+ return node->list;
+}
+
+static TreeNode *
+tree_node_get_nth_child (TreeNode *node,
+ guint position)
+{
+ GtkCssRbTree *tree;
+ TreeNode *child, *tmp;
+ TreeAugment *aug;
+
+ tree = node->children;
+ child = gtk_css_rb_tree_get_root (tree);
+
+ while (TRUE)
+ {
+ tmp = gtk_css_rb_tree_get_left (tree, child);
+ if (tmp)
+ {
+ aug = gtk_css_rb_tree_get_augment (tree, tmp);
+ if (position < aug->n_local)
+ {
+ child = tmp;
+ continue;
+ }
+ position -= aug->n_local;
+ }
+
+ if (position == 0)
+ return child;
+
+ position--;
+
+ child = gtk_css_rb_tree_get_right (tree, child);
+ }
+
+ g_return_val_if_reached (NULL);
+}
+
+static guint
+tree_node_get_n_children (TreeNode *node)
+{
+ TreeAugment *child_aug;
+ TreeNode *child_node;
+
+ if (node->children == NULL)
+ return 0;
+
+ child_node = gtk_css_rb_tree_get_root (node->children);
+ if (child_node == NULL)
+ return 0;
+
+ child_aug = gtk_css_rb_tree_get_augment (node->children, child_node);
+
+ return child_aug->n_items;
+}
+
+static guint
+tree_node_get_local_position (GtkCssRbTree *tree,
+ TreeNode *node)
+{
+ TreeNode *left, *parent;
+ TreeAugment *left_aug;
+ guint n;
+
+ left = gtk_css_rb_tree_get_left (tree, node);
+ if (left)
+ {
+ left_aug = gtk_css_rb_tree_get_augment (tree, left);
+ n = left_aug->n_local;
+ }
+ else
+ {
+ n = 0;
+ }
+
+ for (parent = gtk_css_rb_tree_get_parent (tree, node);
+ parent;
+ parent = gtk_css_rb_tree_get_parent (tree, node))
+ {
+ left = gtk_css_rb_tree_get_left (tree, parent);
+ if (left == node)
+ {
+ /* we are the left node, nothing changes */
+ }
+ else
+ {
+ /* we are the right node */
+ n++;
+ if (left)
+ {
+ left_aug = gtk_css_rb_tree_get_augment (tree, left);
+ n += left_aug->n_local;
+ }
+ }
+ node = parent;
+ }
+
+ return n;
+}
+
+static guint
+tree_node_get_position (TreeNode *node)
+{
+ GtkCssRbTree *tree;
+ TreeNode *left, *parent;
+ TreeAugment *left_aug;
+ guint n;
+
+ for (n = 0;
+ !node->is_root;
+ node = node->parent, n++)
+ {
+ tree = node->parent->children;
+
+ left = gtk_css_rb_tree_get_left (tree, node);
+ if (left)
+ {
+ left_aug = gtk_css_rb_tree_get_augment (tree, left);
+ n += left_aug->n_items;
+ }
+
+ for (parent = gtk_css_rb_tree_get_parent (tree, node);
+ parent;
+ parent = gtk_css_rb_tree_get_parent (tree, node))
+ {
+ left = gtk_css_rb_tree_get_left (tree, parent);
+ if (left == node)
+ {
+ /* we are the left node, nothing changes */
+ }
+ else
+ {
+ /* we are the right node */
+ n += 1 + tree_node_get_n_children (parent);
+ if (left)
+ {
+ left_aug = gtk_css_rb_tree_get_augment (tree, left);
+ n += left_aug->n_items;
+ }
+ }
+ node = parent;
+ }
+ }
+ /* the root isn't visible */
+ n--;
+
+ return n;
+}
+
+static void
+tree_node_mark_dirty (TreeNode *node)
+{
+ for (;
+ !node->is_root;
+ node = node->parent)
+ {
+ gtk_css_rb_tree_mark_dirty (node->parent->children, node);
+ }
+}
+
+static TreeNode *
+gtk_tree_list_model_get_nth (GtkTreeListModel *self,
+ guint position)
+{
+ GtkCssRbTree *tree;
+ TreeNode *node, *tmp;
+ guint n_children;
+
+ n_children = tree_node_get_n_children (&self->root_node);
+ if (n_children <= position)
+ return NULL;
+
+ tree = self->root_node.children;
+ node = gtk_css_rb_tree_get_root (tree);
+
+ while (TRUE)
+ {
+ tmp = gtk_css_rb_tree_get_left (tree, node);
+ if (tmp)
+ {
+ TreeAugment *aug = gtk_css_rb_tree_get_augment (tree, tmp);
+ if (position < aug->n_items)
+ {
+ node = tmp;
+ continue;
+ }
+ position -= aug->n_items;
+ }
+
+ if (position == 0)
+ return node;
+
+ position--;
+
+ n_children = tree_node_get_n_children (node);
+ if (position < n_children)
+ {
+ tree = node->children;
+ node = gtk_css_rb_tree_get_root (tree);
+ continue;
+ }
+ position -= n_children;
+
+ node = gtk_css_rb_tree_get_right (tree, node);
+ }
+
+ g_return_val_if_reached (NULL);
+}
+
+static GType
+gtk_tree_list_model_get_item_type (GListModel *list)
+{
+ GtkTreeListModel *self = GTK_TREE_LIST_MODEL (list);
+
+ return g_list_model_get_item_type (self->root_node.model);
+}
+
+static guint
+gtk_tree_list_model_get_n_items (GListModel *list)
+{
+ GtkTreeListModel *self = GTK_TREE_LIST_MODEL (list);
+
+ return tree_node_get_n_children (&self->root_node);
+}
+
+static gpointer
+gtk_tree_list_model_get_item (GListModel *list,
+ guint position)
+{
+ GtkTreeListModel *self = GTK_TREE_LIST_MODEL (list);
+ TreeNode *node, *parent;
+
+ node = gtk_tree_list_model_get_nth (self, position);
+ if (node == NULL)
+ return NULL;
+
+ parent = node->parent;
+ return g_list_model_get_item (parent->model,
+ tree_node_get_local_position (parent->children, node));
+}
+
+static void
+gtk_tree_list_model_model_init (GListModelInterface *iface)
+{
+ iface->get_item_type = gtk_tree_list_model_get_item_type;
+ iface->get_n_items = gtk_tree_list_model_get_n_items;
+ iface->get_item = gtk_tree_list_model_get_item;
+}
+
+G_DEFINE_TYPE_WITH_CODE (GtkTreeListModel, gtk_tree_list_model, G_TYPE_OBJECT,
+ G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_tree_list_model_model_init))
+
+static void
+gtk_tree_list_model_augment (GtkCssRbTree *tree,
+ gpointer _aug,
+ gpointer _node,
+ gpointer left,
+ gpointer right)
+{
+ TreeAugment *aug = _aug;
+
+ aug->n_items = 1;
+ aug->n_items += tree_node_get_n_children (_node);
+ aug->n_local = 1;
+
+ if (left)
+ {
+ TreeAugment *left_aug = gtk_css_rb_tree_get_augment (tree, left);
+ aug->n_items += left_aug->n_items;
+ aug->n_local += left_aug->n_local;
+ }
+ if (right)
+ {
+ TreeAugment *right_aug = gtk_css_rb_tree_get_augment (tree, right);
+ aug->n_items += right_aug->n_items;
+ aug->n_local += right_aug->n_local;
+ }
+}
+
+static guint
+gtk_tree_list_model_expand_node (GtkTreeListModel *self,
+ TreeNode *node);
+
+static void
+gtk_tree_list_model_items_changed_cb (GListModel *model,
+ guint position,
+ guint removed,
+ guint added,
+ TreeNode *node)
+{
+ GtkTreeListModel *self;
+ TreeNode *child;
+ guint i, tree_position, tree_removed, tree_added, n_local;
+
+ self = tree_node_get_tree_list_model (node);
+ n_local = g_list_model_get_n_items (model) - added + removed;
+
+ if (position < n_local)
+ {
+ child = tree_node_get_nth_child (node, position);
+ tree_position = tree_node_get_position (child);
+ }
+ else
+ {
+ child = NULL;
+ tree_position = tree_node_get_position (node) + tree_node_get_n_children (node) + 1;
+ }
+
+ if (removed)
+ {
+ TreeNode *tmp;
+
+ g_assert (child != NULL);
+ if (position + removed < n_local)
+ {
+ TreeNode *end = tree_node_get_nth_child (node, position + removed);
+ tree_removed = tree_node_get_position (end) - tree_position;
+ }
+ else
+ {
+ tree_removed = tree_node_get_position (node) + tree_node_get_n_children (node) + 1 - tree_position;
+ }
+
+ for (i = 0; i < removed; i++)
+ {
+ tmp = child;
+ child = gtk_css_rb_tree_get_next (node->children, child);
+ gtk_css_rb_tree_remove (node->children, tmp);
+ }
+ }
+ else
+ {
+ tree_removed = 0;
+ }
+
+ tree_added = added;
+ for (i = 0; i < added; i++)
+ {
+ child = gtk_css_rb_tree_insert_before (node->children, child);
+ child->parent = node;
+ if (self->autoexpand)
+ tree_added += gtk_tree_list_model_expand_node (self, child);
+ }
+
+ tree_node_mark_dirty (node);
+
+ g_list_model_items_changed (G_LIST_MODEL (self),
+ tree_position,
+ tree_removed,
+ tree_added);
+}
+
+static void
+gtk_tree_list_model_clear_node (gpointer data)
+{
+ TreeNode *node = data;
+
+ if (node->model)
+ {
+ g_signal_handlers_disconnect_by_func (node->model,
+ gtk_tree_list_model_items_changed_cb,
+ node);
+ g_object_unref (node->model);
+ }
+ if (node->children)
+ gtk_css_rb_tree_unref (node->children);
+}
+
+static void
+gtk_tree_list_model_init_node (GtkTreeListModel *list,
+ TreeNode *self,
+ GListModel *model)
+{
+ gsize i, n;
+ TreeNode *node;
+
+ self->model = g_object_ref (model);
+ g_signal_connect (model,
+ "items-changed",
+ G_CALLBACK (gtk_tree_list_model_items_changed_cb),
+ self);
+ self->children = gtk_css_rb_tree_new (TreeNode,
+ TreeAugment,
+ gtk_tree_list_model_augment,
+ gtk_tree_list_model_clear_node,
+ NULL);
+
+ n = g_list_model_get_n_items (model);
+ node = NULL;
+ for (i = 0; i < n; i++)
+ {
+ node = gtk_css_rb_tree_insert_after (self->children, node);
+ node->parent = self;
+ if (list->autoexpand)
+ gtk_tree_list_model_expand_node (list, node);
+ }
+}
+
+static void
+gtk_tree_list_model_set_property (GObject *object,
+ guint prop_id,
+ const GValue *value,
+ GParamSpec *pspec)
+{
+ GtkTreeListModel *self = GTK_TREE_LIST_MODEL (object);
+
+ switch (prop_id)
+ {
+ case PROP_AUTOEXPAND:
+ gtk_tree_list_model_set_autoexpand (self, g_value_get_boolean (value));
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+ break;
+ }
+}
+
+static void
+gtk_tree_list_model_get_property (GObject *object,
+ guint prop_id,
+ GValue *value,
+ GParamSpec *pspec)
+{
+ GtkTreeListModel *self = GTK_TREE_LIST_MODEL (object);
+
+ switch (prop_id)
+ {
+ case PROP_AUTOEXPAND:
+ g_value_set_boolean (value, self->autoexpand);
+ break;
+
+ case PROP_ROOT_MODEL:
+ g_value_set_object (value, self->root_node.model);
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+ break;
+ }
+}
+
+static void
+gtk_tree_list_model_finalize (GObject *object)
+{
+ GtkTreeListModel *self = GTK_TREE_LIST_MODEL (object);
+
+ gtk_tree_list_model_clear_node (&self->root_node);
+ if (self->user_destroy)
+ self->user_destroy (self->user_data);
+
+ G_OBJECT_CLASS (gtk_tree_list_model_parent_class)->finalize (object);
+};
+
+static void
+gtk_tree_list_model_class_init (GtkTreeListModelClass *class)
+{
+ GObjectClass *gobject_class = G_OBJECT_CLASS (class);
+
+ gobject_class->set_property = gtk_tree_list_model_set_property;
+ gobject_class->get_property = gtk_tree_list_model_get_property;
+ gobject_class->finalize = gtk_tree_list_model_finalize;
+
+ /**
+ * GtkTreeListModel:autoexpand:
+ *
+ * If all rows should be expanded by default
+ */
+ properties[PROP_AUTOEXPAND] =
+ g_param_spec_boolean ("autoexpand",
+ P_("autoexpand"),
+ P_("If all rows should be expanded by default"),
+ FALSE,
+ GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
+
+ /**
+ * GtkTreeListModel:root-model:
+ *
+ * The root model displayed
+ */
+ properties[PROP_ROOT_MODEL] =
+ g_param_spec_object ("root-model",
+ P_("Root model"),
+ P_("The root model displayed"),
+ G_TYPE_LIST_MODEL,
+ GTK_PARAM_READABLE | G_PARAM_EXPLICIT_NOTIFY);
+
+ g_object_class_install_properties (gobject_class, NUM_PROPERTIES, properties);
+}
+
+static void
+gtk_tree_list_model_init (GtkTreeListModel *self)
+{
+ self->root_node.list = self;
+ self->root_node.is_root = TRUE;
+}
+
+/**
+ * gtk_tree_list_model_new:
+ * @root: The #GListModel to use as root
+ * @autoexpand: %TRUE to set the autoexpand property and expand the @root model
+ * @create_func: Function to call to create the #GListModel for the children
+ * of an item
+ * @user_data: Data to pass to @create_func
+ * @user_destroy: Function to call to free @user_data
+ *
+ * Creates a new empty #GtkTreeListModel displaying @root with all rows collapsed.
+ *
+ * Returns: a newly created #GtkTreeListModel.
+ **/
+GtkTreeListModel *
+gtk_tree_list_model_new (GListModel *root,
+ gboolean autoexpand,
+ GtkTreeListModelCreateModelFunc create_func,
+ gpointer user_data,
+ GDestroyNotify user_destroy)
+{
+ GtkTreeListModel *self;
+
+ g_return_val_if_fail (G_IS_LIST_MODEL (root), NULL);
+ g_return_val_if_fail (create_func != NULL, NULL);
+
+ self = g_object_new (GTK_TYPE_TREE_LIST_MODEL,
+ "autoexpand", autoexpand,
+ NULL);
+
+ self->create_func = create_func;
+ self->user_data = user_data;
+ self->user_destroy = user_destroy;
+
+ gtk_tree_list_model_init_node (self, &self->root_node, g_object_ref (root));
+
+ return self;
+}
+
+/**
+ * gtk_tree_list_model_set_autoexpand:
+ * @self: a #GtkTreeListModel
+ * @autoexpand: %TRUE to make the model autoexpand its rows
+ *
+ * If set to %TRUE, the model will recursively expand all rows that
+ * get added to the model. This can be either rows added by changes
+ * to the underlying models or via gtk_tree_list_model_set_expanded().
+ **/
+void
+gtk_tree_list_model_set_autoexpand (GtkTreeListModel *self,
+ gboolean autoexpand)
+{
+ g_return_if_fail (GTK_IS_TREE_LIST_MODEL (self));
+
+ if (self->autoexpand == autoexpand)
+ return;
+
+ self->autoexpand = autoexpand;
+
+ g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_AUTOEXPAND]);
+}
+
+/**
+ * gtk_tree_list_model_get_autoexpand:
+ * @self: a #GtkTreeListModel
+ *
+ * Gets whether the model is set to automatically expand new rows
+ * that get added. This can be either rows added by changes to the
+ * underlying models or via gtk_tree_list_model_set_expanded().
+ *
+ * Returns: %TRUE if the model is set to autoexpand
+ **/
+gboolean
+gtk_tree_list_model_get_autoexpand (GtkTreeListModel *self)
+{
+ g_return_val_if_fail (GTK_IS_TREE_LIST_MODEL (self), FALSE);
+
+ return self->autoexpand;
+}
+
+guint
+gtk_tree_list_model_get_depth (GtkTreeListModel *self,
+ guint position)
+{
+ TreeNode *node;
+ guint depth;
+
+ g_return_val_if_fail (GTK_IS_TREE_LIST_MODEL (self), FALSE);
+
+ node = gtk_tree_list_model_get_nth (self, position);
+ if (node == NULL)
+ return 0;
+
+ depth = 0;
+ for (node = node->parent;
+ !node->is_root;
+ node = node->parent)
+ depth++;
+
+ return depth;
+}
+
+static GListModel *
+tree_node_create_model (GtkTreeListModel *self,
+ TreeNode *node)
+{
+ TreeNode *parent = node->parent;
+ GListModel *model;
+ GObject *item;
+
+ item = g_list_model_get_item (parent->model,
+ tree_node_get_local_position (parent->children, node));
+ model = self->create_func (item, self->user_data);
+ g_object_unref (item);
+ if (model == NULL)
+ node->empty = TRUE;
+
+ return model;
+}
+
+static guint
+gtk_tree_list_model_expand_node (GtkTreeListModel *self,
+ TreeNode *node)
+{
+ GListModel *model;
+
+ if (node->empty)
+ return 0;
+
+ if (node->model != NULL)
+ return 0;
+
+ model = tree_node_create_model (self, node);
+
+ if (model == NULL)
+ return 0;
+
+ g_assert (g_list_model_get_item_type (model) == g_list_model_get_item_type (self->root_node.model));
+ gtk_tree_list_model_init_node (self, node, model);
+
+ tree_node_mark_dirty (node);
+
+ return tree_node_get_n_children (node);
+}
+
+static void
+gtk_tree_list_model_collapse_node (GtkTreeListModel *self,
+ guint position,
+ TreeNode *node)
+{
+ guint n_items;
+
+ if (node->model == NULL)
+ return;
+
+ n_items = tree_node_get_n_children (node);
+
+ g_clear_pointer (&node->children, gtk_css_rb_tree_unref);
+ g_clear_object (&node->model);
+
+ tree_node_mark_dirty (node);
+
+ if (n_items > 0)
+ g_list_model_items_changed (G_LIST_MODEL (self), position + 1, n_items, 0);
+}
+
+void
+gtk_tree_list_model_set_expanded (GtkTreeListModel *self,
+ guint position,
+ gboolean expanded)
+{
+ TreeNode *node;
+ guint n_items;
+
+ g_return_if_fail (GTK_IS_TREE_LIST_MODEL (self));
+
+ node = gtk_tree_list_model_get_nth (self, position);
+ if (node == NULL)
+ return;
+
+ if (expanded)
+ {
+ n_items = gtk_tree_list_model_expand_node (self, node);
+ if (n_items > 0)
+ g_list_model_items_changed (G_LIST_MODEL (self), position + 1, 0, n_items);
+ }
+ else
+ {
+ gtk_tree_list_model_collapse_node (self, position, node);
+ }
+}
+
+gboolean
+gtk_tree_list_model_get_expanded (GtkTreeListModel *self,
+ guint position)
+{
+ TreeNode *node;
+
+ g_return_val_if_fail (GTK_IS_TREE_LIST_MODEL (self), FALSE);
+
+ node = gtk_tree_list_model_get_nth (self, position);
+ if (node == NULL)
+ return FALSE;
+
+ return node->children != NULL;
+}
+
+gboolean
+gtk_tree_list_model_is_expandable (GtkTreeListModel *self,
+ guint position)
+{
+ GListModel *model;
+ TreeNode *node;
+
+ g_return_val_if_fail (GTK_IS_TREE_LIST_MODEL (self), FALSE);
+
+ node = gtk_tree_list_model_get_nth (self, position);
+ if (node == NULL)
+ return FALSE;
+
+ if (node->empty)
+ return FALSE;
+
+ if (node->model)
+ return TRUE;
+
+ model = tree_node_create_model (self, node);
+ if (model)
+ {
+ g_object_unref (model);
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+static void
+node_dump (TreeNode *node,
+ TreeAugment *aug,
+ guint depth)
+{
+ g_print ("%*s %p %u %u %u\n", 2 * depth, "", node, aug->n_items, aug->n_local, tree_node_get_n_children
(node));
+ if (node->children)
+ {
+ TreeNode *child;
+ for (child = gtk_css_rb_tree_get_first (node->children);
+ child != NULL;
+ child = gtk_css_rb_tree_get_next (node->children, child))
+ {
+ node_dump (child, gtk_css_rb_tree_get_augment (node->children, child), depth + 1);
+ }
+ }
+}
+
+void
+gtk_tree_list_model_dump (GtkTreeListModel *self)
+{
+ node_dump (&self->root_node, &(TreeAugment){ 0, }, 0);
+}
+
diff --git a/gtk/gtktreelistmodel.h b/gtk/gtktreelistmodel.h
new file mode 100644
index 0000000000..389fe121d0
--- /dev/null
+++ b/gtk/gtktreelistmodel.h
@@ -0,0 +1,74 @@
+/*
+ * 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_TREE_LIST_MODEL_H__
+#define __GTK_TREE_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>
+
+
+G_BEGIN_DECLS
+
+#define GTK_TYPE_TREE_LIST_MODEL (gtk_tree_list_model_get_type ())
+
+GDK_AVAILABLE_IN_ALL
+G_DECLARE_FINAL_TYPE (GtkTreeListModel, gtk_tree_list_model, GTK, TREE_LIST_MODEL, GObject)
+
+typedef GListModel * (* GtkTreeListModelCreateModelFunc) (gpointer item, gpointer data);
+
+GDK_AVAILABLE_IN_ALL
+GtkTreeListModel * gtk_tree_list_model_new (GListModel *root,
+ gboolean autoexpand,
+ GtkTreeListModelCreateModelFunc create_func,
+ gpointer data,
+ GDestroyNotify data_destroy);
+
+GDK_AVAILABLE_IN_ALL
+void gtk_tree_list_model_set_autoexpand (GtkTreeListModel *self,
+ gboolean autoexpand);
+GDK_AVAILABLE_IN_ALL
+gboolean gtk_tree_list_model_get_autoexpand (GtkTreeListModel *self);
+
+GDK_AVAILABLE_IN_ALL
+guint gtk_tree_list_model_get_depth (GtkTreeListModel *self,
+ guint position);
+GDK_AVAILABLE_IN_ALL
+void gtk_tree_list_model_set_expanded (GtkTreeListModel *self,
+ guint position,
+ gboolean expanded);
+GDK_AVAILABLE_IN_ALL
+gboolean gtk_tree_list_model_get_expanded (GtkTreeListModel *self,
+ guint position);
+GDK_AVAILABLE_IN_ALL
+gboolean gtk_tree_list_model_is_expandable (GtkTreeListModel *self,
+ guint position);
+GDK_AVAILABLE_IN_ALL
+void
+gtk_tree_list_model_dump (GtkTreeListModel *self);
+
+
+G_END_DECLS
+
+#endif /* __GTK_TREE_LIST_MODEL_H__ */
diff --git a/gtk/meson.build b/gtk/meson.build
index 92b811ee56..63d92174b5 100644
--- a/gtk/meson.build
+++ b/gtk/meson.build
@@ -79,6 +79,7 @@ gtk_private_sources = files([
'gtkcssparser.c',
'gtkcsspathnode.c',
'gtkcsspositionvalue.c',
+ 'gtkcssrbtree.c',
'gtkcssrepeatvalue.c',
'gtkcssrgbavalue.c',
'gtkcssselector.c',
@@ -366,6 +367,7 @@ gtk_public_sources = files([
'gtktooltip.c',
'gtktooltipwindow.c',
'gtktreednd.c',
+ 'gtktreelistmodel.c',
'gtktreemenu.c',
'gtktreemodel.c',
'gtktreemodelfilter.c',
@@ -587,6 +589,7 @@ gtk_public_headers = files([
'gtktoolshell.h',
'gtktooltip.h',
'gtktreednd.h',
+ 'gtktreelistmodel.h',
'gtktreemodel.h',
'gtktreemodelfilter.h',
'gtktreemodelsort.h',
diff --git a/tests/meson.build b/tests/meson.build
index 16beab8d36..a6d6350662 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -112,6 +112,7 @@ gtk_tests = [
['testrevealer'],
['testrevealer2'],
['testtitlebar'],
+ ['testtreelistmodel'],
['testsplitheaders'],
['teststackedheaders'],
['testactionbar'],
diff --git a/tests/testtreelistmodel.c b/tests/testtreelistmodel.c
new file mode 100644
index 0000000000..e22b2bcec2
--- /dev/null
+++ b/tests/testtreelistmodel.c
@@ -0,0 +1,152 @@
+#include <gtk/gtk.h>
+
+static GListModel *
+create_list_model_for_directory (gpointer file,
+ gpointer unused)
+{
+ GFileEnumerator *enumerate;
+ GListStore *store;
+ GFile *child;
+ GFileInfo *info;
+
+ enumerate = g_file_enumerate_children (file,
+ G_FILE_ATTRIBUTE_STANDARD_TYPE
+ "," G_FILE_ATTRIBUTE_STANDARD_NAME,
+ 0,
+ NULL,
+ NULL);
+ if (enumerate == NULL)
+ return NULL;
+
+ store = g_list_store_new (G_TYPE_FILE);
+
+ while (g_file_enumerator_iterate (enumerate, &info, NULL, NULL, NULL))
+ {
+ if (info == NULL)
+ break;
+
+ if (g_file_info_get_file_type (info) != G_FILE_TYPE_DIRECTORY)
+ continue;
+
+ child = g_file_get_child (file, g_file_info_get_name (info));
+ g_list_store_append (store, child);
+ g_object_unref (child);
+ }
+
+ g_object_unref (enumerate);
+
+ return G_LIST_MODEL (store);
+}
+
+static GtkTreeListModel *
+get_tree_list_model (GtkWidget *row)
+{
+ return GTK_TREE_LIST_MODEL (g_object_get_data (G_OBJECT (gtk_widget_get_parent (row)), "model"));
+}
+
+static void
+expand_clicked (GtkWidget *button,
+ GtkWidget *row)
+{
+ gtk_tree_list_model_set_expanded (get_tree_list_model (row),
+ gtk_list_box_row_get_index (GTK_LIST_BOX_ROW (row)),
+ TRUE);
+}
+
+static void
+collapse_clicked (GtkWidget *button,
+ GtkWidget *row)
+{
+ gtk_tree_list_model_set_expanded (get_tree_list_model (row),
+ gtk_list_box_row_get_index (GTK_LIST_BOX_ROW (row)),
+ FALSE);
+}
+
+static GtkWidget *
+create_widget_for_model (gpointer file,
+ gpointer root)
+{
+ GtkWidget *row, *box, *child;
+ GFile *iter;
+ guint depth;
+
+ row = gtk_list_box_row_new ();
+
+ depth = 0;
+ for (iter = g_object_ref (g_file_get_parent (file));
+ !g_file_equal (root, iter);
+ g_set_object (&iter, g_file_get_parent (iter)))
+ {
+ g_object_unref (iter);
+ depth++;
+ }
+ g_object_unref (iter);
+ g_object_unref (iter);
+
+ box = gtk_box_new (GTK_ORIENTATION_HORIZONTAL, 0);
+ gtk_container_add (GTK_CONTAINER (row), box);
+
+ if (depth > 0)
+ {
+ child = gtk_box_new (GTK_ORIENTATION_HORIZONTAL, 0);
+ gtk_widget_set_size_request (child, 16 * depth, 0);
+ gtk_container_add (GTK_CONTAINER (box), child);
+ }
+
+ child = gtk_button_new_from_icon_name ("list-remove-symbolic");
+ gtk_button_set_relief (GTK_BUTTON (child), GTK_RELIEF_NONE);
+ g_signal_connect (child, "clicked", G_CALLBACK (collapse_clicked), row);
+ gtk_container_add (GTK_CONTAINER (box), child);
+
+ child = gtk_button_new_from_icon_name ("list-add-symbolic");
+ gtk_button_set_relief (GTK_BUTTON (child), GTK_RELIEF_NONE);
+ g_signal_connect (child, "clicked", G_CALLBACK (expand_clicked), row);
+ gtk_container_add (GTK_CONTAINER (box), child);
+
+ child = gtk_label_new (g_file_get_basename (file));
+ gtk_container_add (GTK_CONTAINER (box), child);
+
+ return row;
+}
+
+int
+main (int argc, char *argv[])
+{
+ GtkWidget *win;
+ GtkWidget *sw;
+ GtkWidget *listbox;
+ GListModel *model, *dirmodel;
+ GFile *root;
+
+ gtk_init ();
+
+ win = gtk_window_new (GTK_WINDOW_TOPLEVEL);
+ gtk_window_set_default_size (GTK_WINDOW (win), 400, 600);
+ g_signal_connect (win, "destroy", G_CALLBACK (gtk_main_quit), win);
+
+ sw = gtk_scrolled_window_new (NULL, NULL);
+ gtk_container_add (GTK_CONTAINER (win), sw);
+
+ listbox = gtk_list_box_new ();
+ gtk_container_add (GTK_CONTAINER (sw), listbox);
+
+ root = g_file_new_for_path (g_get_current_dir ());
+ dirmodel = create_list_model_for_directory (root, NULL);
+ model = G_LIST_MODEL (gtk_tree_list_model_new (dirmodel,
+ FALSE,
+ create_list_model_for_directory,
+ NULL, NULL));
+ g_object_unref (dirmodel);
+ gtk_list_box_bind_model (GTK_LIST_BOX (listbox),
+ model,
+ create_widget_for_model,
+ root, g_object_unref);
+ g_object_set_data (G_OBJECT (listbox), "model", model);
+ g_object_unref (model);
+
+ gtk_widget_show (win);
+
+ gtk_main ();
+
+ return 0;
+}
diff --git a/testsuite/gtk/meson.build b/testsuite/gtk/meson.build
index 296aca3206..963355cfbe 100644
--- a/testsuite/gtk/meson.build
+++ b/testsuite/gtk/meson.build
@@ -44,6 +44,7 @@ tests = [
['templates'],
['textbuffer'],
['textiter'],
+ ['treelistmodel'],
['treemodel', ['treemodel.c', 'liststore.c', 'treestore.c', 'filtermodel.c',
'modelrefcount.c', 'sortmodel.c', 'gtktreemodelrefcount.c']],
['treepath'],
diff --git a/testsuite/gtk/treelistmodel.c b/testsuite/gtk/treelistmodel.c
new file mode 100644
index 0000000000..af6683ab66
--- /dev/null
+++ b/testsuite/gtk/treelistmodel.c
@@ -0,0 +1,260 @@
+/* GtkRBTree tests.
+ *
+ * Copyright (C) 2011, Red Hat, Inc.
+ * Authors: Benjamin Otte <otte gnome org>
+ *
+ * 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 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/>.
+ */
+
+#include <locale.h>
+
+#include <gtk/gtk.h>
+
+static GQuark number_quark;
+static GQuark changes_quark;
+
+static guint
+get (GListModel *model,
+ guint position)
+{
+ GObject *object = g_list_model_get_item (model, position);
+ g_assert (object != NULL);
+ return GPOINTER_TO_UINT (g_object_get_qdata (object, number_quark));
+}
+
+static char *
+model_to_string (GListModel *model)
+{
+ GString *string = g_string_new (NULL);
+ guint i;
+
+ for (i = 0; i < g_list_model_get_n_items (model); i++)
+ {
+ if (i > 0)
+ g_string_append (string, " ");
+ g_string_append_printf (string, "%u", get (model, i));
+ }
+
+ return g_string_free (string, FALSE);
+}
+
+static GListStore *
+new_store (guint start,
+ guint end,
+ guint step);
+
+static void
+prepend (GListStore *store,
+ guint number,
+ guint step)
+{
+ GObject *object;
+
+ /* 0 cannot be differentiated from NULL, so don't use it */
+ g_assert (number != 0);
+
+ if (step / 10)
+ object = G_OBJECT (new_store (number - 9 * step / 10, number, step / 10));
+ else
+ object = g_object_new (G_TYPE_OBJECT, NULL);
+ g_object_set_qdata (object, number_quark, GUINT_TO_POINTER (number));
+ g_list_store_insert (store, 0, object);
+ g_object_unref (object);
+}
+
+#define assert_model(model, expected) G_STMT_START{ \
+ char *s = model_to_string (G_LIST_MODEL (model)); \
+ if (!g_str_equal (s, expected)) \
+ g_assertion_message_cmpstr (G_LOG_DOMAIN, __FILE__, __LINE__, G_STRFUNC, \
+ #model " == " #expected, s, "==", expected); \
+ g_free (s); \
+}G_STMT_END
+
+#define assert_changes(model, expected) G_STMT_START{ \
+ GString *changes = g_object_get_qdata (G_OBJECT (model), changes_quark); \
+ if (!g_str_equal (changes->str, expected)) \
+ g_assertion_message_cmpstr (G_LOG_DOMAIN, __FILE__, __LINE__, G_STRFUNC, \
+ #model " == " #expected, changes->str, "==", expected); \
+ g_string_set_size (changes, 0); \
+}G_STMT_END
+
+static GListStore *
+new_empty_store (void)
+{
+ return g_list_store_new (G_TYPE_OBJECT);
+}
+
+static GListStore *
+new_store (guint start,
+ guint end,
+ guint step)
+{
+ GListStore *store = new_empty_store ();
+ guint i;
+
+ for (i = start; i <= end; i += step)
+ prepend (store, i, step);
+
+ return store;
+}
+
+static void
+items_changed (GListModel *model,
+ guint position,
+ guint removed,
+ guint added,
+ GString *changes)
+{
+ g_assert (removed != 0 || added != 0);
+
+ if (changes->len)
+ g_string_append (changes, ", ");
+
+ if (removed == 1 && added == 0)
+ {
+ g_string_append_printf (changes, "-%u", position);
+ }
+ else if (removed == 0 && added == 1)
+ {
+ g_string_append_printf (changes, "+%u", position);
+ }
+ else
+ {
+ g_string_append_printf (changes, "%u", position);
+ if (removed > 0)
+ g_string_append_printf (changes, "-%u", removed);
+ if (added > 0)
+ g_string_append_printf (changes, "+%u", added);
+ }
+}
+
+static void
+free_changes (gpointer data)
+{
+ GString *changes = data;
+
+ /* all changes must have been checked via assert_changes() before */
+ g_assert_cmpstr (changes->str, ==, "");
+
+ g_string_free (changes, TRUE);
+}
+
+static GListModel *
+create_sub_model_cb (gpointer item,
+ gpointer unused)
+{
+ if (G_IS_LIST_MODEL (item))
+ return item;
+
+ return NULL;
+}
+
+static GtkTreeListModel *
+new_model (guint size,
+ gboolean expanded)
+{
+ GtkTreeListModel *tree;
+ GString *changes;
+
+ tree = gtk_tree_list_model_new (G_LIST_MODEL (new_store (size, size, size)), expanded,
create_sub_model_cb, NULL, NULL);
+ changes = g_string_new ("");
+ g_object_set_qdata_full (G_OBJECT(tree), changes_quark, changes, free_changes);
+ g_signal_connect (tree, "items-changed", G_CALLBACK (items_changed), changes);
+
+ return tree;
+}
+
+static void
+test_expand (void)
+{
+ GtkTreeListModel *tree = new_model (100, FALSE);
+ guint i;
+
+ assert_model (tree, "100");
+
+ for (i = g_list_model_get_n_items (G_LIST_MODEL (tree)); i > 0; i--)
+ {
+ gtk_tree_list_model_set_expanded (tree, i - 1, TRUE);
+ }
+ assert_model (tree, "100 100 90 80 70 60 50 40 30 20 10");
+ assert_changes (tree, "1+10");
+
+ for (i = g_list_model_get_n_items (G_LIST_MODEL (tree)); i > 0; i--)
+ {
+ gtk_tree_list_model_set_expanded (tree, i - 1, TRUE);
+ }
+ assert_model (tree, "100 100 100 99 98 97 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78
77 76 75 74 73 72 71 70 70 69 68 67 66 65 64 63 62 61 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45
44 43 42 41 40 40 39 38 37 36 35 34 33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12
11 10 10 9 8 7 6 5 4 3 2 1");
+ assert_changes (tree, "11+10, 10+10, 9+10, 8+10, 7+10, 6+10, 5+10, 4+10, 3+10, 2+10");
+
+ for (i = g_list_model_get_n_items (G_LIST_MODEL (tree)); i > 0; i--)
+ {
+ gtk_tree_list_model_set_expanded (tree, i - 1, TRUE);
+ }
+ assert_model (tree, "100 100 100 99 98 97 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78
77 76 75 74 73 72 71 70 70 69 68 67 66 65 64 63 62 61 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45
44 43 42 41 40 40 39 38 37 36 35 34 33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12
11 10 10 9 8 7 6 5 4 3 2 1");
+ assert_changes (tree, "");
+
+ g_object_unref (tree);
+}
+
+static void
+test_remove_some (void)
+{
+ GtkTreeListModel *tree = new_model (100, TRUE);
+ gpointer item;
+
+ assert_model (tree, "100 100 100 99 98 97 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78
77 76 75 74 73 72 71 70 70 69 68 67 66 65 64 63 62 61 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45
44 43 42 41 40 40 39 38 37 36 35 34 33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12
11 10 10 9 8 7 6 5 4 3 2 1");
+ assert_changes (tree, "");
+
+ item = g_list_model_get_item (G_LIST_MODEL (tree), 1);
+ g_assert (G_IS_LIST_MODEL (item));
+ g_list_store_remove (item, 3);
+ assert_model (tree, "100 100 100 99 98 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78 77
76 75 74 73 72 71 70 70 69 68 67 66 65 64 63 62 61 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45 44
43 42 41 40 40 39 38 37 36 35 34 33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12 11
10 10 9 8 7 6 5 4 3 2 1");
+ assert_changes (tree, "-5");
+
+ item = g_list_model_get_item (G_LIST_MODEL (tree), 0);
+ g_assert (G_IS_LIST_MODEL (item));
+ g_list_store_remove (item, 3);
+ assert_model (tree, "100 100 100 99 98 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78 77
76 75 74 73 72 71 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45 44 43 42 41 40 40 39 38 37 36 35 34
33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12 11 10 10 9 8 7 6 5 4 3 2 1");
+ assert_changes (tree, "33-11");
+
+ item = g_list_model_get_item (G_LIST_MODEL (tree), 88);
+ g_assert (G_IS_LIST_MODEL (item));
+ g_list_store_remove (item, 9);
+ assert_model (tree, "100 100 100 99 98 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78 77
76 75 74 73 72 71 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45 44 43 42 41 40 40 39 38 37 36 35 34
33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12 11 10 10 9 8 7 6 5 4 3 2");
+ assert_changes (tree, "-98");
+
+ item = g_list_model_get_item (G_LIST_MODEL (tree), 0);
+ g_assert (G_IS_LIST_MODEL (item));
+ g_list_store_remove (item, 8);
+ assert_model (tree, "100 100 100 99 98 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78 77
76 75 74 73 72 71 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45 44 43 42 41 40 40 39 38 37 36 35 34
33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12 11");
+ assert_changes (tree, "88-10");
+
+ g_object_unref (tree);
+}
+
+int
+main (int argc, char *argv[])
+{
+ g_test_init (&argc, &argv, NULL);
+ setlocale (LC_ALL, "C");
+ g_test_bug_base ("http://bugzilla.gnome.org/show_bug.cgi?id=%s";);
+
+ number_quark = g_quark_from_static_string ("Hell and fire was spawned to be released.");
+ changes_quark = g_quark_from_static_string ("What did I see? Can I believe what I saw?");
+
+ g_test_add_func ("/treelistmodel/expand", test_expand);
+ g_test_add_func ("/treelistmodel/remove_some", test_remove_some);
+
+ return g_test_run ();
+}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
