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_depth (s_path) == 0)
 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   GtkTreeIter tmp_iter;
1176   SortLevel *level;
1177   SortElt *elt;
1178
1179   g_return_if_fail (tree_model_sort->child_model != NULL);
1180   g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1181
1182   GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1183
1184   /* Reference the node in the child model */
1185   gtk_tree_model_ref_node (tree_model_sort->child_model, &child_iter);
1186
1187   /* Increase the reference count of this element and its level */
1188   level = iter->user_data;
1189   elt = iter->user_data2;
1190
1191   elt->ref_count++;
1192   level->ref_count++;
1193
1194   /* Increase the reference count of all parent elements */
1195   tmp_iter.stamp = tree_model_sort->stamp;
1196   tmp_iter.user_data = level->parent_level;
1197   tmp_iter.user_data2 = level->parent_elt;;
1198
1199   while (tmp_iter.user_data2)
1200     {
1201       gtk_tree_model_sort_ref_node (tree_model, &tmp_iter);
1202
1203       tmp_iter.user_data2 = SORT_LEVEL (tmp_iter.user_data)->parent_elt;
1204       tmp_iter.user_data = SORT_LEVEL (tmp_iter.user_data)->parent_level;
1205     }
1206
1207   if (level->ref_count == 1)
1208     {
1209       SortLevel *parent_level = level->parent_level;
1210       SortElt *parent_elt = level->parent_elt;
1211       /* We were at zero -- time to decrement the zero_ref_count val */
1212       while (parent_level)
1213         {
1214           parent_elt->zero_ref_count--;
1215
1216           parent_elt = parent_level->parent_elt;
1217           parent_level = parent_level->parent_level;
1218         }
1219
1220       if (tree_model_sort->root != level)
1221         tree_model_sort->zero_ref_count--;
1222     }
1223 }
1224
1225 static void
1226 gtk_tree_model_sort_real_unref_node (GtkTreeModel *tree_model,
1227                                      GtkTreeIter  *iter,
1228                                      gboolean      propagate_unref)
1229 {
1230   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1231   GtkTreeIter tmp_iter;
1232   SortLevel *level;
1233   SortElt *elt;
1234
1235   g_return_if_fail (tree_model_sort->child_model != NULL);
1236   g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1237
1238   if (propagate_unref)
1239     {
1240       GtkTreeIter child_iter;
1241
1242       GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1243       gtk_tree_model_unref_node (tree_model_sort->child_model, &child_iter);
1244     }
1245
1246   level = iter->user_data;
1247   elt = iter->user_data2;
1248
1249   g_return_if_fail (elt->ref_count > 0);
1250
1251   elt->ref_count--;
1252   level->ref_count--;
1253
1254   /* Decrease the reference count of all parent elements */
1255   tmp_iter.stamp = tree_model_sort->stamp;
1256   tmp_iter.user_data = level->parent_level;
1257   tmp_iter.user_data2 = level->parent_elt;;
1258
1259   while (tmp_iter.user_data2)
1260     {
1261       gtk_tree_model_sort_real_unref_node (tree_model, &tmp_iter, FALSE);
1262
1263       tmp_iter.user_data2 = SORT_LEVEL (tmp_iter.user_data)->parent_elt;
1264       tmp_iter.user_data = SORT_LEVEL (tmp_iter.user_data)->parent_level;
1265     }
1266
1267   if (level->ref_count == 0)
1268     {
1269       SortLevel *parent_level = level->parent_level;
1270       SortElt *parent_elt = level->parent_elt;
1271
1272       /* We are at zero -- time to increment the zero_ref_count val */
1273       while (parent_level)
1274         {
1275           parent_elt->zero_ref_count++;
1276
1277           parent_elt = parent_level->parent_elt;
1278           parent_level = parent_level->parent_level;
1279         }
1280
1281       if (tree_model_sort->root != level)
1282         tree_model_sort->zero_ref_count++;
1283     }
1284 }
1285
1286 static void
1287 gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
1288                                 GtkTreeIter  *iter)
1289 {
1290   gtk_tree_model_sort_real_unref_node (tree_model, iter, TRUE);
1291 }
1292
1293 /* Sortable interface */
1294 static gboolean
1295 gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable *sortable,
1296                                         gint            *sort_column_id,
1297                                         GtkSortType     *order)
1298 {
1299   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1300
1301   if (sort_column_id)
1302     *sort_column_id = tree_model_sort->sort_column_id;
1303   if (order)
1304     *order = tree_model_sort->order;
1305
1306   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID ||
1307       tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
1308     return FALSE;
1309
1310   return TRUE;
1311 }
1312
1313 static void
1314 gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable *sortable,
1315                                         gint             sort_column_id,
1316                                         GtkSortType      order)
1317 {
1318   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1319
1320   if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1321     {
1322       GtkTreeDataSortHeader *header = NULL;
1323
1324       header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1325                                                sort_column_id);
1326
1327       /* we want to make sure that we have a function */
1328       g_return_if_fail (header != NULL);
1329       g_return_if_fail (header->func != NULL);
1330     }
1331   else
1332     g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1333
1334   if (tree_model_sort->sort_column_id == sort_column_id)
1335     {
1336       if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1337         {
1338           if (tree_model_sort->order == order)
1339             return;
1340         }
1341       else
1342         return;
1343     }
1344
1345   tree_model_sort->sort_column_id = sort_column_id;
1346   tree_model_sort->order = order;
1347
1348   gtk_tree_sortable_sort_column_changed (sortable);
1349
1350   gtk_tree_model_sort_sort (tree_model_sort);
1351 }
1352
1353 static void
1354 gtk_tree_model_sort_set_sort_func (GtkTreeSortable        *sortable,
1355                                    gint                    sort_column_id,
1356                                    GtkTreeIterCompareFunc  func,
1357                                    gpointer                data,
1358                                    GtkDestroyNotify        destroy)
1359 {
1360   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
1361
1362   tree_model_sort->sort_list = _gtk_tree_data_list_set_header (tree_model_sort->sort_list,
1363                                                                sort_column_id,
1364                                                                func, data, destroy);
1365
1366   if (tree_model_sort->sort_column_id == sort_column_id)
1367     gtk_tree_model_sort_sort (tree_model_sort);
1368 }
1369
1370 static void
1371 gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
1372                                            GtkTreeIterCompareFunc  func,
1373                                            gpointer                data,
1374                                            GtkDestroyNotify        destroy)
1375 {
1376   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1377
1378   if (tree_model_sort->default_sort_destroy)
1379     {
1380       GtkDestroyNotify d = tree_model_sort->default_sort_destroy;
1381
1382       tree_model_sort->default_sort_destroy = NULL;
1383       d (tree_model_sort->default_sort_data);
1384     }
1385
1386   tree_model_sort->default_sort_func = func;
1387   tree_model_sort->default_sort_data = data;
1388   tree_model_sort->default_sort_destroy = destroy;
1389
1390   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1391     gtk_tree_model_sort_sort (tree_model_sort);
1392 }
1393
1394 static gboolean
1395 gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable *sortable)
1396 {
1397   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1398
1399   return (tree_model_sort->default_sort_func != NULL);
1400 }
1401
1402 /* DragSource interface */
1403 static gboolean
1404 gtk_tree_model_sort_row_draggable (GtkTreeDragSource *drag_source,
1405                                    GtkTreePath       *path)
1406 {
1407   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1408   GtkTreePath *child_path;
1409   gboolean draggable;
1410
1411   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort,
1412                                                                path);
1413   draggable = gtk_tree_drag_source_row_draggable (GTK_TREE_DRAG_SOURCE (tree_model_sort->child_model), child_path);
1414   gtk_tree_path_free (child_path);
1415
1416   return draggable;
1417 }
1418
1419 static gboolean
1420 gtk_tree_model_sort_drag_data_get (GtkTreeDragSource *drag_source,
1421                                    GtkTreePath       *path,
1422                                    GtkSelectionData  *selection_data)
1423 {
1424   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1425   GtkTreePath *child_path;
1426   gboolean gotten;
1427
1428   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort, path);
1429   gotten = gtk_tree_drag_source_drag_data_get (GTK_TREE_DRAG_SOURCE (tree_model_sort->child_model), child_path, selection_data);
1430   gtk_tree_path_free (child_path);
1431
1432   return gotten;
1433 }
1434
1435 static gboolean
1436 gtk_tree_model_sort_drag_data_delete (GtkTreeDragSource *drag_source,
1437                                       GtkTreePath       *path)
1438 {
1439   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1440   GtkTreePath *child_path;
1441   gboolean deleted;
1442
1443   child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort, path);
1444   deleted = gtk_tree_drag_source_drag_data_delete (GTK_TREE_DRAG_SOURCE (tree_model_sort->child_model), child_path);
1445   gtk_tree_path_free (child_path);
1446
1447   return deleted;
1448 }
1449
1450 /* sorting code - private */
1451 static gint
1452 gtk_tree_model_sort_compare_func (gconstpointer a,
1453                                   gconstpointer b,
1454                                   gpointer      user_data)
1455 {
1456   SortData *data = (SortData *)user_data;
1457   GtkTreeModelSort *tree_model_sort = data->tree_model_sort;
1458   SortTuple *sa = (SortTuple *)a;
1459   SortTuple *sb = (SortTuple *)b;
1460
1461   GtkTreeIter iter_a, iter_b;
1462   gint retval;
1463
1464   /* shortcut, if we've the same offsets here, they should be equal */
1465   if (sa->offset == sb->offset)
1466     return 0;
1467
1468   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1469     {
1470       iter_a = sa->elt->iter;
1471       iter_b = sb->elt->iter;
1472     }
1473   else
1474     {
1475       data->parent_path_indices [data->parent_path_depth-1] = sa->elt->offset;
1476       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort->child_model), &iter_a, data->parent_path);
1477       data->parent_path_indices [data->parent_path_depth-1] = sb->elt->offset;
1478       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort->child_model), &iter_b, data->parent_path);
1479     }
1480
1481   retval = (* data->sort_func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1482                                 &iter_a, &iter_b,
1483                                 data->sort_data);
1484
1485   if (tree_model_sort->order == GTK_SORT_DESCENDING)
1486     {
1487       if (retval > 0)
1488         retval = -1;
1489       else if (retval < 0)
1490         retval = 1;
1491     }
1492
1493   return retval;
1494 }
1495
1496 static gint
1497 gtk_tree_model_sort_offset_compare_func (gconstpointer a,
1498                                          gconstpointer b,
1499                                          gpointer      user_data)
1500 {
1501   gint retval;
1502
1503   SortTuple *sa = (SortTuple *)a;
1504   SortTuple *sb = (SortTuple *)b;
1505
1506   SortData *data = (SortData *)user_data;
1507
1508   if (sa->elt->offset < sb->elt->offset)
1509     retval = -1;
1510   else if (sa->elt->offset > sb->elt->offset)
1511     retval = 1;
1512   else
1513     retval = 0;
1514
1515   if (data->tree_model_sort->order == GTK_SORT_DESCENDING)
1516     {
1517       if (retval > 0)
1518         retval = -1;
1519       else if (retval < 0)
1520         retval = 1;
1521     }
1522
1523   return retval;
1524 }
1525
1526 static void
1527 gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
1528                                 SortLevel        *level,
1529                                 gboolean          recurse,
1530                                 gboolean          emit_reordered)
1531 {
1532   gint i;
1533   gint ref_offset;
1534   GArray *sort_array;
1535   GArray *new_array;
1536   gint *new_order;
1537
1538   GtkTreeIter iter;
1539   GtkTreePath *path;
1540
1541   SortData data;
1542
1543   g_return_if_fail (level != NULL);
1544
1545   if (level->array->len < 1 && !((SortElt *)level->array->data)->children)
1546     return;
1547
1548   iter.stamp = tree_model_sort->stamp;
1549   iter.user_data = level;
1550   iter.user_data2 = &g_array_index (level->array, SortElt, 0);
1551
1552   gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (tree_model_sort), &iter);
1553   ref_offset = g_array_index (level->array, SortElt, 0).offset;
1554
1555   /* Set up data */
1556   data.tree_model_sort = tree_model_sort;
1557   if (level->parent_elt)
1558     {
1559       data.parent_path = gtk_tree_model_sort_elt_get_path (level->parent_level,
1560                                                            level->parent_elt);
1561       gtk_tree_path_append_index (data.parent_path, 0);
1562     }
1563   else
1564     {
1565       data.parent_path = gtk_tree_path_new_first ();
1566     }
1567   data.parent_path_depth = gtk_tree_path_get_depth (data.parent_path);
1568   data.parent_path_indices = gtk_tree_path_get_indices (data.parent_path);
1569
1570   /* make the array to be sorted */
1571   sort_array = g_array_sized_new (FALSE, FALSE, sizeof (SortTuple), level->array->len);
1572   for (i = 0; i < level->array->len; i++)
1573     {
1574       SortTuple tuple;
1575
1576       tuple.elt = &g_array_index (level->array, SortElt, i);
1577       tuple.offset = i;
1578
1579       g_array_append_val (sort_array, tuple);
1580     }
1581
1582     if (tree_model_sort->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1583       {
1584         GtkTreeDataSortHeader *header = NULL;
1585
1586         header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1587                                                  tree_model_sort->sort_column_id);
1588
1589         g_return_if_fail (header != NULL);
1590         g_return_if_fail (header->func != NULL);
1591
1592         data.sort_func = header->func;
1593         data.sort_data = header->data;
1594       }
1595     else
1596       {
1597         /* absolutely SHOULD NOT happen: */
1598         g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1599
1600         data.sort_func = tree_model_sort->default_sort_func;
1601         data.sort_data = tree_model_sort->default_sort_data;
1602       }
1603
1604   if (data.sort_func == NO_SORT_FUNC)
1605     g_array_sort_with_data (sort_array,
1606                             gtk_tree_model_sort_offset_compare_func,
1607                             &data);
1608   else
1609     g_array_sort_with_data (sort_array,
1610                             gtk_tree_model_sort_compare_func,
1611                             &data);
1612
1613   gtk_tree_path_free (data.parent_path);
1614
1615   new_array = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), level->array->len);
1616   new_order = g_new (gint, level->array->len);
1617
1618   for (i = 0; i < level->array->len; i++)
1619     {
1620       SortElt *elt;
1621
1622       elt = g_array_index (sort_array, SortTuple, i).elt;
1623       new_order[i] = g_array_index (sort_array, SortTuple, i).offset;
1624
1625       g_array_append_val (new_array, *elt);
1626       elt = &g_array_index (new_array, SortElt, i);
1627       if (elt->children)
1628         elt->children->parent_elt = elt;
1629     }
1630
1631   g_array_free (level->array, TRUE);
1632   level->array = new_array;
1633   g_array_free (sort_array, TRUE);
1634
1635   if (emit_reordered)
1636     {
1637       gtk_tree_model_sort_increment_stamp (tree_model_sort);
1638       if (level->parent_elt)
1639         {
1640           iter.stamp = tree_model_sort->stamp;
1641           iter.user_data = level->parent_level;
1642           iter.user_data2 = level->parent_elt;
1643
1644           path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort),
1645                                           &iter);
1646
1647           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1648                                          &iter, new_order);
1649         }
1650       else
1651         {
1652           /* toplevel list */
1653           path = gtk_tree_path_new ();
1654           gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1655                                          NULL, new_order);
1656         }
1657
1658       gtk_tree_path_free (path);
1659     }
1660
1661   /* recurse, if possible */
1662   if (recurse)
1663     {
1664       for (i = 0; i < level->array->len; i++)
1665         {
1666           SortElt *elt = &g_array_index (level->array, SortElt, i);
1667
1668           if (elt->children)
1669             gtk_tree_model_sort_sort_level (tree_model_sort,
1670                                             elt->children,
1671                                             TRUE, emit_reordered);
1672         }
1673     }
1674
1675   g_free (new_order);
1676
1677   /* get the iter we referenced at the beginning of this function and
1678    * unref it again
1679    */
1680   iter.stamp = tree_model_sort->stamp;
1681   iter.user_data = level;
1682
1683   for (i = 0; i < level->array->len; i++)
1684     {
1685       if (g_array_index (level->array, SortElt, i).offset == ref_offset)
1686         {
1687           iter.user_data2 = &g_array_index (level->array, SortElt, i);
1688           break;
1689         }
1690     }
1691
1692   gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (tree_model_sort), &iter);
1693 }
1694
1695 static void
1696 gtk_tree_model_sort_sort (GtkTreeModelSort *tree_model_sort)
1697 {
1698   if (!tree_model_sort->root)
1699     return;
1700
1701   if (tree_model_sort->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1702     {
1703       GtkTreeDataSortHeader *header = NULL;
1704
1705       header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1706                                                tree_model_sort->sort_column_id);
1707
1708       /* we want to make sure that we have a function */
1709       g_return_if_fail (header != NULL);
1710       g_return_if_fail (header->func != NULL);
1711     }
1712   else
1713     g_return_if_fail (tree_model_sort->default_sort_func != NULL);
1714
1715   gtk_tree_model_sort_sort_level (tree_model_sort, tree_model_sort->root,
1716                                   TRUE, TRUE);
1717 }
1718
1719 /* signal helpers */
1720 static gint
1721 gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
1722                                        SortLevel        *level,
1723                                        GtkTreeIter      *iter,
1724                                        gint             skip_index)
1725 {
1726   gint start, middle, end;
1727   gint cmp;
1728   SortElt *tmp_elt;
1729   GtkTreeIter tmp_iter;
1730
1731   GtkTreeIterCompareFunc func;
1732   gpointer data;
1733
1734   if (tree_model_sort->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1735     {
1736       GtkTreeDataSortHeader *header;
1737
1738       header = _gtk_tree_data_list_get_header (tree_model_sort->sort_list,
1739                                                tree_model_sort->sort_column_id);
1740
1741       g_return_val_if_fail (header != NULL, 0);
1742
1743       func = header->func;
1744       data = header->data;
1745     }
1746   else
1747     {
1748       func = tree_model_sort->default_sort_func;
1749       data = tree_model_sort->default_sort_data;
1750
1751       g_return_val_if_fail (func != NO_SORT_FUNC, 0);
1752     }
1753
1754   g_return_val_if_fail (func != NULL, 0);
1755
1756   start = 0;
1757   end = level->array->len;
1758   if (skip_index < 0)
1759     skip_index = end;
1760   else
1761     end--;
1762
1763   if (start == end)
1764     return 0;
1765
1766   while (start != end)
1767     {
1768       middle = (start + end) / 2;
1769
1770       if (middle < skip_index)
1771         tmp_elt = &(g_array_index (level->array, SortElt, middle));
1772       else
1773         tmp_elt = &(g_array_index (level->array, SortElt, middle + 1));
1774
1775       if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1776         {
1777           GtkTreePath *path = gtk_tree_model_sort_elt_get_path (level, tmp_elt);
1778           gtk_tree_model_get_iter (tree_model_sort->child_model,
1779                                    &tmp_iter, path);
1780           gtk_tree_path_free (path);
1781         }
1782       else
1783         tmp_iter = tmp_elt->iter;
1784
1785       if (tree_model_sort->order == GTK_SORT_ASCENDING)
1786         cmp = (* func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1787                         &tmp_iter, iter, data);
1788       else
1789         cmp = (* func) (GTK_TREE_MODEL (tree_model_sort->child_model),
1790                         iter, &tmp_iter, data);
1791
1792       if (cmp <= 0)
1793         start = middle + 1;
1794       else
1795         end = middle;
1796     }
1797
1798   if (cmp <= 0)
1799     return middle + 1;
1800   else
1801     return middle;
1802 }
1803
1804 static gboolean
1805 gtk_tree_model_sort_insert_value (GtkTreeModelSort *tree_model_sort,
1806                                   SortLevel        *level,
1807                                   GtkTreePath      *s_path,
1808                                   GtkTreeIter      *s_iter)
1809 {
1810   gint offset, index, i;
1811
1812   SortElt elt;
1813   SortElt *tmp_elt;
1814
1815   offset = gtk_tree_path_get_indices (s_path)[gtk_tree_path_get_depth (s_path) - 1];
1816
1817   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1818     elt.iter = *s_iter;
1819   elt.offset = offset;
1820   elt.zero_ref_count = 0;
1821   elt.ref_count = 0;
1822   elt.children = NULL;
1823
1824   /* update all larger offsets */
1825   tmp_elt = SORT_ELT (level->array->data);
1826   for (i = 0; i < level->array->len; i++, tmp_elt++)
1827     if (tmp_elt->offset >= offset)
1828       tmp_elt->offset++;
1829
1830   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
1831       tree_model_sort->default_sort_func == NO_SORT_FUNC)
1832     index = offset;
1833   else
1834     index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
1835                                                    level, s_iter,
1836                                                    -1);
1837
1838   g_array_insert_vals (level->array, index, &elt, 1);
1839   tmp_elt = SORT_ELT (level->array->data);
1840   for (i = 0; i < level->array->len; i++, tmp_elt++)
1841     if (tmp_elt->children)
1842       tmp_elt->children->parent_elt = tmp_elt;
1843
1844   return TRUE;
1845 }
1846
1847 /* sort elt stuff */
1848 static GtkTreePath *
1849 gtk_tree_model_sort_elt_get_path (SortLevel *level,
1850                                   SortElt *elt)
1851 {
1852   SortLevel *walker = level;
1853   SortElt *walker2 = elt;
1854   GtkTreePath *path;
1855
1856   g_return_val_if_fail (level != NULL, NULL);
1857   g_return_val_if_fail (elt != NULL, NULL);
1858
1859   path = gtk_tree_path_new ();
1860
1861   while (walker)
1862     {
1863       gtk_tree_path_prepend_index (path, walker2->offset);
1864
1865       walker2 = walker->parent_elt;
1866       walker = walker->parent_level;
1867     }
1868
1869   return path;
1870 }
1871
1872 /**
1873  * gtk_tree_model_sort_set_model:
1874  * @tree_model_sort: The #GtkTreeModelSort.
1875  * @child_model: A #GtkTreeModel, or %NULL.
1876  *
1877  * Sets the model of @tree_model_sort to be @model.  If @model is %NULL,
1878  * then the old model is unset.  The sort function is unset as a result
1879  * of this call. The model will be in an unsorted state until a sort
1880  * function is set.
1881  **/
1882 static void
1883 gtk_tree_model_sort_set_model (GtkTreeModelSort *tree_model_sort,
1884                                GtkTreeModel     *child_model)
1885 {
1886   if (child_model)
1887     g_object_ref (child_model);
1888
1889   if (tree_model_sort->child_model)
1890     {
1891       g_signal_handler_disconnect (tree_model_sort->child_model,
1892                                    tree_model_sort->changed_id);
1893       g_signal_handler_disconnect (tree_model_sort->child_model,
1894                                    tree_model_sort->inserted_id);
1895       g_signal_handler_disconnect (tree_model_sort->child_model,
1896                                    tree_model_sort->has_child_toggled_id);
1897       g_signal_handler_disconnect (tree_model_sort->child_model,
1898                                    tree_model_sort->deleted_id);
1899       g_signal_handler_disconnect (tree_model_sort->child_model,
1900                                    tree_model_sort->reordered_id);
1901
1902       /* reset our state */
1903       if (tree_model_sort->root)
1904         gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
1905       tree_model_sort->root = NULL;
1906       _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
1907       tree_model_sort->sort_list = NULL;
1908       g_object_unref (tree_model_sort->child_model);
1909     }
1910
1911   tree_model_sort->child_model = child_model;
1912
1913   if (child_model)
1914     {
1915       GType *types;
1916       gint i, n_columns;
1917
1918       tree_model_sort->changed_id =
1919         g_signal_connect (child_model, "row_changed",
1920                           G_CALLBACK (gtk_tree_model_sort_row_changed),
1921                           tree_model_sort);
1922       tree_model_sort->inserted_id =
1923         g_signal_connect (child_model, "row_inserted",
1924                           G_CALLBACK (gtk_tree_model_sort_row_inserted),
1925                           tree_model_sort);
1926       tree_model_sort->has_child_toggled_id =
1927         g_signal_connect (child_model, "row_has_child_toggled",
1928                           G_CALLBACK (gtk_tree_model_sort_row_has_child_toggled),
1929                           tree_model_sort);
1930       tree_model_sort->deleted_id =
1931         g_signal_connect (child_model, "row_deleted",
1932                           G_CALLBACK (gtk_tree_model_sort_row_deleted),
1933                           tree_model_sort);
1934       tree_model_sort->reordered_id =
1935         g_signal_connect (child_model, "rows_reordered",
1936                           G_CALLBACK (gtk_tree_model_sort_rows_reordered),
1937                           tree_model_sort);
1938
1939       tree_model_sort->child_flags = gtk_tree_model_get_flags (child_model);
1940       n_columns = gtk_tree_model_get_n_columns (child_model);
1941
1942       types = g_new (GType, n_columns);
1943       for (i = 0; i < n_columns; i++)
1944         types[i] = gtk_tree_model_get_column_type (child_model, i);
1945
1946       tree_model_sort->sort_list = _gtk_tree_data_list_header_new (n_columns, types);
1947       g_free (types);
1948
1949       tree_model_sort->default_sort_func = NO_SORT_FUNC;
1950       tree_model_sort->stamp = g_random_int ();
1951     }
1952 }
1953
1954 /**
1955  * gtk_tree_model_sort_get_model:
1956  * @tree_model: a #GtkTreeModelSort
1957  *
1958  * Returns the model the #GtkTreeModelSort is sorting.
1959  *
1960  * Return value: the "child model" being sorted
1961  **/
1962 GtkTreeModel *
1963 gtk_tree_model_sort_get_model (GtkTreeModelSort *tree_model)
1964 {
1965   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
1966
1967   return tree_model->child_model;
1968 }
1969
1970
1971 static GtkTreePath *
1972 gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
1973                                                      GtkTreePath      *child_path,
1974                                                      gboolean          build_levels)
1975 {
1976   gint *child_indices;
1977   GtkTreePath *retval;
1978   SortLevel *level;
1979   gint i;
1980
1981   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
1982   g_return_val_if_fail (child_path != NULL, NULL);
1983
1984   retval = gtk_tree_path_new ();
1985   child_indices = gtk_tree_path_get_indices (child_path);
1986
1987   if (tree_model_sort->root == NULL && build_levels)
1988     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1989   level = SORT_LEVEL (tree_model_sort->root);
1990
1991   for (i = 0; i < gtk_tree_path_get_depth (child_path); i++)
1992     {
1993       gint j;
1994       gboolean found_child = FALSE;
1995
1996       if (!level)
1997         {
1998           gtk_tree_path_free (retval);
1999           return NULL;
2000         }
2001
2002       if (child_indices[i] >= level->array->len)
2003         {
2004           gtk_tree_path_free (retval);
2005           return NULL;
2006         }
2007       for (j = 0; j < level->array->len; j++)
2008         {
2009           if ((g_array_index (level->array, SortElt, j)).offset == child_indices[i])
2010             {
2011               gtk_tree_path_append_index (retval, j);
2012               if (g_array_index (level->array, SortElt, j).children == NULL && build_levels)
2013                 {
2014                   gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, j));
2015                 }
2016               level = g_array_index (level->array, SortElt, j).children;
2017               found_child = TRUE;
2018               break;
2019             }
2020         }
2021       if (! found_child)
2022         {
2023           gtk_tree_path_free (retval);
2024           return NULL;
2025         }
2026     }
2027
2028   return retval;
2029 }
2030
2031
2032 /**
2033  * gtk_tree_model_sort_convert_child_path_to_path:
2034  * @tree_model_sort: A #GtkTreeModelSort
2035  * @child_path: A #GtkTreePath to convert
2036  *
2037  * Converts @child_path to a path relative to @tree_model_sort.  That is,
2038  * @child_path points to a path in the child model.  The returned path will
2039  * point to the same row in the sorted model.  If @child_path isn't a valid
2040  * path on the child model, then %NULL is returned.
2041  *
2042  * Return value: A newly allocated #GtkTreePath, or %NULL
2043  **/
2044 GtkTreePath *
2045 gtk_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
2046                                                 GtkTreePath      *child_path)
2047 {
2048   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2049   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
2050   g_return_val_if_fail (child_path != NULL, NULL);
2051
2052   return gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path, TRUE);
2053 }
2054
2055 /**
2056  * gtk_tree_model_sort_convert_child_iter_to_iter:
2057  * @tree_model_sort: A #GtkTreeModelSort
2058  * @sort_iter: An uninitialized #GtkTreeIter.
2059  * @child_iter: A valid #GtkTreeIter pointing to a row on the child model
2060  *
2061  * Sets @sort_iter to point to the row in @tree_model_sort that corresponds to
2062  * the row pointed at by @child_iter.
2063  **/
2064 void
2065 gtk_tree_model_sort_convert_child_iter_to_iter (GtkTreeModelSort *tree_model_sort,
2066                                                 GtkTreeIter      *sort_iter,
2067                                                 GtkTreeIter      *child_iter)
2068 {
2069   GtkTreePath *child_path, *path;
2070
2071   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2072   g_return_if_fail (tree_model_sort->child_model != NULL);
2073   g_return_if_fail (sort_iter != NULL);
2074   g_return_if_fail (child_iter != NULL);
2075
2076   sort_iter->stamp = 0;
2077
2078   child_path = gtk_tree_model_get_path (tree_model_sort->child_model, child_iter);
2079   g_return_if_fail (child_path != NULL);
2080
2081   path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path);
2082   gtk_tree_path_free (child_path);
2083   g_return_if_fail (path != NULL);
2084
2085   gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort), sort_iter, path);
2086   gtk_tree_path_free (path);
2087 }
2088
2089 /**
2090  * gtk_tree_model_sort_convert_path_to_child_path:
2091  * @tree_model_sort: A #GtkTreeModelSort
2092  * @sorted_path: A #GtkTreePath to convert
2093  *
2094  * Converts @sorted_path to a path on the child model of @tree_model_sort.
2095  * That is, @sorted_path points to a location in @tree_model_sort.  The
2096  * returned path will point to the same location in the model not being
2097  * sorted.  If @sorted_path does not point to a location in the child model,
2098  * %NULL is returned.
2099  *
2100  * Return value: A newly allocated #GtkTreePath, or %NULL
2101  **/
2102 GtkTreePath *
2103 gtk_tree_model_sort_convert_path_to_child_path (GtkTreeModelSort *tree_model_sort,
2104                                                 GtkTreePath      *sorted_path)
2105 {
2106   gint *sorted_indices;
2107   GtkTreePath *retval;
2108   SortLevel *level;
2109   gint i;
2110
2111   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2112   g_return_val_if_fail (tree_model_sort->child_model != NULL, NULL);
2113   g_return_val_if_fail (sorted_path != NULL, NULL);
2114
2115   retval = gtk_tree_path_new ();
2116   sorted_indices = gtk_tree_path_get_indices (sorted_path);
2117   if (tree_model_sort->root == NULL)
2118     gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
2119   level = SORT_LEVEL (tree_model_sort->root);
2120
2121   for (i = 0; i < gtk_tree_path_get_depth (sorted_path); i++)
2122     {
2123       gint count = sorted_indices[i];
2124
2125       if ((level == NULL) ||
2126           (level->array->len <= count))
2127         {
2128           gtk_tree_path_free (retval);
2129           return NULL;
2130         }
2131
2132       if (g_array_index (level->array, SortElt, count).children == NULL)
2133         gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, count));
2134
2135       if (level == NULL)
2136         {
2137           gtk_tree_path_free (retval);
2138           break;
2139         }
2140
2141       gtk_tree_path_append_index (retval, g_array_index (level->array, SortElt, count).offset);
2142       level = g_array_index (level->array, SortElt, count).children;
2143     }
2144
2145   return retval;
2146 }
2147
2148 /**
2149  * gtk_tree_model_sort_convert_iter_to_child_iter:
2150  * @tree_model_sort: A #GtkTreeModelSort
2151  * @child_iter: An uninitialized #GtkTreeIter
2152  * @sorted_iter: A valid #GtkTreeIter pointing to a row on @tree_model_sort.
2153  *
2154  * Sets @child_iter to point to the row pointed to by @sorted_iter.
2155  **/
2156 void
2157 gtk_tree_model_sort_convert_iter_to_child_iter (GtkTreeModelSort *tree_model_sort,
2158                                                 GtkTreeIter      *child_iter,
2159                                                 GtkTreeIter      *sorted_iter)
2160 {
2161   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2162   g_return_if_fail (tree_model_sort->child_model != NULL);
2163   g_return_if_fail (child_iter != NULL);
2164   g_return_if_fail (VALID_ITER (sorted_iter, tree_model_sort));
2165
2166   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2167     {
2168       *child_iter = SORT_ELT (sorted_iter->user_data2)->iter;
2169     }
2170   else
2171     {
2172       GtkTreePath *path;
2173
2174       path = gtk_tree_model_sort_elt_get_path (sorted_iter->user_data,
2175                                                sorted_iter->user_data2);
2176       gtk_tree_model_get_iter (tree_model_sort->child_model, child_iter, path);
2177       gtk_tree_path_free (path);
2178     }
2179 }
2180
2181 static void
2182 gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
2183                                  SortLevel        *parent_level,
2184                                  SortElt          *parent_elt)
2185 {
2186   GtkTreeIter iter;
2187   SortLevel *new_level;
2188   gint length = 0;
2189   gint i;
2190
2191   g_assert (tree_model_sort->child_model != NULL);
2192
2193   if (parent_level == NULL)
2194     {
2195       if (gtk_tree_model_get_iter_first (tree_model_sort->child_model, &iter) == FALSE)
2196         return;
2197       length = gtk_tree_model_iter_n_children (tree_model_sort->child_model, NULL);
2198     }
2199   else
2200     {
2201       GtkTreeIter parent_iter;
2202       GtkTreeIter child_parent_iter;
2203
2204       parent_iter.stamp = tree_model_sort->stamp;
2205       parent_iter.user_data = parent_level;
2206       parent_iter.user_data2 = parent_elt;
2207
2208       gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2209                                                       &child_parent_iter,
2210                                                       &parent_iter);
2211       if (gtk_tree_model_iter_children (tree_model_sort->child_model,
2212                                         &iter,
2213                                         &child_parent_iter) == FALSE)
2214         return;
2215
2216       /* stamp may have changed */
2217       gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2218                                                       &child_parent_iter,
2219                                                       &parent_iter);
2220
2221       length = gtk_tree_model_iter_n_children (tree_model_sort->child_model, &child_parent_iter);
2222     }
2223
2224   g_return_if_fail (length > 0);
2225
2226   new_level = g_new (SortLevel, 1);
2227   new_level->array = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), length);
2228   new_level->ref_count = 0;
2229   new_level->parent_elt = parent_elt;
2230   new_level->parent_level = parent_level;
2231
2232   if (parent_elt)
2233     parent_elt->children = new_level;
2234   else
2235     tree_model_sort->root = new_level;
2236
2237   /* increase the count of zero ref_counts.*/
2238   while (parent_level)
2239     {
2240       parent_elt->zero_ref_count++;
2241
2242       parent_elt = parent_level->parent_elt;
2243       parent_level = parent_level->parent_level;
2244     }
2245   if (new_level != tree_model_sort->root)
2246     tree_model_sort->zero_ref_count++;
2247
2248   for (i = 0; i < length; i++)
2249     {
2250       SortElt sort_elt;
2251       sort_elt.offset = i;
2252       sort_elt.zero_ref_count = 0;
2253       sort_elt.ref_count = 0;
2254       sort_elt.children = NULL;
2255
2256       if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2257         {
2258           sort_elt.iter = iter;
2259           if (gtk_tree_model_iter_next (tree_model_sort->child_model, &iter) == FALSE &&
2260               i < length - 1)
2261             {
2262               g_warning ("There is a discrepancy between the sort model and the child model.");
2263               return;
2264             }
2265         }
2266       g_array_append_val (new_level->array, sort_elt);
2267     }
2268
2269   /* sort level */
2270   gtk_tree_model_sort_sort_level (tree_model_sort, new_level,
2271                                   FALSE, FALSE);
2272 }
2273
2274 static void
2275 gtk_tree_model_sort_free_level (GtkTreeModelSort *tree_model_sort,
2276                                 SortLevel        *sort_level)
2277 {
2278   gint i;
2279
2280   g_assert (sort_level);
2281
2282   for (i = 0; i < sort_level->array->len; i++)
2283     {
2284       if (g_array_index (sort_level->array, SortElt, i).children)
2285         gtk_tree_model_sort_free_level (tree_model_sort,
2286                                         SORT_LEVEL (g_array_index (sort_level->array, SortElt, i).children));
2287     }
2288
2289   if (sort_level->ref_count == 0)
2290     {
2291       SortLevel *parent_level = sort_level->parent_level;
2292       SortElt *parent_elt = sort_level->parent_elt;
2293
2294       while (parent_level)
2295         {
2296           parent_elt->zero_ref_count--;
2297
2298           parent_elt = parent_level->parent_elt;
2299           parent_level = parent_level->parent_level;
2300         }
2301
2302       if (sort_level != tree_model_sort->root)
2303         tree_model_sort->zero_ref_count--;
2304     }
2305
2306   if (sort_level->parent_elt)
2307     sort_level->parent_elt->children = NULL;
2308   else
2309     tree_model_sort->root = NULL;
2310
2311   g_array_free (sort_level->array, TRUE);
2312   sort_level->array = NULL;
2313
2314   g_free (sort_level);
2315   sort_level = NULL;
2316 }
2317
2318 static void
2319 gtk_tree_model_sort_increment_stamp (GtkTreeModelSort *tree_model_sort)
2320 {
2321   do
2322     {
2323       tree_model_sort->stamp++;
2324     }
2325   while (tree_model_sort->stamp == 0);
2326
2327   gtk_tree_model_sort_clear_cache (tree_model_sort);
2328 }
2329
2330 static void
2331 gtk_tree_model_sort_clear_cache_helper (GtkTreeModelSort *tree_model_sort,
2332                                         SortLevel        *level)
2333 {
2334   gint i;
2335
2336   g_assert (level != NULL);
2337
2338   for (i = 0; i < level->array->len; i++)
2339     {
2340       if (g_array_index (level->array, SortElt, i).zero_ref_count > 0)
2341         gtk_tree_model_sort_clear_cache_helper (tree_model_sort, g_array_index (level->array, SortElt, i).children);
2342     }
2343
2344   if (level->ref_count == 0 && level != tree_model_sort->root)
2345     gtk_tree_model_sort_free_level (tree_model_sort, level);
2346 }
2347
2348 /**
2349  * gtk_tree_model_sort_reset_default_sort_func:
2350  * @tree_model_sort: A #GtkTreeModelSort
2351  *
2352  * This resets the default sort function to be in the 'unsorted' state.  That
2353  * is, it is in the same order as the child model. It will re-sort the model
2354  * to be in the same order as the child model only if the #GtkTreeModelSort
2355  * is in 'unsorted' state.
2356  **/
2357 void
2358 gtk_tree_model_sort_reset_default_sort_func (GtkTreeModelSort *tree_model_sort)
2359 {
2360   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2361
2362   if (tree_model_sort->default_sort_destroy)
2363     {
2364       GtkDestroyNotify d = tree_model_sort->default_sort_destroy;
2365
2366       tree_model_sort->default_sort_destroy = NULL;
2367       d (tree_model_sort->default_sort_data);
2368     }
2369
2370   tree_model_sort->default_sort_func = NO_SORT_FUNC;
2371   tree_model_sort->default_sort_data = NULL;
2372   tree_model_sort->default_sort_destroy = NULL;
2373
2374   if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
2375     gtk_tree_model_sort_sort (tree_model_sort);
2376   tree_model_sort->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
2377 }
2378
2379 /**
2380  * gtk_tree_model_sort_clear_cache:
2381  * @tree_model_sort: A #GtkTreeModelSort
2382  *
2383  * This function should almost never be called.  It clears the @tree_model_sort
2384  * of any cached iterators that haven't been reffed with
2385  * gtk_tree_model_ref_node().  This might be useful if the child model being
2386  * sorted is static (and doesn't change often) and there has been a lot of
2387  * unreffed access to nodes.  As a side effect of this function, all unreffed
2388  * iters will be invalid.
2389  **/
2390 void
2391 gtk_tree_model_sort_clear_cache (GtkTreeModelSort *tree_model_sort)
2392 {
2393   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2394
2395   if (tree_model_sort->zero_ref_count > 0)
2396     gtk_tree_model_sort_clear_cache_helper (tree_model_sort, (SortLevel *)tree_model_sort->root);
2397 }
2398
2399 static gboolean
2400 gtk_tree_model_sort_iter_is_valid_helper (GtkTreeIter *iter,
2401                                           SortLevel   *level)
2402 {
2403   gint i;
2404
2405   for (i = 0; i < level->array->len; i++)
2406     {
2407       SortElt *elt = &g_array_index (level->array, SortElt, i);
2408
2409       if (iter->user_data == level && iter->user_data2 == elt)
2410         return TRUE;
2411
2412       if (elt->children)
2413         if (gtk_tree_model_sort_iter_is_valid_helper (iter, elt->children))
2414           return TRUE;
2415     }
2416
2417   return FALSE;
2418 }
2419
2420 /**
2421  * gtk_tree_model_sort_iter_is_valid:
2422  * @tree_model_sort: A #GtkTreeModelSort.
2423  * @iter: A #GtkTreeIter.
2424  *
2425  * <warning><para>
2426  * This function is slow. Only use it for debugging and/or testing purposes.
2427  * </para></warning>
2428  *
2429  * Checks if the given iter is a valid iter for this #GtkTreeModelSort.
2430  *
2431  * Return value: %TRUE if the iter is valid, %FALSE if the iter is invalid.
2432  *
2433  * Since: 2.2
2434  **/
2435 gboolean
2436 gtk_tree_model_sort_iter_is_valid (GtkTreeModelSort *tree_model_sort,
2437                                    GtkTreeIter      *iter)
2438 {
2439   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), FALSE);
2440   g_return_val_if_fail (iter != NULL, FALSE);
2441
2442   if (!VALID_ITER (iter, tree_model_sort))
2443     return FALSE;
2444
2445   return gtk_tree_model_sort_iter_is_valid_helper (iter,
2446                                                    tree_model_sort->root);
2447 }
2448
2449 #define __GTK_TREE_MODEL_SORT_C__
2450 #include "gtkaliasdef.c"