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

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