gtktreemodelsort.c 66.2 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
16
17
18
19
20
 *
 * 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
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

21
/* NOTE: There is a potential for confusion in this code as to whether an iter,
22
23
 * path or value refers to the GtkTreeModelSort model, or the child model being
 * sorted.  As a convention, variables referencing the child model will have an
24
25
26
 * s_ prefix before them (ie. s_iter, s_value, s_path);
 */

27
28
29
30
31
32
33
/* ITER FORMAT:
 *
 * iter->stamp = tree_model_sort->stamp
 * iter->user_data = SortLevel
 * iter->user_data2 = SortElt
 */

34
35
36
37
38
39
/* WARNING: this code is dangerous, can cause sleepless nights,
 * can cause your dog to die among other bad things
 *
 * we warned you and we're not liable for any head injuries.
 */

40
#include "gtktreemodelsort.h"
41
#include "gtktreesortable.h"
42
#include "gtktreestore.h"
43
#include "gtksignal.h"
44
#include "gtktreedatalist.h"
45
#include <string.h>
46
#include "gtkintl.h"
47
48

typedef struct _SortElt SortElt;
49
50
51
52
typedef struct _SortLevel SortLevel;
typedef struct _SortData SortData;
typedef struct _SortTuple SortTuple;

53
54
struct _SortElt
{
55
56
57
58
59
60
61
62
63
64
65
66
67
  GtkTreeIter  iter;
  SortLevel   *children;
  gint         offset;
  gint         ref_count;
  gint         zero_ref_count;
};

struct _SortLevel
{
  GArray    *array;
  gint       ref_count;
  SortElt   *parent_elt;
  SortLevel *parent_level;
68
69
};

Jonathan Blandford's avatar
Jonathan Blandford committed
70
71
struct _SortData
{
72
  GtkTreeModelSort *tree_model_sort;
73
74
75
76
77
  GtkTreePath *parent_path;
  gint parent_path_depth;
  gint *parent_path_indices;
  GtkTreeIterCompareFunc sort_func;
  gpointer sort_data;
Jonathan Blandford's avatar
Jonathan Blandford committed
78
79
};

80
81
82
struct _SortTuple
{
  SortElt   *elt;
83
  gint       offset;
84
};
85

86
87
88
89
90
91
92
93
94
/* Properties */
enum {
  PROP_0,
  /* Construct args */
  PROP_MODEL
};



95
96
97
98
99
100
#define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) \
	(((GtkTreeModelSort *)tree_model_sort)->child_flags&GTK_TREE_MODEL_ITERS_PERSIST)
#define SORT_ELT(sort_elt) ((SortElt *)sort_elt)
#define SORT_LEVEL(sort_level) ((SortLevel *)sort_level)

#define GET_CHILD_ITER(tree_model_sort,child_iter,sort_iter) gtk_tree_model_sort_convert_iter_to_child_iter(GTK_TREE_MODEL_SORT (tree_model_sort), child_iter, sort_iter);
101

102
103
#define NO_SORT_FUNC ((GtkTreeIterCompareFunc) 0x1)

104
/* general (object/interface init, etc) */
105
106
107
108
109
static void gtk_tree_model_sort_init                  (GtkTreeModelSort      *tree_model_sort);
static void gtk_tree_model_sort_class_init            (GtkTreeModelSortClass *tree_model_sort_class);
static void gtk_tree_model_sort_tree_model_init       (GtkTreeModelIface     *iface);
static void gtk_tree_model_sort_tree_sortable_init    (GtkTreeSortableIface  *iface);
static void gtk_tree_model_sort_finalize              (GObject               *object);
110
111
112
113
114
115
116
117
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);
118

119
/* our signal handlers */
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
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);
140
141

/* TreeModel interface */
142
static guint        gtk_tree_model_sort_get_flags          (GtkTreeModel          *tree_model);
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
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);
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);
173
174
175
static void         gtk_tree_model_sort_real_unref_node    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
							    gboolean               propagate_unref);
176
177
178
179
static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);

