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

   1 /* gtktreemodelsort.c
   2  * Copyright (C) 2000,2001  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
   3  * Copyright (C) 2001,2002  Kristian Rietveld <kris@gtk.org>
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Library General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License along with this library; if not, write to the
  17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18  * Boston, MA 02111-1307, USA.
  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 /* ITER FORMAT:
  28  *
  29  * iter->stamp = tree_model_sort->stamp
  30  * iter->user_data = SortLevel
  31  * iter->user_data2 = SortElt
  32  */
  33
  34 /* WARNING: this code is dangerous, can cause sleepless nights,
  35  * can cause your dog to die among other bad things
  36  *
  37  * we warned you and we're not liable for any head injuries.
  38  */
  39
  40 #include "gtktreemodelsort.h"
  41 #include "gtktreesortable.h"
  42 #include "gtktreestore.h"
  43 #include "gtksignal.h"
  44 #include "gtktreedatalist.h"
  45 #include <string.h>
  46 #include "gtkintl.h"
  47
  48 typedef struct _SortElt SortElt;
  49 typedef struct _SortLevel SortLevel;
  50 typedef struct _SortData SortData;
  51 typedef struct _SortTuple SortTuple;
  52
  53 struct _SortElt
  54 {
  55   GtkTreeIter  iter;
  56   SortLevel   *children;
  57   gint         offset;
  58   gint         ref_count;
  59   gint         zero_ref_count;
  60 };
  61
  62 struct _SortLevel
  63 {
  64   GArray    *array;
  65   gint       ref_count;
  66   SortElt   *parent_elt;
  67   SortLevel *parent_level;
  68 };
  69
  70 struct _SortData
  71 {
  72   GtkTreeModelSort *tree_model_sort;
  73   GtkTreePath *parent_path;
  74   gint parent_path_depth;
  75   gint *parent_path_indices;
  76   GtkTreeIterCompareFunc sort_func;
  77   gpointer sort_data;
  78 };
  79
  80 struct _SortTuple
  81 {
  82   SortElt   *elt;
  83   gint       offset;
  84 };
  85
  86 /* Properties */
  87 enum {
  88   PROP_0,
  89   /* Construct args */
  90   PROP_MODEL
  91 };
  92
  93
  94
  95 #define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) \
  96         (((GtkTreeModelSort *)tree_model_sort)->child_flags&GTK_TREE_MODEL_ITERS_PERSIST)
  97 #define SORT_ELT(sort_elt) ((SortElt *)sort_elt)
  98 #define SORT_LEVEL(sort_level) ((SortLevel *)sort_level)
  99
 100 #define GET_CHILD_ITER(tree_model_sort,child_iter,sort_iter) gtk_tree_model_sort_convert_iter_to_child_iter(GTK_TREE_MODEL_SORT (tree_model_sort), child_iter, sort_iter);
 101
 102 /* general (object/interface init, etc) */
 103 static void gtk_tree_model_sort_init                  (GtkTreeModelSort      *tree_model_sort);
 104 static void gtk_tree_model_sort_class_init            (GtkTreeModelSortClass *tree_model_sort_class);
 105 static void gtk_tree_model_sort_tree_model_init       (GtkTreeModelIface     *iface);
 106 static void gtk_tree_model_sort_tree_sortable_init    (GtkTreeSortableIface  *iface);
 107 static void gtk_tree_model_sort_finalize              (GObject               *object);
 108 static void gtk_tree_model_sort_set_property          (GObject               *object,
 109                                                        guint                  prop_id,
 110                                                        const GValue          *value,
 111                                                        GParamSpec            *pspec);
 112 static void gtk_tree_model_sort_get_property          (GObject               *object,
 113                                                        guint                  prop_id,
 114                                                        GValue                *value,
 115                                                        GParamSpec            *pspec);
 116
 117 /* our signal handlers */
 118 static void gtk_tree_model_sort_row_changed           (GtkTreeModel          *model,
 119                                                        GtkTreePath           *start_path,
 120                                                        GtkTreeIter           *start_iter,
 121                                                        gpointer               data);
 122 static void gtk_tree_model_sort_row_inserted          (GtkTreeModel          *model,
 123                                                        GtkTreePath           *path,
 124                                                        GtkTreeIter           *iter,
 125                                                        gpointer               data);
 126 static void gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel          *model,
 127                                                        GtkTreePath           *path,
 128                                                        GtkTreeIter           *iter,
 129                                                        gpointer               data);
 130 static void gtk_tree_model_sort_row_deleted           (GtkTreeModel          *model,
 131                                                        GtkTreePath           *path,
 132                                                        gpointer               data);
 133 static void gtk_tree_model_sort_rows_reordered        (GtkTreeModel          *s_model,
 134                                                        GtkTreePath           *s_path,
 135                                                        GtkTreeIter           *s_iter,
 136                                                        gint                  *new_order,
 137                                                        gpointer               data);
 138
 139 /* TreeModel interface */
 140 static guint        gtk_tree_model_sort_get_flags          (GtkTreeModel          *tree_model);
 141 static gint         gtk_tree_model_sort_get_n_columns      (GtkTreeModel          *tree_model);
 142 static GType        gtk_tree_model_sort_get_column_type    (GtkTreeModel          *tree_model,
 143                                                             gint                   index);
 144 static gboolean     gtk_tree_model_sort_get_iter           (GtkTreeModel          *tree_model,
 145                                                             GtkTreeIter           *iter,
 146                                                             GtkTreePath           *path);
 147 static GtkTreePath *gtk_tree_model_sort_get_path           (GtkTreeModel          *tree_model,
 148                                                             GtkTreeIter           *iter);
 149 static void         gtk_tree_model_sort_get_value          (GtkTreeModel          *tree_model,
 150                                                             GtkTreeIter           *iter,
 151                                                             gint                   column,
 152                                                             GValue                *value);
 153 static gboolean     gtk_tree_model_sort_iter_next          (GtkTreeModel          *tree_model,
 154                                                             GtkTreeIter           *iter);
 155 static gboolean     gtk_tree_model_sort_iter_children      (GtkTreeModel          *tree_model,
 156                                                             GtkTreeIter           *iter,
 157                                                             GtkTreeIter           *parent);
 158 static gboolean     gtk_tree_model_sort_iter_has_child     (GtkTreeModel          *tree_model,
 159                                                             GtkTreeIter           *iter);
 160 static gint         gtk_tree_model_sort_iter_n_children    (GtkTreeModel          *tree_model,
 161                                                             GtkTreeIter           *iter);
 162 static gboolean     gtk_tree_model_sort_iter_nth_child     (GtkTreeModel          *tree_model,
 163                                                             GtkTreeIter           *iter,
 164                                                             GtkTreeIter           *parent,
 165                                                             gint                   n);
 166 static gboolean     gtk_tree_model_sort_iter_parent        (GtkTreeModel          *tree_model,
 167                                                             GtkTreeIter           *iter,
 168                                                             GtkTreeIter           *child);
 169 static void         gtk_tree_model_sort_ref_node           (GtkTreeModel          *tree_model,
 170                                                             GtkTreeIter           *iter);
 171 static void         gtk_tree_model_sort_real_unref_node    (GtkTreeModel          *tree_model,
 172                                                             GtkTreeIter           *iter,
 173                                                             gboolean               propagate_unref);
 174 static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
 175                                                             GtkTreeIter           *iter);
 176
 177 /* TreeSortable interface */
 178 static gboolean     gtk_tree_model_sort_get_sort_column_id    (GtkTreeSortable        *sortable,
 179                                                                gint                   *sort_column_id,
 180                                                                GtkSortType            *order);
 181 static void         gtk_tree_model_sort_set_sort_column_id    (GtkTreeSortable        *sortable,
 182                                                                gint                    sort_column_id,
 183                                                                GtkSortType        order);
 184 static void         gtk_tree_model_sort_set_sort_func         (GtkTreeSortable        *sortable,
 185                                                                gint                    sort_column_id,
 186                                                                GtkTreeIterCompareFunc  func,
 187                                                                gpointer                data,
 188                                                                GtkDestroyNotify        destroy);
 189 static void         gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
 190                                                                GtkTreeIterCompareFunc  func,
 191                                                                gpointer                data,
 192                                                                GtkDestroyNotify        destroy);
 193 static gboolean     gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable     *sortable);
 194
 195 /* Private functions (sort funcs, level handling and other utils) */
 196 static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,
 197                                                            SortLevel        *parent_level,
 198                                                            SortElt          *parent_elt);
 199 static void         gtk_tree_model_sort_free_level        (GtkTreeModelSort *tree_model_sort,
 200                                                            SortLevel        *sort_level);
 201 static void         gtk_tree_model_sort_increment_stamp   (GtkTreeModelSort *tree_model_sort);
 202 static void         gtk_tree_model_sort_sort_level        (GtkTreeModelSort *tree_model_sort,
 203                                                            SortLevel        *level,
 204                                                            gboolean          recurse,
 205                                                            gboolean          emit_reordered);
 206 static void         gtk_tree_model_sort_sort              (GtkTreeModelSort *tree_model_sort);
 207 static gint         gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
 208                                                            SortLevel        *level,
 209                                                            GtkTreeIter      *iter,
 210                                                            gboolean          skip_sort_elt);
 211 static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
 212                                                            SortLevel        *level,
 213                                                            GtkTreePath      *s_path,
 214                                                            GtkTreeIter      *s_iter);
 215 static GtkTreePath *gtk_tree_model_sort_elt_get_path      (SortLevel        *level,
 216                                                            SortElt          *elt);
 217 static void         gtk_tree_model_sort_set_model         (GtkTreeModelSort *tree_model_sort,
 218                                                            GtkTreeModel     *child_model);
 219 static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
 220                                                                          GtkTreePath      *child_path,
 221                                                                          gboolean          build_levels);
 222
 223 static GObjectClass *parent_class = NULL;
 224
 225 GType
 226 gtk_tree_model_sort_get_type (void)
 227 {
 228   static GType tree_model_sort_type = 0;
 229
 230   if (!tree_model_sort_type)
 231     {
 232       static const GTypeInfo tree_model_sort_info =
 233       {
 234         sizeof (GtkTreeModelSortClass),
 235         NULL,           /* base_init */
 236         NULL,           /* base_finalize */
 237         (GClassInitFunc) gtk_tree_model_sort_class_init,
 238         NULL,           /* class_finalize */
 239         NULL,           /* class_data */
 240         sizeof (GtkTreeModelSort),
 241         0,              /* n_preallocs */
 242         (GInstanceInitFunc) gtk_tree_model_sort_init
 243       };
 244
 245       static const GInterfaceInfo tree_model_info =
 246       {
 247         (GInterfaceInitFunc) gtk_tree_model_sort_tree_model_init,
 248         NULL,
 249         NULL
 250       };
 251
 252       static const GInterfaceInfo sortable_info =
 253       {
 254         (GInterfaceInitFunc) gtk_tree_model_sort_tree_sortable_init,
 255         NULL,
 256         NULL
 257       };
 258
 259       tree_model_sort_type = g_type_register_static (G_TYPE_OBJECT,
 260                                                      "GtkTreeModelSort",
 261                                                      &tree_model_sort_info, 0);
 262       g_type_add_interface_static (tree_model_sort_type,
 263                                    GTK_TYPE_TREE_MODEL,
 264                                    &tree_model_info);
 265
 266       g_type_add_interface_static (tree_model_sort_type,
 267                                    GTK_TYPE_TREE_SORTABLE,
 268                                    &sortable_info);
 269     }
 270
 271   return tree_model_sort_type;
 272 }
 273
 274 static void
 275 gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
 276 {
 277   tree_model_sort->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
 278   tree_model_sort->stamp = 0;
 279   tree_model_sort->zero_ref_count = 0;
 280   tree_model_sort->root = NULL;
 281   tree_model_sort->sort_list = NULL;
 282 }
 283
 284 static void
 285 gtk_tree_model_sort_class_init (GtkTreeModelSortClass *class)
 286 {
 287   GObjectClass *object_class;
 288
 289   object_class = (GObjectClass *) class;
 290   parent_class = g_type_class_peek_parent (class);
 291
 292   object_class->set_property = gtk_tree_model_sort_set_property;
 293   object_class->get_property = gtk_tree_model_sort_get_property;
 294
 295   object_class->finalize = gtk_tree_model_sort_finalize;
 296
 297   /* Properties */
 298   g_object_class_install_property (object_class,
 299                                    PROP_MODEL,
 300                                    g_param_spec_object ("model",
 301                                                         _("TreeModelSort Model"),
 302                                                         _("The model for the TreeModelSort to sort"),
 303                                                         GTK_TYPE_TREE_MODEL,
 304                                                         G_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
 305 }
 306
 307 static void
 308 gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
 309 {
 310   iface->get_flags = gtk_tree_model_sort_get_flags;
 311   iface->get_n_columns = gtk_tree_model_sort_get_n_columns;
 312   iface->get_column_type = gtk_tree_model_sort_get_column_type;
 313   iface->get_iter = gtk_tree_model_sort_get_iter;
 314   iface->get_path = gtk_tree_model_sort_get_path;
 315   iface->get_value = gtk_tree_model_sort_get_value;
 316   iface->iter_next = gtk_tree_model_sort_iter_next;
 317   iface->iter_children = gtk_tree_model_sort_iter_children;
 318   iface->iter_has_child = gtk_tree_model_sort_iter_has_child;
 319   iface->iter_n_children = gtk_tree_model_sort_iter_n_children;
 320   iface->iter_nth_child = gtk_tree_model_sort_iter_nth_child;
 321   iface->iter_parent = gtk_tree_model_sort_iter_parent;
 322   iface->ref_node = gtk_tree_model_sort_ref_node;
 323   iface->unref_node = gtk_tree_model_sort_unref_node;
 324 }
 325
 326 static void
 327 gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface *iface)
 328 {
 329   iface->get_sort_column_id = gtk_tree_model_sort_get_sort_column_id;
 330   iface->set_sort_column_id = gtk_tree_model_sort_set_sort_column_id;
 331   iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
 332   iface->set_default_sort_func = gtk_tree_model_sort_set_default_sort_func;
 333   iface->has_default_sort_func = gtk_tree_model_sort_has_default_sort_func;
 334 }
 335
 336 /**
 337  * gtk_tree_model_sort_new_with_model:
 338  * @child_model: A #GtkTreeModel
 339  *
 340  * Creates a new #GtkTreeModel, with @child_model as the child_model.
 341  *
 342  * Return value: A new #GtkTreeModel.
 343  */
 344 GtkTreeModel *
 345 gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
 346 {
 347   GtkTreeModel *retval;
 348
 349   g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);
 350
 351   retval = GTK_TREE_MODEL (g_object_new (gtk_tree_model_sort_get_type (), NULL));
 352
 353   gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
 354
 355   return retval;
 356 }
 357
 358 /* GObject callbacks */
 359 static void
 360 gtk_tree_model_sort_finalize (GObject *object)
 361 {
 362   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
 363
 364   gtk_tree_model_sort_set_model (tree_model_sort, NULL);
 365
 366   if (tree_model_sort->root)
 367     gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
 368
 369   if (tree_model_sort->sort_list)
 370     {
 371       _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
 372       tree_model_sort->sort_list = NULL;
 373     }
 374
 375   /* must chain up */
 376   parent_class->finalize (object);
 377 }
 378
 379 static void
 380 gtk_tree_model_sort_set_property (GObject      *object,
 381                                   guint         prop_id,
 382                                   const GValue *value,
 383                                   GParamSpec   *pspec)
 384 {
 385   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);
 386
 387   switch (prop_id)
 388     {
 389     case PROP_MODEL:
 390       gtk_tree_model_sort_set_model (tree_model_sort, g_value_get_object (value));
 391       break;
 392     default:
 393       G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
 394       break;
 395     }
 396 }
 397
 398 static void
 399 gtk_tree_model_sort_get_property (GObject    *object,
 400                                   guint       prop_id,
 401                                   GValue     *value,
 402                                   GParamSpec *pspec)
 403 {
 404   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);
 405
 406   switch (prop_id)
 407     {
 408     case PROP_MODEL:
 409       g_value_set_object (value, gtk_tree_model_sort_get_model(tree_model_sort));
 410       break;
 411     default:
 412       G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
 413       break;
 414     }
 415 }
 416
 417 static void
 418 gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
 419                                  GtkTreePath  *start_s_path,
 420                                  GtkTreeIter  *start_s_iter,
 421                                  gpointer      data)
 422 {
 423   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 424   GtkTreePath *path = NULL;
 425   GtkTreeIter iter;
 426   GtkTreeIter tmpiter;
 427
 428   SortElt tmp;
 429   SortElt *elt;
 430   SortLevel *level;
 431
 432   gboolean free_s_path = FALSE;
 433
 434   gint offset, index = 0, i;
 435
 436   g_return_if_fail (start_s_path != NULL || start_s_iter != NULL);
 437
 438   if (!start_s_path)
 439     {
 440       free_s_path = TRUE;
 441       start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
 442     }
 443
 444   path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
 445                                                               start_s_path,
 446                                                               FALSE);
 447   if (!path)
 448     {
 449       if (free_s_path)
 450         gtk_tree_path_free (start_s_path);
 451       return;
 452     }
 453
 454   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 455
 456   level = iter.user_data;
 457   elt = iter.user_data2;
 458
 459   if (level->array->len < 2 || tree_model_sort->sort_column_id == -1)
 460     {
 461       if (free_s_path)
 462         gtk_tree_path_free (start_s_path);
 463
 464       gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
 465
 466       gtk_tree_path_free (path);
 467
 468       return;
 469     }
 470
 471   if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
 472     {
 473       gtk_tree_model_get_iter (tree_model_sort->child_model,
 474                                &tmpiter, start_s_path);
 475     }
 476
 477   offset = elt->offset;
 478
 479   for (i = 0; i < level->array->len; i++)
 480     if (elt->offset == g_array_index (level->array, SortElt, i).offset)
 481       index = i;
 482
 483   memcpy (&tmp, elt, sizeof (SortElt));
 484   g_array_remove_index (level->array, index);
 485
 486   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
 487     index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
 488                                                    level,
 489                                                    &tmp.iter,
 490                                                    TRUE);
 491   else
 492     index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
 493                                                    level,
 494                                                    &tmpiter,
 495                                                    TRUE);
 496
 497   g_array_insert_val (level->array, index, tmp);
 498
 499   for (i = 0; i < level->array->len; i++)
 500     if (g_array_index (level->array, SortElt, i).children)
 501       g_array_index (level->array, SortElt, i).children->parent_elt = &g_array_index (level->array, SortElt, i);
 502
 503   gtk_tree_path_up (path);
 504   gtk_tree_path_append_index (path, index);
 505
 506   gtk_tree_model_sort_increment_stamp (tree_model_sort);
 507   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 508
 509   gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
 510
 511   gtk_tree_path_free (path);
 512   if (free_s_path)
 513     gtk_tree_path_free (start_s_path);
 514 }
 515
 516 static void
 517 gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
 518                                   GtkTreePath           *s_path,
 519                                   GtkTreeIter           *s_iter,
 520                                   gpointer               data)
 521 {
 522   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 523   GtkTreePath *path;
 524   GtkTreeIter iter;
 525   GtkTreeIter real_s_iter;
 526
 527   gint i = 0;
 528
 529   gboolean free_s_path = FALSE;
 530
 531   SortElt *elt;
 532   SortLevel *level;
 533   SortLevel *parent_level = NULL;
 534
 535   parent_level = level = SORT_LEVEL (tree_model_sort->root);
 536
 537   g_return_if_fail (s_path != NULL || s_iter != NULL);
 538
 539   if (!s_path)
 540     {
 541       s_path = gtk_tree_model_get_path (s_model, s_iter);
 542       free_s_path = TRUE;
 543     }
 544
 545   if (!s_iter)
 546     gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
 547   else
 548     real_s_iter = *s_iter;
 549
 550   if (!tree_model_sort->root)
 551     {
 552       gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
 553
 554       /* the build level already put the inserted iter in the level,
 555          so no need to handle this signal anymore */
 556
 557       goto done_and_submit;
 558     }
 559
 560   /* find the parent level */
 561   while (i < gtk_tree_path_get_depth (s_path) - 1)
 562     {
 563       gint j;
 564
 565       if (!level)
 566         {
 567           /* level not yet build, we won't cover this signal */
 568           goto done;
 569         }
 570
 571       if (level->array->len < gtk_tree_path_get_indices (s_path)[i])
 572         {
 573           g_warning ("A node was inserted with a parent that's not in the tree.\n"
 574                      "This possibly means that a GtkTreeModel inserted a child node\n"
 575                      "before the parent was inserted.");
 576           goto done;
 577         }
 578
 579       elt = NULL;
 580       for (j = 0; j < level->array->len; j++)
 581         if (g_array_index (level->array, SortElt, j).offset == gtk_tree_path_get_indices (s_path)[i])
 582           {
 583             elt = &g_array_index (level->array, SortElt, j);
 584             break;
 585           }
 586
 587       g_return_if_fail (elt != NULL);
 588
 589       if (!elt->children)
 590         {
 591           GtkTreePath *tmppath;
 592           GtkTreeIter  tmpiter;
 593
 594           tmppath = gtk_tree_model_sort_elt_get_path (level, elt);
 595           if (tmppath)
 596             {
 597               gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &tmpiter,
 598                                        tmppath);
 599               gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data),
 600                                                     tmppath,
 601                                                     &tmpiter);
 602               gtk_tree_path_free (tmppath);
 603             }
 604
 605           /* not covering this signal */
 606           goto done;
 607         }
 608
 609       level = elt->children;
 610       parent_level = level;
 611       i++;
 612     }
 613
 614   if (!parent_level)
 615     goto done;
 616
 617   if (!gtk_tree_model_sort_insert_value (tree_model_sort,
 618                                          parent_level,
 619                                          s_path,
 620                                          &real_s_iter))
 621     goto done;
 622
 623  done_and_submit:
 624   path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
 625                                                               s_path,
 626                                                               FALSE);
 627
 628   if (!path)
 629     return;
 630
 631   gtk_tree_model_sort_increment_stamp (tree_model_sort);
 632
 633   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 634   gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
 635   gtk_tree_path_free (path);
 636
 637  done:
 638   if (free_s_path)
 639     gtk_tree_path_free (s_path);
 640
 641   return;
 642 }
 643
 644 static void
 645 gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
 646                                            GtkTreePath  *s_path,
 647                                            GtkTreeIter  *s_iter,
 648                                            gpointer      data)
 649 {
 650   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 651   GtkTreePath *path;
 652   GtkTreeIter iter;
 653
 654   g_return_if_fail (s_path != NULL && s_iter != NULL);
 655
 656   path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
 657   if (path == NULL)
 658     return;
 659
 660   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 661   gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
 662
 663   gtk_tree_path_free (path);
 664 }
 665
 666 /* FIXME: I still have doubts if this works */
 667 static void
 668 gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
 669                                  GtkTreePath  *s_path,
 670                                  gpointer      data)
 671 {
 672   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 673   GtkTreePath *path = NULL;
 674   SortElt *elt;
 675   SortLevel *level;
 676   GtkTreeIter iter;
 677   gint offset;
 678   gint i;
 679
 680   g_return_if_fail (s_path != NULL);
 681
 682   path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
 683   if (path == NULL)
 684     return;
 685
 686   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 687
 688   level = SORT_LEVEL (iter.user_data);
 689   elt = SORT_ELT (iter.user_data2);
 690   offset = elt->offset;
 691
 692   while (elt->ref_count > 0)
 693     gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
 694
 695   if (level->ref_count == 0 && level != tree_model_sort->root)
 696     {
 697       /* This will prune the level, so I can just emit the signal and not worry
 698        * about cleaning this level up. */
 699       gtk_tree_model_sort_increment_stamp (tree_model_sort);
 700       gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
 701       gtk_tree_path_free (path);
 702       return;
 703     }
 704
 705   gtk_tree_model_sort_increment_stamp (tree_model_sort);
 706   gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
 707
 708   /* Remove the row */
 709   for (i = 0; i < level->array->len; i++)
 710     if (elt->offset == g_array_index (level->array, SortElt, i).offset)
 711       break;
 712
 713   g_array_remove_index (level->array, i);
 714
 715   /* update all offsets */
 716   for (i = 0; i < level->array->len; i++)
 717     {
 718       elt = & (g_array_index (level->array, SortElt, i));
 719       if (elt->offset > offset)
 720         elt->offset--;
 721       if (elt->children)
 722         elt->children->parent_elt = elt;
 723     }
 724
 725   gtk_tree_path_free (path);
 726 }
 727
 728 static void
 729 gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
 730                                     GtkTreePath  *s_path,
 731                                     GtkTreeIter  *s_iter,
 732                                     gint         *new_order,
 733                                     gpointer      data)
 734 {
 735   SortElt *elt;
 736   SortLevel *level;
 737   GtkTreeIter iter;
 738   gint *tmp_array;
 739   int i, j;
 740   GtkTreePath *path;
 741   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 742
 743   g_return_if_fail (new_order != NULL);
 744
 745   if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
 746     {
 747       if (tree_model_sort->root == NULL)
 748         return;
 749       path = gtk_tree_path_new ();
 750       level = SORT_LEVEL (tree_model_sort->root);
 751     }
 752   else
 753     {
 754       path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
 755       if (path == NULL)
 756         return;
 757       gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 758
 759       level = SORT_LEVEL (iter.user_data);
 760       elt = SORT_ELT (iter.user_data2);
 761
 762       if (!elt->children)
 763         {
 764           gtk_tree_path_free (path);
 765           return;
 766         }
 767
 768       level = elt->children;
 769     }
 770
 771   if (level->array->len < 2)
 772     {
 773       gtk_tree_path_free (path);
 774       return;
 775     }
 776
 777   tmp_array = g_new (int, level->array->len);
 778   for (i = 0; i < level->array->len; i++)
 779     {
 780       for (j = 0; j < level->array->len; j++)
 781         {
 782           if (g_array_index (level->array, SortElt, i).offset == new_order[j])
 783             tmp_array[i] = j;
 784         }
 785     }
 786
 787   for (i = 0; i < level->array->len; i++)
 788     g_array_index (level->array, SortElt, i).offset = tmp_array[i];
 789   g_free (tmp_array);
 790
 791   if (tree_model_sort->sort_column_id == -1 &&
 792       tree_model_sort->default_sort_func == (GtkTreeIterCompareFunc) 0x1)
 793     {
 794
 795       gtk_tree_model_sort_sort_level (tree_model_sort, level,
 796                                       FALSE, FALSE);
 797       gtk_tree_model_sort_increment_stamp (tree_model_sort);
 798
 799       if (gtk_tree_path_get_depth (path))
 800         {
 801           gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
 802                                    &iter,
 803                                    path);
 804           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
 805                                          path, &iter, new_order);
 806         }
 807       else
 808         {
 809           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
 810                                          path, NULL, new_order);
 811         }
 812     }
 813
 814   gtk_tree_path_free (path);
 815 }
 816
 817 /* Fulfill our model requirements */
 818 static guint
 819 gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
 820 {
 821   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
 822
 823   return 0;
 824 }
 825
 826 static gint
 827 gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
 828 {
 829   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
 830
 831   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
 832
 833   if (tree_model_sort->child_model == 0)
 834     return 0;
 835
 836   return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
 837 }
 838
 839 static GType
 840 gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
 841                                      gint          index)
 842 {
 843   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
 844   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
 845
 846   return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
 847 }
 848
 849 static gboolean
 850 gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
 851                               GtkTreeIter  *iter,
 852                               GtkTreePath  *path)
 853 {
 854   GtkTreeModelSort *tree_model_sort;
 855   gint *indices;
 856   SortLevel *level;
 857   gint depth, i;
 858
 859   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 860   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 861
 862   tree_model_sort = (GtkTreeModelSort *) tree_model;
 863   indices = gtk_tree_path_get_indices (path);
 864
 865   if (tree_model_sort->root == NULL)
 866     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
 867   level = SORT_LEVEL (tree_model_sort->root);
 868
 869   depth = gtk_tree_path_get_depth (path);
 870   if (depth == 0)
 871     return FALSE;
 872
 873   for (i = 0; i < depth - 1; i++)
 874     {
 875       if ((level == NULL) ||
 876           (level->array->len < indices[i]))
 877         return FALSE;
 878
 879       if (g_array_index (level->array, SortElt, indices[i]).children == NULL)
 880         gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, indices[i]));
 881       level = g_array_index (level->array, SortElt, indices[i]).children;
 882     }
 883
 884   if (level == NULL)
 885     return FALSE;
 886   iter->stamp = tree_model_sort->stamp;
 887   iter->user_data = level;
 888   iter->user_data2 = &g_array_index (level->array, SortElt, indices[depth - 1]);
 889
 890   return TRUE;
 891 }
 892
 893 static GtkTreePath *
 894 gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
 895                               GtkTreeIter  *iter)
 896 {
 897   GtkTreePath *retval;
 898   SortLevel *level;
 899   SortElt *elt;
 900
 901   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
 902   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
 903   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
 904
 905   retval = gtk_tree_path_new ();
 906   level = iter->user_data;
 907   elt = iter->user_data2;
 908   while (level != NULL)
 909     {
 910       gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);
 911
 912       elt = level->parent_elt;
 913       level = level->parent_level;
 914     }
 915
 916   return retval;
 917 }
 918
 919 static void
 920 gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
 921                                GtkTreeIter  *iter,
 922                                gint          column,
 923                                GValue       *value)
 924 {
 925   GtkTreeIter child_iter;
 926
 927   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
 928   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
 929   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);
 930
 931   GET_CHILD_ITER (tree_model, &child_iter, iter);
 932   gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
 933                             &child_iter, column, value);
 934 }
 935
 936 static gboolean
 937 gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
 938                                GtkTreeIter  *iter)
 939 {
 940   SortLevel *level;
 941   SortElt *elt;
 942
 943   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 944   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 945   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);
 946
 947   level = iter->user_data;
 948   elt = iter->user_data2;
 949
 950   if (elt - (SortElt *)level->array->data >= level->array->len - 1)
 951     {
 952       iter->stamp = 0;
 953       return FALSE;
 954     }
 955   iter->user_data2 = elt + 1;
 956
 957   return TRUE;
 958 }
 959
 960 static gboolean
 961 gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
 962                                    GtkTreeIter  *iter,
 963                                    GtkTreeIter  *parent)
 964 {
 965   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
 966   SortLevel *level;
 967
 968   iter->stamp = 0;
 969   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 970   g_return_val_if_fail (tree_model_sort->child_model != NULL, FALSE);
 971   if (parent) g_return_val_if_fail (tree_model_sort->stamp == parent->stamp, FALSE);
 972
 973   if (parent == NULL)
 974     {
 975       if (tree_model_sort->root == NULL)
 976         gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
 977       if (tree_model_sort->root == NULL)
 978         return FALSE;
 979
 980       level = tree_model_sort->root;
 981       iter->stamp = tree_model_sort->stamp;
 982       iter->user_data = level;
 983       iter->user_data2 = level->array->data;
 984     }
 985   else
 986     {
 987       if (((SortElt *)parent->user_data2)->children == NULL)
 988         gtk_tree_model_sort_build_level (tree_model_sort,
 989                                          (SortLevel *)parent->user_data,
 990                                          (SortElt *)parent->user_data2);
 991       if (((SortElt *)parent->user_data2)->children == NULL)
 992         return FALSE;
 993       iter->stamp = tree_model_sort->stamp;
 994       iter->user_data = ((SortElt *)parent->user_data2)->children;
 995       iter->user_data2 = ((SortLevel *)iter->user_data)->array->data;
 996     }
 997
 998   return TRUE;
 999 }
