gtktreemodelsort.c 65.7 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 696
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

  while (elt->ref_count > 0)
697
    gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
698

699
  if (level->ref_count == 0 && level != tree_model_sort->root)
700
    {
701 702
      /* This will prune the level, so I can just emit the signal and not worry
       * about cleaning this level up. */
703 704
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
      gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
705
      gtk_tree_path_free (path);
706 707
      return;
    }
708

709 710 711
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
  gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);

712 713 714 715 716 717
  /* 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);
718

719 720 721 722 723 724
  /* 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--;
725 726
      if (elt->children)
	elt->children->parent_elt = elt;
727
    }
728 729

  gtk_tree_path_free (path);
730 731
}

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

747
  g_return_if_fail (new_order != NULL);
748

Jonathan Blandford's avatar
Jonathan Blandford committed
749
  if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
750
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
751 752
      if (tree_model_sort->root == NULL)
	return;
Jonathan Blandford's avatar
Jonathan Blandford committed
753
      path = gtk_tree_path_new ();
Jonathan Blandford's avatar
Jonathan Blandford committed
754
      level = SORT_LEVEL (tree_model_sort->root);
755 756
    }
  else
757
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
758 759 760 761
      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);
762

763 764
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
765 766

      if (!elt->children)
Jonathan Blandford's avatar
Jonathan Blandford committed
767 768 769 770
	{
	  gtk_tree_path_free (path);
	  return;
	}
771

772 773 774
      level = elt->children;
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
775
  if (level->array->len < 2)
776
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
777 778 779
      gtk_tree_path_free (path);
      return;
    }
780

Jonathan Blandford's avatar
Jonathan Blandford committed
781 782
  tmp_array = g_new (int, level->array->len);
  for (i = 0; i < level->array->len; i++)
783 784 785 786 787 788 789 790
    {
      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
791 792 793
  for (i = 0; i < level->array->len; i++)
    g_array_index (level->array, SortElt, i).offset = tmp_array[i];
  g_free (tmp_array);
794

795 796
  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
797
    {
798

799 800
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
Jonathan Blandford's avatar
Jonathan Blandford committed
801
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
802

803
      if (gtk_tree_path_get_depth (path))
804
	{
805 806 807 808 809
	  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);
810
	}
811
      else
812 813 814 815
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
816 817
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
818
  gtk_tree_path_free (path);
819 820 821 822 823 824 825 826 827
}

/* 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;
828 829
}

830 831 832
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
833 834
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

835
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
836 837 838

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

840
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
841 842 843 844
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
845
                                     gint          index)
846 847
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
848
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
849

850
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
851 852 853
}

static gboolean
854 855 856
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
857
{
858 859 860 861
  GtkTreeModelSort *tree_model_sort;
  gint *indices;
  SortLevel *level;
  gint depth, i;
862

863 864
  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);
865

866 867 868 869 870 871 872 873 874
  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)
875
    return FALSE;
876

877
  for (i = 0; i < depth - 1; i++)
878
    {
879 880 881
      if ((level == NULL) ||
	  (level->array->len < indices[i]))
	return FALSE;
882

883 884 885
      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;
886 887
    }

888 889 890 891 892
  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]);
893

894
  return TRUE;
895 896 897 898
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
899
			      GtkTreeIter  *iter)
900
{
901 902 903 904
  GtkTreePath *retval;
  SortLevel *level;
  SortElt *elt;

905
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
906
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
907
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
908

909 910 911 912
  retval = gtk_tree_path_new ();
  level = iter->user_data;
  elt = iter->user_data2;
  while (level != NULL)
913
    {
914 915 916 917
      gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);

      elt = level->parent_elt;
      level = level->parent_level;
918
    }
919 920

  return retval;
921 922 923 924
}

static void
gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
925 926 927
			       GtkTreeIter  *iter,
			       gint          column,
			       GValue       *value)
928
{
929
  GtkTreeIter child_iter;
930 931

  g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
932
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
933 934
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);

935
  GET_CHILD_ITER (tree_model, &child_iter, iter);
936 937
  gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
			    &child_iter, column, value);
938 939 940 941
}

static gboolean
gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
942
			       GtkTreeIter  *iter)
943
{
944
  SortLevel *level;
945 946 947
  SortElt *elt;

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
948
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
949 950
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

951 952
  level = iter->user_data;
  elt = iter->user_data2;
953

954
  if (elt - (SortElt *)level->array->data >= level->array->len - 1)
955 956 957 958
    {
      iter->stamp = 0;
      return FALSE;
    }
959
  iter->user_data2 = elt + 1;
960

961 962 963 964 965
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
966 967
				   GtkTreeIter  *iter,
				   GtkTreeIter  *parent)
968
{
969 970
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
971

972
  iter->stamp = 0;