gtktreemodelsort.c 83.8 KB
Newer Older
1
/* gtktreemodelsort.c
2
 * Copyright (C) 2000,2001  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
3
 * Copyright (C) 2001,2002  Kristian Rietveld <kris@gtk.org>
4 5 6 7 8 9 10 11 12 13 14 15
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
Javier Jardón's avatar
Javier Jardón committed
16
 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
17 18
 */

19
#include "config.h"
Manish Singh's avatar
Manish Singh committed
20 21
#include <string.h>

22
#include "gtktreemodelsort.h"
23
#include "gtktreesortable.h"
24
#include "gtktreestore.h"
25
#include "gtktreedatalist.h"
26
#include "gtkintl.h"
27
#include "gtkprivate.h"
28
#include "gtktreednd.h"
29

30

31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
/**
 * SECTION:gtktreemodelsort
 * @Short_description: A GtkTreeModel which makes an underlying tree model sortable
 * @Title: GtkTreeModelSort
 * @See_also: #GtkTreeModel, #GtkListStore, #GtkTreeStore, #GtkTreeSortable, #GtkTreeModelFilter
 *
 * The #GtkTreeModelSort is a model which implements the #GtkTreeSortable
 * interface.  It does not hold any data itself, but rather is created with
 * a child model and proxies its data.  It has identical column types to
 * this child model, and the changes in the child are propagated.  The
 * primary purpose of this model is to provide a way to sort a different
 * model without modifying it. Note that the sort function used by
 * #GtkTreeModelSort is not guaranteed to be stable.
 *
 * The use of this is best demonstrated through an example.  In the
 * following sample code we create two #GtkTreeView widgets each with a
 * view of the same data.  As the model is wrapped here by a
48
 * #GtkTreeModelSort, the two #GtkTreeViews can each sort their
49 50 51 52
 * view of the data without affecting the other.  By contrast, if we
 * simply put the same model in each widget, then sorting the first would
 * sort the second.
 *
53 54
 * ## Using a #GtkTreeModelSort
 *
55
 * |[<!-- language="C" -->
56 57 58 59 60 61 62
 * {
 *   GtkTreeView *tree_view1;
 *   GtkTreeView *tree_view2;
 *   GtkTreeModel *sort_model1;
 *   GtkTreeModel *sort_model2;
 *   GtkTreeModel *child_model;
 *
63
 *   // get the child model
64 65
 *   child_model = get_my_model ();
 *
66
 *   // Create the first tree
67 68 69
 *   sort_model1 = gtk_tree_model_sort_new_with_model (child_model);
 *   tree_view1 = gtk_tree_view_new_with_model (sort_model1);
 *
70
 *   // Create the second tree
71 72 73
 *   sort_model2 = gtk_tree_model_sort_new_with_model (child_model);
 *   tree_view2 = gtk_tree_view_new_with_model (sort_model2);
 *
74
 *   // Now we can sort the two models independently
75 76 77 78 79
 *   gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (sort_model1),
 *                                         COLUMN_1, GTK_SORT_ASCENDING);
 *   gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (sort_model2),
 *                                         COLUMN_1, GTK_SORT_DESCENDING);
 * }
80
 * ]|
81 82 83 84 85 86 87
 *
 * To demonstrate how to access the underlying child model from the sort
 * model, the next example will be a callback for the #GtkTreeSelection
 * #GtkTreeSelection::changed signal.  In this callback, we get a string
 * from COLUMN_1 of the model.  We then modify the string, find the same
 * selected row on the child model, and change the row there.
 *
88 89
 * ## Accessing the child model of in a selection changed callback
 *
90
 * |[<!-- language="C" -->
91 92 93 94 95 96 97 98 99 100
 * void
 * selection_changed (GtkTreeSelection *selection, gpointer data)
 * {
 *   GtkTreeModel *sort_model = NULL;
 *   GtkTreeModel *child_model;
 *   GtkTreeIter sort_iter;
 *   GtkTreeIter child_iter;
 *   char *some_data = NULL;
 *   char *modified_data;
 *
101
 *   // Get the current selected row and the model.
102 103 104 105 106
 *   if (! gtk_tree_selection_get_selected (selection,
 *                                          &sort_model,
 *                                          &sort_iter))
 *     return;
 *
107 108
 *   // Look up the current value on the selected row and get
 *   // a new value to change it to.
109 110 111 112 113 114 115
 *   gtk_tree_model_get (GTK_TREE_MODEL (sort_model), &sort_iter,
 *                       COLUMN_1, &some_data,
 *                       -1);
 *
 *   modified_data = change_the_data (some_data);
 *   g_free (some_data);
 *
116
 *   // Get an iterator on the child model, instead of the sort model.
117 118 119 120
 *   gtk_tree_model_sort_convert_iter_to_child_iter (GTK_TREE_MODEL_SORT (sort_model),
 *                                                   &child_iter,
 *                                                   &sort_iter);
 *
121 122 123
 *   // Get the child model and change the value of the row. In this
 *   // example, the child model is a GtkListStore. It could be any other
 *   // type of model, though.
124 125 126 127 128 129
 *   child_model = gtk_tree_model_sort_get_model (GTK_TREE_MODEL_SORT (sort_model));
 *   gtk_list_store_set (GTK_LIST_STORE (child_model), &child_iter,
 *                       COLUMN_1, &modified_data,
 *                       -1);
 *   g_free (modified_data);
 * }
130
 * ]|
131 132 133
 */


