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