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