134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
/* Notes on this implementation of GtkTreeModelSort
 * ================================================
 *
 * Warnings
 * --------
 *
 * In this code there is a potential for confusion as to whether an iter,
 * path or value refers to the GtkTreeModelSort model, or to the child model
 * that has been set. As a convention, variables referencing the child model
 * will have an s_ prefix before them (ie. s_iter, s_value, s_path);
 * Conversion of iterators and paths between GtkTreeModelSort and the child
 * model is done through the various gtk_tree_model_sort_convert_* functions.
 *
 * Iterator format
 * ---------------
 *
 * The iterator format of iterators handed out by GtkTreeModelSort is as
 * follows:
 *
 *    iter->stamp = tree_model_sort->stamp
 *    iter->user_data = SortLevel
 *    iter->user_data2 = SortElt
 *
 * Internal data structure
 * -----------------------
 *
160
 * Using SortLevel and SortElt, GtkTreeModelSort maintains a “cache” of
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
 * the mapping from GtkTreeModelSort nodes to nodes in the child model.
 * This is to avoid sorting a level each time an operation is requested
 * on GtkTreeModelSort, such as get iter, get path, get value.
 *
 * A SortElt corresponds to a single node. A node and its siblings are
 * stored in a SortLevel. The SortLevel keeps a reference to the parent
 * SortElt and its SortLevel (if any). The SortElt can have a "children"
 * pointer set, which points at a child level (a sub level).
 *
 * In a SortLevel, nodes are stored in a GSequence. The GSequence
 * allows for fast additions and removals, and supports sorting
 * the level of SortElt nodes.
 *
 * It is important to recognize the two different mappings that play
 * a part in this code:
 *   I.  The mapping from the client to this model. The order in which
 *       nodes are stored in the GSequence is the order in which the
 *       nodes are exposed to clients of the GtkTreeModelSort.
 *   II. The mapping from this model to its child model. Each SortElt
180
 *       contains an “offset” field which is the offset of the
181 182 183 184 185 186 187
 *       corresponding node in the child model.
 *
 * Reference counting
 * ------------------
 *
 * GtkTreeModelSort forwards all reference and unreference operations
 * to the corresponding node in the child model. The reference count
188
 * of each node is also maintained internally, in the “ref_count”
189
 * fields in SortElt and SortLevel. For each ref and unref operation on
190
 * a SortElt, the “ref_count” of the SortLevel is updated accordingly.
191 192 193 194 195 196 197 198 199 200
 * In addition, if a SortLevel has a parent, a reference is taken on
 * this parent. This happens in gtk_tree_model_sort_build_level() and
 * the reference is released again in gtk_tree_model_sort_free_level().
 * This ensures that when GtkTreeModelSort takes a reference on a node
 * (for example during sorting), all parent nodes are referenced
 * according to reference counting rule 1, see the GtkTreeModel
 * documentation.
 *
 * When a level has a reference count of zero, which means that
 * none of the nodes in the level is referenced, the level has
201
 * a “zero ref count” on all its parents. As soon as the level
202 203 204 205 206 207 208 209 210 211 212 213 214 215
 * reaches a reference count of zero, the zero ref count value is
 * incremented by one on all parents of this level. Similarly, as
 * soon as the reference count of a level changes from zero, the
 * zero ref count value is decremented by one on all parents.
 *
 * The zero ref count value is used to clear unused portions of
 * the cache. If a SortElt has a zero ref count of one, then
 * its child level is unused and can be removed from the cache.
 * If the zero ref count value is higher than one, then the
 * child level contains sublevels which are unused as well.
 * gtk_tree_model_sort_clear_cache() uses this to not recurse
 * into levels which have a zero ref count of zero.
 */

216
typedef struct _SortElt SortElt;
217 218 219
typedef struct _SortLevel SortLevel;
typedef struct _SortData SortData;

220 221
struct _SortElt
{
222 223 224 225 226 227
  GtkTreeIter    iter;
  SortLevel     *children;
  gint           offset;
  gint           ref_count;
  gint           zero_ref_count;
  gint           old_index; /* used while sorting */
228
  GSequenceIter *siter; /* iter into seq */
229 230 231 232
};

struct _SortLevel
{
233
  GSequence *seq;
234
  gint       ref_count;
235
  SortElt   *parent_elt;
236
  SortLevel *parent_level;
237 238
};

Jonathan Blandford's avatar
Jonathan Blandford committed
239 240
struct _SortData
{
241
  GtkTreeModelSort *tree_model_sort;
242 243
  GtkTreeIterCompareFunc sort_func;
  gpointer sort_data;
Jonathan Blandford's avatar
Jonathan Blandford committed
244

245 246
  GtkTreePath *parent_path;
  gint *parent_path_indices;
247
  gint parent_path_depth;
248
};
249

250 251 252 253 254 255 256 257
/* Properties */
enum {
  PROP_0,
  /* Construct args */
  PROP_MODEL
};


258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283
struct _GtkTreeModelSortPrivate
{
  gpointer root;
  gint stamp;
  guint child_flags;
  GtkTreeModel *child_model;
  gint zero_ref_count;

  /* sort information */
  GList *sort_list;
  gint sort_column_id;
  GtkSortType order;

  /* default sort */
  GtkTreeIterCompareFunc default_sort_func;
  gpointer default_sort_data;
  GDestroyNotify default_sort_destroy;

