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

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