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 != -1)
  29
  30 static void         gtk_tree_store_init            (GtkTreeStore      *tree_store);
  31 static void         gtk_tree_store_class_init      (GtkTreeStoreClass *tree_store_class);
  32 static void         gtk_tree_store_tree_model_init (GtkTreeModelIface *iface);
  33 static void         gtk_tree_store_drag_source_init(GtkTreeDragSourceIface *iface);
  34 static void         gtk_tree_store_drag_dest_init  (GtkTreeDragDestIface   *iface);
  35 static void         gtk_tree_store_sortable_init   (GtkTreeSortableIface   *iface);
  36 static guint        gtk_tree_store_get_flags       (GtkTreeModel      *tree_model);
  37 static gint         gtk_tree_store_get_n_columns   (GtkTreeModel      *tree_model);
  38 static GType        gtk_tree_store_get_column_type (GtkTreeModel      *tree_model,
  39                                                     gint               index);
  40 static GtkTreePath *gtk_tree_store_get_path        (GtkTreeModel      *tree_model,
  41                                                     GtkTreeIter       *iter);
  42 static void         gtk_tree_store_get_value       (GtkTreeModel      *tree_model,
  43                                                     GtkTreeIter       *iter,
  44                                                     gint               column,
  45                                                     GValue            *value);
  46 static gboolean     gtk_tree_store_iter_next       (GtkTreeModel      *tree_model,
  47                                                     GtkTreeIter       *iter);
  48 static gboolean     gtk_tree_store_iter_children   (GtkTreeModel      *tree_model,
  49                                                     GtkTreeIter       *iter,
  50                                                     GtkTreeIter       *parent);
  51 static gboolean     gtk_tree_store_iter_has_child  (GtkTreeModel      *tree_model,
  52                                                     GtkTreeIter       *iter);
  53 static gint         gtk_tree_store_iter_n_children (GtkTreeModel      *tree_model,
  54                                                     GtkTreeIter       *iter);
  55 static gboolean     gtk_tree_store_iter_nth_child  (GtkTreeModel      *tree_model,
  56                                                     GtkTreeIter       *iter,
  57                                                     GtkTreeIter       *parent,
  58                                                     gint               n);
  59 static gboolean     gtk_tree_store_iter_parent     (GtkTreeModel      *tree_model,
  60                                                     GtkTreeIter       *iter,
  61                                                     GtkTreeIter       *child);
  62
  63
  64 /* DND interfaces */
  65 static gboolean gtk_tree_store_drag_data_delete   (GtkTreeDragSource *drag_source,
  66                                                    GtkTreePath       *path);
  67 static gboolean gtk_tree_store_drag_data_get      (GtkTreeDragSource *drag_source,
  68                                                    GtkTreePath       *path,
  69                                                    GtkSelectionData  *selection_data);
  70 static gboolean gtk_tree_store_drag_data_received (GtkTreeDragDest   *drag_dest,
  71                                                    GtkTreePath       *dest,
  72                                                    GtkSelectionData  *selection_data);
  73 static gboolean gtk_tree_store_row_drop_possible  (GtkTreeDragDest   *drag_dest,
  74                                                    GtkTreeModel      *src_model,
  75                                                    GtkTreePath       *src_path,
  76                                                    GtkTreePath       *dest_path);
  77
  78 /* Sortable Interfaces */
  79
  80 static void     gtk_tree_store_sort                    (GtkTreeStore           *tree_store);
  81 static void     gtk_tree_store_sort_iter_changed       (GtkTreeStore           *tree_store,
  82                                                         GtkTreeIter            *iter,
  83                                                         gint                    column);
  84 static gboolean gtk_tree_store_get_sort_column_id      (GtkTreeSortable        *sortable,
  85                                                         gint                   *sort_column_id,
  86                                                         GtkTreeSortOrder       *order);
  87 static void     gtk_tree_store_set_sort_column_id      (GtkTreeSortable        *sortable,
  88                                                         gint                    sort_column_id,
  89                                                         GtkTreeSortOrder        order);
  90 static void     gtk_tree_store_sort_column_id_set_func (GtkTreeSortable        *sortable,
  91                                                         gint                    sort_column_id,
  92                                                         GtkTreeIterCompareFunc  func,
  93                                                         gpointer                data,
  94                                                         GtkDestroyNotify        destroy);
  95
  96
  97 static void     validate_gnode                    (GNode *node);
  98
  99 static inline void
 100 validate_tree (GtkTreeStore *tree_store)
 101 {
 102   if (gtk_debug_flags & GTK_DEBUG_TREE)
 103     {
 104       g_assert (G_NODE (tree_store->root)->parent == NULL);
 105
 106       validate_gnode (G_NODE (tree_store->root));
 107     }
 108 }
 109
 110 GtkType
 111 gtk_tree_store_get_type (void)
 112 {
 113   static GType tree_store_type = 0;
 114
 115   if (!tree_store_type)
 116     {
 117       static const GTypeInfo tree_store_info =
 118       {
 119         sizeof (GtkTreeStoreClass),
 120         NULL,           /* base_init */
 121         NULL,           /* base_finalize */
 122         (GClassInitFunc) gtk_tree_store_class_init,
 123         NULL,           /* class_finalize */
 124         NULL,           /* class_data */
 125         sizeof (GtkTreeStore),
 126         0,              /* n_preallocs */
 127         (GInstanceInitFunc) gtk_tree_store_init
 128       };
 129
 130       static const GInterfaceInfo tree_model_info =
 131       {
 132         (GInterfaceInitFunc) gtk_tree_store_tree_model_init,
 133         NULL,
 134         NULL
 135       };
 136
 137       static const GInterfaceInfo drag_source_info =
 138       {
 139         (GInterfaceInitFunc) gtk_tree_store_drag_source_init,
 140         NULL,
 141         NULL
 142       };
 143
 144       static const GInterfaceInfo drag_dest_info =
 145       {
 146         (GInterfaceInitFunc) gtk_tree_store_drag_dest_init,
 147         NULL,
 148         NULL
 149       };
 150
 151       static const GInterfaceInfo sortable_info =
 152       {
 153         (GInterfaceInitFunc) gtk_tree_store_sortable_init,
 154         NULL,
 155         NULL
 156       };
 157
 158       tree_store_type = g_type_register_static (G_TYPE_OBJECT, "GtkTreeStore", &tree_store_info, 0);
 159
 160       g_type_add_interface_static (tree_store_type,
 161                                    GTK_TYPE_TREE_MODEL,
 162                                    &tree_model_info);
 163       g_type_add_interface_static (tree_store_type,
 164                                    GTK_TYPE_TREE_DRAG_SOURCE,
 165                                    &drag_source_info);
 166       g_type_add_interface_static (tree_store_type,
 167                                    GTK_TYPE_TREE_DRAG_DEST,
 168                                    &drag_dest_info);
 169       g_type_add_interface_static (tree_store_type,
 170                                    GTK_TYPE_TREE_SORTABLE,
 171                                    &sortable_info);
 172
 173     }
 174
 175   return tree_store_type;
 176 }
 177
 178 static void
 179 gtk_tree_store_class_init (GtkTreeStoreClass *tree_store_class)
 180 {
 181   GObjectClass *object_class;
 182
 183   object_class = (GObjectClass *) tree_store_class;
 184
 185 }
 186
 187 static void
 188 gtk_tree_store_tree_model_init (GtkTreeModelIface *iface)
 189 {
 190   iface->get_flags = gtk_tree_store_get_flags;
 191   iface->get_n_columns = gtk_tree_store_get_n_columns;
 192   iface->get_column_type = gtk_tree_store_get_column_type;
 193   iface->get_path = gtk_tree_store_get_path;
 194   iface->get_value = gtk_tree_store_get_value;
 195   iface->iter_next = gtk_tree_store_iter_next;
 196   iface->iter_children = gtk_tree_store_iter_children;
 197   iface->iter_has_child = gtk_tree_store_iter_has_child;
 198   iface->iter_n_children = gtk_tree_store_iter_n_children;
 199   iface->iter_nth_child = gtk_tree_store_iter_nth_child;
 200   iface->iter_parent = gtk_tree_store_iter_parent;
 201 }
 202
 203 static void
 204 gtk_tree_store_drag_source_init (GtkTreeDragSourceIface *iface)
 205 {
 206   iface->drag_data_delete = gtk_tree_store_drag_data_delete;
 207   iface->drag_data_get = gtk_tree_store_drag_data_get;
 208 }
 209
 210 static void
 211 gtk_tree_store_drag_dest_init (GtkTreeDragDestIface *iface)
 212 {
 213   iface->drag_data_received = gtk_tree_store_drag_data_received;
 214   iface->row_drop_possible = gtk_tree_store_row_drop_possible;
 215 }
 216
 217 static void
 218 gtk_tree_store_sortable_init (GtkTreeSortableIface *iface)
 219 {
 220   iface->get_sort_column_id = gtk_tree_store_get_sort_column_id;
 221   iface->set_sort_column_id = gtk_tree_store_set_sort_column_id;
 222   iface->sort_column_id_set_func = gtk_tree_store_sort_column_id_set_func;
 223 }
 224
 225 static void
 226 gtk_tree_store_init (GtkTreeStore *tree_store)
 227 {
 228   tree_store->root = g_node_new (NULL);
 229   tree_store->stamp = g_random_int ();
 230   tree_store->sort_list = NULL;
 231   tree_store->sort_column_id = -1;
 232 }
 233
 234 GtkTreeStore *
 235 gtk_tree_store_new (void)
 236 {
 237   return GTK_TREE_STORE (g_object_new (GTK_TYPE_TREE_STORE, NULL));
 238 }
 239
 240 GtkTreeStore *
 241 gtk_tree_store_new_with_types (gint n_columns,
 242                                ...)
 243 {
 244   GtkTreeStore *retval;
 245   va_list args;
 246   gint i;
 247
 248   g_return_val_if_fail (n_columns > 0, NULL);
 249
 250   retval = gtk_tree_store_new ();
 251   gtk_tree_store_set_n_columns (retval, n_columns);
 252
 253   va_start (args, n_columns);
 254
 255   for (i = 0; i < n_columns; i++)
 256     {
 257       GType type = va_arg (args, GType);
 258       if (! _gtk_tree_data_list_check_type (type))
 259         {
 260           g_warning ("%s: Invalid type %s passed to gtk_tree_store_new_with_types\n", G_STRLOC, g_type_name (type));
 261           g_object_unref (G_OBJECT (retval));
 262           return NULL;
 263         }
 264       gtk_tree_store_set_column_type (retval, i, type);
 265     }
 266   va_end (args);
 267
 268   return retval;
 269 }
 270
 271 /**
 272  * gtk_tree_store_set_n_columns:
 273  * @tree_store:
 274  * @n_columns:
 275  *
 276  * As a side effect of calling this function, all sort columns that overlap with
 277  * the current number of columns will be removed.
 278  **/
 279 void
 280 gtk_tree_store_set_n_columns (GtkTreeStore *tree_store,
 281                               gint          n_columns)
 282 {
 283   GType *new_columns;
 284
 285   g_return_if_fail (tree_store != NULL);
 286   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
 287
 288   if (tree_store->n_columns == n_columns)
 289     return;
 290
 291   new_columns = g_new0 (GType, n_columns);
 292   if (tree_store->column_headers)
 293     {
 294       /* copy the old header orders over */
 295       if (n_columns >= tree_store->n_columns)
 296         memcpy (new_columns, tree_store->column_headers, tree_store->n_columns * sizeof (gchar *));
 297       else
 298         memcpy (new_columns, tree_store->column_headers, n_columns * sizeof (GType));
 299
 300       g_free (tree_store->column_headers);
 301     }
 302
 303   if (tree_store->sort_list)
 304     _gtk_tree_data_list_header_free (tree_store->sort_list);
 305
 306   tree_store->sort_list = _gtk_tree_data_list_header_new (n_columns, tree_store->column_headers);
 307
 308   tree_store->column_headers = new_columns;
 309   tree_store->n_columns = n_columns;
 310 }
 311
 312 /**
 313  * gtk_tree_store_set_column_type:
 314  * @tree_store: a #GtkTreeStore
 315  * @column: column number
 316  * @type: type of the data to be stored in @column
 317  *
 318  * Supported types include: %G_TYPE_UINT, %G_TYPE_INT, %G_TYPE_UCHAR,
 319  * %G_TYPE_CHAR, %G_TYPE_BOOLEAN, %G_TYPE_POINTER, %G_TYPE_FLOAT,
 320  * %G_TYPE_DOUBLE, %G_TYPE_STRING, %G_TYPE_OBJECT, and %G_TYPE_BOXED, along with
 321  * subclasses of those types such as %GDK_TYPE_PIXBUF.
 322  *
 323  **/
 324 void
 325 gtk_tree_store_set_column_type (GtkTreeStore *tree_store,
 326                                 gint          column,
 327                                 GType         type)
 328 {
 329   g_return_if_fail (tree_store != NULL);
 330   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
 331   g_return_if_fail (column >=0 && column < tree_store->n_columns);
 332   if (!_gtk_tree_data_list_check_type (type))
 333     {
 334       g_warning ("%s: Invalid type %s passed to gtk_tree_store_new_with_types\n", G_STRLOC, g_type_name (type));
 335       return;
 336     }
 337   tree_store->column_headers[column] = type;
 338 }
 339
 340 /* fulfill the GtkTreeModel requirements */
 341 /* NOTE: GtkTreeStore::root is a GNode, that acts as the parent node.  However,
 342  * it is not visible to the tree or to the user., and the path "0" refers to the
 343  * first child of GtkTreeStore::root.
 344  */
 345
 346
 347 static guint
 348 gtk_tree_store_get_flags (GtkTreeModel *tree_model)
 349 {
 350   g_return_val_if_fail (GTK_IS_TREE_STORE (tree_model), 0);
 351
 352   return GTK_TREE_MODEL_ITERS_PERSIST;
 353 }
 354
 355 static gint
 356 gtk_tree_store_get_n_columns (GtkTreeModel *tree_model)
 357 {
 358   g_return_val_if_fail (GTK_IS_TREE_STORE (tree_model), 0);
 359
 360   return GTK_TREE_STORE (tree_model)->n_columns;
 361 }
 362
 363 static GType
 364 gtk_tree_store_get_column_type (GtkTreeModel *tree_model,
 365                                 gint          index)
 366 {
 367   g_return_val_if_fail (GTK_IS_TREE_STORE (tree_model), G_TYPE_INVALID);
 368   g_return_val_if_fail (index < GTK_TREE_STORE (tree_model)->n_columns &&
 369                         index >= 0, G_TYPE_INVALID);
 370
 371   return GTK_TREE_STORE (tree_model)->column_headers[index];
 372 }
 373
 374 static GtkTreePath *
 375 gtk_tree_store_get_path (GtkTreeModel *tree_model,
 376                          GtkTreeIter  *iter)
 377 {
 378   GtkTreePath *retval;
 379   GNode *tmp_node;
 380   gint i = 0;
 381
 382   g_return_val_if_fail (tree_model != NULL, NULL);
 383   g_return_val_if_fail (GTK_IS_TREE_STORE (tree_model), NULL);
 384   g_return_val_if_fail (iter != NULL, NULL);
 385   g_return_val_if_fail (iter->user_data != NULL, NULL);
 386
 387   validate_tree ((GtkTreeStore*)tree_model);
 388
 389   g_assert (G_NODE (iter->user_data)->parent != NULL);
 390
 391   if (G_NODE (iter->user_data)->parent == G_NODE (GTK_TREE_STORE (tree_model)->root))
 392     {
 393       retval = gtk_tree_path_new ();
 394       tmp_node = G_NODE (GTK_TREE_STORE (tree_model)->root)->children;
 395     }
 396   else
 397     {
 398       GtkTreeIter tmp_iter = *iter;
 399
 400       tmp_iter.user_data = G_NODE (iter->user_data)->parent;
 401
 402       retval = gtk_tree_store_get_path (tree_model,
 403                                         &tmp_iter);
 404       tmp_node = G_NODE (iter->user_data)->parent->children;
 405     }
 406
 407   if (retval == NULL)
 408     return NULL;
 409
 410   if (tmp_node == NULL)
 411     {
 412       gtk_tree_path_free (retval);
 413       return NULL;
 414     }
 415
 416   for (; tmp_node; tmp_node = tmp_node->next)
 417     {
 418       if (tmp_node == G_NODE (iter->user_data))
 419         break;
 420       i++;
 421     }
 422
 423   if (tmp_node == NULL)
 424     {
 425       /* We couldn't find node, meaning it's prolly not ours */
 426       /* Perhaps I should do a g_return_if_fail here. */
 427       gtk_tree_path_free (retval);
 428       return NULL;
 429     }
 430
 431   gtk_tree_path_append_index (retval, i);
 432
 433   return retval;
 434 }
 435
 436
 437 static void
 438 gtk_tree_store_get_value (GtkTreeModel *tree_model,
 439                           GtkTreeIter  *iter,
 440                           gint          column,
 441                           GValue       *value)
 442 {
 443   GtkTreeDataList *list;
 444   gint tmp_column = column;
 445
 446   g_return_if_fail (tree_model != NULL);
 447   g_return_if_fail (GTK_IS_TREE_STORE (tree_model));
 448   g_return_if_fail (iter != NULL);
 449   g_return_if_fail (column < GTK_TREE_STORE (tree_model)->n_columns);
 450
 451   list = G_NODE (iter->user_data)->data;
 452
 453   while (tmp_column-- > 0 && list)
 454     list = list->next;
 455
 456   if (list)
 457     {
 458       _gtk_tree_data_list_node_to_value (list,
 459                                          GTK_TREE_STORE (tree_model)->column_headers[column],
 460                                          value);
 461     }
 462   else
 463     {
 464       /* We want to return an initialized but empty (default) value */
 465       g_value_init (value, GTK_TREE_STORE (tree_model)->column_headers[column]);
 466     }
 467 }
 468
 469 static gboolean
 470 gtk_tree_store_iter_next (GtkTreeModel  *tree_model,
 471                           GtkTreeIter   *iter)
 472 {
 473   g_return_val_if_fail (iter->user_data != NULL, FALSE);
 474
 475   if (G_NODE (iter->user_data)->next)
 476     {
 477       iter->user_data = G_NODE (iter->user_data)->next;
 478       return TRUE;
 479     }
 480   else
 481     return FALSE;
 482 }
 483
 484 static gboolean
 485 gtk_tree_store_iter_children (GtkTreeModel *tree_model,
 486                               GtkTreeIter  *iter,
 487                               GtkTreeIter  *parent)
 488 {
 489   GNode *children;
 490
 491   g_return_val_if_fail (parent == NULL || parent->user_data != NULL, FALSE);
 492
 493   if (parent)
 494     children = G_NODE (parent->user_data)->children;
 495   else
 496     children = G_NODE (GTK_TREE_STORE (tree_model)->root)->children;
 497
 498   if (children)
 499     {
 500       iter->stamp = GTK_TREE_STORE (tree_model)->stamp;
 501       iter->user_data = children;
 502       return TRUE;
 503     }
 504   else
 505     return FALSE;
 506 }
 507
 508 static gboolean
 509 gtk_tree_store_iter_has_child (GtkTreeModel *tree_model,
 510                                GtkTreeIter  *iter)
 511 {
 512   g_return_val_if_fail (tree_model != NULL, FALSE);
 513   g_return_val_if_fail (GTK_IS_TREE_STORE (tree_model), FALSE);
 514   g_return_val_if_fail (iter != NULL, FALSE);
 515   g_return_val_if_fail (iter->user_data != NULL, FALSE);
 516
 517   return G_NODE (iter->user_data)->children != NULL;
 518 }
 519
 520 static gint
 521 gtk_tree_store_iter_n_children (GtkTreeModel *tree_model,
 522                                 GtkTreeIter  *iter)
 523 {
 524   GNode *node;
 525   gint i = 0;
 526
 527   g_return_val_if_fail (tree_model != NULL, 0);
 528   g_return_val_if_fail (GTK_IS_TREE_STORE (tree_model), 0);
 529   g_return_val_if_fail (iter != NULL, FALSE);
 530   g_return_val_if_fail (iter->user_data != NULL, FALSE);
 531
 532   if (iter == NULL)
 533     node = G_NODE (GTK_TREE_STORE (tree_model)->root)->children;
 534   else
 535     node = G_NODE (iter->user_data)->children;
 536
 537   while (node)
 538     {
 539       i++;
 540       node = node->next;
 541     }
 542
 543   return i;
 544 }
 545
 546 static gboolean
 547 gtk_tree_store_iter_nth_child (GtkTreeModel *tree_model,
 548                                GtkTreeIter  *iter,
 549                                GtkTreeIter  *parent,
 550                                gint          n)
 551 {
 552   GNode *parent_node;
 553   GNode *child;
 554
 555   g_return_val_if_fail (tree_model != NULL, FALSE);
 556   g_return_val_if_fail (GTK_IS_TREE_STORE (tree_model), FALSE);
 557   g_return_val_if_fail (parent == NULL || parent->user_data != NULL, FALSE);
 558
 559   if (parent == NULL)
 560     parent_node = GTK_TREE_STORE (tree_model)->root;
 561   else
 562     parent_node = parent->user_data;
 563
 564   child = g_node_nth_child (parent_node, n);
 565
 566   if (child)
 567     {
 568       iter->user_data = child;
 569       iter->stamp = GTK_TREE_STORE (tree_model)->stamp;
 570       return TRUE;
 571     }
 572   else
 573     return FALSE;
 574 }
 575
 576 static gboolean
 577 gtk_tree_store_iter_parent (GtkTreeModel *tree_model,
 578                             GtkTreeIter  *iter,
 579                             GtkTreeIter  *child)
 580 {
 581   GNode *parent;
 582
 583   g_return_val_if_fail (iter != NULL, FALSE);
 584   g_return_val_if_fail (iter->user_data != NULL, FALSE);
 585
 586   parent = G_NODE (child->user_data)->parent;
 587
 588   g_assert (parent != NULL);
 589
 590   if (parent != GTK_TREE_STORE (tree_model)->root)
 591     {
 592       iter->user_data = parent;
 593       iter->stamp = GTK_TREE_STORE (tree_model)->stamp;
 594       return TRUE;
 595     }
 596   else
 597     return FALSE;
 598 }
 599
 600 /*
 601  * This is a somewhat inelegant function that does a lot of list
 602  * manipulations on it's own.
 603  */
 604 void
 605 gtk_tree_store_set_value (GtkTreeStore *tree_store,
 606                           GtkTreeIter  *iter,
 607                           gint          column,
 608                           GValue       *value)
 609 {
 610   GtkTreeDataList *list;
 611   GtkTreeDataList *prev;
 612   GtkTreePath *path = NULL;
 613   GValue real_value = {0, };
 614   gboolean converted = FALSE;
 615
 616   g_return_if_fail (tree_store != NULL);
 617   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
 618   g_return_if_fail (column >= 0 && column < tree_store->n_columns);
 619   g_return_if_fail (G_IS_VALUE (value));
 620
 621   if (! g_type_is_a (G_VALUE_TYPE (value), tree_store->column_headers[column]))
 622     {
 623       if (! (g_value_type_compatible (G_VALUE_TYPE (value), tree_store->column_headers[column]) &&
 624              g_value_type_compatible (tree_store->column_headers[column], G_VALUE_TYPE (value))))
 625         {
 626           g_warning ("%s: Unable to convert from %s to %s\n",
 627                      G_STRLOC,
 628                      g_type_name (G_VALUE_TYPE (value)),
 629                      g_type_name (tree_store->column_headers[column]));
 630           return;
 631         }
 632       if (!g_value_transform (value, &real_value))
 633         {
 634           g_warning ("%s: Unable to make conversion from %s to %s\n",
 635                      G_STRLOC,
 636                      g_type_name (G_VALUE_TYPE (value)),
 637                      g_type_name (tree_store->column_headers[column]));
 638           g_value_unset (&real_value);
 639           return;
 640         }
 641       converted = TRUE;
 642     }
 643
 644   prev = list = G_NODE (iter->user_data)->data;
 645
 646   path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
 647
 648   while (list != NULL)
 649     {
 650       if (column == 0)
 651         {
 652           if (converted)
 653             _gtk_tree_data_list_value_to_node (list, &real_value);
 654           else
 655             _gtk_tree_data_list_value_to_node (list, value);
 656           gtk_tree_model_range_changed (GTK_TREE_MODEL (tree_store), path, iter, path, iter);
 657           gtk_tree_path_free (path);
 658           if (converted)
 659             g_value_unset (&real_value);
 660           return;
 661         }
 662
 663       column--;
 664       prev = list;
 665       list = list->next;
 666     }
 667
 668   if (G_NODE (iter->user_data)->data == NULL)
 669     {
 670       G_NODE (iter->user_data)->data = list = _gtk_tree_data_list_alloc ();
 671       list->next = NULL;
 672     }
 673   else
 674     {
 675       list = prev->next = _gtk_tree_data_list_alloc ();
 676       list->next = NULL;
 677     }
 678
 679   while (column != 0)
 680     {
 681       list->next = _gtk_tree_data_list_alloc ();
 682       list = list->next;
 683       list->next = NULL;
 684       column --;
 685     }
 686   if (converted)
 687     _gtk_tree_data_list_value_to_node (list, &real_value);
 688   else
 689     _gtk_tree_data_list_value_to_node (list, value);
 690   gtk_tree_model_range_changed (GTK_TREE_MODEL (tree_store), path, iter, path, iter);
 691   gtk_tree_path_free (path);
 692   if (converted)
 693     g_value_unset (&real_value);
 694
 695   if (GTK_TREE_STORE_IS_SORTED (tree_store))
 696     gtk_tree_store_sort_iter_changed (tree_store, iter, column);
 697 }
 698
 699 /**
 700  * gtk_tree_store_set_valist:
 701  * @tree_store: a #GtkTreeStore
 702  * @iter: row to set data for
 703  * @var_args: va_list of column/value pairs
 704  *
 705  * See gtk_tree_store_set(); this version takes a va_list for
 706  * use by language bindings.
 707  *
 708  **/
 709 void
 710 gtk_tree_store_set_valist (GtkTreeStore *tree_store,
 711                            GtkTreeIter  *iter,
 712                            va_list      var_args)
 713 {
 714   gint column;
 715
 716   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
 717
 718   column = va_arg (var_args, gint);
 719
 720   while (column != -1)
 721     {
 722       GValue value = { 0, };
 723       gchar *error = NULL;
 724
 725       if (column >= tree_store->n_columns)
 726         {
 727           g_warning ("%s: Invalid column number %d added to iter (remember to end your list of columns with a -1)", G_STRLOC, column);
 728           break;
 729         }
 730       g_value_init (&value, tree_store->column_headers[column]);
 731
 732       G_VALUE_COLLECT (&value, var_args, 0, &error);
 733       if (error)
 734         {
 735           g_warning ("%s: %s", G_STRLOC, error);
 736           g_free (error);
 737
 738           /* we purposely leak the value here, it might not be
 739            * in a sane state if an error condition occoured
 740            */
 741           break;
 742         }
 743
 744       /* FIXME: instead of calling this n times, refactor with above */
 745       gtk_tree_store_set_value (tree_store,
 746                                 iter,
 747                                 column,
 748                                 &value);
 749
 750       g_value_unset (&value);
 751
 752       column = va_arg (var_args, gint);
 753     }
 754 }
 755
 756 /**
 757  * gtk_tree_store_set:
 758  * @tree_store: a #GtkTreeStore
 759  * @iter: row iterator
 760  * @Varargs: pairs of column number and value, terminated with -1
 761  *
 762  * Sets the value of one or more cells in the row referenced by @iter.
 763  * The variable argument list should contain integer column numbers,
 764  * each column number followed by the value to be set. For example,
 765  * The list is terminated by a -1. For example, to set column 0 with type
 766  * %G_TYPE_STRING to "Foo", you would write gtk_tree_store_set (store, iter,
 767  * 0, "Foo", -1).
 768  **/
 769 void
 770 gtk_tree_store_set (GtkTreeStore *tree_store,
 771                     GtkTreeIter  *iter,
 772                     ...)
 773 {
 774   va_list var_args;
 775
 776   g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
 777
 778   va_start (var_args, iter);
 779   gtk_tree_store_set_valist (tree_store, iter, var_args);
 780   va_end (var_args);
 781 }
 782
 783 void
 784 gtk_tree_store_remove (GtkTreeStore *model,
 785                        GtkTreeIter  *iter)
 786 {
 787   GtkTreePath *path;
 788   GtkTreeIter new_iter = {0,};
 789   GNode *parent;
 790
 791   g_return_if_fail (model != NULL);
 792   g_return_if_fail (GTK_IS_TREE_STORE (model));
 793
 794   parent = G_NODE (iter->user_data)->parent;
 795
 796   g_assert (parent != NULL);
 797
 798   if (G_NODE (iter->user_data)->data)
 799     _gtk_tree_data_list_free ((GtkTreeDataList *) G_NODE (iter->user_data)->data,
 800                               model->column_headers);
 801
 802   path = gtk_tree_store_get_path (GTK_TREE_MODEL (model), iter);
 803   g_node_destroy (G_NODE (iter->user_data));
 804
 805   model->stamp++;
 806   gtk_tree_model_deleted (GTK_TREE_MODEL (model), path);
 807
 808   if (parent != G_NODE (model->root) && parent->children == NULL)
 809     {
 810       gtk_tree_path_up (path);
 811
 812       new_iter.stamp = model->stamp;
 813       new_iter.user_data = parent;
 814       gtk_tree_model_has_child_toggled (GTK_TREE_MODEL (model), path, &new_iter);
 815     }
 816   gtk_tree_path_free (path);
 817 }
 818
 819 void
 820 gtk_tree_store_insert (GtkTreeStore *model,
 821                        GtkTreeIter  *iter,
 822                        GtkTreeIter  *parent,
 823                        gint          position)
 824 {
 825   GtkTreePath *path;
 826   GNode *parent_node;
 827
 828   g_return_if_fail (model != NULL);
 829   g_return_if_fail (GTK_IS_TREE_STORE (model));
 830
 831   if (parent)
 832     parent_node = parent->user_data;
 833   else
 834     parent_node = model->root;
 835
 836   iter->stamp = model->stamp;
 837   iter->user_data = g_node_new (NULL);
 838   g_node_insert (parent_node, position, G_NODE (iter->user_data));
 839
 840   path = gtk_tree_store_get_path (GTK_TREE_MODEL (model), iter);
 841   gtk_tree_model_inserted (GTK_TREE_MODEL (model), path, iter);
 842
 843   gtk_tree_path_free (path);
 844
 845   validate_tree ((GtkTreeStore*)model);
 846 }
 847
 848 void
 849 gtk_tree_store_insert_before (GtkTreeStore *model,
 850                               GtkTreeIter  *iter,
 851                               GtkTreeIter  *parent,
 852                               GtkTreeIter  *sibling)
 853 {
 854   GtkTreePath *path;
 855   GNode *parent_node = NULL;
 856   GNode *new_node;
 857
 858   g_return_if_fail (model != NULL);
 859   g_return_if_fail (GTK_IS_TREE_STORE (model));
 860   g_return_if_fail (iter != NULL);
 861
 862   new_node = g_node_new (NULL);
 863
 864   if (parent == NULL && sibling == NULL)
 865     parent_node = model->root;
 866   else if (parent == NULL)
 867     parent_node = G_NODE (sibling->user_data)->parent;
 868   else if (sibling == NULL)
 869     parent_node = G_NODE (parent->user_data);
 870   else
 871     {
 872       g_return_if_fail (G_NODE (sibling->user_data)->parent ==
 873                         G_NODE (parent->user_data));
 874       parent_node = G_NODE (parent->user_data);
 875     }
 876
 877   g_node_insert_before (parent_node,
 878                         sibling ? G_NODE (sibling->user_data) : NULL,
 879                         new_node);
 880
 881   iter->stamp = model->stamp;
 882   iter->user_data = new_node;
 883
 884   path = gtk_tree_store_get_path (GTK_TREE_MODEL (model), iter);
 885   gtk_tree_model_inserted (GTK_TREE_MODEL (model), path, iter);
 886
 887   gtk_tree_path_free (path);
 888
 889   validate_tree ((GtkTreeStore*)model);
 890 }
 891
 892 void
 893 gtk_tree_store_insert_after (GtkTreeStore *model,
 894                              GtkTreeIter  *iter,
 895                              GtkTreeIter  *parent,
 896                              GtkTreeIter  *sibling)
 897 {
 898   GtkTreePath *path;
 899   GNode *parent_node;
 900   GNode *new_node;
 901
 902   g_return_if_fail (model != NULL);
 903   g_return_if_fail (GTK_IS_TREE_STORE (model));
 904   g_return_if_fail (iter != NULL);
 905
 906   new_node = g_node_new (NULL);
 907
 908   if (parent == NULL && sibling == NULL)
 909     parent_node = model->root;
 910   else if (parent == NULL)
 911     parent_node = G_NODE (sibling->user_data)->parent;
 912   else if (sibling == NULL)
 913     parent_node = G_NODE (parent->user_data);
 914   else
 915     {
 916       g_return_if_fail (G_NODE (sibling->user_data)->parent ==
 917                         G_NODE (parent->user_data));
 918       parent_node = G_NODE (parent->user_data);
 919     }
 920
 921
 922   g_node_insert_after (parent_node,
 923                        sibling ? G_NODE (sibling->user_data) : NULL,
 924                        new_node);
 925
 926   iter->stamp = model->stamp;
 927   iter->user_data = new_node;
 928
 929   path = gtk_tree_store_get_path (GTK_TREE_MODEL (model), iter);
 930   gtk_tree_model_inserted (GTK_TREE_MODEL (model), path, iter);
 931
 932   gtk_tree_path_free (path);
 933
 934   validate_tree ((GtkTreeStore*)model);
 935 }
 936
 937 void
 938 gtk_tree_store_prepend (GtkTreeStore *model,
 939                         GtkTreeIter  *iter,
 940                         GtkTreeIter  *parent)
 941 {
 942   GNode *parent_node;
 943
 944   g_return_if_fail (model != NULL);
 945   g_return_if_fail (GTK_IS_TREE_STORE (model));
 946   g_return_if_fail (iter != NULL);
 947
 948   if (parent == NULL)
 949     parent_node = model->root;
 950   else
 951     parent_node = parent->user_data;
 952
 953   if (parent_node->children == NULL)
 954     {
 955       GtkTreePath *path;
 956
 957       iter->stamp = model->stamp;
 958       iter->user_data = g_node_new (NULL);
 959
 960       g_node_prepend (parent_node, iter->user_data);
 961
 962       if (parent_node != model->root)
 963         {
 964           path = gtk_tree_store_get_path (GTK_TREE_MODEL (model), parent);
 965           gtk_tree_model_has_child_toggled (GTK_TREE_MODEL (model), path, parent);
 966           gtk_tree_path_append_index (path, 0);
 967         }
 968       else
 969         {
 970           path = gtk_tree_store_get_path (GTK_TREE_MODEL (model), iter);
 971         }
 972       gtk_tree_model_inserted (GTK_TREE_MODEL (model), path, iter);
 973       gtk_tree_path_free (path);
 974     }
 975   else
 976     {
 977       gtk_tree_store_insert_after (model, iter, parent, NULL);
 978     }
 979
 980   validate_tree ((GtkTreeStore*)model);
 981 }
 982
 983 void
 984 gtk_tree_store_append (GtkTreeStore *model,
 985                        GtkTreeIter  *iter,
 986                        GtkTreeIter  *parent)
 987 {
 988   GNode *parent_node;
 989
 990   g_return_if_fail (model != NULL);
 991   g_return_if_fail (GTK_IS_TREE_STORE (model));
 992   g_return_if_fail (iter != NULL);
 993
 994   if (parent == NULL)
 995     parent_node = model->root;
 996   else
 997     parent_node = parent->user_data;
 998
 999   if (parent_node->children == NULL)
1000     {
1001       GtkTreePath *path;
1002
1003       iter->stamp = model->stamp;
1004       iter->user_data = g_node_new (NULL);
1005
1006       g_node_append (parent_node, G_NODE (iter->user_data));
1007
1008       if (parent_node != model->root)
1009         {
1010           path = gtk_tree_store_get_path (GTK_TREE_MODEL (model), parent);
1011           gtk_tree_model_has_child_toggled (GTK_TREE_MODEL (model), path, parent);
1012           gtk_tree_path_append_index (path, 0);
1013         }
1014       else
1015         {
1016           path = gtk_tree_store_get_path (GTK_TREE_MODEL (model), iter);
1017         }
1018
1019       gtk_tree_model_inserted (GTK_TREE_MODEL (model), path, iter);
1020       gtk_tree_path_free (path);
1021     }
1022   else
1023     {
1024       gtk_tree_store_insert_before (model, iter, parent, NULL);
1025     }
1026
1027   validate_tree ((GtkTreeStore*)model);
1028 }
1029
1030 gboolean
1031 gtk_tree_store_is_ancestor (GtkTreeStore *model,
1032                             GtkTreeIter  *iter,
1033                             GtkTreeIter  *descendant)
1034 {
1035   g_return_val_if_fail (model != NULL, FALSE);
1036   g_return_val_if_fail (GTK_IS_TREE_STORE (model), FALSE);
1037   g_return_val_if_fail (iter != NULL, FALSE);
1038   g_return_val_if_fail (descendant != NULL, FALSE);
1039
1040   return g_node_is_ancestor (G_NODE (iter->user_data),
1041                              G_NODE (descendant->user_data));
1042 }
1043
1044
1045 gint
1046 gtk_tree_store_iter_depth (GtkTreeStore *model,
1047                            GtkTreeIter  *iter)
1048 {
1049   g_return_val_if_fail (model != NULL, 0);
1050   g_return_val_if_fail (GTK_IS_TREE_STORE (model), 0);
1051   g_return_val_if_fail (iter != NULL, 0);
1052
1053   return g_node_depth (G_NODE (iter->user_data)) - 1;
1054 }
1055
1056 /* DND */
1057
1058
1059
1060 static gboolean
1061 gtk_tree_store_drag_data_delete (GtkTreeDragSource *drag_source,
1062                                  GtkTreePath       *path)
1063 {
1064   GtkTreeIter iter;
1065
1066   g_return_val_if_fail (GTK_IS_TREE_STORE (drag_source), FALSE);
1067
1068   if (gtk_tree_model_get_iter (GTK_TREE_MODEL (drag_source),
1069                                &iter,
1070                                path))
1071     {
1072       gtk_tree_store_remove (GTK_TREE_STORE (drag_source),
1073                              &iter);
1074       return TRUE;
1075     }
1076   else
1077     {
1078       return FALSE;
1079     }
1080 }
1081
1082 static gboolean
1083 gtk_tree_store_drag_data_get (GtkTreeDragSource *drag_source,
1084                               GtkTreePath       *path,
1085                               GtkSelectionData  *selection_data)
1086 {
1087   g_return_val_if_fail (GTK_IS_TREE_STORE (drag_source), FALSE);
1088
1089   /* Note that we don't need to handle the GTK_TREE_MODEL_ROW
1090    * target, because the default handler does it for us, but
1091    * we do anyway for the convenience of someone maybe overriding the
1092    * default handler.
1093    */
1094
1095   if (gtk_selection_data_set_tree_row (selection_data,
1096                                        GTK_TREE_MODEL (drag_source),
1097                                        path))
1098     {
1099       return TRUE;
1100     }
1101   else
1102     {
1103       /* FIXME handle text targets at least. */
1104     }
1105
1106   return FALSE;
1107 }
1108
1109 static void
1110 copy_node_data (GtkTreeStore *tree_store,
1111                 GtkTreeIter  *src_iter,
1112                 GtkTreeIter  *dest_iter)
1113 {
1114   GtkTreeDataList *dl = G_NODE (src_iter->user_data)->data;
1115   GtkTreeDataList *copy_head = NULL;
1116   GtkTreeDataList *copy_prev = NULL;
1117   GtkTreeDataList *copy_iter = NULL;
1118   GtkTreePath *path;
1119   gint col;
1120
1121   col = 0;
1122   while (dl)
1123     {
1124       copy_iter = _gtk_tree_data_list_node_copy (dl, tree_store->column_headers[col]);
1125
1126       if (copy_head == NULL)
1127         copy_head = copy_iter;
1128
1129       if (copy_prev)
1130         copy_prev->next = copy_iter;
1131
1132       copy_prev = copy_iter;
1133
1134       dl = dl->next;
1135       ++col;
1136     }
1137
1138   G_NODE (dest_iter->user_data)->data = copy_head;
1139
1140   path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), dest_iter);
1141   gtk_tree_model_range_changed (GTK_TREE_MODEL (tree_store), path, dest_iter, path, dest_iter);
1142   gtk_tree_path_free (path);
1143 }
1144
1145 static void
1146 recursive_node_copy (GtkTreeStore *tree_store,
1147                      GtkTreeIter  *src_iter,
1148                      GtkTreeIter  *dest_iter)
1149 {
1150   GtkTreeIter child;
1151   GtkTreeModel *model;
1152
1153   model = GTK_TREE_MODEL (tree_store);
1154
1155   copy_node_data (tree_store, src_iter, dest_iter);
1156
1157   if (gtk_tree_model_iter_children (model,
1158                                     &child,
1159                                     src_iter))
1160     {
1161       /* Need to create children and recurse. Note our
1162        * dependence on persistent iterators here.
1163        */
1164       do
1165         {
1166           GtkTreeIter copy;
1167
1168           /* Gee, a really slow algorithm... ;-) FIXME */
1169           gtk_tree_store_append (tree_store,
1170                                  &copy,
1171                                  dest_iter);
1172
1173           recursive_node_copy (tree_store, &child, &copy);
1174         }
1175       while (gtk_tree_model_iter_next (model, &child));
1176     }
1177 }
1178
1179 static gboolean
1180 gtk_tree_store_drag_data_received (GtkTreeDragDest   *drag_dest,
1181                                    GtkTreePath       *dest,
1182                                    GtkSelectionData  *selection_data)
1183 {
1184   GtkTreeModel *tree_model;
1185   GtkTreeStore *tree_store;
1186   GtkTreeModel *src_model = NULL;
1187   GtkTreePath *src_path = NULL;
1188   gboolean retval = FALSE;
1189
1190   g_return_val_if_fail (GTK_IS_TREE_STORE (drag_dest), FALSE);
1191
1192   tree_model = GTK_TREE_MODEL (drag_dest);
1193   tree_store = GTK_TREE_STORE (drag_dest);
1194
1195   validate_tree (tree_store);
1196
1197   if (gtk_selection_data_get_tree_row (selection_data,
1198                                        &src_model,
1199                                        &src_path) &&
1200       src_model == tree_model)
1201     {
1202       /* Copy the given row to a new position */
1203       GtkTreeIter src_iter;
1204       GtkTreeIter dest_iter;
1205       GtkTreePath *prev;
1206
1207       if (!gtk_tree_model_get_iter (src_model,
1208                                     &src_iter,
1209                                     src_path))
1210         {
1211           goto out;
1212         }
1213
1214       /* Get the path to insert _after_ (dest is the path to insert _before_) */
1215       prev = gtk_tree_path_copy (dest);
1216
1217       if (!gtk_tree_path_prev (prev))
1218         {
1219           GtkTreeIter dest_parent;
1220           GtkTreePath *parent;
1221           GtkTreeIter *dest_parent_p;
1222
1223           /* dest was the first spot at the current depth; which means
1224            * we are supposed to prepend.
1225            */
1226
1227           /* Get the parent, NULL if parent is the root */
1228           dest_parent_p = NULL;
1229           parent = gtk_tree_path_copy (dest);
1230           if (gtk_tree_path_up (parent))
1231             {
1232               gtk_tree_model_get_iter (tree_model,
1233                                        &dest_parent,
1234                                        parent);
1235               dest_parent_p = &dest_parent;
1236             }
1237           gtk_tree_path_free (parent);
1238           parent = NULL;
1239
1240           gtk_tree_store_prepend (GTK_TREE_STORE (tree_model),
1241                                   &dest_iter,
1242                                   dest_parent_p);
1243
1244           retval = TRUE;
1245         }
1246       else
1247         {
1248           if (gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model),
1249                                        &dest_iter,
1250                                        prev))
1251             {
1252               GtkTreeIter tmp_iter = dest_iter;
1253               gtk_tree_store_insert_after (GTK_TREE_STORE (tree_model),
1254                                            &dest_iter,
1255                                            NULL,
1256                                            &tmp_iter);
1257               retval = TRUE;
1258
1259             }
1260         }
1261
1262       gtk_tree_path_free (prev);
1263
1264       /* If we succeeded in creating dest_iter, walk src_iter tree branch,
1265        * duplicating it below dest_iter.
1266        */
1267
1268       if (retval)
1269         {
1270           recursive_node_copy (tree_store,
1271                                &src_iter,
1272                                &dest_iter);
1273         }
1274     }
1275   else
1276     {
1277       /* FIXME maybe add some data targets eventually, or handle text
1278        * targets in the simple case.
1279        */
1280
1281     }
1282
1283  out:
1284
1285   if (src_path)
1286     gtk_tree_path_free (src_path);
1287
1288   return retval;
1289 }
1290
1291 static gboolean
1292 gtk_tree_store_row_drop_possible (GtkTreeDragDest *drag_dest,
1293                                   GtkTreeModel    *src_model,
1294                                   GtkTreePath     *src_path,
1295                                   GtkTreePath     *dest_path)
1296 {
1297   /* can only drag to ourselves */
1298   if (src_model != GTK_TREE_MODEL (drag_dest))
1299     return FALSE;
1300
1301   /* Can't drop into ourself. */
1302   if (gtk_tree_path_is_ancestor (src_path,
1303                                  dest_path))
1304     return FALSE;
1305
1306   /* Can't drop if dest_path's parent doesn't exist */
1307   {
1308     GtkTreeIter iter;
1309     GtkTreePath *tmp = gtk_tree_path_copy (dest_path);
1310
1311     /* if we can't go up, we know the parent exists, the root
1312      * always exists.
1313      */
1314     if (gtk_tree_path_up (tmp))
1315       {
1316         if (!gtk_tree_model_get_iter (GTK_TREE_MODEL (drag_dest),
1317                                       &iter, tmp))
1318           {
1319             if (tmp)
1320               gtk_tree_path_free (tmp);
1321             return FALSE;
1322           }
1323       }
1324
1325     if (tmp)
1326       gtk_tree_path_free (tmp);
1327   }
1328
1329   /* Can otherwise drop anywhere. */
1330   return TRUE;
1331 }
1332
1333 /* Sorting */
1334 typedef struct _SortTuple
1335 {
1336   gint offset;
1337   GNode *node;
1338 } SortTuple;
1339
1340 static gint
1341 gtk_tree_store_compare_func (gconstpointer a,
1342                              gconstpointer b,
1343                              gpointer      user_data)
1344 {
1345   GtkTreeStore *tree_store = user_data;
1346   GtkTreeDataSortHeader *header = NULL;
1347   GNode *node_a;
1348   GNode *node_b;
1349   GtkTreeIter iter_a;
1350   GtkTreeIter iter_b;
1351   gint retval;
1352
1353   header = _gtk_tree_data_list_get_header (tree_store->sort_list,
1354                                            tree_store->sort_column_id);
1355
1356   g_return_val_if_fail (header != NULL, 0);
1357   g_return_val_if_fail (header->func != NULL, 0);
1358
1359   node_a = ((SortTuple *) a)->node;
1360   node_b = ((SortTuple *) b)->node;
1361
1362   iter_a.stamp = tree_store->stamp;
1363   iter_a.user_data = node_a;
1364   iter_b.stamp = tree_store->stamp;
1365   iter_b.user_data = node_b;
1366
1367   retval = (* header->func) (GTK_TREE_MODEL (user_data),
1368                              &iter_a, &iter_b,
1369                              header->data);
1370
1371   if (tree_store->order == GTK_TREE_SORT_DESCENDING)
1372     {
1373       if (retval > 0)
1374         retval = -1;
1375       else if (retval < 0)
1376         retval = 1;
1377     }
1378   return retval;
1379 }
1380
1381 static void
1382 gtk_tree_store_sort_helper (GtkTreeStore *tree_store,
1383                             GNode        *node)
1384 {
1385   GtkTreeDataSortHeader *header = NULL;
1386   GtkTreeIter iter;
1387   GArray *sort_array;
1388   GNode *tmp_node;
1389   gint list_length;
1390   gint i;
1391   gint *new_order;
1392   GtkTreePath *path;
1393
1394   if (node->next == NULL)
1395     return;
1396
1397   g_assert (GTK_TREE_STORE_IS_SORTED (tree_store));
1398
1399   header = _gtk_tree_data_list_get_header (tree_store->sort_list, tree_store->sort_column_id);
1400
1401   /* We want to make sure that we have a function */
1402   g_return_if_fail (header != NULL);
1403   g_return_if_fail (header->func != NULL);
1404
1405   list_length = 0;
1406   for (tmp_node = node; tmp_node; tmp_node = tmp_node->next)
1407     list_length++;
1408
1409   sort_array = g_array_sized_new (FALSE, FALSE, sizeof (SortTuple), list_length);
1410
1411   i = 0;
1412   for (tmp_node = node; tmp_node; tmp_node = tmp_node->next)
1413     {
1414       SortTuple tuple;
1415
1416       tuple.offset = i;
1417       tuple.node = tmp_node;
1418       g_array_append_val (sort_array, tuple);
1419       i++;
1420     }
1421
1422   g_array_sort_with_data (sort_array, gtk_tree_store_compare_func, tree_store);
1423
1424   for (i = 0; i < list_length - 1; i++)
1425     {
1426       g_array_index (sort_array, SortTuple, i).node->next =
1427         g_array_index (sort_array, SortTuple, i + 1).node;
1428       g_array_index (sort_array, SortTuple, i + 1).node->prev =
1429         g_array_index (sort_array, SortTuple, i).node;
1430     }
1431   g_array_index (sort_array, SortTuple, list_length - 1).node->next = NULL;
1432   g_array_index (sort_array, SortTuple, 0).node->prev = NULL;
1433   G_NODE (tree_store->root)->children = g_array_index (sort_array, SortTuple, 0).node;
1434
1435   /* Let the world know about our new order */
1436   new_order = g_new (gint, list_length);
1437   for (i = 0; i < list_length; i++)
1438     new_order[i] = g_array_index (sort_array, SortTuple, i).offset;
1439   path = gtk_tree_path_new ();
1440   iter.stamp = tree_store->stamp;
1441   iter.user_data = NULL;
1442
1443   gtk_tree_model_reordered (GTK_TREE_MODEL (tree_store),
1444                             path, &iter, new_order);
1445   gtk_tree_path_free (path);
1446   g_free (new_order);
1447   g_array_free (sort_array, TRUE);
1448 }
1449
1450 static void
1451 gtk_tree_store_sort (GtkTreeStore *tree_store)
1452 {
1453   gtk_tree_store_sort_helper (tree_store, G_NODE (tree_store->root)->children);
1454 }
1455
1456 static void
1457 gtk_tree_store_sort_iter_changed (GtkTreeStore *tree_store,
1458                                   GtkTreeIter  *iter,
1459                                   gint          column)
1460 {
1461   GtkTreeDataSortHeader *header;
1462   GNode *prev = NULL;
1463   GNode *next = NULL;
1464   GNode *node;
1465   GtkTreePath *tmp_path;
1466   GtkTreeIter tmp_iter;
1467   gint cmp_a = 0;
1468   gint cmp_b = 0;
1469   gint i;
1470   gint old_location;
1471   gint new_location;
1472   gint *new_order;
1473   gint length;
1474
1475   /* FIX*/
1476   if (G_NODE (iter->user_data)->parent)
1477     node = G_NODE (iter->user_data)->parent->children;
1478   else
1479     node = G_NODE (tree_store->root);
1480
1481   tmp_iter.stamp = tree_store->stamp;
1482   header = _gtk_tree_data_list_get_header (tree_store->sort_list,
1483                                            tree_store->sort_column_id);
1484   g_return_if_fail (header != NULL);
1485   g_return_if_fail (header->func != NULL);
1486
1487   /* If it's the built in function, we don't sort. */
1488   if (header->func == gtk_tree_data_list_compare_func &&
1489       tree_store->sort_column_id != column)
1490     return;
1491
1492   old_location = 0;
1493   /* First we find the iter, its prev, and its next */
1494   while (node)
1495     {
1496       if (node == G_NODE (iter->user_data))
1497         break;
1498       prev = node;
1499       node = node->next;
1500       old_location++;
1501     }
1502   g_assert (node != NULL);
1503
1504   next = node->next;
1505
1506   /* Check the common case, where we don't need to sort it moved. */
1507   if (prev != NULL)
1508     {
1509       tmp_iter.user_data = prev;
1510       cmp_a = (* header->func) (GTK_TREE_MODEL (tree_store),
1511                                 &tmp_iter, iter,
1512                                 header->data);
1513     }
1514
1515   if (next != NULL)
1516     {
1517       tmp_iter.user_data = next;
1518       cmp_b = (* header->func) (GTK_TREE_MODEL (tree_store),
1519                                 iter, &tmp_iter,
1520                                 header->data);
1521     }
1522
1523
1524   if (tree_store->order == GTK_TREE_SORT_DESCENDING)
1525     {
1526       if (cmp_a < 0)
1527         cmp_a = 1;
1528       else if (cmp_a > 0)
1529         cmp_a = -1;
1530
1531       if (cmp_b < 0)
1532         cmp_b = 1;
1533       else if (cmp_b > 0)
1534         cmp_b = -1;
1535     }
1536
1537   if (prev == NULL && cmp_b <= 0)
1538     return;
1539   else if (next == NULL && cmp_a <= 0)
1540     return;
1541   else if (prev != NULL && next != NULL &&
1542            cmp_a <= 0 && cmp_b <= 0)
1543     return;
1544
1545   /* We actually need to sort it */
1546   /* First, remove the old link. */
1547
1548   if (prev == NULL)
1549     tree_store->root = next;
1550   else
1551     prev->next = next;
1552   node->next = NULL;
1553
1554   /* FIXME: as an optimization, we can potentially start at next */
1555   prev = NULL;
1556   node = G_NODE (tree_store->root);
1557   new_location = 0;
1558   tmp_iter.user_data = node;
1559   if (tree_store->order == GTK_TREE_SORT_DESCENDING)
1560     cmp_a = (* header->func) (GTK_TREE_MODEL (tree_store),
1561                               &tmp_iter, iter, header->data);
1562   else
1563     cmp_a = (* header->func) (GTK_TREE_MODEL (tree_store),
1564                               iter, &tmp_iter, header->data);
1565
1566   while ((node->next) && (cmp_a > 0))
1567     {
1568       prev = node;
1569       node = node->next;
1570       new_location++;
1571       tmp_iter.user_data = node;
1572       if (tree_store->order == GTK_TREE_SORT_DESCENDING)
1573         cmp_a = (* header->func) (GTK_TREE_MODEL (tree_store),
1574                                   &tmp_iter, iter, header->data);
1575       else
1576         cmp_a = (* header->func) (GTK_TREE_MODEL (tree_store),
1577                                   iter, &tmp_iter, header->data);
1578     }
1579
1580   if ((!node->next) && (cmp_a > 0))
1581     {
1582       node->next = G_NODE (iter->user_data);
1583     }
1584   else if (prev)
1585     {
1586       prev->next = G_NODE (iter->user_data);
1587       G_NODE (iter->user_data)->next = node;
1588     }
1589   else
1590     {
1591       G_NODE (iter->user_data)->next = G_NODE (tree_store->root);
1592       tree_store->root = G_NODE (iter->user_data);
1593     }
1594
1595   /* Emit the reordered signal. */
1596   length = g_node_n_children (node->parent);
1597   new_order = g_new (int, length);
1598   if (old_location < new_location)
1599     for (i = 0; i < length; i++)
1600       {
1601         if (i < old_location ||
1602             i > new_location)
1603           new_order[i] = i;
1604         else if (i >= old_location &&
1605                  i < new_location)
1606           new_order[i] = i + 1;
1607         else if (i == new_location)
1608           new_order[i] = old_location;
1609       }
1610   else
1611     for (i = 0; i < length; i++)
1612       {
1613         if (i < new_location ||
1614             i > old_location)
1615           new_order[i] = i;
1616         else if (i > new_location &&
1617                  i <= old_location)
1618           new_order[i] = i - 1;
1619         else if (i == new_location)
1620           new_order[i] = old_location;
1621       }
1622
1623
1624   tmp_path = gtk_tree_path_new ();
1625   tmp_iter.user_data = NULL;
1626
1627   gtk_tree_model_reordered (GTK_TREE_MODEL (tree_store),
1628                             tmp_path, &tmp_iter,
1629                             new_order);
1630
1631   gtk_tree_path_free (tmp_path);
1632   g_free (new_order);
1633 }
1634
1635
1636 static gboolean
1637 gtk_tree_store_get_sort_column_id (GtkTreeSortable  *sortable,
1638                                    gint             *sort_column_id,
1639                                    GtkTreeSortOrder *order)
1640 {
1641   GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
1642
1643   g_return_val_if_fail (sortable != NULL, FALSE);
1644   g_return_val_if_fail (GTK_IS_TREE_STORE (sortable), FALSE);
1645
1646   if (tree_store->sort_column_id == -1)
1647     return FALSE;
1648
1649   if (sort_column_id)
1650     * sort_column_id = tree_store->sort_column_id;
1651   if (order)
1652     * order = tree_store->order;
1653   return TRUE;
1654
1655 }
1656
1657 static void
1658 gtk_tree_store_set_sort_column_id (GtkTreeSortable  *sortable,
1659                                    gint              sort_column_id,
1660                                    GtkTreeSortOrder  order)
1661 {
1662   GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
1663   GList *list;
1664
1665   g_return_if_fail (sortable != NULL);
1666   g_return_if_fail (GTK_IS_TREE_STORE (sortable));
1667
1668   for (list = tree_store->sort_list; list; list = list->next)
1669     {
1670       GtkTreeDataSortHeader *header = (GtkTreeDataSortHeader*) list->data;
1671       if (header->sort_column_id == sort_column_id)
1672         break;
1673     }
1674   g_return_if_fail (list != NULL);
1675
1676   if ((tree_store->sort_column_id == sort_column_id) &&
1677       (tree_store->order == order))
1678     return;
1679
1680   tree_store->sort_column_id = sort_column_id;
1681   tree_store->order = order;
1682
1683   if (tree_store->sort_column_id >= 0)
1684     gtk_tree_store_sort (tree_store);
1685
1686   gtk_tree_sortable_sort_column_changed (sortable);
1687 }
1688
1689 static void
1690 gtk_tree_store_sort_column_id_set_func (GtkTreeSortable        *sortable,
1691                                         gint                    sort_column_id,
1692                                         GtkTreeIterCompareFunc  func,
1693                                         gpointer                data,
1694                                         GtkDestroyNotify        destroy)
1695 {
1696   GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
1697   GtkTreeDataSortHeader *header = NULL;
1698   GList *list;
1699
1700   g_return_if_fail (sortable != NULL);
1701   g_return_if_fail (GTK_IS_TREE_STORE (sortable));
1702   g_return_if_fail (func != NULL);
1703
1704   for (list = tree_store->sort_list; list; list = list->next)
1705     {
1706       header = (GtkTreeDataSortHeader*) list->data;
1707       if (header->sort_column_id == sort_column_id)
1708         break;
1709     }
1710
1711   if (header == NULL)
1712     {
1713       header = g_new0 (GtkTreeDataSortHeader, 1);
1714       header->sort_column_id = sort_column_id;
1715       tree_store->sort_list = g_list_append (tree_store->sort_list, header);
1716     }
1717
1718   if (header->destroy)
1719     (* header->destroy) (header->data);
1720
1721   header->func = func;
1722   header->data = data;
1723   header->destroy = destroy;
1724
1725 }
1726
1727 static void
1728 validate_gnode (GNode* node)
1729 {
1730   GNode *iter;
1731
1732   iter = node->children;
1733   while (iter != NULL)
1734     {
1735       g_assert (iter->parent == node);
1736       if (iter->prev)
1737         g_assert (iter->prev->next == iter);
1738       validate_gnode (iter);
1739       iter = iter->next;
1740     }
1741 }
1742
1743