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