1000
1001 static gboolean
1002 gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
1003                                     GtkTreeIter  *iter)
1004 {
1005   GtkTreeIter child_iter;
1006
1007   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1008   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1009   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);
1010
1011   GET_CHILD_ITER (tree_model, &child_iter, iter);
1012
1013   return gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1014 }
1015
1016 static gint
1017 gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
1018                                      GtkTreeIter  *iter)
1019 {
1020   GtkTreeIter child_iter;
1021
1022   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
1023   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
1024   if (iter) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, 0);
1025
1026   if (iter == NULL)
1027     return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, NULL);
1028
1029   GET_CHILD_ITER (tree_model, &child_iter, iter);
1030
1031   return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1032 }
1033
1034 static gboolean
1035 gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
1036                                     GtkTreeIter  *iter,
1037                                     GtkTreeIter  *parent,
1038                                     gint          n)
1039 {
1040   SortLevel *level;
1041   /* We have this for the iter == parent case */
1042   GtkTreeIter children;
1043
1044   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1045   if (parent) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
1046
1047   /* Use this instead of has_child to force us to build the level, if needed */
1048   if (gtk_tree_model_sort_iter_children (tree_model, &children, parent) == FALSE)
1049     {
1050       iter->stamp = 0;
1051       return FALSE;
1052     }
1053
1054   level = children.user_data;
1055   if (n >= level->array->len)
1056     {
1057       iter->stamp = 0;
1058       return FALSE;
1059     }
1060
1061   iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
1062   iter->user_data = level;
1063   iter->user_data2 = &g_array_index (level->array, SortElt, n);
1064
1065   return TRUE;
1066 }
1067
1068 static gboolean
1069 gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
1070                                  GtkTreeIter  *iter,
1071                                  GtkTreeIter  *child)
1072 {
1073   SortLevel *level;
1074
1075   iter->stamp = 0;
1076   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1077   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1078   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == child->stamp, FALSE);
1079
1080   level = child->user_data;
1081
1082   if (level->parent_level)
1083     {
1084       iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
1085       iter->user_data = level->parent_level;
1086       iter->user_data2 = level->parent_elt;
1087
1088       return TRUE;
1089     }
1090   return FALSE;
1091 }
1092
1093 static void
1094 gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
1095                               GtkTreeIter  *iter)
1096 {
1097   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1098   GtkTreeIter child_iter;
1099   SortLevel *level;
1100   SortElt *elt;
1101
1102   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
1103   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
1104   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);
1105
1106   GET_CHILD_ITER (tree_model, &child_iter, iter);
1107
1108   gtk_tree_model_ref_node (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1109
1110   level = iter->user_data;
1111   elt = iter->user_data2;
1112
1113   elt->ref_count++;
1114   level->ref_count++;
1115   if (level->ref_count == 1)
1116     {
1117       SortLevel *parent_level = level->parent_level;
1118       SortElt *parent_elt = level->parent_elt;
1119       /* We were at zero -- time to decrement the zero_ref_count val */
1120       do
1121         {
1122           if (parent_elt)
1123             parent_elt->zero_ref_count--;
1124           else
1125             tree_model_sort->zero_ref_count--;
1126
1127           if (parent_level)
1128             {
1129               parent_elt = parent_level->parent_elt;
1130               parent_level = parent_level->parent_level;
1131             }
1132         }
1133       while (parent_level);
1134     }
1135 }
1136
1137 static void
1138 gtk_tree_model_sort_real_unref_node (GtkTreeModel *tree_model,
1139                                      GtkTreeIter  *iter,
1140                                      gboolean      propagate_unref)
1141 {
1142   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1143   GtkTreeIter child_iter;
1144   SortLevel *level;
1145   SortElt *elt;
1146
1147   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
1148   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
1149   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);
1150
1151   GET_CHILD_ITER (tree_model, &child_iter, iter);
1152
1153   if (propagate_unref)
1154     gtk_tree_model_unref_node (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1155
1156   level = iter->user_data;
1157   elt = iter->user_data2;
1158
1159   g_return_if_fail (elt->ref_count > 0);
1160
1161   elt->ref_count--;
1162   level->ref_count--;
1163   if (level->ref_count == 0)
1164     {
1165       SortLevel *parent_level = level->parent_level;
1166       SortElt *parent_elt = level->parent_elt;
1167
1168       /* We are at zero -- time to increment the zero_ref_count val */
1169       while (parent_level)
1170         {
1171           parent_elt->zero_ref_count++;
1172
1173           parent_elt = parent_level->parent_elt;
1174           parent_level = parent_level->parent_level;
1175         }
1176       tree_model_sort->zero_ref_count++;
1177     }
1178 }
1179
1180 static void
1181 gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
1182                                 GtkTreeIter  *iter)
1183 {
1184   gtk_tree_model_sort_real_unref_node (tree_model, iter, TRUE);
1185 }
1186
1187 /* Sortable interface */
1188 static gboolean
1189 gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable *sortable,
1190                                         gint            *sort_column_id,
1191                                         GtkSortType     *order)
1192 {
1193   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1194
1195   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (sortable), FALSE);
1196
1197   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1198     return FALSE;
1199
1200   if (sort_column_id)
1201     *sort_column_id = tree_model_sort->sort_column_id;
1202   if (order)
1203     *order = tree_model_sort->order;
1204
1205   return TRUE;
1206 }
1207
1208 static void
1209 gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable *sortable,
1210                                         gint             sort_column_id,
1211                                         GtkSortType      order)
1212 {
1213   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1214
1215   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (sortable));
1216
1217   if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1218     {
1219       GtkTreeDataSortHeader *header = NULL;
1220
1221       header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1222                                                sort_column_id);
1223
1224       /* we want to make sure that we have a function */
1225       g_return_if_fail (header != NULL);
1226       g_return_if_fail (header->func != NULL);
1227     }
1228   else
1229     g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1230
1231   if (tree_model_sort->sort_column_id == sort_column_id)
1232     {
1233       if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1234         {
1235           if (tree_model_sort->order == order)
1236             return;
1237         }
1238       else
1239         return;
1240     }
1241
1242   tree_model_sort->sort_column_id = sort_column_id;
1243   tree_model_sort->order = order;
1244
1245   gtk_tree_model_sort_sort (tree_model_sort);
1246   gtk_tree_sortable_sort_column_changed (sortable);
1247 }
1248
1249 static void
1250 gtk_tree_model_sort_set_sort_func (GtkTreeSortable        *sortable,
1251                                    gint                    sort_column_id,
1252                                    GtkTreeIterCompareFunc  func,
1253                                    gpointer                data,
1254                                    GtkDestroyNotify        destroy)
1255 {
1256   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
1257   GtkTreeDataSortHeader *header = NULL;
1258   GList *list;
1259
1260   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (sortable));
1261   g_return_if_fail (func != NULL);
1262
1263   for (list = tree_model_sort->sort_list; list; list = list->next)
1264     {
1265       header = (GtkTreeDataSortHeader *) list->data;
1266
1267       if (header->sort_column_id == sort_column_id)
1268         break;
1269     }
1270
1271   if (header == NULL)
1272     {
1273       header = g_new0 (GtkTreeDataSortHeader, 1);
1274       header->sort_column_id = sort_column_id;
1275       tree_model_sort->sort_list = g_list_append (tree_model_sort->sort_list,
1276                                                   header);
1277     }
1278
1279   if (header->destroy)
1280     (* header->destroy) (header->data);
1281
1282   header->func = func;
1283   header->data = data;
1284   header->destroy = destroy;
1285 }
1286
1287 static void
1288 gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
1289                                            GtkTreeIterCompareFunc  func,
1290                                            gpointer                data,
1291                                            GtkDestroyNotify        destroy)
1292 {
1293   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1294
1295   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (sortable));
1296
1297   if (tree_model_sort->default_sort_destroy)
1298     (* tree_model_sort->default_sort_destroy) (tree_model_sort->default_sort_data);
1299
1300   tree_model_sort->default_sort_func = func;
1301   tree_model_sort->default_sort_data = data;
1302   tree_model_sort->default_sort_destroy = destroy;
1303 }
1304
1305 static gboolean
1306 gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable *sortable)
1307 {
1308   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1309
1310   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (sortable), FALSE);
1311
1312   return (tree_model_sort->default_sort_func != NULL);
1313 }
1314
1315 /* sorting code - private */
1316 static gint
1317 gtk_tree_model_sort_compare_func (gconstpointer a,
1318                                   gconstpointer b,
1319                                   gpointer      user_data)
1320 {
1321   SortData *data = (SortData *)user_data;
1322   GtkTreeModelSort *tree_model_sort = data->tree_model_sort;
1323   SortTuple *sa = (SortTuple *)a;
1324   SortTuple *sb = (SortTuple *)b;
1325
1326   GtkTreeIter iter_a, iter_b;
1327   gint retval;
1328
1329   /* shortcut, if we've the same offsets here, they should be equal */
1330   if (sa->offset == sb->offset)
1331     return 0;
1332
1333   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1334     {
1335       iter_a = sa->elt->iter;
1336       iter_b = sb->elt->iter;
1337     }
1338   else
1339     {
1340       data->parent_path_indices [data->parent_path_depth-1] = sa->elt->offset;
1341       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort->child_model), &iter_a, data->parent_path);
1342       data->parent_path_indices [data->parent_path_depth-1] = sb->elt->offset;
1343       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort->child_model), &iter_b, data->parent_path);
1344     }
1345
1346   retval = (* data->sort_func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1347                                 &iter_a, &iter_b,
1348                                 data->sort_data);
1349
1350   if (tree_model_sort->order == GTK_SORT_DESCENDING)
1351     {
1352       if (retval > 0)
1353         retval = -1;
1354       else if (retval < 0)
1355         retval = 1;
1356     }
1357
1358   return retval;
1359 }
1360
1361 static gint
1362 gtk_tree_model_sort_offset_compare_func (gconstpointer a,
1363                                          gconstpointer b,
1364                                          gpointer      user_data)
1365 {
1366   gint retval;
1367
1368   SortTuple *sa = (SortTuple *)a;
1369   SortTuple *sb = (SortTuple *)b;
1370
1371   SortData *data = (SortData *)user_data;
1372
1373   if (sa->elt->offset < sb->elt->offset)
1374     retval = -1;
1375   else if (sa->elt->offset > sb->elt->offset)
1376     retval = 1;
1377   else
1378     retval = 0;
1379
1380   if (data->tree_model_sort->order == GTK_SORT_DESCENDING)
1381     {
1382       if (retval > 0)
1383         retval = -1;
1384       else if (retval < 0)
1385         retval = 1;
1386     }
1387
1388   return retval;
1389 }
1390
1391 static void
1392 gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
1393                                 SortLevel        *level,
1394                                 gboolean          recurse,
1395                                 gboolean          emit_reordered)
1396 {
1397   gint i;
1398   GArray *sort_array;
1399   GArray *new_array;
1400   gint *new_order;
1401
1402   GtkTreeIter iter;
1403   GtkTreePath *path;
1404
1405   SortData data;
1406
1407   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
1408   g_return_if_fail (level != NULL);
1409
1410   if (level->array->len < 1 && !((SortElt *)level->array->data)->children)
1411     return;
1412
1413   /* Set up data */
1414   data.tree_model_sort = tree_model_sort;
1415   if (level->parent_elt)
1416     {
1417       data.parent_path = gtk_tree_model_sort_elt_get_path (level->parent_level,
1418                                                            level->parent_elt);
1419       gtk_tree_path_append_index (data.parent_path, 0);
1420     }
1421   else
1422     {
1423       data.parent_path = gtk_tree_path_new_root ();
1424     }
1425   data.parent_path_depth = gtk_tree_path_get_depth (data.parent_path);
1426   data.parent_path_indices = gtk_tree_path_get_indices (data.parent_path);
1427
1428   /* make the array to be sorted */
1429   sort_array = g_array_sized_new (FALSE, FALSE, sizeof (SortTuple), level->array->len);
1430   for (i = 0; i < level->array->len; i++)
1431     {
1432       SortTuple tuple;
1433
1434       tuple.elt = &g_array_index (level->array, SortElt, i);
1435       tuple.offset = i;
1436
1437       g_array_append_val (sort_array, tuple);
1438     }
1439
1440     if (tree_model_sort->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1441       {
1442         GtkTreeDataSortHeader *header = NULL;
1443
1444         header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1445                                                  tree_model_sort->sort_column_id);
1446
1447         g_return_if_fail (header != NULL);
1448         g_return_if_fail (header->func != NULL);
1449
1450         data.sort_func = header->func;
1451         data.sort_data = header->data;
1452       }
1453     else
1454       {
1455         /* absolutely SHOULD NOT happen: */
1456         g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1457
1458         data.sort_func = tree_model_sort->default_sort_func;
1459         data.sort_data = tree_model_sort->default_sort_data;
1460       }
1461
1462   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
1463       tree_model_sort->default_sort_func == (GtkTreeIterCompareFunc) 0x1)
1464     {
1465       g_array_sort_with_data (sort_array,
1466                               gtk_tree_model_sort_offset_compare_func,
1467                               &data);
1468     }
1469   else
1470     {
1471       g_array_sort_with_data (sort_array,
1472                               gtk_tree_model_sort_compare_func,
1473                               &data);
1474     }
1475
1476   gtk_tree_path_free (data.parent_path);
1477
1478   new_array = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), level->array->len);
1479   new_order = g_new (gint, level->array->len);
1480
1481   for (i = 0; i < level->array->len; i++)
1482     {
1483       SortElt *elt;
1484
1485       elt = g_array_index (sort_array, SortTuple, i).elt;
1486       new_order[i] = g_array_index (sort_array, SortTuple, i).offset;
1487
1488       g_array_append_val (new_array, *elt);
1489       elt = &g_array_index (new_array, SortElt, i);
1490       if (elt->children)
1491         elt->children->parent_elt = elt;
1492     }
1493
1494   g_array_free (level->array, TRUE);
1495   level->array = new_array;
1496   g_array_free (sort_array, TRUE);
1497
1498   if (emit_reordered)
1499     {
1500       if (level->parent_elt)
1501         {
1502           iter.stamp = tree_model_sort->stamp;
1503           iter.user_data = level->parent_level;
1504           iter.user_data2 = level->parent_elt;
1505
1506           path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort),
1507                                           &iter);
1508
1509           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1510                                          &iter, new_order);
1511         }
1512       else
1513         {
1514           /* toplevel list */
1515           path = gtk_tree_path_new ();
1516           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1517                                          NULL, new_order);
1518         }
1519
1520       gtk_tree_path_free (path);
1521     }
1522
1523   /* recurse, if possible */
1524   if (recurse)
1525     {
1526       for (i = 0; i < level->array->len; i++)
1527         {
1528           SortElt *elt = &g_array_index (level->array, SortElt, i);
1529
1530           if (elt->children)
1531             gtk_tree_model_sort_sort_level (tree_model_sort,
1532                                             elt->children,
1533                                             TRUE, emit_reordered);
1534         }
1535     }
1536
1537   g_free (new_order);
1538 }
1539
1540 static void
1541 gtk_tree_model_sort_sort (GtkTreeModelSort *tree_model_sort)
1542 {
1543   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
1544
1545   if (!tree_model_sort->root)
1546     return;
1547
1548   if (tree_model_sort->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1549     {
1550       GtkTreeDataSortHeader *header = NULL;
1551
1552       header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1553                                                tree_model_sort->sort_column_id);
1554
1555       /* we want to make sure that we have a function */
1556       g_return_if_fail (header != NULL);
1557       g_return_if_fail (header->func != NULL);
1558     }
1559   else
1560     g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1561
1562   gtk_tree_model_sort_sort_level (tree_model_sort, tree_model_sort->root,
1563                                   TRUE, TRUE);
1564 }
1565
1566 /* signal helpers */
1567 static gint
1568 gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
1569                                        SortLevel        *level,
1570                                        GtkTreeIter      *iter,
1571                                        gboolean          skip_sort_elt)
1572 {
1573   gint middle;
1574   gint cmp;
1575   SortElt *tmp_elt;
1576   GtkTreeIter tmp_iter;
1577
1578   GtkTreeIterCompareFunc func;
1579   gpointer data;
1580
1581   GtkTreePath *path;
1582
1583   {
1584     GtkTreeDataSortHeader *header;
1585
1586     header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1587                                              tree_model_sort->sort_column_id);
1588
1589     if (!header)
1590       return 0;
1591
1592     g_return_val_if_fail (header->func != NULL, 0);
1593
1594     func = header->func;
1595     data = header->data;
1596   }
1597
1598   for (middle = 0; middle < level->array->len; middle++)
1599     {
1600       tmp_elt = &(g_array_index (level->array, SortElt, middle));
1601
1602       if (!skip_sort_elt && SORT_ELT (iter->user_data2) == tmp_elt)
1603         continue;
1604
1605       path = gtk_tree_model_sort_elt_get_path (level, tmp_elt);
1606       gtk_tree_model_get_iter (tree_model_sort->child_model,
1607                                &tmp_iter, path);
1608       gtk_tree_path_free (path);
1609
1610       if (tree_model_sort->order == GTK_SORT_ASCENDING)
1611         cmp = (* func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1612                         &tmp_iter, iter, data);
1613       else
1614         cmp = (* func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1615                         iter, &tmp_iter, data);
1616
1617       if (cmp > 0)
1618         break;
1619     }
1620
1621   return middle;
1622 }
1623
1624 static gboolean
1625 gtk_tree_model_sort_insert_value (GtkTreeModelSort *tree_model_sort,
1626                                   SortLevel        *level,
1627                                   GtkTreePath      *s_path,
1628                                   GtkTreeIter      *s_iter)
1629 {
1630   gint offset, index, i;
1631
1632   SortElt elt;
1633   SortElt *tmp_elt;
1634
1635   offset = gtk_tree_path_get_indices (s_path)[gtk_tree_path_get_depth (s_path) - 1];
1636
1637   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1638     elt.iter = *s_iter;
1639   elt.offset = offset;
1640   elt.zero_ref_count = 0;
1641   elt.ref_count = 0;
1642   elt.children = NULL;
1643
1644   index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
1645                                                  level, s_iter,
1646                                                  FALSE);
1647
1648   g_array_insert_vals (level->array, index, &elt, 1);
1649
1650   /* update all larger offsets */
1651   tmp_elt = SORT_ELT (level->array->data);
1652   for (i = 0; i < level->array->len; i++, tmp_elt++)
1653     {
1654       if ((tmp_elt->offset >= offset) && i != index)
1655         tmp_elt->offset++;
1656       if (tmp_elt->children)
1657         tmp_elt->children->parent_elt = tmp_elt;
1658     }
1659
1660   return TRUE;
1661 }
1662
1663 /* sort elt stuff */
1664 static GtkTreePath *
1665 gtk_tree_model_sort_elt_get_path (SortLevel *level,
1666                                   SortElt *elt)
1667 {
1668   SortLevel *walker = level;
1669   SortElt *walker2 = elt;
1670   GtkTreePath *path;
1671
1672   g_return_val_if_fail (level != NULL, NULL);
1673   g_return_val_if_fail (elt != NULL, NULL);
1674
1675   path = gtk_tree_path_new ();
1676
1677   while (walker)
1678     {
1679       gtk_tree_path_prepend_index (path, walker2->offset);
1680
1681       walker2 = walker->parent_elt;
1682       walker = walker->parent_level;
1683     }
1684
1685   return path;
1686 }
1687
1688 /**
1689  * gtk_tree_model_sort_set_model:
1690  * @tree_model_sort: The #GtkTreeModelSort.
1691  * @child_model: A #GtkTreeModel, or NULL.
1692  *
1693  * Sets the model of @tree_model_sort to be @model.  If @model is NULL, then the
1694  * old model is unset.  The sort function is unset as a result of this call.
1695  * The model will be in an unsorted state until a sort function is set.
1696  **/
1697 static void
1698 gtk_tree_model_sort_set_model (GtkTreeModelSort *tree_model_sort,
1699                                GtkTreeModel     *child_model)
1700 {
1701   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
1702
1703   if (child_model)
1704     g_object_ref (G_OBJECT (child_model));
1705
1706   if (tree_model_sort->child_model)
1707     {
1708       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
1709                                    tree_model_sort->changed_id);
1710       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
1711                                    tree_model_sort->inserted_id);
1712       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
1713                                    tree_model_sort->has_child_toggled_id);
1714       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
1715                                    tree_model_sort->deleted_id);
1716       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
1717                                    tree_model_sort->reordered_id);
1718
1719       /* reset our state */
1720       if (tree_model_sort->root)
1721         gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
1722       tree_model_sort->root = NULL;
1723       _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
1724       tree_model_sort->sort_list = NULL;
1725       g_object_unref (G_OBJECT (tree_model_sort->child_model));
1726     }
1727
1728   tree_model_sort->child_model = child_model;
1729
1730   if (child_model)
1731     {
1732       GType *types;
1733       gint i, n_columns;
1734
1735       g_object_ref (tree_model_sort->child_model);
1736       tree_model_sort->changed_id =
1737         g_signal_connect (child_model, "row_changed",
1738                           G_CALLBACK (gtk_tree_model_sort_row_changed),
1739                           tree_model_sort);
1740       tree_model_sort->inserted_id =
1741         g_signal_connect (child_model, "row_inserted",
1742                           G_CALLBACK (gtk_tree_model_sort_row_inserted),
1743                           tree_model_sort);
1744       tree_model_sort->has_child_toggled_id =
1745         g_signal_connect (child_model, "row_has_child_toggled",
1746                           G_CALLBACK (gtk_tree_model_sort_row_has_child_toggled),
1747                           tree_model_sort);
1748       tree_model_sort->deleted_id =
1749         g_signal_connect (child_model, "row_deleted",
1750                           G_CALLBACK (gtk_tree_model_sort_row_deleted),
1751                           tree_model_sort);
1752       tree_model_sort->reordered_id =
1753         g_signal_connect (child_model, "rows_reordered",
1754                           G_CALLBACK (gtk_tree_model_sort_rows_reordered),
1755                           tree_model_sort);
1756
1757       tree_model_sort->child_flags = gtk_tree_model_get_flags (child_model);
1758       n_columns = gtk_tree_model_get_n_columns (child_model);
1759
1760       types = g_new (GType, n_columns);
1761       for (i = 0; i < n_columns; i++)
1762         types[i] = gtk_tree_model_get_column_type (child_model, i);
1763
1764       tree_model_sort->sort_list = _gtk_tree_data_list_header_new (n_columns, types);
1765       g_free (types);
1766
1767       tree_model_sort->default_sort_func = (GtkTreeIterCompareFunc)0x1;
1768       tree_model_sort->stamp = g_random_int ();
1769     }
1770 }
1771
1772 /**
1773  * gtk_tree_model_sort_get_model:
1774  * @tree_model: a #GtkTreeModelSort
1775  *
1776  * Returns the model the #GtkTreeModelSort is sorting.
1777  *
1778  * Return value: the "child model" being sorted
1779  **/
1780 GtkTreeModel *
1781 gtk_tree_model_sort_get_model (GtkTreeModelSort  *tree_model)
1782 {
1783   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
1784
1785   return tree_model->child_model;
1786 }
1787
1788
1789 static GtkTreePath *
1790 gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
1791                                                      GtkTreePath      *child_path,
1792                                                      gboolean          build_levels)
1793 {
1794   gint *child_indices;
1795   GtkTreePath *retval;
1796   SortLevel *level;
1797   gint i;
1798
1799   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
1800   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
1801   g_return_val_if_fail (child_path != NULL, NULL);
1802
1803   retval = gtk_tree_path_new ();
1804   child_indices = gtk_tree_path_get_indices (child_path);
1805
1806   if (tree_model_sort->root == NULL && build_levels)
1807     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1808   level = SORT_LEVEL (tree_model_sort->root);
1809
1810   for (i = 0; i < gtk_tree_path_get_depth (child_path); i++)
1811     {
1812       gint j;
1813       gboolean found_child = FALSE;
1814
1815       if (!level)
1816         {
1817           gtk_tree_path_free (retval);
1818           return NULL;
1819         }
1820
1821       if (child_indices[i] >= level->array->len)
1822         {
1823           gtk_tree_path_free (retval);
1824           return NULL;
1825         }
1826       for (j = 0; j < level->array->len; j++)
1827         {
1828           if ((g_array_index (level->array, SortElt, j)).offset == child_indices[i])
1829             {
1830               gtk_tree_path_append_index (retval, j);
1831               if (g_array_index (level->array, SortElt, j).children == NULL && build_levels)
1832                 {
1833                   gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, j));
1834                 }
1835               level = g_array_index (level->array, SortElt, j).children;
1836               found_child = TRUE;
1837               break;
1838             }
1839         }
1840       if (! found_child)
1841         {
1842           gtk_tree_path_free (retval);
1843           return NULL;
1844         }
1845     }
1846
1847   return retval;
1848 }
1849
1850
1851 /**
1852  * gtk_tree_model_sort_convert_child_path_to_path:
1853  * @tree_model_sort: A #GtkTreeModelSort
1854  * @child_path: A #GtkTreePath to convert
1855  *
1856  * Converts @child_path to a path relative to @tree_model_sort.  That is,
1857  * @child_path points to a path in the child model.  The returned path will
1858  * point to the same row in the sorted model.  If @child_path isn't a valid path
1859  * on the child model, then %NULL is returned.
1860  *
1861  * Return value: A newly allocated #GtkTreePath, or %NULL
1862  **/
1863 GtkTreePath *
1864 gtk_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
1865                                                 GtkTreePath      *child_path)
1866 {
1867   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
1868   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
1869   g_return_val_if_fail (child_path != NULL, NULL);
1870
1871   return gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path, TRUE);
1872 }
1873
1874 /**
1875  * gtk_tree_model_sort_convert_child_iter_to_iter:
1876  * @tree_model_sort: A #GtkTreeModelSort
1877  * @sort_iter: An uninitialized #GtkTreeIter.
1878  * @child_iter: A valid #GtkTreeIter pointing to a row on the child model
1879  *
1880  * Sets @sort_iter to point to the row in @tree_model_sort that corresponds to
1881  * the row pointed at by @child_iter.
1882  **/
1883 void
1884 gtk_tree_model_sort_convert_child_iter_to_iter (GtkTreeModelSort *tree_model_sort,
1885                                                 GtkTreeIter      *sort_iter,
1886                                                 GtkTreeIter      *child_iter)
1887 {
1888   GtkTreePath *child_path, *path;
1889
1890   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
1891   g_return_if_fail (tree_model_sort->child_model != NULL);
1892   g_return_if_fail (sort_iter != NULL);
1893   g_return_if_fail (child_iter != NULL);
1894
1895   sort_iter->stamp = 0;
1896
1897   child_path = gtk_tree_model_get_path (tree_model_sort->child_model, child_iter);
1898   g_return_if_fail (child_path != NULL);
1899
1900   path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path);
1901   gtk_tree_path_free (child_path);
1902   g_return_if_fail (path != NULL);
1903
1904   gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort), sort_iter, path);
1905   gtk_tree_path_free (path);
1906 }
1907
1908 /**
1909  * gtk_tree_model_sort_convert_path_to_child_path:
1910  * @tree_model_sort: A #GtkTreeModelSort
1911  * @sorted_path: A #GtkTreePath to convert
1912  *
1913  * Converts @sort_path to a path on the child model of @tree_model_sort.  That
1914  * is, @sort_path points ot a location in @tree_model_sort.  The returned path
1915  * will point to the same location in the model not being sorted.  If @path does not point to a
1916  *
1917  * Return value: A newly allocated #GtkTreePath, or %NULL
1918  **/
1919 GtkTreePath *
1920 gtk_tree_model_sort_convert_path_to_child_path (GtkTreeModelSort *tree_model_sort,
1921                                                 GtkTreePath      *sorted_path)
1922 {
1923   gint *sorted_indices;
1924   GtkTreePath *retval;
1925   SortLevel *level;
1926   gint i;
1927
1928   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
1929   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
1930   g_return_val_if_fail (sorted_path != NULL, NULL);
1931
1932   retval = gtk_tree_path_new ();
1933   sorted_indices = gtk_tree_path_get_indices (sorted_path);
1934   if (tree_model_sort->root == NULL)
1935     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1936   level = SORT_LEVEL (tree_model_sort->root);
1937
1938   for (i = 0; i < gtk_tree_path_get_depth (sorted_path); i++)
1939     {
1940       if ((level == NULL) ||
1941           (level->array->len > sorted_indices[i]))
1942         {
1943           gtk_tree_path_free (retval);
1944           return NULL;
1945         }
1946       if (g_array_index (level->array, SortElt, sorted_indices[i]).children == NULL)
1947         gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, sorted_indices[i]));
1948       if (level == NULL)
1949
1950       gtk_tree_path_append_index (retval, g_array_index (level->array, SortElt, i).offset);
1951     }
1952
1953   return retval;
1954 }
1955
1956 /**
1957  * gtk_tree_model_sort_convert_iter_to_child_iter:
1958  * @tree_model_sort: A #GtkTreeModelSort
1959  * @child_iter: An uninitialized #GtkTreeIter
1960  * @sorted_iter: A valid #GtkTreeIter pointing to a row on @tree_model_sort.
1961  *
1962  * Sets @child_iter to point to the row pointed to by *sorted_iter.
1963  **/
1964 void
1965 gtk_tree_model_sort_convert_iter_to_child_iter (GtkTreeModelSort *tree_model_sort,
1966                                                 GtkTreeIter      *child_iter,
1967                                                 GtkTreeIter      *sorted_iter)
1968 {
1969   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
1970   g_return_if_fail (tree_model_sort->child_model != NULL);
1971   g_return_if_fail (child_iter != NULL);
1972   g_return_if_fail (sorted_iter != NULL);
1973   g_return_if_fail (sorted_iter->stamp == tree_model_sort->stamp);
1974
1975   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1976     {
1977       *child_iter = SORT_ELT (sorted_iter->user_data2)->iter;
1978     }
1979   else
1980     {
1981       GtkTreePath *path;
1982
1983       path = gtk_tree_model_sort_elt_get_path (sorted_iter->user_data,
1984                                                sorted_iter->user_data2);
1985       gtk_tree_model_get_iter (tree_model_sort->child_model, child_iter, path);
1986       gtk_tree_path_free (path);
1987     }
1988 }
1989
1990 static void
1991 gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
1992                                  SortLevel        *parent_level,
1993                                  SortElt          *parent_elt)
1994 {
1995   GtkTreeIter iter;
1996   SortLevel *new_level;
1997   gint length = 0;
1998   gint i;
1999
2000   g_assert (tree_model_sort->child_model != NULL);
2001
2002   if (parent_level == NULL)
2003     {
2004       if (gtk_tree_model_get_iter_root (tree_model_sort->child_model, &iter) == FALSE)
2005         return;
2006       length = gtk_tree_model_iter_n_children (tree_model_sort->child_model, NULL);
2007     }
2008   else
2009     {
2010       GtkTreeIter parent_iter;
2011       GtkTreeIter child_parent_iter;
2012
2013       parent_iter.stamp = tree_model_sort->stamp;
2014       parent_iter.user_data = parent_level;
2015       parent_iter.user_data2 = parent_elt;
2016
2017       gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2018                                                       &child_parent_iter,
2019                                                       &parent_iter);
2020       if (gtk_tree_model_iter_children (tree_model_sort->child_model,
2021                                         &iter,
2022                                         &child_parent_iter) == FALSE)
2023         return;
2024
2025       /* stamp may have changed */
2026       gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2027                                                       &child_parent_iter,
2028                                                       &parent_iter);
2029
2030       length = gtk_tree_model_iter_n_children (tree_model_sort->child_model, &child_parent_iter);
2031     }
2032
2033   g_return_if_fail (length > 0);
2034
2035   new_level = g_new (SortLevel, 1);
2036   new_level->array = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), length);
2037   new_level->ref_count = 0;
2038   new_level->parent_elt = parent_elt;
2039   new_level->parent_level = parent_level;
2040
2041   if (parent_elt)
2042     parent_elt->children = new_level;
2043   else
2044     tree_model_sort->root = new_level;
2045
2046   /* increase the count of zero ref_counts.*/
2047   while (parent_level)
2048     {
2049       parent_elt->zero_ref_count++;
2050
2051       parent_elt = parent_level->parent_elt;
2052       parent_level = parent_level->parent_level;
2053     }
2054   if (new_level != tree_model_sort->root)
2055     tree_model_sort->zero_ref_count++;
2056
2057   for (i = 0; i < length; i++)
2058     {
2059       SortElt sort_elt;
2060       sort_elt.offset = i;
2061       sort_elt.zero_ref_count = 0;
2062       sort_elt.ref_count = 0;
2063       sort_elt.children = NULL;
2064
2065       if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2066         {
2067           sort_elt.iter = iter;
2068           if (gtk_tree_model_iter_next (tree_model_sort->child_model, &iter) == FALSE &&
2069               i < length - 1)
2070             {
2071               g_warning ("There is a discrepency between the sort model and the child model.");
2072               return;
2073             }
2074         }
2075       g_array_append_val (new_level->array, sort_elt);
2076     }
2077
2078   /* sort level */
2079   gtk_tree_model_sort_sort_level (tree_model_sort, new_level,
2080                                   FALSE, FALSE);
2081 }
2082
2083 static void
2084 gtk_tree_model_sort_free_level (GtkTreeModelSort *tree_model_sort,
2085                                 SortLevel        *sort_level)
2086 {
2087   gint i;
2088
2089   g_assert (sort_level);
2090
2091   if (sort_level->ref_count == 0)
2092     {
2093       SortLevel *parent_level = sort_level->parent_level;
2094       SortElt *parent_elt = sort_level->parent_elt;
2095
2096       do
2097         {
2098           if (parent_elt)
2099             parent_elt->zero_ref_count--;
2100           else
2101             tree_model_sort->zero_ref_count--;
2102
2103           if (parent_level)
2104             {
2105               parent_elt = parent_level->parent_elt;
2106               parent_level = parent_level->parent_level;
2107             }
2108         }
2109       while (parent_level);
2110     }
2111
2112   for (i = 0; i < sort_level->array->len; i++)
2113     {
2114       if (g_array_index (sort_level->array, SortElt, i).children)
2115         gtk_tree_model_sort_free_level (tree_model_sort,
2116                                         SORT_LEVEL(g_array_index (sort_level->array, SortElt, i).children));
2117     }
2118
2119   if (sort_level->parent_elt)
2120     {
2121       sort_level->parent_elt->children = NULL;
2122     }
2123   else
2124     {
2125       tree_model_sort->root = NULL;
2126     }
2127
2128   g_array_free (sort_level->array, TRUE);
2129   sort_level->array = NULL;
2130
2131   g_free (sort_level);
2132   sort_level = NULL;
2133 }
2134
2135 static void
2136 gtk_tree_model_sort_increment_stamp (GtkTreeModelSort *tree_model_sort)
2137 {
2138   while (tree_model_sort->stamp == 0) tree_model_sort->stamp++;
2139
2140   gtk_tree_model_sort_clear_cache (tree_model_sort);
2141 }
2142
2143 static void
2144 gtk_tree_model_sort_clear_cache_helper (GtkTreeModelSort *tree_model_sort,
2145                                         SortLevel        *level)
2146 {
2147   gint i;
2148
2149   g_assert (level != NULL);
2150
2151   for (i = 0; i < level->array->len; i++)
2152     {
2153       if (g_array_index (level->array, SortElt, i).zero_ref_count > 0)
2154         gtk_tree_model_sort_clear_cache_helper (tree_model_sort, g_array_index (level->array, SortElt, i).children);
2155     }
2156
2157   if (level->ref_count == 0 && level != tree_model_sort->root)
2158     {
2159       gtk_tree_model_sort_free_level (tree_model_sort, level);
2160       return;
2161     }
2162 }
2163
2164 /**
2165  * gtk_tree_model_sort_reset_default_sort_func:
2166  * @tree_model_sort: A #GtkTreeModelSort
2167  *
2168  * This resets the default sort function to be in the 'unsorted' state.  That
2169  * is, it is in the same order as the child model.
2170  **/
2171 void
2172 gtk_tree_model_sort_reset_default_sort_func (GtkTreeModelSort *tree_model_sort)
2173 {
2174   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2175
2176   if (tree_model_sort->default_sort_destroy)
2177     (* tree_model_sort->default_sort_destroy) (tree_model_sort->default_sort_data);
2178
2179   tree_model_sort->default_sort_func = (GtkTreeIterCompareFunc) 0x1;
2180   tree_model_sort->default_sort_data = NULL;
2181   tree_model_sort->default_sort_destroy = NULL;
2182   tree_model_sort->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
2183 }
2184
2185 /**
2186  * gtk_tree_model_sort_clear_cache:
2187  * @tree_model_sort: A #GtkTreeModelSort
2188  *
2189  * This function should almost never be called.  It clears the @tree_model_sort
2190  * of any cached iterators that haven't been reffed with
2191  * gtk_tree_model_ref_node().  This might be useful if the child model being
2192  * sorted is static (and doesn't change often) and there has been a lot of
2193  * unreffed access to nodes.  As a side effect of this function, all unreffed
2194  * iters will be invalid.
2195  **/
2196 void
2197 gtk_tree_model_sort_clear_cache (GtkTreeModelSort *tree_model_sort)
2198 {
2199   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2200
2201   if (tree_model_sort->zero_ref_count)
2202     gtk_tree_model_sort_clear_cache_helper (tree_model_sort, (SortLevel *)tree_model_sort->root);
2203 }