1	/* gtktreestore.c
2	* Copyright (C) 2000 Red Hat, Inc., Jonathan Blandford <jrb@redhat.com>
3	*
4	* This library is free software; you can redistribute it and/or
5	* modify it under the terms of the GNU Library General Public
6	* License as published by the Free Software Foundation; either
7	* version 2 of the License, or (at your option) any later version.
8	*
9	* This library is distributed in the hope that it will be useful,
10	* but WITHOUT ANY WARRANTY; without even the implied warranty of
11	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12	* Library General Public License for more details.
13	*
14	* You should have received a copy of the GNU Library General Public
15	* License along with this library. If not, see <http://www.gnu.org/licenses/>.
16	*/
17
18	#include "config.h"
19	#include <string.h>
20	#include <gobject/gvaluecollector.h>
21	#include "gtktreemodel.h"
22	#include "gtktreestore.h"
23	#include "gtktreedatalist.h"
24	#include "gtktreednd.h"
25	#include "gtkbuildable.h"
26	#include "gtkbuilderprivate.h"
27	#include "gtkdebug.h"
28	#include "gtkintl.h"
29
30
31	/**
32	* GtkTreeStore:
33	*
34	* A tree-like data structure that can be used with the GtkTreeView
35	*
36	* The `GtkTreeStore` object is a list model for use with a `GtkTreeView`
37	* widget. It implements the `GtkTreeModel` interface, and consequently,
38	* can use all of the methods available there. It also implements the
39	* `GtkTreeSortable` interface so it can be sorted by the view. Finally,
40	* it also implements the tree
41	* [drag and drop][gtk3-GtkTreeView-drag-and-drop]
42	* interfaces.
43	*
44	* # GtkTreeStore as GtkBuildable
45	*
46	* The GtkTreeStore implementation of the `GtkBuildable` interface allows
47	* to specify the model columns with a <columns> element that may contain
48	* multiple <column> elements, each specifying one model column. The “type”
49	* attribute specifies the data type for the column.
50	*
51	* An example of a UI Definition fragment for a tree store:
52	* |[
53	* <object class="GtkTreeStore">
54	* <columns>
55	* <column type="gchararray"/>
56	* <column type="gchararray"/>
57	* <column type="gint"/>
58	* </columns>
59	* </object>
60	* ]|
61	*/
62
63	struct _GtkTreeStorePrivate
64	{
65	int stamp;
66	GtkSortType order;
67	gpointer root;
68	gpointer last;
69	int n_columns;
70	int sort_column_id;
71	GList *sort_list;
72	GType *column_headers;
73	GtkTreeIterCompareFunc default_sort_func;
74	gpointer default_sort_data;
75	GDestroyNotify default_sort_destroy;
76	guint columns_dirty : 1;
77	};
78
79
80	#define G_NODE(node) ((GNode *)node)
81	#define GTK_TREE_STORE_IS_SORTED(tree) (((GtkTreeStore*)(tree))->priv->sort_column_id != GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
82	#define VALID_ITER(iter, tree_store) ((iter)!= NULL && (iter)->user_data != NULL && ((GtkTreeStore*)(tree_store))->priv->stamp == (iter)->stamp)
83
84	static void gtk_tree_store_tree_model_init (GtkTreeModelIface *iface);
85	static void gtk_tree_store_drag_source_init(GtkTreeDragSourceIface *iface);
86	static void gtk_tree_store_drag_dest_init (GtkTreeDragDestIface *iface);
87	static void gtk_tree_store_sortable_init (GtkTreeSortableIface *iface);
88	static void gtk_tree_store_buildable_init (GtkBuildableIface *iface);
89	static void gtk_tree_store_finalize (GObject *object);
90	static GtkTreeModelFlags gtk_tree_store_get_flags (GtkTreeModel *tree_model);
91	static int gtk_tree_store_get_n_columns (GtkTreeModel *tree_model);
92	static GType gtk_tree_store_get_column_type (GtkTreeModel *tree_model,
93	int index);
94	static gboolean gtk_tree_store_get_iter (GtkTreeModel *tree_model,
95	GtkTreeIter *iter,
96	GtkTreePath *path);
97	static GtkTreePath *gtk_tree_store_get_path (GtkTreeModel *tree_model,
98	GtkTreeIter *iter);
99	static void gtk_tree_store_get_value (GtkTreeModel *tree_model,
100	GtkTreeIter *iter,
101	int column,
102	GValue *value);
103	static gboolean gtk_tree_store_iter_next (GtkTreeModel *tree_model,
104	GtkTreeIter *iter);
105	static gboolean gtk_tree_store_iter_previous (GtkTreeModel *tree_model,
106	GtkTreeIter *iter);
107	static gboolean gtk_tree_store_iter_children (GtkTreeModel *tree_model,
108	GtkTreeIter *iter,
109	GtkTreeIter *parent);
110	static gboolean gtk_tree_store_iter_has_child (GtkTreeModel *tree_model,
111	GtkTreeIter *iter);
112	static int gtk_tree_store_iter_n_children (GtkTreeModel *tree_model,
113	GtkTreeIter *iter);
114	static gboolean gtk_tree_store_iter_nth_child (GtkTreeModel *tree_model,
115	GtkTreeIter *iter,
116	GtkTreeIter *parent,
117	int n);
118	static gboolean gtk_tree_store_iter_parent (GtkTreeModel *tree_model,
119	GtkTreeIter *iter,
120	GtkTreeIter *child);
121
122
123	static void gtk_tree_store_set_n_columns (GtkTreeStore *tree_store,
124	int n_columns);
125	static void gtk_tree_store_set_column_type (GtkTreeStore *tree_store,
126	int column,
127	GType type);
128
129	static void gtk_tree_store_increment_stamp (GtkTreeStore *tree_store);
130
131
132	/* DND interfaces */
133	static gboolean real_gtk_tree_store_row_draggable (GtkTreeDragSource *drag_source,
134	GtkTreePath *path);
135	static gboolean gtk_tree_store_drag_data_delete (GtkTreeDragSource *drag_source,
136	GtkTreePath *path);
137	static GdkContentProvider *
138	gtk_tree_store_drag_data_get (GtkTreeDragSource *drag_source,
139	GtkTreePath *path);
140	static gboolean gtk_tree_store_drag_data_received (GtkTreeDragDest *drag_dest,
141	GtkTreePath *dest,
142	const GValue *value);
143	static gboolean gtk_tree_store_row_drop_possible (GtkTreeDragDest *drag_dest,
144	GtkTreePath *dest_path,
145	const GValue *value);
146
147	/* Sortable Interfaces */
148
149	static void gtk_tree_store_sort (GtkTreeStore *tree_store);
150	static void gtk_tree_store_sort_iter_changed (GtkTreeStore *tree_store,
151	GtkTreeIter *iter,
152	int column,
153	gboolean emit_signal);
154	static gboolean gtk_tree_store_get_sort_column_id (GtkTreeSortable *sortable,
155	int *sort_column_id,
156	GtkSortType *order);
157	static void gtk_tree_store_set_sort_column_id (GtkTreeSortable *sortable,
158	int sort_column_id,
159	GtkSortType order);
160	static void gtk_tree_store_set_sort_func (GtkTreeSortable *sortable,
161	int sort_column_id,
162	GtkTreeIterCompareFunc func,
163	gpointer data,
164	GDestroyNotify destroy);
165	static void gtk_tree_store_set_default_sort_func (GtkTreeSortable *sortable,
166	GtkTreeIterCompareFunc func,
167	gpointer data,
168	GDestroyNotify destroy);
169	static gboolean gtk_tree_store_has_default_sort_func (GtkTreeSortable *sortable);
170
171
172	/* buildable */
173
174	static gboolean gtk_tree_store_buildable_custom_tag_start (GtkBuildable *buildable,
175	GtkBuilder *builder,
176	GObject *child,
177	const char *tagname,
178	GtkBuildableParser *parser,
179	gpointer *data);
180	static void gtk_tree_store_buildable_custom_finished (GtkBuildable *buildable,
181	GtkBuilder *builder,
182	GObject *child,
183	const char *tagname,
184	gpointer user_data);
185
186	static void gtk_tree_store_move (GtkTreeStore *tree_store,
187	GtkTreeIter *iter,
188	GtkTreeIter *position,
189	gboolean before);
190
191
192	#ifdef G_ENABLE_DEBUG
193	static void validate_gnode (GNode *node);
194
195	static inline void
196	validate_tree (GtkTreeStore *tree_store)
197	{
198	if (GTK_DEBUG_CHECK (TREE))
199	{
200	g_assert (G_NODE (tree_store->priv->root)->parent == NULL);
201	validate_gnode (G_NODE (tree_store->priv->root));
202	}
203	}
204	#else
205	#define validate_tree(store)
206	#endif
207
208	G_DEFINE_TYPE_WITH_CODE (GtkTreeStore, gtk_tree_store, G_TYPE_OBJECT,
209	G_ADD_PRIVATE (GtkTreeStore)
210	G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_MODEL,
211	gtk_tree_store_tree_model_init)
212	G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_DRAG_SOURCE,
213	gtk_tree_store_drag_source_init)
214	G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_DRAG_DEST,
215	gtk_tree_store_drag_dest_init)
216	G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_SORTABLE,
217	gtk_tree_store_sortable_init)
218	G_IMPLEMENT_INTERFACE (GTK_TYPE_BUILDABLE,
219	gtk_tree_store_buildable_init))
220
221	static void
222	gtk_tree_store_class_init (GtkTreeStoreClass *class)
223	{
224	GObjectClass *object_class;
225
226	object_class = (GObjectClass *) class;
227
228	object_class->finalize = gtk_tree_store_finalize;
229	}
230
231	static void
232	gtk_tree_store_tree_model_init (GtkTreeModelIface *iface)
233	{
234	iface->get_flags = gtk_tree_store_get_flags;
235	iface->get_n_columns = gtk_tree_store_get_n_columns;
236	iface->get_column_type = gtk_tree_store_get_column_type;
237	iface->get_iter = gtk_tree_store_get_iter;
238	iface->get_path = gtk_tree_store_get_path;
239	iface->get_value = gtk_tree_store_get_value;
240	iface->iter_next = gtk_tree_store_iter_next;
241	iface->iter_previous = gtk_tree_store_iter_previous;
242	iface->iter_children = gtk_tree_store_iter_children;
243	iface->iter_has_child = gtk_tree_store_iter_has_child;
244	iface->iter_n_children = gtk_tree_store_iter_n_children;
245	iface->iter_nth_child = gtk_tree_store_iter_nth_child;
246	iface->iter_parent = gtk_tree_store_iter_parent;
247	}
248
249	static void
250	gtk_tree_store_drag_source_init (GtkTreeDragSourceIface *iface)
251	{
252	iface->row_draggable = real_gtk_tree_store_row_draggable;
253	iface->drag_data_delete = gtk_tree_store_drag_data_delete;
254	iface->drag_data_get = gtk_tree_store_drag_data_get;
255	}
256
257	static void
258	gtk_tree_store_drag_dest_init (GtkTreeDragDestIface *iface)
259	{
260	iface->drag_data_received = gtk_tree_store_drag_data_received;
261	iface->row_drop_possible = gtk_tree_store_row_drop_possible;
262	}
263
264	static void
265	gtk_tree_store_sortable_init (GtkTreeSortableIface *iface)
266	{
267	iface->get_sort_column_id = gtk_tree_store_get_sort_column_id;
268	iface->set_sort_column_id = gtk_tree_store_set_sort_column_id;
269	iface->set_sort_func = gtk_tree_store_set_sort_func;
270	iface->set_default_sort_func = gtk_tree_store_set_default_sort_func;
271	iface->has_default_sort_func = gtk_tree_store_has_default_sort_func;
272	}
273
274	void
275	gtk_tree_store_buildable_init (GtkBuildableIface *iface)
276	{
277	iface->custom_tag_start = gtk_tree_store_buildable_custom_tag_start;
278	iface->custom_finished = gtk_tree_store_buildable_custom_finished;
279	}
280
281	static void
282	gtk_tree_store_init (GtkTreeStore *tree_store)
283	{
284	GtkTreeStorePrivate *priv;
285
286	priv = gtk_tree_store_get_instance_private (self: tree_store);
287	tree_store->priv = priv;
288	priv->root = g_node_new (NULL);
289	/* While the odds are against us getting 0... */
290	do
291	{
292	priv->stamp = g_random_int ();
293	}
294	while (priv->stamp == 0);
295
296	priv->sort_list = NULL;
297	priv->sort_column_id = GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID;
298	priv->columns_dirty = FALSE;
299	}
300
301	/**
302	* gtk_tree_store_new:
303	* @n_columns: number of columns in the tree store
304	* @...: all `GType` types for the columns, from first to last
305	*
306	* Creates a new tree store as with @n_columns columns each of the types passed
307	* in. Note that only types derived from standard GObject fundamental types
308	* are supported.
309	*
310	* As an example,
311	*
312	* ```
313	* gtk_tree_store_new (3, G_TYPE_INT, G_TYPE_STRING, GDK_TYPE_TEXTURE);
314	* ```
315	*
316	* will create a new `GtkTreeStore` with three columns, of type
317	* `int`, `gchararray`, and `GdkTexture` respectively.
318	*
319	* Returns: a new `GtkTreeStore`
320	**/
321	GtkTreeStore *
322	gtk_tree_store_new (int n_columns,
323	...)
324	{
325	GtkTreeStore *retval;
326	va_list args;
327	int i;
328
329	g_return_val_if_fail (n_columns > 0, NULL);
330
331	retval = g_object_new (GTK_TYPE_TREE_STORE, NULL);
332	gtk_tree_store_set_n_columns (tree_store: retval, n_columns);
333
334	va_start (args, n_columns);
335
336	for (i = 0; i < n_columns; i++)
337	{
338	GType type = va_arg (args, GType);
339	if (! _gtk_tree_data_list_check_type (type))
340	{
341	g_warning ("%s: Invalid type %s", G_STRLOC, g_type_name (type));
342	g_object_unref (object: retval);
343	va_end (args);
344	return NULL;
345	}
346	gtk_tree_store_set_column_type (tree_store: retval, column: i, type);
347	}
348	va_end (args);
349
350	return retval;
351	}
352	/**
353	* gtk_tree_store_newv: (rename-to gtk_tree_store_new)
354	* @n_columns: number of columns in the tree store
355	* @types: (array length=n_columns): an array of `GType` types for the columns, from first to last
356	*
357	* Non vararg creation function. Used primarily by language bindings.
358	*
359	* Returns: (transfer full): a new `GtkTreeStore`
360	**/
361	GtkTreeStore *
362	gtk_tree_store_newv (int n_columns,
363	GType *types)
364	{
365	GtkTreeStore *retval;
366	int i;
367
368	g_return_val_if_fail (n_columns > 0, NULL);
369
370	retval = g_object_new (GTK_TYPE_TREE_STORE, NULL);
371	gtk_tree_store_set_n_columns (tree_store: retval, n_columns);
372
373	for (i = 0; i < n_columns; i++)
374	{
375	if (! _gtk_tree_data_list_check_type (type: types[i]))
376	{
377	g_warning ("%s: Invalid type %s", G_STRLOC, g_type_name (types[i]));
378	g_object_unref (object: retval);
379	return NULL;
380	}
381	gtk_tree_store_set_column_type (tree_store: retval, column: i, type: types[i]);
382	}
383
384	return retval;
385	}
386
387
388	/**
389	* gtk_tree_store_set_column_types:
390	* @tree_store: A `GtkTreeStore`
391	* @n_columns: Number of columns for the tree store
392	* @types: (array length=n_columns): An array of `GType` types, one for each column
393	*
394	* This function is meant primarily for `GObjects` that inherit from
395	* `GtkTreeStore`, and should only be used when constructing a new
396	* `GtkTreeStore`. It will not function after a row has been added,
397	* or a method on the `GtkTreeModel` interface is called.
398	**/
399	void
400	gtk_tree_store_set_column_types (GtkTreeStore *tree_store,
401	int n_columns,
402	GType *types)
403	{
404	int i;
405
406	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
407	g_return_if_fail (tree_store->priv->columns_dirty == 0);
408
409	gtk_tree_store_set_n_columns (tree_store, n_columns);
410	for (i = 0; i < n_columns; i++)
411	{
412	if (! _gtk_tree_data_list_check_type (type: types[i]))
413	{
414	g_warning ("%s: Invalid type %s", G_STRLOC, g_type_name (types[i]));
415	continue;
416	}
417	gtk_tree_store_set_column_type (tree_store, column: i, type: types[i]);
418	}
419	}
420
421	static void
422	gtk_tree_store_set_n_columns (GtkTreeStore *tree_store,
423	int n_columns)
424	{
425	GtkTreeStorePrivate *priv = tree_store->priv;
426	int i;
427
428	if (priv->n_columns == n_columns)
429	return;
430
431	priv->column_headers = g_renew (GType, priv->column_headers, n_columns);
432	for (i = priv->n_columns; i < n_columns; i++)
433	priv->column_headers[i] = G_TYPE_INVALID;
434	priv->n_columns = n_columns;
435
436	if (priv->sort_list)
437	_gtk_tree_data_list_header_free (header_list: priv->sort_list);
438
439	priv->sort_list = _gtk_tree_data_list_header_new (n_columns, types: priv->column_headers);
440	}
441
442	/**
443	* gtk_tree_store_set_column_type:
444	* @tree_store: a `GtkTreeStore`
445	* @column: column number
446	* @type: type of the data to be stored in @column
447	*
448	* Supported types include: %G_TYPE_UINT, %G_TYPE_INT, %G_TYPE_UCHAR,
449	* %G_TYPE_CHAR, %G_TYPE_BOOLEAN, %G_TYPE_POINTER, %G_TYPE_FLOAT,
450	* %G_TYPE_DOUBLE, %G_TYPE_STRING, %G_TYPE_OBJECT, and %G_TYPE_BOXED, along with
451	* subclasses of those types such as %GDK_TYPE_PIXBUF.
452	*
453	**/
454	static void
455	gtk_tree_store_set_column_type (GtkTreeStore *tree_store,
456	int column,
457	GType type)
458	{
459	GtkTreeStorePrivate *priv = tree_store->priv;
460
461	if (!_gtk_tree_data_list_check_type (type))
462	{
463	g_warning ("%s: Invalid type %s", G_STRLOC, g_type_name (type));
464	return;
465	}
466	priv->column_headers[column] = type;
467	}
468
469	static gboolean
470	node_free (GNode *node, gpointer data)
471	{
472	if (node->data)
473	_gtk_tree_data_list_free (list: node->data, column_headers: (GType*)data);
474	node->data = NULL;
475
476	return FALSE;
477	}
478
479	static void
480	gtk_tree_store_finalize (GObject *object)
481	{
482	GtkTreeStore *tree_store = GTK_TREE_STORE (object);
483	GtkTreeStorePrivate *priv = tree_store->priv;
484
485	g_node_traverse (root: priv->root, order: G_POST_ORDER, flags: G_TRAVERSE_ALL, max_depth: -1,
486	func: node_free, data: priv->column_headers);
487	g_node_destroy (root: priv->root);
488	_gtk_tree_data_list_header_free (header_list: priv->sort_list);
489	g_free (mem: priv->column_headers);
490
491	if (priv->default_sort_destroy)
492	{
493	GDestroyNotify d = priv->default_sort_destroy;
494
495	priv->default_sort_destroy = NULL;
496	d (priv->default_sort_data);
497	priv->default_sort_data = NULL;
498	}
499
500	/* must chain up */
501	G_OBJECT_CLASS (gtk_tree_store_parent_class)->finalize (object);
502	}
503
504	/* fulfill the GtkTreeModel requirements */
505	/* NOTE: GtkTreeStore::root is a GNode, that acts as the parent node. However,
506	* it is not visible to the tree or to the user., and the path “0” refers to the
507	* first child of GtkTreeStore::root.
508	*/
509
510
511	static GtkTreeModelFlags
512	gtk_tree_store_get_flags (GtkTreeModel *tree_model)
513	{
514	return GTK_TREE_MODEL_ITERS_PERSIST;
515	}
516
517	static int
518	gtk_tree_store_get_n_columns (GtkTreeModel *tree_model)
519	{
520	GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
521	GtkTreeStorePrivate *priv = tree_store->priv;
522
523	priv->columns_dirty = TRUE;
524
525	return priv->n_columns;
526	}
527
528	static GType
529	gtk_tree_store_get_column_type (GtkTreeModel *tree_model,
530	int index)
531	{
532	GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
533	GtkTreeStorePrivate *priv = tree_store->priv;
534
535	g_return_val_if_fail (index < priv->n_columns, G_TYPE_INVALID);
536
537	priv->columns_dirty = TRUE;
538
539	return priv->column_headers[index];
540	}
541
542	static gboolean
543	gtk_tree_store_get_iter (GtkTreeModel *tree_model,
544	GtkTreeIter *iter,
545	GtkTreePath *path)
546	{
547	GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
548	GtkTreeStorePrivate *priv = tree_store->priv;
549	GtkTreeIter parent;
550	int *indices;
551	int depth, i;
552
553	priv->columns_dirty = TRUE;
554
555	indices = gtk_tree_path_get_indices (path);
556	depth = gtk_tree_path_get_depth (path);
557
558	g_return_val_if_fail (depth > 0, FALSE);
559
560	parent.stamp = priv->stamp;
561	parent.user_data = priv->root;
562
563	if (!gtk_tree_store_iter_nth_child (tree_model, iter, parent: &parent, n: indices[0]))
564	{
565	iter->stamp = 0;
566	return FALSE;
567	}
568
569	for (i = 1; i < depth; i++)
570	{
571	parent = *iter;
572	if (!gtk_tree_store_iter_nth_child (tree_model, iter, parent: &parent, n: indices[i]))
573	{
574	iter->stamp = 0;
575	return FALSE;
576	}
577	}
578
579	return TRUE;
580	}
581
582	static GtkTreePath *
583	gtk_tree_store_get_path (GtkTreeModel *tree_model,
584	GtkTreeIter *iter)
585	{
586	GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
587	GtkTreeStorePrivate *priv = tree_store->priv;
588	GtkTreePath *retval;
589	GNode *tmp_node;
590	int i = 0;
591
592	g_return_val_if_fail (iter->user_data != NULL, NULL);
593	g_return_val_if_fail (iter->stamp == priv->stamp, NULL);
594
595	validate_tree (tree_store);
596
597	if (G_NODE (iter->user_data)->parent == NULL &&
598	G_NODE (iter->user_data) == priv->root)
599	return gtk_tree_path_new ();
600	g_assert (G_NODE (iter->user_data)->parent != NULL);
601
602	if (G_NODE (iter->user_data)->parent == G_NODE (priv->root))
603	{
604	retval = gtk_tree_path_new ();
605	tmp_node = G_NODE (priv->root)->children;
606	}
607	else
608	{
609	GtkTreeIter tmp_iter = *iter;
610
611	tmp_iter.user_data = G_NODE (iter->user_data)->parent;
612
613	retval = gtk_tree_store_get_path (tree_model, iter: &tmp_iter);
614	tmp_node = G_NODE (iter->user_data)->parent->children;
615	}
616
617	if (retval == NULL)
618	return NULL;
619
620	if (tmp_node == NULL)
621	{
622	gtk_tree_path_free (path: retval);
623	return NULL;
624	}
625
626	for (; tmp_node; tmp_node = tmp_node->next)
627	{
628	if (tmp_node == G_NODE (iter->user_data))
629	break;
630	i++;
631	}
632
633	if (tmp_node == NULL)
634	{
635	/* We couldn't find node, meaning it's prolly not ours */
636	/* Perhaps I should do a g_return_if_fail here. */
637	gtk_tree_path_free (path: retval);
638	return NULL;
639	}
640
641	gtk_tree_path_append_index (path: retval, index_: i);
642
643	return retval;
644	}
645
646
647	static void
648	gtk_tree_store_get_value (GtkTreeModel *tree_model,
649	GtkTreeIter *iter,
650	int column,
651	GValue *value)
652	{
653	GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
654	GtkTreeStorePrivate *priv = tree_store->priv;
655	GtkTreeDataList *list;
656	int tmp_column = column;
657
658	g_return_if_fail (column < priv->n_columns);
659	g_return_if_fail (VALID_ITER (iter, tree_store));
660
661	list = G_NODE (iter->user_data)->data;
662
663	while (tmp_column-- > 0 && list)
664	list = list->next;
665
666	if (list)
667	{
668	_gtk_tree_data_list_node_to_value (list,
669	type: priv->column_headers[column],
670	value);
671	}
672	else
673	{
674	/* We want to return an initialized but empty (default) value */
675	g_value_init (value, g_type: priv->column_headers[column]);
676	}
677	}
678
679	static gboolean
680	gtk_tree_store_iter_next (GtkTreeModel *tree_model,
681	GtkTreeIter *iter)
682	{
683	g_return_val_if_fail (iter->user_data != NULL, FALSE);
684	g_return_val_if_fail (iter->stamp == GTK_TREE_STORE (tree_model)->priv->stamp, FALSE);
685
686	if (G_NODE (iter->user_data)->next == NULL)
687	{
688	iter->stamp = 0;
689	return FALSE;
690	}
691
692	iter->user_data = G_NODE (iter->user_data)->next;
693
694	return TRUE;
695	}
696
697	static gboolean
698	gtk_tree_store_iter_previous (GtkTreeModel *tree_model,
699	GtkTreeIter *iter)
700	{
701	g_return_val_if_fail (iter->user_data != NULL, FALSE);
702	g_return_val_if_fail (iter->stamp == GTK_TREE_STORE (tree_model)->priv->stamp, FALSE);
703
704	if (G_NODE (iter->user_data)->prev == NULL)
705	{
706	iter->stamp = 0;
707	return FALSE;
708	}
709
710	iter->user_data = G_NODE (iter->user_data)->prev;
711
712	return TRUE;
713	}
714
715	static gboolean
716	gtk_tree_store_iter_children (GtkTreeModel *tree_model,
717	GtkTreeIter *iter,
718	GtkTreeIter *parent)
719	{
720	GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
721	GtkTreeStorePrivate *priv = tree_store->priv;
722	GNode *children;
723
724	if (parent)
725	g_return_val_if_fail (VALID_ITER (parent, tree_store), FALSE);
726
727	if (parent)
728	children = G_NODE (parent->user_data)->children;
729	else
730	children = G_NODE (priv->root)->children;
731
732	if (children)
733	{
734	iter->stamp = priv->stamp;
735	iter->user_data = children;
736	return TRUE;
737	}
738	else
739	{
740	iter->stamp = 0;
741	return FALSE;
742	}
743	}
744
745	static gboolean
746	gtk_tree_store_iter_has_child (GtkTreeModel *tree_model,
747	GtkTreeIter *iter)
748	{
749	g_return_val_if_fail (iter->user_data != NULL, FALSE);
750	g_return_val_if_fail (VALID_ITER (iter, tree_model), FALSE);
751
752	return G_NODE (iter->user_data)->children != NULL;
753	}
754
755	static int
756	gtk_tree_store_iter_n_children (GtkTreeModel *tree_model,
757	GtkTreeIter *iter)
758	{
759	GNode *node;
760	int i = 0;
761
762	g_return_val_if_fail (iter == NULL || iter->user_data != NULL, 0);
763
764	if (iter == NULL)
765	node = G_NODE (GTK_TREE_STORE (tree_model)->priv->root)->children;
766	else
767	node = G_NODE (iter->user_data)->children;
768
769	while (node)
770	{
771	i++;
772	node = node->next;
773	}
774
775	return i;
776	}
777
778	static gboolean
779	gtk_tree_store_iter_nth_child (GtkTreeModel *tree_model,
780	GtkTreeIter *iter,
781	GtkTreeIter *parent,
782	int n)
783	{
784	GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
785	GtkTreeStorePrivate *priv = tree_store->priv;
786	GNode *parent_node;
787	GNode *child;
788
789	g_return_val_if_fail (parent == NULL || parent->user_data != NULL, FALSE);
790
791	if (parent == NULL)
792	parent_node = priv->root;
793	else
794	parent_node = parent->user_data;
795
796	child = g_node_nth_child (node: parent_node, n);
797
798	if (child)
799	{
800	iter->user_data = child;
801	iter->stamp = priv->stamp;
802	return TRUE;
803	}
804	else
805	{
806	iter->stamp = 0;
807	return FALSE;
808	}
809	}
810
811	static gboolean
812	gtk_tree_store_iter_parent (GtkTreeModel *tree_model,
813	GtkTreeIter *iter,
814	GtkTreeIter *child)
815	{
816	GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
817	GtkTreeStorePrivate *priv = tree_store->priv;
818	GNode *parent;
819
820	g_return_val_if_fail (iter != NULL, FALSE);
821	g_return_val_if_fail (VALID_ITER (child, tree_store), FALSE);
822
823	parent = G_NODE (child->user_data)->parent;
824
825	g_assert (parent != NULL);
826
827	if (parent != priv->root)
828	{
829	iter->user_data = parent;
830	iter->stamp = priv->stamp;
831	return TRUE;
832	}
833	else
834	{
835	iter->stamp = 0;
836	return FALSE;
837	}
838	}
839
840
841	/* Does not emit a signal */
842	static gboolean
843	gtk_tree_store_real_set_value (GtkTreeStore *tree_store,
844	GtkTreeIter *iter,
845	int column,
846	GValue *value,
847	gboolean sort)
848	{
849	GtkTreeStorePrivate *priv = tree_store->priv;
850	GtkTreeDataList *list;
851	GtkTreeDataList *prev;
852	int old_column = column;
853	GValue real_value = G_VALUE_INIT;
854	gboolean converted = FALSE;
855	gboolean retval = FALSE;
856
857	if (! g_type_is_a (G_VALUE_TYPE (value), is_a_type: priv->column_headers[column]))
858	{
859	if (! (g_value_type_transformable (G_VALUE_TYPE (value), dest_type: priv->column_headers[column])))
860	{
861	g_warning ("%s: Unable to convert from %s to %s",
862	G_STRLOC,
863	g_type_name (G_VALUE_TYPE (value)),
864	g_type_name (priv->column_headers[column]));
865	return retval;
866	}
867
868	g_value_init (value: &real_value, g_type: priv->column_headers[column]);
869	if (!g_value_transform (src_value: value, dest_value: &real_value))
870	{
871	g_warning ("%s: Unable to make conversion from %s to %s",
872	G_STRLOC,
873	g_type_name (G_VALUE_TYPE (value)),
874	g_type_name (priv->column_headers[column]));
875	g_value_unset (value: &real_value);
876	return retval;
877	}
878	converted = TRUE;
879	}
880
881	prev = list = G_NODE (iter->user_data)->data;
882
883	while (list != NULL)
884	{
885	if (column == 0)
886	{
887	if (converted)
888	_gtk_tree_data_list_value_to_node (list, value: &real_value);
889	else
890	_gtk_tree_data_list_value_to_node (list, value);
891	retval = TRUE;
892	if (converted)
893	g_value_unset (value: &real_value);
894	if (sort && GTK_TREE_STORE_IS_SORTED (tree_store))
895	gtk_tree_store_sort_iter_changed (tree_store, iter, column: old_column, TRUE);
896	return retval;
897	}
898
899	column--;
900	prev = list;
901	list = list->next;
902	}
903
904	if (G_NODE (iter->user_data)->data == NULL)
905	{
906	G_NODE (iter->user_data)->data = list = _gtk_tree_data_list_alloc ();
907	list->next = NULL;
908	}
909	else
910	{
911	list = prev->next = _gtk_tree_data_list_alloc ();
912	list->next = NULL;
913	}
914
915	while (column != 0)
916	{
917	list->next = _gtk_tree_data_list_alloc ();
918	list = list->next;
919	list->next = NULL;
920	column --;
921	}
922
923	if (converted)
924	_gtk_tree_data_list_value_to_node (list, value: &real_value);
925	else
926	_gtk_tree_data_list_value_to_node (list, value);
927
928	retval = TRUE;
929	if (converted)
930	g_value_unset (value: &real_value);
931
932	if (sort && GTK_TREE_STORE_IS_SORTED (tree_store))
933	gtk_tree_store_sort_iter_changed (tree_store, iter, column: old_column, TRUE);
934
935	return retval;
936	}
937
938	/**
939	* gtk_tree_store_set_value:
940	* @tree_store: a `GtkTreeStore`
941	* @iter: A valid `GtkTreeIter` for the row being modified
942	* @column: column number to modify
943	* @value: new value for the cell
944	*
945	* Sets the data in the cell specified by @iter and @column.
946	* The type of @value must be convertible to the type of the
947	* column.
948	*
949	**/
950	void
951	gtk_tree_store_set_value (GtkTreeStore *tree_store,
952	GtkTreeIter *iter,
953	int column,
954	GValue *value)
955	{
956	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
957	g_return_if_fail (VALID_ITER (iter, tree_store));
958	g_return_if_fail (column >= 0 && column < tree_store->priv->n_columns);
959	g_return_if_fail (G_IS_VALUE (value));
960
961	if (gtk_tree_store_real_set_value (tree_store, iter, column, value, TRUE))
962	{
963	GtkTreePath *path;
964
965	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
966	gtk_tree_model_row_changed (GTK_TREE_MODEL (tree_store), path, iter);
967	gtk_tree_path_free (path);
968	}
969	}
970
971	static GtkTreeIterCompareFunc
972	gtk_tree_store_get_compare_func (GtkTreeStore *tree_store)
973	{
974	GtkTreeStorePrivate *priv = tree_store->priv;
975	GtkTreeIterCompareFunc func = NULL;
976
977	if (GTK_TREE_STORE_IS_SORTED (tree_store))
978	{
979	if (priv->sort_column_id != -1)
980	{
981	GtkTreeDataSortHeader *header;
982	header = _gtk_tree_data_list_get_header (header_list: priv->sort_list,
983	sort_column_id: priv->sort_column_id);
984	g_return_val_if_fail (header != NULL, NULL);
985	g_return_val_if_fail (header->func != NULL, NULL);
986	func = header->func;
987	}
988	else
989	{
990	func = priv->default_sort_func;
991	}
992	}
993
994	return func;
995	}
996
997	static void
998	gtk_tree_store_set_vector_internal (GtkTreeStore *tree_store,
999	GtkTreeIter *iter,
1000	gboolean *emit_signal,
1001	gboolean *maybe_need_sort,
1002	int *columns,
1003	GValue *values,
1004	int n_values)
1005	{
1006	GtkTreeStorePrivate *priv = tree_store->priv;
1007	int i;
1008	GtkTreeIterCompareFunc func = NULL;
1009
1010	func = gtk_tree_store_get_compare_func (tree_store);
1011	if (func != _gtk_tree_data_list_compare_func)
1012	*maybe_need_sort = TRUE;
1013
1014	for (i = 0; i < n_values; i++)
1015	{
1016	*emit_signal = gtk_tree_store_real_set_value (tree_store, iter,
1017	column: columns[i], value: &values[i],
1018	FALSE) || *emit_signal;
1019
1020	if (func == _gtk_tree_data_list_compare_func &&
1021	columns[i] == priv->sort_column_id)
1022	*maybe_need_sort = TRUE;
1023	}
1024	}
1025
1026	static void
1027	gtk_tree_store_set_valist_internal (GtkTreeStore *tree_store,
1028	GtkTreeIter *iter,
1029	gboolean *emit_signal,
1030	gboolean *maybe_need_sort,
1031	va_list var_args)
1032	{
1033	GtkTreeStorePrivate *priv = tree_store->priv;
1034	int column;
1035	GtkTreeIterCompareFunc func = NULL;
1036
1037	column = va_arg (var_args, int);
1038
1039	func = gtk_tree_store_get_compare_func (tree_store);
1040	if (func != _gtk_tree_data_list_compare_func)
1041	*maybe_need_sort = TRUE;
1042
1043	while (column != -1)
1044	{
1045	GValue value = G_VALUE_INIT;
1046	char *error = NULL;
1047
1048	if (column < 0 || column >= priv->n_columns)
1049	{
1050	g_warning ("%s: Invalid column number %d added to iter (remember to end your list of columns with a -1)", G_STRLOC, column);
1051	break;
1052	}
1053
1054	G_VALUE_COLLECT_INIT (&value, priv->column_headers[column],
1055	var_args, 0, &error);
1056	if (error)
1057	{
1058	g_warning ("%s: %s", G_STRLOC, error);
1059	g_free (mem: error);
1060
1061	/* we purposely leak the value here, it might not be
1062	* in a sane state if an error condition occurred
1063	*/
1064	break;
1065	}
1066
1067	*emit_signal = gtk_tree_store_real_set_value (tree_store,
1068	iter,
1069	column,
1070	value: &value,
1071	FALSE) || *emit_signal;
1072
1073	if (func == _gtk_tree_data_list_compare_func &&
1074	column == priv->sort_column_id)
1075	*maybe_need_sort = TRUE;
1076
1077	g_value_unset (value: &value);
1078
1079	column = va_arg (var_args, int);
1080	}
1081	}
1082
1083	/**
1084	* gtk_tree_store_set_valuesv: (rename-to gtk_tree_store_set)
1085	* @tree_store: A `GtkTreeStore`
1086	* @iter: A valid `GtkTreeIter` for the row being modified
1087	* @columns: (array length=n_values): an array of column numbers
1088	* @values: (array length=n_values): an array of GValues
1089	* @n_values: the length of the @columns and @values arrays
1090	*
1091	* A variant of gtk_tree_store_set_valist() which takes
1092	* the columns and values as two arrays, instead of varargs. This
1093	* function is mainly intended for language bindings or in case
1094	* the number of columns to change is not known until run-time.
1095	**/
1096	void
1097	gtk_tree_store_set_valuesv (GtkTreeStore *tree_store,
1098	GtkTreeIter *iter,
1099	int *columns,
1100	GValue *values,
1101	int n_values)
1102	{
1103	GtkTreeStorePrivate *priv = tree_store->priv;
1104	gboolean emit_signal = FALSE;
1105	gboolean maybe_need_sort = FALSE;
1106
1107	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1108	g_return_if_fail (VALID_ITER (iter, tree_store));
1109
1110	gtk_tree_store_set_vector_internal (tree_store, iter,
1111	emit_signal: &emit_signal,
1112	maybe_need_sort: &maybe_need_sort,
1113	columns, values, n_values);
1114
1115	if (maybe_need_sort && GTK_TREE_STORE_IS_SORTED (tree_store))
1116	gtk_tree_store_sort_iter_changed (tree_store, iter, column: priv->sort_column_id, TRUE);
1117
1118	if (emit_signal)
1119	{
1120	GtkTreePath *path;
1121
1122	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1123	gtk_tree_model_row_changed (GTK_TREE_MODEL (tree_store), path, iter);
1124	gtk_tree_path_free (path);
1125	}
1126	}
1127
1128	/**
1129	* gtk_tree_store_set_valist:
1130	* @tree_store: A `GtkTreeStore`
1131	* @iter: A valid `GtkTreeIter` for the row being modified
1132	* @var_args: va_list of column/value pairs
1133	*
1134	* See gtk_tree_store_set(); this version takes a va_list for
1135	* use by language bindings.
1136	*
1137	**/
1138	void
1139	gtk_tree_store_set_valist (GtkTreeStore *tree_store,
1140	GtkTreeIter *iter,
1141	va_list var_args)
1142	{
1143	GtkTreeStorePrivate *priv = tree_store->priv;
1144	gboolean emit_signal = FALSE;
1145	gboolean maybe_need_sort = FALSE;
1146
1147	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1148	g_return_if_fail (VALID_ITER (iter, tree_store));
1149
1150	gtk_tree_store_set_valist_internal (tree_store, iter,
1151	emit_signal: &emit_signal,
1152	maybe_need_sort: &maybe_need_sort,
1153	var_args);
1154
1155	if (maybe_need_sort && GTK_TREE_STORE_IS_SORTED (tree_store))
1156	gtk_tree_store_sort_iter_changed (tree_store, iter, column: priv->sort_column_id, TRUE);
1157
1158	if (emit_signal)
1159	{
1160	GtkTreePath *path;
1161
1162	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1163	gtk_tree_model_row_changed (GTK_TREE_MODEL (tree_store), path, iter);
1164	gtk_tree_path_free (path);
1165	}
1166	}
1167
1168	/**
1169	* gtk_tree_store_set:
1170	* @tree_store: A `GtkTreeStore`
1171	* @iter: A valid `GtkTreeIter` for the row being modified
1172	* @...: pairs of column number and value, terminated with -1
1173	*
1174	* Sets the value of one or more cells in the row referenced by @iter.
1175	* The variable argument list should contain integer column numbers,
1176	* each column number followed by the value to be set.
1177	* The list is terminated by a -1. For example, to set column 0 with type
1178	* %G_TYPE_STRING to “Foo”, you would write
1179	* `gtk_tree_store_set (store, iter, 0, "Foo", -1)`.
1180	*
1181	* The value will be referenced by the store if it is a %G_TYPE_OBJECT, and it
1182	* will be copied if it is a %G_TYPE_STRING or %G_TYPE_BOXED.
1183	**/
1184	void
1185	gtk_tree_store_set (GtkTreeStore *tree_store,
1186	GtkTreeIter *iter,
1187	...)
1188	{
1189	va_list var_args;
1190
1191	va_start (var_args, iter);
1192	gtk_tree_store_set_valist (tree_store, iter, var_args);
1193	va_end (var_args);
1194	}
1195
1196	/**
1197	* gtk_tree_store_remove:
1198	* @tree_store: A `GtkTreeStore`
1199	* @iter: A valid `GtkTreeIter`
1200	*
1201	* Removes @iter from @tree_store. After being removed, @iter is set to the
1202	* next valid row at that level, or invalidated if it previously pointed to the
1203	* last one.
1204	*
1205	* Returns: %TRUE if @iter is still valid, %FALSE if not.
1206	**/
1207	gboolean
1208	gtk_tree_store_remove (GtkTreeStore *tree_store,
1209	GtkTreeIter *iter)
1210	{
1211	GtkTreeStorePrivate *priv = tree_store->priv;
1212	GtkTreePath *path;
1213	GtkTreeIter new_iter = {0,};
1214	GNode *parent;
1215	GNode *next_node;
1216
1217	g_return_val_if_fail (GTK_IS_TREE_STORE (tree_store), FALSE);
1218	g_return_val_if_fail (VALID_ITER (iter, tree_store), FALSE);
1219
1220	parent = G_NODE (iter->user_data)->parent;
1221
1222	g_assert (parent != NULL);
1223	next_node = G_NODE (iter->user_data)->next;
1224
1225	if (G_NODE (iter->user_data)->data)
1226	g_node_traverse (G_NODE (iter->user_data), order: G_POST_ORDER, flags: G_TRAVERSE_ALL,
1227	max_depth: -1, func: node_free, data: priv->column_headers);
1228
1229	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1230	g_node_destroy (G_NODE (iter->user_data));
1231
1232	gtk_tree_model_row_deleted (GTK_TREE_MODEL (tree_store), path);
1233
1234	if (parent != G_NODE (priv->root))
1235	{
1236	/* child_toggled */
1237	if (parent->children == NULL)
1238	{
1239	gtk_tree_path_up (path);
1240
1241	new_iter.stamp = priv->stamp;
1242	new_iter.user_data = parent;
1243	gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, iter: &new_iter);
1244	}
1245	}
1246	gtk_tree_path_free (path);
1247
1248	/* revalidate iter */
1249	if (next_node != NULL)
1250	{
1251	iter->stamp = priv->stamp;
1252	iter->user_data = next_node;
1253	return TRUE;
1254	}
1255	else
1256	{
1257	iter->stamp = 0;
1258	iter->user_data = NULL;
1259	}
1260
1261	return FALSE;
1262	}
1263
1264	/**
1265	* gtk_tree_store_insert:
1266	* @tree_store: A `GtkTreeStore`
1267	* @iter: (out): An unset `GtkTreeIter` to set to the new row
1268	* @parent: (nullable): A valid `GtkTreeIter`
1269	* @position: position to insert the new row, or -1 for last
1270	*
1271	* Creates a new row at @position. If parent is non-%NULL, then the row will be
1272	* made a child of @parent. Otherwise, the row will be created at the toplevel.
1273	* If @position is -1 or is larger than the number of rows at that level, then
1274	* the new row will be inserted to the end of the list. @iter will be changed
1275	* to point to this new row. The row will be empty after this function is
1276	* called. To fill in values, you need to call gtk_tree_store_set() or
1277	* gtk_tree_store_set_value().
1278	*
1279	**/
1280	void
1281	gtk_tree_store_insert (GtkTreeStore *tree_store,
1282	GtkTreeIter *iter,
1283	GtkTreeIter *parent,
1284	int position)
1285	{
1286	GtkTreeStorePrivate *priv = tree_store->priv;
1287	GtkTreePath *path;
1288	GNode *parent_node;
1289	GNode *new_node;
1290
1291	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1292	g_return_if_fail (iter != NULL);
1293	if (parent)
1294	g_return_if_fail (VALID_ITER (parent, tree_store));
1295
1296	if (parent)
1297	parent_node = parent->user_data;
1298	else
1299	parent_node = priv->root;
1300
1301	priv->columns_dirty = TRUE;
1302
1303	new_node = g_node_new (NULL);
1304
1305	iter->stamp = priv->stamp;
1306	iter->user_data = new_node;
1307	g_node_insert (parent: parent_node, position, node: new_node);
1308
1309	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1310	gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1311
1312	if (parent_node != priv->root)
1313	{
1314	if (new_node->prev == NULL && new_node->next == NULL)
1315	{
1316	gtk_tree_path_up (path);
1317	gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, iter: parent);
1318	}
1319	}
1320
1321	gtk_tree_path_free (path);
1322
1323	validate_tree (tree_store: (GtkTreeStore*)tree_store);
1324	}
1325
1326	/**
1327	* gtk_tree_store_insert_before:
1328	* @tree_store: A `GtkTreeStore`
1329	* @iter: (out): An unset `GtkTreeIter` to set to the new row
1330	* @parent: (nullable): A valid `GtkTreeIter`
1331	* @sibling: (nullable): A valid `GtkTreeIter`
1332	*
1333	* Inserts a new row before @sibling. If @sibling is %NULL, then the row will
1334	* be appended to @parent ’s children. If @parent and @sibling are %NULL, then
1335	* the row will be appended to the toplevel. If both @sibling and @parent are
1336	* set, then @parent must be the parent of @sibling. When @sibling is set,
1337	* @parent is optional.
1338	*
1339	* @iter will be changed to point to this new row. The row will be empty after
1340	* this function is called. To fill in values, you need to call
1341	* gtk_tree_store_set() or gtk_tree_store_set_value().
1342	*
1343	**/
1344	void
1345	gtk_tree_store_insert_before (GtkTreeStore *tree_store,
1346	GtkTreeIter *iter,
1347	GtkTreeIter *parent,
1348	GtkTreeIter *sibling)
1349	{
1350	GtkTreeStorePrivate *priv = tree_store->priv;
1351	GtkTreePath *path;
1352	GNode *parent_node = NULL;
1353	GNode *new_node;
1354
1355	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1356	g_return_if_fail (iter != NULL);
1357	if (parent != NULL)
1358	g_return_if_fail (VALID_ITER (parent, tree_store));
1359	if (sibling != NULL)
1360	g_return_if_fail (VALID_ITER (sibling, tree_store));
1361
1362	if (parent == NULL && sibling == NULL)
1363	parent_node = priv->root;
1364	else if (parent == NULL)
1365	parent_node = G_NODE (sibling->user_data)->parent;
1366	else if (sibling == NULL)
1367	parent_node = G_NODE (parent->user_data);
1368	else
1369	{
1370	g_return_if_fail (G_NODE (sibling->user_data)->parent == G_NODE (parent->user_data));
1371	parent_node = G_NODE (parent->user_data);
1372	}
1373
1374	priv->columns_dirty = TRUE;
1375
1376	new_node = g_node_new (NULL);
1377
1378	g_node_insert_before (parent: parent_node,
1379	sibling: sibling ? G_NODE (sibling->user_data) : NULL,
1380	node: new_node);
1381
1382	iter->stamp = priv->stamp;
1383	iter->user_data = new_node;
1384
1385	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1386	gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1387
1388	if (parent_node != priv->root)
1389	{
1390	if (new_node->prev == NULL && new_node->next == NULL)
1391	{
1392	GtkTreeIter parent_iter;
1393
1394	parent_iter.stamp = priv->stamp;
1395	parent_iter.user_data = parent_node;
1396
1397	gtk_tree_path_up (path);
1398	gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, iter: &parent_iter);
1399	}
1400	}
1401
1402	gtk_tree_path_free (path);
1403
1404	validate_tree (tree_store);
1405	}
1406
1407	/**
1408	* gtk_tree_store_insert_after:
1409	* @tree_store: A `GtkTreeStore`
1410	* @iter: (out): An unset `GtkTreeIter` to set to the new row
1411	* @parent: (nullable): A valid `GtkTreeIter`
1412	* @sibling: (nullable): A valid `GtkTreeIter`
1413	*
1414	* Inserts a new row after @sibling. If @sibling is %NULL, then the row will be
1415	* prepended to @parent ’s children. If @parent and @sibling are %NULL, then
1416	* the row will be prepended to the toplevel. If both @sibling and @parent are
1417	* set, then @parent must be the parent of @sibling. When @sibling is set,
1418	* @parent is optional.
1419	*
1420	* @iter will be changed to point to this new row. The row will be empty after
1421	* this function is called. To fill in values, you need to call
1422	* gtk_tree_store_set() or gtk_tree_store_set_value().
1423	*
1424	**/
1425	void
1426	gtk_tree_store_insert_after (GtkTreeStore *tree_store,
1427	GtkTreeIter *iter,
1428	GtkTreeIter *parent,
1429	GtkTreeIter *sibling)
1430	{
1431	GtkTreeStorePrivate *priv = tree_store->priv;
1432	GtkTreePath *path;
1433	GNode *parent_node;
1434	GNode *new_node;
1435
1436	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1437	g_return_if_fail (iter != NULL);
1438	if (parent != NULL)
1439	g_return_if_fail (VALID_ITER (parent, tree_store));
1440	if (sibling != NULL)
1441	g_return_if_fail (VALID_ITER (sibling, tree_store));
1442
1443	if (parent == NULL && sibling == NULL)
1444	parent_node = priv->root;
1445	else if (parent == NULL)
1446	parent_node = G_NODE (sibling->user_data)->parent;
1447	else if (sibling == NULL)
1448	parent_node = G_NODE (parent->user_data);
1449	else
1450	{
1451	g_return_if_fail (G_NODE (sibling->user_data)->parent ==
1452	G_NODE (parent->user_data));
1453	parent_node = G_NODE (parent->user_data);
1454	}
1455
1456	priv->columns_dirty = TRUE;
1457
1458	new_node = g_node_new (NULL);
1459
1460	g_node_insert_after (parent: parent_node,
1461	sibling: sibling ? G_NODE (sibling->user_data) : NULL,
1462	node: new_node);
1463
1464	iter->stamp = priv->stamp;
1465	iter->user_data = new_node;
1466
1467	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1468	gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1469
1470	if (parent_node != priv->root)
1471	{
1472	if (new_node->prev == NULL && new_node->next == NULL)
1473	{
1474	GtkTreeIter parent_iter;
1475
1476	parent_iter.stamp = priv->stamp;
1477	parent_iter.user_data = parent_node;
1478
1479	gtk_tree_path_up (path);
1480	gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, iter: &parent_iter);
1481	}
1482	}
1483
1484	gtk_tree_path_free (path);
1485
1486	validate_tree (tree_store);
1487	}
1488
1489	/**
1490	* gtk_tree_store_insert_with_values:
1491	* @tree_store: A `GtkTreeStore`
1492	* @iter: (out) (optional): An unset `GtkTreeIter` to set the new row
1493	* @parent: (nullable): A valid `GtkTreeIter`
1494	* @position: position to insert the new row, or -1 to append after existing rows
1495	* @...: pairs of column number and value, terminated with -1
1496	*
1497	* Creates a new row at @position. @iter will be changed to point to this
1498	* new row. If @position is -1, or larger than the number of rows on the list, then
1499	* the new row will be appended to the list. The row will be filled with
1500	* the values given to this function.
1501	*
1502	* Calling
1503	* `gtk_tree_store_insert_with_values (tree_store, iter, position, ...)`
1504	* has the same effect as calling
1505	* |[<!-- language="C" -->
1506	* gtk_tree_store_insert (tree_store, iter, position);
1507	* gtk_tree_store_set (tree_store, iter, ...);
1508	* ]|
1509	* with the different that the former will only emit a row_inserted signal,
1510	* while the latter will emit row_inserted, row_changed and if the tree store
1511	* is sorted, rows_reordered. Since emitting the rows_reordered signal
1512	* repeatedly can affect the performance of the program,
1513	* gtk_tree_store_insert_with_values() should generally be preferred when
1514	* inserting rows in a sorted tree store.
1515	*/
1516	void
1517	gtk_tree_store_insert_with_values (GtkTreeStore *tree_store,
1518	GtkTreeIter *iter,
1519	GtkTreeIter *parent,
1520	int position,
1521	...)
1522	{
1523	GtkTreeStorePrivate *priv = tree_store->priv;
1524	GtkTreePath *path;
1525	GNode *parent_node;
1526	GNode *new_node;
1527	GtkTreeIter tmp_iter;
1528	va_list var_args;
1529	gboolean changed = FALSE;
1530	gboolean maybe_need_sort = FALSE;
1531
1532	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1533
1534	if (!iter)
1535	iter = &tmp_iter;
1536
1537	if (parent)
1538	g_return_if_fail (VALID_ITER (parent, tree_store));
1539
1540	if (parent)
1541	parent_node = parent->user_data;
1542	else
1543	parent_node = priv->root;
1544
1545	priv->columns_dirty = TRUE;
1546
1547	new_node = g_node_new (NULL);
1548
1549	iter->stamp = priv->stamp;
1550	iter->user_data = new_node;
1551	g_node_insert (parent: parent_node, position, node: new_node);
1552
1553	va_start (var_args, position);
1554	gtk_tree_store_set_valist_internal (tree_store, iter,
1555	emit_signal: &changed, maybe_need_sort: &maybe_need_sort,
1556	var_args);
1557	va_end (var_args);
1558
1559	if (maybe_need_sort && GTK_TREE_STORE_IS_SORTED (tree_store))
1560	gtk_tree_store_sort_iter_changed (tree_store, iter, column: priv->sort_column_id, FALSE);
1561
1562	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1563	gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1564
1565	if (parent_node != priv->root)
1566	{
1567	if (new_node->prev == NULL && new_node->next == NULL)
1568	{
1569	gtk_tree_path_up (path);
1570	gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, iter: parent);
1571	}
1572	}
1573
1574	gtk_tree_path_free (path);
1575
1576	validate_tree (tree_store: (GtkTreeStore *)tree_store);
1577	}
1578
1579	/**
1580	* gtk_tree_store_insert_with_valuesv: (rename-to gtk_tree_store_insert_with_values)
1581	* @tree_store: A `GtkTreeStore`
1582	* @iter: (out) (optional): An unset `GtkTreeIter` to set the new row
1583	* @parent: (nullable): A valid `GtkTreeIter`
1584	* @position: position to insert the new row, or -1 for last
1585	* @columns: (array length=n_values): an array of column numbers
1586	* @values: (array length=n_values): an array of GValues
1587	* @n_values: the length of the @columns and @values arrays
1588	*
1589	* A variant of gtk_tree_store_insert_with_values() which takes
1590	* the columns and values as two arrays, instead of varargs. This
1591	* function is mainly intended for language bindings.
1592	*/
1593	void
1594	gtk_tree_store_insert_with_valuesv (GtkTreeStore *tree_store,
1595	GtkTreeIter *iter,
1596	GtkTreeIter *parent,
1597	int position,
1598	int *columns,
1599	GValue *values,
1600	int n_values)
1601	{
1602	GtkTreeStorePrivate *priv = tree_store->priv;
1603	GtkTreePath *path;
1604	GNode *parent_node;
1605	GNode *new_node;
1606	GtkTreeIter tmp_iter;
1607	gboolean changed = FALSE;
1608	gboolean maybe_need_sort = FALSE;
1609
1610	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1611
1612	if (!iter)
1613	iter = &tmp_iter;
1614
1615	if (parent)
1616	g_return_if_fail (VALID_ITER (parent, tree_store));
1617
1618	if (parent)
1619	parent_node = parent->user_data;
1620	else
1621	parent_node = priv->root;
1622
1623	priv->columns_dirty = TRUE;
1624
1625	new_node = g_node_new (NULL);
1626
1627	iter->stamp = priv->stamp;
1628	iter->user_data = new_node;
1629	g_node_insert (parent: parent_node, position, node: new_node);
1630
1631	gtk_tree_store_set_vector_internal (tree_store, iter,
1632	emit_signal: &changed, maybe_need_sort: &maybe_need_sort,
1633	columns, values, n_values);
1634
1635	if (maybe_need_sort && GTK_TREE_STORE_IS_SORTED (tree_store))
1636	gtk_tree_store_sort_iter_changed (tree_store, iter, column: priv->sort_column_id, FALSE);
1637
1638	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1639	gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1640
1641	if (parent_node != priv->root)
1642	{
1643	if (new_node->prev == NULL && new_node->next == NULL)
1644	{
1645	gtk_tree_path_up (path);
1646	gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, iter: parent);
1647	}
1648	}
1649
1650	gtk_tree_path_free (path);
1651
1652	validate_tree (tree_store: (GtkTreeStore *)tree_store);
1653	}
1654
1655	/**
1656	* gtk_tree_store_prepend:
1657	* @tree_store: A `GtkTreeStore`
1658	* @iter: (out): An unset `GtkTreeIter` to set to the prepended row
1659	* @parent: (nullable): A valid `GtkTreeIter`
1660	*
1661	* Prepends a new row to @tree_store. If @parent is non-%NULL, then it will prepend
1662	* the new row before the first child of @parent, otherwise it will prepend a row
1663	* to the top level. @iter will be changed to point to this new row. The row
1664	* will be empty after this function is called. To fill in values, you need to
1665	* call gtk_tree_store_set() or gtk_tree_store_set_value().
1666	**/
1667	void
1668	gtk_tree_store_prepend (GtkTreeStore *tree_store,
1669	GtkTreeIter *iter,
1670	GtkTreeIter *parent)
1671	{
1672	GtkTreeStorePrivate *priv = tree_store->priv;
1673	GNode *parent_node;
1674
1675	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1676	g_return_if_fail (iter != NULL);
1677	if (parent != NULL)
1678	g_return_if_fail (VALID_ITER (parent, tree_store));
1679
1680	priv->columns_dirty = TRUE;
1681
1682	if (parent == NULL)
1683	parent_node = priv->root;
1684	else
1685	parent_node = parent->user_data;
1686
1687	if (parent_node->children == NULL)
1688	{
1689	GtkTreePath *path;
1690
1691	iter->stamp = priv->stamp;
1692	iter->user_data = g_node_new (NULL);
1693
1694	g_node_prepend (parent: parent_node, G_NODE (iter->user_data));
1695
1696	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1697	gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1698
1699	if (parent_node != priv->root)
1700	{
1701	gtk_tree_path_up (path);
1702	gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, iter: parent);
1703	}
1704	gtk_tree_path_free (path);
1705	}
1706	else
1707	{
1708	gtk_tree_store_insert_after (tree_store, iter, parent, NULL);
1709	}
1710
1711	validate_tree (tree_store);
1712	}
1713
1714	/**
1715	* gtk_tree_store_append:
1716	* @tree_store: A `GtkTreeStore`
1717	* @iter: (out): An unset `GtkTreeIter` to set to the appended row
1718	* @parent: (nullable): A valid `GtkTreeIter`
1719	*
1720	* Appends a new row to @tree_store. If @parent is non-%NULL, then it will append the
1721	* new row after the last child of @parent, otherwise it will append a row to
1722	* the top level. @iter will be changed to point to this new row. The row will
1723	* be empty after this function is called. To fill in values, you need to call
1724	* gtk_tree_store_set() or gtk_tree_store_set_value().
1725	**/
1726	void
1727	gtk_tree_store_append (GtkTreeStore *tree_store,
1728	GtkTreeIter *iter,
1729	GtkTreeIter *parent)
1730	{
1731	GtkTreeStorePrivate *priv = tree_store->priv;
1732	GNode *parent_node;
1733
1734	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1735	g_return_if_fail (iter != NULL);
1736	if (parent != NULL)
1737	g_return_if_fail (VALID_ITER (parent, tree_store));
1738
1739	if (parent == NULL)
1740	parent_node = priv->root;
1741	else
1742	parent_node = parent->user_data;
1743
1744	priv->columns_dirty = TRUE;
1745
1746	if (parent_node->children == NULL)
1747	{
1748	GtkTreePath *path;
1749
1750	iter->stamp = priv->stamp;
1751	iter->user_data = g_node_new (NULL);
1752
1753	g_node_append (parent_node, G_NODE (iter->user_data));
1754
1755	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1756	gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1757
1758	if (parent_node != priv->root)
1759	{
1760	gtk_tree_path_up (path);
1761	gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, iter: parent);
1762	}
1763	gtk_tree_path_free (path);
1764	}
1765	else
1766	{
1767	gtk_tree_store_insert_before (tree_store, iter, parent, NULL);
1768	}
1769
1770	validate_tree (tree_store);
1771	}
1772
1773	/**
1774	* gtk_tree_store_is_ancestor:
1775	* @tree_store: A `GtkTreeStore`
1776	* @iter: A valid `GtkTreeIter`
1777	* @descendant: A valid `GtkTreeIter`
1778	*
1779	* Returns %TRUE if @iter is an ancestor of @descendant. That is, @iter is the
1780	* parent (or grandparent or great-grandparent) of @descendant.
1781	*
1782	* Returns: %TRUE, if @iter is an ancestor of @descendant
1783	**/
1784	gboolean
1785	gtk_tree_store_is_ancestor (GtkTreeStore *tree_store,
1786	GtkTreeIter *iter,
1787	GtkTreeIter *descendant)
1788	{
1789	g_return_val_if_fail (GTK_IS_TREE_STORE (tree_store), FALSE);
1790	g_return_val_if_fail (VALID_ITER (iter, tree_store), FALSE);
1791	g_return_val_if_fail (VALID_ITER (descendant, tree_store), FALSE);
1792
1793	return g_node_is_ancestor (G_NODE (iter->user_data),
1794	G_NODE (descendant->user_data));
1795	}
1796
1797
1798	/**
1799	* gtk_tree_store_iter_depth:
1800	* @tree_store: A `GtkTreeStore`
1801	* @iter: A valid `GtkTreeIter`
1802	*
1803	* Returns the depth of @iter. This will be 0 for anything on the root level, 1
1804	* for anything down a level, etc.
1805	*
1806	* Returns: The depth of @iter
1807	**/
1808	int
1809	gtk_tree_store_iter_depth (GtkTreeStore *tree_store,
1810	GtkTreeIter *iter)
1811	{
1812	g_return_val_if_fail (GTK_IS_TREE_STORE (tree_store), 0);
1813	g_return_val_if_fail (VALID_ITER (iter, tree_store), 0);
1814
1815	return g_node_depth (G_NODE (iter->user_data)) - 2;
1816	}
1817
1818	/* simple ripoff from g_node_traverse_post_order */
1819	static gboolean
1820	gtk_tree_store_clear_traverse (GNode *node,
1821	GtkTreeStore *store)
1822	{
1823	GtkTreeIter iter;
1824
1825	if (node->children)
1826	{
1827	GNode *child;
1828
1829	child = node->children;
1830	while (child)
1831	{
1832	register GNode *current;
1833
1834	current = child;
1835	child = current->next;
1836	if (gtk_tree_store_clear_traverse (node: current, store))
1837	return TRUE;
1838	}
1839
1840	if (node->parent)
1841	{
1842	iter.stamp = store->priv->stamp;
1843	iter.user_data = node;
1844
1845	gtk_tree_store_remove (tree_store: store, iter: &iter);
1846	}
1847	}
1848	else if (node->parent)
1849	{
1850	iter.stamp = store->priv->stamp;
1851	iter.user_data = node;
1852
1853	gtk_tree_store_remove (tree_store: store, iter: &iter);
1854	}
1855
1856	return FALSE;
1857	}
1858
1859	static void
1860	gtk_tree_store_increment_stamp (GtkTreeStore *tree_store)
1861	{
1862	GtkTreeStorePrivate *priv = tree_store->priv;
1863	do
1864	{
1865	priv->stamp++;
1866	}
1867	while (priv->stamp == 0);
1868	}
1869
1870	/**
1871	* gtk_tree_store_clear:
1872	* @tree_store: a `GtkTreeStore`
1873	*
1874	* Removes all rows from @tree_store
1875	**/
1876	void
1877	gtk_tree_store_clear (GtkTreeStore *tree_store)
1878	{
1879	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1880
1881	gtk_tree_store_clear_traverse (node: tree_store->priv->root, store: tree_store);
1882	gtk_tree_store_increment_stamp (tree_store);
1883	}
1884
1885	static gboolean
1886	gtk_tree_store_iter_is_valid_helper (GtkTreeIter *iter,
1887	GNode *first)
1888	{
1889	GNode *node;
1890
1891	node = first;
1892
1893	do
1894	{
1895	if (node == iter->user_data)
1896	return TRUE;
1897
1898	if (node->children)
1899	if (gtk_tree_store_iter_is_valid_helper (iter, first: node->children))
1900	return TRUE;
1901
1902	node = node->next;
1903	}
1904	while (node);
1905
1906	return FALSE;
1907	}
1908
1909	/**
1910	* gtk_tree_store_iter_is_valid:
1911	* @tree_store: a tree store
1912	* @iter: the iterator to check
1913	*
1914	* Checks if the given iter is a valid iter for this `GtkTreeStore`.
1915	*
1916	* This function is slow. Only use it for debugging and/or testing
1917	* purposes.
1918	*
1919	* Returns: %TRUE if the iter is valid, %FALSE if the iter is invalid.
1920	**/
1921	gboolean
1922	gtk_tree_store_iter_is_valid (GtkTreeStore *tree_store,
1923	GtkTreeIter *iter)
1924	{
1925	g_return_val_if_fail (GTK_IS_TREE_STORE (tree_store), FALSE);
1926	g_return_val_if_fail (iter != NULL, FALSE);
1927
1928	if (!VALID_ITER (iter, tree_store))
1929	return FALSE;
1930
1931	return gtk_tree_store_iter_is_valid_helper (iter, first: tree_store->priv->root);
1932	}
1933
1934	/* DND */
1935
1936
1937	static gboolean real_gtk_tree_store_row_draggable (GtkTreeDragSource *drag_source,
1938	GtkTreePath *path)
1939	{
1940	return TRUE;
1941	}
1942
1943	static gboolean
1944	gtk_tree_store_drag_data_delete (GtkTreeDragSource *drag_source,
1945	GtkTreePath *path)
1946	{
1947	GtkTreeIter iter;
1948
1949	if (gtk_tree_store_get_iter (GTK_TREE_MODEL (drag_source),
1950	iter: &iter,
1951	path))
1952	{
1953	gtk_tree_store_remove (GTK_TREE_STORE (drag_source),
1954	iter: &iter);
1955	return TRUE;
1956	}
1957	else
1958	{
1959	return FALSE;
1960	}
1961	}
1962
1963	static GdkContentProvider *
1964	gtk_tree_store_drag_data_get (GtkTreeDragSource *drag_source,
1965	GtkTreePath *path)
1966	{
1967	/* Note that we don't need to handle the GTK_TREE_MODEL_ROW
1968	* target, because the default handler does it for us, but
1969	* we do anyway for the convenience of someone maybe overriding the
1970	* default handler.
1971	*/
1972	return gtk_tree_create_row_drag_content (GTK_TREE_MODEL (drag_source), path);
1973	}
1974
1975	static void
1976	copy_node_data (GtkTreeStore *tree_store,
1977	GtkTreeIter *src_iter,
1978	GtkTreeIter *dest_iter)
1979	{
1980	GtkTreeDataList *dl = G_NODE (src_iter->user_data)->data;
1981	GtkTreeDataList *copy_head = NULL;
1982	GtkTreeDataList *copy_prev = NULL;
1983	GtkTreeDataList *copy_iter = NULL;
1984	GtkTreePath *path;
1985	int col;
1986
1987	col = 0;
1988	while (dl)
1989	{
1990	copy_iter = _gtk_tree_data_list_node_copy (list: dl, type: tree_store->priv->column_headers[col]);
1991
1992	if (copy_head == NULL)
1993	copy_head = copy_iter;
1994
1995	if (copy_prev)
1996	copy_prev->next = copy_iter;
1997
1998	copy_prev = copy_iter;
1999
2000	dl = dl->next;
2001	++col;
2002	}
2003
2004	G_NODE (dest_iter->user_data)->data = copy_head;
2005
2006	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter: dest_iter);
2007	gtk_tree_model_row_changed (GTK_TREE_MODEL (tree_store), path, iter: dest_iter);
2008	gtk_tree_path_free (path);
2009	}
2010
2011	static void
2012	recursive_node_copy (GtkTreeStore *tree_store,
2013	GtkTreeIter *src_iter,
2014	GtkTreeIter *dest_iter)
2015	{
2016	GtkTreeIter child;
2017	GtkTreeModel *model;
2018
2019	model = GTK_TREE_MODEL (tree_store);
2020
2021	copy_node_data (tree_store, src_iter, dest_iter);
2022
2023	if (gtk_tree_store_iter_children (tree_model: model,
2024	iter: &child,
2025	parent: src_iter))
2026	{
2027	/* Need to create children and recurse. Note our
2028	* dependence on persistent iterators here.
2029	*/
2030	do
2031	{
2032	GtkTreeIter copy;
2033
2034	/* Gee, a really slow algorithm... ;-) FIXME */
2035	gtk_tree_store_append (tree_store,
2036	iter: &copy,
2037	parent: dest_iter);
2038
2039	recursive_node_copy (tree_store, src_iter: &child, dest_iter: &copy);
2040	}
2041	while (gtk_tree_store_iter_next (tree_model: model, iter: &child));
2042	}
2043	}
2044
2045	static gboolean
2046	gtk_tree_store_drag_data_received (GtkTreeDragDest *drag_dest,
2047	GtkTreePath *dest,
2048	const GValue *value)
2049	{
2050	GtkTreeModel *tree_model;
2051	GtkTreeStore *tree_store;
2052	GtkTreeModel *src_model = NULL;
2053	GtkTreePath *src_path = NULL;
2054	gboolean retval = FALSE;
2055
2056	tree_model = GTK_TREE_MODEL (drag_dest);
2057	tree_store = GTK_TREE_STORE (drag_dest);
2058
2059	validate_tree (tree_store);
2060
2061	if (gtk_tree_get_row_drag_data (value,
2062	tree_model: &src_model,
2063	path: &src_path) &&
2064	src_model == tree_model)
2065	{
2066	/* Copy the given row to a new position */
2067	GtkTreeIter src_iter;
2068	GtkTreeIter dest_iter;
2069	GtkTreePath *prev;
2070
2071	if (!gtk_tree_store_get_iter (tree_model: src_model,
2072	iter: &src_iter,
2073	path: src_path))
2074	{
2075	goto out;
2076	}
2077
2078	/* Get the path to insert _after_ (dest is the path to insert _before_) */
2079	prev = gtk_tree_path_copy (path: dest);
2080
2081	if (!gtk_tree_path_prev (path: prev))
2082	{
2083	GtkTreeIter dest_parent;
2084	GtkTreePath *parent;
2085	GtkTreeIter *dest_parent_p;
2086
2087	/* dest was the first spot at the current depth; which means
2088	* we are supposed to prepend.
2089	*/
2090
2091	/* Get the parent, NULL if parent is the root */
2092	dest_parent_p = NULL;
2093	parent = gtk_tree_path_copy (path: dest);
2094	if (gtk_tree_path_up (path: parent) &&
2095	gtk_tree_path_get_depth (path: parent) > 0)
2096	{
2097	gtk_tree_store_get_iter (tree_model,
2098	iter: &dest_parent,
2099	path: parent);
2100	dest_parent_p = &dest_parent;
2101	}
2102	gtk_tree_path_free (path: parent);
2103	parent = NULL;
2104
2105	gtk_tree_store_prepend (tree_store,
2106	iter: &dest_iter,
2107	parent: dest_parent_p);
2108
2109	retval = TRUE;
2110	}
2111	else
2112	{
2113	if (gtk_tree_store_get_iter (tree_model, iter: &dest_iter, path: prev))
2114	{
2115	GtkTreeIter tmp_iter = dest_iter;
2116
2117	gtk_tree_store_insert_after (tree_store, iter: &dest_iter, NULL,
2118	sibling: &tmp_iter);
2119
2120	retval = TRUE;
2121	}
2122	}
2123
2124	gtk_tree_path_free (path: prev);
2125
2126	/* If we succeeded in creating dest_iter, walk src_iter tree branch,
2127	* duplicating it below dest_iter.
2128	*/
2129
2130	if (retval)
2131	{
2132	recursive_node_copy (tree_store,
2133	src_iter: &src_iter,
2134	dest_iter: &dest_iter);
2135	}
2136	}
2137	else
2138	{
2139	/* FIXME maybe add some data targets eventually, or handle text
2140	* targets in the simple case.
2141	*/
2142
2143	}
2144
2145	out:
2146
2147	if (src_path)
2148	gtk_tree_path_free (path: src_path);
2149
2150	return retval;
2151	}
2152
2153	static gboolean
2154	gtk_tree_store_row_drop_possible (GtkTreeDragDest *drag_dest,
2155	GtkTreePath *dest_path,
2156	const GValue *value)
2157	{
2158	GtkTreeModel *src_model = NULL;
2159	GtkTreePath *src_path = NULL;
2160	GtkTreePath *tmp = NULL;
2161	gboolean retval = FALSE;
2162
2163	/* don't accept drops if the tree has been sorted */
2164	if (GTK_TREE_STORE_IS_SORTED (drag_dest))
2165	return FALSE;
2166
2167	if (!gtk_tree_get_row_drag_data (value,
2168	tree_model: &src_model,
2169	path: &src_path))
2170	goto out;
2171
2172	/* can only drag to ourselves */
2173	if (src_model != GTK_TREE_MODEL (drag_dest))
2174	goto out;
2175
2176	/* Can't drop into ourself. */
2177	if (gtk_tree_path_is_ancestor (path: src_path,
2178	descendant: dest_path))
2179	goto out;
2180
2181	/* Can't drop if dest_path's parent doesn't exist */
2182	{
2183	GtkTreeIter iter;
2184
2185	if (gtk_tree_path_get_depth (path: dest_path) > 1)
2186	{
2187	tmp = gtk_tree_path_copy (path: dest_path);
2188	gtk_tree_path_up (path: tmp);
2189
2190	if (!gtk_tree_store_get_iter (GTK_TREE_MODEL (drag_dest),
2191	iter: &iter, path: tmp))
2192	goto out;
2193	}
2194	}
2195
2196	/* Can otherwise drop anywhere. */
2197	retval = TRUE;
2198
2199	out:
2200
2201	if (src_path)
2202	gtk_tree_path_free (path: src_path);
2203	if (tmp)
2204	gtk_tree_path_free (path: tmp);
2205
2206	return retval;
2207	}
2208
2209	/* Sorting and reordering */
2210	typedef struct _SortTuple
2211	{
2212	int offset;
2213	GNode *node;
2214	} SortTuple;
2215
2216	/* Reordering */
2217	static int
2218	gtk_tree_store_reorder_func (gconstpointer a,
2219	gconstpointer b,
2220	gpointer user_data)
2221	{
2222	SortTuple *a_reorder;
2223	SortTuple *b_reorder;
2224
2225	a_reorder = (SortTuple *)a;
2226	b_reorder = (SortTuple *)b;
2227
2228	if (a_reorder->offset < b_reorder->offset)
2229	return -1;
2230	if (a_reorder->offset > b_reorder->offset)
2231	return 1;
2232
2233	return 0;
2234	}
2235
2236	/**
2237	* gtk_tree_store_reorder: (skip)
2238	* @tree_store: A `GtkTreeStore`
2239	* @parent: (nullable): A `GtkTreeIter`
2240	* @new_order: (array): an array of integers mapping the new position of each child
2241	* to its old position before the re-ordering,
2242	* i.e. @new_order`[newpos] = oldpos`.
2243	*
2244	* Reorders the children of @parent in @tree_store to follow the order
2245	* indicated by @new_order. Note that this function only works with
2246	* unsorted stores.
2247	*/
2248	void
2249	gtk_tree_store_reorder (GtkTreeStore *tree_store,
2250	GtkTreeIter *parent,
2251	int *new_order)
2252	{
2253	int i, length = 0;
2254	GNode *level, *node;
2255	GtkTreePath *path;
2256	SortTuple *sort_array;
2257
2258	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
2259	g_return_if_fail (!GTK_TREE_STORE_IS_SORTED (tree_store));
2260	g_return_if_fail (parent == NULL || VALID_ITER (parent, tree_store));
2261	g_return_if_fail (new_order != NULL);
2262
2263	if (!parent)
2264	level = G_NODE (tree_store->priv->root)->children;
2265	else
2266	level = G_NODE (parent->user_data)->children;
2267
2268	if (G_UNLIKELY (!level))
2269	{
2270	g_warning ("%s: Cannot reorder, parent has no children", G_STRLOC);
2271	return;
2272	}
2273
2274	/* count nodes */
2275	node = level;
2276	while (node)
2277	{
2278	length++;
2279	node = node->next;
2280	}
2281
2282	/* set up sortarray */
2283	sort_array = g_new (SortTuple, length);
2284
2285	node = level;
2286	for (i = 0; i < length; i++)
2287	{
2288	sort_array[new_order[i]].offset = i;
2289	sort_array[i].node = node;
2290
2291	node = node->next;
2292	}
2293
2294	g_qsort_with_data (pbase: sort_array,
2295	total_elems: length,
2296	size: sizeof (SortTuple),
2297	compare_func: gtk_tree_store_reorder_func,
2298	NULL);
2299
2300	/* fix up level */
2301	for (i = 0; i < length - 1; i++)
2302	{
2303	sort_array[i].node->next = sort_array[i+1].node;
2304	sort_array[i+1].node->prev = sort_array[i].node;
2305	}
2306
2307	sort_array[length-1].node->next = NULL;
2308	sort_array[0].node->prev = NULL;
2309	if (parent)
2310	G_NODE (parent->user_data)->children = sort_array[0].node;
2311	else
2312	G_NODE (tree_store->priv->root)->children = sort_array[0].node;
2313
2314	/* emit signal */
2315	if (parent)
2316	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter: parent);
2317	else
2318	path = gtk_tree_path_new ();
2319	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store), path,
2320	iter: parent, new_order);
2321	gtk_tree_path_free (path);
2322	g_free (mem: sort_array);
2323	}
2324
2325	/**
2326	* gtk_tree_store_swap:
2327	* @tree_store: A `GtkTreeStore`.
2328	* @a: A `GtkTreeIter`.
2329	* @b: Another `GtkTreeIter`.
2330	*
2331	* Swaps @a and @b in the same level of @tree_store. Note that this function
2332	* only works with unsorted stores.
2333	**/
2334	void
2335	gtk_tree_store_swap (GtkTreeStore *tree_store,
2336	GtkTreeIter *a,
2337	GtkTreeIter *b)
2338	{
2339	GNode *tmp, *node_a, *node_b, *parent_node;
2340	GNode *a_prev, *a_next, *b_prev, *b_next;
2341	int i, a_count, b_count, length, *order;
2342	GtkTreePath *path_a, *path_b;
2343	GtkTreeIter parent;
2344
2345	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
2346	g_return_if_fail (VALID_ITER (a, tree_store));
2347	g_return_if_fail (VALID_ITER (b, tree_store));
2348
2349	node_a = G_NODE (a->user_data);
2350	node_b = G_NODE (b->user_data);
2351
2352	/* basic sanity checking */
2353	if (node_a == node_b)
2354	return;
2355
2356	path_a = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter: a);
2357	path_b = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter: b);
2358
2359	g_return_if_fail (path_a && path_b);
2360
2361	gtk_tree_path_up (path: path_a);
2362	gtk_tree_path_up (path: path_b);
2363
2364	if (gtk_tree_path_get_depth (path: path_a) == 0
2365	|| gtk_tree_path_get_depth (path: path_b) == 0)
2366	{
2367	if (gtk_tree_path_get_depth (path: path_a) != gtk_tree_path_get_depth (path: path_b))
2368	{
2369	gtk_tree_path_free (path: path_a);
2370	gtk_tree_path_free (path: path_b);
2371
2372	g_warning ("Given children are not in the same level\n");
2373	return;
2374	}
2375	parent_node = G_NODE (tree_store->priv->root);
2376	}
2377	else
2378	{
2379	if (gtk_tree_path_compare (a: path_a, b: path_b))
2380	{
2381	gtk_tree_path_free (path: path_a);
2382	gtk_tree_path_free (path: path_b);
2383
2384	g_warning ("Given children don't have a common parent\n");
2385	return;
2386	}
2387	gtk_tree_store_get_iter (GTK_TREE_MODEL (tree_store), iter: &parent,
2388	path: path_a);
2389	parent_node = G_NODE (parent.user_data);
2390	}
2391	gtk_tree_path_free (path: path_b);
2392
2393	/* old links which we have to keep around */
2394	a_prev = node_a->prev;
2395	a_next = node_a->next;
2396
2397	b_prev = node_b->prev;
2398	b_next = node_b->next;
2399
2400	/* fix up links if the nodes are next to each other */
2401	if (a_prev == node_b)
2402	a_prev = node_a;
2403	if (a_next == node_b)
2404	a_next = node_a;
2405
2406	if (b_prev == node_a)
2407	b_prev = node_b;
2408	if (b_next == node_a)
2409	b_next = node_b;
2410
2411	/* counting nodes */
2412	tmp = parent_node->children;
2413	i = a_count = b_count = 0;
2414	while (tmp)
2415	{
2416	if (tmp == node_a)
2417	a_count = i;
2418	if (tmp == node_b)
2419	b_count = i;
2420
2421	tmp = tmp->next;
2422	i++;
2423	}
2424	length = i;
2425
2426	/* hacking the tree */
2427	if (!a_prev)
2428	parent_node->children = node_b;
2429	else
2430	a_prev->next = node_b;
2431
2432	if (a_next)
2433	a_next->prev = node_b;
2434
2435	if (!b_prev)
2436	parent_node->children = node_a;
2437	else
2438	b_prev->next = node_a;
2439
2440	if (b_next)
2441	b_next->prev = node_a;
2442
2443	node_a->prev = b_prev;
2444	node_a->next = b_next;
2445
2446	node_b->prev = a_prev;
2447	node_b->next = a_next;
2448
2449	/* emit signal */
2450	order = g_new (int, length);
2451	for (i = 0; i < length; i++)
2452	if (i == a_count)
2453	order[i] = b_count;
2454	else if (i == b_count)
2455	order[i] = a_count;
2456	else
2457	order[i] = i;
2458
2459	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store), path: path_a,
2460	iter: parent_node == tree_store->priv->root
2461	? NULL : &parent, new_order: order);
2462	gtk_tree_path_free (path: path_a);
2463	g_free (mem: order);
2464	}
2465
2466	/* WARNING: this function is *incredibly* fragile. Please smashtest after
2467	* making changes here.
2468	* -Kris
2469	*/
2470	static void
2471	gtk_tree_store_move (GtkTreeStore *tree_store,
2472	GtkTreeIter *iter,
2473	GtkTreeIter *position,
2474	gboolean before)
2475	{
2476	GNode *parent, *node, *a, *b, *tmp, *tmp_a, *tmp_b;
2477	int old_pos, new_pos, length, i, *order;
2478	GtkTreePath *path = NULL, *tmppath, *pos_path = NULL;
2479	GtkTreeIter parent_iter = { 0, };
2480	GtkTreeIter dst_a = { 0, };
2481	GtkTreeIter dst_b = { 0, };
2482	int depth = 0;
2483	gboolean handle_b = TRUE;
2484
2485	g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
2486	g_return_if_fail (!GTK_TREE_STORE_IS_SORTED (tree_store));
2487	g_return_if_fail (VALID_ITER (iter, tree_store));
2488	if (position)
2489	g_return_if_fail (VALID_ITER (position, tree_store));
2490
2491	a = b = NULL;
2492
2493	/* sanity checks */
2494	if (position)
2495	{
2496	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
2497	pos_path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store),
2498	iter: position);
2499
2500	/* if before:
2501	* moving the iter before path or "path + 1" doesn't make sense
2502	* else
2503	* moving the iter before path or "path - 1" doesn't make sense
2504	*/
2505	if (!gtk_tree_path_compare (a: path, b: pos_path))
2506	goto free_paths_and_out;
2507
2508	if (before)
2509	gtk_tree_path_next (path);
2510	else
2511	gtk_tree_path_prev (path);
2512
2513	if (!gtk_tree_path_compare (a: path, b: pos_path))
2514	goto free_paths_and_out;
2515
2516	if (before)
2517	gtk_tree_path_prev (path);
2518	else
2519	gtk_tree_path_next (path);
2520
2521	if (gtk_tree_path_get_depth (path) != gtk_tree_path_get_depth (path: pos_path))
2522	{
2523	g_warning ("Given children are not in the same level\n");
2524
2525	goto free_paths_and_out;
2526	}
2527
2528	tmppath = gtk_tree_path_copy (path: pos_path);
2529	gtk_tree_path_up (path);
2530	gtk_tree_path_up (path: tmppath);
2531
2532	if (gtk_tree_path_get_depth (path) > 0 &&
2533	gtk_tree_path_compare (a: path, b: tmppath))
2534	{
2535	g_warning ("Given children are not in the same level\n");
2536
2537	gtk_tree_path_free (path: tmppath);
2538	goto free_paths_and_out;
2539	}
2540
2541	gtk_tree_path_free (path: tmppath);
2542	}
2543
2544	if (!path)
2545	{
2546	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
2547	gtk_tree_path_up (path);
2548	}
2549
2550	depth = gtk_tree_path_get_depth (path);
2551
2552	if (depth)
2553	{
2554	gtk_tree_store_get_iter (GTK_TREE_MODEL (tree_store),
2555	iter: &parent_iter, path);
2556
2557	parent = G_NODE (parent_iter.user_data);
2558	}
2559	else
2560	parent = G_NODE (tree_store->priv->root);
2561
2562	/* yes, I know that this can be done shorter, but I'm doing it this way
2563	* so the code is also maintainable
2564	*/
2565
2566	if (before && position)
2567	{
2568	b = G_NODE (position->user_data);
2569
2570	if (gtk_tree_path_get_indices (path: pos_path)[gtk_tree_path_get_depth (path: pos_path) - 1] > 0)
2571	{
2572	gtk_tree_path_prev (path: pos_path);
2573	if (gtk_tree_store_get_iter (GTK_TREE_MODEL (tree_store),
2574	iter: &dst_a, path: pos_path))
2575	a = G_NODE (dst_a.user_data);
2576	else
2577	a = NULL;
2578	gtk_tree_path_next (path: pos_path);
2579	}
2580
2581	/* if b is NULL, a is NULL too -- we are at the beginning of the list
2582	* yes and we leak memory here ...
2583	*/
2584	g_return_if_fail (b);
2585	}
2586	else if (before && !position)
2587	{
2588	/* move before without position is appending */
2589	a = NULL;
2590	b = NULL;
2591	}
2592	else /* !before */
2593	{
2594	if (position)
2595	a = G_NODE (position->user_data);
2596	else
2597	a = NULL;
2598
2599	if (position)
2600	{
2601	gtk_tree_path_next (path: pos_path);
2602	if (gtk_tree_store_get_iter (GTK_TREE_MODEL (tree_store), iter: &dst_b, path: pos_path))
2603	b = G_NODE (dst_b.user_data);
2604	else
2605	b = NULL;
2606	gtk_tree_path_prev (path: pos_path);
2607	}
2608	else
2609	{
2610	/* move after without position is prepending */
2611	if (depth)
2612	gtk_tree_store_iter_children (GTK_TREE_MODEL (tree_store), iter: &dst_b,
2613	parent: &parent_iter);
2614	else
2615	gtk_tree_store_iter_children (GTK_TREE_MODEL (tree_store), iter: &dst_b,
2616	NULL);
2617
2618	b = G_NODE (dst_b.user_data);
2619	}
2620
2621	/* if a is NULL, b is NULL too -- we are at the end of the list
2622	* yes and we leak memory here ...
2623	*/
2624	if (position)
2625	g_return_if_fail (a);
2626	}
2627
2628	/* counting nodes */
2629	tmp = parent->children;
2630
2631	length = old_pos = 0;
2632	while (tmp)
2633	{
2634	if (tmp == iter->user_data)
2635	old_pos = length;
2636
2637	tmp = tmp->next;
2638	length++;
2639	}
2640
2641	/* remove node from list */
2642	node = G_NODE (iter->user_data);
2643	tmp_a = node->prev;
2644	tmp_b = node->next;
2645
2646	if (tmp_a)
2647	tmp_a->next = tmp_b;
2648	else
2649	parent->children = tmp_b;
2650
2651	if (tmp_b)
2652	tmp_b->prev = tmp_a;
2653
2654	/* and reinsert the node */
2655	if (a)
2656	{
2657	tmp = a->next;
2658
2659	a->next = node;
2660	node->next = tmp;
2661	node->prev = a;
2662	}
2663	else if (!a && !before)
2664	{
2665	tmp = parent->children;
2666
2667	node->prev = NULL;
2668	parent->children = node;
2669
2670	node->next = tmp;
2671	if (tmp)
2672	tmp->prev = node;
2673
2674	handle_b = FALSE;
2675	}
2676	else if (!a && before)
2677	{
2678	if (!position)
2679	{
2680	node->parent = NULL;
2681	node->next = node->prev = NULL;
2682
2683	/* before with sibling = NULL appends */
2684	g_node_insert_before (parent, NULL, node);
2685	}
2686	else
2687	{
2688	node->parent = NULL;
2689	node->next = node->prev = NULL;
2690
2691	/* after with sibling = NULL prepends */
2692	g_node_insert_after (parent, NULL, node);
2693	}
2694
2695	handle_b = FALSE;
2696	}
2697
2698	if (handle_b)
2699	{
2700	if (b)
2701	{
2702	tmp = b->prev;
2703
2704	b->prev = node;
2705	node->prev = tmp;
2706	node->next = b;
2707	}
2708	else if (!(!a && before)) /* !a && before is completely handled above */
2709	node->next = NULL;
2710	}
2711
2712	/* emit signal */
2713	if (position)
2714	new_pos = gtk_tree_path_get_indices (path: pos_path)[gtk_tree_path_get_depth (path: pos_path)-1];
2715	else if (before)
2716	{
2717	if (depth)
2718	new_pos = gtk_tree_store_iter_n_children (GTK_TREE_MODEL (tree_store),
2719	iter: &parent_iter) - 1;
2720	else
2721	new_pos = gtk_tree_store_iter_n_children (GTK_TREE_MODEL (tree_store),
2722	NULL) - 1;
2723	}
2724	else
2725	new_pos = 0;
2726
2727	if (new_pos > old_pos)
2728	{
2729	if (before && position)
2730	new_pos--;
2731	}
2732	else
2733	{
2734	if (!before && position)
2735	new_pos++;
2736	}
2737
2738	order = g_new (int, length);
2739	if (new_pos > old_pos)
2740	{
2741	for (i = 0; i < length; i++)
2742	if (i < old_pos)
2743	order[i] = i;
2744	else if (i >= old_pos && i < new_pos)
2745	order[i] = i + 1;
2746	else if (i == new_pos)
2747	order[i] = old_pos;
2748	else
2749	order[i] = i;
2750	}
2751	else
2752	{
2753	for (i = 0; i < length; i++)
2754	if (i == new_pos)
2755	order[i] = old_pos;
2756	else if (i > new_pos && i <= old_pos)
2757	order[i] = i - 1;
2758	else
2759	order[i] = i;
2760	}
2761
2762	if (depth)
2763	{
2764	tmppath = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store),
2765	iter: &parent_iter);
2766	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
2767	path: tmppath, iter: &parent_iter, new_order: order);
2768	}
2769	else
2770	{
2771	tmppath = gtk_tree_path_new ();
2772	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
2773	path: tmppath, NULL, new_order: order);
2774	}
2775
2776	gtk_tree_path_free (path: tmppath);
2777	gtk_tree_path_free (path);
2778	if (position)
2779	gtk_tree_path_free (path: pos_path);
2780	g_free (mem: order);
2781
2782	return;
2783
2784	free_paths_and_out:
2785	gtk_tree_path_free (path);
2786	gtk_tree_path_free (path: pos_path);
2787	}
2788
2789	/**
2790	* gtk_tree_store_move_before:
2791	* @tree_store: A `GtkTreeStore`
2792	* @iter: A `GtkTreeIter`
2793	* @position: (nullable): A `GtkTreeIter`
2794	*
2795	* Moves @iter in @tree_store to the position before @position. @iter and
2796	* @position should be in the same level. Note that this function only
2797	* works with unsorted stores. If @position is %NULL, @iter will be
2798	* moved to the end of the level.
2799	**/
2800	void
2801	gtk_tree_store_move_before (GtkTreeStore *tree_store,
2802	GtkTreeIter *iter,
2803	GtkTreeIter *position)
2804	{
2805	gtk_tree_store_move (tree_store, iter, position, TRUE);
2806	}
2807
2808	/**
2809	* gtk_tree_store_move_after:
2810	* @tree_store: A `GtkTreeStore`
2811	* @iter: A `GtkTreeIter`.
2812	* @position: (nullable): A `GtkTreeIter`.
2813	*
2814	* Moves @iter in @tree_store to the position after @position. @iter and
2815	* @position should be in the same level. Note that this function only
2816	* works with unsorted stores. If @position is %NULL, @iter will be moved
2817	* to the start of the level.
2818	**/
2819	void
2820	gtk_tree_store_move_after (GtkTreeStore *tree_store,
2821	GtkTreeIter *iter,
2822	GtkTreeIter *position)
2823	{
2824	gtk_tree_store_move (tree_store, iter, position, FALSE);
2825	}
2826
2827	/* Sorting */
2828	static int
2829	gtk_tree_store_compare_func (gconstpointer a,
2830	gconstpointer b,
2831	gpointer user_data)
2832	{
2833	GtkTreeStore *tree_store = user_data;
2834	GtkTreeStorePrivate *priv = tree_store->priv;
2835	GNode *node_a;
2836	GNode *node_b;
2837	GtkTreeIterCompareFunc func;
2838	gpointer data;
2839
2840	GtkTreeIter iter_a;
2841	GtkTreeIter iter_b;
2842	int retval;
2843
2844	if (priv->sort_column_id != -1)
2845	{
2846	GtkTreeDataSortHeader *header;
2847
2848	header = _gtk_tree_data_list_get_header (header_list: priv->sort_list,
2849	sort_column_id: priv->sort_column_id);
2850	g_return_val_if_fail (header != NULL, 0);
2851	g_return_val_if_fail (header->func != NULL, 0);
2852
2853	func = header->func;
2854	data = header->data;
2855	}
2856	else
2857	{
2858	g_return_val_if_fail (priv->default_sort_func != NULL, 0);
2859	func = priv->default_sort_func;
2860	data = priv->default_sort_data;
2861	}
2862
2863	node_a = ((SortTuple *) a)->node;
2864	node_b = ((SortTuple *) b)->node;
2865
2866	iter_a.stamp = priv->stamp;
2867	iter_a.user_data = node_a;
2868	iter_b.stamp = priv->stamp;
2869	iter_b.user_data = node_b;
2870
2871	retval = (* func) (GTK_TREE_MODEL (user_data), &iter_a, &iter_b, data);
2872
2873	if (priv->order == GTK_SORT_DESCENDING)
2874	{
2875	if (retval > 0)
2876	retval = -1;
2877	else if (retval < 0)
2878	retval = 1;
2879	}
2880	return retval;
2881	}
2882
2883	static void
2884	gtk_tree_store_sort_helper (GtkTreeStore *tree_store,
2885	GNode *parent,
2886	gboolean recurse)
2887	{
2888	GtkTreeIter iter;
2889	GArray *sort_array;
2890	GNode *node;
2891	GNode *tmp_node;
2892	int list_length;
2893	int i;
2894	int *new_order;
2895	GtkTreePath *path;
2896
2897	node = parent->children;
2898	if (node == NULL || node->next == NULL)
2899	{
2900	if (recurse && node && node->children)
2901	gtk_tree_store_sort_helper (tree_store, parent: node, TRUE);
2902
2903	return;
2904	}
2905
2906	list_length = 0;
2907	for (tmp_node = node; tmp_node; tmp_node = tmp_node->next)
2908	list_length++;
2909
2910	sort_array = g_array_sized_new (FALSE, FALSE, element_size: sizeof (SortTuple), reserved_size: list_length);
2911
2912	i = 0;
2913	for (tmp_node = node; tmp_node; tmp_node = tmp_node->next)
2914	{
2915	SortTuple tuple;
2916
2917	tuple.offset = i;
2918	tuple.node = tmp_node;
2919	g_array_append_val (sort_array, tuple);
2920	i++;
2921	}
2922
2923	/* Sort the array */
2924	g_array_sort_with_data (array: sort_array, compare_func: gtk_tree_store_compare_func, user_data: tree_store);
2925
2926	for (i = 0; i < list_length - 1; i++)
2927	{
2928	g_array_index (sort_array, SortTuple, i).node->next =
2929	g_array_index (sort_array, SortTuple, i + 1).node;
2930	g_array_index (sort_array, SortTuple, i + 1).node->prev =
2931	g_array_index (sort_array, SortTuple, i).node;
2932	}
2933	g_array_index (sort_array, SortTuple, list_length - 1).node->next = NULL;
2934	g_array_index (sort_array, SortTuple, 0).node->prev = NULL;
2935	parent->children = g_array_index (sort_array, SortTuple, 0).node;
2936
2937	/* Let the world know about our new order */
2938	new_order = g_new (int, list_length);
2939	for (i = 0; i < list_length; i++)
2940	new_order[i] = g_array_index (sort_array, SortTuple, i).offset;
2941
2942	iter.stamp = tree_store->priv->stamp;
2943	iter.user_data = parent;
2944	path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter: &iter);
2945	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
2946	path, iter: &iter, new_order);
2947	gtk_tree_path_free (path);
2948	g_free (mem: new_order);
2949	g_array_free (array: sort_array, TRUE);
2950
2951	if (recurse)
2952	{
2953	for (tmp_node = parent->children; tmp_node; tmp_node = tmp_node->next)
2954	{
2955	if (tmp_node->children)
2956	gtk_tree_store_sort_helper (tree_store, parent: tmp_node, TRUE);
2957	}
2958	}
2959	}
2960
2961	static void
2962	gtk_tree_store_sort (GtkTreeStore *tree_store)
2963	{
2964	GtkTreeStorePrivate *priv = tree_store->priv;
2965
2966	if (!GTK_TREE_STORE_IS_SORTED (tree_store))
2967	return;
2968
2969	if (priv->sort_column_id != -1)
2970	{
2971	GtkTreeDataSortHeader *header = NULL;
2972
2973	header = _gtk_tree_data_list_get_header (header_list: priv->sort_list,
2974	sort_column_id: priv->sort_column_id);
2975
2976	/* We want to make sure that we have a function */
2977	g_return_if_fail (header != NULL);
2978	g_return_if_fail (header->func != NULL);
2979	}
2980	else
2981	{
2982	g_return_if_fail (priv->default_sort_func != NULL);
2983	}
2984
2985	gtk_tree_store_sort_helper (tree_store, G_NODE (priv->root), TRUE);
2986	}
2987
2988	static void
2989	gtk_tree_store_sort_iter_changed (GtkTreeStore *tree_store,
2990	GtkTreeIter *iter,
2991	int column,
2992	gboolean emit_signal)
2993	{
2994	GtkTreeStorePrivate *priv = tree_store->priv;
2995	GNode *prev = NULL;
2996	GNode *next = NULL;
2997	GNode *node;
2998	GtkTreePath *tmp_path;
2999	GtkTreeIter tmp_iter;
3000	int cmp_a = 0;
3001	int cmp_b = 0;
3002	int i;
3003	int old_location;
3004	int new_location;
3005	int *new_order;
3006	int length;
3007	GtkTreeIterCompareFunc func;
3008	gpointer data;
3009
3010	g_return_if_fail (G_NODE (iter->user_data)->parent != NULL);
3011
3012	tmp_iter.stamp = priv->stamp;
3013	if (priv->sort_column_id != -1)
3014	{
3015	GtkTreeDataSortHeader *header;
3016	header = _gtk_tree_data_list_get_header (header_list: priv->sort_list,
3017	sort_column_id: priv->sort_column_id);
3018	g_return_if_fail (header != NULL);
3019	g_return_if_fail (header->func != NULL);
3020	func = header->func;
3021	data = header->data;
3022	}
3023	else
3024	{
3025	g_return_if_fail (priv->default_sort_func != NULL);
3026	func = priv->default_sort_func;
3027	data = priv->default_sort_data;
3028	}
3029
3030	/* If it's the built in function, we don't sort. */
3031	if (func == _gtk_tree_data_list_compare_func &&
3032	priv->sort_column_id != column)
3033	return;
3034
3035	old_location = 0;
3036	node = G_NODE (iter->user_data)->parent->children;
3037	/* First we find the iter, its prev, and its next */
3038	while (node)
3039	{
3040	if (node == G_NODE (iter->user_data))
3041	break;
3042	old_location++;
3043	node = node->next;
3044	}
3045	g_assert (node != NULL);
3046
3047	prev = node->prev;
3048	next = node->next;
3049
3050	/* Check the common case, where we don't need to sort it moved. */
3051	if (prev != NULL)
3052	{
3053	tmp_iter.user_data = prev;
3054	cmp_a = (* func) (GTK_TREE_MODEL (tree_store), &tmp_iter, iter, data);
3055	}
3056
3057	if (next != NULL)
3058	{
3059	tmp_iter.user_data = next;
3060	cmp_b = (* func) (GTK_TREE_MODEL (tree_store), iter, &tmp_iter, data);
3061	}
3062
3063	if (priv->order == GTK_SORT_DESCENDING)
3064	{
3065	if (cmp_a < 0)
3066	cmp_a = 1;
3067	else if (cmp_a > 0)
3068	cmp_a = -1;
3069
3070	if (cmp_b < 0)
3071	cmp_b = 1;
3072	else if (cmp_b > 0)
3073	cmp_b = -1;
3074	}
3075
3076	if (prev == NULL && cmp_b <= 0)
3077	return;
3078	else if (next == NULL && cmp_a <= 0)
3079	return;
3080	else if (prev != NULL && next != NULL &&
3081	cmp_a <= 0 && cmp_b <= 0)
3082	return;
3083
3084	/* We actually need to sort it */
3085	/* First, remove the old link. */
3086
3087	if (prev)
3088	prev->next = next;
3089	else
3090	node->parent->children = next;
3091
3092	if (next)
3093	next->prev = prev;
3094
3095	node->prev = NULL;
3096	node->next = NULL;
3097
3098	/* FIXME: as an optimization, we can potentially start at next */
3099	prev = NULL;
3100	node = node->parent->children;
3101	new_location = 0;
3102	tmp_iter.user_data = node;
3103	if (priv->order == GTK_SORT_DESCENDING)
3104	cmp_a = (* func) (GTK_TREE_MODEL (tree_store), &tmp_iter, iter, data);
3105	else
3106	cmp_a = (* func) (GTK_TREE_MODEL (tree_store), iter, &tmp_iter, data);
3107
3108	while ((node->next) && (cmp_a > 0))
3109	{
3110	prev = node;
3111	node = node->next;
3112	new_location++;
3113	tmp_iter.user_data = node;
3114	if (priv->order == GTK_SORT_DESCENDING)
3115	cmp_a = (* func) (GTK_TREE_MODEL (tree_store), &tmp_iter, iter, data);
3116	else
3117	cmp_a = (* func) (GTK_TREE_MODEL (tree_store), iter, &tmp_iter, data);
3118	}
3119
3120	if ((!node->next) && (cmp_a > 0))
3121	{
3122	new_location++;
3123	node->next = G_NODE (iter->user_data);
3124	node->next->prev = node;
3125	}
3126	else if (prev)
3127	{
3128	prev->next = G_NODE (iter->user_data);
3129	prev->next->prev = prev;
3130	G_NODE (iter->user_data)->next = node;
3131	G_NODE (iter->user_data)->next->prev = G_NODE (iter->user_data);
3132	}
3133	else
3134	{
3135	G_NODE (iter->user_data)->next = G_NODE (iter->user_data)->parent->children;
3136	G_NODE (iter->user_data)->next->prev = G_NODE (iter->user_data);
3137	G_NODE (iter->user_data)->parent->children = G_NODE (iter->user_data);
3138	}
3139
3140	if (!emit_signal)
3141	return;
3142
3143	/* Emit the reordered signal. */
3144	length = g_node_n_children (node: node->parent);
3145	new_order = g_new (int, length);
3146	if (old_location < new_location)
3147	for (i = 0; i < length; i++)
3148	{
3149	if (i < old_location ||
3150	i > new_location)
3151	new_order[i] = i;
3152	else if (i >= old_location &&
3153	i < new_location)
3154	new_order[i] = i + 1;
3155	else if (i == new_location)
3156	new_order[i] = old_location;
3157	}
3158	else
3159	for (i = 0; i < length; i++)
3160	{
3161	if (i < new_location ||
3162	i > old_location)
3163	new_order[i] = i;
3164	else if (i > new_location &&
3165	i <= old_location)
3166	new_order[i] = i - 1;
3167	else if (i == new_location)
3168	new_order[i] = old_location;
3169	}
3170
3171	tmp_iter.user_data = node->parent;
3172	tmp_path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter: &tmp_iter);
3173
3174	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
3175	path: tmp_path, iter: &tmp_iter,
3176	new_order);
3177
3178	gtk_tree_path_free (path: tmp_path);
3179	g_free (mem: new_order);
3180	}
3181
3182
3183	static gboolean
3184	gtk_tree_store_get_sort_column_id (GtkTreeSortable *sortable,
3185	int *sort_column_id,
3186	GtkSortType *order)
3187	{
3188	GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
3189	GtkTreeStorePrivate *priv = tree_store->priv;
3190
3191	if (sort_column_id)
3192	* sort_column_id = priv->sort_column_id;
3193	if (order)
3194	* order = priv->order;
3195
3196	if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID ||
3197	priv->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
3198	return FALSE;
3199
3200	return TRUE;
3201	}
3202
3203	static void
3204	gtk_tree_store_set_sort_column_id (GtkTreeSortable *sortable,
3205	int sort_column_id,
3206	GtkSortType order)
3207	{
3208	GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
3209	GtkTreeStorePrivate *priv = tree_store->priv;
3210
3211	if ((priv->sort_column_id == sort_column_id) &&
3212	(priv->order == order))
3213	return;
3214
3215	if (sort_column_id != GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
3216	{
3217	if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
3218	{
3219	GtkTreeDataSortHeader *header = NULL;
3220
3221	header = _gtk_tree_data_list_get_header (header_list: priv->sort_list,
3222	sort_column_id);
3223
3224	/* We want to make sure that we have a function */
3225	g_return_if_fail (header != NULL);
3226	g_return_if_fail (header->func != NULL);
3227	}
3228	else
3229	{
3230	g_return_if_fail (priv->default_sort_func != NULL);
3231	}
3232	}
3233
3234	priv->sort_column_id = sort_column_id;
3235	priv->order = order;
3236
3237	gtk_tree_sortable_sort_column_changed (sortable);
3238
3239	gtk_tree_store_sort (tree_store);
3240	}
3241
3242	static void
3243	gtk_tree_store_set_sort_func (GtkTreeSortable *sortable,
3244	int sort_column_id,
3245	GtkTreeIterCompareFunc func,
3246	gpointer data,
3247	GDestroyNotify destroy)
3248	{
3249	GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
3250	GtkTreeStorePrivate *priv = tree_store->priv;
3251
3252	priv->sort_list = _gtk_tree_data_list_set_header (header_list: priv->sort_list,
3253	sort_column_id,
3254	func, data, destroy);
3255
3256	if (priv->sort_column_id == sort_column_id)
3257	gtk_tree_store_sort (tree_store);
3258	}
3259
3260	static void
3261	gtk_tree_store_set_default_sort_func (GtkTreeSortable *sortable,
3262	GtkTreeIterCompareFunc func,
3263	gpointer data,
3264	GDestroyNotify destroy)
3265	{
3266	GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
3267	GtkTreeStorePrivate *priv = tree_store->priv;
3268
3269	if (priv->default_sort_destroy)
3270	{
3271	GDestroyNotify d = priv->default_sort_destroy;
3272
3273	priv->default_sort_destroy = NULL;
3274	d (priv->default_sort_data);
3275	}
3276
3277	priv->default_sort_func = func;
3278	priv->default_sort_data = data;
3279	priv->default_sort_destroy = destroy;
3280
3281	if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
3282	gtk_tree_store_sort (tree_store);
3283	}
3284
3285	static gboolean
3286	gtk_tree_store_has_default_sort_func (GtkTreeSortable *sortable)
3287	{
3288	GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
3289
3290	return (tree_store->priv->default_sort_func != NULL);
3291	}
3292
3293	#ifdef G_ENABLE_DEBUG
3294	static void
3295	validate_gnode (GNode* node)
3296	{
3297	GNode *iter;
3298
3299	iter = node->children;
3300	while (iter != NULL)
3301	{
3302	g_assert (iter->parent == node);
3303	if (iter->prev)
3304	g_assert (iter->prev->next == iter);
3305	validate_gnode (node: iter);
3306	iter = iter->next;
3307	}
3308	}
3309	#endif
3310
3311	/* GtkBuildable custom tag implementation
3312	*
3313	* <columns>
3314	* <column type="..."/>
3315	* <column type="..."/>
3316	* </columns>
3317	*/
3318	typedef struct {
3319	GtkBuilder *builder;
3320	GObject *object;
3321	GSList *items;
3322	} GSListSubParserData;
3323
3324	static void
3325	tree_model_start_element (GtkBuildableParseContext *context,
3326	const char *element_name,
3327	const char **names,
3328	const char **values,
3329	gpointer user_data,
3330	GError **error)
3331	{
3332	GSListSubParserData *data = (GSListSubParserData*)user_data;
3333
3334	if (strcmp (s1: element_name, s2: "columns") == 0)
3335	{
3336	if (!_gtk_builder_check_parent (builder: data->builder, context, parent_name: "object", error))
3337	return;
3338
3339	if (!g_markup_collect_attributes (element_name, attribute_names: names, attribute_values: values, error,
3340	first_type: G_MARKUP_COLLECT_INVALID, NULL, NULL,
3341	G_MARKUP_COLLECT_INVALID))
3342	_gtk_builder_prefix_error (builder: data->builder, context, error);
3343
3344	}
3345	else if (strcmp (s1: element_name, s2: "column") == 0)
3346	{
3347	const char *type;
3348
3349	if (!_gtk_builder_check_parent (builder: data->builder, context, parent_name: "columns", error))
3350	return;
3351
3352	if (!g_markup_collect_attributes (element_name, attribute_names: names, attribute_values: values, error,
3353	first_type: G_MARKUP_COLLECT_STRING, first_attr: "type", &type,
3354	G_MARKUP_COLLECT_INVALID))
3355	{
3356	_gtk_builder_prefix_error (builder: data->builder, context, error);
3357	return;
3358	}
3359
3360	data->items = g_slist_prepend (list: data->items, data: g_strdup (str: type));
3361	}
3362	else
3363	{
3364	_gtk_builder_error_unhandled_tag (builder: data->builder, context,
3365	object: "GtkTreeStore", element_name,
3366	error);
3367	}
3368	}
3369
3370	static void
3371	tree_model_end_element (GtkBuildableParseContext *context,
3372	const char *element_name,
3373	gpointer user_data,
3374	GError **error)
3375	{
3376	GSListSubParserData *data = (GSListSubParserData*)user_data;
3377
3378	g_assert(data->builder);
3379
3380	if (strcmp (s1: element_name, s2: "columns") == 0)
3381	{
3382	GSList *l;
3383	GType *types;
3384	int i;
3385	GType type;
3386
3387	data = (GSListSubParserData*)user_data;
3388	data->items = g_slist_reverse (list: data->items);
3389	types = g_new0 (GType, g_slist_length (data->items));
3390
3391	for (l = data->items, i = 0; l; l = l->next, i++)
3392	{
3393	type = gtk_builder_get_type_from_name (builder: data->builder, type_name: l->data);
3394	if (type == G_TYPE_INVALID)
3395	{
3396	g_warning ("Unknown type %s specified in treemodel %s",
3397	(const char *)l->data,
3398	gtk_buildable_get_buildable_id (GTK_BUILDABLE (data->object)));
3399	continue;
3400	}
3401	types[i] = type;
3402
3403	g_free (mem: l->data);
3404	}
3405
3406	gtk_tree_store_set_column_types (GTK_TREE_STORE (data->object), n_columns: i, types);
3407
3408	g_free (mem: types);
3409	}
3410	}
3411
3412	static const GtkBuildableParser tree_model_parser =
3413	{
3414	tree_model_start_element,
3415	tree_model_end_element
3416	};
3417
3418
3419	static gboolean
3420	gtk_tree_store_buildable_custom_tag_start (GtkBuildable *buildable,
3421	GtkBuilder *builder,
3422	GObject *child,
3423	const char *tagname,
3424	GtkBuildableParser *parser,
3425	gpointer *parser_data)
3426	{
3427	GSListSubParserData *data;
3428
3429	if (child)
3430	return FALSE;
3431
3432	if (strcmp (s1: tagname, s2: "columns") == 0)
3433	{
3434	data = g_slice_new0 (GSListSubParserData);
3435	data->builder = builder;
3436	data->items = NULL;
3437	data->object = G_OBJECT (buildable);
3438
3439	*parser = tree_model_parser;
3440	*parser_data = data;
3441
3442	return TRUE;
3443	}
3444
3445	return FALSE;
3446	}
3447
3448	static void
3449	gtk_tree_store_buildable_custom_finished (GtkBuildable *buildable,
3450	GtkBuilder *builder,
3451	GObject *child,
3452	const char *tagname,
3453	gpointer user_data)
3454	{
3455	GSListSubParserData *data;
3456
3457	if (strcmp (s1: tagname, s2: "columns"))
3458	return;
3459
3460	data = (GSListSubParserData*)user_data;
3461
3462	g_slist_free (list: data->items);
3463	g_slice_free (GSListSubParserData, data);
3464	}
3465