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