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

  /* Properties */
  g_object_class_install_property (object_class,
                                   PROP_MODEL,
                                   g_param_spec_object ("model",
328 329
							P_("TreeModelSort Model"),
							P_("The model for the TreeModelSort to sort"),
330 331
							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)
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
      if (level == tree_model_sort->root)
	tree_model_sort->root = NULL;
816 817
      return;
    }
818

819 820
  gtk_tree_model_sort_increment_stamp (tree_model_sort);

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

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

  gtk_tree_path_free (path);
839 840
}

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

856
  g_return_if_fail (new_order != NULL);
857

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

872 873
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
874 875

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

881 882 883
      level = elt->children;
    }

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

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

904 905
  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
906
    {
907

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

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

Jonathan Blandford's avatar
Jonathan Blandford committed
927
  gtk_tree_path_free (path);
928 929 930
}

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

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

  return 0;
945 946
}

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

952
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
953 954 955

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

957
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
958 959 960 961
}

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

967
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
968 969 970
}

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

980 981
  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);
982

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

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

1000 1001 1002
      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;
1003 1004
    }

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

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

1015
  return TRUE;
1016 1017 1018 1019
}

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

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

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

      elt = level->parent_elt;
      level = level->parent_level;
1039
    }
1040 1041

  return retval;
1042 1043 1044 1045
}

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

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

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

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

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

1072 1073
  level = iter->user_data;
  elt = iter->user_data2;
1074

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

1082 1083 1084 1085 1086
  return TRUE;
}

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

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

1098 1099 1100 1101 1102 1103
  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;
1104

1105 1106 1107 1108 1109
      level = tree_model_sort->root;
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = level;
      iter->user_data2 = level->array->data;
    }
1110
  else
1111
    {
1112 1113 1114 1115 1116
      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)
1117
	re