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