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