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