gtktreemodelsort.c 64.5 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
/* general (object/interface init, etc) */
103 104 105 106 107
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);
108 109 110 111 112 113 114 115
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);
116

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

/* TreeModel interface */
140
static guint        gtk_tree_model_sort_get_flags          (GtkTreeModel          *tree_model);
141 142 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 173 174
static gint         gtk_tree_model_sort_get_n_columns      (GtkTreeModel          *tree_model);
static GType        gtk_tree_model_sort_get_column_type    (GtkTreeModel          *tree_model,
                                                            gint                   index);
static gboolean     gtk_tree_model_sort_get_iter           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreePath           *path);
static GtkTreePath *gtk_tree_model_sort_get_path           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static void         gtk_tree_model_sort_get_value          (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            gint                   column,
                                                            GValue                *value);
static gboolean     gtk_tree_model_sort_iter_next          (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gboolean     gtk_tree_model_sort_iter_children      (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *parent);
static gboolean     gtk_tree_model_sort_iter_has_child     (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gint         gtk_tree_model_sort_iter_n_children    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gboolean     gtk_tree_model_sort_iter_nth_child     (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *parent,
                                                            gint                   n);
static gboolean     gtk_tree_model_sort_iter_parent        (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *child);
static void         gtk_tree_model_sort_ref_node           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);

/* TreeSortable interface */
175 176 177 178 179 180 181 182 183 184 185
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);
186 187 188 189 190
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);
191

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

220
static GObjectClass *parent_class = NULL;
221

222
GType
223 224
gtk_tree_model_sort_get_type (void)
{
225
  static GType tree_model_sort_type = 0;
226

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

      static const GInterfaceInfo tree_model_info =
      {
244 245 246
        (GInterfaceInitFunc) gtk_tree_model_sort_tree_model_init,
        NULL,
        NULL
247 248
      };

249 250
      static const GInterfaceInfo sortable_info =
      {
251 252 253
        (GInterfaceInitFunc) gtk_tree_model_sort_tree_sortable_init,
        NULL,
        NULL
254 255
      };

256 257 258
      tree_model_sort_type = g_type_register_static (G_TYPE_OBJECT,
						     "GtkTreeModelSort",
						     &tree_model_sort_info, 0);
259
      g_type_add_interface_static (tree_model_sort_type,
260 261
                                   GTK_TYPE_TREE_MODEL,
                                   &tree_model_info);
262

263
      g_type_add_interface_static (tree_model_sort_type,
264 265
                                   GTK_TYPE_TREE_SORTABLE,
                                   &sortable_info);
266 267 268 269 270 271
    }

  return tree_model_sort_type;
}

static void
272 273 274 275 276 277 278 279 280 281 282
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)
283 284 285
{
  GObjectClass *object_class;

286
  object_class = (GObjectClass *) class;
287
  parent_class = g_type_class_peek_parent (class);
288

289 290 291
  object_class->set_property = gtk_tree_model_sort_set_property;
  object_class->get_property = gtk_tree_model_sort_get_property;

292
  object_class->finalize = gtk_tree_model_sort_finalize;
293 294 295 296 297 298 299 300 301

  /* 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));
302 303 304 305 306
}

static void
gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
{
307
  iface->get_flags = gtk_tree_model_sort_get_flags;
308 309 310 311 312 313 314 315 316 317 318
  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;
319 320
  iface->ref_node = gtk_tree_model_sort_ref_node;
  iface->unref_node = gtk_tree_model_sort_unref_node;
321 322
}

323 324 325 326 327
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;
328
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
329 330
  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;
331 332
}

333 334 335 336 337 338 339 340
/**
 * 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.
 */
341
GtkTreeModel *
342
gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
343 344 345
{
  GtkTreeModel *retval;

346 347 348 349
  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));

350
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
351 352 353 354

  return retval;
}

