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