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