Pileus Git - ~andy/gtk/blob - gtk/gtktreestore.c

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