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

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