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

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