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