gtktreemodelsort.c 67.2 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 83 84
#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) ((((GtkTreeModelSort *)tree_model_sort)->child_flags&GTK_TREE_MODEL_ITERS_PERSIST)?((*child_iter)=SORT_ELT(sort_iter->user_data)->iter):gtk_tree_model_sort_convert_iter_to_child_iter (GTK_TREE_MODEL_SORT(tree_model_sort),sort_iter,child_iter))

#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);
85

86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
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);
111
static void gtk_tree_model_sort_destroy               (GtkObject             *gobject);
112

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

/* TreeModel interface */
135
static guint        gtk_tree_model_sort_get_flags          (GtkTreeModel          *tree_model);
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 167 168 169 170 171 172 173 174 175 176 177 178 179 180
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 */
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);
181 182 183 184 185
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);
186

187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218
/* Private functions */
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);

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,
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
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);
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
{
  GObjectClass *object_class;
284
  GtkObjectClass *gobject_class;
285

286 287
  object_class = (GObjectClass *) class;
  gobject_class = (GtkObjectClass *) class;
288

289
  object_class->finalize = gtk_tree_model_sort_finalize;
290
  gobject_class->destroy = gtk_tree_model_sort_destroy;
291 292 293 294 295
}

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

312 313 314 315 316
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;
317
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
318 319
  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;
320 321
}

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

335 336 337 338
  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));

339
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
340 341 342 343

  return retval;
}

344 345 346
/* GObject callbacks */
static void
gtk_tree_model_sort_finalize (GObject *object)
347
{
348
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
349

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

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

360
/* GtkObject callbacks */
361
static void
362
gtk_tree_model_sort_destroy (GtkObject *gobject)
363
{
364
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) gobject;
365

366
  if (tree_model_sort->child_model)
367
    gtk_tree_model_sort_set_model (tree_model_sort, NULL);
368 369 370
}

static void
371
gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
372 373
				 GtkTreePath  *start_s_path,
				 GtkTreeIter  *start_s_iter,
374
				 gpointer      data)
375 376
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
377 378
  GtkTreePath *path;
  GtkTreeIter iter;
379
  GtkTreeIter tmpiter;
380
  
381
  SortElt tmp;
382 383
  SortElt *elt;
  SortLevel *level;
384

385 386 387 388 389
  gboolean free_s_path;

  gint offset, index, i;
  
  g_return_if_fail (start_s_path != NULL || start_s_iter != NULL);
390

391
  if (!start_s_path)
392 393
    {
      free_s_path = TRUE;
394
      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
395
    }
396

397 398 399
  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
400 401
    {
      if (free_s_path)
402
	gtk_tree_path_free (start_s_path);
Jonathan Blandford's avatar
Jonathan Blandford committed
403 404
      return;
    }
Jonathan Blandford's avatar
sync  
Jonathan Blandford committed
405

406
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
407 408 409 410 411
  
  level = iter.user_data;
  elt = iter.user_data2;
  
  if (level->array->len < 2)
412 413
    {
      if (free_s_path)
414
	gtk_tree_path_free (start_s_path);
415 416 417

      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
      
418
      gtk_tree_path_free (path);
419
      
420 421 422
      return;
    }

423 424
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
    get_child_iter_from_elt (tree_model_sort, &tmpiter, level, elt);
425
  
426 427 428 429 430
  offset = elt->offset;

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

446
  g_array_insert_val (level->array, index, tmp);
447
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
448
  /* FIXME: update stamp?? */
449
  
450 451
  gtk_tree_path_free (path);
  if (free_s_path)
452
    gtk_tree_path_free (start_s_path);
453 454
}

455 456 457 458 459
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
460
{
461 462
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  GtkTreePath *path;
463
  GtkTreeIter iter;
464

465
  g_return_if_fail (s_path != NULL || s_iter != NULL);
466
  
467 468
  if (!s_path)
    s_path = gtk_tree_model_get_path (s_model, s_iter);
Jonathan Blandford's avatar
Jonathan Blandford committed
469

470 471
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort)
      && tree_model_sort->root)
