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

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