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   GtkTreePath *path = NULL;
1088
1089   gboolean emit_child_toggled = FALSE;
1090
1091   iter.stamp = filter->priv->stamp;
1092   iter.user_data = level;
1093   iter.user_data2 = elt;
1094
1095   path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
1096
1097   parent_elt_index = level->parent_elt_index;
1098   if (parent_elt_index >= 0)
1099     parent = FILTER_LEVEL_PARENT_ELT (level);
1100   else
1101     parent = NULL;
1102   parent_level = level->parent_level;
1103
1104   length = level->array->len;
1105
1106   /* first register the node to be invisible */
1107   level->visible_nodes--;
1108   elt->visible = FALSE;
1109
1110   /* we distinguish a couple of cases:
1111    *  - root level, length > 1: emit row-deleted and remove.
1112    *  - root level, length == 1: emit row-deleted and keep in cache.
1113    *  - level, length == 1: parent->ref_count > 1: emit row-deleted and keep.
1114    *  - level, length > 1: emit row-deleted and remove.
1115    *  - else, remove level.
1116    *
1117    *  if level != root level and visible nodes == 0, emit row-has-child-toggled.
1118    */
1119
1120   if (level != filter->priv->root
1121       && level->visible_nodes == 0
1122       && parent
1123       && parent->visible)
1124     emit_child_toggled = TRUE;
1125
1126   if (length > 1)
1127     {
1128       FilterElt *tmp;
1129
1130       /* We emit row-deleted, and remove the node from the cache.
1131        * If it has any children, these will be removed here as well.
1132        */
1133
1134       if (elt->children)
1135         gtk_tree_model_filter_free_level (filter, elt->children, TRUE);
1136
1137       gtk_tree_model_filter_increment_stamp (filter);
1138       iter.stamp = filter->priv->stamp;
1139       gtk_tree_model_row_deleted (GTK_TREE_MODEL (filter), path);
1140
1141       while (elt->ref_count > 1)
1142         gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
1143                                                &iter, FALSE);
1144
1145       if (parent_level || filter->priv->virtual_root)
1146         gtk_tree_model_filter_unref_node (GTK_TREE_MODEL (filter), &iter);
1147       else if (elt->ref_count > 0)
1148         gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
1149                                                &iter, FALSE);
1150
1151       /* remove the node */
1152       tmp = bsearch_elt_with_offset (level->array, elt->offset, &i);
1153
1154       if (tmp)
1155         {
1156           g_array_remove_index (level->array, i);
1157
1158           i--;
1159           for (i = MAX (i, 0); i < level->array->len; i++)
1160             {
1161               /* NOTE: here we do *not* decrease offsets, because the node was
1162                * not removed from the child model
1163                */
1164               elt = &g_array_index (level->array, FilterElt, i);
1165               if (elt->children)
1166                 elt->children->parent_elt_index = i;
1167             }
1168         }
1169     }
1170   else if ((length == 1 && parent && parent->ref_count > 1)
1171            || (length == 1 && level == filter->priv->root))
1172     {
1173       /* We emit row-deleted, but keep the node in the cache and
1174        * referenced.  Its children will be removed.
1175        */
1176
1177       if (elt->children)
1178         {
1179           gtk_tree_model_filter_free_level (filter, elt->children, TRUE);
1180           elt->children = NULL;
1181         }
1182
1183       gtk_tree_model_filter_increment_stamp (filter);
1184       gtk_tree_model_row_deleted (GTK_TREE_MODEL (filter), path);
1185     }
1186   else
1187     {
1188       /* Blow level away, including any child levels */
1189
1190       gtk_tree_model_filter_increment_stamp (filter);
1191       iter.stamp = filter->priv->stamp;
1192       gtk_tree_model_row_deleted (GTK_TREE_MODEL (filter), path);
1193
1194       while (elt->ref_count > 1)
1195         gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (filter),
1196                                                &iter, FALSE);
1197
1198       gtk_tree_model_filter_free_level (filter, level, TRUE);
1199     }
1200
1201   gtk_tree_path_free (path);
1202
1203   if (emit_child_toggled)
1204     {
1205       GtkTreeIter piter;
1206       GtkTreePath *ppath;
1207
1208       piter.stamp = filter->priv->stamp;
1209       piter.user_data = parent_level;
1210       piter.user_data2 = parent;
1211
1212       ppath = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &piter);
1213
1214       gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (filter),
1215                                             ppath, &piter);
1216       gtk_tree_path_free (ppath);
1217     }
1218 }
1219
1220 static void
1221 gtk_tree_model_filter_update_children (GtkTreeModelFilter *filter,
1222                                        FilterLevel        *level,
1223                                        FilterElt          *elt)
1224 {
1225   GtkTreeIter c_iter;
1226   GtkTreeIter iter;
1227
1228   if (!elt->visible)
1229     return;
1230
1231   iter.stamp = filter->priv->stamp;
1232   iter.user_data = level;
1233   iter.user_data2 = elt;
1234
1235   gtk_tree_model_filter_convert_iter_to_child_iter (filter, &c_iter, &iter);
1236
1237   if (gtk_tree_model_iter_has_child (filter->priv->child_model, &c_iter))
1238     {
1239       GtkTreePath *path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter),
1240                                                    &iter);
1241       gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (filter),
1242                                             path,
1243                                             &iter);
1244       if (path)
1245         gtk_tree_path_free (path);
1246     }
1247 }
1248
1249 static FilterElt *
1250 bsearch_elt_with_offset (GArray *array,
1251                          gint    offset,
1252                          gint   *index)
1253 {
1254   gint start, middle, end;
1255   FilterElt *elt;
1256
1257   start = 0;
1258   end = array->len;
1259
1260   if (array->len < 1)
1261     return NULL;
1262
1263   if (start == end)
1264     {
1265       elt = &g_array_index (array, FilterElt, 0);
1266
1267       if (elt->offset == offset)
1268         {
1269           *index = 0;
1270           return elt;
1271         }
1272       else
1273         return NULL;
1274     }
1275
1276   do
1277     {
1278       middle = (start + end) / 2;
1279
1280       elt = &g_array_index (array, FilterElt, middle);
1281
1282       if (elt->offset < offset)
1283         start = middle + 1;
1284       else if (elt->offset > offset)
1285         end = middle;
1286       else
1287         break;
1288     }
1289   while (start != end);
1290
1291   if (elt->offset == offset)
1292     {
1293       *index = middle;
1294       return elt;
1295     }
1296
1297   return NULL;
1298 }
1299
1300 /* Path is relative to the child model (this is on search on elt offset)
1301  * but with the virtual root already removed if necesssary.
1302  */
1303 static gboolean
1304 find_elt_with_offset (GtkTreeModelFilter *filter,
1305                       GtkTreePath        *path,
1306                       FilterLevel       **level_,
1307                       FilterElt         **elt_)
1308 {
1309   int i = 0;
1310   FilterLevel *level;
1311   FilterLevel *parent_level = NULL;
1312   FilterElt *elt = NULL;
1313
1314   level = FILTER_LEVEL (filter->priv->root);
1315
1316   while (i < gtk_tree_path_get_depth (path))
1317     {
1318       int j;
1319
1320       if (!level)
1321         return FALSE;
1322
1323       elt = bsearch_elt_with_offset (level->array,
1324                                      gtk_tree_path_get_indices (path)[i],
1325                                      &j);
1326
1327       if (!elt)
1328         return FALSE;
1329
1330       parent_level = level;
1331       level = elt->children;
1332       i++;
1333     }
1334
1335   if (level_)
1336     *level_ = parent_level;
1337
1338   if (elt_)
1339     *elt_ = elt;
1340
1341   return TRUE;
1342 }
1343
1344 /* TreeModel signals */
1345 static void
1346 gtk_tree_model_filter_emit_row_inserted_for_path (GtkTreeModelFilter *filter,
1347                                                   GtkTreeModel       *c_model,
1348                                                   GtkTreePath        *c_path,
1349                                                   GtkTreeIter        *c_iter)
1350 {
1351   FilterLevel *level;
1352   FilterElt *elt;
1353   GtkTreePath *path;
1354   GtkTreeIter iter, children;
1355   gboolean signals_emitted = FALSE;
1356
1357   if (!filter->priv->root)
1358     {
1359       gtk_tree_model_filter_build_level (filter, NULL, -1, TRUE);
1360
1361       /* We will only proceed below if the item is found.  If the item
1362        * is found, we can be sure row-inserted has just been emitted
1363        * for it.
1364        */
1365       if (filter->priv->root &&
1366           FILTER_LEVEL (filter->priv->root)->visible_nodes)
1367         signals_emitted = TRUE;
1368     }
1369
1370   /* We need to disallow to build new levels, because we are then pulling
1371    * in a child in an invisible level.  We only want to find path if it
1372    * is in a visible level (and thus has a parent that is visible).
1373    */
1374   path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
1375                                                                 c_path,
1376                                                                 FALSE,
1377                                                                 TRUE);
1378
1379   if (!path)
1380     /* parent is probably being filtered out */
1381     return;
1382
1383   gtk_tree_model_filter_increment_stamp (filter);
1384
1385   gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (filter), &iter, path);
1386
1387   level = FILTER_LEVEL (iter.user_data);
1388   elt = FILTER_ELT (iter.user_data2);
1389
1390   /* Make sure elt is visible.  elt can already be visible in case
1391    * it was pulled in above, so avoid increasing level->visible_nodes twice.
1392    */
1393   if (!elt->visible)
1394     {
1395       elt->visible = TRUE;
1396       level->visible_nodes++;
1397     }
1398
1399   /* Check whether the node and all of its parents are visible */
1400   if (gtk_tree_model_filter_elt_is_visible_in_target (level, elt))
1401     {
1402       /* visibility changed -- reget path */
1403       gtk_tree_path_free (path);
1404       path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
1405
1406       if (!signals_emitted)
1407         gtk_tree_model_row_inserted (GTK_TREE_MODEL (filter), path, &iter);
1408
1409       if (level->parent_level && level->visible_nodes == 1)
1410         {
1411           /* We know that this is the first visible node in this level, so
1412            * we need to emit row-has-child-toggled on the parent.  This
1413            * does not apply to the root level.
1414            */
1415
1416           gtk_tree_path_up (path);
1417           gtk_tree_model_get_iter (GTK_TREE_MODEL (filter), &iter, path);
1418
1419           gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (filter),
1420                                                 path,
1421                                                 &iter);
1422         }
1423
1424       if (!signals_emitted
1425           && gtk_tree_model_iter_children (c_model, &children, c_iter))
1426         gtk_tree_model_filter_update_children (filter, level, elt);
1427     }
1428
1429   gtk_tree_path_free (path);
1430 }
1431
1432 static void
1433 gtk_tree_model_filter_row_changed (GtkTreeModel *c_model,
1434                                    GtkTreePath  *c_path,
1435                                    GtkTreeIter  *c_iter,
1436                                    gpointer      data)
1437 {
1438   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (data);
1439   GtkTreeIter iter;
1440   GtkTreeIter children;
1441   GtkTreeIter real_c_iter;
1442   GtkTreePath *path = NULL;
1443
1444   FilterElt *elt;
1445   FilterLevel *level;
1446
1447   gboolean requested_state;
1448   gboolean current_state;
1449   gboolean free_c_path = FALSE;
1450
1451   g_return_if_fail (c_path != NULL || c_iter != NULL);
1452
1453   if (!c_path)
1454     {
1455       c_path = gtk_tree_model_get_path (c_model, c_iter);
1456       free_c_path = TRUE;
1457     }
1458
1459   if (c_iter)
1460     real_c_iter = *c_iter;
1461   else
1462     gtk_tree_model_get_iter (c_model, &real_c_iter, c_path);
1463
1464   /* is this node above the virtual root? */
1465   if (filter->priv->virtual_root &&
1466       (gtk_tree_path_get_depth (filter->priv->virtual_root)
1467           >= gtk_tree_path_get_depth (c_path)))
1468     goto done;
1469
1470   /* what's the requested state? */
1471   requested_state = gtk_tree_model_filter_visible (filter, &real_c_iter);
1472
1473   /* now, let's see whether the item is there */
1474   path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
1475                                                                 c_path,
1476                                                                 FALSE,
1477                                                                 FALSE);
1478
1479   if (path)
1480     {
1481       gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (filter),
1482                                            &iter, path);
1483       current_state = FILTER_ELT (iter.user_data2)->visible;
1484     }
1485   else
1486     current_state = FALSE;
1487
1488   if (current_state == FALSE && requested_state == FALSE)
1489     /* no changes required */
1490     goto done;
1491
1492   if (current_state == TRUE && requested_state == FALSE)
1493     {
1494       gtk_tree_model_filter_remove_elt_from_level (filter, level,
1495                                                    FILTER_ELT (iter.user_data2));
1496
1497       goto done;
1498     }
1499
1500   if (current_state == TRUE && requested_state == TRUE)
1501     {
1502       /* propagate the signal; also get a path taking only visible
1503        * nodes into account.
1504        */
1505       gtk_tree_path_free (path);
1506       path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
1507
1508       level = FILTER_LEVEL (iter.user_data);
1509       elt = FILTER_ELT (iter.user_data2);
1510
1511       if (gtk_tree_model_filter_elt_is_visible_in_target (level, elt))
1512         {
1513           gtk_tree_model_row_changed (GTK_TREE_MODEL (filter), path, &iter);
1514
1515           /* and update the children */
1516           if (gtk_tree_model_iter_children (c_model, &children, &real_c_iter))
1517             gtk_tree_model_filter_update_children (filter, level, elt);
1518         }
1519
1520       goto done;
1521     }
1522
1523   /* only current == FALSE and requested == TRUE is left,
1524    * pull in the child
1525    */
1526   g_return_if_fail (current_state == FALSE && requested_state == TRUE);
1527
1528   gtk_tree_model_filter_emit_row_inserted_for_path (filter, c_model,
1529                                                     c_path, c_iter);
1530
1531 done:
1532   if (path)
1533     gtk_tree_path_free (path);
1534
1535   if (free_c_path)
1536     gtk_tree_path_free (c_path);
1537 }
1538
1539 static void
1540 gtk_tree_model_filter_row_inserted (GtkTreeModel *c_model,
1541                                     GtkTreePath  *c_path,
1542                                     GtkTreeIter  *c_iter,
1543                                     gpointer      data)
1544 {
1545   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (data);
1546   GtkTreePath *real_path = NULL;
1547
1548   GtkTreeIter real_c_iter;
1549
1550   FilterElt *elt = NULL;
1551   FilterLevel *level = NULL;
1552   FilterLevel *parent_level = NULL;
1553
1554   gint i = 0, offset;
1555
1556   gboolean free_c_path = FALSE;
1557   gboolean emit_row_inserted = FALSE;
1558
1559   g_return_if_fail (c_path != NULL || c_iter != NULL);
1560
1561   if (!c_path)
1562     {
1563       c_path = gtk_tree_model_get_path (c_model, c_iter);
1564       free_c_path = TRUE;
1565     }
1566
1567   if (c_iter)
1568     real_c_iter = *c_iter;
1569   else
1570     gtk_tree_model_get_iter (c_model, &real_c_iter, c_path);
1571
1572   /* the row has already been inserted. so we need to fixup the
1573    * virtual root here first
1574    */
1575   if (filter->priv->virtual_root)
1576     {
1577       if (gtk_tree_path_get_depth (filter->priv->virtual_root) >=
1578           gtk_tree_path_get_depth (c_path))
1579         {
1580           gint level;
1581           gint *v_indices, *c_indices;
1582           gboolean common_prefix = TRUE;
1583
1584           level = gtk_tree_path_get_depth (c_path) - 1;
1585           v_indices = gtk_tree_path_get_indices (filter->priv->virtual_root);
1586           c_indices = gtk_tree_path_get_indices (c_path);
1587
1588           for (i = 0; i < level; i++)
1589             if (v_indices[i] != c_indices[i])
1590               {
1591                 common_prefix = FALSE;
1592                 break;
1593               }
1594
1595           if (common_prefix && v_indices[level] >= c_indices[level])
1596             (v_indices[level])++;
1597         }
1598     }
1599
1600   if (!filter->priv->root)
1601     {
1602       /* No point in building the level if this node is not visible. */
1603       if (!filter->priv->virtual_root
1604           && !gtk_tree_model_filter_visible (filter, c_iter))
1605         goto done;
1606
1607       /* build level will pull in the new child */
1608       gtk_tree_model_filter_build_level (filter, NULL, -1, FALSE);
1609
1610       if (filter->priv->root
1611           && FILTER_LEVEL (filter->priv->root)->visible_nodes)
1612         emit_row_inserted = TRUE;
1613
1614       goto done;
1615     }
1616
1617   /* subtract virtual root if necessary */
1618   if (filter->priv->virtual_root)
1619     {
1620       real_path = gtk_tree_model_filter_remove_root (c_path,
1621                                                      filter->priv->virtual_root);
1622       /* not our child */
1623       if (!real_path)
1624         goto done;
1625     }
1626   else
1627     real_path = gtk_tree_path_copy (c_path);
1628
1629   if (gtk_tree_path_get_depth (real_path) - 1 >= 1)
1630     {
1631       gboolean found = FALSE;
1632       GtkTreePath *parent = gtk_tree_path_copy (real_path);
1633       gtk_tree_path_up (parent);
1634
1635       found = find_elt_with_offset (filter, parent, &parent_level, &elt);
1636
1637       gtk_tree_path_free (parent);
1638
1639       if (!found)
1640         /* Parent is not in the cache and probably being filtered out */
1641         goto done;
1642
1643       level = elt->children;
1644     }
1645   else
1646     level = FILTER_LEVEL (filter->priv->root);
1647
1648   if (!level)
1649     {
1650       if (elt && elt->visible)
1651         {
1652           /* The level in which the new node should be inserted does not
1653            * exist, but the parent, elt, does.  If elt is visible, emit
1654            * row-has-child-toggled.
1655            */
1656           GtkTreePath *tmppath;
1657           GtkTreeIter  tmpiter;
1658
1659           tmpiter.stamp = filter->priv->stamp;
1660           tmpiter.user_data = parent_level;
1661           tmpiter.user_data2 = elt;
1662
1663           tmppath = gtk_tree_model_get_path (GTK_TREE_MODEL (filter),
1664                                              &tmpiter);
1665
1666           if (tmppath)
1667             {
1668               gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (filter),
1669                                                     tmppath, &tmpiter);
1670               gtk_tree_path_free (tmppath);
1671             }
1672         }
1673       goto done;
1674     }
1675
1676   /* let's try to insert the value */
1677   offset = gtk_tree_path_get_indices (real_path)[gtk_tree_path_get_depth (real_path) - 1];
1678
1679   /* update the offsets, yes if we didn't insert the node above, there will
1680    * be a gap here. This will be filled with the node (via fetch_child) when
1681    * it becomes visible
1682    */
1683   for (i = 0; i < level->array->len; i++)
1684     {
1685       FilterElt *e = &g_array_index (level->array, FilterElt, i);
1686       if ((e->offset >= offset))
1687         e->offset++;
1688     }
1689
1690   /* only insert when visible */
1691   if (gtk_tree_model_filter_visible (filter, &real_c_iter))
1692     {
1693       FilterElt *felt;
1694
1695       felt = gtk_tree_model_filter_insert_elt_in_level (filter,
1696                                                         &real_c_iter,
1697                                                         level, offset,
1698                                                         &i);
1699
1700       /* insert_elt_in_level defaults to FALSE */
1701       felt->visible = TRUE;
1702       level->visible_nodes++;
1703
1704       emit_row_inserted = TRUE;
1705     }
1706
1707 done:
1708   if (emit_row_inserted)
1709     gtk_tree_model_filter_emit_row_inserted_for_path (filter, c_model,
1710                                                       c_path, c_iter);
1711
1712   if (real_path)
1713     gtk_tree_path_free (real_path);
1714
1715   if (free_c_path)
1716     gtk_tree_path_free (c_path);
1717 }
1718
1719 static void
1720 gtk_tree_model_filter_row_has_child_toggled (GtkTreeModel *c_model,
1721                                              GtkTreePath  *c_path,
1722                                              GtkTreeIter  *c_iter,
1723                                              gpointer      data)
1724 {
1725   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (data);
1726   GtkTreePath *path;
1727   GtkTreeIter iter;
1728   FilterLevel *level;
1729   FilterElt *elt;
1730   gboolean requested_state;
1731
1732   g_return_if_fail (c_path != NULL && c_iter != NULL);
1733
1734   /* If we get row-has-child-toggled on the virtual root, and there is
1735    * no root level; try to build it now.
1736    */
1737   if (filter->priv->virtual_root && !filter->priv->root
1738       && !gtk_tree_path_compare (c_path, filter->priv->virtual_root))
1739     {
1740       gtk_tree_model_filter_build_level (filter, NULL, -1, TRUE);
1741       return;
1742     }
1743
1744   /* For all other levels, there is a chance that the visibility state
1745    * of the parent has changed now.
1746    */
1747
1748   path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
1749                                                                 c_path,
1750                                                                 FALSE,
1751                                                                 TRUE);
1752   if (!path)
1753     return;
1754
1755   gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (data), &iter, path);
1756
1757   level = FILTER_LEVEL (iter.user_data);
1758   elt = FILTER_ELT (iter.user_data2);
1759
1760   gtk_tree_path_free (path);
1761
1762   requested_state = gtk_tree_model_filter_visible (filter, c_iter);
1763
1764   if (!elt->visible && !requested_state)
1765     {
1766       /* The parent node currently is not visible and will not become
1767        * visible, so we will not pass on the row-has-child-toggled event.
1768        */
1769       return;
1770     }
1771   else if (elt->visible && !requested_state)
1772     {
1773       /* The node is no longer visible, so it has to be removed.
1774        * _remove_elt_from_level() takes care of emitting row-has-child-toggled
1775        * when required.
1776        */
1777       gtk_tree_model_filter_remove_elt_from_level (filter, level, elt);
1778
1779       return;
1780     }
1781   else if (!elt->visible && requested_state)
1782     {
1783       elt->visible = TRUE;
1784       level->visible_nodes++;
1785
1786       /* Only insert if the parent is visible in the target */
1787       if (gtk_tree_model_filter_elt_is_visible_in_target (level, elt))
1788         {
1789           path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
1790           gtk_tree_model_row_inserted (GTK_TREE_MODEL (filter), path, &iter);
1791           gtk_tree_path_free (path);
1792
1793           /* We do not update children now, because that will happen
1794            * below.
1795            */
1796         }
1797     }
1798   /* For the remaining possibility, elt->visible && requested_state
1799    * no action is required.
1800    */
1801
1802   /* If this node is referenced and has children, build the level so we
1803    * can monitor it for changes.
1804    */
1805   if (elt->ref_count > 1 && gtk_tree_model_iter_has_child (c_model, c_iter))
1806     gtk_tree_model_filter_build_level (filter, level,
1807                                        FILTER_LEVEL_ELT_INDEX (level, elt),
1808                                        TRUE);
1809
1810   /* get a path taking only visible nodes into account */
1811   path = gtk_tree_model_get_path (GTK_TREE_MODEL (data), &iter);
1812   gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
1813   gtk_tree_path_free (path);
1814 }
1815
1816 static void
1817 gtk_tree_model_filter_virtual_root_deleted (GtkTreeModelFilter *filter,
1818                                             GtkTreePath        *c_path)
1819 {
1820   gint i;
1821   GtkTreePath *path;
1822   FilterLevel *level = FILTER_LEVEL (filter->priv->root);
1823
1824   /* The virtual root (or one of its ancestors) has been deleted.  This
1825    * means that all content for our model is now gone.  We deal with
1826    * this by removing everything in the filter model: we just iterate
1827    * over the root level and emit a row-deleted for each FilterElt.
1828    * (FIXME: Should we emit row-deleted for child nodes as well? This
1829    * has never been fully clear in TreeModel).
1830    */
1831
1832   /* We unref the path of the virtual root, up to and not including the
1833    * deleted node which can no longer be unreffed.
1834    */
1835   gtk_tree_model_filter_unref_path (filter, filter->priv->virtual_root,
1836                                     gtk_tree_path_get_depth (c_path) - 1);
1837   filter->priv->virtual_root_deleted = TRUE;
1838
1839   if (!level)
1840     return;
1841
1842   gtk_tree_model_filter_increment_stamp (filter);
1843   path = gtk_tree_path_new ();
1844   gtk_tree_path_append_index (path, 0);
1845
1846   for (i = 0; i < level->visible_nodes; i++)
1847     gtk_tree_model_row_deleted (GTK_TREE_MODEL (filter), path);
1848
1849   gtk_tree_path_free (path);
1850
1851   /* We should not propagate the unref here.  An unref for any of these
1852    * nodes will fail, since the respective nodes in the child model are
1853    * no longer there.
1854    */
1855   gtk_tree_model_filter_free_level (filter, filter->priv->root, FALSE);
1856 }
1857
1858 static void
1859 gtk_tree_model_filter_adjust_virtual_root (GtkTreeModelFilter *filter,
1860                                            GtkTreePath        *c_path)
1861 {
1862   gint i;
1863   gint level;
1864   gint *v_indices, *c_indices;
1865   gboolean common_prefix = TRUE;
1866
1867   level = gtk_tree_path_get_depth (c_path) - 1;
1868   v_indices = gtk_tree_path_get_indices (filter->priv->virtual_root);
1869   c_indices = gtk_tree_path_get_indices (c_path);
1870
1871   for (i = 0; i < level; i++)
1872     if (v_indices[i] != c_indices[i])
1873       {
1874         common_prefix = FALSE;
1875         break;
1876       }
1877
1878   if (common_prefix && v_indices[level] > c_indices[level])
1879     (v_indices[level])--;
1880 }
1881
1882 static void
1883 gtk_tree_model_filter_row_deleted_invisible_node (GtkTreeModelFilter *filter,
1884                                                   GtkTreePath        *c_path)
1885 {
1886   int i;
1887   int offset;
1888   GtkTreePath *real_path;
1889   FilterLevel *level;
1890   FilterElt *elt;
1891
1892   /* The node deleted in the child model is not visible in the
1893    * filter model.  We will not emit a signal, just fixup the offsets
1894    * of the other nodes.
1895    */
1896
1897   if (!filter->priv->root)
1898     return;
1899
1900   level = FILTER_LEVEL (filter->priv->root);
1901
1902   /* subtract vroot if necessary */
1903   if (filter->priv->virtual_root)
1904     {
1905       real_path = gtk_tree_model_filter_remove_root (c_path,
1906                                                      filter->priv->virtual_root);
1907       /* we don't handle this */
1908       if (!real_path)
1909         return;
1910     }
1911   else
1912     real_path = gtk_tree_path_copy (c_path);
1913
1914   if (gtk_tree_path_get_depth (real_path) - 1 >= 1)
1915     {
1916       gboolean found = FALSE;
1917       GtkTreePath *parent = gtk_tree_path_copy (real_path);
1918       gtk_tree_path_up (parent);
1919
1920       found = find_elt_with_offset (filter, parent, &level, &elt);
1921
1922       gtk_tree_path_free (parent);
1923
1924       if (!found)
1925         {
1926           /* parent is filtered out, so no level */
1927           gtk_tree_path_free (real_path);
1928           return;
1929         }
1930
1931       level = elt->children;
1932     }
1933
1934   offset = gtk_tree_path_get_indices (real_path)[gtk_tree_path_get_depth (real_path) - 1];
1935   gtk_tree_path_free (real_path);
1936
1937   if (!level)
1938     return;
1939
1940   /* decrease offset of all nodes following the deleted node */
1941   for (i = 0; i < level->array->len; i++)
1942     {
1943       elt = &g_array_index (level->array, FilterElt, i);
1944       if (elt->offset > offset)
1945         elt->offset--;
1946       if (elt->children)
1947         elt->children->parent_elt_index = i;
1948     }
1949 }
1950
1951 static void
1952 gtk_tree_model_filter_row_deleted (GtkTreeModel *c_model,
1953                                    GtkTreePath  *c_path,
1954                                    gpointer      data)
1955 {
1956   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (data);
1957   GtkTreePath *path;
1958   GtkTreeIter iter;
1959   FilterElt *elt;
1960   FilterLevel *level, *parent_level = NULL;
1961   gboolean emit_child_toggled = FALSE;
1962   gboolean emit_row_deleted = FALSE;
1963   gint offset;
1964   gint i;
1965   gint parent_elt_index = -1;
1966
1967   g_return_if_fail (c_path != NULL);
1968
1969   /* special case the deletion of an ancestor of the virtual root */
1970   if (filter->priv->virtual_root &&
1971       (gtk_tree_path_is_ancestor (c_path, filter->priv->virtual_root) ||
1972        !gtk_tree_path_compare (c_path, filter->priv->virtual_root)))
1973     {
1974       gtk_tree_model_filter_virtual_root_deleted (filter, c_path);
1975       return;
1976     }
1977
1978   /* adjust the virtual root for the deleted row */
1979   if (filter->priv->virtual_root &&
1980       gtk_tree_path_get_depth (filter->priv->virtual_root) >=
1981       gtk_tree_path_get_depth (c_path))
1982     gtk_tree_model_filter_adjust_virtual_root (filter, c_path);
1983
1984   path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
1985                                                                 c_path,
1986                                                                 FALSE,
1987                                                                 FALSE);
1988
1989   if (!path)
1990     {
1991       gtk_tree_model_filter_row_deleted_invisible_node (filter, c_path);
1992       return;
1993     }
1994
1995   /* a node was deleted, which was in our cache */
1996   gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (data), &iter, path);
1997
1998   level = FILTER_LEVEL (iter.user_data);
1999   elt = FILTER_ELT (iter.user_data2);
2000   offset = elt->offset;
2001
2002   if (elt->visible)
2003     {
2004       /* get a path taking only visible nodes into account */
2005       gtk_tree_path_free (path);
2006       path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
2007
2008       level->visible_nodes--;
2009
2010       if (level->visible_nodes == 0)
2011         {
2012           emit_child_toggled = TRUE;
2013           parent_level = level->parent_level;
2014           parent_elt_index = level->parent_elt_index;
2015         }
2016
2017       emit_row_deleted = TRUE;
2018     }
2019
2020   /* Release the references on this node, without propagation because
2021    * the node does not exist anymore in the child model.  The filter
2022    * model's references on the node in case of level->parent or use
2023    * of a virtual root are automatically destroyed by the child model.
2024    */
2025   while (elt->ref_count > 0)
2026     gtk_tree_model_filter_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
2027
2028   if (level->array->len == 1)
2029     {
2030       /* kill level */
2031       gtk_tree_model_filter_free_level (filter, level, FALSE);
2032     }
2033   else
2034     {
2035       FilterElt *tmp;
2036
2037       /* remove the row */
2038       tmp = bsearch_elt_with_offset (level->array, elt->offset, &i);
2039
2040       offset = tmp->offset;
2041       g_array_remove_index (level->array, i);
2042
2043       i--;
2044       for (i = MAX (i, 0); i < level->array->len; i++)
2045         {
2046           elt = &g_array_index (level->array, FilterElt, i);
2047           if (elt->offset > offset)
2048             elt->offset--;
2049           if (elt->children)
2050             elt->children->parent_elt_index = i;
2051         }
2052     }
2053
2054   if (emit_row_deleted)
2055     {
2056       /* emit row_deleted */
2057       gtk_tree_model_filter_increment_stamp (filter);
2058       gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
2059       iter.stamp = filter->priv->stamp;
2060     }
2061
2062   if (emit_child_toggled && parent_level)
2063     {
2064       GtkTreeIter iter2;
2065       GtkTreePath *path2;
2066
2067       iter2.stamp = filter->priv->stamp;
2068       iter2.user_data = parent_level;
2069       iter2.user_data2 = &g_array_index (parent_level->array, FilterElt, parent_elt_index);
2070
2071       /* We set in_row_deleted to TRUE to avoid a level build triggered
2072        * by row-has-child-toggled (parent model could call iter_has_child
2073        * for example).
2074        */
2075       filter->priv->in_row_deleted = TRUE;
2076       path2 = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter2);
2077       gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (filter),
2078                                             path2, &iter2);
2079       gtk_tree_path_free (path2);
2080       filter->priv->in_row_deleted = FALSE;
2081     }
2082
2083   gtk_tree_path_free (path);
2084 }
2085
2086 static void
2087 gtk_tree_model_filter_rows_reordered (GtkTreeModel *c_model,
2088                                       GtkTreePath  *c_path,
2089                                       GtkTreeIter  *c_iter,
2090                                       gint         *new_order,
2091                                       gpointer      data)
2092 {
2093   FilterElt *elt;
2094   FilterLevel *level;
2095   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (data);
2096
2097   GtkTreePath *path;
2098   GtkTreeIter iter;
2099
2100   gint *tmp_array;
2101   gint i, j, elt_count;
2102   gint length;
2103
2104   GArray *new_array;
2105
2106   g_return_if_fail (new_order != NULL);
2107
2108   if (c_path == NULL || gtk_tree_path_get_depth (c_path) == 0)
2109     {
2110       length = gtk_tree_model_iter_n_children (c_model, NULL);
2111
2112       if (filter->priv->virtual_root)
2113         {
2114           gint new_pos = -1;
2115
2116           /* reorder root level of path */
2117           for (i = 0; i < length; i++)
2118             if (new_order[i] == gtk_tree_path_get_indices (filter->priv->virtual_root)[0])
2119               new_pos = i;
2120
2121           if (new_pos < 0)
2122             return;
2123
2124           gtk_tree_path_get_indices (filter->priv->virtual_root)[0] = new_pos;
2125           return;
2126         }
2127
2128       path = gtk_tree_path_new ();
2129       level = FILTER_LEVEL (filter->priv->root);
2130     }
2131   else
2132     {
2133       GtkTreeIter child_iter;
2134
2135       /* virtual root anchor reordering */
2136       if (filter->priv->virtual_root &&
2137           gtk_tree_path_is_ancestor (c_path, filter->priv->virtual_root))
2138         {
2139           gint new_pos = -1;
2140           gint length;
2141           gint level;
2142           GtkTreeIter real_c_iter;
2143
2144           level = gtk_tree_path_get_depth (c_path);
2145
2146           if (c_iter)
2147             real_c_iter = *c_iter;
2148           else
2149             gtk_tree_model_get_iter (c_model, &real_c_iter, c_path);
2150
2151           length = gtk_tree_model_iter_n_children (c_model, &real_c_iter);
2152
2153           for (i = 0; i < length; i++)
2154             if (new_order[i] == gtk_tree_path_get_indices (filter->priv->virtual_root)[level])
2155               new_pos = i;
2156
2157           if (new_pos < 0)
2158             return;
2159
2160           gtk_tree_path_get_indices (filter->priv->virtual_root)[level] = new_pos;
2161           return;
2162         }
2163
2164       path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
2165                                                                     c_path,
2166                                                                     FALSE,
2167                                                                     FALSE);
2168
2169       if (!path && filter->priv->virtual_root &&
2170           gtk_tree_path_compare (c_path, filter->priv->virtual_root))
2171         return;
2172
2173       if (!path && !filter->priv->virtual_root)
2174         return;
2175
2176       if (!path)
2177         {
2178           /* root level mode */
2179           if (!c_iter)
2180             gtk_tree_model_get_iter (c_model, c_iter, c_path);
2181           length = gtk_tree_model_iter_n_children (c_model, c_iter);
2182           path = gtk_tree_path_new ();
2183           level = FILTER_LEVEL (filter->priv->root);
2184         }
2185       else
2186         {
2187           gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (data),
2188                                                &iter, path);
2189
2190           level = FILTER_LEVEL (iter.user_data);
2191           elt = FILTER_ELT (iter.user_data2);
2192
2193           if (!elt->children)
2194             {
2195               gtk_tree_path_free (path);
2196               return;
2197             }
2198
2199           level = elt->children;
2200
2201           gtk_tree_model_filter_convert_iter_to_child_iter (GTK_TREE_MODEL_FILTER (filter), &child_iter, &iter);
2202           length = gtk_tree_model_iter_n_children (c_model, &child_iter);
2203         }
2204     }
2205
2206   if (!level || level->array->len < 1)
2207     {
2208       gtk_tree_path_free (path);
2209       return;
2210     }
2211
2212   /* NOTE: we do not bail out here if level->array->len < 2 like
2213    * GtkTreeModelSort does. This because we do some special tricky
2214    * reordering.
2215    */
2216
2217   /* construct a new array */
2218   new_array = g_array_sized_new (FALSE, FALSE, sizeof (FilterElt),
2219                                  level->array->len);
2220   tmp_array = g_new (gint, level->array->len);
2221
2222   for (i = 0, elt_count = 0; i < length; i++)
2223     {
2224       FilterElt *e = NULL;
2225       gint old_offset = -1;
2226
2227       for (j = 0; j < level->array->len; j++)
2228         if (g_array_index (level->array, FilterElt, j).offset == new_order[i])
2229           {
2230             e = &g_array_index (level->array, FilterElt, j);
2231             old_offset = j;
2232             break;
2233           }
2234
2235       if (!e)
2236         continue;
2237
2238       tmp_array[elt_count] = old_offset;
2239       g_array_append_val (new_array, *e);
2240       g_array_index (new_array, FilterElt, elt_count).offset = i;
2241       elt_count++;
2242     }
2243
2244   g_array_free (level->array, TRUE);
2245   level->array = new_array;
2246
2247   /* fix up stuff */
2248   for (i = 0; i < level->array->len; i++)
2249     {
2250       FilterElt *e = &g_array_index (level->array, FilterElt, i);
2251       if (e->children)
2252         e->children->parent_elt_index = i;
2253     }
2254
2255   /* emit rows_reordered */
2256   if (!gtk_tree_path_get_indices (path))
2257     gtk_tree_model_rows_reordered (GTK_TREE_MODEL (data), path, NULL,
2258                                    tmp_array);
2259   else
2260     {
2261       /* get a path taking only visible nodes into account */
2262       gtk_tree_path_free (path);
2263       path = gtk_tree_model_get_path (GTK_TREE_MODEL (data), &iter);
2264
2265       gtk_tree_model_rows_reordered (GTK_TREE_MODEL (data), path, &iter,
2266                                      tmp_array);
2267     }
2268
2269   /* done */
2270   g_free (tmp_array);
2271   gtk_tree_path_free (path);
2272 }
2273
2274 /* TreeModelIface implementation */
2275 static GtkTreeModelFlags
2276 gtk_tree_model_filter_get_flags (GtkTreeModel *model)
2277 {
2278   GtkTreeModelFlags flags;
2279
2280   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), 0);
2281   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL, 0);
2282
2283   flags = gtk_tree_model_get_flags (GTK_TREE_MODEL_FILTER (model)->priv->child_model);
2284
2285   if ((flags & GTK_TREE_MODEL_LIST_ONLY) == GTK_TREE_MODEL_LIST_ONLY)
2286     return GTK_TREE_MODEL_LIST_ONLY;
2287
2288   return 0;
2289 }
2290
2291 static gint
2292 gtk_tree_model_filter_get_n_columns (GtkTreeModel *model)
2293 {
2294   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2295
2296   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), 0);
2297   g_return_val_if_fail (filter->priv->child_model != NULL, 0);
2298
2299   if (filter->priv->child_model == NULL)
2300     return 0;
2301
2302   /* so we can't modify the modify func after this ... */
2303   filter->priv->modify_func_set = TRUE;
2304
2305   if (filter->priv->modify_n_columns > 0)
2306     return filter->priv->modify_n_columns;
2307
2308   return gtk_tree_model_get_n_columns (filter->priv->child_model);
2309 }
2310
2311 static GType
2312 gtk_tree_model_filter_get_column_type (GtkTreeModel *model,
2313                                        gint          index)
2314 {
2315   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2316
2317   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), G_TYPE_INVALID);
2318   g_return_val_if_fail (filter->priv->child_model != NULL, G_TYPE_INVALID);
2319
2320   /* so we can't modify the modify func after this ... */
2321   filter->priv->modify_func_set = TRUE;
2322
2323   if (filter->priv->modify_types)
2324     {
2325       g_return_val_if_fail (index < filter->priv->modify_n_columns, G_TYPE_INVALID);
2326
2327       return filter->priv->modify_types[index];
2328     }
2329
2330   return gtk_tree_model_get_column_type (filter->priv->child_model, index);
2331 }
2332
2333 /* A special case of _get_iter; this function can also get iters which
2334  * are not visible.  These iters should ONLY be passed internally, never
2335  * pass those along with a signal emission.
2336  */
2337 static gboolean
2338 gtk_tree_model_filter_get_iter_full (GtkTreeModel *model,
2339                                      GtkTreeIter  *iter,
2340                                      GtkTreePath  *path)
2341 {
2342   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2343   gint *indices;
2344   FilterLevel *level;
2345   FilterElt *elt;
2346   gint depth, i;
2347   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
2348   g_return_val_if_fail (filter->priv->child_model != NULL, FALSE);
2349
2350   indices = gtk_tree_path_get_indices (path);
2351
2352   if (filter->priv->root == NULL)
2353     gtk_tree_model_filter_build_level (filter, NULL, -1, FALSE);
2354   level = FILTER_LEVEL (filter->priv->root);
2355
2356   depth = gtk_tree_path_get_depth (path);
2357   if (!depth)
2358     {
2359       iter->stamp = 0;
2360       return FALSE;
2361     }
2362
2363   for (i = 0; i < depth - 1; i++)
2364     {
2365       if (!level || indices[i] >= level->array->len)
2366         {
2367           iter->stamp = 0;
2368           return FALSE;
2369         }
2370
2371       elt = gtk_tree_model_filter_get_nth (filter, level, indices[i]);
2372
2373       if (!elt->children)
2374         gtk_tree_model_filter_build_level (filter, level,
2375                                            FILTER_LEVEL_ELT_INDEX (level, elt),
2376                                            FALSE);
2377       level = elt->children;
2378     }
2379
2380   if (!level || indices[i] >= level->array->len)
2381     {
2382       iter->stamp = 0;
2383       return FALSE;
2384     }
2385
2386   iter->stamp = filter->priv->stamp;
2387   iter->user_data = level;
2388
2389   elt = gtk_tree_model_filter_get_nth (filter, level, indices[depth - 1]);
2390   iter->user_data2 = elt;
2391
2392   return TRUE;
2393 }
2394
2395 static gboolean
2396 gtk_tree_model_filter_get_iter (GtkTreeModel *model,
2397                                 GtkTreeIter  *iter,
2398                                 GtkTreePath  *path)
2399 {
2400   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2401   gint *indices;
2402   FilterLevel *level;
2403   FilterElt *elt;
2404   gint depth, i;
2405   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
2406   g_return_val_if_fail (filter->priv->child_model != NULL, FALSE);
2407
2408   indices = gtk_tree_path_get_indices (path);
2409
2410   if (filter->priv->root == NULL)
2411     gtk_tree_model_filter_build_level (filter, NULL, -1, FALSE);
2412   level = FILTER_LEVEL (filter->priv->root);
2413
2414   depth = gtk_tree_path_get_depth (path);
2415   if (!depth)
2416     {
2417       iter->stamp = 0;
2418       return FALSE;
2419     }
2420
2421   for (i = 0; i < depth - 1; i++)
2422     {
2423       if (!level || indices[i] >= level->visible_nodes)
2424         {
2425           iter->stamp = 0;
2426           return FALSE;
2427         }
2428
2429       elt = gtk_tree_model_filter_get_nth_visible (filter, level, indices[i]);
2430
2431       if (!elt->children)
2432         gtk_tree_model_filter_build_level (filter, level,
2433                                            FILTER_LEVEL_ELT_INDEX (level, elt),
2434                                            FALSE);
2435       level = elt->children;
2436     }
2437
2438   if (!level || indices[i] >= level->visible_nodes)
2439     {
2440       iter->stamp = 0;
2441       return FALSE;
2442     }
2443
2444   iter->stamp = filter->priv->stamp;
2445   iter->user_data = level;
2446
2447   elt = gtk_tree_model_filter_get_nth_visible (filter, level,
2448                                                indices[depth - 1]);
2449   iter->user_data2 = elt;
2450
2451   return TRUE;
2452 }
2453
2454 static GtkTreePath *
2455 gtk_tree_model_filter_get_path (GtkTreeModel *model,
2456                                 GtkTreeIter  *iter)
2457 {
2458   GtkTreePath *retval;
2459   FilterLevel *level;
2460   FilterElt *elt;
2461   gint elt_index;
2462
2463   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), NULL);
2464   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL, NULL);
2465   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == iter->stamp, NULL);
2466
2467   level = iter->user_data;
2468   elt = iter->user_data2;
2469   elt_index = FILTER_LEVEL_ELT_INDEX (level, elt);
2470
2471   if (!elt->visible)
2472     return NULL;
2473
2474   retval = gtk_tree_path_new ();
2475
2476   while (level)
2477     {
2478       int i = 0, index = 0;
2479
2480       while (i < elt_index)
2481         {
2482           if (g_array_index (level->array, FilterElt, i).visible)
2483             index++;
2484           i++;
2485
2486           g_assert (i < level->array->len);
2487         }
2488
2489       gtk_tree_path_prepend_index (retval, index);
2490       elt_index = level->parent_elt_index;
2491       level = level->parent_level;
2492     }
2493
2494   return retval;
2495 }
2496
2497 static void
2498 gtk_tree_model_filter_real_modify (GtkTreeModelFilter *self,
2499                                    GtkTreeModel       *child_model,
2500                                    GtkTreeIter        *iter,
2501                                    GValue             *value,
2502                                    gint                column)
2503 {
2504   if (self->priv->modify_func)
2505     {
2506       g_return_if_fail (column < self->priv->modify_n_columns);
2507
2508       g_value_init (value, self->priv->modify_types[column]);
2509       self->priv->modify_func (GTK_TREE_MODEL (self),
2510                            iter,
2511                            value,
2512                            column,
2513                            self->priv->modify_data);
2514     }
2515   else
2516     {
2517       GtkTreeIter child_iter;
2518
2519       gtk_tree_model_filter_convert_iter_to_child_iter (
2520           GTK_TREE_MODEL_FILTER (self), &child_iter, iter);
2521       gtk_tree_model_get_value (child_model,
2522           &child_iter, column, value);
2523     }
2524 }
2525
2526 static void
2527 gtk_tree_model_filter_get_value (GtkTreeModel *model,
2528                                  GtkTreeIter  *iter,
2529                                  gint          column,
2530                                  GValue       *value)
2531 {
2532   GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (model);
2533
2534   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (model));
2535   g_return_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL);
2536   g_return_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == iter->stamp);
2537
2538   GTK_TREE_MODEL_FILTER_GET_CLASS (model)->modify (filter,
2539       filter->priv->child_model, iter, value, column);
2540 }
2541
2542 static gboolean
2543 gtk_tree_model_filter_iter_next (GtkTreeModel *model,
2544                                  GtkTreeIter  *iter)
2545 {
2546   int i;
2547   FilterLevel *level;
2548   FilterElt *elt;
2549
2550   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
2551   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL, FALSE);
2552   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == iter->stamp, FALSE);
2553
2554   level = iter->user_data;
2555   elt = iter->user_data2;
2556
2557   i = elt - FILTER_ELT (level->array->data);
2558
2559   while (i < level->array->len - 1)
2560     {
2561       i++;
2562       elt++;
2563
2564       if (elt->visible)
2565         {
2566           iter->user_data2 = elt;
2567           return TRUE;
2568         }
2569     }
2570
2571   /* no next visible iter */
2572   iter->stamp = 0;
2573
2574   return FALSE;
2575 }
2576
2577 static gboolean
2578 gtk_tree_model_filter_iter_previous (GtkTreeModel *model,
2579                                      GtkTreeIter  *iter)
2580 {
2581   int i;
2582   FilterLevel *level;
2583   FilterElt *elt;
2584
2585   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
2586   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL, FALSE);
2587   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == iter->stamp, FALSE);
2588
2589   level = iter->user_data;
2590   elt = iter->user_data2;
2591
2592   i = elt - FILTER_ELT (level->array->data);
2593
2594   while (i > 0)
2595     {
2596       i--;
2597       elt--;
2598
2599       if (elt->visible)
2600         {
2601           iter->user_data2 = elt;
2602           return TRUE;
2603         }
2604     }
2605
2606   /* no previous visible iter */
2607   iter->stamp = 0;
2608
2609   return FALSE;
2610 }
2611
2612 static gboolean
2613 gtk_tree_model_filter_iter_children (GtkTreeModel *model,
2614                                      GtkTreeIter  *iter,
2615                                      GtkTreeIter  *parent)
2616 {
2617   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2618   FilterLevel *level;
2619
2620   iter->stamp = 0;
2621   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
2622   g_return_val_if_fail (filter->priv->child_model != NULL, FALSE);
2623   if (parent)
2624     g_return_val_if_fail (filter->priv->stamp == parent->stamp, FALSE);
2625
2626   if (!parent)
2627     {
2628       int i = 0;
2629
2630       if (!filter->priv->root)
2631         gtk_tree_model_filter_build_level (filter, NULL, -1, FALSE);
2632       if (!filter->priv->root)
2633         return FALSE;
2634
2635       level = filter->priv->root;
2636
2637       if (!level->visible_nodes)
2638         return FALSE;
2639
2640       iter->stamp = filter->priv->stamp;
2641       iter->user_data = level;
2642
2643       while (i < level->array->len)
2644         {
2645           if (!g_array_index (level->array, FilterElt, i).visible)
2646             {
2647               i++;
2648               continue;
2649             }
2650
2651           iter->user_data2 = &g_array_index (level->array, FilterElt, i);
2652           return TRUE;
2653         }
2654
2655       iter->stamp = 0;
2656       return FALSE;
2657     }
2658   else
2659     {
2660       int i = 0;
2661       FilterElt *elt;
2662
2663       elt = FILTER_ELT (parent->user_data2);
2664
2665       if (elt->children == NULL)
2666         gtk_tree_model_filter_build_level (filter,
2667                                            FILTER_LEVEL (parent->user_data),
2668                                            FILTER_LEVEL_ELT_INDEX (parent->user_data, elt),
2669                                            FALSE);
2670
2671       if (elt->children == NULL)
2672         return FALSE;
2673
2674       if (elt->children->visible_nodes <= 0)
2675         return FALSE;
2676
2677       iter->stamp = filter->priv->stamp;
2678       iter->user_data = elt->children;
2679
2680       level = FILTER_LEVEL (iter->user_data);
2681
2682       while (i < level->array->len)
2683         {
2684           if (!g_array_index (level->array, FilterElt, i).visible)
2685             {
2686               i++;
2687               continue;
2688             }
2689
2690           iter->user_data2 = &g_array_index (level->array, FilterElt, i);
2691           return TRUE;
2692         }
2693
2694       iter->stamp = 0;
2695       return FALSE;
2696     }
2697
2698   iter->stamp = 0;
2699   return FALSE;
2700 }
2701
2702 static gboolean
2703 gtk_tree_model_filter_iter_has_child (GtkTreeModel *model,
2704                                       GtkTreeIter  *iter)
2705 {
2706   GtkTreeIter child_iter;
2707   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2708   FilterElt *elt;
2709
2710   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
2711   g_return_val_if_fail (filter->priv->child_model != NULL, FALSE);
2712   g_return_val_if_fail (filter->priv->stamp == iter->stamp, FALSE);
2713
2714   filter = GTK_TREE_MODEL_FILTER (model);
2715
2716   gtk_tree_model_filter_convert_iter_to_child_iter (GTK_TREE_MODEL_FILTER (model), &child_iter, iter);
2717   elt = FILTER_ELT (iter->user_data2);
2718
2719   if (!elt->visible)
2720     return FALSE;
2721
2722   /* we need to build the level to check if not all children are filtered
2723    * out
2724    */
2725   if (!elt->children
2726       && gtk_tree_model_iter_has_child (filter->priv->child_model, &child_iter))
2727     gtk_tree_model_filter_build_level (filter, FILTER_LEVEL (iter->user_data),
2728                                        FILTER_LEVEL_ELT_INDEX (iter->user_data, elt),
2729                                        FALSE);
2730
2731   if (elt->children && elt->children->visible_nodes > 0)
2732     return TRUE;
2733
2734   return FALSE;
2735 }
2736
2737 static gint
2738 gtk_tree_model_filter_iter_n_children (GtkTreeModel *model,
2739                                        GtkTreeIter  *iter)
2740 {
2741   GtkTreeIter child_iter;
2742   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2743   FilterElt *elt;
2744
2745   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), 0);
2746   g_return_val_if_fail (filter->priv->child_model != NULL, 0);
2747   if (iter)
2748     g_return_val_if_fail (filter->priv->stamp == iter->stamp, 0);
2749
2750   if (!iter)
2751     {
2752       if (!filter->priv->root)
2753         gtk_tree_model_filter_build_level (filter, NULL, -1, FALSE);
2754
2755       if (filter->priv->root)
2756         return FILTER_LEVEL (filter->priv->root)->visible_nodes;
2757
2758       return 0;
2759     }
2760
2761   elt = FILTER_ELT (iter->user_data2);
2762
2763   if (!elt->visible)
2764     return 0;
2765
2766   gtk_tree_model_filter_convert_iter_to_child_iter (GTK_TREE_MODEL_FILTER (model), &child_iter, iter);
2767
2768   if (!elt->children &&
2769       gtk_tree_model_iter_has_child (filter->priv->child_model, &child_iter))
2770     gtk_tree_model_filter_build_level (filter,
2771                                        FILTER_LEVEL (iter->user_data),
2772                                        FILTER_LEVEL_ELT_INDEX (iter->user_data, elt),
2773                                        FALSE);
2774
2775   if (elt->children)
2776     return elt->children->visible_nodes;
2777
2778   return 0;
2779 }
2780
2781 static gboolean
2782 gtk_tree_model_filter_iter_nth_child (GtkTreeModel *model,
2783                                       GtkTreeIter  *iter,
2784                                       GtkTreeIter  *parent,
2785                                       gint          n)
2786 {
2787   FilterElt *elt;
2788   FilterLevel *level;
2789   GtkTreeIter children;
2790
2791   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
2792   if (parent)
2793     g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == parent->stamp, FALSE);
2794
2795   /* use this instead of has_child to force us to build the level, if needed */
2796   if (gtk_tree_model_filter_iter_children (model, &children, parent) == FALSE)
2797     {
2798       iter->stamp = 0;
2799       return FALSE;
2800     }
2801
2802   level = children.user_data;
2803   elt = FILTER_ELT (level->array->data);
2804
2805   if (n >= level->visible_nodes)
2806     {
2807       iter->stamp = 0;
2808       return FALSE;
2809     }
2810
2811   elt = gtk_tree_model_filter_get_nth_visible (GTK_TREE_MODEL_FILTER (model),
2812                                                level, n);
2813
2814   iter->stamp = GTK_TREE_MODEL_FILTER (model)->priv->stamp;
2815   iter->user_data = level;
2816   iter->user_data2 = elt;
2817
2818   return TRUE;
2819 }
2820
2821 static gboolean
2822 gtk_tree_model_filter_iter_parent (GtkTreeModel *model,
2823                                    GtkTreeIter  *iter,
2824                                    GtkTreeIter  *child)
2825 {
2826   FilterLevel *level;
2827
2828   iter->stamp = 0;
2829   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (model), FALSE);
2830   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL, FALSE);
2831   g_return_val_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == child->stamp, FALSE);
2832
2833   level = child->user_data;
2834
2835   if (level->parent_level)
2836     {
2837       iter->stamp = GTK_TREE_MODEL_FILTER (model)->priv->stamp;
2838       iter->user_data = level->parent_level;
2839       iter->user_data2 = FILTER_LEVEL_PARENT_ELT (level);
2840
2841       return TRUE;
2842     }
2843
2844   return FALSE;
2845 }
2846
2847 static void
2848 gtk_tree_model_filter_ref_node (GtkTreeModel *model,
2849                                 GtkTreeIter  *iter)
2850 {
2851   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2852   GtkTreeIter child_iter;
2853   FilterLevel *level;
2854   FilterElt *elt;
2855
2856   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (model));
2857   g_return_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->child_model != NULL);
2858   g_return_if_fail (GTK_TREE_MODEL_FILTER (model)->priv->stamp == iter->stamp);
2859
2860   gtk_tree_model_filter_convert_iter_to_child_iter (GTK_TREE_MODEL_FILTER (model), &child_iter, iter);
2861
2862   gtk_tree_model_ref_node (filter->priv->child_model, &child_iter);
2863
2864   level = iter->user_data;
2865   elt = iter->user_data2;
2866
2867   elt->ref_count++;
2868   level->ref_count++;
2869   if (level->ref_count == 1)
2870     {
2871       FilterLevel *parent_level = level->parent_level;
2872       gint parent_elt_index = level->parent_elt_index;
2873
2874       /* we were at zero -- time to decrease the zero_ref_count val */
2875       while (parent_level)
2876         {
2877           g_array_index (parent_level->array, FilterElt, parent_elt_index).zero_ref_count--;
2878
2879           parent_elt_index = parent_level->parent_elt_index;
2880           parent_level = parent_level->parent_level;
2881         }
2882
2883       if (filter->priv->root != level)
2884         filter->priv->zero_ref_count--;
2885     }
2886 }
2887
2888 static void
2889 gtk_tree_model_filter_unref_node (GtkTreeModel *model,
2890                                   GtkTreeIter  *iter)
2891 {
2892   gtk_tree_model_filter_real_unref_node (model, iter, TRUE);
2893 }
2894
2895 static void
2896 gtk_tree_model_filter_real_unref_node (GtkTreeModel *model,
2897                                        GtkTreeIter  *iter,
2898                                        gboolean      propagate_unref)
2899 {
2900   GtkTreeModelFilter *filter = (GtkTreeModelFilter *)model;
2901   FilterLevel *level;
2902   FilterElt *elt;
2903
2904   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (model));
2905   g_return_if_fail (filter->priv->child_model != NULL);
2906   g_return_if_fail (filter->priv->stamp == iter->stamp);
2907
2908   if (propagate_unref)
2909     {
2910       GtkTreeIter child_iter;
2911       gtk_tree_model_filter_convert_iter_to_child_iter (GTK_TREE_MODEL_FILTER (model), &child_iter, iter);
2912       gtk_tree_model_unref_node (filter->priv->child_model, &child_iter);
2913     }
2914
2915   level = iter->user_data;
2916   elt = iter->user_data2;
2917
2918   g_return_if_fail (elt->ref_count > 0);
2919
2920   elt->ref_count--;
2921   level->ref_count--;
2922   if (level->ref_count == 0)
2923     {
2924       FilterLevel *parent_level = level->parent_level;
2925       gint parent_elt_index = level->parent_elt_index;
2926
2927       /* we are at zero -- time to increase the zero_ref_count val */
2928       while (parent_level)
2929         {
2930           g_array_index (parent_level->array, FilterElt, parent_elt_index).zero_ref_count++;
2931
2932           parent_elt_index = parent_level->parent_elt_index;
2933           parent_level = parent_level->parent_level;
2934         }
2935
2936       if (filter->priv->root != level)
2937         filter->priv->zero_ref_count++;
2938     }
2939 }
2940
2941 /* TreeDragSource interface implementation */
2942 static gboolean
2943 gtk_tree_model_filter_row_draggable (GtkTreeDragSource *drag_source,
2944                                      GtkTreePath       *path)
2945 {
2946   GtkTreeModelFilter *tree_model_filter = (GtkTreeModelFilter *)drag_source;
2947   GtkTreePath *child_path;
2948   gboolean draggable;
2949
2950   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (drag_source), FALSE);
2951   g_return_val_if_fail (path != NULL, FALSE);
2952
2953   child_path = gtk_tree_model_filter_convert_path_to_child_path (tree_model_filter, path);
2954   draggable = gtk_tree_drag_source_row_draggable (GTK_TREE_DRAG_SOURCE (tree_model_filter->priv->child_model), child_path);
2955   gtk_tree_path_free (child_path);
2956
2957   return draggable;
2958 }
2959
2960 static gboolean
2961 gtk_tree_model_filter_drag_data_get (GtkTreeDragSource *drag_source,
2962                                      GtkTreePath       *path,
2963                                      GtkSelectionData  *selection_data)
2964 {
2965   GtkTreeModelFilter *tree_model_filter = (GtkTreeModelFilter *)drag_source;
2966   GtkTreePath *child_path;
2967   gboolean gotten;
2968
2969   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (drag_source), FALSE);
2970   g_return_val_if_fail (path != NULL, FALSE);
2971
2972   child_path = gtk_tree_model_filter_convert_path_to_child_path (tree_model_filter, path);
2973   gotten = gtk_tree_drag_source_drag_data_get (GTK_TREE_DRAG_SOURCE (tree_model_filter->priv->child_model), child_path, selection_data);
2974   gtk_tree_path_free (child_path);
2975
2976   return gotten;
2977 }
2978
2979 static gboolean
2980 gtk_tree_model_filter_drag_data_delete (GtkTreeDragSource *drag_source,
2981                                         GtkTreePath       *path)
2982 {
2983   GtkTreeModelFilter *tree_model_filter = (GtkTreeModelFilter *)drag_source;
2984   GtkTreePath *child_path;
2985   gboolean deleted;
2986
2987   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (drag_source), FALSE);
2988   g_return_val_if_fail (path != NULL, FALSE);
2989
2990   child_path = gtk_tree_model_filter_convert_path_to_child_path (tree_model_filter, path);
2991   deleted = gtk_tree_drag_source_drag_data_delete (GTK_TREE_DRAG_SOURCE (tree_model_filter->priv->child_model), child_path);
2992   gtk_tree_path_free (child_path);
2993
2994   return deleted;
2995 }
2996
2997 /* bits and pieces */
2998 static void
2999 gtk_tree_model_filter_set_model (GtkTreeModelFilter *filter,
3000                                  GtkTreeModel       *child_model)
3001 {
3002   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3003
3004   if (filter->priv->child_model)
3005     {
3006       g_signal_handler_disconnect (filter->priv->child_model,
3007                                    filter->priv->changed_id);
3008       g_signal_handler_disconnect (filter->priv->child_model,
3009                                    filter->priv->inserted_id);
3010       g_signal_handler_disconnect (filter->priv->child_model,
3011                                    filter->priv->has_child_toggled_id);
3012       g_signal_handler_disconnect (filter->priv->child_model,
3013                                    filter->priv->deleted_id);
3014       g_signal_handler_disconnect (filter->priv->child_model,
3015                                    filter->priv->reordered_id);
3016
3017       /* reset our state */
3018       if (filter->priv->root)
3019         gtk_tree_model_filter_free_level (filter, filter->priv->root, TRUE);
3020
3021       filter->priv->root = NULL;
3022       g_object_unref (filter->priv->child_model);
3023       filter->priv->visible_column = -1;
3024
3025       /* FIXME: do we need to destroy more here? */
3026     }
3027
3028   filter->priv->child_model = child_model;
3029
3030   if (child_model)
3031     {
3032       g_object_ref (filter->priv->child_model);
3033       filter->priv->changed_id =
3034         g_signal_connect (child_model, "row-changed",
3035                           G_CALLBACK (gtk_tree_model_filter_row_changed),
3036                           filter);
3037       filter->priv->inserted_id =
3038         g_signal_connect (child_model, "row-inserted",
3039                           G_CALLBACK (gtk_tree_model_filter_row_inserted),
3040                           filter);
3041       filter->priv->has_child_toggled_id =
3042         g_signal_connect (child_model, "row-has-child-toggled",
3043                           G_CALLBACK (gtk_tree_model_filter_row_has_child_toggled),
3044                           filter);
3045       filter->priv->deleted_id =
3046         g_signal_connect (child_model, "row-deleted",
3047                           G_CALLBACK (gtk_tree_model_filter_row_deleted),
3048                           filter);
3049       filter->priv->reordered_id =
3050         g_signal_connect (child_model, "rows-reordered",
3051                           G_CALLBACK (gtk_tree_model_filter_rows_reordered),
3052                           filter);
3053
3054       filter->priv->child_flags = gtk_tree_model_get_flags (child_model);
3055       filter->priv->stamp = g_random_int ();
3056     }
3057 }
3058
3059 static void
3060 gtk_tree_model_filter_ref_path (GtkTreeModelFilter *filter,
3061                                 GtkTreePath        *path)
3062 {
3063   int len;
3064   GtkTreePath *p;
3065
3066   len = gtk_tree_path_get_depth (path);
3067   p = gtk_tree_path_copy (path);
3068   while (len--)
3069     {
3070       GtkTreeIter iter;
3071
3072       gtk_tree_model_get_iter (GTK_TREE_MODEL (filter->priv->child_model), &iter, p);
3073       gtk_tree_model_ref_node (GTK_TREE_MODEL (filter->priv->child_model), &iter);
3074       gtk_tree_path_up (p);
3075     }
3076
3077   gtk_tree_path_free (p);
3078 }
3079
3080 static void
3081 gtk_tree_model_filter_unref_path (GtkTreeModelFilter *filter,
3082                                   GtkTreePath        *path,
3083                                   int                 depth)
3084 {
3085   int len;
3086   GtkTreePath *p;
3087
3088   if (depth != -1)
3089     len = depth;
3090   else
3091     len = gtk_tree_path_get_depth (path);
3092
3093   p = gtk_tree_path_copy (path);
3094   while (len--)
3095     {
3096       GtkTreeIter iter;
3097
3098       gtk_tree_model_get_iter (GTK_TREE_MODEL (filter->priv->child_model), &iter, p);
3099       gtk_tree_model_unref_node (GTK_TREE_MODEL (filter->priv->child_model), &iter);
3100       gtk_tree_path_up (p);
3101     }
3102
3103   gtk_tree_path_free (p);
3104 }
3105
3106 static void
3107 gtk_tree_model_filter_set_root (GtkTreeModelFilter *filter,
3108                                 GtkTreePath        *root)
3109 {
3110   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3111
3112   if (!root)
3113     filter->priv->virtual_root = NULL;
3114   else
3115     filter->priv->virtual_root = gtk_tree_path_copy (root);
3116 }
3117
3118 /* public API */
3119
3120 /**
3121  * gtk_tree_model_filter_new:
3122  * @child_model: A #GtkTreeModel.
3123  * @root: (allow-none): A #GtkTreePath or %NULL.
3124  *
3125  * Creates a new #GtkTreeModel, with @child_model as the child_model
3126  * and @root as the virtual root.
3127  *
3128  * Return value: (transfer full): A new #GtkTreeModel.
3129  *
3130  * Since: 2.4
3131  */
3132 GtkTreeModel *
3133 gtk_tree_model_filter_new (GtkTreeModel *child_model,
3134                            GtkTreePath  *root)
3135 {
3136   GtkTreeModel *retval;
3137   GtkTreeModelFilter *filter;
3138
3139   g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);
3140
3141   retval = g_object_new (GTK_TYPE_TREE_MODEL_FILTER,
3142                          "child-model", child_model,
3143                          "virtual-root", root,
3144                          NULL);
3145
3146   filter = GTK_TREE_MODEL_FILTER (retval);
3147   if (filter->priv->virtual_root)
3148     {
3149       gtk_tree_model_filter_ref_path (filter, filter->priv->virtual_root);
3150       filter->priv->virtual_root_deleted = FALSE;
3151     }
3152
3153   return retval;
3154 }
3155
3156 /**
3157  * gtk_tree_model_filter_get_model:
3158  * @filter: A #GtkTreeModelFilter.
3159  *
3160  * Returns a pointer to the child model of @filter.
3161  *
3162  * Return value: (transfer none): A pointer to a #GtkTreeModel.
3163  *
3164  * Since: 2.4
3165  */
3166 GtkTreeModel *
3167 gtk_tree_model_filter_get_model (GtkTreeModelFilter *filter)
3168 {
3169   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (filter), NULL);
3170
3171   return filter->priv->child_model;
3172 }
3173
3174 /**
3175  * gtk_tree_model_filter_set_visible_func:
3176  * @filter: A #GtkTreeModelFilter.
3177  * @func: A #GtkTreeModelFilterVisibleFunc, the visible function.
3178  * @data: (allow-none): User data to pass to the visible function, or %NULL.
3179  * @destroy: (allow-none): Destroy notifier of @data, or %NULL.
3180  *
3181  * Sets the visible function used when filtering the @filter to be @func. The
3182  * function should return %TRUE if the given row should be visible and
3183  * %FALSE otherwise.
3184  *
3185  * If the condition calculated by the function changes over time (e.g. because
3186  * it depends on some global parameters), you must call
3187  * gtk_tree_model_filter_refilter() to keep the visibility information of
3188  * the model uptodate.
3189  *
3190  * Note that @func is called whenever a row is inserted, when it may still be
3191  * empty. The visible function should therefore take special care of empty
3192  * rows, like in the example below.
3193  *
3194  * <informalexample><programlisting>
3195  * static gboolean
3196  * visible_func (GtkTreeModel *model,
3197  *               GtkTreeIter  *iter,
3198  *               gpointer      data)
3199  * {
3200  *   /&ast; Visible if row is non-empty and first column is "HI" &ast;/
3201  *   gchar *str;
3202  *   gboolean visible = FALSE;
3203  *
3204  *   gtk_tree_model_get (model, iter, 0, &str, -1);
3205  *   if (str && strcmp (str, "HI") == 0)
3206  *     visible = TRUE;
3207  *   g_free (str);
3208  *
3209  *   return visible;
3210  * }
3211  * </programlisting></informalexample>
3212  *
3213  * Since: 2.4
3214  */
3215 void
3216 gtk_tree_model_filter_set_visible_func (GtkTreeModelFilter            *filter,
3217                                         GtkTreeModelFilterVisibleFunc  func,
3218                                         gpointer                       data,
3219                                         GDestroyNotify                 destroy)
3220 {
3221   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3222   g_return_if_fail (func != NULL);
3223   g_return_if_fail (filter->priv->visible_method_set == FALSE);
3224
3225   filter->priv->visible_func = func;
3226   filter->priv->visible_data = data;
3227   filter->priv->visible_destroy = destroy;
3228
3229   filter->priv->visible_method_set = TRUE;
3230 }
3231
3232 /**
3233  * gtk_tree_model_filter_set_modify_func:
3234  * @filter: A #GtkTreeModelFilter.
3235  * @n_columns: The number of columns in the filter model.
3236  * @types: (array length=n_columns): The #GType<!-- -->s of the columns.
3237  * @func: A #GtkTreeModelFilterModifyFunc
3238  * @data: (allow-none): User data to pass to the modify function, or %NULL.
3239  * @destroy: (allow-none): Destroy notifier of @data, or %NULL.
3240  *
3241  * With the @n_columns and @types parameters, you give an array of column
3242  * types for this model (which will be exposed to the parent model/view).
3243  * The @func, @data and @destroy parameters are for specifying the modify
3244  * function. The modify function will get called for <emphasis>each</emphasis>
3245  * data access, the goal of the modify function is to return the data which
3246  * should be displayed at the location specified using the parameters of the
3247  * modify function.
3248  *
3249  * Since: 2.4
3250  */
3251 void
3252 gtk_tree_model_filter_set_modify_func (GtkTreeModelFilter           *filter,
3253                                        gint                          n_columns,
3254                                        GType                        *types,
3255                                        GtkTreeModelFilterModifyFunc  func,
3256                                        gpointer                      data,
3257                                        GDestroyNotify                destroy)
3258 {
3259   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3260   g_return_if_fail (func != NULL);
3261   g_return_if_fail (filter->priv->modify_func_set == FALSE);
3262
3263   if (filter->priv->modify_destroy)
3264     {
3265       GDestroyNotify d = filter->priv->modify_destroy;
3266
3267       filter->priv->modify_destroy = NULL;
3268       d (filter->priv->modify_data);
3269     }
3270
3271   filter->priv->modify_n_columns = n_columns;
3272   filter->priv->modify_types = g_new0 (GType, n_columns);
3273   memcpy (filter->priv->modify_types, types, sizeof (GType) * n_columns);
3274   filter->priv->modify_func = func;
3275   filter->priv->modify_data = data;
3276   filter->priv->modify_destroy = destroy;
3277
3278   filter->priv->modify_func_set = TRUE;
3279 }
3280
3281 /**
3282  * gtk_tree_model_filter_set_visible_column:
3283  * @filter: A #GtkTreeModelFilter.
3284  * @column: A #gint which is the column containing the visible information.
3285  *
3286  * Sets @column of the child_model to be the column where @filter should
3287  * look for visibility information. @columns should be a column of type
3288  * %G_TYPE_BOOLEAN, where %TRUE means that a row is visible, and %FALSE
3289  * if not.
3290  *
3291  * Since: 2.4
3292  */
3293 void
3294 gtk_tree_model_filter_set_visible_column (GtkTreeModelFilter *filter,
3295                                           gint column)
3296 {
3297   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3298   g_return_if_fail (column >= 0);
3299   g_return_if_fail (filter->priv->visible_method_set == FALSE);
3300
3301   filter->priv->visible_column = column;
3302
3303   filter->priv->visible_method_set = TRUE;
3304 }
3305
3306 /* conversion */
3307
3308 /**
3309  * gtk_tree_model_filter_convert_child_iter_to_iter:
3310  * @filter: A #GtkTreeModelFilter.
3311  * @filter_iter: (out): An uninitialized #GtkTreeIter.
3312  * @child_iter: A valid #GtkTreeIter pointing to a row on the child model.
3313  *
3314  * Sets @filter_iter to point to the row in @filter that corresponds to the
3315  * row pointed at by @child_iter.  If @filter_iter was not set, %FALSE is
3316  * returned.
3317  *
3318  * Return value: %TRUE, if @filter_iter was set, i.e. if @child_iter is a
3319  * valid iterator pointing to a visible row in child model.
3320  *
3321  * Since: 2.4
3322  */
3323 gboolean
3324 gtk_tree_model_filter_convert_child_iter_to_iter (GtkTreeModelFilter *filter,
3325                                                   GtkTreeIter        *filter_iter,
3326                                                   GtkTreeIter        *child_iter)
3327 {
3328   gboolean ret;
3329   GtkTreePath *child_path, *path;
3330
3331   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (filter), FALSE);
3332   g_return_val_if_fail (filter->priv->child_model != NULL, FALSE);
3333   g_return_val_if_fail (filter_iter != NULL, FALSE);
3334   g_return_val_if_fail (child_iter != NULL, FALSE);
3335   g_return_val_if_fail (filter_iter != child_iter, FALSE);
3336
3337   filter_iter->stamp = 0;
3338
3339   child_path = gtk_tree_model_get_path (filter->priv->child_model, child_iter);
3340   g_return_val_if_fail (child_path != NULL, FALSE);
3341
3342   path = gtk_tree_model_filter_convert_child_path_to_path (filter,
3343                                                            child_path);
3344   gtk_tree_path_free (child_path);
3345
3346   if (!path)
3347     return FALSE;
3348
3349   ret = gtk_tree_model_get_iter (GTK_TREE_MODEL (filter), filter_iter, path);
3350   gtk_tree_path_free (path);
3351
3352   return ret;
3353 }
3354
3355 /**
3356  * gtk_tree_model_filter_convert_iter_to_child_iter:
3357  * @filter: A #GtkTreeModelFilter.
3358  * @child_iter: (out): An uninitialized #GtkTreeIter.
3359  * @filter_iter: A valid #GtkTreeIter pointing to a row on @filter.
3360  *
3361  * Sets @child_iter to point to the row pointed to by @filter_iter.
3362  *
3363  * Since: 2.4
3364  */
3365 void
3366 gtk_tree_model_filter_convert_iter_to_child_iter (GtkTreeModelFilter *filter,
3367                                                   GtkTreeIter        *child_iter,
3368                                                   GtkTreeIter        *filter_iter)
3369 {
3370   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3371   g_return_if_fail (filter->priv->child_model != NULL);
3372   g_return_if_fail (child_iter != NULL);
3373   g_return_if_fail (filter_iter != NULL);
3374   g_return_if_fail (filter_iter->stamp == filter->priv->stamp);
3375   g_return_if_fail (filter_iter != child_iter);
3376
3377   if (GTK_TREE_MODEL_FILTER_CACHE_CHILD_ITERS (filter))
3378     {
3379       *child_iter = FILTER_ELT (filter_iter->user_data2)->iter;
3380     }
3381   else
3382     {
3383       GtkTreePath *path;
3384       gboolean valid = FALSE;
3385
3386       path = gtk_tree_model_filter_elt_get_path (filter_iter->user_data,
3387                                                  filter_iter->user_data2,
3388                                                  filter->priv->virtual_root);
3389       valid = gtk_tree_model_get_iter (filter->priv->child_model, child_iter,
3390                                        path);
3391       gtk_tree_path_free (path);
3392
3393       g_return_if_fail (valid == TRUE);
3394     }
3395 }
3396
3397 /* The path returned can only be used internally in the filter model. */
3398 static GtkTreePath *
3399 gtk_real_tree_model_filter_convert_child_path_to_path (GtkTreeModelFilter *filter,
3400                                                        GtkTreePath        *child_path,
3401                                                        gboolean            build_levels,
3402                                                        gboolean            fetch_children)
3403 {
3404   gint *child_indices;
3405   GtkTreePath *retval;
3406   GtkTreePath *real_path;
3407   FilterLevel *level;
3408   FilterElt *tmp;
3409   gint i;
3410
3411   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (filter), NULL);
3412   g_return_val_if_fail (filter->priv->child_model != NULL, NULL);
3413   g_return_val_if_fail (child_path != NULL, NULL);
3414
3415   if (!filter->priv->virtual_root)
3416     real_path = gtk_tree_path_copy (child_path);
3417   else
3418     real_path = gtk_tree_model_filter_remove_root (child_path,
3419                                                    filter->priv->virtual_root);
3420
3421   if (!real_path)
3422     return NULL;
3423
3424   retval = gtk_tree_path_new ();
3425   child_indices = gtk_tree_path_get_indices (real_path);
3426
3427   if (filter->priv->root == NULL && build_levels)
3428     gtk_tree_model_filter_build_level (filter, NULL, -1, FALSE);
3429   level = FILTER_LEVEL (filter->priv->root);
3430
3431   for (i = 0; i < gtk_tree_path_get_depth (real_path); i++)
3432     {
3433       gint j;
3434       gboolean found_child = FALSE;
3435
3436       if (!level)
3437         {
3438           gtk_tree_path_free (real_path);
3439           gtk_tree_path_free (retval);
3440           return NULL;
3441         }
3442
3443       tmp = bsearch_elt_with_offset (level->array, child_indices[i], &j);
3444       if (tmp)
3445         {
3446           gtk_tree_path_append_index (retval, j);
3447           if (!tmp->children && build_levels)
3448             gtk_tree_model_filter_build_level (filter, level,
3449                                                FILTER_LEVEL_ELT_INDEX (level, tmp),
3450                                                FALSE);
3451           level = tmp->children;
3452           found_child = TRUE;
3453         }
3454
3455       if (!found_child && fetch_children)
3456         {
3457           tmp = gtk_tree_model_filter_fetch_child (filter, level,
3458                                                    child_indices[i],
3459                                                    &j);
3460
3461           /* didn't find the child, let's try to bring it back */
3462           if (!tmp || tmp->offset != child_indices[i])
3463             {
3464               /* not there */
3465               gtk_tree_path_free (real_path);
3466               gtk_tree_path_free (retval);
3467               return NULL;
3468             }
3469
3470           gtk_tree_path_append_index (retval, j);
3471           if (!tmp->children && build_levels)
3472             gtk_tree_model_filter_build_level (filter, level,
3473                                                FILTER_LEVEL_ELT_INDEX (level, tmp),
3474                                                FALSE);
3475           level = tmp->children;
3476           found_child = TRUE;
3477         }
3478       else if (!found_child && !fetch_children)
3479         {
3480           /* no path */
3481           gtk_tree_path_free (real_path);
3482           gtk_tree_path_free (retval);
3483           return NULL;
3484         }
3485     }
3486
3487   gtk_tree_path_free (real_path);
3488   return retval;
3489 }
3490
3491 /**
3492  * gtk_tree_model_filter_convert_child_path_to_path:
3493  * @filter: A #GtkTreeModelFilter.
3494  * @child_path: A #GtkTreePath to convert.
3495  *
3496  * Converts @child_path to a path relative to @filter. That is, @child_path
3497  * points to a path in the child model. The rerturned path will point to the
3498  * same row in the filtered model. If @child_path isn't a valid path on the
3499  * child model or points to a row which is not visible in @filter, then %NULL
3500  * is returned.
3501  *
3502  * Return value: A newly allocated #GtkTreePath, or %NULL.
3503  *
3504  * Since: 2.4
3505  */
3506 GtkTreePath *
3507 gtk_tree_model_filter_convert_child_path_to_path (GtkTreeModelFilter *filter,
3508                                                   GtkTreePath        *child_path)
3509 {
3510   GtkTreeIter iter;
3511   GtkTreePath *path;
3512
3513   /* this function does the sanity checks */
3514   path = gtk_real_tree_model_filter_convert_child_path_to_path (filter,
3515                                                                 child_path,
3516                                                                 TRUE,
3517                                                                 TRUE);
3518
3519   if (!path)
3520       return NULL;
3521
3522   /* get a new path which only takes visible nodes into account.
3523    * -- if this gives any performance issues, we can write a special
3524    *    version of convert_child_path_to_path immediately returning
3525    *    a visible-nodes-only path.
3526    */
3527   gtk_tree_model_filter_get_iter_full (GTK_TREE_MODEL (filter), &iter, path);
3528
3529   gtk_tree_path_free (path);
3530   path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter), &iter);
3531
3532   return path;
3533 }
3534
3535 /**
3536  * gtk_tree_model_filter_convert_path_to_child_path:
3537  * @filter: A #GtkTreeModelFilter.
3538  * @filter_path: A #GtkTreePath to convert.
3539  *
3540  * Converts @filter_path to a path on the child model of @filter. That is,
3541  * @filter_path points to a location in @filter. The returned path will
3542  * point to the same location in the model not being filtered. If @filter_path
3543  * does not point to a location in the child model, %NULL is returned.
3544  *
3545  * Return value: A newly allocated #GtkTreePath, or %NULL.
3546  *
3547  * Since: 2.4
3548  */
3549 GtkTreePath *
3550 gtk_tree_model_filter_convert_path_to_child_path (GtkTreeModelFilter *filter,
3551                                                   GtkTreePath        *filter_path)
3552 {
3553   gint *filter_indices;
3554   GtkTreePath *retval;
3555   FilterLevel *level;
3556   gint i;
3557
3558   g_return_val_if_fail (GTK_IS_TREE_MODEL_FILTER (filter), NULL);
3559   g_return_val_if_fail (filter->priv->child_model != NULL, NULL);
3560   g_return_val_if_fail (filter_path != NULL, NULL);
3561
3562   /* convert path */
3563   retval = gtk_tree_path_new ();
3564   filter_indices = gtk_tree_path_get_indices (filter_path);
3565   if (!filter->priv->root)
3566     gtk_tree_model_filter_build_level (filter, NULL, -1, FALSE);
3567   level = FILTER_LEVEL (filter->priv->root);
3568
3569   for (i = 0; i < gtk_tree_path_get_depth (filter_path); i++)
3570     {
3571       FilterElt *elt;
3572
3573       if (!level || level->visible_nodes <= filter_indices[i])
3574         {
3575           gtk_tree_path_free (retval);
3576           return NULL;
3577         }
3578
3579       elt = gtk_tree_model_filter_get_nth_visible (filter, level,
3580                                                    filter_indices[i]);
3581
3582       if (elt->children == NULL)
3583         gtk_tree_model_filter_build_level (filter, level,
3584                                            FILTER_LEVEL_ELT_INDEX (level, elt),
3585                                            FALSE);
3586
3587       if (!level || level->visible_nodes <= filter_indices[i])
3588         {
3589           gtk_tree_path_free (retval);
3590           return NULL;
3591         }
3592
3593       gtk_tree_path_append_index (retval, elt->offset);
3594       level = elt->children;
3595     }
3596
3597   /* apply vroot */
3598
3599   if (filter->priv->virtual_root)
3600     {
3601       GtkTreePath *real_retval;
3602
3603       real_retval = gtk_tree_model_filter_add_root (retval,
3604                                                     filter->priv->virtual_root);
3605       gtk_tree_path_free (retval);
3606
3607       return real_retval;
3608     }
3609
3610   return retval;
3611 }
3612
3613 static gboolean
3614 gtk_tree_model_filter_refilter_helper (GtkTreeModel *model,
3615                                        GtkTreePath  *path,
3616                                        GtkTreeIter  *iter,
3617                                        gpointer      data)
3618 {
3619   /* evil, don't try this at home, but certainly speeds things up */
3620   gtk_tree_model_filter_row_changed (model, path, iter, data);
3621
3622   return FALSE;
3623 }
3624
3625 /**
3626  * gtk_tree_model_filter_refilter:
3627  * @filter: A #GtkTreeModelFilter.
3628  *
3629  * Emits ::row_changed for each row in the child model, which causes
3630  * the filter to re-evaluate whether a row is visible or not.
3631  *
3632  * Since: 2.4
3633  */
3634 void
3635 gtk_tree_model_filter_refilter (GtkTreeModelFilter *filter)
3636 {
3637   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3638
3639   /* S L O W */
3640   gtk_tree_model_foreach (filter->priv->child_model,
3641                           gtk_tree_model_filter_refilter_helper,
3642                           filter);
3643 }
3644
3645 /**
3646  * gtk_tree_model_filter_clear_cache:
3647  * @filter: A #GtkTreeModelFilter.
3648  *
3649  * This function should almost never be called. It clears the @filter
3650  * of any cached iterators that haven't been reffed with
3651  * gtk_tree_model_ref_node(). This might be useful if the child model
3652  * being filtered is static (and doesn't change often) and there has been
3653  * a lot of unreffed access to nodes. As a side effect of this function,
3654  * all unreffed iters will be invalid.
3655  *
3656  * Since: 2.4
3657  */
3658 void
3659 gtk_tree_model_filter_clear_cache (GtkTreeModelFilter *filter)
3660 {
3661   g_return_if_fail (GTK_IS_TREE_MODEL_FILTER (filter));
3662
3663   if (filter->priv->zero_ref_count > 0)
3664     gtk_tree_model_filter_clear_cache_helper (filter,
3665                                               FILTER_LEVEL (filter->priv->root));
3666 }