gtktreemodelsort.c 66.6 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
/* gtktreemodelsort.c
 * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
 *
 * 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.
 */

20
/* NOTE: There is a potential for confusion in this code as to whether an iter,
21 22
 * 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
23 24 25
 * s_ prefix before them (ie. s_iter, s_value, s_path);
 */

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

33
#include "gtktreemodelsort.h"
34
#include "gtktreesortable.h"
35
#include "gtktreestore.h"
36
#include "gtksignal.h"
37
#include "gtktreedatalist.h"
38
#include <string.h>
39 40

typedef struct _SortElt SortElt;
41 42 43 44
typedef struct _SortLevel SortLevel;
typedef struct _SortData SortData;
typedef struct _SortTuple SortTuple;

45 46
struct _SortElt
{
47 48 49 50 51 52 53 54 55 56 57 58 59
  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;
60 61
};

Jonathan Blandford's avatar
Jonathan Blandford committed
62 63
struct _SortData
{
64 65 66
  GtkTreeModelSort *tree_model_sort;
  GtkTreePath *parent_a;
  GtkTreePath *parent_b;
Jonathan Blandford's avatar
Jonathan Blandford committed
67 68
};

69 70 71
struct _SortTuple
{
  SortElt   *elt;
72 73
  SortLevel *level;
  SortLevel *children;
74 75
  gint       offset;  
};
76

77 78 79 80 81 82
#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);
83

84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
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);
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);
109

110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
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);
130 131

/* TreeModel interface */
132
static guint        gtk_tree_model_sort_get_flags          (GtkTreeModel          *tree_model);
133 134 135 136 137 138 139 140 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
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 */
167 168 169 170 171 172 173 174 175 176 177
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);
178 179 180 181 182
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);
183

184
/* Private functions */
185 186 187 188 189 190 191 192 193 194 195
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);
196 197 198 199 200
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,
201
							   SortLevel        *level,
202 203
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
204 205 206 207 208 209 210 211 212 213 214 215
static GtkTreePath *gtk_tree_model_sort_elt_get_path      (SortLevel        *level,
							   SortElt          *elt);
static void         get_child_iter_from_elt_no_cache      (GtkTreeModelSort *tree_model_sort,
							   GtkTreeIter      *child_iter,
							   SortLevel        *level,
							   SortElt          *elt);
static void         get_child_iter_from_elt               (GtkTreeModelSort *tree_model_sort,
							   GtkTreeIter      *child_iter,
							   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


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

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

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

255 256 257
      tree_model_sort_type = g_type_register_static (G_TYPE_OBJECT,
						     "GtkTreeModelSort",
						     &tree_model_sort_info, 0);
258
      g_type_add_interface_static (tree_model_sort_type,
259 260
                                   GTK_TYPE_TREE_MODEL,
                                   &tree_model_info);
261
      
262
      g_type_add_interface_static (tree_model_sort_type,
263 264
                                   GTK_TYPE_TREE_SORTABLE,
                                   &sortable_info);
265 266 267 268 269 270
    }

  return tree_model_sort_type;
}

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

285
  object_class = (GObjectClass *) class;
286

287
  object_class->finalize = gtk_tree_model_sort_finalize;
288 289 290 291 292
}

static void
gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
{
293
  iface->get_flags = gtk_tree_model_sort_get_flags;
294 295 296 297 298 299 300 301 302 303 304
  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;
305 306
  iface->ref_node = gtk_tree_model_sort_ref_node;
  iface->unref_node = gtk_tree_model_sort_unref_node;
307 308
}

309 310 311 312 313
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;
314
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
315 316
  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;
317 318
}

319 320 321 322 323 324 325 326
/**
 * 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.
 */
327
GtkTreeModel *
328
gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
329 330 331
{
  GtkTreeModel *retval;

332 333 334 335
  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));

336
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
337 338 339 340

  return retval;
}

341 342 343
/* GObject callbacks */
static void
gtk_tree_model_sort_finalize (GObject *object)
344
{
345
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
346

347 348
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

349
  if (tree_model_sort->root)
350
    gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
351 352 353 354 355 356

  if (tree_model_sort->sort_list)
    {
      _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
      tree_model_sort->sort_list = NULL;
    }
357 358
}

359
static void
360
gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
361 362
				 GtkTreePath  *start_s_path,
				 GtkTreeIter  *start_s_iter,
363
				 gpointer      data)
364 365
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
366
  GtkTreePath *path = NULL;
367
  GtkTreeIter iter;
368
  GtkTreeIter tmpiter;
369
  
370
  SortElt tmp;
371 372
  SortElt *elt;
  SortLevel *level;
373

