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

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

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

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

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

42
#include "gtktreemodelsort.h"
43
#include "gtktreesortable.h"
44
#include "gtktreestore.h"
45
#include "gtktreedatalist.h"
46
#include "gtkintl.h"
47 48

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

227
static GObjectClass *parent_class = NULL;
228

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

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

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

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

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

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

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

  return tree_model_sort_type;
}

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

static void
gtk_tree_model_sort_class_init (GtkTreeModelSortClass *class)
291 292 293
{
  GObjectClass *object_class;

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

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

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

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

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

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

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

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

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

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

  return retval;
}

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

369 370
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

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

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

  /* must chain up */
  parent_class->finalize (object);
382 383
}

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

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

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

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

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

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

437 438
  gboolean free_s_path = FALSE;

Kristian Rietveld's avatar
Kristian Rietveld committed
439
  gint index = 0, old_index, i;
440 441

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

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

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

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

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

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

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

473
      gtk_tree_path_free (path);
474

475 476 477
      return;
    }

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

Kristian Rietveld's avatar
Kristian Rietveld committed
484
  old_index = elt - SORT_ELT (level->array->data);
485

486
  memcpy (&tmp, elt, sizeof (SortElt));
487

488 489 490
  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
491
						   &tmp.iter,
Kristian Rietveld's avatar
Kristian Rietveld committed
492
						   old_index);
493
  else
494 495
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
496
						   &tmpiter,
Kristian Rietveld's avatar
Kristian Rietveld committed
497
						   old_index);
498

499 500 501 502 503 504 505 506 507 508 509 510 511 512
  if (index < old_index)
    {
      g_memmove (level->array->data + ((index + 1)*sizeof (SortElt)),
		 level->array->data + ((index)*sizeof (SortElt)),
		 (old_index - index)* sizeof(SortElt));
    }
  else if (index > old_index)
    {
      g_memmove (level->array->data + ((old_index)*sizeof (SortElt)),
		 level->array->data + ((old_index + 1)*sizeof (SortElt)),
		 (index - old_index)* sizeof(SortElt));
    }
  memcpy (level->array->data + ((index)*sizeof (SortElt)),
	  &tmp, sizeof (SortElt));
513

514 515 516
  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);
517

518 519
  gtk_tree_path_up (path);
  gtk_tree_path_append_index (path, index);
520

521
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
522

523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581
  /* if the item moved, then emit rows_reordered */
  if (old_index != index)
    {
      gint *new_order;
      gint j;

      GtkTreePath *tmppath;

      new_order = g_new (gint, level->array->len);

      for (j = 0; j < level->array->len; j++)
        {
	  if (index > old_index)
	    {
	      if (j == index)
		new_order[j] = old_index;
	      else if (j >= old_index && j < index)
		new_order[j] = j + 1;
	      else
		new_order[j] = j;
	    }
	  else if (index < old_index)
	    {
	      if (j == index)
		new_order[j] = old_index;
	      else if (j > index && j <= old_index)
		new_order[j] = j - 1;
	      else
		new_order[j] = j;
	    }
	  /* else? shouldn't really happen */
	}

      if (level->parent_elt)
        {
	  iter.stamp = tree_model_sort->stamp;
	  iter.user_data = level->parent_level;
	  iter.user_data2 = level->parent_elt;

	  tmppath = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort), &iter);

	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
	                                 tmppath, &iter, new_order);
	}
      else
        {
	  /* toplevel */
	  tmppath = gtk_tree_path_new ();

          gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), tmppath,
	                                 NULL, new_order);
	}

      gtk_tree_path_free (tmppath);
      g_free (new_order);
    }

  /* emit row_changed signal (at new location) */
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
582 583
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);

584 585
  gtk_tree_path_free (path);
  if (free_s_path)
586
    gtk_tree_path_free (start_s_path);
587 588
}

589 590 591 592 593
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
594
{
595 596
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  GtkTreePath *path;
597
  GtkTreeIter iter;
598 599 600 601 602 603 604 605 606 607 608
  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);
609

610
  g_return_if_fail (s_path != NULL || s_iter != NULL);
611

612
  if (!s_path)
613
    {
614 615
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
616
    }
617

618 619
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
620
  else
621
    real_s_iter = *s_iter;
622

