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