374 375 376
  gboolean free_s_path = FALSE;

  gint offset, index = 0, i;
377 378

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

380
  if (!start_s_path)
381 382
    {
      free_s_path = TRUE;
383
      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
384
    }
385

386 387 388
  path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							 start_s_path);
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
389 390
    {
      if (free_s_path)
391
	gtk_tree_path_free (start_s_path);
Jonathan Blandford's avatar
Jonathan Blandford committed
392 393
      return;
    }
Jonathan Blandford's avatar
sync  
Jonathan Blandford committed
394

395
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
396 397 398 399
  
  level = iter.user_data;
  elt = iter.user_data2;
  
400
  if (level->array->len < 2 || tree_model_sort->sort_column_id == -1)
401 402
    {
      if (free_s_path)
403
	gtk_tree_path_free (start_s_path);
404
      
405 406
      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
      
407
      gtk_tree_path_free (path);
408
      
409 410 411
      return;
    }

412
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
413 414 415 416
    {
      gtk_tree_model_get_iter (tree_model_sort->child_model,
			       &tmpiter, start_s_path);
    }
417
  
418 419 420 421 422
  offset = elt->offset;

  for (i = 0; i < level->array->len; i++)
    if (elt->offset == g_array_index (level->array, SortElt, i).offset)
      index = i;
423 424
  
  memcpy (&tmp, elt, sizeof (SortElt));
425
  g_array_remove_index (level->array, index);
426
  
427 428 429
  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
430 431 432
						   &tmp.iter,
						   TRUE);
  else
433 434
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
435 436
						   &tmpiter,
						   TRUE);
437
  
438
  g_array_insert_val (level->array, index, tmp);
439 440 441 442 443 444 445 446 447 448

  gtk_tree_model_sort_increment_stamp (tree_model_sort);

  if (path)
    gtk_tree_path_free (path);

  path = gtk_tree_model_sort_elt_get_path (level, &g_array_index (level->array, SortElt, index));
  g_return_if_fail (path != NULL);

  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
449
  
450 451
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);

452 453
  gtk_tree_path_free (path);
  if (free_s_path)
454
    gtk_tree_path_free (start_s_path);
455 456
}

457 458 459 460 461
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
462
{
463 464
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  GtkTreePath *path;
465
  GtkTreeIter iter;
466 467 468 469 470 471 472 473 474 475 476
  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);
477

478
  g_return_if_fail (s_path != NULL || s_iter != NULL);
479
  
480
  if (!s_path)
481
    {
482 483
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
484
    }
485 486 487
  
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
488
  else
489
    real_s_iter = *s_iter;
490

491 492 493
  if (!tree_model_sort->root)
    {
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
494

495 496 497 498
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
      
      goto done_and_submit;
499
    }
500 501 502 503
  
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
504 505
      gint j;

506 507 508 509 510
      if (!level)
	{
	  /* level not yet build, we won't cover this signal */
	  goto done;
	}
511

512 513 514 515 516 517 518
      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;
	}
519 520 521 522 523 524 525 526 527 528
      
      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);
529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546

      if (!elt->children)
	{
	  /* FIXME: emit has_child_toggled here? like the treeview? */

	  GtkTreePath *tmppath;
	  GtkTreeIter  tmpiter;
	  
	  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);
	    }
547

548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568
	  /* not covering this signal */
	  goto done;
	}

      level = elt->children;
      parent_level = level;
      i++;
    }
  
  if (!parent_level)
    {
      goto done;
    }
  
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
  
 done_and_submit:
569 570
  path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							 s_path);
571
  
572
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
573
    return;
574

575
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
576
  
577
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
578
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
579
  gtk_tree_path_free (path);
580 581 582 583 584 585 586

 done:

  if (free_s_path)
    gtk_tree_path_free (s_path);
  
  return;
587 588 589
}

static void
590 591 592 593
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
594 595
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
596 597
  GtkTreePath *path;
  GtkTreeIter iter;
598

599
  g_return_if_fail (s_path != NULL && s_iter != NULL);
600

601 602
  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
603
    return;
604
  
605
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
606
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
607

608
  gtk_tree_path_free (path);
609 610 611
}

static void
612 613 614
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
615 616
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
617
  GtkTreePath *path = NULL;
618 619 620 621 622 623 624
  SortElt *elt;
  SortLevel *level;
  GtkTreeIter iter;
  gint offset;
  gint i;
  
  g_return_if_fail (s_path != NULL);
625

626 627
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
628 629
    return;

630 631
  g_print ("path to be deleted: %s\n", gtk_tree_path_to_string (path));
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
632

633 634 635 636 637 638 639 640
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

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

  if (level->ref_count == 0)
