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