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   if (g_sequence_iter_is_begin (elt->siter))
1410     {
1411       iter->stamp = 0;
1412       return FALSE;
1413     }
1414
1415   siter = g_sequence_iter_prev (elt->siter);
1416   iter->user_data2 = GET_ELT (siter);
1417
1418   return TRUE;
1419 }
1420
1421 static gboolean
1422 gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
1423                                    GtkTreeIter  *iter,
1424                                    GtkTreeIter  *parent)
1425 {
1426   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1427   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1428   SortLevel *level;
1429
1430   iter->stamp = 0;
1431   g_return_val_if_fail (priv->child_model != NULL, FALSE);
1432   if (parent)
1433     g_return_val_if_fail (VALID_ITER (parent, tree_model_sort), FALSE);
1434
1435   if (parent == NULL)
1436     {
1437       if (priv->root == NULL)
1438         gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1439       if (priv->root == NULL)
1440         return FALSE;
1441
1442       level = priv->root;
1443       iter->stamp = priv->stamp;
1444       iter->user_data = level;
1445       iter->user_data2 = g_sequence_get (g_sequence_get_begin_iter (level->seq));
1446     }
1447   else
1448     {
1449       SortElt *elt;
1450
1451       level = SORT_LEVEL (parent->user_data);
1452       elt = SORT_ELT (parent->user_data2);
1453
1454       if (elt->children == NULL)
1455         gtk_tree_model_sort_build_level (tree_model_sort, level, elt);
1456
1457       if (elt->children == NULL)
1458         return FALSE;
1459
1460       iter->stamp = priv->stamp;
1461       iter->user_data = elt->children;
1462       iter->user_data2 = g_sequence_get (g_sequence_get_begin_iter (elt->children->seq));
1463     }
1464
1465   return TRUE;
1466 }
1467
1468 static gboolean
1469 gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
1470                                     GtkTreeIter  *iter)
1471 {
1472   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1473   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1474   GtkTreeIter child_iter;
1475
1476   g_return_val_if_fail (priv->child_model != NULL, FALSE);
1477   g_return_val_if_fail (VALID_ITER (iter, tree_model_sort), FALSE);
1478
1479   GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1480
1481   return gtk_tree_model_iter_has_child (priv->child_model, &child_iter);
1482 }
1483
1484 static gint
1485 gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
1486                                      GtkTreeIter  *iter)
1487 {
1488   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1489   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1490   GtkTreeIter child_iter;
1491
1492   g_return_val_if_fail (priv->child_model != NULL, 0);
1493   if (iter)
1494     g_return_val_if_fail (VALID_ITER (iter, tree_model_sort), 0);
1495
1496   if (iter == NULL)
1497     return gtk_tree_model_iter_n_children (priv->child_model, NULL);
1498
1499   GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1500
1501   return gtk_tree_model_iter_n_children (priv->child_model, &child_iter);
1502 }
1503
1504 static gboolean
1505 gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
1506                                     GtkTreeIter  *iter,
1507                                     GtkTreeIter  *parent,
1508                                     gint          n)
1509 {
1510   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1511   SortLevel *level;
1512   /* We have this for the iter == parent case */
1513   GtkTreeIter children;
1514
1515   if (parent)
1516     g_return_val_if_fail (VALID_ITER (parent, tree_model_sort), FALSE);
1517
1518   /* Use this instead of has_child to force us to build the level, if needed */
1519   if (gtk_tree_model_sort_iter_children (tree_model, &children, parent) == FALSE)
1520     {
1521       iter->stamp = 0;
1522       return FALSE;
1523     }
1524
1525   level = children.user_data;
1526   if (n >= g_sequence_get_length (level->seq))
1527     {
1528       iter->stamp = 0;
1529       return FALSE;
1530     }
1531
1532   iter->stamp = tree_model_sort->priv->stamp;
1533   iter->user_data = level;
1534   iter->user_data2 = g_sequence_get (g_sequence_get_iter_at_pos (level->seq, n));
1535
1536   return TRUE;
1537 }
1538
1539 static gboolean
1540 gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
1541                                  GtkTreeIter  *iter,
1542                                  GtkTreeIter  *child)
1543 {
1544   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1545   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1546   SortLevel *level;
1547
1548   iter->stamp = 0;
1549   g_return_val_if_fail (priv->child_model != NULL, FALSE);
1550   g_return_val_if_fail (VALID_ITER (child, tree_model_sort), FALSE);
1551
1552   level = child->user_data;
1553
1554   if (level->parent_level)
1555     {
1556       iter->stamp = priv->stamp;
1557       iter->user_data = level->parent_level;
1558       iter->user_data2 = level->parent_elt;
1559
1560       return TRUE;
1561     }
1562   return FALSE;
1563 }
1564
1565 static void
1566 gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
1567                               GtkTreeIter  *iter)
1568 {
1569   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1570   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1571   GtkTreeIter child_iter;
1572   SortLevel *level;
1573   SortElt *elt;
1574
1575   g_return_if_fail (priv->child_model != NULL);
1576   g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1577
1578   GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1579
1580   /* Reference the node in the child model */
1581   gtk_tree_model_ref_node (priv->child_model, &child_iter);
1582
1583   /* Increase the reference count of this element and its level */
1584   level = iter->user_data;
1585   elt = iter->user_data2;
1586
1587   elt->ref_count++;
1588   level->ref_count++;
1589
1590   if (level->ref_count == 1)
1591     {
1592       SortLevel *parent_level = level->parent_level;
1593       SortElt *parent_elt = level->parent_elt;
1594
1595       /* We were at zero -- time to decrement the zero_ref_count val */
1596       while (parent_level)
1597         {
1598           parent_elt->zero_ref_count--;
1599
1600           parent_elt = parent_level->parent_elt;
1601           parent_level = parent_level->parent_level;
1602         }
1603
1604       if (priv->root != level)
1605         priv->zero_ref_count--;
1606     }
1607 }
1608
1609 static void
1610 gtk_tree_model_sort_real_unref_node (GtkTreeModel *tree_model,
1611                                      GtkTreeIter  *iter,
1612                                      gboolean      propagate_unref)
1613 {
1614   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1615   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1616   SortLevel *level;
1617   SortElt *elt;
1618
1619   g_return_if_fail (priv->child_model != NULL);
1620   g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1621
1622   if (propagate_unref)
1623     {
1624       GtkTreeIter child_iter;
1625
1626       GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1627       gtk_tree_model_unref_node (priv->child_model, &child_iter);
1628     }
1629
1630   level = iter->user_data;
1631   elt = iter->user_data2;
1632
1633   g_return_if_fail (elt->ref_count > 0);
1634
1635   elt->ref_count--;
1636   level->ref_count--;
1637
1638   if (level->ref_count == 0)
1639     {
1640       SortLevel *parent_level = level->parent_level;
1641       SortElt *parent_elt = level->parent_elt;
1642
1643       /* We are at zero -- time to increment the zero_ref_count val */
1644       while (parent_level)
1645         {
1646           parent_elt->zero_ref_count++;
1647
1648           parent_elt = parent_level->parent_elt;
1649           parent_level = parent_level->parent_level;
1650         }
1651
1652       if (priv->root != level)
1653         priv->zero_ref_count++;
1654     }
1655 }
1656
1657 static void
1658 gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
1659                                 GtkTreeIter  *iter)
1660 {
1661   gtk_tree_model_sort_real_unref_node (tree_model, iter, TRUE);
1662 }
1663
1664 /* Sortable interface */
1665 static gboolean
1666 gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable *sortable,
1667                                         gint            *sort_column_id,
1668                                         GtkSortType     *order)
1669 {
1670   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1671   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1672
1673   if (sort_column_id)
1674     *sort_column_id = priv->sort_column_id;
1675   if (order)
1676     *order = priv->order;
1677
1678   if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID ||
1679       priv->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
1680     return FALSE;
1681
1682   return TRUE;
1683 }
1684
1685 static void
1686 gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable *sortable,
1687                                         gint             sort_column_id,
1688                                         GtkSortType      order)
1689 {
1690   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1691   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1692
1693   if (sort_column_id != GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
1694     {
1695       if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1696         {
1697           GtkTreeDataSortHeader *header = NULL;
1698
1699           header = _gtk_tree_data_list_get_header (priv->sort_list,
1700                                                    sort_column_id);
1701
1702           /* we want to make sure that we have a function */
1703           g_return_if_fail (header != NULL);
1704           g_return_if_fail (header->func != NULL);
1705         }
1706       else
1707         g_return_if_fail (priv->default_sort_func != NULL);
1708
1709       if (priv->sort_column_id == sort_column_id)
1710         {
1711           if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1712             {
1713               if (priv->order == order)
1714                 return;
1715             }
1716           else
1717             return;
1718         }
1719     }
1720
1721   priv->sort_column_id = sort_column_id;
1722   priv->order = order;
1723
1724   gtk_tree_sortable_sort_column_changed (sortable);
1725
1726   gtk_tree_model_sort_sort (tree_model_sort);
1727 }
1728
1729 static void
1730 gtk_tree_model_sort_set_sort_func (GtkTreeSortable        *sortable,
1731                                    gint                    sort_column_id,
1732                                    GtkTreeIterCompareFunc  func,
1733                                    gpointer                data,
1734                                    GDestroyNotify          destroy)
1735 {
1736   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
1737   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1738
1739   priv->sort_list = _gtk_tree_data_list_set_header (priv->sort_list,
1740                                                     sort_column_id,
1741                                                     func, data, destroy);
1742
1743   if (priv->sort_column_id == sort_column_id)
1744     gtk_tree_model_sort_sort (tree_model_sort);
1745 }
1746
1747 static void
1748 gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
1749                                            GtkTreeIterCompareFunc  func,
1750                                            gpointer                data,
1751                                            GDestroyNotify          destroy)
1752 {
1753   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1754   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1755
1756   if (priv->default_sort_destroy)
1757     {
1758       GDestroyNotify d = priv->default_sort_destroy;
1759
1760       priv->default_sort_destroy = NULL;
1761       d (priv->default_sort_data);
1762     }
1763
1764   priv->default_sort_func = func;
1765   priv->default_sort_data = data;
1766   priv->default_sort_destroy = destroy;
1767
1768   if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1769     gtk_tree_model_sort_sort (tree_model_sort);
1770 }
1771
1772 static gboolean
1773 gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable *sortable)
1774 {
1775   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1776
1777   return (tree_model_sort->priv->default_sort_func != NULL);
1778 }
1779
1780 /* DragSource interface */
1781 static gboolean
1782 gtk_tree_model_sort_row_draggable (GtkTreeDragSource *drag_source,
1783                                    GtkTreePath       *path)
1784 {
1785   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1786   GtkTreePath *child_path;
1787   gboolean draggable;
1788
1789   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort,
1790                                                                path);
1791   draggable = gtk_tree_drag_source_row_draggable (GTK_TREE_DRAG_SOURCE (tree_model_sort->priv->child_model), child_path);
1792   gtk_tree_path_free (child_path);
1793
1794   return draggable;
1795 }
1796
1797 static gboolean
1798 gtk_tree_model_sort_drag_data_get (GtkTreeDragSource *drag_source,
1799                                    GtkTreePath       *path,
1800                                    GtkSelectionData  *selection_data)
1801 {
1802   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1803   GtkTreePath *child_path;
1804   gboolean gotten;
1805
1806   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort, path);
1807   gotten = gtk_tree_drag_source_drag_data_get (GTK_TREE_DRAG_SOURCE (tree_model_sort->priv->child_model), child_path, selection_data);
1808   gtk_tree_path_free (child_path);
1809
1810   return gotten;
1811 }
1812
1813 static gboolean
1814 gtk_tree_model_sort_drag_data_delete (GtkTreeDragSource *drag_source,
1815                                       GtkTreePath       *path)
1816 {
1817   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1818   GtkTreePath *child_path;
1819   gboolean deleted;
1820
1821   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort, path);
1822   deleted = gtk_tree_drag_source_drag_data_delete (GTK_TREE_DRAG_SOURCE (tree_model_sort->priv->child_model), child_path);
1823   gtk_tree_path_free (child_path);
1824
1825   return deleted;
1826 }
1827
1828 /* sorting code - private */
1829 static gint
1830 gtk_tree_model_sort_compare_func (gconstpointer a,
1831                                   gconstpointer b,
1832                                   gpointer      user_data)
1833 {
1834   SortData *data = (SortData *)user_data;
1835   GtkTreeModelSort *tree_model_sort = data->tree_model_sort;
1836   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1837   const SortElt *sa = a;
1838   const SortElt *sb = b;
1839
1840   GtkTreeIter iter_a, iter_b;
1841   gint retval;
1842
1843   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1844     {
1845       iter_a = sa->iter;
1846       iter_b = sb->iter;
1847     }
1848   else
1849     {
1850       data->parent_path_indices [data->parent_path_depth-1] = sa->offset;
1851       gtk_tree_model_get_iter (GTK_TREE_MODEL (priv->child_model), &iter_a, data->parent_path);
1852       data->parent_path_indices [data->parent_path_depth-1] = sb->offset;
1853       gtk_tree_model_get_iter (GTK_TREE_MODEL (priv->child_model), &iter_b, data->parent_path);
1854     }
1855
1856   retval = (* data->sort_func) (GTK_TREE_MODEL (priv->child_model),
1857                                 &iter_a, &iter_b,
1858                                 data->sort_data);
1859
1860   if (priv->order == GTK_SORT_DESCENDING)
1861     {
1862       if (retval > 0)
1863         retval = -1;
1864       else if (retval < 0)
1865         retval = 1;
1866     }
1867
1868   return retval;
1869 }
1870
1871 static gint
1872 gtk_tree_model_sort_offset_compare_func (gconstpointer a,
1873                                          gconstpointer b,
1874                                          gpointer      user_data)
1875 {
1876   gint retval;
1877
1878   const SortElt *sa = (SortElt *)a;
1879   const SortElt *sb = (SortElt *)b;
1880
1881   SortData *data = (SortData *)user_data;
1882
1883   if (sa->offset < sb->offset)
1884     retval = -1;
1885   else if (sa->offset > sb->offset)
1886     retval = 1;
1887   else
1888     retval = 0;
1889
1890   if (data->tree_model_sort->priv->order == GTK_SORT_DESCENDING)
1891     {
1892       if (retval > 0)
1893         retval = -1;
1894       else if (retval < 0)
1895         retval = 1;
1896     }
1897
1898   return retval;
1899 }
1900
1901 static void
1902 gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
1903                                 SortLevel        *level,
1904                                 gboolean          recurse,
1905                                 gboolean          emit_reordered)
1906 {
1907   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1908   gint i;
1909   GSequenceIter *begin_siter, *end_siter, *siter;
1910   SortElt *begin_elt;
1911   gint *new_order;
1912
1913   GtkTreeIter iter;
1914   GtkTreePath *path;
1915
1916   SortData data;
1917
1918   g_return_if_fail (level != NULL);
1919
1920   begin_siter = g_sequence_get_begin_iter (level->seq);
1921   begin_elt = g_sequence_get (begin_siter);
1922
1923   if (g_sequence_get_length (level->seq) < 1 && !begin_elt->children)
1924     return;
1925
1926   iter.stamp = priv->stamp;
1927   iter.user_data = level;
1928   iter.user_data2 = begin_elt;
1929
1930   gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (tree_model_sort), &iter);
1931
1932   i = 0;
1933   end_siter = g_sequence_get_end_iter (level->seq);
1934   for (siter = g_sequence_get_begin_iter (level->seq);
1935        siter != end_siter;
1936        siter = g_sequence_iter_next (siter))
1937     {
1938       SortElt *elt = g_sequence_get (siter);
1939
1940       elt->old_index = i;
1941       i++;
1942     }
1943
1944   fill_sort_data (&data, tree_model_sort, level);
1945
1946   if (data.sort_func == NO_SORT_FUNC)
1947     g_sequence_sort (level->seq, gtk_tree_model_sort_offset_compare_func,
1948                      &data);
1949   else
1950     g_sequence_sort (level->seq, gtk_tree_model_sort_compare_func, &data);
1951
1952   free_sort_data (&data);
1953
1954   new_order = g_new (gint, g_sequence_get_length (level->seq));
1955
1956   i = 0;
1957   end_siter = g_sequence_get_end_iter (level->seq);
1958   for (siter = g_sequence_get_begin_iter (level->seq);
1959        siter != end_siter;
1960        siter = g_sequence_iter_next (siter))
1961     {
1962       SortElt *elt = g_sequence_get (siter);
1963
1964       new_order[i++] = elt->old_index;
1965     }
1966
1967   if (emit_reordered)
1968     {
1969       gtk_tree_model_sort_increment_stamp (tree_model_sort);
1970       if (level->parent_elt)
1971         {
1972           iter.stamp = priv->stamp;
1973           iter.user_data = level->parent_level;
1974           iter.user_data2 = level->parent_elt;
1975
1976           path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort),
1977                                           &iter);
1978
1979           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1980                                          &iter, new_order);
1981         }
1982       else
1983         {
1984           /* toplevel list */
1985           path = gtk_tree_path_new ();
1986           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1987                                          NULL, new_order);
1988         }
1989
1990       gtk_tree_path_free (path);
1991     }
1992
1993   /* recurse, if possible */
1994   if (recurse)
1995     {
1996       end_siter = g_sequence_get_end_iter (level->seq);
1997       for (siter = g_sequence_get_begin_iter (level->seq);
1998            siter != end_siter;
1999            siter = g_sequence_iter_next (siter))
2000         {
2001           SortElt *elt = g_sequence_get (siter);
2002
2003           if (elt->children)
2004             gtk_tree_model_sort_sort_level (tree_model_sort,
2005                                             elt->children,
2006                                             TRUE, emit_reordered);
2007         }
2008     }
2009
2010   g_free (new_order);
2011
2012   /* get the iter we referenced at the beginning of this function and
2013    * unref it again
2014    */
2015   iter.stamp = priv->stamp;
2016   iter.user_data = level;
2017   iter.user_data2 = begin_elt;
2018
2019   gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (tree_model_sort), &iter);
2020 }
2021
2022 static void
2023 gtk_tree_model_sort_sort (GtkTreeModelSort *tree_model_sort)
2024 {
2025   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2026
2027   if (priv->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
2028     return;
2029
2030   if (!priv->root)
2031     return;
2032
2033   if (priv->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
2034     {
2035       GtkTreeDataSortHeader *header = NULL;
2036
2037       header = _gtk_tree_data_list_get_header (priv->sort_list,
2038                                                priv->sort_column_id);
2039
2040       /* we want to make sure that we have a function */
2041       g_return_if_fail (header != NULL);
2042       g_return_if_fail (header->func != NULL);
2043     }
2044   else
2045     g_return_if_fail (priv->default_sort_func != NULL);
2046
2047   gtk_tree_model_sort_sort_level (tree_model_sort, priv->root,
2048                                   TRUE, TRUE);
2049 }
2050
2051 /* signal helpers */
2052 static gboolean
2053 gtk_tree_model_sort_insert_value (GtkTreeModelSort *tree_model_sort,
2054                                   SortLevel        *level,
2055                                   GtkTreePath      *s_path,
2056                                   GtkTreeIter      *s_iter)
2057 {
2058   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2059   SortElt *elt;
2060   SortData data;
2061   gint offset;
2062
2063   elt = sort_elt_new ();
2064
2065   offset = gtk_tree_path_get_indices (s_path)[gtk_tree_path_get_depth (s_path) - 1];
2066
2067   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2068     elt->iter = *s_iter;
2069   elt->offset = offset;
2070   elt->zero_ref_count = 0;
2071   elt->ref_count = 0;
2072   elt->children = NULL;
2073
2074   /* update all larger offsets */
2075   g_sequence_foreach (level->seq, increase_offset_iter, GINT_TO_POINTER (offset));
2076
2077   fill_sort_data (&data, tree_model_sort, level);
2078
2079   if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
2080       priv->default_sort_func == NO_SORT_FUNC)
2081     {
2082       elt->siter = g_sequence_insert_sorted (level->seq, elt,
2083                                              gtk_tree_model_sort_offset_compare_func,
2084                                              &data);
2085     }
2086   else
2087     {
2088       elt->siter = g_sequence_insert_sorted (level->seq, elt,
2089                                              gtk_tree_model_sort_compare_func,
2090                                              &data);
2091     }
2092
2093   free_sort_data (&data);
2094
2095   return TRUE;
2096 }
2097
2098 /* sort elt stuff */
2099 static GtkTreePath *
2100 gtk_tree_model_sort_elt_get_path (SortLevel *level,
2101                                   SortElt *elt)
2102 {
2103   SortLevel *walker = level;
2104   SortElt *walker2 = elt;
2105   GtkTreePath *path;
2106
2107   g_return_val_if_fail (level != NULL, NULL);
2108   g_return_val_if_fail (elt != NULL, NULL);
2109
2110   path = gtk_tree_path_new ();
2111
2112   while (walker)
2113     {
2114       gtk_tree_path_prepend_index (path, walker2->offset);
2115
2116       if (!walker->parent_level)
2117         break;
2118
2119       walker2 = walker->parent_elt;
2120       walker = walker->parent_level;
2121     }
2122
2123   return path;
2124 }
2125
2126 /**
2127  * gtk_tree_model_sort_set_model:
2128  * @tree_model_sort: The #GtkTreeModelSort.
2129  * @child_model: (allow-none): A #GtkTreeModel, or %NULL.
2130  *
2131  * Sets the model of @tree_model_sort to be @model.  If @model is %NULL,
2132  * then the old model is unset.  The sort function is unset as a result
2133  * of this call. The model will be in an unsorted state until a sort
2134  * function is set.
2135  **/
2136 static void
2137 gtk_tree_model_sort_set_model (GtkTreeModelSort *tree_model_sort,
2138                                GtkTreeModel     *child_model)
2139 {
2140   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2141
2142   if (child_model)
2143     g_object_ref (child_model);
2144
2145   if (priv->child_model)
2146     {
2147       g_signal_handler_disconnect (priv->child_model,
2148                                    priv->changed_id);
2149       g_signal_handler_disconnect (priv->child_model,
2150                                    priv->inserted_id);
2151       g_signal_handler_disconnect (priv->child_model,
2152                                    priv->has_child_toggled_id);
2153       g_signal_handler_disconnect (priv->child_model,
2154                                    priv->deleted_id);
2155       g_signal_handler_disconnect (priv->child_model,
2156                                    priv->reordered_id);
2157
2158       /* reset our state */
2159       if (priv->root)
2160         gtk_tree_model_sort_free_level (tree_model_sort, priv->root, TRUE);
2161       priv->root = NULL;
2162       _gtk_tree_data_list_header_free (priv->sort_list);
2163       priv->sort_list = NULL;
2164       g_object_unref (priv->child_model);
2165     }
2166
2167   priv->child_model = child_model;
2168
2169   if (child_model)
2170     {
2171       GType *types;
2172       gint i, n_columns;
2173
2174       priv->changed_id =
2175         g_signal_connect (child_model, "row-changed",
2176                           G_CALLBACK (gtk_tree_model_sort_row_changed),
2177                           tree_model_sort);
2178       priv->inserted_id =
2179         g_signal_connect (child_model, "row-inserted",
2180                           G_CALLBACK (gtk_tree_model_sort_row_inserted),
2181                           tree_model_sort);
2182       priv->has_child_toggled_id =
2183         g_signal_connect (child_model, "row-has-child-toggled",
2184                           G_CALLBACK (gtk_tree_model_sort_row_has_child_toggled),
2185                           tree_model_sort);
2186       priv->deleted_id =
2187         g_signal_connect (child_model, "row-deleted",
2188                           G_CALLBACK (gtk_tree_model_sort_row_deleted),
2189                           tree_model_sort);
2190       priv->reordered_id =
2191         g_signal_connect (child_model, "rows-reordered",
2192                           G_CALLBACK (gtk_tree_model_sort_rows_reordered),
2193                           tree_model_sort);
2194
2195       priv->child_flags = gtk_tree_model_get_flags (child_model);
2196       n_columns = gtk_tree_model_get_n_columns (child_model);
2197
2198       types = g_new (GType, n_columns);
2199       for (i = 0; i < n_columns; i++)
2200         types[i] = gtk_tree_model_get_column_type (child_model, i);
2201
2202       priv->sort_list = _gtk_tree_data_list_header_new (n_columns, types);
2203       g_free (types);
2204
2205       priv->default_sort_func = NO_SORT_FUNC;
2206       priv->stamp = g_random_int ();
2207     }
2208 }
2209
2210 /**
2211  * gtk_tree_model_sort_get_model:
2212  * @tree_model: a #GtkTreeModelSort
2213  *
2214  * Returns the model the #GtkTreeModelSort is sorting.
2215  *
2216  * Return value: (transfer none): the "child model" being sorted
2217  **/
2218 GtkTreeModel *
2219 gtk_tree_model_sort_get_model (GtkTreeModelSort *tree_model)
2220 {
2221   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
2222
2223   return tree_model->priv->child_model;
2224 }
2225
2226
2227 static GtkTreePath *
2228 gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
2229                                                      GtkTreePath      *child_path,
2230                                                      gboolean          build_levels)
2231 {
2232   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2233   gint *child_indices;
2234   GtkTreePath *retval;
2235   SortLevel *level;
2236   gint i;
2237
2238   g_return_val_if_fail (priv->child_model != NULL, NULL);
2239   g_return_val_if_fail (child_path != NULL, NULL);
2240
2241   retval = gtk_tree_path_new ();
2242   child_indices = gtk_tree_path_get_indices (child_path);
2243
2244   if (priv->root == NULL && build_levels)
2245     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
2246   level = SORT_LEVEL (priv->root);
2247
2248   for (i = 0; i < gtk_tree_path_get_depth (child_path); i++)
2249     {
2250       SortElt *tmp;
2251       GSequenceIter *siter;
2252       gboolean found_child = FALSE;
2253
2254       if (!level)
2255         {
2256           gtk_tree_path_free (retval);
2257           return NULL;
2258         }
2259
2260       if (child_indices[i] >= g_sequence_get_length (level->seq))
2261         {
2262           gtk_tree_path_free (retval);
2263           return NULL;
2264         }
2265       tmp = lookup_elt_with_offset (tree_model_sort, level,
2266                                     child_indices[i], &siter);
2267       if (tmp)
2268         {
2269           gtk_tree_path_append_index (retval, g_sequence_iter_get_position (siter));
2270           if (tmp->children == NULL && build_levels)
2271             gtk_tree_model_sort_build_level (tree_model_sort, level, tmp);
2272
2273           level = tmp->children;
2274           found_child = TRUE;
2275         }
2276
2277       if (! found_child)
2278         {
2279           gtk_tree_path_free (retval);
2280           return NULL;
2281         }
2282     }
2283
2284   return retval;
2285 }
2286
2287
2288 /**
2289  * gtk_tree_model_sort_convert_child_path_to_path:
2290  * @tree_model_sort: A #GtkTreeModelSort
2291  * @child_path: A #GtkTreePath to convert
2292  *
2293  * Converts @child_path to a path relative to @tree_model_sort.  That is,
2294  * @child_path points to a path in the child model.  The returned path will
2295  * point to the same row in the sorted model.  If @child_path isn't a valid
2296  * path on the child model, then %NULL is returned.
2297  *
2298  * Return value: A newly allocated #GtkTreePath, or %NULL
2299  **/
2300 GtkTreePath *
2301 gtk_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
2302                                                 GtkTreePath      *child_path)
2303 {
2304   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2305   g_return_val_if_fail (tree_model_sort->priv->child_model != NULL, NULL);
2306   g_return_val_if_fail (child_path != NULL, NULL);
2307
2308   return gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path, TRUE);
2309 }
2310
2311 /**
2312  * gtk_tree_model_sort_convert_child_iter_to_iter:
2313  * @tree_model_sort: A #GtkTreeModelSort
2314  * @sort_iter: (out): An uninitialized #GtkTreeIter.
2315  * @child_iter: A valid #GtkTreeIter pointing to a row on the child model
2316  *
2317  * Sets @sort_iter to point to the row in @tree_model_sort that corresponds to
2318  * the row pointed at by @child_iter.  If @sort_iter was not set, %FALSE
2319  * is returned.  Note: a boolean is only returned since 2.14.
2320  *
2321  * Return value: %TRUE, if @sort_iter was set, i.e. if @sort_iter is a
2322  * valid iterator pointer to a visible row in the child model.
2323  **/
2324 gboolean
2325 gtk_tree_model_sort_convert_child_iter_to_iter (GtkTreeModelSort *tree_model_sort,
2326                                                 GtkTreeIter      *sort_iter,
2327                                                 GtkTreeIter      *child_iter)
2328 {
2329   gboolean ret;
2330   GtkTreePath *child_path, *path;
2331   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2332
2333   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), FALSE);
2334   g_return_val_if_fail (priv->child_model != NULL, FALSE);
2335   g_return_val_if_fail (sort_iter != NULL, FALSE);
2336   g_return_val_if_fail (child_iter != NULL, FALSE);
2337   g_return_val_if_fail (sort_iter != child_iter, FALSE);
2338
2339   sort_iter->stamp = 0;
2340
2341   child_path = gtk_tree_model_get_path (priv->child_model, child_iter);
2342   g_return_val_if_fail (child_path != NULL, FALSE);
2343
2344   path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path);
2345   gtk_tree_path_free (child_path);
2346
2347   if (!path)
2348     {
2349       g_warning ("%s: The conversion of the child path to a GtkTreeModel sort path failed", G_STRLOC);
2350       return FALSE;
2351     }
2352
2353   ret = gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
2354                                  sort_iter, path);
2355   gtk_tree_path_free (path);
2356
2357   return ret;
2358 }
2359
2360 /**
2361  * gtk_tree_model_sort_convert_path_to_child_path:
2362  * @tree_model_sort: A #GtkTreeModelSort
2363  * @sorted_path: A #GtkTreePath to convert
2364  *
2365  * Converts @sorted_path to a path on the child model of @tree_model_sort.
2366  * That is, @sorted_path points to a location in @tree_model_sort.  The
2367  * returned path will point to the same location in the model not being
2368  * sorted.  If @sorted_path does not point to a location in the child model,
2369  * %NULL is returned.
2370  *
2371  * Return value: A newly allocated #GtkTreePath, or %NULL
2372  **/
2373 GtkTreePath *
2374 gtk_tree_model_sort_convert_path_to_child_path (GtkTreeModelSort *tree_model_sort,
2375                                                 GtkTreePath      *sorted_path)
2376 {
2377   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2378   gint *sorted_indices;
2379   GtkTreePath *retval;
2380   SortLevel *level;
2381   gint i;
2382
2383   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2384   g_return_val_if_fail (priv->child_model != NULL, NULL);
2385   g_return_val_if_fail (sorted_path != NULL, NULL);
2386
2387   retval = gtk_tree_path_new ();
2388   sorted_indices = gtk_tree_path_get_indices (sorted_path);
2389   if (priv->root == NULL)
2390     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
2391   level = SORT_LEVEL (priv->root);
2392
2393   for (i = 0; i < gtk_tree_path_get_depth (sorted_path); i++)
2394     {
2395       SortElt *elt = NULL;
2396       GSequenceIter *siter;
2397
2398       if ((level == NULL) ||
2399           (g_sequence_get_length (level->seq) <= sorted_indices[i]))
2400         {
2401           gtk_tree_path_free (retval);
2402           return NULL;
2403         }
2404
2405       siter = g_sequence_get_iter_at_pos (level->seq, sorted_indices[i]);
2406       if (g_sequence_iter_is_end (siter))
2407         {
2408           gtk_tree_path_free (retval);
2409           return NULL;
2410         }
2411
2412       elt = GET_ELT (siter);
2413       if (elt->children == NULL)
2414         gtk_tree_model_sort_build_level (tree_model_sort, level, elt);
2415
2416       if (level == NULL)
2417         {
2418           gtk_tree_path_free (retval);
2419           break;
2420         }
2421
2422       gtk_tree_path_append_index (retval, elt->offset);
2423       level = elt->children;
2424     }
2425
2426   return retval;
2427 }
2428
2429 /**
2430  * gtk_tree_model_sort_convert_iter_to_child_iter:
2431  * @tree_model_sort: A #GtkTreeModelSort
2432  * @child_iter: (out): An uninitialized #GtkTreeIter
2433  * @sorted_iter: A valid #GtkTreeIter pointing to a row on @tree_model_sort.
2434  *
2435  * Sets @child_iter to point to the row pointed to by @sorted_iter.
2436  **/
2437 void
2438 gtk_tree_model_sort_convert_iter_to_child_iter (GtkTreeModelSort *tree_model_sort,
2439                                                 GtkTreeIter      *child_iter,
2440                                                 GtkTreeIter      *sorted_iter)
2441 {
2442   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2443   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2444   g_return_if_fail (priv->child_model != NULL);
2445   g_return_if_fail (child_iter != NULL);
2446   g_return_if_fail (VALID_ITER (sorted_iter, tree_model_sort));
2447   g_return_if_fail (sorted_iter != child_iter);
2448
2449   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2450     {
2451       *child_iter = SORT_ELT (sorted_iter->user_data2)->iter;
2452     }
2453   else
2454     {
2455       GtkTreePath *path;
2456       gboolean valid = FALSE;
2457
2458       path = gtk_tree_model_sort_elt_get_path (sorted_iter->user_data,
2459                                                sorted_iter->user_data2);
2460       valid = gtk_tree_model_get_iter (priv->child_model, child_iter, path);
2461       gtk_tree_path_free (path);
2462
2463       g_return_if_fail (valid == TRUE);
2464     }
2465 }
2466
2467 static void
2468 gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
2469                                  SortLevel        *parent_level,
2470                                  SortElt          *parent_elt)
2471 {
2472   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2473   GtkTreeIter iter;
2474   SortLevel *new_level;
2475   gint length = 0;
2476   gint i;
2477
2478   g_assert (priv->child_model != NULL);
2479
2480   if (parent_level == NULL)
2481     {
2482       if (gtk_tree_model_get_iter_first (priv->child_model, &iter) == FALSE)
2483         return;
2484       length = gtk_tree_model_iter_n_children (priv->child_model, NULL);
2485     }
2486   else
2487     {
2488       GtkTreeIter parent_iter;
2489       GtkTreeIter child_parent_iter;
2490
2491       parent_iter.stamp = priv->stamp;
2492       parent_iter.user_data = parent_level;
2493       parent_iter.user_data2 = parent_elt;
2494
2495       gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2496                                                       &child_parent_iter,
2497                                                       &parent_iter);
2498       if (gtk_tree_model_iter_children (priv->child_model,
2499                                         &iter,
2500                                         &child_parent_iter) == FALSE)
2501         return;
2502
2503       /* stamp may have changed */
2504       gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2505                                                       &child_parent_iter,
2506                                                       &parent_iter);
2507
2508       length = gtk_tree_model_iter_n_children (priv->child_model, &child_parent_iter);
2509
2510       gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (tree_model_sort),
2511                                     &parent_iter);
2512     }
2513
2514   g_return_if_fail (length > 0);
2515
2516   new_level = g_new (SortLevel, 1);
2517   new_level->seq = g_sequence_new (sort_elt_free);
2518   new_level->ref_count = 0;
2519   new_level->parent_level = parent_level;
2520   new_level->parent_elt = parent_elt;
2521
2522   if (parent_elt)
2523     parent_elt->children = new_level;
2524   else
2525     priv->root = new_level;
2526
2527   /* increase the count of zero ref_counts.*/
2528   while (parent_level)
2529     {
2530       parent_elt->zero_ref_count++;
2531
2532       parent_elt = parent_level->parent_elt;
2533       parent_level = parent_level->parent_level;
2534     }
2535
2536   if (new_level != priv->root)
2537     priv->zero_ref_count++;
2538
2539   for (i = 0; i < length; i++)
2540     {
2541       SortElt *sort_elt;
2542
2543       sort_elt = sort_elt_new ();
2544       sort_elt->offset = i;
2545       sort_elt->zero_ref_count = 0;
2546       sort_elt->ref_count = 0;
2547       sort_elt->children = NULL;
2548
2549       if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2550         {
2551           sort_elt->iter = iter;
2552           if (gtk_tree_model_iter_next (priv->child_model, &iter) == FALSE &&
2553               i < length - 1)
2554             {
2555               if (parent_level)
2556                 {
2557                   GtkTreePath *level;
2558                   gchar *str;
2559
2560                   level = gtk_tree_model_sort_elt_get_path (parent_level,
2561                                                             parent_elt);
2562                   str = gtk_tree_path_to_string (level);
2563                   gtk_tree_path_free (level);
2564
2565                   g_warning ("%s: There is a discrepancy between the sort model "
2566                              "and the child model.  The child model is "
2567                              "advertising a wrong length for level %s:.",
2568                              G_STRLOC, str);
2569                   g_free (str);
2570                 }
2571               else
2572                 {
2573                   g_warning ("%s: There is a discrepancy between the sort model "
2574                              "and the child model.  The child model is "
2575                              "advertising a wrong length for the root level.",
2576                              G_STRLOC);
2577                 }
2578
2579               return;
2580             }
2581         }
2582
2583       sort_elt->siter = g_sequence_append (new_level->seq, sort_elt);
2584     }
2585
2586   /* sort level */
2587   gtk_tree_model_sort_sort_level (tree_model_sort, new_level,
2588                                   FALSE, FALSE);
2589 }
2590
2591 static void
2592 gtk_tree_model_sort_free_level (GtkTreeModelSort *tree_model_sort,
2593                                 SortLevel        *sort_level,
2594                                 gboolean          unref)
2595 {
2596   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2597   GSequenceIter *siter;
2598   GSequenceIter *end_siter;
2599
2600   g_assert (sort_level);
2601
2602   end_siter = g_sequence_get_end_iter (sort_level->seq);
2603   for (siter = g_sequence_get_begin_iter (sort_level->seq);
2604        siter != end_siter;
2605        siter = g_sequence_iter_next (siter))
2606     {
2607       SortElt *elt = g_sequence_get (siter);
2608
2609       if (elt->children)
2610         gtk_tree_model_sort_free_level (tree_model_sort,
2611                                         elt->children, unref);
2612     }
2613
2614   if (sort_level->ref_count == 0)
2615     {
2616       SortLevel *parent_level = sort_level->parent_level;
2617       SortElt *parent_elt = sort_level->parent_elt;
2618
2619       while (parent_level)
2620         {
2621           parent_elt->zero_ref_count--;
2622
2623           parent_elt = parent_level->parent_elt;
2624           parent_level = parent_level->parent_level;
2625         }
2626
2627       if (sort_level != priv->root)
2628         priv->zero_ref_count--;
2629     }
2630
2631   if (sort_level->parent_elt)
2632     {
2633       if (unref)
2634         {
2635           GtkTreeIter parent_iter;
2636
2637           parent_iter.stamp = tree_model_sort->priv->stamp;
2638           parent_iter.user_data = sort_level->parent_level;
2639           parent_iter.user_data2 = sort_level->parent_elt;
2640
2641           gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (tree_model_sort),
2642                                           &parent_iter);
2643         }
2644
2645       sort_level->parent_elt->children = NULL;
2646     }
2647   else
2648     priv->root = NULL;
2649
2650   g_sequence_free (sort_level->seq);
2651   sort_level->seq = NULL;
2652
2653   g_free (sort_level);
2654   sort_level = NULL;
2655 }
2656
2657 static void
2658 gtk_tree_model_sort_increment_stamp (GtkTreeModelSort *tree_model_sort)
2659 {
2660   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2661
2662   do
2663     {
2664       priv->stamp++;
2665     }
2666   while (priv->stamp == 0);
2667
2668   gtk_tree_model_sort_clear_cache (tree_model_sort);
2669 }
2670
2671 static void
2672 gtk_tree_model_sort_clear_cache_helper_iter (gpointer data,
2673                                              gpointer user_data)
2674 {
2675   GtkTreeModelSort *tree_model_sort = user_data;
2676   SortElt *elt = data;
2677
2678   if (elt->zero_ref_count > 0)
2679     gtk_tree_model_sort_clear_cache_helper (tree_model_sort, elt->children);
2680 }
2681
2682 static void
2683 gtk_tree_model_sort_clear_cache_helper (GtkTreeModelSort *tree_model_sort,
2684                                         SortLevel        *level)
2685 {
2686   g_assert (level != NULL);
2687
2688   g_sequence_foreach (level->seq, gtk_tree_model_sort_clear_cache_helper_iter,
2689                       tree_model_sort);
2690
2691   if (level->ref_count == 0 && level != tree_model_sort->priv->root)
2692     gtk_tree_model_sort_free_level (tree_model_sort, level, TRUE);
2693 }
2694
2695 /**
2696  * gtk_tree_model_sort_reset_default_sort_func:
2697  * @tree_model_sort: A #GtkTreeModelSort
2698  *
2699  * This resets the default sort function to be in the 'unsorted' state.  That
2700  * is, it is in the same order as the child model. It will re-sort the model
2701  * to be in the same order as the child model only if the #GtkTreeModelSort
2702  * is in 'unsorted' state.
2703  **/
2704 void
2705 gtk_tree_model_sort_reset_default_sort_func (GtkTreeModelSort *tree_model_sort)
2706 {
2707   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2708
2709   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2710
2711   if (priv->default_sort_destroy)
2712     {
2713       GDestroyNotify d = priv->default_sort_destroy;
2714
2715       priv->default_sort_destroy = NULL;
2716       d (priv->default_sort_data);
2717     }
2718
2719   priv->default_sort_func = NO_SORT_FUNC;
2720   priv->default_sort_data = NULL;
2721   priv->default_sort_destroy = NULL;
2722
2723   if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
2724     gtk_tree_model_sort_sort (tree_model_sort);
2725   priv->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
2726 }
2727
2728 /**
2729  * gtk_tree_model_sort_clear_cache:
2730  * @tree_model_sort: A #GtkTreeModelSort
2731  *
2732  * This function should almost never be called.  It clears the @tree_model_sort
2733  * of any cached iterators that haven't been reffed with
2734  * gtk_tree_model_ref_node().  This might be useful if the child model being
2735  * sorted is static (and doesn't change often) and there has been a lot of
2736  * unreffed access to nodes.  As a side effect of this function, all unreffed
2737  * iters will be invalid.
2738  **/
2739 void
2740 gtk_tree_model_sort_clear_cache (GtkTreeModelSort *tree_model_sort)
2741 {
2742   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2743
2744   if (tree_model_sort->priv->zero_ref_count > 0)
2745     gtk_tree_model_sort_clear_cache_helper (tree_model_sort, (SortLevel *)tree_model_sort->priv->root);
2746 }
2747
2748 static gboolean
2749 gtk_tree_model_sort_iter_is_valid_helper (GtkTreeIter *iter,
2750                                           SortLevel   *level)
2751 {
2752   GSequenceIter *siter;
2753   GSequenceIter *end_siter;
2754
2755   end_siter = g_sequence_get_end_iter (level->seq);
2756   for (siter = g_sequence_get_begin_iter (level->seq);
2757        siter != end_siter; siter = g_sequence_iter_next (siter))
2758     {
2759       SortElt *elt = g_sequence_get (siter);
2760
2761       if (iter->user_data == level && iter->user_data2 == elt)
2762         return TRUE;
2763
2764       if (elt->children)
2765         if (gtk_tree_model_sort_iter_is_valid_helper (iter, elt->children))
2766           return TRUE;
2767     }
2768
2769   return FALSE;
2770 }
2771
2772 /**
2773  * gtk_tree_model_sort_iter_is_valid:
2774  * @tree_model_sort: A #GtkTreeModelSort.
2775  * @iter: A #GtkTreeIter.
2776  *
2777  * <warning><para>
2778  * This function is slow. Only use it for debugging and/or testing purposes.
2779  * </para></warning>
2780  *
2781  * Checks if the given iter is a valid iter for this #GtkTreeModelSort.
2782  *
2783  * Return value: %TRUE if the iter is valid, %FALSE if the iter is invalid.
2784  *
2785  * Since: 2.2
2786  **/
2787 gboolean
2788 gtk_tree_model_sort_iter_is_valid (GtkTreeModelSort *tree_model_sort,
2789                                    GtkTreeIter      *iter)
2790 {
2791   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), FALSE);
2792   g_return_val_if_fail (iter != NULL, FALSE);
2793
2794   if (!VALID_ITER (iter, tree_model_sort))
2795     return FALSE;
2796
2797   return gtk_tree_model_sort_iter_is_valid_helper (iter,
2798                                                    tree_model_sort->priv->root);
2799 }