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