/* TreeSortable interface */
180
181
182
183
184
185
186
187
188
189
190
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,
							       GtkDestroyNotify        destroy);
191
192
193
194
195
static void         gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
							       GtkTreeIterCompareFunc  func,
							       gpointer                data,
							       GtkDestroyNotify        destroy);
static gboolean     gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable     *sortable);
196

197
/* Private functions (sort funcs, level handling and other utils) */
198
199
200
201
202
203
204
205
206
207
208
static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *parent_level,
							   SortElt          *parent_elt);
static void         gtk_tree_model_sort_free_level        (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *sort_level);
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);
209
210
211
212
213
static gint         gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *level,
							   GtkTreeIter      *iter,
							   gboolean          skip_sort_elt);
static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
214
							   SortLevel        *level,
215
216
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
217
218
219
220
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);
221
222
223
static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
									 GtkTreePath      *child_path,
									 gboolean          build_levels);
224

225
static GObjectClass *parent_class = NULL;
226

227
GType
228
229
gtk_tree_model_sort_get_type (void)
{
230
  static GType tree_model_sort_type = 0;
231

232
233
234
235
236
  if (!tree_model_sort_type)
    {
      static const GTypeInfo tree_model_sort_info =
      {
        sizeof (GtkTreeModelSortClass),
237
238
        NULL,           /* base_init */
        NULL,           /* base_finalize */
239
        (GClassInitFunc) gtk_tree_model_sort_class_init,
240
241
        NULL,           /* class_finalize */
        NULL,           /* class_data */
242
        sizeof (GtkTreeModelSort),
243
        0,              /* n_preallocs */
244
245
246
247
248
        (GInstanceInitFunc) gtk_tree_model_sort_init
      };

      static const GInterfaceInfo tree_model_info =
      {
249
250
251
        (GInterfaceInitFunc) gtk_tree_model_sort_tree_model_init,
        NULL,
        NULL
252
253
      };

254
255
      static const GInterfaceInfo sortable_info =
      {
256
257
258
        (GInterfaceInitFunc) gtk_tree_model_sort_tree_sortable_init,
        NULL,
        NULL
259
260
      };

261
262
263
      tree_model_sort_type = g_type_register_static (G_TYPE_OBJECT,
						     "GtkTreeModelSort",
						     &tree_model_sort_info, 0);
264
      g_type_add_interface_static (tree_model_sort_type,
265
266
                                   GTK_TYPE_TREE_MODEL,
                                   &tree_model_info);
267

268
      g_type_add_interface_static (tree_model_sort_type,
269
270
                                   GTK_TYPE_TREE_SORTABLE,
                                   &sortable_info);
271
272
273
274
275
276
    }

  return tree_model_sort_type;
}

static void
277
278
279
280
281
282
283
284
285
286
287
gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
{
  tree_model_sort->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
  tree_model_sort->stamp = 0;
  tree_model_sort->zero_ref_count = 0;
  tree_model_sort->root = NULL;
  tree_model_sort->sort_list = NULL;
}

static void
gtk_tree_model_sort_class_init (GtkTreeModelSortClass *class)
288
289
290
{
  GObjectClass *object_class;

291
  object_class = (GObjectClass *) class;
292
  parent_class = g_type_class_peek_parent (class);
293

294
295
296
  object_class->set_property = gtk_tree_model_sort_set_property;
  object_class->get_property = gtk_tree_model_sort_get_property;

297
  object_class->finalize = gtk_tree_model_sort_finalize;
298
299
300
301
302
303
304
305
306

  /* Properties */
  g_object_class_install_property (object_class,
                                   PROP_MODEL,
                                   g_param_spec_object ("model",
							_("TreeModelSort Model"),
							_("The model for the TreeModelSort to sort"),
							GTK_TYPE_TREE_MODEL,
							G_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
307
308
309
310
311
}

static void
gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
{
312
  iface->get_flags = gtk_tree_model_sort_get_flags;
313
314
315
316
317
318
319
320
321
322
323
  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;
  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;
324
325
  iface->ref_node = gtk_tree_model_sort_ref_node;
  iface->unref_node = gtk_tree_model_sort_unref_node;
326
327
}

328
329
330
331
332
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;
333
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
334
335
  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;
336
337
}

338
339
340
341
342
343
344
345
/**
 * gtk_tree_model_sort_new_with_model:
 * @child_model: A #GtkTreeModel
 *
 * Creates a new #GtkTreeModel, with @child_model as the child_model.
 *
 * Return value: A new #GtkTreeModel.
 */
346
GtkTreeModel *
347
gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
348
349
350
{
  GtkTreeModel *retval;

351
352
353
354
  g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);

  retval = GTK_TREE_MODEL (g_object_new (gtk_tree_model_sort_get_type (), NULL));

355
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
356
357
358
359

  return retval;
}

