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