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