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