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