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