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

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