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

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