355 356 357
/* GObject callbacks */
static void
gtk_tree_model_sort_finalize (GObject *object)
358
{
359
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
360

361 362
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

363
  if (tree_model_sort->root)
364
    gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
365 366 367 368 369 370

  if (tree_model_sort->sort_list)
    {
      _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
      tree_model_sort->sort_list = NULL;
    }
371 372 373

  /* must chain up */
  parent_class->finalize (object);
374 375
}

376 377 378 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
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;
    }
}

414
static void
415
gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
416 417
				 GtkTreePath  *start_s_path,
				 GtkTreeIter  *start_s_iter,
418
				 gpointer      data)
419 420
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
421
  GtkTreePath *path = NULL;
422
  GtkTreeIter iter;
423
  GtkTreeIter tmpiter;
424

425
  SortElt tmp;
426 427
  SortElt *elt;
  SortLevel *level;
428

429 430 431
  gboolean free_s_path = FALSE;

  gint offset, index = 0, i;
432 433

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

435
  if (!start_s_path)
436 437
    {
      free_s_path = TRUE;
438
      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
439
    }
440

441 442 443
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      start_s_path,
							      FALSE);
444
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
445 446
    {
      if (free_s_path)
447
	gtk_tree_path_free (start_s_path);
Jonathan Blandford's avatar
Jonathan Blandford committed
448 449
      return;
    }
Jonathan Blandford's avatar
sync  
Jonathan Blandford committed
450

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

453 454
  level = iter.user_data;
  elt = iter.user_data2;
455

456
  if (level->array->len < 2 || tree_model_sort->sort_column_id == -1)
457 458
    {
      if (free_s_path)
459
	gtk_tree_path_free (start_s_path);
460

461
      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
462

463
      gtk_tree_path_free (path);
464

465 466 467
      return;
    }

468
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
469 470 471 472
    {
      gtk_tree_model_get_iter (tree_model_sort->child_model,
			       &tmpiter, start_s_path);
    }
473

474 475 476 477 478
  offset = elt->offset;

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

480
  memcpy (&tmp, elt, sizeof (SortElt));
481
  g_array_remove_index (level->array, index);
482

483 484 485
  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
486 487 488
						   &tmp.iter,
						   TRUE);
  else
489 490
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
491 492
						   &tmpiter,
						   TRUE);
493

494
  g_array_insert_val (level->array, index, tmp);
495

496 497 498
  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);
499

500 501
  gtk_tree_path_up (path);
  gtk_tree_path_append_index (path, index);
502

503 504
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
505

506 507
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);

508 509
  gtk_tree_path_free (path);
  if (free_s_path)
510
    gtk_tree_path_free (start_s_path);
511 512
}

513 514 515 516 517
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
518
{
519 520
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  GtkTreePath *path;
521
  GtkTreeIter iter;
522 523 524 525 526 527 528 529 530 531 532
  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);
533

534
  g_return_if_fail (s_path != NULL || s_iter != NULL);
535

536
  if (!s_path)
537
    {
538 539
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
540
    }
541

542 543
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
544
  else
545
    real_s_iter = *s_iter;
546

547 548 549
  if (!tree_model_sort->root)
    {
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
550

551 552
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
553

554
      goto done_and_submit;
555
    }
556

557 558 559
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
560 561
      gint j;

562 563 564 565 566
      if (!level)
	{
	  /* level not yet build, we won't cover this signal */
	  goto done;
	}
567

568 569 570 571 572 573 574
      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;
	}
575

576 577 578 579 580 581 582 583 584
      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);
585 586 587 588 589

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

591 592 593 594 595 596 597 598 599 600
	  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);
	    }
601

602 603 604 605 606 607 608 609
	  /* not covering this signal */
	  goto done;
	}

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

611
  if (!parent_level)
612
    goto done;
613

614 615 616 617 618
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
619

620
 done_and_submit:
621 622 623
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
624

625
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
626
    return;
627

628
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
629

630
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
631
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
632
  gtk_tree_path_free (path);
633

634
 done:
635 636
  if (free_s_path)
    gtk_tree_path_free (s_path);