623 624 625
  if (!tree_model_sort->root)
    {
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
626

627 628
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
629

630
      goto done_and_submit;
631
    }
632

633 634 635
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
636 637
      gint j;

638 639 640 641 642
      if (!level)
	{
	  /* level not yet build, we won't cover this signal */
	  goto done;
	}
643

644 645 646 647 648 649 650
      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;
	}
651

652 653 654 655 656 657 658 659 660
      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);
661 662 663 664 665

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

667 668 669 670 671
	  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);
672 673 674 675 676 677 678
	  if (tmppath)
	    {
	      gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data),
						    tmppath,
						    &tmpiter);
	      gtk_tree_path_free (tmppath);
	    }
679

680 681 682 683 684 685 686 687
	  /* not covering this signal */
	  goto done;
	}

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

689
  if (!parent_level)
690
    goto done;
691

692 693 694 695 696
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
697

698
 done_and_submit:
699 700 701
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
702

703
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
704
    return;
705

706
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
707

708
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
709
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
710
  gtk_tree_path_free (path);
711

712
 done:
713 714
  if (free_s_path)
    gtk_tree_path_free (s_path);
715

716
  return;
717 718 719
}

static void
720 721 722 723
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
724 725
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
726 727
  GtkTreePath *path;
  GtkTreeIter iter;
728

729
  g_return_if_fail (s_path != NULL && s_iter != NULL);
730

731 732
  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
733
    return;
734

735
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
736
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
737

738
  gtk_tree_path_free (path);
739 740
}

741
/* FIXME: I still have doubts if this works */
742
static void
743 744 745
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
746 747
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
748
  GtkTreePath *path = NULL;
749 750 751 752 753
  SortElt *elt;
  SortLevel *level;
  GtkTreeIter iter;
  gint offset;
  gint i;
754

755
  g_return_if_fail (s_path != NULL);
756

757 758
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
759 760
    return;

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

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

767 768 769 770 771 772 773 774
  /* 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);

775
  while (elt->ref_count > 0)
776
    gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
777

778
  if (level->ref_count == 0 && level != tree_model_sort->root)
779
    {
780 781
      /* This will prune the level, so I can just emit the signal and not worry
       * about cleaning this level up. */
782
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
783
      gtk_tree_path_free (path);
784 785
      return;
    }
786

787 788
  gtk_tree_model_sort_increment_stamp (tree_model_sort);

789 790 791 792 793 794
  /* 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);
795

796 797 798 799 800 801
  /* 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--;
802 803
      if (elt->children)
	elt->children->parent_elt = elt;
804
    }
805 806

  gtk_tree_path_free (path);
807 808
}

809
static void
810 811 812 813 814
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
815
{
816 817
  SortElt *elt;
  SortLevel *level;
Jonathan Blandford's avatar
Jonathan Blandford committed
818 819
  GtkTreeIter iter;
  gint *tmp_array;
820
  int i, j;
821
  GtkTreePath *path;
822
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
823

824
  g_return_if_fail (new_order != NULL);
825

Jonathan Blandford's avatar
Jonathan Blandford committed
826
  if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
827
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
828 829
      if (tree_model_sort->root == NULL)
	return;
Jonathan Blandford's avatar
Jonathan Blandford committed
830
      path = gtk_tree_path_new ();
Jonathan Blandford's avatar
Jonathan Blandford committed
831
      level = SORT_LEVEL (tree_model_sort->root);
832 833
    }
  else
834
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
835 836 837 838
      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);
839

840 841
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
842 843

      if (!elt->children)
Jonathan Blandford's avatar
Jonathan Blandford committed
844 845 846 847
	{
	  gtk_tree_path_free (path);
	  return;
	}
848

849 850 851
      level = elt->children;
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
852
  if (level->array->len < 2)
853
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
854 855 856
      gtk_tree_path_free (path);
      return;
    }
857

Jonathan Blandford's avatar
Jonathan Blandford committed
858 859
  tmp_array = g_new (int, level->array->len);
  for (i = 0; i < level->array->len; i++)
860 861 862 863 864 865 866 867
    {
      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
868 869 870
  for (i = 0; i < level->array->len; i++)
    g_array_index (level->array, SortElt, i).offset = tmp_array[i];
  g_free (tmp_array);
871

872 873
  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
874
    {
875

876 877
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
Owen Taylor's avatar
Owen Taylor committed
878
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
879

880
      if (gtk_tree_path_get_depth (path))
881
	{
882 883 884 885 886
	  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);
887
	}
888
      else
889 890 891 892
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
893 894
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
895
  gtk_tree_path_free (path);
896 897 898
}

/* Fulfill our model requirements */
899
static GtkTreeModelFlags
900 901
gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
{
902 903
  GtkTreeModelFlags flags;

904
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
905 906 907 908 909 910
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);

  flags = gtk_tree_model_get_flags (GTK_TREE_MODEL_SORT (tree_model)->child_model);

  if ((flags & GTK_TREE_MODEL_LIST_ONLY) == GTK_TREE_MODEL_LIST_ONLY)
    return GTK_TREE_MODEL_LIST_ONLY;
