gtktreemodelsort.c 68.1 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.
 */

Manish Singh's avatar
Manish Singh committed
40 41
#include <string.h>

42
#include "gtktreemodelsort.h"
43
#include "gtktreesortable.h"
44
#include "gtktreestore.h"
45
#include "gtktreedatalist.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)

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

106
/* general (object/interface init, etc) */
107 108 109 110 111
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);
112 113 114 115 116 117 118 119
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);
120

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

/* TreeModel interface */
144
static GtkTreeModelFlags gtk_tree_model_sort_get_flags     (GtkTreeModel          *tree_model);
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 173 174
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);
175 176 177
static void         gtk_tree_model_sort_real_unref_node    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
							    gboolean               propagate_unref);
178 179 180 181
static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);

/* TreeSortable interface */
182 183 184 185 186 187 188 189 190 191 192
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);
193 194 195 196 197
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);
198

199
/* Private functions (sort funcs, level handling and other utils) */
200 201 202 203 204 205 206 207 208 209 210
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);
211 212 213 214 215
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,
216
							   SortLevel        *level,
217 218
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
219 220 221 222
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);
223 224 225
static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
									 GtkTreePath      *child_path,
									 gboolean          build_levels);
226

227
static GObjectClass *parent_class = NULL;
228

229
GType
230 231
gtk_tree_model_sort_get_type (void)
{
232
  static GType tree_model_sort_type = 0;
233

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

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

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

Manish Singh's avatar
Manish Singh committed
263 264 265 266
      tree_model_sort_type =
	g_type_register_static (G_TYPE_OBJECT, "GtkTreeModelSort",
				&tree_model_sort_info, 0);

267
      g_type_add_interface_static (tree_model_sort_type,
268 269
                                   GTK_TYPE_TREE_MODEL,
                                   &tree_model_info);
270

271
      g_type_add_interface_static (tree_model_sort_type,
272 273
                                   GTK_TYPE_TREE_SORTABLE,
                                   &sortable_info);
274 275 276 277 278 279
    }

  return tree_model_sort_type;
}

static void
280 281 282 283 284 285 286 287 288 289 290
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)
291 292 293
{
  GObjectClass *object_class;

294
  object_class = (GObjectClass *) class;
295
  parent_class = g_type_class_peek_parent (class);
296

297 298 299
  object_class->set_property = gtk_tree_model_sort_set_property;
  object_class->get_property = gtk_tree_model_sort_get_property;

300
  object_class->finalize = gtk_tree_model_sort_finalize;
301 302 303 304 305 306 307 308 309

  /* 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));
310 311 312 313 314
}

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

331 332 333 334 335
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;
336
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
337 338
  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;
339 340
}

341 342 343 344 345 346 347 348
/**
 * 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.
 */
349
GtkTreeModel *
350
gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
351 352 353
{
  GtkTreeModel *retval;

354 355
  g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);

Manish Singh's avatar
Manish Singh committed
356
  retval = g_object_new (gtk_tree_model_sort_get_type (), NULL);
357

358
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
359 360 361 362

  return retval;
}

363 364 365
/* GObject callbacks */
static void
gtk_tree_model_sort_finalize (GObject *object)
366
{
367
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
368

369 370
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

371
  if (tree_model_sort->root)
372
    gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
373 374 375 376 377 378

  if (tree_model_sort->sort_list)
    {
      _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
      tree_model_sort->sort_list = NULL;
    }
379 380 381

  /* must chain up */
  parent_class->finalize (object);
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 419 420 421
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;
    }
}

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

433
  SortElt tmp;
434 435
  SortElt *elt;
  SortLevel *level;
436

437 438 439
  gboolean free_s_path = FALSE;

  gint offset, index = 0, i;
440 441

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

443
  if (!start_s_path)
444 445
    {
      free_s_path = TRUE;
446
      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
447
    }
448

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

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

461 462
  level = iter.user_data;
  elt = iter.user_data2;
463

464 465 466
  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))
467 468
    {
      if (free_s_path)
469
	gtk_tree_path_free (start_s_path);
470

471
      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
472

473
      gtk_tree_path_free (path);
474

475 476 477
      return;
    }

478
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
479 480 481 482
    {
      gtk_tree_model_get_iter (tree_model_sort->child_model,
			       &tmpiter, start_s_path);
    }
483

484 485 486 487 488
  offset = elt->offset;

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

490
  memcpy (&tmp, elt, sizeof (SortElt));
491
  g_array_remove_index (level->array, index);
492

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

504
  g_array_insert_val (level->array, index, tmp);
505

506 507 508
  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);
509

510 511
  gtk_tree_path_up (path);
  gtk_tree_path_append_index (path, index);
512

513 514
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
515

516 517
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);

518 519
  gtk_tree_path_free (path);
  if (free_s_path)
520
    gtk_tree_path_free (start_s_path);
