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