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