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