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