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

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