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

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