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

   1 /* gtktreemodelfilter.c
   2  * Copyright (C) 2000,2001  Red Hat, Inc., Jonathan Blandford <jrb@redhat.com>
   3  * Copyright (C) 2001-2003  Kristian Rietveld <kris@gtk.org>
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Library General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License along with this library; if not, write to the
  17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18  * Boston, MA 02111-1307, USA.
  19  */
  20
  21 #include "config.h"
  22 #include "gtktreemodelfilter.h"
  23 #include "gtkintl.h"
  24 #include "gtktreednd.h"
  25 #include "gtkprivate.h"
  26 #include <string.h>
  27
  28
  29 /**
  30  * SECTION:gtktreemodelfilter
  31  * @Short_description: A GtkTreeModel which hides parts of an underlying tree model
  32  * @Title: GtkTreeModelFilter
  33  * @See_also:#GtkTreeModelSort
  34  *
  35  * A #GtkTreeModelFilter is a tree model which wraps another tree model,
  36  * and can do the following things:
  37  * <itemizedlist>
  38  * <listitem><para>
  39  * Filter specific rows, based on data from a "visible column", a column
  40  * storing booleans indicating whether the row should be filtered or not,
  41  * or based on the return value of a "visible function", which gets a
  42  * model, iter and user_data and returns a boolean indicating whether the
  43  * row should be filtered or not.
  44  * </para></listitem>
  45  * <listitem><para>
  46  * Modify the "appearance" of the model, using a modify function.
  47  * This is extremely powerful and allows for just changing
  48  * some values and also for creating a completely different model based on
  49  * the given child model.
  50  * </para></listitem>
  51  * <listitem><para>
  52  * Set a different root node, also known as a "virtual root". You can pass in
  53  * a #GtkTreePath indicating the root node for the filter at construction time.
  54  * </para></listitem>
  55  * </itemizedlist>
  56  *
  57  * The basic API is similar to #GtkTreeModelSort. For an example on its usage,
  58  * see the section on #GtkTreeModelSort.
  59  *
  60  * When using #GtkTreeModelFilter, it is important to realize that
  61  * #GtkTreeModelFilter maintains an internal cache of all nodes which are
  62  * visible in its clients. The cache is likely to be a subtree of the tree
  63  * exposed by the child model. #GtkTreeModelFilter will not cache the entire
  64  * child model when unnecessary to not compromise the caching mechanism
  65  * that is exposed by the reference counting scheme. If the child model
  66  * implements reference counting, unnecessary signals may not be emitted
  67  * because of reference counting rule 3, see the #GtkTreeModel
  68  * documentation. (Note that e.g. #GtkTreeStore does not implement
  69  * reference counting and will always emit all signals, even when
  70  * the receiving node is not visible).
  71  *
  72  * Because of this, limitations for possible visible functions do apply.
  73  * In general, visible functions should only use data or properties from
  74  * the node for which the visibility state must be determined, its siblings
  75  * or its parents. Usually, having a dependency on the state of any child
  76  * node is not possible, unless references are taken on these explicitly.
  77  * When no such reference exists, no signals may be received for these child
  78  * nodes (see reference couting rule number 3 in the #GtkTreeModel section).
  79  *
  80  * Determining the visibility state of a given node based on the state
  81  * of its child nodes is a frequently occurring use case. Therefore,
  82  * #GtkTreeModelFilter explicitly supports this. For example, when a node
  83  * does not have any children, you might not want the node to be visible.
  84  * As soon as the first row is added to the node's child level (or the
  85  * last row removed), the node's visibility should be updated.
  86  *
  87  * This introduces a dependency from the node on its child nodes. In order
  88  * to accommodate this, #GtkTreeModelFilter must make sure the necesary
  89  * signals are received from the child model. This is achieved by building,
  90  * for all nodes which are exposed as visible nodes to #GtkTreeModelFilter's
  91  * clients, the child level (if any) and take a reference on the first node
  92  * in this level. Furthermore, for every row-inserted, row-changed or
  93  * row-deleted signal (also these which were not handled because the node
  94  * was not cached), #GtkTreeModelFilter will check if the visibility state
  95  * of any parent node has changed.
  96  *
  97  * Beware, however, that this explicit support is limited to these two
  98  * cases. For example, if you want a node to be visible only if two nodes
  99  * in a child's child level (2 levels deeper) are visible, you are on your
 100  * own. In this case, either rely on #GtkTreeStore to emit all signals
 101  * because it does not implement reference counting, or for models that
 102  * do implement reference counting, obtain references on these child levels
 103  * yourself.
 104  */
 105
 106 /* Notes on this implementation of GtkTreeModelFilter
 107  * ==================================================
 108  *
 109  * Warnings
 110  * --------
 111  *
 112  * In this code there is a potential for confusion as to whether an iter,
 113  * path or value refers to the GtkTreeModelFilter model, or to the child
 114  * model that has been set. As a convention, variables referencing the
 115  * child model will have a c_ prefix before them (ie. c_iter, c_value,
 116  * c_path). In case the c_ prefixed names are already in use, an f_
 117  * prefix is used. Conversion of iterators and paths between
 118  * GtkTreeModelFilter and the child model is done through the various
 119  * gtk_tree_model_filter_convert_* functions.
 120  *
 121  * Even though the GtkTreeModelSort and GtkTreeModelFilter have very
 122  * similar data structures, many assumptions made in the GtkTreeModelSort
 123  * code do *not* apply in the GtkTreeModelFilter case. Reference counting
 124  * in particular is more complicated in GtkTreeModelFilter, because
 125  * we explicitly support reliance on the state of a node's children as
 126  * outlined in the public API documentation. Because of these differences,
 127  * you are strongly recommended to first read through these notes before
 128  * making any modification to the code.
 129  *
 130  * Iterator format
 131  * ---------------
 132  *
 133  * The iterator format of iterators handed out by GtkTreeModelFilter is
 134  * as follows:
 135  *
 136  *     iter->stamp = filter->priv->stamp
 137  *     iter->user_data = FilterLevel
 138  *     iter->user_data2 = FilterElt
 139  *
 140  * Internal data structure
 141  * -----------------------
 142  *
 143  * Using FilterLevel and FilterElt, GtkTreeModelFilter maintains a "cache"
 144  * of the mapping from GtkTreeModelFilter nodes to nodes in the child model.
 145  * This is to avoid re-creating a level each time (which involves computing
 146  * visibility for each node in that level) an operation is requested on
 147  * GtkTreeModelFilter, such as get iter, get path and get value.
 148  *
 149  * A FilterElt corresponds to a single node. The FilterElt can either be
 150  * visible or invisible in the model that is exposed to the clients of this
 151  * GtkTreeModelFilter. The visibility state is stored in the "visible_siter"
 152  * field, which is NULL when the node is not visible. The FilterLevel keeps
 153  * a reference to the parent FilterElt and its FilterLevel (if any). The
 154  * FilterElt can have a "children" pointer set, which points at a child
 155  * level (a sub level).
 156  *
 157  * In a FilterLevel, two separate GSequences are maintained. One contains
 158  * all nodes of this FilterLevel, regardless of the visibility state of
 159  * the node. Another contains only visible nodes. A visible FilterElt
 160  * is thus present in both the full and the visible GSequence. The
 161  * GSequence allows for fast access, addition and removal of nodes.
 162  *
 163  * It is important to recognize the two different mappings that play
 164  * a part in this code:
 165  *   I.  The mapping from the client to this model. The order in which
 166  *       nodes are stored in the *visible* GSequence is the order in
 167  *       which the nodes are exposed to clients of the GtkTreeModelFilter.
 168  *   II. The mapping from this model to its child model. Each FilterElt
 169  *       contains an "offset" field which is the offset of the
 170  *       corresponding node in the child model.
 171  *
 172  * Throughout the code, two kinds of paths relative to the GtkTreeModelFilter
 173  * (those generated from the sequence positions) are used. There are paths
 174  * which take non-visible nodes into account (generated from the full
 175  * sequences) and paths which don't (generated from the visible sequences).
 176  * Paths which have been generated from the full sequences should only be
 177  * used internally and NEVER be passed along with a signal emisson.
 178  *
 179  * Reference counting
 180  * ------------------
 181  *
 182  * GtkTreeModelFilter forwards all reference and unreference operations
 183  * to the corresponding node in the child model. In addition,
 184  * GtkTreeModelFilter will also add references of its own. The full reference
 185  * count of each node (i.e. all forwarded references and these by the
 186  * filter model) is maintained internally in the "ref_count" fields in
 187  * FilterElt and FilterLevel. Because there is a need to determine whether
 188  * a node should be visible for the client, the reference count of only
 189  * the forwarded references is maintained as well, in the "ext_ref_count"
 190  * fields.
 191  *
 192  * In a few cases, GtkTreeModelFilter takes additional references on
 193  * nodes. The first case is that a reference is taken on the parent
 194  * (if any) of each level. This happens in gtk_tree_model_filter_build_level()
 195  * and the reference is released again in gtk_tree_model_filter_free_level().
 196  * This ensures that for all references which are taken by the filter
 197  * model, all parent nodes are referenced according to reference counting
 198  * rule 1 in the GtkTreeModel documentation.
 199  *
 200  * A second case is required to support visible functions which depend on
 201  * the state of a node's children (see the public API documentation for
 202  * GtkTreeModelFilter above). We build the child level of each node that
 203  * could be visible in the client (i.e. the level has an ext_ref_count > 0;
 204  * not the elt, because the elt might be invisible and thus unreferenced
 205  * by the client). For each node that becomes visible, due to insertion or
 206  * changes in visibility state, it is checked whether node has children, if
 207  * so the child level is built.
 208  *
 209  * A reference is taken on the first node of each level so that the child
 210  * model will emit all signals for this level, due to reference counting
 211  * rule 3 in the GtkTreeModel documentation. If due to changes in the level,
 212  * another node becomes the first node (e.g. due to insertion or reordering),
 213  * this reference is transferred from the old to the new first node.
 214  *
 215  * When a level has an *external* reference count of zero (which means that
 216  * none of the nodes in the level is referenced by the clients), the level
 217  * has a "zero ref count" on all its parents. As soon as the level reaches
 218  * an *external* reference count of zero, the zero ref count value is
 219  * incremented by one for all parents of this level. Due to the additional
 220  * references taken by the filter model, it is important to base the
 221  * zero ref count on the external reference count instead of on the full
 222  * reference count of the node.
 223  *
 224  * The zero ref count value aids in determining which portions of the
 225  * cache are possibly unused and could be removed. If a FilterElt has
 226  * a zero ref count of one, then its child level is unused. However, the
 227  * child level can only be removed from the cache if the FilterElt's
 228  * parent level has an external ref count of zero. (Not the parent elt,
 229  * because an invisible parent elt with external ref count == 0 might still
 230  * become visible because of a state change in its child level!).  Otherwise,
 231  * monitoring this level is necessary to possibly update the visibility state
 232  * of the parent. This is an important difference from GtkTreeModelSort!
 233  *
 234  * Signals are only required for levels with an external ref count > 0.
 235  * This due to reference counting rule 3, see the GtkTreeModel
 236  * documentation. In the GtkTreeModelFilter we try hard to stick to this
 237  * rule and not emit redundant signals (though redundant emissions of
 238  * row-has-child-toggled could appear frequently; it does happen that
 239  * we simply forward the signal emitted by e.g. GtkTreeStore but also
 240  * emit our own copy).
 241  */
 242
 243
 244 typedef struct _FilterElt FilterElt;
 245 typedef struct _FilterLevel FilterLevel;
 246
 247 struct _FilterElt
 248 {
 249   GtkTreeIter iter;
 250   FilterLevel *children;
 251   gint offset;
 252   gint ref_count;
 253   gint ext_ref_count;
 254   gint zero_ref_count;
 255   GSequenceIter *visible_siter; /* iter into visible_seq */
 256 };
 257
 258 struct _FilterLevel
 259 {
 260   GSequence *seq;
 261   GSequence *visible_seq;
 262   gint ref_count;
 263   gint ext_ref_count;
 264
 265   FilterElt *parent_elt;
 266   FilterLevel *parent_level;
 267 };
 268
 269
 270 struct _GtkTreeModelFilterPrivate
 271 {
 272   GtkTreeModel *child_model;
 273   gpointer root;
 274   GtkTreePath *virtual_root;
 275
 276   gint stamp;
 277   guint child_flags;
 278   gint zero_ref_count;
 279   gint visible_column;
 280
 281   GtkTreeModelFilterVisibleFunc visible_func;
 282   gpointer visible_data;
 283   GDestroyNotify visible_destroy;
 284
 285   GType *modify_types;
 286   GtkTreeModelFilterModifyFunc modify_func;
 287   gpointer modify_data;
 288   GDestroyNotify modify_destroy;
 289   gint modify_n_columns;
 290
 291   guint visible_method_set   : 1;
 292   guint modify_func_set      : 1;
 293
 294   guint in_row_deleted       : 1;
 295   guint virtual_root_deleted : 1;
 296
 297   /* signal ids */
 298   gulong changed_id;
 299   gulong inserted_id;
 300   gulong has_child_toggled_id;
 301   gulong deleted_id;
 302   gulong reordered_id;
 303 };
 304
 305 /* properties */
 306 enum
 307 {
 308   PROP_0,
 309   PROP_CHILD_MODEL,
 310   PROP_VIRTUAL_ROOT
 311 };
 312
 313 /* Set this to 0 to disable caching of child iterators.  This
 314  * allows for more stringent testing.  It is recommended to set this
 315  * to one when refactoring this code and running the unit tests to
 316  * catch more errors.
 317  */
 318 #if 1
 319 #  define GTK_TREE_MODEL_FILTER_CACHE_CHILD_ITERS(filter) \
 320         (((GtkTreeModelFilter *)filter)->priv->child_flags & GTK_TREE_MODEL_ITERS_PERSIST)
 321 #else
 322 #  define GTK_TREE_MODEL_FILTER_CACHE_CHILD_ITERS(filter) (FALSE)
 323 #endif
 324
 325 /* Defining this constant enables more assertions, which will be
 326  * helpful when debugging the code.
 327  */
 328 #undef MODEL_FILTER_DEBUG
 329
 330 #define FILTER_ELT(filter_elt) ((FilterElt *)filter_elt)
 331 #define FILTER_LEVEL(filter_level) ((FilterLevel *)filter_level)
 332 #define GET_ELT(siter) ((FilterElt*) (siter ? g_sequence_get (siter) : NULL))
 333
 334 /* general code (object/interface init, properties, etc) */
 335 static void         gtk_tree_model_filter_tree_model_init                 (GtkTreeModelIface       *iface);
 336 static void         gtk_tree_model_filter_drag_source_init                (GtkTreeDragSourceIface  *iface);
 337 static void         gtk_tree_model_filter_finalize                        (GObject                 *object);
 338 static void         gtk_tree_model_filter_set_property                    (GObject                 *object,
 339                                                                            guint                    prop_id,
 340                                                                            const GValue            *value,
 341                                                                            GParamSpec              *pspec);
 342 static void         gtk_tree_model_filter_get_property                    (GObject                 *object,
 343                                                                            guint                    prop_id,
 344                                                                            GValue                 *value,
 345                                                                            GParamSpec             *pspec);
 346
 347 /* signal handlers */
 348 static void         gtk_tree_model_filter_row_changed                     (GtkTreeModel           *c_model,
 349                                                                            GtkTreePath            *c_path,
 350                                                                            GtkTreeIter            *c_iter,
 351                                                                            gpointer                data);
 352 static void         gtk_tree_model_filter_row_inserted                    (GtkTreeModel           *c_model,
 353                                                                            GtkTreePath            *c_path,
 354                                                                            GtkTreeIter            *c_iter,
 355                                                                            gpointer                data);
 356 static void         gtk_tree_model_filter_row_has_child_toggled           (GtkTreeModel           *c_model,
 357                                                                            GtkTreePath            *c_path,
 358                                                                            GtkTreeIter            *c_iter,
 359                                                                            gpointer                data);
 360 static void         gtk_tree_model_filter_row_deleted                     (GtkTreeModel           *c_model,
 361                                                                            GtkTreePath            *c_path,
 362                                                                            gpointer                data);
 363 static void         gtk_tree_model_filter_rows_reordered                  (GtkTreeModel           *c_model,
 364                                                                            GtkTreePath            *c_path,
 365                                                                            GtkTreeIter            *c_iter,
 366                                                                            gint                   *new_order,
 367                                                                            gpointer                data);
 368
 369 /* GtkTreeModel interface */
 370 static GtkTreeModelFlags gtk_tree_model_filter_get_flags                       (GtkTreeModel           *model);
 371 static gint         gtk_tree_model_filter_get_n_columns                   (GtkTreeModel           *model);
 372 static GType        gtk_tree_model_filter_get_column_type                 (GtkTreeModel           *model,
 373                                                                            gint                    index);
 374 static gboolean     gtk_tree_model_filter_get_iter_full                   (GtkTreeModel           *model,
 375                                                                            GtkTreeIter            *iter,
 376                                                                            GtkTreePath            *path);
 377 static gboolean     gtk_tree_model_filter_get_iter                        (GtkTreeModel           *model,
 378                                                                            GtkTreeIter            *iter,
 379                                                                            GtkTreePath            *path);
 380 static GtkTreePath *gtk_tree_model_filter_get_path                        (GtkTreeModel           *model,
 381                                                                            GtkTreeIter            *iter);
 382 static void         gtk_tree_model_filter_get_value                       (GtkTreeModel           *model,
 383                                                                            GtkTreeIter            *iter,
 384                                                                            gint                    column,
 385                                                                            GValue                 *value);
 386 static gboolean     gtk_tree_model_filter_iter_next                       (GtkTreeModel           *model,
 387                                                                            GtkTreeIter            *iter);
 388 static gboolean     gtk_tree_model_filter_iter_previous                   (GtkTreeModel           *model,
 389                                                                            GtkTreeIter            *iter);
 390 static gboolean     gtk_tree_model_filter_iter_children                   (GtkTreeModel           *model,
 391                                                                            GtkTreeIter            *iter,
 392                                                                            GtkTreeIter            *parent);
 393 static gboolean     gtk_tree_model_filter_iter_has_child                  (GtkTreeModel           *model,
 394                                                                            GtkTreeIter            *iter);
 395 static gint         gtk_tree_model_filter_iter_n_children                 (GtkTreeModel           *model,
 396                                                                            GtkTreeIter            *iter);
 397 static gboolean     gtk_tree_model_filter_iter_nth_child                  (GtkTreeModel           *model,
 398                                                                            GtkTreeIter            *iter,
 399                                                                            GtkTreeIter            *parent,
 400                                                                            gint                    n);
 401 static gboolean     gtk_tree_model_filter_iter_parent                     (GtkTreeModel           *model,
 402                                                                            GtkTreeIter            *iter,
 403                                                                            GtkTreeIter            *child);
 404 static void         gtk_tree_model_filter_ref_node                        (GtkTreeModel           *model,
 405                                                                            GtkTreeIter            *iter);
 406 static void         gtk_tree_model_filter_unref_node                      (GtkTreeModel           *model,
 407                                                                            GtkTreeIter            *iter);
 408
 409 /* TreeDragSource interface */
 410 static gboolean    gtk_tree_model_filter_row_draggable                    (GtkTreeDragSource      *drag_source,
 411                                                                            GtkTreePath            *path);
 412 static gboolean    gtk_tree_model_filter_drag_data_get                    (GtkTreeDragSource      *drag_source,
 413                                                                            GtkTreePath            *path,
 414                                                                            GtkSelectionData       *selection_data);
 415 static gboolean    gtk_tree_model_filter_drag_data_delete                 (GtkTreeDragSource      *drag_source,
 416                                                                            GtkTreePath            *path);
 417
 418 /* private functions */
 419 static void        gtk_tree_model_filter_build_level                      (GtkTreeModelFilter     *filter,
 420                                                                            FilterLevel            *parent_level,
 421                                                                            FilterElt              *parent_elt,
 422                                                                            gboolean                emit_inserted);
 423
 424 static void        gtk_tree_model_filter_free_level                       (GtkTreeModelFilter     *filter,
 425                                                                            FilterLevel            *filter_level,
 426                                                                            gboolean                unref_self,
 427                                                                            gboolean                unref_parent,
 428                                                                            gboolean                unref_external);
 429
 430 static GtkTreePath *gtk_tree_model_filter_elt_get_path                    (FilterLevel            *level,
 431                                                                            FilterElt              *elt,
 432                                                                            GtkTreePath            *root);
 433
 434 static GtkTreePath *gtk_tree_model_filter_add_root                        (GtkTreePath            *src,
 435                                                                            GtkTreePath            *root);
 436 static GtkTreePath *gtk_tree_model_filter_remove_root                     (GtkTreePath            *src,
 437                                                                            GtkTreePath            *root);
 438
 439 static void         gtk_tree_model_filter_increment_stamp                 (GtkTreeModelFilter     *filter);
 440
 441 static void         gtk_tree_model_filter_real_modify                     (GtkTreeModelFilter     *self,
 442                                                                            GtkTreeModel           *child_model,
 443                                                                            GtkTreeIter            *iter,
 444                                                                            GValue                 *value,
 445                                                                            gint                    column);
 446 static gboolean     gtk_tree_model_filter_real_visible                    (GtkTreeModelFilter     *filter,
 447                                                                            GtkTreeModel           *child_model,
 448                                                                            GtkTreeIter            *child_iter);
 449 static gboolean     gtk_tree_model_filter_visible                         (GtkTreeModelFilter     *filter,
 450                                                                            GtkTreeIter            *child_iter);
 451 static void         gtk_tree_model_filter_clear_cache_helper              (GtkTreeModelFilter     *filter,
 452                                                                            FilterLevel            *level);
 453
 454 static void         gtk_tree_model_filter_real_ref_node                   (GtkTreeModel           *model,
 455                                                                            GtkTreeIter            *iter,
 456                                                                            gboolean                external);
 457 static void         gtk_tree_model_filter_real_unref_node                 (GtkTreeModel           *model,
 458                                                                            GtkTreeIter            *iter,
 459                                                                            gboolean                external,
 460                                                                            gboolean                propagate_unref);
 461
 462 static void         gtk_tree_model_filter_set_model                       (GtkTreeModelFilter     *filter,
 463                                                                            GtkTreeModel           *child_model);
 464 static void         gtk_tree_model_filter_ref_path                        (GtkTreeModelFilter     *filter,
 465                                                                            GtkTreePath            *path);
 466 static void         gtk_tree_model_filter_unref_path                      (GtkTreeModelFilter     *filter,
 467                                                                            GtkTreePath            *path,
 468                                                                            int                     depth);
 469 static void         gtk_tree_model_filter_set_root                        (GtkTreeModelFilter     *filter,
 470                                                                            GtkTreePath            *root);
 471
 472 static GtkTreePath *gtk_real_tree_model_filter_convert_child_path_to_path (GtkTreeModelFilter     *filter,
 473                                                                            GtkTreePath            *child_path,
 474                                                                            gboolean                build_levels,
 475                                                                            gboolean                fetch_children);
 476
 477 static gboolean    gtk_tree_model_filter_elt_is_visible_in_target         (FilterLevel            *level,
 478                                                                            FilterElt              *elt);
 479
 480 static FilterElt   *gtk_tree_model_filter_insert_elt_in_level             (GtkTreeModelFilter     *filter,
 481                                                                            GtkTreeIter            *c_iter,
 482                                                                            FilterLevel            *level,
 483                                                                            gint                    offset,
 484                                                                            gint                   *index);
 485 static FilterElt   *gtk_tree_model_filter_fetch_child                     (GtkTreeModelFilter     *filter,
 486                                                                            FilterLevel            *level,
 487                                                                            gint                    offset,
 488                                                                            gint                   *index);
 489 static void         gtk_tree_model_filter_remove_elt_from_level           (GtkTreeModelFilter     *filter,
 490                                                                            FilterLevel            *level,
 491                                                                            FilterElt              *elt);
 492 static void         gtk_tree_model_filter_update_children                 (GtkTreeModelFilter     *filter,
 493                                                                            FilterLevel            *level,
 494                                                                            FilterElt              *elt);
 495 static void         gtk_tree_model_filter_emit_row_inserted_for_path      (GtkTreeModelFilter     *filter,
 496                                                                            GtkTreeModel           *c_model,
 497                                                                            GtkTreePath            *c_path,
 498                                                                            GtkTreeIter            *c_iter);
 499
 500
 501 G_DEFINE_TYPE_WITH_CODE (GtkTreeModelFilter, gtk_tree_model_filter, G_TYPE_OBJECT,
 502                          G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_MODEL,
 503                                                 gtk_tree_model_filter_tree_model_init)
 504                          G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_DRAG_SOURCE,
 505                                                 gtk_tree_model_filter_drag_source_init))
 506
 507 static void
 508 gtk_tree_model_filter_init (GtkTreeModelFilter *filter)
 509 {
 510   filter->priv = G_TYPE_INSTANCE_GET_PRIVATE (filter,
 511                                               GTK_TYPE_TREE_MODEL_FILTER,
 512                                               GtkTreeModelFilterPrivate);
 513
 514   filter->priv->visible_column = -1;
 515   filter->priv->zero_ref_count = 0;
 516   filter->priv->visible_method_set = FALSE;
 517   filter->priv->modify_func_set = FALSE;
 518   filter->priv->in_row_deleted = FALSE;
 519   filter->priv->virtual_root_deleted = FALSE;
 520 }
 521
 522 static void
 523 gtk_tree_model_filter_class_init (GtkTreeModelFilterClass *filter_class)
 524 {
 525   GObjectClass *object_class;
 526
 527   object_class = (GObjectClass *) filter_class;
 528
 529   object_class->set_property = gtk_tree_model_filter_set_property;
 530   object_class->get_property = gtk_tree_model_filter_get_property;
 531
 532   object_class->finalize = gtk_tree_model_filter_finalize;
 533
 534   filter_class->visible = gtk_tree_model_filter_real_visible;
 535   filter_class->modify  = gtk_tree_model_filter_real_modify;
 536
 537   /* Properties -- FIXME: disabled translations for now, until I can come up with a
 538    * better description
 539    */
 540   g_object_class_install_property (object_class,
 541                                    PROP_CHILD_MODEL,
 542                                    g_param_spec_object ("child-model",
 543                                                         ("The child model"),
 544                                                         ("The model for the filtermodel to filter"),
 545                                                         GTK_TYPE_TREE_MODEL,
 546                                                         GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
 547
 548   g_object_class_install_property (object_class,
 549                                    PROP_VIRTUAL_ROOT,
 550                                    g_param_spec_boxed ("virtual-root",
 551                                                        ("The virtual root"),
 552                                                        ("The virtual root (relative to the child model) for this filtermodel"),
 553                                                        GTK_TYPE_TREE_PATH,
 554                                                        GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
 555
 556   g_type_class_add_private (object_class, sizeof (GtkTreeModelFilterPrivate));
 557 }
 558
 559 static void
 560 gtk_tree_model_filter_tree_model_init (GtkTreeModelIface *iface)
 561 {
 562   iface->get_flags = gtk_tree_model_filter_get_flags;
 563   iface->get_n_columns = gtk_tree_model_filter_get_n_columns;
 564   iface->get_column_type = gtk_tree_model_filter_get_column_type;
 565   iface->get_iter = gtk_tree_model_filter_get_iter;
 566   iface->get_path = gtk_tree_model_filter_get_path;
 567   iface->get_value = gtk_tree_model_filter_get_value;
 568   iface->iter_next = gtk_tree_model_filter_iter_next;
 569   iface->iter_previous = gtk_tree_model_filter_iter_previous;
 570   iface->iter_children = gtk_tree_model_filter_iter_children;
 571   iface->iter_has_child = gtk_tree_model_filter_iter_has_child;
 572   iface->iter_n_children = gtk_tree_model_filter_iter_n_children;
 573   iface->iter_nth_child = gtk_tree_model_filter_iter_nth_child;
 574   iface->iter_parent = gtk_tree_model_filter_iter_parent;
 575   iface->ref_node = gtk_tree_model_filter_ref_node;
 576   iface->unref_node = gtk_tree_model_filter_unref_node;
 577 }
 578
 579 static void
 580 gtk_tree_model_filter_drag_source_init (GtkTreeDragSourceIface *iface)
 581 {
 582   iface->row_draggable = gtk_tree_model_filter_row_draggable;
 583   iface->drag_data_delete = gtk_tree_model_filter_drag_data_delete;
 584   iface->drag_data_get = gtk_tree_model_filter_drag_data_get;
 585 }
 586
 587
 588 static void
 589 gtk_tree_model_filter_finalize (GObject *object)
 590 {
 591   GtkTreeModelFilter *filter = (GtkTreeModelFilter *) object;
 592
 593   if (filter->priv->virtual_root && !filter->priv->virtual_root_deleted)
 594     {
 595       gtk_tree_model_filter_unref_path (filter, filter->priv->virtual_root,
 596                                         -1);
 597       filter->priv->virtual_root_deleted = TRUE;
 598     }
 599
 600   gtk_tree_model_filter_set_model (filter, NULL);
 601
 602   if (filter->priv->virtual_root)
 603     gtk_tree_path_free (filter->priv->virtual_root);
 604
 605   if (filter->priv->root)
 606     gtk_tree_model_filter_free_level (filter, filter->priv->root, TRUE, TRUE, FALSE);
 607
 608   g_free (filter->priv->modify_types);
 609
 610   if (filter->priv->modify_destroy)
 611     filter->priv->modify_destroy (filter->priv->modify_data);
 612
 613   if (filter->priv->visible_destroy)
 614     filter->priv->visible_destroy (filter->priv->visible_data);
 615
 616   /* must chain up */
 617   G_OBJECT_CLASS (gtk_tree_model_filter_parent_class)->finalize (object);
 618 }
 619
 620 static void
 621 gtk_tree_model_filter_set_property (GObject      *object,
 622                                     guint         prop_id,
 623                                     const GValue *value,
 624                                     GParamSpec   *pspec)
 625 {
 626   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (object);
 627
 628   switch (prop_id)
 629     {
 630       case PROP_CHILD_MODEL:
 631         gtk_tree_model_filter_set_model (filter, g_value_get_object (value));
 632         break;
 633       case PROP_VIRTUAL_ROOT:
 634         gtk_tree_model_filter_set_root (filter, g_value_get_boxed (value));
 635         break;
 636       default:
 637         G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
 638         break;
 639     }
 640 }
 641
 642 static void
 643 gtk_tree_model_filter_get_property (GObject    *object,
 644                                     guint       prop_id,
 645                                     GValue     *value,
 646                                     GParamSpec *pspec)
 647 {
 648   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (object);
 649
 650   switch (prop_id)
 651     {
 652       case PROP_CHILD_MODEL:
 653         g_value_set_object (value, filter->priv->child_model);
 654         break;
 655       case PROP_VIRTUAL_ROOT:
 656         g_value_set_boxed (value, filter->priv->virtual_root);
 657         break;
 658       default:
 659         G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
 660         break;
 661     }
 662 }
 663
 664 /* helpers */
 665
 666 static FilterElt *
 667 filter_elt_new (void)
 668 {
 669   return g_slice_new (FilterElt);
 670 }
 671
 672 static void
 673 filter_elt_free (gpointer elt)
 674 {
 675   g_slice_free (FilterElt, elt);
 676 }
 677
 678 static gint
 679 filter_elt_cmp (gconstpointer a,
 680                 gconstpointer b,
 681                 gpointer      user_data)
 682 {
 683   const FilterElt *elt_a = a;
 684   const FilterElt *elt_b = b;
 685
 686   if (elt_a->offset > elt_b->offset)
 687     return +1;
 688   else if (elt_a->offset < elt_b->offset)
 689     return -1;
 690   else
 691     return 0;
 692 }
 693
 694 static FilterElt *
 695 lookup_elt_with_offset (GSequence      *seq,
 696                         gint            offset,
 697                         GSequenceIter **ret_siter)
 698 {
 699   GSequenceIter *siter;
 700   FilterElt dummy;
 701
 702   dummy.offset = offset;
 703   siter = g_sequence_lookup (seq, &dummy, filter_elt_cmp, NULL);
 704
 705   if (ret_siter)
 706     *ret_siter = siter;
 707
 708   return GET_ELT (siter);
 709 }
 710
 711 static void
 712 increase_offset_iter (gpointer data,
 713                       gpointer user_data)
 714 {
 715   FilterElt *elt = data;
 716   gint offset = GPOINTER_TO_INT (user_data);
 717
 718   if (elt->offset >= offset)
 719     elt->offset++;
 720 }
 721
 722 static void
 723 decrease_offset_iter (gpointer data,
 724                       gpointer user_data)
 725 {
 726   FilterElt *elt = data;
 727   gint offset = GPOINTER_TO_INT (user_data);
 728
 729   if (elt->offset > offset)
 730     elt->offset--;
 731 }
 732
 733 static void
 734 gtk_tree_model_filter_build_level (GtkTreeModelFilter *filter,
 735                                    FilterLevel        *parent_level,
 736                                    FilterElt          *parent_elt,
 737                                    gboolean            emit_inserted)
 738 {
 739   GtkTreeIter iter;
 740   GtkTreeIter first_node;
 741   GtkTreeIter root;
 742   FilterLevel *new_level;
 743   FilterLevel *tmp_level;
 744   FilterElt *tmp_elt;
 745   GtkTreeIter f_iter;
 746   gint length = 0;
 747   gint i;
 748   gboolean empty = TRUE;
 749
 750   g_assert (filter->priv->child_model != NULL);
 751
 752   /* Avoid building a level that already exists */
 753   if (parent_level)
 754     g_assert (parent_elt->children == NULL);
 755   else
 756     g_assert (filter->priv->root == NULL);
 757
 758   if (filter->priv->in_row_deleted)
 759     return;
 760
 761   if (!parent_level)
 762     {
 763       if (filter->priv->virtual_root)
 764         {
 765           if (gtk_tree_model_get_iter (filter->priv->child_model, &root, filter->priv->virtual_root) == FALSE)
 766             return;
 767           length = gtk_tree_model_iter_n_children (filter->priv->child_model, &root);
 768
 769           if (gtk_tree_model_iter_children (filter->priv->child_model, &iter, &root) == FALSE)
 770             return;
 771         }
 772       else
 773         {
 774           if (!gtk_tree_model_get_iter_first (filter->priv->child_model, &iter))
 775             return;
 776           length = gtk_tree_model_iter_n_children (filter->priv->child_model, NULL);
 777         }
 778     }
 779   else
 780     {
 781       GtkTreeIter parent_iter;
 782       GtkTreeIter child_parent_iter;
 783
 784       parent_iter.stamp = filter->priv->stamp;
 785       parent_iter.user_data = parent_level;
 786       parent_iter.user_data2 = parent_elt;
 787
 788       gtk_tree_model_filter_convert_iter_to_child_iter (filter,
 789                                                         &child_parent_iter,
 790                                                         &parent_iter);
 791       if (gtk_tree_model_iter_children (filter->priv->child_model, &iter, &child_parent_iter) == FALSE)
 792         return;
 793
 794       /* stamp may have changed */
 795       gtk_tree_model_filter_convert_iter_to_child_iter (filter,
 796                                                         &child_parent_iter,
 797                                                         &parent_iter);
 798       length = gtk_tree_model_iter_n_children (filter->priv->child_model, &child_parent_iter);
 799
 800       /* Take a reference on the parent */
 801       gtk_tree_model_filter_real_ref_node (GTK_TREE_MODEL (filter),
 802                                            &parent_iter, FALSE);
 803     }
 804
 805   g_return_if_fail (length > 0);
 806
 807   new_level = g_new (FilterLevel, 1);
 808   new_level->seq = g_sequence_new (filter_elt_free);
 809   new_level->visible_seq = g_sequence_new (NULL);
 810   new_level->ref_count = 0;
 811   new_level->ext_ref_count = 0;
 812   new_level->parent_elt = parent_elt;
 813   new_level->parent_level = parent_level;
 814
 815   if (parent_elt)
 816     parent_elt->children = new_level;
 817   else
 818     filter->priv->root = new_level;
 819
 820   /* increase the count of zero ref_counts */
 821   tmp_level = parent_level;
 822   tmp_elt = parent_elt;
 823
 824   while (tmp_level)
 825     {
 826       tmp_elt->zero_ref_count++;
 827
 828       tmp_elt = tmp_level->parent_elt;
 829       tmp_level = tmp_level->parent_level;
 830     }
 831   if (new_level != filter->priv->root)
 832     filter->priv->zero_ref_count++;
 833
 834   i = 0;
 835
 836   first_node = iter;
 837
 838   do
 839     {
 840       if (gtk_tree_model_filter_visible (filter, &iter))
 841         {
 842           FilterElt *filter_elt;
 843
 844           filter_elt = filter_elt_new ();
 845           filter_elt->offset = i;
 846           filter_elt->zero_ref_count = 0;
 847           filter_elt->ref_count = 0;
 848           filter_elt->ext_ref_count = 0;
 849           filter_elt->children = NULL;
 850           filter_elt->visible_siter = NULL;
 851
 852           if (GTK_TREE_MODEL_FILTER_CACHE_CHILD_ITERS (filter))
 853             filter_elt->iter = iter;
 854
 855           g_sequence_append (new_level->seq, filter_elt);
 856           filter_elt->visible_siter = g_sequence_append (new_level->visible_seq, filter_elt);
 857           empty = FALSE;
 858
 859           if (emit_inserted)
 860             {
 861               GtkTreePath *f_path;
 862               GtkTreeIter f_iter;
 863               GtkTreeIter children;
 864
 865               f_iter.stamp = filter->priv->stamp;
 866               f_iter.user_data = new_level;
 867               f_iter.user_data2 = filter_elt;
 868
 869               f_path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter),
 870                                                 &f_iter);
 871               gtk_tree_model_row_inserted (GTK_TREE_MODEL (filter),
 872                                            f_path, &f_iter);
 873               gtk_tree_path_free (f_path);
 874
 875               if (gtk_tree_model_iter_children (filter->priv->child_model,
 876                                                 &children, &iter))
 877                 gtk_tree_model_filter_update_children (filter,
 878                                                        new_level,
 879                                                        FILTER_ELT (f_iter.user_data2));
 880             }
 881         }
 882       i++;
 883     }
 884   while (gtk_tree_model_iter_next (filter->priv->child_model, &iter));
 885
 886   /* The level does not contain any visible nodes.  However, changes in
 887    * this level might affect the parent node, which can either be visible
 888    * or invisible.  Therefore, this level can only be removed again,
 889    * if the parent level has an external reference count of zero.  That is,
 890    * if this level changes state, no signals are required in the parent
 891    * level.
 892    */
 893   if (empty &&
 894        (parent_level && parent_level->ext_ref_count == 0))
 895     {
 896       gtk_tree_model_filter_free_level (filter, new_level, FALSE, TRUE, FALSE);
 897       return;
 898     }
 899
 900   /* If none of the nodes are visible, we will just pull in the
 901    * first node of the level.
 902    */
 903   if (empty)
 904     {
 905       FilterElt *filter_elt;
 906
 907       filter_elt = filter_elt_new ();
 908       filter_elt->offset = 0;
 909       filter_elt->zero_ref_count = 0;
 910       filter_elt->ref_count = 0;
 911       filter_elt->ext_ref_count = 0;
 912       filter_elt->children = NULL;
 913       filter_elt->visible_siter = NULL;
 914
 915       if (GTK_TREE_MODEL_FILTER_CACHE_CHILD_ITERS (filter))
 916         filter_elt->iter = first_node;
 917
 918       g_sequence_append (new_level->seq, filter_elt);
 919     }
 920
 921   /* Keep a reference on the first node of this level.  We need this
 922    * to make sure that we get all signals for this level.
 923    */
 924   f_iter.stamp = filter->priv->stamp;
 925   f_iter.user_data = new_level;
 926   f_iter.user_data2 = g_sequence_get (g_sequence_get_begin_iter (new_level->seq));
 927
 928   gtk_tree_model_filter_real_ref_node (GTK_TREE_MODEL (filter), &f_iter,
 929                                        FALSE);
 930 }
 931
 932 static void
 933 gtk_tree_model_filter_free_level (GtkTreeModelFilter *filter,
 934                                   FilterLevel        *filter_level,
 935                                   gboolean            unref_self,
 936                                   gboolean            unref_parent,
 937                                   gboolean            unref_external)
 938 {
 939   GSequenceIter *siter;
 940   GSequenceIter *end_siter;
 941
 942   g_assert (filter_level);
 943
 944   end_siter = g_sequence_get_end_iter (filter_level->seq);
 945   for (siter = g_sequence_get_begin_iter (filter_level->seq);
 946        siter != end_siter;
 947        siter = g_sequence_iter_next (siter))
 948     {
 949       FilterElt *elt = g_sequence_get (siter);
 950
 951       if (elt->children)
 952         {
 953           /* If we recurse and unref_self == FALSE, then unref_parent
 954            * must also be FALSE (otherwise a still unref a node in this
 955            * level).
 956            */
 957           gtk_tree_model_filter_free_level (filter,
 958                                             FILTER_LEVEL (elt->children),
 959                                             unref_self,
 960                                             unref_self == FALSE ? FALSE : unref_parent,
 961                                             unref_external);
 962         }
 963
 964       if (unref_external)
 965         {
 966           GtkTreeIter f_iter;
 967
 968           f_iter.stamp = filter->priv->stamp;
 969           f_iter.user_data = filter_level;
 970           f_iter.user_data2 = elt;
 971
 972           while (elt->ext_ref_count > 0)
 973             gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
 974                                                    &f_iter,
 975                                                    TRUE, unref_self);
 976         }
 977     }
 978
 979   /* Release the reference on the first item.
 980    */
 981   if (unref_self)
 982     {
 983       GtkTreeIter f_iter;
 984
 985       f_iter.stamp = filter->priv->stamp;
 986       f_iter.user_data = filter_level;
 987       f_iter.user_data2 = g_sequence_get (g_sequence_get_begin_iter (filter_level->seq));
 988
 989       gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
 990                                              &f_iter, FALSE, TRUE);
 991     }
 992
 993   if (filter_level->ext_ref_count == 0)
 994     {
 995       FilterLevel *parent_level = filter_level->parent_level;
 996       FilterElt *parent_elt = filter_level->parent_elt;
 997
 998       while (parent_level)
 999         {
1000           parent_elt->zero_ref_count--;
1001
1002           parent_elt = parent_level->parent_elt;
1003           parent_level = parent_level->parent_level;
1004         }
1005
1006       if (filter_level != filter->priv->root)
1007         filter->priv->zero_ref_count--;
1008     }
1009
1010 #ifdef MODEL_FILTER_DEBUG
1011   if (filter_level == filter->priv->root)
1012     g_assert (filter->priv->zero_ref_count == 0);
1013 #endif
1014
1015   if (filter_level->parent_elt)
1016     {
1017       /* Release reference on parent */
1018       GtkTreeIter parent_iter;
1019
1020       parent_iter.stamp = filter->priv->stamp;
1021       parent_iter.user_data = filter_level->parent_level;
1022       parent_iter.user_data2 = filter_level->parent_elt;
1023
1024       gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
1025                                              &parent_iter, FALSE, unref_parent);
1026
1027       filter_level->parent_elt->children = NULL;
1028     }
1029   else
1030     filter->priv->root = NULL;
1031
1032   g_sequence_free (filter_level->seq);
1033   g_sequence_free (filter_level->visible_seq);
1034   g_free (filter_level);
1035 }
1036
1037 /* prune_level() is like free_level(), however instead of being fully
1038  * freed, the level is pruned to a level with only the first node used
1039  * for monitoring.  For now it is only being called from
1040  * gtk_tree_model_filter_remove_elt_from_level(), which is the reason
1041  * this function is lacking a "gboolean unref" argument.
1042  */
1043 static void
1044 gtk_tree_model_filter_prune_level (GtkTreeModelFilter *filter,
1045                                    FilterLevel        *level)
1046 {
1047   GSequenceIter *siter;
1048   GSequenceIter *end_siter;
1049   FilterElt *elt;
1050   GtkTreeIter f_iter;
1051
1052   /* This function is called when the parent of level became invisible.
1053    * All external ref counts of the children need to be dropped.
1054    * All children except the first one can be removed.
1055    */
1056
1057   /* Any child levels can be freed */
1058   end_siter = g_sequence_get_end_iter (level->seq);
1059   for (siter = g_sequence_get_begin_iter (level->seq);
1060        siter != end_siter;
1061        siter = g_sequence_iter_next (siter))
1062     {
1063       FilterElt *elt = g_sequence_get (siter);
1064
1065       if (elt->children)
1066         gtk_tree_model_filter_free_level (filter,
1067                                           FILTER_LEVEL (elt->children),
1068                                           TRUE, TRUE, TRUE);
1069     }
1070
1071   /* For the first item, only drop the external references */
1072   elt = g_sequence_get (g_sequence_get_begin_iter (level->seq));
1073
1074   f_iter.stamp = filter->priv->stamp;
1075   f_iter.user_data = level;
1076   f_iter.user_data2 = elt;
1077
1078   while (elt->ext_ref_count > 0)
1079     gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
1080                                            &f_iter, TRUE, TRUE);
1081
1082   if (elt->visible_siter)
1083     {
1084       g_sequence_remove (elt->visible_siter);
1085       elt->visible_siter = NULL;
1086     }
1087
1088   /* Remove the other elts */
1089   end_siter = g_sequence_get_end_iter (level->seq);
1090   siter = g_sequence_get_begin_iter (level->seq);
1091   siter = g_sequence_iter_next (siter);
1092   for (; siter != end_siter; siter = g_sequence_iter_next (siter))
1093     {
1094       elt = g_sequence_get (siter);
1095
1096       f_iter.stamp = filter->priv->stamp;
1097       f_iter.user_data = level;
1098       f_iter.user_data2 = elt;
1099
1100       while (elt->ext_ref_count > 0)
1101         gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
1102                                                &f_iter, TRUE, TRUE);
1103       /* In this case, we do remove reference counts we've added ourselves,
1104        * since the node will be removed from the data structures.
1105        */
1106       while (elt->ref_count > 0)
1107         gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
1108                                                &f_iter, FALSE, TRUE);
1109
1110       if (elt->visible_siter)
1111         {
1112           g_sequence_remove (elt->visible_siter);
1113           elt->visible_siter = NULL;
1114         }
1115     }
1116
1117   /* Remove [begin + 1, end] */
1118   siter = g_sequence_get_begin_iter (level->seq);
1119   siter = g_sequence_iter_next (siter);
1120
1121   g_sequence_remove_range (siter, end_siter);
1122
1123   /* The level must have reached an ext ref count of zero by now, though
1124    * we only assert on this in debugging mode.
1125    */
1126 #ifdef MODEL_FILTER_DEBUG
1127   g_assert (level->ext_ref_count == 0);
1128 #endif
1129 }
1130
1131 static void
1132 gtk_tree_model_filter_level_transfer_first_ref (GtkTreeModelFilter *filter,
1133                                                 FilterLevel        *level,
1134                                                 GSequenceIter      *from_iter,
1135                                                 GSequenceIter      *to_iter)
1136 {
1137   GtkTreeIter f_iter;
1138
1139   f_iter.stamp = filter->priv->stamp;
1140   f_iter.user_data = level;
1141   f_iter.user_data2 = g_sequence_get (to_iter);
1142
1143   gtk_tree_model_filter_real_ref_node (GTK_TREE_MODEL (filter),
1144                                        &f_iter, FALSE);
1145
1146   f_iter.stamp = filter->priv->stamp;
1147   f_iter.user_data = level;
1148   f_iter.user_data2 = g_sequence_get (from_iter);
1149
1150   gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
1151                                          &f_iter, FALSE, TRUE);
1152 }
1153
1154 static void
1155 gtk_tree_model_filter_level_transfer_first_ref_with_index (GtkTreeModelFilter *filter,
1156                                                            FilterLevel        *level,
1157                                                            gint                from_index,
1158                                                            gint                to_index)
1159 {
1160   gtk_tree_model_filter_level_transfer_first_ref (filter, level,
1161                                                   g_sequence_get_iter_at_pos (level->seq, from_index),
1162                                                   g_sequence_get_iter_at_pos (level->seq, to_index));
1163 }
1164
1165 /* Creates paths suitable for accessing the child model. */
1166 static GtkTreePath *
1167 gtk_tree_model_filter_elt_get_path (FilterLevel *level,
1168                                     FilterElt   *elt,
1169                                     GtkTreePath *root)
1170 {
1171   FilterLevel *walker = level;
1172   FilterElt *walker2 = elt;
1173   GtkTreePath *path;
1174   GtkTreePath *real_path;
1175
1176   g_return_val_if_fail (level != NULL, NULL);
1177   g_return_val_if_fail (elt != NULL, NULL);
1178
1179   path = gtk_tree_path_new ();
1180
1181   while (walker)
1182     {
1183       gtk_tree_path_prepend_index (path, walker2->offset);
1184
1185       walker2 = walker->parent_elt;
1186       walker = walker->parent_level;
1187     }
1188
1189   if (root)
1190     {
1191       real_path = gtk_tree_model_filter_add_root (path, root);
1192       gtk_tree_path_free (path);
1193       return real_path;
1194     }
1195
1196   return path;
1197 }
1198
1199 static GtkTreePath *
1200 gtk_tree_model_filter_add_root (GtkTreePath *src,
1201                                 GtkTreePath *root)
1202 {
1203   GtkTreePath *retval;
1204   gint i;
1205
1206   retval = gtk_tree_path_copy (root);
1207
1208   for (i = 0; i < gtk_tree_path_get_depth (src); i++)
1209     gtk_tree_path_append_index (retval, gtk_tree_path_get_indices (src)[i]);
1210
1211   return retval;
1212 }
1213
1214 static GtkTreePath *
1215 gtk_tree_model_filter_remove_root (GtkTreePath *src,
1216                                    GtkTreePath *root)
1217 {
1218   GtkTreePath *retval;
1219   gint i;
1220   gint depth;
1221   gint *indices;
1222
1223   if (gtk_tree_path_get_depth (src) <= gtk_tree_path_get_depth (root))
1224     return NULL;
1225
1226   depth = gtk_tree_path_get_depth (src);
1227   indices = gtk_tree_path_get_indices (src);
1228
1229   for (i = 0; i < gtk_tree_path_get_depth (root); i++)
1230     if (indices[i] != gtk_tree_path_get_indices (root)[i])
1231       return NULL;
1232
1233   retval = gtk_tree_path_new ();
1234
1235   for (; i < depth; i++)
1236     gtk_tree_path_append_index (retval, indices[i]);
1237
1238   return retval;
1239 }
1240
1241 static void
1242 gtk_tree_model_filter_increment_stamp (GtkTreeModelFilter *filter)
1243 {
1244   do
1245     {
1246       filter->priv->stamp++;
1247     }
1248   while (filter->priv->stamp == 0);
1249
1250   gtk_tree_model_filter_clear_cache (filter);
1251 }
1252
1253 static gboolean
1254 gtk_tree_model_filter_real_visible (GtkTreeModelFilter *filter,
1255                                     GtkTreeModel       *child_model,
1256                                     GtkTreeIter        *child_iter)
1257 {
1258   if (filter->priv->visible_func)
1259     {
1260       return filter->priv->visible_func (child_model,
1261                                          child_iter,
1262                                          filter->priv->visible_data)
1263         ? TRUE : FALSE;
1264     }
1265   else if (filter->priv->visible_column >= 0)
1266    {
1267      GValue val = {0, };
1268
1269      gtk_tree_model_get_value (child_model, child_iter,
1270                                filter->priv->visible_column, &val);
1271
1272      if (g_value_get_boolean (&val))
1273        {
1274          g_value_unset (&val);
1275          return TRUE;
1276        }
1277
1278      g_value_unset (&val);
1279      return FALSE;
1280    }
1281
1282   /* no visible function set, so always visible */
1283   return TRUE;
1284 }
1285
1286 static gboolean
1287 gtk_tree_model_filter_visible (GtkTreeModelFilter *self,
1288                                GtkTreeIter        *child_iter)
1289 {
1290   return GTK_TREE_MODEL_FILTER_GET_CLASS (self)->visible (self,
1291       self->priv->child_model, child_iter);
1292 }
1293
1294 static void
1295 gtk_tree_model_filter_clear_cache_helper_iter (gpointer data,
1296                                                gpointer user_data)
1297 {
1298   GtkTreeModelFilter *filter = user_data;
1299   FilterElt *elt = data;
1300
1301 #ifdef MODEL_FILTER_DEBUG
1302   g_assert (elt->zero_ref_count >= 0);
1303 #endif
1304
1305   if (elt->zero_ref_count > 0)
1306     gtk_tree_model_filter_clear_cache_helper (filter, elt->children);
1307 }
1308
1309 static void
1310 gtk_tree_model_filter_clear_cache_helper (GtkTreeModelFilter *filter,
1311                                           FilterLevel        *level)
1312 {
1313   g_assert (level);
1314
1315   g_sequence_foreach (level->seq, gtk_tree_model_filter_clear_cache_helper_iter, filter);
1316
1317   /* If the level's ext_ref_count is zero, it means the level is not visible
1318    * and can be removed.  But, since we support monitoring a child level
1319    * of a parent for changes (these might affect the parent), we will only
1320    * free the level if the parent level also has an external ref
1321    * count of zero.  In that case, changes concerning our parent are
1322    * not requested.
1323    *
1324    * The root level is always visible, so an exception holds for levels
1325    * with the root level as parent level: these have to remain cached.
1326    */
1327   if (level->ext_ref_count == 0 && level != filter->priv->root &&
1328       level->parent_level && level->parent_level != filter->priv->root &&
1329       level->parent_level->ext_ref_count == 0)
1330     {
1331       gtk_tree_model_filter_free_level (filter, level, TRUE, TRUE, FALSE);
1332       return;
1333     }
1334 }
1335
1336 static gboolean
1337 gtk_tree_model_filter_elt_is_visible_in_target (FilterLevel *level,
1338                                                 FilterElt   *elt)
1339 {
1340   if (!elt->visible_siter)
1341     return FALSE;
1342
1343   if (!level->parent_elt)
1344     return TRUE;
1345
1346   do
1347     {
1348       elt = level->parent_elt;
1349       level = level->parent_level;
1350
1351       if (elt && !elt->visible_siter)
1352         return FALSE;
1353     }
1354   while (level);
1355
1356   return TRUE;
1357 }
1358
1359 /* If a change has occurred in path (inserted, changed or deleted),
1360  * then this function is used to check all its ancestors.  An ancestor
1361  * could have changed state as a result and this needs to be propagated
1362  * to the objects monitoring the filter model.
1363  */
1364 static void
1365 gtk_tree_model_filter_check_ancestors (GtkTreeModelFilter *filter,
1366                                        GtkTreePath        *path)
1367 {
1368   int i = 0;
1369   int *indices = gtk_tree_path_get_indices (path);
1370   FilterElt *elt;
1371   FilterLevel *level;
1372   GtkTreeIter c_iter, tmp_iter;
1373
1374   level = FILTER_LEVEL (filter->priv->root);
1375
1376   if (!level)
1377     return;
1378
1379   if (filter->priv->virtual_root)
1380     gtk_tree_model_get_iter (filter->priv->child_model, &c_iter,
1381                              filter->priv->virtual_root);
1382
1383   tmp_iter = c_iter;
1384   gtk_tree_model_iter_nth_child (filter->priv->child_model, &c_iter,
1385                                  filter->priv->virtual_root ? &tmp_iter : NULL,
1386                                  indices[i]);
1387
1388   while (i < gtk_tree_path_get_depth (path) - 1)
1389     {
1390       gboolean requested_state;
1391
1392       elt = lookup_elt_with_offset (level->seq,
1393                                     gtk_tree_path_get_indices (path)[i], NULL);
1394
1395       requested_state = gtk_tree_model_filter_visible (filter, &c_iter);
1396
1397       if (!elt)
1398         {
1399           int index;
1400           GtkTreePath *c_path;
1401
1402           if (requested_state == FALSE)
1403             return;
1404
1405           /* The elt does not exist in this level (so it is not
1406            * visible), but should now be visible.  We emit the
1407            * row-inserted and row-has-child-toggled signals.
1408            */
1409           elt = gtk_tree_model_filter_insert_elt_in_level (filter,
1410                                                            &c_iter,
1411                                                            level,
1412                                                            indices[i],
1413                                                            &index);
1414
1415           /* insert_elt_in_level defaults to FALSE */
1416           elt->visible_siter = g_sequence_insert_sorted (level->visible_seq,
1417                                                          elt,
1418                                                          filter_elt_cmp, NULL);
1419
1420           c_path = gtk_tree_model_get_path (filter->priv->child_model,
1421                                             &c_iter);
1422
1423           gtk_tree_model_filter_emit_row_inserted_for_path (filter,
1424                                                             filter->priv->child_model,
1425                                                             c_path,
1426                                                             &c_iter);
1427
1428           gtk_tree_path_free (c_path);
1429
1430           /* We can immediately return, because this node was not visible
1431            * before and its children will be checked for in response to
1432            * the emitted row-has-child-toggled signal.
1433            */
1434           return;
1435         }
1436       else if (elt->visible_siter)
1437         {
1438           if (!requested_state)
1439             {
1440               /* A node has turned invisible.  Remove it from the level
1441                * and emit row-deleted.  Since this node is being
1442                * deleted. it makes no sense to look further up the
1443                * chain.
1444                */
1445               gtk_tree_model_filter_remove_elt_from_level (filter,
1446                                                            level, elt);
1447               return;
1448             }
1449
1450           /* Otherwise continue up the chain */
1451         }
1452       else if (!elt->visible_siter)
1453         {
1454           if (requested_state)
1455             {
1456               /* A node is already in the cache, but invisible.  This
1457                * is usually a node on which a reference is kept by
1458                * the filter model, or a node fetched on the filter's
1459                * request, and thus not shown.  Therefore, we will
1460                * not emit row-inserted for this node.  Instead,
1461                * we signal to its parent that a change has occurred.
1462                *
1463                * Exception: root level, in this case, we must emit
1464                * row-inserted.
1465                */
1466               if (level->parent_level)
1467                 {
1468                   GtkTreeIter f_iter;
1469                   GtkTreePath *f_path;
1470
1471                   elt->visible_siter = g_sequence_insert_sorted (level->visible_seq, elt,
1472                                                                  filter_elt_cmp, NULL);
1473
1474                   f_iter.stamp = filter->priv->stamp;
1475                   f_iter.user_data = level->parent_level;
1476                   f_iter.user_data2 = level->parent_elt;
1477
1478                   f_path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter),
1479                                                     &f_iter);
1480                   gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (filter),
1481                                                         f_path, &f_iter);
1482                   gtk_tree_path_free (f_path);
1483                 }
1484               else
1485                 {
1486                   GtkTreePath *c_path;
1487
1488                   elt->visible_siter = g_sequence_insert_sorted (level->visible_seq, elt,
1489                                                                  filter_elt_cmp, NULL);
1490
1491                   c_path = gtk_tree_model_get_path (filter->priv->child_model,
1492                                                     &c_iter);
1493
1494                   gtk_tree_model_filter_emit_row_inserted_for_path (filter,
1495                                                                     filter->priv->child_model,
1496                                                                     c_path,
1497                                                                     &c_iter);
1498
1499                   gtk_tree_path_free (c_path);
1500                 }
1501
1502               /* We can immediately return, because this node was not visible
1503                * before and the parent will check its children, including
1504                * this node, in response to the emitted row-has-child-toggled
1505                * signal.
1506                */
1507               return;
1508             }
1509
1510           /* Not visible, so no need to continue. */
1511           return;
1512         }
1513
1514       if (!elt->children)
1515         {
1516           /* If an elt does not have children, these are not visible.
1517            * Therefore, any signals emitted for these children will
1518            * be ignored, so we do not have to emit them.
1519            */
1520           return;
1521         }
1522
1523       level = elt->children;
1524       i++;
1525
1526       tmp_iter = c_iter;
1527       gtk_tree_model_iter_nth_child (filter->priv->child_model, &c_iter,
1528                                      &tmp_iter, indices[i]);
1529     }
1530 }
1531
1532 static FilterElt *
1533 gtk_tree_model_filter_insert_elt_in_level (GtkTreeModelFilter *filter,
1534                                            GtkTreeIter        *c_iter,
1535                                            FilterLevel        *level,
1536                                            gint                offset,
1537                                            gint               *index)
1538 {
1539   FilterElt *elt;
1540   GSequenceIter *siter;
1541
1542   elt = filter_elt_new ();
1543
1544   if (GTK_TREE_MODEL_FILTER_CACHE_CHILD_ITERS (filter))
1545     elt->iter = *c_iter;
1546
1547   elt->offset = offset;
1548   elt->zero_ref_count = 0;
1549   elt->ref_count = 0;
1550   elt->ext_ref_count = 0;
1551   elt->children = NULL;
1552
1553   /* Because we don't emit row_inserted, the node is invisible and thus
1554    * not inserted in visible_seq
1555    */
1556   elt->visible_siter = NULL;
1557
1558   siter = g_sequence_insert_sorted (level->seq, elt, filter_elt_cmp, NULL);
1559   *index = g_sequence_iter_get_position (siter);
1560
1561   /* If the insert location is zero, we need to move our reference
1562    * on the old first node to the new first node.
1563    */
1564   if (*index == 0)
1565     gtk_tree_model_filter_level_transfer_first_ref_with_index (filter, level,
1566                                                                1, 0);
1567
1568   return elt;
1569 }
1570
1571 static FilterElt *
1572 gtk_tree_model_filter_fetch_child (GtkTreeModelFilter *filter,
1573                                    FilterLevel        *level,
1574                                    gint                offset,
1575                                    gint               *index)
1576 {
1577   gint len;
1578   GtkTreePath *c_path = NULL;
1579   GtkTreeIter c_iter;
1580   GtkTreePath *c_parent_path = NULL;
1581   GtkTreeIter c_parent_iter;
1582
1583   /* check if child exists and is visible */
1584   if (level->parent_elt)
1585     {
1586       c_parent_path =
1587         gtk_tree_model_filter_elt_get_path (level->parent_level,
1588                                             level->parent_elt,
1589                                             filter->priv->virtual_root);
1590       if (!c_parent_path)
1591         return NULL;
1592     }
1593   else
1594     {
1595       if (filter->priv->virtual_root)
1596         c_parent_path = gtk_tree_path_copy (filter->priv->virtual_root);
1597       else
1598         c_parent_path = NULL;
1599     }
1600
1601   if (c_parent_path)
1602     {
1603       gtk_tree_model_get_iter (filter->priv->child_model,
1604                                &c_parent_iter,
1605                                c_parent_path);
1606       len = gtk_tree_model_iter_n_children (filter->priv->child_model,
1607                                             &c_parent_iter);
1608
1609       c_path = gtk_tree_path_copy (c_parent_path);
1610       gtk_tree_path_free (c_parent_path);
1611     }
1612   else
1613     {
1614       len = gtk_tree_model_iter_n_children (filter->priv->child_model, NULL);
1615       c_path = gtk_tree_path_new ();
1616     }
1617
1618   gtk_tree_path_append_index (c_path, offset);
1619   gtk_tree_model_get_iter (filter->priv->child_model, &c_iter, c_path);
1620   gtk_tree_path_free (c_path);
1621
1622   if (offset >= len || !gtk_tree_model_filter_visible (filter, &c_iter))
1623     return NULL;
1624
1625   return gtk_tree_model_filter_insert_elt_in_level (filter, &c_iter,
1626                                                     level, offset,
1627                                                     index);
1628 }
1629
1630 /* Note that this function is never called from the row-deleted handler.
1631  * This means that this function is only used for removing elements
1632  * which are still present in the child model.  As a result, we must
1633  * take care to properly release the references the filter model has
1634  * on the child model nodes.
1635  */
1636 static void
1637 gtk_tree_model_filter_remove_elt_from_level (GtkTreeModelFilter *filter,
1638                                              FilterLevel        *level,
1639                                              FilterElt          *elt)
1640 {
1641   FilterElt *parent;
1642   FilterLevel *parent_level;
1643   gint length, orig_level_ext_ref_count;
1644   GtkTreeIter iter;
1645   GtkTreePath *path = NULL;
1646
1647   gboolean emit_child_toggled = FALSE;
1648
1649   /* We need to know about the level's ext ref count before removal
1650    * of this node.
1651    */
1652   orig_level_ext_ref_count = level->ext_ref_count;
1653
1654   iter.stamp = filter->priv->stamp;
1655   iter.user_data = level;
1656   iter.user_data2 = elt;
1657
1658   if (!parent || orig_level_ext_ref_count > 0)
1659     path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
1660   else
1661     /* If the level is not visible, the parent is potentially invisible
1662      * too.  Either way, as no signal will be emitted, there is no use
1663      * for a path.
1664      */
1665     path = NULL;
1666
1667   parent = level->parent_elt;
1668   parent_level = level->parent_level;
1669
1670   length = g_sequence_get_length (level->seq);
1671
1672   /* first register the node to be invisible */
1673   g_sequence_remove (elt->visible_siter);
1674   elt->visible_siter = NULL;
1675
1676   /*
1677    * If level != root level and the number of visible nodes is 0 (ie. this
1678    * is the last node to be removed from the level), emit
1679    * row-has-child-toggled.
1680    */
1681
1682   if (level != filter->priv->root
1683       && g_sequence_get_length (level->visible_seq) == 0
1684       && parent
1685       && parent->visible_siter)
1686     emit_child_toggled = TRUE;
1687
1688   /* Distinguish:
1689    *   - length > 1: in this case, the node is removed from the level
1690    *                 and row-deleted is emitted.
1691    *   - length == 1: in this case, we need to decide whether to keep
1692    *                  the level or to free it.
1693    */
1694   if (length > 1)
1695     {
1696       GSequenceIter *siter;
1697
1698       /* We emit row-deleted, and remove the node from the cache.
1699        * If it has any children, these will be removed here as well.
1700        */
1701
1702       /* FIXME: I am not 100% sure it is always save to fully free the
1703        * level here.  Perhaps the state of the parent level, etc. has to
1704        * be checked to make the right decision, like is done below for
1705        * the case length == 1.
1706        */
1707       if (elt->children)
1708         gtk_tree_model_filter_free_level (filter, elt->children, TRUE, TRUE, TRUE);
1709
1710       /* If the first node is being removed, transfer, the reference */
1711       if (elt == g_sequence_get (g_sequence_get_begin_iter (level->seq)))
1712         {
1713           gtk_tree_model_filter_level_transfer_first_ref_with_index (filter, level,
1714                                                                      0, 1);
1715         }
1716
1717       while (elt->ext_ref_count > 0)
1718         gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
1719                                                &iter, TRUE, TRUE);
1720       /* In this case, we do remove reference counts we've added ourselves,
1721        * since the node will be removed from the data structures.
1722        */
1723       while (elt->ref_count > 0)
1724         gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
1725                                                &iter, FALSE, TRUE);
1726
1727       /* remove the node */
1728       lookup_elt_with_offset (level->seq, elt->offset, &siter);
1729       g_sequence_remove (siter);
1730
1731       gtk_tree_model_filter_increment_stamp (filter);
1732
1733       /* Only if the node is in the root level (parent == NULL) or
1734        * the level is visible, a row-deleted signal is necessary.
1735        */
1736       if (!parent || orig_level_ext_ref_count > 0)
1737         gtk_tree_model_row_deleted (GTK_TREE_MODEL (filter), path);
1738     }
1739   else
1740     {
1741       /* There is only one node left in this level */
1742 #ifdef MODEL_FILTER_DEBUG
1743       g_assert (length == 1);
1744 #endif
1745
1746       /* The row is signalled as deleted to the client.  We have to
1747        * drop the remaining external reference count here, the client
1748        * will not do it.
1749        *
1750        * We keep the reference counts we've obtained ourselves.
1751        */
1752       while (elt->ext_ref_count > 0)
1753         gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
1754                                                &iter, TRUE, TRUE);
1755
1756       /* This level is still required if:
1757        * - it is the root level
1758        * - its parent level is the root level
1759        * - its parent level has an external ref count > 0
1760        */
1761       if (! (level == filter->priv->root ||
1762              level->parent_level == filter->priv->root ||
1763              level->parent_level->ext_ref_count > 0))
1764         {
1765           /* Otherwise, the level can be removed */
1766           gtk_tree_model_filter_free_level (filter, level, TRUE, TRUE, TRUE);
1767         }
1768       else
1769         {
1770           /* Level is kept, but we turn our attention to a child level.
1771            *
1772            * If level is not the root level, it is a child level with
1773            * an ext ref count that is now 0.  That means that any child level
1774            * of elt can be removed.
1775            */
1776           if (level != filter->priv->root)
1777             {
1778 #ifdef MODEL_FILTER_DEBUG
1779               g_assert (level->ext_ref_count == 0);
1780 #endif
1781               if (elt->children)
1782                 gtk_tree_model_filter_free_level (filter, elt->children,
1783                                                   TRUE, TRUE, TRUE);
1784             }
1785           else
1786             {
1787               /* In this case, we want to keep the level with the first
1788                * node pulled in to monitor for signals.
1789                */
1790               if (elt->children)
1791                 gtk_tree_model_filter_prune_level (filter, elt->children);
1792             }
1793         }
1794
1795       if (!parent || orig_level_ext_ref_count > 0)
1796         gtk_tree_model_row_deleted (GTK_TREE_MODEL (filter), path);
1797     }
1798
1799   gtk_tree_path_free (path);
1800
1801   if (emit_child_toggled && parent->ext_ref_count > 0)
1802     {
1803       GtkTreeIter piter;
1804       GtkTreePath *ppath;
1805
1806       piter.stamp = filter->priv->stamp;
1807       piter.user_data = parent_level;
1808       piter.user_data2 = parent;
1809
1810       ppath = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &piter);
1811
1812       gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (filter),
1813                                             ppath, &piter);
1814       gtk_tree_path_free (ppath);
1815     }
1816 }
1817
1818 /* This function is called after the given node has become visible.
1819  * When the node has children, we should build the level and
1820  * take a reference on the first child.
1821  */
1822 static void
1823 gtk_tree_model_filter_update_children (GtkTreeModelFilter *filter,
1824                                        FilterLevel        *level,
1825                                        FilterElt          *elt)
1826 {
1827   GtkTreeIter c_iter;
1828   GtkTreeIter iter;
1829
1830   if (!elt->visible_siter)
1831     return;
1832
1833   iter.stamp = filter->priv->stamp;
1834   iter.user_data = level;
1835   iter.user_data2 = elt;
1836
1837   gtk_tree_model_filter_convert_iter_to_child_iter (filter, &c_iter, &iter);
1838
1839   if ((!level->parent_level || level->parent_level->ext_ref_count > 0) &&
1840       gtk_tree_model_iter_has_child (filter->priv->child_model, &c_iter))
1841     {
1842       if (!elt->children)
1843         gtk_tree_model_filter_build_level (filter, level, elt, FALSE);
1844
1845       if (elt->ext_ref_count > 0 && elt->children &&
1846           g_sequence_get_length (elt->children->seq))
1847         {
1848           GtkTreePath *path;
1849           path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
1850           gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (filter),
1851                                                 path,
1852                                                 &iter);
1853           if (path)
1854             gtk_tree_path_free (path);
1855         }
1856     }
1857 }
1858
1859 /* Path is relative to the child model (this is on search on elt offset)
1860  * but with the virtual root already removed if necesssary.
1861  */
1862 static gboolean
1863 find_elt_with_offset (GtkTreeModelFilter *filter,
1864                       GtkTreePath        *path,
1865                       FilterLevel       **level_,
1866                       FilterElt         **elt_)
1867 {
1868   int i = 0;
1869   FilterLevel *level;
1870   FilterLevel *parent_level = NULL;
1871   FilterElt *elt = NULL;
1872
1873   level = FILTER_LEVEL (filter->priv->root);
1874
1875   while (i < gtk_tree_path_get_depth (path))
1876     {
1877       if (!level)
1878         return FALSE;
1879
1880       elt = lookup_elt_with_offset (level->seq,
1881                                     gtk_tree_path_get_indices (path)[i],
1882                                     NULL);
1883
1884       if (!elt)
1885         return FALSE;
1886
1887       parent_level = level;
1888       level = elt->children;
1889       i++;
1890     }
1891
1892   if (level_)
1893     *level_ = parent_level;
1894
1895   if (elt_)
1896     *elt_ = elt;
1897
1898   return TRUE;
1899 }
1900
1901 /* TreeModel signals */
1902 static void
1903 gtk_tree_model_filter_emit_row_inserted_for_path (GtkTreeModelFilter *filter,
1904                                                   GtkTreeModel       *c_model,
1905                                                   GtkTreePath        *c_path,
1906                                                   GtkTreeIter        *c_iter)
1907 {
1908   FilterLevel *level;
1909   FilterElt *elt;
1910   GtkTreePath *path;
1911   GtkTreeIter iter, children;
1912   gboolean signals_emitted = FALSE;
1913
1914   if (!filter->priv->root)
1915     {
1916       /* The root level has not been exposed to the view yet, so we
1917        * need to emit signals for any node that is being inserted.
1918        */
1919       gtk_tree_model_filter_build_level (filter, NULL, NULL, TRUE);
1920
1921       /* Check if the root level was built.  Then child levels
1922        * that matter have also been built (due to update_children,
1923        * which triggers iter_n_children).
1924        */
1925       if (filter->priv->root &&
1926           g_sequence_get_length (FILTER_LEVEL (filter->priv->root)->visible_seq) > 0)
1927         signals_emitted = TRUE;
1928     }
1929
1930   gtk_tree_model_filter_increment_stamp (filter);
1931
1932   /* We need to disallow to build new levels, because we are then pulling
1933    * in a child in an invisible level.  We only want to find path if it
1934    * is in a visible level (and thus has a parent that is visible).
1935    */
1936   path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
1937                                                                 c_path,
1938                                                                 FALSE,
1939                                                                 TRUE);
1940
1941   if (!path)
1942     /* parent is probably being filtered out */
1943     return;
1944
1945   gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (filter), &iter, path);
1946
1947   level = FILTER_LEVEL (iter.user_data);
1948   elt = FILTER_ELT (iter.user_data2);
1949
1950   /* Make sure elt is visible.  elt can already be visible in case
1951    * it was pulled in above, so avoid inserted it into visible_seq twice.
1952    */
1953   if (!elt->visible_siter)
1954     {
1955       elt->visible_siter = g_sequence_insert_sorted (level->visible_seq,
1956                                                      elt, filter_elt_cmp,
1957                                                      NULL);
1958     }
1959
1960   /* Check whether the node and all of its parents are visible */
1961   if (gtk_tree_model_filter_elt_is_visible_in_target (level, elt))
1962     {
1963       /* visibility changed -- reget path */
1964       gtk_tree_path_free (path);
1965       path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
1966
1967       if (!signals_emitted &&
1968           (!level->parent_level || level->ext_ref_count > 0))
1969         gtk_tree_model_row_inserted (GTK_TREE_MODEL (filter), path, &iter);
1970
1971       if (level->parent_level && level->parent_elt->ext_ref_count > 0 &&
1972           g_sequence_get_length (level->visible_seq) == 1)
1973         {
1974           /* We know that this is the first visible node in this level, so
1975            * we need to emit row-has-child-toggled on the parent.  This
1976            * does not apply to the root level.
1977            */
1978
1979           gtk_tree_path_up (path);
1980           gtk_tree_model_get_iter (GTK_TREE_MODEL (filter), &iter, path);
1981
1982           gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (filter),
1983                                                 path,
1984                                                 &iter);
1985         }
1986
1987       if (!signals_emitted
1988           && gtk_tree_model_iter_children (c_model, &children, c_iter))
1989         gtk_tree_model_filter_update_children (filter, level, elt);
1990     }
1991
1992   gtk_tree_path_free (path);
1993 }
1994
1995 static void
1996 gtk_tree_model_filter_row_changed (GtkTreeModel *c_model,
1997                                    GtkTreePath  *c_path,
1998                                    GtkTreeIter  *c_iter,
1999                                    gpointer      data)
2000 {
2001   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (data);
2002   GtkTreeIter iter;
2003   GtkTreeIter children;
2004   GtkTreeIter real_c_iter;
2005   GtkTreePath *path = NULL;
2006   GtkTreePath *real_path = NULL;
2007
2008   FilterElt *elt;
2009   FilterLevel *level;
2010
2011   gboolean requested_state;
2012   gboolean current_state;
2013   gboolean free_c_path = FALSE;
2014
2015   g_return_if_fail (c_path != NULL || c_iter != NULL);
2016
2017   if (!c_path)
2018     {
2019       c_path = gtk_tree_model_get_path (c_model, c_iter);
2020       free_c_path = TRUE;
2021     }
2022
2023   if (filter->priv->virtual_root)
2024     real_path = gtk_tree_model_filter_remove_root (c_path,
2025                                                    filter->priv->virtual_root);
2026   else
2027     real_path = gtk_tree_path_copy (c_path);
2028
2029   if (c_iter)
2030     real_c_iter = *c_iter;
2031   else
2032     gtk_tree_model_get_iter (c_model, &real_c_iter, c_path);
2033
2034   /* is this node above the virtual root? */
2035   if (filter->priv->virtual_root &&
2036       (gtk_tree_path_get_depth (filter->priv->virtual_root)
2037           >= gtk_tree_path_get_depth (c_path)))
2038     goto done;
2039
2040   /* what's the requested state? */
2041   requested_state = gtk_tree_model_filter_visible (filter, &real_c_iter);
2042
2043   /* now, let's see whether the item is there */
2044   path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
2045                                                                 c_path,
2046                                                                 FALSE,
2047                                                                 FALSE);
2048
2049   if (path)
2050     {
2051       gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (filter),
2052                                            &iter, path);
2053       current_state = FILTER_ELT (iter.user_data2)->visible_siter != NULL;
2054     }
2055   else
2056     current_state = FALSE;
2057
2058   if (current_state == FALSE && requested_state == FALSE)
2059     /* no changes required */
2060     goto done;
2061
2062   if (current_state == TRUE && requested_state == FALSE)
2063     {
2064       gtk_tree_model_filter_remove_elt_from_level (filter,
2065                                                    FILTER_LEVEL (iter.user_data),
2066                                                    FILTER_ELT (iter.user_data2));
2067
2068       if (real_path)
2069         gtk_tree_model_filter_check_ancestors (filter, real_path);
2070
2071       goto done;
2072     }
2073
2074   if (current_state == TRUE && requested_state == TRUE)
2075     {
2076       /* propagate the signal; also get a path taking only visible
2077        * nodes into account.
2078        */
2079       gtk_tree_path_free (path);
2080       path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
2081
2082       level = FILTER_LEVEL (iter.user_data);
2083       elt = FILTER_ELT (iter.user_data2);
2084
2085       if (gtk_tree_model_filter_elt_is_visible_in_target (level, elt))
2086         {
2087           if (level->ext_ref_count > 0)
2088             gtk_tree_model_row_changed (GTK_TREE_MODEL (filter), path, &iter);
2089
2090           /* and update the children */
2091           if (gtk_tree_model_iter_children (c_model, &children, &real_c_iter))
2092             gtk_tree_model_filter_update_children (filter, level, elt);
2093         }
2094
2095       if (real_path)
2096         gtk_tree_model_filter_check_ancestors (filter, real_path);
2097
2098       goto done;
2099     }
2100
2101   /* only current == FALSE and requested == TRUE is left,
2102    * pull in the child
2103    */
2104   g_return_if_fail (current_state == FALSE && requested_state == TRUE);
2105
2106   if (real_path)
2107     gtk_tree_model_filter_check_ancestors (filter, real_path);
2108
2109   gtk_tree_model_filter_emit_row_inserted_for_path (filter, c_model,
2110                                                     c_path, c_iter);
2111
2112 done:
2113   if (path)
2114     gtk_tree_path_free (path);
2115
2116   if (real_path)
2117     gtk_tree_path_free (real_path);
2118
2119   if (free_c_path)
2120     gtk_tree_path_free (c_path);
2121 }
2122
2123 static void
2124 gtk_tree_model_filter_row_inserted (GtkTreeModel *c_model,
2125                                     GtkTreePath  *c_path,
2126                                     GtkTreeIter  *c_iter,
2127                                     gpointer      data)
2128 {
2129   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (data);
2130   GtkTreePath *real_path = NULL;
2131
2132   GtkTreeIter real_c_iter;
2133
2134   FilterElt *elt = NULL;
2135   FilterLevel *level = NULL;
2136   FilterLevel *parent_level = NULL;
2137   GSequenceIter *siter;
2138   FilterElt dummy;
2139
2140   gint i = 0, offset;
2141
2142   gboolean free_c_path = FALSE;
2143   gboolean emit_row_inserted = FALSE;
2144
2145   g_return_if_fail (c_path != NULL || c_iter != NULL);
2146
2147   if (!c_path)
2148     {
2149       c_path = gtk_tree_model_get_path (c_model, c_iter);
2150       free_c_path = TRUE;
2151     }
2152
2153   if (c_iter)
2154     real_c_iter = *c_iter;
2155   else
2156     gtk_tree_model_get_iter (c_model, &real_c_iter, c_path);
2157
2158   /* the row has already been inserted. so we need to fixup the
2159    * virtual root here first
2160    */
2161   if (filter->priv->virtual_root)
2162     {
2163       if (gtk_tree_path_get_depth (filter->priv->virtual_root) >=
2164           gtk_tree_path_get_depth (c_path))
2165         {
2166           gint level;
2167           gint *v_indices, *c_indices;
2168           gboolean common_prefix = TRUE;
2169
2170           level = gtk_tree_path_get_depth (c_path) - 1;
2171           v_indices = gtk_tree_path_get_indices (filter->priv->virtual_root);
2172           c_indices = gtk_tree_path_get_indices (c_path);
2173
2174           for (i = 0; i < level; i++)
2175             if (v_indices[i] != c_indices[i])
2176               {
2177                 common_prefix = FALSE;
2178                 break;
2179               }
2180
2181           if (common_prefix && v_indices[level] >= c_indices[level])
2182             (v_indices[level])++;
2183         }
2184     }
2185
2186   /* subtract virtual root if necessary */
2187   if (filter->priv->virtual_root)
2188     {
2189       real_path = gtk_tree_model_filter_remove_root (c_path,
2190                                                      filter->priv->virtual_root);
2191       /* not our child */
2192       if (!real_path)
2193         goto done;
2194     }
2195   else
2196     real_path = gtk_tree_path_copy (c_path);
2197
2198   if (!filter->priv->root)
2199     {
2200       /* The root level has not been exposed to the view yet, so we
2201        * need to emit signals for any node that is being inserted.
2202        */
2203       gtk_tree_model_filter_build_level (filter, NULL, NULL, TRUE);
2204
2205       /* Check if the root level was built.  Then child levels
2206        * that matter have also been built (due to update_children,
2207        * which triggers iter_n_children).
2208        */
2209       if (filter->priv->root)
2210         {
2211           emit_row_inserted = FALSE;
2212           goto done;
2213         }
2214     }
2215
2216   if (gtk_tree_path_get_depth (real_path) - 1 >= 1)
2217     {
2218       gboolean found = FALSE;
2219       GtkTreePath *parent = gtk_tree_path_copy (real_path);
2220       gtk_tree_path_up (parent);
2221
2222       found = find_elt_with_offset (filter, parent, &parent_level, &elt);
2223
2224       gtk_tree_path_free (parent);
2225
2226       if (!found)
2227         /* Parent is not in the cache and probably being filtered out */
2228         goto done;
2229
2230       level = elt->children;
2231     }
2232   else
2233     level = FILTER_LEVEL (filter->priv->root);
2234
2235   if (!level)
2236     {
2237       if (elt && elt->visible_siter)
2238         {
2239           /* The level in which the new node should be inserted does not
2240            * exist, but the parent, elt, does.  If elt is visible, emit
2241            * row-has-child-toggled.
2242            */
2243           GtkTreePath *tmppath;
2244           GtkTreeIter  tmpiter;
2245
2246           tmpiter.stamp = filter->priv->stamp;
2247           tmpiter.user_data = parent_level;
2248           tmpiter.user_data2 = elt;
2249
2250           tmppath = gtk_tree_model_get_path (GTK_TREE_MODEL (filter),
2251                                              &tmpiter);
2252
2253           if (tmppath)
2254             {
2255               gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (filter),
2256                                                     tmppath, &tmpiter);
2257               gtk_tree_path_free (tmppath);
2258             }
2259         }
2260       goto done;
2261     }
2262
2263   /* let's try to insert the value */
2264   offset = gtk_tree_path_get_indices (real_path)[gtk_tree_path_get_depth (real_path) - 1];
2265
2266   /* update the offsets, yes if we didn't insert the node above, there will
2267    * be a gap here. This will be filled with the node (via fetch_child) when
2268    * it becomes visible
2269    */
2270   dummy.offset = offset;
2271   siter = g_sequence_search (level->seq, &dummy, filter_elt_cmp, NULL);
2272   siter = g_sequence_iter_prev (siter);
2273   g_sequence_foreach_range (siter, g_sequence_get_end_iter (level->seq),
2274                             increase_offset_iter, GINT_TO_POINTER (offset));
2275
2276   /* only insert when visible */
2277   if (gtk_tree_model_filter_visible (filter, &real_c_iter))
2278     {
2279       FilterElt *felt;
2280
2281       felt = gtk_tree_model_filter_insert_elt_in_level (filter,
2282                                                         &real_c_iter,
2283                                                         level, offset,
2284                                                         &i);
2285
2286       /* insert_elt_in_level defaults to FALSE */
2287       felt->visible_siter = g_sequence_insert_sorted (level->visible_seq,
2288                                                       felt,
2289                                                       filter_elt_cmp, NULL);
2290       emit_row_inserted = TRUE;
2291     }
2292
2293 done:
2294   if (real_path)
2295     gtk_tree_model_filter_check_ancestors (filter, real_path);
2296
2297   if (emit_row_inserted)
2298     gtk_tree_model_filter_emit_row_inserted_for_path (filter, c_model,
2299                                                       c_path, c_iter);
2300
2301   if (real_path)
2302     gtk_tree_path_free (real_path);
2303
2304   if (free_c_path)
2305     gtk_tree_path_free (c_path);
2306 }
2307
2308 static void
2309 gtk_tree_model_filter_row_has_child_toggled (GtkTreeModel *c_model,
2310                                              GtkTreePath  *c_path,
2311                                              GtkTreeIter  *c_iter,
2312                                              gpointer      data)
2313 {
2314   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (data);
2315   GtkTreePath *path;
2316   GtkTreeIter iter;
2317   FilterLevel *level;
2318   FilterElt *elt;
2319   gboolean requested_state;
2320
2321   g_return_if_fail (c_path != NULL && c_iter != NULL);
2322
2323   /* If we get row-has-child-toggled on the virtual root, and there is
2324    * no root level; try to build it now.
2325    */
2326   if (filter->priv->virtual_root && !filter->priv->root
2327       && !gtk_tree_path_compare (c_path, filter->priv->virtual_root))
2328     {
2329       gtk_tree_model_filter_build_level (filter, NULL, NULL, TRUE);
2330       return;
2331     }
2332
2333   /* For all other levels, there is a chance that the visibility state
2334    * of the parent has changed now.
2335    */
2336
2337   path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
2338                                                                 c_path,
2339                                                                 FALSE,
2340                                                                 TRUE);
2341   if (!path)
2342     return;
2343
2344   gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (data), &iter, path);
2345
2346   level = FILTER_LEVEL (iter.user_data);
2347   elt = FILTER_ELT (iter.user_data2);
2348
2349   gtk_tree_path_free (path);
2350
2351   requested_state = gtk_tree_model_filter_visible (filter, c_iter);
2352
2353   if (!elt->visible_siter && !requested_state)
2354     {
2355       /* The parent node currently is not visible and will not become
2356        * visible, so we will not pass on the row-has-child-toggled event.
2357        */
2358       return;
2359     }
2360   else if (elt->visible_siter && !requested_state)
2361     {
2362       /* The node is no longer visible, so it has to be removed.
2363        * _remove_elt_from_level() takes care of emitting row-has-child-toggled
2364        * when required.
2365        */
2366       gtk_tree_model_filter_remove_elt_from_level (filter, level, elt);
2367
2368       return;
2369     }
2370   else if (!elt->visible_siter && requested_state)
2371     {
2372       elt->visible_siter = g_sequence_insert_sorted (level->visible_seq,
2373                                                      elt, filter_elt_cmp,
2374                                                      NULL);
2375
2376       /* Only insert if the parent is visible in the target */
2377       if (gtk_tree_model_filter_elt_is_visible_in_target (level, elt))
2378         {
2379           path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
2380           gtk_tree_model_row_inserted (GTK_TREE_MODEL (filter), path, &iter);
2381           gtk_tree_path_free (path);
2382
2383           /* We do not update children now, because that will happen
2384            * below.
2385            */
2386         }
2387     }
2388   /* For the remaining possibility, elt->visible && requested_state
2389    * no action is required.
2390    */
2391
2392   /* If this node is referenced and has children, build the level so we
2393    * can monitor it for changes.
2394    */
2395   if (elt->ref_count > 1 && !elt->children &&
2396       gtk_tree_model_iter_has_child (c_model, c_iter))
2397     gtk_tree_model_filter_build_level (filter, level, elt, FALSE);
2398
2399   /* get a path taking only visible nodes into account */
2400   path = gtk_tree_model_get_path (GTK_TREE_MODEL (data), &iter);
2401   gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
2402   gtk_tree_path_free (path);
2403 }
2404
2405 static void
2406 gtk_tree_model_filter_virtual_root_deleted (GtkTreeModelFilter *filter,
2407                                             GtkTreePath        *c_path)
2408 {
2409   gint i, nodes;
2410   GtkTreePath *path;
2411   FilterLevel *level = FILTER_LEVEL (filter->priv->root);
2412
2413   /* The virtual root (or one of its ancestors) has been deleted.  This
2414    * means that all content for our model is now gone.  We deal with
2415    * this by removing everything in the filter model: we just iterate
2416    * over the root level and emit a row-deleted for each FilterElt.
2417    * (FIXME: Should we emit row-deleted for child nodes as well? This
2418    * has never been fully clear in TreeModel).
2419    */
2420
2421   /* We unref the path of the virtual root, up to and not including the
2422    * deleted node which can no longer be unreffed.
2423    */
2424   gtk_tree_model_filter_unref_path (filter, filter->priv->virtual_root,
2425                                     gtk_tree_path_get_depth (c_path) - 1);
2426   filter->priv->virtual_root_deleted = TRUE;
2427
2428   if (!level)
2429     return;
2430
2431   nodes = g_sequence_get_length (level->visible_seq);
2432
2433   /* We should not propagate the unref here.  An unref for any of these
2434    * nodes will fail, since the respective nodes in the child model are
2435    * no longer there.
2436    */
2437   gtk_tree_model_filter_free_level (filter, filter->priv->root, FALSE, TRUE, FALSE);
2438
2439   gtk_tree_model_filter_increment_stamp (filter);
2440
2441   path = gtk_tree_path_new ();
2442   gtk_tree_path_append_index (path, 0);
2443
2444   for (i = 0; i < nodes; i++)
2445     gtk_tree_model_row_deleted (GTK_TREE_MODEL (filter), path);
2446
2447   gtk_tree_path_free (path);
2448 }
2449
2450 static void
2451 gtk_tree_model_filter_adjust_virtual_root (GtkTreeModelFilter *filter,
2452                                            GtkTreePath        *c_path)
2453 {
2454   gint i;
2455   gint level;
2456   gint *v_indices, *c_indices;
2457   gboolean common_prefix = TRUE;
2458
2459   level = gtk_tree_path_get_depth (c_path) - 1;
2460   v_indices = gtk_tree_path_get_indices (filter->priv->virtual_root);
2461   c_indices = gtk_tree_path_get_indices (c_path);
2462
2463   for (i = 0; i < level; i++)
2464     if (v_indices[i] != c_indices[i])
2465       {
2466         common_prefix = FALSE;
2467         break;
2468       }
2469
2470   if (common_prefix && v_indices[level] > c_indices[level])
2471     (v_indices[level])--;
2472 }
2473
2474 static void
2475 gtk_tree_model_filter_row_deleted_invisible_node (GtkTreeModelFilter *filter,
2476                                                   GtkTreePath        *c_path)
2477 {
2478   int offset;
2479   GtkTreePath *real_path;
2480   FilterLevel *level;
2481   FilterElt *elt;
2482   FilterElt dummy;
2483   GSequenceIter *siter;
2484
2485   /* The node deleted in the child model is not visible in the
2486    * filter model.  We will not emit a signal, just fixup the offsets
2487    * of the other nodes.
2488    */
2489
2490   if (!filter->priv->root)
2491     return;
2492
2493   level = FILTER_LEVEL (filter->priv->root);
2494
2495   /* subtract vroot if necessary */
2496   if (filter->priv->virtual_root)
2497     {
2498       real_path = gtk_tree_model_filter_remove_root (c_path,
2499                                                      filter->priv->virtual_root);
2500       /* we don't handle this */
2501       if (!real_path)
2502         return;
2503     }
2504   else
2505     real_path = gtk_tree_path_copy (c_path);
2506
2507   if (gtk_tree_path_get_depth (real_path) - 1 >= 1)
2508     {
2509       gboolean found = FALSE;
2510       GtkTreePath *parent = gtk_tree_path_copy (real_path);
2511       gtk_tree_path_up (parent);
2512
2513       found = find_elt_with_offset (filter, parent, &level, &elt);
2514
2515       gtk_tree_path_free (parent);
2516
2517       if (!found)
2518         {
2519           /* parent is filtered out, so no level */
2520           gtk_tree_path_free (real_path);
2521           return;
2522         }
2523
2524       level = elt->children;
2525     }
2526
2527   offset = gtk_tree_path_get_indices (real_path)[gtk_tree_path_get_depth (real_path) - 1];
2528   gtk_tree_path_free (real_path);
2529
2530   if (!level)
2531     return;
2532
2533   /* decrease offset of all nodes following the deleted node */
2534   dummy.offset = offset;
2535   siter = g_sequence_search (level->seq, &dummy, filter_elt_cmp, NULL);
2536   g_sequence_foreach_range (siter, g_sequence_get_end_iter (level->seq),
2537                             decrease_offset_iter, GINT_TO_POINTER (offset));
2538 }
2539
2540 static void
2541 gtk_tree_model_filter_row_deleted (GtkTreeModel *c_model,
2542                                    GtkTreePath  *c_path,
2543                                    gpointer      data)
2544 {
2545   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (data);
2546   GtkTreePath *path;
2547   GtkTreeIter iter;
2548   FilterElt *elt, *parent_elt = NULL;
2549   FilterLevel *level, *parent_level = NULL;
2550   GSequenceIter *siter;
2551   gboolean emit_child_toggled = FALSE;
2552   gboolean emit_row_deleted = FALSE;
2553   gint offset;
2554   gint orig_level_ext_ref_count;
2555
2556   g_return_if_fail (c_path != NULL);
2557
2558   /* special case the deletion of an ancestor of the virtual root */
2559   if (filter->priv->virtual_root &&
2560       (gtk_tree_path_is_ancestor (c_path, filter->priv->virtual_root) ||
2561        !gtk_tree_path_compare (c_path, filter->priv->virtual_root)))
2562     {
2563       gtk_tree_model_filter_virtual_root_deleted (filter, c_path);
2564       return;
2565     }
2566
2567   /* adjust the virtual root for the deleted row */
2568   if (filter->priv->virtual_root &&
2569       gtk_tree_path_get_depth (filter->priv->virtual_root) >=
2570       gtk_tree_path_get_depth (c_path))
2571     gtk_tree_model_filter_adjust_virtual_root (filter, c_path);
2572
2573   path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
2574                                                                 c_path,
2575                                                                 FALSE,
2576                                                                 FALSE);
2577
2578   if (!path)
2579     {
2580       gtk_tree_model_filter_row_deleted_invisible_node (filter, c_path);
2581       return;
2582     }
2583
2584   /* a node was deleted, which was in our cache */
2585   gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (data), &iter, path);
2586
2587   level = FILTER_LEVEL (iter.user_data);
2588   elt = FILTER_ELT (iter.user_data2);
2589   offset = elt->offset;
2590   orig_level_ext_ref_count = level->ext_ref_count;
2591
2592   if (elt->visible_siter)
2593     {
2594       /* get a path taking only visible nodes into account */
2595       gtk_tree_path_free (path);
2596       path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
2597
2598       if (g_sequence_get_length (level->visible_seq) == 1)
2599         {
2600           emit_child_toggled = TRUE;
2601           parent_level = level->parent_level;
2602           parent_elt = level->parent_elt;
2603         }
2604
2605       emit_row_deleted = TRUE;
2606     }
2607
2608   /* Release the references on this node, without propagation because
2609    * the node does not exist anymore in the child model.  The filter
2610    * model's references on the node in case of level->parent or use
2611    * of a virtual root are automatically destroyed by the child model.
2612    */
2613   while (elt->ext_ref_count > 0)
2614     gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (data), &iter,
2615                                            TRUE, FALSE);
2616
2617   if (g_sequence_get_length (level->seq) == 1)
2618     {
2619       if (elt->children)
2620         /* If this last node has children, then the recursion in free_level
2621          * will release this reference.
2622          */
2623         while (elt->ref_count > 1)
2624           gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (data), &iter,
2625                                                  FALSE, FALSE);
2626       else
2627         while (elt->ref_count > 0)
2628           gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (data), &iter,
2629                                                  FALSE, FALSE);
2630
2631       /* kill level */
2632       gtk_tree_model_filter_free_level (filter, level, FALSE, TRUE, FALSE);
2633     }
2634   else
2635     {
2636       GSequenceIter *tmp;
2637       gboolean is_first;
2638
2639       /* Release last references, if needed */
2640       while (elt->ref_count > 0)
2641         gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (data), &iter,
2642                                                FALSE, FALSE);
2643
2644       lookup_elt_with_offset (level->seq, elt->offset, &siter);
2645       is_first = g_sequence_get_begin_iter (level->seq) == siter;
2646
2647       /* remove the row */
2648       g_sequence_remove (elt->visible_siter);
2649       tmp = g_sequence_iter_next (siter);
2650       g_sequence_remove (siter);
2651       g_sequence_foreach_range (tmp, g_sequence_get_end_iter (level->seq),
2652                                 decrease_offset_iter, GINT_TO_POINTER (offset));
2653
2654       /* Take a reference on the new first node.  The first node previously
2655        * keeping this reference has been removed above.
2656        */
2657       if (is_first)
2658         {
2659           GtkTreeIter f_iter;
2660
2661           f_iter.stamp = filter->priv->stamp;
2662           f_iter.user_data = level;
2663           f_iter.user_data2 = g_sequence_get (g_sequence_get_begin_iter (level->seq));
2664
2665           gtk_tree_model_filter_real_ref_node (GTK_TREE_MODEL (filter),
2666                                                &f_iter, FALSE);
2667         }
2668     }
2669
2670   if (emit_row_deleted)
2671     {
2672       /* emit row_deleted */
2673       gtk_tree_model_filter_increment_stamp (filter);
2674
2675       if (!parent_elt || orig_level_ext_ref_count > 0)
2676         gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
2677     }
2678
2679   if (emit_child_toggled && parent_level)
2680     {
2681       GtkTreeIter iter2;
2682       GtkTreePath *path2;
2683
2684       iter2.stamp = filter->priv->stamp;
2685       iter2.user_data = parent_level;
2686       iter2.user_data2 = parent_elt;
2687
2688       /* We set in_row_deleted to TRUE to avoid a level build triggered
2689        * by row-has-child-toggled (parent model could call iter_has_child
2690        * for example).
2691        */
2692       filter->priv->in_row_deleted = TRUE;
2693       path2 = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter2);
2694       gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (filter),
2695                                             path2, &iter2);
2696       gtk_tree_path_free (path2);
2697       filter->priv->in_row_deleted = FALSE;
2698     }
2699
2700   if (filter->priv->virtual_root)
2701     {
2702       GtkTreePath *real_path;
2703
2704       real_path = gtk_tree_model_filter_remove_root (c_path,
2705                                                      filter->priv->root);
2706       if (real_path)
2707         {
2708           gtk_tree_model_filter_check_ancestors (filter, real_path);
2709           gtk_tree_path_free (real_path);
2710         }
2711     }
2712   else
2713     gtk_tree_model_filter_check_ancestors (filter, c_path);
2714
2715   gtk_tree_path_free (path);
2716 }
2717
2718 static void
2719 gtk_tree_model_filter_rows_reordered (GtkTreeModel *c_model,
2720                                       GtkTreePath  *c_path,
2721                                       GtkTreeIter  *c_iter,
2722                                       gint         *new_order,
2723                                       gpointer      data)
2724 {
2725   FilterElt *elt;
2726   FilterLevel *level;
2727   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (data);
2728
2729   GtkTreePath *path;
2730   GtkTreeIter iter;
2731
2732   GSequence *tmp_seq;
2733   GSequenceIter *tmp_end_iter;
2734   GSequenceIter *old_first_siter = NULL;
2735   gint *tmp_array;
2736   gint i, elt_count;
2737   gint length;
2738
2739   g_return_if_fail (new_order != NULL);
2740
2741   if (c_path == NULL || gtk_tree_path_get_depth (c_path) == 0)
2742     {
2743       length = gtk_tree_model_iter_n_children (c_model, NULL);
2744
2745       if (filter->priv->virtual_root)
2746         {
2747           gint new_pos = -1;
2748
2749           /* reorder root level of path */
2750           for (i = 0; i < length; i++)
2751             if (new_order[i] == gtk_tree_path_get_indices (filter->priv->virtual_root)[0])
2752               new_pos = i;
2753
2754           if (new_pos < 0)
2755             return;
2756
2757           gtk_tree_path_get_indices (filter->priv->virtual_root)[0] = new_pos;
2758           return;
2759         }
2760
2761       path = gtk_tree_path_new ();
2762       level = FILTER_LEVEL (filter->priv->root);
2763     }
2764   else
2765     {
2766       GtkTreeIter child_iter;
2767
2768       /* virtual root anchor reordering */
2769       if (filter->priv->virtual_root &&
2770           gtk_tree_path_is_ancestor (c_path, filter->priv->virtual_root))
2771         {
2772           gint new_pos = -1;
2773           gint length;
2774           gint level;
2775           GtkTreeIter real_c_iter;
2776
2777           level = gtk_tree_path_get_depth (c_path);
2778
2779           if (c_iter)
2780             real_c_iter = *c_iter;
2781           else
2782             gtk_tree_model_get_iter (c_model, &real_c_iter, c_path);
2783
2784           length = gtk_tree_model_iter_n_children (c_model, &real_c_iter);
2785
2786           for (i = 0; i < length; i++)
2787             if (new_order[i] == gtk_tree_path_get_indices (filter->priv->virtual_root)[level])
2788               new_pos = i;
2789
2790           if (new_pos < 0)
2791             return;
2792
2793           gtk_tree_path_get_indices (filter->priv->virtual_root)[level] = new_pos;
2794           return;
2795         }
2796
2797       path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
2798                                                                     c_path,
2799                                                                     FALSE,
2800                                                                     FALSE);
2801
2802       if (!path && filter->priv->virtual_root &&
2803           gtk_tree_path_compare (c_path, filter->priv->virtual_root))
2804         return;
2805
2806       if (!path && !filter->priv->virtual_root)
2807         return;
2808
2809       if (!path)
2810         {
2811           /* root level mode */
2812           if (!c_iter)
2813             gtk_tree_model_get_iter (c_model, c_iter, c_path);
2814           length = gtk_tree_model_iter_n_children (c_model, c_iter);
2815           path = gtk_tree_path_new ();
2816           level = FILTER_LEVEL (filter->priv->root);
2817         }
2818       else
2819         {
2820           gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (data),
2821                                                &iter, path);
2822
2823           elt = FILTER_ELT (iter.user_data2);
2824
2825           if (!elt->children)
2826             {
2827               gtk_tree_path_free (path);
2828               return;
2829             }
2830
2831           level = elt->children;
2832
2833           gtk_tree_model_filter_convert_iter_to_child_iter (GTK_TREE_MODEL_FILTER (filter), &child_iter, &iter);
2834           length = gtk_tree_model_iter_n_children (c_model, &child_iter);
2835         }
2836     }
2837
2838   if (!level || g_sequence_get_length (level->seq) < 1)
2839     {
2840       gtk_tree_path_free (path);
2841       return;
2842     }
2843
2844   /* NOTE: we do not bail out here if level->seq->len < 2 like
2845    * GtkTreeModelSort does. This because we do some special tricky
2846    * reordering.
2847    */
2848
2849   tmp_seq = g_sequence_new (filter_elt_free);
2850   tmp_end_iter = g_sequence_get_end_iter (tmp_seq);
2851   tmp_array = g_new (gint, g_sequence_get_length (level->visible_seq));
2852   elt_count = 0;
2853
2854   old_first_siter = g_sequence_get_iter_at_pos (level->seq, 0);
2855
2856   for (i = 0; i < length; i++)
2857     {
2858       FilterElt *elt;
2859       GSequenceIter *siter;
2860
2861       elt = lookup_elt_with_offset (level->seq, new_order[i], &siter);
2862       if (elt == NULL)
2863         continue;
2864
2865       /* Only for visible items an entry should be present in the order array
2866        * to be emitted.
2867        */
2868       if (elt->visible_siter)
2869         tmp_array[elt_count++] = g_sequence_iter_get_position (elt->visible_siter);
2870
2871       /* Steal elt from level->seq and append it to tmp_seq */
2872       g_sequence_move (siter, tmp_end_iter);
2873       elt->offset = i;
2874     }
2875
2876   g_warn_if_fail (g_sequence_get_length (level->seq) == 0);
2877   g_sequence_free (level->seq);
2878   level->seq = tmp_seq;
2879   g_sequence_sort (level->visible_seq, filter_elt_cmp, NULL);
2880
2881   /* Transfer the reference from the old item at position 0 to the
2882    * new item at position 0, unless the old item at position 0 is also
2883    * at position 0 in the new sequence.
2884    */
2885   if (g_sequence_iter_get_position (old_first_siter) != 0)
2886     gtk_tree_model_filter_level_transfer_first_ref (filter,
2887                                                     level,
2888                                                     old_first_siter,
2889                                                     g_sequence_get_iter_at_pos (level->seq, 0));
2890
2891   /* emit rows_reordered */
2892   if (g_sequence_get_length (level->visible_seq) > 0)
2893     {
2894       if (!gtk_tree_path_get_indices (path))
2895         gtk_tree_model_rows_reordered (GTK_TREE_MODEL (data), path, NULL,
2896                                        tmp_array);
2897       else
2898         {
2899           /* get a path taking only visible nodes into account */
2900           gtk_tree_path_free (path);
2901           path = gtk_tree_model_get_path (GTK_TREE_MODEL (data), &iter);
2902
2903           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (data), path, &iter,
2904                                          tmp_array);
2905         }
2906     }
2907
2908   /* done */
2909   g_free (tmp_array);
2910   gtk_tree_path_free (path);
2911 }
2912
2913 /* TreeModelIface implementation */
2914 static GtkTreeModelFlags
2915 gtk_tree_model_filter_get_flags (GtkTreeModel *model)
2916 {
2917   GtkTreeModelFlags flags;
2918
2919   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), 0);
2920   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL, 0);
2921
2922   flags = gtk_tree_model_get_flags (GTK_TREE_MODEL_FILTER (model)->priv->child_model);
2923
2924   if ((flags & GTK_TREE_MODEL_LIST_ONLY) == GTK_TREE_MODEL_LIST_ONLY)
2925     return GTK_TREE_MODEL_LIST_ONLY;
2926
2927   return 0;
2928 }
2929
2930 static gint
2931 gtk_tree_model_filter_get_n_columns (GtkTreeModel *model)
2932 {
2933   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2934
2935   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), 0);
2936   g_return_val_if_fail (filter->priv->child_model != NULL, 0);
2937
2938   if (filter->priv->child_model == NULL)
2939     return 0;
2940
2941   /* so we can't modify the modify func after this ... */
2942   filter->priv->modify_func_set = TRUE;
2943
2944   if (filter->priv->modify_n_columns > 0)
2945     return filter->priv->modify_n_columns;
2946
2947   return gtk_tree_model_get_n_columns (filter->priv->child_model);
2948 }
2949
2950 static GType
2951 gtk_tree_model_filter_get_column_type (GtkTreeModel *model,
2952                                        gint          index)
2953 {
2954   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2955
2956   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), G_TYPE_INVALID);
2957   g_return_val_if_fail (filter->priv->child_model != NULL, G_TYPE_INVALID);
2958
2959   /* so we can't modify the modify func after this ... */
2960   filter->priv->modify_func_set = TRUE;
2961
2962   if (filter->priv->modify_types)
2963     {
2964       g_return_val_if_fail (index < filter->priv->modify_n_columns, G_TYPE_INVALID);
2965
2966       return filter->priv->modify_types[index];
2967     }
2968
2969   return gtk_tree_model_get_column_type (filter->priv->child_model, index);
2970 }
2971
2972 /* A special case of _get_iter; this function can also get iters which
2973  * are not visible.  These iters should ONLY be passed internally, never
2974  * pass those along with a signal emission.
2975  */
2976 static gboolean
2977 gtk_tree_model_filter_get_iter_full (GtkTreeModel *model,
2978                                      GtkTreeIter  *iter,
2979                                      GtkTreePath  *path)
2980 {
2981   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2982   gint *indices;
2983   FilterLevel *level;
2984   FilterElt *elt;
2985   gint depth, i;
2986   GSequenceIter *siter;
2987
2988   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
2989   g_return_val_if_fail (filter->priv->child_model != NULL, FALSE);
2990
2991   indices = gtk_tree_path_get_indices (path);
2992
2993   if (filter->priv->root == NULL)
2994     gtk_tree_model_filter_build_level (filter, NULL, NULL, FALSE);
2995   level = FILTER_LEVEL (filter->priv->root);
2996
2997   depth = gtk_tree_path_get_depth (path);
2998   if (!depth)
2999     {
3000       iter->stamp = 0;
3001       return FALSE;
3002     }
3003
3004   for (i = 0; i < depth - 1; i++)
3005     {
3006       if (!level || indices[i] >= g_sequence_get_length (level->seq))
3007         {
3008           iter->stamp = 0;
3009           return FALSE;
3010         }
3011
3012       siter = g_sequence_get_iter_at_pos (level->seq, indices[i]);
3013       if (g_sequence_iter_is_end (siter))
3014         {
3015           iter->stamp = 0;
3016           return FALSE;
3017         }
3018
3019       elt = GET_ELT (siter);
3020
3021       if (!elt->children)
3022         gtk_tree_model_filter_build_level (filter, level, elt, FALSE);
3023       level = elt->children;
3024     }
3025
3026   if (!level || indices[i] >= g_sequence_get_length (level->seq))
3027     {
3028       iter->stamp = 0;
3029       return FALSE;
3030     }
3031
3032   iter->stamp = filter->priv->stamp;
3033   iter->user_data = level;
3034
3035   siter = g_sequence_get_iter_at_pos (level->seq, indices[depth - 1]);
3036   if (g_sequence_iter_is_end (siter))
3037     {
3038       iter->stamp = 0;
3039       return FALSE;
3040     }
3041   iter->user_data2 = GET_ELT (siter);
3042
3043   return TRUE;
3044 }
3045
3046 static gboolean
3047 gtk_tree_model_filter_get_iter (GtkTreeModel *model,
3048                                 GtkTreeIter  *iter,
3049                                 GtkTreePath  *path)
3050 {
3051   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
3052   gint *indices;
3053   FilterLevel *level;
3054   FilterElt *elt;
3055   GSequenceIter *siter;
3056   gint depth, i;
3057
3058   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
3059   g_return_val_if_fail (filter->priv->child_model != NULL, FALSE);
3060
3061   indices = gtk_tree_path_get_indices (path);
3062
3063   if (filter->priv->root == NULL)
3064     gtk_tree_model_filter_build_level (filter, NULL, NULL, FALSE);
3065   level = FILTER_LEVEL (filter->priv->root);
3066
3067   depth = gtk_tree_path_get_depth (path);
3068   if (!depth)
3069     {
3070       iter->stamp = 0;
3071       return FALSE;
3072     }
3073
3074   for (i = 0; i < depth - 1; i++)
3075     {
3076       if (!level || indices[i] >= g_sequence_get_length (level->visible_seq))
3077         {
3078           iter->stamp = 0;
3079           return FALSE;
3080         }
3081
3082       siter = g_sequence_get_iter_at_pos (level->visible_seq, indices[i]);
3083       if (g_sequence_iter_is_end (siter))
3084         {
3085           iter->stamp = 0;
3086           return FALSE;
3087         }
3088
3089       elt = GET_ELT (siter);
3090       if (!elt->children)
3091         gtk_tree_model_filter_build_level (filter, level, elt, FALSE);
3092       level = elt->children;
3093     }
3094
3095   if (!level || indices[i] >= g_sequence_get_length (level->visible_seq))
3096     {
3097       iter->stamp = 0;
3098       return FALSE;
3099     }
3100
3101   iter->stamp = filter->priv->stamp;
3102   iter->user_data = level;
3103
3104   siter = g_sequence_get_iter_at_pos (level->visible_seq, indices[depth - 1]);
3105   if (g_sequence_iter_is_end (siter))
3106     {
3107       iter->stamp = 0;
3108       return FALSE;
3109     }
3110   iter->user_data2 = GET_ELT (siter);
3111
3112   return TRUE;
3113 }
3114
3115 static GtkTreePath *
3116 gtk_tree_model_filter_get_path (GtkTreeModel *model,
3117                                 GtkTreeIter  *iter)
3118 {
3119   GtkTreePath *retval;
3120   FilterLevel *level;
3121   FilterElt *elt;
3122
3123   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), NULL);
3124   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL, NULL);
3125   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == iter->stamp, NULL);
3126
3127   level = iter->user_data;
3128   elt = iter->user_data2;
3129
3130   if (!elt->visible_siter)
3131     return NULL;
3132
3133   retval = gtk_tree_path_new ();
3134
3135   while (level)
3136     {
3137       gint index;
3138
3139       index = g_sequence_iter_get_position (elt->visible_siter);
3140       gtk_tree_path_prepend_index (retval, index);
3141
3142       elt = level->parent_elt;
3143       level = level->parent_level;
3144     }
3145
3146   return retval;
3147 }
3148
3149 static void
3150 gtk_tree_model_filter_real_modify (GtkTreeModelFilter *self,
3151                                    GtkTreeModel       *child_model,
3152                                    GtkTreeIter        *iter,
3153                                    GValue             *value,
3154                                    gint                column)
3155 {
3156   if (self->priv->modify_func)
3157     {
3158       g_return_if_fail (column < self->priv->modify_n_columns);
3159
3160       g_value_init (value, self->priv->modify_types[column]);
3161       self->priv->modify_func (GTK_TREE_MODEL (self),
3162                            iter,
3163                            value,
3164                            column,
3165                            self->priv->modify_data);
3166     }
3167   else
3168     {
3169       GtkTreeIter child_iter;
3170
3171       gtk_tree_model_filter_convert_iter_to_child_iter (GTK_TREE_MODEL_FILTER (self),
3172                                                         &child_iter, iter);
3173       gtk_tree_model_get_value (child_model, &child_iter, column, value);
3174     }
3175 }
3176
3177 static void
3178 gtk_tree_model_filter_get_value (GtkTreeModel *model,
3179                                  GtkTreeIter  *iter,
3180                                  gint          column,
3181                                  GValue       *value)
3182 {
3183   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (model);
3184
3185   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (model));
3186   g_return_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL);
3187   g_return_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == iter->stamp);
3188
3189   GTK_TREE_MODEL_FILTER_GET_CLASS (model)->modify (filter,
3190       filter->priv->child_model, iter, value, column);
3191 }
3192
3193 static gboolean
3194 gtk_tree_model_filter_iter_next (GtkTreeModel *model,
3195                                  GtkTreeIter  *iter)
3196 {
3197   FilterLevel *level;
3198   FilterElt *elt;
3199   GSequenceIter *siter;
3200
3201   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
3202   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL, FALSE);
3203   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == iter->stamp, FALSE);
3204
3205   level = iter->user_data;
3206   elt = iter->user_data2;
3207
3208   siter = g_sequence_iter_next (elt->visible_siter);
3209   if (g_sequence_iter_is_end (siter))
3210     {
3211       iter->stamp = 0;
3212       return FALSE;
3213     }
3214
3215   iter->user_data2 = GET_ELT (siter);
3216
3217   return TRUE;
3218 }
3219
3220 static gboolean
3221 gtk_tree_model_filter_iter_previous (GtkTreeModel *model,
3222                                      GtkTreeIter  *iter)
3223 {
3224   FilterElt *elt;
3225   GSequenceIter *siter;
3226
3227   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
3228   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL, FALSE);
3229   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == iter->stamp, FALSE);
3230
3231   elt = iter->user_data2;
3232
3233   siter = g_sequence_iter_prev (elt->visible_siter);
3234   if (g_sequence_iter_is_begin (siter))
3235     {
3236       iter->stamp = 0;
3237       return FALSE;
3238     }
3239
3240   iter->user_data2 = GET_ELT (siter);
3241
3242   return TRUE;
3243 }
3244
3245 static gboolean
3246 gtk_tree_model_filter_iter_children (GtkTreeModel *model,
3247                                      GtkTreeIter  *iter,
3248                                      GtkTreeIter  *parent)
3249 {
3250   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
3251   FilterLevel *level;
3252   GSequenceIter *siter;
3253
3254   iter->stamp = 0;
3255   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
3256   g_return_val_if_fail (filter->priv->child_model != NULL, FALSE);
3257   if (parent)
3258     g_return_val_if_fail (filter->priv->stamp == parent->stamp, FALSE);
3259
3260   if (!parent)
3261     {
3262       if (!filter->priv->root)
3263         gtk_tree_model_filter_build_level (filter, NULL, NULL, FALSE);
3264       if (!filter->priv->root)
3265         return FALSE;
3266
3267       level = filter->priv->root;
3268       siter = g_sequence_get_begin_iter (level->visible_seq);
3269       if (g_sequence_iter_is_end (siter))
3270         {
3271           iter->stamp = 0;
3272           return FALSE;
3273         }
3274
3275       iter->stamp = filter->priv->stamp;
3276       iter->user_data = level;
3277       iter->user_data2 = GET_ELT (siter);
3278
3279       return TRUE;
3280     }
3281   else
3282     {
3283       if (FILTER_ELT (parent->user_data2)->children == NULL)
3284         gtk_tree_model_filter_build_level (filter,
3285                                            FILTER_LEVEL (parent->user_data),
3286                                            FILTER_ELT (parent->user_data2),
3287                                            FALSE);
3288       if (FILTER_ELT (parent->user_data2)->children == NULL)
3289         return FALSE;
3290
3291       level = FILTER_ELT (parent->user_data2)->children;
3292       siter = g_sequence_get_begin_iter (level->visible_seq);
3293       if (g_sequence_iter_is_end (siter))
3294         {
3295           iter->stamp = 0;
3296           return FALSE;
3297         }
3298
3299       iter->stamp = filter->priv->stamp;
3300       iter->user_data = level;
3301       iter->user_data2 = GET_ELT (siter);
3302
3303       return TRUE;
3304     }
3305
3306   iter->stamp = 0;
3307   return FALSE;
3308 }
3309
3310 static gboolean
3311 gtk_tree_model_filter_iter_has_child (GtkTreeModel *model,
3312                                       GtkTreeIter  *iter)
3313 {
3314   GtkTreeIter child_iter;
3315   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
3316   FilterElt *elt;
3317
3318   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
3319   g_return_val_if_fail (filter->priv->child_model != NULL, FALSE);
3320   g_return_val_if_fail (filter->priv->stamp == iter->stamp, FALSE);
3321
3322   filter = GTK_TREE_MODEL_FILTER (model);
3323
3324   gtk_tree_model_filter_convert_iter_to_child_iter (GTK_TREE_MODEL_FILTER (model), &child_iter, iter);
3325   elt = FILTER_ELT (iter->user_data2);
3326
3327   if (!elt->visible_siter)
3328     return FALSE;
3329
3330   /* we need to build the level to check if not all children are filtered
3331    * out
3332    */
3333   if (!elt->children
3334       && gtk_tree_model_iter_has_child (filter->priv->child_model, &child_iter))
3335     gtk_tree_model_filter_build_level (filter, FILTER_LEVEL (iter->user_data),
3336                                        elt, FALSE);
3337
3338   if (elt->children && g_sequence_get_length (elt->children->visible_seq) > 0)
3339     return TRUE;
3340
3341   return FALSE;
3342 }
3343
3344 static gint
3345 gtk_tree_model_filter_iter_n_children (GtkTreeModel *model,
3346                                        GtkTreeIter  *iter)
3347 {
3348   GtkTreeIter child_iter;
3349   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
3350   FilterElt *elt;
3351
3352   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), 0);
3353   g_return_val_if_fail (filter->priv->child_model != NULL, 0);
3354   if (iter)
3355     g_return_val_if_fail (filter->priv->stamp == iter->stamp, 0);
3356
3357   if (!iter)
3358     {
3359       if (!filter->priv->root)
3360         gtk_tree_model_filter_build_level (filter, NULL, NULL, FALSE);
3361
3362       if (filter->priv->root)
3363         return g_sequence_get_length (FILTER_LEVEL (filter->priv->root)->visible_seq);
3364
3365       return 0;
3366     }
3367
3368   elt = FILTER_ELT (iter->user_data2);
3369
3370   if (!elt->visible_siter)
3371     return 0;
3372
3373   gtk_tree_model_filter_convert_iter_to_child_iter (GTK_TREE_MODEL_FILTER (model), &child_iter, iter);
3374
3375   if (!elt->children &&
3376       gtk_tree_model_iter_has_child (filter->priv->child_model, &child_iter))
3377     gtk_tree_model_filter_build_level (filter,
3378                                        FILTER_LEVEL (iter->user_data),
3379                                        elt, FALSE);
3380
3381   if (elt->children)
3382     return g_sequence_get_length (elt->children->visible_seq);
3383
3384   return 0;
3385 }
3386
3387 static gboolean
3388 gtk_tree_model_filter_iter_nth_child (GtkTreeModel *model,
3389                                       GtkTreeIter  *iter,
3390                                       GtkTreeIter  *parent,
3391                                       gint          n)
3392 {
3393   FilterLevel *level;
3394   GtkTreeIter children;
3395   GSequenceIter *siter;
3396
3397   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
3398   if (parent)
3399     g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == parent->stamp, FALSE);
3400
3401   /* use this instead of has_child to force us to build the level, if needed */
3402   if (gtk_tree_model_filter_iter_children (model, &children, parent) == FALSE)
3403     {
3404       iter->stamp = 0;
3405       return FALSE;
3406     }
3407
3408   level = children.user_data;
3409   siter = g_sequence_get_iter_at_pos (level->visible_seq, n);
3410   if (g_sequence_iter_is_end (siter))
3411     return FALSE;
3412
3413   iter->stamp = GTK_TREE_MODEL_FILTER (model)->priv->stamp;
3414   iter->user_data = level;
3415   iter->user_data2 = GET_ELT (siter);
3416
3417   return TRUE;
3418 }
3419
3420 static gboolean
3421 gtk_tree_model_filter_iter_parent (GtkTreeModel *model,
3422                                    GtkTreeIter  *iter,
3423                                    GtkTreeIter  *child)
3424 {
3425   FilterLevel *level;
3426
3427   iter->stamp = 0;
3428   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
3429   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL, FALSE);
3430   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == child->stamp, FALSE);
3431
3432   level = child->user_data;
3433
3434   if (level->parent_level)
3435     {
3436       iter->stamp = GTK_TREE_MODEL_FILTER (model)->priv->stamp;
3437       iter->user_data = level->parent_level;
3438       iter->user_data2 = level->parent_elt;
3439
3440       return TRUE;
3441     }
3442
3443   return FALSE;
3444 }
3445
3446 static void
3447 gtk_tree_model_filter_ref_node (GtkTreeModel *model,
3448                                 GtkTreeIter  *iter)
3449 {
3450   gtk_tree_model_filter_real_ref_node (model, iter, TRUE);
3451 }
3452
3453 static void
3454 gtk_tree_model_filter_real_ref_node (GtkTreeModel *model,
3455                                      GtkTreeIter  *iter,
3456                                      gboolean      external)
3457 {
3458   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
3459   GtkTreeIter child_iter;
3460   FilterLevel *level;
3461   FilterElt *elt;
3462
3463   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (model));
3464   g_return_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL);
3465   g_return_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == iter->stamp);
3466
3467   gtk_tree_model_filter_convert_iter_to_child_iter (GTK_TREE_MODEL_FILTER (model), &child_iter, iter);
3468
3469   gtk_tree_model_ref_node (filter->priv->child_model, &child_iter);
3470
3471   level = iter->user_data;
3472   elt = iter->user_data2;
3473
3474   elt->ref_count++;
3475   level->ref_count++;
3476
3477   if (external)
3478     {
3479       elt->ext_ref_count++;
3480       level->ext_ref_count++;
3481
3482       if (level->ext_ref_count == 1)
3483         {
3484           FilterLevel *parent_level = level->parent_level;
3485           FilterElt *parent_elt = level->parent_elt;
3486
3487           /* we were at zero -- time to decrease the zero_ref_count val */
3488           while (parent_level)
3489             {
3490               parent_elt->zero_ref_count--;
3491
3492               parent_elt = parent_level->parent_elt;
3493               parent_level = parent_level->parent_level;
3494             }
3495
3496           if (filter->priv->root != level)
3497             filter->priv->zero_ref_count--;
3498
3499 #ifdef MODEL_FILTER_DEBUG
3500           g_assert (filter->priv->zero_ref_count >= 0);
3501           if (filter->priv->zero_ref_count > 0)
3502             g_assert (filter->priv->root != NULL);
3503 #endif
3504         }
3505     }
3506
3507 #ifdef MODEL_FILTER_DEBUG
3508   g_assert (elt->ref_count >= elt->ext_ref_count);
3509   g_assert (elt->ref_count >= 0);
3510   g_assert (elt->ext_ref_count >= 0);
3511 #endif
3512 }
3513
3514 static void
3515 gtk_tree_model_filter_unref_node (GtkTreeModel *model,
3516                                   GtkTreeIter  *iter)
3517 {
3518   gtk_tree_model_filter_real_unref_node (model, iter, TRUE, TRUE);
3519 }
3520
3521 static void
3522 gtk_tree_model_filter_real_unref_node (GtkTreeModel *model,
3523                                        GtkTreeIter  *iter,
3524                                        gboolean      external,
3525                                        gboolean      propagate_unref)
3526 {
3527   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
3528   FilterLevel *level;
3529   FilterElt *elt;
3530
3531   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (model));
3532   g_return_if_fail (filter->priv->child_model != NULL);
3533   g_return_if_fail (filter->priv->stamp == iter->stamp);
3534
3535   if (propagate_unref)
3536     {
3537       GtkTreeIter child_iter;
3538       gtk_tree_model_filter_convert_iter_to_child_iter (GTK_TREE_MODEL_FILTER (model), &child_iter, iter);
3539       gtk_tree_model_unref_node (filter->priv->child_model, &child_iter);
3540     }
3541
3542   level = iter->user_data;
3543   elt = iter->user_data2;
3544
3545   g_return_if_fail (elt->ref_count > 0);
3546 #ifdef MODEL_FILTER_DEBUG
3547   g_assert (elt->ref_count >= elt->ext_ref_count);
3548   g_assert (elt->ref_count >= 0);
3549   g_assert (elt->ext_ref_count >= 0);
3550 #endif
3551
3552   elt->ref_count--;
3553   level->ref_count--;
3554
3555   if (external)
3556     {
3557       elt->ext_ref_count--;
3558       level->ext_ref_count--;
3559
3560       if (level->ext_ref_count == 0)
3561         {
3562           FilterLevel *parent_level = level->parent_level;
3563           FilterElt *parent_elt = level->parent_elt;
3564
3565           /* we are at zero -- time to increase the zero_ref_count val */
3566           while (parent_level)
3567             {
3568               parent_elt->zero_ref_count++;
3569
3570               parent_elt = parent_level->parent_elt;
3571               parent_level = parent_level->parent_level;
3572             }
3573
3574           if (filter->priv->root != level)
3575             filter->priv->zero_ref_count++;
3576
3577 #ifdef MODEL_FILTER_DEBUG
3578           g_assert (filter->priv->zero_ref_count >= 0);
3579           if (filter->priv->zero_ref_count > 0)
3580             g_assert (filter->priv->root != NULL);
3581 #endif
3582         }
3583     }
3584
3585 #ifdef MODEL_FILTER_DEBUG
3586   g_assert (elt->ref_count >= elt->ext_ref_count);
3587   g_assert (elt->ref_count >= 0);
3588   g_assert (elt->ext_ref_count >= 0);
3589 #endif
3590 }
3591
3592 /* TreeDragSource interface implementation */
3593 static gboolean
3594 gtk_tree_model_filter_row_draggable (GtkTreeDragSource *drag_source,
3595                                      GtkTreePath       *path)
3596 {
3597   GtkTreeModelFilter *tree_model_filter = (GtkTreeModelFilter *)drag_source;
3598   GtkTreePath *child_path;
3599   gboolean draggable;
3600
3601   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (drag_source), FALSE);
3602   g_return_val_if_fail (path != NULL, FALSE);
3603
3604   child_path = gtk_tree_model_filter_convert_path_to_child_path (tree_model_filter, path);
3605   draggable = gtk_tree_drag_source_row_draggable (GTK_TREE_DRAG_SOURCE (tree_model_filter->priv->child_model), child_path);
3606   gtk_tree_path_free (child_path);
3607
3608   return draggable;
3609 }
3610
3611 static gboolean
3612 gtk_tree_model_filter_drag_data_get (GtkTreeDragSource *drag_source,
3613                                      GtkTreePath       *path,
3614                                      GtkSelectionData  *selection_data)
3615 {
3616   GtkTreeModelFilter *tree_model_filter = (GtkTreeModelFilter *)drag_source;
3617   GtkTreePath *child_path;
3618   gboolean gotten;
3619
3620   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (drag_source), FALSE);
3621   g_return_val_if_fail (path != NULL, FALSE);
3622
3623   child_path = gtk_tree_model_filter_convert_path_to_child_path (tree_model_filter, path);
3624   gotten = gtk_tree_drag_source_drag_data_get (GTK_TREE_DRAG_SOURCE (tree_model_filter->priv->child_model), child_path, selection_data);
3625   gtk_tree_path_free (child_path);
3626
3627   return gotten;
3628 }
3629
3630 static gboolean
3631 gtk_tree_model_filter_drag_data_delete (GtkTreeDragSource *drag_source,
3632                                         GtkTreePath       *path)
3633 {
3634   GtkTreeModelFilter *tree_model_filter = (GtkTreeModelFilter *)drag_source;
3635   GtkTreePath *child_path;
3636   gboolean deleted;
3637
3638   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (drag_source), FALSE);
3639   g_return_val_if_fail (path != NULL, FALSE);
3640
3641   child_path = gtk_tree_model_filter_convert_path_to_child_path (tree_model_filter, path);
3642   deleted = gtk_tree_drag_source_drag_data_delete (GTK_TREE_DRAG_SOURCE (tree_model_filter->priv->child_model), child_path);
3643   gtk_tree_path_free (child_path);
3644
3645   return deleted;
3646 }
3647
3648 /* bits and pieces */
3649 static void
3650 gtk_tree_model_filter_set_model (GtkTreeModelFilter *filter,
3651                                  GtkTreeModel       *child_model)
3652 {
3653   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3654
3655   if (filter->priv->child_model)
3656     {
3657       g_signal_handler_disconnect (filter->priv->child_model,
3658                                    filter->priv->changed_id);
3659       g_signal_handler_disconnect (filter->priv->child_model,
3660                                    filter->priv->inserted_id);
3661       g_signal_handler_disconnect (filter->priv->child_model,
3662                                    filter->priv->has_child_toggled_id);
3663       g_signal_handler_disconnect (filter->priv->child_model,
3664                                    filter->priv->deleted_id);
3665       g_signal_handler_disconnect (filter->priv->child_model,
3666                                    filter->priv->reordered_id);
3667
3668       /* reset our state */
3669       if (filter->priv->root)
3670         gtk_tree_model_filter_free_level (filter, filter->priv->root,
3671                                           TRUE, TRUE, FALSE);
3672
3673       filter->priv->root = NULL;
3674       g_object_unref (filter->priv->child_model);
3675       filter->priv->visible_column = -1;
3676
3677       /* FIXME: do we need to destroy more here? */
3678     }
3679
3680   filter->priv->child_model = child_model;
3681
3682   if (child_model)
3683     {
3684       g_object_ref (filter->priv->child_model);
3685       filter->priv->changed_id =
3686         g_signal_connect (child_model, "row-changed",
3687                           G_CALLBACK (gtk_tree_model_filter_row_changed),
3688                           filter);
3689       filter->priv->inserted_id =
3690         g_signal_connect (child_model, "row-inserted",
3691                           G_CALLBACK (gtk_tree_model_filter_row_inserted),
3692                           filter);
3693       filter->priv->has_child_toggled_id =
3694         g_signal_connect (child_model, "row-has-child-toggled",
3695                           G_CALLBACK (gtk_tree_model_filter_row_has_child_toggled),
3696                           filter);
3697       filter->priv->deleted_id =
3698         g_signal_connect (child_model, "row-deleted",
3699                           G_CALLBACK (gtk_tree_model_filter_row_deleted),
3700                           filter);
3701       filter->priv->reordered_id =
3702         g_signal_connect (child_model, "rows-reordered",
3703                           G_CALLBACK (gtk_tree_model_filter_rows_reordered),
3704                           filter);
3705
3706       filter->priv->child_flags = gtk_tree_model_get_flags (child_model);
3707       filter->priv->stamp = g_random_int ();
3708     }
3709 }
3710
3711 static void
3712 gtk_tree_model_filter_ref_path (GtkTreeModelFilter *filter,
3713                                 GtkTreePath        *path)
3714 {
3715   int len;
3716   GtkTreePath *p;
3717
3718   len = gtk_tree_path_get_depth (path);
3719   p = gtk_tree_path_copy (path);
3720   while (len--)
3721     {
3722       GtkTreeIter iter;
3723
3724       gtk_tree_model_get_iter (GTK_TREE_MODEL (filter->priv->child_model), &iter, p);
3725       gtk_tree_model_ref_node (GTK_TREE_MODEL (filter->priv->child_model), &iter);
3726       gtk_tree_path_up (p);
3727     }
3728
3729   gtk_tree_path_free (p);
3730 }
3731
3732 static void
3733 gtk_tree_model_filter_unref_path (GtkTreeModelFilter *filter,
3734                                   GtkTreePath        *path,
3735                                   int                 depth)
3736 {
3737   int len;
3738   GtkTreePath *p;
3739
3740   if (depth != -1)
3741     len = depth;
3742   else
3743     len = gtk_tree_path_get_depth (path);
3744
3745   p = gtk_tree_path_copy (path);
3746   while (len--)
3747     {
3748       GtkTreeIter iter;
3749
3750       gtk_tree_model_get_iter (GTK_TREE_MODEL (filter->priv->child_model), &iter, p);
3751       gtk_tree_model_unref_node (GTK_TREE_MODEL (filter->priv->child_model), &iter);
3752       gtk_tree_path_up (p);
3753     }
3754
3755   gtk_tree_path_free (p);
3756 }
3757
3758 static void
3759 gtk_tree_model_filter_set_root (GtkTreeModelFilter *filter,
3760                                 GtkTreePath        *root)
3761 {
3762   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3763
3764   if (!root)
3765     filter->priv->virtual_root = NULL;
3766   else
3767     filter->priv->virtual_root = gtk_tree_path_copy (root);
3768 }
3769
3770 /* public API */
3771
3772 /**
3773  * gtk_tree_model_filter_new:
3774  * @child_model: A #GtkTreeModel.
3775  * @root: (allow-none): A #GtkTreePath or %NULL.
3776  *
3777  * Creates a new #GtkTreeModel, with @child_model as the child_model
3778  * and @root as the virtual root.
3779  *
3780  * Return value: (transfer full): A new #GtkTreeModel.
3781  *
3782  * Since: 2.4
3783  */
3784 GtkTreeModel *
3785 gtk_tree_model_filter_new (GtkTreeModel *child_model,
3786                            GtkTreePath  *root)
3787 {
3788   GtkTreeModel *retval;
3789   GtkTreeModelFilter *filter;
3790
3791   g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);
3792
3793   retval = g_object_new (GTK_TYPE_TREE_MODEL_FILTER,
3794                          "child-model", child_model,
3795                          "virtual-root", root,
3796                          NULL);
3797
3798   filter = GTK_TREE_MODEL_FILTER (retval);
3799   if (filter->priv->virtual_root)
3800     {
3801       gtk_tree_model_filter_ref_path (filter, filter->priv->virtual_root);
3802       filter->priv->virtual_root_deleted = FALSE;
3803     }
3804
3805   return retval;
3806 }
3807
3808 /**
3809  * gtk_tree_model_filter_get_model:
3810  * @filter: A #GtkTreeModelFilter.
3811  *
3812  * Returns a pointer to the child model of @filter.
3813  *
3814  * Return value: (transfer none): A pointer to a #GtkTreeModel.
3815  *
3816  * Since: 2.4
3817  */
3818 GtkTreeModel *
3819 gtk_tree_model_filter_get_model (GtkTreeModelFilter *filter)
3820 {
3821   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (filter), NULL);
3822
3823   return filter->priv->child_model;
3824 }
3825
3826 /**
3827  * gtk_tree_model_filter_set_visible_func:
3828  * @filter: A #GtkTreeModelFilter.
3829  * @func: A #GtkTreeModelFilterVisibleFunc, the visible function.
3830  * @data: (allow-none): User data to pass to the visible function, or %NULL.
3831  * @destroy: (allow-none): Destroy notifier of @data, or %NULL.
3832  *
3833  * Sets the visible function used when filtering the @filter to be @func. The
3834  * function should return %TRUE if the given row should be visible and
3835  * %FALSE otherwise.
3836  *
3837  * If the condition calculated by the function changes over time (e.g. because
3838  * it depends on some global parameters), you must call
3839  * gtk_tree_model_filter_refilter() to keep the visibility information of
3840  * the model uptodate.
3841  *
3842  * Note that @func is called whenever a row is inserted, when it may still be
3843  * empty. The visible function should therefore take special care of empty
3844  * rows, like in the example below.
3845  *
3846  * <informalexample><programlisting>
3847  * static gboolean
3848  * visible_func (GtkTreeModel *model,
3849  *               GtkTreeIter  *iter,
3850  *               gpointer      data)
3851  * {
3852  *   /&ast; Visible if row is non-empty and first column is "HI" &ast;/
3853  *   gchar *str;
3854  *   gboolean visible = FALSE;
3855  *
3856  *   gtk_tree_model_get (model, iter, 0, &str, -1);
3857  *   if (str && strcmp (str, "HI") == 0)
3858  *     visible = TRUE;
3859  *   g_free (str);
3860  *
3861  *   return visible;
3862  * }
3863  * </programlisting></informalexample>
3864  *
3865  * Since: 2.4
3866  */
3867 void
3868 gtk_tree_model_filter_set_visible_func (GtkTreeModelFilter            *filter,
3869                                         GtkTreeModelFilterVisibleFunc  func,
3870                                         gpointer                       data,
3871                                         GDestroyNotify                 destroy)
3872 {
3873   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3874   g_return_if_fail (func != NULL);
3875   g_return_if_fail (filter->priv->visible_method_set == FALSE);
3876
3877   filter->priv->visible_func = func;
3878   filter->priv->visible_data = data;
3879   filter->priv->visible_destroy = destroy;
3880
3881   filter->priv->visible_method_set = TRUE;
3882 }
3883
3884 /**
3885  * gtk_tree_model_filter_set_modify_func:
3886  * @filter: A #GtkTreeModelFilter.
3887  * @n_columns: The number of columns in the filter model.
3888  * @types: (array length=n_columns): The #GType<!-- -->s of the columns.
3889  * @func: A #GtkTreeModelFilterModifyFunc
3890  * @data: (allow-none): User data to pass to the modify function, or %NULL.
3891  * @destroy: (allow-none): Destroy notifier of @data, or %NULL.
3892  *
3893  * With the @n_columns and @types parameters, you give an array of column
3894  * types for this model (which will be exposed to the parent model/view).
3895  * The @func, @data and @destroy parameters are for specifying the modify
3896  * function. The modify function will get called for <emphasis>each</emphasis>
3897  * data access, the goal of the modify function is to return the data which
3898  * should be displayed at the location specified using the parameters of the
3899  * modify function.
3900  *
3901  * Since: 2.4
3902  */
3903 void
3904 gtk_tree_model_filter_set_modify_func (GtkTreeModelFilter           *filter,
3905                                        gint                          n_columns,
3906                                        GType                        *types,
3907                                        GtkTreeModelFilterModifyFunc  func,
3908                                        gpointer                      data,
3909                                        GDestroyNotify                destroy)
3910 {
3911   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3912   g_return_if_fail (func != NULL);
3913   g_return_if_fail (filter->priv->modify_func_set == FALSE);
3914
3915   if (filter->priv->modify_destroy)
3916     {
3917       GDestroyNotify d = filter->priv->modify_destroy;
3918
3919       filter->priv->modify_destroy = NULL;
3920       d (filter->priv->modify_data);
3921     }
3922
3923   filter->priv->modify_n_columns = n_columns;
3924   filter->priv->modify_types = g_new0 (GType, n_columns);
3925   memcpy (filter->priv->modify_types, types, sizeof (GType) * n_columns);
3926   filter->priv->modify_func = func;
3927   filter->priv->modify_data = data;
3928   filter->priv->modify_destroy = destroy;
3929
3930   filter->priv->modify_func_set = TRUE;
3931 }
3932
3933 /**
3934  * gtk_tree_model_filter_set_visible_column:
3935  * @filter: A #GtkTreeModelFilter.
3936  * @column: A #gint which is the column containing the visible information.
3937  *
3938  * Sets @column of the child_model to be the column where @filter should
3939  * look for visibility information. @columns should be a column of type
3940  * %G_TYPE_BOOLEAN, where %TRUE means that a row is visible, and %FALSE
3941  * if not.
3942  *
3943  * Since: 2.4
3944  */
3945 void
3946 gtk_tree_model_filter_set_visible_column (GtkTreeModelFilter *filter,
3947                                           gint column)
3948 {
3949   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3950   g_return_if_fail (column >= 0);
3951   g_return_if_fail (filter->priv->visible_method_set == FALSE);
3952
3953   filter->priv->visible_column = column;
3954
3955   filter->priv->visible_method_set = TRUE;
3956 }
3957
3958 /* conversion */
3959
3960 /**
3961  * gtk_tree_model_filter_convert_child_iter_to_iter:
3962  * @filter: A #GtkTreeModelFilter.
3963  * @filter_iter: (out): An uninitialized #GtkTreeIter.
3964  * @child_iter: A valid #GtkTreeIter pointing to a row on the child model.
3965  *
3966  * Sets @filter_iter to point to the row in @filter that corresponds to the
3967  * row pointed at by @child_iter.  If @filter_iter was not set, %FALSE is
3968  * returned.
3969  *
3970  * Return value: %TRUE, if @filter_iter was set, i.e. if @child_iter is a
3971  * valid iterator pointing to a visible row in child model.
3972  *
3973  * Since: 2.4
3974  */
3975 gboolean
3976 gtk_tree_model_filter_convert_child_iter_to_iter (GtkTreeModelFilter *filter,
3977                                                   GtkTreeIter        *filter_iter,
3978                                                   GtkTreeIter        *child_iter)
3979 {
3980   gboolean ret;
3981   GtkTreePath *child_path, *path;
3982
3983   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (filter), FALSE);
3984   g_return_val_if_fail (filter->priv->child_model != NULL, FALSE);
3985   g_return_val_if_fail (filter_iter != NULL, FALSE);
3986   g_return_val_if_fail (child_iter != NULL, FALSE);
3987   g_return_val_if_fail (filter_iter != child_iter, FALSE);
3988
3989   filter_iter->stamp = 0;
3990
3991   child_path = gtk_tree_model_get_path (filter->priv->child_model, child_iter);
3992   g_return_val_if_fail (child_path != NULL, FALSE);
3993
3994   path = gtk_tree_model_filter_convert_child_path_to_path (filter,
3995                                                            child_path);
3996   gtk_tree_path_free (child_path);
3997
3998   if (!path)
3999     return FALSE;
4000
4001   ret = gtk_tree_model_get_iter (GTK_TREE_MODEL (filter), filter_iter, path);
4002   gtk_tree_path_free (path);
4003
4004   return ret;
4005 }
4006
4007 /**
4008  * gtk_tree_model_filter_convert_iter_to_child_iter:
4009  * @filter: A #GtkTreeModelFilter.
4010  * @child_iter: (out): An uninitialized #GtkTreeIter.
4011  * @filter_iter: A valid #GtkTreeIter pointing to a row on @filter.
4012  *
4013  * Sets @child_iter to point to the row pointed to by @filter_iter.
4014  *
4015  * Since: 2.4
4016  */
4017 void
4018 gtk_tree_model_filter_convert_iter_to_child_iter (GtkTreeModelFilter *filter,
4019                                                   GtkTreeIter        *child_iter,
4020                                                   GtkTreeIter        *filter_iter)
4021 {
4022   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
4023   g_return_if_fail (filter->priv->child_model != NULL);
4024   g_return_if_fail (child_iter != NULL);
4025   g_return_if_fail (filter_iter != NULL);
4026   g_return_if_fail (filter_iter->stamp == filter->priv->stamp);
4027   g_return_if_fail (filter_iter != child_iter);
4028
4029   if (GTK_TREE_MODEL_FILTER_CACHE_CHILD_ITERS (filter))
4030     {
4031       *child_iter = FILTER_ELT (filter_iter->user_data2)->iter;
4032     }
4033   else
4034     {
4035       GtkTreePath *path;
4036       gboolean valid = FALSE;
4037
4038       path = gtk_tree_model_filter_elt_get_path (filter_iter->user_data,
4039                                                  filter_iter->user_data2,
4040                                                  filter->priv->virtual_root);
4041       valid = gtk_tree_model_get_iter (filter->priv->child_model, child_iter,
4042                                        path);
4043       gtk_tree_path_free (path);
4044
4045       g_return_if_fail (valid == TRUE);
4046     }
4047 }
4048
4049 /* The path returned can only be used internally in the filter model. */
4050 static GtkTreePath *
4051 gtk_real_tree_model_filter_convert_child_path_to_path (GtkTreeModelFilter *filter,
4052                                                        GtkTreePath        *child_path,
4053                                                        gboolean            build_levels,
4054                                                        gboolean            fetch_children)
4055 {
4056   gint *child_indices;
4057   GtkTreePath *retval;
4058   GtkTreePath *real_path;
4059   FilterLevel *level;
4060   FilterElt *tmp;
4061   gint i;
4062
4063   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (filter), NULL);
4064   g_return_val_if_fail (filter->priv->child_model != NULL, NULL);
4065   g_return_val_if_fail (child_path != NULL, NULL);
4066
4067   if (!filter->priv->virtual_root)
4068     real_path = gtk_tree_path_copy (child_path);
4069   else
4070     real_path = gtk_tree_model_filter_remove_root (child_path,
4071                                                    filter->priv->virtual_root);
4072
4073   if (!real_path)
4074     return NULL;
4075
4076   retval = gtk_tree_path_new ();
4077   child_indices = gtk_tree_path_get_indices (real_path);
4078
4079   if (filter->priv->root == NULL && build_levels)
4080     gtk_tree_model_filter_build_level (filter, NULL, NULL, FALSE);
4081   level = FILTER_LEVEL (filter->priv->root);
4082
4083   for (i = 0; i < gtk_tree_path_get_depth (real_path); i++)
4084     {
4085       GSequenceIter *siter;
4086       gboolean found_child = FALSE;
4087
4088       if (!level)
4089         {
4090           gtk_tree_path_free (real_path);
4091           gtk_tree_path_free (retval);
4092           return NULL;
4093         }
4094
4095       tmp = lookup_elt_with_offset (level->seq, child_indices[i], &siter);
4096       if (tmp)
4097         {
4098           gtk_tree_path_append_index (retval, g_sequence_iter_get_position (siter));
4099           if (!tmp->children && build_levels)
4100             gtk_tree_model_filter_build_level (filter, level, tmp, FALSE);
4101           level = tmp->children;
4102           found_child = TRUE;
4103         }
4104
4105       if (!found_child && fetch_children)
4106         {
4107           int j;
4108
4109           tmp = gtk_tree_model_filter_fetch_child (filter, level,
4110                                                    child_indices[i],
4111                                                    &j);
4112
4113           /* didn't find the child, let's try to bring it back */
4114           if (!tmp || tmp->offset != child_indices[i])
4115             {
4116               /* not there */
4117               gtk_tree_path_free (real_path);
4118               gtk_tree_path_free (retval);
4119               return NULL;
4120             }
4121
4122           gtk_tree_path_append_index (retval, j);
4123           if (!tmp->children && build_levels)
4124             gtk_tree_model_filter_build_level (filter, level, tmp, FALSE);
4125           level = tmp->children;
4126           found_child = TRUE;
4127         }
4128       else if (!found_child && !fetch_children)
4129         {
4130           /* no path */
4131           gtk_tree_path_free (real_path);
4132           gtk_tree_path_free (retval);
4133           return NULL;
4134         }
4135     }
4136
4137   gtk_tree_path_free (real_path);
4138   return retval;
4139 }
4140
4141 /**
4142  * gtk_tree_model_filter_convert_child_path_to_path:
4143  * @filter: A #GtkTreeModelFilter.
4144  * @child_path: A #GtkTreePath to convert.
4145  *
4146  * Converts @child_path to a path relative to @filter. That is, @child_path
4147  * points to a path in the child model. The rerturned path will point to the
4148  * same row in the filtered model. If @child_path isn't a valid path on the
4149  * child model or points to a row which is not visible in @filter, then %NULL
4150  * is returned.
4151  *
4152  * Return value: A newly allocated #GtkTreePath, or %NULL.
4153  *
4154  * Since: 2.4
4155  */
4156 GtkTreePath *
4157 gtk_tree_model_filter_convert_child_path_to_path (GtkTreeModelFilter *filter,
4158                                                   GtkTreePath        *child_path)
4159 {
4160   GtkTreeIter iter;
4161   GtkTreePath *path;
4162
4163   /* this function does the sanity checks */
4164   path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
4165                                                                 child_path,
4166                                                                 TRUE,
4167                                                                 TRUE);
4168
4169   if (!path)
4170       return NULL;
4171
4172   /* get a new path which only takes visible nodes into account.
4173    * -- if this gives any performance issues, we can write a special
4174    *    version of convert_child_path_to_path immediately returning
4175    *    a visible-nodes-only path.
4176    */
4177   gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (filter), &iter, path);
4178
4179   gtk_tree_path_free (path);
4180   path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
4181
4182   return path;
4183 }
4184
4185 /**
4186  * gtk_tree_model_filter_convert_path_to_child_path:
4187  * @filter: A #GtkTreeModelFilter.
4188  * @filter_path: A #GtkTreePath to convert.
4189  *
4190  * Converts @filter_path to a path on the child model of @filter. That is,
4191  * @filter_path points to a location in @filter. The returned path will
4192  * point to the same location in the model not being filtered. If @filter_path
4193  * does not point to a location in the child model, %NULL is returned.
4194  *
4195  * Return value: A newly allocated #GtkTreePath, or %NULL.
4196  *
4197  * Since: 2.4
4198  */
4199 GtkTreePath *
4200 gtk_tree_model_filter_convert_path_to_child_path (GtkTreeModelFilter *filter,
4201                                                   GtkTreePath        *filter_path)
4202 {
4203   gint *filter_indices;
4204   GtkTreePath *retval;
4205   FilterLevel *level;
4206   gint i;
4207
4208   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (filter), NULL);
4209   g_return_val_if_fail (filter->priv->child_model != NULL, NULL);
4210   g_return_val_if_fail (filter_path != NULL, NULL);
4211
4212   /* convert path */
4213   retval = gtk_tree_path_new ();
4214   filter_indices = gtk_tree_path_get_indices (filter_path);
4215   if (!filter->priv->root)
4216     gtk_tree_model_filter_build_level (filter, NULL, NULL, FALSE);
4217   level = FILTER_LEVEL (filter->priv->root);
4218
4219   for (i = 0; i < gtk_tree_path_get_depth (filter_path); i++)
4220     {
4221       FilterElt *elt;
4222       GSequenceIter *siter;
4223
4224       if (!level)
4225         {
4226           gtk_tree_path_free (retval);
4227           return NULL;
4228         }
4229
4230       siter = g_sequence_get_iter_at_pos (level->visible_seq, filter_indices[i]);
4231       if (g_sequence_iter_is_end (siter))
4232         {
4233           gtk_tree_path_free (retval);
4234           return NULL;
4235         }
4236
4237       elt = GET_ELT (siter);
4238       if (elt->children == NULL)
4239         gtk_tree_model_filter_build_level (filter, level, elt, FALSE);
4240
4241       gtk_tree_path_append_index (retval, elt->offset);
4242       level = elt->children;
4243     }
4244
4245   /* apply vroot */
4246
4247   if (filter->priv->virtual_root)
4248     {
4249       GtkTreePath *real_retval;
4250
4251       real_retval = gtk_tree_model_filter_add_root (retval,
4252                                                     filter->priv->virtual_root);
4253       gtk_tree_path_free (retval);
4254
4255       return real_retval;
4256     }
4257
4258   return retval;
4259 }
4260
4261 static gboolean
4262 gtk_tree_model_filter_refilter_helper (GtkTreeModel *model,
4263                                        GtkTreePath  *path,
4264                                        GtkTreeIter  *iter,
4265                                        gpointer      data)
4266 {
4267   /* evil, don't try this at home, but certainly speeds things up */
4268   gtk_tree_model_filter_row_changed (model, path, iter, data);
4269
4270   return FALSE;
4271 }
4272
4273 /**
4274  * gtk_tree_model_filter_refilter:
4275  * @filter: A #GtkTreeModelFilter.
4276  *
4277  * Emits ::row_changed for each row in the child model, which causes
4278  * the filter to re-evaluate whether a row is visible or not.
4279  *
4280  * Since: 2.4
4281  */
4282 void
4283 gtk_tree_model_filter_refilter (GtkTreeModelFilter *filter)
4284 {
4285   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
4286
4287   /* S L O W */
4288   gtk_tree_model_foreach (filter->priv->child_model,
4289                           gtk_tree_model_filter_refilter_helper,
4290                           filter);
4291 }
4292
4293 /**
4294  * gtk_tree_model_filter_clear_cache:
4295  * @filter: A #GtkTreeModelFilter.
4296  *
4297  * This function should almost never be called. It clears the @filter
4298  * of any cached iterators that haven't been reffed with
4299  * gtk_tree_model_ref_node(). This might be useful if the child model
4300  * being filtered is static (and doesn't change often) and there has been
4301  * a lot of unreffed access to nodes. As a side effect of this function,
4302  * all unreffed iters will be invalid.
4303  *
4304  * Since: 2.4
4305  */
4306 void
4307 gtk_tree_model_filter_clear_cache (GtkTreeModelFilter *filter)
4308 {
4309   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
4310
4311   if (filter->priv->zero_ref_count > 0)
4312     gtk_tree_model_filter_clear_cache_helper (filter,
4313                                               FILTER_LEVEL (filter->priv->root));
4314 }