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                                                         P_("TreeModelSort Model"),
 329                                                         P_("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)
 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       if (level == tree_model_sort->root)
 815         tree_model_sort->root = NULL;
 816       return;
 817     }
 818
 819   gtk_tree_model_sort_increment_stamp (tree_model_sort);
 820
 821   /* Remove the row */
 822   for (i = 0; i < level->array->len; i++)
 823     if (elt->offset == g_array_index (level->array, SortElt, i).offset)
 824       break;
 825
 826   g_array_remove_index (level->array, i);
 827
 828   /* update all offsets */
 829   for (i = 0; i < level->array->len; i++)
 830     {
 831       elt = & (g_array_index (level->array, SortElt, i));
 832       if (elt->offset > offset)
 833         elt->offset--;
 834       if (elt->children)
 835         elt->children->parent_elt = elt;
 836     }
 837
 838   gtk_tree_path_free (path);
 839 }
 840
 841 static void
 842 gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
 843                                     GtkTreePath  *s_path,
 844                                     GtkTreeIter  *s_iter,
 845                                     gint         *new_order,
 846                                     gpointer      data)
 847 {
 848   SortElt *elt;
 849   SortLevel *level;
 850   GtkTreeIter iter;
 851   gint *tmp_array;
 852   int i, j;
 853   GtkTreePath *path;
 854   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 855
 856   g_return_if_fail (new_order != NULL);
 857
 858   if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
 859     {
 860       if (tree_model_sort->root == NULL)
 861         return;
 862       path = gtk_tree_path_new ();
 863       level = SORT_LEVEL (tree_model_sort->root);
 864     }
 865   else
 866     {
 867       path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
 868       if (path == NULL)
 869         return;
 870       gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 871
 872       level = SORT_LEVEL (iter.user_data);
 873       elt = SORT_ELT (iter.user_data2);
 874
 875       if (!elt->children)
 876         {
 877           gtk_tree_path_free (path);
 878           return;
 879         }
 880
 881       level = elt->children;
 882     }
 883
 884   if (level->array->len < 2)
 885     {
 886       gtk_tree_path_free (path);
 887       return;
 888     }
 889
 890   tmp_array = g_new (int, level->array->len);
 891   for (i = 0; i < level->array->len; i++)
 892     {
 893       for (j = 0; j < level->array->len; j++)
 894         {
 895           if (g_array_index (level->array, SortElt, i).offset == new_order[j])
 896             tmp_array[i] = j;
 897         }
 898     }
 899
 900   for (i = 0; i < level->array->len; i++)
 901     g_array_index (level->array, SortElt, i).offset = tmp_array[i];
 902   g_free (tmp_array);
 903
 904   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
 905       tree_model_sort->default_sort_func == NO_SORT_FUNC)
 906     {
 907
 908       gtk_tree_model_sort_sort_level (tree_model_sort, level,
 909                                       FALSE, FALSE);
 910       gtk_tree_model_sort_increment_stamp (tree_model_sort);
 911
 912       if (gtk_tree_path_get_depth (path))
 913         {
 914           gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
 915                                    &iter,
 916                                    path);
 917           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
 918                                          path, &iter, new_order);
 919         }
 920       else
 921         {
 922           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
 923                                          path, NULL, new_order);
 924         }
 925     }
 926
 927   gtk_tree_path_free (path);
 928 }
 929
 930 /* Fulfill our model requirements */
 931 static GtkTreeModelFlags
 932 gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
 933 {
 934   GtkTreeModelFlags flags;
 935
 936   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
 937   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
 938
 939   flags = gtk_tree_model_get_flags (GTK_TREE_MODEL_SORT (tree_model)->child_model);
 940
 941   if ((flags & GTK_TREE_MODEL_LIST_ONLY) == GTK_TREE_MODEL_LIST_ONLY)
 942     return GTK_TREE_MODEL_LIST_ONLY;
 943
 944   return 0;
 945 }
 946
 947 static gint
 948 gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
 949 {
 950   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
 951
 952   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
 953
 954   if (tree_model_sort->child_model == 0)
 955     return 0;
 956
 957   return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
 958 }
 959
 960 static GType
 961 gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
 962                                      gint          index)
 963 {
 964   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
 965   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
 966
 967   return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
 968 }
 969
 970 static gboolean
 971 gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
 972                               GtkTreeIter  *iter,
 973                               GtkTreePath  *path)
 974 {
 975   GtkTreeModelSort *tree_model_sort;
 976   gint *indices;
 977   SortLevel *level;
 978   gint depth, i;
 979
 980   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 981   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 982
 983   tree_model_sort = (GtkTreeModelSort *) tree_model;
 984   indices = gtk_tree_path_get_indices (path);
 985
 986   if (tree_model_sort->root == NULL)
 987     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
 988   level = SORT_LEVEL (tree_model_sort->root);
 989
 990   depth = gtk_tree_path_get_depth (path);
 991   if (depth == 0)
 992     return FALSE;
 993
 994   for (i = 0; i < depth - 1; i++)
 995     {
 996       if ((level == NULL) ||
 997           (indices[i] >= level->array->len))
 998         return FALSE;
 999
1000       if (g_array_index (level->array, SortElt, indices[i]).children == NULL)
1001         gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, indices[i]));
1002       level = g_array_index (level->array, SortElt, indices[i]).children;
1003     }
1004
1005   if (!level || indices[i] >= level->array->len)
1006     {
1007       iter->stamp = 0;
1008       return FALSE;
1009     }
1010
1011   iter->stamp = tree_model_sort->stamp;
1012   iter->user_data = level;
1013   iter->user_data2 = &g_array_index (level->array, SortElt, indices[depth - 1]);
1014
1015   return TRUE;
1016 }
1017
1018 static GtkTreePath *
1019 gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
1020                               GtkTreeIter  *iter)
1021 {
1022   GtkTreePath *retval;
1023   SortLevel *level;
1024   SortElt *elt;
1025
1026   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
1027   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
1028   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
1029
1030   retval = gtk_tree_path_new ();
1031   level = iter->user_data;
1032   elt = iter->user_data2;
1033   while (level != NULL)
1034     {
1035       gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);
1036
1037       elt = level->parent_elt;
1038       level = level->parent_level;
1039     }
1040
1041   return retval;
1042 }
1043
1044 static void
1045 gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
1046                                GtkTreeIter  *iter,
1047                                gint          column,
1048                                GValue       *value)
1049 {
1050   GtkTreeIter child_iter;
1051
1052   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
1053   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
1054   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);
1055
1056   GET_CHILD_ITER (tree_model, &child_iter, iter);
1057   gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
1058                             &child_iter, column, value);
1059 }
1060
1061 static gboolean
1062 gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
1063                                GtkTreeIter  *iter)
1064 {
1065   SortLevel *level;
1066   SortElt *elt;
1067
1068   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1069   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1070   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);
1071
1072   level = iter->user_data;
1073   elt = iter->user_data2;
1074
1075   if (elt - (SortElt *)level->array->data >= level->array->len - 1)
1076     {
1077       iter->stamp = 0;
1078       return FALSE;
1079     }
1080   iter->user_data2 = elt + 1;
1081
1082   return TRUE;
1083 }
1084
1085 static gboolean
1086 gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
1087                                    GtkTreeIter  *iter,
1088                                    GtkTreeIter  *parent)
1089 {
1090   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1091   SortLevel *level;
1092
1093   iter->stamp = 0;
1094   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1095   g_return_val_if_fail (tree_model_sort->child_model != NULL, FALSE);
1096   if (parent) g_return_val_if_fail (tree_model_sort->stamp == parent->stamp, FALSE);
1097
1098   if (parent == NULL)
1099     {
1100       if (tree_model_sort->root == NULL)
1101         gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1102       if (tree_model_sort->root == NULL)
1103         return FALSE;
1104
1105       level = tree_model_sort->root;
1106       iter->stamp = tree_model_sort->stamp;
1107       iter->user_data = level;
1108       iter->user_data2 = level->array->data;
1109     }
1110   else
1111     {
1112       if (((SortElt *)parent->user_data2)->children == NULL)
1113         gtk_tree_model_sort_build_level (tree_model_sort,
1114                                          (SortLevel *)parent->user_data,
1115                                          (SortElt *)parent->user_data2);
1116       if (((SortElt *)parent->user_data2)->children == NULL)
1117         return FALSE;
1118       iter->stamp = tree_model_sort->stamp;
1119       iter->user_data = ((SortElt *)parent->user_data2)->children;
1120       iter->user_data2 = ((SortLevel *)iter->user_data)->array->data;
1121     }
1122
1123   return TRUE;
1124 }
1125
1126 static gboolean
1127 gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
1128                                     GtkTreeIter  *iter)
1129 {
1130   GtkTreeIter child_iter;
1131
1132   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1133   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1134   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);
1135
1136   GET_CHILD_ITER (tree_model, &child_iter, iter);
1137
1138   return gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1139 }
1140
1141 static gint
1142 gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
1143                                      GtkTreeIter  *iter)
1144 {
1145   GtkTreeIter child_iter;
1146
1147   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
1148   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
1149   if (iter) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, 0);
1150
1151   if (iter == NULL)
1152     return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, NULL);
1153
1154   GET_CHILD_ITER (tree_model, &child_iter, iter);
1155
1156   return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1157 }
1158
1159 static gboolean
1160 gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
1161                                     GtkTreeIter  *iter,
1162                                     GtkTreeIter  *parent,
1163                                     gint          n)
1164 {
1165   SortLevel *level;
1166   /* We have this for the iter == parent case */
1167   GtkTreeIter children;
1168
1169   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1170   if (parent) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
1171
1172   /* Use this instead of has_child to force us to build the level, if needed */
1173   if (gtk_tree_model_sort_iter_children (tree_model, &children, parent) == FALSE)
1174     {
1175       iter->stamp = 0;
1176       return FALSE;
1177     }
1178
1179   level = children.user_data;
1180   if (n >= level->array->len)
1181     {
1182       iter->stamp = 0;
1183       return FALSE;
1184     }
1185
1186   iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
1187   iter->user_data = level;
1188   iter->user_data2 = &g_array_index (level->array, SortElt, n);
1189
1190   return TRUE;
1191 }
1192
1193 static gboolean
1194 gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
1195                                  GtkTreeIter  *iter,
1196                                  GtkTreeIter  *child)
1197 {
1198   SortLevel *level;
1199
1200   iter->stamp = 0;
1201   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1202   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1203   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == child->stamp, FALSE);
1204
1205   level = child->user_data;
1206
1207   if (level->parent_level)
1208     {
1209       iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
1210       iter->user_data = level->parent_level;
1211       iter->user_data2 = level->parent_elt;
1212
1213       return TRUE;
1214     }
1215   return FALSE;
1216 }
1217
1218 static void
1219 gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
1220                               GtkTreeIter  *iter)
1221 {
1222   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1223   GtkTreeIter child_iter;
1224   SortLevel *level;
1225   SortElt *elt;
1226
1227   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
1228   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
1229   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);
1230
1231   GET_CHILD_ITER (tree_model, &child_iter, iter);
1232
1233   gtk_tree_model_ref_node (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1234
1235   level = iter->user_data;
1236   elt = iter->user_data2;
1237
1238   elt->ref_count++;
1239   level->ref_count++;
1240   if (level->ref_count == 1)
1241     {
1242       SortLevel *parent_level = level->parent_level;
1243       SortElt *parent_elt = level->parent_elt;
1244       /* We were at zero -- time to decrement the zero_ref_count val */
1245       do
1246         {
1247           if (parent_elt)
1248             parent_elt->zero_ref_count--;
1249           else
1250             tree_model_sort->zero_ref_count--;
1251
1252           if (parent_level)
1253             {
1254               parent_elt = parent_level->parent_elt;
1255               parent_level = parent_level->parent_level;
1256             }
1257         }
1258       while (parent_level);
1259     }
1260 }
1261
1262 static void
1263 gtk_tree_model_sort_real_unref_node (GtkTreeModel *tree_model,
1264                                      GtkTreeIter  *iter,
1265                                      gboolean      propagate_unref)
1266 {
1267   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1268   GtkTreeIter child_iter;
1269   SortLevel *level;
1270   SortElt *elt;
1271
1272   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
1273   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
1274   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);
1275
1276   GET_CHILD_ITER (tree_model, &child_iter, iter);
1277
1278   if (propagate_unref)
1279     gtk_tree_model_unref_node (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1280
1281   level = iter->user_data;
1282   elt = iter->user_data2;
1283
1284   g_return_if_fail (elt->ref_count > 0);
1285
1286   elt->ref_count--;
1287   level->ref_count--;
1288
1289   if (level->ref_count == 0)
1290     {
1291       SortLevel *parent_level = level->parent_level;
1292       SortElt *parent_elt = level->parent_elt;
1293
1294       /* We are at zero -- time to increment the zero_ref_count val */
1295       while (parent_level)
1296         {
1297           parent_elt->zero_ref_count++;
1298
1299           parent_elt = parent_level->parent_elt;
1300           parent_level = parent_level->parent_level;
1301         }
1302       tree_model_sort->zero_ref_count++;
1303     }
1304 }
1305
1306 static void
1307 gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
1308                                 GtkTreeIter  *iter)
1309 {
1310   gtk_tree_model_sort_real_unref_node (tree_model, iter, TRUE);
1311 }
1312
1313 /* Sortable interface */
1314 static gboolean
1315 gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable *sortable,
1316                                         gint            *sort_column_id,
1317                                         GtkSortType     *order)
1318 {
1319   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1320
1321   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (sortable), FALSE);
1322
1323   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1324     return FALSE;
1325
1326   if (sort_column_id)
1327     *sort_column_id = tree_model_sort->sort_column_id;
1328   if (order)
1329     *order = tree_model_sort->order;
1330
1331   return TRUE;
1332 }
1333
1334 static void
1335 gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable *sortable,
1336                                         gint             sort_column_id,
1337                                         GtkSortType      order)
1338 {
1339   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1340
1341   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (sortable));
1342
1343   if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1344     {
1345       GtkTreeDataSortHeader *header = NULL;
1346
1347       header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1348                                                sort_column_id);
1349
1350       /* we want to make sure that we have a function */
1351       g_return_if_fail (header != NULL);
1352       g_return_if_fail (header->func != NULL);
1353     }
1354   else
1355     g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1356
1357   if (tree_model_sort->sort_column_id == sort_column_id)
1358     {
1359       if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1360         {
1361           if (tree_model_sort->order == order)
1362             return;
1363         }
1364       else
1365         return;
1366     }
1367
1368   tree_model_sort->sort_column_id = sort_column_id;
1369   tree_model_sort->order = order;
1370
1371   gtk_tree_sortable_sort_column_changed (sortable);
1372
1373   gtk_tree_model_sort_sort (tree_model_sort);
1374 }
1375
1376 static void
1377 gtk_tree_model_sort_set_sort_func (GtkTreeSortable        *sortable,
1378                                    gint                    sort_column_id,
1379                                    GtkTreeIterCompareFunc  func,
1380                                    gpointer                data,
1381                                    GtkDestroyNotify        destroy)
1382 {
1383   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
1384   GtkTreeDataSortHeader *header = NULL;
1385   GList *list;
1386
1387   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (sortable));
1388   g_return_if_fail (func != NULL);
1389
1390   for (list = tree_model_sort->sort_list; list; list = list->next)
1391     {
1392       GtkTreeDataSortHeader *list_header;
1393
1394       list_header = (GtkTreeDataSortHeader*) list->data;
1395       if (list_header->sort_column_id == sort_column_id)
1396         {
1397           header = list_header;
1398           break;
1399         }
1400     }
1401
1402   if (header == NULL)
1403     {
1404       header = g_new0 (GtkTreeDataSortHeader, 1);
1405       header->sort_column_id = sort_column_id;
1406       tree_model_sort->sort_list = g_list_append (tree_model_sort->sort_list,
1407                                                   header);
1408     }
1409
1410   if (header->destroy)
1411     {
1412       GtkDestroyNotify d = header->destroy;
1413
1414       header->destroy = NULL;
1415       d (header->data);
1416     }
1417
1418   header->func = func;
1419   header->data = data;
1420   header->destroy = destroy;
1421
1422   if (tree_model_sort->sort_column_id == sort_column_id)
1423     gtk_tree_model_sort_sort (tree_model_sort);
1424 }
1425
1426 static void
1427 gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
1428                                            GtkTreeIterCompareFunc  func,
1429                                            gpointer                data,
1430                                            GtkDestroyNotify        destroy)
1431 {
1432   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1433
1434   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (sortable));
1435
1436   if (tree_model_sort->default_sort_destroy)
1437     {
1438       GtkDestroyNotify d = tree_model_sort->default_sort_destroy;
1439
1440       tree_model_sort->default_sort_destroy = NULL;
1441       d (tree_model_sort->default_sort_data);
1442     }
1443
1444   tree_model_sort->default_sort_func = func;
1445   tree_model_sort->default_sort_data = data;
1446   tree_model_sort->default_sort_destroy = destroy;
1447
1448   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1449     gtk_tree_model_sort_sort (tree_model_sort);
1450 }
1451
1452 static gboolean
1453 gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable *sortable)
1454 {
1455   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1456
1457   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (sortable), FALSE);
1458
1459   return (tree_model_sort->default_sort_func != NULL);
1460 }
1461
1462 /* DragSource interface */
1463 static gboolean
1464 gtk_tree_model_sort_row_draggable (GtkTreeDragSource *drag_source,
1465                                    GtkTreePath       *path)
1466 {
1467   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1468   GtkTreePath *child_path;
1469   gboolean draggable;
1470
1471   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (drag_source), FALSE);
1472   g_return_val_if_fail (path != NULL, FALSE);
1473
1474   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort,
1475                                                                path);
1476   draggable = gtk_tree_drag_source_row_draggable (GTK_TREE_DRAG_SOURCE (tree_model_sort->child_model), child_path);
1477   gtk_tree_path_free (child_path);
1478
1479   return draggable;
1480 }
1481
1482 static gboolean
1483 gtk_tree_model_sort_drag_data_get (GtkTreeDragSource *drag_source,
1484                                    GtkTreePath       *path,
1485                                    GtkSelectionData  *selection_data)
1486 {
1487   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1488   GtkTreePath *child_path;
1489   gboolean gotten;
1490
1491   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (drag_source), FALSE);
1492   g_return_val_if_fail (path != NULL, FALSE);
1493
1494   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort,
1495                                                                path);
1496   gotten = gtk_tree_drag_source_drag_data_get (GTK_TREE_DRAG_SOURCE (tree_model_sort->child_model), child_path, selection_data);
1497   gtk_tree_path_free (child_path);
1498
1499   return gotten;
1500 }
1501
1502 static gboolean
1503 gtk_tree_model_sort_drag_data_delete (GtkTreeDragSource *drag_source,
1504                                       GtkTreePath       *path)
1505 {
1506   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1507   GtkTreePath *child_path;
1508   gboolean deleted;
1509
1510   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (drag_source), FALSE);
1511   g_return_val_if_fail (path != NULL, FALSE);
1512
1513   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort,
1514                                                                path);
1515   deleted = gtk_tree_drag_source_drag_data_delete (GTK_TREE_DRAG_SOURCE (tree_model_sort->child_model), child_path);
1516   gtk_tree_path_free (child_path);
1517
1518   return deleted;
1519 }
1520
1521 /* sorting code - private */
1522 static gint
1523 gtk_tree_model_sort_compare_func (gconstpointer a,
1524                                   gconstpointer b,
1525                                   gpointer      user_data)
1526 {
1527   SortData *data = (SortData *)user_data;
1528   GtkTreeModelSort *tree_model_sort = data->tree_model_sort;
1529   SortTuple *sa = (SortTuple *)a;
1530   SortTuple *sb = (SortTuple *)b;
1531
1532   GtkTreeIter iter_a, iter_b;
1533   gint retval;
1534
1535   /* shortcut, if we've the same offsets here, they should be equal */
1536   if (sa->offset == sb->offset)
1537     return 0;
1538
1539   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1540     {
1541       iter_a = sa->elt->iter;
1542       iter_b = sb->elt->iter;
1543     }
1544   else
1545     {
1546       data->parent_path_indices [data->parent_path_depth-1] = sa->elt->offset;
1547       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort->child_model), &iter_a, data->parent_path);
1548       data->parent_path_indices [data->parent_path_depth-1] = sb->elt->offset;
1549       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort->child_model), &iter_b, data->parent_path);
1550     }
1551
1552   retval = (* data->sort_func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1553                                 &iter_a, &iter_b,
1554                                 data->sort_data);
1555
1556   if (tree_model_sort->order == GTK_SORT_DESCENDING)
1557     {
1558       if (retval > 0)
1559         retval = -1;
1560       else if (retval < 0)
1561         retval = 1;
1562     }
1563
1564   return retval;
1565 }
1566
1567 static gint
1568 gtk_tree_model_sort_offset_compare_func (gconstpointer a,
1569                                          gconstpointer b,
1570                                          gpointer      user_data)
1571 {
1572   gint retval;
1573
1574   SortTuple *sa = (SortTuple *)a;
1575   SortTuple *sb = (SortTuple *)b;
1576
1577   SortData *data = (SortData *)user_data;
1578
1579   if (sa->elt->offset < sb->elt->offset)
1580     retval = -1;
1581   else if (sa->elt->offset > sb->elt->offset)
1582     retval = 1;
1583   else
1584     retval = 0;
1585
1586   if (data->tree_model_sort->order == GTK_SORT_DESCENDING)
1587     {
1588       if (retval > 0)
1589         retval = -1;
1590       else if (retval < 0)
1591         retval = 1;
1592     }
1593
1594   return retval;
1595 }
1596
1597 static void
1598 gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
1599                                 SortLevel        *level,
1600                                 gboolean          recurse,
1601                                 gboolean          emit_reordered)
1602 {
1603   gint i;
1604   GArray *sort_array;
1605   GArray *new_array;
1606   gint *new_order;
1607
1608   GtkTreeIter iter;
1609   GtkTreePath *path;
1610
1611   SortData data;
1612
1613   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
1614   g_return_if_fail (level != NULL);
1615
1616   if (level->array->len < 1 && !((SortElt *)level->array->data)->children)
1617     return;
1618
1619   /* Set up data */
1620   data.tree_model_sort = tree_model_sort;
1621   if (level->parent_elt)
1622     {
1623       data.parent_path = gtk_tree_model_sort_elt_get_path (level->parent_level,
1624                                                            level->parent_elt);
1625       gtk_tree_path_append_index (data.parent_path, 0);
1626     }
1627   else
1628     {
1629       data.parent_path = gtk_tree_path_new_first ();
1630     }
1631   data.parent_path_depth = gtk_tree_path_get_depth (data.parent_path);
1632   data.parent_path_indices = gtk_tree_path_get_indices (data.parent_path);
1633
1634   /* make the array to be sorted */
1635   sort_array = g_array_sized_new (FALSE, FALSE, sizeof (SortTuple), level->array->len);
1636   for (i = 0; i < level->array->len; i++)
1637     {
1638       SortTuple tuple;
1639
1640       tuple.elt = &g_array_index (level->array, SortElt, i);
1641       tuple.offset = i;
1642
1643       g_array_append_val (sort_array, tuple);
1644     }
1645
1646     if (tree_model_sort->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1647       {
1648         GtkTreeDataSortHeader *header = NULL;
1649
1650         header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1651                                                  tree_model_sort->sort_column_id);
1652
1653         g_return_if_fail (header != NULL);
1654         g_return_if_fail (header->func != NULL);
1655
1656         data.sort_func = header->func;
1657         data.sort_data = header->data;
1658       }
1659     else
1660       {
1661         /* absolutely SHOULD NOT happen: */
1662         g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1663
1664         data.sort_func = tree_model_sort->default_sort_func;
1665         data.sort_data = tree_model_sort->default_sort_data;
1666       }
1667
1668   if (data.sort_func == NO_SORT_FUNC)
1669     g_array_sort_with_data (sort_array,
1670                             gtk_tree_model_sort_offset_compare_func,
1671                             &data);
1672   else
1673     g_array_sort_with_data (sort_array,
1674                             gtk_tree_model_sort_compare_func,
1675                             &data);
1676
1677   gtk_tree_path_free (data.parent_path);
1678
1679   new_array = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), level->array->len);
1680   new_order = g_new (gint, level->array->len);
1681
1682   for (i = 0; i < level->array->len; i++)
1683     {
1684       SortElt *elt;
1685
1686       elt = g_array_index (sort_array, SortTuple, i).elt;
1687       new_order[i] = g_array_index (sort_array, SortTuple, i).offset;
1688
1689       g_array_append_val (new_array, *elt);
1690       elt = &g_array_index (new_array, SortElt, i);
1691       if (elt->children)
1692         elt->children->parent_elt = elt;
1693     }
1694
1695   g_array_free (level->array, TRUE);
1696   level->array = new_array;
1697   g_array_free (sort_array, TRUE);
1698
1699   if (emit_reordered)
1700     {
1701       gtk_tree_model_sort_increment_stamp (tree_model_sort);
1702       if (level->parent_elt)
1703         {
1704           iter.stamp = tree_model_sort->stamp;
1705           iter.user_data = level->parent_level;
1706           iter.user_data2 = level->parent_elt;
1707
1708           path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort),
1709                                           &iter);
1710
1711           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1712                                          &iter, new_order);
1713         }
1714       else
1715         {
1716           /* toplevel list */
1717           path = gtk_tree_path_new ();
1718           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1719                                          NULL, new_order);
1720         }
1721
1722       gtk_tree_path_free (path);
1723     }
1724
1725   /* recurse, if possible */
1726   if (recurse)
1727     {
1728       for (i = 0; i < level->array->len; i++)
1729         {
1730           SortElt *elt = &g_array_index (level->array, SortElt, i);
1731
1732           if (elt->children)
1733             gtk_tree_model_sort_sort_level (tree_model_sort,
1734                                             elt->children,
1735                                             TRUE, emit_reordered);
1736         }
1737     }
1738
1739   g_free (new_order);
1740 }
1741
1742 static void
1743 gtk_tree_model_sort_sort (GtkTreeModelSort *tree_model_sort)
1744 {
1745   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
1746
1747   if (!tree_model_sort->root)
1748     return;
1749
1750   if (tree_model_sort->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1751     {
1752       GtkTreeDataSortHeader *header = NULL;
1753
1754       header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1755                                                tree_model_sort->sort_column_id);
1756
1757       /* we want to make sure that we have a function */
1758       g_return_if_fail (header != NULL);
1759       g_return_if_fail (header->func != NULL);
1760     }
1761   else
1762     g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1763
1764   gtk_tree_model_sort_sort_level (tree_model_sort, tree_model_sort->root,
1765                                   TRUE, TRUE);
1766 }
1767
1768 /* signal helpers */
1769 static gint
1770 gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
1771                                        SortLevel        *level,
1772                                        GtkTreeIter      *iter,
1773                                        gint             skip_index)
1774 {
1775   gint start, middle, end;
1776   gint cmp;
1777   SortElt *tmp_elt;
1778   GtkTreeIter tmp_iter;
1779
1780   GtkTreeIterCompareFunc func;
1781   gpointer data;
1782
1783   if (tree_model_sort->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1784     {
1785       GtkTreeDataSortHeader *header;
1786
1787       header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1788                                                tree_model_sort->sort_column_id);
1789
1790       g_return_val_if_fail (header != NULL, 0);
1791
1792       func = header->func;
1793       data = header->data;
1794     }
1795   else
1796     {
1797       func = tree_model_sort->default_sort_func;
1798       data = tree_model_sort->default_sort_data;
1799
1800       g_return_val_if_fail (func != NO_SORT_FUNC, 0);
1801     }
1802
1803   g_return_val_if_fail (func != NULL, 0);
1804
1805   start = 0;
1806   end = level->array->len;
1807   if (skip_index < 0)
1808     skip_index = end;
1809   else
1810     end--;
1811
1812   if (start == end)
1813     return 0;
1814
1815   while (start != end)
1816     {
1817       middle = (start + end) / 2;
1818
1819       if (middle < skip_index)
1820         tmp_elt = &(g_array_index (level->array, SortElt, middle));
1821       else
1822         tmp_elt = &(g_array_index (level->array, SortElt, middle + 1));
1823
1824       if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1825         {
1826           GtkTreePath *path = gtk_tree_model_sort_elt_get_path (level, tmp_elt);
1827           gtk_tree_model_get_iter (tree_model_sort->child_model,
1828                                    &tmp_iter, path);
1829           gtk_tree_path_free (path);
1830         }
1831       else
1832         tmp_iter = tmp_elt->iter;
1833
1834       if (tree_model_sort->order == GTK_SORT_ASCENDING)
1835         cmp = (* func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1836                         &tmp_iter, iter, data);
1837       else
1838         cmp = (* func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1839                         iter, &tmp_iter, data);
1840
1841       if (cmp <= 0)
1842         start = middle + 1;
1843       else
1844         end = middle;
1845     }
1846
1847   if (cmp <= 0)
1848     return middle + 1;
1849   else
1850     return middle;
1851 }
1852
1853 static gboolean
1854 gtk_tree_model_sort_insert_value (GtkTreeModelSort *tree_model_sort,
1855                                   SortLevel        *level,
1856                                   GtkTreePath      *s_path,
1857                                   GtkTreeIter      *s_iter)
1858 {
1859   gint offset, index, i;
1860
1861   SortElt elt;
1862   SortElt *tmp_elt;
1863
1864   offset = gtk_tree_path_get_indices (s_path)[gtk_tree_path_get_depth (s_path) - 1];
1865
1866   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1867     elt.iter = *s_iter;
1868   elt.offset = offset;
1869   elt.zero_ref_count = 0;
1870   elt.ref_count = 0;
1871   elt.children = NULL;
1872
1873   /* update all larger offsets */
1874   tmp_elt = SORT_ELT (level->array->data);
1875   for (i = 0; i < level->array->len; i++, tmp_elt++)
1876     if (tmp_elt->offset >= offset)
1877       tmp_elt->offset++;
1878
1879   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
1880       tree_model_sort->default_sort_func == NO_SORT_FUNC)
1881     index = offset;
1882   else
1883     index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
1884                                                    level, s_iter,
1885                                                    -1);
1886
1887   g_array_insert_vals (level->array, index, &elt, 1);
1888   tmp_elt = SORT_ELT (level->array->data);
1889   for (i = 0; i < level->array->len; i++, tmp_elt++)
1890     if (tmp_elt->children)
1891       tmp_elt->children->parent_elt = tmp_elt;
1892
1893   return TRUE;
1894 }
1895
1896 /* sort elt stuff */
1897 static GtkTreePath *
1898 gtk_tree_model_sort_elt_get_path (SortLevel *level,
1899                                   SortElt *elt)
1900 {
1901   SortLevel *walker = level;
1902   SortElt *walker2 = elt;
1903   GtkTreePath *path;
1904
1905   g_return_val_if_fail (level != NULL, NULL);
1906   g_return_val_if_fail (elt != NULL, NULL);
1907
1908   path = gtk_tree_path_new ();
1909
1910   while (walker)
1911     {
1912       gtk_tree_path_prepend_index (path, walker2->offset);
1913
1914       walker2 = walker->parent_elt;
1915       walker = walker->parent_level;
1916     }
1917
1918   return path;
1919 }
1920
1921 /**
1922  * gtk_tree_model_sort_set_model:
1923  * @tree_model_sort: The #GtkTreeModelSort.
1924  * @child_model: A #GtkTreeModel, or NULL.
1925  *
1926  * Sets the model of @tree_model_sort to be @model.  If @model is NULL, then the
1927  * old model is unset.  The sort function is unset as a result of this call.
1928  * The model will be in an unsorted state until a sort function is set.
1929  **/
1930 static void
1931 gtk_tree_model_sort_set_model (GtkTreeModelSort *tree_model_sort,
1932                                GtkTreeModel     *child_model)
1933 {
1934   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
1935
1936   if (child_model)
1937     g_object_ref (child_model);
1938
1939   if (tree_model_sort->child_model)
1940     {
1941       g_signal_handler_disconnect (tree_model_sort->child_model,
1942                                    tree_model_sort->changed_id);
1943       g_signal_handler_disconnect (tree_model_sort->child_model,
1944                                    tree_model_sort->inserted_id);
1945       g_signal_handler_disconnect (tree_model_sort->child_model,
1946                                    tree_model_sort->has_child_toggled_id);
1947       g_signal_handler_disconnect (tree_model_sort->child_model,
1948                                    tree_model_sort->deleted_id);
1949       g_signal_handler_disconnect (tree_model_sort->child_model,
1950                                    tree_model_sort->reordered_id);
1951
1952       /* reset our state */
1953       if (tree_model_sort->root)
1954         gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
1955       tree_model_sort->root = NULL;
1956       _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
1957       tree_model_sort->sort_list = NULL;
1958       g_object_unref (tree_model_sort->child_model);
1959     }
1960
1961   tree_model_sort->child_model = child_model;
1962
1963   if (child_model)
1964     {
1965       GType *types;
1966       gint i, n_columns;
1967
1968       tree_model_sort->changed_id =
1969         g_signal_connect (child_model, "row_changed",
1970                           G_CALLBACK (gtk_tree_model_sort_row_changed),
1971                           tree_model_sort);
1972       tree_model_sort->inserted_id =
1973         g_signal_connect (child_model, "row_inserted",
1974                           G_CALLBACK (gtk_tree_model_sort_row_inserted),
1975                           tree_model_sort);
1976       tree_model_sort->has_child_toggled_id =
1977         g_signal_connect (child_model, "row_has_child_toggled",
1978                           G_CALLBACK (gtk_tree_model_sort_row_has_child_toggled),
1979                           tree_model_sort);
1980       tree_model_sort->deleted_id =
1981         g_signal_connect (child_model, "row_deleted",
1982                           G_CALLBACK (gtk_tree_model_sort_row_deleted),
1983                           tree_model_sort);
1984       tree_model_sort->reordered_id =
1985         g_signal_connect (child_model, "rows_reordered",
1986                           G_CALLBACK (gtk_tree_model_sort_rows_reordered),
1987                           tree_model_sort);
1988
1989       tree_model_sort->child_flags = gtk_tree_model_get_flags (child_model);
1990       n_columns = gtk_tree_model_get_n_columns (child_model);
1991
1992       types = g_new (GType, n_columns);
1993       for (i = 0; i < n_columns; i++)
1994         types[i] = gtk_tree_model_get_column_type (child_model, i);
1995
1996       tree_model_sort->sort_list = _gtk_tree_data_list_header_new (n_columns, types);
1997       g_free (types);
1998
1999       tree_model_sort->default_sort_func = NO_SORT_FUNC;
2000       tree_model_sort->stamp = g_random_int ();
2001     }
2002 }
2003
2004 /**
2005  * gtk_tree_model_sort_get_model:
2006  * @tree_model: a #GtkTreeModelSort
2007  *
2008  * Returns the model the #GtkTreeModelSort is sorting.
2009  *
2010  * Return value: the "child model" being sorted
2011  **/
2012 GtkTreeModel *
2013 gtk_tree_model_sort_get_model (GtkTreeModelSort  *tree_model)
2014 {
2015   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
2016
2017   return tree_model->child_model;
2018 }
2019
2020
2021 static GtkTreePath *
2022 gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
2023                                                      GtkTreePath      *child_path,
2024                                                      gboolean          build_levels)
2025 {
2026   gint *child_indices;
2027   GtkTreePath *retval;
2028   SortLevel *level;
2029   gint i;
2030
2031   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2032   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
2033   g_return_val_if_fail (child_path != NULL, NULL);
2034
2035   retval = gtk_tree_path_new ();
2036   child_indices = gtk_tree_path_get_indices (child_path);
2037
2038   if (tree_model_sort->root == NULL && build_levels)
2039     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
2040   level = SORT_LEVEL (tree_model_sort->root);
2041
2042   for (i = 0; i < gtk_tree_path_get_depth (child_path); i++)
2043     {
2044       gint j;
2045       gboolean found_child = FALSE;
2046
2047       if (!level)
2048         {
2049           gtk_tree_path_free (retval);
2050           return NULL;
2051         }
2052
2053       if (child_indices[i] >= level->array->len)
2054         {
2055           gtk_tree_path_free (retval);
2056           return NULL;
2057         }
2058       for (j = 0; j < level->array->len; j++)
2059         {
2060           if ((g_array_index (level->array, SortElt, j)).offset == child_indices[i])
2061             {
2062               gtk_tree_path_append_index (retval, j);
2063               if (g_array_index (level->array, SortElt, j).children == NULL && build_levels)
2064                 {
2065                   gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, j));
2066                 }
2067               level = g_array_index (level->array, SortElt, j).children;
2068               found_child = TRUE;
2069               break;
2070             }
2071         }
2072       if (! found_child)
2073         {
2074           gtk_tree_path_free (retval);
2075           return NULL;
2076         }
2077     }
2078
2079   return retval;
2080 }
2081
2082
2083 /**
2084  * gtk_tree_model_sort_convert_child_path_to_path:
2085  * @tree_model_sort: A #GtkTreeModelSort
2086  * @child_path: A #GtkTreePath to convert
2087  *
2088  * Converts @child_path to a path relative to @tree_model_sort.  That is,
2089  * @child_path points to a path in the child model.  The returned path will
2090  * point to the same row in the sorted model.  If @child_path isn't a valid path
2091  * on the child model, then %NULL is returned.
2092  *
2093  * Return value: A newly allocated #GtkTreePath, or %NULL
2094  **/
2095 GtkTreePath *
2096 gtk_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
2097                                                 GtkTreePath      *child_path)
2098 {
2099   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2100   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
2101   g_return_val_if_fail (child_path != NULL, NULL);
2102
2103   return gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path, TRUE);
2104 }
2105
2106 /**
2107  * gtk_tree_model_sort_convert_child_iter_to_iter:
2108  * @tree_model_sort: A #GtkTreeModelSort
2109  * @sort_iter: An uninitialized #GtkTreeIter.
2110  * @child_iter: A valid #GtkTreeIter pointing to a row on the child model
2111  *
2112  * Sets @sort_iter to point to the row in @tree_model_sort that corresponds to
2113  * the row pointed at by @child_iter.
2114  **/
2115 void
2116 gtk_tree_model_sort_convert_child_iter_to_iter (GtkTreeModelSort *tree_model_sort,
2117                                                 GtkTreeIter      *sort_iter,
2118                                                 GtkTreeIter      *child_iter)
2119 {
2120   GtkTreePath *child_path, *path;
2121
2122   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2123   g_return_if_fail (tree_model_sort->child_model != NULL);
2124   g_return_if_fail (sort_iter != NULL);
2125   g_return_if_fail (child_iter != NULL);
2126
2127   sort_iter->stamp = 0;
2128
2129   child_path = gtk_tree_model_get_path (tree_model_sort->child_model, child_iter);
2130   g_return_if_fail (child_path != NULL);
2131
2132   path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path);
2133   gtk_tree_path_free (child_path);
2134   g_return_if_fail (path != NULL);
2135
2136   gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort), sort_iter, path);
2137   gtk_tree_path_free (path);
2138 }
2139
2140 /**
2141  * gtk_tree_model_sort_convert_path_to_child_path:
2142  * @tree_model_sort: A #GtkTreeModelSort
2143  * @sorted_path: A #GtkTreePath to convert
2144  *
2145  * Converts @sorted_path to a path on the child model of @tree_model_sort.  That
2146  * is, @sorted_path points to a location in @tree_model_sort.  The returned path
2147  * will point to the same location in the model not being sorted.  If @sorted_path
2148  * does not point to a location in the child model, %NULL is returned.
2149  *
2150  * Return value: A newly allocated #GtkTreePath, or %NULL
2151  **/
2152 GtkTreePath *
2153 gtk_tree_model_sort_convert_path_to_child_path (GtkTreeModelSort *tree_model_sort,
2154                                                 GtkTreePath      *sorted_path)
2155 {
2156   gint *sorted_indices;
2157   GtkTreePath *retval;
2158   SortLevel *level;
2159   gint i;
2160
2161   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2162   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
2163   g_return_val_if_fail (sorted_path != NULL, NULL);
2164
2165   retval = gtk_tree_path_new ();
2166   sorted_indices = gtk_tree_path_get_indices (sorted_path);
2167   if (tree_model_sort->root == NULL)
2168     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
2169   level = SORT_LEVEL (tree_model_sort->root);
2170
2171   for (i = 0; i < gtk_tree_path_get_depth (sorted_path); i++)
2172     {
2173       gint count = sorted_indices[i];
2174
2175       if ((level == NULL) ||
2176           (level->array->len <= count))
2177         {
2178           gtk_tree_path_free (retval);
2179           return NULL;
2180         }
2181
2182       if (g_array_index (level->array, SortElt, count).children == NULL)
2183         gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, count));
2184
2185       if (level == NULL)
2186         {
2187           gtk_tree_path_free (retval);
2188           break;
2189         }
2190
2191       gtk_tree_path_append_index (retval, g_array_index (level->array, SortElt, count).offset);
2192       level = g_array_index (level->array, SortElt, count).children;
2193     }
2194
2195   return retval;
2196 }
2197
2198 /**
2199  * gtk_tree_model_sort_convert_iter_to_child_iter:
2200  * @tree_model_sort: A #GtkTreeModelSort
2201  * @child_iter: An uninitialized #GtkTreeIter
2202  * @sorted_iter: A valid #GtkTreeIter pointing to a row on @tree_model_sort.
2203  *
2204  * Sets @child_iter to point to the row pointed to by @sorted_iter.
2205  **/
2206 void
2207 gtk_tree_model_sort_convert_iter_to_child_iter (GtkTreeModelSort *tree_model_sort,
2208                                                 GtkTreeIter      *child_iter,
2209                                                 GtkTreeIter      *sorted_iter)
2210 {
2211   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2212   g_return_if_fail (tree_model_sort->child_model != NULL);
2213   g_return_if_fail (child_iter != NULL);
2214   g_return_if_fail (sorted_iter != NULL);
2215   g_return_if_fail (sorted_iter->stamp == tree_model_sort->stamp);
2216
2217   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2218     {
2219       *child_iter = SORT_ELT (sorted_iter->user_data2)->iter;
2220     }
2221   else
2222     {
2223       GtkTreePath *path;
2224
2225       path = gtk_tree_model_sort_elt_get_path (sorted_iter->user_data,
2226                                                sorted_iter->user_data2);
2227       gtk_tree_model_get_iter (tree_model_sort->child_model, child_iter, path);
2228       gtk_tree_path_free (path);
2229     }
2230 }
2231
2232 static void
2233 gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
2234                                  SortLevel        *parent_level,
2235                                  SortElt          *parent_elt)
2236 {
2237   GtkTreeIter iter;
2238   SortLevel *new_level;
2239   gint length = 0;
2240   gint i;
2241
2242   g_assert (tree_model_sort->child_model != NULL);
2243
2244   if (parent_level == NULL)
2245     {
2246       if (gtk_tree_model_get_iter_first (tree_model_sort->child_model, &iter) == FALSE)
2247         return;
2248       length = gtk_tree_model_iter_n_children (tree_model_sort->child_model, NULL);
2249     }
2250   else
2251     {
2252       GtkTreeIter parent_iter;
2253       GtkTreeIter child_parent_iter;
2254
2255       parent_iter.stamp = tree_model_sort->stamp;
2256       parent_iter.user_data = parent_level;
2257       parent_iter.user_data2 = parent_elt;
2258
2259       gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2260                                                       &child_parent_iter,
2261                                                       &parent_iter);
2262       if (gtk_tree_model_iter_children (tree_model_sort->child_model,
2263                                         &iter,
2264                                         &child_parent_iter) == FALSE)
2265         return;
2266
2267       /* stamp may have changed */
2268       gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2269                                                       &child_parent_iter,
2270                                                       &parent_iter);
2271
2272       length = gtk_tree_model_iter_n_children (tree_model_sort->child_model, &child_parent_iter);
2273     }
2274
2275   g_return_if_fail (length > 0);
2276
2277   new_level = g_new (SortLevel, 1);
2278   new_level->array = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), length);
2279   new_level->ref_count = 0;
2280   new_level->parent_elt = parent_elt;
2281   new_level->parent_level = parent_level;
2282
2283   if (parent_elt)
2284     parent_elt->children = new_level;
2285   else
2286     tree_model_sort->root = new_level;
2287
2288   /* increase the count of zero ref_counts.*/
2289   while (parent_level)
2290     {
2291       parent_elt->zero_ref_count++;
2292
2293       parent_elt = parent_level->parent_elt;
2294       parent_level = parent_level->parent_level;
2295     }
2296   if (new_level != tree_model_sort->root)
2297     tree_model_sort->zero_ref_count++;
2298
2299   for (i = 0; i < length; i++)
2300     {
2301       SortElt sort_elt;
2302       sort_elt.offset = i;
2303       sort_elt.zero_ref_count = 0;
2304       sort_elt.ref_count = 0;
2305       sort_elt.children = NULL;
2306
2307       if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2308         {
2309           sort_elt.iter = iter;
2310           if (gtk_tree_model_iter_next (tree_model_sort->child_model, &iter) == FALSE &&
2311               i < length - 1)
2312             {
2313               g_warning ("There is a discrepency between the sort model and the child model.");
2314               return;
2315             }
2316         }
2317       g_array_append_val (new_level->array, sort_elt);
2318     }
2319
2320   /* sort level */
2321   gtk_tree_model_sort_sort_level (tree_model_sort, new_level,
2322                                   FALSE, FALSE);
2323 }
2324
2325 static void
2326 gtk_tree_model_sort_free_level (GtkTreeModelSort *tree_model_sort,
2327                                 SortLevel        *sort_level)
2328 {
2329   gint i;
2330
2331   g_assert (sort_level);
2332
2333   if (sort_level->ref_count == 0)
2334     {
2335       SortLevel *parent_level = sort_level->parent_level;
2336       SortElt *parent_elt = sort_level->parent_elt;
2337
2338       do
2339         {
2340           if (parent_elt)
2341             parent_elt->zero_ref_count--;
2342           else
2343             tree_model_sort->zero_ref_count--;
2344
2345           if (parent_level)
2346             {
2347               parent_elt = parent_level->parent_elt;
2348               parent_level = parent_level->parent_level;
2349             }
2350         }
2351       while (parent_level);
2352     }
2353
2354   for (i = 0; i < sort_level->array->len; i++)
2355     {
2356       if (g_array_index (sort_level->array, SortElt, i).children)
2357         gtk_tree_model_sort_free_level (tree_model_sort,
2358                                         SORT_LEVEL(g_array_index (sort_level->array, SortElt, i).children));
2359     }
2360
2361   if (sort_level->parent_elt)
2362     sort_level->parent_elt->children = NULL;
2363   else
2364     tree_model_sort->root = NULL;
2365
2366   g_array_free (sort_level->array, TRUE);
2367   sort_level->array = NULL;
2368
2369   g_free (sort_level);
2370   sort_level = NULL;
2371 }
2372
2373 static void
2374 gtk_tree_model_sort_increment_stamp (GtkTreeModelSort *tree_model_sort)
2375 {
2376   do
2377     {
2378       tree_model_sort->stamp++;
2379     }
2380   while (tree_model_sort->stamp == 0);
2381
2382   gtk_tree_model_sort_clear_cache (tree_model_sort);
2383 }
2384
2385 static void
2386 gtk_tree_model_sort_clear_cache_helper (GtkTreeModelSort *tree_model_sort,
2387                                         SortLevel        *level)
2388 {
2389   gint i;
2390
2391   g_assert (level != NULL);
2392
2393   for (i = 0; i < level->array->len; i++)
2394     {
2395       if (g_array_index (level->array, SortElt, i).zero_ref_count > 0)
2396         gtk_tree_model_sort_clear_cache_helper (tree_model_sort, g_array_index (level->array, SortElt, i).children);
2397     }
2398
2399   if (level->ref_count == 0 && level != tree_model_sort->root)
2400     gtk_tree_model_sort_free_level (tree_model_sort, level);
2401 }
2402
2403 /**
2404  * gtk_tree_model_sort_reset_default_sort_func:
2405  * @tree_model_sort: A #GtkTreeModelSort
2406  *
2407  * This resets the default sort function to be in the 'unsorted' state.  That
2408  * is, it is in the same order as the child model. It will re-sort the model
2409  * to be in the same order as the child model only if the #GtkTreeModelSort
2410  * is in 'unsorted' state.
2411  **/
2412 void
2413 gtk_tree_model_sort_reset_default_sort_func (GtkTreeModelSort *tree_model_sort)
2414 {
2415   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2416
2417   if (tree_model_sort->default_sort_destroy)
2418     {
2419       GtkDestroyNotify d = tree_model_sort->default_sort_destroy;
2420
2421       tree_model_sort->default_sort_destroy = NULL;
2422       d (tree_model_sort->default_sort_data);
2423     }
2424
2425   tree_model_sort->default_sort_func = NO_SORT_FUNC;
2426   tree_model_sort->default_sort_data = NULL;
2427   tree_model_sort->default_sort_destroy = NULL;
2428
2429   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
2430     gtk_tree_model_sort_sort (tree_model_sort);
2431   tree_model_sort->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
2432 }
2433
2434 /**
2435  * gtk_tree_model_sort_clear_cache:
2436  * @tree_model_sort: A #GtkTreeModelSort
2437  *
2438  * This function should almost never be called.  It clears the @tree_model_sort
2439  * of any cached iterators that haven't been reffed with
2440  * gtk_tree_model_ref_node().  This might be useful if the child model being
2441  * sorted is static (and doesn't change often) and there has been a lot of
2442  * unreffed access to nodes.  As a side effect of this function, all unreffed
2443  * iters will be invalid.
2444  **/
2445 void
2446 gtk_tree_model_sort_clear_cache (GtkTreeModelSort *tree_model_sort)
2447 {
2448   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2449
2450   if (tree_model_sort->zero_ref_count)
2451     gtk_tree_model_sort_clear_cache_helper (tree_model_sort, (SortLevel *)tree_model_sort->root);
2452 }
2453
2454 static gboolean
2455 gtk_tree_model_sort_iter_is_valid_helper (GtkTreeIter *iter,
2456                                           SortLevel   *level)
2457 {
2458   gint i;
2459
2460   for (i = 0; i < level->array->len; i++)
2461     {
2462       SortElt *elt = &g_array_index (level->array, SortElt, i);
2463
2464       if (iter->user_data == level && iter->user_data2 == elt)
2465         return TRUE;
2466
2467       if (elt->children)
2468         if (gtk_tree_model_sort_iter_is_valid_helper (iter, elt->children))
2469           return TRUE;
2470     }
2471
2472   return FALSE;
2473 }
2474
2475 /**
2476  * gtk_tree_model_sort_iter_is_valid:
2477  * @tree_model_sort: A #GtkTreeModelSort.
2478  * @iter: A #GtkTreeIter.
2479  *
2480  * WARNING: This function is slow. Only use it for debugging and/or testing
2481  * purposes.
2482  *
2483  * Checks if the given iter is a valid iter for this #GtkTreeModelSort.
2484  *
2485  * Return value: %TRUE if the iter is valid, %FALSE if the iter is invalid.
2486  *
2487  * Since: 2.2
2488  **/
2489 gboolean
2490 gtk_tree_model_sort_iter_is_valid (GtkTreeModelSort *tree_model_sort,
2491                                    GtkTreeIter      *iter)
2492 {
2493   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), FALSE);
2494   g_return_val_if_fail (iter != NULL, FALSE);
2495
2496   if (!VALID_ITER (iter, tree_model_sort))
2497     return FALSE;
2498
2499   return gtk_tree_model_sort_iter_is_valid_helper (iter,
2500                                                    tree_model_sort->root);
2501 }