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

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