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