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