637

638
  return;
639 640 641
}

static void
642 643 644 645
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
646 647
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
648 649
  GtkTreePath *path;
  GtkTreeIter iter;
650

651
  g_return_if_fail (s_path != NULL && s_iter != NULL);
652

653 654
  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
655
    return;
656

657
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
658
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
659

660
  gtk_tree_path_free (path);
661 662
}

663
/* FIXME: I still have doubts if this works */
664
static void
665 666 667
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
668 669
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
670
  GtkTreePath *path = NULL;
671 672 673 674 675
  SortElt *elt;
  SortLevel *level;
  GtkTreeIter iter;
  gint offset;
  gint i;
676

677
  g_return_if_fail (s_path != NULL);
678

679 680
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
681 682
    return;

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

685 686 687 688
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

689 690 691
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
  gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);

692 693 694
  while (elt->ref_count > 0)
    gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);

695
  if (level->ref_count == 0 && level != tree_model_sort->root)
696
    {
697 698 699 700
      /* This will prune the level, so I can just emit the signal and not worry
       * about cleaning this level up. */

      gtk_tree_path_free (path);
701 702
      return;
    }
703

704 705 706 707 708 709
  /* 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);
710

711 712 713 714 715 716
  /* 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--;
717 718
      if (elt->children)
	elt->children->parent_elt = elt;
719
    }
720 721

  gtk_tree_path_free (path);
722 723
}

724
static void
725 726 727 728 729
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
730
{
731 732
  SortElt *elt;
  SortLevel *level;
Jonathan Blandford's avatar
Jonathan Blandford committed
733 734
  GtkTreeIter iter;
  gint *tmp_array;
735
  int i, j;
736
  GtkTreePath *path;
737
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
738

739
  g_return_if_fail (new_order != NULL);
740

Jonathan Blandford's avatar
Jonathan Blandford committed
741
  if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
742
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
743 744
      if (tree_model_sort->root == NULL)
	return;
Jonathan Blandford's avatar
Jonathan Blandford committed
745
      path = gtk_tree_path_new ();
Jonathan Blandford's avatar
Jonathan Blandford committed
746
      level = SORT_LEVEL (tree_model_sort->root);
747 748
    }
  else
749
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
750 751 752 753
      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);
754

755 756
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
757 758

      if (!elt->children)
Jonathan Blandford's avatar
Jonathan Blandford committed
759 760 761 762
	{
	  gtk_tree_path_free (path);
	  return;
	}
763

764 765 766
      level = elt->children;
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
767
  if (level->array->len < 2)
768
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
769 770 771
      gtk_tree_path_free (path);
      return;
    }
772

Jonathan Blandford's avatar
Jonathan Blandford committed
773 774
  tmp_array = g_new (int, level->array->len);
  for (i = 0; i < level->array->len; i++)
775 776 777 778 779 780 781 782
    {
      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
783 784 785
  for (i = 0; i < level->array->len; i++)
    g_array_index (level->array, SortElt, i).offset = tmp_array[i];
  g_free (tmp_array);
786

Jonathan Blandford's avatar
Jonathan Blandford committed
787 788 789
  if (tree_model_sort->sort_column_id == -1 &&
      tree_model_sort->default_sort_func == (GtkTreeIterCompareFunc) 0x1)
    {
790

791 792
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
Jonathan Blandford's avatar
Jonathan Blandford committed
793
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
794

795
      if (gtk_tree_path_get_depth (path))
796
	{
797 798 799 800 801
	  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);
802
	}
803
      else
804 805 806 807
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
808 809
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
810
  gtk_tree_path_free (path);
811 812 813 814 815 816 817 818 819
}

/* 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;
820 821
}

822 823 824
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
825 826
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

827
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
828 829 830

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

832
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
833 834 835 836
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
837
                                     gint          index)
838 839
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
840
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
841

842
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
843 844 845
}

static gboolean
846 847 848
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
849
{
850 851 852 853
  GtkTreeModelSort *tree_model_sort;
  gint *indices;
  SortLevel *level;
  gint depth, i;
854

855 856
  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);
857

858 859 860 861 862 863 864 865 866
  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)
867
    return FALSE;
868

869
  for (i = 0; i < depth - 1; i++)
870
    {
871 872 873
      if ((level == NULL) ||
	  (level->array->len < indices[i]))
	return FALSE;
874

875 876 877
      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;
878 879
    }

880 881 882 883 884
  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]);
885

886
  return TRUE;
887 888 889 890
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
891
			      GtkTreeIter  *iter)
892
{
893 894 895 896
  GtkTreePath *retval;
  SortLevel *level;
  SortElt *elt;

897
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
898
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
899
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
900

901 902 903 904
  retval = gtk_tree_path_new ();
  level = iter->user_data;
  elt = iter->user_data2;
  while (level != NULL)
905
    {
906 907 908 909
      gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);

      elt = level->parent_elt;
      level = level->parent_level;
910
    }
911 912

  return retval;
913 914 915 916
}

static void
gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
917 918 919
			       GtkTreeIter  *iter,
			       gint          column,
			       GValue       *value)
920
{
921
  GtkTreeIter child_iter;
922 923

  g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
924
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
925 926
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);

927
  GET_CHILD_ITER (tree_model, &child_iter, iter);
928 929
  gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
			    &child_iter, column, value);
930 931 932 933
}

static gboolean
gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
934
			       GtkTreeIter  *iter)
935
{
936
  SortLevel *level;
937 938 939
  SortElt *elt;

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

943 944
  level = iter->user_data;
  elt = iter->user_data2;
945

946
  if (elt - (SortElt *)level->array->data >= level->array->len - 1)
947 948 949 950
    {
      iter->stamp = 0;
      return FALSE;
    }
951
  iter->user_data2 = elt + 1;
952

953 954 955 956 957
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
958 959
				   GtkTreeIter  *iter,
				   GtkTreeIter  *parent)
960
{
961 962
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
963

964
  iter->stamp = 0;
965
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
966 967
  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
968

969 970 971 972 973 974
  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;
975

976 977 978 979 980
      level = tree_model_sort->root;
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = level;
      iter->user_data2 = level->array->data;
    }
981
  else
982
    {
983 984 985 986 987
      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)
988
	return FALSE;
989 990 991
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = ((SortElt *)parent->user_data2)->children;
      iter->user_data2 = ((SortLevel *)iter->user_data)->array->data;
992
    }
993

994 995 996 997 998
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
999
				    GtkTreeIter  *iter)
1000
{
1001
  GtkTreeIter child_iter;
1002 1003

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1004
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1005 1006
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

1007
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1008

1009
  return gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1010 1011 1012 1013 1014 1015
}

static gint
gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
				     GtkTreeIter  *iter)
{
1016
  GtkTreeIter child_iter;
1017 1018

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
1019
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
1020
  if (iter) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, 0);
1021

1022 1023
  if (iter == NULL)
    return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, NULL);
1024

1025
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1026

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

static gboolean
gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
1032 1033 1034
				    GtkTreeIter  *iter,
				    GtkTreeIter  *parent,
				    gint          n)
1035
{
1036
  SortLevel *level;
1037 1038
  /* We have this for the iter == parent case */
  GtkTreeIter children;
1039 1040

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1041
  if (parent) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
1042

1043 1044 1045 1046 1047 1048
  /* 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;
    }
1049

1050
  level = children.user_data;
1051
  if (n >= level->array->len)
1052
    {
1053 1054
      iter->stamp = 0;
      return FALSE;
1055 1056
    }

1057 1058
  iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
  iter->user_data = level;
1059
  iter->user_data2 = &g_array_index (level->array, SortElt, n);
1060

1061 1062 1063 1064 1065
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
1066 1067
				 GtkTreeIter  *iter,
				 GtkTreeIter  *child)
1068
{
1069
  SortLevel *level;