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