360
361
362
/* GObject callbacks */
static void
gtk_tree_model_sort_finalize (GObject *object)
363
{
364
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
365

366
367
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

368
  if (tree_model_sort->root)
369
    gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
370
371
372
373
374
375

  if (tree_model_sort->sort_list)
    {
      _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
      tree_model_sort->sort_list = NULL;
    }
376
377
378

  /* must chain up */
  parent_class->finalize (object);
379
380
}

381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
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:
      g_value_set_object (value, gtk_tree_model_sort_get_model(tree_model_sort));
      break;
    default:
      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
      break;
    }
}

419
static void
420
gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
421
422
				 GtkTreePath  *start_s_path,
				 GtkTreeIter  *start_s_iter,
423
				 gpointer      data)
424
425
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
426
  GtkTreePath *path = NULL;
427
  GtkTreeIter iter;
428
  GtkTreeIter tmpiter;
429

430
  SortElt tmp;
431
432
  SortElt *elt;
  SortLevel *level;
433

434
435
436
  gboolean free_s_path = FALSE;

  gint offset, index = 0, i;
437
438

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

440
  if (!start_s_path)
441
442
    {
      free_s_path = TRUE;
443
      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
444
    }
445

446
447
448
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      start_s_path,
							      FALSE);
449
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
450
451
    {
      if (free_s_path)
452
	gtk_tree_path_free (start_s_path);
Jonathan Blandford's avatar
Jonathan Blandford committed
453
454
      return;
    }
Jonathan Blandford's avatar
sync    
Jonathan Blandford committed
455

456
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
457

458
459
  level = iter.user_data;
  elt = iter.user_data2;
460

461
462
463
  if (level->array->len < 2 ||
      (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
       tree_model_sort->default_sort_func == NO_SORT_FUNC))
464
465
    {
      if (free_s_path)
466
	gtk_tree_path_free (start_s_path);
467

468
      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
469

470
      gtk_tree_path_free (path);
471

472
473
474
      return;
    }

475
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
476
477
478
479
    {
      gtk_tree_model_get_iter (tree_model_sort->child_model,
			       &tmpiter, start_s_path);
    }
480

481
482
483
484
485
  offset = elt->offset;

  for (i = 0; i < level->array->len; i++)
    if (elt->offset == g_array_index (level->array, SortElt, i).offset)
      index = i;
486

487
  memcpy (&tmp, elt, sizeof (SortElt));
488
  g_array_remove_index (level->array, index);
489

490
491
492
  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
493
494
495
						   &tmp.iter,
						   TRUE);
  else
496
497
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
498
499
						   &tmpiter,
						   TRUE);
500

501
  g_array_insert_val (level->array, index, tmp);
502

503
504
505
  for (i = 0; i < level->array->len; i++)
    if (g_array_index (level->array, SortElt, i).children)
      g_array_index (level->array, SortElt, i).children->parent_elt = &g_array_index (level->array, SortElt, i);
506

507
508
  gtk_tree_path_up (path);
  gtk_tree_path_append_index (path, index);
509

510
511
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
512

513
514
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);

515
516
  gtk_tree_path_free (path);
  if (free_s_path)
