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