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