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

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