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