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

   1 /* gtktreemodelsort.c
   2  * Copyright (C) 2000,2001  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
   3  * Copyright (C) 2001,2002  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 /* NOTE: There is a potential for confusion in this code as to whether an iter,
  22  * path or value refers to the GtkTreeModelSort model, or the child model being
  23  * sorted.  As a convention, variables referencing the child model will have an
  24  * s_ prefix before them (ie. s_iter, s_value, s_path);
  25  */
  26
  27 /* ITER FORMAT:
  28  *
  29  * iter->stamp = tree_model_sort->stamp
  30  * iter->user_data = SortLevel
  31  * iter->user_data2 = SortElt
  32  */
  33
  34 /* WARNING: this code is dangerous, can cause sleepless nights,
  35  * can cause your dog to die among other bad things
  36  *
  37  * we warned you and we're not liable for any head injuries.
  38  */
  39
  40 #include <config.h>
  41 #include <string.h>
  42
  43 #include "gtktreemodelsort.h"
  44 #include "gtktreesortable.h"
  45 #include "gtktreestore.h"
  46 #include "gtktreedatalist.h"
  47 #include "gtkintl.h"
  48 #include "gtkprivate.h"
  49 #include "gtktreednd.h"
  50 #include "gtkalias.h"
  51
  52 typedef struct _SortElt SortElt;
  53 typedef struct _SortLevel SortLevel;
  54 typedef struct _SortData SortData;
  55 typedef struct _SortTuple SortTuple;
  56
  57 struct _SortElt
  58 {
  59   GtkTreeIter  iter;
  60   SortLevel   *children;
  61   gint         offset;
  62   gint         ref_count;
  63   gint         zero_ref_count;
  64 };
  65
  66 struct _SortLevel
  67 {
  68   GArray    *array;
  69   gint       ref_count;
  70   SortElt   *parent_elt;
  71   SortLevel *parent_level;
  72 };
  73
  74 struct _SortData
  75 {
  76   GtkTreeModelSort *tree_model_sort;
  77   GtkTreePath *parent_path;
  78   gint parent_path_depth;
  79   gint *parent_path_indices;
  80   GtkTreeIterCompareFunc sort_func;
  81   gpointer sort_data;
  82 };
  83
  84 struct _SortTuple
  85 {
  86   SortElt   *elt;
  87   gint       offset;
  88 };
  89
  90 /* Properties */
  91 enum {
  92   PROP_0,
  93   /* Construct args */
  94   PROP_MODEL
  95 };
  96
  97
  98
  99 #define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) \
 100         (((GtkTreeModelSort *)tree_model_sort)->child_flags&GTK_TREE_MODEL_ITERS_PERSIST)
 101 #define SORT_ELT(sort_elt) ((SortElt *)sort_elt)
 102 #define SORT_LEVEL(sort_level) ((SortLevel *)sort_level)
 103
 104 #define GET_CHILD_ITER(tree_model_sort,ch_iter,so_iter) gtk_tree_model_sort_convert_iter_to_child_iter((GtkTreeModelSort*)(tree_model_sort), (ch_iter), (so_iter));
 105
 106 #define NO_SORT_FUNC ((GtkTreeIterCompareFunc) 0x1)
 107
 108 #define VALID_ITER(iter, tree_model_sort) ((iter) != NULL && (iter)->user_data != NULL && (iter)->user_data2 != NULL && (tree_model_sort)->stamp == (iter)->stamp)
 109
 110 /* general (object/interface init, etc) */
 111 static void gtk_tree_model_sort_tree_model_init       (GtkTreeModelIface     *iface);
 112 static void gtk_tree_model_sort_tree_sortable_init    (GtkTreeSortableIface  *iface);
 113 static void gtk_tree_model_sort_drag_source_init      (GtkTreeDragSourceIface*iface);
 114 static void gtk_tree_model_sort_finalize              (GObject               *object);
 115 static void gtk_tree_model_sort_set_property          (GObject               *object,
 116                                                        guint                  prop_id,
 117                                                        const GValue          *value,
 118                                                        GParamSpec            *pspec);
 119 static void gtk_tree_model_sort_get_property          (GObject               *object,
 120                                                        guint                  prop_id,
 121                                                        GValue                *value,
 122                                                        GParamSpec            *pspec);
 123
 124 /* our signal handlers */
 125 static void gtk_tree_model_sort_row_changed           (GtkTreeModel          *model,
 126                                                        GtkTreePath           *start_path,
 127                                                        GtkTreeIter           *start_iter,
 128                                                        gpointer               data);
 129 static void gtk_tree_model_sort_row_inserted          (GtkTreeModel          *model,
 130                                                        GtkTreePath           *path,
 131                                                        GtkTreeIter           *iter,
 132                                                        gpointer               data);
 133 static void gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel          *model,
 134                                                        GtkTreePath           *path,
 135                                                        GtkTreeIter           *iter,
 136                                                        gpointer               data);
 137 static void gtk_tree_model_sort_row_deleted           (GtkTreeModel          *model,
 138                                                        GtkTreePath           *path,
 139                                                        gpointer               data);
 140 static void gtk_tree_model_sort_rows_reordered        (GtkTreeModel          *s_model,
 141                                                        GtkTreePath           *s_path,
 142                                                        GtkTreeIter           *s_iter,
 143                                                        gint                  *new_order,
 144                                                        gpointer               data);
 145
 146 /* TreeModel interface */
 147 static GtkTreeModelFlags gtk_tree_model_sort_get_flags     (GtkTreeModel          *tree_model);
 148 static gint         gtk_tree_model_sort_get_n_columns      (GtkTreeModel          *tree_model);
 149 static GType        gtk_tree_model_sort_get_column_type    (GtkTreeModel          *tree_model,
 150                                                             gint                   index);
 151 static gboolean     gtk_tree_model_sort_get_iter           (GtkTreeModel          *tree_model,
 152                                                             GtkTreeIter           *iter,
 153                                                             GtkTreePath           *path);
 154 static GtkTreePath *gtk_tree_model_sort_get_path           (GtkTreeModel          *tree_model,
 155                                                             GtkTreeIter           *iter);
 156 static void         gtk_tree_model_sort_get_value          (GtkTreeModel          *tree_model,
 157                                                             GtkTreeIter           *iter,
 158                                                             gint                   column,
 159                                                             GValue                *value);
 160 static gboolean     gtk_tree_model_sort_iter_next          (GtkTreeModel          *tree_model,
 161                                                             GtkTreeIter           *iter);
 162 static gboolean     gtk_tree_model_sort_iter_children      (GtkTreeModel          *tree_model,
 163                                                             GtkTreeIter           *iter,
 164                                                             GtkTreeIter           *parent);
 165 static gboolean     gtk_tree_model_sort_iter_has_child     (GtkTreeModel          *tree_model,
 166                                                             GtkTreeIter           *iter);
 167 static gint         gtk_tree_model_sort_iter_n_children    (GtkTreeModel          *tree_model,
 168                                                             GtkTreeIter           *iter);
 169 static gboolean     gtk_tree_model_sort_iter_nth_child     (GtkTreeModel          *tree_model,
 170                                                             GtkTreeIter           *iter,
 171                                                             GtkTreeIter           *parent,
 172                                                             gint                   n);
 173 static gboolean     gtk_tree_model_sort_iter_parent        (GtkTreeModel          *tree_model,
 174                                                             GtkTreeIter           *iter,
 175                                                             GtkTreeIter           *child);
 176 static void         gtk_tree_model_sort_ref_node           (GtkTreeModel          *tree_model,
 177                                                             GtkTreeIter           *iter);
 178 static void         gtk_tree_model_sort_real_unref_node    (GtkTreeModel          *tree_model,
 179                                                             GtkTreeIter           *iter,
 180                                                             gboolean               propagate_unref);
 181 static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
 182                                                             GtkTreeIter           *iter);
 183
 184 /* TreeDragSource interface */
 185 static gboolean     gtk_tree_model_sort_row_draggable         (GtkTreeDragSource      *drag_source,
 186                                                                GtkTreePath            *path);
 187 static gboolean     gtk_tree_model_sort_drag_data_get         (GtkTreeDragSource      *drag_source,
 188                                                                GtkTreePath            *path,
 189                                                                GtkSelectionData       *selection_data);
 190 static gboolean     gtk_tree_model_sort_drag_data_delete      (GtkTreeDragSource      *drag_source,
 191                                                                GtkTreePath            *path);
 192
 193 /* TreeSortable interface */
 194 static gboolean     gtk_tree_model_sort_get_sort_column_id    (GtkTreeSortable        *sortable,
 195                                                                gint                   *sort_column_id,
 196                                                                GtkSortType            *order);
 197 static void         gtk_tree_model_sort_set_sort_column_id    (GtkTreeSortable        *sortable,
 198                                                                gint                    sort_column_id,
 199                                                                GtkSortType        order);
 200 static void         gtk_tree_model_sort_set_sort_func         (GtkTreeSortable        *sortable,
 201                                                                gint                    sort_column_id,
 202                                                                GtkTreeIterCompareFunc  func,
 203                                                                gpointer                data,
 204                                                                GtkDestroyNotify        destroy);
 205 static void         gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
 206                                                                GtkTreeIterCompareFunc  func,
 207                                                                gpointer                data,
 208                                                                GtkDestroyNotify        destroy);
 209 static gboolean     gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable     *sortable);
 210
 211 /* Private functions (sort funcs, level handling and other utils) */
 212 static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,
 213                                                            SortLevel        *parent_level,
 214                                                            SortElt          *parent_elt);
 215 static void         gtk_tree_model_sort_free_level        (GtkTreeModelSort *tree_model_sort,
 216                                                            SortLevel        *sort_level);
 217 static void         gtk_tree_model_sort_increment_stamp   (GtkTreeModelSort *tree_model_sort);
 218 static void         gtk_tree_model_sort_sort_level        (GtkTreeModelSort *tree_model_sort,
 219                                                            SortLevel        *level,
 220                                                            gboolean          recurse,
 221                                                            gboolean          emit_reordered);
 222 static void         gtk_tree_model_sort_sort              (GtkTreeModelSort *tree_model_sort);
 223 static gint         gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
 224                                                            SortLevel        *level,
 225                                                            GtkTreeIter      *iter,
 226                                                            gint             skip_index);
 227 static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
 228                                                            SortLevel        *level,
 229                                                            GtkTreePath      *s_path,
 230                                                            GtkTreeIter      *s_iter);
 231 static GtkTreePath *gtk_tree_model_sort_elt_get_path      (SortLevel        *level,
 232                                                            SortElt          *elt);
 233 static void         gtk_tree_model_sort_set_model         (GtkTreeModelSort *tree_model_sort,
 234                                                            GtkTreeModel     *child_model);
 235 static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
 236                                                                          GtkTreePath      *child_path,
 237                                                                          gboolean          build_levels);
 238
 239
 240 G_DEFINE_TYPE_WITH_CODE (GtkTreeModelSort, gtk_tree_model_sort, G_TYPE_OBJECT,
 241                          G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_MODEL,
 242                                                 gtk_tree_model_sort_tree_model_init)
 243                          G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_SORTABLE,
 244                                                 gtk_tree_model_sort_tree_sortable_init)
 245                          G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_DRAG_SOURCE,
 246                                                 gtk_tree_model_sort_drag_source_init))
 247
 248 static void
 249 gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
 250 {
 251   tree_model_sort->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
 252   tree_model_sort->stamp = 0;
 253   tree_model_sort->zero_ref_count = 0;
 254   tree_model_sort->root = NULL;
 255   tree_model_sort->sort_list = NULL;
 256 }
 257
 258 static void
 259 gtk_tree_model_sort_class_init (GtkTreeModelSortClass *class)
 260 {
 261   GObjectClass *object_class;
 262
 263   object_class = (GObjectClass *) class;
 264
 265   object_class->set_property = gtk_tree_model_sort_set_property;
 266   object_class->get_property = gtk_tree_model_sort_get_property;
 267
 268   object_class->finalize = gtk_tree_model_sort_finalize;
 269
 270   /* Properties */
 271   g_object_class_install_property (object_class,
 272                                    PROP_MODEL,
 273                                    g_param_spec_object ("model",
 274                                                         P_("TreeModelSort Model"),
 275                                                         P_("The model for the TreeModelSort to sort"),
 276                                                         GTK_TYPE_TREE_MODEL,
 277                                                         GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
 278 }
 279
 280 static void
 281 gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
 282 {
 283   iface->get_flags = gtk_tree_model_sort_get_flags;
 284   iface->get_n_columns = gtk_tree_model_sort_get_n_columns;
 285   iface->get_column_type = gtk_tree_model_sort_get_column_type;
 286   iface->get_iter = gtk_tree_model_sort_get_iter;
 287   iface->get_path = gtk_tree_model_sort_get_path;
 288   iface->get_value = gtk_tree_model_sort_get_value;
 289   iface->iter_next = gtk_tree_model_sort_iter_next;
 290   iface->iter_children = gtk_tree_model_sort_iter_children;
 291   iface->iter_has_child = gtk_tree_model_sort_iter_has_child;
 292   iface->iter_n_children = gtk_tree_model_sort_iter_n_children;
 293   iface->iter_nth_child = gtk_tree_model_sort_iter_nth_child;
 294   iface->iter_parent = gtk_tree_model_sort_iter_parent;
 295   iface->ref_node = gtk_tree_model_sort_ref_node;
 296   iface->unref_node = gtk_tree_model_sort_unref_node;
 297 }
 298
 299 static void
 300 gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface *iface)
 301 {
 302   iface->get_sort_column_id = gtk_tree_model_sort_get_sort_column_id;
 303   iface->set_sort_column_id = gtk_tree_model_sort_set_sort_column_id;
 304   iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
 305   iface->set_default_sort_func = gtk_tree_model_sort_set_default_sort_func;
 306   iface->has_default_sort_func = gtk_tree_model_sort_has_default_sort_func;
 307 }
 308
 309 static void
 310 gtk_tree_model_sort_drag_source_init (GtkTreeDragSourceIface *iface)
 311 {
 312   iface->row_draggable = gtk_tree_model_sort_row_draggable;
 313   iface->drag_data_delete = gtk_tree_model_sort_drag_data_delete;
 314   iface->drag_data_get = gtk_tree_model_sort_drag_data_get;
 315 }
 316
 317 /**
 318  * gtk_tree_model_sort_new_with_model:
 319  * @child_model: A #GtkTreeModel
 320  *
 321  * Creates a new #GtkTreeModel, with @child_model as the child model.
 322  *
 323  * Return value: A new #GtkTreeModel.
 324  */
 325 GtkTreeModel *
 326 gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
 327 {
 328   GtkTreeModel *retval;
 329
 330   g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);
 331
 332   retval = g_object_new (gtk_tree_model_sort_get_type (), NULL);
 333
 334   gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
 335
 336   return retval;
 337 }
 338
 339 /* GObject callbacks */
 340 static void
 341 gtk_tree_model_sort_finalize (GObject *object)
 342 {
 343   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
 344
 345   gtk_tree_model_sort_set_model (tree_model_sort, NULL);
 346
 347   if (tree_model_sort->root)
 348     gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
 349
 350   if (tree_model_sort->sort_list)
 351     {
 352       _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
 353       tree_model_sort->sort_list = NULL;
 354     }
 355
 356   if (tree_model_sort->default_sort_destroy)
 357     {
 358       tree_model_sort->default_sort_destroy (tree_model_sort->default_sort_data);
 359       tree_model_sort->default_sort_destroy = NULL;
 360       tree_model_sort->default_sort_data = NULL;
 361     }
 362
 363
 364   /* must chain up */
 365   G_OBJECT_CLASS (gtk_tree_model_sort_parent_class)->finalize (object);
 366 }
 367
 368 static void
 369 gtk_tree_model_sort_set_property (GObject      *object,
 370                                   guint         prop_id,
 371                                   const GValue *value,
 372                                   GParamSpec   *pspec)
 373 {
 374   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);
 375
 376   switch (prop_id)
 377     {
 378     case PROP_MODEL:
 379       gtk_tree_model_sort_set_model (tree_model_sort, g_value_get_object (value));
 380       break;
 381     default:
 382       G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
 383       break;
 384     }
 385 }
 386
 387 static void
 388 gtk_tree_model_sort_get_property (GObject    *object,
 389                                   guint       prop_id,
 390                                   GValue     *value,
 391                                   GParamSpec *pspec)
 392 {
 393   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);
 394
 395   switch (prop_id)
 396     {
 397     case PROP_MODEL:
 398       g_value_set_object (value, gtk_tree_model_sort_get_model(tree_model_sort));
 399       break;
 400     default:
 401       G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
 402       break;
 403     }
 404 }
 405
 406 static void
 407 gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
 408                                  GtkTreePath  *start_s_path,
 409                                  GtkTreeIter  *start_s_iter,
 410                                  gpointer      data)
 411 {
 412   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 413   GtkTreePath *path = NULL;
 414   GtkTreeIter iter;
 415   GtkTreeIter tmpiter;
 416
 417   SortElt tmp;
 418   SortElt *elt;
 419   SortLevel *level;
 420
 421   gboolean free_s_path = FALSE;
 422
 423   gint index = 0, old_index, i;
 424
 425   g_return_if_fail (start_s_path != NULL || start_s_iter != NULL);
 426
 427   if (!start_s_path)
 428     {
 429       free_s_path = TRUE;
 430       start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
 431     }
 432
 433   path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
 434                                                               start_s_path,
 435                                                               FALSE);
 436   if (!path)
 437     {
 438       if (free_s_path)
 439         gtk_tree_path_free (start_s_path);
 440       return;
 441     }
 442
 443   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 444   gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (data), &iter);
 445
 446   level = iter.user_data;
 447   elt = iter.user_data2;
 448
 449   if (level->array->len < 2 ||
 450       (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
 451        tree_model_sort->default_sort_func == NO_SORT_FUNC))
 452     {
 453       if (free_s_path)
 454         gtk_tree_path_free (start_s_path);
 455
 456       gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
 457       gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);
 458
 459       gtk_tree_path_free (path);
 460
 461       return;
 462     }
 463
 464   if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
 465     {
 466       gtk_tree_model_get_iter (tree_model_sort->child_model,
 467                                &tmpiter, start_s_path);
 468     }
 469
 470   old_index = elt - SORT_ELT (level->array->data);
 471
 472   memcpy (&tmp, elt, sizeof (SortElt));
 473
 474   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
 475     index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
 476                                                    level,
 477                                                    &tmp.iter,
 478                                                    old_index);
 479   else
 480     index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
 481                                                    level,
 482                                                    &tmpiter,
 483                                                    old_index);
 484
 485   if (index < old_index)
 486     {
 487       g_memmove (level->array->data + ((index + 1)*sizeof (SortElt)),
 488                  level->array->data + ((index)*sizeof (SortElt)),
 489                  (old_index - index)* sizeof(SortElt));
 490     }
 491   else if (index > old_index)
 492     {
 493       g_memmove (level->array->data + ((old_index)*sizeof (SortElt)),
 494                  level->array->data + ((old_index + 1)*sizeof (SortElt)),
 495                  (index - old_index)* sizeof(SortElt));
 496     }
 497   memcpy (level->array->data + ((index)*sizeof (SortElt)),
 498           &tmp, sizeof (SortElt));
 499
 500   for (i = 0; i < level->array->len; i++)
 501     if (g_array_index (level->array, SortElt, i).children)
 502       g_array_index (level->array, SortElt, i).children->parent_elt = &g_array_index (level->array, SortElt, i);
 503
 504   gtk_tree_path_up (path);
 505   gtk_tree_path_append_index (path, index);
 506
 507   gtk_tree_model_sort_increment_stamp (tree_model_sort);
 508
 509   /* if the item moved, then emit rows_reordered */
 510   if (old_index != index)
 511     {
 512       gint *new_order;
 513       gint j;
 514
 515       GtkTreePath *tmppath;
 516
 517       new_order = g_new (gint, level->array->len);
 518
 519       for (j = 0; j < level->array->len; j++)
 520         {
 521           if (index > old_index)
 522             {
 523               if (j == index)
 524                 new_order[j] = old_index;
 525               else if (j >= old_index && j < index)
 526                 new_order[j] = j + 1;
 527               else
 528                 new_order[j] = j;
 529             }
 530           else if (index < old_index)
 531             {
 532               if (j == index)
 533                 new_order[j] = old_index;
 534               else if (j > index && j <= old_index)
 535                 new_order[j] = j - 1;
 536               else
 537                 new_order[j] = j;
 538             }
 539           /* else? shouldn't really happen */
 540         }
 541
 542       if (level->parent_elt)
 543         {
 544           iter.stamp = tree_model_sort->stamp;
 545           iter.user_data = level->parent_level;
 546           iter.user_data2 = level->parent_elt;
 547
 548           tmppath = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort), &iter);
 549
 550           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
 551                                          tmppath, &iter, new_order);
 552         }
 553       else
 554         {
 555           /* toplevel */
 556           tmppath = gtk_tree_path_new ();
 557
 558           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), tmppath,
 559                                          NULL, new_order);
 560         }
 561
 562       gtk_tree_path_free (tmppath);
 563       g_free (new_order);
 564     }
 565
 566   /* emit row_changed signal (at new location) */
 567   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 568   gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
 569   gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);
 570
 571   gtk_tree_path_free (path);
 572   if (free_s_path)
 573     gtk_tree_path_free (start_s_path);
 574 }
 575
 576 static void
 577 gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
 578                                   GtkTreePath           *s_path,
 579                                   GtkTreeIter           *s_iter,
 580                                   gpointer               data)
 581 {
 582   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 583   GtkTreePath *path;
 584   GtkTreeIter iter;
 585   GtkTreeIter real_s_iter;
 586
 587   gint i = 0;
 588
 589   gboolean free_s_path = FALSE;
 590
 591   SortElt *elt;
 592   SortLevel *level;
 593   SortLevel *parent_level = NULL;
 594
 595   parent_level = level = SORT_LEVEL (tree_model_sort->root);
 596
 597   g_return_if_fail (s_path != NULL || s_iter != NULL);
 598
 599   if (!s_path)
 600     {
 601       s_path = gtk_tree_model_get_path (s_model, s_iter);
 602       free_s_path = TRUE;
 603     }
 604
 605   if (!s_iter)
 606     gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
 607   else
 608     real_s_iter = *s_iter;
 609
 610   if (!tree_model_sort->root)
 611     {
 612       gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
 613
 614       /* the build level already put the inserted iter in the level,
 615          so no need to handle this signal anymore */
 616
 617       goto done_and_submit;
 618     }
 619
 620   /* find the parent level */
 621   while (i < gtk_tree_path_get_depth (s_path) - 1)
 622     {
 623       gint j;
 624
 625       if (!level)
 626         {
 627           /* level not yet build, we won't cover this signal */
 628           goto done;
 629         }
 630
 631       if (level->array->len < gtk_tree_path_get_indices (s_path)[i])
 632         {
 633           g_warning ("A node was inserted with a parent that's not in the tree.\n"
 634                      "This possibly means that a GtkTreeModel inserted a child node\n"
 635                      "before the parent was inserted.");
 636           goto done;
 637         }
 638
 639       elt = NULL;
 640       for (j = 0; j < level->array->len; j++)
 641         if (g_array_index (level->array, SortElt, j).offset == gtk_tree_path_get_indices (s_path)[i])
 642           {
 643             elt = &g_array_index (level->array, SortElt, j);
 644             break;
 645           }
 646
 647       g_return_if_fail (elt != NULL);
 648
 649       if (!elt->children)
 650         {
 651           /* not covering this signal */
 652           goto done;
 653         }
 654
 655       level = elt->children;
 656       parent_level = level;
 657       i++;
 658     }
 659
 660   if (!parent_level)
 661     goto done;
 662
 663   if (level->ref_count == 0 && level != tree_model_sort->root)
 664     {
 665       gtk_tree_model_sort_free_level (tree_model_sort, level);
 666       goto done;
 667     }
 668
 669   if (!gtk_tree_model_sort_insert_value (tree_model_sort,
 670                                          parent_level,
 671                                          s_path,
 672                                          &real_s_iter))
 673     goto done;
 674
 675  done_and_submit:
 676   path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
 677                                                               s_path,
 678                                                               FALSE);
 679
 680   if (!path)
 681     return;
 682
 683   gtk_tree_model_sort_increment_stamp (tree_model_sort);
 684
 685   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 686   gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
 687   gtk_tree_path_free (path);
 688
 689  done:
 690   if (free_s_path)
 691     gtk_tree_path_free (s_path);
 692
 693   return;
 694 }
 695
 696 static void
 697 gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
 698                                            GtkTreePath  *s_path,
 699                                            GtkTreeIter  *s_iter,
 700                                            gpointer      data)
 701 {
 702   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 703   GtkTreePath *path;
 704   GtkTreeIter iter;
 705
 706   g_return_if_fail (s_path != NULL && s_iter != NULL);
 707
 708   path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
 709   if (path == NULL)
 710     return;
 711
 712   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 713   gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
 714
 715   gtk_tree_path_free (path);
 716 }
 717
 718 static void
 719 gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
 720                                  GtkTreePath  *s_path,
 721                                  gpointer      data)
 722 {
 723   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 724   GtkTreePath *path = NULL;
 725   SortElt *elt;
 726   SortLevel *level;
 727   GtkTreeIter iter;
 728   gint offset;
 729   gint i;
 730
 731   g_return_if_fail (s_path != NULL);
 732
 733   path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
 734   if (path == NULL)
 735     return;
 736
 737   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 738
 739   level = SORT_LEVEL (iter.user_data);
 740   elt = SORT_ELT (iter.user_data2);
 741   offset = elt->offset;
 742
 743   /* we _need_ to emit ::row_deleted before we start unreffing the node
 744    * itself. This is because of the row refs, which start unreffing nodes
 745    * when we emit ::row_deleted
 746    */
 747   gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
 748
 749   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 750
 751   while (elt->ref_count > 0)
 752     gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
 753
 754   if (level->ref_count == 0)
 755     {
 756       /* This will prune the level, so I can just emit the signal and
 757        * not worry about cleaning this level up.
 758        * Careful, root level is not cleaned up in increment stamp.
 759        */
 760       gtk_tree_model_sort_increment_stamp (tree_model_sort);
 761       gtk_tree_path_free (path);
 762       if (level == tree_model_sort->root)
 763         {
 764           gtk_tree_model_sort_free_level (tree_model_sort,
 765                                           tree_model_sort->root);
 766           tree_model_sort->root = NULL;
 767         }
 768       return;
 769     }
 770
 771   gtk_tree_model_sort_increment_stamp (tree_model_sort);
 772
 773   /* Remove the row */
 774   for (i = 0; i < level->array->len; i++)
 775     if (elt->offset == g_array_index (level->array, SortElt, i).offset)
 776       break;
 777
 778   g_array_remove_index (level->array, i);
 779
 780   /* update all offsets */
 781   for (i = 0; i < level->array->len; i++)
 782     {
 783       elt = & (g_array_index (level->array, SortElt, i));
 784       if (elt->offset > offset)
 785         elt->offset--;
 786       if (elt->children)
 787         elt->children->parent_elt = elt;
 788     }
 789
 790   gtk_tree_path_free (path);
 791 }
 792
 793 static void
 794 gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
 795                                     GtkTreePath  *s_path,
 796                                     GtkTreeIter  *s_iter,
 797                                     gint         *new_order,
 798                                     gpointer      data)
 799 {
 800   SortElt *elt;
 801   SortLevel *level;
 802   GtkTreeIter iter;
 803   gint *tmp_array;
 804   int i, j;
 805   GtkTreePath *path;
 806   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 807
 808   g_return_if_fail (new_order != NULL);
 809
 810   if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
 811     {
 812       if (tree_model_sort->root == NULL)
 813         return;
 814       path = gtk_tree_path_new ();
 815       level = SORT_LEVEL (tree_model_sort->root);
 816     }
 817   else
 818     {
 819       path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
 820       if (path == NULL)
 821         return;
 822       gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 823
 824       level = SORT_LEVEL (iter.user_data);
 825       elt = SORT_ELT (iter.user_data2);
 826
 827       if (!elt->children)
 828         {
 829           gtk_tree_path_free (path);
 830           return;
 831         }
 832
 833       level = elt->children;
 834     }
 835
 836   if (level->array->len < 2)
 837     {
 838       gtk_tree_path_free (path);
 839       return;
 840     }
 841
 842   tmp_array = g_new (int, level->array->len);
 843   for (i = 0; i < level->array->len; i++)
 844     {
 845       for (j = 0; j < level->array->len; j++)
 846         {
 847           if (g_array_index (level->array, SortElt, i).offset == new_order[j])
 848             tmp_array[i] = j;
 849         }
 850     }
 851
 852   for (i = 0; i < level->array->len; i++)
 853     g_array_index (level->array, SortElt, i).offset = tmp_array[i];
 854   g_free (tmp_array);
 855
 856   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
 857       tree_model_sort->default_sort_func == NO_SORT_FUNC)
 858     {
 859
 860       gtk_tree_model_sort_sort_level (tree_model_sort, level,
 861                                       FALSE, FALSE);
 862       gtk_tree_model_sort_increment_stamp (tree_model_sort);
 863
 864       if (gtk_tree_path_get_depth (path))
 865         {
 866           gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
 867                                    &iter,
 868                                    path);
 869           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
 870                                          path, &iter, new_order);
 871         }
 872       else
 873         {
 874           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
 875                                          path, NULL, new_order);
 876         }
 877     }
 878
 879   gtk_tree_path_free (path);
 880 }
 881
 882 /* Fulfill our model requirements */
 883 static GtkTreeModelFlags
 884 gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
 885 {
 886   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
 887   GtkTreeModelFlags flags;
 888
 889   g_return_val_if_fail (tree_model_sort->child_model != NULL, 0);
 890
 891   flags = gtk_tree_model_get_flags (tree_model_sort->child_model);
 892
 893   if ((flags & GTK_TREE_MODEL_LIST_ONLY) == GTK_TREE_MODEL_LIST_ONLY)
 894     return GTK_TREE_MODEL_LIST_ONLY;
 895
 896   return 0;
 897 }
 898
 899 static gint
 900 gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
 901 {
 902   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
 903
 904   if (tree_model_sort->child_model == 0)
 905     return 0;
 906
 907   return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
 908 }
 909
 910 static GType
 911 gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
 912                                      gint          index)
 913 {
 914   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
 915
 916   g_return_val_if_fail (tree_model_sort->child_model != NULL, G_TYPE_INVALID);
 917
 918   return gtk_tree_model_get_column_type (tree_model_sort->child_model, index);
 919 }
 920
 921 static gboolean
 922 gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
 923                               GtkTreeIter  *iter,
 924                               GtkTreePath  *path)
 925 {
 926   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
 927   gint *indices;
 928   SortLevel *level;
 929   gint depth, i;
 930
 931   g_return_val_if_fail (tree_model_sort->child_model != NULL, FALSE);
 932
 933   indices = gtk_tree_path_get_indices (path);
 934
 935   if (tree_model_sort->root == NULL)
 936     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
 937   level = SORT_LEVEL (tree_model_sort->root);
 938
 939   depth = gtk_tree_path_get_depth (path);
 940   if (depth == 0)
 941     return FALSE;
 942
 943   for (i = 0; i < depth - 1; i++)
 944     {
 945       if ((level == NULL) ||
 946           (indices[i] >= level->array->len))
 947         return FALSE;
 948
 949       if (g_array_index (level->array, SortElt, indices[i]).children == NULL)
 950         gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, indices[i]));
 951       level = g_array_index (level->array, SortElt, indices[i]).children;
 952     }
 953
 954   if (!level || indices[i] >= level->array->len)
 955     {
 956       iter->stamp = 0;
 957       return FALSE;
 958     }
 959
 960   iter->stamp = tree_model_sort->stamp;
 961   iter->user_data = level;
 962   iter->user_data2 = &g_array_index (level->array, SortElt, indices[depth - 1]);
 963
 964   return TRUE;
 965 }
 966
 967 static GtkTreePath *
 968 gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
 969                               GtkTreeIter  *iter)
 970 {
 971   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
 972   GtkTreePath *retval;
 973   SortLevel *level;
 974   SortElt *elt;
 975
 976   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
 977   g_return_val_if_fail (tree_model_sort->stamp == iter->stamp, NULL);
 978
 979   retval = gtk_tree_path_new ();
 980   level = iter->user_data;
 981   elt = iter->user_data2;
 982   while (level != NULL)
 983     {
 984       gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);
 985
 986       elt = level->parent_elt;
 987       level = level->parent_level;
 988     }
 989
 990   return retval;
 991 }
 992
 993 static void
 994 gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
 995                                GtkTreeIter  *iter,
 996                                gint          column,
 997                                GValue       *value)
 998 {
 999   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1000   GtkTreeIter child_iter;
1001
1002   g_return_if_fail (tree_model_sort->child_model != NULL);
1003   g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1004
1005   GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1006   gtk_tree_model_get_value (tree_model_sort->child_model,
1007                             &child_iter, column, value);
1008 }
1009
1010 static gboolean
1011 gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
1012                                GtkTreeIter  *iter)
1013 {
1014   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1015   SortLevel *level;
1016   SortElt *elt;
1017
1018   g_return_val_if_fail (tree_model_sort->child_model != NULL, FALSE);
1019   g_return_val_if_fail (tree_model_sort->stamp == iter->stamp, FALSE);
1020
1021   level = iter->user_data;
1022   elt = iter->user_data2;
1023
1024   if (elt - (SortElt *)level->array->data >= level->array->len - 1)
1025     {
1026       iter->stamp = 0;
1027       return FALSE;
1028     }
1029   iter->user_data2 = elt + 1;
1030
1031   return TRUE;
1032 }
1033
1034 static gboolean
1035 gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
1036                                    GtkTreeIter  *iter,
1037                                    GtkTreeIter  *parent)
1038 {
1039   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1040   SortLevel *level;
1041
1042   iter->stamp = 0;
1043   g_return_val_if_fail (tree_model_sort->child_model != NULL, FALSE);
1044   if (parent)
1045     g_return_val_if_fail (VALID_ITER (parent, tree_model_sort), FALSE);
1046
1047   if (parent == NULL)
1048     {
1049       if (tree_model_sort->root == NULL)
1050         gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1051       if (tree_model_sort->root == NULL)
1052         return FALSE;
1053
1054       level = tree_model_sort->root;
1055       iter->stamp = tree_model_sort->stamp;
1056       iter->user_data = level;
1057       iter->user_data2 = level->array->data;
1058     }
1059   else
1060     {
1061       if (((SortElt *)parent->user_data2)->children == NULL)
1062         gtk_tree_model_sort_build_level (tree_model_sort,
1063                                          (SortLevel *)parent->user_data,
1064                                          (SortElt *)parent->user_data2);
1065       if (((SortElt *)parent->user_data2)->children == NULL)
1066         return FALSE;
1067       iter->stamp = tree_model_sort->stamp;
1068       iter->user_data = ((SortElt *)parent->user_data2)->children;
1069       iter->user_data2 = ((SortLevel *)iter->user_data)->array->data;
1070     }
1071
1072   return TRUE;
1073 }
1074
1075 static gboolean
1076 gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
1077                                     GtkTreeIter  *iter)
1078 {
1079   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1080   GtkTreeIter child_iter;
1081
1082   g_return_val_if_fail (tree_model_sort->child_model != NULL, FALSE);
1083   g_return_val_if_fail (VALID_ITER (iter, tree_model_sort), FALSE);
1084
1085   GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1086
1087   return gtk_tree_model_iter_has_child (tree_model_sort->child_model, &child_iter);
1088 }
1089
1090 static gint
1091 gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
1092                                      GtkTreeIter  *iter)
1093 {
1094   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1095   GtkTreeIter child_iter;
1096
1097   g_return_val_if_fail (tree_model_sort->child_model != NULL, 0);
1098   if (iter)
1099     g_return_val_if_fail (VALID_ITER (iter, tree_model_sort), 0);
1100
1101   if (iter == NULL)
1102     return gtk_tree_model_iter_n_children (tree_model_sort->child_model, NULL);
1103
1104   GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1105
1106   return gtk_tree_model_iter_n_children (tree_model_sort->child_model, &child_iter);
1107 }
1108
1109 static gboolean
1110 gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
1111                                     GtkTreeIter  *iter,
1112                                     GtkTreeIter  *parent,
1113                                     gint          n)
1114 {
1115   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1116   SortLevel *level;
1117   /* We have this for the iter == parent case */
1118   GtkTreeIter children;
1119
1120   if (parent)
1121     g_return_val_if_fail (VALID_ITER (parent, tree_model_sort), FALSE);
1122
1123   /* Use this instead of has_child to force us to build the level, if needed */
1124   if (gtk_tree_model_sort_iter_children (tree_model, &children, parent) == FALSE)
1125     {
1126       iter->stamp = 0;
1127       return FALSE;
1128     }
1129
1130   level = children.user_data;
1131   if (n >= level->array->len)
1132     {
1133       iter->stamp = 0;
1134       return FALSE;
1135     }
1136
1137   iter->stamp = tree_model_sort->stamp;
1138   iter->user_data = level;
1139   iter->user_data2 = &g_array_index (level->array, SortElt, n);
1140
1141   return TRUE;
1142 }
1143
1144 static gboolean
1145 gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
1146                                  GtkTreeIter  *iter,
1147                                  GtkTreeIter  *child)
1148 {
1149   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1150   SortLevel *level;
1151
1152   iter->stamp = 0;
1153   g_return_val_if_fail (tree_model_sort->child_model != NULL, FALSE);
1154   g_return_val_if_fail (VALID_ITER (child, tree_model_sort), FALSE);
1155
1156   level = child->user_data;
1157
1158   if (level->parent_level)
1159     {
1160       iter->stamp = tree_model_sort->stamp;
1161       iter->user_data = level->parent_level;
1162       iter->user_data2 = level->parent_elt;
1163
1164       return TRUE;
1165     }
1166   return FALSE;
1167 }
1168
1169 static void
1170 gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
1171                               GtkTreeIter  *iter)
1172 {
1173   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1174   GtkTreeIter child_iter;
1175   SortLevel *level;
1176   SortElt *elt;
1177
1178   g_return_if_fail (tree_model_sort->child_model != NULL);
1179   g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1180
1181   GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1182
1183   gtk_tree_model_ref_node (tree_model_sort->child_model, &child_iter);
1184
1185   level = iter->user_data;
1186   elt = iter->user_data2;
1187
1188   elt->ref_count++;
1189   level->ref_count++;
1190   if (level->ref_count == 1)
1191     {
1192       SortLevel *parent_level = level->parent_level;
1193       SortElt *parent_elt = level->parent_elt;
1194       /* We were at zero -- time to decrement the zero_ref_count val */
1195       while (parent_level)
1196         {
1197           parent_elt->zero_ref_count--;
1198
1199           parent_elt = parent_level->parent_elt;
1200           parent_level = parent_level->parent_level;
1201         }
1202
1203       if (tree_model_sort->root != level)
1204         tree_model_sort->zero_ref_count--;
1205     }
1206 }
1207
1208 static void
1209 gtk_tree_model_sort_real_unref_node (GtkTreeModel *tree_model,
1210                                      GtkTreeIter  *iter,
1211                                      gboolean      propagate_unref)
1212 {
1213   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1214   SortLevel *level;
1215   SortElt *elt;
1216
1217   g_return_if_fail (tree_model_sort->child_model != NULL);
1218   g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1219
1220   if (propagate_unref)
1221     {
1222       GtkTreeIter child_iter;
1223
1224       GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1225       gtk_tree_model_unref_node (tree_model_sort->child_model, &child_iter);
1226     }
1227
1228   level = iter->user_data;
1229   elt = iter->user_data2;
1230
1231   g_return_if_fail (elt->ref_count > 0);
1232
1233   elt->ref_count--;
1234   level->ref_count--;
1235
1236   if (level->ref_count == 0)
1237     {
1238       SortLevel *parent_level = level->parent_level;
1239       SortElt *parent_elt = level->parent_elt;
1240
1241       /* We are at zero -- time to increment the zero_ref_count val */
1242       while (parent_level)
1243         {
1244           parent_elt->zero_ref_count++;
1245
1246           parent_elt = parent_level->parent_elt;
1247           parent_level = parent_level->parent_level;
1248         }
1249
1250       if (tree_model_sort->root != level)
1251         tree_model_sort->zero_ref_count++;
1252     }
1253 }
1254
1255 static void
1256 gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
1257                                 GtkTreeIter  *iter)
1258 {
1259   gtk_tree_model_sort_real_unref_node (tree_model, iter, TRUE);
1260 }
1261
1262 /* Sortable interface */
1263 static gboolean
1264 gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable *sortable,
1265                                         gint            *sort_column_id,
1266                                         GtkSortType     *order)
1267 {
1268   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1269
1270   if (sort_column_id)
1271     *sort_column_id = tree_model_sort->sort_column_id;
1272   if (order)
1273     *order = tree_model_sort->order;
1274
1275   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID ||
1276       tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
1277     return FALSE;
1278
1279   return TRUE;
1280 }
1281
1282 static void
1283 gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable *sortable,
1284                                         gint             sort_column_id,
1285                                         GtkSortType      order)
1286 {
1287   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1288
1289   if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1290     {
1291       GtkTreeDataSortHeader *header = NULL;
1292
1293       header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1294                                                sort_column_id);
1295
1296       /* we want to make sure that we have a function */
1297       g_return_if_fail (header != NULL);
1298       g_return_if_fail (header->func != NULL);
1299     }
1300   else
1301     g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1302
1303   if (tree_model_sort->sort_column_id == sort_column_id)
1304     {
1305       if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1306         {
1307           if (tree_model_sort->order == order)
1308             return;
1309         }
1310       else
1311         return;
1312     }
1313
1314   tree_model_sort->sort_column_id = sort_column_id;
1315   tree_model_sort->order = order;
1316
1317   gtk_tree_sortable_sort_column_changed (sortable);
1318
1319   gtk_tree_model_sort_sort (tree_model_sort);
1320 }
1321
1322 static void
1323 gtk_tree_model_sort_set_sort_func (GtkTreeSortable        *sortable,
1324                                    gint                    sort_column_id,
1325                                    GtkTreeIterCompareFunc  func,
1326                                    gpointer                data,
1327                                    GtkDestroyNotify        destroy)
1328 {
1329   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
1330
1331   tree_model_sort->sort_list = _gtk_tree_data_list_set_header (tree_model_sort->sort_list,
1332                                                                sort_column_id,
1333                                                                func, data, destroy);
1334
1335   if (tree_model_sort->sort_column_id == sort_column_id)
1336     gtk_tree_model_sort_sort (tree_model_sort);
1337 }
1338
1339 static void
1340 gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
1341                                            GtkTreeIterCompareFunc  func,
1342                                            gpointer                data,
1343                                            GtkDestroyNotify        destroy)
1344 {
1345   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1346
1347   if (tree_model_sort->default_sort_destroy)
1348     {
1349       GtkDestroyNotify d = tree_model_sort->default_sort_destroy;
1350
1351       tree_model_sort->default_sort_destroy = NULL;
1352       d (tree_model_sort->default_sort_data);
1353     }
1354
1355   tree_model_sort->default_sort_func = func;
1356   tree_model_sort->default_sort_data = data;
1357   tree_model_sort->default_sort_destroy = destroy;
1358
1359   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1360     gtk_tree_model_sort_sort (tree_model_sort);
1361 }
1362
1363 static gboolean
1364 gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable *sortable)
1365 {
1366   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1367
1368   return (tree_model_sort->default_sort_func != NULL);
1369 }
1370
1371 /* DragSource interface */
1372 static gboolean
1373 gtk_tree_model_sort_row_draggable (GtkTreeDragSource *drag_source,
1374                                    GtkTreePath       *path)
1375 {
1376   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1377   GtkTreePath *child_path;
1378   gboolean draggable;
1379
1380   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort,
1381                                                                path);
1382   draggable = gtk_tree_drag_source_row_draggable (GTK_TREE_DRAG_SOURCE (tree_model_sort->child_model), child_path);
1383   gtk_tree_path_free (child_path);
1384
1385   return draggable;
1386 }
1387
1388 static gboolean
1389 gtk_tree_model_sort_drag_data_get (GtkTreeDragSource *drag_source,
1390                                    GtkTreePath       *path,
1391                                    GtkSelectionData  *selection_data)
1392 {
1393   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1394   GtkTreePath *child_path;
1395   gboolean gotten;
1396
1397   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort, path);
1398   gotten = gtk_tree_drag_source_drag_data_get (GTK_TREE_DRAG_SOURCE (tree_model_sort->child_model), child_path, selection_data);
1399   gtk_tree_path_free (child_path);
1400
1401   return gotten;
1402 }
1403
1404 static gboolean
1405 gtk_tree_model_sort_drag_data_delete (GtkTreeDragSource *drag_source,
1406                                       GtkTreePath       *path)
1407 {
1408   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1409   GtkTreePath *child_path;
1410   gboolean deleted;
1411
1412   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort, path);
1413   deleted = gtk_tree_drag_source_drag_data_delete (GTK_TREE_DRAG_SOURCE (tree_model_sort->child_model), child_path);
1414   gtk_tree_path_free (child_path);
1415
1416   return deleted;
1417 }
1418
1419 /* sorting code - private */
1420 static gint
1421 gtk_tree_model_sort_compare_func (gconstpointer a,
1422                                   gconstpointer b,
1423                                   gpointer      user_data)
1424 {
1425   SortData *data = (SortData *)user_data;
1426   GtkTreeModelSort *tree_model_sort = data->tree_model_sort;
1427   SortTuple *sa = (SortTuple *)a;
1428   SortTuple *sb = (SortTuple *)b;
1429
1430   GtkTreeIter iter_a, iter_b;
1431   gint retval;
1432
1433   /* shortcut, if we've the same offsets here, they should be equal */
1434   if (sa->offset == sb->offset)
1435     return 0;
1436
1437   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1438     {
1439       iter_a = sa->elt->iter;
1440       iter_b = sb->elt->iter;
1441     }
1442   else
1443     {
1444       data->parent_path_indices [data->parent_path_depth-1] = sa->elt->offset;
1445       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort->child_model), &iter_a, data->parent_path);
1446       data->parent_path_indices [data->parent_path_depth-1] = sb->elt->offset;
1447       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort->child_model), &iter_b, data->parent_path);
1448     }
1449
1450   retval = (* data->sort_func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1451                                 &iter_a, &iter_b,
1452                                 data->sort_data);
1453
1454   if (tree_model_sort->order == GTK_SORT_DESCENDING)
1455     {
1456       if (retval > 0)
1457         retval = -1;
1458       else if (retval < 0)
1459         retval = 1;
1460     }
1461
1462   return retval;
1463 }
1464
1465 static gint
1466 gtk_tree_model_sort_offset_compare_func (gconstpointer a,
1467                                          gconstpointer b,
1468                                          gpointer      user_data)
1469 {
1470   gint retval;
1471
1472   SortTuple *sa = (SortTuple *)a;
1473   SortTuple *sb = (SortTuple *)b;
1474
1475   SortData *data = (SortData *)user_data;
1476
1477   if (sa->elt->offset < sb->elt->offset)
1478     retval = -1;
1479   else if (sa->elt->offset > sb->elt->offset)
1480     retval = 1;
1481   else
1482     retval = 0;
1483
1484   if (data->tree_model_sort->order == GTK_SORT_DESCENDING)
1485     {
1486       if (retval > 0)
1487         retval = -1;
1488       else if (retval < 0)
1489         retval = 1;
1490     }
1491
1492   return retval;
1493 }
1494
1495 static void
1496 gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
1497                                 SortLevel        *level,
1498                                 gboolean          recurse,
1499                                 gboolean          emit_reordered)
1500 {
1501   gint i;
1502   gint ref_offset;
1503   GArray *sort_array;
1504   GArray *new_array;
1505   gint *new_order;
1506
1507   GtkTreeIter iter;
1508   GtkTreePath *path;
1509
1510   SortData data;
1511
1512   g_return_if_fail (level != NULL);
1513
1514   if (level->array->len < 1 && !((SortElt *)level->array->data)->children)
1515     return;
1516
1517   iter.stamp = tree_model_sort->stamp;
1518   iter.user_data = level;
1519   iter.user_data2 = &g_array_index (level->array, SortElt, 0);
1520
1521   gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (tree_model_sort), &iter);
1522   ref_offset = g_array_index (level->array, SortElt, 0).offset;
1523
1524   /* Set up data */
1525   data.tree_model_sort = tree_model_sort;
1526   if (level->parent_elt)
1527     {
1528       data.parent_path = gtk_tree_model_sort_elt_get_path (level->parent_level,
1529                                                            level->parent_elt);
1530       gtk_tree_path_append_index (data.parent_path, 0);
1531     }
1532   else
1533     {
1534       data.parent_path = gtk_tree_path_new_first ();
1535     }
1536   data.parent_path_depth = gtk_tree_path_get_depth (data.parent_path);
1537   data.parent_path_indices = gtk_tree_path_get_indices (data.parent_path);
1538
1539   /* make the array to be sorted */
1540   sort_array = g_array_sized_new (FALSE, FALSE, sizeof (SortTuple), level->array->len);
1541   for (i = 0; i < level->array->len; i++)
1542     {
1543       SortTuple tuple;
1544
1545       tuple.elt = &g_array_index (level->array, SortElt, i);
1546       tuple.offset = i;
1547
1548       g_array_append_val (sort_array, tuple);
1549     }
1550
1551     if (tree_model_sort->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1552       {
1553         GtkTreeDataSortHeader *header = NULL;
1554
1555         header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1556                                                  tree_model_sort->sort_column_id);
1557
1558         g_return_if_fail (header != NULL);
1559         g_return_if_fail (header->func != NULL);
1560
1561         data.sort_func = header->func;
1562         data.sort_data = header->data;
1563       }
1564     else
1565       {
1566         /* absolutely SHOULD NOT happen: */
1567         g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1568
1569         data.sort_func = tree_model_sort->default_sort_func;
1570         data.sort_data = tree_model_sort->default_sort_data;
1571       }
1572
1573   if (data.sort_func == NO_SORT_FUNC)
1574     g_array_sort_with_data (sort_array,
1575                             gtk_tree_model_sort_offset_compare_func,
1576                             &data);
1577   else
1578     g_array_sort_with_data (sort_array,
1579                             gtk_tree_model_sort_compare_func,
1580                             &data);
1581
1582   gtk_tree_path_free (data.parent_path);
1583
1584   new_array = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), level->array->len);
1585   new_order = g_new (gint, level->array->len);
1586
1587   for (i = 0; i < level->array->len; i++)
1588     {
1589       SortElt *elt;
1590
1591       elt = g_array_index (sort_array, SortTuple, i).elt;
1592       new_order[i] = g_array_index (sort_array, SortTuple, i).offset;
1593
1594       g_array_append_val (new_array, *elt);
1595       elt = &g_array_index (new_array, SortElt, i);
1596       if (elt->children)
1597         elt->children->parent_elt = elt;
1598     }
1599
1600   g_array_free (level->array, TRUE);
1601   level->array = new_array;
1602   g_array_free (sort_array, TRUE);
1603
1604   if (emit_reordered)
1605     {
1606       gtk_tree_model_sort_increment_stamp (tree_model_sort);
1607       if (level->parent_elt)
1608         {
1609           iter.stamp = tree_model_sort->stamp;
1610           iter.user_data = level->parent_level;
1611           iter.user_data2 = level->parent_elt;
1612
1613           path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort),
1614                                           &iter);
1615
1616           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1617                                          &iter, new_order);
1618         }
1619       else
1620         {
1621           /* toplevel list */
1622           path = gtk_tree_path_new ();
1623           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1624                                          NULL, new_order);
1625         }
1626
1627       gtk_tree_path_free (path);
1628     }
1629
1630   /* recurse, if possible */
1631   if (recurse)
1632     {
1633       for (i = 0; i < level->array->len; i++)
1634         {
1635           SortElt *elt = &g_array_index (level->array, SortElt, i);
1636
1637           if (elt->children)
1638             gtk_tree_model_sort_sort_level (tree_model_sort,
1639                                             elt->children,
1640                                             TRUE, emit_reordered);
1641         }
1642     }
1643
1644   g_free (new_order);
1645
1646   /* get the iter we referenced at the beginning of this function and
1647    * unref it again
1648    */
1649   iter.stamp = tree_model_sort->stamp;
1650   iter.user_data = level;
1651
1652   for (i = 0; i < level->array->len; i++)
1653     {
1654       if (g_array_index (level->array, SortElt, i).offset == ref_offset)
1655         {
1656           iter.user_data2 = &g_array_index (level->array, SortElt, i);
1657           break;
1658         }
1659     }
1660
1661   gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (tree_model_sort), &iter);
1662 }
1663
1664 static void
1665 gtk_tree_model_sort_sort (GtkTreeModelSort *tree_model_sort)
1666 {
1667   if (!tree_model_sort->root)
1668     return;
1669
1670   if (tree_model_sort->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1671     {
1672       GtkTreeDataSortHeader *header = NULL;
1673
1674       header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1675                                                tree_model_sort->sort_column_id);
1676
1677       /* we want to make sure that we have a function */
1678       g_return_if_fail (header != NULL);
1679       g_return_if_fail (header->func != NULL);
1680     }
1681   else
1682     g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1683
1684   gtk_tree_model_sort_sort_level (tree_model_sort, tree_model_sort->root,
1685                                   TRUE, TRUE);
1686 }
1687
1688 /* signal helpers */
1689 static gint
1690 gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
1691                                        SortLevel        *level,
1692                                        GtkTreeIter      *iter,
1693                                        gint             skip_index)
1694 {
1695   gint start, middle, end;
1696   gint cmp;
1697   SortElt *tmp_elt;
1698   GtkTreeIter tmp_iter;
1699
1700   GtkTreeIterCompareFunc func;
1701   gpointer data;
1702
1703   if (tree_model_sort->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1704     {
1705       GtkTreeDataSortHeader *header;
1706
1707       header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1708                                                tree_model_sort->sort_column_id);
1709
1710       g_return_val_if_fail (header != NULL, 0);
1711
1712       func = header->func;
1713       data = header->data;
1714     }
1715   else
1716     {
1717       func = tree_model_sort->default_sort_func;
1718       data = tree_model_sort->default_sort_data;
1719
1720       g_return_val_if_fail (func != NO_SORT_FUNC, 0);
1721     }
1722
1723   g_return_val_if_fail (func != NULL, 0);
1724
1725   start = 0;
1726   end = level->array->len;
1727   if (skip_index < 0)
1728     skip_index = end;
1729   else
1730     end--;
1731
1732   if (start == end)
1733     return 0;
1734
1735   while (start != end)
1736     {
1737       middle = (start + end) / 2;
1738
1739       if (middle < skip_index)
1740         tmp_elt = &(g_array_index (level->array, SortElt, middle));
1741       else
1742         tmp_elt = &(g_array_index (level->array, SortElt, middle + 1));
1743
1744       if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1745         {
1746           GtkTreePath *path = gtk_tree_model_sort_elt_get_path (level, tmp_elt);
1747           gtk_tree_model_get_iter (tree_model_sort->child_model,
1748                                    &tmp_iter, path);
1749           gtk_tree_path_free (path);
1750         }
1751       else
1752         tmp_iter = tmp_elt->iter;
1753
1754       if (tree_model_sort->order == GTK_SORT_ASCENDING)
1755         cmp = (* func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1756                         &tmp_iter, iter, data);
1757       else
1758         cmp = (* func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1759                         iter, &tmp_iter, data);
1760
1761       if (cmp <= 0)
1762         start = middle + 1;
1763       else
1764         end = middle;
1765     }
1766
1767   if (cmp <= 0)
1768     return middle + 1;
1769   else
1770     return middle;
1771 }
1772
1773 static gboolean
1774 gtk_tree_model_sort_insert_value (GtkTreeModelSort *tree_model_sort,
1775                                   SortLevel        *level,
1776                                   GtkTreePath      *s_path,
1777                                   GtkTreeIter      *s_iter)
1778 {
1779   gint offset, index, i;
1780
1781   SortElt elt;
1782   SortElt *tmp_elt;
1783
1784   offset = gtk_tree_path_get_indices (s_path)[gtk_tree_path_get_depth (s_path) - 1];
1785
1786   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1787     elt.iter = *s_iter;
1788   elt.offset = offset;
1789   elt.zero_ref_count = 0;
1790   elt.ref_count = 0;
1791   elt.children = NULL;
1792
1793   /* update all larger offsets */
1794   tmp_elt = SORT_ELT (level->array->data);
1795   for (i = 0; i < level->array->len; i++, tmp_elt++)
1796     if (tmp_elt->offset >= offset)
1797       tmp_elt->offset++;
1798
1799   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
1800       tree_model_sort->default_sort_func == NO_SORT_FUNC)
1801     index = offset;
1802   else
1803     index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
1804                                                    level, s_iter,
1805                                                    -1);
1806
1807   g_array_insert_vals (level->array, index, &elt, 1);
1808   tmp_elt = SORT_ELT (level->array->data);
1809   for (i = 0; i < level->array->len; i++, tmp_elt++)
1810     if (tmp_elt->children)
1811       tmp_elt->children->parent_elt = tmp_elt;
1812
1813   return TRUE;
1814 }
1815
1816 /* sort elt stuff */
1817 static GtkTreePath *
1818 gtk_tree_model_sort_elt_get_path (SortLevel *level,
1819                                   SortElt *elt)
1820 {
1821   SortLevel *walker = level;
1822   SortElt *walker2 = elt;
1823   GtkTreePath *path;
1824
1825   g_return_val_if_fail (level != NULL, NULL);
1826   g_return_val_if_fail (elt != NULL, NULL);
1827
1828   path = gtk_tree_path_new ();
1829
1830   while (walker)
1831     {
1832       gtk_tree_path_prepend_index (path, walker2->offset);
1833
1834       walker2 = walker->parent_elt;
1835       walker = walker->parent_level;
1836     }
1837
1838   return path;
1839 }
1840
1841 /**
1842  * gtk_tree_model_sort_set_model:
1843  * @tree_model_sort: The #GtkTreeModelSort.
1844  * @child_model: A #GtkTreeModel, or %NULL.
1845  *
1846  * Sets the model of @tree_model_sort to be @model.  If @model is %NULL,
1847  * then the old model is unset.  The sort function is unset as a result
1848  * of this call. The model will be in an unsorted state until a sort
1849  * function is set.
1850  **/
1851 static void
1852 gtk_tree_model_sort_set_model (GtkTreeModelSort *tree_model_sort,
1853                                GtkTreeModel     *child_model)
1854 {
1855   if (child_model)
1856     g_object_ref (child_model);
1857
1858   if (tree_model_sort->child_model)
1859     {
1860       g_signal_handler_disconnect (tree_model_sort->child_model,
1861                                    tree_model_sort->changed_id);
1862       g_signal_handler_disconnect (tree_model_sort->child_model,
1863                                    tree_model_sort->inserted_id);
1864       g_signal_handler_disconnect (tree_model_sort->child_model,
1865                                    tree_model_sort->has_child_toggled_id);
1866       g_signal_handler_disconnect (tree_model_sort->child_model,
1867                                    tree_model_sort->deleted_id);
1868       g_signal_handler_disconnect (tree_model_sort->child_model,
1869                                    tree_model_sort->reordered_id);
1870
1871       /* reset our state */
1872       if (tree_model_sort->root)
1873         gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
1874       tree_model_sort->root = NULL;
1875       _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
1876       tree_model_sort->sort_list = NULL;
1877       g_object_unref (tree_model_sort->child_model);
1878     }
1879
1880   tree_model_sort->child_model = child_model;
1881
1882   if (child_model)
1883     {
1884       GType *types;
1885       gint i, n_columns;
1886
1887       tree_model_sort->changed_id =
1888         g_signal_connect (child_model, "row_changed",
1889                           G_CALLBACK (gtk_tree_model_sort_row_changed),
1890                           tree_model_sort);
1891       tree_model_sort->inserted_id =
1892         g_signal_connect (child_model, "row_inserted",
1893                           G_CALLBACK (gtk_tree_model_sort_row_inserted),
1894                           tree_model_sort);
1895       tree_model_sort->has_child_toggled_id =
1896         g_signal_connect (child_model, "row_has_child_toggled",
1897                           G_CALLBACK (gtk_tree_model_sort_row_has_child_toggled),
1898                           tree_model_sort);
1899       tree_model_sort->deleted_id =
1900         g_signal_connect (child_model, "row_deleted",
1901                           G_CALLBACK (gtk_tree_model_sort_row_deleted),
1902                           tree_model_sort);
1903       tree_model_sort->reordered_id =
1904         g_signal_connect (child_model, "rows_reordered",
1905                           G_CALLBACK (gtk_tree_model_sort_rows_reordered),
1906                           tree_model_sort);
1907
1908       tree_model_sort->child_flags = gtk_tree_model_get_flags (child_model);
1909       n_columns = gtk_tree_model_get_n_columns (child_model);
1910
1911       types = g_new (GType, n_columns);
1912       for (i = 0; i < n_columns; i++)
1913         types[i] = gtk_tree_model_get_column_type (child_model, i);
1914
1915       tree_model_sort->sort_list = _gtk_tree_data_list_header_new (n_columns, types);
1916       g_free (types);
1917
1918       tree_model_sort->default_sort_func = NO_SORT_FUNC;
1919       tree_model_sort->stamp = g_random_int ();
1920     }
1921 }
1922
1923 /**
1924  * gtk_tree_model_sort_get_model:
1925  * @tree_model: a #GtkTreeModelSort
1926  *
1927  * Returns the model the #GtkTreeModelSort is sorting.
1928  *
1929  * Return value: the "child model" being sorted
1930  **/
1931 GtkTreeModel *
1932 gtk_tree_model_sort_get_model (GtkTreeModelSort *tree_model)
1933 {
1934   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
1935
1936   return tree_model->child_model;
1937 }
1938
1939
1940 static GtkTreePath *
1941 gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
1942                                                      GtkTreePath      *child_path,
1943                                                      gboolean          build_levels)
1944 {
1945   gint *child_indices;
1946   GtkTreePath *retval;
1947   SortLevel *level;
1948   gint i;
1949
1950   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
1951   g_return_val_if_fail (child_path != NULL, NULL);
1952
1953   retval = gtk_tree_path_new ();
1954   child_indices = gtk_tree_path_get_indices (child_path);
1955
1956   if (tree_model_sort->root == NULL && build_levels)
1957     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1958   level = SORT_LEVEL (tree_model_sort->root);
1959
1960   for (i = 0; i < gtk_tree_path_get_depth (child_path); i++)
1961     {
1962       gint j;
1963       gboolean found_child = FALSE;
1964
1965       if (!level)
1966         {
1967           gtk_tree_path_free (retval);
1968           return NULL;
1969         }
1970
1971       if (child_indices[i] >= level->array->len)
1972         {
1973           gtk_tree_path_free (retval);
1974           return NULL;
1975         }
1976       for (j = 0; j < level->array->len; j++)
1977         {
1978           if ((g_array_index (level->array, SortElt, j)).offset == child_indices[i])
1979             {
1980               gtk_tree_path_append_index (retval, j);
1981               if (g_array_index (level->array, SortElt, j).children == NULL && build_levels)
1982                 {
1983                   gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, j));
1984                 }
1985               level = g_array_index (level->array, SortElt, j).children;
1986               found_child = TRUE;
1987               break;
1988             }
1989         }
1990       if (! found_child)
1991         {
1992           gtk_tree_path_free (retval);
1993           return NULL;
1994         }
1995     }
1996
1997   return retval;
1998 }
1999
2000
2001 /**
2002  * gtk_tree_model_sort_convert_child_path_to_path:
2003  * @tree_model_sort: A #GtkTreeModelSort
2004  * @child_path: A #GtkTreePath to convert
2005  *
2006  * Converts @child_path to a path relative to @tree_model_sort.  That is,
2007  * @child_path points to a path in the child model.  The returned path will
2008  * point to the same row in the sorted model.  If @child_path isn't a valid
2009  * path on the child model, then %NULL is returned.
2010  *
2011  * Return value: A newly allocated #GtkTreePath, or %NULL
2012  **/
2013 GtkTreePath *
2014 gtk_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
2015                                                 GtkTreePath      *child_path)
2016 {
2017   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2018   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
2019   g_return_val_if_fail (child_path != NULL, NULL);
2020
2021   return gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path, TRUE);
2022 }
2023
2024 /**
2025  * gtk_tree_model_sort_convert_child_iter_to_iter:
2026  * @tree_model_sort: A #GtkTreeModelSort
2027  * @sort_iter: An uninitialized #GtkTreeIter.
2028  * @child_iter: A valid #GtkTreeIter pointing to a row on the child model
2029  *
2030  * Sets @sort_iter to point to the row in @tree_model_sort that corresponds to
2031  * the row pointed at by @child_iter.
2032  **/
2033 void
2034 gtk_tree_model_sort_convert_child_iter_to_iter (GtkTreeModelSort *tree_model_sort,
2035                                                 GtkTreeIter      *sort_iter,
2036                                                 GtkTreeIter      *child_iter)
2037 {
2038   GtkTreePath *child_path, *path;
2039
2040   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2041   g_return_if_fail (tree_model_sort->child_model != NULL);
2042   g_return_if_fail (sort_iter != NULL);
2043   g_return_if_fail (child_iter != NULL);
2044
2045   sort_iter->stamp = 0;
2046
2047   child_path = gtk_tree_model_get_path (tree_model_sort->child_model, child_iter);
2048   g_return_if_fail (child_path != NULL);
2049
2050   path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path);
2051   gtk_tree_path_free (child_path);
2052   g_return_if_fail (path != NULL);
2053
2054   gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort), sort_iter, path);
2055   gtk_tree_path_free (path);
2056 }
2057
2058 /**
2059  * gtk_tree_model_sort_convert_path_to_child_path:
2060  * @tree_model_sort: A #GtkTreeModelSort
2061  * @sorted_path: A #GtkTreePath to convert
2062  *
2063  * Converts @sorted_path to a path on the child model of @tree_model_sort.
2064  * That is, @sorted_path points to a location in @tree_model_sort.  The
2065  * returned path will point to the same location in the model not being
2066  * sorted.  If @sorted_path does not point to a location in the child model,
2067  * %NULL is returned.
2068  *
2069  * Return value: A newly allocated #GtkTreePath, or %NULL
2070  **/
2071 GtkTreePath *
2072 gtk_tree_model_sort_convert_path_to_child_path (GtkTreeModelSort *tree_model_sort,
2073                                                 GtkTreePath      *sorted_path)
2074 {
2075   gint *sorted_indices;
2076   GtkTreePath *retval;
2077   SortLevel *level;
2078   gint i;
2079
2080   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2081   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
2082   g_return_val_if_fail (sorted_path != NULL, NULL);
2083
2084   retval = gtk_tree_path_new ();
2085   sorted_indices = gtk_tree_path_get_indices (sorted_path);
2086   if (tree_model_sort->root == NULL)
2087     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
2088   level = SORT_LEVEL (tree_model_sort->root);
2089
2090   for (i = 0; i < gtk_tree_path_get_depth (sorted_path); i++)
2091     {
2092       gint count = sorted_indices[i];
2093
2094       if ((level == NULL) ||
2095           (level->array->len <= count))
2096         {
2097           gtk_tree_path_free (retval);
2098           return NULL;
2099         }
2100
2101       if (g_array_index (level->array, SortElt, count).children == NULL)
2102         gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, count));
2103
2104       if (level == NULL)
2105         {
2106           gtk_tree_path_free (retval);
2107           break;
2108         }
2109
2110       gtk_tree_path_append_index (retval, g_array_index (level->array, SortElt, count).offset);
2111       level = g_array_index (level->array, SortElt, count).children;
2112     }
2113
2114   return retval;
2115 }
2116
2117 /**
2118  * gtk_tree_model_sort_convert_iter_to_child_iter:
2119  * @tree_model_sort: A #GtkTreeModelSort
2120  * @child_iter: An uninitialized #GtkTreeIter
2121  * @sorted_iter: A valid #GtkTreeIter pointing to a row on @tree_model_sort.
2122  *
2123  * Sets @child_iter to point to the row pointed to by @sorted_iter.
2124  **/
2125 void
2126 gtk_tree_model_sort_convert_iter_to_child_iter (GtkTreeModelSort *tree_model_sort,
2127                                                 GtkTreeIter      *child_iter,
2128                                                 GtkTreeIter      *sorted_iter)
2129 {
2130   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2131   g_return_if_fail (tree_model_sort->child_model != NULL);
2132   g_return_if_fail (child_iter != NULL);
2133   g_return_if_fail (VALID_ITER (sorted_iter, tree_model_sort));
2134
2135   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2136     {
2137       *child_iter = SORT_ELT (sorted_iter->user_data2)->iter;
2138     }
2139   else
2140     {
2141       GtkTreePath *path;
2142
2143       path = gtk_tree_model_sort_elt_get_path (sorted_iter->user_data,
2144                                                sorted_iter->user_data2);
2145       gtk_tree_model_get_iter (tree_model_sort->child_model, child_iter, path);
2146       gtk_tree_path_free (path);
2147     }
2148 }
2149
2150 static void
2151 gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
2152                                  SortLevel        *parent_level,
2153                                  SortElt          *parent_elt)
2154 {
2155   GtkTreeIter iter;
2156   SortLevel *new_level;
2157   gint length = 0;
2158   gint i;
2159
2160   g_assert (tree_model_sort->child_model != NULL);
2161
2162   if (parent_level == NULL)
2163     {
2164       if (gtk_tree_model_get_iter_first (tree_model_sort->child_model, &iter) == FALSE)
2165         return;
2166       length = gtk_tree_model_iter_n_children (tree_model_sort->child_model, NULL);
2167     }
2168   else
2169     {
2170       GtkTreeIter parent_iter;
2171       GtkTreeIter child_parent_iter;
2172
2173       parent_iter.stamp = tree_model_sort->stamp;
2174       parent_iter.user_data = parent_level;
2175       parent_iter.user_data2 = parent_elt;
2176
2177       gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2178                                                       &child_parent_iter,
2179                                                       &parent_iter);
2180       if (gtk_tree_model_iter_children (tree_model_sort->child_model,
2181                                         &iter,
2182                                         &child_parent_iter) == FALSE)
2183         return;
2184
2185       /* stamp may have changed */
2186       gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2187                                                       &child_parent_iter,
2188                                                       &parent_iter);
2189
2190       length = gtk_tree_model_iter_n_children (tree_model_sort->child_model, &child_parent_iter);
2191     }
2192
2193   g_return_if_fail (length > 0);
2194
2195   new_level = g_new (SortLevel, 1);
2196   new_level->array = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), length);
2197   new_level->ref_count = 0;
2198   new_level->parent_elt = parent_elt;
2199   new_level->parent_level = parent_level;
2200
2201   if (parent_elt)
2202     parent_elt->children = new_level;
2203   else
2204     tree_model_sort->root = new_level;
2205
2206   /* increase the count of zero ref_counts.*/
2207   while (parent_level)
2208     {
2209       parent_elt->zero_ref_count++;
2210
2211       parent_elt = parent_level->parent_elt;
2212       parent_level = parent_level->parent_level;
2213     }
2214   if (new_level != tree_model_sort->root)
2215     tree_model_sort->zero_ref_count++;
2216
2217   for (i = 0; i < length; i++)
2218     {
2219       SortElt sort_elt;
2220       sort_elt.offset = i;
2221       sort_elt.zero_ref_count = 0;
2222       sort_elt.ref_count = 0;
2223       sort_elt.children = NULL;
2224
2225       if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2226         {
2227           sort_elt.iter = iter;
2228           if (gtk_tree_model_iter_next (tree_model_sort->child_model, &iter) == FALSE &&
2229               i < length - 1)
2230             {
2231               g_warning ("There is a discrepancy between the sort model and the child model.");
2232               return;
2233             }
2234         }
2235       g_array_append_val (new_level->array, sort_elt);
2236     }
2237
2238   /* sort level */
2239   gtk_tree_model_sort_sort_level (tree_model_sort, new_level,
2240                                   FALSE, FALSE);
2241 }
2242
2243 static void
2244 gtk_tree_model_sort_free_level (GtkTreeModelSort *tree_model_sort,
2245                                 SortLevel        *sort_level)
2246 {
2247   gint i;
2248
2249   g_assert (sort_level);
2250
2251   for (i = 0; i < sort_level->array->len; i++)
2252     {
2253       if (g_array_index (sort_level->array, SortElt, i).children)
2254         gtk_tree_model_sort_free_level (tree_model_sort,
2255                                         SORT_LEVEL (g_array_index (sort_level->array, SortElt, i).children));
2256     }
2257
2258   if (sort_level->ref_count == 0)
2259     {
2260       SortLevel *parent_level = sort_level->parent_level;
2261       SortElt *parent_elt = sort_level->parent_elt;
2262
2263       while (parent_level)
2264         {
2265           parent_elt->zero_ref_count--;
2266
2267           parent_elt = parent_level->parent_elt;
2268           parent_level = parent_level->parent_level;
2269         }
2270
2271       if (sort_level != tree_model_sort->root)
2272         tree_model_sort->zero_ref_count--;
2273     }
2274
2275   if (sort_level->parent_elt)
2276     sort_level->parent_elt->children = NULL;
2277   else
2278     tree_model_sort->root = NULL;
2279
2280   g_array_free (sort_level->array, TRUE);
2281   sort_level->array = NULL;
2282
2283   g_free (sort_level);
2284   sort_level = NULL;
2285 }
2286
2287 static void
2288 gtk_tree_model_sort_increment_stamp (GtkTreeModelSort *tree_model_sort)
2289 {
2290   do
2291     {
2292       tree_model_sort->stamp++;
2293     }
2294   while (tree_model_sort->stamp == 0);
2295
2296   gtk_tree_model_sort_clear_cache (tree_model_sort);
2297 }
2298
2299 static void
2300 gtk_tree_model_sort_clear_cache_helper (GtkTreeModelSort *tree_model_sort,
2301                                         SortLevel        *level)
2302 {
2303   gint i;
2304
2305   g_assert (level != NULL);
2306
2307   for (i = 0; i < level->array->len; i++)
2308     {
2309       if (g_array_index (level->array, SortElt, i).zero_ref_count > 0)
2310         gtk_tree_model_sort_clear_cache_helper (tree_model_sort, g_array_index (level->array, SortElt, i).children);
2311     }
2312
2313   if (level->ref_count == 0 && level != tree_model_sort->root)
2314     gtk_tree_model_sort_free_level (tree_model_sort, level);
2315 }
2316
2317 /**
2318  * gtk_tree_model_sort_reset_default_sort_func:
2319  * @tree_model_sort: A #GtkTreeModelSort
2320  *
2321  * This resets the default sort function to be in the 'unsorted' state.  That
2322  * is, it is in the same order as the child model. It will re-sort the model
2323  * to be in the same order as the child model only if the #GtkTreeModelSort
2324  * is in 'unsorted' state.
2325  **/
2326 void
2327 gtk_tree_model_sort_reset_default_sort_func (GtkTreeModelSort *tree_model_sort)
2328 {
2329   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2330
2331   if (tree_model_sort->default_sort_destroy)
2332     {
2333       GtkDestroyNotify d = tree_model_sort->default_sort_destroy;
2334
2335       tree_model_sort->default_sort_destroy = NULL;
2336       d (tree_model_sort->default_sort_data);
2337     }
2338
2339   tree_model_sort->default_sort_func = NO_SORT_FUNC;
2340   tree_model_sort->default_sort_data = NULL;
2341   tree_model_sort->default_sort_destroy = NULL;
2342
2343   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
2344     gtk_tree_model_sort_sort (tree_model_sort);
2345   tree_model_sort->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
2346 }
2347
2348 /**
2349  * gtk_tree_model_sort_clear_cache:
2350  * @tree_model_sort: A #GtkTreeModelSort
2351  *
2352  * This function should almost never be called.  It clears the @tree_model_sort
2353  * of any cached iterators that haven't been reffed with
2354  * gtk_tree_model_ref_node().  This might be useful if the child model being
2355  * sorted is static (and doesn't change often) and there has been a lot of
2356  * unreffed access to nodes.  As a side effect of this function, all unreffed
2357  * iters will be invalid.
2358  **/
2359 void
2360 gtk_tree_model_sort_clear_cache (GtkTreeModelSort *tree_model_sort)
2361 {
2362   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2363
2364   if (tree_model_sort->zero_ref_count > 0)
2365     gtk_tree_model_sort_clear_cache_helper (tree_model_sort, (SortLevel *)tree_model_sort->root);
2366 }
2367
2368 static gboolean
2369 gtk_tree_model_sort_iter_is_valid_helper (GtkTreeIter *iter,
2370                                           SortLevel   *level)
2371 {
2372   gint i;
2373
2374   for (i = 0; i < level->array->len; i++)
2375     {
2376       SortElt *elt = &g_array_index (level->array, SortElt, i);
2377
2378       if (iter->user_data == level && iter->user_data2 == elt)
2379         return TRUE;
2380
2381       if (elt->children)
2382         if (gtk_tree_model_sort_iter_is_valid_helper (iter, elt->children))
2383           return TRUE;
2384     }
2385
2386   return FALSE;
2387 }
2388
2389 /**
2390  * gtk_tree_model_sort_iter_is_valid:
2391  * @tree_model_sort: A #GtkTreeModelSort.
2392  * @iter: A #GtkTreeIter.
2393  *
2394  * <warning><para>
2395  * This function is slow. Only use it for debugging and/or testing purposes.
2396  * </para></warning>
2397  *
2398  * Checks if the given iter is a valid iter for this #GtkTreeModelSort.
2399  *
2400  * Return value: %TRUE if the iter is valid, %FALSE if the iter is invalid.
2401  *
2402  * Since: 2.2
2403  **/
2404 gboolean
2405 gtk_tree_model_sort_iter_is_valid (GtkTreeModelSort *tree_model_sort,
2406                                    GtkTreeIter      *iter)
2407 {
2408   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), FALSE);
2409   g_return_val_if_fail (iter != NULL, FALSE);
2410
2411   if (!VALID_ITER (iter, tree_model_sort))
2412     return FALSE;
2413
2414   return gtk_tree_model_sort_iter_is_valid_helper (iter,
2415                                                    tree_model_sort->root);
2416 }
2417
2418 #define __GTK_TREE_MODEL_SORT_C__
2419 #include "gtkaliasdef.c"