  /* signal ids */
  gulong changed_id;
  gulong inserted_id;
  gulong has_child_toggled_id;
  gulong deleted_id;
  gulong reordered_id;
};

284 285 286 287 288 289 290
/* Set this to 0 to disable caching of child iterators.  This
 * allows for more stringent testing.  It is recommended to set this
 * to one when refactoring this code and running the unit tests to
 * catch more errors.
 */
#if 1
#  define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) \
291
	(((GtkTreeModelSort *)tree_model_sort)->priv->child_flags&GTK_TREE_MODEL_ITERS_PERSIST)
292 293 294 295
#else
#  define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) (FALSE)
#endif

296 297
#define SORT_ELT(sort_elt) ((SortElt *)sort_elt)
#define SORT_LEVEL(sort_level) ((SortLevel *)sort_level)
298
#define GET_ELT(siter) ((SortElt *) (siter ? g_sequence_get (siter) : NULL))
299

300

Matthias Clasen's avatar
Matthias Clasen committed
301
#define GET_CHILD_ITER(tree_model_sort,ch_iter,so_iter) gtk_tree_model_sort_convert_iter_to_child_iter((GtkTreeModelSort*)(tree_model_sort), (ch_iter), (so_iter));
302

303 304
#define NO_SORT_FUNC ((GtkTreeIterCompareFunc) 0x1)

305
#define VALID_ITER(iter, tree_model_sort) ((iter) != NULL && (iter)->user_data != NULL && (iter)->user_data2 != NULL && (tree_model_sort)->priv->stamp == (iter)->stamp)
Kristian Rietveld's avatar
Kristian Rietveld committed
306

307
/* general (object/interface init, etc) */
308 309
static void gtk_tree_model_sort_tree_model_init       (GtkTreeModelIface     *iface);
static void gtk_tree_model_sort_tree_sortable_init    (GtkTreeSortableIface  *iface);
310
static void gtk_tree_model_sort_drag_source_init      (GtkTreeDragSourceIface*iface);
311
static void gtk_tree_model_sort_finalize              (GObject               *object);
312 313 314 315 316 317 318 319
static void gtk_tree_model_sort_set_property          (GObject               *object,
						       guint                  prop_id,
						       const GValue          *value,
						       GParamSpec            *pspec);
static void gtk_tree_model_sort_get_property          (GObject               *object,
						       guint                  prop_id,
						       GValue                *value,
						       GParamSpec            *pspec);
320

321
/* our signal handlers */
322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341
static void gtk_tree_model_sort_row_changed           (GtkTreeModel          *model,
						       GtkTreePath           *start_path,
						       GtkTreeIter           *start_iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_inserted          (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       GtkTreeIter           *iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       GtkTreeIter           *iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_deleted           (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       gpointer               data);
static void gtk_tree_model_sort_rows_reordered        (GtkTreeModel          *s_model,
						       GtkTreePath           *s_path,
						       GtkTreeIter           *s_iter,
						       gint                  *new_order,
						       gpointer               data);
342 343

/* TreeModel interface */
344
static GtkTreeModelFlags gtk_tree_model_sort_get_flags     (GtkTreeModel          *tree_model);
345 346 347 348 349 350 351 352 353 354 355 356 357 358
static gint         gtk_tree_model_sort_get_n_columns      (GtkTreeModel          *tree_model);
static GType        gtk_tree_model_sort_get_column_type    (GtkTreeModel          *tree_model,
                                                            gint                   index);
static gboolean     gtk_tree_model_sort_get_iter           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreePath           *path);
static GtkTreePath *gtk_tree_model_sort_get_path           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static void         gtk_tree_model_sort_get_value          (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            gint                   column,
                                                            GValue                *value);
static gboolean     gtk_tree_model_sort_iter_next          (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
359 360
static gboolean     gtk_tree_model_sort_iter_previous      (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376
static gboolean     gtk_tree_model_sort_iter_children      (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *parent);
static gboolean     gtk_tree_model_sort_iter_has_child     (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gint         gtk_tree_model_sort_iter_n_children    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gboolean     gtk_tree_model_sort_iter_nth_child     (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *parent,
                                                            gint                   n);
static gboolean     gtk_tree_model_sort_iter_parent        (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *child);
static void         gtk_tree_model_sort_ref_node           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
377 378 379
static void         gtk_tree_model_sort_real_unref_node    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
							    gboolean               propagate_unref);
380 381 382
static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);

383 384 385 386 387 388 389 390 391
/* TreeDragSource interface */
static gboolean     gtk_tree_model_sort_row_draggable         (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path);
static gboolean     gtk_tree_model_sort_drag_data_get         (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path,
							       GtkSelectionData       *selection_data);
static gboolean     gtk_tree_model_sort_drag_data_delete      (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path);

392
/* TreeSortable interface */
393 394 395 396 397 398 399 400 401 402
static gboolean     gtk_tree_model_sort_get_sort_column_id    (GtkTreeSortable        *sortable,
							       gint                   *sort_column_id,
							       GtkSortType            *order);
static void         gtk_tree_model_sort_set_sort_column_id    (GtkTreeSortable        *sortable,
							       gint                    sort_column_id,
							       GtkSortType        order);
static void         gtk_tree_model_sort_set_sort_func         (GtkTreeSortable        *sortable,
							       gint                    sort_column_id,
							       GtkTreeIterCompareFunc  func,
							       gpointer                data,
403
							       GDestroyNotify          destroy);
404 405 406
static void         gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
							       GtkTreeIterCompareFunc  func,
							       gpointer                data,
407
							       GDestroyNotify          destroy);
408
static gboolean     gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable     *sortable);
409

