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