Pileus Git - ~andy/gtk/blob - gtk/gtktreemodelsort.c

   1 /* gtktreemodelsort.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
  21 /* NOTE: There is a potential for confusion in this code as to whether an iter,
  22  * path or value refers to the GtkTreeModelSort model, or the child model being
  23  * sorted.  As a convention, variables referencing the child model will have an
  24  * s_ prefix before them (ie. s_iter, s_value, s_path);
  25  */
  26
  27 #include "gtktreemodelsort.h"
  28 #include "gtktreesortable.h"
  29 #include "gtksignal.h"
  30 #include "gtktreedatalist.h"
  31 #include <string.h>
  32
  33
  34
  35 typedef struct _SortElt SortElt;
  36 struct _SortElt
  37 {
  38   GtkTreeIter iter;
  39   SortElt *parent;
  40   GArray *children;
  41   gint ref;
  42   gint offset;
  43 };
  44
  45 typedef struct _SortData SortData;
  46 struct _SortData
  47 {
  48   GtkTreeModel *model;
  49   gint sort_col;
  50   GValueCompareFunc func;
  51 };
  52
  53
  54 #define get_array(e,t) ((GArray *)((e)->parent?(e)->parent->children:GTK_TREE_MODEL_SORT(t)->root))
  55
  56
  57 static void         gtk_tree_model_sort_init            (GtkTreeModelSort      *tree_model_sort);
  58 static void         gtk_tree_model_sort_class_init      (GtkTreeModelSortClass *tree_model_sort_class);
  59 static void         gtk_tree_model_sort_tree_model_init (GtkTreeModelIface     *iface);
  60 static void         gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface   *iface);
  61 static void         gtk_tree_model_sort_finalize        (GObject               *object);
  62 static void         gtk_tree_model_sort_range_changed   (GtkTreeModel          *model,
  63                                                          GtkTreePath           *start_path,
  64                                                          GtkTreeIter           *start_iter,
  65                                                          GtkTreePath           *end_path,
  66                                                          GtkTreeIter           *end_iter,
  67                                                          gpointer               data);
  68 static void         gtk_tree_model_sort_inserted        (GtkTreeModel          *model,
  69                                                          GtkTreePath           *path,
  70                                                          GtkTreeIter           *iter,
  71                                                          gpointer               data);
  72 static void         gtk_tree_model_sort_has_child_toggled   (GtkTreeModel          *model,
  73                                                              GtkTreePath           *path,
  74                                                              GtkTreeIter           *iter,
  75                                                              gpointer               data);
  76 static void         gtk_tree_model_sort_deleted         (GtkTreeModel          *model,
  77                                                          GtkTreePath           *path,
  78                                                          gpointer               data);
  79 static gint         gtk_tree_model_sort_get_n_columns   (GtkTreeModel          *tree_model);
  80 static GType        gtk_tree_model_sort_get_column_type (GtkTreeModel          *tree_model,
  81                                                          gint                   index);
  82 static gboolean     gtk_tree_model_sort_get_iter        (GtkTreeModel          *tree_model,
  83                                                          GtkTreeIter           *iter,
  84                                                          GtkTreePath           *path);
  85 static GtkTreePath *gtk_tree_model_sort_get_path        (GtkTreeModel          *tree_model,
  86                                                          GtkTreeIter           *iter);
  87 static void         gtk_tree_model_sort_get_value       (GtkTreeModel          *tree_model,
  88                                                          GtkTreeIter           *iter,
  89                                                          gint                   column,
  90                                                          GValue                *value);
  91 static gboolean     gtk_tree_model_sort_iter_next       (GtkTreeModel          *tree_model,
  92                                                          GtkTreeIter           *iter);
  93 static gboolean     gtk_tree_model_sort_iter_children   (GtkTreeModel          *tree_model,
  94                                                          GtkTreeIter           *iter,
  95                                                          GtkTreeIter           *parent);
  96 static gboolean     gtk_tree_model_sort_iter_has_child  (GtkTreeModel          *tree_model,
  97                                                          GtkTreeIter           *iter);
  98 static gint         gtk_tree_model_sort_iter_n_children (GtkTreeModel          *tree_model,
  99                                                          GtkTreeIter           *iter);
 100 static gboolean     gtk_tree_model_sort_iter_nth_child  (GtkTreeModel          *tree_model,
 101                                                          GtkTreeIter           *iter,
 102                                                          GtkTreeIter           *parent,
 103                                                          gint                   n);
 104 static gboolean     gtk_tree_model_sort_iter_parent     (GtkTreeModel          *tree_model,
 105                                                          GtkTreeIter           *iter,
 106                                                          GtkTreeIter           *child);
 107 static void         gtk_tree_model_sort_ref_node        (GtkTreeModel          *tree_model,
 108                                                          GtkTreeIter           *iter);
 109 static void         gtk_tree_model_sort_unref_node      (GtkTreeModel          *tree_model,
 110                                                          GtkTreeIter           *iter);
 111
 112 /* sortable */
 113 static gboolean gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable        *sortable,
 114                                                         gint                   *sort_column_id,
 115                                                         GtkTreeSortOrder       *order);
 116 static void     gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable        *sortable,
 117                                                         gint                    sort_column_id,
 118                                                         GtkTreeSortOrder        order);
 119 static void     gtk_tree_model_sort_set_sort_func      (GtkTreeSortable        *sortable,
 120                                                         gint                    sort_column_id,
 121                                                         GtkTreeIterCompareFunc  func,
 122                                                         gpointer                data,
 123                                                         GtkDestroyNotify        destroy);
 124
 125 /* Internal functions */
 126 static gint         gtk_tree_model_sort_array_find_insert (GtkTreeModelSort *tree_model_sort,
 127                                                            GArray           *array,
 128                                                            GtkTreeIter      *iter,
 129                                                            gboolean          skip_sort_elt);
 130 static GtkTreePath *gtk_tree_model_sort_convert_path_real (GtkTreeModelSort *tree_model_sort,
 131                                                            GtkTreePath      *child_path,
 132                                                            gboolean          build_children);
 133 static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,
 134                                                            SortElt          *place);
 135 static void         gtk_tree_model_sort_free_level        (GArray           *array);
 136
 137
 138
 139 GType
 140 gtk_tree_model_sort_get_type (void)
 141 {
 142   static GType tree_model_sort_type = 0;
 143
 144   if (!tree_model_sort_type)
 145     {
 146       static const GTypeInfo tree_model_sort_info =
 147       {
 148         sizeof (GtkTreeModelSortClass),
 149         NULL,           /* base_init */
 150         NULL,           /* base_finalize */
 151         (GClassInitFunc) gtk_tree_model_sort_class_init,
 152         NULL,           /* class_finalize */
 153         NULL,           /* class_data */
 154         sizeof (GtkTreeModelSort),
 155         0,              /* n_preallocs */
 156         (GInstanceInitFunc) gtk_tree_model_sort_init
 157       };
 158
 159       static const GInterfaceInfo tree_model_info =
 160       {
 161         (GInterfaceInitFunc) gtk_tree_model_sort_tree_model_init,
 162         NULL,
 163         NULL
 164       };
 165
 166       static const GInterfaceInfo sortable_info =
 167       {
 168         (GInterfaceInitFunc) gtk_tree_model_sort_tree_sortable_init,
 169         NULL,
 170         NULL
 171       };
 172
 173       tree_model_sort_type = g_type_register_static (G_TYPE_OBJECT, "GtkTreeModelSort", &tree_model_sort_info, 0);
 174       g_type_add_interface_static (tree_model_sort_type,
 175                                    GTK_TYPE_TREE_MODEL,
 176                                    &tree_model_info);
 177
 178       g_type_add_interface_static (tree_model_sort_type,
 179                                    GTK_TYPE_TREE_SORTABLE,
 180                                    &sortable_info);
 181     }
 182
 183   return tree_model_sort_type;
 184 }
 185
 186 static void
 187 gtk_tree_model_sort_class_init (GtkTreeModelSortClass *tree_model_sort_class)
 188 {
 189   GObjectClass *object_class;
 190
 191   object_class = (GObjectClass *) tree_model_sort_class;
 192
 193   object_class->finalize = gtk_tree_model_sort_finalize;
 194 }
 195
 196 static void
 197 gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
 198 {
 199   iface->get_n_columns = gtk_tree_model_sort_get_n_columns;
 200   iface->get_column_type = gtk_tree_model_sort_get_column_type;
 201   iface->get_iter = gtk_tree_model_sort_get_iter;
 202   iface->get_path = gtk_tree_model_sort_get_path;
 203   iface->get_value = gtk_tree_model_sort_get_value;
 204   iface->iter_next = gtk_tree_model_sort_iter_next;
 205   iface->iter_children = gtk_tree_model_sort_iter_children;
 206   iface->iter_has_child = gtk_tree_model_sort_iter_has_child;
 207   iface->iter_n_children = gtk_tree_model_sort_iter_n_children;
 208   iface->iter_nth_child = gtk_tree_model_sort_iter_nth_child;
 209   iface->iter_parent = gtk_tree_model_sort_iter_parent;
 210   iface->ref_node = gtk_tree_model_sort_ref_node;
 211   iface->unref_node = gtk_tree_model_sort_unref_node;
 212 }
 213
 214 static void
 215 gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface *iface)
 216 {
 217   iface->get_sort_column_id = gtk_tree_model_sort_get_sort_column_id;
 218   iface->set_sort_column_id = gtk_tree_model_sort_set_sort_column_id;
 219   iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
 220 }
 221
 222 static void
 223 gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
 224 {
 225   tree_model_sort->sort_column_id = -1;
 226   tree_model_sort->stamp = g_random_int ();
 227 }
 228
 229 GtkTreeModel *
 230 gtk_tree_model_sort_new (void)
 231 {
 232   return GTK_TREE_MODEL (g_object_new (gtk_tree_model_sort_get_type (), NULL));
 233 }
 234
 235 GtkTreeModel *
 236 gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
 237 {
 238   GtkTreeModel *retval;
 239
 240   retval = gtk_tree_model_sort_new ();
 241   gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
 242
 243   return retval;
 244 }
 245
 246 /**
 247  * gtk_tree_model_sort_set_model:
 248  * @tree_model_sort: The #GtkTreeModelSort.
 249  * @child_model: A #GtkTreeModel, or NULL.
 250  *
 251  * Sets the model of @tree_model_sort to be @model.  If @model is NULL, then the
 252  * old model is unset.
 253  **/
 254 void
 255 gtk_tree_model_sort_set_model (GtkTreeModelSort *tree_model_sort,
 256                                GtkTreeModel     *child_model)
 257 {
 258   g_return_if_fail (tree_model_sort != NULL);
 259   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
 260
 261   if (child_model)
 262     g_object_ref (G_OBJECT (child_model));
 263
 264   if (tree_model_sort->child_model)
 265     {
 266       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
 267                                    tree_model_sort->changed_id);
 268       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
 269                                    tree_model_sort->inserted_id);
 270       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
 271                                    tree_model_sort->has_child_toggled_id);
 272       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
 273                                    tree_model_sort->deleted_id);
 274
 275       g_object_unref (G_OBJECT (tree_model_sort->child_model));
 276     }
 277
 278   if (tree_model_sort->root)
 279     {
 280       gtk_tree_model_sort_free_level (tree_model_sort->root);
 281       tree_model_sort->root = NULL;
 282     }
 283
 284   if (tree_model_sort->sort_list)
 285     {
 286       _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
 287       tree_model_sort->sort_list = NULL;
 288     }
 289
 290   tree_model_sort->child_model = child_model;
 291   if (child_model)
 292     {
 293       GType *types;
 294       gint i, n_columns;
 295
 296       tree_model_sort->changed_id =
 297         g_signal_connect (child_model,
 298                           "range_changed",
 299                           G_CALLBACK (gtk_tree_model_sort_range_changed),
 300                           tree_model_sort);
 301       tree_model_sort->inserted_id =
 302         g_signal_connect (child_model,
 303                           "inserted",
 304                           G_CALLBACK (gtk_tree_model_sort_inserted),
 305                           tree_model_sort);
 306       tree_model_sort->has_child_toggled_id =
 307         g_signal_connect (child_model,
 308                           "has_child_toggled",
 309                           G_CALLBACK (gtk_tree_model_sort_has_child_toggled),
 310                           tree_model_sort);
 311       tree_model_sort->deleted_id =
 312         g_signal_connect (child_model,
 313                           "deleted",
 314                           G_CALLBACK (gtk_tree_model_sort_deleted),
 315                           tree_model_sort);
 316
 317       tree_model_sort->flags = gtk_tree_model_get_flags (child_model);
 318       n_columns = gtk_tree_model_get_n_columns (child_model);
 319       types = g_new (GType, n_columns);
 320       for (i = 0; i < n_columns; i++)
 321         types[i] = gtk_tree_model_get_column_type (child_model, i);
 322       tree_model_sort->sort_list = _gtk_tree_data_list_header_new (n_columns, types);
 323       g_free (types);
 324     }
 325 }
 326
 327 /**
 328  * gtk_tree_model_sort_get_model:
 329  * @tree_model: a #GtkTreeModelSort
 330  *
 331  * Returns the model the #GtkTreeModelSort is sorting.
 332  *
 333  * Return value: the "child model" being sorted
 334  **/
 335 GtkTreeModel*
 336 gtk_tree_model_sort_get_model (GtkTreeModelSort  *tree_model)
 337 {
 338   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
 339
 340   return tree_model->child_model;
 341 }
 342
 343 /**
 344  * gtk_tree_model_sort_convert_path:
 345  * @tree_model_sort: The #GtkTreeModelSort.
 346  * @child_path: A #GtkTreePath, relative to the child model.
 347  *
 348  * Converts the @child_path to a new path, relative to the sorted position.  In other
 349  * words, the value found in the @tree_model_sort ->child_model at the @child_path, is
 350  * identical to that found in the @tree_model_sort and the return value.
 351  *
 352  * Return value: A new path, or NULL if @child_path does not exist in @tree_model_sort
 353  * ->child_model.
 354  **/
 355 GtkTreePath *
 356 gtk_tree_model_sort_convert_path (GtkTreeModelSort *tree_model_sort,
 357                                   GtkTreePath      *child_path)
 358 {
 359   g_return_val_if_fail (tree_model_sort != NULL, NULL);
 360   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
 361   g_return_val_if_fail (child_path != NULL, NULL);
 362
 363   return gtk_tree_model_sort_convert_path_real (tree_model_sort, child_path, TRUE);
 364 }
 365
 366 static void
 367 gtk_tree_model_sort_finalize (GObject *object)
 368 {
 369   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
 370
 371   if (tree_model_sort->root)
 372     gtk_tree_model_sort_free_level (tree_model_sort->root);
 373
 374   if (tree_model_sort->child_model)
 375     {
 376       g_object_unref (G_OBJECT (tree_model_sort->child_model));
 377       tree_model_sort->child_model = NULL;
 378     }
 379   if (tree_model_sort->sort_list)
 380     {
 381       _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
 382       tree_model_sort->sort_list = NULL;
 383     }
 384 }
 385
 386 static void
 387 gtk_tree_model_sort_range_changed (GtkTreeModel *s_model,
 388                                    GtkTreePath  *s_start_path,
 389                                    GtkTreeIter  *s_start_iter,
 390                                    GtkTreePath  *s_end_path,
 391                                    GtkTreeIter  *s_end_iter,
 392                                    gpointer      data)
 393 {
 394   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 395   GtkTreePath *path;
 396   GtkTreeIter iter;
 397   SortElt *elt;
 398   GArray *array;
 399   gboolean free_s_path = FALSE;
 400   gint index;
 401
 402   g_return_if_fail (s_start_path != NULL || s_start_iter != NULL);
 403
 404   if (s_start_path == NULL)
 405     {
 406       free_s_path = TRUE;
 407       s_start_path = gtk_tree_model_get_path (s_model, s_start_iter);
 408     }
 409
 410   path = gtk_tree_model_sort_convert_path_real (tree_model_sort, s_start_path, FALSE);
 411   if (path == NULL)
 412     {
 413       if (free_s_path)
 414         gtk_tree_path_free (s_start_path);
 415       return;
 416     }
 417
 418   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 419   elt = (SortElt *) iter.user_data;
 420   array = get_array (elt, tree_model_sort);
 421
 422   /* FIXME: as an optimization for when the column other then the one we're
 423    * sorting is changed, we can check the prev and next element to see if
 424    * they're different.
 425    */
 426
 427   /* Now we need to resort things. */
 428   index = gtk_tree_model_sort_array_find_insert (tree_model_sort,
 429                                                  array,
 430                                                  (GtkTreeIter *) elt,
 431                                                  TRUE);
 432
 433   gtk_tree_model_range_changed (GTK_TREE_MODEL (data), path, &iter, path, &iter);
 434
 435   gtk_tree_path_free (path);
 436   if (free_s_path)
 437     gtk_tree_path_free (s_start_path);
 438 }
 439
 440 /* FALSE if the value was inserted, TRUE otherwise */
 441 static gboolean
 442 gtk_tree_model_sort_insert_value (GtkTreeModelSort *sort,
 443                                   GtkTreePath      *s_path,
 444                                   GtkTreeIter      *s_iter)
 445 {
 446   GtkTreePath *tmp_path;
 447   GArray *array;
 448   gint index;
 449   GtkTreeIter iter;
 450   SortElt elt;
 451   gint offset;
 452   gint j;
 453   SortElt *tmp_elt;
 454   offset = gtk_tree_path_get_indices (s_path)[gtk_tree_path_get_depth (s_path) - 1];
 455
 456   elt.iter = *s_iter;
 457   elt.ref = 0;
 458   elt.children = NULL;
 459   elt.offset = offset;
 460
 461   tmp_path = gtk_tree_path_copy (s_path);
 462
 463   if (gtk_tree_path_up (tmp_path))
 464     {
 465       GtkTreePath *parent_path;
 466
 467       parent_path = gtk_tree_model_sort_convert_path_real (sort, tmp_path, FALSE);
 468       if (parent_path == NULL)
 469         {
 470           gtk_tree_path_free (tmp_path);
 471           return FALSE;
 472         }
 473       gtk_tree_model_get_iter (GTK_TREE_MODEL (sort), &iter, parent_path);
 474       elt.parent = ((SortElt *) iter.user_data);
 475       array = ((SortElt *) iter.user_data)->children;
 476       gtk_tree_path_free (parent_path);
 477       if (array == NULL)
 478         {
 479           gtk_tree_path_free (tmp_path);
 480           return FALSE;
 481         }
 482     }
 483   else
 484     {
 485       if (sort->root == NULL)
 486         sort->root = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), 1);
 487       array = sort->root;
 488       elt.parent = NULL;
 489     }
 490   gtk_tree_path_free (tmp_path);
 491
 492   index = gtk_tree_model_sort_array_find_insert (sort, array, (GtkTreeIter *) &elt, FALSE);
 493
 494   g_array_insert_vals (array, index, &elt, 1);
 495
 496   /* update all the larger offsets */
 497   tmp_elt = (SortElt *) array->data;
 498   for (j = 0; j < array->len; j++, tmp_elt++)
 499         {
 500           if ((tmp_elt->offset >= offset) &&
 501               j != index)
 502             tmp_elt->offset ++;
 503         }
 504
 505   return TRUE;
 506 }
 507
 508 static void
 509 gtk_tree_model_sort_inserted (GtkTreeModel *s_model,
 510                               GtkTreePath  *s_path,
 511                               GtkTreeIter  *s_iter,
 512                               gpointer      data)
 513 {
 514   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 515   GtkTreePath *path;
 516   GtkTreeIter iter;
 517
 518   g_return_if_fail (s_path != NULL || s_iter != NULL);
 519
 520   if (s_path == NULL)
 521     s_path = gtk_tree_model_get_path (s_model, s_iter);
 522
 523   if (!(tree_model_sort->flags & GTK_TREE_MODEL_ITERS_PERSIST))
 524     {
 525       gtk_tree_model_sort_free_level ((GArray *) tree_model_sort->root);
 526       tree_model_sort->root = NULL;
 527     }
 528   else
 529     {
 530       GtkTreeIter real_s_iter;
 531
 532       if (s_iter == NULL)
 533         gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
 534       else
 535         real_s_iter = (* s_iter);
 536
 537       if (!gtk_tree_model_sort_insert_value (tree_model_sort, s_path, &real_s_iter))
 538         return;
 539     }
 540
 541   path = gtk_tree_model_sort_convert_path_real (tree_model_sort, s_path, FALSE);
 542   if (path == NULL)
 543     return;
 544
 545   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 546   g_signal_emit_by_name (G_OBJECT (data), "inserted", path, &iter);
 547   gtk_tree_path_free (path);
 548 }
 549
 550 static void
 551 gtk_tree_model_sort_has_child_toggled (GtkTreeModel *s_model,
 552                                        GtkTreePath  *s_path,
 553                                        GtkTreeIter  *s_iter,
 554                                        gpointer      data)
 555 {
 556   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 557   GtkTreePath *path;
 558   GtkTreeIter iter;
 559   gboolean free_s_path = FALSE;
 560
 561   g_return_if_fail (s_path != NULL || s_iter != NULL);
 562
 563   if (!(tree_model_sort->flags & GTK_TREE_MODEL_ITERS_PERSIST))
 564     {
 565       gtk_tree_model_sort_free_level ((GArray *)tree_model_sort->root);
 566       tree_model_sort->root = NULL;
 567     }
 568
 569   if (s_path == NULL)
 570     {
 571       s_path = gtk_tree_model_get_path (s_model, s_iter);
 572       free_s_path = TRUE;
 573     }
 574
 575   path = gtk_tree_model_sort_convert_path_real (tree_model_sort, s_path, FALSE);
 576   if (path == NULL)
 577     return;
 578   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 579   g_signal_emit_by_name (G_OBJECT (data),
 580                            "has_child_toggled",
 581                            path, &iter);
 582   gtk_tree_path_free (path);
 583   if (free_s_path)
 584     gtk_tree_path_free (s_path);
 585 }
 586
 587 static void
 588 gtk_tree_model_sort_deleted (GtkTreeModel *s_model,
 589                              GtkTreePath  *s_path,
 590                              gpointer      data)
 591 {
 592   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 593   GtkTreePath *path;
 594
 595   g_return_if_fail (s_path != NULL);
 596   path = gtk_tree_model_sort_convert_path (tree_model_sort, s_path);
 597   g_return_if_fail (path != NULL);
 598
 599   if (!(tree_model_sort->flags & GTK_TREE_MODEL_ITERS_PERSIST))
 600     {
 601       gtk_tree_model_sort_free_level ((GArray *)tree_model_sort->root);
 602       tree_model_sort->root = NULL;
 603     }
 604   else
 605     {
 606       GArray *array;
 607       GtkTreeIter iter;
 608       SortElt *elt;
 609       gint offset;
 610       gint i;
 611
 612       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort), &iter, path);
 613       elt = (SortElt *) iter.user_data;
 614       offset = elt->offset;
 615       array = get_array (elt, tree_model_sort);
 616       if (array->len == 1)
 617         {
 618           if (((SortElt *)array->data)->parent == NULL)
 619             tree_model_sort->root = NULL;
 620           else
 621             (((SortElt *)array->data)->parent)->children = NULL;
 622           gtk_tree_model_sort_free_level (array);
 623         }
 624       else
 625         {
 626           g_array_remove_index (array, elt - ((SortElt *) array->data));
 627
 628           for (i = 0; i < array->len; i++)
 629             {
 630               elt = & (g_array_index (array, SortElt, i));
 631               if (elt->offset > offset)
 632                 elt->offset--;
 633             }
 634         }
 635     }
 636
 637   tree_model_sort->stamp++;
 638   g_signal_emit_by_name (G_OBJECT (data), "deleted", path);
 639   gtk_tree_path_free (path);
 640 }
 641
 642 static gint
 643 gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
 644 {
 645   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
 646
 647   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
 648
 649   if (tree_model_sort->child_model == 0)
 650     return 0;
 651
 652   return gtk_tree_model_get_n_columns (GTK_TREE_MODEL_SORT (tree_model)->child_model);
 653 }
 654
 655 static GType
 656 gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
 657                                      gint          index)
 658 {
 659   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
 660   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
 661
 662   return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
 663 }
 664
 665 static gboolean
 666 gtk_tree_model_sort_get_iter_helper (GtkTreeModelSort *tree_model_sort,
 667                                      GArray       *array,
 668                                      GtkTreeIter  *iter,
 669                                      gint          depth,
 670                                      GtkTreePath  *path)
 671 {
 672   SortElt *elt;
 673
 674   if (array == NULL)
 675     return FALSE;
 676
 677   if (gtk_tree_path_get_indices (path)[depth] > array->len)
 678     return FALSE;
 679
 680   elt = & (g_array_index (array, SortElt, gtk_tree_path_get_indices (path)[depth]));
 681
 682   if (depth == gtk_tree_path_get_depth (path) - 1)
 683     {
 684       iter->stamp = tree_model_sort->stamp;
 685       iter->user_data = elt;
 686       return TRUE;
 687     }
 688
 689   if (elt->children != NULL)
 690     return gtk_tree_model_sort_get_iter_helper (tree_model_sort,
 691                                                 elt->children,
 692                                                 iter,
 693                                                 depth + 1,
 694                                                 path);
 695
 696   if (gtk_tree_model_iter_has_child (tree_model_sort->child_model,
 697                                      &(elt->iter)))
 698
 699     gtk_tree_model_sort_build_level (tree_model_sort, elt);
 700
 701   return gtk_tree_model_sort_get_iter_helper (tree_model_sort,
 702                                               elt->children,
 703                                               iter,
 704                                               depth + 1,
 705                                               path);
 706 }
 707
 708 static gboolean
 709 gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
 710                               GtkTreeIter  *iter,
 711                               GtkTreePath  *path)
 712 {
 713   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 714   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 715
 716   if (GTK_TREE_MODEL_SORT (tree_model)->root == NULL)
 717     gtk_tree_model_sort_build_level (GTK_TREE_MODEL_SORT (tree_model), NULL);
 718
 719   return gtk_tree_model_sort_get_iter_helper (GTK_TREE_MODEL_SORT (tree_model),
 720                                               GTK_TREE_MODEL_SORT (tree_model)->root,
 721                                               iter, 0, path);
 722 }
 723
 724 static GtkTreePath *
 725 gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
 726                               GtkTreeIter  *iter)
 727 {
 728   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
 729   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
 730
 731   return gtk_tree_model_get_path (GTK_TREE_MODEL_SORT (tree_model)->child_model, iter);
 732 }
 733
 734 static void
 735 gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
 736                                GtkTreeIter  *iter,
 737                                gint          column,
 738                                GValue        *value)
 739 {
 740   SortElt *elt;
 741
 742   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
 743   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
 744   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);
 745
 746   elt = iter->user_data;
 747
 748   gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *)elt, column, value);
 749 }
 750
 751 static gboolean
 752 gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
 753                                GtkTreeIter  *iter)
 754 {
 755   GArray *array;
 756   SortElt *elt;
 757
 758   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 759   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 760   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);
 761
 762   elt = iter->user_data;
 763   array = get_array (elt, tree_model);
 764
 765   if (elt - ((SortElt*) array->data) >=  array->len - 1)
 766     {
 767       iter->stamp = 0;
 768       return FALSE;
 769     }
 770   iter->user_data = elt + 1;
 771   return TRUE;
 772 }
 773
 774 static gboolean
 775 gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
 776                                    GtkTreeIter  *iter,
 777                                    GtkTreeIter  *parent)
 778 {
 779   SortElt *elt;
 780
 781   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 782   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 783
 784   if (parent)
 785     g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
 786
 787   if (parent)
 788     elt = parent->user_data;
 789   else
 790     elt = (SortElt *) ((GArray *)GTK_TREE_MODEL_SORT (tree_model)->root)->data;
 791
 792   if (elt == NULL)
 793     return FALSE;
 794
 795   if (elt->children == NULL &&
 796       gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *)elt))
 797     gtk_tree_model_sort_build_level (GTK_TREE_MODEL_SORT (tree_model), elt);
 798
 799   if (elt->children == NULL)
 800     return FALSE;
 801
 802   iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
 803   iter->user_data = elt->children->data;
 804
 805   return TRUE;
 806 }
 807
 808 static gboolean
 809 gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
 810                                     GtkTreeIter  *iter)
 811 {
 812   SortElt *elt;
 813
 814   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 815   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 816   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);
 817
 818   elt = iter->user_data;
 819   if (elt->children)
 820     return TRUE;
 821
 822   return gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *) elt);
 823 }
 824
 825 static gint
 826 gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
 827                                      GtkTreeIter  *iter)
 828 {
 829   SortElt *elt;
 830
 831   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
 832   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
 833   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, 0);
 834
 835   elt = iter->user_data;
 836   if (elt->children)
 837     return elt->children->len;
 838
 839   return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *) elt);
 840 }
 841
 842
 843 static gboolean
 844 gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
 845                                     GtkTreeIter  *iter,
 846                                     GtkTreeIter  *parent,
 847                                     gint          n)
 848 {
 849   SortElt *elt;
 850
 851   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 852   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 853   if (parent)
 854     g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
 855
 856   elt = iter->user_data;
 857
 858
 859   if (elt->children == NULL)
 860     {
 861       if (gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *)elt))
 862         gtk_tree_model_sort_build_level (GTK_TREE_MODEL_SORT (tree_model), elt);
 863       else
 864         return FALSE;
 865     }
 866
 867   if (elt->children == NULL)
 868     return FALSE;
 869
 870   if (n >= elt->children->len)
 871     return FALSE;
 872
 873   iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
 874   iter->user_data = &g_array_index (elt->children, SortElt, n);
 875
 876   return TRUE;
 877 }
 878
 879 static gboolean
 880 gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
 881                                  GtkTreeIter  *iter,
 882                                  GtkTreeIter  *child)
 883 {
 884   SortElt *elt;
 885
 886   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 887   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 888   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == child->stamp, FALSE);
 889
 890   elt = iter->user_data;
 891   if (elt->parent)
 892     {
 893       iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
 894       iter->user_data = elt->parent;
 895
 896       return TRUE;
 897     }
 898   return FALSE;
 899 }
 900
 901 static void
 902 gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
 903                               GtkTreeIter  *iter)
 904 {
 905 }
 906
 907 static void
 908 gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
 909                                 GtkTreeIter  *iter)
 910 {
 911
 912
 913 }
 914
 915 static gboolean
 916 gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable  *sortable,
 917                                         gint             *sort_column_id,
 918                                         GtkTreeSortOrder *order)
 919 {
 920   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
 921
 922   g_return_val_if_fail (sortable != NULL, FALSE);
 923   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (sortable), FALSE);
 924
 925   if (tree_model_sort->sort_column_id == -1)
 926     return FALSE;
 927
 928   if (sort_column_id)
 929     *sort_column_id = tree_model_sort->sort_column_id;
 930   if (order)
 931     *order = tree_model_sort->order;
 932
 933   return TRUE;
 934 }
 935
 936 static void
 937 gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable  *sortable,
 938                                          gint              sort_column_id,
 939                                          GtkTreeSortOrder  order)
 940 {
 941   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
 942   GList *list;
 943
 944   g_return_if_fail (sortable != NULL);
 945   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (sortable));
 946
 947   for (list = tree_model_sort->sort_list; list; list = list->next)
 948     {
 949       GtkTreeDataSortHeader *header = (GtkTreeDataSortHeader*) list->data;
 950       if (header->sort_column_id == sort_column_id)
 951         break;
 952     }
 953   g_return_if_fail (list != NULL);
 954
 955   if ((tree_model_sort->sort_column_id == sort_column_id) &&
 956       (tree_model_sort->order == order))
 957     return;
 958
 959   tree_model_sort->sort_column_id = sort_column_id;
 960   tree_model_sort->order = order;
 961
 962   /*  if (tree_model_sort->sort_column_id >= 0)
 963       gtk_list_store_sort (tree_model_sort);*/
 964
 965   gtk_tree_sortable_sort_column_changed (sortable);
 966
 967 }
 968
 969 static void
 970 gtk_tree_model_sort_set_sort_func (GtkTreeSortable        *sortable,
 971                                    gint                    sort_column_id,
 972                                    GtkTreeIterCompareFunc  func,
 973                                    gpointer                data,
 974                                    GtkDestroyNotify        destroy)
 975 {
 976   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
 977   GtkTreeDataSortHeader *header = NULL;
 978   GList *list;
 979
 980   g_return_if_fail (sortable != NULL);
 981   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (sortable));
 982   g_return_if_fail (func != NULL);
 983
 984   for (list = tree_model_sort->sort_list; list; list = list->next)
 985     {
 986       header = (GtkTreeDataSortHeader*) list->data;
 987       if (header->sort_column_id == sort_column_id)
 988         break;
 989     }
 990
 991   if (header == NULL)
 992     {
 993       header = g_new0 (GtkTreeDataSortHeader, 1);
 994       header->sort_column_id = sort_column_id;
 995       tree_model_sort->sort_list = g_list_append (tree_model_sort->sort_list, header);
 996     }
 997
 998   if (header->destroy)
 999     (* header->destroy) (header->data);