911 912

  return 0;
913 914
}

915 916 917
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
918 919
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

920
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
921 922 923

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

925
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
926 927 928 929
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
930
                                     gint          index)
931 932
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
933
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
934

935
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
936 937 938
}

static gboolean
939 940 941
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
942
{
943 944 945 946
  GtkTreeModelSort *tree_model_sort;
  gint *indices;
  SortLevel *level;
  gint depth, i;
947

948 949
  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);
950

951 952 953 954 955 956 957 958 959
  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)
960
    return FALSE;
961

962
  for (i = 0; i < depth - 1; i++)
963
    {
964
      if ((level == NULL) ||
965
	  (indices[i] >= level->array->len))
966
	return FALSE;
967

968 969 970
      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;
971 972
    }

973 974 975 976 977 978
  if (!level || indices[i] >= level->array->len)
    {
      iter->stamp = 0;
      return FALSE;
    }

979 980 981
  iter->stamp = tree_model_sort->stamp;
  iter->user_data = level;
  iter->user_data2 = &g_array_index (level->array, SortElt, indices[depth - 1]);
982

983
  return TRUE;
984 985 986 987
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
988
			      GtkTreeIter  *iter)
989
{
990 991 992 993
  GtkTreePath *retval;
  SortLevel *level;
  SortElt *elt;

994
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
995
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
996
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
997

998 999 1000 1001
  retval = gtk_tree_path_new ();
  level = iter->user_data;
  elt = iter->user_data2;
  while (level != NULL)
1002
    {
1003 1004 1005 1006
      gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);

      elt = level->parent_elt;
      level = level->parent_level;
1007
    }
1008 1009

  return retval;
1010 1011 1012 1013
}

static void
gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
1014 1015 1016
			       GtkTreeIter  *iter,
			       gint          column,
			       GValue       *value)
1017
{
1018
  GtkTreeIter child_iter;
1019 1020

  g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
1021
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
1022 1023
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);

1024
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1025 1026
  gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
			    &child_iter, column, value);
1027 1028 1029 1030
}

static gboolean
gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
1031
			       GtkTreeIter  *iter)
1032
{
1033
  SortLevel *level;
1034 1035 1036
  SortElt *elt;

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1037
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1038 1039
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

1040 1041
  level = iter->user_data;
  elt = iter->user_data2;
1042

1043
  if (elt - (SortElt *)level->array->data >= level->array->len - 1)
1044 1045 1046 1047
    {
      iter->stamp = 0;
      return FALSE;
    }
1048
  iter->user_data2 = elt + 1;
1049

1050 1051 1052 1053 1054
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
1055 1056
				   GtkTreeIter  *iter,
				   GtkTreeIter  *parent)
1057
{
1058 1059
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
1060

1061
  iter->stamp = 0;
1062
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1063 1064
  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
1065

1066 1067 1068 1069 1070 1071
  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;
1072

1073 1074 1075 1076 1077
      level = tree_model_sort->root;
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = level;
      iter->user_data2 = level->array->data;
    }
1078
  else
1079
    {
1080 1081 1082 1083 1084
      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)
1085
	return FALSE;
1086 1087 1088
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = ((SortElt *)parent->user_data2)->children;
      iter->user_data2 = ((SortLevel *)iter->user_data)->array->data;
1089
    }
1090

1091 1092 1093 1094 1095
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
1096
				    GtkTreeIter  *iter)
1097
{
1098
  GtkTreeIter child_iter;
1099 1100

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1101
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1102 1103
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

1104
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1105