410
/* Private functions (sort funcs, level handling and other utils) */
411 412
static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *parent_level,
413
                                                           SortElt          *parent_elt);
414
static void         gtk_tree_model_sort_free_level        (GtkTreeModelSort *tree_model_sort,
415 416
							   SortLevel        *sort_level,
                                                           gboolean          unref);
417 418 419 420 421 422
static void         gtk_tree_model_sort_increment_stamp   (GtkTreeModelSort *tree_model_sort);
static void         gtk_tree_model_sort_sort_level        (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *level,
							   gboolean          recurse,
							   gboolean          emit_reordered);
static void         gtk_tree_model_sort_sort              (GtkTreeModelSort *tree_model_sort);
423
static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
424
							   SortLevel        *level,
425 426
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
427 428 429 430
static GtkTreePath *gtk_tree_model_sort_elt_get_path      (SortLevel        *level,
							   SortElt          *elt);
static void         gtk_tree_model_sort_set_model         (GtkTreeModelSort *tree_model_sort,
							   GtkTreeModel     *child_model);
431 432 433
static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
									 GtkTreePath      *child_path,
									 gboolean          build_levels);
434

435 436 437 438 439 440 441 442 443
static gint         gtk_tree_model_sort_compare_func        (gconstpointer     a,
                                                             gconstpointer     b,
                                                             gpointer          user_data);
static gint         gtk_tree_model_sort_offset_compare_func (gconstpointer     a,
                                                             gconstpointer     b,
                                                             gpointer          user_data);
static void         gtk_tree_model_sort_clear_cache_helper  (GtkTreeModelSort *tree_model_sort,
                                                             SortLevel        *level);

444

Matthias Clasen's avatar
Matthias Clasen committed
445
G_DEFINE_TYPE_WITH_CODE (GtkTreeModelSort, gtk_tree_model_sort, G_TYPE_OBJECT,
446
                         G_ADD_PRIVATE (GtkTreeModelSort)
Matthias Clasen's avatar
Matthias Clasen committed
447 448 449 450 451
			 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_MODEL,
						gtk_tree_model_sort_tree_model_init)
			 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_SORTABLE,
						gtk_tree_model_sort_tree_sortable_init)
			 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_DRAG_SOURCE,
Matthias Clasen's avatar
Matthias Clasen committed
452
						gtk_tree_model_sort_drag_source_init))
453 454

static void
455 456
gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
{
457 458
  GtkTreeModelSortPrivate *priv;

459 460
  tree_model_sort->priv = priv =
    gtk_tree_model_sort_get_instance_private (tree_model_sort);
461 462 463 464 465
  priv->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
  priv->stamp = 0;
  priv->zero_ref_count = 0;
  priv->root = NULL;
  priv->sort_list = NULL;
466 467 468 469
}

static void
gtk_tree_model_sort_class_init (GtkTreeModelSortClass *class)
470 471 472
{
  GObjectClass *object_class;

473
  object_class = (GObjectClass *) class;
474

475 476 477
  object_class->set_property = gtk_tree_model_sort_set_property;
  object_class->get_property = gtk_tree_model_sort_get_property;

478
  object_class->finalize = gtk_tree_model_sort_finalize;
479 480 481 482 483

  /* Properties */
  g_object_class_install_property (object_class,
                                   PROP_MODEL,
                                   g_param_spec_object ("model",
484 485
							P_("TreeModelSort Model"),
							P_("The model for the TreeModelSort to sort"),
486
							GTK_TYPE_TREE_MODEL,
487
							GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
488 489 490 491 492
}

static void
gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
{
493
  iface->get_flags = gtk_tree_model_sort_get_flags;
494 495 496 497 498 499
  iface->get_n_columns = gtk_tree_model_sort_get_n_columns;
  iface->get_column_type = gtk_tree_model_sort_get_column_type;
  iface->get_iter = gtk_tree_model_sort_get_iter;
  iface->get_path = gtk_tree_model_sort_get_path;
  iface->get_value = gtk_tree_model_sort_get_value;
  iface->iter_next = gtk_tree_model_sort_iter_next;
500
  iface->iter_previous = gtk_tree_model_sort_iter_previous;
501 502 503 504 505
  iface->iter_children = gtk_tree_model_sort_iter_children;
  iface->iter_has_child = gtk_tree_model_sort_iter_has_child;
  iface->iter_n_children = gtk_tree_model_sort_iter_n_children;
  iface->iter_nth_child = gtk_tree_model_sort_iter_nth_child;
  iface->iter_parent = gtk_tree_model_sort_iter_parent;
506 507
  iface->ref_node = gtk_tree_model_sort_ref_node;
  iface->unref_node = gtk_tree_model_sort_unref_node;
508 509
}

510 511 512 513 514
static void
gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface *iface)
{
  iface->get_sort_column_id = gtk_tree_model_sort_get_sort_column_id;
  iface->set_sort_column_id = gtk_tree_model_sort_set_sort_column_id;
515
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
516 517
  iface->set_default_sort_func = gtk_tree_model_sort_set_default_sort_func;
  iface->has_default_sort_func = gtk_tree_model_sort_has_default_sort_func;
518 519
}

520 521 522 523 524 525 526 527
static void
gtk_tree_model_sort_drag_source_init (GtkTreeDragSourceIface *iface)
{
  iface->row_draggable = gtk_tree_model_sort_row_draggable;
  iface->drag_data_delete = gtk_tree_model_sort_drag_data_delete;
  iface->drag_data_get = gtk_tree_model_sort_drag_data_get;
}

528 529 530 531
/**
 * gtk_tree_model_sort_new_with_model:
 * @child_model: A #GtkTreeModel
 *
Matthias Clasen's avatar
Matthias Clasen committed
532
 * Creates a new #GtkTreeModel, with @child_model as the child model.
533
 *
534
 * Returns: (transfer full): A new #GtkTreeModel.
535
 */
536
GtkTreeModel *
537
gtk_tree_model_sort_new_with_model (GtkTreeModel *child_model)
538 539 540
{
  GtkTreeModel *retval;

541 542
  g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);

Manish Singh's avatar
Manish Singh committed
543
  retval = g_object_new (gtk_tree_model_sort_get_type (), NULL);
544

545
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
546 547 548 549

  return retval;
}

