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

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