gtktreemodelsort.c 66.2 KB
Newer Older
1
/* gtktreemodelsort.c
2
 * Copyright (C) 2000,2001  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
3
 * Copyright (C) 2001,2002  Kristian Rietveld <kris@gtk.org>
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

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

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

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

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

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

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

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

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

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

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



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

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

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

104
/* general (object/interface init, etc) */
105 106 107 108 109
static void gtk_tree_model_sort_init                  (GtkTreeModelSort      *tree_model_sort);
static void gtk_tree_model_sort_class_init            (GtkTreeModelSortClass *tree_model_sort_class);
static void gtk_tree_model_sort_tree_model_init       (GtkTreeModelIface     *iface);
static void gtk_tree_model_sort_tree_sortable_init    (GtkTreeSortableIface  *iface);
static void gtk_tree_model_sort_finalize              (GObject               *object);
110 111 112 113 114 115 116 117
static void gtk_tree_model_sort_set_property          (GObject               *object,
						       guint                  prop_id,
						       const GValue          *value,
						       GParamSpec            *pspec);
static void gtk_tree_model_sort_get_property          (GObject               *object,
						       guint                  prop_id,
						       GValue                *value,
						       GParamSpec            *pspec);
118

119
/* our signal handlers */
120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
static void gtk_tree_model_sort_row_changed           (GtkTreeModel          *model,
						       GtkTreePath           *start_path,
						       GtkTreeIter           *start_iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_inserted          (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       GtkTreeIter           *iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       GtkTreeIter           *iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_deleted           (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       gpointer               data);
static void gtk_tree_model_sort_rows_reordered        (GtkTreeModel          *s_model,
						       GtkTreePath           *s_path,
						       GtkTreeIter           *s_iter,
						       gint                  *new_order,
						       gpointer               data);
140 141

/* TreeModel interface */
142
static guint        gtk_tree_model_sort_get_flags          (GtkTreeModel          *tree_model);
143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
static gint         gtk_tree_model_sort_get_n_columns      (GtkTreeModel          *tree_model);
static GType        gtk_tree_model_sort_get_column_type    (GtkTreeModel          *tree_model,
                                                            gint                   index);
static gboolean     gtk_tree_model_sort_get_iter           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreePath           *path);
static GtkTreePath *gtk_tree_model_sort_get_path           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static void         gtk_tree_model_sort_get_value          (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            gint                   column,
                                                            GValue                *value);
static gboolean     gtk_tree_model_sort_iter_next          (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gboolean     gtk_tree_model_sort_iter_children      (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *parent);
static gboolean     gtk_tree_model_sort_iter_has_child     (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gint         gtk_tree_model_sort_iter_n_children    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gboolean     gtk_tree_model_sort_iter_nth_child     (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *parent,
                                                            gint                   n);
static gboolean     gtk_tree_model_sort_iter_parent        (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *child);
static void         gtk_tree_model_sort_ref_node           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
173 174 175
static void         gtk_tree_model_sort_real_unref_node    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
							    gboolean               propagate_unref);
176 177 178 179
static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);

/* TreeSortable interface */
180 181 182 183 184 185 186 187 188 189 190
static gboolean     gtk_tree_model_sort_get_sort_column_id    (GtkTreeSortable        *sortable,
							       gint                   *sort_column_id,
							       GtkSortType            *order);
static void         gtk_tree_model_sort_set_sort_column_id    (GtkTreeSortable        *sortable,
							       gint                    sort_column_id,
							       GtkSortType        order);
static void         gtk_tree_model_sort_set_sort_func         (GtkTreeSortable        *sortable,
							       gint                    sort_column_id,
							       GtkTreeIterCompareFunc  func,
							       gpointer                data,
							       GtkDestroyNotify        destroy);
191 192 193 194 195
static void         gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
							       GtkTreeIterCompareFunc  func,
							       gpointer                data,
							       GtkDestroyNotify        destroy);
static gboolean     gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable     *sortable);
196

197
/* Private functions (sort funcs, level handling and other utils) */
198 199 200 201 202 203 204 205 206 207 208
static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *parent_level,
							   SortElt          *parent_elt);
static void         gtk_tree_model_sort_free_level        (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *sort_level);
static void         gtk_tree_model_sort_increment_stamp   (GtkTreeModelSort *tree_model_sort);
static void         gtk_tree_model_sort_sort_level        (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *level,
							   gboolean          recurse,
							   gboolean          emit_reordered);
static void         gtk_tree_model_sort_sort              (GtkTreeModelSort *tree_model_sort);
209 210 211 212 213
static gint         gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *level,
							   GtkTreeIter      *iter,
							   gboolean          skip_sort_elt);
static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
214
							   SortLevel        *level,
215 216
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
217 218 219 220
static GtkTreePath *gtk_tree_model_sort_elt_get_path      (SortLevel        *level,
							   SortElt          *elt);
