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