472
    {
473 474 475 476 477 478 479
      gtk_tree_model_sort_free_level (tree_model_sort,
				      SORT_LEVEL (tree_model_sort->root));
      tree_model_sort->root = NULL;
    }
  else
    {
      GtkTreeIter real_s_iter;
480

481 482 483 484
      if (!s_iter)
	gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
      else
	real_s_iter = (* s_iter);
485

486 487 488 489
      if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					     s_path, &real_s_iter))
	return;
    }
490

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

494 495
  path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							 s_path);
496
  
497
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
498
    return;
499

500
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
501
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
502
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
503
  gtk_tree_path_free (path);
504 505 506
}

static void
507 508 509 510
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
511 512
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
513 514 515
  GtkTreePath *path;
  GtkTreeIter iter;
  gboolean free_s_path = FALSE;
516

517
  g_return_if_fail (s_path != NULL || s_iter != NULL);
518

519 520 521 522 523
  /* we don't handle signals which we don't cover */
  if (!tree_model_sort->root)
    return;

  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
524
    {
525 526
      gtk_tree_model_sort_free_level (tree_model_sort,
				      SORT_LEVEL (tree_model_sort->root));
527 528 529
      tree_model_sort->root = NULL;
    }

530
  if (!s_path)
531 532 533 534
    {
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
    }
535

536 537 538
  path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							 s_path);
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
539
    return;
540
  
541
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
542 543
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path,
					&iter);
544
  gtk_tree_path_free (path);
545
  
546 547
  if (free_s_path)
    gtk_tree_path_free (s_path);
548 549 550
}

static void
551 552 553
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
554 555
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
556
  GtkTreePath *path;
557

558 559 560 561
  /* we don't handle signals which we don't cover */
  if (!tree_model_sort->root)
    return;

562
  g_return_if_fail (s_path != NULL);
563 564
  path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							 s_path);
565 566
  g_return_if_fail (path != NULL);

567
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
568
    {
569 570
      gtk_tree_model_sort_free_level (tree_model_sort,
				      SORT_LEVEL (tree_model_sort->root));
571 572
      tree_model_sort->root = NULL;
    }
573 574 575
  else
    {
      SortElt *elt;
576 577
      SortLevel *level;
      GtkTreeIter iter;
578 579
      gint offset;
      gint i;
580 581 582 583 584
      
      gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
			       &iter, path);
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
585
      offset = elt->offset;
586 587 588 589 590 591 592 593 594 595 596

      if (level->array->len == 1)
	{
	  //	  if (SORT_ELT (level->array->data)->parent == NULL)
	  if (level->parent_elt == NULL)
	    tree_model_sort->root = NULL;
	  else
	    //	    (SORT_ELT (level->array->data)->parent)->children = NULL;
	    level->parent_level->array = NULL;
	  gtk_tree_model_sort_free_level (tree_model_sort, level);
	}
597
      else
598 599 600
	{
	  for (i = 0; i < level->array->len; i++)
	    if (elt->offset == g_array_index (level->array, SortElt, i).offset)
601 602
	      break;

603 604
	  g_array_remove_index (level->array, i);

605
	  /* update all offsets */
606 607 608 609 610 611 612
	  for (i = 0; i < level->array->len; i++)
	    {
	      elt = & (g_array_index (level->array, SortElt, i));
	      if (elt->offset > offset)
		elt->offset--;
	    }
	}
613 614
    }

615
  gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
616
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
617
  gtk_tree_path_free (path);
618 619
}

620
static void
621 622 623 624 625
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
626
{
627 628 629 630 631 632 633 634
  int i;
  int len;
  int *my_new_order;
  SortElt *elt;
  SortLevel *level;
  gboolean free_s_path = FALSE;
  
  GtkTreeIter  iter;
635 636
  GtkTreePath *path;

637 638
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  
639 640
  g_return_if_fail (s_path != NULL || s_iter != NULL);
  g_return_if_fail (new_order != NULL);
641

642
  if (!s_path)
643 644 645 646 647
    {
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
    }

648 649 650 651 652 653
  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)
654 655 656 657 658 659 660
    {
      if (free_s_path)
	gtk_tree_path_free (s_path);
      return;
    }

  /** get correct sort level **/
661

