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

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