517
    gtk_tree_path_free (start_s_path);
518
519
}

520
521
522
523
524
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
525
{
526
527
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  GtkTreePath *path;
528
  GtkTreeIter iter;
529
530
531
532
533
534
535
536
537
538
539
  GtkTreeIter real_s_iter;

  gint i = 0;

  gboolean free_s_path = FALSE;

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

  parent_level = level = SORT_LEVEL (tree_model_sort->root);
540

541
  g_return_if_fail (s_path != NULL || s_iter != NULL);
542

543
  if (!s_path)
544
    {
545
546
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
547
    }
548

549
550
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
551
  else
552
    real_s_iter = *s_iter;
553

554
555
556
  if (!tree_model_sort->root)
    {
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
557

558
559
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
560

561
      goto done_and_submit;
562
    }
563

564
565
566
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
567
568
      gint j;

569
570
571
572
573
      if (!level)
	{
	  /* level not yet build, we won't cover this signal */
	  goto done;
	}
574

575
576
577
578
579
580
581
      if (level->array->len < gtk_tree_path_get_indices (s_path)[i])
	{
	  g_warning ("A node was inserted with a parent that's not in the tree.\n"
		     "This possibly means that a GtkTreeModel inserted a child node\n"
		     "before the parent was inserted.");
	  goto done;
	}
582

583
584
585
586
587
588
589
590
591
      elt = NULL;
      for (j = 0; j < level->array->len; j++)
	if (g_array_index (level->array, SortElt, j).offset == gtk_tree_path_get_indices (s_path)[i])
	  {
	    elt = &g_array_index (level->array, SortElt, j);
	    break;
	  }

      g_return_if_fail (elt != NULL);
592
593
594
595
596

      if (!elt->children)
	{
	  GtkTreePath *tmppath;
	  GtkTreeIter  tmpiter;
597

598
599
600
601
602
603
604
605
606
607
	  tmppath = gtk_tree_model_sort_elt_get_path (level, elt);
	  if (tmppath)
	    {
	      gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &tmpiter,
				       tmppath);
	      gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data),
						    tmppath,
						    &tmpiter);
	      gtk_tree_path_free (tmppath);
	    }
608

609
610
611
612
613
614
615
616
	  /* not covering this signal */
	  goto done;
	}

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

618
  if (!parent_level)
619
    goto done;
620

621
622
623
624
625
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
626

627
 done_and_submit:
628
629
630
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
631

632
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
633
    return;
634

635
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
636

637
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
638
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
639
  gtk_tree_path_free (path);
640

641
 done:
642
643
  if (free_s_path)
    gtk_tree_path_free (s_path);
644

645
  return;
646
647
648
}

static void
649
650
651
652
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
653
654
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
655
656
  GtkTreePath *path;
  GtkTreeIter iter;
657

658
  g_return_if_fail (s_path != NULL && s_iter != NULL);
659

660
661
  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
662
    return;
663

664
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
665
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
666

667
  gtk_tree_path_free (path);
668
669
}

670
/* FIXME: I still have doubts if this works */
671
static void
672
673
674
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
675
676
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
677
  GtkTreePath *path = NULL;
678
679
680
681
682
  SortElt *elt;
  SortLevel *level;
  GtkTreeIter iter;
  gint offset;
  gint i;
683

684
  g_return_if_fail (s_path != NULL);
685

686
687
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
688
689
    return;

690
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
691

692
693
694
695
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

696
697
698
699
700
701
702
703
  /* we _need_ to emit ::row_deleted before we start unreffing the node
   * itself. This is because of the row refs, which start unreffing nodes
   * when we emit ::row_deleted
   */
  gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);

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

704
  while (elt->ref_count > 0)
705
    gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
706

707
  if (level->ref_count == 0 && level != tree_model_sort->root)
708
    {
709
710
      /* This will prune the level, so I can just emit the signal and not worry
       * about cleaning this level up. */
711
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
712
      gtk_tree_path_free (path);
713
714
      return;
    }
