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

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