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