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