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