662
  if (!gtk_tree_path_get_indices (s_path))
663 664
    level = SORT_LEVEL (tree_model_sort->root);
  else
665
    {
666 667 668 669
      path = gtk_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							     s_path);
      
      if (!path)
670
	{
671 672
	  if (free_s_path)
	    gtk_tree_path_free (s_path);
673 674
	  return;
	}
675

676
      if (!gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path))
677
	{
678 679 680 681 682
	  /* no iter for me */
	  if (free_s_path)
	    gtk_tree_path_free (s_path);
	  gtk_tree_path_free (path);
	  return;
683 684
	}
      
685 686
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
687 688
      gtk_tree_path_free (path);

689
      /* FIXME: is this needed ? */
690 691 692 693 694 695
      if (!s_iter)
	gtk_tree_model_get_iter (s_model, s_iter, s_path);

      if (!elt->children)
	return;

696 697 698 699 700 701 702 703 704 705 706
      level = elt->children;
    }

  if (!level)
    {
      if (free_s_path)
	gtk_tree_path_free (s_path);

      /* ignore signal */
      return;
    }
707

708 709 710 711
  if (len != level->array->len)
    {
      if (free_s_path)
	gtk_tree_path_free (s_path);
712

713 714 715 716 717 718 719 720 721 722 723
      /* length mismatch, pretty bad, shouldn't happen */
      g_warning ("length mismatch!");
      
      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);
724

725 726 727 728
      if (!path)
	{
	  if (free_s_path)
	    gtk_tree_path_free (s_path);
729
	  
730
	  return;
731
	}
732 733

      for (i = 0; i < level->array->len; i++)
734 735 736 737 738 739 740 741 742
	{
	  g_array_index (level->array, SortElt, i).offset = new_order[i];
	  
	  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
	    {
	      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));
	    }
	}
743 744 745 746 747 748 749
      
      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))
750
	{
751 752 753 754 755
	  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);
756
	}
757 758 759 760 761 762 763 764
      else
	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
				       path, NULL, new_order);
      
      gtk_tree_path_free (path);

      if (free_s_path)
	gtk_tree_path_free (s_path);
765

766
      return;
767 768
    }

769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787
  /** sorted: update offsets, no emission of reordered signal **/
  g_print ("B");
  for (i = 0; i < level->array->len; i++)
    g_print ("%3d", g_array_index (level->array, SortElt, i).offset);
  g_print ("\n");

  g_print ("N");
  for (i = 0; i < level->array->len; i++)
    g_print ("%3d", new_order[i]);
  g_print ("\n");

  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];

  g_print ("A");
  for (i = 0; i < level->array->len; i++)
    g_print ("%3d", g_array_index (level->array, SortElt, i).offset);
  g_print ("\n");
788
  
789
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
790

791 792 793 794 795 796 797 798 799 800 801
  if (free_s_path)
    gtk_tree_path_free (s_path);
}

