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

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