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