/* 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;
802 803
}

804 805 806
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
807 808
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

809
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
810 811 812

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

814
  return gtk_tree_model_get_n_columns (GTK_TREE_MODEL_SORT (tree_model)->child_model);
815 816 817 818
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
819
                                     gint          index)
820 821
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
822
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
823

824
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
825 826 827
}

static gboolean
828 829 830
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
831
{
832 833 834 835
  GtkTreeModelSort *tree_model_sort;
  gint *indices;
  SortLevel *level;
  gint depth, i;
836

837 838
  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);
839

840 841 842 843 844 845 846 847 848
  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)
849
    return FALSE;
850

851
  for (i = 0; i < depth - 1; i++)
852
    {
853 854 855
      if ((level == NULL) ||
	  (level->array->len < indices[i]))
	return FALSE;
856

857 858 859
      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;
860 861
    }

862 863 864 865 866
  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]);
867

868
  return TRUE;
869 870 871 872
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
873
			      GtkTreeIter  *iter)
874
{
875 876 877 878
  GtkTreePath *retval;
  SortLevel *level;
  SortElt *elt;

879
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
880
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
881
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
882

883 884 885 886
  retval = gtk_tree_path_new ();
  level = iter->user_data;
  elt = iter->user_data2;
  while (level != NULL)
887
    {
888 889 890 891
      gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);

      elt = level->parent_elt;
      level = level->parent_level;
892
    }
893 894

  return retval;
895 896 897 898
}

static void
gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
899 900 901
			       GtkTreeIter  *iter,
			       gint          column,
			       GValue       *value)
902
{
903
  GtkTreeIter child_iter;
904 905

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

909
  GET_CHILD_ITER (tree_model, &child_iter, iter);
910 911
  gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
			    &child_iter, column, value);
912 913 914 915
}

static gboolean
gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
916
			       GtkTreeIter  *iter)
917
{
918
  SortLevel *level;
919 920 921
  SortElt *elt;

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
922
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
923 924
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

925 926
  level = iter->user_data;
  elt = iter->user_data2;
927

928
  if (elt - (SortElt *)level->array->data >= level->array->len - 1)
929 930 931 932
    {
      iter->stamp = 0;
      return FALSE;
    }
933
  iter->user_data2 = elt + 1;
934

935 936 937 938 939
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
940 941
				   GtkTreeIter  *iter,
				   GtkTreeIter  *parent)
942
{
943 944
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
945 946

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
947 948
  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
949

950 951
  if (parent == NULL)
    {
952

953 954 955 956
      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;
957

958 959 960 961 962
      level = tree_model_sort->root;
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = level;
      iter->user_data2 = level->array->data;
    }
963
  else
964
    {
965 966 967 968 969
      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)
970
	return FALSE;
971 972 973
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = ((SortElt *)parent->user_data2)->children;
      iter->user_data2 = ((SortLevel *)iter->user_data)->array->data;
974 975
    }
  
976 977 978 979 980
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
981
				    GtkTreeIter  *iter)
982
{
983
  GtkTreeIter child_iter;
984 985

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
986
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
987 988
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

989
  GET_CHILD_ITER (tree_model, &child_iter, iter);
990

991
  return gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
992 993 994 995 996 997
}

static gint
gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
				     GtkTreeIter  *iter)
{
998
  GtkTreeIter child_iter;
999 1000

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
1001
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
1002
  if (iter) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, 0);
1003

1004 1005
  if (iter == NULL)
    return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, NULL);
1006

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

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

static gboolean
gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
1014 1015 1016
				    GtkTreeIter  *iter,
				    GtkTreeIter  *parent,
				    gint          n)
1017
{
1018
  SortLevel *level;
1019 1020

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

1023 1024
  if (gtk_tree_model_sort_iter_children (tree_model, iter, parent) == FALSE)
    return FALSE;
1025

1026 1027
  level = iter->user_data;
  if (n >= level->array->len)
1028
    {
1029 1030
      iter->stamp = 0;
      return FALSE;
1031 1032
    }

1033
  iter->user_data2 = &g_array_index (level->array, SortElt, n);
1034 1035 1036 1037 1038
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
1039 1040
				 GtkTreeIter  *iter,
				 GtkTreeIter  *child)
1041
{
1042
  SortLevel *level;
1043 1044

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1045
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1046 1047
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == child->stamp, FALSE);

1048
  level = child->user_data;
1049

1050
  if (level->parent_level)
1051 1052
    {
      iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
1053 1054 1055
      iter->user_data = level->parent_level;
      iter->user_data2 = level->parent_elt;

1056 1057 1058 1059 1060 1061
      return TRUE;
    }
  return FALSE;
}

static void
1062
gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
1063
			      GtkTreeIter  *iter)
1064
{
1065 1066
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
1067 1068 1069 1070 1071 1072
  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);

1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097
  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);
    }
1098 1099 1100
}

static void
1101
gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
1102
				GtkTreeIter  *iter)
1103
{
1104 1105
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
1106
  SortElt *elt;
1107

1108 1109 1110
  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);
1111 1112 1113 1114 1115 1116 1117

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

  elt->ref_count--;
  level->ref_count--;
  if (level->ref_count == 0)
1118
    {
1119 1120 1121 1122
      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
1123
	{
1124 1125 1126 1127 1128 1129 1130 1131 1132 1133
	  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;
	    }
1134
	}
1135
      while (parent_level);
1136
    }
1137 1138
}