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