641
    {
642 643 644 645 646 647
      /* This will prune the level, so I can just emit the signal and not worry
       * about cleaning this level up. */
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
      gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);

      gtk_tree_path_free (path);
648 649
      return;
    }
650

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

666
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
667 668
  gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);

669
  gtk_tree_path_free (path);
670 671
}

672
static void
673 674 675 676 677
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
678
{
679 680 681 682 683 684
  int i;
  int len;
  SortElt *elt;
  SortLevel *level;
  
  GtkTreeIter  iter;
685 686
  GtkTreePath *path;

687 688
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  
689
  g_return_if_fail (s_path != NULL && s_iter != NULL);
690
  g_return_if_fail (new_order != NULL);
691

692 693 694 695 696 697
  if (!gtk_tree_path_get_indices (s_path))
    len = gtk_tree_model_iter_n_children (s_model, NULL);
  else
    len = gtk_tree_model_iter_n_children (s_model, s_iter);

  if (len < 2)
698 699 700 701 702
    {
      return;
    }

  /** get correct sort level **/
703

704
  if (!gtk_tree_path_get_indices (s_path))
705 706
    level = SORT_LEVEL (tree_model_sort->root);
  else
707
    {
708 709 710 711
      path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							     s_path);
      
      if (!path)
712 713 714
	{
	  return;
	}
715

716
      if (!gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path))
717
	{
718 719 720
	  /* no iter for me */
	  gtk_tree_path_free (path);
	  return;
721 722
	}
      
723 724
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
725 726
      gtk_tree_path_free (path);

727
      /* FIXME: is this needed ? */
728 729 730 731 732 733
      if (!s_iter)
	gtk_tree_model_get_iter (s_model, s_iter, s_path);

      if (!elt->children)
	return;

734 735 736 737 738 739 740 741
      level = elt->children;
    }

  if (!level)
    {
      /* ignore signal */
      return;
    }
742

743 744 745 746 747 748 749 750 751 752 753 754
  if (len != level->array->len)
    {
      /* length mismatch, pretty bad, shouldn't happen */
      
      return;
    }
  
  /** unsorted: set offsets, resort without reordered emission **/
  if (tree_model_sort->sort_column_id == -1)
    {
      path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							     s_path);
755

756 757 758
      if (!path)
	{
	  return;
759
	}
760
      
761
      for (i = 0; i < level->array->len; i++)
762 763 764
	{
	  g_array_index (level->array, SortElt, i).offset = new_order[i];
	  
765 766
	  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort)
	      && tree_model_sort->sort_column_id == -1)
767 768 769 770 771
	    {
	      get_child_iter_from_elt_no_cache (tree_model_sort,
						&(g_array_index (level->array, SortElt, i).iter), level, &g_array_index (level->array, SortElt, i));
	    }
	}
772

773 774 775 776 777 778
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
      
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);

      if (gtk_tree_path_get_depth (path))
779
	{
780 781 782 783 784
	  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);
785
	}
786
      else
787 788 789 790
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
791 792
      
      gtk_tree_path_free (path);
793
      
794
      return;
795 796
    }

797 798 799 800 801 802
  /** sorted: update offsets, no emission of reordered signal **/
  for (i = 0; i < level->array->len; i++)
    g_array_index (level->array, SortElt, i).offset =
      new_order[g_array_index (level->array, SortElt, i).offset];

  gtk_tree_model_sort_increment_stamp (tree_model_sort);
803

804 805 806 807 808 809 810 811 812
}

