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

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