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