static void         gtk_tree_model_sort_set_model         (GtkTreeModelSort *tree_model_sort,
							   GtkTreeModel     *child_model);
221 222 223
static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
									 GtkTreePath      *child_path,
									 gboolean          build_levels);
224

225
static GObjectClass *parent_class = NULL;
226

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

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

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

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

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

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

  return tree_model_sort_type;
}

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

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

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

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

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

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

static void
gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
{
312
  iface->get_flags = gtk_tree_model_sort_get_flags;
313 314 315 316 317 318 319 320 321 322 323
  iface->get_n_columns = gtk_tree_model_sort_get_n_columns;
  iface->get_column_type = gtk_tree_model_sort_get_column_type;
  iface->get_iter = gtk_tree_model_sort_get_iter;
  iface->get_path = gtk_tree_model_sort_get_path;
  iface->get_value = gtk_tree_model_sort_get_value;
  iface->iter_next = gtk_tree_model_sort_iter_next;
  iface->iter_children = gtk_tree_model_sort_iter_children;
  iface->iter_has_child = gtk_tree_model_sort_iter_has_child;
  iface->iter_n_children = gtk_tree_model_sort_iter_n_children;
  iface->iter_nth_child = gtk_tree_model_sort_iter_nth_child;
  iface->iter_parent = gtk_tree_model_sort_iter_parent;
324 325
  iface->ref_node = gtk_tree_model_sort_ref_node;
  iface->unref_node = gtk_tree_model_sort_unref_node;
326 327
}

328 329 330 331 332
static void
gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface *iface)
{
  iface->get_sort_column_id = gtk_tree_model_sort_get_sort_column_id;
  iface->set_sort_column_id = gtk_tree_model_sort_set_sort_column_id;
333
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
334 335
  iface->set_default_sort_func = gtk_tree_model_sort_set_default_sort_func;
  iface->has_default_sort_func = gtk_tree_model_sort_has_default_sort_func;
336 337
}

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

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

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

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

  return retval;
}

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

366 367
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

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

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

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

381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418
static void
gtk_tree_model_sort_set_property (GObject      *object,
				  guint         prop_id,
				  const GValue *value,
				  GParamSpec   *pspec)
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);

  switch (prop_id)
    {
    case PROP_MODEL:
      gtk_tree_model_sort_set_model (tree_model_sort, g_value_get_object (value));
      break;
    default:
      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
      break;
    }
}

static void
gtk_tree_model_sort_get_property (GObject    *object,
				  guint       prop_id,
				  GValue     *value,
				  GParamSpec *pspec)
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);

  switch (prop_id)
    {
    case PROP_MODEL:
      g_value_set_object (value, gtk_tree_model_sort_get_model(tree_model_sort));
      break;
    default:
      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
      break;
    }
}

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

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

434 435 436
  gboolean free_s_path = FALSE;

  gint offset, index = 0, i;
437 438

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

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

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

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

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

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

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

470
      gtk_tree_path_free (path);
471

472 473 474
      return;
    }

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

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

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

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

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

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

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

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

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

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

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

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

  gint i = 0;

  gboolean free_s_path = FALSE;

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

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

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

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

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

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

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

561
      goto done_and_submit;
562
    }
563

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

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

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

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

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

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

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

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

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

618
  if (!parent_level)
619
    goto done;
620

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

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

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

635
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
636

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

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

645
  return;
646 647 648
}

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

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

660 661
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
Jonathan Blandford's avatar
Jonathan Blandford committed
662
    return;
663

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

667
  gtk_tree_path_free (path);
668 669
}

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

684
  g_return_if_fail (s_path != NULL);
685

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

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

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

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

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

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

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

716 717
  gtk_tree_model_sort_increment_stamp (tree_model_sort);

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

  g_array_remove_index (level->array, i);
724

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

  gtk_tree_path_free (path);
736 737
}

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

753
  g_return_if_fail (new_order != NULL);
754

Jonathan Blandford's avatar
Jonathan Blandford committed
755
  if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
756
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
757 758
      if (tree_model_sort->root == NULL)
	return;
Jonathan Blandford's avatar
Jonathan Blandford committed
759
      path = gtk_tree_path_new ();
Jonathan Blandford's avatar
Jonathan Blandford committed
760
      level = SORT_LEVEL (tree_model_sort->root);
761 762
    }
  else
763
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
764 765 766 767
      path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
      if (path == NULL)
	return;
      gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
768

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

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

778 779 780
      level = elt->children;
    }

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

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

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

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

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

809
      if (gtk_tree_path_get_depth (path))
810
	{
811 812 813 814 815
	  gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
				   &iter,
				   path);
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, &iter, new_order);
816
	}
817
      else
818 819 820 821
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
822 823
    }

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

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

  return 0;
834 835
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

900
  return TRUE;
901 902 903 904
}

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

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

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

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

  return retval;
927 928 929 930
}

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

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

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

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

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

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

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

967 968 969 970 971
  return TRUE;
}

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