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

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