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 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public
16 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include "config.h"
20 #include <string.h>
21
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 * SECTION:gtktreemodelsort
33 * @Short_description: A GtkTreeModel which makes an underlying tree model sortable
34 * @Title: GtkTreeModelSort
35 * @See_also: #GtkTreeModel, #GtkListStore, #GtkTreeStore, #GtkTreeSortable, #GtkTreeModelFilter
36 *
37 * The #GtkTreeModelSort is a model which implements the #GtkTreeSortable
38 * interface. It does not hold any data itself, but rather is created with
39 * a child model and proxies its data. It has identical column types to
40 * this child model, and the changes in the child are propagated. The
41 * primary purpose of this model is to provide a way to sort a different
42 * model without modifying it. Note that the sort function used by
43 * #GtkTreeModelSort is not guaranteed to be stable.
44 *
45 * The use of this is best demonstrated through an example. In the
46 * following sample code we create two #GtkTreeView widgets each with a
47 * view of the same data. As the model is wrapped here by a
48 * #GtkTreeModelSort, the two #GtkTreeViews can each sort their
49 * view of the data without affecting the other. By contrast, if we
50 * simply put the same model in each widget, then sorting the first would
51 * sort the second.
52 *
53 * ## Using a #GtkTreeModelSort
54 *
55 * |[<!-- language="C" -->
56 * {
57 * GtkTreeView *tree_view1;
58 * GtkTreeView *tree_view2;
59 * GtkTreeModel *sort_model1;
60 * GtkTreeModel *sort_model2;
61 * GtkTreeModel *child_model;
62 *
63 * // get the child model
64 * child_model = get_my_model ();
65 *
66 * // Create the first tree
67 * sort_model1 = gtk_tree_model_sort_new_with_model (child_model);
68 * tree_view1 = gtk_tree_view_new_with_model (sort_model1);
69 *
70 * // Create the second tree
71 * sort_model2 = gtk_tree_model_sort_new_with_model (child_model);
72 * tree_view2 = gtk_tree_view_new_with_model (sort_model2);
73 *
74 * // Now we can sort the two models independently
75 * gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (sort_model1),
76 * COLUMN_1, GTK_SORT_ASCENDING);
77 * gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (sort_model2),
78 * COLUMN_1, GTK_SORT_DESCENDING);
79 * }
80 * ]|
81 *
82 * To demonstrate how to access the underlying child model from the sort
83 * model, the next example will be a callback for the #GtkTreeSelection
84 * #GtkTreeSelection::changed signal. In this callback, we get a string
85 * from COLUMN_1 of the model. We then modify the string, find the same
86 * selected row on the child model, and change the row there.
87 *
88 * ## Accessing the child model of in a selection changed callback
89 *
90 * |[<!-- language="C" -->
91 * void
92 * selection_changed (GtkTreeSelection *selection, gpointer data)
93 * {
94 * GtkTreeModel *sort_model = NULL;
95 * GtkTreeModel *child_model;
96 * GtkTreeIter sort_iter;
97 * GtkTreeIter child_iter;
98 * char *some_data = NULL;
99 * char *modified_data;
100 *
101 * // Get the current selected row and the model.
102 * if (! gtk_tree_selection_get_selected (selection,
103 * &sort_model,
104 * &sort_iter))
105 * return;
106 *
107 * // Look up the current value on the selected row and get
108 * // a new value to change it to.
109 * gtk_tree_model_get (GTK_TREE_MODEL (sort_model), &sort_iter,
110 * COLUMN_1, &some_data,
111 * -1);
112 *
113 * modified_data = change_the_data (some_data);
114 * g_free (some_data);
115 *
116 * // Get an iterator on the child model, instead of the sort model.
117 * gtk_tree_model_sort_convert_iter_to_child_iter (GTK_TREE_MODEL_SORT (sort_model),
118 * &child_iter,
119 * &sort_iter);
120 *
121 * // Get the child model and change the value of the row. In this
122 * // example, the child model is a GtkListStore. It could be any other
123 * // type of model, though.
124 * child_model = gtk_tree_model_sort_get_model (GTK_TREE_MODEL_SORT (sort_model));
125 * gtk_list_store_set (GTK_LIST_STORE (child_model), &child_iter,
126 * COLUMN_1, &modified_data,
127 * -1);
128 * g_free (modified_data);
129 * }
130 * ]|
131 */
132
133
134 /* Notes on this implementation of GtkTreeModelSort
135 * ================================================
136 *
137 * Warnings
138 * --------
139 *
140 * In this code there is a potential for confusion as to whether an iter,
141 * path or value refers to the GtkTreeModelSort model, or to the child model
142 * that has been set. As a convention, variables referencing the child model
143 * will have an s_ prefix before them (ie. s_iter, s_value, s_path);
144 * Conversion of iterators and paths between GtkTreeModelSort and the child
145 * model is done through the various gtk_tree_model_sort_convert_* functions.
146 *
147 * Iterator format
148 * ---------------
149 *
150 * The iterator format of iterators handed out by GtkTreeModelSort is as
151 * follows:
152 *
153 * iter->stamp = tree_model_sort->stamp
154 * iter->user_data = SortLevel
155 * iter->user_data2 = SortElt
156 *
157 * Internal data structure
158 * -----------------------
159 *
160 * Using SortLevel and SortElt, GtkTreeModelSort maintains a “cache” of
161 * the mapping from GtkTreeModelSort nodes to nodes in the child model.
162 * This is to avoid sorting a level each time an operation is requested
163 * on GtkTreeModelSort, such as get iter, get path, get value.
164 *
165 * A SortElt corresponds to a single node. A node and its siblings are
166 * stored in a SortLevel. The SortLevel keeps a reference to the parent
167 * SortElt and its SortLevel (if any). The SortElt can have a "children"
168 * pointer set, which points at a child level (a sub level).
169 *
170 * In a SortLevel, nodes are stored in a GSequence. The GSequence
171 * allows for fast additions and removals, and supports sorting
172 * the level of SortElt nodes.
173 *
174 * It is important to recognize the two different mappings that play
175 * a part in this code:
176 * I. The mapping from the client to this model. The order in which
177 * nodes are stored in the GSequence is the order in which the
178 * nodes are exposed to clients of the GtkTreeModelSort.
179 * II. The mapping from this model to its child model. Each SortElt
180 * contains an “offset” field which is the offset of the
181 * corresponding node in the child model.
182 *
183 * Reference counting
184 * ------------------
185 *
186 * GtkTreeModelSort forwards all reference and unreference operations
187 * 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 * In addition, if a SortLevel has a parent, a reference is taken on
192 * this parent. This happens in gtk_tree_model_sort_build_level() and
193 * the reference is released again in gtk_tree_model_sort_free_level().
194 * This ensures that when GtkTreeModelSort takes a reference on a node
195 * (for example during sorting), all parent nodes are referenced
196 * according to reference counting rule 1, see the GtkTreeModel
197 * documentation.
198 *
199 * When a level has a reference count of zero, which means that
200 * 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 * reaches a reference count of zero, the zero ref count value is
203 * incremented by one on all parents of this level. Similarly, as
204 * soon as the reference count of a level changes from zero, the
205 * zero ref count value is decremented by one on all parents.
206 *
207 * The zero ref count value is used to clear unused portions of
208 * the cache. If a SortElt has a zero ref count of one, then
209 * its child level is unused and can be removed from the cache.
210 * If the zero ref count value is higher than one, then the
211 * child level contains sublevels which are unused as well.
212 * gtk_tree_model_sort_clear_cache() uses this to not recurse
213 * into levels which have a zero ref count of zero.
214 */
215
216 typedef struct _SortElt SortElt;
217 typedef struct _SortLevel SortLevel;
218 typedef struct _SortData SortData;
219
220 struct _SortElt
221 {
222 GtkTreeIter iter;
223 SortLevel *children;
224 gint offset;
225 gint ref_count;
226 gint zero_ref_count;
227 gint old_index; /* used while sorting */
228 GSequenceIter *siter; /* iter into seq */
229 };
230
231 struct _SortLevel
232 {
233 GSequence *seq;
234 gint ref_count;
235 SortElt *parent_elt;
236 SortLevel *parent_level;
237 };
238
239 struct _SortData
240 {
241 GtkTreeModelSort *tree_model_sort;
242 GtkTreeIterCompareFunc sort_func;
243 gpointer sort_data;
244
245 GtkTreePath *parent_path;
246 gint *parent_path_indices;
247 gint parent_path_depth;
248 };
249
250 /* Properties */
251 enum {
252 PROP_0,
253 /* Construct args */
254 PROP_MODEL
255 };
256
257
258 struct _GtkTreeModelSortPrivate
259 {
260 gpointer root;
261 gint stamp;
262 guint child_flags;
263 GtkTreeModel *child_model;
264 gint zero_ref_count;
265
266 /* sort information */
267 GList *sort_list;
268 gint sort_column_id;
269 GtkSortType order;
270
271 /* default sort */
272 GtkTreeIterCompareFunc default_sort_func;
273 gpointer default_sort_data;
274 GDestroyNotify default_sort_destroy;
275
276 /* signal ids */
277 gulong changed_id;
278 gulong inserted_id;
279 gulong has_child_toggled_id;
280 gulong deleted_id;
281 gulong reordered_id;
282 };
283
284 /* Set this to 0 to disable caching of child iterators. This
285 * allows for more stringent testing. It is recommended to set this
286 * to one when refactoring this code and running the unit tests to
287 * catch more errors.
288 */
289 #if 1
290 # define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) \
291 (((GtkTreeModelSort *)tree_model_sort)->priv->child_flags>K_TREE_MODEL_ITERS_PERSIST)
292 #else
293 # define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) (FALSE)
294 #endif
295
296 #define SORT_ELT(sort_elt) ((SortElt *)sort_elt)
297 #define SORT_LEVEL(sort_level) ((SortLevel *)sort_level)
298 #define GET_ELT(siter) ((SortElt *) (siter ? g_sequence_get (siter) : NULL))
299
300
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 #define NO_SORT_FUNC ((GtkTreeIterCompareFunc) 0x1)
304
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)
306
307 /* general (object/interface init, etc) */
308 static void gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface);
309 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 static void gtk_tree_model_sort_set_property (GObject *object,
313 guint prop_id,
314 const GValue *value,
315 GParamSpec *pspec);
316 static void gtk_tree_model_sort_get_property (GObject *object,
317 guint prop_id,
318 GValue *value,
319 GParamSpec *pspec);
320
321 /* our signal handlers */
322 static void gtk_tree_model_sort_row_changed (GtkTreeModel *model,
323 GtkTreePath *start_path,
324 GtkTreeIter *start_iter,
325 gpointer data);
326 static void gtk_tree_model_sort_row_inserted (GtkTreeModel *model,
327 GtkTreePath *path,
328 GtkTreeIter *iter,
329 gpointer data);
330 static void gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *model,
331 GtkTreePath *path,
332 GtkTreeIter *iter,
333 gpointer data);
334 static void gtk_tree_model_sort_row_deleted (GtkTreeModel *model,
335 GtkTreePath *path,
336 gpointer data);
337 static void gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
338 GtkTreePath *s_path,
339 GtkTreeIter *s_iter,
340 gint *new_order,
341 gpointer data);
342
343 /* TreeModel interface */
344 static GtkTreeModelFlags gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model);
345 static gint gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model);
346 static GType gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
347 gint index);
348 static gboolean gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
349 GtkTreeIter *iter,
350 GtkTreePath *path);
351 static GtkTreePath *gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
352 GtkTreeIter *iter);
353 static void gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
354 GtkTreeIter *iter,
355 gint column,
356 GValue *value);
357 static gboolean gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
358 GtkTreeIter *iter);
359 static gboolean gtk_tree_model_sort_iter_previous (GtkTreeModel *tree_model,
360 GtkTreeIter *iter);
361 static gboolean gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
362 GtkTreeIter *iter,
363 GtkTreeIter *parent);
364 static gboolean gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
365 GtkTreeIter *iter);
366 static gint gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
367 GtkTreeIter *iter);
368 static gboolean gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
369 GtkTreeIter *iter,
370 GtkTreeIter *parent,
371 gint n);
372 static gboolean gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
373 GtkTreeIter *iter,
374 GtkTreeIter *child);
375 static void gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
376 GtkTreeIter *iter);
377 static void gtk_tree_model_sort_real_unref_node (GtkTreeModel *tree_model,
378 GtkTreeIter *iter,
379 gboolean propagate_unref);
380 static void gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
381 GtkTreeIter *iter);
382
383 /* TreeDragSource interface */
384 static gboolean gtk_tree_model_sort_row_draggable (GtkTreeDragSource *drag_source,
385 GtkTreePath *path);
386 static gboolean gtk_tree_model_sort_drag_data_get (GtkTreeDragSource *drag_source,
387 GtkTreePath *path,
388 GtkSelectionData *selection_data);
389 static gboolean gtk_tree_model_sort_drag_data_delete (GtkTreeDragSource *drag_source,
390 GtkTreePath *path);
391
392 /* TreeSortable interface */
393 static gboolean gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable *sortable,
394 gint *sort_column_id,
395 GtkSortType *order);
396 static void gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable *sortable,
397 gint sort_column_id,
398 GtkSortType order);
399 static void gtk_tree_model_sort_set_sort_func (GtkTreeSortable *sortable,
400 gint sort_column_id,
401 GtkTreeIterCompareFunc func,
402 gpointer data,
403 GDestroyNotify destroy);
404 static void gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable *sortable,
405 GtkTreeIterCompareFunc func,
406 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 static void gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
412 SortLevel *parent_level,
413 SortElt *parent_elt);
414 static void gtk_tree_model_sort_free_level (GtkTreeModelSort *tree_model_sort,
415 SortLevel *sort_level,
416 gboolean unref);
417 static void gtk_tree_model_sort_increment_stamp (GtkTreeModelSort *tree_model_sort);
418 static void gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
419 SortLevel *level,
420 gboolean recurse,
421 gboolean emit_reordered);
422 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 GtkTreePath *s_path,
426 GtkTreeIter *s_iter);
427 static GtkTreePath *gtk_tree_model_sort_elt_get_path (SortLevel *level,
428 SortElt *elt);
429 static void gtk_tree_model_sort_set_model (GtkTreeModelSort *tree_model_sort,
430 GtkTreeModel *child_model);
431 static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
432 GtkTreePath *child_path,
433 gboolean build_levels);
434
435 static gint gtk_tree_model_sort_compare_func (gconstpointer a,
436 gconstpointer b,
437 gpointer user_data);
438 static gint gtk_tree_model_sort_offset_compare_func (gconstpointer a,
439 gconstpointer b,
440 gpointer user_data);
441 static void gtk_tree_model_sort_clear_cache_helper (GtkTreeModelSort *tree_model_sort,
442 SortLevel *level);
443
444
G_DEFINE_TYPE_WITH_CODE(GtkTreeModelSort,gtk_tree_model_sort,G_TYPE_OBJECT,G_ADD_PRIVATE (GtkTreeModelSort)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,gtk_tree_model_sort_drag_source_init))445 G_DEFINE_TYPE_WITH_CODE (GtkTreeModelSort, gtk_tree_model_sort, G_TYPE_OBJECT,
446 G_ADD_PRIVATE (GtkTreeModelSort)
447 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_MODEL,
448 gtk_tree_model_sort_tree_model_init)
449 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_SORTABLE,
450 gtk_tree_model_sort_tree_sortable_init)
451 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_DRAG_SOURCE,
452 gtk_tree_model_sort_drag_source_init))
453
454 static void
455 gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
456 {
457 GtkTreeModelSortPrivate *priv;
458
459 tree_model_sort->priv = priv =
460 gtk_tree_model_sort_get_instance_private (tree_model_sort);
461 priv->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
462 priv->stamp = 0;
463 priv->zero_ref_count = 0;
464 priv->root = NULL;
465 priv->sort_list = NULL;
466 }
467
468 static void
gtk_tree_model_sort_class_init(GtkTreeModelSortClass * class)469 gtk_tree_model_sort_class_init (GtkTreeModelSortClass *class)
470 {
471 GObjectClass *object_class;
472
473 object_class = (GObjectClass *) class;
474
475 object_class->set_property = gtk_tree_model_sort_set_property;
476 object_class->get_property = gtk_tree_model_sort_get_property;
477
478 object_class->finalize = gtk_tree_model_sort_finalize;
479
480 /* Properties */
481 g_object_class_install_property (object_class,
482 PROP_MODEL,
483 g_param_spec_object ("model",
484 P_("TreeModelSort Model"),
485 P_("The model for the TreeModelSort to sort"),
486 GTK_TYPE_TREE_MODEL,
487 GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
488 }
489
490 static void
gtk_tree_model_sort_tree_model_init(GtkTreeModelIface * iface)491 gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
492 {
493 iface->get_flags = gtk_tree_model_sort_get_flags;
494 iface->get_n_columns = gtk_tree_model_sort_get_n_columns;
495 iface->get_column_type = gtk_tree_model_sort_get_column_type;
496 iface->get_iter = gtk_tree_model_sort_get_iter;
497 iface->get_path = gtk_tree_model_sort_get_path;
498 iface->get_value = gtk_tree_model_sort_get_value;
499 iface->iter_next = gtk_tree_model_sort_iter_next;
500 iface->iter_previous = gtk_tree_model_sort_iter_previous;
501 iface->iter_children = gtk_tree_model_sort_iter_children;
502 iface->iter_has_child = gtk_tree_model_sort_iter_has_child;
503 iface->iter_n_children = gtk_tree_model_sort_iter_n_children;
504 iface->iter_nth_child = gtk_tree_model_sort_iter_nth_child;
505 iface->iter_parent = gtk_tree_model_sort_iter_parent;
506 iface->ref_node = gtk_tree_model_sort_ref_node;
507 iface->unref_node = gtk_tree_model_sort_unref_node;
508 }
509
510 static void
gtk_tree_model_sort_tree_sortable_init(GtkTreeSortableIface * iface)511 gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface *iface)
512 {
513 iface->get_sort_column_id = gtk_tree_model_sort_get_sort_column_id;
514 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 iface->set_default_sort_func = gtk_tree_model_sort_set_default_sort_func;
517 iface->has_default_sort_func = gtk_tree_model_sort_has_default_sort_func;
518 }
519
520 static void
gtk_tree_model_sort_drag_source_init(GtkTreeDragSourceIface * iface)521 gtk_tree_model_sort_drag_source_init (GtkTreeDragSourceIface *iface)
522 {
523 iface->row_draggable = gtk_tree_model_sort_row_draggable;
524 iface->drag_data_delete = gtk_tree_model_sort_drag_data_delete;
525 iface->drag_data_get = gtk_tree_model_sort_drag_data_get;
526 }
527
528 /**
529 * gtk_tree_model_sort_new_with_model: (constructor)
530 * @child_model: A #GtkTreeModel
531 *
532 * Creates a new #GtkTreeModelSort, with @child_model as the child model.
533 *
534 * Returns: (transfer full) (type Gtk.TreeModelSort): A new #GtkTreeModelSort.
535 */
536 GtkTreeModel *
gtk_tree_model_sort_new_with_model(GtkTreeModel * child_model)537 gtk_tree_model_sort_new_with_model (GtkTreeModel *child_model)
538 {
539 GtkTreeModel *retval;
540
541 g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);
542
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 return retval;
548 }
549
550 /* GObject callbacks */
551 static void
gtk_tree_model_sort_finalize(GObject * object)552 gtk_tree_model_sort_finalize (GObject *object)
553 {
554 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
555 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
556
557 gtk_tree_model_sort_set_model (tree_model_sort, NULL);
558
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 _gtk_tree_data_list_header_free (priv->sort_list);
565 priv->sort_list = NULL;
566 }
567
568 if (priv->default_sort_destroy)
569 {
570 priv->default_sort_destroy (priv->default_sort_data);
571 priv->default_sort_destroy = NULL;
572 priv->default_sort_data = NULL;
573 }
574
575
576 /* must chain up */
577 G_OBJECT_CLASS (gtk_tree_model_sort_parent_class)->finalize (object);
578 }
579
580 static void
gtk_tree_model_sort_set_property(GObject * object,guint prop_id,const GValue * value,GParamSpec * pspec)581 gtk_tree_model_sort_set_property (GObject *object,
582 guint prop_id,
583 const GValue *value,
584 GParamSpec *pspec)
585 {
586 GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);
587
588 switch (prop_id)
589 {
590 case PROP_MODEL:
591 gtk_tree_model_sort_set_model (tree_model_sort, g_value_get_object (value));
592 break;
593 default:
594 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
595 break;
596 }
597 }
598
599 static void
gtk_tree_model_sort_get_property(GObject * object,guint prop_id,GValue * value,GParamSpec * pspec)600 gtk_tree_model_sort_get_property (GObject *object,
601 guint prop_id,
602 GValue *value,
603 GParamSpec *pspec)
604 {
605 GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);
606
607 switch (prop_id)
608 {
609 case PROP_MODEL:
610 g_value_set_object (value, gtk_tree_model_sort_get_model (tree_model_sort));
611 break;
612 default:
613 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
614 break;
615 }
616 }
617
618 /* helpers */
619 static SortElt *
sort_elt_new(void)620 sort_elt_new (void)
621 {
622 return g_slice_new (SortElt);
623 }
624
625 static void
sort_elt_free(gpointer elt)626 sort_elt_free (gpointer elt)
627 {
628 g_slice_free (SortElt, elt);
629 }
630
631 static void
increase_offset_iter(gpointer data,gpointer user_data)632 increase_offset_iter (gpointer data,
633 gpointer user_data)
634 {
635 SortElt *elt = data;
636 gint offset = GPOINTER_TO_INT (user_data);
637
638 if (elt->offset >= offset)
639 elt->offset++;
640 }
641
642 static void
decrease_offset_iter(gpointer data,gpointer user_data)643 decrease_offset_iter (gpointer data,
644 gpointer user_data)
645 {
646 SortElt *elt = data;
647 gint offset = GPOINTER_TO_INT (user_data);
648
649 if (elt->offset > offset)
650 elt->offset--;
651 }
652
653 static void
fill_sort_data(SortData * data,GtkTreeModelSort * tree_model_sort,SortLevel * level)654 fill_sort_data (SortData *data,
655 GtkTreeModelSort *tree_model_sort,
656 SortLevel *level)
657 {
658 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
659
660 data->tree_model_sort = tree_model_sort;
661
662 if (priv->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
663 {
664 GtkTreeDataSortHeader *header;
665
666 header = _gtk_tree_data_list_get_header (priv->sort_list,
667 priv->sort_column_id);
668
669 g_return_if_fail (header != NULL);
670 g_return_if_fail (header->func != NULL);
671
672 data->sort_func = header->func;
673 data->sort_data = header->data;
674 }
675 else
676 {
677 /* absolutely SHOULD NOT happen: */
678 g_return_if_fail (priv->default_sort_func != NULL);
679
680 data->sort_func = priv->default_sort_func;
681 data->sort_data = priv->default_sort_data;
682 }
683
684 if (level->parent_elt)
685 {
686 data->parent_path = gtk_tree_model_sort_elt_get_path (level->parent_level,
687 level->parent_elt);
688 gtk_tree_path_append_index (data->parent_path, 0);
689 }
690 else
691 {
692 data->parent_path = gtk_tree_path_new_first ();
693 }
694 data->parent_path_depth = gtk_tree_path_get_depth (data->parent_path);
695 data->parent_path_indices = gtk_tree_path_get_indices (data->parent_path);
696 }
697
698 static void
free_sort_data(SortData * data)699 free_sort_data (SortData *data)
700 {
701 gtk_tree_path_free (data->parent_path);
702 }
703
704 static SortElt *
lookup_elt_with_offset(GtkTreeModelSort * tree_model_sort,SortLevel * level,gint offset,GSequenceIter ** ret_siter)705 lookup_elt_with_offset (GtkTreeModelSort *tree_model_sort,
706 SortLevel *level,
707 gint offset,
708 GSequenceIter **ret_siter)
709 {
710 GSequenceIter *siter, *end_siter;
711
712 /* FIXME: We have to do a search like this, because the sequence is not
713 * (always) sorted on offset order. Perhaps we should introduce a
714 * second sequence which is sorted on offset order.
715 */
716 end_siter = g_sequence_get_end_iter (level->seq);
717 for (siter = g_sequence_get_begin_iter (level->seq);
718 siter != end_siter;
719 siter = g_sequence_iter_next (siter))
720 {
721 SortElt *elt = g_sequence_get (siter);
722
723 if (elt->offset == offset)
724 break;
725 }
726
727 if (ret_siter)
728 *ret_siter = siter;
729
730 return GET_ELT (siter);
731 }
732
733
734 static void
gtk_tree_model_sort_row_changed(GtkTreeModel * s_model,GtkTreePath * start_s_path,GtkTreeIter * start_s_iter,gpointer data)735 gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
736 GtkTreePath *start_s_path,
737 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 SortElt *elt;
747 SortLevel *level;
748 SortData sort_data;
749
750 gboolean free_s_path = FALSE;
751
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 path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
763 start_s_path,
764 FALSE);
765 if (!path)
766 {
767 if (free_s_path)
768 gtk_tree_path_free (start_s_path);
769 return;
770 }
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 level = iter.user_data;
776 elt = iter.user_data2;
777
778 if (g_sequence_get_length (level->seq) < 2 ||
779 (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
780 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 return;
791 }
792
793 if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
794 tmpiter = elt->iter;
795 else
796 gtk_tree_model_get_iter (priv->child_model,
797 &tmpiter, start_s_path);
798
799 old_index = g_sequence_iter_get_position (elt->siter);
800
801 fill_sort_data (&sort_data, tree_model_sort, level);
802 g_sequence_sort_changed (elt->siter,
803 gtk_tree_model_sort_compare_func,
804 &sort_data);
805 free_sort_data (&sort_data);
806
807 index = g_sequence_iter_get_position (elt->siter);
808
809 /* Prepare the path for signal emission */
810 gtk_tree_path_up (path);
811 gtk_tree_path_append_index (path, index);
812
813 gtk_tree_model_sort_increment_stamp (tree_model_sort);
814
815 /* if the item moved, then emit rows_reordered */
816 if (old_index != index)
817 {
818 gint *new_order;
819 gint j;
820
821 GtkTreePath *tmppath;
822
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 if (index > old_index)
828 {
829 if (j == index)
830 new_order[j] = old_index;
831 else if (j >= old_index && j < index)
832 new_order[j] = j + 1;
833 else
834 new_order[j] = j;
835 }
836 else if (index < old_index)
837 {
838 if (j == index)
839 new_order[j] = old_index;
840 else if (j > index && j <= old_index)
841 new_order[j] = j - 1;
842 else
843 new_order[j] = j;
844 }
845 /* else? shouldn't really happen */
846 }
847
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 tmppath = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort), &iter);
855
856 gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
857 tmppath, &iter, new_order);
858 }
859 else
860 {
861 /* toplevel */
862 tmppath = gtk_tree_path_new ();
863
864 gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), tmppath,
865 NULL, new_order);
866 }
867
868 gtk_tree_path_free (tmppath);
869 g_free (new_order);
870 }
871
872 /* emit row_changed signal (at new location) */
873 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 gtk_tree_path_free (path);
878 if (free_s_path)
879 gtk_tree_path_free (start_s_path);
880 }
881
882 static void
gtk_tree_model_sort_row_inserted(GtkTreeModel * s_model,GtkTreePath * s_path,GtkTreeIter * s_iter,gpointer data)883 gtk_tree_model_sort_row_inserted (GtkTreeModel *s_model,
884 GtkTreePath *s_path,
885 GtkTreeIter *s_iter,
886 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 GtkTreeIter real_s_iter;
893
894 gint i = 0;
895
896 gboolean free_s_path = FALSE;
897
898 SortElt *elt;
899 SortLevel *level;
900 SortLevel *parent_level = NULL;
901
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 s_path = gtk_tree_model_get_path (s_model, s_iter);
909 free_s_path = TRUE;
910 }
911
912 if (!s_iter)
913 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 /* the build level already put the inserted iter in the level,
922 so no need to handle this signal anymore */
923
924 goto done_and_submit;
925 }
926
927 /* find the parent level */
928 while (i < gtk_tree_path_get_depth (s_path) - 1)
929 {
930 if (!level)
931 {
932 /* level not yet build, we won't cover this signal */
933 goto done;
934 }
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 "before the parent was inserted.",
941 G_STRLOC);
942 goto done;
943 }
944
945 elt = lookup_elt_with_offset (tree_model_sort, level,
946 gtk_tree_path_get_indices (s_path)[i],
947 NULL);
948
949 g_return_if_fail (elt != NULL);
950
951 if (!elt->children)
952 {
953 /* not covering this signal */
954 goto done;
955 }
956
957 level = elt->children;
958 parent_level = level;
959 i++;
960 }
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 goto done;
969 }
970
971 if (!gtk_tree_model_sort_insert_value (tree_model_sort,
972 parent_level,
973 s_path,
974 &real_s_iter))
975 goto done;
976
977 done_and_submit:
978 path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
979 s_path,
980 FALSE);
981
982 if (!path)
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 if (free_s_path)
993 gtk_tree_path_free (s_path);
994
995 return;
996 }
997
998 static void
gtk_tree_model_sort_row_has_child_toggled(GtkTreeModel * s_model,GtkTreePath * s_path,GtkTreeIter * s_iter,gpointer data)999 gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
1000 GtkTreePath *s_path,
1001 GtkTreeIter *s_iter,
1002 gpointer data)
1003 {
1004 GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
1005 GtkTreePath *path;
1006 GtkTreeIter iter;
1007
1008 g_return_if_fail (s_path != NULL && s_iter != NULL);
1009
1010 path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
1011 if (path == NULL)
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
gtk_tree_model_sort_row_deleted(GtkTreeModel * s_model,GtkTreePath * s_path,gpointer data)1021 gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
1022 GtkTreePath *s_path,
1023 gpointer data)
1024 {
1025 GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
1026 GtkTreePath *path = NULL;
1027 SortElt *elt;
1028 SortLevel *level;
1029 GtkTreeIter iter;
1030 gint offset;
1031
1032 g_return_if_fail (s_path != NULL);
1033
1034 path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
1035 if (path == NULL)
1036 return;
1037
1038 gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
1039
1040 level = SORT_LEVEL (iter.user_data);
1041 elt = SORT_ELT (iter.user_data2);
1042 offset = elt->offset;
1043
1044 gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
1045
1046 while (elt->ref_count > 0)
1047 gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
1048
1049 /* If this node has children, we free the level (recursively) here
1050 * and specify that unref may not be used, because parent and its
1051 * children have been removed by now.
1052 */
1053 if (elt->children)
1054 gtk_tree_model_sort_free_level (tree_model_sort,
1055 elt->children, FALSE);
1056
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 gtk_tree_model_sort_free_level (tree_model_sort,
1066 tree_model_sort->priv->root,
1067 TRUE);
1068 tree_model_sort->priv->root = NULL;
1069 }
1070 return;
1071 }
1072
1073 g_sequence_remove (elt->siter);
1074 elt = NULL;
1075
1076 /* The sequence is not ordered on offset, so we traverse the entire
1077 * sequence.
1078 */
1079 g_sequence_foreach (level->seq, decrease_offset_iter,
1080 GINT_TO_POINTER (offset));
1081
1082 gtk_tree_model_sort_increment_stamp (tree_model_sort);
1083 gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
1084
1085 gtk_tree_path_free (path);
1086 }
1087
1088 static void
gtk_tree_model_sort_rows_reordered(GtkTreeModel * s_model,GtkTreePath * s_path,GtkTreeIter * s_iter,gint * new_order,gpointer data)1089 gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
1090 GtkTreePath *s_path,
1091 GtkTreeIter *s_iter,
1092 gint *new_order,
1093 gpointer data)
1094 {
1095 SortLevel *level;
1096 GtkTreeIter iter;
1097 GtkTreePath *path;
1098 gint *tmp_array;
1099 int i, length;
1100 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
1106 if (s_path == NULL || gtk_tree_path_get_depth (s_path) == 0)
1107 {
1108 if (priv->root == NULL)
1109 return;
1110 path = gtk_tree_path_new ();
1111 level = SORT_LEVEL (priv->root);
1112 }
1113 else
1114 {
1115 SortElt *elt;
1116
1117 path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
1118 if (path == NULL)
1119 return;
1120 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 gtk_tree_path_free (path);
1127 return;
1128 }
1129
1130 level = elt->children;
1131 }
1132
1133 length = g_sequence_get_length (level->seq);
1134 if (length < 2)
1135 {
1136 gtk_tree_path_free (path);
1137 return;
1138 }
1139
1140 tmp_array = g_new (int, length);
1141
1142 /* FIXME: I need to think about whether this can be done in a more
1143 * efficient way?
1144 */
1145 i = 0;
1146 end_siter = g_sequence_get_end_iter (level->seq);
1147 for (siter = g_sequence_get_begin_iter (level->seq);
1148 siter != end_siter;
1149 siter = g_sequence_iter_next (siter))
1150 {
1151 gint j;
1152 SortElt *elt = g_sequence_get (siter);
1153
1154 for (j = 0; j < length; j++)
1155 {
1156 if (elt->offset == new_order[j])
1157 tmp_array[i] = j;
1158 }
1159
1160 i++;
1161 }
1162
1163 /* This loop cannot be merged with the above loop nest, because that
1164 * would introduce duplicate offsets.
1165 */
1166 i = 0;
1167 end_siter = g_sequence_get_end_iter (level->seq);
1168 for (siter = g_sequence_get_begin_iter (level->seq);
1169 siter != end_siter;
1170 siter = g_sequence_iter_next (siter))
1171 {
1172 SortElt *elt = g_sequence_get (siter);
1173
1174 elt->offset = tmp_array[i];
1175 i++;
1176 }
1177 g_free (tmp_array);
1178
1179 if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
1180 priv->default_sort_func == NO_SORT_FUNC)
1181 {
1182 gtk_tree_model_sort_sort_level (tree_model_sort, level,
1183 FALSE, FALSE);
1184 gtk_tree_model_sort_increment_stamp (tree_model_sort);
1185
1186 if (gtk_tree_path_get_depth (path))
1187 {
1188 gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
1189 &iter,
1190 path);
1191 gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
1192 path, &iter, new_order);
1193 }
1194 else
1195 {
1196 gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
1197 path, NULL, new_order);
1198 }
1199 }
1200
1201 gtk_tree_path_free (path);
1202 }
1203
1204 /* Fulfill our model requirements */
1205 static GtkTreeModelFlags
gtk_tree_model_sort_get_flags(GtkTreeModel * tree_model)1206 gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
1207 {
1208 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1209 GtkTreeModelFlags flags;
1210
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 if ((flags & GTK_TREE_MODEL_LIST_ONLY) == GTK_TREE_MODEL_LIST_ONLY)
1216 return GTK_TREE_MODEL_LIST_ONLY;
1217
1218 return 0;
1219 }
1220
1221 static gint
gtk_tree_model_sort_get_n_columns(GtkTreeModel * tree_model)1222 gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
1223 {
1224 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1225
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 static GType
gtk_tree_model_sort_get_column_type(GtkTreeModel * tree_model,gint index)1233 gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
1234 gint index)
1235 {
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);
1239
1240 return gtk_tree_model_get_column_type (tree_model_sort->priv->child_model, index);
1241 }
1242
1243 static gboolean
gtk_tree_model_sort_get_iter(GtkTreeModel * tree_model,GtkTreeIter * iter,GtkTreePath * path)1244 gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
1245 GtkTreeIter *iter,
1246 GtkTreePath *path)
1247 {
1248 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1249 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1250 gint *indices;
1251 SortElt *elt;
1252 SortLevel *level;
1253 gint depth, i;
1254 GSequenceIter *siter;
1255
1256 g_return_val_if_fail (priv->child_model != NULL, FALSE);
1257
1258 indices = gtk_tree_path_get_indices (path);
1259
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 depth = gtk_tree_path_get_depth (path);
1265 if (depth == 0)
1266 {
1267 iter->stamp = 0;
1268 return FALSE;
1269 }
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 iter->stamp = 0;
1277 return FALSE;
1278 }
1279
1280 siter = g_sequence_get_iter_at_pos (level->seq, indices[i]);
1281 if (g_sequence_iter_is_end (siter))
1282 {
1283 iter->stamp = 0;
1284 return FALSE;
1285 }
1286
1287 elt = GET_ELT (siter);
1288 if (elt->children == NULL)
1289 gtk_tree_model_sort_build_level (tree_model_sort, level, elt);
1290
1291 level = elt->children;
1292 }
1293
1294 if (!level || indices[i] >= g_sequence_get_length (level->seq))
1295 {
1296 iter->stamp = 0;
1297 return FALSE;
1298 }
1299
1300 iter->stamp = priv->stamp;
1301 iter->user_data = level;
1302
1303 siter = g_sequence_get_iter_at_pos (level->seq, indices[depth - 1]);
1304 if (g_sequence_iter_is_end (siter))
1305 {
1306 iter->stamp = 0;
1307 return FALSE;
1308 }
1309 iter->user_data2 = GET_ELT (siter);
1310
1311 return TRUE;
1312 }
1313
1314 static GtkTreePath *
gtk_tree_model_sort_get_path(GtkTreeModel * tree_model,GtkTreeIter * iter)1315 gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
1316 GtkTreeIter *iter)
1317 {
1318 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1319 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1320 GtkTreePath *retval;
1321 SortLevel *level;
1322 SortElt *elt;
1323
1324 g_return_val_if_fail (priv->child_model != NULL, NULL);
1325 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 gint index;
1335
1336 index = g_sequence_iter_get_position (elt->siter);
1337 gtk_tree_path_prepend_index (retval, index);
1338
1339 elt = level->parent_elt;
1340 level = level->parent_level;
1341 }
1342
1343 return retval;
1344 }
1345
1346 static void
gtk_tree_model_sort_get_value(GtkTreeModel * tree_model,GtkTreeIter * iter,gint column,GValue * value)1347 gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
1348 GtkTreeIter *iter,
1349 gint column,
1350 GValue *value)
1351 {
1352 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1353 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1354 GtkTreeIter child_iter;
1355
1356 g_return_if_fail (priv->child_model != NULL);
1357 g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1358
1359 GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1360 gtk_tree_model_get_value (priv->child_model,
1361 &child_iter, column, value);
1362 }
1363
1364 static gboolean
gtk_tree_model_sort_iter_next(GtkTreeModel * tree_model,GtkTreeIter * iter)1365 gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
1366 GtkTreeIter *iter)
1367 {
1368 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1369 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1370 SortElt *elt;
1371 GSequenceIter *siter;
1372
1373 g_return_val_if_fail (priv->child_model != NULL, FALSE);
1374 g_return_val_if_fail (priv->stamp == iter->stamp, FALSE);
1375
1376 elt = iter->user_data2;
1377
1378 siter = g_sequence_iter_next (elt->siter);
1379 if (g_sequence_iter_is_end (siter))
1380 {
1381 iter->stamp = 0;
1382 return FALSE;
1383 }
1384 iter->user_data2 = GET_ELT (siter);
1385
1386 return TRUE;
1387 }
1388
1389 static gboolean
gtk_tree_model_sort_iter_previous(GtkTreeModel * tree_model,GtkTreeIter * iter)1390 gtk_tree_model_sort_iter_previous (GtkTreeModel *tree_model,
1391 GtkTreeIter *iter)
1392 {
1393 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1394 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1395 SortElt *elt;
1396 GSequenceIter *siter;
1397
1398 g_return_val_if_fail (priv->child_model != NULL, FALSE);
1399 g_return_val_if_fail (priv->stamp == iter->stamp, FALSE);
1400
1401 elt = iter->user_data2;
1402
1403 if (g_sequence_iter_is_begin (elt->siter))
1404 {
1405 iter->stamp = 0;
1406 return FALSE;
1407 }
1408
1409 siter = g_sequence_iter_prev (elt->siter);
1410 iter->user_data2 = GET_ELT (siter);
1411
1412 return TRUE;
1413 }
1414
1415 static gboolean
gtk_tree_model_sort_iter_children(GtkTreeModel * tree_model,GtkTreeIter * iter,GtkTreeIter * parent)1416 gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
1417 GtkTreeIter *iter,
1418 GtkTreeIter *parent)
1419 {
1420 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1421 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1422 SortLevel *level;
1423
1424 iter->stamp = 0;
1425 g_return_val_if_fail (priv->child_model != NULL, FALSE);
1426 if (parent)
1427 g_return_val_if_fail (VALID_ITER (parent, tree_model_sort), FALSE);
1428
1429 if (parent == NULL)
1430 {
1431 if (priv->root == NULL)
1432 gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1433 if (priv->root == NULL)
1434 return FALSE;
1435
1436 level = priv->root;
1437 iter->stamp = priv->stamp;
1438 iter->user_data = level;
1439 iter->user_data2 = g_sequence_get (g_sequence_get_begin_iter (level->seq));
1440 }
1441 else
1442 {
1443 SortElt *elt;
1444
1445 level = SORT_LEVEL (parent->user_data);
1446 elt = SORT_ELT (parent->user_data2);
1447
1448 if (elt->children == NULL)
1449 gtk_tree_model_sort_build_level (tree_model_sort, level, elt);
1450
1451 if (elt->children == NULL)
1452 return FALSE;
1453
1454 iter->stamp = priv->stamp;
1455 iter->user_data = elt->children;
1456 iter->user_data2 = g_sequence_get (g_sequence_get_begin_iter (elt->children->seq));
1457 }
1458
1459 return TRUE;
1460 }
1461
1462 static gboolean
gtk_tree_model_sort_iter_has_child(GtkTreeModel * tree_model,GtkTreeIter * iter)1463 gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
1464 GtkTreeIter *iter)
1465 {
1466 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1467 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1468 GtkTreeIter child_iter;
1469
1470 g_return_val_if_fail (priv->child_model != NULL, FALSE);
1471 g_return_val_if_fail (VALID_ITER (iter, tree_model_sort), FALSE);
1472
1473 GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1474
1475 return gtk_tree_model_iter_has_child (priv->child_model, &child_iter);
1476 }
1477
1478 static gint
gtk_tree_model_sort_iter_n_children(GtkTreeModel * tree_model,GtkTreeIter * iter)1479 gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
1480 GtkTreeIter *iter)
1481 {
1482 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1483 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1484 GtkTreeIter child_iter;
1485
1486 g_return_val_if_fail (priv->child_model != NULL, 0);
1487 if (iter)
1488 g_return_val_if_fail (VALID_ITER (iter, tree_model_sort), 0);
1489
1490 if (iter == NULL)
1491 return gtk_tree_model_iter_n_children (priv->child_model, NULL);
1492
1493 GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1494
1495 return gtk_tree_model_iter_n_children (priv->child_model, &child_iter);
1496 }
1497
1498 static gboolean
gtk_tree_model_sort_iter_nth_child(GtkTreeModel * tree_model,GtkTreeIter * iter,GtkTreeIter * parent,gint n)1499 gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
1500 GtkTreeIter *iter,
1501 GtkTreeIter *parent,
1502 gint n)
1503 {
1504 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1505 SortLevel *level;
1506 /* We have this for the iter == parent case */
1507 GtkTreeIter children;
1508
1509 if (parent)
1510 g_return_val_if_fail (VALID_ITER (parent, tree_model_sort), FALSE);
1511
1512 /* Use this instead of has_child to force us to build the level, if needed */
1513 if (gtk_tree_model_sort_iter_children (tree_model, &children, parent) == FALSE)
1514 {
1515 iter->stamp = 0;
1516 return FALSE;
1517 }
1518
1519 level = children.user_data;
1520 if (n >= g_sequence_get_length (level->seq))
1521 {
1522 iter->stamp = 0;
1523 return FALSE;
1524 }
1525
1526 iter->stamp = tree_model_sort->priv->stamp;
1527 iter->user_data = level;
1528 iter->user_data2 = g_sequence_get (g_sequence_get_iter_at_pos (level->seq, n));
1529
1530 return TRUE;
1531 }
1532
1533 static gboolean
gtk_tree_model_sort_iter_parent(GtkTreeModel * tree_model,GtkTreeIter * iter,GtkTreeIter * child)1534 gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
1535 GtkTreeIter *iter,
1536 GtkTreeIter *child)
1537 {
1538 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1539 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1540 SortLevel *level;
1541
1542 iter->stamp = 0;
1543 g_return_val_if_fail (priv->child_model != NULL, FALSE);
1544 g_return_val_if_fail (VALID_ITER (child, tree_model_sort), FALSE);
1545
1546 level = child->user_data;
1547
1548 if (level->parent_level)
1549 {
1550 iter->stamp = priv->stamp;
1551 iter->user_data = level->parent_level;
1552 iter->user_data2 = level->parent_elt;
1553
1554 return TRUE;
1555 }
1556 return FALSE;
1557 }
1558
1559 static void
gtk_tree_model_sort_ref_node(GtkTreeModel * tree_model,GtkTreeIter * iter)1560 gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
1561 GtkTreeIter *iter)
1562 {
1563 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1564 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1565 GtkTreeIter child_iter;
1566 SortLevel *level;
1567 SortElt *elt;
1568
1569 g_return_if_fail (priv->child_model != NULL);
1570 g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1571
1572 GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1573
1574 /* Reference the node in the child model */
1575 gtk_tree_model_ref_node (priv->child_model, &child_iter);
1576
1577 /* Increase the reference count of this element and its level */
1578 level = iter->user_data;
1579 elt = iter->user_data2;
1580
1581 elt->ref_count++;
1582 level->ref_count++;
1583
1584 if (level->ref_count == 1)
1585 {
1586 SortLevel *parent_level = level->parent_level;
1587 SortElt *parent_elt = level->parent_elt;
1588
1589 /* We were at zero -- time to decrement the zero_ref_count val */
1590 while (parent_level)
1591 {
1592 parent_elt->zero_ref_count--;
1593
1594 parent_elt = parent_level->parent_elt;
1595 parent_level = parent_level->parent_level;
1596 }
1597
1598 if (priv->root != level)
1599 priv->zero_ref_count--;
1600 }
1601 }
1602
1603 static void
gtk_tree_model_sort_real_unref_node(GtkTreeModel * tree_model,GtkTreeIter * iter,gboolean propagate_unref)1604 gtk_tree_model_sort_real_unref_node (GtkTreeModel *tree_model,
1605 GtkTreeIter *iter,
1606 gboolean propagate_unref)
1607 {
1608 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1609 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1610 SortLevel *level;
1611 SortElt *elt;
1612
1613 g_return_if_fail (priv->child_model != NULL);
1614 g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1615
1616 if (propagate_unref)
1617 {
1618 GtkTreeIter child_iter;
1619
1620 GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1621 gtk_tree_model_unref_node (priv->child_model, &child_iter);
1622 }
1623
1624 level = iter->user_data;
1625 elt = iter->user_data2;
1626
1627 g_return_if_fail (elt->ref_count > 0);
1628
1629 elt->ref_count--;
1630 level->ref_count--;
1631
1632 if (level->ref_count == 0)
1633 {
1634 SortLevel *parent_level = level->parent_level;
1635 SortElt *parent_elt = level->parent_elt;
1636
1637 /* We are at zero -- time to increment the zero_ref_count val */
1638 while (parent_level)
1639 {
1640 parent_elt->zero_ref_count++;
1641
1642 parent_elt = parent_level->parent_elt;
1643 parent_level = parent_level->parent_level;
1644 }
1645
1646 if (priv->root != level)
1647 priv->zero_ref_count++;
1648 }
1649 }
1650
1651 static void
gtk_tree_model_sort_unref_node(GtkTreeModel * tree_model,GtkTreeIter * iter)1652 gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
1653 GtkTreeIter *iter)
1654 {
1655 gtk_tree_model_sort_real_unref_node (tree_model, iter, TRUE);
1656 }
1657
1658 /* Sortable interface */
1659 static gboolean
gtk_tree_model_sort_get_sort_column_id(GtkTreeSortable * sortable,gint * sort_column_id,GtkSortType * order)1660 gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable *sortable,
1661 gint *sort_column_id,
1662 GtkSortType *order)
1663 {
1664 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1665 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1666
1667 if (sort_column_id)
1668 *sort_column_id = priv->sort_column_id;
1669 if (order)
1670 *order = priv->order;
1671
1672 if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID ||
1673 priv->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
1674 return FALSE;
1675
1676 return TRUE;
1677 }
1678
1679 static void
gtk_tree_model_sort_set_sort_column_id(GtkTreeSortable * sortable,gint sort_column_id,GtkSortType order)1680 gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable *sortable,
1681 gint sort_column_id,
1682 GtkSortType order)
1683 {
1684 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1685 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1686
1687 if (priv->sort_column_id == sort_column_id && priv->order == order)
1688 return;
1689
1690 if (sort_column_id != GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
1691 {
1692 if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1693 {
1694 GtkTreeDataSortHeader *header = NULL;
1695
1696 header = _gtk_tree_data_list_get_header (priv->sort_list,
1697 sort_column_id);
1698
1699 /* we want to make sure that we have a function */
1700 g_return_if_fail (header != NULL);
1701 g_return_if_fail (header->func != NULL);
1702 }
1703 else
1704 g_return_if_fail (priv->default_sort_func != NULL);
1705 }
1706
1707 priv->sort_column_id = sort_column_id;
1708 priv->order = order;
1709
1710 gtk_tree_sortable_sort_column_changed (sortable);
1711
1712 gtk_tree_model_sort_sort (tree_model_sort);
1713 }
1714
1715 static void
gtk_tree_model_sort_set_sort_func(GtkTreeSortable * sortable,gint sort_column_id,GtkTreeIterCompareFunc func,gpointer data,GDestroyNotify destroy)1716 gtk_tree_model_sort_set_sort_func (GtkTreeSortable *sortable,
1717 gint sort_column_id,
1718 GtkTreeIterCompareFunc func,
1719 gpointer data,
1720 GDestroyNotify destroy)
1721 {
1722 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
1723 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1724
1725 priv->sort_list = _gtk_tree_data_list_set_header (priv->sort_list,
1726 sort_column_id,
1727 func, data, destroy);
1728
1729 if (priv->sort_column_id == sort_column_id)
1730 gtk_tree_model_sort_sort (tree_model_sort);
1731 }
1732
1733 static void
gtk_tree_model_sort_set_default_sort_func(GtkTreeSortable * sortable,GtkTreeIterCompareFunc func,gpointer data,GDestroyNotify destroy)1734 gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable *sortable,
1735 GtkTreeIterCompareFunc func,
1736 gpointer data,
1737 GDestroyNotify destroy)
1738 {
1739 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1740 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1741
1742 if (priv->default_sort_destroy)
1743 {
1744 GDestroyNotify d = priv->default_sort_destroy;
1745
1746 priv->default_sort_destroy = NULL;
1747 d (priv->default_sort_data);
1748 }
1749
1750 priv->default_sort_func = func;
1751 priv->default_sort_data = data;
1752 priv->default_sort_destroy = destroy;
1753
1754 if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
1755 gtk_tree_model_sort_sort (tree_model_sort);
1756 }
1757
1758 static gboolean
gtk_tree_model_sort_has_default_sort_func(GtkTreeSortable * sortable)1759 gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable *sortable)
1760 {
1761 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)sortable;
1762
1763 return (tree_model_sort->priv->default_sort_func != NO_SORT_FUNC);
1764 }
1765
1766 /* DragSource interface */
1767 static gboolean
gtk_tree_model_sort_row_draggable(GtkTreeDragSource * drag_source,GtkTreePath * path)1768 gtk_tree_model_sort_row_draggable (GtkTreeDragSource *drag_source,
1769 GtkTreePath *path)
1770 {
1771 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1772 GtkTreePath *child_path;
1773 gboolean draggable;
1774
1775 child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort,
1776 path);
1777 draggable = gtk_tree_drag_source_row_draggable (GTK_TREE_DRAG_SOURCE (tree_model_sort->priv->child_model), child_path);
1778 gtk_tree_path_free (child_path);
1779
1780 return draggable;
1781 }
1782
1783 static gboolean
gtk_tree_model_sort_drag_data_get(GtkTreeDragSource * drag_source,GtkTreePath * path,GtkSelectionData * selection_data)1784 gtk_tree_model_sort_drag_data_get (GtkTreeDragSource *drag_source,
1785 GtkTreePath *path,
1786 GtkSelectionData *selection_data)
1787 {
1788 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1789 GtkTreePath *child_path;
1790 gboolean gotten;
1791
1792 child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort, path);
1793 gotten = gtk_tree_drag_source_drag_data_get (GTK_TREE_DRAG_SOURCE (tree_model_sort->priv->child_model), child_path, selection_data);
1794 gtk_tree_path_free (child_path);
1795
1796 return gotten;
1797 }
1798
1799 static gboolean
gtk_tree_model_sort_drag_data_delete(GtkTreeDragSource * drag_source,GtkTreePath * path)1800 gtk_tree_model_sort_drag_data_delete (GtkTreeDragSource *drag_source,
1801 GtkTreePath *path)
1802 {
1803 GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *)drag_source;
1804 GtkTreePath *child_path;
1805 gboolean deleted;
1806
1807 child_path = gtk_tree_model_sort_convert_path_to_child_path (tree_model_sort, path);
1808 deleted = gtk_tree_drag_source_drag_data_delete (GTK_TREE_DRAG_SOURCE (tree_model_sort->priv->child_model), child_path);
1809 gtk_tree_path_free (child_path);
1810
1811 return deleted;
1812 }
1813
1814 /* sorting code - private */
1815 static gint
gtk_tree_model_sort_compare_func(gconstpointer a,gconstpointer b,gpointer user_data)1816 gtk_tree_model_sort_compare_func (gconstpointer a,
1817 gconstpointer b,
1818 gpointer user_data)
1819 {
1820 SortData *data = (SortData *)user_data;
1821 GtkTreeModelSort *tree_model_sort = data->tree_model_sort;
1822 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1823 const SortElt *sa = a;
1824 const SortElt *sb = b;
1825
1826 GtkTreeIter iter_a, iter_b;
1827 gint retval;
1828
1829 if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
1830 {
1831 iter_a = sa->iter;
1832 iter_b = sb->iter;
1833 }
1834 else
1835 {
1836 data->parent_path_indices [data->parent_path_depth-1] = sa->offset;
1837 gtk_tree_model_get_iter (GTK_TREE_MODEL (priv->child_model), &iter_a, data->parent_path);
1838 data->parent_path_indices [data->parent_path_depth-1] = sb->offset;
1839 gtk_tree_model_get_iter (GTK_TREE_MODEL (priv->child_model), &iter_b, data->parent_path);
1840 }
1841
1842 retval = (* data->sort_func) (GTK_TREE_MODEL (priv->child_model),
1843 &iter_a, &iter_b,
1844 data->sort_data);
1845
1846 if (priv->order == GTK_SORT_DESCENDING)
1847 {
1848 if (retval > 0)
1849 retval = -1;
1850 else if (retval < 0)
1851 retval = 1;
1852 }
1853
1854 return retval;
1855 }
1856
1857 static gint
gtk_tree_model_sort_offset_compare_func(gconstpointer a,gconstpointer b,gpointer user_data)1858 gtk_tree_model_sort_offset_compare_func (gconstpointer a,
1859 gconstpointer b,
1860 gpointer user_data)
1861 {
1862 gint retval;
1863
1864 const SortElt *sa = (SortElt *)a;
1865 const SortElt *sb = (SortElt *)b;
1866
1867 SortData *data = (SortData *)user_data;
1868
1869 if (sa->offset < sb->offset)
1870 retval = -1;
1871 else if (sa->offset > sb->offset)
1872 retval = 1;
1873 else
1874 retval = 0;
1875
1876 if (data->tree_model_sort->priv->order == GTK_SORT_DESCENDING)
1877 {
1878 if (retval > 0)
1879 retval = -1;
1880 else if (retval < 0)
1881 retval = 1;
1882 }
1883
1884 return retval;
1885 }
1886
1887 static void
gtk_tree_model_sort_sort_level(GtkTreeModelSort * tree_model_sort,SortLevel * level,gboolean recurse,gboolean emit_reordered)1888 gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
1889 SortLevel *level,
1890 gboolean recurse,
1891 gboolean emit_reordered)
1892 {
1893 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1894 gint i;
1895 GSequenceIter *begin_siter, *end_siter, *siter;
1896 SortElt *begin_elt;
1897 gint *new_order;
1898
1899 GtkTreeIter iter;
1900 GtkTreePath *path;
1901
1902 SortData data;
1903
1904 g_return_if_fail (level != NULL);
1905
1906 begin_siter = g_sequence_get_begin_iter (level->seq);
1907 begin_elt = g_sequence_get (begin_siter);
1908
1909 if (g_sequence_get_length (level->seq) < 1 && !begin_elt->children)
1910 return;
1911
1912 iter.stamp = priv->stamp;
1913 iter.user_data = level;
1914 iter.user_data2 = begin_elt;
1915
1916 gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (tree_model_sort), &iter);
1917
1918 i = 0;
1919 end_siter = g_sequence_get_end_iter (level->seq);
1920 for (siter = g_sequence_get_begin_iter (level->seq);
1921 siter != end_siter;
1922 siter = g_sequence_iter_next (siter))
1923 {
1924 SortElt *elt = g_sequence_get (siter);
1925
1926 elt->old_index = i;
1927 i++;
1928 }
1929
1930 fill_sort_data (&data, tree_model_sort, level);
1931
1932 if (data.sort_func == NO_SORT_FUNC)
1933 g_sequence_sort (level->seq, gtk_tree_model_sort_offset_compare_func,
1934 &data);
1935 else
1936 g_sequence_sort (level->seq, gtk_tree_model_sort_compare_func, &data);
1937
1938 free_sort_data (&data);
1939
1940 new_order = g_new (gint, g_sequence_get_length (level->seq));
1941
1942 i = 0;
1943 end_siter = g_sequence_get_end_iter (level->seq);
1944 for (siter = g_sequence_get_begin_iter (level->seq);
1945 siter != end_siter;
1946 siter = g_sequence_iter_next (siter))
1947 {
1948 SortElt *elt = g_sequence_get (siter);
1949
1950 new_order[i++] = elt->old_index;
1951 }
1952
1953 if (emit_reordered)
1954 {
1955 gtk_tree_model_sort_increment_stamp (tree_model_sort);
1956 if (level->parent_elt)
1957 {
1958 iter.stamp = priv->stamp;
1959 iter.user_data = level->parent_level;
1960 iter.user_data2 = level->parent_elt;
1961
1962 path = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort),
1963 &iter);
1964
1965 gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1966 &iter, new_order);
1967 }
1968 else
1969 {
1970 /* toplevel list */
1971 path = gtk_tree_path_new ();
1972 gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), path,
1973 NULL, new_order);
1974 }
1975
1976 gtk_tree_path_free (path);
1977 }
1978
1979 /* recurse, if possible */
1980 if (recurse)
1981 {
1982 end_siter = g_sequence_get_end_iter (level->seq);
1983 for (siter = g_sequence_get_begin_iter (level->seq);
1984 siter != end_siter;
1985 siter = g_sequence_iter_next (siter))
1986 {
1987 SortElt *elt = g_sequence_get (siter);
1988
1989 if (elt->children)
1990 gtk_tree_model_sort_sort_level (tree_model_sort,
1991 elt->children,
1992 TRUE, emit_reordered);
1993 }
1994 }
1995
1996 g_free (new_order);
1997
1998 /* get the iter we referenced at the beginning of this function and
1999 * unref it again
2000 */
2001 iter.stamp = priv->stamp;
2002 iter.user_data = level;
2003 iter.user_data2 = begin_elt;
2004
2005 gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (tree_model_sort), &iter);
2006 }
2007
2008 static void
gtk_tree_model_sort_sort(GtkTreeModelSort * tree_model_sort)2009 gtk_tree_model_sort_sort (GtkTreeModelSort *tree_model_sort)
2010 {
2011 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2012
2013 if (priv->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
2014 return;
2015
2016 if (!priv->root)
2017 return;
2018
2019 if (priv->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
2020 {
2021 GtkTreeDataSortHeader *header = NULL;
2022
2023 header = _gtk_tree_data_list_get_header (priv->sort_list,
2024 priv->sort_column_id);
2025
2026 /* we want to make sure that we have a function */
2027 g_return_if_fail (header != NULL);
2028 g_return_if_fail (header->func != NULL);
2029 }
2030 else
2031 g_return_if_fail (priv->default_sort_func != NULL);
2032
2033 gtk_tree_model_sort_sort_level (tree_model_sort, priv->root,
2034 TRUE, TRUE);
2035 }
2036
2037 /* signal helpers */
2038 static gboolean
gtk_tree_model_sort_insert_value(GtkTreeModelSort * tree_model_sort,SortLevel * level,GtkTreePath * s_path,GtkTreeIter * s_iter)2039 gtk_tree_model_sort_insert_value (GtkTreeModelSort *tree_model_sort,
2040 SortLevel *level,
2041 GtkTreePath *s_path,
2042 GtkTreeIter *s_iter)
2043 {
2044 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2045 SortElt *elt;
2046 SortData data;
2047 gint offset;
2048
2049 elt = sort_elt_new ();
2050
2051 offset = gtk_tree_path_get_indices (s_path)[gtk_tree_path_get_depth (s_path) - 1];
2052
2053 if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2054 elt->iter = *s_iter;
2055 elt->offset = offset;
2056 elt->zero_ref_count = 0;
2057 elt->ref_count = 0;
2058 elt->children = NULL;
2059
2060 /* update all larger offsets */
2061 g_sequence_foreach (level->seq, increase_offset_iter, GINT_TO_POINTER (offset));
2062
2063 fill_sort_data (&data, tree_model_sort, level);
2064
2065 if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
2066 priv->default_sort_func == NO_SORT_FUNC)
2067 {
2068 elt->siter = g_sequence_insert_sorted (level->seq, elt,
2069 gtk_tree_model_sort_offset_compare_func,
2070 &data);
2071 }
2072 else
2073 {
2074 elt->siter = g_sequence_insert_sorted (level->seq, elt,
2075 gtk_tree_model_sort_compare_func,
2076 &data);
2077 }
2078
2079 free_sort_data (&data);
2080
2081 return TRUE;
2082 }
2083
2084 /* sort elt stuff */
2085 static GtkTreePath *
gtk_tree_model_sort_elt_get_path(SortLevel * level,SortElt * elt)2086 gtk_tree_model_sort_elt_get_path (SortLevel *level,
2087 SortElt *elt)
2088 {
2089 SortLevel *walker = level;
2090 SortElt *walker2 = elt;
2091 GtkTreePath *path;
2092
2093 g_return_val_if_fail (level != NULL, NULL);
2094 g_return_val_if_fail (elt != NULL, NULL);
2095
2096 path = gtk_tree_path_new ();
2097
2098 while (walker)
2099 {
2100 gtk_tree_path_prepend_index (path, walker2->offset);
2101
2102 if (!walker->parent_level)
2103 break;
2104
2105 walker2 = walker->parent_elt;
2106 walker = walker->parent_level;
2107 }
2108
2109 return path;
2110 }
2111
2112 /**
2113 * gtk_tree_model_sort_set_model:
2114 * @tree_model_sort: The #GtkTreeModelSort.
2115 * @child_model: (allow-none): A #GtkTreeModel, or %NULL.
2116 *
2117 * Sets the model of @tree_model_sort to be @model. If @model is %NULL,
2118 * then the old model is unset. The sort function is unset as a result
2119 * of this call. The model will be in an unsorted state until a sort
2120 * function is set.
2121 **/
2122 static void
gtk_tree_model_sort_set_model(GtkTreeModelSort * tree_model_sort,GtkTreeModel * child_model)2123 gtk_tree_model_sort_set_model (GtkTreeModelSort *tree_model_sort,
2124 GtkTreeModel *child_model)
2125 {
2126 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2127
2128 if (child_model)
2129 g_object_ref (child_model);
2130
2131 if (priv->child_model)
2132 {
2133 g_signal_handler_disconnect (priv->child_model,
2134 priv->changed_id);
2135 g_signal_handler_disconnect (priv->child_model,
2136 priv->inserted_id);
2137 g_signal_handler_disconnect (priv->child_model,
2138 priv->has_child_toggled_id);
2139 g_signal_handler_disconnect (priv->child_model,
2140 priv->deleted_id);
2141 g_signal_handler_disconnect (priv->child_model,
2142 priv->reordered_id);
2143
2144 /* reset our state */
2145 if (priv->root)
2146 gtk_tree_model_sort_free_level (tree_model_sort, priv->root, TRUE);
2147 priv->root = NULL;
2148 _gtk_tree_data_list_header_free (priv->sort_list);
2149 priv->sort_list = NULL;
2150 g_object_unref (priv->child_model);
2151 }
2152
2153 priv->child_model = child_model;
2154
2155 if (child_model)
2156 {
2157 GType *types;
2158 gint i, n_columns;
2159
2160 priv->changed_id =
2161 g_signal_connect (child_model, "row-changed",
2162 G_CALLBACK (gtk_tree_model_sort_row_changed),
2163 tree_model_sort);
2164 priv->inserted_id =
2165 g_signal_connect (child_model, "row-inserted",
2166 G_CALLBACK (gtk_tree_model_sort_row_inserted),
2167 tree_model_sort);
2168 priv->has_child_toggled_id =
2169 g_signal_connect (child_model, "row-has-child-toggled",
2170 G_CALLBACK (gtk_tree_model_sort_row_has_child_toggled),
2171 tree_model_sort);
2172 priv->deleted_id =
2173 g_signal_connect (child_model, "row-deleted",
2174 G_CALLBACK (gtk_tree_model_sort_row_deleted),
2175 tree_model_sort);
2176 priv->reordered_id =
2177 g_signal_connect (child_model, "rows-reordered",
2178 G_CALLBACK (gtk_tree_model_sort_rows_reordered),
2179 tree_model_sort);
2180
2181 priv->child_flags = gtk_tree_model_get_flags (child_model);
2182 n_columns = gtk_tree_model_get_n_columns (child_model);
2183
2184 types = g_new (GType, n_columns);
2185 for (i = 0; i < n_columns; i++)
2186 types[i] = gtk_tree_model_get_column_type (child_model, i);
2187
2188 priv->sort_list = _gtk_tree_data_list_header_new (n_columns, types);
2189 g_free (types);
2190
2191 priv->default_sort_func = NO_SORT_FUNC;
2192 priv->stamp = g_random_int ();
2193 }
2194 }
2195
2196 /**
2197 * gtk_tree_model_sort_get_model:
2198 * @tree_model: a #GtkTreeModelSort
2199 *
2200 * Returns the model the #GtkTreeModelSort is sorting.
2201 *
2202 * Returns: (transfer none): the "child model" being sorted
2203 **/
2204 GtkTreeModel *
gtk_tree_model_sort_get_model(GtkTreeModelSort * tree_model)2205 gtk_tree_model_sort_get_model (GtkTreeModelSort *tree_model)
2206 {
2207 g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
2208
2209 return tree_model->priv->child_model;
2210 }
2211
2212
2213 static GtkTreePath *
gtk_real_tree_model_sort_convert_child_path_to_path(GtkTreeModelSort * tree_model_sort,GtkTreePath * child_path,gboolean build_levels)2214 gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
2215 GtkTreePath *child_path,
2216 gboolean build_levels)
2217 {
2218 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2219 gint *child_indices;
2220 GtkTreePath *retval;
2221 SortLevel *level;
2222 gint i;
2223
2224 g_return_val_if_fail (priv->child_model != NULL, NULL);
2225 g_return_val_if_fail (child_path != NULL, NULL);
2226
2227 retval = gtk_tree_path_new ();
2228 child_indices = gtk_tree_path_get_indices (child_path);
2229
2230 if (priv->root == NULL && build_levels)
2231 gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
2232 level = SORT_LEVEL (priv->root);
2233
2234 for (i = 0; i < gtk_tree_path_get_depth (child_path); i++)
2235 {
2236 SortElt *tmp;
2237 GSequenceIter *siter;
2238 gboolean found_child = FALSE;
2239
2240 if (!level)
2241 {
2242 gtk_tree_path_free (retval);
2243 return NULL;
2244 }
2245
2246 if (child_indices[i] >= g_sequence_get_length (level->seq))
2247 {
2248 gtk_tree_path_free (retval);
2249 return NULL;
2250 }
2251 tmp = lookup_elt_with_offset (tree_model_sort, level,
2252 child_indices[i], &siter);
2253 if (tmp)
2254 {
2255 gtk_tree_path_append_index (retval, g_sequence_iter_get_position (siter));
2256 if (tmp->children == NULL && build_levels)
2257 gtk_tree_model_sort_build_level (tree_model_sort, level, tmp);
2258
2259 level = tmp->children;
2260 found_child = TRUE;
2261 }
2262
2263 if (! found_child)
2264 {
2265 gtk_tree_path_free (retval);
2266 return NULL;
2267 }
2268 }
2269
2270 return retval;
2271 }
2272
2273
2274 /**
2275 * gtk_tree_model_sort_convert_child_path_to_path:
2276 * @tree_model_sort: A #GtkTreeModelSort
2277 * @child_path: A #GtkTreePath to convert
2278 *
2279 * Converts @child_path to a path relative to @tree_model_sort. That is,
2280 * @child_path points to a path in the child model. The returned path will
2281 * point to the same row in the sorted model. If @child_path isn’t a valid
2282 * path on the child model, then %NULL is returned.
2283 *
2284 * Returns: (nullable) (transfer full): A newly allocated #GtkTreePath, or %NULL
2285 **/
2286 GtkTreePath *
gtk_tree_model_sort_convert_child_path_to_path(GtkTreeModelSort * tree_model_sort,GtkTreePath * child_path)2287 gtk_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
2288 GtkTreePath *child_path)
2289 {
2290 g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2291 g_return_val_if_fail (tree_model_sort->priv->child_model != NULL, NULL);
2292 g_return_val_if_fail (child_path != NULL, NULL);
2293
2294 return gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path, TRUE);
2295 }
2296
2297 /**
2298 * gtk_tree_model_sort_convert_child_iter_to_iter:
2299 * @tree_model_sort: A #GtkTreeModelSort
2300 * @sort_iter: (out): An uninitialized #GtkTreeIter.
2301 * @child_iter: A valid #GtkTreeIter pointing to a row on the child model
2302 *
2303 * Sets @sort_iter to point to the row in @tree_model_sort that corresponds to
2304 * the row pointed at by @child_iter. If @sort_iter was not set, %FALSE
2305 * is returned. Note: a boolean is only returned since 2.14.
2306 *
2307 * Returns: %TRUE, if @sort_iter was set, i.e. if @sort_iter is a
2308 * valid iterator pointer to a visible row in the child model.
2309 **/
2310 gboolean
gtk_tree_model_sort_convert_child_iter_to_iter(GtkTreeModelSort * tree_model_sort,GtkTreeIter * sort_iter,GtkTreeIter * child_iter)2311 gtk_tree_model_sort_convert_child_iter_to_iter (GtkTreeModelSort *tree_model_sort,
2312 GtkTreeIter *sort_iter,
2313 GtkTreeIter *child_iter)
2314 {
2315 gboolean ret;
2316 GtkTreePath *child_path, *path;
2317 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2318
2319 g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), FALSE);
2320 g_return_val_if_fail (priv->child_model != NULL, FALSE);
2321 g_return_val_if_fail (sort_iter != NULL, FALSE);
2322 g_return_val_if_fail (child_iter != NULL, FALSE);
2323 g_return_val_if_fail (sort_iter != child_iter, FALSE);
2324
2325 sort_iter->stamp = 0;
2326
2327 child_path = gtk_tree_model_get_path (priv->child_model, child_iter);
2328 g_return_val_if_fail (child_path != NULL, FALSE);
2329
2330 path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort, child_path);
2331 gtk_tree_path_free (child_path);
2332
2333 if (!path)
2334 {
2335 g_warning ("%s: The conversion of the child path to a GtkTreeModel sort path failed", G_STRLOC);
2336 return FALSE;
2337 }
2338
2339 ret = gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
2340 sort_iter, path);
2341 gtk_tree_path_free (path);
2342
2343 return ret;
2344 }
2345
2346 /**
2347 * gtk_tree_model_sort_convert_path_to_child_path:
2348 * @tree_model_sort: A #GtkTreeModelSort
2349 * @sorted_path: A #GtkTreePath to convert
2350 *
2351 * Converts @sorted_path to a path on the child model of @tree_model_sort.
2352 * That is, @sorted_path points to a location in @tree_model_sort. The
2353 * returned path will point to the same location in the model not being
2354 * sorted. If @sorted_path does not point to a location in the child model,
2355 * %NULL is returned.
2356 *
2357 * Returns: (nullable) (transfer full): A newly allocated #GtkTreePath, or %NULL
2358 **/
2359 GtkTreePath *
gtk_tree_model_sort_convert_path_to_child_path(GtkTreeModelSort * tree_model_sort,GtkTreePath * sorted_path)2360 gtk_tree_model_sort_convert_path_to_child_path (GtkTreeModelSort *tree_model_sort,
2361 GtkTreePath *sorted_path)
2362 {
2363 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2364 gint *sorted_indices;
2365 GtkTreePath *retval;
2366 SortLevel *level;
2367 gint i;
2368
2369 g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
2370 g_return_val_if_fail (priv->child_model != NULL, NULL);
2371 g_return_val_if_fail (sorted_path != NULL, NULL);
2372
2373 retval = gtk_tree_path_new ();
2374 sorted_indices = gtk_tree_path_get_indices (sorted_path);
2375 if (priv->root == NULL)
2376 gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
2377 level = SORT_LEVEL (priv->root);
2378
2379 for (i = 0; i < gtk_tree_path_get_depth (sorted_path); i++)
2380 {
2381 SortElt *elt = NULL;
2382 GSequenceIter *siter;
2383
2384 if ((level == NULL) ||
2385 (g_sequence_get_length (level->seq) <= sorted_indices[i]))
2386 {
2387 gtk_tree_path_free (retval);
2388 return NULL;
2389 }
2390
2391 siter = g_sequence_get_iter_at_pos (level->seq, sorted_indices[i]);
2392 if (g_sequence_iter_is_end (siter))
2393 {
2394 gtk_tree_path_free (retval);
2395 return NULL;
2396 }
2397
2398 elt = GET_ELT (siter);
2399 if (elt->children == NULL)
2400 gtk_tree_model_sort_build_level (tree_model_sort, level, elt);
2401
2402 if (level == NULL)
2403 {
2404 gtk_tree_path_free (retval);
2405 break;
2406 }
2407
2408 gtk_tree_path_append_index (retval, elt->offset);
2409 level = elt->children;
2410 }
2411
2412 return retval;
2413 }
2414
2415 /**
2416 * gtk_tree_model_sort_convert_iter_to_child_iter:
2417 * @tree_model_sort: A #GtkTreeModelSort
2418 * @child_iter: (out): An uninitialized #GtkTreeIter
2419 * @sorted_iter: A valid #GtkTreeIter pointing to a row on @tree_model_sort.
2420 *
2421 * Sets @child_iter to point to the row pointed to by @sorted_iter.
2422 **/
2423 void
gtk_tree_model_sort_convert_iter_to_child_iter(GtkTreeModelSort * tree_model_sort,GtkTreeIter * child_iter,GtkTreeIter * sorted_iter)2424 gtk_tree_model_sort_convert_iter_to_child_iter (GtkTreeModelSort *tree_model_sort,
2425 GtkTreeIter *child_iter,
2426 GtkTreeIter *sorted_iter)
2427 {
2428 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2429 g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2430 g_return_if_fail (priv->child_model != NULL);
2431 g_return_if_fail (child_iter != NULL);
2432 g_return_if_fail (VALID_ITER (sorted_iter, tree_model_sort));
2433 g_return_if_fail (sorted_iter != child_iter);
2434
2435 if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2436 {
2437 *child_iter = SORT_ELT (sorted_iter->user_data2)->iter;
2438 }
2439 else
2440 {
2441 GtkTreePath *path;
2442 gboolean valid = FALSE;
2443
2444 path = gtk_tree_model_sort_elt_get_path (sorted_iter->user_data,
2445 sorted_iter->user_data2);
2446 valid = gtk_tree_model_get_iter (priv->child_model, child_iter, path);
2447 gtk_tree_path_free (path);
2448
2449 g_return_if_fail (valid == TRUE);
2450 }
2451 }
2452
2453 static void
gtk_tree_model_sort_build_level(GtkTreeModelSort * tree_model_sort,SortLevel * parent_level,SortElt * parent_elt)2454 gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
2455 SortLevel *parent_level,
2456 SortElt *parent_elt)
2457 {
2458 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2459 GtkTreeIter iter;
2460 SortLevel *new_level;
2461 gint length = 0;
2462 gint i;
2463
2464 g_assert (priv->child_model != NULL);
2465
2466 if (parent_level == NULL)
2467 {
2468 if (gtk_tree_model_get_iter_first (priv->child_model, &iter) == FALSE)
2469 return;
2470 length = gtk_tree_model_iter_n_children (priv->child_model, NULL);
2471 }
2472 else
2473 {
2474 GtkTreeIter parent_iter;
2475 GtkTreeIter child_parent_iter;
2476
2477 parent_iter.stamp = priv->stamp;
2478 parent_iter.user_data = parent_level;
2479 parent_iter.user_data2 = parent_elt;
2480
2481 gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2482 &child_parent_iter,
2483 &parent_iter);
2484 if (gtk_tree_model_iter_children (priv->child_model,
2485 &iter,
2486 &child_parent_iter) == FALSE)
2487 return;
2488
2489 /* stamp may have changed */
2490 gtk_tree_model_sort_convert_iter_to_child_iter (tree_model_sort,
2491 &child_parent_iter,
2492 &parent_iter);
2493
2494 length = gtk_tree_model_iter_n_children (priv->child_model, &child_parent_iter);
2495
2496 gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (tree_model_sort),
2497 &parent_iter);
2498 }
2499
2500 g_return_if_fail (length > 0);
2501
2502 new_level = g_new (SortLevel, 1);
2503 new_level->seq = g_sequence_new (sort_elt_free);
2504 new_level->ref_count = 0;
2505 new_level->parent_level = parent_level;
2506 new_level->parent_elt = parent_elt;
2507
2508 if (parent_elt)
2509 parent_elt->children = new_level;
2510 else
2511 priv->root = new_level;
2512
2513 /* increase the count of zero ref_counts.*/
2514 while (parent_level)
2515 {
2516 parent_elt->zero_ref_count++;
2517
2518 parent_elt = parent_level->parent_elt;
2519 parent_level = parent_level->parent_level;
2520 }
2521
2522 if (new_level != priv->root)
2523 priv->zero_ref_count++;
2524
2525 for (i = 0; i < length; i++)
2526 {
2527 SortElt *sort_elt;
2528
2529 sort_elt = sort_elt_new ();
2530 sort_elt->offset = i;
2531 sort_elt->zero_ref_count = 0;
2532 sort_elt->ref_count = 0;
2533 sort_elt->children = NULL;
2534
2535 if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
2536 {
2537 sort_elt->iter = iter;
2538 if (gtk_tree_model_iter_next (priv->child_model, &iter) == FALSE &&
2539 i < length - 1)
2540 {
2541 if (parent_level)
2542 {
2543 GtkTreePath *level;
2544 gchar *str;
2545
2546 level = gtk_tree_model_sort_elt_get_path (parent_level,
2547 parent_elt);
2548 str = gtk_tree_path_to_string (level);
2549 gtk_tree_path_free (level);
2550
2551 g_warning ("%s: There is a discrepancy between the sort model "
2552 "and the child model. The child model is "
2553 "advertising a wrong length for level %s:.",
2554 G_STRLOC, str);
2555 g_free (str);
2556 }
2557 else
2558 {
2559 g_warning ("%s: There is a discrepancy between the sort model "
2560 "and the child model. The child model is "
2561 "advertising a wrong length for the root level.",
2562 G_STRLOC);
2563 }
2564
2565 return;
2566 }
2567 }
2568
2569 sort_elt->siter = g_sequence_append (new_level->seq, sort_elt);
2570 }
2571
2572 /* sort level */
2573 gtk_tree_model_sort_sort_level (tree_model_sort, new_level,
2574 FALSE, FALSE);
2575 }
2576
2577 static void
gtk_tree_model_sort_free_level(GtkTreeModelSort * tree_model_sort,SortLevel * sort_level,gboolean unref)2578 gtk_tree_model_sort_free_level (GtkTreeModelSort *tree_model_sort,
2579 SortLevel *sort_level,
2580 gboolean unref)
2581 {
2582 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2583 GSequenceIter *siter;
2584 GSequenceIter *end_siter;
2585
2586 g_assert (sort_level);
2587
2588 end_siter = g_sequence_get_end_iter (sort_level->seq);
2589 for (siter = g_sequence_get_begin_iter (sort_level->seq);
2590 siter != end_siter;
2591 siter = g_sequence_iter_next (siter))
2592 {
2593 SortElt *elt = g_sequence_get (siter);
2594
2595 if (elt->children)
2596 gtk_tree_model_sort_free_level (tree_model_sort,
2597 elt->children, unref);
2598 }
2599
2600 if (sort_level->ref_count == 0)
2601 {
2602 SortLevel *parent_level = sort_level->parent_level;
2603 SortElt *parent_elt = sort_level->parent_elt;
2604
2605 while (parent_level)
2606 {
2607 parent_elt->zero_ref_count--;
2608
2609 parent_elt = parent_level->parent_elt;
2610 parent_level = parent_level->parent_level;
2611 }
2612
2613 if (sort_level != priv->root)
2614 priv->zero_ref_count--;
2615 }
2616
2617 if (sort_level->parent_elt)
2618 {
2619 if (unref)
2620 {
2621 GtkTreeIter parent_iter;
2622
2623 parent_iter.stamp = tree_model_sort->priv->stamp;
2624 parent_iter.user_data = sort_level->parent_level;
2625 parent_iter.user_data2 = sort_level->parent_elt;
2626
2627 gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (tree_model_sort),
2628 &parent_iter);
2629 }
2630
2631 sort_level->parent_elt->children = NULL;
2632 }
2633 else
2634 priv->root = NULL;
2635
2636 g_sequence_free (sort_level->seq);
2637 sort_level->seq = NULL;
2638
2639 g_free (sort_level);
2640 sort_level = NULL;
2641 }
2642
2643 static void
gtk_tree_model_sort_increment_stamp(GtkTreeModelSort * tree_model_sort)2644 gtk_tree_model_sort_increment_stamp (GtkTreeModelSort *tree_model_sort)
2645 {
2646 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2647
2648 do
2649 {
2650 priv->stamp++;
2651 }
2652 while (priv->stamp == 0);
2653
2654 gtk_tree_model_sort_clear_cache (tree_model_sort);
2655 }
2656
2657 static void
gtk_tree_model_sort_clear_cache_helper_iter(gpointer data,gpointer user_data)2658 gtk_tree_model_sort_clear_cache_helper_iter (gpointer data,
2659 gpointer user_data)
2660 {
2661 GtkTreeModelSort *tree_model_sort = user_data;
2662 SortElt *elt = data;
2663
2664 if (elt->zero_ref_count > 0)
2665 gtk_tree_model_sort_clear_cache_helper (tree_model_sort, elt->children);
2666 }
2667
2668 static void
gtk_tree_model_sort_clear_cache_helper(GtkTreeModelSort * tree_model_sort,SortLevel * level)2669 gtk_tree_model_sort_clear_cache_helper (GtkTreeModelSort *tree_model_sort,
2670 SortLevel *level)
2671 {
2672 g_assert (level != NULL);
2673
2674 g_sequence_foreach (level->seq, gtk_tree_model_sort_clear_cache_helper_iter,
2675 tree_model_sort);
2676
2677 if (level->ref_count == 0 && level != tree_model_sort->priv->root)
2678 gtk_tree_model_sort_free_level (tree_model_sort, level, TRUE);
2679 }
2680
2681 /**
2682 * gtk_tree_model_sort_reset_default_sort_func:
2683 * @tree_model_sort: A #GtkTreeModelSort
2684 *
2685 * This resets the default sort function to be in the “unsorted” state. That
2686 * is, it is in the same order as the child model. It will re-sort the model
2687 * to be in the same order as the child model only if the #GtkTreeModelSort
2688 * is in “unsorted” state.
2689 **/
2690 void
gtk_tree_model_sort_reset_default_sort_func(GtkTreeModelSort * tree_model_sort)2691 gtk_tree_model_sort_reset_default_sort_func (GtkTreeModelSort *tree_model_sort)
2692 {
2693 GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
2694
2695 g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2696
2697 if (priv->default_sort_destroy)
2698 {
2699 GDestroyNotify d = priv->default_sort_destroy;
2700
2701 priv->default_sort_destroy = NULL;
2702 d (priv->default_sort_data);
2703 }
2704
2705 priv->default_sort_func = NO_SORT_FUNC;
2706 priv->default_sort_data = NULL;
2707 priv->default_sort_destroy = NULL;
2708
2709 if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
2710 gtk_tree_model_sort_sort (tree_model_sort);
2711 priv->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
2712 }
2713
2714 /**
2715 * gtk_tree_model_sort_clear_cache:
2716 * @tree_model_sort: A #GtkTreeModelSort
2717 *
2718 * This function should almost never be called. It clears the @tree_model_sort
2719 * of any cached iterators that haven’t been reffed with
2720 * gtk_tree_model_ref_node(). This might be useful if the child model being
2721 * sorted is static (and doesn’t change often) and there has been a lot of
2722 * unreffed access to nodes. As a side effect of this function, all unreffed
2723 * iters will be invalid.
2724 **/
2725 void
gtk_tree_model_sort_clear_cache(GtkTreeModelSort * tree_model_sort)2726 gtk_tree_model_sort_clear_cache (GtkTreeModelSort *tree_model_sort)
2727 {
2728 g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
2729
2730 if (tree_model_sort->priv->zero_ref_count > 0)
2731 gtk_tree_model_sort_clear_cache_helper (tree_model_sort, (SortLevel *)tree_model_sort->priv->root);
2732 }
2733
2734 static gboolean
gtk_tree_model_sort_iter_is_valid_helper(GtkTreeIter * iter,SortLevel * level)2735 gtk_tree_model_sort_iter_is_valid_helper (GtkTreeIter *iter,
2736 SortLevel *level)
2737 {
2738 GSequenceIter *siter;
2739 GSequenceIter *end_siter;
2740
2741 end_siter = g_sequence_get_end_iter (level->seq);
2742 for (siter = g_sequence_get_begin_iter (level->seq);
2743 siter != end_siter; siter = g_sequence_iter_next (siter))
2744 {
2745 SortElt *elt = g_sequence_get (siter);
2746
2747 if (iter->user_data == level && iter->user_data2 == elt)
2748 return TRUE;
2749
2750 if (elt->children)
2751 if (gtk_tree_model_sort_iter_is_valid_helper (iter, elt->children))
2752 return TRUE;
2753 }
2754
2755 return FALSE;
2756 }
2757
2758 /**
2759 * gtk_tree_model_sort_iter_is_valid:
2760 * @tree_model_sort: A #GtkTreeModelSort.
2761 * @iter: A #GtkTreeIter.
2762 *
2763 * > This function is slow. Only use it for debugging and/or testing
2764 * > purposes.
2765 *
2766 * Checks if the given iter is a valid iter for this #GtkTreeModelSort.
2767 *
2768 * Returns: %TRUE if the iter is valid, %FALSE if the iter is invalid.
2769 *
2770 * Since: 2.2
2771 **/
2772 gboolean
gtk_tree_model_sort_iter_is_valid(GtkTreeModelSort * tree_model_sort,GtkTreeIter * iter)2773 gtk_tree_model_sort_iter_is_valid (GtkTreeModelSort *tree_model_sort,
2774 GtkTreeIter *iter)
2775 {
2776 g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), FALSE);
2777 g_return_val_if_fail (iter != NULL, FALSE);
2778
2779 if (!VALID_ITER (iter, tree_model_sort))
2780 return FALSE;
2781
2782 return gtk_tree_model_sort_iter_is_valid_helper (iter,
2783 tree_model_sort->priv->root);
2784 }
2785