715

716
717
  gtk_tree_model_sort_increment_stamp (tree_model_sort);

718
719
720
721
722
723
  /* Remove the row */
  for (i = 0; i < level->array->len; i++)
    if (elt->offset == g_array_index (level->array, SortElt, i).offset)
      break;

  g_array_remove_index (level->array, i);
724

725
726
727
728
729
730
  /* update all offsets */
  for (i = 0; i < level->array->len; i++)
    {
      elt = & (g_array_index (level->array, SortElt, i));
      if (elt->offset > offset)
	elt->offset--;
731
732
      if (elt->children)
	elt->children->parent_elt = elt;
733
    }
734
735

  gtk_tree_path_free (path);
736
737
}

738
static void
739
740
741
742
743
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
744
{
745
746
  SortElt *elt;
  SortLevel *level;
Jonathan Blandford's avatar
Jonathan Blandford committed
747
748
  GtkTreeIter iter;
  gint *tmp_array;
749
  int i, j;
750
  GtkTreePath *path;
751
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
752

753
  g_return_if_fail (new_order != NULL);
754

Jonathan Blandford's avatar
Jonathan Blandford committed
755
  if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
756
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
757
758
      if (tree_model_sort->root == NULL)
	return;
Jonathan Blandford's avatar
Jonathan Blandford committed
759
      path = gtk_tree_path_new ();
Jonathan Blandford's avatar
Jonathan Blandford committed
760
      level = SORT_LEVEL (tree_model_sort->root);
761
762
    }
  else
763
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
764
765
766
767
      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);
768

769
770
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
771
772

      if (!elt->children)
Jonathan Blandford's avatar
Jonathan Blandford committed
773
774
775
776
	{
	  gtk_tree_path_free (path);
	  return;
	}
777

778
779
780
      level = elt->children;
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
781
  if (level->array->len < 2)
782
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
783
784
785
      gtk_tree_path_free (path);
      return;
    }
786

Jonathan Blandford's avatar
Jonathan Blandford committed
787
788
  tmp_array = g_new (int, level->array->len);
  for (i = 0; i < level->array->len; i++)
789
790
791
792
793
794
795
796
    {
      for (j = 0; j < level->array->len; j++)
	{
	  if (g_array_index (level->array, SortElt, i).offset == new_order[j])
	    tmp_array[i] = j;
	}
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
797
798
799
  for (i = 0; i < level->array->len; i++)
    g_array_index (level->array, SortElt, i).offset = tmp_array[i];
  g_free (tmp_array);
800

801
802
  if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
      tree_model_sort->default_sort_func == NO_SORT_FUNC)
Jonathan Blandford's avatar
Jonathan Blandford committed
803
    {
804

805
806
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
Jonathan Blandford's avatar
Jonathan Blandford committed
807
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
808

809
      if (gtk_tree_path_get_depth (path))
810
	{
811
812
813
814
815
	  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);
816
	}
817
      else
818
819
820
821
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
822
823
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
824
  gtk_tree_path_free (path);
825
826
827
828
829
830
831
832
833
}

/* Fulfill our model requirements */
static guint
gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);

  return 0;
834
835
}

836
837
838
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
839
840
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

841
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
842
843
844

  if (tree_model_sort->child_model == 0)
    return 0;
845

846
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
847
848
849
850
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
851
                                     gint          index)
852
853
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
854
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
855

856
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
857
858
859
}

static gboolean
860
861
862
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
863
{
864
865
866
867
  GtkTreeModelSort *tree_model_sort;
  gint *indices;
  SortLevel *level;
  gint depth, i;
868

869
870
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
871

872
873
874
875
876
877
878
879
880
  tree_model_sort = (GtkTreeModelSort *) tree_model;
  indices = gtk_tree_path_get_indices (path);

  if (tree_model_sort->root == NULL)
    gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
  level = SORT_LEVEL (tree_model_sort->root);

  depth = gtk_tree_path_get_depth (path);
  if (depth == 0)
881
    return FALSE;
882

883
  for (i = 0; i < depth - 1; i++)
884
    {
885
886
887
      if ((level == NULL) ||
	  (level->array->len < indices[i]))
	return FALSE;
888

889
890
891
      if (g_array_index (level->array, SortElt, indices[i]).children == NULL)
	gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, indices[i]));
      level = g_array_index (level->array, SortElt, indices[i]).children;
