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