550 551 552
/* GObject callbacks */
static void
gtk_tree_model_sort_finalize (GObject *object)
553
{
554
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
555
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
556

557 558
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

559
  if (priv->root)
560
    gtk_tree_model_sort_free_level (tree_model_sort, priv->root, TRUE);
561

562
  if (priv->sort_list)
563
    {
564 565
      _gtk_tree_data_list_header_free (priv->sort_list);
      priv->sort_list = NULL;
566
    }
567

568
  if (priv->default_sort_destroy)
569
    {
570 571 572
      priv->default_sort_destroy (priv->default_sort_data);
      priv->default_sort_destroy = NULL;
      priv->default_sort_data = NULL;
573 574 575
    }


576
  /* must chain up */
Matthias Clasen's avatar
Matthias Clasen committed
577
  G_OBJECT_CLASS (gtk_tree_model_sort_parent_class)->finalize (object);
578 579
}

580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609
static void
gtk_tree_model_sort_set_property (GObject      *object,
				  guint         prop_id,
				  const GValue *value,
				  GParamSpec   *pspec)
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);

  switch (prop_id)
    {
    case PROP_MODEL:
      gtk_tree_model_sort_set_model (tree_model_sort, g_value_get_object (value));
      break;
    default:
      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
      break;
    }
}

static void
gtk_tree_model_sort_get_property (GObject    *object,
				  guint       prop_id,
				  GValue     *value,
				  GParamSpec *pspec)
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);

  switch (prop_id)
    {
    case PROP_MODEL:
610
      g_value_set_object (value, gtk_tree_model_sort_get_model (tree_model_sort));
611 612 613 614 615 616 617
      break;
    default:
      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
      break;
    }
}

618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733
/* helpers */
static SortElt *
sort_elt_new (void)
{
  return g_slice_new (SortElt);
}

static void
sort_elt_free (gpointer elt)
{
  g_slice_free (SortElt, elt);
}

static void
increase_offset_iter (gpointer data,
                      gpointer user_data)
{
  SortElt *elt = data;
  gint offset = GPOINTER_TO_INT (user_data);

  if (elt->offset >= offset)
    elt->offset++;
}

static void
decrease_offset_iter (gpointer data,
                      gpointer user_data)
{
  SortElt *elt = data;
  gint offset = GPOINTER_TO_INT (user_data);

  if (elt->offset > offset)
    elt->offset--;
}

static void
fill_sort_data (SortData         *data,
                GtkTreeModelSort *tree_model_sort,
                SortLevel        *level)
{
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;

  data->tree_model_sort = tree_model_sort;

  if (priv->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
    {
      GtkTreeDataSortHeader *header;
      
      header = _gtk_tree_data_list_get_header (priv->sort_list,
					       priv->sort_column_id);
      
      g_return_if_fail (header != NULL);
      g_return_if_fail (header->func != NULL);
      
      data->sort_func = header->func;
      data->sort_data = header->data;
    }
  else
    {
      /* absolutely SHOULD NOT happen: */
      g_return_if_fail (priv->default_sort_func != NULL);

      data->sort_func = priv->default_sort_func;
      data->sort_data = priv->default_sort_data;
    }

  if (level->parent_elt)
    {
      data->parent_path = gtk_tree_model_sort_elt_get_path (level->parent_level,
                                                            level->parent_elt);
      gtk_tree_path_append_index (data->parent_path, 0);
    }
  else
    {
      data->parent_path = gtk_tree_path_new_first ();
    }
  data->parent_path_depth = gtk_tree_path_get_depth (data->parent_path);
  data->parent_path_indices = gtk_tree_path_get_indices (data->parent_path);
}

static void
free_sort_data (SortData *data)
{
  gtk_tree_path_free (data->parent_path);
}

static SortElt *
lookup_elt_with_offset (GtkTreeModelSort *tree_model_sort,
                        SortLevel        *level,
                        gint              offset,
                        GSequenceIter   **ret_siter)
{
  GSequenceIter *siter, *end_siter;

  /* FIXME: We have to do a search like this, because the sequence is not
   * (always) sorted on offset order.  Perhaps we should introduce a
   * second sequence which is sorted on offset order.
   */
  end_siter = g_sequence_get_end_iter (level->seq);
  for (siter = g_sequence_get_begin_iter (level->seq);
       siter != end_siter;
       siter = g_sequence_iter_next (siter))
    {
      SortElt *elt = g_sequence_get (siter);

      if (elt->offset == offset)
        break;
    }

  if (ret_siter)
    *ret_siter = siter;

  return GET_ELT (siter);
}


734
static void
735
gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
736 737
				 GtkTreePath  *start_s_path,
				 GtkTreeIter  *start_s_iter,
738
				 gpointer      data)