521 522
}

523 524 525 526 527
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
528
{
529 530
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  GtkTreePath *path;
531
  GtkTreeIter iter;
532 533 534 535 536 537 538 539 540 541 542
  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);
543

544
  g_return_if_fail (s_path != NULL || s_iter != NULL);
545

546
  if (!s_path)
547
    {
548 549
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
550
    }
551

552 553
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
554
  else
555
    real_s_iter = *s_iter;
556

557 558 559
  if (!tree_model_sort->root)
    {
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
560

561 562
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
563

564
      goto done_and_submit;
565
    }
566

567 568 569
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
570 571
      gint j;

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

578 579 580 581 582 583 584
      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;
	}
585

586 587 588 589 590 591 592 593 594
      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);
595 596 597 598 599

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

601 602 603 604 605
	  tmpiter.stamp = tree_model_sort->stamp;
	  tmpiter.user_data = level;
	  tmpiter.user_data2 = elt;

	  tmppath = gtk_tree_model_get_path (GTK_TREE_MODEL (data), &tmpiter);
606 607 608 609 610 611 612
	  if (tmppath)
	    {
	      gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data),
						    tmppath,
						    &tmpiter);
	      gtk_tree_path_free (tmppath);
	    }
613

614 615 616 617 618 619 620 621
	  /* not covering this signal */
	  goto done;
	}

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

623
  if (!parent_level)
624
    goto done;
625

626 627 628 629 630
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
631

632
 done_and_submit:
633 634 635
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
636

637
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
638
    return;
639

640
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
641

642
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
643
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
644
  gtk_tree_path_free (path);
645

646
 done:
647 648
  if (free_s_path)
    gtk_tree_path_free (s_path);
649

650
  return;
651 652 653
}

static void
654 655 656 657
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
658 659
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
660 661
  GtkTreePath *path;
  GtkTreeIter iter;
662

663
  g_return_if_fail (s_path != NULL && s_iter != NULL);
664

665 666
  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
667
    return;
668

669
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
670
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
671

672
  gtk_tree_path_free (path);
673 674
}

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

689
  g_return_if_fail (s_path != NULL);
690

691 692
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
693 694
    return;

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

697 698 699 700
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

701 702 703 704 705 706 707 708
  /* 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);

709
  while (elt->ref_count > 0)
710
    gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
711

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

721 722
  gtk_tree_model_sort_increment_stamp (tree_model_sort);

723 724 725 726 727 728
  /* 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);
729

730 731 732 733 734 735
  /* 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--;
736 737
      if (elt->children)
	elt->children->parent_elt = elt;
738
    }
739 740

  gtk_tree_path_free (path);
741 742
}

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

758
  g_return_if_fail (new_order != NULL);
759

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

774 775
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
776 777

      if (!elt->children)
Jonathan Blandford's avatar
Jonathan Blandford committed
778 779 780 781
	{
	  gtk_tree_path_free (path);
	  return;
	}
782

783 784 785
      level = elt->children;
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
786
  if (level->array->len < 2)
787
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
788 789 790
      gtk_tree_path_free (path);
      return;
    }
791

Jonathan Blandford's avatar
Jonathan Blandford committed
792 793
  tmp_array = g_new (int, level->array->len);
  for (i = 0; i < level->array->len; i++)
794 795 796 797 798 799 800 801
    {
      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
802 803 804
  for (i = 0; i < level->array->len; i++)
    g_array_index (level->array, SortElt, i).offset = tmp_array[i];
  g_free (tmp_array);
805

806 807
  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
808
    {
809

810 811
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
Owen Taylor's avatar
Owen Taylor committed
812
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
813

814
      if (gtk_tree_path_get_depth (path))
815
	{
816 817 818 819 820
	  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);
821
	}
822
      else
823 824 825 826
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
827 828
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
829
  gtk_tree_path_free (path);
830 831 832
}

/* Fulfill our model requirements */
833
static GtkTreeModelFlags
834 835 836 837 838
gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);

  return 0;
839 840
}

841 842 843
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
844 845
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

846
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
847 848 849

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

851
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
852 853 854 855
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
856
                                     gint          index)
857 858
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
859
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
860

861
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
862 863 864
}

static gboolean
865 866 867
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
868
{
869 870 871 872
  GtkTreeModelSort *tree_model_sort;
  gint *indices;
  SortLevel *level;
  gint depth, i;
873

874 875
  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);
876

877 878 879 880 881 882 883 884 885
  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)
886
    return FALSE;
887

888
  for (i = 0; i < depth - 1; i++)
889
    {
890
      if ((level == NULL) ||
891
	  (indices[i] >= level->array->len))
892
	return FALSE;
893

894 895 896
      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;
897 898
    }

899 900 901 902 903
  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]);
904

905
  return TRUE;
906 907 908 909
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
910
			      GtkTreeIter  *iter)