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