892
893
    }

894
895
896
897
898
  if (level == NULL)
    return FALSE;
  iter->stamp = tree_model_sort->stamp;
  iter->user_data = level;
  iter->user_data2 = &g_array_index (level->array, SortElt, indices[depth - 1]);
899

900
  return TRUE;
901
902
903
904
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
905
			      GtkTreeIter  *iter)
906
{
907
908
909
910
  GtkTreePath *retval;
  SortLevel *level;
  SortElt *elt;

911
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
912
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
913
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
914

915
916
917
918
  retval = gtk_tree_path_new ();
  level = iter->user_data;
  elt = iter->user_data2;
  while (level != NULL)
919
    {
920
921
922
923
      gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);

      elt = level->parent_elt;
      level = level->parent_level;
924
    }
925
926

  return retval;
927
928
929
930
}

static void
gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
931
932
933
			       GtkTreeIter  *iter,
			       gint          column,
			       GValue       *value)
934
{
935
  GtkTreeIter child_iter;
936
937

  g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
938
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
939
940
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);

941
  GET_CHILD_ITER (tree_model, &child_iter, iter);
942
943
  gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
			    &child_iter, column, value);
944
945
946
947
}

static gboolean
gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
948
			       GtkTreeIter  *iter)
949
{
950
  SortLevel *level;
951
952
953
  SortElt *elt;

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
954
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
955
956
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

957
958
  level = iter->user_data;
  elt = iter->user_data2;
959

960
  if (elt - (SortElt *)level->array->data >= level->array->len - 1)
961
962
963
964
    {
      iter->stamp = 0;
      return FALSE;
    }
965
  iter->user_data2 = elt + 1;
966

967
968
969
970
971
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
972
973
				   GtkTreeIter  *iter,
				   GtkTreeIter  *parent)
974
{
975
976
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
977

978
  iter->stamp = 0;
979
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
980
981
  g_return_val_if_fail (tree_model_sort->child_model != NULL, FALSE);
  if (parent) g_return_val_if_fail (tree_model_sort->stamp == parent->stamp, FALSE);
Jonathan Blandford's avatar
Jonathan Blandford committed
982

983
984
985
986
987
988
  if (parent == NULL)
    {
      if (tree_model_sort->root == NULL)
	gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
      if (tree_model_sort->root == NULL)
	return FALSE;
989

990
991
992
993
994
      level = tree_model_sort->root;
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = level;
      iter->user_data2 = level->array->data;
    }
995
  else
996
    {
997
998
999
1000
1001
      if (((SortElt *)parent->user_data2)->children == NULL)
	gtk_tree_model_sort_build_level (tree_model_sort,
					 (SortLevel *)parent->user_data,
					 (SortElt *)parent->user_data2);
      if (((SortElt *)parent->user_data2)->children == NULL)
1002
	return FALSE;
1003
1004
1005
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = ((SortElt *)parent->user_data2)->children;
      iter->user_data2 = ((SortLevel *)iter->user_data)->array->data;
1006
    }
1007

1008
1009
1010
1011
1012
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
1013
				    GtkTreeIter  *iter)
1014
{
1015
  GtkTreeIter child_iter;
1016
1017

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1018
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1019
1020
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

1021
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1022

1023
  return gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1024
1025
1026
1027
1028
1029
}

static gint
gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
				     GtkTreeIter  *iter)
{
1030
  GtkTreeIter child_iter;
1031
1032

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
1033
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
1034
  if (iter) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, 0);
1035

1036
1037
  if (iter == NULL)
    return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, NULL);
1038

1039
  GET_CHILD_ITER (tree_model, &child_iter, iter);