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