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

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

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

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

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
#include "gtktreednd.h"
48 49

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

54 55
struct _SortElt
{
56 57 58 59 60 61 62 63 64 65 66 67 68
  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;
69 70
};

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

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

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



96 97 98 99 100 101
#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);
102

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

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

107
/* general (object/interface init, etc) */
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);
112
static void gtk_tree_model_sort_drag_source_init      (GtkTreeDragSourceIface*iface);
113
static void gtk_tree_model_sort_finalize              (GObject               *object);
114 115 116 117 118 119 120 121
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);
122

123
/* our signal handlers */
124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
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);
144 145

/* TreeModel interface */
146
static GtkTreeModelFlags gtk_tree_model_sort_get_flags     (GtkTreeModel          *tree_model);
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
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);
177 178 179
static void         gtk_tree_model_sort_real_unref_node    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
							    gboolean               propagate_unref);
180 181 182
static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);

183 184 185 186 187 188 189 190 191
/* TreeDragSource interface */
static gboolean     gtk_tree_model_sort_row_draggable         (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path);
static gboolean     gtk_tree_model_sort_drag_data_get         (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path,
							       GtkSelectionData       *selection_data);
static gboolean     gtk_tree_model_sort_drag_data_delete      (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path);

192
/* TreeSortable interface */
193 194 195 196 197 198 199 200 201 202 203
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);
204 205 206 207 208
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);
209

210
/* Private functions (sort funcs, level handling and other utils) */
211 212 213 214 215 216 217 218 219 220 221
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);
222 223 224
static gint         gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *level,
							   GtkTreeIter      *iter,
Kristian Rietveld's avatar
Kristian Rietveld committed
225
							   gint             skip_index);
226
static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
227
							   SortLevel        *level,
228 229
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
230 231 232 233
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);
234 235 236
static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
									 GtkTreePath      *child_path,
									 gboolean          build_levels);
237

238
static GObjectClass *parent_class = NULL;
239

240
GType
241 242
gtk_tree_model_sort_get_type (void)
{
243
  static GType tree_model_sort_type = 0;
244

245 246 247 248 249
  if (!tree_model_sort_type)
    {
      static const GTypeInfo tree_model_sort_info =
      {
        sizeof (GtkTreeModelSortClass),
250 251
        NULL,           /* base_init */
        NULL,           /* base_finalize */
252
        (GClassInitFunc) gtk_tree_model_sort_class_init,
253 254
        NULL,           /* class_finalize */
        NULL,           /* class_data */
255
        sizeof (GtkTreeModelSort),
256
        0,              /* n_preallocs */
257 258 259 260 261
        (GInstanceInitFunc) gtk_tree_model_sort_init
      };

      static const GInterfaceInfo tree_model_info =
      {
262 263 264
        (GInterfaceInitFunc) gtk_tree_model_sort_tree_model_init,
        NULL,
        NULL
265 266
      };

267 268
      static const GInterfaceInfo sortable_info =
      {
269 270 271
        (GInterfaceInitFunc) gtk_tree_model_sort_tree_sortable_init,
        NULL,
        NULL
272 273
      };

274 275 276 277 278 279 280
      static const GInterfaceInfo drag_source_info =
      {
        (GInterfaceInitFunc) gtk_tree_model_sort_drag_source_init,
        NULL,
        NULL
      };

Manish Singh's avatar
Manish Singh committed
281 282 283 284
      tree_model_sort_type =
	g_type_register_static (G_TYPE_OBJECT, "GtkTreeModelSort",
				&tree_model_sort_info, 0);

285
      g_type_add_interface_static (tree_model_sort_type,
286 287
                                   GTK_TYPE_TREE_MODEL,
                                   &tree_model_info);
288

289
      g_type_add_interface_static (tree_model_sort_type,
290 291
                                   GTK_TYPE_TREE_SORTABLE,
                                   &sortable_info);
292 293 294 295

      g_type_add_interface_static (tree_model_sort_type,
                                   GTK_TYPE_TREE_DRAG_SOURCE,
                                   &drag_source_info);
296 297 298 299 300 301
    }

  return tree_model_sort_type;
}

