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 "gtktreemodel.h"
  24 #include "gtktreestore.h"
  25 #include "gtktreedatalist.h"
  26 #include "gtktreednd.h"
  27 #include "gtkalias.h"
  28
  29 #define G_NODE(node) ((GNode *)node)
  30 #define GTK_TREE_STORE_IS_SORTED(tree) (GTK_TREE_STORE (tree)->sort_column_id != GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
  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   GNode *new_node;
1144
1145   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1146   g_return_if_fail (iter != NULL);
1147   if (parent)
1148     g_return_if_fail (VALID_ITER (parent, tree_store));
1149
1150   if (parent)
1151     parent_node = parent->user_data;
1152   else
1153     parent_node = tree_store->root;
1154
1155   tree_store->columns_dirty = TRUE;
1156
1157   new_node = g_node_new (NULL);
1158
1159   iter->stamp = tree_store->stamp;
1160   iter->user_data = new_node;
1161   g_node_insert (parent_node, position, new_node);
1162
1163   path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1164   gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1165
1166   if (parent_node != tree_store->root)
1167     {
1168       if (new_node->prev == NULL && new_node->next == NULL)
1169         {
1170           gtk_tree_path_up (path);
1171           gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, parent);
1172         }
1173     }
1174
1175   gtk_tree_path_free (path);
1176
1177   validate_tree ((GtkTreeStore*)tree_store);
1178 }
1179
1180 /**
1181  * gtk_tree_store_insert_before:
1182  * @tree_store: A #GtkTreeStore
1183  * @iter: An unset #GtkTreeIter to set to the new row
1184  * @parent: A valid #GtkTreeIter, or %NULL
1185  * @sibling: A valid #GtkTreeIter, or %NULL
1186  *
1187  * Inserts a new row before @sibling.  If @sibling is %NULL, then the row will
1188  * be appended to @parent 's children.  If @parent and @sibling are %NULL, then
1189  * the row will be appended to the toplevel.  If both @sibling and @parent are
1190  * set, then @parent must be the parent of @sibling.  When @sibling is set,
1191  * @parent is optional.
1192  *
1193  * @iter will be changed to point to this new row.  The row will be empty after
1194  * this function is called.  To fill in values, you need to call
1195  * gtk_tree_store_set() or gtk_tree_store_set_value().
1196  *
1197  **/
1198 void
1199 gtk_tree_store_insert_before (GtkTreeStore *tree_store,
1200                               GtkTreeIter  *iter,
1201                               GtkTreeIter  *parent,
1202                               GtkTreeIter  *sibling)
1203 {
1204   GtkTreePath *path;
1205   GNode *parent_node = NULL;
1206   GNode *new_node;
1207
1208   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1209   g_return_if_fail (iter != NULL);
1210   if (parent != NULL)
1211     g_return_if_fail (VALID_ITER (parent, tree_store));
1212   if (sibling != NULL)
1213     g_return_if_fail (VALID_ITER (sibling, tree_store));
1214
1215   if (parent == NULL && sibling == NULL)
1216     parent_node = tree_store->root;
1217   else if (parent == NULL)
1218     parent_node = G_NODE (sibling->user_data)->parent;
1219   else if (sibling == NULL)
1220     parent_node = G_NODE (parent->user_data);
1221   else
1222     {
1223       g_return_if_fail (G_NODE (sibling->user_data)->parent == G_NODE (parent->user_data));
1224       parent_node = G_NODE (parent->user_data);
1225     }
1226
1227   tree_store->columns_dirty = TRUE;
1228
1229   new_node = g_node_new (NULL);
1230
1231   g_node_insert_before (parent_node,
1232                         sibling ? G_NODE (sibling->user_data) : NULL,
1233                         new_node);
1234
1235   iter->stamp = tree_store->stamp;
1236   iter->user_data = new_node;
1237
1238   path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1239   gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1240
1241   if (parent_node != tree_store->root)
1242     {
1243       if (new_node->prev == NULL && new_node->next == NULL)
1244         {
1245           GtkTreeIter parent_iter;
1246
1247           parent_iter.stamp = tree_store->stamp;
1248           parent_iter.user_data = parent_node;
1249
1250           gtk_tree_path_up (path);
1251           gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, &parent_iter);
1252         }
1253     }
1254
1255   gtk_tree_path_free (path);
1256
1257   validate_tree ((GtkTreeStore*)tree_store);
1258 }
1259
1260 /**
1261  * gtk_tree_store_insert_after:
1262  * @tree_store: A #GtkTreeStore
1263  * @iter: An unset #GtkTreeIter to set to the new row
1264  * @parent: A valid #GtkTreeIter, or %NULL
1265  * @sibling: A valid #GtkTreeIter, or %NULL
1266  *
1267  * Inserts a new row after @sibling.  If @sibling is %NULL, then the row will be
1268  * prepended to @parent 's children.  If @parent and @sibling are %NULL, then
1269  * the row will be prepended to the toplevel.  If both @sibling and @parent are
1270  * set, then @parent must be the parent of @sibling.  When @sibling is set,
1271  * @parent is optional.
1272  *
1273  * @iter will be changed to point to this new row.  The row will be empty after
1274  * this function is called.  To fill in values, you need to call
1275  * gtk_tree_store_set() or gtk_tree_store_set_value().
1276  *
1277  **/
1278 void
1279 gtk_tree_store_insert_after (GtkTreeStore *tree_store,
1280                              GtkTreeIter  *iter,
1281                              GtkTreeIter  *parent,
1282                              GtkTreeIter  *sibling)
1283 {
1284   GtkTreePath *path;
1285   GNode *parent_node;
1286   GNode *new_node;
1287
1288   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1289   g_return_if_fail (iter != NULL);
1290   if (parent != NULL)
1291     g_return_if_fail (VALID_ITER (parent, tree_store));
1292   if (sibling != NULL)
1293     g_return_if_fail (VALID_ITER (sibling, tree_store));
1294
1295   if (parent == NULL && sibling == NULL)
1296     parent_node = tree_store->root;
1297   else if (parent == NULL)
1298     parent_node = G_NODE (sibling->user_data)->parent;
1299   else if (sibling == NULL)
1300     parent_node = G_NODE (parent->user_data);
1301   else
1302     {
1303       g_return_if_fail (G_NODE (sibling->user_data)->parent ==
1304                         G_NODE (parent->user_data));
1305       parent_node = G_NODE (parent->user_data);
1306     }
1307
1308   tree_store->columns_dirty = TRUE;
1309
1310   new_node = g_node_new (NULL);
1311
1312   g_node_insert_after (parent_node,
1313                        sibling ? G_NODE (sibling->user_data) : NULL,
1314                        new_node);
1315
1316   iter->stamp = tree_store->stamp;
1317   iter->user_data = new_node;
1318
1319   path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1320   gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1321
1322   if (parent_node != tree_store->root)
1323     {
1324       if (new_node->prev == NULL && new_node->next == NULL)
1325         {
1326           GtkTreeIter parent_iter;
1327
1328           parent_iter.stamp = tree_store->stamp;
1329           parent_iter.user_data = parent_node;
1330
1331           gtk_tree_path_up (path);
1332           gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, &parent_iter);
1333         }
1334     }
1335
1336   gtk_tree_path_free (path);
1337
1338   validate_tree ((GtkTreeStore*)tree_store);
1339 }
1340
1341 /**
1342  * gtk_tree_store_prepend:
1343  * @tree_store: A #GtkTreeStore
1344  * @iter: An unset #GtkTreeIter to set to the prepended row
1345  * @parent: A valid #GtkTreeIter, or %NULL
1346  *
1347  * Prepends a new row to @tree_store.  If @parent is non-%NULL, then it will prepend
1348  * the new row before the first child of @parent, otherwise it will prepend a row
1349  * to the top level.  @iter will be changed to point to this new row.  The row
1350  * will be empty after this function is called.  To fill in values, you need to
1351  * call gtk_tree_store_set() or gtk_tree_store_set_value().
1352  **/
1353 void
1354 gtk_tree_store_prepend (GtkTreeStore *tree_store,
1355                         GtkTreeIter  *iter,
1356                         GtkTreeIter  *parent)
1357 {
1358   GNode *parent_node;
1359
1360   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1361   g_return_if_fail (iter != NULL);
1362   if (parent != NULL)
1363     g_return_if_fail (VALID_ITER (parent, tree_store));
1364
1365   tree_store->columns_dirty = TRUE;
1366
1367   if (parent == NULL)
1368     parent_node = tree_store->root;
1369   else
1370     parent_node = parent->user_data;
1371
1372   if (parent_node->children == NULL)
1373     {
1374       GtkTreePath *path;
1375
1376       iter->stamp = tree_store->stamp;
1377       iter->user_data = g_node_new (NULL);
1378
1379       g_node_prepend (parent_node, G_NODE (iter->user_data));
1380
1381       path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1382       gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1383
1384       if (parent_node != tree_store->root)
1385         {
1386           gtk_tree_path_up (path);
1387           gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, parent);
1388         }
1389       gtk_tree_path_free (path);
1390     }
1391   else
1392     {
1393       gtk_tree_store_insert_after (tree_store, iter, parent, NULL);
1394     }
1395
1396   validate_tree ((GtkTreeStore*)tree_store);
1397 }
1398
1399 /**
1400  * gtk_tree_store_append:
1401  * @tree_store: A #GtkTreeStore
1402  * @iter: An unset #GtkTreeIter to set to the appended row
1403  * @parent: A valid #GtkTreeIter, or %NULL
1404  *
1405  * Appends a new row to @tree_store.  If @parent is non-%NULL, then it will append the
1406  * new row after the last child of @parent, otherwise it will append a row to
1407  * the top level.  @iter will be changed to point to this new row.  The row will
1408  * be empty after this function is called.  To fill in values, you need to call
1409  * gtk_tree_store_set() or gtk_tree_store_set_value().
1410  **/
1411 void
1412 gtk_tree_store_append (GtkTreeStore *tree_store,
1413                        GtkTreeIter  *iter,
1414                        GtkTreeIter  *parent)
1415 {
1416   GNode *parent_node;
1417
1418   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1419   g_return_if_fail (iter != NULL);
1420
1421   if (parent != NULL)
1422     g_return_if_fail (VALID_ITER (parent, tree_store));
1423
1424   if (parent == NULL)
1425     parent_node = tree_store->root;
1426   else
1427     parent_node = parent->user_data;
1428
1429   tree_store->columns_dirty = TRUE;
1430
1431   if (parent_node->children == NULL)
1432     {
1433       GtkTreePath *path;
1434
1435       iter->stamp = tree_store->stamp;
1436       iter->user_data = g_node_new (NULL);
1437
1438       g_node_append (parent_node, G_NODE (iter->user_data));
1439
1440       path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
1441       gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);
1442
1443       if (parent_node != tree_store->root)
1444         {
1445           gtk_tree_path_up (path);
1446           gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, parent);
1447         }
1448       gtk_tree_path_free (path);
1449     }
1450   else
1451     {
1452       gtk_tree_store_insert_before (tree_store, iter, parent, NULL);
1453     }
1454
1455   validate_tree ((GtkTreeStore*)tree_store);
1456 }
1457
1458 /**
1459  * gtk_tree_store_is_ancestor:
1460  * @tree_store: A #GtkTreeStore
1461  * @iter: A valid #GtkTreeIter
1462  * @descendant: A valid #GtkTreeIter
1463  *
1464  * Returns %TRUE if @iter is an ancestor of @descendant.  That is, @iter is the
1465  * parent (or grandparent or great-grandparent) of @descendant.
1466  *
1467  * Return value: %TRUE, if @iter is an ancestor of @descendant
1468  **/
1469 gboolean
1470 gtk_tree_store_is_ancestor (GtkTreeStore *tree_store,
1471                             GtkTreeIter  *iter,
1472                             GtkTreeIter  *descendant)
1473 {
1474   g_return_val_if_fail (GTK_IS_TREE_STORE (tree_store), FALSE);
1475   g_return_val_if_fail (VALID_ITER (iter, tree_store), FALSE);
1476   g_return_val_if_fail (VALID_ITER (descendant, tree_store), FALSE);
1477
1478   return g_node_is_ancestor (G_NODE (iter->user_data),
1479                              G_NODE (descendant->user_data));
1480 }
1481
1482
1483 /**
1484  * gtk_tree_store_iter_depth:
1485  * @tree_store: A #GtkTreeStore
1486  * @iter: A valid #GtkTreeIter
1487  *
1488  * Returns the depth of @iter.  This will be 0 for anything on the root level, 1
1489  * for anything down a level, etc.
1490  *
1491  * Return value: The depth of @iter
1492  **/
1493 gint
1494 gtk_tree_store_iter_depth (GtkTreeStore *tree_store,
1495                            GtkTreeIter  *iter)
1496 {
1497   g_return_val_if_fail (GTK_IS_TREE_STORE (tree_store), 0);
1498   g_return_val_if_fail (VALID_ITER (iter, tree_store), 0);
1499
1500   return g_node_depth (G_NODE (iter->user_data)) - 2;
1501 }
1502
1503 /* simple ripoff from g_node_traverse_post_order */
1504 static gboolean
1505 gtk_tree_store_clear_traverse (GNode *node,
1506                                GtkTreeStore *store)
1507 {
1508   GtkTreeIter iter;
1509
1510   if (node->children)
1511     {
1512       GNode *child;
1513
1514       child = node->children;
1515       while (child)
1516         {
1517           register GNode *current;
1518
1519           current = child;
1520           child = current->next;
1521           if (gtk_tree_store_clear_traverse (current, store))
1522             return TRUE;
1523         }
1524
1525       if (node->parent)
1526         {
1527           iter.stamp = store->stamp;
1528           iter.user_data = node;
1529
1530           gtk_tree_store_remove (store, &iter);
1531         }
1532     }
1533   else if (node->parent)
1534     {
1535       iter.stamp = store->stamp;
1536       iter.user_data = node;
1537
1538       gtk_tree_store_remove (store, &iter);
1539     }
1540
1541   return FALSE;
1542 }
1543
1544 /**
1545  * gtk_tree_store_clear:
1546  * @tree_store: a #GtkTreeStore
1547  *
1548  * Removes all rows from @tree_store
1549  **/
1550 void
1551 gtk_tree_store_clear (GtkTreeStore *tree_store)
1552 {
1553   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1554
1555   gtk_tree_store_clear_traverse (tree_store->root, tree_store);
1556 }
1557
1558 static gboolean
1559 gtk_tree_store_iter_is_valid_helper (GtkTreeIter *iter,
1560                                      GNode       *first)
1561 {
1562   GNode *node;
1563
1564   node = first;
1565
1566   do
1567     {
1568       if (node == iter->user_data)
1569         return TRUE;
1570
1571       if (node->children)
1572         if (gtk_tree_store_iter_is_valid_helper (iter, node->children))
1573           return TRUE;
1574
1575       node = node->next;
1576     }
1577   while (node);
1578
1579   return FALSE;
1580 }
1581
1582 /**
1583  * gtk_tree_store_iter_is_valid:
1584  * @tree_store: A #GtkTreeStore.
1585  * @iter: A #GtkTreeIter.
1586  *
1587  * WARNING: This function is slow. Only use it for debugging and/or testing
1588  * purposes.
1589  *
1590  * Checks if the given iter is a valid iter for this #GtkTreeStore.
1591  *
1592  * Return value: %TRUE if the iter is valid, %FALSE if the iter is invalid.
1593  *
1594  * Since: 2.2
1595  **/
1596 gboolean
1597 gtk_tree_store_iter_is_valid (GtkTreeStore *tree_store,
1598                               GtkTreeIter  *iter)
1599 {
1600   g_return_val_if_fail (GTK_IS_TREE_STORE (tree_store), FALSE);
1601   g_return_val_if_fail (iter != NULL, FALSE);
1602
1603   if (!VALID_ITER (iter, tree_store))
1604     return FALSE;
1605
1606   return gtk_tree_store_iter_is_valid_helper (iter, tree_store->root);
1607 }
1608
1609 /* DND */
1610
1611
1612 static gboolean real_gtk_tree_store_row_draggable (GtkTreeDragSource *drag_source,
1613                                                    GtkTreePath       *path)
1614 {
1615   return TRUE;
1616 }
1617
1618 static gboolean
1619 gtk_tree_store_drag_data_delete (GtkTreeDragSource *drag_source,
1620                                  GtkTreePath       *path)
1621 {
1622   GtkTreeIter iter;
1623
1624   g_return_val_if_fail (GTK_IS_TREE_STORE (drag_source), FALSE);
1625
1626   if (gtk_tree_model_get_iter (GTK_TREE_MODEL (drag_source),
1627                                &iter,
1628                                path))
1629     {
1630       gtk_tree_store_remove (GTK_TREE_STORE (drag_source),
1631                              &iter);
1632       return TRUE;
1633     }
1634   else
1635     {
1636       return FALSE;
1637     }
1638 }
1639
1640 static gboolean
1641 gtk_tree_store_drag_data_get (GtkTreeDragSource *drag_source,
1642                               GtkTreePath       *path,
1643                               GtkSelectionData  *selection_data)
1644 {
1645   g_return_val_if_fail (GTK_IS_TREE_STORE (drag_source), FALSE);
1646
1647   /* Note that we don't need to handle the GTK_TREE_MODEL_ROW
1648    * target, because the default handler does it for us, but
1649    * we do anyway for the convenience of someone maybe overriding the
1650    * default handler.
1651    */
1652
1653   if (gtk_tree_set_row_drag_data (selection_data,
1654                                   GTK_TREE_MODEL (drag_source),
1655                                   path))
1656     {
1657       return TRUE;
1658     }
1659   else
1660     {
1661       /* FIXME handle text targets at least. */
1662     }
1663
1664   return FALSE;
1665 }
1666
1667 static void
1668 copy_node_data (GtkTreeStore *tree_store,
1669                 GtkTreeIter  *src_iter,
1670                 GtkTreeIter  *dest_iter)
1671 {
1672   GtkTreeDataList *dl = G_NODE (src_iter->user_data)->data;
1673   GtkTreeDataList *copy_head = NULL;
1674   GtkTreeDataList *copy_prev = NULL;
1675   GtkTreeDataList *copy_iter = NULL;
1676   GtkTreePath *path;
1677   gint col;
1678
1679   col = 0;
1680   while (dl)
1681     {
1682       copy_iter = _gtk_tree_data_list_node_copy (dl, tree_store->column_headers[col]);
1683
1684       if (copy_head == NULL)
1685         copy_head = copy_iter;
1686
1687       if (copy_prev)
1688         copy_prev->next = copy_iter;
1689
1690       copy_prev = copy_iter;
1691
1692       dl = dl->next;
1693       ++col;
1694     }
1695
1696   G_NODE (dest_iter->user_data)->data = copy_head;
1697
1698   path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), dest_iter);
1699   gtk_tree_model_row_changed (GTK_TREE_MODEL (tree_store), path, dest_iter);
1700   gtk_tree_path_free (path);
1701 }
1702
1703 static void
1704 recursive_node_copy (GtkTreeStore *tree_store,
1705                      GtkTreeIter  *src_iter,
1706                      GtkTreeIter  *dest_iter)
1707 {
1708   GtkTreeIter child;
1709   GtkTreeModel *model;
1710
1711   model = GTK_TREE_MODEL (tree_store);
1712
1713   copy_node_data (tree_store, src_iter, dest_iter);
1714
1715   if (gtk_tree_model_iter_children (model,
1716                                     &child,
1717                                     src_iter))
1718     {
1719       /* Need to create children and recurse. Note our
1720        * dependence on persistent iterators here.
1721        */
1722       do
1723         {
1724           GtkTreeIter copy;
1725
1726           /* Gee, a really slow algorithm... ;-) FIXME */
1727           gtk_tree_store_append (tree_store,
1728                                  &copy,
1729                                  dest_iter);
1730
1731           recursive_node_copy (tree_store, &child, &copy);
1732         }
1733       while (gtk_tree_model_iter_next (model, &child));
1734     }
1735 }
1736
1737 static gboolean
1738 gtk_tree_store_drag_data_received (GtkTreeDragDest   *drag_dest,
1739                                    GtkTreePath       *dest,
1740                                    GtkSelectionData  *selection_data)
1741 {
1742   GtkTreeModel *tree_model;
1743   GtkTreeStore *tree_store;
1744   GtkTreeModel *src_model = NULL;
1745   GtkTreePath *src_path = NULL;
1746   gboolean retval = FALSE;
1747
1748   g_return_val_if_fail (GTK_IS_TREE_STORE (drag_dest), FALSE);
1749
1750   tree_model = GTK_TREE_MODEL (drag_dest);
1751   tree_store = GTK_TREE_STORE (drag_dest);
1752
1753   validate_tree (tree_store);
1754
1755   if (gtk_tree_get_row_drag_data (selection_data,
1756                                   &src_model,
1757                                   &src_path) &&
1758       src_model == tree_model)
1759     {
1760       /* Copy the given row to a new position */
1761       GtkTreeIter src_iter;
1762       GtkTreeIter dest_iter;
1763       GtkTreePath *prev;
1764
1765       if (!gtk_tree_model_get_iter (src_model,
1766                                     &src_iter,
1767                                     src_path))
1768         {
1769           goto out;
1770         }
1771
1772       /* Get the path to insert _after_ (dest is the path to insert _before_) */
1773       prev = gtk_tree_path_copy (dest);
1774
1775       if (!gtk_tree_path_prev (prev))
1776         {
1777           GtkTreeIter dest_parent;
1778           GtkTreePath *parent;
1779           GtkTreeIter *dest_parent_p;
1780
1781           /* dest was the first spot at the current depth; which means
1782            * we are supposed to prepend.
1783            */
1784
1785           /* Get the parent, NULL if parent is the root */
1786           dest_parent_p = NULL;
1787           parent = gtk_tree_path_copy (dest);
1788           if (gtk_tree_path_up (parent) &&
1789               gtk_tree_path_get_depth (parent) > 0)
1790             {
1791               gtk_tree_model_get_iter (tree_model,
1792                                        &dest_parent,
1793                                        parent);
1794               dest_parent_p = &dest_parent;
1795             }
1796           gtk_tree_path_free (parent);
1797           parent = NULL;
1798
1799           gtk_tree_store_prepend (tree_store,
1800                                   &dest_iter,
1801                                   dest_parent_p);
1802
1803           retval = TRUE;
1804         }
1805       else
1806         {
1807           if (gtk_tree_model_get_iter (tree_model, &dest_iter, prev))
1808             {
1809               GtkTreeIter tmp_iter = dest_iter;
1810
1811               gtk_tree_store_insert_after (tree_store, &dest_iter, NULL,
1812                                            &tmp_iter);
1813
1814               retval = TRUE;
1815             }
1816         }
1817
1818       gtk_tree_path_free (prev);
1819
1820       /* If we succeeded in creating dest_iter, walk src_iter tree branch,
1821        * duplicating it below dest_iter.
1822        */
1823
1824       if (retval)
1825         {
1826           recursive_node_copy (tree_store,
1827                                &src_iter,
1828                                &dest_iter);
1829         }
1830     }
1831   else
1832     {
1833       /* FIXME maybe add some data targets eventually, or handle text
1834        * targets in the simple case.
1835        */
1836
1837     }
1838
1839  out:
1840
1841   if (src_path)
1842     gtk_tree_path_free (src_path);
1843
1844   return retval;
1845 }
1846
1847 static gboolean
1848 gtk_tree_store_row_drop_possible (GtkTreeDragDest  *drag_dest,
1849                                   GtkTreePath      *dest_path,
1850                                   GtkSelectionData *selection_data)
1851 {
1852   GtkTreeModel *src_model = NULL;
1853   GtkTreePath *src_path = NULL;
1854   GtkTreePath *tmp = NULL;
1855   gboolean retval = FALSE;
1856
1857   g_return_val_if_fail (GTK_IS_TREE_STORE (drag_dest), FALSE);
1858
1859   /* don't accept drops if the tree has been sorted */
1860   if (GTK_TREE_STORE_IS_SORTED (drag_dest))
1861     return FALSE;
1862
1863   if (!gtk_tree_get_row_drag_data (selection_data,
1864                                    &src_model,
1865                                    &src_path))
1866     goto out;
1867
1868   /* can only drag to ourselves */
1869   if (src_model != GTK_TREE_MODEL (drag_dest))
1870     goto out;
1871
1872   /* Can't drop into ourself. */
1873   if (gtk_tree_path_is_ancestor (src_path,
1874                                  dest_path))
1875     goto out;
1876
1877   /* Can't drop if dest_path's parent doesn't exist */
1878   {
1879     GtkTreeIter iter;
1880
1881     if (gtk_tree_path_get_depth (dest_path) > 1)
1882       {
1883         tmp = gtk_tree_path_copy (dest_path);
1884         gtk_tree_path_up (tmp);
1885
1886         if (!gtk_tree_model_get_iter (GTK_TREE_MODEL (drag_dest),
1887                                       &iter, tmp))
1888           goto out;
1889       }
1890   }
1891
1892   /* Can otherwise drop anywhere. */
1893   retval = TRUE;
1894
1895  out:
1896
1897   if (src_path)
1898     gtk_tree_path_free (src_path);
1899   if (tmp)
1900     gtk_tree_path_free (tmp);
1901
1902   return retval;
1903 }
1904
1905 /* Sorting and reordering */
1906 typedef struct _SortTuple
1907 {
1908   gint offset;
1909   GNode *node;
1910 } SortTuple;
1911
1912 /* Reordering */
1913 static gint
1914 gtk_tree_store_reorder_func (gconstpointer a,
1915                              gconstpointer b,
1916                              gpointer      user_data)
1917 {
1918   SortTuple *a_reorder;
1919   SortTuple *b_reorder;
1920
1921   a_reorder = (SortTuple *)a;
1922   b_reorder = (SortTuple *)b;
1923
1924   if (a_reorder->offset < b_reorder->offset)
1925     return -1;
1926   if (a_reorder->offset > b_reorder->offset)
1927     return 1;
1928
1929   return 0;
1930 }
1931
1932 /**
1933  * gtk_tree_store_reorder:
1934  * @tree_store: A #GtkTreeStore.
1935  * @parent: A #GtkTreeIter.
1936  * @new_order: an array of integers mapping the new position of each child
1937  *      to its old position before the re-ordering,
1938  *      i.e. @new_order<literal>[newpos] = oldpos</literal>.
1939  *
1940  * Reorders the children of @parent in @tree_store to follow the order
1941  * indicated by @new_order. Note that this function only works with
1942  * unsorted stores.
1943  *
1944  * Since: 2.2
1945  **/
1946 void
1947 gtk_tree_store_reorder (GtkTreeStore *tree_store,
1948                         GtkTreeIter  *parent,
1949                         gint         *new_order)
1950 {
1951   gint i, length = 0;
1952   GNode *level, *node;
1953   GtkTreePath *path;
1954   SortTuple *sort_array;
1955
1956   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
1957   g_return_if_fail (!GTK_TREE_STORE_IS_SORTED (tree_store));
1958   g_return_if_fail (parent == NULL || VALID_ITER (parent, tree_store));
1959   g_return_if_fail (new_order != NULL);
1960
1961   if (!parent)
1962     level = G_NODE (tree_store->root)->children;
1963   else
1964     level = G_NODE (parent->user_data)->children;
1965
1966   /* count nodes */
1967   node = level;
1968   while (node)
1969     {
1970       length++;
1971       node = node->next;
1972     }
1973
1974   /* set up sortarray */
1975   sort_array = g_new (SortTuple, length);
1976
1977   node = level;
1978   for (i = 0; i < length; i++)
1979     {
1980       sort_array[new_order[i]].offset = i;
1981       sort_array[i].node = node;
1982
1983       node = node->next;
1984     }
1985
1986   g_qsort_with_data (sort_array,
1987                      length,
1988                      sizeof (SortTuple),
1989                      gtk_tree_store_reorder_func,
1990                      NULL);
1991
1992   /* fix up level */
1993   for (i = 0; i < length - 1; i++)
1994     {
1995       sort_array[i].node->next = sort_array[i+1].node;
1996       sort_array[i+1].node->prev = sort_array[i].node;
1997     }
1998
1999   sort_array[length-1].node->next = NULL;
2000   sort_array[0].node->prev = NULL;
2001   if (parent)
2002     G_NODE (parent->user_data)->children = sort_array[0].node;
2003   else
2004     G_NODE (tree_store->root)->children = sort_array[0].node;
2005
2006   /* emit signal */
2007   if (parent)
2008     path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_store), parent);
2009   else
2010     path = gtk_tree_path_new ();
2011   gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store), path,
2012                                  parent, new_order);
2013   gtk_tree_path_free (path);
2014   g_free (sort_array);
2015 }
2016
2017 /**
2018  * gtk_tree_store_swap:
2019  * @tree_store: A #GtkTreeStore.
2020  * @a: A #GtkTreeIter.
2021  * @b: Another #GtkTreeIter.
2022  *
2023  * Swaps @a and @b in the same level of @tree_store. Note that this function
2024  * only works with unsorted stores.
2025  *
2026  * Since: 2.2
2027  **/
2028 void
2029 gtk_tree_store_swap (GtkTreeStore *tree_store,
2030                      GtkTreeIter  *a,
2031                      GtkTreeIter  *b)
2032 {
2033   GNode *tmp, *node_a, *node_b, *parent_node;
2034   GNode *a_prev, *a_next, *b_prev, *b_next;
2035   gint i, a_count, b_count, length, *order;
2036   GtkTreePath *path_a, *path_b;
2037   GtkTreeIter parent;
2038
2039   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
2040   g_return_if_fail (VALID_ITER (a, tree_store));
2041   g_return_if_fail (VALID_ITER (b, tree_store));
2042
2043   node_a = G_NODE (a->user_data);
2044   node_b = G_NODE (b->user_data);
2045
2046   /* basic sanity checking */
2047   if (node_a == node_b)
2048     return;
2049
2050   path_a = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_store), a);
2051   path_b = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_store), b);
2052
2053   g_return_if_fail (path_a && path_b);
2054
2055   gtk_tree_path_up (path_a);
2056   gtk_tree_path_up (path_b);
2057
2058   if (gtk_tree_path_get_depth (path_a) == 0
2059       || gtk_tree_path_get_depth (path_b) == 0)
2060     {
2061       if (gtk_tree_path_get_depth (path_a) != gtk_tree_path_get_depth (path_b))
2062         {
2063           gtk_tree_path_free (path_a);
2064           gtk_tree_path_free (path_b);
2065
2066           g_warning ("Given children are not in the same level\n");
2067           return;
2068         }
2069       parent_node = G_NODE (tree_store->root);
2070     }
2071   else
2072     {
2073       if (gtk_tree_path_compare (path_a, path_b))
2074         {
2075           gtk_tree_path_free (path_a);
2076           gtk_tree_path_free (path_b);
2077
2078           g_warning ("Given children don't have a common parent\n");
2079           return;
2080         }
2081       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_store), &parent,
2082                                path_a);
2083       parent_node = G_NODE (parent.user_data);
2084     }
2085   gtk_tree_path_free (path_b);
2086
2087   /* old links which we have to keep around */
2088   a_prev = node_a->prev;
2089   a_next = node_a->next;
2090
2091   b_prev = node_b->prev;
2092   b_next = node_b->next;
2093
2094   /* fix up links if the nodes are next to eachother */
2095   if (a_prev == node_b)
2096     a_prev = node_a;
2097   if (a_next == node_b)
2098     a_next = node_a;
2099
2100   if (b_prev == node_a)
2101     b_prev = node_b;
2102   if (b_next == node_a)
2103     b_next = node_b;
2104
2105   /* counting nodes */
2106   tmp = parent_node->children;
2107   i = a_count = b_count = 0;
2108   while (tmp)
2109     {
2110       if (tmp == node_a)
2111         a_count = i;
2112       if (tmp == node_b)
2113         b_count = i;
2114
2115       tmp = tmp->next;
2116       i++;
2117     }
2118   length = i;
2119
2120   /* hacking the tree */
2121   if (!a_prev)
2122     parent_node->children = node_b;
2123   else
2124     a_prev->next = node_b;
2125
2126   if (a_next)
2127     a_next->prev = node_b;
2128
2129   if (!b_prev)
2130     parent_node->children = node_a;
2131   else
2132     b_prev->next = node_a;
2133
2134   if (b_next)
2135     b_next->prev = node_a;
2136
2137   node_a->prev = b_prev;
2138   node_a->next = b_next;
2139
2140   node_b->prev = a_prev;
2141   node_b->next = a_next;
2142
2143   /* emit signal */
2144   order = g_new (gint, length);
2145   for (i = 0; i < length; i++)
2146     if (i == a_count)
2147       order[i] = b_count;
2148     else if (i == b_count)
2149       order[i] = a_count;
2150     else
2151       order[i] = i;
2152
2153   gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store), path_a,
2154                                  parent_node == tree_store->root
2155                                  ? NULL : &parent, order);
2156   gtk_tree_path_free (path_a);
2157   g_free (order);
2158 }
2159
2160 /* WARNING: this function is *incredibly* fragile. Please smashtest after
2161  * making changes here.
2162  *      -Kris
2163  */
2164 static void
2165 gtk_tree_store_move (GtkTreeStore *tree_store,
2166                      GtkTreeIter  *iter,
2167                      GtkTreeIter  *position,
2168                      gboolean      before)
2169 {
2170   GNode *parent, *node, *a, *b, *tmp, *tmp_a, *tmp_b;
2171   gint old_pos, new_pos, length, i, *order;
2172   GtkTreePath *path = NULL, *tmppath, *pos_path = NULL;
2173   GtkTreeIter parent_iter, dst_a, dst_b;
2174   gint depth = 0;
2175   gboolean handle_b = TRUE;
2176
2177   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
2178   g_return_if_fail (!GTK_TREE_STORE_IS_SORTED (tree_store));
2179   g_return_if_fail (VALID_ITER (iter, tree_store));
2180   if (position)
2181     g_return_if_fail (VALID_ITER (position, tree_store));
2182
2183   a = b = NULL;
2184
2185   /* sanity checks */
2186   if (position)
2187     {
2188       path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_store), iter);
2189       pos_path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_store),
2190                                           position);
2191
2192       /* if before:
2193        *   moving the iter before path or "path + 1" doesn't make sense
2194        * else
2195        *   moving the iter before path or "path - 1" doesn't make sense
2196        */
2197       if (!gtk_tree_path_compare (path, pos_path))
2198         goto free_paths_and_out;
2199
2200       if (before)
2201         gtk_tree_path_next (path);
2202       else
2203         gtk_tree_path_prev (path);
2204
2205       if (!gtk_tree_path_compare (path, pos_path))
2206         goto free_paths_and_out;
2207
2208       if (before)
2209         gtk_tree_path_prev (path);
2210       else
2211         gtk_tree_path_next (path);
2212
2213       if (gtk_tree_path_get_depth (path) != gtk_tree_path_get_depth (pos_path))
2214         {
2215           g_warning ("Given children are not in the same level\n");
2216
2217           goto free_paths_and_out;
2218         }
2219
2220       tmppath = gtk_tree_path_copy (pos_path);
2221       gtk_tree_path_up (path);
2222       gtk_tree_path_up (tmppath);
2223
2224       if (gtk_tree_path_get_depth (path) > 0 &&
2225           gtk_tree_path_compare (path, tmppath))
2226         {
2227           g_warning ("Given children are not in the same level\n");
2228
2229           gtk_tree_path_free (tmppath);
2230           goto free_paths_and_out;
2231         }
2232
2233       gtk_tree_path_free (tmppath);
2234     }
2235
2236   if (!path)
2237     {
2238       path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_store), iter);
2239       gtk_tree_path_up (path);
2240     }
2241
2242   depth = gtk_tree_path_get_depth (path);
2243
2244   if (depth)
2245     {
2246       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_store), &parent_iter, path);
2247       gtk_tree_path_free (path);
2248
2249       parent = G_NODE (parent_iter.user_data);
2250     }
2251   else
2252     parent = G_NODE (tree_store->root);
2253
2254   /* yes, I know that this can be done shorter, but I'm doing it this way
2255    * so the code is also maintainable
2256    */
2257
2258   if (before && position)
2259     {
2260       b = G_NODE (position->user_data);
2261
2262       if (gtk_tree_path_get_indices (pos_path)[gtk_tree_path_get_depth (pos_path) - 1] > 0)
2263         {
2264           gtk_tree_path_prev (pos_path);
2265           if (gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_store), &dst_a, pos_path))
2266             a = G_NODE (dst_a.user_data);
2267           else
2268             a = NULL;
2269           gtk_tree_path_next (pos_path);
2270         }
2271
2272       /* if b is NULL, a is NULL too -- we are at the beginning of the list
2273        * yes and we leak memory here ...
2274        */
2275       g_return_if_fail (b);
2276     }
2277   else if (before && !position)
2278     {
2279       /* move before without position is appending */
2280       a = NULL;
2281       b = NULL;
2282     }
2283   else /* !before */
2284     {
2285       if (position)
2286         a = G_NODE (position->user_data);
2287       else
2288         a = NULL;
2289
2290       if (position)
2291         {
2292           gtk_tree_path_next (pos_path);
2293           if (gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_store), &dst_b, pos_path))
2294              b = G_NODE (dst_b.user_data);
2295           else
2296              b = NULL;
2297           gtk_tree_path_prev (pos_path);
2298         }
2299       else
2300         {
2301           /* move after without position is prepending */
2302           if (depth)
2303             gtk_tree_model_iter_children (GTK_TREE_MODEL (tree_store), &dst_b,
2304                                           &parent_iter);
2305           else
2306             gtk_tree_model_iter_children (GTK_TREE_MODEL (tree_store), &dst_b,
2307                                           NULL);
2308
2309           b = G_NODE (dst_b.user_data);
2310         }
2311
2312       /* if a is NULL, a is NULL too -- we are at the end of the list
2313        * yes and we leak memory here ...
2314        */
2315       if (position)
2316         g_return_if_fail (a);
2317     }
2318
2319   /* counting nodes */
2320   tmp = parent->children;
2321
2322   length = old_pos = 0;
2323   while (tmp)
2324     {
2325       if (tmp == iter->user_data)
2326         old_pos = length;
2327
2328       tmp = tmp->next;
2329       length++;
2330     }
2331
2332   /* remove node from list */
2333   node = G_NODE (iter->user_data);
2334   tmp_a = node->prev;
2335   tmp_b = node->next;
2336
2337   if (tmp_a)
2338     tmp_a->next = tmp_b;
2339   else
2340     parent->children = tmp_b;
2341
2342   if (tmp_b)
2343     tmp_b->prev = tmp_a;
2344
2345   /* and reinsert the node */
2346   if (a)
2347     {
2348       tmp = a->next;
2349
2350       a->next = node;
2351       node->next = tmp;
2352       node->prev = a;
2353     }
2354   else if (!a && !before)
2355     {
2356       tmp = parent->children;
2357
2358       node->prev = NULL;
2359       parent->children = node;
2360
2361       node->next = tmp;
2362       if (tmp)
2363         tmp->prev = node;
2364
2365       handle_b = FALSE;
2366     }
2367   else if (!a && before)
2368     {
2369       if (!position)
2370         {
2371           node->parent = NULL;
2372           node->next = node->prev = NULL;
2373
2374           /* before with sibling = NULL appends */
2375           g_node_insert_before (parent, NULL, node);
2376         }
2377       else
2378         {
2379           node->parent = NULL;
2380           node->next = node->prev = NULL;
2381
2382           /* after with sibling = NULL prepends */
2383           g_node_insert_after (parent, NULL, node);
2384         }
2385
2386       handle_b = FALSE;
2387     }
2388
2389   if (handle_b)
2390     {
2391       if (b)
2392         {
2393           tmp = b->prev;
2394
2395           b->prev = node;
2396           node->prev = tmp;
2397           node->next = b;
2398         }
2399       else if (!(!a && before)) /* !a && before is completely handled above */
2400         node->next = NULL;
2401     }
2402
2403   /* emit signal */
2404   if (position)
2405     new_pos = gtk_tree_path_get_indices (pos_path)[gtk_tree_path_get_depth (pos_path)-1];
2406   else if (before)
2407     {
2408       if (depth)
2409         new_pos = gtk_tree_model_iter_n_children (GTK_TREE_MODEL (tree_store),
2410                                                   &parent_iter) - 1;
2411       else
2412         new_pos = gtk_tree_model_iter_n_children (GTK_TREE_MODEL (tree_store),
2413                                                   NULL) - 1;
2414     }
2415   else
2416     new_pos = 0;
2417
2418   if (new_pos > old_pos)
2419     {
2420       if (before && position)
2421         new_pos--;
2422     }
2423   else
2424     {
2425       if (!before && position)
2426         new_pos++;
2427     }
2428
2429   order = g_new (gint, length);
2430   if (new_pos > old_pos)
2431     {
2432       for (i = 0; i < length; i++)
2433         if (i < old_pos)
2434           order[i] = i;
2435         else if (i >= old_pos && i < new_pos)
2436           order[i] = i + 1;
2437         else if (i == new_pos)
2438           order[i] = old_pos;
2439         else
2440           order[i] = i;
2441     }
2442   else
2443     {
2444       for (i = 0; i < length; i++)
2445         if (i == new_pos)
2446           order[i] = old_pos;
2447         else if (i > new_pos && i <= old_pos)
2448           order[i] = i - 1;
2449         else
2450           order[i] = i;
2451     }
2452
2453   if (depth)
2454     {
2455       path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_store), &parent_iter);
2456       gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
2457                                      path, &parent_iter, order);
2458     }
2459   else
2460     {
2461       path = gtk_tree_path_new ();
2462       gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
2463                                      path, NULL, order);
2464     }
2465
2466   gtk_tree_path_free (path);
2467   if (position)
2468     gtk_tree_path_free (pos_path);
2469   g_free (order);
2470
2471   return;
2472
2473 free_paths_and_out:
2474   gtk_tree_path_free (path);
2475   gtk_tree_path_free (pos_path);
2476 }
2477
2478 /**
2479  * gtk_tree_store_move_before:
2480  * @tree_store: A #GtkTreeStore.
2481  * @iter: A #GtkTreeIter.
2482  * @position: A #GtkTreeIter or %NULL.
2483  *
2484  * Moves @iter in @tree_store to the position before @position. @iter and
2485  * @position should be in the same level. Note that this function only
2486  * works with unsorted stores. If @position is %NULL, @iter will be
2487  * moved to the end of the level.
2488  *
2489  * Since: 2.2
2490  **/
2491 void
2492 gtk_tree_store_move_before (GtkTreeStore *tree_store,
2493                             GtkTreeIter  *iter,
2494                             GtkTreeIter  *position)
2495 {
2496   gtk_tree_store_move (tree_store, iter, position, TRUE);
2497 }
2498
2499 /**
2500  * gtk_tree_store_move_after:
2501  * @tree_store: A #GtkTreeStore.
2502  * @iter: A #GtkTreeIter.
2503  * @position: A #GtkTreeIter.
2504  *
2505  * Moves @iter in @tree_store to the position after @position. @iter and
2506  * @position should be in the same level. Note that this function only
2507  * works with unsorted stores. If @position is %NULL, @iter will be moved
2508  * to the start of the level.
2509  *
2510  * Since: 2.2
2511  **/
2512 void
2513 gtk_tree_store_move_after (GtkTreeStore *tree_store,
2514                            GtkTreeIter  *iter,
2515                            GtkTreeIter  *position)
2516 {
2517   gtk_tree_store_move (tree_store, iter, position, FALSE);
2518 }
2519
2520 /* Sorting */
2521 static gint
2522 gtk_tree_store_compare_func (gconstpointer a,
2523                              gconstpointer b,
2524                              gpointer      user_data)
2525 {
2526   GtkTreeStore *tree_store = user_data;
2527   GNode *node_a;
2528   GNode *node_b;
2529   GtkTreeIterCompareFunc func;
2530   gpointer data;
2531
2532   GtkTreeIter iter_a;
2533   GtkTreeIter iter_b;
2534   gint retval;
2535
2536   if (tree_store->sort_column_id != -1)
2537     {
2538       GtkTreeDataSortHeader *header;
2539
2540       header = _gtk_tree_data_list_get_header (tree_store->sort_list,
2541                                                tree_store->sort_column_id);
2542       g_return_val_if_fail (header != NULL, 0);
2543       g_return_val_if_fail (header->func != NULL, 0);
2544
2545       func = header->func;
2546       data = header->data;
2547     }
2548   else
2549     {
2550       g_return_val_if_fail (tree_store->default_sort_func != NULL, 0);
2551       func = tree_store->default_sort_func;
2552       data = tree_store->default_sort_data;
2553     }
2554
2555   node_a = ((SortTuple *) a)->node;
2556   node_b = ((SortTuple *) b)->node;
2557
2558   iter_a.stamp = tree_store->stamp;
2559   iter_a.user_data = node_a;
2560   iter_b.stamp = tree_store->stamp;
2561   iter_b.user_data = node_b;
2562
2563   retval = (* func) (GTK_TREE_MODEL (user_data), &iter_a, &iter_b, data);
2564
2565   if (tree_store->order == GTK_SORT_DESCENDING)
2566     {
2567       if (retval > 0)
2568         retval = -1;
2569       else if (retval < 0)
2570         retval = 1;
2571     }
2572   return retval;
2573 }
2574
2575 static void
2576 gtk_tree_store_sort_helper (GtkTreeStore *tree_store,
2577                             GNode        *parent,
2578                             gboolean      recurse)
2579 {
2580   GtkTreeIter iter;
2581   GArray *sort_array;
2582   GNode *node;
2583   GNode *tmp_node;
2584   gint list_length;
2585   gint i;
2586   gint *new_order;
2587   GtkTreePath *path;
2588
2589   node = parent->children;
2590   if (node == NULL || node->next == NULL)
2591     {
2592       if (recurse && node && node->children)
2593         gtk_tree_store_sort_helper (tree_store, node, TRUE);
2594
2595       return;
2596     }
2597
2598   list_length = 0;
2599   for (tmp_node = node; tmp_node; tmp_node = tmp_node->next)
2600     list_length++;
2601
2602   sort_array = g_array_sized_new (FALSE, FALSE, sizeof (SortTuple), list_length);
2603
2604   i = 0;
2605   for (tmp_node = node; tmp_node; tmp_node = tmp_node->next)
2606     {
2607       SortTuple tuple;
2608
2609       tuple.offset = i;
2610       tuple.node = tmp_node;
2611       g_array_append_val (sort_array, tuple);
2612       i++;
2613     }
2614
2615   /* Sort the array */
2616   g_array_sort_with_data (sort_array, gtk_tree_store_compare_func, tree_store);
2617
2618   for (i = 0; i < list_length - 1; i++)
2619     {
2620       g_array_index (sort_array, SortTuple, i).node->next =
2621         g_array_index (sort_array, SortTuple, i + 1).node;
2622       g_array_index (sort_array, SortTuple, i + 1).node->prev =
2623         g_array_index (sort_array, SortTuple, i).node;
2624     }
2625   g_array_index (sort_array, SortTuple, list_length - 1).node->next = NULL;
2626   g_array_index (sort_array, SortTuple, 0).node->prev = NULL;
2627   parent->children = g_array_index (sort_array, SortTuple, 0).node;
2628
2629   /* Let the world know about our new order */
2630   new_order = g_new (gint, list_length);
2631   for (i = 0; i < list_length; i++)
2632     new_order[i] = g_array_index (sort_array, SortTuple, i).offset;
2633
2634   iter.stamp = tree_store->stamp;
2635   iter.user_data = parent;
2636   path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), &iter);
2637   gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
2638                                  path, &iter, new_order);
2639   gtk_tree_path_free (path);
2640   g_free (new_order);
2641   g_array_free (sort_array, TRUE);
2642
2643   if (recurse)
2644     {
2645       for (tmp_node = parent->children; tmp_node; tmp_node = tmp_node->next)
2646         {
2647           if (tmp_node->children)
2648             gtk_tree_store_sort_helper (tree_store, tmp_node, TRUE);
2649         }
2650     }
2651 }
2652
2653 static void
2654 gtk_tree_store_sort (GtkTreeStore *tree_store)
2655 {
2656   if (!GTK_TREE_STORE_IS_SORTED (tree_store))
2657     return;
2658
2659   if (tree_store->sort_column_id != -1)
2660     {
2661       GtkTreeDataSortHeader *header = NULL;
2662
2663       header = _gtk_tree_data_list_get_header (tree_store->sort_list, tree_store->sort_column_id);
2664
2665       /* We want to make sure that we have a function */
2666       g_return_if_fail (header != NULL);
2667       g_return_if_fail (header->func != NULL);
2668     }
2669   else
2670     {
2671       g_return_if_fail (tree_store->default_sort_func != NULL);
2672     }
2673
2674   gtk_tree_store_sort_helper (tree_store, G_NODE (tree_store->root), TRUE);
2675 }
2676
2677 static void
2678 gtk_tree_store_sort_iter_changed (GtkTreeStore *tree_store,
2679                                   GtkTreeIter  *iter,
2680                                   gint          column)
2681 {
2682   GNode *prev = NULL;
2683   GNode *next = NULL;
2684   GNode *node;
2685   GtkTreePath *tmp_path;
2686   GtkTreeIter tmp_iter;
2687   gint cmp_a = 0;
2688   gint cmp_b = 0;
2689   gint i;
2690   gint old_location;
2691   gint new_location;
2692   gint *new_order;
2693   gint length;
2694   GtkTreeIterCompareFunc func;
2695   gpointer data;
2696
2697   g_return_if_fail (G_NODE (iter->user_data)->parent != NULL);
2698
2699   tmp_iter.stamp = tree_store->stamp;
2700   if (tree_store->sort_column_id != -1)
2701     {
2702       GtkTreeDataSortHeader *header;
2703       header = _gtk_tree_data_list_get_header (tree_store->sort_list,
2704                                                tree_store->sort_column_id);
2705       g_return_if_fail (header != NULL);
2706       g_return_if_fail (header->func != NULL);
2707       func = header->func;
2708       data = header->data;
2709     }
2710   else
2711     {
2712       g_return_if_fail (tree_store->default_sort_func != NULL);
2713       func = tree_store->default_sort_func;
2714       data = tree_store->default_sort_data;
2715     }
2716
2717   /* If it's the built in function, we don't sort. */
2718   if (func == _gtk_tree_data_list_compare_func &&
2719       tree_store->sort_column_id != column)
2720     return;
2721
2722   old_location = 0;
2723   node = G_NODE (iter->user_data)->parent->children;
2724   /* First we find the iter, its prev, and its next */
2725   while (node)
2726     {
2727       if (node == G_NODE (iter->user_data))
2728         break;
2729       old_location++;
2730       node = node->next;
2731     }
2732   g_assert (node != NULL);
2733
2734   prev = node->prev;
2735   next = node->next;
2736
2737   /* Check the common case, where we don't need to sort it moved. */
2738   if (prev != NULL)
2739     {
2740       tmp_iter.user_data = prev;
2741       cmp_a = (* func) (GTK_TREE_MODEL (tree_store), &tmp_iter, iter, data);
2742     }
2743
2744   if (next != NULL)
2745     {
2746       tmp_iter.user_data = next;
2747       cmp_b = (* func) (GTK_TREE_MODEL (tree_store), iter, &tmp_iter, data);
2748     }
2749
2750   if (tree_store->order == GTK_SORT_DESCENDING)
2751     {
2752       if (cmp_a < 0)
2753         cmp_a = 1;
2754       else if (cmp_a > 0)
2755         cmp_a = -1;
2756
2757       if (cmp_b < 0)
2758         cmp_b = 1;
2759       else if (cmp_b > 0)
2760         cmp_b = -1;
2761     }
2762
2763   if (prev == NULL && cmp_b <= 0)
2764     return;
2765   else if (next == NULL && cmp_a <= 0)
2766     return;
2767   else if (prev != NULL && next != NULL &&
2768            cmp_a <= 0 && cmp_b <= 0)
2769     return;
2770
2771   /* We actually need to sort it */
2772   /* First, remove the old link. */
2773
2774   if (prev)
2775     prev->next = next;
2776   else
2777     node->parent->children = next;
2778
2779   if (next)
2780     next->prev = prev;
2781
2782   node->prev = NULL;
2783   node->next = NULL;
2784
2785   /* FIXME: as an optimization, we can potentially start at next */
2786   prev = NULL;
2787   node = node->parent->children;
2788   new_location = 0;
2789   tmp_iter.user_data = node;
2790   if (tree_store->order == GTK_SORT_DESCENDING)
2791     cmp_a = (* func) (GTK_TREE_MODEL (tree_store), &tmp_iter, iter, data);
2792   else
2793     cmp_a = (* func) (GTK_TREE_MODEL (tree_store), iter, &tmp_iter, data);
2794
2795   while ((node->next) && (cmp_a > 0))
2796     {
2797       prev = node;
2798       node = node->next;
2799       new_location++;
2800       tmp_iter.user_data = node;
2801       if (tree_store->order == GTK_SORT_DESCENDING)
2802         cmp_a = (* func) (GTK_TREE_MODEL (tree_store), &tmp_iter, iter, data);
2803       else
2804         cmp_a = (* func) (GTK_TREE_MODEL (tree_store), iter, &tmp_iter, data);
2805     }
2806
2807   if ((!node->next) && (cmp_a > 0))
2808     {
2809       new_location++;
2810       node->next = G_NODE (iter->user_data);
2811       node->next->prev = node;
2812     }
2813   else if (prev)
2814     {
2815       prev->next = G_NODE (iter->user_data);
2816       prev->next->prev = prev;
2817       G_NODE (iter->user_data)->next = node;
2818       G_NODE (iter->user_data)->next->prev = G_NODE (iter->user_data);
2819     }
2820   else
2821     {
2822       G_NODE (iter->user_data)->next = G_NODE (iter->user_data)->parent->children;
2823       G_NODE (iter->user_data)->next->prev = G_NODE (iter->user_data);
2824       G_NODE (iter->user_data)->parent->children = G_NODE (iter->user_data);
2825     }
2826
2827   /* Emit the reordered signal. */
2828   length = g_node_n_children (node->parent);
2829   new_order = g_new (int, length);
2830   if (old_location < new_location)
2831     for (i = 0; i < length; i++)
2832       {
2833         if (i < old_location ||
2834             i > new_location)
2835           new_order[i] = i;
2836         else if (i >= old_location &&
2837                  i < new_location)
2838           new_order[i] = i + 1;
2839         else if (i == new_location)
2840           new_order[i] = old_location;
2841       }
2842   else
2843     for (i = 0; i < length; i++)
2844       {
2845         if (i < new_location ||
2846             i > old_location)
2847           new_order[i] = i;
2848         else if (i > new_location &&
2849                  i <= old_location)
2850           new_order[i] = i - 1;
2851         else if (i == new_location)
2852           new_order[i] = old_location;
2853       }
2854
2855   tmp_iter.user_data = node->parent;
2856   tmp_path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), &tmp_iter);
2857
2858   gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
2859                                  tmp_path, &tmp_iter,
2860                                  new_order);
2861
2862   gtk_tree_path_free (tmp_path);
2863   g_free (new_order);
2864 }
2865
2866
2867 static gboolean
2868 gtk_tree_store_get_sort_column_id (GtkTreeSortable  *sortable,
2869                                    gint             *sort_column_id,
2870                                    GtkSortType      *order)
2871 {
2872   GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
2873
2874   g_return_val_if_fail (GTK_IS_TREE_STORE (sortable), FALSE);
2875
2876   if (sort_column_id)
2877     * sort_column_id = tree_store->sort_column_id;
2878   if (order)
2879     * order = tree_store->order;
2880
2881   if (tree_store->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID ||
2882       tree_store->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
2883     return FALSE;
2884
2885   return TRUE;
2886 }
2887
2888 static void
2889 gtk_tree_store_set_sort_column_id (GtkTreeSortable  *sortable,
2890                                    gint              sort_column_id,
2891                                    GtkSortType       order)
2892 {
2893   GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
2894
2895   g_return_if_fail (GTK_IS_TREE_STORE (sortable));
2896
2897
2898   if ((tree_store->sort_column_id == sort_column_id) &&
2899       (tree_store->order == order))
2900     return;
2901
2902   if (sort_column_id != GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
2903     {
2904       if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
2905         {
2906           GtkTreeDataSortHeader *header = NULL;
2907
2908           header = _gtk_tree_data_list_get_header (tree_store->sort_list, sort_column_id);
2909
2910           /* We want to make sure that we have a function */
2911           g_return_if_fail (header != NULL);
2912           g_return_if_fail (header->func != NULL);
2913         }
2914       else
2915         {
2916           g_return_if_fail (tree_store->default_sort_func != NULL);
2917         }
2918     }
2919
2920   tree_store->sort_column_id = sort_column_id;
2921   tree_store->order = order;
2922
2923   gtk_tree_sortable_sort_column_changed (sortable);
2924
2925   gtk_tree_store_sort (tree_store);
2926 }
2927
2928 static void
2929 gtk_tree_store_set_sort_func (GtkTreeSortable        *sortable,
2930                               gint                    sort_column_id,
2931                               GtkTreeIterCompareFunc  func,
2932                               gpointer                data,
2933                               GtkDestroyNotify        destroy)
2934 {
2935   GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
2936   GtkTreeDataSortHeader *header = NULL;
2937   GList *list;
2938
2939   g_return_if_fail (GTK_IS_TREE_STORE (sortable));
2940   g_return_if_fail (func != NULL);
2941
2942   for (list = tree_store->sort_list; list; list = list->next)
2943     {
2944       GtkTreeDataSortHeader *list_header;
2945
2946       list_header = (GtkTreeDataSortHeader*) list->data;
2947       if (list_header->sort_column_id == sort_column_id)
2948         {
2949           header = list_header;
2950           break;
2951         }
2952     }
2953
2954   if (header == NULL)
2955     {
2956       header = g_new0 (GtkTreeDataSortHeader, 1);
2957       header->sort_column_id = sort_column_id;
2958       tree_store->sort_list = g_list_append (tree_store->sort_list, header);
2959     }
2960
2961   if (header->destroy)
2962     {
2963       GtkDestroyNotify d = header->destroy;
2964
2965       header->destroy = NULL;
2966       d (header->data);
2967     }
2968
2969   header->func = func;
2970   header->data = data;
2971   header->destroy = destroy;
2972
2973   if (tree_store->sort_column_id == sort_column_id)
2974     gtk_tree_store_sort (tree_store);
2975 }
2976
2977 static void
2978 gtk_tree_store_set_default_sort_func (GtkTreeSortable        *sortable,
2979                                       GtkTreeIterCompareFunc  func,
2980                                       gpointer                data,
2981                                       GtkDestroyNotify        destroy)
2982 {
2983   GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
2984
2985   g_return_if_fail (GTK_IS_TREE_STORE (sortable));
2986
2987   if (tree_store->default_sort_destroy)
2988     {
2989       GtkDestroyNotify d = tree_store->default_sort_destroy;
2990
2991       tree_store->default_sort_destroy = NULL;
2992       d (tree_store->default_sort_data);
2993     }
2994
2995   tree_store->default_sort_func = func;
2996   tree_store->default_sort_data = data;
2997   tree_store->default_sort_destroy = destroy;
2998
2999   if (tree_store->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
3000     gtk_tree_store_sort (tree_store);
3001 }
3002
3003 static gboolean
3004 gtk_tree_store_has_default_sort_func (GtkTreeSortable *sortable)
3005 {
3006   GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
3007
3008   g_return_val_if_fail (GTK_IS_TREE_STORE (sortable), FALSE);
3009
3010   return (tree_store->default_sort_func != NULL);
3011 }
3012
3013 static void
3014 validate_gnode (GNode* node)
3015 {
3016   GNode *iter;
3017
3018   iter = node->children;
3019   while (iter != NULL)
3020     {
3021       g_assert (iter->parent == node);
3022       if (iter->prev)
3023         g_assert (iter->prev->next == iter);
3024       validate_gnode (iter);
3025       iter = iter->next;
3026     }
3027 }
3028
3029 #define __GTK_TREE_STORE_C__
3030 #include "gtkaliasdef.c"