/* 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;
813 814
}

815 816 817
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
818 819
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

820
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
821 822 823

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

825
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
826 827 828 829
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
830
                                     gint          index)
831 832
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
833
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
834

835
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
836 837 838
}

static gboolean
839 840 841
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
842
{
843 844 845 846
  GtkTreeModelSort *tree_model_sort;
  gint *indices;
  SortLevel *level;
  gint depth, i;
847

848 849
  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);
850

851 852 853 854 855 856 857 858 859
  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)
860
    return FALSE;
861

862
  for (i = 0; i < depth - 1; i++)
863
    {
864 865 866
      if ((level == NULL) ||
	  (level->array->len < indices[i]))
	return FALSE;
867

868 869 870
      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;
871 872
    }

873 874 875 876 877
  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]);
878

879
  return TRUE;
880 881 882 883
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
884
			      GtkTreeIter  *iter)
885
{
886 887 888 889
  GtkTreePath *retval;
  SortLevel *level;
  SortElt *elt;

890
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
891
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
892
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
893

894 895 896 897
  retval = gtk_tree_path_new ();
  level = iter->user_data;
  elt = iter->user_data2;
  while (level != NULL)
898
    {
899 900 901 902
      gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);

      elt = level->parent_elt;
      level = level->parent_level;
903
    }
904 905

  return retval;
906 907 908 909
}

static void
gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
910 911 912
			       GtkTreeIter  *iter,
			       gint          column,
			       GValue       *value)
913
{
914
  GtkTreeIter child_iter;
915 916

  g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
917
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
918 919
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);

920
  GET_CHILD_ITER (tree_model, &child_iter, iter);
921 922
  gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
			    &child_iter, column, value);
923 924 925 926
}

static gboolean
gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
927
			       GtkTreeIter  *iter)
928
{
929
  SortLevel *level;
930 931 932
  SortElt *elt;

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
933
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
934 935
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

936 937
  level = iter->user_data;
  elt = iter->user_data2;
938

939
  if (elt - (SortElt *)level->array->data >= level->array->len - 1)
940 941 942 943
    {
      iter->stamp = 0;
      return FALSE;
    }
944
  iter->user_data2 = elt + 1;
945

946 947 948 949 950
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
951 952
				   GtkTreeIter  *iter,
				   GtkTreeIter  *parent)
953
{
954 955
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
956

957
  iter->stamp = 0;
958
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
959 960
  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
961

962 963 964 965 966 967
  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;
968

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

static gboolean
gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
992
				    GtkTreeIter  *iter)
993
{
994
  GtkTreeIter child_iter;
995 996

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
997
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
998 999
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

1000
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1001

1002
  return gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1003 1004 1005 1006 1007 1008
}

static gint
gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
				     GtkTreeIter  *iter)
{
1009
  GtkTreeIter child_iter;
1010 1011

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
1012
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
1013
  if (iter) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, 0);
1014

1015 1016
  if (iter == NULL)
    return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, NULL);
1017

1018
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1019

1020
  return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1021
}
1022 1023 1024

static gboolean
gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
1025 1026 1027
				    GtkTreeIter  *iter,
				    GtkTreeIter  *parent,
				    gint          n)
1028
{
1029
  SortLevel *level;
1030 1031
  /* We have this for the iter == parent case */
  GtkTreeIter children;
1032 1033

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1034
  if (parent) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
1035

1036 1037 1038 1039 1040 1041
  /* 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;
    }
1042

1043
  level = children.user_data;
1044
  if (n >= level->array->len)
1045
    {
1046 1047
      iter->stamp = 0;
      return FALSE;
1048 1049
    }

1050 1051
  iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
  iter->user_data = level;
1052
  iter->user_data2 = &g_array_index (level->array, SortElt, n);
1053

1054 1055 1056 1057 1058
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
1059 1060
				 GtkTreeIter  *iter,
				 GtkTreeIter  *child)
1061
{
1062
  SortLevel *level;
1063

1064
  iter->stamp = 0;
1065
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1066
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1067 1068
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == child->stamp, FALSE);

1069
  level = child->user_data;
1070

1071
  if (level->parent_level)
1072 1073
    {
      iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
1074 1075 1076
      iter->user_data = level->parent_level;
      iter->user_data2 = level->parent_elt;

1077 1078 1079 1080 1081 1082
      return TRUE;
    }
  return FALSE;
}

static void
1083
gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
1084
			      GtkTreeIter  *iter)
1085
{
1086 1087
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
1088 1089 1090 1091 1092 1093
  SortElt *elt;

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

1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118
  level = iter->user_data;
  elt = iter->user_data2;

  elt->ref_count++;
  level->ref_count++;
  if (level->ref_count == 1)
    {
      SortLevel *parent_level = level->parent_level;
      SortElt *parent_elt = level->parent_elt;
      /* We were at zero -- time to decrement the zero_ref_count val */
      do
	{
	  if (parent_elt)
	    parent_elt->zero_ref_count--;
	  else
	    tree_model_sort->zero_ref_count--;
	  
	  if (parent_level)
	    {
	      parent_elt = parent_level->parent_elt;
	      parent_level = parent_level->parent_level;
	    }
	}
      while (parent_level);
    }
1119 1120 1121
}

static void
1122
gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
1123
				GtkTreeIter  *iter)
1124
{
1125 1126
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
1127
  SortElt *elt;
1128

1129 1130 1131
  g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);
1132 1133 1134 1135

  level = iter->user_data;
  elt = iter->user_data2;

1136 1137
  g_return_if_fail (elt->ref_count > 0);

1138 1139 1140
  elt->ref_count--;
  level->ref_count--;
  if (level->ref_count == 0)
1141
    {
1142 1143
      SortLevel *parent_level = level->parent_level;
      SortElt *parent_elt = l