static void
302 303 304 305 306 307 308 309 310 311 312
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)
313 314 315
{
  GObjectClass *object_class;

316
  object_class = (GObjectClass *) class;
317
  parent_class = g_type_class_peek_parent (class);
318

319 320 321
  object_class->set_property = gtk_tree_model_sort_set_property;
  object_class->get_property = gtk_tree_model_sort_get_property;

322
  object_class->finalize = gtk_tree_model_sort_finalize;
323 324 325 326 327 328 329 330 331

  /* 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));
332 333 334 335 336
}

static void
gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
{
337
  iface->get_flags = gtk_tree_model_sort_get_flags;
338 339 340 341 342 343 344 345 346 347 348
  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;
349 350
  iface->ref_node = gtk_tree_model_sort_ref_node;
  iface->unref_node = gtk_tree_model_sort_unref_node;
351 352
}

353 354 355 356 357
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;
358
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
359 360
  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;
361 362
}

363 364 365 366 367 368 369 370
static void
gtk_tree_model_sort_drag_source_init (GtkTreeDragSourceIface *iface)
{
  iface->row_draggable = gtk_tree_model_sort_row_draggable;
  iface->drag_data_delete = gtk_tree_model_sort_drag_data_delete;
  iface->drag_data_get = gtk_tree_model_sort_drag_data_get;
}

371 372 373 374 375 376 377 378
/**
 * 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.
 */
379
GtkTreeModel *
380
gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
381 382 383
{
  GtkTreeModel *retval;

384 385
  g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);

Manish Singh's avatar
Manish Singh committed
386
  retval = g_object_new (gtk_tree_model_sort_get_type (), NULL);
387

388
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
389 390 391 392

  return retval;
}

393 394 395
/* GObject callbacks */
static void
gtk_tree_model_sort_finalize (GObject *object)
396
{
397
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
398

399 400
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

401
  if (tree_model_sort->root)
402
    gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
403 404 405 406 407 408

  if (tree_model_sort->sort_list)
    {
      _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
      tree_model_sort->sort_list = NULL;
    }
409 410 411

  /* must chain up */
  parent_class->finalize (object);
412 413
}

414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451
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;
    }
}

452
static void
453
gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
454 455
				 GtkTreePath  *start_s_path,
				 GtkTreeIter  *start_s_iter,
456
				 gpointer      data)
457 458
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
459
  GtkTreePath *path = NULL;
460
  GtkTreeIter iter;
461
  GtkTreeIter tmpiter;
462

463
  SortElt tmp;
464 465
  SortElt *elt;
  SortLevel *level;
466

467 468
  gboolean free_s_path = FALSE;

Kristian Rietveld's avatar
Kristian Rietveld committed
469
  gint index = 0, old_index, i;
470 471

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

473
  if (!start_s_path)
474 475
    {
      free_s_path = TRUE;
476
      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
477
    }
478

479 480 481
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      start_s_path,
							      FALSE);
482
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
483 484
    {
      if (free_s_path)
485
	gtk_tree_path_free (start_s_path);
Jonathan Blandford's avatar
Jonathan Blandford committed
486 487
      return;
    }
Jonathan Blandford's avatar
sync  
Jonathan Blandford committed
488

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

491 492
  level = iter.user_data;
  elt = iter.user_data2;
493

494 495 496
  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))
497 498
    {
      if (free_s_path)
499
	gtk_tree_path_free (start_s_path);
500

501
      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
502

503
      gtk_tree_path_free (path);
504

505 506 507
      return;
    }

508
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
509 510 511 512
    {
      gtk_tree_model_get_iter (tree_model_sort->child_model,
			       &tmpiter, start_s_path);
    }
513

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

516
  memcpy (&tmp, elt, sizeof (SortElt));
517

518 519 520
  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
521
						   &tmp.iter,
Kristian Rietveld's avatar
Kristian Rietveld committed
522
						   old_index);
523
  else
524 525
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
526
						   &tmpiter,
Kristian Rietveld's avatar
Kristian Rietveld committed
527
						   old_index);
528

529 530 531 532 533 534 535 536 537 538 539 540 541 542
  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));
543

544 545 546
  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);
547

548 549
  gtk_tree_path_up (path);
  gtk_tree_path_append_index (path, index);
550

