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