Pileus Git - ~andy/gtk/blob - gtk/gtktreestore.c

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