1	/* gtktreemodelsort.c
2	* Copyright (C) 2000,2001 Red Hat, Inc., Jonathan Blandford <jrb@redhat.com>
3	* Copyright (C) 2001,2002 Kristian Rietveld <kris@gtk.org>
4	*
5	* This library is free software; you can redistribute it and/or
6	* modify it under the terms of the GNU Library General Public
7	* License as published by the Free Software Foundation; either
8	* version 2 of the License, or (at your option) any later version.
9	*
10	* This library is distributed in the hope that it will be useful,
11	* but WITHOUT ANY WARRANTY; without even the implied warranty of
12	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13	* Library General Public License for more details.
14	*
15	* You should have received a copy of the GNU Library General Public
16	* License along with this library. If not, see <http://www.gnu.org/licenses/>.
17	*/
18
19	#include "config.h"
20	#include <string.h>
21
22	#include "gtktreemodelsort.h"
23	#include "gtktreesortable.h"
24	#include "gtktreestore.h"
25	#include "gtktreedatalist.h"
26	#include "gtkintl.h"
27	#include "gtkprivate.h"
28	#include "gtktreednd.h"
29
30
31	/**
32	* GtkTreeModelSort:
33	*
34	* A GtkTreeModel which makes an underlying tree model sortable
35	*
36	* The `GtkTreeModelSort` is a model which implements the `GtkTreeSortable`
37	* interface. It does not hold any data itself, but rather is created with
38	* a child model and proxies its data. It has identical column types to
39	* this child model, and the changes in the child are propagated. The
40	* primary purpose of this model is to provide a way to sort a different
41	* model without modifying it. Note that the sort function used by
42	* `GtkTreeModelSort` is not guaranteed to be stable.
43	*
44	* The use of this is best demonstrated through an example. In the
45	* following sample code we create two `GtkTreeView` widgets each with a
46	* view of the same data. As the model is wrapped here by a
47	* `GtkTreeModelSort`, the two `GtkTreeView`s can each sort their
48	* view of the data without affecting the other. By contrast, if we
49	* simply put the same model in each widget, then sorting the first would
50	* sort the second.
51	*
52	* ## Using a `GtkTreeModelSort`
53	*
54	* |[<!-- language="C" -->
55	* {
56	* GtkTreeView *tree_view1;
57	* GtkTreeView *tree_view2;
58	* GtkTreeModel *sort_model1;
59	* GtkTreeModel *sort_model2;
60	* GtkTreeModel *child_model;
61	*
62	* // get the child model
63	* child_model = get_my_model ();
64	*
65	* // Create the first tree
66	* sort_model1 = gtk_tree_model_sort_new_with_model (child_model);
67	* tree_view1 = gtk_tree_view_new_with_model (sort_model1);
68	*
69	* // Create the second tree
70	* sort_model2 = gtk_tree_model_sort_new_with_model (child_model);
71	* tree_view2 = gtk_tree_view_new_with_model (sort_model2);
72	*
73	* // Now we can sort the two models independently
74	* gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (sort_model1),
75	* COLUMN_1, GTK_SORT_ASCENDING);
76	* gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (sort_model2),
77	* COLUMN_1, GTK_SORT_DESCENDING);
78	* }
79	* ]|
80	*
81	* To demonstrate how to access the underlying child model from the sort
82	* model, the next example will be a callback for the `GtkTreeSelection`
83	* `GtkTreeSelection::changed` signal. In this callback, we get a string
84	* from COLUMN_1 of the model. We then modify the string, find the same
85	* selected row on the child model, and change the row there.
86	*
87	* ## Accessing the child model of in a selection changed callback
88	*
89	* |[<!-- language="C" -->
90	* void
91	* selection_changed (GtkTreeSelection *selection, gpointer data)
92	* {
93	* GtkTreeModel *sort_model = NULL;
94	* GtkTreeModel *child_model;
95	* GtkTreeIter sort_iter;
96	* GtkTreeIter child_iter;
97	* char *some_data = NULL;
98	* char *modified_data;
99	*
100	* // Get the current selected row and the model.
101	* if (! gtk_tree_selection_get_selected (selection,
102	* &sort_model,
103	* &sort_iter))
104	* return;
105	*
106	* // Look up the current value on the selected row and get
107	* // a new value to change it to.
108	* gtk_tree_model_get (GTK_TREE_MODEL (sort_model), &sort_iter,
109	* COLUMN_1, &some_data,
110	* -1);
111	*
112	* modified_data = change_the_data (some_data);
113	* g_free (some_data);
114	*
115	* // Get an iterator on the child model, instead of the sort model.
116	* gtk_tree_model_sort_convert_iter_to_child_iter (GTK_TREE_MODEL_SORT (sort_model),
117	* &child_iter,
118	* &sort_iter);
119	*
120	* // Get the child model and change the value of the row. In this
121	* // example, the child model is a GtkListStore. It could be any other
122	* // type of model, though.
123	* child_model = gtk_tree_model_sort_get_model (GTK_TREE_MODEL_SORT (sort_model));
124	* gtk_list_store_set (GTK_LIST_STORE (child_model), &child_iter,
125	* COLUMN_1, &modified_data,
126	* -1);
127	* g_free (modified_data);
128	* }
129	* ]|
130	*/
131
132
133	/* Notes on this implementation of GtkTreeModelSort
134	* ================================================
135	*
136	* Warnings
137	* --------
138	*
139	* In this code there is a potential for confusion as to whether an iter,
140	* path or value refers to the GtkTreeModelSort model, or to the child model
141	* that has been set. As a convention, variables referencing the child model
142	* will have an s_ prefix before them (ie. s_iter, s_value, s_path);
143	* Conversion of iterators and paths between GtkTreeModelSort and the child
144	* model is done through the various gtk_tree_model_sort_convert_* functions.
145	*
146	* Iterator format
147	* ---------------
148	*
149	* The iterator format of iterators handed out by GtkTreeModelSort is as
150	* follows:
151	*
152	* iter->stamp = tree_model_sort->stamp
153	* iter->user_data = SortLevel
154	* iter->user_data2 = SortElt
155	*
156	* Internal data structure
157	* -----------------------
158	*
159	* Using SortLevel and SortElt, GtkTreeModelSort maintains a “cache” of
160	* the mapping from GtkTreeModelSort nodes to nodes in the child model.
161	* This is to avoid sorting a level each time an operation is requested
162	* on GtkTreeModelSort, such as get iter, get path, get value.
163	*
164	* A SortElt corresponds to a single node. A node and its siblings are
165	* stored in a SortLevel. The SortLevel keeps a reference to the parent
166	* SortElt and its SortLevel (if any). The SortElt can have a "children"
167	* pointer set, which points at a child level (a sub level).
168	*
169	* In a SortLevel, nodes are stored in a GSequence. The GSequence
170	* allows for fast additions and removals, and supports sorting
171	* the level of SortElt nodes.
172	*
173	* It is important to recognize the two different mappings that play
174	* a part in this code:
175	* I. The mapping from the client to this model. The order in which
176	* nodes are stored in the GSequence is the order in which the
177	* nodes are exposed to clients of the GtkTreeModelSort.
178	* II. The mapping from this model to its child model. Each SortElt
179	* contains an “offset” field which is the offset of the
180	* corresponding node in the child model.
181	*
182	* Reference counting
183	* ------------------
184	*
185	* GtkTreeModelSort forwards all reference and unreference operations
186	* to the corresponding node in the child model. The reference count
187	* of each node is also maintained internally, in the “ref_count”
188	* fields in SortElt and SortLevel. For each ref and unref operation on
189	* a SortElt, the “ref_count” of the SortLevel is updated accordingly.
190	* In addition, if a SortLevel has a parent, a reference is taken on
191	* this parent. This happens in gtk_tree_model_sort_build_level() and
192	* the reference is released again in gtk_tree_model_sort_free_level().
193	* This ensures that when GtkTreeModelSort takes a reference on a node
194	* (for example during sorting), all parent nodes are referenced
195	* according to reference counting rule 1, see the GtkTreeModel
196	* documentation.
197	*
198	* When a level has a reference count of zero, which means that
199	* none of the nodes in the level is referenced, the level has
200	* a “zero ref count” on all its parents. As soon as the level
201	* reaches a reference count of zero, the zero ref count value is
202	* incremented by one on all parents of this level. Similarly, as
203	* soon as the reference count of a level changes from zero, the
204	* zero ref count value is decremented by one on all parents.
205	*
206	* The zero ref count value is used to clear unused portions of
207	* the cache. If a SortElt has a zero ref count of one, then
208	* its child level is unused and can be removed from the cache.
209	* If the zero ref count value is higher than one, then the
210	* child level contains sublevels which are unused as well.
211	* gtk_tree_model_sort_clear_cache() uses this to not recurse
212	* into levels which have a zero ref count of zero.
213	*/
214
215	typedef struct _SortElt SortElt;
216	typedef struct _SortLevel SortLevel;
217	typedef struct _SortData SortData;
218
219	struct _SortElt
220	{
221	GtkTreeIter iter;
222	SortLevel *children;
223	int offset;
224	int ref_count;
225	int zero_ref_count;
226	int old_index; /* used while sorting */
227	GSequenceIter *siter; /* iter into seq */
228	};
229
230	struct _SortLevel
231	{
232	GSequence *seq;
233	int ref_count;
234	SortElt *parent_elt;
235	SortLevel *parent_level;
236	};
237
238	struct _SortData
239	{
240	GtkTreeModelSort *tree_model_sort;
241	GtkTreeIterCompareFunc sort_func;
242	gpointer sort_data;
243
244	GtkTreePath *parent_path;
245	int *parent_path_indices;
246	int parent_path_depth;
247	};
248
249	/* Properties */
250	enum {
251	PROP_0,
252	/* Construct args */
253	PROP_MODEL
254	};
255
256
257	struct _GtkTreeModelSortPrivate
258	{
259	gpointer root;
260	int stamp;
261	guint child_flags;
262	GtkTreeModel *child_model;
263	int zero_ref_count;
264
265	/* sort information */
266	GList *sort_list;
267	int sort_column_id;
268	GtkSortType order;
269
270	/* default sort */
271	GtkTreeIterCompareFunc default_sort_func;
272	gpointer default_sort_data;
273	GDestroyNotify default_sort_destroy;
274
275	/* signal ids */
276	gulong changed_id;
277	gulong inserted_id;
278	gulong has_child_toggled_id;
279	gulong deleted_id;
280	gulong reordered_id;
281	};
282
283	/* Set this to 0 to disable caching of child iterators. This
284	* allows for more stringent testing. It is recommended to set this
285	* to one when refactoring this code and running the unit tests to
286	* catch more errors.
287	*/
288	#if 1
289	# define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) \
290	(((GtkTreeModelSort *)tree_model_sort)->priv->child_flags&GTK_TREE_MODEL_ITERS_PERSIST)
291	#else
292	# define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) (FALSE)
293	#endif
294
295	#define SORT_ELT(sort_elt) ((SortElt *)sort_elt)
296	#define SORT_LEVEL(sort_level) ((SortLevel *)sort_level)
297	#define GET_ELT(siter) ((SortElt *) (siter ? g_sequence_get (siter) : NULL))
298
299
300	#define GET_CHILD_ITER(tree_model_sort,ch_iter,so_iter) gtk_tree_model_sort_convert_iter_to_child_iter((GtkTreeModelSort*)(tree_model_sort), (ch_iter), (so_iter));
301
302	#define NO_SORT_FUNC ((GtkTreeIterCompareFunc) 0x1)
303
304	#define VALID_ITER(iter, tree_model_sort) ((iter) != NULL && (iter)->user_data != NULL && (iter)->user_data2 != NULL && (tree_model_sort)->priv->stamp == (iter)->stamp)
305
306	/* general (object/interface init, etc) */
307	static void gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface);
308	static void gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface *iface);
309	static void gtk_tree_model_sort_drag_source_init (GtkTreeDragSourceIface*iface);
310	static void gtk_tree_model_sort_finalize (GObject *object);
311	static void gtk_tree_model_sort_set_property (GObject *object,
312	guint prop_id,
313	const GValue *value,
314	GParamSpec *pspec);
315	static void gtk_tree_model_sort_get_property (GObject *object,
316	guint prop_id,
317	GValue *value,
318	GParamSpec *pspec);
319
320	/* our signal handlers */
321	static void gtk_tree_model_sort_row_changed (GtkTreeModel *model,
322	GtkTreePath *start_path,
323	GtkTreeIter *start_iter,
324	gpointer data);
325	static void gtk_tree_model_sort_row_inserted (GtkTreeModel *model,
326	GtkTreePath *path,
327	GtkTreeIter *iter,
328	gpointer data);
329	static void gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *model,
330	GtkTreePath *path,
331	GtkTreeIter *iter,
332	gpointer data);
333	static void gtk_tree_model_sort_row_deleted (GtkTreeModel *model,
334	GtkTreePath *path,
335	gpointer data);
336	static void gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
337	GtkTreePath *s_path,
338	GtkTreeIter *s_iter,
339	int *new_order,
340	gpointer data);
341
342	/* TreeModel interface */
343	static GtkTreeModelFlags gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model);
344	static int gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model);
345	static GType gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
346	int index);
347	static gboolean gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
348	GtkTreeIter *iter,
349	GtkTreePath *path);
350	static GtkTreePath *gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
351	GtkTreeIter *iter);
352	static void gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
353	GtkTreeIter *iter,
354	int column,
355	GValue *value);
356	static gboolean gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
357	GtkTreeIter *iter);
358	static gboolean gtk_tree_model_sort_iter_previous (GtkTreeModel *tree_model,
359	GtkTreeIter *iter);
360	static gboolean gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
361	GtkTreeIter *iter,
362	GtkTreeIter *parent);
363	static gboolean gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
364	GtkTreeIter *iter);
365	static int gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
366	GtkTreeIter *iter);
367	static gboolean gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
368	GtkTreeIter *iter,
369	GtkTreeIter *parent,
370	int n);
371	static gboolean gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
372	GtkTreeIter *iter,
373	GtkTreeIter *child);
374	static void gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
375	GtkTreeIter *iter);
376	static void gtk_tree_model_sort_real_unref_node (GtkTreeModel *tree_model,
377	GtkTreeIter *iter,
378	gboolean propagate_unref);
379	static void gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
380	GtkTreeIter *iter);
381
382	/* TreeDragSource interface */
383	static gboolean gtk_tree_model_sort_row_draggable (GtkTreeDragSource *drag_source,
384	GtkTreePath *path);
385	static GdkContentProvider *
386	gtk_tree_model_sort_drag_data_get (GtkTreeDragSource *drag_source,
387	GtkTreePath *path);
388	static gboolean gtk_tree_model_sort_drag_data_delete (GtkTreeDragSource *drag_source,
389	GtkTreePath *path);
390
391	/* TreeSortable interface */
392	static gboolean gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable *sortable,
393	int *sort_column_id,
394	GtkSortType *order);
395	static void gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable *sortable,
396	int sort_column_id,
397	GtkSortType order);
398	static void gtk_tree_model_sort_set_sort_func (GtkTreeSortable *sortable,
399	int sort_column_id,
400	GtkTreeIterCompareFunc func,
401	gpointer data,
402	GDestroyNotify destroy);
403	static void gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable *sortable,
404	GtkTreeIterCompareFunc func,
405	gpointer data,
406	GDestroyNotify destroy);
407	static gboolean gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable *sortable);
408
409	/* Private functions (sort funcs, level handling and other utils) */
410	static void gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
411	SortLevel *parent_level,
412	SortElt *parent_elt);
413	static void gtk_tree_model_sort_free_level (GtkTreeModelSort *tree_model_sort,
414	SortLevel *sort_level,
415	gboolean unref);
416	static void gtk_tree_model_sort_increment_stamp (GtkTreeModelSort *tree_model_sort);
417	static void gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
418	SortLevel *level,
419	gboolean recurse,
420	gboolean emit_reordered);
421	static void gtk_tree_model_sort_sort (GtkTreeModelSort *tree_model_sort);
422	static gboolean gtk_tree_model_sort_insert_value (GtkTreeModelSort *tree_model_sort,
423	SortLevel *level,
424	GtkTreePath *s_path,
425	GtkTreeIter *s_iter);
426	static GtkTreePath *gtk_tree_model_sort_elt_get_path (SortLevel *level,
427	SortElt *elt);
428	static void gtk_tree_model_sort_set_model (GtkTreeModelSort *tree_model_sort,
429	GtkTreeModel *child_model);
430	static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
431	GtkTreePath *child_path,
432	gboolean build_levels);
433
434	static int gtk_tree_model_sort_compare_func (gconstpointer a,
435	gconstpointer b,
436	gpointer user_data);
437	static int gtk_tree_model_sort_offset_compare_func (gconstpointer a,
438	gconstpointer b,
439	gpointer user_data);
440	static void gtk_tree_model_sort_clear_cache_helper (GtkTreeModelSort *tree_model_sort,
441	SortLevel *level);
442
443
444	G_DEFINE_TYPE_WITH_CODE (GtkTreeModelSort, gtk_tree_model_sort, G_TYPE_OBJECT,
445	G_ADD_PRIVATE (GtkTreeModelSort)
446	G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_MODEL,
447	gtk_tree_model_sort_tree_model_init)
448	G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_SORTABLE,
449	gtk_tree_model_sort_tree_sortable_init)
450	G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_DRAG_SOURCE,
451	gtk_tree_model_sort_drag_source_init))
452
453	static void
454	gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
455	{
456	GtkTreeModelSortPrivate *priv;
457
458	tree_model_sort->priv = priv =
459	gtk_tree_model_sort_get_instance_private (self: tree_model_sort);
460	priv->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
461	priv->stamp = 0;
462	priv->zero_ref_count = 0;
463	priv->root = NULL;
464	priv->sort_list = NULL;
465	}
466
467	static void
468	gtk_tree_model_sort_class_init (GtkTreeModelSortClass *class)
469	{
470	GObjectClass *object_class;
471
472	object_class = (GObjectClass *) class;
473
474	object_class->set_property = gtk_tree_model_sort_set_property;
475	object_class->get_property = gtk_tree_model_sort_get_property;
476
477	object_class->finalize = gtk_tree_model_sort_finalize;
478
479	/* Properties */
480	g_object_class_install_property (oclass: object_class,
481	property_id: PROP_MODEL,
482	pspec: g_param_spec_object (name: "model",
483	P_("TreeModelSort Model"),
484	P_("The model for the TreeModelSort to sort"),
485	GTK_TYPE_TREE_MODEL,
486	GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
487	}
488
489	static void
490	gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
491	{
492	iface->get_flags = gtk_tree_model_sort_get_flags;
493	iface->get_n_columns = gtk_tree_model_sort_get_n_columns;
494	iface->get_column_type = gtk_tree_model_sort_get_column_type;
495	iface->get_iter = gtk_tree_model_sort_get_iter;
496	iface->get_path = gtk_tree_model_sort_get_path;
497	iface->get_value = gtk_tree_model_sort_get_value;
498	iface->iter_next = gtk_tree_model_sort_iter_next;
499	iface->iter_previous = gtk_tree_model_sort_iter_previous;
500	iface->iter_children = gtk_tree_model_sort_iter_children;
501	iface->iter_has_child = gtk_tree_model_sort_iter_has_child;
502	iface->iter_n_children = gtk_tree_model_sort_iter_n_children;
503	iface->iter_nth_child = gtk_tree_model_sort_iter_nth_child;
504	iface->iter_parent = gtk_tree_model_sort_iter_parent;
505	iface->ref_node = gtk_tree_model_sort_ref_node;
506	iface->unref_node = gtk_tree_model_sort_unref_node;
507	}
508
509	static void
510	gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface *iface)
511	{
512	iface->get_sort_column_id = gtk_tree_model_sort_get_sort_column_id;
513	iface->set_sort_column_id = gtk_tree_model_sort_set_sort_column_id;
514	iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
515	iface->set_default_sort_func = gtk_tree_model_sort_set_default_sort_func;
516	iface->has_default_sort_func = gtk_tree_model_sort_has_default_sort_func;
517	}
518
519	static void
520	gtk_tree_model_sort_drag_source_init (GtkTreeDragSourceIface *iface)
521	{
522	iface->row_draggable = gtk_tree_model_sort_row_draggable;
523	iface->drag_data_delete = gtk_tree_model_sort_drag_data_delete;
524	iface->drag_data_get = gtk_tree_model_sort_drag_data_get;
525	}
526
527	/**
528	* gtk_tree_model_sort_new_with_model: (constructor)
529	* @child_model: A `GtkTreeModel`
530	*
531	* Creates a new `GtkTreeModelSort`, with @child_model as the child model.
532	*
533	* Returns: (transfer full) (type Gtk.TreeModelSort): A new `GtkTreeModelSort`.
534	*/
535	GtkTreeModel *
536	gtk_tree_model_sort_new_with_model (GtkTreeModel *child_model)
537	{
538	GtkTreeModel *retval;
539
540	g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);
541
542	retval = g_object_new (object_type: gtk_tree_model_sort_get_type (), NULL);
543
544	gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
545
546	return retval;
547	}
548
549	/* GObject callbacks */
550	static void
551	gtk_tree_model_sort_finalize (GObject *object)
552	{
553	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
554	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
555
556	gtk_tree_model_sort_set_model (tree_model_sort, NULL);
557
558	if (priv->root)
559	gtk_tree_model_sort_free_level (tree_model_sort, sort_level: priv->root, TRUE);
560
561	if (priv->sort_list)
562	{
563	_gtk_tree_data_list_header_free (header_list: priv->sort_list);
564	priv->sort_list = NULL;
565	}
566
567	if (priv->default_sort_destroy)
568	{
569	priv->default_sort_destroy (priv->default_sort_data);
570	priv->default_sort_destroy = NULL;
571	priv->default_sort_data = NULL;
572	}
573
574
575	/* must chain up */
576	G_OBJECT_CLASS (gtk_tree_model_sort_parent_class)->finalize (object);
577	}
578
579	static void
580	gtk_tree_model_sort_set_property (GObject *object,
581	guint prop_id,
582	const GValue *value,
583	GParamSpec *pspec)
584	{
585	GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);
586
587	switch (prop_id)
588	{
589	case PROP_MODEL:
590	gtk_tree_model_sort_set_model (tree_model_sort, child_model: g_value_get_object (value));
591	break;
592	default:
593	G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
594	break;
595	}
596	}
597
598	static void
599	gtk_tree_model_sort_get_property (GObject *object,
600	guint prop_id,
601	GValue *value,
602	GParamSpec *pspec)
603	{
604	GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);
605
606	switch (prop_id)
607	{
608	case PROP_MODEL:
609	g_value_set_object (value, v_object: gtk_tree_model_sort_get_model (tree_model: tree_model_sort));
610	break;
611	default:
612	G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
613	break;
614	}
615	}
616
617	/* helpers */
618	static SortElt *
619	sort_elt_new (void)
620	{
621	return g_slice_new (SortElt);
622	}
623
624	static void
625	sort_elt_free (gpointer elt)
626	{
627	g_slice_free (SortElt, elt);
628	}
629
630	static void
631	increase_offset_iter (gpointer data,
632	gpointer user_data)
633	{
634	SortElt *elt = data;
635	int offset = GPOINTER_TO_INT (user_data);
636
637	if (elt->offset >= offset)
638	elt->offset++;
639	}
640
641	static void
642	decrease_offset_iter (gpointer data,
643	gpointer user_data)
644	{
645	SortElt *elt = data;
646	int offset = GPOINTER_TO_INT (user_data);
647
648	if (elt->offset > offset)
649	elt->offset--;
650	}
651
652	static void
653	fill_sort_data (SortData *data,
654	GtkTreeModelSort *tree_model_sort,
655	SortLevel *level)
656	{
657	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
658
659	data->tree_model_sort = tree_model_sort;
660
661	if (priv->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
662	{
663	GtkTreeDataSortHeader *header;
664
665	header = _gtk_tree_data_list_get_header (header_list: priv->sort_list,
666	sort_column_id: priv->sort_column_id);
667
668	g_return_if_fail (header != NULL);
669	g_return_if_fail (header->func != NULL);
670
671	data->sort_func = header->func;
672	data->sort_data = header->data;
673	}
674	else
675	{
676	/* absolutely SHOULD NOT happen: */
677	g_return_if_fail (priv->default_sort_func != NULL);
678
679	data->sort_func = priv->default_sort_func;
680	data->sort_data = priv->default_sort_data;
681	}
682
683	if (level->parent_elt)
684	{
685	data->parent_path = gtk_tree_model_sort_elt_get_path (level: level->parent_level,
686	elt: level->parent_elt);
687	gtk_tree_path_append_index (path: data->parent_path, index_: 0);
688	}
689	else
690	{
691	data->parent_path = gtk_tree_path_new_first ();
692	}
693	data->parent_path_depth = gtk_tree_path_get_depth (path: data->parent_path);
694	data->parent_path_indices = gtk_tree_path_get_indices (path: data->parent_path);
695	}
696
697	static void
698	free_sort_data (SortData *data)
699	{
700	gtk_tree_path_free (path: data->parent_path);
701	}
702
703	static SortElt *
704	lookup_elt_with_offset (GtkTreeModelSort *tree_model_sort,
705	SortLevel *level,
706	int offset,
707	GSequenceIter **ret_siter)
708	{
709	GSequenceIter *siter, *end_siter;
710
711	/* FIXME: We have to do a search like this, because the sequence is not
712	* (always) sorted on offset order. Perhaps we should introduce a
713	* second sequence which is sorted on offset order.
714	*/
715	end_siter = g_sequence_get_end_iter (seq: level->seq);
716	for (siter = g_sequence_get_begin_iter (seq: level->seq);
717	siter != end_siter;
718	siter = g_sequence_iter_next (iter: siter))
719	{
720	SortElt *elt = g_sequence_get (iter: siter);
721
722	if (elt->offset == offset)
723	break;
724	}
725
726	if (ret_siter)
727	*ret_siter = siter;
728
729	return GET_ELT (siter);
730	}
731
732
733	static void
734	gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
735	GtkTreePath *start_s_path,
736	GtkTreeIter *start_s_iter,
737	gpointer data)
738	{
739	GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
740	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
741	GtkTreePath *path = NULL;
742	GtkTreeIter iter;
743	GtkTreeIter tmpiter;
744
745	SortElt *elt;
746	SortLevel *level;
747	SortData sort_data;
748
749	gboolean free_s_path = FALSE;
750
751	int index = 0, old_index;
752
753	g_return_if_fail (start_s_path != NULL || start_s_iter != NULL);
754
755	if (!start_s_path)
756	{
757	free_s_path = TRUE;
758	start_s_path = gtk_tree_model_get_path (tree_model: s_model, iter: start_s_iter);
759	}
760
761	path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
762	child_path: start_s_path,
763	FALSE);
764	if (!path)
765	{
766	if (free_s_path)
767	gtk_tree_path_free (path: start_s_path);
768	return;
769	}
770
771	gtk_tree_model_get_iter (GTK_TREE_MODEL (data), iter: &iter, path);
772	gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (data), iter: &iter);
773
774	level = iter.user_data;
775	elt = iter.user_data2;
776
777	if (g_sequence_get_length (seq: level->seq) < 2 ||
778	(priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
779	priv->default_sort_func == NO_SORT_FUNC))
780	{
781	if (free_s_path)
782	gtk_tree_path_free (path: start_s_path);
783
784	gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, iter: &iter);
785	gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), iter: &iter);
786
787	gtk_tree_path_free (path);
788
789	return;
790	}
791
792	if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
793	tmpiter = elt->iter;
794	else
795	gtk_tree_model_get_iter (tree_model: priv->child_model,
796	iter: &tmpiter, path: start_s_path);
797
798	old_index = g_sequence_iter_get_position (iter: elt->siter);
799
800	fill_sort_data (data: &sort_data, tree_model_sort, level);
801	g_sequence_sort_changed (iter: elt->siter,
802	cmp_func: gtk_tree_model_sort_compare_func,
803	cmp_data: &sort_data);
804	free_sort_data (data: &sort_data);
805
806	index = g_sequence_iter_get_position (iter: elt->siter);
807
808	/* Prepare the path for signal emission */
809	gtk_tree_path_up (path);
810	gtk_tree_path_append_index (path, index_: index);
811
812	gtk_tree_model_sort_increment_stamp (tree_model_sort);
813
814	/* if the item moved, then emit rows_reordered */
815	if (old_index != index)
816	{
817	int *new_order;
818	int j;
819
820	GtkTreePath *tmppath;
821
822	new_order = g_new (int, g_sequence_get_length (level->seq));
823
824	for (j = 0; j < g_sequence_get_length (seq: level->seq); j++)
825	{
826	if (index > old_index)
827	{
828	if (j == index)
829	new_order[j] = old_index;
830	else if (j >= old_index && j < index)
831	new_order[j] = j + 1;
832	else
833	new_order[j] = j;
834	}
835	else if (index < old_index)
836	{
837	if (j == index)
838	new_order[j] = old_index;
839	else if (j > index && j <= old_index)
840	new_order[j] = j - 1;
841	else
842	new_order[j] = j;
843	}
844	/* else? shouldn't really happen */
845	}
846
847	if (level->parent_elt)
848	{
849	iter.stamp = priv->stamp;
850	iter.user_data = level->parent_level;
851	iter.user_data2 = level->parent_elt;
852
853	tmppath = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort), iter: &iter);
854
855	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
856	path: tmppath, iter: &iter, new_order);
857	}
858	else
859	{
860	/* toplevel */
861	tmppath = gtk_tree_path_new ();
862
863	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path: tmppath,
864	NULL, new_order);
865	}
866
867	gtk_tree_path_free (path: tmppath);
868	g_free (mem: new_order);
869	}
870
871	/* emit row_changed signal (at new location) */
872	gtk_tree_model_get_iter (GTK_TREE_MODEL (data), iter: &iter, path);
873	gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, iter: &iter);
874	gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), iter: &iter);
875
876	gtk_tree_path_free (path);
877	if (free_s_path)
878	gtk_tree_path_free (path: start_s_path);
879	}
880
881	static void
882	gtk_tree_model_sort_row_inserted (GtkTreeModel *s_model,
883	GtkTreePath *s_path,
884	GtkTreeIter *s_iter,
885	gpointer data)
886	{
887	GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
888	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
889	GtkTreePath *path;
890	GtkTreeIter iter;
891	GtkTreeIter real_s_iter;
892
893	int i = 0;
894
895	gboolean free_s_path = FALSE;
896
897	SortElt *elt;
898	SortLevel *level;
899	SortLevel *parent_level = NULL;
900
901	parent_level = level = SORT_LEVEL (priv->root);
902
903	g_return_if_fail (s_path != NULL || s_iter != NULL);
904
905	if (!s_path)
906	{
907	s_path = gtk_tree_model_get_path (tree_model: s_model, iter: s_iter);
908	free_s_path = TRUE;
909	}
910
911	if (!s_iter)
912	gtk_tree_model_get_iter (tree_model: s_model, iter: &real_s_iter, path: s_path);
913	else
914	real_s_iter = *s_iter;
915
916	if (!priv->root)
917	{
918	gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
919
920	/* the build level already put the inserted iter in the level,
921	so no need to handle this signal anymore */
922
923	goto done_and_submit;
924	}
925
926	/* find the parent level */
927	while (i < gtk_tree_path_get_depth (path: s_path) - 1)
928	{
929	if (!level)
930	{
931	/* level not yet build, we won't cover this signal */
932	goto done;
933	}
934
935	if (g_sequence_get_length (seq: level->seq) < gtk_tree_path_get_indices (path: s_path)[i])
936	{
937	g_warning ("%s: A node was inserted with a parent that's not in the tree.\n"
938	"This possibly means that a GtkTreeModel inserted a child node\n"
939	"before the parent was inserted.",
940	G_STRLOC);
941	goto done;
942	}
943
944	elt = lookup_elt_with_offset (tree_model_sort, level,
945	offset: gtk_tree_path_get_indices (path: s_path)[i],
946	NULL);
947
948	g_return_if_fail (elt != NULL);
949
950	if (!elt->children)
951	{
952	/* not covering this signal */
953	goto done;
954	}
955
956	level = elt->children;
957	parent_level = level;
958	i++;
959	}
960
961	if (!parent_level)
962	goto done;
963
964	if (level->ref_count == 0 && level != priv->root)
965	{
966	gtk_tree_model_sort_free_level (tree_model_sort, sort_level: level, TRUE);
967	goto done;
968	}
969
970	if (!gtk_tree_model_sort_insert_value (tree_model_sort,
971	level: parent_level,
972	s_path,
973	s_iter: &real_s_iter))
974	goto done;
975
976	done_and_submit:
977	path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
978	child_path: s_path,
979	FALSE);
980
981	if (!path)
982	return;
983
984	gtk_tree_model_sort_increment_stamp (tree_model_sort);
985
986	gtk_tree_model_get_iter (GTK_TREE_MODEL (data), iter: &iter, path);
987	gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, iter: &iter);
988	gtk_tree_path_free (path);
989
990	done:
991	if (free_s_path)
992	gtk_tree_path_free (path: s_path);
993
994	return;
995	}
996
997	static void
998	gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
999	GtkTreePath *s_path,
1000	GtkTreeIter *s_iter,
1001	gpointer data)
1002	{
1003	GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
1004	GtkTreePath *path;
1005	GtkTreeIter iter;
1006
1007	g_return_if_fail (s_path != NULL && s_iter != NULL);
1008
1009	path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path: s_path, FALSE);
1010	if (path == NULL)
1011	return;
1012
1013	gtk_tree_model_get_iter (GTK_TREE_MODEL (data), iter: &iter, path);
1014	gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, iter: &iter);
1015
1016	gtk_tree_path_free (path);
1017	}
1018
1019	static void
1020	gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
1021	GtkTreePath *s_path,
1022	gpointer data)
1023	{
1024	GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
1025	GtkTreePath *path = NULL;
1026	SortElt *elt;
1027	SortLevel *level;
1028	GtkTreeIter iter;
1029	int offset;
1030
1031	g_return_if_fail (s_path != NULL);
1032
1033	path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path: s_path, FALSE);
1034	if (path == NULL)
1035	return;
1036
1037	gtk_tree_model_get_iter (GTK_TREE_MODEL (data), iter: &iter, path);
1038
1039	level = SORT_LEVEL (iter.user_data);
1040	elt = SORT_ELT (iter.user_data2);
1041	offset = elt->offset;
1042
1043	gtk_tree_model_get_iter (GTK_TREE_MODEL (data), iter: &iter, path);
1044
1045	while (elt->ref_count > 0)
1046	gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), iter: &iter, FALSE);
1047
1048	/* If this node has children, we free the level (recursively) here
1049	* and specify that unref may not be used, because parent and its
1050	* children have been removed by now.
1051	*/
1052	if (elt->children)
1053	gtk_tree_model_sort_free_level (tree_model_sort,
1054	sort_level: elt->children, FALSE);
1055
1056	if (level->ref_count == 0 && g_sequence_get_length (seq: level->seq) == 1)
1057	{
1058	gtk_tree_model_sort_increment_stamp (tree_model_sort);
1059	gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
1060	gtk_tree_path_free (path);
1061
1062	if (level == tree_model_sort->priv->root)
1063	{
1064	gtk_tree_model_sort_free_level (tree_model_sort,
1065	sort_level: tree_model_sort->priv->root,
1066	TRUE);
1067	tree_model_sort->priv->root = NULL;
1068	}
1069	return;
1070	}
1071
1072	g_sequence_remove (iter: elt->siter);
1073	elt = NULL;
1074
1075	/* The sequence is not ordered on offset, so we traverse the entire
1076	* sequence.
1077	*/
1078	g_sequence_foreach (seq: level->seq, func: decrease_offset_iter,
1079	GINT_TO_POINTER (offset));
1080
1081	gtk_tree_model_sort_increment_stamp (tree_model_sort);
1082	gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
1083
1084	gtk_tree_path_free (path);
1085	}
1086
1087	static void
1088	gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
1089	GtkTreePath *s_path,
1090	GtkTreeIter *s_iter,
1091	int *new_order,
1092	gpointer data)
1093	{
1094	SortLevel *level;
1095	GtkTreeIter iter;
1096	GtkTreePath *path;
1097	int *tmp_array;
1098	int i, length;
1099	GSequenceIter *siter, *end_siter;
1100	GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
1101	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1102
1103	g_return_if_fail (new_order != NULL);
1104
1105	if (s_path == NULL || gtk_tree_path_get_depth (path: s_path) == 0)
1106	{
1107	if (priv->root == NULL)
1108	return;
1109	path = gtk_tree_path_new ();
1110	level = SORT_LEVEL (priv->root);
1111	}
1112	else
1113	{
1114	SortElt *elt;
1115
1116	path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path: s_path, FALSE);
1117	if (path == NULL)
1118	return;
1119	gtk_tree_model_get_iter (GTK_TREE_MODEL (data), iter: &iter, path);
1120
1121	elt = SORT_ELT (iter.user_data2);
1122
1123	if (!elt->children)
1124	{
1125	gtk_tree_path_free (path);
1126	return;
1127	}
1128
1129	level = elt->children;
1130	}
1131
1132	length = g_sequence_get_length (seq: level->seq);
1133	if (length < 2)
1134	{
1135	gtk_tree_path_free (path);
1136	return;
1137	}
1138
1139	tmp_array = g_new (int, length);
1140
1141	/* FIXME: I need to think about whether this can be done in a more
1142	* efficient way?
1143	*/
1144	i = 0;
1145	end_siter = g_sequence_get_end_iter (seq: level->seq);
1146	for (siter = g_sequence_get_begin_iter (seq: level->seq);
1147	siter != end_siter;
1148	siter = g_sequence_iter_next (iter: siter))
1149	{
1150	int j;
1151	SortElt *elt = g_sequence_get (iter: siter);
1152
1153	for (j = 0; j < length; j++)
1154	{
1155	if (elt->offset == new_order[j])
1156	tmp_array[i] = j;
1157	}
1158
1159	i++;
1160	}
1161
1162	/* This loop cannot be merged with the above loop nest, because that
1163	* would introduce duplicate offsets.
1164	*/
1165	i = 0;
1166	end_siter = g_sequence_get_end_iter (seq: level->seq);
1167	for (siter = g_sequence_get_begin_iter (seq: level->seq);
1168	siter != end_siter;
1169	siter = g_sequence_iter_next (iter: siter))
1170	{
1171	SortElt *elt = g_sequence_get (iter: siter);
1172
1173	elt->offset = tmp_array[i];
1174	i++;
1175	}
1176	g_free (mem: tmp_array);
1177
1178	if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
1179	priv->default_sort_func == NO_SORT_FUNC)
1180	{
1181	gtk_tree_model_sort_sort_level (tree_model_sort, level,
1182	FALSE, FALSE);
1183	gtk_tree_model_sort_increment_stamp (tree_model_sort);
1184
1185	if (gtk_tree_path_get_depth (path))
1186	{
1187	gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
1188	iter: &iter,
1189	path);
1190	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
1191	path, iter: &iter, new_order);
1192	}
1193	else
1194	{
1195	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
1196	path, NULL, new_order);
1197	}
1198	}
1199
1200	gtk_tree_path_free (path);
1201	}
1202
1203	/* Fulfill our model requirements */
1204	static GtkTreeModelFlags
1205	gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
1206	{
1207	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1208	GtkTreeModelFlags flags;
1209
1210	g_return_val_if_fail (tree_model_sort->priv->child_model != NULL, 0);
1211
1212	flags = gtk_tree_model_get_flags (tree_model: tree_model_sort->priv->child_model);
1213
1214	if ((flags & GTK_TREE_MODEL_LIST_ONLY) == GTK_TREE_MODEL_LIST_ONLY)
1215	return GTK_TREE_MODEL_LIST_ONLY;
1216
1217	return 0;
1218	}
1219
1220	static int
1221	gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
1222	{
1223	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1224
1225	if (tree_model_sort->priv->child_model == 0)
1226	return 0;
1227
1228	return gtk_tree_model_get_n_columns (tree_model: tree_model_sort->priv->child_model);
1229	}
1230
1231	static GType
1232	gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
1233	int index)
1234	{
1235	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1236
1237	g_return_val_if_fail (tree_model_sort->priv->child_model != NULL, G_TYPE_INVALID);
1238
1239	return gtk_tree_model_get_column_type (tree_model: tree_model_sort->priv->child_model, index_: index);
1240	}
1241
1242	static gboolean
1243	gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
1244	GtkTreeIter *iter,
1245	GtkTreePath *path)
1246	{
1247	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1248	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1249	int *indices;
1250	SortElt *elt;
1251	SortLevel *level;
1252	int depth, i;
1253	GSequenceIter *siter;
1254
1255	g_return_val_if_fail (priv->child_model != NULL, FALSE);
1256
1257	indices = gtk_tree_path_get_indices (path);
1258
1259	if (priv->root == NULL)
1260	gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1261	level = SORT_LEVEL (priv->root);
1262
1263	depth = gtk_tree_path_get_depth (path);
1264	if (depth == 0)
1265	{
1266	iter->stamp = 0;
1267	return FALSE;
1268	}
1269
1270	for (i = 0; i < depth - 1; i++)
1271	{
1272	if ((level == NULL) ||
1273	(indices[i] >= g_sequence_get_length (seq: level->seq)))
1274	{
1275	iter->stamp = 0;
1276	return FALSE;
1277	}
1278
1279	siter = g_sequence_get_iter_at_pos (seq: level->seq, pos: indices[i]);
1280	if (g_sequence_iter_is_end (iter: siter))
1281	{
1282	iter->stamp = 0;
1283	return FALSE;
1284	}
1285
1286	elt = GET_ELT (siter);
1287	g_assert (elt);
1288	if (elt->children == NULL)
1289	gtk_tree_model_sort_build_level (tree_model_sort, parent_level: level, parent_elt: elt);
1290
1291	level = elt->children;
1292	}
1293
1294	if (!level || indices[i] >= g_sequence_get_length (seq: level->seq))
1295	{
1296	iter->stamp = 0;
1297	return FALSE;
1298	}
1299
1300	iter->stamp = priv->stamp;
1301	iter->user_data = level;
1302
1303	siter = g_sequence_get_iter_at_pos (seq: level->seq, pos: indices[depth - 1]);
1304	if (g_sequence_iter_is_end (iter: siter))
1305	{
1306	iter->stamp = 0;
1307	return FALSE;
1308	}
1309	iter->user_data2 = GET_ELT (siter);
1310
1311	return TRUE;
1312	}
1313
1314	static GtkTreePath *
1315	gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
1316	GtkTreeIter *iter)
1317	{
1318	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1319	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1320	GtkTreePath *retval;
1321	SortLevel *level;
1322	SortElt *elt;
1323
1324	g_return_val_if_fail (priv->child_model != NULL, NULL);
1325	g_return_val_if_fail (priv->stamp == iter->stamp, NULL);
1326
1327	retval = gtk_tree_path_new ();
1328
1329	level = SORT_LEVEL (iter->user_data);
1330	elt = SORT_ELT (iter->user_data2);
1331
1332	while (level)
1333	{
1334	int index;
1335
1336	index = g_sequence_iter_get_position (iter: elt->siter);
1337	gtk_tree_path_prepend_index (path: retval, index_: index);
1338
1339	elt = level->parent_elt;
1340	level = level->parent_level;
1341	}
1342
1343	return retval;
1344	}
1345
1346	static void
1347	gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
1348	GtkTreeIter *iter,
1349	int column,
1350	GValue *value)
1351	{
1352	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1353	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1354	GtkTreeIter child_iter;
1355
1356	g_return_if_fail (priv->child_model != NULL);
1357	g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1358
1359	GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1360	gtk_tree_model_get_value (tree_model: priv->child_model,
1361	iter: &child_iter, column, value);
1362	}
1363
1364	static gboolean
1365	gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
1366	GtkTreeIter *iter)
1367	{
1368	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1369	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1370	SortElt *elt;
1371	GSequenceIter *siter;
1372
1373	g_return_val_if_fail (priv->child_model != NULL, FALSE);
1374	g_return_val_if_fail (priv->stamp == iter->stamp, FALSE);
1375
1376	elt = iter->user_data2;
1377
1378	siter = g_sequence_iter_next (iter: elt->siter);
1379	if (g_sequence_iter_is_end (iter: siter))
1380	{
1381	iter->stamp = 0;
1382	return FALSE;
1383	}
1384	iter->user_data2 = GET_ELT (siter);
1385
1386	return TRUE;
1387	}
1388
1389	static gboolean
1390	gtk_tree_model_sort_iter_previous (GtkTreeModel *tree_model,
1391	GtkTreeIter *iter)
1392	{
1393	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1394	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1395	SortElt *elt;
1396	GSequenceIter *siter;
1397
1398	g_return_val_if_fail (priv->child_model != NULL, FALSE);
1399	g_return_val_if_fail (priv->stamp == iter->stamp, FALSE);
1400
1401	elt = iter->user_data2;
1402
1403	if (g_sequence_iter_is_begin (iter: elt->siter))
1404	{
1405	iter->stamp = 0;
1406	return FALSE;
1407	}
1408
1409	siter = g_sequence_iter_prev (iter: elt->siter);
1410	iter->user_data2 = GET_ELT (siter);
1411
1412	return TRUE;
1413	}
1414
1415	static gboolean
1416	gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
1417	GtkTreeIter *iter,
1418	GtkTreeIter *parent)
1419	{
1420	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1421	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1422	SortLevel *level;
1423
1424	iter->stamp = 0;
1425	g_return_val_if_fail (priv->child_model != NULL, FALSE);
1426	if (parent)
1427	g_return_val_if_fail (VALID_ITER (parent, tree_model_sort), FALSE);
1428
1429	if (parent == NULL)
1430	{
1431	if (priv->root == NULL)
1432	gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1433	if (priv->root == NULL)
1434	return FALSE;
1435
1436	level = priv->root;
1437	iter->stamp = priv->stamp;
1438	iter->user_data = level;
1439	iter->user_data2 = g_sequence_get (iter: g_sequence_get_begin_iter (seq: level->seq));
1440	}
1441	else
1442	{
1443	SortElt *elt;
1444
1445	level = SORT_LEVEL (parent->user_data);
1446	elt = SORT_ELT (parent->user_data2);
1447
1448	if (elt->children == NULL)
1449	gtk_tree_model_sort_build_level (tree_model_sort, parent_level: level, parent_elt: elt);
1450
1451	if (elt->children == NULL)
1452	return FALSE;
1453
1454	iter->stamp = priv->stamp;
1455	iter->user_data = elt->children;
1456	iter->user_data2 = g_sequence_get (iter: g_sequence_get_begin_iter (seq: elt->children->seq));
1457	}
1458
1459	return TRUE;
1460	}
1461
1462	static gboolean
1463	gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
1464	GtkTreeIter *iter)
1465	{
1466	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1467	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1468	GtkTreeIter child_iter;
1469
1470	g_return_val_if_fail (priv->child_model != NULL, FALSE);
1471	g_return_val_if_fail (VALID_ITER (iter, tree_model_sort), FALSE);
1472
1473	GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1474
1475	return gtk_tree_model_iter_has_child (tree_model: priv->child_model, iter: &child_iter);
1476	}
1477
1478	static int
1479	gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
1480	GtkTreeIter *iter)
1481	{
1482	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1483	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1484	GtkTreeIter child_iter;
1485
1486	g_return_val_if_fail (priv->child_model != NULL, 0);
1487	if (iter)
1488	g_return_val_if_fail (VALID_ITER (iter, tree_model_sort), 0);
1489
1490	if (iter == NULL)
1491	return gtk_tree_model_iter_n_children (tree_model: priv->child_model, NULL);
1492
1493	GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1494
1495	return gtk_tree_model_iter_n_children (tree_model: priv->child_model, iter: &child_iter);
1496	}
1497
1498	static gboolean
1499	gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
1500	GtkTreeIter *iter,
1501	GtkTreeIter *parent,
1502	int n)
1503	{
1504	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1505	SortLevel *level;
1506	/* We have this for the iter == parent case */
1507	GtkTreeIter children;
1508
1509	if (parent)
1510	g_return_val_if_fail (VALID_ITER (parent, tree_model_sort), FALSE);
1511
1512	/* Use this instead of has_child to force us to build the level, if needed */
1513	if (gtk_tree_model_sort_iter_children (tree_model, iter: &children, parent) == FALSE)
1514	{
1515	iter->stamp = 0;
1516	return FALSE;
1517	}
1518
1519	level = children.user_data;
1520	if (n >= g_sequence_get_length (seq: level->seq))
1521	{
1522	iter->stamp = 0;
1523	return FALSE;
1524	}
1525
1526	iter->stamp = tree_model_sort->priv->stamp;
1527	iter->user_data = level;
1528	iter->user_data2 = g_sequence_get (iter: g_sequence_get_iter_at_pos (seq: level->seq, pos: n));
1529
1530	return TRUE;
1531	}
1532
1533	static gboolean
1534	gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
1535	GtkTreeIter *iter,
1536	GtkTreeIter *child)
1537	{
1538	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1539	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1540	SortLevel *level;
1541
1542	iter->stamp = 0;
1543	g_return_val_if_fail (priv->child_model != NULL, FALSE);
1544	g_return_val_if_fail (VALID_ITER (child, tree_model_sort), FALSE);
1545
1546	level = child->user_data;
1547
1548	if (level->parent_level)
1549	{
1550	iter->stamp = priv->stamp;
1551	iter->user_data = level->parent_level;
1552	iter->user_data2 = level->parent_elt;
1553
1554	return TRUE;
1555	}
1556	return FALSE;
1557	}
1558
1559	static void
1560	gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
1561	GtkTreeIter *iter)
1562	{
1563	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1564	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1565	GtkTreeIter child_iter;
1566	SortLevel *level;
1567	SortElt *elt;
1568
1569	g_return_if_fail (priv->child_model != NULL);
1570	g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1571
1572	GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1573
1574	/* Reference the node in the child model */
1575	gtk_tree_model_ref_node (tree_model: priv->child_model, iter: &child_iter);
1576
1577	/* Increase the reference count of this element and its level */
1578	level = iter->user_data;
1579	elt = iter->user_data2;
1580
1581	elt->ref_count++;
1582	level->ref_count++;
1583
1584	if (level->ref_count == 1)
1585	{
1586	SortLevel *parent_level = level->parent_level;
1587	SortElt *parent_elt = level->parent_elt;
1588
1589	/* We were at zero -- time to decrement the zero_ref_count val */
1590	while (parent_level)
1591	{
1592	parent_elt->zero_ref_count--;
1593
1594	parent_elt = parent_level->parent_elt;
1595	parent_level = parent_level->parent_level;
1596	}
1597
1598	if (priv->root != level)
1599	priv->zero_ref_count--;
1600	}
1601	}
1602
1603	static void
1604	gtk_tree_model_sort_real_unref_node (GtkTreeModel *tree_model,
1605	GtkTreeIter *iter,
1606	gboolean propagate_unref)
1607	{
1608	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1609	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1610	SortLevel *level;
1611	SortElt *elt;
1612
1613	g_return_if_fail (priv->child_model != NULL);
1614	g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1615
1616	if (propagate_unref)
1617	{
1618	GtkTreeIter child_iter;
1619
1620	GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1621	gtk_tree_model_unref_node (tree_model: priv->child_model, iter: &child_iter);
1622	}
1623
1624	level = iter->user_data;
1625	elt = iter->user_data2;
1626
1627	g_return_if_fail (elt->ref_count > 0);
1628
1629	elt->ref_count--;
1630	level->ref_count--;
1631
1632	if (level->ref_count == 0)
1633	{
1634	SortLevel *parent_level = level->parent_level;
1635	SortElt *parent_elt = level->parent_elt;
1636
1637	/* We are at zero -- time to increment the zero_ref_count val */
1638	while (parent_level)
1639	{
1640	parent_elt->zero_ref_count++;
1641
1642	parent_elt = parent_level->parent_elt;
1643	parent_level = parent_level->parent_level;
1644	}
1645
1646	if (priv->root != level)
1647	priv->zero_ref_count++;
1648	}
1649	}
1650
1651	static void
1652	gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
1653	GtkTreeIter *iter)
1654	{
1655	gtk_tree_model_sort_real_unref_node (tree_model, iter, TRUE);
1656	}
1657
1658	/* Sortable interface */
1659	static gboolean
1660	gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable *sortable,
1661	int *sort_column_id,
1662	GtkSortType *order)
1663	{
1664	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1665	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1666
1667	if (sort_column_id)
1668	*sort_column_id = priv->sort_column_id;
1669	if (order)
1670	*order = priv->order;
1671
1672	if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID ||
1673	priv->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
1674	return FALSE;
1675
1676	return TRUE;
1677	}
1678
1679	static void
1680	gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable *sortable,
1681	int sort_column_id,
1682	GtkSortType order)
1683	{
1684	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1685	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1686
1687	if (priv->sort_column_id == sort_column_id && priv->order == order)
1688	return;
1689
1690	if (sort_column_id != GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
1691	{
1692	if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1693	{
1694	GtkTreeDataSortHeader *header = NULL;
1695
1696	header = _gtk_tree_data_list_get_header (header_list: priv->sort_list,
1697	sort_column_id);
1698
1699	/* we want to make sure that we have a function */
1700	g_return_if_fail (header != NULL);
1701	g_return_if_fail (header->func != NULL);
1702	}
1703	else
1704	g_return_if_fail (priv->default_sort_func != NULL);
1705	}
1706
1707	priv->sort_column_id = sort_column_id;
1708	priv->order = order;
1709
1710	gtk_tree_sortable_sort_column_changed (sortable);
1711
1712	gtk_tree_model_sort_sort (tree_model_sort);
1713	}
1714
1715	static void
1716	gtk_tree_model_sort_set_sort_func (GtkTreeSortable *sortable,
1717	int sort_column_id,
1718	GtkTreeIterCompareFunc func,
1719	gpointer data,
1720	GDestroyNotify destroy)
1721	{
1722	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
1723	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1724
1725	priv->sort_list = _gtk_tree_data_list_set_header (header_list: priv->sort_list,
1726	sort_column_id,
1727	func, data, destroy);
1728
1729	if (priv->sort_column_id == sort_column_id)
1730	gtk_tree_model_sort_sort (tree_model_sort);
1731	}
1732
1733	static void
1734	gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable *sortable,
1735	GtkTreeIterCompareFunc func,
1736	gpointer data,
1737	GDestroyNotify destroy)
1738	{
1739	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1740	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1741
1742	if (priv->default_sort_destroy)
1743	{
1744	GDestroyNotify d = priv->default_sort_destroy;
1745
1746	priv->default_sort_destroy = NULL;
1747	d (priv->default_sort_data);
1748	}
1749
1750	priv->default_sort_func = func;
1751	priv->default_sort_data = data;
1752	priv->default_sort_destroy = destroy;
1753
1754	if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1755	gtk_tree_model_sort_sort (tree_model_sort);
1756	}
1757
1758	static gboolean
1759	gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable *sortable)
1760	{
1761	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1762
1763	return (tree_model_sort->priv->default_sort_func != NO_SORT_FUNC);
1764	}
1765
1766	/* DragSource interface */
1767	static gboolean
1768	gtk_tree_model_sort_row_draggable (GtkTreeDragSource *drag_source,
1769	GtkTreePath *path)
1770	{
1771	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1772	GtkTreePath *child_path;
1773	gboolean draggable;
1774
1775	child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort,
1776	sorted_path: path);
1777	draggable = gtk_tree_drag_source_row_draggable (GTK_TREE_DRAG_SOURCE (tree_model_sort->priv->child_model), path: child_path);
1778	gtk_tree_path_free (path: child_path);
1779
1780	return draggable;
1781	}
1782
1783	static GdkContentProvider *
1784	gtk_tree_model_sort_drag_data_get (GtkTreeDragSource *drag_source,
1785	GtkTreePath *path)
1786	{
1787	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1788	GtkTreePath *child_path;
1789	GdkContentProvider *gotten;
1790
1791	child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort, sorted_path: path);
1792	gotten = gtk_tree_drag_source_drag_data_get (GTK_TREE_DRAG_SOURCE (tree_model_sort->priv->child_model), path: child_path);
1793	gtk_tree_path_free (path: child_path);
1794
1795	return gotten;
1796	}
1797
1798	static gboolean
1799	gtk_tree_model_sort_drag_data_delete (GtkTreeDragSource *drag_source,
1800	GtkTreePath *path)
1801	{
1802	GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1803	GtkTreePath *child_path;
1804	gboolean deleted;
1805
1806	child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort, sorted_path: path);
1807	deleted = gtk_tree_drag_source_drag_data_delete (GTK_TREE_DRAG_SOURCE (tree_model_sort->priv->child_model), path: child_path);
1808	gtk_tree_path_free (path: child_path);
1809
1810	return deleted;
1811	}
1812
1813	/* sorting code - private */
1814	static int
1815	gtk_tree_model_sort_compare_func (gconstpointer a,
1816	gconstpointer b,
1817	gpointer user_data)
1818	{
1819	SortData *data = (SortData *)user_data;
1820	GtkTreeModelSort *tree_model_sort = data->tree_model_sort;
1821	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1822	const SortElt *sa = a;
1823	const SortElt *sb = b;
1824
1825	GtkTreeIter iter_a, iter_b;
1826	int retval;
1827
1828	if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1829	{
1830	iter_a = sa->iter;
1831	iter_b = sb->iter;
1832	}
1833	else
1834	{
1835	data->parent_path_indices [data->parent_path_depth-1] = sa->offset;
1836	gtk_tree_model_get_iter (GTK_TREE_MODEL (priv->child_model), iter: &iter_a, path: data->parent_path);
1837	data->parent_path_indices [data->parent_path_depth-1] = sb->offset;
1838	gtk_tree_model_get_iter (GTK_TREE_MODEL (priv->child_model), iter: &iter_b, path: data->parent_path);
1839	}
1840
1841	retval = (* data->sort_func) (GTK_TREE_MODEL (priv->child_model),
1842	&iter_a, &iter_b,
1843	data->sort_data);
1844
1845	if (priv->order == GTK_SORT_DESCENDING)
1846	{
1847	if (retval > 0)
1848	retval = -1;
1849	else if (retval < 0)
1850	retval = 1;
1851	}
1852
1853	return retval;
1854	}
1855
1856	static int
1857	gtk_tree_model_sort_offset_compare_func (gconstpointer a,
1858	gconstpointer b,
1859	gpointer user_data)
1860	{
1861	int retval;
1862
1863	const SortElt *sa = (SortElt *)a;
1864	const SortElt *sb = (SortElt *)b;
1865
1866	SortData *data = (SortData *)user_data;
1867
1868	if (sa->offset < sb->offset)
1869	retval = -1;
1870	else if (sa->offset > sb->offset)
1871	retval = 1;
1872	else
1873	retval = 0;
1874
1875	if (data->tree_model_sort->priv->order == GTK_SORT_DESCENDING)
1876	{
1877	if (retval > 0)
1878	retval = -1;
1879	else if (retval < 0)
1880	retval = 1;
1881	}
1882
1883	return retval;
1884	}
1885
1886	static void
1887	gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
1888	SortLevel *level,
1889	gboolean recurse,
1890	gboolean emit_reordered)
1891	{
1892	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1893	int i;
1894	GSequenceIter *begin_siter, *end_siter, *siter;
1895	SortElt *begin_elt;
1896	int *new_order;
1897
1898	GtkTreeIter iter;
1899	GtkTreePath *path;
1900
1901	SortData data;
1902
1903	g_return_if_fail (level != NULL);
1904
1905	begin_siter = g_sequence_get_begin_iter (seq: level->seq);
1906	begin_elt = g_sequence_get (iter: begin_siter);
1907
1908	if (g_sequence_get_length (seq: level->seq) < 1 && !begin_elt->children)
1909	return;
1910
1911	iter.stamp = priv->stamp;
1912	iter.user_data = level;
1913	iter.user_data2 = begin_elt;
1914
1915	gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (tree_model_sort), iter: &iter);
1916
1917	i = 0;
1918	end_siter = g_sequence_get_end_iter (seq: level->seq);
1919	for (siter = g_sequence_get_begin_iter (seq: level->seq);
1920	siter != end_siter;
1921	siter = g_sequence_iter_next (iter: siter))
1922	{
1923	SortElt *elt = g_sequence_get (iter: siter);
1924
1925	elt->old_index = i;
1926	i++;
1927	}
1928
1929	fill_sort_data (data: &data, tree_model_sort, level);
1930
1931	if (data.sort_func == NO_SORT_FUNC)
1932	g_sequence_sort (seq: level->seq, cmp_func: gtk_tree_model_sort_offset_compare_func,
1933	cmp_data: &data);
1934	else
1935	g_sequence_sort (seq: level->seq, cmp_func: gtk_tree_model_sort_compare_func, cmp_data: &data);
1936
1937	free_sort_data (data: &data);
1938
1939	new_order = g_new (int, g_sequence_get_length (level->seq));
1940
1941	i = 0;
1942	end_siter = g_sequence_get_end_iter (seq: level->seq);
1943	for (siter = g_sequence_get_begin_iter (seq: level->seq);
1944	siter != end_siter;
1945	siter = g_sequence_iter_next (iter: siter))
1946	{
1947	SortElt *elt = g_sequence_get (iter: siter);
1948
1949	new_order[i++] = elt->old_index;
1950	}
1951
1952	if (emit_reordered)
1953	{
1954	gtk_tree_model_sort_increment_stamp (tree_model_sort);
1955	if (level->parent_elt)
1956	{
1957	iter.stamp = priv->stamp;
1958	iter.user_data = level->parent_level;
1959	iter.user_data2 = level->parent_elt;
1960
1961	path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort),
1962	iter: &iter);
1963
1964	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1965	iter: &iter, new_order);
1966	}
1967	else
1968	{
1969	/* toplevel list */
1970	path = gtk_tree_path_new ();
1971	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1972	NULL, new_order);
1973	}
1974
1975	gtk_tree_path_free (path);
1976	}
1977
1978	/* recurse, if possible */
1979	if (recurse)
1980	{
1981	end_siter = g_sequence_get_end_iter (seq: level->seq);
1982	for (siter = g_sequence_get_begin_iter (seq: level->seq);
1983	siter != end_siter;
1984	siter = g_sequence_iter_next (iter: siter))
1985	{
1986	SortElt *elt = g_sequence_get (iter: siter);
1987
1988	if (elt->children)
1989	gtk_tree_model_sort_sort_level (tree_model_sort,
1990	level: elt->children,
1991	TRUE, emit_reordered);
1992	}
1993	}
1994
1995	g_free (mem: new_order);
1996
1997	/* get the iter we referenced at the beginning of this function and
1998	* unref it again
1999	*/
2000	iter.stamp = priv->stamp;
2001	iter.user_data = level;
2002	iter.user_data2 = begin_elt;
2003
2004	gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (tree_model_sort), iter: &iter);
2005	}
2006
2007	static void
2008	gtk_tree_model_sort_sort (GtkTreeModelSort *tree_model_sort)
2009	{
2010	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2011
2012	if (priv->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
2013	return;
2014
2015	if (!priv->root)
2016	return;
2017
2018	if (priv->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
2019	{
2020	GtkTreeDataSortHeader *header = NULL;
2021
2022	header = _gtk_tree_data_list_get_header (header_list: priv->sort_list,
2023	sort_column_id: priv->sort_column_id);
2024
2025	/* we want to make sure that we have a function */
2026	g_return_if_fail (header != NULL);
2027	g_return_if_fail (header->func != NULL);
2028	}
2029	else
2030	g_return_if_fail (priv->default_sort_func != NULL);
2031
2032	gtk_tree_model_sort_sort_level (tree_model_sort, level: priv->root,
2033	TRUE, TRUE);
2034	}
2035
2036	/* signal helpers */
2037	static gboolean
2038	gtk_tree_model_sort_insert_value (GtkTreeModelSort *tree_model_sort,
2039	SortLevel *level,
2040	GtkTreePath *s_path,
2041	GtkTreeIter *s_iter)
2042	{
2043	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2044	SortElt *elt;
2045	SortData data;
2046	int offset;
2047
2048	elt = sort_elt_new ();
2049
2050	offset = gtk_tree_path_get_indices (path: s_path)[gtk_tree_path_get_depth (path: s_path) - 1];
2051
2052	if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2053	elt->iter = *s_iter;
2054	elt->offset = offset;
2055	elt->zero_ref_count = 0;
2056	elt->ref_count = 0;
2057	elt->children = NULL;
2058
2059	/* update all larger offsets */
2060	g_sequence_foreach (seq: level->seq, func: increase_offset_iter, GINT_TO_POINTER (offset));
2061
2062	fill_sort_data (data: &data, tree_model_sort, level);
2063
2064	if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
2065	priv->default_sort_func == NO_SORT_FUNC)
2066	{
2067	elt->siter = g_sequence_insert_sorted (seq: level->seq, data: elt,
2068	cmp_func: gtk_tree_model_sort_offset_compare_func,
2069	cmp_data: &data);
2070	}
2071	else
2072	{
2073	elt->siter = g_sequence_insert_sorted (seq: level->seq, data: elt,
2074	cmp_func: gtk_tree_model_sort_compare_func,
2075	cmp_data: &data);
2076	}
2077
2078	free_sort_data (data: &data);
2079
2080	return TRUE;
2081	}
2082
2083	/* sort elt stuff */
2084	static GtkTreePath *
2085	gtk_tree_model_sort_elt_get_path (SortLevel *level,
2086	SortElt *elt)
2087	{
2088	SortLevel *walker = level;
2089	SortElt *walker2 = elt;
2090	GtkTreePath *path;
2091
2092	g_return_val_if_fail (level != NULL, NULL);
2093	g_return_val_if_fail (elt != NULL, NULL);
2094
2095	path = gtk_tree_path_new ();
2096
2097	while (walker)
2098	{
2099	gtk_tree_path_prepend_index (path, index_: walker2->offset);
2100
2101	if (!walker->parent_level)
2102	break;
2103
2104	walker2 = walker->parent_elt;
2105	walker = walker->parent_level;
2106	}
2107
2108	return path;
2109	}
2110
2111	/**
2112	* gtk_tree_model_sort_set_model:
2113	* @tree_model_sort: The `GtkTreeModelSort`.
2114	* @child_model: (nullable): A `GtkTreeModel`
2115	*
2116	* Sets the model of @tree_model_sort to be @model. If @model is %NULL,
2117	* then the old model is unset. The sort function is unset as a result
2118	* of this call. The model will be in an unsorted state until a sort
2119	* function is set.
2120	**/
2121	static void
2122	gtk_tree_model_sort_set_model (GtkTreeModelSort *tree_model_sort,
2123	GtkTreeModel *child_model)
2124	{
2125	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2126
2127	if (child_model)
2128	g_object_ref (child_model);
2129
2130	if (priv->child_model)
2131	{
2132	g_signal_handler_disconnect (instance: priv->child_model,
2133	handler_id: priv->changed_id);
2134	g_signal_handler_disconnect (instance: priv->child_model,
2135	handler_id: priv->inserted_id);
2136	g_signal_handler_disconnect (instance: priv->child_model,
2137	handler_id: priv->has_child_toggled_id);
2138	g_signal_handler_disconnect (instance: priv->child_model,
2139	handler_id: priv->deleted_id);
2140	g_signal_handler_disconnect (instance: priv->child_model,
2141	handler_id: priv->reordered_id);
2142
2143	/* reset our state */
2144	if (priv->root)
2145	gtk_tree_model_sort_free_level (tree_model_sort, sort_level: priv->root, TRUE);
2146	priv->root = NULL;
2147	_gtk_tree_data_list_header_free (header_list: priv->sort_list);
2148	priv->sort_list = NULL;
2149	g_object_unref (object: priv->child_model);
2150	}
2151
2152	priv->child_model = child_model;
2153
2154	if (child_model)
2155	{
2156	GType *types;
2157	int i, n_columns;
2158
2159	priv->changed_id =
2160	g_signal_connect (child_model, "row-changed",
2161	G_CALLBACK (gtk_tree_model_sort_row_changed),
2162	tree_model_sort);
2163	priv->inserted_id =
2164	g_signal_connect (child_model, "row-inserted",
2165	G_CALLBACK (gtk_tree_model_sort_row_inserted),
2166	tree_model_sort);
2167	priv->has_child_toggled_id =
2168	g_signal_connect (child_model, "row-has-child-toggled",
2169	G_CALLBACK (gtk_tree_model_sort_row_has_child_toggled),
2170	tree_model_sort);
2171	priv->deleted_id =
2172	g_signal_connect (child_model, "row-deleted",
2173	G_CALLBACK (gtk_tree_model_sort_row_deleted),
2174	tree_model_sort);
2175	priv->reordered_id =
2176	g_signal_connect (child_model, "rows-reordered",
2177	G_CALLBACK (gtk_tree_model_sort_rows_reordered),
2178	tree_model_sort);
2179
2180	priv->child_flags = gtk_tree_model_get_flags (tree_model: child_model);
2181	n_columns = gtk_tree_model_get_n_columns (tree_model: child_model);
2182
2183	types = g_new (GType, n_columns);
2184	for (i = 0; i < n_columns; i++)
2185	types[i] = gtk_tree_model_get_column_type (tree_model: child_model, index_: i);
2186
2187	priv->sort_list = _gtk_tree_data_list_header_new (n_columns, types);
2188	g_free (mem: types);
2189
2190	priv->default_sort_func = NO_SORT_FUNC;
2191	priv->stamp = g_random_int ();
2192	}
2193	}
2194
2195	/**
2196	* gtk_tree_model_sort_get_model:
2197	* @tree_model: a `GtkTreeModelSort`
2198	*
2199	* Returns the model the `GtkTreeModelSort` is sorting.
2200	*
2201	* Returns: (transfer none): the "child model" being sorted
2202	**/
2203	GtkTreeModel *
2204	gtk_tree_model_sort_get_model (GtkTreeModelSort *tree_model)
2205	{
2206	g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
2207
2208	return tree_model->priv->child_model;
2209	}
2210
2211
2212	static GtkTreePath *
2213	gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
2214	GtkTreePath *child_path,
2215	gboolean build_levels)
2216	{
2217	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2218	int *child_indices;
2219	GtkTreePath *retval;
2220	SortLevel *level;
2221	int i;
2222
2223	g_return_val_if_fail (priv->child_model != NULL, NULL);
2224	g_return_val_if_fail (child_path != NULL, NULL);
2225
2226	retval = gtk_tree_path_new ();
2227	child_indices = gtk_tree_path_get_indices (path: child_path);
2228
2229	if (priv->root == NULL && build_levels)
2230	gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
2231	level = SORT_LEVEL (priv->root);
2232
2233	for (i = 0; i < gtk_tree_path_get_depth (path: child_path); i++)
2234	{
2235	SortElt *tmp;
2236	GSequenceIter *siter;
2237	gboolean found_child = FALSE;
2238
2239	if (!level)
2240	{
2241	gtk_tree_path_free (path: retval);
2242	return NULL;
2243	}
2244
2245	if (child_indices[i] >= g_sequence_get_length (seq: level->seq))
2246	{
2247	gtk_tree_path_free (path: retval);
2248	return NULL;
2249	}
2250	tmp = lookup_elt_with_offset (tree_model_sort, level,
2251	offset: child_indices[i], ret_siter: &siter);
2252	if (tmp)
2253	{
2254	gtk_tree_path_append_index (path: retval, index_: g_sequence_iter_get_position (iter: siter));
2255	if (tmp->children == NULL && build_levels)
2256	gtk_tree_model_sort_build_level (tree_model_sort, parent_level: level, parent_elt: tmp);
2257
2258	level = tmp->children;
2259	found_child = TRUE;
2260	}
2261
2262	if (! found_child)
2263	{
2264	gtk_tree_path_free (path: retval);
2265	return NULL;
2266	}
2267	}
2268
2269	return retval;
2270	}
2271
2272
2273	/**
2274	* gtk_tree_model_sort_convert_child_path_to_path:
2275	* @tree_model_sort: A `GtkTreeModelSort`
2276	* @child_path: A `GtkTreePath` to convert
2277	*
2278	* Converts @child_path to a path relative to @tree_model_sort. That is,
2279	* @child_path points to a path in the child model. The returned path will
2280	* point to the same row in the sorted model. If @child_path isn’t a valid
2281	* path on the child model, then %NULL is returned.
2282	*
2283	* Returns: (nullable) (transfer full): A newly allocated `GtkTreePath`
2284	**/
2285	GtkTreePath *
2286	gtk_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
2287	GtkTreePath *child_path)
2288	{
2289	g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2290	g_return_val_if_fail (tree_model_sort->priv->child_model != NULL, NULL);
2291	g_return_val_if_fail (child_path != NULL, NULL);
2292
2293	return gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path, TRUE);
2294	}
2295
2296	/**
2297	* gtk_tree_model_sort_convert_child_iter_to_iter:
2298	* @tree_model_sort: A `GtkTreeModelSort`
2299	* @sort_iter: (out): An uninitialized `GtkTreeIter`
2300	* @child_iter: A valid `GtkTreeIter` pointing to a row on the child model
2301	*
2302	* Sets @sort_iter to point to the row in @tree_model_sort that corresponds to
2303	* the row pointed at by @child_iter. If @sort_iter was not set, %FALSE
2304	* is returned. Note: a boolean is only returned since 2.14.
2305	*
2306	* Returns: %TRUE, if @sort_iter was set, i.e. if @sort_iter is a
2307	* valid iterator pointer to a visible row in the child model.
2308	**/
2309	gboolean
2310	gtk_tree_model_sort_convert_child_iter_to_iter (GtkTreeModelSort *tree_model_sort,
2311	GtkTreeIter *sort_iter,
2312	GtkTreeIter *child_iter)
2313	{
2314	gboolean ret;
2315	GtkTreePath *child_path, *path;
2316	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2317
2318	g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), FALSE);
2319	g_return_val_if_fail (priv->child_model != NULL, FALSE);
2320	g_return_val_if_fail (sort_iter != NULL, FALSE);
2321	g_return_val_if_fail (child_iter != NULL, FALSE);
2322	g_return_val_if_fail (sort_iter != child_iter, FALSE);
2323
2324	sort_iter->stamp = 0;
2325
2326	child_path = gtk_tree_model_get_path (tree_model: priv->child_model, iter: child_iter);
2327	g_return_val_if_fail (child_path != NULL, FALSE);
2328
2329	path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path);
2330	gtk_tree_path_free (path: child_path);
2331
2332	if (!path)
2333	{
2334	g_warning ("%s: The conversion of the child path to a GtkTreeModel sort path failed", G_STRLOC);
2335	return FALSE;
2336	}
2337
2338	ret = gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
2339	iter: sort_iter, path);
2340	gtk_tree_path_free (path);
2341
2342	return ret;
2343	}
2344
2345	/**
2346	* gtk_tree_model_sort_convert_path_to_child_path:
2347	* @tree_model_sort: A `GtkTreeModelSort`
2348	* @sorted_path: A `GtkTreePath` to convert
2349	*
2350	* Converts @sorted_path to a path on the child model of @tree_model_sort.
2351	* That is, @sorted_path points to a location in @tree_model_sort. The
2352	* returned path will point to the same location in the model not being
2353	* sorted. If @sorted_path does not point to a location in the child model,
2354	* %NULL is returned.
2355	*
2356	* Returns: (nullable) (transfer full): A newly allocated `GtkTreePath`
2357	**/
2358	GtkTreePath *
2359	gtk_tree_model_sort_convert_path_to_child_path (GtkTreeModelSort *tree_model_sort,
2360	GtkTreePath *sorted_path)
2361	{
2362	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2363	int *sorted_indices;
2364	GtkTreePath *retval;
2365	SortLevel *level;
2366	int i;
2367
2368	g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2369	g_return_val_if_fail (priv->child_model != NULL, NULL);
2370	g_return_val_if_fail (sorted_path != NULL, NULL);
2371
2372	retval = gtk_tree_path_new ();
2373	sorted_indices = gtk_tree_path_get_indices (path: sorted_path);
2374	if (priv->root == NULL)
2375	gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
2376	level = SORT_LEVEL (priv->root);
2377
2378	for (i = 0; i < gtk_tree_path_get_depth (path: sorted_path); i++)
2379	{
2380	SortElt *elt = NULL;
2381	GSequenceIter *siter;
2382
2383	if ((level == NULL) ||
2384	(g_sequence_get_length (seq: level->seq) <= sorted_indices[i]))
2385	{
2386	gtk_tree_path_free (path: retval);
2387	return NULL;
2388	}
2389
2390	siter = g_sequence_get_iter_at_pos (seq: level->seq, pos: sorted_indices[i]);
2391	if (g_sequence_iter_is_end (iter: siter))
2392	{
2393	gtk_tree_path_free (path: retval);
2394	return NULL;
2395	}
2396
2397	elt = GET_ELT (siter);
2398	g_assert (elt);
2399	if (elt->children == NULL)
2400	gtk_tree_model_sort_build_level (tree_model_sort, parent_level: level, parent_elt: elt);
2401
2402	if (level == NULL)
2403	{
2404	gtk_tree_path_free (path: retval);
2405	break;
2406	}
2407
2408	gtk_tree_path_append_index (path: retval, index_: elt->offset);
2409	level = elt->children;
2410	}
2411
2412	return retval;
2413	}
2414
2415	/**
2416	* gtk_tree_model_sort_convert_iter_to_child_iter:
2417	* @tree_model_sort: A `GtkTreeModelSort`
2418	* @child_iter: (out): An uninitialized `GtkTreeIter`
2419	* @sorted_iter: A valid `GtkTreeIter` pointing to a row on @tree_model_sort.
2420	*
2421	* Sets @child_iter to point to the row pointed to by @sorted_iter.
2422	**/
2423	void
2424	gtk_tree_model_sort_convert_iter_to_child_iter (GtkTreeModelSort *tree_model_sort,
2425	GtkTreeIter *child_iter,
2426	GtkTreeIter *sorted_iter)
2427	{
2428	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2429	g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2430	g_return_if_fail (priv->child_model != NULL);
2431	g_return_if_fail (child_iter != NULL);
2432	g_return_if_fail (VALID_ITER (sorted_iter, tree_model_sort));
2433	g_return_if_fail (sorted_iter != child_iter);
2434
2435	if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2436	{
2437	*child_iter = SORT_ELT (sorted_iter->user_data2)->iter;
2438	}
2439	else
2440	{
2441	GtkTreePath *path;
2442	gboolean valid = FALSE;
2443
2444	path = gtk_tree_model_sort_elt_get_path (level: sorted_iter->user_data,
2445	elt: sorted_iter->user_data2);
2446	valid = gtk_tree_model_get_iter (tree_model: priv->child_model, iter: child_iter, path);
2447	gtk_tree_path_free (path);
2448
2449	g_return_if_fail (valid == TRUE);
2450	}
2451	}
2452
2453	static void
2454	gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
2455	SortLevel *parent_level,
2456	SortElt *parent_elt)
2457	{
2458	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2459	GtkTreeIter iter;
2460	SortLevel *new_level;
2461	int length = 0;
2462	int i;
2463
2464	g_assert (priv->child_model != NULL);
2465
2466	if (parent_level == NULL)
2467	{
2468	if (gtk_tree_model_get_iter_first (tree_model: priv->child_model, iter: &iter) == FALSE)
2469	return;
2470	length = gtk_tree_model_iter_n_children (tree_model: priv->child_model, NULL);
2471	}
2472	else
2473	{
2474	GtkTreeIter parent_iter;
2475	GtkTreeIter child_parent_iter;
2476
2477	parent_iter.stamp = priv->stamp;
2478	parent_iter.user_data = parent_level;
2479	parent_iter.user_data2 = parent_elt;
2480
2481	gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2482	child_iter: &child_parent_iter,
2483	sorted_iter: &parent_iter);
2484	if (gtk_tree_model_iter_children (tree_model: priv->child_model,
2485	iter: &iter,
2486	parent: &child_parent_iter) == FALSE)
2487	return;
2488
2489	/* stamp may have changed */
2490	gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2491	child_iter: &child_parent_iter,
2492	sorted_iter: &parent_iter);
2493
2494	length = gtk_tree_model_iter_n_children (tree_model: priv->child_model, iter: &child_parent_iter);
2495
2496	gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (tree_model_sort),
2497	iter: &parent_iter);
2498	}
2499
2500	g_return_if_fail (length > 0);
2501
2502	new_level = g_new (SortLevel, 1);
2503	new_level->seq = g_sequence_new (data_destroy: sort_elt_free);
2504	new_level->ref_count = 0;
2505	new_level->parent_level = parent_level;
2506	new_level->parent_elt = parent_elt;
2507
2508	if (parent_elt)
2509	parent_elt->children = new_level;
2510	else
2511	priv->root = new_level;
2512
2513	/* increase the count of zero ref_counts.*/
2514	while (parent_level)
2515	{
2516	parent_elt->zero_ref_count++;
2517
2518	parent_elt = parent_level->parent_elt;
2519	parent_level = parent_level->parent_level;
2520	}
2521
2522	if (new_level != priv->root)
2523	priv->zero_ref_count++;
2524
2525	for (i = 0; i < length; i++)
2526	{
2527	SortElt *sort_elt;
2528
2529	sort_elt = sort_elt_new ();
2530	sort_elt->offset = i;
2531	sort_elt->zero_ref_count = 0;
2532	sort_elt->ref_count = 0;
2533	sort_elt->children = NULL;
2534
2535	if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2536	{
2537	sort_elt->iter = iter;
2538	if (gtk_tree_model_iter_next (tree_model: priv->child_model, iter: &iter) == FALSE &&
2539	i < length - 1)
2540	{
2541	if (parent_level)
2542	{
2543	GtkTreePath *level;
2544	char *str;
2545
2546	level = gtk_tree_model_sort_elt_get_path (level: parent_level,
2547	elt: parent_elt);
2548	str = gtk_tree_path_to_string (path: level);
2549	gtk_tree_path_free (path: level);
2550
2551	g_warning ("%s: There is a discrepancy between the sort model "
2552	"and the child model. The child model is "
2553	"advertising a wrong length for level %s:.",
2554	G_STRLOC, str);
2555	g_free (mem: str);
2556	}
2557	else
2558	{
2559	g_warning ("%s: There is a discrepancy between the sort model "
2560	"and the child model. The child model is "
2561	"advertising a wrong length for the root level.",
2562	G_STRLOC);
2563	}
2564
2565	return;
2566	}
2567	}
2568
2569	sort_elt->siter = g_sequence_append (seq: new_level->seq, data: sort_elt);
2570	}
2571
2572	/* sort level */
2573	gtk_tree_model_sort_sort_level (tree_model_sort, level: new_level,
2574	FALSE, FALSE);
2575	}
2576
2577	static void
2578	gtk_tree_model_sort_free_level (GtkTreeModelSort *tree_model_sort,
2579	SortLevel *sort_level,
2580	gboolean unref)
2581	{
2582	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2583	GSequenceIter *siter;
2584	GSequenceIter *end_siter;
2585
2586	g_assert (sort_level);
2587
2588	end_siter = g_sequence_get_end_iter (seq: sort_level->seq);
2589	for (siter = g_sequence_get_begin_iter (seq: sort_level->seq);
2590	siter != end_siter;
2591	siter = g_sequence_iter_next (iter: siter))
2592	{
2593	SortElt *elt = g_sequence_get (iter: siter);
2594
2595	if (elt->children)
2596	gtk_tree_model_sort_free_level (tree_model_sort,
2597	sort_level: elt->children, unref);
2598	}
2599
2600	if (sort_level->ref_count == 0)
2601	{
2602	SortLevel *parent_level = sort_level->parent_level;
2603	SortElt *parent_elt = sort_level->parent_elt;
2604
2605	while (parent_level)
2606	{
2607	parent_elt->zero_ref_count--;
2608
2609	parent_elt = parent_level->parent_elt;
2610	parent_level = parent_level->parent_level;
2611	}
2612
2613	if (sort_level != priv->root)
2614	priv->zero_ref_count--;
2615	}
2616
2617	if (sort_level->parent_elt)
2618	{
2619	if (unref)
2620	{
2621	GtkTreeIter parent_iter;
2622
2623	parent_iter.stamp = tree_model_sort->priv->stamp;
2624	parent_iter.user_data = sort_level->parent_level;
2625	parent_iter.user_data2 = sort_level->parent_elt;
2626
2627	gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (tree_model_sort),
2628	iter: &parent_iter);
2629	}
2630
2631	sort_level->parent_elt->children = NULL;
2632	}
2633	else
2634	priv->root = NULL;
2635
2636	g_sequence_free (seq: sort_level->seq);
2637	sort_level->seq = NULL;
2638
2639	g_free (mem: sort_level);
2640	sort_level = NULL;
2641	}
2642
2643	static void
2644	gtk_tree_model_sort_increment_stamp (GtkTreeModelSort *tree_model_sort)
2645	{
2646	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2647
2648	do
2649	{
2650	priv->stamp++;
2651	}
2652	while (priv->stamp == 0);
2653
2654	gtk_tree_model_sort_clear_cache (tree_model_sort);
2655	}
2656
2657	static void
2658	gtk_tree_model_sort_clear_cache_helper_iter (gpointer data,
2659	gpointer user_data)
2660	{
2661	GtkTreeModelSort *tree_model_sort = user_data;
2662	SortElt *elt = data;
2663
2664	if (elt->zero_ref_count > 0)
2665	gtk_tree_model_sort_clear_cache_helper (tree_model_sort, level: elt->children);
2666	}
2667
2668	static void
2669	gtk_tree_model_sort_clear_cache_helper (GtkTreeModelSort *tree_model_sort,
2670	SortLevel *level)
2671	{
2672	g_assert (level != NULL);
2673
2674	g_sequence_foreach (seq: level->seq, func: gtk_tree_model_sort_clear_cache_helper_iter,
2675	user_data: tree_model_sort);
2676
2677	if (level->ref_count == 0 && level != tree_model_sort->priv->root)
2678	gtk_tree_model_sort_free_level (tree_model_sort, sort_level: level, TRUE);
2679	}
2680
2681	/**
2682	* gtk_tree_model_sort_reset_default_sort_func:
2683	* @tree_model_sort: A `GtkTreeModelSort`
2684	*
2685	* This resets the default sort function to be in the “unsorted” state. That
2686	* is, it is in the same order as the child model. It will re-sort the model
2687	* to be in the same order as the child model only if the `GtkTreeModelSort`
2688	* is in “unsorted” state.
2689	**/
2690	void
2691	gtk_tree_model_sort_reset_default_sort_func (GtkTreeModelSort *tree_model_sort)
2692	{
2693	GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2694
2695	g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2696
2697	if (priv->default_sort_destroy)
2698	{
2699	GDestroyNotify d = priv->default_sort_destroy;
2700
2701	priv->default_sort_destroy = NULL;
2702	d (priv->default_sort_data);
2703	}
2704
2705	priv->default_sort_func = NO_SORT_FUNC;
2706	priv->default_sort_data = NULL;
2707	priv->default_sort_destroy = NULL;
2708
2709	if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
2710	gtk_tree_model_sort_sort (tree_model_sort);
2711	priv->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
2712	}
2713
2714	/**
2715	* gtk_tree_model_sort_clear_cache:
2716	* @tree_model_sort: A `GtkTreeModelSort`
2717	*
2718	* This function should almost never be called. It clears the @tree_model_sort
2719	* of any cached iterators that haven’t been reffed with
2720	* gtk_tree_model_ref_node(). This might be useful if the child model being
2721	* sorted is static (and doesn’t change often) and there has been a lot of
2722	* unreffed access to nodes. As a side effect of this function, all unreffed
2723	* iters will be invalid.
2724	**/
2725	void
2726	gtk_tree_model_sort_clear_cache (GtkTreeModelSort *tree_model_sort)
2727	{
2728	g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2729
2730	if (tree_model_sort->priv->zero_ref_count > 0)
2731	gtk_tree_model_sort_clear_cache_helper (tree_model_sort, level: (SortLevel *)tree_model_sort->priv->root);
2732	}
2733
2734	static gboolean
2735	gtk_tree_model_sort_iter_is_valid_helper (GtkTreeIter *iter,
2736	SortLevel *level)
2737	{
2738	GSequenceIter *siter;
2739	GSequenceIter *end_siter;
2740
2741	end_siter = g_sequence_get_end_iter (seq: level->seq);
2742	for (siter = g_sequence_get_begin_iter (seq: level->seq);
2743	siter != end_siter; siter = g_sequence_iter_next (iter: siter))
2744	{
2745	SortElt *elt = g_sequence_get (iter: siter);
2746
2747	if (iter->user_data == level && iter->user_data2 == elt)
2748	return TRUE;
2749
2750	if (elt->children)
2751	if (gtk_tree_model_sort_iter_is_valid_helper (iter, level: elt->children))
2752	return TRUE;
2753	}
2754
2755	return FALSE;
2756	}
2757
2758	/**
2759	* gtk_tree_model_sort_iter_is_valid:
2760	* @tree_model_sort: A `GtkTreeModelSort`.
2761	* @iter: A `GtkTreeIter`
2762	*
2763	* > This function is slow. Only use it for debugging and/or testing
2764	* > purposes.
2765	*
2766	* Checks if the given iter is a valid iter for this `GtkTreeModelSort`.
2767	*
2768	* Returns: %TRUE if the iter is valid, %FALSE if the iter is invalid.
2769	**/
2770	gboolean
2771	gtk_tree_model_sort_iter_is_valid (GtkTreeModelSort *tree_model_sort,
2772	GtkTreeIter *iter)
2773	{
2774	g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), FALSE);
2775	g_return_val_if_fail (iter != NULL, FALSE);
2776
2777	if (!VALID_ITER (iter, tree_model_sort))
2778	return FALSE;
2779
2780	return gtk_tree_model_sort_iter_is_valid_helper (iter,
2781	level: tree_model_sort->priv->root);
2782	}
2783