1000
1001   header->func = func;
1002   header->data = data;
1003   header->destroy = destroy;
1004 }
1005
1006 /* Internal functions */
1007
1008 static gint
1009 gtk_tree_model_sort_array_find_insert (GtkTreeModelSort *tree_model_sort,
1010                                        GArray           *array,
1011                                        GtkTreeIter      *iter,
1012                                        gboolean          skip_sort_elt)
1013 {
1014   gint middle;
1015   gint cmp;
1016   GValueCompareFunc func;
1017   GValue value = {0, };
1018   GValue tmp_value = {0, };
1019   SortElt *tmp_elt;
1020
1021   func = NULL; //(GValueCompareFunc) gtk_tree_model_sort_get_func (tree_model_sort);
1022
1023   g_return_val_if_fail (func != NULL, 0);
1024
1025   gtk_tree_model_get_value (tree_model_sort->child_model, iter, tree_model_sort->sort_column_id, &value);
1026
1027   for (middle = 0; middle < array->len; middle++)
1028     {
1029       tmp_elt = &(g_array_index (array, SortElt, middle));
1030       if (!skip_sort_elt &&
1031           (SortElt *) iter == tmp_elt)
1032           continue;
1033       gtk_tree_model_get_value (tree_model_sort->child_model,
1034                                 (GtkTreeIter *) tmp_elt,
1035                                 tree_model_sort->sort_column_id,
1036                                 &tmp_value);
1037
1038       cmp = ((func) (&value, &tmp_value));
1039       g_value_unset (&tmp_value);
1040
1041       if (cmp >= 0)
1042         break;
1043     }
1044   return middle;
1045 }
1046
1047
1048 static GtkTreePath *
1049 gtk_tree_model_sort_convert_path_real (GtkTreeModelSort *tree_model_sort,
1050                                        GtkTreePath      *child_path,
1051                                        gboolean          build_children)
1052 {
1053   GtkTreePath *retval;
1054   GArray *array;
1055   gint *indices;
1056   gint i = 0;
1057
1058   if (tree_model_sort->root == NULL)
1059     {
1060       if (build_children)
1061         gtk_tree_model_sort_build_level (tree_model_sort, NULL);
1062       else
1063         return FALSE;
1064     }
1065
1066   retval = gtk_tree_path_new ();
1067   array = (GArray *) tree_model_sort->root;
1068   indices = gtk_tree_path_get_indices (child_path);
1069
1070   do
1071     {
1072       SortElt *elt;
1073       gboolean found = FALSE;
1074       gint j;
1075
1076       if ((array->len < indices[i]) || (array == NULL))
1077         {
1078           gtk_tree_path_free (retval);
1079           return NULL;
1080         }
1081
1082       elt = (SortElt *) array->data;
1083       for (j = 0; j < array->len; j++, elt++)
1084         {
1085           if (elt->offset == indices[i])
1086             {
1087               found = TRUE;
1088               break;
1089             }
1090         }
1091       if (! found)
1092         {
1093           gtk_tree_path_free (retval);
1094           return NULL;
1095         }
1096
1097       gtk_tree_path_prepend_index (retval, j);
1098
1099       i++;
1100
1101       if (i == gtk_tree_path_get_depth (child_path))
1102         break;
1103
1104       if (elt->children == NULL)
1105         {
1106           if (build_children)
1107             {
1108               gtk_tree_path_prepend_index (retval, j);
1109               gtk_tree_model_sort_build_level (tree_model_sort, elt);
1110             }
1111           else
1112             {
1113               gtk_tree_path_free (retval);
1114               return NULL;
1115             }
1116         }
1117     }
1118   while (TRUE);
1119
1120   return retval;
1121 }
1122
1123 static void
1124 gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
1125                                  SortElt          *place)
1126 {
1127   gint n, i = 0;
1128   GArray *children;
1129   GtkTreeIter *parent_iter = NULL;
1130   GtkTreeIter iter;
1131   SortElt elt;
1132   SortData sort_data;
1133
1134   if (place)
1135     parent_iter = & (place->iter);
1136
1137
1138   n = gtk_tree_model_iter_n_children (tree_model_sort->child_model, parent_iter);
1139
1140   if (n == 0)
1141     return;
1142
1143   children = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), n);
1144
1145   if (place)
1146     place->children = children;
1147   else
1148     tree_model_sort->root = children;
1149
1150   gtk_tree_model_iter_children (tree_model_sort->child_model,
1151                                 &iter,
1152                                 parent_iter);
1153
1154   do
1155     {
1156       elt.iter = iter;
1157       elt.parent = place;
1158       elt.children = NULL;
1159       elt.ref = 0;
1160       elt.offset = i;
1161
1162       g_array_append_vals (children, &elt, 1);
1163       i++;
1164     }
1165   while (gtk_tree_model_iter_next (tree_model_sort->child_model, &iter));
1166 }
1167
1168 static void
1169 gtk_tree_model_sort_free_level (GArray *array)
1170 {
1171   gint i;
1172
1173   if (array == NULL)
1174     return;
1175
1176   for (i = 0; i < array->len; i++)
1177     {
1178       SortElt *elt;
1179
1180       elt = &g_array_index (array, SortElt, i);
1181       if (elt->children)
1182         gtk_tree_model_sort_free_level (array);
1183     }
1184
1185   g_array_free (array, TRUE);
1186 }
1187
1188 /* DEAD CODE */
1189
1190 #if 0
1191   /* FIXME: we can, as we are an array, do binary search to find the correct
1192    * location to insert the element.  However, I'd rather get it working.  The
1193    * below is quite wrong, but a step in the right direction.
1194    */
1195   low = 0;
1196   high = array->len;
1197   middle = (low + high)/2;
1198
1199   /* Insert the value into the array */
1200   while (low != high)
1201     {
1202       gint cmp;
1203       tmp_elt = &(g_array_index (array, SortElt, middle));
1204       gtk_tree_model_get_value (sort->child_model,
1205                                 (GtkTreeIter *) tmp_elt,
1206                                 sort->sort_column_id,
1207                                 &tmp_value);
1208
1209       cmp = ((func) (&tmp_value, &s_value));
1210       g_value_unset (&tmp_value);
1211
1212       if (cmp < 0)
1213         high = middle;
1214       else if (cmp > 0)
1215         low = middle;
1216       else if (cmp == 0)
1217         break;
1218       middle = (low + high)/2;
1219     }
1220 #endif