739 740
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
741
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
742
  GtkTreePath *path = NULL;
743
  GtkTreeIter iter;
744
  GtkTreeIter tmpiter;
745

746 747
  SortElt *elt;
  SortLevel *level;
748
  SortData sort_data;
749

750 751
  gboolean free_s_path = FALSE;

752
  gint index = 0, old_index;
753 754

  g_return_if_fail (start_s_path != NULL || start_s_iter != NULL);
755

756
  if (!start_s_path)
757 758
    {
      free_s_path = TRUE;
759
      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
760
    }
761

762 763 764
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      start_s_path,
							      FALSE);
765
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
766 767
    {
      if (free_s_path)
768
	gtk_tree_path_free (start_s_path);
Jonathan Blandford's avatar
Jonathan Blandford committed
769 770
      return;
    }
Jonathan Blandford's avatar
Jonathan Blandford committed
771

772
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
773
  gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (data), &iter);
774

775 776
  level = iter.user_data;
  elt = iter.user_data2;
777

778
  if (g_sequence_get_length (level->seq) < 2 ||
779 780
      (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
       priv->default_sort_func == NO_SORT_FUNC))
781 782
    {
      if (free_s_path)
783
	gtk_tree_path_free (start_s_path);
784

785
      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
786
      gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);
787

788
      gtk_tree_path_free (path);
789

790 791
      return;
    }
792

793
  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
794
    tmpiter = elt->iter;
795
  else
796 797
    gtk_tree_model_get_iter (priv->child_model,
                             &tmpiter, start_s_path);
798

799 800 801 802 803 804 805
  old_index = g_sequence_iter_get_position (elt->siter);

  fill_sort_data (&sort_data, tree_model_sort, level);
  g_sequence_sort_changed (elt->siter,
                           gtk_tree_model_sort_compare_func,
                           &sort_data);
  free_sort_data (&sort_data);
806

807
  index = g_sequence_iter_get_position (elt->siter);
808

809
  /* Prepare the path for signal emission */
810 811
  gtk_tree_path_up (path);
  gtk_tree_path_append_index (path, index);
812

813
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
814

815 816 817 818 819 820 821 822
  /* if the item moved, then emit rows_reordered */
  if (old_index != index)
    {
      gint *new_order;
      gint j;

      GtkTreePath *tmppath;

823
      new_order = g_new (gint, g_sequence_get_length (level->seq));
824

825
      for (j = 0; j < g_sequence_get_length (level->seq); j++)
826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847
        {
	  if (index > old_index)
	    {
	      if (j == index)
		new_order[j] = old_index;
	      else if (j >= old_index && j < index)
		new_order[j] = j + 1;
	      else
		new_order[j] = j;
	    }
	  else if (index < old_index)
	    {
	      if (j == index)
		new_order[j] = old_index;
	      else if (j > index && j <= old_index)
		new_order[j] = j - 1;
	      else
		new_order[j] = j;
	    }
	  /* else? shouldn't really happen */
	}

848
      if (level->parent_elt)
849
        {
850
	  iter.stamp = priv->stamp;
851
	  iter.user_data = level->parent_level;
852
	  iter.user_data2 = level->parent_elt;
853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873

	  tmppath = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort), &iter);

	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
	                                 tmppath, &iter, new_order);
	}
      else
        {
	  /* toplevel */
	  tmppath = gtk_tree_path_new ();

          gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), tmppath,
	                                 NULL, new_order);
	}

      gtk_tree_path_free (tmppath);
      g_free (new_order);
    }

  /* emit row_changed signal (at new location) */
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
874
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
875
  gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);
876

877 878
  gtk_tree_path_free (path);
  if (free_s_path)
879
    gtk_tree_path_free (start_s_path);
880 881
}

882 883 884 885 886
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
887
{
888
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
889
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
890
  GtkTreePath *path;
891
  GtkTreeIter iter;
892 893 894 895 896 897 898 899 900 901
  GtkTreeIter real_s_iter;

  gint i = 0;

  gboolean free_s_path = FALSE;

  SortElt *elt;
  SortLevel *level;
  SortLevel *parent_level = NULL;

902
  parent_level = level = SORT_LEVEL (priv->root);
903

904
  g_return_if_fail (s_path != NULL || s_iter != NULL);
905

906
  if (!s_path)
907
    {
908 909
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
910
    }
911

912 913
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
914
  else
915
    real_s_iter = *s_iter;
916

917
  if (!priv->root)
918
    {
919
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
920

921 922
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
923

924
      goto done_and_submit;
925
    }
926

927 928 929 930 931 932 933 934
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
      if (!level)
	{
	  /* level not yet build, we won't cover this signal */
	  goto done;
	}
935

936
      if (g_sequence_get_length (level->seq) < gtk_tree_path_get_indices (s_path)[i])
937
	{
938
	  g_warning ("%s: A node was inserted with a parent that's not in the tree.\n"
939
		     "This possibly means that a GtkTreeModel inserted a child node\n"
940 941
		     "before the parent was inserted.",
		     G_STRLOC);
942 943
	  goto done;
	}
944

945 946 947
      elt = lookup_elt_with_offset (tree_model_sort, level,
                                    gtk_tree_path_get_indices (s_path)[i],
                                    NULL);
948 949

      g_return_if_fail (elt != NULL);
950 951 952 953 954 955 956 957 958 959 960

      if (!elt->children)
	{
	  /* not covering this signal */
	  goto done;
	}

      level = elt->children;
      parent_level = level;
      i++;
    }
