gtktreemodelsort.c 66.9 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
	  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);
603 604 605 606 607 608 609
	  if (tmppath)
	    {
	      gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data),
						    tmppath,
						    &tmpiter);
	      gtk_tree_path_free (tmppath);
	    }
610

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

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

620
  if (!parent_level)
621
    goto done;
622

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

629
 done_and_submit:
630 631 632
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
633

634
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
635
    return;
636

637
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
638

639
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
640
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
641
  gtk_tree_path_free (path);
642

643
 done:
644 645
  if (free_s_path)
    gtk_tree_path_free (s_path);
646

647
  return;
648 649 650
}

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

660
  g_return_if_fail (s_path != NULL && s_iter != NULL);
661

662 663
  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
664
    return;
665

666
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
667
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
668

669
  gtk_tree_path_free (path);
670 671
}

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

686
  g_return_if_fail (s_path != NULL);
687

688 689
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
690 691
    return;

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

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

698 699 700 701 702 703 704 705
  /* 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);

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

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

718 719
  gtk_tree_model_sort_increment_stamp (tree_model_sort);

720 721 722 723 724 725
  /* 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);
726

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

  gtk_tree_path_free (path);
738 739
}

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

755
  g_return_if_fail (new_order != NULL);
756

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

771 772
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
773 774

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

780 781 782
      level = elt->children;
    }

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

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

803 804
  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
805
    {
806

807 808
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
Owen Taylor's avatar
Owen Taylor committed
809
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
810

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

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

/* 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;
836 837
}

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

843
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
844 845 846

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

848
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
849 850 851 852
}

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

858
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
859 860 861
}

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

871 872
  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);
873

874 875 876 877 878 879 880 881 882
  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)
883
    return FALSE;
884

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

891 892 893
      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;
894 895
    }

896 897 898 899 900
  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]);
901

902
  return TRUE;
903 904 905 906
}

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

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

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

      elt = level->parent_elt;
      level = level->parent_level;
926
    }
927 928

  return retval;
929 930 931 932
}

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

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

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

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

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

959 960
  level = iter->user_data;
  elt = iter->user_data2;
961

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

969 970 971 972 973
  return TRUE;
}

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

980
  iter->stamp = 0;
981
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
982 983
  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
984

985 986 987 988 989 990
  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;
991

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

1010 1011 1012 1013 1014
  return TRUE;
}

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

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

1023
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1024

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

static gint
gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
				     GtkTreeIter  *iter)
{
1032
  GtkTreeIter child_iter;
1033 1034

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

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

1041
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1042

1043
  return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1044
}
1045 1046 1047

static gboolean
gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
1048 1049 1050
				    GtkTreeIter  *iter,
				    GtkTreeIter  *parent,
				    gint          n)
1051
{
1052
  SortLevel *level;
1053 1054
  /* We have this for the iter == parent case */
  GtkTreeIter children;
1055 1056

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1057
  if (parent) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
1058

1059 1060 1061 1062 1063 1064
  /* Use this instead of has_child to force us to build the level, if needed */
  if (gtk_tree_model_sort_iter_children (tree_model, &children, parent) == FALSE)
    {
      iter->stamp = 0;
      return FALSE;
    }
1065