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

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