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