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