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

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