551
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
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 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611
  /* 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);
612 613
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);

614 615
  gtk_tree_path_free (path);
  if (free_s_path)
616
    gtk_tree_path_free (start_s_path);
617 618
}

619 620 621 622 623
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
624
{
625 626
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  GtkTreePath *path;
627
  GtkTreeIter iter;
628 629 630 631 632 633 634 635 636 637 638
  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);
639

640
  g_return_if_fail (s_path != NULL || s_iter != NULL);
641

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

648 649
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
650
  else
651
    real_s_iter = *s_iter;
652

653 654 655
  if (!tree_model_sort->root)
    {
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
656

657 658
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
659

660
      goto done_and_submit;
661
    }
662

663 664 665
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
666 667
      gint j;

668 669 670 671 672
      if (!level)
	{
	  /* level not yet build, we won't cover this signal */
	  goto done;
	}
673

674 675 676 677 678 679 680
      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;
	}
681

682 683 684 685 686 687 688 689 690
      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);
691 692 693 694 695

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

697 698 699 700 701
	  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);
702 703 704 705 706 707 708
	  if (tmppath)
	    {
	      gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data),
						    tmppath,
						    &tmpiter);
	      gtk_tree_path_free (tmppath);
	    }
709

710 711 712 713 714 715 716 717
	  /* not covering this signal */
	  goto done;
	}

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

719
  if (!parent_level)
720
    goto done;
721

722 723 724 725 726
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
727

728
 done_and_submit:
729 730 731
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
732

733
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
734
    return;
735

736
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
737

738
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
739
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
740
  gtk_tree_path_free (path);
741

742
 done:
743 744
  if (free_s_path)
    gtk_tree_path_free (s_path);
745

746
  return;
747 748 749
}

static void
750 751 752 753
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
754 755
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
756 757
  GtkTreePath *path;
  GtkTreeIter iter;
758

759
  g_return_if_fail (s_path != NULL && s_iter != NULL);
760

761 762
  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
763
    return;
764

765
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
766
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
767

768
  gtk_tree_path_free (path);
769 770
}

771
/* FIXME: I still have doubts if this works */
772
static void
773 774 775
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
776 777
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
778
  GtkTreePath *path = NULL;
779 780 781 782 783
  SortElt *elt;
  SortLevel *level;
  GtkTreeIter iter;
  gint offset;
  gint i;
784

785
  g_return_if_fail (s_path != NULL);
786

787 788
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
789 790
    return;

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

793 794 795 796
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

797 798 799 800 801 802 803 804
  /* 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);

805
  while (elt->ref_count > 0)
806
    gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
807

808
  if (level->ref_count == 0 && level != tree_model_sort->root)
809
    {
810 811
      /* This will prune the level, so I can just emit the signal and not worry
       * about cleaning this level up. */
812
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
813
      gtk_tree_path_free (path);
814 815
      return;
    }
816

817 818
  gtk_tree_model_sort_increment_stamp (tree_model_sort);

819 820 821 822 823 824
  /* 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);
825

826 827 828 829 830 831
  /* 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--;
832 833
      if (elt->children)
	elt->children->parent_elt = elt;
834
    }
835 836

  gtk_tree_path_free (path);
837 838
}

839
static void
840 841 842 843 844
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
845
{
846 847
  SortElt *elt;
  SortLevel *level;
Jonathan Blandford's avatar
Jonathan Blandford committed
848 849
  GtkTreeIter iter;
  gint *tmp_array;
850
  int i, j;
851
  GtkTreePath *path;
852
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
853

854
  g_return_if_fail (new_order != NULL);
855

Jonathan Blandford's avatar
Jonathan Blandford committed
856
  if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
857
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
858 859
      if (tree_model_sort->root == NULL)
	return;
Jonathan Blandford's avatar
Jonathan Blandford committed
860
      path = gtk_tree_path_new ();
Jonathan Blandford's avatar
Jonathan Blandford committed
861
      level = SORT_LEVEL (tree_model_sort->root);
862 863
    }
  else
864
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
865 866 867 868
      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);
869

870 871
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
872 873

      if (!elt->children)
Jonathan Blandford's avatar
Jonathan Blandford committed
874 875 876 877
	{
	  gtk_tree_path_free (path);
	  return;
	}
878

879 880 881
      level = elt->children;
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
882
  if (level->array->len < 2)
883
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
884 885 886
      gtk_tree_path_free (path);
      return;
    }
887

Jonathan Blandford's avatar
Jonathan Blandford committed
888 889
  tmp_array = g_new (int, level->array->len);
  for (i = 0; i < level->array->len; i++)
890 891 892 893 894 895 896 897
    {
      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
898 899 900
  for (i = 0; i < level->array->len; i++)
    g_array_index (level->array, SortElt, i).offset = tmp_array[i];
  g_free (tmp_array);
901

902 903
  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
904
    {
905

906 907
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
Owen Taylor's avatar
Owen Taylor committed
908
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
909

910
      if (gtk_tree_path_get_depth (path))
911
	{
912 913 914 915 916
	  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);
917
	}
918
      else
919 920 921 922
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
923 924
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
925
  gtk_tree_path_free (path);
926 927 928
}

/* Fulfill our model requirements */
929
static GtkTreeModelFlags
930 931
gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
{
932 933
  GtkTreeModelFlags flags;

934
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
935 936 937 938 939 940
  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;
941 942

  return 0;
943 944
}

