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);
807

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

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

/* 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;
833
834
}

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

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

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

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

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

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

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

868
869
  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);
870

871
872
873
874
875
876
877
878
879
  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)
880
    return FALSE;
881

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

888
889
890
      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;
891
892
    }

893
894
895
896
897
  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]);
898

899
  return TRUE;
900
901
902
903
}

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

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

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

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

  return retval;
926
927
928
929
}

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

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

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

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

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

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

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

966
967
968
969
970
  return TRUE;
}

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

977
  iter->stamp = 0;
978
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
979
980
  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
981

982
983
984
985
986
987
  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;
988

989
990
991
992
993
      level = tree_model_sort->root;
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = level;
      iter->user_data2 = level->array->data;
    }
994
  else
995
    {
996
997
998
999
1000
      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)
1001
	return FALSE;
1002
1003
1004
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = ((SortElt *)parent->user_data2)->children;
      iter->user_data2 = ((SortLevel *)iter->user_data)->array->data;
1005
    }
1006

1007
1008
1009
1010
1011
  return TRUE;
}

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

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

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

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

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

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

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

1038
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1039