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