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

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