945 946 947
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
948 949
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

950
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
951 952 953

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

955
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
956 957 958 959
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
960
                                     gint          index)
961 962
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
963
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
964

965
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
966 967 968
}

static gboolean
969 970 971
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
972
{
973 974 975 976
  GtkTreeModelSort *tree_model_sort;
  gint *indices;
  SortLevel *level;
  gint depth, i;
977

978 979
  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);
980

981 982 983 984 985 986 987 988 989
  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)
990
    return FALSE;
991

992
  for (i = 0; i < depth - 1; i++)
993
    {
994
      if ((level == NULL) ||
995
	  (indices[i] >= level->array->len))
996
	return FALSE;
997

998 999 1000
      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;
1001 1002
    }

1003 1004 1005 1006 1007 1008
  if (!level || indices[i] >= level->array->len)
    {
      iter->stamp = 0;
      return FALSE;
    }

1009 1010 1011
  iter->stamp = tree_model_sort->stamp;
  iter->user_data = level;
  iter->user_data2 = &g_array_index (level->array, SortElt, indices[depth - 1]);
1012

1013
  return TRUE;
1014 1015 1016 1017
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
1018
			      GtkTreeIter  *iter)
1019
{
1020 1021 1022 1023
  GtkTreePath *retval;
  SortLevel *level;
  SortElt *elt;

1024
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
1025
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
1026
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
1027

1028 1029 1030 1031
  retval = gtk_tree_path_new ();
  level = iter->user_data;
  elt = iter->user_data2;
  while (level != NULL)
1032
    {
1033 1034 1035 1036
      gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);

      elt = level->parent_elt;
      level = level->parent_level;
1037
    }
1038 1039

  return retval;
1040 1041 1042 1043
}

static void
gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
1044 1045 1046
			       GtkTreeIter  *iter,
			       gint          column,
			       GValue       *value)
1047
{
1048
  GtkTreeIter child_iter;
1049 1050

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

1054
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1055 1056
  gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
			    &child_iter, column, value);
1057 1058 1059 1060
}

static gboolean
gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
1061
			       GtkTreeIter  *iter)
1062
{
1063
  SortLevel *level;
1064 1065 1066
  SortElt *elt;

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1067
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1068 1069
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

1070 1071
  level = iter->user_data;
  elt = iter->user_data2;
1072

1073
  if (elt - (SortElt *)level->array->data >= level->array->len - 1)
1074 1075 1076 1077
    {
      iter->stamp = 0;
      return FALSE;
    }
1078
  iter->user_data2 = elt + 1;
1079

1080 1081 1082 1083 1084
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
1085 1086
				   GtkTreeIter  *iter,
				   GtkTreeIter  *parent)
1087
{
1088 1089
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
1090

1091
  iter->stamp = 0;
1092
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1093 1094
  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
1095

1096 1097 1098 1099 1100 1101
  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;
1102

1103 1104 1105 1106 1107
      level = tree_model_sort->root;
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = level;
      iter->user_data2 = level->array->data;
    }
1108
  else
1109
    {
1110 1111 1112 1113 1114
      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)
1115
	return FALSE;
1116 1117 1118
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = ((SortElt *)parent->user_data2)->children;
      iter->user_data2 = ((SortLevel *)iter->user_data)->array->data;
1119
    }