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