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