961

962
  if (!parent_level)
963
    goto done;
964

965
  if (level->ref_count == 0 && level != priv->root)
966
    {
967
      gtk_tree_model_sort_free_level (tree_model_sort, level, TRUE);
968 969 970
      goto done;
    }

971 972 973 974 975
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
976

977
 done_and_submit:
978 979 980
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
981

982
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
983
    return;
984

985
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
986

987
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
988
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
989
  gtk_tree_path_free (path);
990

991
 done:
992 993
  if (free_s_path)
    gtk_tree_path_free (s_path);
994

995
  return;
996 997 998
}

static void
999 1000 1001 1002
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
1003 1004
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
1005 1006
  GtkTreePath *path;
  GtkTreeIter iter;
1007

1008
  g_return_if_fail (s_path != NULL && s_iter != NULL);
1009

1010 1011
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
Jonathan Blandford's avatar
Jonathan Blandford committed
1012
    return;
1013

1014
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
1015
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
1016

1017
  gtk_tree_path_free (path);
1018 1019 1020
}

static void
1021 1022 1023
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
1024 1025
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
1026
  GtkTreePath *path = NULL;
1027 1028 1029 1030
  SortElt *elt;
  SortLevel *level;
  GtkTreeIter iter;
  gint offset;
1031

1032
  g_return_if_fail (s_path != NULL);
1033

1034 1035
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
1036 1037
    return;

1038
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
1039

1040 1041 1042 1043
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

1044 1045
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);

1046
  while (elt->ref_count > 0)
1047
    gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
1048

1049 1050 1051 1052 1053 1054 1055 1056
  /* If this node has children, we free the level (recursively) here
   * and specify that unref may not be used, because parent and its
   * children have been removed by now.
   */
  if (elt->children)
    gtk_tree_model_sort_free_level (tree_model_sort,
                                    elt->children, FALSE);

1057
  if (level->ref_count == 0 && g_sequence_get_length (level->seq) == 1)
1058
    {
1059
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
1060
      gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
1061
      gtk_tree_path_free (path);
1062

1063
      if (level == tree_model_sort->priv->root)
1064
	{
1065 1066 1067
	  gtk_tree_model_sort_free_level (tree_model_sort,
					  tree_model_sort->priv->root,
                                          TRUE);
1068
	  tree_model_sort->priv->root = NULL;
1069
	}
1070 1071
      return;
    }
1072

1073 1074
  g_sequence_remove (elt->siter);
  elt = NULL;
1075

1076 1077 1078 1079 1080
  /* The sequence is not ordered on offset, so we traverse the entire
   * sequence.
   */
  g_sequence_foreach (level->seq, decrease_offset_iter,
                      GINT_TO_POINTER (offset));
1081

1082 1083 1084
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
  gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);

1085
  gtk_tree_path_free (path);
1086 1087
}

1088
static void
1089 1090 1091 1092 1093
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
1094
{
1095
  SortLevel *level;
1096
  GtkTreeIter iter;
1097
  GtkTreePath *path;
1098
  gint *tmp_array;
1099 1100
  int i, length;
  GSequenceIter *siter, *end_siter;
1101
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
1102
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1103

1104
  g_return_if_fail (new_order != NULL);
1105

Matthias Clasen's avatar
Matthias Clasen committed
1106
  if (s_path == NULL || gtk_tree_path_get_depth (s_path) == 0)
1107
    {
1108
      if (priv->root == NULL)
Jonathan Blandford's avatar
Jonathan Blandford committed
1109
	return;
1110
      path = gtk_tree_path_new ();
1111
      level = SORT_LEVEL (priv->root);
1112 1113
    }
  else
1114
    {
1115 1116
      SortElt *elt;

Jonathan Blandford's avatar
Jonathan Blandford committed
1117 1118 1119 1120
      path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
      if (path == NULL)
	return;
      gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
1121

1122
      elt = SORT_ELT (iter.user_data2);
1123 1124

      if (!elt->children)
1125 1126 1127 1128
	{
	  gtk_tree_path_free (path);
	  return;
	}
1129

1130 1131 1132
      level = elt->children;
    }

1133 1134
  length = g_sequence_get_length (level->seq);
  if (length < 2)
1135
    {
1136 1137 1138
      gtk_tree_path_free (path);
      return;
    }
1139

1140 1141 1142 1143 1144 1145 1146 1147 1148 1149
  tmp_array = g_new (int, length);

  /* FIXME: I need to think about whether this can be done in a more
   * efficient way?
   */
  i = 0;
  end_siter = g_sequence_get_end_iter (level->seq);
  for (siter = g_sequence_get_begin_iter (level->seq);
       siter != end_siter;
       siter = g_sequence_iter_next (siter))
1150
    {
1151 1152 1153 1154
      gint j;
      SortElt *elt = g_sequence_get (siter);

      for (j = 0; j < length; j++)
1155
	{
1156
	  if (elt->offset == new_order[j])
1157 1158
	    tmp_array[i] = j;
	}
1159 1160

      i++;
1161 1162
    }

1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176
  /* This loop cannot be merged with the above loop nest, because that
   * would introduce duplicate offsets.
   */
  i = 0;
  end_siter = g_sequence_get_end_iter (level->seq);
  for (siter = g_sequence_get_begin_iter (level->seq);
       siter != end_siter;
       siter = g_sequence_iter_next (siter))
    {
      SortElt *elt = g_sequence_get (siter);

      elt->offset = tmp_array[i];
      i++;
    }
1177
  g_free (tmp_array);
1178

1179 1180
  if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
      priv->default_sort_func == NO_SORT_FUNC)
