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