1181
    {
1182 1183
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
1184
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
1185

1186
      if (gtk_tree_path_get_depth (path))
1187
	{
1188 1189 1190 1191 1192
	  gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
				   &iter,
				   path);
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, &iter, new_order);
1193
	}
1194
      else
1195 1196 1197 1198
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
1199 1200
    }

1201
  gtk_tree_path_free (path);
1202 1203 1204
}

/* Fulfill our model requirements */
1205
static GtkTreeModelFlags
1206 1207
gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
{
Matthias Clasen's avatar
Matthias Clasen committed
1208
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1209 1210
  GtkTreeModelFlags flags;

1211
  g_return_val_if_fail (tree_model_sort->priv->child_model != NULL, 0);
1212

1213
  flags = gtk_tree_model_get_flags (tree_model_sort->priv->child_model);
1214 1215 1216

  if ((flags & GTK_TREE_MODEL_LIST_ONLY) == GTK_TREE_MODEL_LIST_ONLY)
    return GTK_TREE_MODEL_LIST_ONLY;
1217 1218

  return 0;
1219 1220
}

1221 1222 1223
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
1224 1225
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

1226
  if (tree_model_sort->priv->child_model == 0)
1227
    return 0;
1228

1229
  return gtk_tree_model_get_n_columns (tree_model_sort->priv->child_model);
1230 1231 1232 1233
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
1234
                                     gint          index)
1235
{
Matthias Clasen's avatar
Matthias Clasen committed
1236
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1237

1238
  g_return_val_if_fail (tree_model_sort->priv->child_model != NULL, G_TYPE_INVALID);
Matthias Clasen's avatar
Matthias Clasen committed
1239

1240
  return gtk_tree_model_get_column_type (tree_model_sort->priv->child_model, index);
1241 1242 1243
}

static gboolean
1244 1245 1246
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
1247
{
Matthias Clasen's avatar
Matthias Clasen committed
1248
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1249
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1250
  gint *indices;
1251
  SortElt *elt;
1252 1253
  SortLevel *level;
  gint depth, i;
1254
  GSequenceIter *siter;
1255

1256
  g_return_val_if_fail (priv->child_model != NULL, FALSE);
1257

1258 1259
  indices = gtk_tree_path_get_indices (path);

1260
  if (priv->root == NULL)
1261
    gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1262
  level = SORT_LEVEL (priv->root);
1263 1264 1265

  depth = gtk_tree_path_get_depth (path);
  if (depth == 0)
1266 1267 1268 1269
    {
      iter->stamp = 0;
      return FALSE;
    }
1270

1271
  for (i = 0; i < depth - 1; i++)
1272
    {
1273
      if ((level == NULL) ||
1274
	  (indices[i] >= g_sequence_get_length (level->seq)))
1275 1276 1277 1278
        {
          iter->stamp = 0;
          return FALSE;
        }
1279

1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291
      siter = g_sequence_get_iter_at_pos (level->seq, indices[i]);
      if (g_sequence_iter_is_end (siter))
        {
          iter->stamp = 0;
          return FALSE;
        }

      elt = GET_ELT (siter);
      if (elt->children == NULL)
	gtk_tree_model_sort_build_level (tree_model_sort, level, elt);

      level = elt->children;
1292 1293
    }

1294
  if (!level || indices[i] >= g_sequence_get_length (level->seq))
1295 1296 1297 1298 1299
    {
      iter->stamp = 0;
      return FALSE;
    }

1300
  iter->stamp = priv->stamp;
1301
  iter->user_data = level;
1302 1303 1304 1305 1306 1307 1308 1309

  siter = g_sequence_get_iter_at_pos (level->seq, indices[depth - 1]);
  if (g_sequence_iter_is_end (siter))
    {
      iter->stamp = 0;
      return FALSE;
    }
  iter->user_data2 = GET_ELT (siter);
1310

1311
  return TRUE;
1312 1313 1314 1315
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
1316
			      GtkTreeIter  *iter)
1317
{
Matthias Clasen's avatar
Matthias Clasen committed
1318
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1319
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1320 1321
  GtkTreePath *retval;
  SortLevel *level;
1322
  SortElt *elt;
1323

1324 1325
  g_return_val_if_fail (priv->child_model != NULL, NULL);
  g_return_val_if_fail (priv->stamp == iter->stamp, NULL);
1326

1327
  retval = gtk_tree_path_new ();
1328 1329

  level = SORT_LEVEL (iter->user_data);
1330
  elt = SORT_ELT (iter->user_data2);
1331 1332

  while (level)
1333
    {
1334 1335 1336 1337
      gint index;

      index = g_sequence_iter_get_position (elt->siter);
      gtk_tree_path_prepend_index (retval, index);
1338

1339
      elt = level->parent_elt;
Kristian Rietveld's avatar